###### tags: `AI/ML`
# 人工智慧導論(修課筆記) (II)
# CH19 Learning from example
## 模型訓練
 訓練過程主要目標為找尋一個接近真實方程解的假說(hypothesis)，而最終準確度會以測試集作為回測資料(需與訓練集不同)，當今天訓練時若y值為有限值則稱為分類(Classification)，而當y值為數值時，則稱為回歸(Regression)。<br>
 在模型訓練時，可能會有多個假說符合現今狀況，而在當中我們需要選擇使用到假定最少的那個假說，此種方式稱為奧坎剃刀 (Occam's razor)。
## 學習方法
1. 監督式學習(Supervised Learning):在訓練時會包含需要訓練的特徵以及該資料的標籤(label)。
2. 非監督式學習（Un-supervised learning）:資料沒有經過標註，機器自行在學習時進行分類，此種方式對機器較為困難，但對人類較為簡單(不需要人工先進行分類)
3. 半監督式學習（Semi-supervised learning）:對部分資料進行標註，電腦只要透過有標註的資料找出特徵並對其它的資料進行分類。
4. 強化學習(Reinforcement learning）:建立在enviroment base model上，機器透過每一次與環境互動來學習，以取得最大化的預期利益。運用強化式學習的方式，我們不標註任何資料，但告訴它所採取的哪一步是正確、那一步是錯誤的，根據反饋的好壞，機器自行逐步修正、最終得到正確的結果。
## 決策樹(Decision Tree)
 以是否要等待餐廳做為範例:<Br>
<img src = 'https://i.imgur.com/DDek54M.png'>
 若將此以常見的dataframe形式表達成訓練資料、特徵以及標籤，則形式如下:<br>
<img src = 'https://i.imgur.com/7l6OAkp.png'>
 在建構決策樹時，我們希望建構出來的樹深度能夠愈淺愈好(與空間複雜度有關)，因此在每次分枝時，會以最重要的特徵作為分枝依據(能夠最佳切分情況)，以下圖為例，當中左邊的Type作為分割依據於分割後的結果可看出其內部並沒有分類，而已Patrons則可大幅度分類。
<img src = 'https://i.imgur.com/MrKWMK1.png'><br>
 在判斷每條資訊所富含的資訊量時，會使用資訊熵(entropy)作為判斷依據，若entropy愈大，則代表富含的資訊量越多，其公式為:
<img src = 'https://i.imgur.com/8mKc2Do.png' width = 500><br>
而若以布林隨機變數發生true的機率，預測其entropy又可寫成:
<img src = 'https://i.imgur.com/hsmRXk2.png' width = 400><br>
 而今天要計算採取行動所獲的的好處(gain)，則可用原狀態的entropy與採取行動後的預測entropy(Remainder)之差獲得，設邊可想為在採取行動前後，資料的亂度差異，依照預想狀態而言，在什麼行動都還沒採取時資料應該是最為混亂的(entropy最大)，而且取行動後，資料會整齊些許(enropy略減)，因此利用兩者差，就可以得到現採取的行動，能夠讓資料整齊多少，以此判斷要採取哪個行為。<br>
<img src = 'https://i.imgur.com/KL1TIg1.png' width = 300><br>
 在決策樹的情況下，當今天發生overfitting的情況時，可採取剪枝的方式，減少擬和，利用虛無假說的方式，剪去與目標較無關聯的枝條。<br>
 下式為虛無假說所使用的式子，於此使用凱方分析做假說檢定，當中pk與nk分別代表子集合中的正與負資料，而p hat k與n hat k代表預期的正負資料數(期望值)。
**註解:用抽樣/總資料x正或負資料，得到期望值**<br>
<img src = 'https://i.imgur.com/AkXFdAP.png' width = 350><br>
<img src = 'https://i.imgur.com/OMMqsdm.png' width = 300><br>
 通常經過剪枝處理後的決策樹，會減少許多雜訊，且樹木的大小也會相較較小，且同時在發展樹木的成長時，也會搭配early stopping，在判斷沒有有效的發展後，便會停止生長。
### 樹模型可能會遇到的問題
1. 資料遺失
2. 單個數據具有多個屬性(會導致information gain用處下降)
3. 連續變數(樹模型比較能夠應付的是離散變數)
4. 連續結果輸出(因為樹模型比較偏向於分類用模型，因此無法使用於regression上)
--------------
## 發展與選擇假說
1. have to satisfy assumptions:
1. independent
2. identically distributed
2. best fit:
1. error rate
### k-fold validation
 避免data peeking問題
### 模型選擇
 當今天有兩模型能夠完美擬和情況，則此情況，我們可能會從比較簡單，比較小的模型開始執行，並且不斷疊代，每次皆使模型更加複雜，直到模型開始過擬和。
### Loss function
Loss function =>由訓練資料的output結果減去真實情況結果
<img src = 'https://i.imgur.com/Hsu5Ko0.png' width = 400><br>
一個好的學習代理人，理論上應該會選擇損失最少的模型，也就是指，在考量先驗機率的情況下，其generalization loss應該會如下:<br>
<img src = 'https://i.imgur.com/53skXuE.png' width = 350><br>
也就是，認為最好的假說會使得generalization loss最小，而由於在大多情況下先驗機率為一個未知數，因此會選擇採用最小empirical loss(取算數平均)取代最小generalization loss，如下:<br>
<img src = 'https://i.imgur.com/6n2Zp9r.png' width = 350><br>
### Regularization
 於此先定義模型的花費Cost(h)為:<br>
<img src = 'https://i.imgur.com/SMmvcfI.png' width = 350><br>
 而在實際運用上，會選擇最佳的lambda使得獲得最好的validation score，而在實際應用上，依照模型的複雜度給予懲罰的行為稱為regularization。<br>
------------
## Regression and Classification with Linear Models
### 單變量線性回歸(Univariate linear regression)
 在單變量線性回歸內，會給定一個輸入量 x，以及一個輸出量y，其關聯為y=w~1~x+w~0~，當中藉由調整權重w~1~以及bias w~0~，而目標為找到一個最能擬合資料點的回歸方程式。<br>
 在傳統上，在訓練過程中，會對每個訓練資料點使用squared loss function作為損失函數，如下:<br>
<img src = 'https://i.imgur.com/YUKu02x.png' width = 500><br>
 而為了能夠有效的找到使得損失函數最小的權重，通常會將權重w~0~以及w~1~視為變數，對兩者分別做偏微分，利用微積分觀念找到其最符合的權重值，而此方式具有唯一解，如下:<br>
<img src = 'https://i.imgur.com/BIdRXQr.png' width = 500><br>
 然而在線性方程式的模型上很可能沒有closed-form solution，因此在執行上可使用梯度下降法尋找最佳解答，如下:<br>
<img src = 'https://i.imgur.com/ZzIGKuA.png' width = 250><br>
 上式當中alpha為learning rate，會用此方式直到最終收斂。
而當今天有很多組training data時，則會將所有誤差梯度加總，並乘上learning rate alpha，以此更新，這種方式被命名為batch gradiend descent，方式如下:<br>
<img src = 'https://i.imgur.com/Kemdugs.png' width = 500><br>
**SGD:每次隨機選取小數量的training data作為更新**
### 多變量線性回歸(Multivariate linear regression)
 基本公式如同單變量線性回歸分析，只是增加權重數量，而計算損失函數的方式基本與單變量線性回歸分析相同，如下:<br>
<img src = 'https://i.imgur.com/oq9WTrq.png' width = 450><br>
**多變量線性回歸有一個快速找到最小損失函數的方式，會使用到data matrix，方式如下:**
<img src = 'https://i.imgur.com/KP9jD5h.png' width = 150><br>
 在線性回歸分析上，可能會使用到regularization的方式，因此需要先訂定計算模型複雜度的方式，在此會將模型複雜度定義如下:<br>
<img src = 'https://i.imgur.com/jBLFou1.png' width = 350><br>
 上式子當中的q若為1則為L1 regularization，為2則為L2 regularization，較為特別的是L1 regularization有傾向為產生一個稀疏模型(sparse model)。<br>
### 線性分類(Linear classifier)
 線性方程式不僅可以用來作為回歸分析的模型，也可做為一個分類模型使用，最簡單的方式即是給定一個threshold，以大於特定值作為第一類，小於特定值作為第二類的方式做分類，而調整方式則視是否錯誤分類來看，若真實情況是1而預估為0，則可能會將權重調大(輸入為正的情況)，反之同理。
#### 邏輯斯回歸(logistic Regression)
 將經由線性回歸產出的結果通過logistic function，使其數值成為平滑的S曲線，並以大於或小於0.5作為分類依據，logistic function如下:<br>
<img src = 'https://i.imgur.com/t9FeeHo.png' width = 350><br>
 而在logistic regression 的情況下，在權重調整時一樣使用gradient descent的方式做調整，但由於logistic function內含有權重，因此會產生需要使用到chain rule的情況，流程如下:<br>
<img src = 'https://i.imgur.com/NKjkL83.png' width = 550><br>
### 無母數模型 (Nonparametric Models)
 無母數模型為一種不限定參數數量的模型，會以資料點本身作為訓練資料，並以此預測下一個資料點，而此種模型的增長會依照訓練資料而言，此方式稱為instance-based learning or memory-based learning，最簡單的一種為直接查表，這種方式若是測試的資料沒有在訓練集內，則會直接回報預設值。
#### Nearest Neighbor models
 取最近幾個點作為分類依據。而在公式上，何謂最近則由Minkowski distance定義(L^p^ norm)，其公式如下:<br>
<img src = 'https://i.imgur.com/5r9F56R.png' width = 300><br>
在Minkowski distance當中p=2定義為Euclidean distance，p=1定義為Manhattan distance，而在boolean attribution values上，兩點差異則稱為Hamming distance。<br>
 而在Nearest Neighbor models上，如果輸入的資料維度過高，在計算周圍長度時，空間的增長，導致資料的稀疏，導致幾乎涵蓋整個區域，產生維度詛咒(curse of dimensionality)，公式如下，當中n代表維度，l代表在n為空間中從N個點中劃分出k個點所需的長度:<br>
<img src = 'https://i.imgur.com/gQEuD9b.png' width = 100><br>
則由上式可輕鬆看出，當維度越大，則所需花費的長度則越長。
#### k-d tree
 基本定義為一棵發展平衡的二元樹
#### Locality-sensitive hashing
 雜湊表的變形，為將靠近的資料點grouped在一起而形成的雜湊表，給定資料的範例點以及查詢點(qurey point X~q~)，並從範例點中找到最靠近X~q~的點，更明確的可以說，從特定點i為中心，展開半徑為R的區域，從中找尋X~q~，而若是沒有找到這個點，則會回報失敗。而距離很遠的點，則很容易被投影到不同的區域內，然而依然可能會有特殊的投影方式使得距離很遠的點，被投影到同區域內，而此方式的訣竅則在於，隨機產生多種投影方式，並且結合他們，以此形成多種不同的雜湊表，以此來找到候選點集合C，在此集合C當中，有高機率有真正的最近點存在。
### 支援向量機(Support Vector Machines)
 支援向量機為一種無母數的模型會包含maximum margin separator，且支援向量機可於形成線性分類器後，藉由kernel trick將資料擴展到高維，形成於高維度做分類的效果。
 支援向量機的核心概念為，認為每筆資料對於分類的重要程度不同，有部分的資料相較於其他資料點而言是較為重要的，而會這些較為重要的資料點作為support vector，用以作為劃分界線用，而於兩個類別的support vector 中取平均值得到的分界線則為maximum margin separator，如下圖：<br>
<img src = 'https://i.imgur.com/Lvs8vp6.png' width = 400><br>
 在向量機內，原始理想是尋找到分隔兩類別的分界帶，並且讓分界帶愈寬愈好，但由於其解決難易度較高，因此改解決下列公式，將下列公式解決則也可解決分界帶的問題，而此問題為一個有最佳化的問題，並不存在區域最小值：<br>
<img src = 'https://i.imgur.com/jMFojhA.png' width = 300><br>
 於模型訓練完後，將測試資料點帶入，利用與支援向量的內積，得出其正負號，以此來判斷所屬的類別。<br>
<img src = 'https://i.imgur.com/iQ6nBmM.png' width = 300><br>
 若今天我們能將資料投影到高維度，則可以此方式做非線性的劃分，例如將二維投影至三維，其投影方式如下:<br>
<img src = 'https://i.imgur.com/0KQq4dL.png' width = 300><br>
<img src = 'https://i.imgur.com/boztfGD.png' width = 400><br>
而在多數時候，並不需要先投影至高維度再計算內積，而是能以低維度間的運算得到，而這些運算則稱為kernel function，下面為其中一個範例，而依不同的投影方式，可能將原本的分線性結構，在高維中找到不同的線性結構能夠分割群體，<br>
<img src = 'https://i.imgur.com/mzPueUc.png' width = 200><br>
### Ensemble Learning
 訓練許多模型，並將這些模型集成更大模型，作為實際使用的模型，集成方式可分為下列幾種:
1. Bagging
2. Stacking
3. Boosting
4. Online Learning
#### Bagging
 Bagging的方式會生成K個模型，每個模型獨立運作，而最終這K個模型會對類別做投票，以此決定最終答案，而若是遇到回歸問題，則會取這K個模型的算術平均作為最終答案。
##### Random Forest
 是使用決策樹建立出的Bagging模型，每棵決策數內所使用的特徵樹木會從總特徵內隨機選取，因此每棵樹都會有些許差距。
#### Stacking
 在使用Stacking時，會先訓練許多不同的基礎模型，並將訓練結果作為新的參考特徵，產生新的特徵資料，並將這個新的特徵資料用來訓練新的模型。
#### Boosting
 在每次疊代時，依照前次訓練訓練資料權重，以此來著重訓練錯誤分類的資料點，每次疊代所產生的K個模型，最終會依造在分類上的效能再給予K個模型個別權重，並將這K個模型組合成新的大模型。
#### Online Learning
 運用在資料點會隨時更新的模型上，以過去資料所建立出的模型，對新的資料點做判斷，並以此判斷時時更新模型。
##### randomized weighted majority algorithm
 接收K個專家意見，並以這些專家(模型)的正確性作為信任權重，以產生最終模型，流程如下:<br>
<img src = 'https://i.imgur.com/PG1Jt8I.png' width = 500><br>
 在最終模型會使用後見之明作為判斷模型好壞的標準，所做的比較為，以此模型與最佳的專家做比較，而與專家的準確差異則稱為regret，以此regret作為評判標準，而若以 M* 作為專家的錯誤，則該模型的錯誤M會被局限於下式:<br>
<img src = 'https://i.imgur.com/GiiYfCX.png' width = 200><br>
-----------
# CH20 Learning Probabilistic Models
## Statistical Learning
在這個單元內，主要會學習到hypotheses以及資料的概念。<br>
 在開始先設定現有情況，以便後續舉例，假設現在有以個不透明的包裝，裡面的糖果分布情況共有五中假說:
1. h1: 100% cherry
2. h2: 78% cherry + 25% lime
3. h3: 50% cherry + 50% lime
4. h4: 25% cherry +75% lime
5. h5: 100% lime
 現在從一個未知包裝中逐漸拿出N個糖果，並以D~i~表示拿出的第i個糖果是哪種口味的可能性，而代理人的目標為預測下次拿出的糖果口味。
### Bayesian learning
 藉由計算每個假說發生的機率，並以此來計算下一個糖果發生的可能性，這種方式可以避免單純使用最佳假說來預測，取而代之的是計算不同種出現的機率值，主要會使用到貝氏定理，左式為預測為h~i~的機率，如下:<br>
<img src = 'https://i.imgur.com/CMyx5WT.png' width = 200><br>
則預測未知的機率為:<br>
<img src = 'https://i.imgur.com/KrtVcq6.png' width = 400><br>
 P(d|h~i~)被稱為likelihood，P(h~i~)為假說的先驗機率(hypothesis prior)，這兩者為主要操控機率的因素。<br>
 則給定已知j顆糖果，且藉由這j顆糖果皆為第i個假說出現的機率為(likelihood):<br>
<img src = 'https://i.imgur.com/whxWvNc.png' width = 200><br>
可由likelihood與每個假說出現的機率，計算出以觀察的糖果出現為各個假說的機率。
<img src = 'https://i.imgur.com/EOu8hXJ.png' width = 500><br>
**奧坎剃刀 (Occam's razor):如果關於同一個問題有許多種理論，每一種都能作出同樣準確的預言，那麼應該挑選其中使用假定最少的**
 而在使用上，時常直接使用能使likelihood最大的假說，這種方式稱為maximum a posteriori(MAP hypothesis)，而在實際應用上，找h~MAP~相等於最大化P(d| h~i~)P(h~i~)，也就等同於最小化:<br>
<img src = 'https://i.imgur.com/fiafL7m.png' width = 250><br>
### Maximum-likelihood parameter learning: Discrete models
 現在假設隨機開到cherry的機率為theta，而現在總共開N個包裝，當中有c個cherry，N-c個lime，此情況的likelihood為:<br>
<img src = 'https://i.imgur.com/VDUpXyw.png' width = 250>基本上為一個bionomial distribution<br>
而為了使計算方便，此likelihood取log，稱為log likelihood，同樣依造使得likelihood最大化，來取得最佳假說的方法，可對theta做偏微分，並取其值為零，得到使得likelihood最大化的機率，計算完後為C/N，這機率非常值觀，現在便是從N個內開到C顆cherry，因此最可能的假說分布同樣也為此。
 若是今天不僅與口味有關，同樣包裝的顏色也是隨機的，則可以寫成下式:<br>
<img src = 'https://i.imgur.com/TfLiXKa.png' width = 350><br>
<img src = 'https://i.imgur.com/zLfk7pJ.png' width = 550><br>
且利用同樣的方式計算max likelihood，得到的機率為下:<br>
<img src = 'https://i.imgur.com/tq4Bzdp.png' width = 350><br>
#### Naive Bayes Models
 Naive Bayes Models便是依照貝氏定理建構出的模型。
### Maximum-likelihood parameter learning: Continuous models
 現在考慮模型資料為連續，且資料產生機率如下:<br>
<img src = 'https://i.imgur.com/VDzCg2W.png' width = 150><br>
在連續情況下的Likelihood以及最大Likelihood找尋如下:<br>
<img src = 'https://i.imgur.com/1uQJSUM.png' width = 450><br>
<img src = 'https://i.imgur.com/1KXEIF3.png' width = 450><br>
 若今天是連續變數x而產生出連續變數Y，便以theta1、theta2作為變數，則需要最大化似然比(likelihood)如下:<br>
<img src = 'https://i.imgur.com/DLu89Yn.png' width = 250><br>
### Bayesian parameter learning
 在Bayesian parameter learning 的情況下，主要會使用到beta distribution，如下:<br>
<img src = 'https://i.imgur.com/p2RhnSt.png' width = 250><br>
每個beta分布會有兩個超參數a 以及 b，在這邊a以及b分別代表開到的糖果種類為cherry或是lime，下圖中，橫軸為theta的數值(cherry出現的機率)，縱軸theta的機率密度。
<img src = 'https://i.imgur.com/e928LG8.png' width = 550><br>
計算公式如下:<br>
<img src = 'https://i.imgur.com/L5qaaxU.png' width = 450><br>
### Density estimation with nonparametric models
 以KNN為例，如果在選擇上取的距離太近或太遠，可能分別會使得模型產生的密度過於尖銳或是平滑，如下:<br>
<img src = 'https://i.imgur.com/FJ4lQSV.png' width = 550><br>
而在生產個點機率時，則可使用Kernel function，當中d代表x的維度，而D則是兩點間的Euclidean distance，公式如下:<br>
<img src = 'https://i.imgur.com/WPLysgN.png' width = 200> -- 機率公式<br>
<img src = 'https://i.imgur.com/fpbhP2a.png' width = 300> -- Kernel Function<br>
### EM algorithm
 在真實世界中，許多情況會包含hidden variable，例如疾病，往往只知道行為與症狀間的關聯，而無法確認確切疾病，因此會將疾病移除，直接建立行為與症狀間的關聯模型，如下:<br>
<img src = 'https://i.imgur.com/Rxzt9KR.png' width = 500><br>
#### Unsupervised clustering: Learning mixtures of Gaussians
 Unsupervised clustering主要是用來將資料做分群的運算，但並不會得知訓練集資料的分群結果。在下列範例中，以貝氏定理作為解說，將C作為K個類別的，則依照貝氏定理可寫成:<br>
<img src = 'https://i.imgur.com/eYsPqBi.png' width = 250><br>
當今天的變數為連續變數時，則資料的分布會成為mulitvaariate Gaussian，我們將這種模型稱為混合高斯模型(mixture of Gaussian)。而由於在此我們不知道資料的分群或是他們的係數，因此會使用到EM演算法。在EM演算法當中，我們會先假設我們知道模型的係數，而後藉由疊代的方式不斷修正係數，直到結果收斂，以混和高斯模型為例，會分為E步驟以及M步驟，如下:
1. E step (expectation step)
• E-step: Compute the probabilities p~ij~ = P(C = i | x~j~), the probability that datum xj was generated by component i. By Bayes’ rule, we have p~ij~ = α P(x~j~|C = i)P(C = i). The term P(xj |C = i) is just the probability at x~j~ of the ith Gaussian, and the term P(C = i) is just the weight parameter for the ith
Gaussian.
• Define n~i~ = sum(p~ij~)~j~，以此計算出目前被歸納在第i類別的資料點有幾個(確切來說是強度，因為加總的為機率值)
2. M step (maximization step)
Compute the new mean, covariance, and component weights using the following steps in sequence:
<img src = 'https://i.imgur.com/y21SOj7.png' width = 300><br>
where N is the total number of data points
則可依照上面的方式，先經過Estep計算每個類別點的機率，在將其帶到M step 算出新的平均以及共變異數，之後再度回到E step用新的值計算機率，以此反覆直到最終收斂，當中E step主要為運算期望機率p~ij~，用於預期indicatro variable Z~ij~，若為ith 則Z~ij~為1，反之為0。而M step，則是找到新的參數，以滿足最大化似然比。
#### EM注意事項:
1. 隨著疊代增加，會看到最大似然比逐漸超越最原本的模型，而這只印證了資料是隨機產生這點，而無法印證到任何底層模型
2. EM 類似於梯度下降法，但並沒有步長的概念在裡面(no learning rate)
# CH21 Deep Learning
 在網路中，每個節點的input，會經由線性轉換後，在通過一個非線性的方程式後，輸出成最終結果，架構圖如下:<br>
<img src = 'https://i.imgur.com/LFqPZ6m.png' width = 400><br>
<img src = 'https://i.imgur.com/YXB1qvO.jpg' width = 400><br>
而如19章所學，會使用梯度下降法使得損失函數最小化，如下:<br>
<img src = 'https://i.imgur.com/wzPHpmW.jpg' width = 400><br>
而如果要在往更前面的節點作權重改變，則需要使用chain rule，如下:<br>
<img src = 'https://i.imgur.com/dxWVfaE.jpg' width = 400><br>
 而這種一層一層由後往前改變權重的方式稱為back-propagation，而由於每次往前一層，便需要對前一層做偏微分，因此若是層數很深的時候，可能會造成前面層數的偏微分值很小，這種情況被稱為梯度消逝(gradient vanish)。
 在兩類問題時，通常會使用sigmoid作為activation function，而在多重類別問題時，則多會使用softmax作為activation function。
## Convolutional neural network(CNN)
 在CNN網路中會使用到kernel 以及 stride，kernel size主要決定要同時對幾個單位做內積，通常為奇數，而stride則是一次移動幾個單位，stride會決定output的數量，若原先有n個單位，而每次移動s stride，則最終output只會剩下n/s個結果。
<img src = 'https://i.imgur.com/ZiopxKE.png' width = 400><br>
<img src = 'https://i.imgur.com/bfF4Exz.png' width = 400><br>
 而kernel未必只有一層，也可以為高維度的kernel。
### Pooling and downsampling
 在CNN網路中有許多池化(pooling)的方式，能使資料減少，常用的方式有下面兩個:
1. Average-pooling:取附近k個點的平均值，並以此值取代原本K個點。
2. Max-pooling:取k個點中的最大值，並以此值取代原本K個點。
### Tensor operations
 在捲積網路內會用到大量的張量運算，例如原本有一張256x256的RGB圖片，並且每次讀取64張做為minibatch size(訓練資料)，則代表他的input張量為256x256x3x64，則我們給定96個大小為5x5x5且stride為2的kernel，那麼代表output的tensor為128x128x96x64。
此張量被稱為feature map，代表的是會包含96個channel，當中每個channel便會富帶有一個特徵。
## Residual Network
 延續前面的觀念，在深度網路內，每一層都會從上一層的結果做下一步的運算，如:z^(i)^ = f(z^(i−1)^) = g^(i)^(W^(i)^z^(i−1)^)，而在Residual Network的概念中則是應該藉由混和上一層的input以及output作為下一層的input，而不是用output直接取代原本的值，因此該公式就會變成:z^(i)^ = g~r~^(i)^(z^(i−1)^ + f(z^(i−1)^))，則f(z)會改寫為:
**f(z) = Vg(Wz)** 當中的V以及W會藉由學習而不斷更新
**下面為他種解釋(非課程所教)**
<img src = 'https://i.imgur.com/OYxxSJ8.png' width = 400><br>
簡單來說，若原本輸入為x，學習到的特徵為H(x)，而原本的學習為 x -> H(x)，而今天定義一個殘差F(x) = H(x) - x ，也就是特徵與x所差，則學習過稱可改為 x -> F(x) + x，代表若這個階段甚麼都沒學到，則與原本的input成恆等映射。
## 學習方式
1. SGD:基本雷同於最常見的梯度下降法
2. momentum:會隨梯度與現在進行方向，逐漸修正learning rate，若現在進行方向與梯度相同，則會加大learning rate，反之則減少。
下圖為梯度找尋以及公式:
<img src = 'https://i.imgur.com/8hlxK89.png' width = 500><br>
<img src = 'https://i.imgur.com/o95ObFa.png' width = 200><br>
<img src = 'https://i.imgur.com/LelNe6l.png' width = 100> <img src = 'https://i.imgur.com/FjJX1hJ.png' width = 120><br>
## Batch Normalization
 對hidden layer的結果做normalization，一來可以增加SGD的收斂速度，二來可以增加模型泛化能力。
## RNN (Recurrent Neural Networks)
 基本邏輯為，會將前一個的hidden layer結果在經過一個權重轉換後，放入到下一層作為其中一個input，因此每一個node會包含該層的特徵以及上一層的node結果作為輸入，圖如下:<br>
<img src = 'https://i.imgur.com/jZOd2Zn.png' width = 400><br>
 上圖當中，y為z經過權重轉換後的結果，而每一層的z在傳送到下一層前，也會經過一個權重w~z,z~。<br>因此z~t~可寫為:z~t~ = g~z~(w~z,z~z~t−1~ + w~x,z~x~t~ + w~0,z~)<br>output y為:y~t~ = g~y~(w~z,y~z~t~ + w~0,y~)
 而利用梯度下降法算梯度的方式如下:<br>
<img src = 'https://i.imgur.com/aKA99Tx.jpg' width = 400><br>
在RNN當中，每一層的往前推等於往前一個時間點調整權重，因此這種方式被稱為:back-propagation through time.如同一般的梯度下降法往前推的方式，若原本的權重小於1，則代表會發生梯度消失的情況，反之則可能發生梯度爆炸，因此發展出LSTM(Long short-term memory)
### LSTM (Long short-term memory)
 在LSTM當中會有3個gate去決定與上一層或下一層之間的關聯，分別為下列，以及公式如下圖:
1. forget gate f:上一層傳過來的資訊是否要遺忘，或是要繼承多少
2. input gate i:新資料所要占比的權重
3. output gate o:決定z的output值
<img src = 'https://i.imgur.com/1eLI121.jpg' width = 350><br>
<img src = 'https://i.imgur.com/oxCoj95.png' width = 400><br>
## Unsupervised Learning and Transfer Learning:
1. Unsupervised learning:輸入值不帶有標籤
2. Transfer learning:藉由使用已經在相似資料點上訓練過的模型，在更改其中幾個hidden layers用新的模型再度訓練。
3. Semisupervised learning:同時訓練有標籤以及沒標籤的資料點。
### Probabilistic PCA
P~W~(x|z) = *N*(x;Wz, (sigma)^2^*I*)
而當中的W可藉由找到最大似然比而學習得。
### Autoencoders
 主要包含Encoder以及Decoder兩個部分，前者用以將input mapping到另一個空間，後者為將於另一個空間的值mapping回input空間，主要是希望將input x 經過encoder以及decoder兩個階段轉換後，還是與x十分接近，可寫為:x 約等於 g(f(x))。
<img src = 'https://i.imgur.com/GzyBF7c.png' width = 120><br>
通常會使用norm 2 error。
### GAN
 概念為希望產生一個建構者，能夠產生出接近於原本資料分布的資料點，以此將z值放入，能夠產生接近的x值，並且其中有另一個分歧者，能夠將藉由建構者產生的值與真實點做分別。
----------
# CH24 Deep Learning for Natural Language Processing
## Word Embeddings
 一種將文字轉成向量的技術，使文字能做運算，最常見的方式有one-hot encoding，能夠用0跟1表示文字，但此種方式無法展現出文字間的屬性關聯，則希望創造能夠表達文字間關聯的方式，使其達到下列效果:<br>
<img src = 'https://i.imgur.com/qFye7P2.png' width = 420><br>
通常這個步驟會被包含在做文字處理的深度運算當中，如下:<br>
<img src = 'https://i.imgur.com/uaqTLYj.png' width = 420><br>
## Language models/Classification with RNNs
 由於一段文字通常唯一整個序列，且具有前後相關性，因此使用RNN模型來預測便成為一個好選擇。在language模型中會將已經embedding完成的值送入當作輸入值，並以文字出現機率值作為輸出值，而在做分類問題時，與language模型中的差異僅在於輸入資料需先附加標籤，而在分類模型中，若能夠從兩個方向去做文字序列的解說，會對辨別十分有幫助，如下:<br>
<img src = 'https://i.imgur.com/Q20XPyG.png' width = 500><br>
## Sequence-to-Sequence Models
 序列對序列模型為一種最常見的NLP，而最常見的應用出現在翻譯機器上，其流程如下，會先建立一個來源的RNN模型，並將原本句子傳入，將其最後一層的hidden layers傳入到新的Target RNN上，並給予一個開始信號，以得到一個開頭文字作為結果，後續會以前一個產生的文字作為下一層的輸入值，直到最後產生結束信號。
<img src = 'https://i.imgur.com/LAhdAET.png' width = 500><br>
然而這種模型可能會包含下列幾種問題:
1. Nearby context bias:通常相鄰的字間的關聯性比較高，但是在某些時候，距離很遠的字可能也會有很高的關聯性。
2. Fixed context size limit:模型的大小通常為固定的。
3. Slower sequential process:由於一次只能訓練一個字，因此可能需要花比較多的時間。
## Attention
 使用attention可以從source資料內抓取最有關連的資訊，用以給發展出下一個單字。
<img src = 'https://i.imgur.com/LYJBHhP.png' width = 500><br>
在數學上內積代表有相似性的關聯，因此r~ij~代表的是將hidden information之間做相似性比對，因此r~ij~被稱為對於source j的attentin score，
<img src = 'https://i.imgur.com/7xwn62O.png' width = 500><br>
## Decoding
 在訓練之後，需要對完成訓練的資料做解析，因為輸出值通常為機率，因此有不同的decode方式，下列列舉幾個常見的:
1. Greedy decoding:選取機率最高的字，並將其作為下一個timestep的輸入
2. Beam search(ch3):在每個階段會依照可能性給予值，之後會將這個階段的值與上個階段的值做加總，並從中選擇錯誤率最低的兩解延伸到下個階段，如下:
<img src = 'https://i.imgur.com/AtBCP99.png' width = 600><br>
## Transformer (self attention)
 在前面提到的attention只能在source 以及target之間做attention，而經過處理後，可以讓模型在target內attend到其他target。
 Transformer會將資訊投影成三種不同表達方式，分別如下:
1. query vector:q~i~=W~q~x~i~，是attend的發起人，以此來看要找的attend資料是哪個，如同最基礎attention內的target所做的功用
2. key vector:k~i~=W~k~x~i~，是被attend到的對象，就如同最基礎attention中的source
3. value vector:v~i~=W~v~x~i~，是被產生出的內容。
則最原本的attention會被改寫為如下:<br>
<img src = 'https://i.imgur.com/q1egn8L.png' width = 350><br>
而使用self attention的好處是，每一個字所對應到的c~i~皆可以藉由平行運算得到，因此可以減少計算時間(因為每一個字都可以attend到其他字)
#### Multihead attention(學到的跟文獻上的不太一樣)
 將片段分成m個片段，並每個片段會獲得一個權重，最後將這些權重加總得到c~i~。而文獻上的則是單次學習會獲得一個q、k、v的權重，而多次學習會有不同種的q、k、v。
### Transformer layers
 在每一層transforemer layers內會包含許多部份，一開始會先執行self attention，之後會將self attention後的結果輸入到feedforward layers，最後將feedforward layers出來的結果通過activation function產生最終結果，且為了避免梯度消失問題，在transformer layers內會有兩個Residual connection。
<img src = 'https://i.imgur.com/C5g5BBq.png' width = 350><br>
然而在transformal model中，可能會沒考量到位置的關聯，因此可能會使用包含資料的positional embedding資料之後，再傳入網路。
<img src = 'https://i.imgur.com/VHuRtjw.png' width = 500><br>
### Pretrained model/embedding
#### GloVe
 用來預測在同一個window下，兩個字同時出現的機率。
概念為設定X~ij~為ij兩個字同時在window內出現的次數，而X~i~為i出現的次數，則兩者同時出現的機率為P~ij~ = X~ij~/X~i~，而最後用由此方法產生的兩字embeding取內積應該會等於log(P~ij~)。
#### Pretrained contextual representations
 在英文內會出現一字多意的情況，因此可使用RNN做上下文解釋分析:<br>
<img src = 'https://i.imgur.com/MuLE0i3.png' width = 500><br>
#### Masked language model (MLM)
 主要概念為克漏字填寫，會將input值隱藏部分，並訓練模型能夠有能力填寫出隱藏的部分，而此模型大多使用到雙向的RNN模型作為訓練架構，如下:<br>
<img src = 'https://i.imgur.com/VEBO5jk.png' width = 600><br>
# CH22 Reinforcement Learning
 模型的學習會經由本身的行為得到報酬，並經由好的報酬以及逞罰得知道哪個些行為是正確的，這些報酬稱為reward或是reinforcement，並且藉由這種方式學習到如何因應環境。
### Action-utility learning
 Q-learning會學習一個行為利益方程式或稱為Q-function，用來預估行為背後的利益。
### Policy search
 直接將狀態映射到行為並做學習，也就是reflex agent。
## Passive Reinforcement Learning
passive learning中agent的策略π是固定的：即在狀態s上，將總是執行動作π (s)，其目標僅僅只是學習策略π有多好，即學習效用函數。我們同樣以MDP中4x3網格作為環境，使用一個fully observable 環境示例來對passive learning agent 進行講解（如下圖所示）。
<img src = 'https://i.imgur.com/loIXkJM.png' width = 600><br>
<img src = 'https://i.imgur.com/Z4YhB63.png' width = 600><br>
而在每一次後的state都會比原先減少0.04(除了最終格)，而最終格分別包含+1以及-1，例如採取10個動作到+1格，則會有+0.6作為utility。
 Passive Reinforcement Learning的目標是學習到終止狀態的效用期望，如下:<br>
<img src = 'https://i.imgur.com/hKSsRGv.png' width = 250>(當中S~t~代表當時課的狀態值)<br>
下面單元主要為使用不同方式解決Passive Reinforcement。
## Direct utility estimation
 每個點的狀態值為由後往前推，例如上述的流程圖中，(1,1)採取六步後會到(4,3)，則我們由1-0.04x6得知，(1,1)點的utility為0.76，而(1,2)為0.8以及0.88，以此類推。
<img src = 'https://i.imgur.com/1U1KMy4.png' width = 300><br>**本式為直接法的效用期望值公式(r為discount factor在本例子中取1)**<br>
 直接效用估計法實際上是將reinforcement learning簡化為inductive learning 問題。該方法實際上是一個監督問題，即以state 為輸入，以觀測到reward-to-go為輸出。該方法存在的一個問題是沒有考慮states的效用之間並非是相互獨立的，因為一個state的utility等於它自身的reward外加他之後的states的expected utility。即對於一個固定策略而言，效用遵循的Bellman公式如下，當我們使用直接法取樣夠多次時，理論上會無限接近於Bellman公式的理論值結果<br>
<img src = 'https://i.imgur.com/kgGQLrQ.png' width = 400><br>
 在忽略狀態之間關係的情況下，直接效用估計會導致錯失學習的機會。比如說在上述三次嘗試中的第二次中，首次通過了狀態（3,2），且其後的狀態為（3,3），根據bellman 公式我們在第一個trail中已經知道了（3,3）的utility很高，而（3,3）又和（3,2）直接相連，因此也可以推斷出（3,2）的效用應該也會比較高。但是如果只是單獨使用directed utility estimation，那麼在第二次trail結束之前，我們並不知道（3,2）的效用是多少。因此我們可以將直接效用估計理解為在一個比需要更大的假設空間中來找到效用，在很多情況下他的局部解會和Bellman等式相衝突，即不滿足在固定policy條件下的Bellman等式的關係。
## Adaptive dynamic programming
 The counts record how often state s’ is reached when executing a in s. For example, Right is executed four times in (3,3) and the resulting state is (3,2) twice and (4,3) twice, so P((3,2)| (3,3), Right) and P((4,3)| (3,3), Right) are both estimated to be ½。
 使用統計的方式做，直接使用統計的方式，學習到transition model。
<img src = 'https://i.imgur.com/CUiS9Ll.png' width = 600><br>
左圖中，部分點在N次以前沒有數值，則代表在經過N次後，才會第一次走到那個點。
## Temporal-difference learning
 假設在第一輪trail結束之後，我們有:<img src = 'https://i.imgur.com/li5hQKS.png' width = 200>
&emsp在第二輪中（1,3）到（2,3）之間存在轉換。假設總是發生這個轉換，那麼我們有：
<img src = 'https://i.imgur.com/SfOHJWK.png' width = 200><br>
由此可知，也就是說當前 可能偏小需要對其進行調整。更加通用的講，當發生一個從狀態s到s ' 的一個轉換，我們對做如下更新：
<img src = 'https://i.imgur.com/kJoYNwE.png' width = 400><br>
 其中的alpha稱之為學習率，由於計算中存在兩個相鄰狀態效用的差值，因此被稱之為temporal-difference。和公式21.2相比，這裡我們僅僅只考慮了實際觀測到的下一個狀態s ' ，並沒有考慮其對應的轉換概率。這裡可能大家會疑惑如果s ' 對應的是一個小概率事件，那麼對U^pi^(s)的調整可能不對。實際上由於小概率事件發生的概率也會比較小。因此U^pi^(s)的平均值(average value)最終將會收斂。另外，如果隨著狀態s被訪問次數增加，我們將α值大小，那麼U^pi^(s)值本身（即非平均值）最終將實現收斂，括弧內式子表示為，以s'的預期值與現在的s的值差異，以此做為調整依據(兩者應該差距接近0.04))。
 相對於Adaptive dynamic programing (ADP)，TD收斂的速度更慢，但是計算量更小，方法更加的簡單（不需要估計transition probobility）。實際上TD和ADP算法兩者的聯繫非常的緊密，TD基於每一次觀測來進行調整，而ADP則是基於所以可能的狀態及其對應概率來進行調整。兩者都對Bellman等式進行了考慮。從某個角度來講，我們可以認為ADP是一種更加粗糙形式的TP。當然也可以使用一些啟發式算法來提高ADP的計算效率，如prioritized sweeping heuristic 算法（此處不再累述）。
## Exploration
 核心概念為一個代理人必須在利用現在最佳行動讓利益最大化，或是探索未知的狀態，以便未來能夠獲得更好的收穫。而藉由不斷探索(如同之前的有機率朝較差方向前進)，也就是符合"“greedy in the limit of infinite exploration"，GLIE的模型，在最終會無限逼近真實的transition model。<br> 當中最簡單的探索方式是每個行為會有同樣的發生機率(1/t)，而更好的是對於模型採取行動的頻率給予不同的權重值。
 若依照ADP公式作改編，則會呈現如下:<br>
<img src = 'https://i.imgur.com/FekElb9.png' width = 400><br>
 這邊的f(u,n)為exploration function，逗號右邊的N代表在state s會做a action的次數，最後會使用下面的不等式做劃分:<br>
<img src = 'https://i.imgur.com/DPdfqAn.png' width = 200><br>
 而藉由這種不等是劃分後的收斂結果如下:<br>
<img src = 'https://i.imgur.com/qARVZrG.png' width = 600><br>
## Temporal-difference Q-learning
 跳過state =>action =>state=>reward，而是直接取用action =>到state的機率以及預期效益。
<img src = 'https://i.imgur.com/LZzmO8o.png' width = 400><br>
## Approximating direct utility estimation
 然而由於現實情況有很多種，無法完全列舉所有state以及action，因此使用function來近似於實際所有狀況，如下:<br>
<img src = 'https://i.imgur.com/yDx7iGD.png' width = 400><br>
例如今天有方程式如下:<br>
<img src = 'https://i.imgur.com/f6wjMWe.png' width = 250><br>
則我們希望將x = 1 & y = 1帶入方程式後，得到的值會近似於我們前面使用ADP或TD之解。 而在調整方程式時，同時還是可使用類似梯度下降法的方式找尋最佳參數，現在假設在第j次的total reward表示為u~j~(s)，則<img src = 'https://i.imgur.com/OgepNZi.png' width = 150>為誤差值，現在對thetai做篇微分，用以找尋誤差最小值，則可得到修正公式如下(基本等同於梯度下降法):<br>
<img src = 'https://i.imgur.com/7dVJbAe.png' width = 400><br>
若直接將這個概念放到TD learning，可得到:<br>
<img src = 'https://i.imgur.com/ueTq2KX.png' width = 350><br>
## Policy Search
 Policy => 可以想像成一堆Q function的集合(hypothises的集合)如下:<br>
<img src = 'https://i.imgur.com/mebEkSM.png' width = 170><br>
 然而由於目前Q function 是許多離散點，因此無法直接使用梯度下降法求解(找尋最大pi)，因此為了因應這種狀況，可使用方程式將離散值轉為連續值，例如softmax，如下:<br>
<img src = 'https://i.imgur.com/4uBtSnM.png' width = 200><br>
而用來決定一個policy的好壞，則可以使用policy value ρ(θ)(預測使用的hypothesis好壞)，在這邊可使用梯度下降法找尋最佳解。
-----
# 其餘篇筆記
<a href = 'https://hackmd.io/ZG9hy13IT6-Bqh30YIbcBQ?both'>人工智慧導論(修課筆記) (I)</a>
Sign in with Wallet
Connect another wallet