|
【導(dǎo)讀】作者用超過1.2萬字的篇幅,，總結(jié)了自己學(xué)習(xí)機(jī)器學(xué)習(xí)過程中遇到知識點(diǎn),?！叭腴T后，才知道機(jī)器學(xué)習(xí)的魅力與可怕,。”希望正在閱讀本文的你,，也能在機(jī)器學(xué)習(xí)上學(xué)有所成,。 機(jī)器學(xué)習(xí)是什么，人工智能的子類,，深度學(xué)習(xí)的父類,。機(jī)器學(xué)習(xí)：使計(jì)算機(jī)改進(jìn)或是適應(yīng)他們的行為，從而使他們的行為更加準(zhǔn)確,。也就是通過數(shù)據(jù)中學(xué)習(xí),，從而在某項(xiàng)工作上做的更好。引用王鈺院士在2008年會議的一句話,，假定W是給定世界的有限或者無限的所有對象的集合,，Q是我們能夠或得到的有限數(shù)據(jù)，Q是W的一個(gè)很小的真子集,，機(jī)器學(xué)習(xí)就是根據(jù)世界的樣本集來推算世界的模型,，使得模型對于整體世界來說為真。機(jī)器學(xué)習(xí)的兩個(gè)驅(qū)動：神經(jīng)網(wǎng)絡(luò),，數(shù)據(jù)挖掘,。- 監(jiān)督學(xué)習(xí)：提供了包含正確回答的訓(xùn)練集，并以這個(gè)訓(xùn)練集為基礎(chǔ),，算法進(jìn)行泛化,，直到對所有的可能輸入都給出正確回答，這也稱在范例中學(xué)習(xí),。
- 無監(jiān)督學(xué)習(xí)：沒有提供正確回答,，算法試圖鑒別出輸入之間的相似，從而將同樣的輸入歸為一類,，這種方法稱密度學(xué)習(xí),。
- 強(qiáng)化學(xué)習(xí)：介于監(jiān)督和無監(jiān)督之間，當(dāng)答案不正確時(shí),，算法被告知,，如何改正則不得而知，算法需要去探索，試驗(yàn)不同情況,，直到得到正確答案,，強(qiáng)化學(xué)習(xí)有時(shí)稱為伴隨評論家的學(xué)習(xí)，因?yàn)樗粚Υ鸢冈u分,，而不給出改進(jìn)建議,。
- 進(jìn)化學(xué)習(xí)：將生物學(xué)的進(jìn)化看成一個(gè)學(xué)習(xí)過程，我們研究如何在計(jì)算機(jī)中對這一過程進(jìn)行建模,，采用適應(yīng)度的概念,，相當(dāng)于對當(dāng)前解答方案好壞程度的評分。（不是所有機(jī)器學(xué)習(xí)書籍都包含進(jìn)化學(xué)習(xí)）
優(yōu)點(diǎn)：泛化,，對于未曾碰到的輸入也能給出合理的輸出,。監(jiān)督學(xué)習(xí)：回歸、分類,。- 輸入：輸入向量x作為算法輸入給出的數(shù)據(jù)
- 突觸：wij是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的加權(quán)連接,，類似于大腦中的突觸，排列成矩陣W
- 目標(biāo)：目標(biāo)向量t,，有n個(gè)維度，監(jiān)督學(xué)習(xí)所需要等待額外數(shù)據(jù),，提供了算法正在學(xué)習(xí)的“正確答案”
- 激活函數(shù)：對于神經(jīng)網(wǎng)絡(luò),，g（·）是一種數(shù)學(xué)函數(shù)，描述神經(jīng)元的激發(fā)和作為對加權(quán)輸入的響應(yīng)
- 誤差：E是根據(jù)y和t計(jì)算網(wǎng)絡(luò)不準(zhǔn)確性的函數(shù)
- 權(quán)重空間：當(dāng)我們的輸入數(shù)據(jù)達(dá)到200維時(shí),，人類的限制使得我們無法看見,，我們最多只能看到三維投影，而對于計(jì)算機(jī)可以抽象出200個(gè)相互正交的軸的超平面進(jìn)行計(jì)算,，神經(jīng)網(wǎng)絡(luò)的參數(shù)是將神經(jīng)元連接到輸入的一組權(quán)重值,，如將神經(jīng)元的權(quán)重視為一組坐標(biāo)，即所謂的權(quán)重空間
- 維度災(zāi)難：隨著維度的增加,，單位超球面的體積也在不斷增加,，2d中，單位超球面為圓,，3d中則為求,，而更高的維度便稱為超球面，Vn = （2π/n）*Vn-2,，于是當(dāng)n>2π時(shí),，體積開始縮小，因此可用數(shù)據(jù)減少,，意味著我們需要更多的數(shù)據(jù),，當(dāng)數(shù)據(jù)到達(dá)100維以上時(shí),，單位數(shù)據(jù)變得極小,，進(jìn)而需要更多的數(shù)據(jù),，從而造成維度災(zāi)難
算法成功程度是預(yù)測和一直目標(biāo)進(jìn)行比較，對此我們需要一組新的數(shù)據(jù),，測試集,。當(dāng)對算法進(jìn)行訓(xùn)練時(shí)，過度的訓(xùn)練將會導(dǎo)致過擬合,，即擬合曲線與數(shù)據(jù)完美擬合,，但是失去了泛化能力，為檢測過擬合我們需要用測試集進(jìn)行驗(yàn)證,，稱為統(tǒng)計(jì)中的交叉驗(yàn)證,，它是模型選擇中的一部門：為模型選擇正確的參數(shù)，以便盡可能的泛化,。數(shù)據(jù)的準(zhǔn)備,，我們需要三組數(shù)據(jù)集，訓(xùn)練算法的訓(xùn)練集,，跟蹤算法學(xué)習(xí)效果的驗(yàn)證集,，用于產(chǎn)生最終結(jié)果的測試集，數(shù)據(jù)充足情況便執(zhí)行50:25:25或60:20:20的劃分,，數(shù)據(jù)集分配應(yīng)隨機(jī)處理,，當(dāng)數(shù)據(jù)請核實(shí)板塊，則采用流出方法或多折交叉驗(yàn)證,。混淆矩陣是檢測結(jié)果是否良好的分類,，制作一個(gè)方陣，其包含水平和垂直方向上所有可能的類,，在（i,，j）處的矩陣元素告訴我們在目標(biāo)中有多少模式被放入類i中，主對角線上任何東西都是正確答案,，主對角線元素之和除以所有元素的和,，從而得到的百分比便是精度。精度指標(biāo)：真正例是被正確放入類1,，假正例是被錯(cuò)誤放入類1,，而真反例是被正確放入類2，假反例是被錯(cuò)誤放入類2,。- 敏感率=#TP/(#TP+#FN) 特異率=#TN/(#TN+#FP)
- 查準(zhǔn)率=#TP/(#TP+#FP) 查全率=#TP/(#TP+#FN)
- F1 = 2*(查準(zhǔn)率*查全率)/(查準(zhǔn)率+查全率)
受試者工作曲線：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所涉及的風(fēng)險(xiǎn),。基本統(tǒng)計(jì)概念：協(xié)方差,，度量兩個(gè)變量的依賴程度。Cov（{xi},{yi}）=E({xi} – u)E({yi} – v)權(quán)衡偏差與方差：偏差-方差困境：更復(fù)雜的模型不一定能產(chǎn)生更好的結(jié)果,；模型糟糕可能由于兩個(gè)原因,，模型不準(zhǔn)確而與數(shù)據(jù)不匹配，或者不精確而有極大的不穩(wěn)定性,。第一種情況稱為偏差,，第二種情況稱為方差。01 神經(jīng)元,、神經(jīng)網(wǎng)絡(luò)和線性判別魯棒是Robust的音譯,，也就是健壯和強(qiáng)壯的意思。它是在異常和危險(xiǎn)情況下系統(tǒng)生存的關(guān)鍵,。比如說,，計(jì)算機(jī)軟件在輸入錯(cuò)誤、磁盤故障,、網(wǎng)絡(luò)過載或有意攻擊情況下,，能否不死機(jī)、不崩潰,，就是該軟件的魯棒性,。神經(jīng)網(wǎng)絡(luò)模仿的便是生物學(xué)中的神經(jīng)網(wǎng)絡(luò)，通過輸入進(jìn)而判定神經(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)重和閾值進(jìn)而得到正確的結(jié)果，歷史上的第一個(gè)神經(jīng)網(wǎng)絡(luò)——感知器,。突觸連接強(qiáng)度的變化和兩個(gè)相連神經(jīng)元激活得相關(guān)性成比例,，如果兩個(gè)神經(jīng)元始終同時(shí)激活，那么他們之間連接的強(qiáng)度會變大,，反之,，如果兩個(gè)神經(jīng)元從來不同時(shí)激活，那么他們之間的連接會消失,。也被成為長時(shí)效增強(qiáng)法則和神經(jīng)可塑性,。4. McCulloch和Pitts神經(jīng)元建模,，一組輸入加權(quán)wi相當(dāng)于突觸，一個(gè)加法器把輸入信號相加（等價(jià)于收集電荷的細(xì)胞膜）,，一個(gè)激活函數(shù),，決定細(xì)胞對于當(dāng)前的輸入是否激活，輸入乘于權(quán)重的和與閾值進(jìn)行判斷,，大于則激活，否則抑制,。局限性：現(xiàn)實(shí)中的神經(jīng)元不給出單一的輸出相應(yīng),，而是給出一個(gè)點(diǎn)位序列，一種連續(xù)的方式給出分等級的輸出,。神經(jīng)元不會根據(jù)電腦的時(shí)鐘脈沖去順序更新,，而是隨機(jī)的異步更新。Wij <- Wij – n(yi – ti)*xiN為學(xué)習(xí)效率,，過大會造成網(wǎng)絡(luò)不穩(wěn)定,，過小會造成學(xué)習(xí)時(shí)間久；yi為神經(jīng)元輸出,，ti為神經(jīng)元目標(biāo),，xi為神經(jīng)元輸入，Wij為權(quán)重,。分為兩部分,，訓(xùn)練階段和再現(xiàn)階段。初始化：設(shè)置所有的權(quán)重wij為小的隨機(jī)數(shù)（正或負(fù)都可）,。 訓(xùn)練：對T次循環(huán),，對每一個(gè)輸入向量利用激活函數(shù)g計(jì)算每一個(gè)神經(jīng)元j的激活狀態(tài)：
一條直線將神經(jīng)元激活的和不激活的神經(jīng)元?jiǎng)澐珠_來，這條直線稱為決策邊界,，也稱為判別函數(shù),，在三維空間該決策邊界為平面，更高維則為超平面,。感知器以1/γ*γ為界,，其中γ為分離超平面與最接近的數(shù)據(jù)點(diǎn)之間的距離。只要把數(shù)據(jù)映射到正確的維度空間,，那么總是可以用一個(gè)線性函數(shù)來把兩個(gè)類別區(qū)分開,，為了較有效率的解決這個(gè)問題，有一整類的方法稱為核分類器,，也是支持向量機(jī)的基礎(chǔ),。8. 數(shù)據(jù)項(xiàng)預(yù)處理特征選擇，我們每次去掉一個(gè)不同的特征,，然后試著在所得的輸入子集上訓(xùn)練分類器,，看結(jié)果是否有所提高,，如果去掉某一個(gè)特征能使得結(jié)果有所改進(jìn)，那么久徹底去掉他,，在嘗試能否去掉其他的特征,，這是一個(gè)測試輸出與每一個(gè)特征的相關(guān)性的過于簡單方法。回歸問題是用一條線去擬合數(shù)據(jù),，而分類問題是尋找一條線來劃分不同類別,。回歸方法,，引入一個(gè)指示變量,，它簡單的標(biāo)識每一個(gè)數(shù)據(jù)點(diǎn)所屬的類別。現(xiàn)在問題就變成了用數(shù)據(jù)去預(yù)測指示變量,，第二種方法是進(jìn)行重復(fù)的回歸,，每一次對其中的一個(gè)類別，指示值為1代表樣本屬于該類別,，0代表屬于其他類別,。特征選擇法：仔細(xì)查找可見的并可以利用的特征而無論他們是否有用，把它與輸出變量關(guān)聯(lián)起來 特征推導(dǎo)法：通過應(yīng)用數(shù)據(jù)遷移,，即通過可以用矩陣來描述的平移和旋轉(zhuǎn)來改變圖標(biāo)的坐標(biāo)系,，從而用舊的特征推導(dǎo)出新的特征，因?yàn)樗试S聯(lián)合特征,，并且堅(jiān)定哪一個(gè)是有用的,，哪一個(gè)沒用 聚類法：把相似的數(shù)據(jù)點(diǎn)放一起，看能不能有更少的特征
建設(shè)性方法：通過迭代不斷加入,，測試每一個(gè)階段的錯(cuò)誤以了解某個(gè)特征加入時(shí)是否會發(fā)生變化,。破壞性方法是去掉應(yīng)用在決策樹上的特征。主成分的概念是數(shù)據(jù)中變化最大的方向,。算法首先通過減去平均值來把數(shù)據(jù)集中,， 選擇變化最大的方向并把它設(shè)為坐標(biāo)軸，然后檢查余下的變化并且找一個(gè)坐標(biāo)軸使得它垂直于第一個(gè)并且覆蓋盡可能多的變化,。不斷重復(fù)這個(gè)方法直到找到所有可能的坐標(biāo)軸,。這樣的結(jié)果就是所有的變量都是沿著直角坐標(biāo)系的軸，并且協(xié)方差矩陣是對角的——每個(gè)新變量都與其他變量無關(guān),，而只與自己有關(guān),。一些變化非常小的軸可以去掉不影響數(shù)據(jù)的變化性。寫成N個(gè)點(diǎn)Xi=(X1i,，X2i,，... xXi)作為行向量。把這些向量寫成一個(gè)矩陣X(X將是N*M階矩陣),。通過減去每列的平均值來把數(shù)據(jù)中心化,，并令變化好的矩陣為B,。計(jì)算協(xié)方差陣C= 1/N *B^TB。計(jì)算C的特征向量和特征值,，即V^-1CV=D,其中V由C的特征向量組成,，D是由特征值組成的M*M階對角矩陣。把D對角線上元素按降序排列,，并對V的列向量做同樣的排列,。去掉那些小于η的特征值，剩下L維的數(shù)據(jù),。 選擇核并且把它應(yīng)用于距離矩陣從而得到矩陣K,。通過特征值的平方根標(biāo)準(zhǔn)化特征向量,。 觀察數(shù)據(jù)是否可以被少量不相關(guān)的因素或潛在的變量解釋,，目的用于發(fā)現(xiàn)獨(dú)立因素和測量每一個(gè)因素固有的誤差,。統(tǒng)計(jì)成分是獨(dú)立的，即對于E[bi,bj] = E[bi]E[bj]與及bi是不相關(guān)的,。找出每個(gè)點(diǎn)的鄰近點(diǎn)(即前k個(gè)近的點(diǎn)):計(jì)算每對點(diǎn)間的距離,。找到前k個(gè)小的距離。對于其他點(diǎn),，令Wij=0.對每個(gè)點(diǎn)xi:創(chuàng)建一個(gè)鄰近點(diǎn)的位置表z,計(jì)算zi=zi-xi,。根據(jù)約束條件計(jì)算令等式（6.31）最小的權(quán)矩陣W:計(jì)算局部協(xié)方差C=ZZ^T，其中Z是zi組成的矩陣,。利用CW=I計(jì)算W,其中I是N*N單位矩陣,。對于非鄰近點(diǎn)，令Wij=0,。對W/∑W設(shè)置其他元素計(jì)算使得等式(6.32)最小的低維向量 yi:創(chuàng)建M=(I-W)T(I-W).計(jì)算M的特征值和特征向量,。根據(jù)特征值的大小給特征向量排序。對應(yīng)于第q小的特征值,，將向量y的第q行設(shè)置為第q+1 個(gè)特征向量(忽略特征值為0)計(jì)算由每對點(diǎn)平方相似度組成的矩陣D, Dij=|xi-xj|.計(jì)算J=IN – 1/N (IN是N*N單位矩陣,，N是數(shù)據(jù)點(diǎn)個(gè)數(shù))。找到B的L個(gè)最大的特征值入i,,，以及相對應(yīng)的特征向量ei,。用特征值組成對角矩陣V并且用特征向量組成矩陣P的列向量。 創(chuàng)建所有點(diǎn)對之間的距離確定每個(gè)點(diǎn)的鄰近點(diǎn),，并做成一個(gè)權(quán)重表G 額外加入位置變量,，通過這些變量最大化函數(shù)。設(shè)置 是從數(shù)據(jù)集中隨機(jī)選出來的值設(shè)置 （這里 是整個(gè)數(shù)據(jù)集的平均值）設(shè)置=0.5
猜測參數(shù)除了通過模型選擇確定停止學(xué)習(xí)的時(shí)間,，前期采用驗(yàn)證集思想,，而信息準(zhǔn)則則是確定一些方法從而期待這個(gè)訓(xùn)練過的模型可以表現(xiàn)的多好,。- 艾卡信息準(zhǔn)則：AIC = ln（C）-k
- 貝葉斯信息準(zhǔn)則：BIC = 2ln（C）-klnN
K是模型中參數(shù)的數(shù)目，N是訓(xùn)練樣本的數(shù)量,，C是模型的最大似然,。以上兩種方法都是奧卡姆剃刀的一種形式。如無必要,，勿增實(shí)體,，即簡單有效原理。如果沒有一個(gè)描述數(shù)據(jù)的模型,，那么最好的事情就是觀察相似的數(shù)據(jù)并且把他們選擇成同一類,。用一個(gè)和（一堆點(diǎn)的權(quán)重函數(shù)）來根據(jù)輸入的距離來決定每一個(gè)數(shù)據(jù)點(diǎn)有多少權(quán)重。當(dāng)兩個(gè)核都會對離當(dāng)前輸入更近的點(diǎn)給出更高的權(quán)重,，而當(dāng)他們離當(dāng)前輸入點(diǎn)越遠(yuǎn)時(shí),，權(quán)重會光滑的減少為0，權(quán)重通過λ來具體化,。在一個(gè)時(shí)刻選擇一個(gè)維度并且將它分裂成兩個(gè),，從而創(chuàng)建一顆二進(jìn)制樹，并且讓一條直線通過這個(gè)維度里點(diǎn)的坐標(biāo)的中位數(shù),。這與決策樹的差別不大,。數(shù)據(jù)點(diǎn)作為樹的樹葉。制作樹與通常的二進(jìn)制樹的方法基本相同：我們定義一個(gè)地方來分裂成兩種選擇——左邊和右邊,， 然后沿著它們向下,。可以很自然地想到用遞歸的方法來寫算法,。選擇在哪分裂和如何分裂使得KD-Tree是不同的,。在每一步只有一個(gè)維度分裂，分裂的地方是通過計(jì)算那一維度的點(diǎn)的中位數(shù)得到的,，并且在那畫一條直線,。通常，選擇哪一個(gè)維度分裂要么通過不同的選擇要么隨機(jī)選擇,。算法向下搜索可能的維度是基于到目前為止樹的深度,，所以在二維里，它要么是水平的要么是垂直的分裂,。組成這個(gè)方法的核心是簡單地選代選取分裂的函數(shù),，找到那個(gè)坐標(biāo)的中位數(shù)的值，并且根據(jù)那個(gè)值來分裂點(diǎn),。當(dāng)前現(xiàn)代機(jī)器學(xué)習(xí)中最流行的算法之一,，其在大小合理的數(shù)據(jù)集上經(jīng)常提供比其他機(jī)器學(xué)習(xí)算法更好的分類性能。在每個(gè)類中距離分類線最近的那些點(diǎn)則被稱為支持向量,。如果有一個(gè)非線性可分?jǐn)?shù)據(jù)集,，那么就不能滿足所有數(shù)據(jù)點(diǎn)的約束條件,，解決方法是引入一些松弛變量η>=0。任何一個(gè)對稱函數(shù)如果是正定的,，都可以用來做核,。這就是Mercer定理的結(jié)果，Mercer定理也指出一些核旋繞到一起的結(jié)果可能是另一個(gè)核,。對于指定的內(nèi)核和內(nèi)核參數(shù),，計(jì)算數(shù)據(jù)之間距離的內(nèi)核 對于線性內(nèi)核,，返回K,，對于多項(xiàng)式的次數(shù)d，返回1/σ 8 K^d,。 對于RBF核,，計(jì)算K=exp(-(x-x')^2/2σ*σ。約束于將文持向量標(biāo)識為距高最近點(diǎn)一定距離內(nèi)的向量,并處理其余的訓(xùn)練集,。
對于給定的測試數(shù)據(jù)z，使用支持向量對相關(guān)內(nèi)核的數(shù)據(jù)進(jìn)行分類,，計(jì)算測試數(shù)據(jù)與支持向量的內(nèi)積,，進(jìn)行分類,，返回標(biāo)記或值,。采用線性搜索，知道方向,，那么久沿著他一直走,，直到最小值，這僅是直線的搜索,； 信賴域,，通過二次型建立函數(shù)的局部模型并且找到這個(gè)局部模型的最小值。由于我們不知道防線,，因此可以采用貪婪選擇法并且在每個(gè)點(diǎn)都沿著下降最快的方向走,，這就是所知的最速下降，它意味著pk=-▽f（xk）,。最速下降基于函數(shù)中的泰勒展開,，這是一種根據(jù)導(dǎo)數(shù)近似函數(shù)值的方法。
當(dāng)J^Tr(x)>公差并且沒有超出最大迭代次數(shù):用線性最小二乘法算出(J^TJ+vI)dx=一J^Tr中的dx,。令Xnew=x+dx,。計(jì)算實(shí)際減少和預(yù)測減少的比例:實(shí)際=||f(x)- f(xnew)|| 二維空間中,，如下圖所示,，一步沿x軸方向，另一部沿y方向,，這樣足以足以達(dá)到最小值,。而在n維空間我們應(yīng)該走n步以達(dá)到最小值，它嘗試在線性情況下實(shí)現(xiàn)這個(gè)想法,，但是我們通常感興趣的非線性情況下,，只需要多一點(diǎn)迭代就可以達(dá)到最小。左邊：如果方向之間是相互正交的并且步長是正確的,，每一個(gè)維度只需要走一步,，這里走了兩步。右邊：在橢圓上共軛的方向不是相互正交的,。
給一個(gè)初始點(diǎn)x0和停止參數(shù)ε,令p0=-▽f(x),。α=-(▽f(x)^T p)(p^T H(x)p)計(jì)算βn+1-更新p←▽f(xnew)+βk+1p,。 - 貪婪搜索：整個(gè)系統(tǒng)只找一條路,，在每一步都找局部最優(yōu)解,。所以對于TSP,任意選擇第-個(gè)城市，然后不斷重復(fù)選擇和當(dāng)前所在城市最近并且沒有訪問過的城市,，直到走完所有城市,。它的計(jì)算量非常小，只有O(NlogN),但它并不保證能找到最優(yōu)解,，并且我們無法預(yù)測它找到的解決方案如何,，有可能很糟糕。
- 爬山法：爬山法的基本想法是通過對當(dāng)前解決方案的局部搜索,，選擇任一個(gè)選項(xiàng)來改善結(jié)果,，進(jìn)行局部搜索時(shí)做出的選擇來自于一個(gè)移動集(moveset)。它描述了當(dāng)前解決方案如何被改變從而用來產(chǎn)生新的解決方案,。所以如果我們想象在2D歐幾里得空間中移動,，可能的移動就是東、南,、西,、北。
對于TSP，爬山法要先任意選一個(gè)解決方案,， 然后調(diào)換其中一對城市的順序,，看看總的旅行距離是否減少。當(dāng)交換的對數(shù)達(dá)到預(yù)先給定的數(shù)時(shí),，或找不到一個(gè)調(diào)換可以改善相對于預(yù)先給定的長度的結(jié)果時(shí)停止算法,。就像貪婪算法一樣，我們無法預(yù)測結(jié)果將會怎樣：有可能找到全局最優(yōu)解,，也有可能陷在第一個(gè)局部最大值上,， 從而并不定能找到全局最優(yōu)解，爬山法的核心循環(huán)僅僅是調(diào)換對城市,， 并且僅當(dāng)它使得距離變小時(shí)才保留調(diào)換,。開始時(shí)選擇一個(gè)任意的很高的溫度T，之后我們將隨機(jī)選擇狀態(tài)并且改變它們的值,，監(jiān)視系統(tǒng)變化前后的能量,。如果能量變低了，系統(tǒng)就會喜歡這種解決方法,，所以我們接受這個(gè)變化,。目前為止，這和梯度下降法很像,。然而,，如果能量不變低，我們?nèi)匀豢紤]是否接受這個(gè)解決方法,，并且接受的概率是exp((Ebefore- Eafter)/T),。這叫作波爾茲曼分布(Boltzmann distribution)。注意到Ebefore Eafter 是負(fù)的,，所以我們定義的概率是合理的,。偶爾接受這個(gè)不好的狀態(tài)是因?yàn)槲覀兛赡苷业降氖蔷植孔钚?，并且通過接受這個(gè)能量更多的狀態(tài),，我們可以逃離出這個(gè)區(qū)域。在重復(fù)上述方法幾次后,，我們采用一個(gè)退火時(shí)間表以便降低溫度并且使得該方法能延續(xù)下去直到溫度達(dá)到0,。由于溫度變低，所以接受任一個(gè)特殊的較高的能量狀態(tài)的機(jī)會就會變少,。最常用的退火時(shí)間表是T(l+1)=cT(t),，這里0<c<1(更加常用的是0.8<c<1)。需要減慢退火的速度以允許更多的搜索,。第一行為最好的解決方案和距離,，第二行為運(yùn)行時(shí)間，城市為10個(gè)。((1, 5, 10, 6, 3, 9, 2, 4, 8, 7, 0), 4.18)((3, 9, 2, 6, 10, 5, 1, 8, 4, 7, 0]), 4.49)((7, 9, 6, 2, 4, 0, 3, 8, 1, 5, 10]), 7.00)((10, 1, 6, 9, 8, 0, 5, 2, 4, 7, 3]), 8.95)模擬進(jìn)化是如何搜索的,，通過改變基因來改變個(gè)體的適應(yīng)度,。GA使用字符串（類似染色體的作用），字符串中的每個(gè)元素都是從某些字母表中選擇,，字母表中的值通常是二進(jìn)制的相當(dāng)于等位基因,，對于解決方法，將被變?yōu)橐粋€(gè)字符串,，然后我們隨機(jī)生產(chǎn)字符串作為初始種群,。評價(jià)適應(yīng)度可以被看成一個(gè)預(yù)測，它作用于一個(gè)字符串并且返回一個(gè)值,，它是遺傳算法中唯一因具體問題不同而不同的部分,。最好的字符串有最高的適應(yīng)值，當(dāng)解決方案不好時(shí),，適應(yīng)度也隨之下降,，GA工作于由種群組成的字符串，然后評價(jià)每個(gè)字符串的適應(yīng)度,，并進(jìn)行培養(yǎng),。- 聯(lián)賽選擇：反復(fù)從種群中挑選四個(gè)字符串，替換并將最適合的兩個(gè)字符串放人交配池中,。
- 截?cái)噙x擇：僅按比例f挑出適應(yīng)度最好的一-部分并且忽略其他的,。比如，f= 0.5經(jīng)常被使用,，所以前50%的字符串被放入交配池,，并且被等可能地選擇。這很顯然是一個(gè)非常簡單的實(shí)施方法,，但是它限制了算法探索的數(shù)量,，使得GA偏向于進(jìn)化。
- 適應(yīng)度比例選擇：最好的方法是按概率選擇字符串,，每個(gè)字符串被選擇的概率與它們的適應(yīng)度成比例,。通常采用的函數(shù)是(對于字符串a(chǎn))：
這里F^α是適應(yīng)度，如果適應(yīng)度不是正值,，則F需要在整個(gè)過程中被exp?(sF)替換,，這里s是選擇強(qiáng)度(selection strength)參數(shù)，并且你會意識到這個(gè)等式作為第4章的softmax激活）：最常用時(shí)實(shí)現(xiàn)方法是在字符串中隨機(jī)找一個(gè)點(diǎn),，在這個(gè)點(diǎn)之前的部分用字符串1的,，而在交叉點(diǎn)之后，用字符串2的剩下部分,。我們實(shí)際上產(chǎn)生了兩個(gè)后代,，第2個(gè)是由字符串2的第一部分和字符串1的第二部分組成的。這個(gè)方式稱為單點(diǎn)交叉，顯然,，它的擴(kuò)展是多點(diǎn)交叉,。最極端的情形是均勻交叉，它的字符串中的每一個(gè)元素都隨機(jī)地選自與他的父母,，下圖展示了三中類型的交叉法：交叉算子的不同形式,。（a）單點(diǎn)交叉。隨機(jī)選擇字符串中的一個(gè)位置,，然后用字符串1的第一部分和字符串2的第二部分組成后代,。（b）多點(diǎn)交叉。選擇多個(gè)點(diǎn),，后代的生成方式和前面一樣,。（c）均勻交叉。每個(gè)元素都隨機(jī)的選自于它的父母,。
對當(dāng)前最好的字符串實(shí)現(xiàn)進(jìn)化通過編譯算子實(shí)現(xiàn),，字符串中每個(gè)元素的值以概率p（通常很小）改變,。進(jìn)過我們選的字母表產(chǎn)生N個(gè)長為L的字符事,。 通過適應(yīng)度在當(dāng)前種群中選擇兩個(gè)字符串,。 重組它們產(chǎn)生兩個(gè)新的字符串,。 要么把兩個(gè)后代加到種群中,，要么使用精英法和比賽法可選性地，使用精英法從父代中挑選最合適的字符串,，并替換子代中的一些其他字符串,。
直到到達(dá)停止標(biāo)準(zhǔn),。
把方案編碼成字符串,，選擇合適的適應(yīng)度函數(shù)，選擇合適的遺傳算子,。5. 與采樣結(jié)合的進(jìn)化學(xué)習(xí)最基礎(chǔ)的版本是我們熟知的基于種群的增長學(xué)習(xí)算法(PBIL).該算法非常簡單,，像基本的GA一樣,，它采用一個(gè)二進(jìn)制字母表,，但不保留種群，而是利用一個(gè)概率向來給出每一個(gè)元素是0或1的概率,。起初,，向量的每一個(gè)值都是0.5，所以每一個(gè)元素有相等的機(jī)會變成0或1，之后通過從分布指定的向量中取樣來構(gòu)建群體,并計(jì)算群體中每個(gè)成員的適合度,。我們使用這個(gè)種群中的一個(gè)子集(通常只有前兩個(gè)適應(yīng)度最高的向量)和一個(gè)學(xué)習(xí)速率p來更新概率向量,，學(xué)習(xí)速率通常被設(shè)置為0.005(這里best和second代表種群中最好的和第二好的成員):p= pX(1 - η)+ η(best十second)/2。之后丟棄這些種群,，并且利用更新的概率向量重新取樣來產(chǎn)生新的種群,，算法的核心就是簡單地利用適應(yīng)度最高的兩個(gè)字符串和更多的向量來尋找新的字符串。07 強(qiáng)化學(xué)習(xí) 強(qiáng)化學(xué)習(xí)是狀態(tài)(state)或情形(situation)與動作(action)之間的映射,，目的是最大化一些數(shù)值形式的獎(jiǎng)賞(reward),。也就是說，算法知道當(dāng)前的輸人(狀態(tài)),，以及它可能做的一些事(動作),，目的是最大化獎(jiǎng)賞。進(jìn)行學(xué)習(xí)的智能體和環(huán)境之間有著明顯的區(qū)別,，環(huán)境是智能體完成動作的地方,，也是產(chǎn)生狀態(tài)和獎(jiǎng)賞的地方。馬爾可夫性：當(dāng)前的狀態(tài)對于計(jì)算獎(jiǎng)賞提供了足夠的信息而不需要以前的狀態(tài)信息,，一個(gè)具有馬爾可夫性的強(qiáng)化學(xué)習(xí)成為馬爾可夫決策過程,。它意味著基于以前的經(jīng)歷，我們只需要知道當(dāng)前的狀態(tài)和動作就可以計(jì)算下一步獎(jiǎng)賞的近似,，以及下一步的狀態(tài),。強(qiáng)化學(xué)習(xí)嘗試決定選擇哪一個(gè)動作來最大化未來的期望獎(jiǎng)賞，這個(gè)期望獎(jiǎng)賞就是值,，可以考慮當(dāng)前狀態(tài),，對所有采取的動作進(jìn)行平均，讓策略來自己解決這個(gè)問題,，即狀態(tài)值函數(shù),，或者考慮當(dāng)前狀態(tài)和可能采取的動作即動作值函數(shù)。對于所有的s和a, 設(shè)置Q(s, a)為一個(gè)很小的隨機(jī)數(shù),。 更新Q(s, a)←Q(s, a)+u(r+γmaxa’ (s', a')-Q(s, a))應(yīng)用到當(dāng)前情節(jié)的每一步。直到?jīng)]有更多的情節(jié),。 對于所有的s和a,設(shè)置Q(s, a)為一個(gè)很小的隨機(jī)數(shù),。 更新Q(s, a)<-Q(s, a)+u(r+yYQ(s',a')-Q(s,a)).應(yīng)用到當(dāng)前情節(jié)的每一步 都是bootstrap方法,，因?yàn)樗麄兌际菑膶φ_答案很少的估計(jì)開始,，并且在算法進(jìn)行過程中不斷迭代。兩個(gè)算法一開始都沒有環(huán)境的任何信息,，因此會利用ε-greedy策略隨機(jī)探索,。然而，隨著時(shí)間的推移,，兩個(gè)算法所產(chǎn)生的決策出現(xiàn)了很大的不同,。產(chǎn)生不同的主要原因是Q-learning總是嘗試跟著最優(yōu)的路徑，也就是最短的路,，這使它離懸崖很近,。并且，ε-greedy也意味著有時(shí)將會不可避免地翻倒,。通過對比的方式,，sarsa 算法將會收斂到一個(gè)非常安全的路線，它遠(yuǎn)離懸崖,，即使走的路線很長,。sarsa 算法產(chǎn)生了一個(gè)非常安全的路線，因?yàn)樵谒腝的估計(jì)中包含了關(guān)于動作選擇的信息,，而Q-learning生成了一條冒險(xiǎn)但更短的路線,。哪種路線更好由你決定，并且依賴于跌落懸崖的后果有多么嚴(yán)重,。決策樹的主要思想是從樹根開始,，把分類任務(wù)按順序分類成一個(gè)選擇，一步步進(jìn)行到葉子節(jié)點(diǎn)最終得到分類的結(jié)果,，樹結(jié)構(gòu)可以表示成if-then規(guī)則的集合,，適合應(yīng)用于規(guī)則歸納系統(tǒng)。在決策樹下一次分類是,，對于每一個(gè)特征,，通過計(jì)算真?zhèn)€訓(xùn)練集的熵減少來選擇特征，這成為信息增益,，描述為整個(gè)集合的熵減去每一個(gè)特定特征被選擇后的熵減去每一個(gè)特定特征被選中后的熵,。如果所有的樣本都具有同一標(biāo)記:返回標(biāo)記為該類標(biāo)記的葉子節(jié)點(diǎn)。否則,，如果沒有剩余特征用于測試:返回標(biāo)記為最常見標(biāo)記的葉子節(jié)點(diǎn),，否則:使用公式選擇S中具有最大信息增益的特征戶作為下一個(gè)節(jié)點(diǎn)。為每一個(gè)特征戶的可能取值f增加一個(gè)分支,。對于每個(gè)分支:計(jì)算除去F后的每一個(gè)特征的Sf,，使用Sf遞歸調(diào)用算法，計(jì)算目前樣本集合的信息增益,。 假設(shè)樹是近似平衡的,，那么每個(gè)節(jié)點(diǎn)的成本包括搜索d個(gè)可能的特征（盡管每個(gè)層級減少1,，但這不會影響O(·)符號的復(fù)雜性）,，然后計(jì)算每個(gè)分裂的數(shù)據(jù)集的信息贈與,，這需要花費(fèi)O（dnlogn），其中n為該節(jié)點(diǎn)上數(shù)據(jù)及的大小,，對于根節(jié)點(diǎn),，n=N，并且如果樹是平衡的,，則在樹的每個(gè)階段將n除于2,。在樹種的大約logN層級上對此求和，得到計(jì)算成本O(dN^2logN),。下圖為集成學(xué)習(xí)的基本思想,，給定一個(gè)相對簡單的二類分類問題和一些學(xué)習(xí)器，一個(gè)學(xué)習(xí)器的橢圓覆蓋數(shù)據(jù)的一個(gè)子集,，組合多個(gè)橢圓給出相當(dāng)復(fù)雜的決策邊界,。通過組合許多簡單的分類器（這里簡單地將橢圓決策邊界放在數(shù)據(jù)上），決策邊界可以變得更加復(fù)雜,，使得正例與圓圈難以分離,。每次迭代中，一個(gè)新的分類器在訓(xùn)練集上訓(xùn)練,，而訓(xùn)集中的每-個(gè)數(shù)據(jù)點(diǎn)在每一步迭代時(shí)都會調(diào)整權(quán)重,，改變權(quán)重的根據(jù)是數(shù)據(jù)點(diǎn)被之前的分類器成功分類的難度。一開始,， 這些權(quán)重都被初始化為1/N,其中N是訓(xùn)練集中點(diǎn)的個(gè)數(shù)然后,，每次迭代時(shí)，用所有被錯(cuò)分的點(diǎn)的權(quán)重之和作為誤差函數(shù)ε,。對于錯(cuò)誤分類的點(diǎn),，其權(quán)重更新乘子為a=(1-ε)/ ε。對于正確分類的點(diǎn),，其權(quán)重不變,。接著在整個(gè)數(shù)層集上做歸一化(這是降低被正確分類的數(shù)據(jù)點(diǎn)的重要性的有效方法)。在設(shè)定的迭代次數(shù)結(jié)束之后訓(xùn)練終止,，或者當(dāng)所有的數(shù)據(jù)點(diǎn)都被正確分類后訓(xùn)練終止,，或者一個(gè)點(diǎn)的權(quán)重大于最大可用權(quán)重的一半時(shí)訓(xùn)練也終止。初始化所有的權(quán)值為1/N,，其中N為數(shù)據(jù)點(diǎn)的個(gè)數(shù)當(dāng)(t<T,最大迭代次數(shù))：在上訓(xùn)練分類器,，得到數(shù)據(jù)點(diǎn)的假設(shè) 計(jì)算訓(xùn)練誤差設(shè)置返回標(biāo)記為最普通類標(biāo)的葉子節(jié)點(diǎn)如果一棵樹是好的，那么許多樹木應(yīng)該更好,，只要他們有足夠的變化,。創(chuàng)建一個(gè)訓(xùn)練集的bootstrap樣本,。使用這個(gè)bootstrap樣本訓(xùn)練決策樹。在決策樹的每一個(gè)節(jié)點(diǎn),，隨機(jī)選擇m個(gè)特征,，然后只在這些特征集合中計(jì)算信息增益(或者基尼不純度)，選擇最優(yōu)的一個(gè),。 計(jì)算屬于每一個(gè)可能的類別的輸入的概率，通過如下公式計(jì)算（其中w_i是對于每個(gè)分類器的權(quán)重）：對于樹上的每個(gè)門控網(wǎng)絡(luò)：傳遞一個(gè)輸入到下一層門（這里的和是和該門相關(guān)的輸入上的和）：無監(jiān)督學(xué)習(xí)在不知道數(shù)據(jù)點(diǎn)屬于這一類而那些數(shù)據(jù)點(diǎn)屬于另一類的情況下找到數(shù)據(jù)中相似輸入的簇,。對每一個(gè)數(shù)據(jù)點(diǎn)Xi: 用下面的距離將數(shù)據(jù)點(diǎn)安排到最近的簇中心。 將中心的位置移到這個(gè)簇中點(diǎn)的均值處(Nj是簇j中點(diǎn)的個(gè)數(shù)): 用下面的距離將數(shù)據(jù)點(diǎn)安排到最近的簇中心選擇一個(gè)值k,它與輸出節(jié)點(diǎn)的數(shù)目有關(guān),。歸一化數(shù)據(jù)以便所有的點(diǎn)都在單位球上,。 對每一個(gè)數(shù)據(jù)點(diǎn): 計(jì)算所有節(jié)點(diǎn)的激活,。 選出激活最高的那個(gè)節(jié)點(diǎn)作為勝利者。 選擇激活最高的節(jié)點(diǎn)作為勝利者。 選擇大?。ㄉ窠?jīng)元數(shù)目）和映射的維度d 隨機(jī)選擇權(quán)重向量的值使得它們都是不同的OR 設(shè)置權(quán)值來增加數(shù)據(jù)的前d個(gè)主成分的方向 對每一個(gè)數(shù)據(jù)點(diǎn)： 用權(quán)重和輸入間的歐氏距離的最小值來選擇最匹配的神經(jīng)元,， 用下面的公式來更新最匹配節(jié)點(diǎn)的權(quán)重向量： 其他的神經(jīng)元用下面的公式更新權(quán)重向量： 這里是鄰居節(jié)點(diǎn)的學(xué)習(xí)效率，而是鄰居函數(shù),，它決定是否每個(gè)神經(jīng)元應(yīng)該是勝利神經(jīng)元的鄰居（所以h=1是鄰居,，h=0不是鄰居） 減少學(xué)習(xí)效率并且調(diào)整鄰居函數(shù)，一般通過,，這里0≤α≤1決定大小下降的速度,，k是算法已經(jīng)運(yùn)行的迭代次數(shù)，k_max是算法停止的迭代次數(shù),。相同的公式被用于學(xué)習(xí)效率(η,ηn)和鄰居函數(shù) 用權(quán)重和輸入間的歐氏距離的最小值來選擇最匹配的神經(jīng)元n_b：(*本文為 AI科技大本營轉(zhuǎn)載文章,，轉(zhuǎn)載請聯(lián)系作者)
|
