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

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

2、集合D 一致，當(dāng)且僅當(dāng)對D中每一個樣例都有h(x)=c(x)，即 Consistent(h,D) ( D)h(x)=c(x)一個樣例x在h(x)=1時稱為滿足假設(shè)h,無論x是目標(biāo)概念的正例還是反例。 當(dāng)一假設(shè)能正確劃分一個正例時，稱該假設(shè)覆蓋該正例。變型空間(version space):與訓(xùn)練樣例一致的所有假設(shè)組成的集合，表示了目標(biāo)概念的所 有合理的變型，VS H,D=h H|C on siste nt(h,D)第三章決策樹適用問題的特征：實例由 屬性-值對(pair)表示 目標(biāo)函數(shù)具有離散的輸出值 可能需要析取的描述 訓(xùn)練數(shù)據(jù)可以包含錯誤 訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實例ID3算法特點：搜

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

4、空間，但徹底地搜索這個空間ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來自搜索策略 候選消除算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來自對搜索空間的定義過度擬合：對于一個假設(shè)， 當(dāng)存在其他的假設(shè)對訓(xùn)練樣例的擬合比它差， 但事實上在實例的整個分布上 表現(xiàn)得卻更好時，我們說這個假設(shè)過度擬合訓(xùn)練樣例定義：給定一個假設(shè)空間 H，個假設(shè)h H，如果存在其他的假設(shè) h H，使得在訓(xùn)練樣例 上h的錯誤率比h小，但在整個實例分布上 h的錯誤率比h小，那么就說假設(shè) h過度擬合 訓(xùn)練數(shù)據(jù)導(dǎo)致過度擬合的原因1. 一種可能原因是訓(xùn)練樣例含有隨機(jī)錯誤或噪聲2. 特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點時，很可能出現(xiàn)巧合的規(guī)律性

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

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

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

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

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

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

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

12、的先驗概率下使新實例被正確分類的可能性到達(dá)最大樸素貝葉斯分類器的定義vNB argmaxP(vj)P(ai |vj)v j V i只要條件獨(dú)立性得到滿足，樸素貝葉斯分類vNB 等于 MAP 分類，否那么是近似區(qū)別： 沒有明確地搜索可能假設(shè)空間的過程 假設(shè)的形成不需要搜索， 只是簡單地計算訓(xùn)練樣例中不同數(shù)據(jù)組合的出現(xiàn)頻率各學(xué)習(xí)器的歸納偏置：機(jī)械式學(xué)習(xí)器沒有歸納偏置候選消除算法的歸納偏置： 目標(biāo)概念 c 包含在給定的假設(shè)空間 H 中，即 h H Find-s 的歸納偏置 ：除了假設(shè)目標(biāo)概念須在假設(shè)空間中，還有另一個歸納偏置前提：任何 實例，除非它的逆實例可由其他知識邏輯推出，否那么它為反例。ID3

13、 算法的歸納偏置 ：較短的樹比擬長的樹優(yōu)先。 那些信息增益高的屬性更靠近根節(jié)點的樹 優(yōu)先。反向傳播算法的歸納偏置：在數(shù)據(jù)之間平滑插值 奧坎姆剃刀 ：優(yōu)先選擇擬合數(shù)據(jù)的最簡單假設(shè) 誤差平方最小化的法那么尋找到極大似然假設(shè)的前提是 ：訓(xùn)練數(shù)據(jù)可以由目標(biāo)函數(shù)值加上正 態(tài)分布噪聲來模擬使交叉熵最小化的法那么尋找極大似然假設(shè)基于的前提是 ：觀察到的布爾值為輸入實例的概 率函數(shù)對于不等式約束的條件極值問題，可以用拉格朗日方法求解。于是得到拉格朗日 方程如下：j2 J-JJl側(cè),礙=-H - e礙他M再+&-IHr - S塀耳3用+方十乞礙匕3-19-113其中：那么我們要處理的規(guī)劃問題就變?yōu)?5式是一個凸

14、規(guī)劃問題，其意義是先對 后再對w和b求L的最小值。為此我們把a(bǔ)求偏導(dǎo)，令其等于0消掉a,然5式做一個等價變換：min maxwj 居上式即為對偶變換，這樣就把這個凸規(guī)劃問題轉(zhuǎn)換成了對偶問題:rn ax min L f屯曲啜丿6其意義是：原凸規(guī)劃問題可以轉(zhuǎn)化為先對 w和b求偏導(dǎo)，令其等于0消掉w和b， 然后再對a求L的最大值。下面我們就來求解6式，為此我們先計算w和b 的偏導(dǎo)數(shù)。由3式有：(7)0,于是得到:為了讓L在w和b上取到最小值，令7式的兩個偏導(dǎo)數(shù)分別為2-178將8代回3式，可得:1 E f1i%嚴(yán)何響制時-神刀書込-吃和“Jj-li-li-1=|w| _wh_aq+22 牛 1 a=Z4wfi-l乙| A ij-lE M 問再把9代入6式有：j f S10碑 I i-lz ；-1 問考慮到8式，我們的對偶問題就變?yōu)椋簉naz 憶礙-于另吟皿伝?！繄R |jl i-l J-LJI血遲礙乃二o;-1蟲 011上式這個規(guī)劃問題可以直接從數(shù)值方法計算求解。5式的凸規(guī)需要指出的一點是，2式的條件極值問題能夠轉(zhuǎn)化為 劃問題，其中隱含著一個約束，即：舛価何齊+3-1二0這個約束是這樣得來的，如果2和5等效，必有：m ax把3式代入上式中，得到:藝JIJ二訥-駅 ir乞逼3 *兀十巧Tm一m斛工必也他延+。-1=013又因為