作者用超過1.2萬字的篇幅，總結(jié)了自己學(xué)習(xí)機器學(xué)習(xí)過程中遇到知識點。“入門后，才知道機器學(xué)習(xí)的魅力與可怕。”希望正在閱讀本文的你，也能在機器學(xué)習(xí)上學(xué)有所成。

 作者 塵戀

 

00 準備

機器學(xué)習(xí)是什么，人工智能的子類，深度學(xué)習(xí)的父類。

機器學(xué)習(xí)：使計算機改進或是適應(yīng)他們的行為，從而使他們的行為更加準確。也就是通過數(shù)據(jù)中學(xué)習(xí)，從而在某項工作上做的更好。

引用王鈺院士在2008年會議的一句話，假定W是給定世界的有限或者無限的所有對象的集合，Q是我們能夠或得到的有限數(shù)據(jù)，Q是W的一個很小的真子集，機器學(xué)習(xí)就是根據(jù)世界的樣本集來推算世界的模型，使得模型對于整體世界來說為真。

機器學(xué)習(xí)的兩個驅(qū)動：神經(jīng)網(wǎng)絡(luò)，數(shù)據(jù)挖掘。

機器學(xué)習(xí)的分類：

監(jiān)督學(xué)習(xí)：提供了包含正確回答的訓(xùn)練集，并以這個訓(xùn)練集為基礎(chǔ)，算法進行泛化，直到對所有的可能輸入都給出正確回答，這也稱在范例中學(xué)習(xí)。

無監(jiān)督學(xué)習(xí)：沒有提供正確回答，算法試圖鑒別出輸入之間的相似，從而將同樣的輸入歸為一類，這種方法稱密度學(xué)習(xí)。

強化學(xué)習(xí)：介于監(jiān)督和無監(jiān)督之間，當答案不正確時，算法被告知，如何改正則不得而知，算法需要去探索，試驗不同情況，直到得到正確答案，強化學(xué)習(xí)有時稱為伴隨評論家的學(xué)習(xí)，因為他只對答案評分，而不給出改進建議。

進化學(xué)習(xí)：將生物學(xué)的進化看成一個學(xué)習(xí)過程，我們研究如何在計算機中對這一過程進行建模，采用適應(yīng)度的概念，相當于對當前解答方案好壞程度的評分。(不是所有機器學(xué)習(xí)書籍都包含進化學(xué)習(xí))

優(yōu)點：泛化，對于未曾碰到的輸入也能給出合理的輸出。

監(jiān)督學(xué)習(xí)：回歸、分類。

機器學(xué)習(xí)過程：

數(shù)據(jù)的收集和準備
特征選擇
算法選擇
參數(shù)和模型選擇
訓(xùn)練
評估

專業(yè)術(shù)語：

輸入：輸入向量x作為算法輸入給出的數(shù)據(jù)

突觸：wij是節(jié)點i和節(jié)點j之間的加權(quán)連接，類似于大腦中的突觸，排列成矩陣W

輸出：輸出向量y，可以有n個維度

目標：目標向量t，有n個維度，監(jiān)督學(xué)習(xí)所需要等待額外數(shù)據(jù)，提供了算法正在學(xué)習(xí)的“正確答案”

維度：輸入向量的個數(shù)

激活函數(shù)：對于神經(jīng)網(wǎng)絡(luò)，g(·)是一種數(shù)學(xué)函數(shù)，描述神經(jīng)元的激發(fā)和作為對加權(quán)輸入的響應(yīng)

誤差：E是根據(jù)y和t計算網(wǎng)絡(luò)不準確性的函數(shù)

權(quán)重空間：當我們的輸入數(shù)據(jù)達到200維時，人類的限制使得我們無法看見，我們最多只能看到三維投影，而對于計算機可以抽象出200個相互正交的軸的超平面進行計算，神經(jīng)網(wǎng)絡(luò)的參數(shù)是將神經(jīng)元連接到輸入的一組權(quán)重值，如將神經(jīng)元的權(quán)重視為一組坐標，即所謂的權(quán)重空間

維度災(zāi)難：隨著維度的增加，單位超球面的體積也在不斷增加，2d中，單位超球面為圓，3d中則為求，而更高的維度便稱為超球面，Vn = (2π/n)*Vn-2，于是當n>2π時，體積開始縮小，因此可用數(shù)據(jù)減少，意味著我們需要更多的數(shù)據(jù)，當數(shù)據(jù)到達100維以上時，單位數(shù)據(jù)變得極小，進而需要更多的數(shù)據(jù)，從而造成維度災(zāi)難

維度和體積的關(guān)系：

 

 

機器學(xué)習(xí)算法測試：

算法成功程度是預(yù)測和一直目標進行比較，對此我們需要一組新的數(shù)據(jù)，測試集。

當對算法進行訓(xùn)練時，過度的訓(xùn)練將會導(dǎo)致過擬合，即擬合曲線與數(shù)據(jù)完美擬合，但是失去了泛化能力，為檢測過擬合我們需要用測試集進行驗證，稱為統(tǒng)計中的交叉驗證，它是模型選擇中的一部門：為模型選擇正確的參數(shù)，以便盡可能的泛化。

數(shù)據(jù)的準備，我們需要三組數(shù)據(jù)集，訓(xùn)練算法的訓(xùn)練集，跟蹤算法學(xué)習(xí)效果的驗證集，用于產(chǎn)生最終結(jié)果的測試集，數(shù)據(jù)充足情況便執(zhí)行50:25:25或60:20:20的劃分，數(shù)據(jù)集分配應(yīng)隨機處理，當數(shù)據(jù)請核實板塊，則采用流出方法或多折交叉驗證。

混淆矩陣是檢測結(jié)果是否良好的分類，制作一個方陣，其包含水平和垂直方向上所有可能的類，在(i，j)處的矩陣元素告訴我們在目標中有多少模式被放入類i中，主對角線上任何東西都是正確答案，主對角線元素之和除以所有元素的和，從而得到的百分比便是精度。

精度指標：真正例是被正確放入類1，假正例是被錯誤放入類1，而真反例是被正確放入類2，假反例是被錯誤放入類2。

 

 

敏感率=#TP/(#TP+#FN) 特異率=#TN/(#TN+#FP)
查準率=#TP/(#TP+#FP) 查全率=#TP/(#TP+#FN)
F1 = 2*(查準率*查全率)/(查準率+查全率)

受試者工作曲線：y軸真正例率，x軸假正例率，線下區(qū)面積：AUC。

數(shù)據(jù)與概率的轉(zhuǎn)換：通過貝葉斯法則處理聯(lián)合概率P(C,X)和條件概率P(X|C)得出P(C|X)，MAP問題是訓(xùn)練數(shù)據(jù)中最可能的類是什么。將所有類的最終結(jié)果考慮在內(nèi)的方法稱為貝葉斯最優(yōu)分類。

損失矩陣：指定類Ci被分為類Cj所涉及的風險。

基本統(tǒng)計概念：協(xié)方差，度量兩個變量的依賴程度。

Cov({xi},{yi})=E({xi} – u)E({yi} – v)

權(quán)衡偏差與方差：偏差-方差困境：更復(fù)雜的模型不一定能產(chǎn)生更好的結(jié)果;模型糟糕可能由于兩個原因，模型不準確而與數(shù)據(jù)不匹配，或者不精確而有極大的不穩(wěn)定性。第一種情況稱為偏差，第二種情況稱為方差。

01 神經(jīng)元、神經(jīng)網(wǎng)絡(luò)和線性判別

1. 魯棒性

魯棒是Robust的音譯，也就是健壯和強壯的意思。它是在異常和危險情況下系統(tǒng)生存的關(guān)鍵。比如說，計算機軟件在輸入錯誤、磁盤故障、網(wǎng)絡(luò)過載或有意攻擊情況下，能否不死機、不崩潰，就是該軟件的魯棒性。

2. 神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)模仿的便是生物學(xué)中的神經(jīng)網(wǎng)絡(luò)，通過輸入進而判定神經(jīng)元激活否。

將一系列的神經(jīng)元放置在一起，假設(shè)數(shù)據(jù)存在模式。通過神經(jīng)元一些已知的樣例，我們希望他能夠發(fā)現(xiàn)這種模式，并且正確預(yù)測其他樣例，稱為模式識別。為了讓神經(jīng)網(wǎng)絡(luò)能夠?qū)W習(xí)，我們需要改變神經(jīng)元的權(quán)重和閾值進而得到正確的結(jié)果，歷史上的第一個神經(jīng)網(wǎng)絡(luò)——感知器。

3. Hebb法則

突觸連接強度的變化和兩個相連神經(jīng)元激活得相關(guān)性成比例，如果兩個神經(jīng)元始終同時激活，那么他們之間連接的強度會變大，反之，如果兩個神經(jīng)元從來不同時激活，那么他們之間的連接會消失。也被成為長時效增強法則和神經(jīng)可塑性。

4. McCulloch和Pitts神經(jīng)元

建模，一組輸入加權(quán)wi相當于突觸，一個加法器把輸入信號相加(等價于收集電荷的細胞膜)，一個激活函數(shù)，決定細胞對于當前的輸入是否激活，輸入乘于權(quán)重的和與閾值進行判斷，大于則激活，否則抑制。局限性：現(xiàn)實中的神經(jīng)元不給出單一的輸出相應(yīng)，而是給出一個點位序列，一種連續(xù)的方式給出分等級的輸出。神經(jīng)元不會根據(jù)電腦的時鐘脈沖去順序更新，而是隨機的異步更新。

5. 感知器

 

 

▲感知器神經(jīng)網(wǎng)絡(luò)

權(quán)重更新規(guī)則

Wij <- Wij – n(yi – ti)*xi

N為學(xué)習(xí)效率，過大會造成網(wǎng)絡(luò)不穩(wěn)定，過小會造成學(xué)習(xí)時間久;yi為神經(jīng)元輸出，ti為神經(jīng)元目標，xi為神經(jīng)元輸入，Wij為權(quán)重。

感知器學(xué)習(xí)算法

分為兩部分，訓(xùn)練階段和再現(xiàn)階段。

 

 

6. 線性可分性

一條直線將神經(jīng)元激活的和不激活的神經(jīng)元劃分開來，這條直線稱為決策邊界，也稱為判別函數(shù)，在三維空間該決策邊界為平面，更高維則為超平面。

7. 感知器收斂定理

感知器以1/γ*γ為界，其中γ為分離超平面與最接近的數(shù)據(jù)點之間的距離。

只要把數(shù)據(jù)映射到正確的維度空間，那么總是可以用一個線性函數(shù)來把兩個類別區(qū)分開，為了較有效率的解決這個問題，有一整類的方法稱為核分類器，也是支持向量機的基礎(chǔ)。

8. 數(shù)據(jù)項預(yù)處理

特征選擇，我們每次去掉一個不同的特征，然后試著在所得的輸入子集上訓(xùn)練分類器，看結(jié)果是否有所提高，如果去掉某一個特征能使得結(jié)果有所改進，那么久徹底去掉他，在嘗試能否去掉其他的特征，這是一個測試輸出與每一個特征的相關(guān)性的過于簡單方法。

9. 線性回歸

回歸問題是用一條線去擬合數(shù)據(jù)，而分類問題是尋找一條線來劃分不同類別�；貧w方法，引入一個指示變量，它簡單的標識每一個數(shù)據(jù)點所屬的類別�，F(xiàn)在問題就變成了用數(shù)據(jù)去預(yù)測指示變量，第二種方法是進行重復(fù)的回歸，每一次對其中的一個類別，指示值為1代表樣本屬于該類別，0代表屬于其他類別。

02 維度簡約

1. 降維的三種算法

特征選擇法：仔細查找可見的并可以利用的特征而無論他們是否有用，把它與輸出變量關(guān)聯(lián)起來

特征推導(dǎo)法：通過應(yīng)用數(shù)據(jù)遷移，即通過可以用矩陣來描述的平移和旋轉(zhuǎn)來改變圖標的坐標系，從而用舊的特征推導(dǎo)出新的特征，因為他允許聯(lián)合特征，并且堅定哪一個是有用的，哪一個沒用

聚類法：把相似的數(shù)據(jù)點放一起，看能不能有更少的特征

2. 特征選擇方法

建設(shè)性方法：通過迭代不斷加入，測試每一個階段的錯誤以了解某個特征加入時是否會發(fā)生變化。破壞性方法是去掉應(yīng)用在決策樹上的特征。

主成分分析(PCA)

主成分的概念是數(shù)據(jù)中變化最大的方向。算法首先通過減去平均值來把數(shù)據(jù)集中， 選擇變化最大的方向并把它設(shè)為坐標軸，然后檢查余下的變化并且找一個坐標軸使得它垂直于第一個并且覆蓋盡可能多的變化。

不斷重復(fù)這個方法直到找到所有可能的坐標軸。這樣的結(jié)果就是所有的變量都是沿著直角坐標系的軸，并且協(xié)方差矩陣是對角的——每個新變量都與其他變量無關(guān)，而只與自己有關(guān)。一些變化非常小的軸可以去掉不影響數(shù)據(jù)的變化性。

具體算法

 

 

3. 基于核的PCA算法

 

 

4. 因素分析

觀察數(shù)據(jù)是否可以被少量不相關(guān)的因素或潛在的變量解釋，目的用于發(fā)現(xiàn)獨立因素和測量每一個因素固有的誤差。

5. 獨立成分分析(ICA)

統(tǒng)計成分是獨立的，即對于E[bi,bj] = E[bi]E[bj]與及bi是不相關(guān)的。

6. 局部線性嵌入算法

找出每個點的鄰近點(即前k個近的點):計算每對點間的距離。找到前k個小的距離。對于其他點，令Wij=0.對每個點xi:創(chuàng)建一個鄰近點的位置表z,計算zi=zi-xi。

根據(jù)約束條件計算令等式(6.31)最小的權(quán)矩陣W:計算局部協(xié)方差C=ZZ^T，其中Z是zi組成的矩陣。利用CW=I計算W,其中I是N*N單位矩陣。對于非鄰近點，令Wij=0。

對W/∑W設(shè)置其他元素計算使得等式(6.32)最小的低維向量 yi:創(chuàng)建M=(I-W)T(I-W).計算M的特征值和特征向量。根據(jù)特征值的大小給特征向量排序。對應(yīng)于第q小的特征值，將向量y的第q行設(shè)置為第q+1 個特征向量(忽略特征值為0)

 

 

7. 多維標度算法

 

 

8. ISOMAP算法

 

 

03 概率學(xué)習(xí)

1. 期望最大算法(EM)

額外加入位置變量，通過這些變量最大化函數(shù)。

2. 高斯混合模型的期望最大算法

 

 

3. 通常的期望最大化算法

 

 

4. 信息準則

除了通過模型選擇確定停止學(xué)習(xí)的時間，前期采用驗證集思想，而信息準則則是確定一些方法從而期待這個訓(xùn)練過的模型可以表現(xiàn)的多好。

艾卡信息準則：AIC = ln(C)-k
貝葉斯信息準則：BIC = 2ln(C)-klnN

K是模型中參數(shù)的數(shù)目，N是訓(xùn)練樣本的數(shù)量，C是模型的最大似然。以上兩種方法都是奧卡姆剃刀的一種形式。

5. 奧卡姆剃刀

如無必要，勿增實體，即簡單有效原理。

6. 最近鄰法

如果沒有一個描述數(shù)據(jù)的模型，那么最好的事情就是觀察相似的數(shù)據(jù)并且把他們選擇成同一類。

7. 核平滑法

用一個和(一堆點的權(quán)重函數(shù))來根據(jù)輸入的距離來決定每一個數(shù)據(jù)點有多少權(quán)重。當兩個核都會對離當前輸入更近的點給出更高的權(quán)重，而當他們離當前輸入點越遠時，權(quán)重會光滑的減少為0，權(quán)重通過λ來具體化。

8. KD-Tree

在一個時刻選擇一個維度并且將它分裂成兩個，從而創(chuàng)建一顆二進制樹，并且讓一條直線通過這個維度里點的坐標的中位數(shù)。這與決策樹的差別不大。數(shù)據(jù)點作為樹的樹葉。

制作樹與通常的二進制樹的方法基本相同：我們定義一個地方來分裂成兩種選擇——左邊和右邊， 然后沿著它們向下�？梢院茏匀坏叵氲接眠f歸的方法來寫算法。

選擇在哪分裂和如何分裂使得KD-Tree是不同的。在每一步只有一個維度分裂，分裂的地方是通過計算那一維度的點的中位數(shù)得到的，并且在那畫一條直線。通常，選擇哪一個維度分裂要么通過不同的選擇要么隨機選擇。

算法向下搜索可能的維度是基于到目前為止樹的深度，所以在二維里，它要么是水平的要么是垂直的分裂。組成這個方法的核心是簡單地選代選取分裂的函數(shù)，找到那個坐標的中位數(shù)的值，并且根據(jù)那個值來分裂點。

04 支持向量機

1. 支持向量機(SVM)

當前現(xiàn)代機器學(xué)習(xí)中最流行的算法之一，其在大小合理的數(shù)據(jù)集上經(jīng)常提供比其他機器學(xué)習(xí)算法更好的分類性能。

2. 支持向量

在每個類中距離分類線最近的那些點則被稱為支持向量。

如果有一個非線性可分數(shù)據(jù)集，那么就不能滿足所有數(shù)據(jù)點的約束條件，解決方法是引入一些松弛變量η>=0。

3. 選擇核

任何一個對稱函數(shù)如果是正定的，都可以用來做核。這就是Mercer定理的結(jié)果，Mercer定理也指出一些核旋繞到一起的結(jié)果可能是另一個核。

4. 支持向量機算法

 

 

5. 分類

對于給定的測試數(shù)據(jù)z，使用支持向量對相關(guān)內(nèi)核的數(shù)據(jù)進行分類，計算測試數(shù)據(jù)與支持向量的內(nèi)積，進行分類，返回標記或值。

05 優(yōu)化和搜索

1. 下山法

朝哪個方向移動才能下降盡可能快：

采用線性搜索，知道方向，那么久沿著他一直走，直到最小值，這僅是直線的搜索;

信賴域，通過二次型建立函數(shù)的局部模型并且找到這個局部模型的最小值。由于我們不知道防線，因此可以采用貪婪選擇法并且在每個點都沿著下降最快的方向走，這就是所知的最速下降，它意味著pk=-▽f(xk)。最速下降基于函數(shù)中的泰勒展開，這是一種根據(jù)導(dǎo)數(shù)近似函數(shù)值的方法。

2. Lenenberg-Marquardt算法

 

 

3. 共軛梯度

二維空間中，如下圖所示，一步沿x軸方向，另一部沿y方向，這樣足以足以達到最小值。而在n維空間我們應(yīng)該走n步以達到最小值，它嘗試在線性情況下實現(xiàn)這個想法，但是我們通常感興趣的非線性情況下，只需要多一點迭代就可以達到最小。

 

 

▲左邊：如果方向之間是相互正交的并且步長是正確的，每一個維度只需要走一步，這里走了兩步。右邊：在橢圓上共軛的方向不是相互正交的。

具體算法：

 

 

4. 搜索的三種基本方法

窮舉法：檢查所有方法，保證找到全局最優(yōu)

貪婪搜索：整個系統(tǒng)只找一條路，在每一步都找局部最優(yōu)解。所以對于TSP,任意選擇第-個城市，然后不斷重復(fù)選擇和當前所在城市最近并且沒有訪問過的城市，直到走完所有城市。它的計算量非常小，只有O(NlogN),但它并不保證能找到最優(yōu)解，并且我們無法預(yù)測它找到的解決方案如何，有可能很糟糕。

爬山法：爬山法的基本想法是通過對當前解決方案的局部搜索，選擇任一個選項來改善結(jié)果，進行局部搜索時做出的選擇來自于一個移動集(moveset)。它描述了當前解決方案如何被改變從而用來產(chǎn)生新的解決方案。所以如果我們想象在2D歐幾里得空間中移動，可能的移動就是東、南、西、北。

對于TSP，爬山法要先任意選一個解決方案， 然后調(diào)換其中一對城市的順序，看看總的旅行距離是否減少。當交換的對數(shù)達到預(yù)先給定的數(shù)時，或找不到一個調(diào)換可以改善相對于預(yù)先給定的長度的結(jié)果時停止算法。

就像貪婪算法一樣，我們無法預(yù)測結(jié)果將會怎樣：有可能找到全局最優(yōu)解，也有可能陷在第一個局部最大值上， 從而并不定能找到全局最優(yōu)解，爬山法的核心循環(huán)僅僅是調(diào)換對城市， 并且僅當它使得距離變小時才保留調(diào)換。

5. 模擬退火算法

開始時選擇一個任意的很高的溫度T，之后我們將隨機選擇狀態(tài)并且改變它們的值，監(jiān)視系統(tǒng)變化前后的能量。如果能量變低了，系統(tǒng)就會喜歡這種解決方法，所以我們接受這個變化。目前為止，這和梯度下降法很像。

然而，如果能量不變低，我們?nèi)匀豢紤]是否接受這個解決方法，并且接受的概率是exp((Ebefore- Eafter)/T)。這叫作波爾茲曼分布(Boltzmann distribution)。注意到Ebefore Eafter 是負的，所以我們定義的概率是合理的。偶爾接受這個不好的狀態(tài)是因為我們可能找到的是局部最小，并且通過接受這個能量更多的狀態(tài)，我們可以逃離出這個區(qū)域。

在重復(fù)上述方法幾次后，我們采用一個退火時間表以便降低溫度并且使得該方法能延續(xù)下去直到溫度達到0。由于溫度變低，所以接受任一個特殊的較高的能量狀態(tài)的機會就會變少。最常用的退火時間表是T(l+1)=cT(t)，這里0

6. 四種算法TSP結(jié)果比較

第一行為最好的解決方案和距離，第二行為運行時間，城市為10個。

 

 

06 進化學(xué)習(xí)

1. 遺傳算法(GA)

模擬進化是如何搜索的，通過改變基因來改變個體的適應(yīng)度。

GA使用字符串(類似染色體的作用)，字符串中的每個元素都是從某些字母表中選擇，字母表中的值通常是二進制的相當于等位基因，對于解決方法，將被變?yōu)橐粋�字符串，然后我們隨機生產(chǎn)字符串作為初始種群。

評價適應(yīng)度可以被看成一個預(yù)測，它作用于一個字符串并且返回一個值，它是遺傳算法中唯一因具體問題不同而不同的部分。最好的字符串有最高的適應(yīng)值，當解決方案不好時，適應(yīng)度也隨之下降，GA工作于由種群組成的字符串，然后評價每個字符串的適應(yīng)度，并進行培養(yǎng)。

產(chǎn)生后代的常用3種方法：

聯(lián)賽選擇：反復(fù)從種群中挑選四個字符串，替換并將最適合的兩個字符串放人交配池中。

截斷選擇：僅按比例f挑出適應(yīng)度最好的一-部分并且忽略其他的。比如，f= 0.5經(jīng)常被使用，所以前50%的字符串被放入交配池，并且被等可能地選擇。這很顯然是一個非常簡單的實施方法，但是它限制了算法探索的數(shù)量，使得GA偏向于進化。

適應(yīng)度比例選擇：最好的方法是按概率選擇字符串，每個字符串被選擇的概率與它們的適應(yīng)度成比例。通常采用的函數(shù)是(對于字符串a(chǎn))：

 

 

這里F^α是適應(yīng)度，如果適應(yīng)度不是正值，則F需要在整個過程中被exp?(sF)替換，這里s是選擇強度(selection strength)參數(shù)，并且你會意識到這個等式作為第4章的softmax激活)：

 

 

2. 遺傳算子產(chǎn)生

最常用時實現(xiàn)方法是在字符串中隨機找一個點，在這個點之前的部分用字符串1的，而在交叉點之后，用字符串2的剩下部分。我們實際上產(chǎn)生了兩個后代，第2個是由字符串2的第一部分和字符串1的第二部分組成的。這個方式稱為單點交叉，顯然，它的擴展是多點交叉。

最極端的情形是均勻交叉，它的字符串中的每一個元素都隨機地選自與他的父母，下圖展示了三中類型的交叉法：

 

 

▲交叉算子的不同形式。(a)單點交叉。隨機選擇字符串中的一個位置，然后用字符串1的第一部分和字符串2的第二部分組成后代。(b)多點交叉。選擇多個點，后代的生成方式和前面一樣。(c)均勻交叉。每個元素都隨機的選自于它的父母。

對當前最好的字符串實現(xiàn)進化通過編譯算子實現(xiàn)，字符串中每個元素的值以概率p(通常很小)改變。

3. 基本遺傳算法

 

 

4. 使用遺傳算法進行圖著色

把方案編碼成字符串，選擇合適的適應(yīng)度函數(shù)，選擇合適的遺傳算子。

5. 與采樣結(jié)合的進化學(xué)習(xí)

最基礎(chǔ)的版本是我們熟知的基于種群的增長學(xué)習(xí)算法(PBIL).該算法非常簡單，像基本的GA一樣，它采用一個二進制字母表，但不保留種群，而是利用一個概率向來給出每一個元素是0或1的概率。

起初，向量的每一個值都是0.5，所以每一個元素有相等的機會變成0或1，之后通過從分布指定的向量中取樣來構(gòu)建群體,并計算群體中每個成員的適合度。

我們使用這個種群中的一個子集(通常只有前兩個適應(yīng)度最高的向量)和一個學(xué)習(xí)速率p來更新概率向量，學(xué)習(xí)速率通常被設(shè)置為0.005(這里best和second代表種群中最好的和第二好的成員):p= pX(1 - η)+ η(best十second)/2。

之后丟棄這些種群，并且利用更新的概率向量重新取樣來產(chǎn)生新的種群，算法的核心就是簡單地利用適應(yīng)度最高的兩個字符串和更多的向量來尋找新的字符串。

07 強化學(xué)習(xí)

強化學(xué)習(xí)是狀態(tài)(state)或情形(situation)與動作(action)之間的映射，目的是最大化一些數(shù)值形式的獎賞(reward)。也就是說，算法知道當前的輸人(狀態(tài))，以及它可能做的一些事(動作)，目的是最大化獎賞。進行學(xué)習(xí)的智能體和環(huán)境之間有著明顯的區(qū)別，環(huán)境是智能體完成動作的地方，也是產(chǎn)生狀態(tài)和獎賞的地方。

1. 馬爾可夫決策過程

馬爾可夫性：當前的狀態(tài)對于計算獎賞提供了足夠的信息而不需要以前的狀態(tài)信息，一個具有馬爾可夫性的強化學(xué)習(xí)成為馬爾可夫決策過程。它意味著基于以前的經(jīng)歷，我們只需要知道當前的狀態(tài)和動作就可以計算下一步獎賞的近似，以及下一步的狀態(tài)。

2. 值

強化學(xué)習(xí)嘗試決定選擇哪一個動作來最大化未來的期望獎賞，這個期望獎賞就是值，可以考慮當前狀態(tài)，對所有采取的動作進行平均，讓策略來自己解決這個問題，即狀態(tài)值函數(shù)，或者考慮當前狀態(tài)和可能采取的動作即動作值函數(shù)。

3. O-learning算法

 

 

4. Sarsa算法

 

 

兩種算法的相同

都是bootstrap方法，因為他們都是從對正確答案很少的估計開始，并且在算法進行過程中不斷迭代。

不同

兩個算法一開始都沒有環(huán)境的任何信息，因此會利用ε-greedy策略隨機探索。然而，隨著時間的推移，兩個算法所產(chǎn)生的決策出現(xiàn)了很大的不同。

產(chǎn)生不同的主要原因是Q-learning總是嘗試跟著最優(yōu)的路徑，也就是最短的路，這使它離懸崖很近。并且，ε-greedy也意味著有時將會不可避免地翻倒。通過對比的方式，sarsa 算法將會收斂到一個非常安全的路線，它遠離懸崖，即使走的路線很長。

sarsa 算法產(chǎn)生了一個非常安全的路線，因為在它的Q的估計中包含了關(guān)于動作選擇的信息，而Q-learning生成了一條冒險但更短的路線。哪種路線更好由你決定，并且依賴于跌落懸崖的后果有多么嚴重。

08 樹的學(xué)習(xí)

決策樹的主要思想是從樹根開始，把分類任務(wù)按順序分類成一個選擇，一步步進行到葉子節(jié)點最終得到分類的結(jié)果，樹結(jié)構(gòu)可以表示成if-then規(guī)則的集合，適合應(yīng)用于規(guī)則歸納系統(tǒng)。

1. ID3

在決策樹下一次分類是，對于每一個特征，通過計算真?zhèn)�訓(xùn)練集的熵減少來選擇特征，這成為信息增益，描述為整個集合的熵減去每一個特定特征被選擇后的熵減去每一個特定特征被選中后的熵。

具體算法

 

 

決策樹復(fù)雜度

假設(shè)樹是近似平衡的，那么每個節(jié)點的成本包括搜索d個可能的特征(盡管每個層級減少1，但這不會影響O(·)符號的復(fù)雜性)，然后計算每個分裂的數(shù)據(jù)集的信息贈與，這需要花費O(dnlogn)，其中n為該節(jié)點上數(shù)據(jù)及的大小，對于根節(jié)點，n=N，并且如果樹是平衡的，則在樹的每個階段將n除于2。在樹種的大約logN層級上對此求和，得到計算成本O(dN^2logN)。

09 委員會決策：集成學(xué)習(xí)

下圖為集成學(xué)習(xí)的基本思想，給定一個相對簡單的二類分類問題和一些學(xué)習(xí)器，一個學(xué)習(xí)器的橢圓覆蓋數(shù)據(jù)的一個子集，組合多個橢圓給出相當復(fù)雜的決策邊界。

 

 

▲通過組合許多簡單的分類器(這里簡單地將橢圓決策邊界放在數(shù)據(jù)上)，決策邊界可以變得更加復(fù)雜，使得正例與圓圈難以分離。

1. AdaBoost(自適應(yīng)提升)

每次迭代中，一個新的分類器在訓(xùn)練集上訓(xùn)練，而訓(xùn)集中的每-個數(shù)據(jù)點在每一步迭代時都會調(diào)整權(quán)重，改變權(quán)重的根據(jù)是數(shù)據(jù)點被之前的分類器成功分類的難度。一開始， 這些權(quán)重都被初始化為1/N,其中N是訓(xùn)練集中點的個數(shù)然后，每次迭代時，用所有被錯分的點的權(quán)重之和作為誤差函數(shù)ε。

對于錯誤分類的點，其權(quán)重更新乘子為a=(1-ε)/ ε。對于正確分類的點，其權(quán)重不變。接著在整個數(shù)層集上做歸一化(這是降低被正確分類的數(shù)據(jù)點的重要性的有效方法)。在設(shè)定的迭代次數(shù)結(jié)束之后訓(xùn)練終止，或者當所有的數(shù)據(jù)點都被正確分類后訓(xùn)練終止，或者一個點的權(quán)重大于最大可用權(quán)重的一半時訓(xùn)練也終止。

具體算法：

 

 

2. 隨機森林

如果一棵樹是好的，那么許多樹木應(yīng)該更好，只要他們有足夠的變化。

3. 基本的隨機森林訓(xùn)練算法

 

 

4. 專家混合算法

 

 

10 無監(jiān)督學(xué)習(xí)

無監(jiān)督學(xué)習(xí)在不知道數(shù)據(jù)點屬于這一類而那些數(shù)據(jù)點屬于另一類的情況下找到數(shù)據(jù)中相似輸入的簇。

1. k-means算法

 

 

2. 在線k-Means算法

 

 

3. 自組織特征映射算法

 

 

 

 

標簽： 機器學(xué)習(xí) 深度學(xué)習(xí)

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。