機器學習復習總結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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