機(jī)器學(xué)習(xí)復(fù)習(xí)總結(jié)

1、第一章基本設(shè)計(jì)方法和學(xué)習(xí)途徑選擇訓(xùn)練經(jīng)驗(yàn)選擇目標(biāo)函數(shù)選擇目標(biāo)函數(shù)的表示選擇函數(shù)逼近算法最終設(shè)計(jì)選擇訓(xùn)練經(jīng)驗(yàn)第一個(gè)關(guān)鍵屬性，訓(xùn)練經(jīng)驗(yàn)?zāi)芊駷橄到y(tǒng)的決策提供直接或間接的反饋第二個(gè)重要屬性，學(xué)習(xí)器在多大程度上控制樣例序列第三個(gè)重要屬性，訓(xùn)練樣例的分布能多好地表示實(shí)例分布，通過(guò)樣例來(lái)衡量最終系統(tǒng)的性能最終設(shè)計(jì)執(zhí)行系統(tǒng)用學(xué)會(huì)的目標(biāo)函數(shù)來(lái)解決給定的任務(wù)鑒定器以對(duì)弈的路線或歷史記錄作為輸入，輸出目標(biāo)函數(shù)的一系列訓(xùn)練樣例。泛化器以訓(xùn)練樣例為輸入，產(chǎn)生一個(gè)輸出假設(shè)，作為它對(duì)目標(biāo)函數(shù)的估計(jì)。實(shí)驗(yàn)生成器以當(dāng)前的假設(shè)作為輸入，輸出一個(gè)新的問(wèn)題，供執(zhí)行系統(tǒng)去探索。第二章一致，滿足，覆蓋的定義：一致 ：一個(gè)假設(shè)h 與訓(xùn)練樣

2、例集合D 一致，當(dāng)且僅當(dāng)對(duì)D 中每一個(gè)樣例<x,c(x)> 都有h(x)=c(x) ，即 Consistent(h,D) ( <x,c(x)> D)h(x)=c(x)一個(gè)樣例x 在h( x) =1 時(shí)稱為 滿足 假設(shè)h，無(wú)論x 是目標(biāo)概念的正例還是反例。當(dāng)一假設(shè)能正確劃分一個(gè)正例時(shí)，稱該假設(shè)覆蓋 該正例。變型空間(version space) ： 與訓(xùn)練樣例一致的所有假設(shè)組成的集合，表示了目標(biāo)概念的所有合理的變型，VS H,D=hH|Consistent(h,D)第三章決策樹(shù)適用問(wèn)題的特征：實(shí)例由 “屬性 -值 ”對(duì) (pair)表示目標(biāo)函數(shù)具有離散的輸出值可能需要析取

3、的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例ID3 算法特點(diǎn)：搜索完整的假設(shè)空間(也就是說(shuō)，決策樹(shù)空間能夠表示定義在離散實(shí)例上的任何離散值函數(shù))從根向下推斷決策樹(shù)，為每個(gè)要加入樹(shù)的新決策分支貪婪地選擇最佳的屬性。歸納偏置，優(yōu)先選擇較小的樹(shù)觀察 ID3 的搜索空間和搜索策略，認(rèn)識(shí)到這個(gè)算法的優(yōu)勢(shì)和不足假設(shè)空間包含所有的決策樹(shù)，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間維護(hù)單一的當(dāng)前假設(shè)(不同于第二章的變型空間候選消除算法)不進(jìn)行回溯，可能收斂到局部最優(yōu)每一步使用所有的訓(xùn)練樣例，不同于基于單獨(dú)的訓(xùn)練樣例遞增作出決定，容錯(cuò)性增強(qiáng)ID3 和候選消除算法的比較ID3 的搜索范圍是一個(gè)完

4、整的假設(shè)空間，但不徹底地搜索這個(gè)空間候選消除算法的搜索范圍是不完整的假設(shè)空間，但徹底地搜索這個(gè)空間ID3 的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來(lái)自搜索策略候選消除算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來(lái)自對(duì)搜索空間的定義過(guò)度擬合：對(duì)于一個(gè)假設(shè)，當(dāng)存在其他的假設(shè)對(duì)訓(xùn)練樣例的擬合比它差，但事實(shí)上在實(shí)例的整個(gè)分布上表現(xiàn)得卻更好時(shí)，我們說(shuō)這個(gè)假設(shè)過(guò)度擬合訓(xùn)練樣例定義 ：給定一個(gè)假設(shè)空間H ，一個(gè)假設(shè)h H ，如果存在其他的假設(shè)h H，使得在訓(xùn)練樣例上 h 的錯(cuò)誤率比h小，但在整個(gè)實(shí)例分布上h的錯(cuò)誤率比h 小，那么就說(shuō)假設(shè)h 過(guò)度擬合訓(xùn)練數(shù)據(jù)導(dǎo)致過(guò)度擬合的原因1 .一種可能原因是訓(xùn)練樣例含有隨機(jī)錯(cuò)誤或

5、噪聲2 .特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點(diǎn)時(shí)，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實(shí)際的目標(biāo)函數(shù)并無(wú)關(guān)系避免過(guò)度擬合的方法特點(diǎn)及早停止樹(shù)增長(zhǎng)精確地估計(jì)何時(shí)停止樹(shù)增長(zhǎng)后修剪法被證明在實(shí)踐中更成功避免過(guò)度擬合的關(guān)鍵：使用什么樣的準(zhǔn)則來(lái)確定最終正確樹(shù)的規(guī)模，解決這個(gè)問(wèn)題的方法有：訓(xùn)練和驗(yàn)證集法可用數(shù)據(jù)分成兩個(gè)樣例集合：訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè)驗(yàn)證集合，評(píng)估這個(gè)假設(shè)在后續(xù)數(shù)據(jù)上的精度方法的動(dòng)機(jī)：即使學(xué)習(xí)器可能會(huì)被訓(xùn)練集合誤導(dǎo)，但驗(yàn)證集合不大可能表現(xiàn)出同樣的隨機(jī)波動(dòng)驗(yàn)證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計(jì)意義的實(shí)例樣本常見(jiàn)的做法是，樣例的三分之二作訓(xùn)練集合，三分之一

6、作驗(yàn)證集合錯(cuò)誤率降低修剪(reduced-error pruning)將樹(shù)上的每一個(gè)節(jié)點(diǎn)作為修剪的候選對(duì)象修剪步驟刪除以此節(jié)點(diǎn)為根的子樹(shù)，使它成為葉結(jié)點(diǎn)把和該節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例的最常見(jiàn)分類賦給它反復(fù)修剪節(jié)點(diǎn)，每次總是選取那些刪除后可以最大提高決策樹(shù)在驗(yàn)證集合上的精度的節(jié)點(diǎn)繼續(xù)修剪，直到進(jìn)一步的修剪是有害的為止數(shù)據(jù)集分成3 個(gè)子集訓(xùn)練樣例，形成決策樹(shù)驗(yàn)證樣例，修剪決策樹(shù)測(cè)試樣例，精度的無(wú)偏估計(jì)如果有大量的數(shù)據(jù)可供使用，那么使用分離的數(shù)據(jù)集合來(lái)引導(dǎo)修剪規(guī)則后修剪(rule post-pruning)步驟從訓(xùn)練集合推導(dǎo)出決策樹(shù)，增長(zhǎng)決策樹(shù)直到盡可能好地?cái)M合訓(xùn)練數(shù)據(jù)，允許過(guò)度擬合發(fā)生將決策樹(shù)轉(zhuǎn)化為等價(jià)

7、的規(guī)則集合，方法是為從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑創(chuàng)建一條規(guī)則通過(guò)刪除任何能導(dǎo)致估計(jì)精度提高的前件來(lái)修剪每一條規(guī)則按照修剪過(guò)的規(guī)則的估計(jì)精度對(duì)它們進(jìn)行排序，并按這樣的順序應(yīng)用這些規(guī)則來(lái)分類后來(lái)的實(shí)例第四章解決反向傳播算法中的過(guò)度擬合問(wèn)題的方法：權(quán)值衰減它在每次迭代過(guò)程中以某個(gè)小因子降低每個(gè)權(quán)值，這等效于修改E 的定義，加入一個(gè)與網(wǎng)絡(luò)權(quán)值的總量相應(yīng)的懲罰項(xiàng)，此方法的動(dòng)機(jī)是保持權(quán)值較小，從而使學(xué)習(xí)過(guò)程向著復(fù)雜決策面的反方向偏置驗(yàn)證數(shù)據(jù)一個(gè)最成功的方法是在訓(xùn)練數(shù)據(jù)外再為算法提供一套驗(yàn)證數(shù)據(jù)，應(yīng)該使用在驗(yàn)證集合上產(chǎn)生最小誤差的迭代次數(shù)，不是總能明顯地確定驗(yàn)證集合何時(shí)達(dá)到最小誤差k-fold 交叉方法把訓(xùn)

8、練樣例分成k 份， 然后進(jìn)行k 次交叉驗(yàn)證過(guò)程，每次使用不同的一份作為驗(yàn)證集合，其余 k-1 份合并作為訓(xùn)練集合。每個(gè)樣例會(huì)在一次實(shí)驗(yàn)中被用作驗(yàn)證樣例，在k-1 次實(shí)驗(yàn)中被用作訓(xùn)練樣例每次實(shí)驗(yàn)中，使用上面討論的交叉驗(yàn)證過(guò)程來(lái)決定在驗(yàn)證集合上取得最佳性能的迭代次數(shù)，然后計(jì)算這些迭代次數(shù)的均值最后，運(yùn)行一次反向傳播算法，訓(xùn)練所有m 個(gè)實(shí)例并迭代i 次前饋網(wǎng)絡(luò)的表征能力布爾函數(shù)： 任何布爾函數(shù)可以被具有兩層單元的網(wǎng)絡(luò)準(zhǔn)確表示，盡管在最壞情況下所需隱藏單元的數(shù)量隨著網(wǎng)絡(luò)輸入數(shù)量的增加成指數(shù)級(jí)增長(zhǎng)。連續(xù)函數(shù)： 每個(gè)有界的連續(xù)函數(shù)可以由一個(gè)兩層的網(wǎng)絡(luò)以任意小的誤差逼近。這個(gè)結(jié)論適用于在隱藏層使用sigmo

9、id 單元、在輸出層使用（非閾值）線性單元的網(wǎng)絡(luò)。所需的隱藏單元數(shù)量依賴于要逼近的函數(shù)。任意函數(shù)： 任意函數(shù)可以被一個(gè)有三層單元的網(wǎng)絡(luò)以任意精度逼近。兩個(gè)隱藏層使用sigmoid單元，輸出層使用線性單元，每層所需單元數(shù)不確定。第五章error S (h) zNerror S ( h)(1 errorS(h)對(duì)有限數(shù)據(jù)樣本集的采樣方法k-fold 方法隨機(jī)抽取至少有30 個(gè)樣例的測(cè)試集合，剩余樣例組成訓(xùn)練集合，重復(fù)這一過(guò)程直到足夠的次數(shù)隨機(jī)方法的好處是能夠重復(fù)無(wú)數(shù)次，以減少置信區(qū)間到需要的寬度k-fold 方法受限于樣例的總數(shù)隨機(jī)方法的缺點(diǎn)是，測(cè)試集合不再被看作是從基準(zhǔn)實(shí)例分布中獨(dú)立抽取k-fo

10、ld 交叉驗(yàn)證生成的測(cè)試集合是獨(dú)立的，因?yàn)橐粋€(gè)實(shí)例只在測(cè)試集合中出現(xiàn)一次概括而言，統(tǒng)計(jì)學(xué)模型在數(shù)據(jù)有限時(shí)很少能完美地匹配學(xué)習(xí)算法驗(yàn)證中的所有約束。然而，它們確實(shí)提供了近似的置信區(qū)間第六章貝葉斯學(xué)習(xí)方法的特性觀察到的每個(gè)訓(xùn)練樣例可以增量地降低或升高某假設(shè)的估計(jì)概率先驗(yàn)知識(shí)可以與觀察數(shù)據(jù)一起決定假設(shè)的最終概率每個(gè)候選假設(shè)的先驗(yàn)概率每個(gè)可能假設(shè)在可觀察數(shù)據(jù)上的概率分布貝葉斯方法可允許假設(shè)做出不確定性的預(yù)測(cè)新的實(shí)例分類可由多個(gè)假設(shè)一起做出預(yù)測(cè)，用它們的概率來(lái)加權(quán)即使在貝葉斯方法計(jì)算復(fù)雜度較高時(shí)，它們?nèi)钥勺鳛橐粋€(gè)最優(yōu)的決策標(biāo)準(zhǔn)衡量其他方法一致學(xué)習(xí)器定義：如果某個(gè)學(xué)習(xí)器輸出的假設(shè)在訓(xùn)練樣例上為0 錯(cuò)誤率一

11、致學(xué)習(xí)器輸出一個(gè)MAP 假設(shè)的條件1 H 上有均勻的先驗(yàn)概率2 .。訓(xùn)練數(shù)據(jù)是確定性和無(wú)噪聲的在特定前提下，任一學(xué)習(xí)算法如果使輸出的假設(shè)預(yù)測(cè)和訓(xùn)練數(shù)據(jù)之間的誤差平方和最小化，它將輸出一極大似然假設(shè)誤差平方最小化的法則尋找到極大似然假設(shè)的前提是：訓(xùn)練數(shù)據(jù)可以由目標(biāo)函數(shù)值加上正態(tài)分布噪聲來(lái)模擬使交叉熵最小化的法則尋找極大似然假設(shè)基于的前提是：觀察到的布爾值為輸入實(shí)例的概率函數(shù)argmaxP(vj |hi )P(hi | D)貝葉斯最優(yōu)分類器的定義：vj V hi H特點(diǎn) ： 1。它所做的分類可以對(duì)應(yīng)于H 中不存在的假設(shè)3 .在給定可用數(shù)據(jù)、假設(shè)空間及這些假設(shè)的先驗(yàn)概率下使新實(shí)例被正確分類的可能性達(dá)

12、到最大樸素貝葉斯分類器的定義vNBargmaxP(vj)P(ai |vj)vj V只要條件獨(dú)立性得到滿足，樸素貝葉斯分類區(qū)別： 沒(méi)有明確地搜索可能假設(shè)空間的過(guò)程樣例中不同數(shù)據(jù)組合的出現(xiàn)頻率)ivNB 等于 MAP 分類，否則是近似只是簡(jiǎn)單地計(jì)算訓(xùn)練各學(xué)習(xí)器的歸納偏置：機(jī)械式學(xué)習(xí)器沒(méi)有歸納偏置候選消除算法的歸納偏置：目標(biāo)概念c 包含在給定的假設(shè)空間H 中，即 h HFind-s 的歸納偏置：除了假設(shè)目標(biāo)概念須在假設(shè)空間中，還有另一個(gè)歸納偏置前提：任何實(shí)例，除非它的逆實(shí)例可由其他知識(shí)邏輯推出，否則它為反例。ID3 算法的歸納偏置： 較短的樹(shù)比較長(zhǎng)的樹(shù)優(yōu)先。那些信息增益高的屬性更靠近根節(jié)點(diǎn)的樹(shù)優(yōu)先。

13、反向傳播算法的歸納偏置：在數(shù)據(jù)之間平滑插值奧坎姆剃刀：優(yōu)先選擇擬合數(shù)據(jù)的最簡(jiǎn)單假設(shè)誤差平方最小化的法則尋找到極大似然假設(shè)的前提是：訓(xùn)練數(shù)據(jù)可以由目標(biāo)函數(shù)值加上正態(tài)分布噪聲來(lái)模擬使交叉熵最小化的法則尋找極大似然假設(shè)基于的前提是：觀察到的布爾值為輸入實(shí)例的概率函數(shù)對(duì)于不等式約束的條件極值問(wèn)題，可以用拉格朗日方法求解。于是得到拉格朗日方程如下：（ 3） 其中：（ 4）那么我們要處理的規(guī)劃問(wèn)題就變?yōu)椋海?5）（ 5）式是一個(gè)凸規(guī)劃問(wèn)題，其意義是先對(duì) 求偏導(dǎo)，令其等于0 消掉 ，然后再對(duì)w和b 求 L 的最小值。為此我們把（5）式做一個(gè)等價(jià)變換：上式即為對(duì)偶變換，這樣就把這個(gè)凸規(guī)劃問(wèn)題轉(zhuǎn)換成了對(duì)偶問(wèn)題：

14、（ 6）其意義是：原凸規(guī)劃問(wèn)題可以轉(zhuǎn)化為先對(duì)w和 b 求偏導(dǎo)， 令其等于0 消掉 w和 b，然后再對(duì) 求 L 的最大值。下面我們就來(lái)求解（6）式，為此我們先計(jì)算w和b的偏導(dǎo)數(shù)。由（3）式有：7）為了讓 L 在 w和 b 上取到最小值，令（7）式的兩個(gè)偏導(dǎo)數(shù)分別為0，于是得到：（ 8）將（8）代回（3）式，可得：（ 9）再把（9）代入（6）式有：考慮到（8）式，我們的對(duì)偶問(wèn)題就變?yōu)椋海?11）上式這個(gè)規(guī)劃問(wèn)題可以直接從數(shù)值方法計(jì)算求解。需要指出的一點(diǎn)是，（2）式的條件極值問(wèn)題能夠轉(zhuǎn)化為（5）式的凸規(guī)劃問(wèn)題，其中隱含著一個(gè)約束，即：（ 12）這個(gè)約束是這樣得來(lái)的，如果（2）和（5）等效，必有：把（3）式代入上式中，得到：化簡(jiǎn)得到：（ 13）又因?yàn)榧s束（1）式和（4）式，