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

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)的決策提供直接或間接的反應(yī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è)樣例都有h(x)=c(x)，即 Consistent(h,D) ( 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=h H|C on siste nt(h,D)第三章決策樹(shù)適用問(wèn)題的特征：實(shí)例由 屬性-值對(duì)(pair)表示 目標(biāo)函數(shù)具有離散的輸出值 可能需要析取的描述 訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤 訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例ID3算法特點(diǎn)：搜

3、索完整的假設(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è)完整的假設(shè)空間，但不徹底地搜索這個(gè)空間 候選消除算法的搜索范圍是不完整的假設(shè)

4、空間，但徹底地搜索這個(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ò)誤或噪聲2. 特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點(diǎn)時(shí)，很可能出現(xiàn)巧合的規(guī)律性

5、，使得一些屬性恰巧 可以很好地分割樣例，但卻與實(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)練集合，三分之一作驗(yàn)證集合 錯(cuò)誤率降低修剪 (reduced-er

6、ror 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à)的規(guī)那么集合， 方法

7、是為從根節(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交叉方法

8、把訓(xùn)練樣例分成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í)例并迭代T次前饋網(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é)論適用于在隱藏層使用sigmoid單元、

9、在輸出層使用非閾值線性單元的網(wǎng)絡(luò)。所需的隱藏單元 數(shù)量依賴于要逼近的函數(shù)。任意函數(shù)：任意函數(shù)可以被一個(gè)有三層單元的網(wǎng)絡(luò)以任意精度逼近。兩個(gè)隱藏層使用sigmoid單元，輸出層使用線性單元，每層所需單元數(shù)不確定。第五章error s(h) Zns(h)(1 error s(h)nwin809%0,671,282,332.5興對(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ú)立

10、抽取k-fold交叉驗(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è)在

11、訓(xùn)練樣例上為0 錯(cuò)誤率一致學(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ù)貝葉斯最優(yōu)分類器的定義argmax P(vj |hi )P(hi |D) vj V hi H特點(diǎn)： 1。它所做的分類可以對(duì)應(yīng)于 H 中不存在的假設(shè)2.在給定可用數(shù)據(jù)、 假設(shè)空間及這些假設(shè)

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

13、 算法的歸納偏置 ：較短的樹(shù)比擬長(zhǎng)的樹(shù)優(yōu)先。 那些信息增益高的屬性更靠近根節(jié)點(diǎn)的樹(shù) 優(yōu)先。反向傳播算法的歸納偏置：在數(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)題，可以用拉格朗日方法求解。于是得到拉格朗日 方程如下：j2 J-JJl側(cè),礙=-H - e礙他M再+&-IHr - S塀耳3用+方十乞礙匕3-19-113其中：那么我們要處理的規(guī)劃問(wèn)題就變?yōu)?5式是一個(gè)凸

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