# AI筆記 (期末考)
###### tags: `課堂筆記`

# Chap 19

## Supervised Learning (監督式學習）

* 給定 N 個 pairs ， 共有輸入以及結果，我們的目標為找到一個f 去逼近x 的真實取縣
:::success
這邊給予學習的定義：

如果學習的東西會得出 布林值的話，那這個問題為（classification）分類問題
如果學習的東西會得出 實數 的話，那這個問題為（Regression）回歸問題
:::

* Ockham's razor is: to
**prefer the simplest hypothesis consistent with the data**

## Learning Decision Trees
* 他是一種 Greedy divide_and_conquer 演算法，每次都會找最重要的 **參數** 參考
* 可以得到一個 **還算不錯** 的解法
* 每次進到下一層都會得到少一個參數(因為前一層把她拔掉了）

Pseudo code 如下：

function Decision_Tree_Learning(examples, attributes, parent_examples){
// 	It returns a Tree
	if(example == 'empty') return Plurality_Value(parent_examples);
	else if(all examples have the same classification) return the classification;
	else if(attributes == 'empty') return Plurality_Value(examples)
	else{
		A = argmax_Importance(a,examples);
		tree = {a new decision tree with root test A};
		for v in A{
			exs = {every e}
			subtree = Decision_Tree_Learning(exs,attr-A,examples)
			// add a branch to tree with label (A = v_k)
		}
		return tree
		
		
		
	}
}
// Plurality_Value selects the most common output value among a set of examples braking ties randomly

## Entropy 的意義：
- 通常，這個可以用來表示一個空間裡面的亂度，如果數值越大，這個空間裡面包含的東西越多，而且會越亂

## Evaluating and Choosing the Best Hyphothesis
* 我們必須要定義甚麼是 "future data" 以及 "best"，我們先利用簡易的定義：
* There is a probability distribution over examples that remains stationary over time
* 並且假設每一個E_J都是獨立且相同的
* 符合以上的假設我們稱它做 Independent and identically distributed : i.i.d
:::info
K-fold Cross-validation:

首先把所有資料分成K個子集合，然後對她做K個回合的學習
每一次使用1/k 個資料點來做訓練，其他都當作驗證集
**當K = n 的時候，我們稱它做 Leave-one-out cross-validation**
LOOCV

當整體資料少得可憐的時候，LOOCV很重要
但是一直調參數，會導致data peeking的問題，而且訓練不夠嚴謹
:::
也因以上的data peeking 的問題，如此一來我們現代的訓練通常都把它分成三個集合

* training
* testing
* validation

### 到底要怎麼選model, model selection
* 複雜度的問題，太高--> overfitting
太低 --> too general
### 在計算 Error rate 的時候，如果考慮加權，可以更好的表示 F 的能力
* 假設有一個(x,y)出現的機率很低，這樣搞到loss 中會倒至學習效果不好
* 於是我們利用 GenLoss(h) 來表示你的Loss Function
* 
* 它的目的就是把所有機率都加總之後再考慮loss

但是大部分的時候我們都不知道資料要怎麼樣有加權直，所以利用平均數可以比較好(比較快）的表示loss
**EmpLoss**
基本上就是Loss 加總之後除N

## L1 regularization
* it Tends to produce a sparce model

## Linearly separable 代表，如果這個資料可以被一條直線分類，即是

## linearly separable 太武斷了，可以使其軟化(softening)，利用logistic function

如此一來，對於graph的描述可以變成曲線的型態，這樣一來，我們labeling的時候得到就不會是0 1 這種武斷的結果

最開始是假設內積 大於某個threadhold ，他就是1 反之則0

* 用這種logistic 方法去找出output 這種方法就是logistic regression
* Learning rate 可以經由a(t) = 1000/(1000 + t) 隨著iteration 時間越長越小

## Nonparametric Model (不具參數性的模型)
* 之前都在描述有參數的模組，也就是如果有參數的話，就可以描述這個麼型，但這邊無法
* 我們不去找這些餐數，而我們用資料表示資料本身的特性
:::success
這個做法也稱作 Instance_based learning or memory based learning
:::
最簡單的作法為 ==查表法==
但如果用查表法的話，我們永遠都不知道X如果不再表中我們要怎麼做

## K-Nearest neighbor models

以分類來說，我們先找出K個鄰居，找到他們的特性(通常是奇數)
==以資料本身表示==

* 這邊有個很好玩的距離算法
* 雖然我們已經很熟悉歐式空間的距離了，那我們可以用其他方法算距離
* Minkowski distance 在 L$p 的空間
* 

而這個圖片，
當p = 1的時候為 **Manhattan distance**
當p = 2的時候為 **Euclidean distance**
而在input 只有boolean val的時候，我們把她稱作為 hamming distance

* K-Nearest 中，每次找鄰居實在非常沒有效率，於是有一個方法叫做k-d tree 可以有效率地找到鄰居
* 找的方法為：
* 利用一個tree來代表
* 先利用一個col/row 來討論，然後開始一一放入tree中，之後就可以用這種方法來找

https://blog.yucheng.me/post/kd-tree/

* 還有另外一個方法 Locality-sensitive hash 是利用一系列的hashfunction來幫忙找

## 另外一個 Non parametric model -- SVM Support Vector Machine
### 目標為找到 decision boundry
* SVM 利用 Kernel trick來對資料進行大改
* SVM 利用超平面\\
* 那甚麼是 Kernel trick?
* 經由數學模型推出來的 alpha (support vector) 可以幫忙帶入參數模型的優點

:::success
Kernel trick
把低維度的向量進行內積，在平方，跟把vector 對應到更高維的空間的內積相同
也就是 低維度丟給 function 直接吐出高維度的內積結果
:::

## Ensemble Learning (策略)

### Random forest (一堆樹)
* 隨機變動 attribute 的選擇，每次選擇隨機的中斷點來進行訓練(基本上就是決策樹)

### Stacking (堆疊法)

* 同樣的訓練資料，利用更多不同的方法(模組)來進行訓練，藉由不同的模組

### Boosting -- 19-113

* 最常見的一種，要先了解甚麼是weighted training set，在這training set中，如果w_j 越大的話，對於set的影響力會越大
* 其中一個很有名的方法為 adaboost
* 
### Online Learning

* 也是一種策略
* 當data 不是iid(資料互不干擾)時，用過去train出來的model進行判斷，跟實驗室的灌新詞的意義差不多，他假設資料跟過去的東西都有關，根據新的東西對舊的東西調整(重新訓練／建構)

### 結語： SVM 在資料集合沒有很大的時候，用NN可能還沒有很好
* 而Machine Learning 的問題在於以下兩點
* Interpretability
* 他得出的答案為啥會這樣，是否可以解釋
* Explainability
* 為甚麼input 這樣會得到 如此的output

# chap 20 -- Statistical Learning

## Key concept
* Data
* instantiations of some or all of the random variable describing the domain
* Hypothesis
* probabilistic theories of how the domain works
## Bayesian Learning
* 基本上就是 ==利用data的特性／機率，找出原本的分類==

## Maximum a posteriori (MAP hypothesis)
* [看不懂](https://chih-sheng-huang821.medium.com/%E8%B2%9D%E6%B0%8F%E6%B1%BA%E7%AD%96%E6%B3%95%E5%89%87-bayesian-decision-rule-%E6%9C%80%E5%A4%A7%E5%BE%8C%E9%A9%97%E6%A9%9F%E7%8E%87%E6%B3%95-maximum-a-posterior-map-96625afa19e7)

## Density estimation
* 意思就是利用data 觀察到的東西進而去推估模型

## Maximum-likelihood 的流程 -- 離散狀況
1. 先把likelihood 寫成 function parameters的樣子
2. 對他們作微分
3. 找微分=0的狀況

## Maximum-likelihood 流程-- 連續情況

# chap 21 -- deep learning

* Dl 相對於本來前面介紹的方法來說，存在更多資料以及運算

* feedforward network has connections only in one direction
* 整個DL可以視為一堆function的集合

## 一個Node 在幹嘛
* 在計算 input 的 weighted sum，之後丟進一個 activaction function
* 
* 目標就是把W (模組參數) 調整成可以變成預測的狀況
基本上可以寫成線性代數的樣子，變成下面這個樣子
* 當所有 node 都會連結到前一層的結果時，我們稱它做==fully connected network==
## activaction Function

* 重點之一為必須要壤他是連續的函數
* activaction function 的微分永遠不是負的
## Loss function

* 意義上來講，基本上就是預估值與實際狀況的差距 ==> 越小越好

## back propagation (反向傳遞)

* 因為對於 function Parameters，loss function 必須要把誤差傳回前面，所以存在此演算法

## Gradient Vanishing (梯度消失)
* 一旦中間有一個很接近0的 gradient，這樣會導致整個func para變成0或趨近於0

## input ? output?

* input encoding
* 表示法通常為 N 維的向量 (one-hot encoding)
* output layers and loss function
* 分類的結果
## hidden layer

* 表現的好的部分原因

## Convolutional Networks
* 在影像處理中非常重要
* 由於pixels附近的pixels也很重要，而考慮整張圖的成本又太大==> 考慮一張圖片中，一個部位(batch)，並且對她處理
* CNN構成要素：
* ==具有可以分享weight的特性 => Spatial Invariance==
* ==具有局部process的特性==
* CNN中 一種local pattern(一種遮罩／特性) 為一種kernel
* 由左到右，由上到下對於圖片進行process我們稱作[convolution](https://www.youtube.com/watch?v=KuXjwB4LzSA)
* CNN不要亂做，一開始只是因為圖像跟cnn會有關聯，所以使用CNN有意義，但在其他狀況不一定有意義

## Residual networks
* 應該不用解釋

## SGD

* 每次找一定量的batch 去做gradient decent

SGD一定有一些缺點，才會有後續的演進，在當下的問題如果學習率太大，容易造成參數更新呈現鋸齒狀的更新，這是很沒有效率的路徑。

## 反向傳遞的缺點：一路傳回去的時候，必須要用很多額外的記憶體空間儲存計算好的資料

## Batch Normalization
* 可以讓SGD收斂的速度更快
* 把同一個minibatch的output做適當的調整
* 假設z_i是output, mu是平均 gamma, beta 都是希望model可以學到的參數
* 

## adversarial example (attack)
意義為：當你在本來的input中 汙染了部分的資料，導致，雖然用人眼辨識不出來，但機器卻辨識錯誤

* 那我們的目標就是要找出更有效的方法去反制他

## Weight decay -- generalization

* 
* 把所有weight平方之後加總，但大部分的人不知道為啥有用
* 有人解釋：他可以模擬sigmoid的樣子
## Dropout-- generalization
* 隨機把一些node給停掉，具體來說：
* 你有一個p 的機率，每次有p的機率output會呈上1/p再output
* ==目標就是，遇到詭異的資料的時候會有比較高的機率可以ignore他==

## RNN

* RNN 可以讓我們再運算的過程中存在cycle，讓整個NN 有記憶性，除此之外，他做出了markov assumption(前面的資料會影響後面
這邊的W_ij 都是一樣的

## 梯度爆炸原因
* 因為在RNN 或是其他NN 具有markov assumption的狀況，如果gradient一直都大於1的狀況，就會產生梯度爆炸，他會越乘越大
* 梯度消失反之，他們都是基於markov assumption
* 必須要寫出 Back-proba over time
## LSTM (為了解決梯度消失／但無法解決梯度爆炸)
* LSTM 中存在的memory cell 用加法，可以比較有效避免梯度消失

## Unsupervised Learning
不需要從output學習模組，直接從data本身學習
* 通常只能看 沒有被標記的 x
* 算完之後，可以對於input做一些好玩的運算

### 在這之前，有個東西叫做 PPCA Probabilistic PCA
* 
* 我們假設有一個 z ，他input還要低維度，我們用這個z來表示高維度的X

### Autoencoder

1. encoder先把input (x) map到 z 上
2. decoder再把 z map到x上面，而我們預估出來的x要跟原本的x很接近
:::success
基本上就是seq2seq的概念

:::
* 他很難利用線性代數的方法表示，因為data本身不一定是線性的
* 而如果用這種方式來做的話，他實際上的意義跟PCA差不多

### GAN generative adversarial network 生成對抗網路
* generator 把 input(z) map 到 x
* discriminator 把 x 變成 real or fake的資訊 --> 他用來分辨資料是否是經過訓練的

* 語言翻譯可以利用GAN
* 先利用GAN 把x轉變成y
* 同時利用discriminator干涉
* 另外訓練一個GAN把Y轉回x
* 這個方法好處是不用很多y就可以訓練(搞不好可以用在台語翻譯上)
## Transfer learning
轉移學習就是把已經訓練好的模型、參數，轉移至另外的一個新模型上
使得我們不需要從零開始，重新訓練一個新model
* 也就是微調模型
* 也會利用梯度下降之類的方法對於新的模型做最佳化
* 很重要的點就是==可以站在巨人的肩膀上，利用很多人已經訓練好的model去做調整==
* 可以用來模擬現實世界的狀況

### Multi-task learning
- 也是一種 transfer learning

# Chap 24, deeplearning 在NLP中的貢獻
## 文字的元件
* one-hot vector
* 也就是瓊舉所有的文字，把它給予編號，在某一列是1，其他都是0
* 缺點是他們之間的co-relation不夠好(距離不好)
* word embedding
* 可以視作把vector mapping到一個新的空間(比較小)
* 如果做完這個事情之後，可以得到一種關聯 B-A = C
* word2vec, gloVe, FastText
* 其實也可以自己訓練自己的word embedding
* 也可以用其他方法進行fine tune
* word embedding 不夠，此時要看前後文
* Language Model 可以表達這個狀況
* 要如何建構？
* N-gram Language Models，FFN-language model
* N-gram無法看到更前面的問題，FNN 也有這個問題
* 可以用在語音辨識、
## seq2seq model
* 機器翻譯中的很重要的工作
* 原本seq2seq只考慮最後一個地方算出來的info，但如此會導致最後一個字的權重最高，也可能導致後面的資訊忘掉
* 此時attention機制就介入了
* 而利用一個context vector c_i 去考慮整個output
* 原本RNN長成這樣
* 後續利用context vector，整個算式變成這樣
* S![](https://i.imgur.com/wfV7D36.png
### Decoding
* 從source 訓練出來的資料，把她經由(attention) 之類的參數考慮進去之後生成的資料
* 通常採用 Greedy decoding (最高機率的字就吐出來)
* 或是用Beam Search
* 
## From Target_to_Transformer
* Transformer中的參數／會經由三個model matrix W_i 乘過去
* query vector q_i = W_q * x_i
* 可以把它視為attention
* key vector k_i = W_k * x_i
* 可以把它視為source的attention
* value vector v_i = V_i * x_i
* 沒有之前的對應，他代表著上下文的對應
* transformer -- architecture
* Multi-attention
* 會把sentence 分成m個同樣大小的碎塊，然後丟進attention model之後，每個碎塊都有自己的weight，最後在把這些weight拚在一起形成c_i
* 如果要對文字做描述，可以對於文字做positional embedding
## Transfer Learning
* 通常對於研究者來說，我們基本上無法拿到巨量的資料，所以我們拿別人訓練好的資料來進行微調

## RNN 可以做到描述上下文的word embedding

## Masked Language Models
* 有時候前文對於context有幫助，也有時候後面的東西對於context非常重要
* 為了要考慮到前後文，MLM(Masked Language Models) 有幫助，而他實作的方法就是有點像克漏字填充的方法，要求模型取出句子上下文的意義，然後猜出空白區域的文字
* 如此一來，所需要訓練資料並不用這麼多，而且不用labeling

# Ch25 -- Computer Vision
* Perception(感知)到的東西，會賦予sensors(感測器) 感受到
* 而這個章節主要要講的東西就是 ==視覺==的sensor

:::success
總共有兩個重點
* Reconstruction:
* 此agent 能否藉由感知到的東西重建這個世界
* Recognition:
* 此agent能否辨識出遇到的物體
:::
## 影像的構成：The pinhole camera(針孔攝影機)

* 攝影機會有感光的元件，
* 通常存在CMOS物件來感知光源
* 但他也會有motion blur的缺點

## Gaussian smoothing (convolution的一種變種)
詳情可以看 [but what is convolution](https://www.youtube.com/watch?v=KuXjwB4LzSA)

# Chap 22 -- Reinforcement Learning(強化學習)
* 概念圖：
* 

* action 導致環境的變動，如果這個action對於整體狀態變好的話，reinforcement learning使用了 ==Reward function== 來告訴agent 下次的action該怎麼做
* 很多時候，資料蒐集不到，所以在很東情況下，我們沒有辦法學習一個資料by data pair
* 事實上，以下棋來說，只能以最後的結果**輸贏** 來表達這個action是好還是不好
## 基本上 Reinforcement Learning就是以Reward的方法來對於模型進行調整

## Learning from Rewards

### Model_based Reinforcement learning
* 利用transition model 來判別當下做的決定是否好

### Model-free reinforcement learning

* Action-util learning:
* 利用 Q-learning(Q-function) 來判別在某個情況下會得到的utility(這邊應該是指reward)
* Policy Search
* 這個agent會自動學習一個model，他會告訴你每個states要怎麼act

### 怎麼找policy變為這個章節的一個大課題：
* 在被動式學習中，agent的policy 是被固定住的
* 而這個agent要設法學習 U_pi(s:state) utility_function ==> 意思是在此policy下做出的選擇會得到多少的reward
* 注意：此 utility function 是在一開始就要定義好的，他會經由(markov assumption) 也就是以過往紀錄來判斷state的reward值
此種找過往紀錄的方法導出了一個新的議題：
### Revisit

* 我們規定：
* 在每一個 s:state ，reward 必須要在一定的區間之內(must be bounded)
* 每一個 utility function 的 output 必須要清楚描述agent要做甚麼，而此solution又稱 ==policy==
* 以下的function 為 Bellman equation，他可以幫我們找出optimal solution of utility function
* 
## Direct utility estimation (直接性的 utility 估算)
* Reward-to-go
* The idea is that the utility of a state is defined as the expected
total reward from that state onward, and that each trial provides a sample of this quantity for
each state visited
意思是：每一個state 的utility 為前面所有reward的加總
* 
## Adaptive dynamic programming (ADP)
* ADP 可以理解成，利用dynamic programming的方法，記住每個state 的 utilities，然後再用這些值去計算出合理的reward

## Temporal-difference learning(TD)
* 可以理解為，當一個state重複出現過多次，我們去調整他的utility estimates
* 
:::warning
## 重要！ ADP跟TD的差別
* 相同點：
* 兩個都會局部性調整(local adjustments) utility estimates，只為了
* 相異點：
* ADP 會根據所有前面的資料作調整
* TD 只會根據部分資料的特性做調整
:::
## Active reinforcement Learning
* Active(活躍的) agent 必須要自己決定action
* 相比之下 Passive(被動的) agent 仰賴其他人幫忙做決定

==以下為active learning的步驟==
1. agent 必須要學會對於所有action的機率
2. 在來，必須要讓agent知道他有action的選擇(比如一個pi(s:state) 對應到很多種選擇==> output 機率)
******
大概就這樣

# 會考的
1. Describe what is the kernel trick in SVM
:::spoiler
在SVM中，我們必須要有效率的算出距離，但有時候把更高維度的向量算出他們之間的距離非常浪費計算資源，而kernel trick就是一個function 可以在低維度空間直接算出他們在高維度空間的距離的function
:::
2. Describe the idea of ensemble learning
:::spoiler
指的是以一個系統化的方式將好幾個監督式學習的模型結合在一起，目的是希望結合眾多的模型產生一個更強大的模型。
:::
3. The random forest model is a kind of ensemble learning method. Describe the idea of random forest.
:::spoiler
隨機變動 attribute 的選擇，每次選擇隨機的中斷點來進行訓練(基本上就是決策樹)
:::
1. What is overfitting
:::spoiler
是指過於緊密或精確地匹配特定資料集，以致於無法良好地調適其他資料或預測未來的觀察結果的現象
:::
2. We may suffer from overfitting when learning a decision tree. What strategies we can apply to reduce overfitting
:::spoiler
修剪(pruning)decision tree 是一個很好的做法
:::
1. In a hidden Markov model, to solve the filtering problem and the smooth problem, what is the main idea of the forward-backward algorithm that can largely reduce the time complexity
:::spoiler
Dynamic programming
:::