機器學習復習大綱

第一章機器學習涉及學科(八大學科)：人工智能、概率和統(tǒng)計、計算復雜性理論、控制論、信息論、心理學和神經(jīng)生物學、哲學。學習定義對于某類任務T和性能度量P，如果一個計算機程序在T上以P衡量的性能隨著經(jīng)驗E而自我完善，那么我們稱這個計算機程序在從經(jīng)驗E中學習。設計一個學習系統(tǒng)(五個步驟)：選擇訓練經(jīng)驗②選擇目標函數(shù)③選擇目標函數(shù)的表示④選擇函數(shù)逼近算法⑤最終設計最終設計(四個模塊)執(zhí)行系統(tǒng)：用學會的目標函數(shù)來解決給定的任務。鑒定器：以對弈的路線或歷史記錄作為輸入，輸出目標函數(shù)的一系列訓練樣例。泛化器：以訓練樣例為輸入，產(chǎn)生一個輸出假設，作為它對目標函數(shù)的估計。實驗生成器：以當前的假設作為輸入，輸出一個新的問題，供執(zhí)行系統(tǒng)去探索。第二章概念學習：是指從有關某個布爾函數(shù)的輸入輸出訓練樣例中推斷出該布爾函數(shù)。*****題型設計：計算實例、語法不同、語義不同的假設個數(shù)(P17頁)FIND-S尋找極大特殊假設“一致”的定義:一個假設h與訓練樣例集合D一致，當且僅當對D中每一個樣例<x,c(x)>都有h(x)=c(x)，即Consistent(h,D)三(V<x,c(x)>￡D)h(x)=c(x)“一致”與“滿足”的關系變型空間(versionspace):與訓練樣例一致的所有假設組成的集合;表示了目標概念的所有合理的變型關于H和D的變型空間，記為VSH,D，是H中與訓練樣例D一致的所有假設構(gòu)成的子集VSHD={heH|Consistent(h,D)} '*****題型設計：求一般邊界和特殊邊界，候選消除算法(習題2-4,2-5)需要什么樣的訓練樣例一般來說，概念學習的最優(yōu)查詢策略，是產(chǎn)生實例以滿足當前變型空間中大約半數(shù)的假設。這樣，變型空間的大小可以在遇到每個新樣例時減半，正確的目標概念就可在只用log2IVSI次實驗后得到。X的幕集:一般來說在集合X上定義的相異子集數(shù)目(X幕集的大小)為2|x|，其中|X|是X的元素數(shù)目。歸納學習需要的預先假定，稱為歸納偏置?？梢杂脷w納偏執(zhí)來描述不同學習方法的特征。第三章決策樹學習是應用最廣的歸納推理算法之一，是一種逼近離散值函數(shù)的方法決策樹適用問題的特征：實例由“屬性-值”對表示目標函數(shù)具有離散的輸出值可能需要析取的描述訓練數(shù)據(jù)可以包含錯誤訓練數(shù)據(jù)可以包含缺少屬性值的實例.*****題型設計：畫決策樹(習題3-1)用熵度量樣例的均一性嫡刻畫了任意樣例集的純度，給定包含關于某個目標概念的正反樣例的樣例集S，那么S相

對這個布爾型分類的嫡為Entropy(s)=-plogp—plogp十 2 十一2 —用信息增益度量期望的熵降低Gain(S,Gain(S,A)=Entropy(S)- ￡ Entropy(S)ISI vveValues(A)*****題型設計：求嫡和信息增益(習題3-2)過度擬合定義：給定一個假設空間H,一個假設heH,如果存在其他的假設h'eH,使得在訓練樣例上h的錯誤率比h'小，但在整個實例分布上h'的錯誤率比h小，那么就說假設h過度擬合訓練數(shù)據(jù)。避免過度擬合的兩種途徑：①及早停止樹增長②后修剪法第五章當給定的數(shù)據(jù)集有限時，要學習一個概念并估計其將來的精度，存在兩個很關鍵的困難：估計的偏差②估計的方差樣本錯誤率和真實錯誤率1f(x)豐h(x)0otherwise定義：假設h關于目標函數(shù)f1f(x)豐h(x)0otherwiseerror(h)=—^5(f(x),h(x)) 6(f(x),h(x))=snxeS定義：假設h關于目標函數(shù)f和分布D的真實錯誤率(標記為errorD(h))error(h)=Pr[f(x)。h(x)]D xeD3.定義zN為計算N%置信區(qū)間的常數(shù)(取值見表5-1)，計算errorD(h^TN%置信區(qū)間的一般表達式(公式5.1)為：(^)+ ierror(h)(1-error(h))n\ n定義：針對任意參數(shù)p的估計量Y的估計偏差是：E[Y]-p如果估計偏差為0,稱Y為p的無偏估計量。通常描述某估計的不確定性的方法是使用置信區(qū)間，真實的值以一定的概率落入該區(qū)間中，這樣的估計稱為置信區(qū)間估計。定義：某個參數(shù)p的N%置信區(qū)間是一個以N%的概率包含p的區(qū)間*****題型設計：求置信區(qū)間、單側(cè)和雙側(cè)邊界(習題5-3)第六章貝葉斯學習方法的特性觀察到的每個訓練樣例可以增量地降低或升高某假設的估計概率。而其他算法會在某個假設與任一樣例不一致時完全去掉該假設先驗知識可以與觀察數(shù)據(jù)一起決定假設的最終概率，先驗知識的形式是：1)每個候選假設的先驗概率；2)每個可能假設在可觀察數(shù)據(jù)上的概率分布貝葉斯方法可允許假設做出不確定性的預測新的實例分類可由多個假設一起做出預測，用它們的概率來加權即使在貝葉斯方法計算復雜度較高時，它們?nèi)钥勺鳛橐粋€最優(yōu)的決策標準衡量其他方法最佳假設：一種方法是把它定義為在給定數(shù)據(jù)D以及H中不同假設的先驗概率的有關知識下的最可能假設。用P(h)表示在沒有訓練數(shù)據(jù)前假設h擁有的初始概率。P(h)被稱為h的先驗概率。類似地，P(D)表示訓練數(shù)據(jù)D的先驗概率，P(Dlh)表示假設h成立時D的概率。機器學習中，我們關心的是P(hlD)，即給定D時h的成立的概率，稱為h的后驗概率。貝葉斯公式提供了從先驗概率P(h)、P(D)和P(Dlh)計算后驗概率P(hlD)的方法：P(hlD)=P(D|岫)P(D)學習器在候選假設集合H中尋找給定數(shù)據(jù)D時可能性最大的假設h，h被稱為極大后驗假設(MaximumAPosteriori,MAP). 一P(Dlh)P(h) h=argmaxP(hlD)=argmax =argmaxP(Dlh)P(h)heH heH P(D) heHP(Dlh)常被稱為給定h時數(shù)據(jù)D的似然度，而使P(Dlh)最大的假設被稱為極大似然假設(MaximumLikelihoodPosteriori,MLP)h=argmaxP(Dlh)heH貝葉斯推理的結(jié)果很大程度上依賴于先驗概率，另外不是完全接受或拒絕假設，只是在觀察到較多的數(shù)據(jù)后增大或減小了假設的可能性。—致學習器：如果某個學習器輸出的假設在訓練樣例上為0錯誤率，則稱為一致學習器。如果H上有均勻的先驗概率，且訓練數(shù)據(jù)是確定性和無噪聲的，任意一致學習器將輸出一個MAP假設。通過簡單的貝葉斯分析，可以表明在特定前提下，任一學習算法如果使輸出的假設預測和訓練數(shù)據(jù)之間的誤差平方和最小化，它將輸出一極大似然假設。最小描述長度準則(MinimumDescriptionLength,MDL)MDL準則提供了一種方法在假設的復雜性和假設產(chǎn)生錯誤的數(shù)量之間進行折中，它有可能選擇一個較短的產(chǎn)生少量錯誤的假設，而不是完美地分類訓練數(shù)據(jù)的較長的假設。上面討論自然給出了一種處理數(shù)據(jù)過度擬合的方法。*****題型設計：貝葉斯最優(yōu)分類器(P125頁)樸素貝葉斯分類器基于一個簡單的假定：在給定目標值時屬性值之間相互條件獨立。只要條件獨立性得到滿足，樸素貝葉斯分類vNB等于MAP分類，否則是近似。EM算法：期望最大化第八章1?k-近鄰算法*****題型設計：計算幾個點之間的距離來自統(tǒng)計模式識別領域的術語回歸：逼近一個實數(shù)值的目標函數(shù)殘差：逼近目標函數(shù)時的誤差核函數(shù)：一個距離函數(shù)，用來決定每個訓練樣例的權值，就是使wi=K(d(xi,xq))的函數(shù)K局部加權回歸的名稱解釋局部：目標函數(shù)的逼近僅僅根據(jù)查詢點附近的數(shù)據(jù)加權：每個訓練樣例的貢獻由它與查詢點間的距離加權得到回歸：表示逼近實數(shù)值函數(shù)的問題4?k-近鄰算法和局部加權回歸具有三個共同的關鍵特性：消極學習方法通過分析相似的實例來分類新的查詢實例，而忽略與查詢極其不同的實例實例表示為n維歐氏空間中的實數(shù)點基于案例的推理（Case-BasedReasoning,CBR）滿足前2個原則，但不滿足第3個消極方法和積極方法的差異：計算時間的差異消極算法在訓練時需要較少的計算，但在預測新查詢的目標值時需要更多的計算時間對新查詢的分類的差異（歸納偏置的差異）消極方法在決定如何從訓練數(shù)據(jù)D中泛化時考慮查詢實例xq，積極方法在見到xq之前，就完成了泛化 9 9核心觀點：消極學習可以通過很多局部逼近的組合表示目標函數(shù)，積極學習必須在訓練時提交單個的全局逼近第九章GA：遺傳算法最常見的算子是交叉和變異*****題型設計：單點交叉、兩點交叉和均勻交叉的選擇假設的概率計算方法適應度比例選擇（或稱輪盤賭選擇）：選擇某假設的概率是通過這個假設的適應度與當前群體中其他成員的適應度的比值得到的錦標賽選擇：先從當前群體中隨機選取兩個假設，再按照事先定義的概率p選擇適應度較高的假設，按照概率1-p選擇適應度較低的假設排序選擇:當前群體中的假設按適應度排序，某假設的概率與它在排序列表中的位置成比例，而不是與適應度成比例遺傳算法應用中的一個難題：擁擠問題擁擠：群體中某個體適應度大大高于其他個體，因此它迅速繁殖，以至于此個體和與它相似的個體占據(jù)了群體的絕大部分。擁擠降低了群體的多樣性，從而減慢了進化的進程。降低擁擠的策略：使用錦標賽選擇或排序選擇，而不用適應度比例輪盤賭選擇。適應度共享，根據(jù)群體中與某個體相似的個體數(shù)量，減小該個體的適應度，對可重組生成后代的個體種類進行限制，比如受到生物進化的啟示。通過只允許最相似的個體重組，可以在群體中促成相似的個體聚類，形成亞種，按空間分布個體，只允許相鄰的個體重組。第十三章增強學習問題與普通函數(shù)逼近問題有幾個重要的不同：延遲回報：施教者只在機器人執(zhí)行其序列動作時提供一個序列