人工智慧導論期末整理
目錄
Chapter 19. Learning from examples
Entropy
decision tree pruning
- 從一個已經完整建好的 decision tree 開始做,將不重要的 attribute 刪除。
- 決定是否重要可從 得知,如果 代表這個 attribute 不重要,也就是 。
Statistical significance test
TBA, not something I could read
p.28 and p.29
independent and identically distributed (i.i.d.)
- 每個 sample 值與之前的 sample 直接無關
- 而且每次 sample 之間的機率分布狀況皆相同
k-fold cross validation
- 將資料分成 等分,每次皆拿一部分作為 testing,其他部分作為 training data,將每次結果取平均作為整體模型的表現
- 如果 ,這代表只使用一筆資料作為 testing,別名為 leave-one-out cross-validation (LOOCV)
expected loss
-
對於 hypothesis 和 loss function 來說,expected generalization loss(GenLoss) 為 ,而 為所有輸入輸出 (x, y) 組合
- 最佳的 hypothesis 即為上面式子中得出最小值的 ,也就是 。
-
因為實際的 未知,我們只能用 empirical loss 預測,假設一個 example set ,預測算式為
Regularization
- 也可以把 Cost 定義為 empirical loss 和 model complexity 的 weighted sum,也就是
- 此時最佳的 hypothesis
- 而 要找一個能讓 validation 判別最準確的數值。
- 透過懲罰過高 complexity 的方式定義 cost 就是regularization
Univariate(Multivariate) linear regression
??
p.46
Non-parametric model
Table lookup
- 在遇到一個輸入參數時直接尋找 training data 中是否有相同的輸入,有的話就輸出對應值;沒有的話就輸出一個預設數值。
Nearest neighbor(KNN)
-
給定一個輸入,找距離最近的 K 個數值當作數值處理的依據
- 對於 classification 來說,將每個數值做為投票,較多數的做為輸出。(因此需要 K 為奇數)
- 對於 regression 來說,可輸出所有數值的平均或是中位數。又或是使用 linear regression 的方式取值。
-
計算距離的方式是 Minkowski Distance 或稱為 ,定義為 。
- 代表是 Eulicean distance,而 代表是 Manhattan distance。
- 對於 boolean variable,兩個點的 attribute 差異稱為 Hamming distance。
- 計算 distance 的實際數字容易受到數量級的影響,因此需要先經過 normalize 的處理。
- 另一個計算 distance 的更複雜方式稱為 Mahalanobis distance
-
在資料是低維度的狀況下,KNN 的表現還算不錯;但是到了高維度,KNN 會因為很難找到距離夠近的鄰居而讓表現變得非常差。( Curse of Dimensionality )
k-dimentional tree (k-d tree)
- balanced binary tree
- 每個 node 都是將一個 attribute 做一個 threshold ,讓一半的元素落在一邊,另一半落在另一邊。
- 這方法需要非常大量的 data,至少 個資料才能很快速的查詢到需要的資料。
Locality-sensitive hashing
- 如果兩點間距離小於 ,這兩點在 hash 後落在同個 bin 的機率很高,反之亦然。
- 從 bit-string 的 subset 隨機取值作為 hash function 。
Locally weighted regression
- 給很接近輸入數值的點很高的 weight ,距離越遠 weight 越低,透過這種方式計算平均值。
- 計算 weight 的 function 稱為 kernel。
Support vector machine (SVM)
- 目標是建構出 maximum margin seperator。
- 透過 kernel function 將低維度的輸入資料映射到高維度後再進行 linear seperation。這方法叫做 kernel trick。
- SVM 是 non-parametric model。
- 一個核心點是 SVM 認為有些資料相較於其他資料更加重要,如果給這些更重要的資料更多關注可以讓整個 model generalize 得更好。
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Ensemble learning
-
將許多的 hypothesis 級合起來一起做出預測。
- 以 Classification 來說,這方法就是多數決。
- 以 Regression 來說,可以輸出這些預測的平均值。
-
Random forest 就是 decision tree 的 ensemble learning。透過隨機改變如何取 attribute 來建出不同的 tree。
- Random forest 不受 overfitting 影響。
- 經過證明,在 Random Forest 內加入越多 Tree 後,錯誤會逐漸收斂。
-
Stacked generalization(stacking) 是拿同一個 training data 在不同的 model 底下訓練,並將前面的訓練結果加入原先資料中在給下一層的 model 訓練。
-
Boosting 一開始先將所有 training data 的 weight 設為 1。每次訓練時對於分類錯誤的 trainging data 要提升對應的 weight;而分類正確的 data 則減少 weight。
- 調整完 weight 後救生成了一個新的 hypothesis ,重複直到有 K 個 hypothesis 後再互相比較表現狀況。
- 一個比較著名的 algorithm 是 ADABOOST ,只要 learning algorithm 的表現狀況比亂猜還要好,這個方法可以在足夠大的 K 之後完美的分類所有 data。
-
如果取樣不符合 i.i.d.,可以使用 online learning 的方式。也就是 agent 在當下獲取環境資訊並做出決策,然後再檢驗是否符合預設答案。
trust, intrepretability, explainability
- trust: 我們有沒有辦法信任這個 model
- intrepretability: 我們能不能解釋 model 內的那些參數產生了這個輸出。
- explainability: 我們能不能理解為何這個輸入經過這個 model 後產生了這個輸出。
Chapter 20. Learning Probabilistic Models
Statistical learning
-
Baysian learning 在給定資料的狀況下計算每個 hypothesis 的機率,並且做出預測。也就是預測的結果會使用到全部的 hypothesis,並使用這個 hypothesis 對應的機率做為 weight。
-
使用貝式定理,可在只有事前機率和 likelihood 就得到事後機率 。
- 是事前機率
- 是在特定的 hypothesis 狀況下的 likelihood,可透過 計算得到(假設取樣皆 i.i.d.)。
-
對於錯誤的 hypothesis,事後機率會逐漸趨向零;對於正確的 hypothesis,事後機率會逐漸趨向實際分布狀況。
Maximum a posteriori(MAP hypothesis)
- 直接用一個最有可能的 hypothesis 去做預測,最佳 hypothesis 的取法是讓 最大化。
- 將 最大化的過程可視為將 最小化(取 後再轉負數)。 可當成是給定 hypothesis 後需要多少 bit 才能選定這筆 data,而 可以視為需要多少 bit 才能選定這個 hypothesis。
- 這個方法則被稱為是 minimum description length(MDL),直接計算這個 hypothesis 和 data 能夠取得多少 bits 的資料。
- 如果 hypothesis space 是 uniform,MAP 就變成只需要找到一個 可以最大化 。也就是 Maximum-likelihood hypothesis ()。
Density estimation
在已知資料後,訓練一個模型的這回事。
TBA, uncertain, p.16
Naive bayes model
Bayesian parameter learning
- 先針對所有可能的 hypothesis 定義事前機率的分布狀況,這種作法稱為 hypothesis prior。當 data 開始進來後,再逐步更新 posterior probablility。
beta distribution
- 這種 distribution 定義為 , 是 normalization constant。而 uniform distribution 正是 。
Expectation-maximization algorithm
-
先隨機對於所有 data points 指派對應的 component
-
Expectation step(E-Step): 計算資料 由 component 生成的機率,也就是 ,其中 落在第 個 component 的機率,而 是第 個 component 的 weight 數值。
-
Maximization step(M-Step): 計算新的 mean, covariance, component weight。其中用到的數值 為目前 component 中的 data point 個數,以及 是所有的 data point 個數。
- E-step 可視為是計算 hidden indicator variable 的期望值,而 在 是被 component 生成時才為 1,反之為 0。
Chapter 21. Deep Learning
Vanishing gradient
- 在某些狀況下,偏微分數值會變得極小。又因為偏微分的過程需要使用到 chain rule,越前面的 layer 更容易受到這個極小值的影響讓 weight 幾乎沒辦法更新。
Spatial invariance
Convolutional neural network (CNN)
- 在空間中距離很接近的 pixel 值可以透過 kernel 的運算傳送到下一層。
- stride: 每次運算之間 kernel 中心移動的 pixel 數量。
- receptive field: 這個 neuron 接收的涵蓋範圍。
- pooling and downsampling: 透過 pooling 運算,會讓輸出的圖片稍微變小,這叫做 downsampling。
- tensor: 任意維度的陣列
- 其中 vector 就是一維的 tensor,matrix 則是二維的 tensor。
Residual network
- 將前面 layer 的資訊直接傳送到後面的 layer。

Learning algorithm
- 通常使用 Stochastic gradient decent(SGD),透過 SGD 的隨機性讓學習過程不容易停在 local minimum。
- 另一個方法是使用 momentum,把前面幾次的數據納入考量後加入更新數值內。
Generalization
Recurrent neural network(RNN)
- 將之前訓練的結果往回接到前面的 layer,讓這些成果可以在新的 input 就有影響。
- Markov assumption: 每個 hidden state 都可以從之前的 input 取得足夠多的資料。
- 表示 Grediant 的式子有 recursive 的特性,因此也稱為 back-propagation through time。
- 其中包含了一個與 成正比的項,如果這個值小於 1,可能會發生 vanishing gradient 的問題;如果這個值大於 1,則會發生 exploding gradient 的問題。

Chapter 24. Deep Learning for Natural Language Processing
one-hot vector
- 來表示目前的字詞,但是這個方法沒辦法描述各個字之間的相似度。
word-embedding
- 這個方式可以讓模型學習各個字之間的相似度。

bidirectional RNN
- 這個方法讓文字辨識時可以取得這個字左邊及右邊的文字。

Attention
- 讓模型學習每個字對於判別的重要性,在模型中會以機率的方式呈現。
- 同時這種機率也可以讓人更容易解釋為何模型會這樣判別。(interpretable)
decoding – beam search
- 多緒平行選擇每一步的最適合字詞,並輸出最佳的字詞組合。
masked language models(MLM)
- 將部分字詞刻意 mask 起來,要求模型可以預測這些字詞。
Chapter 25. Computer Vision
- CV 中兩大問題分別是 reconstruction 和 recognition。也就是根據圖形內容重建出世界以及辨識出圖形內的物件。
pinhole camera

- 到鏡頭的光量會受到三個因素影響
- 環境光的光強度
- 物件是面光還是背光
- 從物件反射到鏡頭內的光量
- 大多物件在反射光時會以漫反射(diffuse reflection)的方式將光反射回去;與漫反射相對地點則是鏡面反射(specular reflection)。
Edge
- edge 是影像亮度有大幅度地改變的直線或曲線。
- 一個偵測 edge 的方式是 gaussian filter,設計一個特殊的 kernel 並透過 convolution 的方式找到 edge。
Chapter 22. Reinforcement Learning
- agent 透過收到獎勵(reinforcement)來學習最佳的做法。
Action-utility learning
-
一個 Q-learning 的 agent 會學習一個 action-utility function(Q-function),在特定的 state 內做出最佳的 action。
- 而從對應的 state 到 action 的過程就是 policy,找到最佳的 policy 就是 policy search。
-
在 passive reinforcement learning 的狀況下,agent 的 policy 是固定的,也就是 action 是固定的,而此時的 agent 要學習 utility function 。
-
enviornment history: 曾經經過的 state 和做過的 action 紀錄。
-
每次在一個 state ,因為做了 action 而到了 state 就會得到一個 reward 。這個 reward 值可正可負,正值可以視為獎勵;而負值可以視為懲罰。
Bellman equation
Passive reinforcement learning
- utility 在透過 policy 之下,定義為 reward 的加總期望值,也就是 ,其中 為 discount factor。
Temporal-difference learning
- 這裡的 utility 的更新方法為 ,其中 是 learning rate。而算式中使用到了之前 state 的資料,因此稱為 temporal difference。
Active reinforcement learning
Temporal-difference Q-learning
期末題目整理
-
What is the main difference between CNN and RNN?
- CNN is suitable for spatial data like images. RNN is used for temporal data, also called sequential data.
-
What is overfitting?
- Overfitting refers to the condition when the model completely fits the training data but fails to generalize the testing unseen data.
-
How can we reduce overfitting? Describe at least two tips.
- k folds cross-validation
- Regularization
- Pruning
- Dropout
- Ensembling
- Batch normalization
-
What strategies can apply to reduce overfitting when learning a decision tree?
- decision tree pruning
- build a full tree
- find a test node
- if irrelevant(only noise in data) –> replace with leaf node
-
What is the kernel trick in SVM.
- 用kernel function(低維度的計算)在很高維的空間中有效率的找到optimal linear separator,這個結果map回低維度時,可能會對應到一個扭曲非線性的boundary.
-
Describe the idea of ensemble learning.
- The idea of ensemble learning is to select a collection, or ensemble, of hypotheses from the hypothesis space and combine their predictions.
-
Describe the idea of random forest.
- The key idea is randomly vary the attribute choices. At each split point in constructing the tree, select a random sampling of attributes, and then compute which of those gives the highest information gain.
reference
王承揚