機(jī)器學(xué)習(xí)讀書(shū)筆記

機(jī)器學(xué)習(xí)讀書(shū)筆記〔一〕機(jī)器學(xué)習(xí)的根本概念和學(xué)習(xí)系統(tǒng)的設(shè)計(jì)最近在看機(jī)器學(xué)習(xí)的書(shū)和視頻，我的感覺(jué)是機(jī)器學(xué)習(xí)是很用的東西，而且是很多學(xué)科交叉形成的領(lǐng)域。最相關(guān)的幾個(gè)領(lǐng)域要屬人工智能、概率統(tǒng)計(jì)、計(jì)算復(fù)雜性理論、計(jì)算智能。機(jī)器學(xué)習(xí)的定義《機(jī)器學(xué)習(xí)》ByM.Mitchell第一章中和斯坦福機(jī)器學(xué)習(xí)公開(kāi)課第一課都提到了一個(gè)這樣定義：對(duì)于某類任務(wù)T和性能度量P，如果一個(gè)計(jì)算機(jī)程序在T上以P衡量的性能隨著經(jīng)驗(yàn)E而自我完善，那么我們稱這個(gè)計(jì)算機(jī)程序從經(jīng)驗(yàn)E中學(xué)習(xí)。并舉了一個(gè)例子，西洋跳棋學(xué)習(xí)問(wèn)題：任務(wù)T：下西洋跳棋性能標(biāo)準(zhǔn)P：比賽中擊敗對(duì)手的百分比訓(xùn)練經(jīng)驗(yàn)E：和自己進(jìn)行對(duì)弈這個(gè)例子很清楚的解釋了上面的定義，后面會(huì)以這個(gè)例子來(lái)說(shuō)明機(jī)器學(xué)習(xí)的根本設(shè)計(jì)方法。設(shè)計(jì)學(xué)習(xí)系統(tǒng)選擇任務(wù)根據(jù)上面的定義，我們就選擇任務(wù)是學(xué)習(xí)下西洋跳棋。選擇性能標(biāo)準(zhǔn)在世界錦標(biāo)賽中的獲勝百分比訓(xùn)練經(jīng)驗(yàn)選擇相比上面兩個(gè)，這個(gè)選擇要考慮的東西要麻煩得多，因?yàn)榻o學(xué)習(xí)器提供的訓(xùn)練經(jīng)驗(yàn)對(duì)它的成敗有重大的影響。一個(gè)關(guān)鍵的選擇準(zhǔn)那么是訓(xùn)練經(jīng)驗(yàn)必須要能對(duì)學(xué)習(xí)器的決策提供直接或間接的反應(yīng)。以下西洋跳棋為例子,提供直接反應(yīng)的訓(xùn)練樣例，即各種棋盤(pán)狀態(tài)和相應(yīng)的正確走子。提供間接反應(yīng)的訓(xùn)練樣例，很多過(guò)去對(duì)弈序列和最終結(jié)局。對(duì)于這種情況，存在著一個(gè)信用分配的問(wèn)題，也就是考慮每一次走子對(duì)最終結(jié)果的奉獻(xiàn)程度。這個(gè)問(wèn)題很難解決，以后再來(lái)談。(為什么？只要你下過(guò)棋，你就應(yīng)該明白，就算一開(kāi)始的走子是最正確的，后面下的很差一盤(pán)棋也會(huì)輸?shù)簦粗?，一開(kāi)始走得不是最正確的，但是也有可能反敗為勝)第二個(gè)重要的準(zhǔn)那么是學(xué)習(xí)期多大程度上可以控制訓(xùn)練樣例序列。我的理解是獲得訓(xùn)練樣例的自動(dòng)程度還是以下西洋跳棋為例子,1.訓(xùn)練樣例全是“手工”獲得的，即學(xué)習(xí)器需要的訓(xùn)練樣例是人工選取的棋盤(pán)狀態(tài)和該棋盤(pán)狀態(tài)下的一次正確走子。2.訓(xùn)練樣例是“半自動(dòng)”獲得的，即學(xué)習(xí)器需要的訓(xùn)練樣例是它本身自己選取的棋盤(pán)狀態(tài)〔它對(duì)這些棋盤(pán)狀態(tài)感到困惑〕，然后由人工指導(dǎo)它該如何正確走子。3.訓(xùn)練樣例是“全自動(dòng)”獲得的，學(xué)習(xí)器跟自己對(duì)弈來(lái)進(jìn)行學(xué)習(xí)。這種情況下，又有兩種情形：(1)試驗(yàn)它還未考慮過(guò)的全新棋局；(2)在它目前發(fā)現(xiàn)的最有效的路線的微小變化上對(duì)弈，來(lái)磨礪它的技能。第三個(gè)重要的準(zhǔn)那么是訓(xùn)練樣例的分布能多好地表示實(shí)例分布，而最終系統(tǒng)的性能P是通過(guò)后者來(lái)衡量的。一般而言，當(dāng)訓(xùn)練樣例的分布和將來(lái)的測(cè)試樣例的分布相似時(shí)，學(xué)習(xí)具有最大的可信度。比方，西洋跳棋學(xué)習(xí)中性能指標(biāo)P是該系統(tǒng)在世界錦標(biāo)賽上獲勝的百分比。假設(shè)說(shuō)世界錦標(biāo)賽上的選手都是萬(wàn)里挑一的高手，如果你給的訓(xùn)練樣例都是一些初學(xué)者下的棋局，那么可想而知，學(xué)習(xí)器最終會(huì)在世界錦標(biāo)賽上敗得很慘。不幸的是，通常情況下學(xué)習(xí)的樣例與最終學(xué)習(xí)系統(tǒng)被評(píng)估時(shí)使用的樣例有一定的差異，比方世界級(jí)的西洋跳棋冠軍可能不會(huì)有有興趣和一個(gè)程序下棋。然而，目前許多機(jī)器學(xué)習(xí)理論都依賴于訓(xùn)練樣例與測(cè)試樣例分布一致這一假設(shè)，但在實(shí)踐中這個(gè)假設(shè)經(jīng)常是不成立的。假設(shè)我們決定系統(tǒng)將通過(guò)和自己對(duì)弈來(lái)訓(xùn)練。這個(gè)好處是不需要人工干預(yù)，只要時(shí)間允許，可以讓系統(tǒng)產(chǎn)生無(wú)限多的訓(xùn)練數(shù)據(jù)。學(xué)習(xí)系統(tǒng)的具體設(shè)計(jì)步驟上面我們確定了學(xué)習(xí)框架：任務(wù)T：下西洋跳棋性能標(biāo)準(zhǔn)P：比賽中擊敗對(duì)手的百分比訓(xùn)練經(jīng)驗(yàn)E：和自己進(jìn)行對(duì)弈現(xiàn)在，有三個(gè)具體的內(nèi)容要確定：(1)要學(xué)習(xí)的知識(shí)確實(shí)切類型(2)對(duì)于這個(gè)目標(biāo)知識(shí)的表示(3)一種學(xué)習(xí)機(jī)制選擇目標(biāo)函數(shù)在機(jī)器學(xué)習(xí)中，要學(xué)習(xí)的知識(shí)確實(shí)切類型通常是一個(gè)函數(shù)，我們把它稱為目標(biāo)函數(shù)(TargetFunction)。在學(xué)習(xí)西洋跳棋中，我們要給出一個(gè)函數(shù)，它對(duì)任何給定的器具能選出最好的走法，假設(shè)記這個(gè)函數(shù)為ChooseMove，那么它的形式如下：ChooseMove:B->M其中B是合法棋局集合中的某一棋盤(pán)狀態(tài)，M是走子的方法。這樣，我們可以把提高任務(wù)T的性能P的問(wèn)題簡(jiǎn)化為學(xué)習(xí)像ChooseMove這樣某個(gè)特定的目標(biāo)函數(shù)的問(wèn)題。所以目標(biāo)函數(shù)的選擇是關(guān)鍵性的問(wèn)題。事實(shí)上，直接學(xué)習(xí)ChooseMove是非常困難的。所以一般情況下，我們把一個(gè)評(píng)估函數(shù)作為目標(biāo)函數(shù)。令這個(gè)函數(shù)為V，并用V：B->R來(lái)表示把任何合法的棋局映射到某一個(gè)實(shí)數(shù)值(R表示實(shí)數(shù)集合)。我們讓這個(gè)V給好的棋局賦予較高的評(píng)分。如果這個(gè)V被成功學(xué)習(xí)，那么系統(tǒng)就很容易找到當(dāng)前棋局的最正確走法。方法是，先產(chǎn)生每一個(gè)合法走子對(duì)應(yīng)的所有后繼棋局，然后用V來(lái)選取分值最高的后繼棋局，從而選擇最正確走子。現(xiàn)在一個(gè)重要問(wèn)題是，目標(biāo)函數(shù)V的準(zhǔn)確值是多少？我們可以如下定義V(b)：(1)如果b是一最終的勝局，V(b)=100(2)如果b是一最終的敗局，V(b)=–100(3)如果b是以最終的和局，V(b)=0(4)如果b不是最終棋局，那么V(b)=V(b’)，其中b’是從b開(kāi)始雙發(fā)都采取最優(yōu)對(duì)弈后可到達(dá)的終局。我們發(fā)現(xiàn)上面的定義雖然貌似很有道理，但有一個(gè)問(wèn)題，就是(4)中包含遞歸，因此運(yùn)算效率不高〔因?yàn)樗阉鲝腷開(kāi)始到達(dá)終局的所有路線〕，算法復(fù)雜度到達(dá)了實(shí)際不可操作的地步。所以V是一個(gè)理想目標(biāo)函數(shù)，我們必須找到一個(gè)V的可操作的描述，實(shí)際上就是一個(gè)近似地刻畫(huà)V的函數(shù)。由于這個(gè)原因，學(xué)習(xí)目標(biāo)函數(shù)的過(guò)程本質(zhì)上是函數(shù)逼近的過(guò)程。選擇目標(biāo)函數(shù)的表示如上所述，我們得到了理想的目標(biāo)函數(shù)，但我們實(shí)際上是要學(xué)習(xí)一個(gè)近似函數(shù)V’來(lái)描述〔或表示〕目標(biāo)函數(shù)?！稒C(jī)器學(xué)習(xí)》ByM.Mitchell書(shū)上說(shuō)這個(gè)描述包含一個(gè)重要的權(quán)衡過(guò)程，一方面，我們總希望選取一個(gè)非常有表征能力的描述，以最大可能地逼近理想的目標(biāo)函數(shù)V。另一方面，越有表征能力的描述需要越多的訓(xùn)練數(shù)據(jù)，使程序能從它表示的多種假設(shè)中選擇。這里剛好與GeorgeF.Luger的《人工智能：復(fù)雜問(wèn)題求解的結(jié)構(gòu)和策略》中的一句話不謀而合：“AI研究者所關(guān)心的兩個(gè)最根本的問(wèn)題是知識(shí)表示和搜索，而表現(xiàn)力〔特征抽取的結(jié)果〕和效率〔特征抽取算法的計(jì)算復(fù)雜度〕是評(píng)價(jià)知識(shí)表示語(yǔ)言的主要尺度”。在機(jī)器學(xué)習(xí)中，目標(biāo)函數(shù)就是知識(shí)，近似函數(shù)就是知識(shí)表示，后來(lái)我們可以知道，學(xué)習(xí)機(jī)制〔函數(shù)逼近算法〕就是搜索策略。所以，我覺(jué)得人工智能和機(jī)器學(xué)習(xí)本質(zhì)上其實(shí)是相同的東西，只不過(guò)前者在更理論的層面上〔討論意識(shí)和物理世界的關(guān)系〕，而后者更注重實(shí)踐〔解決實(shí)際問(wèn)題，例如下西洋跳棋〕。題外話到此，為了簡(jiǎn)化討論我們?yōu)槟繕?biāo)函數(shù)選擇一個(gè)簡(jiǎn)單的表示法：對(duì)于任何給定的棋盤(pán)狀態(tài)，函數(shù)V’可以通過(guò)以下棋盤(pán)參數(shù)的線性組合來(lái)計(jì)算：x1:棋盤(pán)上黑子的數(shù)量x2:棋盤(pán)上白子的數(shù)量x3:棋盤(pán)上黑王的數(shù)量x4:棋盤(pán)上紅王的數(shù)量x5:被紅字威脅的黑子數(shù)量(即會(huì)在下一次被紅子吃掉的黑子數(shù)量)x6:被黑子威脅的紅子的數(shù)量于是學(xué)習(xí)程序把V’(b)表示為一個(gè)線性函數(shù)V’(b)=w0+w1x1+w2x2+w3x3+w4x4+w5x5+w6x6其中，w0到w6為數(shù)字系數(shù)，或叫權(quán)，由學(xué)習(xí)算法來(lái)選擇。在決定某一個(gè)棋盤(pán)狀態(tài)值，權(quán)w1到w6決定了不同的棋盤(pán)特征的相對(duì)重要性，而權(quán)w0為一個(gè)附加的棋盤(pán)狀態(tài)值常量。好了，現(xiàn)在我們把學(xué)習(xí)西洋跳棋戰(zhàn)略的問(wèn)題轉(zhuǎn)化為學(xué)習(xí)目標(biāo)函數(shù)表示中系數(shù)w0到w6值的問(wèn)題，也即選擇函數(shù)逼近算法。選擇函數(shù)逼近算法為了學(xué)習(xí)V’(b)，我們需要一系列訓(xùn)練樣例，它的形式為<b,Vtrain(b)>其中，b是由x1-x6參數(shù)描述的棋盤(pán)狀態(tài)，Vtrain(b)是b的訓(xùn)練值。舉例來(lái)說(shuō)，<<x1=3,x2=0,x3=1,x4=0,x5=0,x6=0>,+100>;描述了一個(gè)黑棋取勝的棋盤(pán)狀態(tài)b，因?yàn)閤2=0表示紅旗已經(jīng)沒(méi)有子了。上面的訓(xùn)練樣例表示仍然有一個(gè)問(wèn)題：雖然對(duì)弈結(jié)束時(shí)最終狀態(tài)的棋盤(pán)的評(píng)分Vtrain(b)很好確定，但是大量中間狀態(tài)〔未分出勝負(fù)〕的棋盤(pán)如何評(píng)分呢？于是這里需要一個(gè)訓(xùn)練值估計(jì)法那么：Vtrain(b)<-V’(Successor(b))Successor(b)表示b之后再輪到程序走棋時(shí)的棋盤(pán)狀態(tài)〔也就是程序走了一步和對(duì)手回應(yīng)了一步以后的棋局〕。這個(gè)看起來(lái)有點(diǎn)難理解，我們用當(dāng)前的V’來(lái)估計(jì)訓(xùn)練值，又用這一訓(xùn)練值來(lái)更新V’。當(dāng)然，我們使用后續(xù)棋局Successor(b)的估計(jì)值來(lái)估計(jì)棋局b的值。直觀地講，越接近游戲結(jié)束的棋局的V’越趨向精確。事實(shí)上，可以證明這種基于對(duì)后繼棋局進(jìn)行估計(jì)的迭代估計(jì)訓(xùn)練值的方法，可以近乎完美地收斂到Vtrain估計(jì)值。接下來(lái)，我們面臨的就是如何調(diào)整權(quán)值的問(wèn)題。首先我們要定義如何最正確擬合訓(xùn)練數(shù)據(jù)，一種常用的方法是最小誤差平方和E：有很多算法可以得到線性函數(shù)的權(quán)使此定義的E最小化，這里我們選擇一個(gè)稱為最小均方法(LeastMeanSquares)的算法，它對(duì)可能的假設(shè)〔權(quán)值〕空間進(jìn)行隨機(jī)地梯度下降搜索，以使誤差平方和E最小化。LMS如下對(duì)wi進(jìn)行更新：對(duì)于每一個(gè)訓(xùn)練樣例<b,Vtrain(b)>使用當(dāng)前的權(quán)計(jì)算V’(b)對(duì)于每一個(gè)權(quán)值wi進(jìn)行如下更新這里就是一個(gè)小的常數(shù)〔比方0.1〕，用來(lái)調(diào)整向梯度方向移動(dòng)的步長(zhǎng)，之所以稱為梯度下降法，因?yàn)榭梢宰C明(Vtrain(b)-V’(b))xi實(shí)際上就是〔這里如有疑問(wèn)，看最后的補(bǔ)充局部〕。最終設(shè)計(jì)到此為止，我們的學(xué)習(xí)系統(tǒng)設(shè)計(jì)已經(jīng)完成，我們可以模塊化描述這個(gè)學(xué)習(xí)系統(tǒng)，下面這張圖來(lái)自《機(jī)器學(xué)習(xí)》ByM.Mitchell由圖可以知道，一個(gè)學(xué)習(xí)系統(tǒng)一般由四個(gè)模塊組成，以上面下西洋跳棋的學(xué)習(xí)系統(tǒng)為例：執(zhí)行系統(tǒng)：利用V’來(lái)做決策，決定下一步走法的策略鑒定器：以對(duì)弈的路線或歷史記錄作為輸入，輸出一系列訓(xùn)練樣例泛化器：以訓(xùn)練樣例為輸入，產(chǎn)生一個(gè)輸出假設(shè)，即目標(biāo)函數(shù)的描述V’實(shí)驗(yàn)生成器：以當(dāng)前的假設(shè)V’作為輸入，輸出一個(gè)新的問(wèn)題供執(zhí)行系統(tǒng)區(qū)探索。在下棋的例子中可以是給出一個(gè)初始棋局參考資料：機(jī)器學(xué)習(xí)ByM.Mitchell人工智能:復(fù)雜問(wèn)題求解的結(jié)構(gòu)和策略ByGeorgeF.Luger斯坦福公開(kāi)課機(jī)器學(xué)習(xí)第一課補(bǔ)充：上面提到這個(gè)梯度下降迭代式時(shí)這里要聲明一下，準(zhǔn)確地說(shuō)(Vtrain(b)-V’(b))xi是只有一個(gè)訓(xùn)練樣例時(shí)E的偏導(dǎo)當(dāng)有m個(gè)訓(xùn)練樣例時(shí):此時(shí)，上面這個(gè)式子稱為批梯度下降(BatchGradientDescent)，它一定會(huì)收斂到局部極小值〔實(shí)際上，線性回歸的平方函數(shù)通常是一個(gè)二次的碗狀函數(shù)，只有一個(gè)全局最小值〕。但是，它存在一個(gè)問(wèn)題，就是每次迭代要輸入全部的數(shù)據(jù)，當(dāng)訓(xùn)練樣例集很大時(shí)〔想象一個(gè)有幾百萬(wàn)條記錄的數(shù)據(jù)庫(kù)〕，這顯然是不劃算的。因此，上文中使用了這個(gè)式子，這個(gè)又稱為隨機(jī)梯度下降〔StochasticGradientDescent〕,或增量式梯度下降，每次輸入一個(gè)訓(xùn)練樣例。但是，它不一定會(huì)收斂到局部極小值，可能會(huì)在局部極小值附近徘徊。

機(jī)器學(xué)習(xí)讀書(shū)筆記〔二〕概念學(xué)習(xí)和歸納偏置感覺(jué)概念學(xué)習(xí)現(xiàn)在提得很少，可能是因?yàn)樵跈C(jī)器學(xué)習(xí)的實(shí)際應(yīng)用中很少用到，但是從概念學(xué)習(xí)中很容易引出歸納偏置的概念，而歸納偏置是個(gè)很重要的概念，因此這次會(huì)簡(jiǎn)單講講概念學(xué)習(xí)，著重于歸納偏置?？梢钥吹綒w納偏置對(duì)于機(jī)器學(xué)習(xí)的重要性。概念學(xué)習(xí)給定一樣例集合以及每個(gè)樣例是否屬于某一概念的標(biāo)注，怎樣自動(dòng)推斷出該概念的一般定義。這一問(wèn)題被稱為概念學(xué)習(xí)。一個(gè)更準(zhǔn)確的定義：概念學(xué)習(xí)是指從有關(guān)某個(gè)布爾函數(shù)的輸入輸出訓(xùn)練樣例中推斷出該布爾函數(shù)。注意，在前面一篇文章《機(jī)器學(xué)習(xí)的根本概念和學(xué)習(xí)系統(tǒng)的設(shè)計(jì)》中提到，機(jī)器學(xué)習(xí)中要學(xué)習(xí)的知識(shí)確實(shí)切類型通常是一個(gè)函數(shù)，在概念學(xué)習(xí)里面，這個(gè)函數(shù)被限定為是一個(gè)布爾函數(shù)，也就是它的輸出只有{0,1}〔0代表false，1〔代表true〕〕，也就是說(shuō)目標(biāo)函數(shù)的形式如下：f:X->{0,1}根據(jù)上面的定義，很明顯概念學(xué)習(xí)屬于監(jiān)督學(xué)習(xí)的分類問(wèn)題。舉一個(gè)《機(jī)器學(xué)習(xí)》Bymitchell書(shū)上的例子來(lái)更好的理解概念學(xué)習(xí)。目標(biāo)概念：Aldo〔人名〕會(huì)去海邊游泳的日子，注意，這里這樣描述不太好，很容易理解成我們要得到的表示目標(biāo)感念的函數(shù)輸出的是一串日期，不符合前面所說(shuō)的概念學(xué)習(xí)的目標(biāo)是推斷一個(gè)布爾函數(shù)，實(shí)際上，這里是給出一個(gè)日子，基于這一天的各種屬性，推斷Aldo是否會(huì)在這天去游泳。下面的表1描述了一系列日子的樣例，每個(gè)樣例表示為屬性的集合。屬性EnjoySport表示這一天Aldo是否樂(lè)于進(jìn)行水上運(yùn)動(dòng)，也是需要預(yù)測(cè)的屬性；Sky、AirTemp、Humidity、Wind、Water、Forcast是的屬性，就是要基于這些屬性來(lái)推斷Aldo是否會(huì)在這天去海邊游泳。表1目標(biāo)概念EnjoySport的正例和反例ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes接下來(lái)要確定假設(shè)〔目標(biāo)函數(shù)〕的形式，可以先考慮一個(gè)較為簡(jiǎn)單的形式，即實(shí)例的各個(gè)屬性的合取式。可令每個(gè)假設(shè)為6個(gè)約束的向量，這些約束指定了Sky、AirTemp、Humidity、Wind、Water、Forcast的值。每個(gè)屬性可取值為：由“？”表示任意本屬性可接受的值。明確指定的屬性值〔如warm〕。由“?”表示不接受任何值。如果某些實(shí)例x滿足假設(shè)h的所有約束，那么h將x分類為正例(h(x)=1)。比方，為判定Aldo只在寒冷的和潮濕的日子里進(jìn)行隨上運(yùn)動(dòng)〔并與其他屬性無(wú)關(guān)〕，這樣的假設(shè)可以表示為下面的表達(dá)式：<?,Cold,High,?,?,?>也就是要表達(dá)：ifAirTemp=Cold∧Humidity=HighthenEnjoySport=Yes那么最一般的假設(shè)是每一天都是正例，可表示為：<?,?,?,?,?,?>而最特殊的假設(shè)即每一天都是反例，表示為：<?,?,?,?,?,?>這里有幾點(diǎn)要注意：1.<?,?,?,?,?,?>和<?,?,?,?,?,?>、<?,?,?,?,?,?>等等其實(shí)是一樣的假設(shè)，也就是只要假設(shè)中有一個(gè)屬性為“?”，那么這個(gè)假設(shè)就表示每天都是反例。2.你很可能會(huì)疑心，這里假設(shè)的形式為什么一定是屬性的合取，假設(shè)屬性Humidity有3種取值：High、Normal和Low，那么就無(wú)法表達(dá)Aldo會(huì)在濕度Normal或High的時(shí)候去海邊游泳，因?yàn)檫@是一個(gè)析取式:ifHumidity=Normal∨Humidity=HighthenEnjoySport=Yes后面會(huì)講，斷言假設(shè)的形式為屬性的合取是一種歸納偏置，它使得我們的學(xué)習(xí)器是有偏的，如果學(xué)習(xí)器是無(wú)偏的，那么它根本上無(wú)法對(duì)未見(jiàn)實(shí)例進(jìn)行分類，這一點(diǎn)很重要，后面會(huì)慢慢解釋?，F(xiàn)在做一些術(shù)語(yǔ)定義，方便后面的表述：(1)待學(xué)習(xí)的概念或函數(shù)稱為目標(biāo)概念，記作c。(2)概念定義在一個(gè)實(shí)例集合上，這個(gè)集合表示為X。學(xué)習(xí)目標(biāo)概念時(shí)，必須提供一套訓(xùn)練樣例〔訓(xùn)練集，記為D〕，訓(xùn)練集中的人每個(gè)樣例為X中的一個(gè)實(shí)例x和它的目標(biāo)概念值c(x)〔如上面的表1中的example〕。c(x)=1，x稱為正例(positive)；c(x)=0，x稱為反例(negative)。可以用序偶<x,c(x)>來(lái)描述訓(xùn)練樣例。(3)給定目標(biāo)概念c的訓(xùn)練樣例集，學(xué)習(xí)器面臨的問(wèn)題就是假設(shè)或估計(jì)c。使用符號(hào)H來(lái)表示所有可能假設(shè)的集合，也稱為假設(shè)空間，對(duì)于我們的問(wèn)題來(lái)說(shuō)假設(shè)空間就是所有各個(gè)屬性的合取式。H中的每個(gè)假設(shè)h表示X上定義的布爾函數(shù),即h:X->{0,1}。機(jī)器學(xué)習(xí)的目標(biāo)就是尋找一個(gè)假設(shè)h，使對(duì)于X中的所有x，h(x)=c(x)。歸納學(xué)習(xí)假設(shè)機(jī)器學(xué)習(xí)的任務(wù)是在實(shí)例集合X上尋找一個(gè)與目標(biāo)概念c相同的假設(shè)h，然而我們對(duì)于c僅有的信息只是它在訓(xùn)練結(jié)合上的值。因此，歸納學(xué)習(xí)算法最多只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬合。如果沒(méi)有更多的信息，我們只能假定，對(duì)于未見(jiàn)實(shí)例最好的假設(shè)就是與訓(xùn)練樣例數(shù)據(jù)最正確擬合的假設(shè)。這是一個(gè)歸納學(xué)習(xí)的根本假定。下面給出一個(gè)準(zhǔn)確的定義：歸納學(xué)習(xí)假設(shè)任一假設(shè)如果在足夠大的訓(xùn)練樣例集合中很好地逼近目標(biāo)函數(shù)，它也能在未見(jiàn)實(shí)例中很好地逼近目標(biāo)函數(shù)。那么現(xiàn)在該講講如何逼近目標(biāo)函數(shù)，也就是先前在《機(jī)器學(xué)習(xí)的根本概念和學(xué)習(xí)系統(tǒng)的設(shè)計(jì)》中提到的搜索策略，即如何搜索假設(shè)空間H獲得與目標(biāo)概念c一致的假設(shè)h。假設(shè)的一般到特殊序、變型空間和候選消除算法假設(shè)的一般到特殊序許多概念學(xué)習(xí)算法〔如這里要講的候選消除算法〕，搜索假設(shè)空間的方法依賴于一種針對(duì)任意概念學(xué)習(xí)都很有效的結(jié)構(gòu)：假設(shè)的一般到特殊序關(guān)系?？紤]下面兩個(gè)假設(shè)：h1=<Sunny,?,?,Strong,?,?>h2=<Sunny,?,?,?,?,?>很明顯，被h1劃分為正例的實(shí)例都會(huì)被h2劃分為正例，因此，可以說(shuō)h2比h1更一般，h1比h2更特殊。現(xiàn)在要定義“比……更一般”這種關(guān)系定義：令hj和hk為在X上定義的布爾函數(shù)。稱hjmore_general_than_or_equal_tohk〔記作hj≥ghk〕，當(dāng)且僅當(dāng)如果hj≥ghk∧(hk≠ghj)，那么就說(shuō)hj嚴(yán)格的more_general_thanhk〔寫(xiě)作hj>ghk〕，可以得出≥g的一些簡(jiǎn)單性質(zhì)：(1)自反性，hj≥ghj(2)反對(duì)稱，假設(shè)hj≥ghk，那么hk非≥ghj(3)傳遞性，假設(shè)hi≥ghj且hj≥ghk，那么hi≥ghk很明顯，≥g是假設(shè)空間H上的一個(gè)偏序關(guān)系?！輌很重要，因?yàn)樗诩僭O(shè)空間H上對(duì)任意概念學(xué)習(xí)問(wèn)題提供了一種有效的結(jié)構(gòu)，可以更加有效地搜索假設(shè)空間。變型空間為了更好的說(shuō)明變型空間，先給出一個(gè)定義：一個(gè)假設(shè)h與訓(xùn)練樣例集合D一致，當(dāng)且僅當(dāng)對(duì)D中每一個(gè)樣例<x,c(x)>都有h(x)=c(x)。記為馬上要提到的候選現(xiàn)出算法能夠表示與訓(xùn)練樣例一致的所有假設(shè)。在假設(shè)空間中的這一子集被稱為關(guān)于假設(shè)空間H和訓(xùn)練樣例D的變型空間，因?yàn)樗四繕?biāo)概念的所有合理的變型。定義：關(guān)于假設(shè)空間H和訓(xùn)練樣例集D的變型空間，標(biāo)記為VSH,D，是H中與訓(xùn)練樣例D一致的所有假設(shè)構(gòu)成的子集。使用上面介紹到的一般到特殊序的結(jié)構(gòu)，可以用更簡(jiǎn)潔的形式表示變型空間。變型空間可以表示為它的極大一般的和極大特殊的成員。看下面一個(gè)假設(shè)〔怎么得到的先不管〕，h=<Sunny,Warm,?,Strong,?,?>這個(gè)h和表1中的4個(gè)訓(xùn)練樣例一致，實(shí)際上，這只是與訓(xùn)練樣例一致的所有6個(gè)假設(shè)之一。下面的圖1給出了這個(gè)6假設(shè)：圖1圖1中的6個(gè)假設(shè)構(gòu)成一個(gè)變型空間〔6個(gè)假設(shè)都與訓(xùn)練樣例集一致〕，箭頭表示實(shí)例間的more_general_than關(guān)系。其中S就是極大特殊假設(shè)的集合，而G就是極大一般假設(shè)的集合，圖上很容易看出，如果給定G和S那么很容易通過(guò)一般到特殊偏序結(jié)構(gòu)來(lái)生成S和G之間的所有假設(shè)，因此只需要給定極大特殊假設(shè)的集合和極大一般假設(shè)的集合，就能夠完整地表示一個(gè)變型空間。下面給出準(zhǔn)確的定義：一般邊界：關(guān)于假設(shè)空間H和訓(xùn)練數(shù)據(jù)D的一般邊界〔generalboundary〕G，是在H中與D相一致的極大一般成員的集合。特殊邊界：關(guān)于假設(shè)空間H和訓(xùn)練數(shù)據(jù)D的特殊邊界〔specificboundary〕S，是在H中與D相一致的極大特殊成員的集合。變型空間表示定理：令X為一任意的實(shí)例集合，H為X上定義的布爾假設(shè)的結(jié)合。令c:X->{0,1}為X上定義的任意目標(biāo)概念，并令D為任一訓(xùn)練樣例的集合{<x,c(x)>}。對(duì)所有的X,H,c,D以及良好定義的S和G：候選消除算法有了上面的一些預(yù)備知識(shí)，現(xiàn)在可以來(lái)說(shuō)明候選消除算法。算法的思路如下：獲得變型空間VSH,D，首先將G邊界和S邊界分別初始化為H中最一般的假設(shè)和最特殊的假設(shè)。即:G0<-{<?,?,?,?,?,?>}S0<-{<?,?,?,?,?,?>}然后處理每個(gè)訓(xùn)練樣例，使得S被一般化，G被特殊化，從而逐步縮小變型空間，消去變型空間中與樣例不一致的假設(shè)。偽代碼描述如下：候選消除算法，輸入訓(xùn)練樣例D，輸出由G和S表示的變型空間G<-{<?,?,?,?,?,?>}S<-{<?,?,?,?,?,?>}foreachdinD

{

if(d==positive)

{

foreachginG

{

if(g與d不一致)

{

從G中移去g;

}

}

foreachsinS

{

if(s與d不一致)

{

從S從移去s;

foreachs的極小一般化式h

{

if(h與d一致&&G的某個(gè)成員比h更一般)

{

將h參加到S中;

}

}

從S中移去所有這樣的假設(shè)：它比S中另一假設(shè)更一般;

}

}

}

else

{

foreachsinS

{

if(s與d不一致)

{

從S中移去s;

}

}

foreachginG

{

if(g與d不一致)

{

從G中移去g;

foreachg的極小特殊化式h

{

if(h與d一致&&S的某個(gè)成員比h更特殊)

{

將h參加到G中;

}

}

從G中移去所有這樣的假設(shè)：它比G中另一假設(shè)更特殊;

}

}

}

}簡(jiǎn)單總結(jié)一下上面的算法。正例使得變型空間的S邊界逐漸一般化，而反例扮演的角色恰好使得G邊界逐漸特殊化。每輸入一個(gè)訓(xùn)練樣例，S和G邊界將繼續(xù)單調(diào)移動(dòng)并相互靠近，劃分出越來(lái)越小的變型空間。對(duì)表1執(zhí)行候選消除算法，便可以得到圖1的結(jié)果。使用不完全學(xué)習(xí)概念進(jìn)行分類假設(shè)只提供了表1中的4個(gè)訓(xùn)練樣例，沒(méi)有更多的訓(xùn)練樣例，現(xiàn)在要對(duì)未見(jiàn)過(guò)的實(shí)例進(jìn)行分類。圖1表示的變型空間仍包含多個(gè)假設(shè)，即目標(biāo)概念還未完全學(xué)習(xí)到，但是仍然有可能對(duì)新樣例進(jìn)行一定可信度的分類。為示范這一過(guò)程，給出表2列出待分類的新實(shí)例：表2待分類的新實(shí)例InstanceSkyAirTempHumidityWindWaterForecastEnjoySportASunnyWarmNormalStrongCoolChange?BRainyColdNormalLightWarmSame?CSunnyWarmNormalLightWarmSame?DSunnyColdNormalStrongWarmSame?先看A，圖1所示的當(dāng)前的變型空間中的每個(gè)假設(shè)都將A分類為正例。由于變型空間的所有假設(shè)一致同意實(shí)例A為正例，學(xué)習(xí)器將A劃分為正例的可信度，與只有單個(gè)的目標(biāo)概念一樣〔當(dāng)然前提是假設(shè)了目標(biāo)概念一定在假設(shè)空間中，且訓(xùn)練樣例沒(méi)有錯(cuò)誤〕。事實(shí)上，只要S中的每個(gè)成員將實(shí)例劃分為正例，就可以斷言變型空間中的每個(gè)假設(shè)將其劃分正例，因?yàn)橛蒻ore_general_than定義，如果新的實(shí)例滿足S的所有成員，它一定也滿足這些更一般的假設(shè)。同樣，B被變型空間中的每個(gè)假設(shè)劃分為反例，可以放心地把B劃分為反例，即使概念學(xué)習(xí)是不完全的。只要實(shí)例不滿足G中的所有成員，那么該實(shí)例就可以被斷言為反例。碰到實(shí)例C就要注意了，變型空間中半數(shù)將C劃分為正例，半數(shù)劃分為反例。因此，學(xué)習(xí)器無(wú)法可信的分類地這一樣例，除非提供更多的訓(xùn)練樣例。實(shí)例D在變型空間中被兩個(gè)假設(shè)分為正例，被其他劃分為正例。這個(gè)例子的分類可信度比A和B要小，又比C要大。投票選取傾向于將其分類為反例，所以可以輸出擁有最大票數(shù)的分類，還可附帶一個(gè)可信度比例以說(shuō)明投票的傾向程度。〔注意，如果假定H中所有假設(shè)有相等的先驗(yàn)概率，那么投票的方法能得到新實(shí)例的最可能的分類〕現(xiàn)在，可以講講一個(gè)非常重要的概念，歸納偏置。歸納偏置如前所述，如果訓(xùn)練樣例沒(méi)有錯(cuò)誤，初始假設(shè)空間包含概念目標(biāo)時(shí)，如果提供足夠多的訓(xùn)練樣例，候選消除算法可以收斂到目標(biāo)概念。前面提到，斷言假設(shè)的形式為屬性的合取，事實(shí)上是為了縮小需要搜索的假設(shè)空間的范圍。這樣做的一個(gè)后果是，有可能目標(biāo)概念不在這樣一個(gè)初始的假設(shè)空間中。如果想要保證假設(shè)空間中包含目標(biāo)概念，一個(gè)明顯的方法是擴(kuò)大假設(shè)空間，使每個(gè)可能的假設(shè)都被包含在內(nèi)。再次以EnjoySport為例子，其中將假設(shè)空間限制為只包含屬性值的合取。由于這一限制，假設(shè)空間不能夠表示最簡(jiǎn)單的析取形式的目標(biāo)如“Sky=Sunny或Sky=Cloudy”。所以問(wèn)題在于，我們使學(xué)習(xí)器偏向于只考慮合取的假設(shè)。無(wú)偏學(xué)習(xí)的無(wú)用性好吧，居然這種偏向可能使得假設(shè)空間漏掉了目標(biāo)概念，那我們就提供一個(gè)表達(dá)能力更強(qiáng)的空間，它能表達(dá)所有的可教授概念。換言之，它能夠表達(dá)實(shí)例集X的所有可能的子集。一般我們把集合X的所有子集的集合稱為X的冪集〔powerset〕。假設(shè)AirTemp、Humidity、Wind、Water、Forcast都只有兩種可能取值，Sky有三種可能取值，那么實(shí)例空間X包含了3×2×2×2×2×2=96種不同的實(shí)例。根據(jù)集合的知識(shí)，在這一實(shí)例集合X的冪集的大小是2^|X|，其中|X|是X的元素?cái)?shù)目。因此在這一實(shí)例空間上可以定義2^96，或大約10^28個(gè)不同的目標(biāo)概念，我們稱包含了2^|X|個(gè)假設(shè)的這樣一個(gè)假設(shè)空間是一個(gè)無(wú)偏的假設(shè)空間。先前我們將假設(shè)空間限制為只包含屬性值的合取，那么只能表示1+4×3×3×3×3×3=973個(gè)假設(shè)。哈，看來(lái)我們先前的空間實(shí)在是一個(gè)偏置很大的假設(shè)空間。從感覺(jué)上講，無(wú)偏的假設(shè)空間雖然一定包含了目標(biāo)概念，但是它包含的假設(shè)的數(shù)量太大，搜索這樣一個(gè)空間必然會(huì)很費(fèi)時(shí)。然而，你馬上會(huì)發(fā)現(xiàn)，這里還存在一個(gè)根本的問(wèn)題：如果使用無(wú)偏的假設(shè)空間，概念學(xué)習(xí)算法將無(wú)法從訓(xùn)練樣例從泛化，要想得到單個(gè)目標(biāo)概念，必須提供X中所有的實(shí)例作為訓(xùn)練樣例。我們根本不能從這樣一個(gè)學(xué)習(xí)器中，得到對(duì)未知實(shí)例的分類?，F(xiàn)在來(lái)看看為什么這么說(shuō)。假定我們給學(xué)習(xí)器提供了3個(gè)正例(x1,x2,x3)以及反例(x4,x5)。這時(shí)，變型空間的S邊界包含的假設(shè)正好是三個(gè)正例的析?。篠:{(x1∨x2∨x3)}因?yàn)檫@是能覆蓋3個(gè)正例的最特殊假設(shè)。相似地，G邊界將由那些剛好能排除掉的那些假設(shè)組成。G:{否認(rèn)符號(hào)(x4∨x5)}問(wèn)題來(lái)了，在這一非常具有表達(dá)力的假設(shè)表示方法中，S邊界總是所有正例的析取式，G邊界總是所有反例的析取的否認(rèn)式。這樣能夠由S和G無(wú)歧義分類的，只有已見(jiàn)到的訓(xùn)練樣例本身。要想獲得單個(gè)目標(biāo)概念，就必須提供提供X中所有的實(shí)例作為訓(xùn)練樣例。好吧，為了防止這個(gè)問(wèn)題，我們只使用不完全學(xué)習(xí)得到的變型空間，像前面使用成員投票的方式對(duì)未見(jiàn)實(shí)例進(jìn)行分類。遺憾的是，你馬上會(huì)發(fā)現(xiàn)投票對(duì)于那些未見(jiàn)過(guò)的實(shí)例不起作用，為什么？未見(jiàn)實(shí)例會(huì)被變形空間中剛好半數(shù)的假設(shè)劃分為正例，而被另一半劃分為反例，原因如下，假設(shè)H是X的冪集，而x是某個(gè)未出現(xiàn)的實(shí)例，那么對(duì)于變型空間中一覆蓋x的假設(shè)h。必然存在另一假設(shè)h’，它與h幾乎相等，只不過(guò)對(duì)x的分類不同。而且，如果h在變型空間中，那么h’也在，因?yàn)樗鼘?duì)于已往訓(xùn)練樣例的劃分與h完全一樣。以上討論說(shuō)明了歸納推理的一個(gè)根本屬性：學(xué)習(xí)器如果不對(duì)目標(biāo)概念的形式做預(yù)先的假定，它從根本上無(wú)法對(duì)未見(jiàn)實(shí)例進(jìn)行分類。這便是無(wú)偏學(xué)習(xí)的無(wú)用性。我們?cè)瓉?lái)的EnjoySport任務(wù)中，候選消除算法能夠從訓(xùn)練樣例中泛化，惟一的原因就是它是有偏的，隱含假定了目標(biāo)概念可以由屬性值的合取來(lái)表示。由于歸納學(xué)習(xí)需要某種形式的預(yù)先假定，或稱為歸納偏置〔inductivebias〕，我們可以用歸納偏置來(lái)描述不同學(xué)習(xí)方法的特征。歸納偏置還有一個(gè)更術(shù)語(yǔ)化的定義，這里就不提了。簡(jiǎn)單的講，歸納偏置就是一個(gè)附加的前提集合B，以后還會(huì)提到，這個(gè)前提集合B有兩種情況，第一種是對(duì)假設(shè)空間進(jìn)行限定，就像候選消除算法那樣；第二種是假設(shè)空間是完整的假設(shè)空間，但是進(jìn)行不徹底的搜索，很多貪心算法都是這樣的，如以后會(huì)提到的決策樹(shù)算法。前一種歸納偏置叫做限定偏置，后一種叫做優(yōu)選偏置。在研究其他的歸納推理方法時(shí)，有必要牢記這種歸納偏置的存在及其強(qiáng)度。一種算法如果有偏性越強(qiáng)，那它的歸納能力越強(qiáng)，可以分類更多的未見(jiàn)實(shí)例。當(dāng)然，分類的正確性也依賴于歸納偏置的正確性。參考資料：機(jī)器學(xué)習(xí)ByM.Mitchell機(jī)器學(xué)習(xí)讀書(shū)筆記〔三〕決策樹(shù)決策樹(shù)可以說(shuō)是用的非常廣泛的學(xué)習(xí)算法，對(duì)噪聲數(shù)據(jù)有很好的健壯性，而且表達(dá)能力也很強(qiáng)〔機(jī)器學(xué)習(xí)讀書(shū)筆記〔二〕中的候選消除算法只能表示屬性的合取，決策樹(shù)可以表示屬性的析取〕。雖然決策樹(shù)不是最好的學(xué)習(xí)算法，但是目前最牛哄哄的幾個(gè)學(xué)習(xí)算法，如boosting和隨機(jī)森林〔RandomForest〕在內(nèi)部都使用了決策樹(shù)，因此很有必要深入了解一下決策樹(shù)。--------------------------------------------------------------------------------簡(jiǎn)介及決策樹(shù)表示法在《機(jī)器學(xué)習(xí)》ByMitchell書(shū)中講到?jīng)Q策樹(shù)是一種逼近離散值目標(biāo)函數(shù)的方法，也就是說(shuō)決策樹(shù)適用于分類(classification)問(wèn)題，事實(shí)上，決策樹(shù)也可以用來(lái)做回歸〔regression〕,例如有名的CART〔ClassficationandRegressionTree，分類與回歸樹(shù)〕系統(tǒng)〔由Friedman和Breiman兩個(gè)大牛提出來(lái)的〕。這里還是主要講如何使用決策樹(shù)學(xué)習(xí)來(lái)解決分類問(wèn)題。下面的圖是一個(gè)通常的決策樹(shù)表示：由于以樹(shù)的形式表達(dá)，決策樹(shù)的一個(gè)優(yōu)點(diǎn)就是讓人一目了然，也很符合人的思維習(xí)慣〔人在做某個(gè)決定時(shí)，總會(huì)將一系列需要考慮的”因素”按某種重要性準(zhǔn)那么先排個(gè)序，然后優(yōu)先考慮該因素〕。圖上是一個(gè)根據(jù)天氣情況分類“星期六上午是否適合打網(wǎng)球“的決策樹(shù)，每一個(gè)非葉子節(jié)點(diǎn)都指定了對(duì)待分類實(shí)例的某個(gè)屬性的測(cè)試(如Outlook表示測(cè)試天氣預(yù)報(bào)的情況，即詢問(wèn)天氣預(yù)報(bào)的情況是晴天Sunny，陰天Overcast，還是下雨Rain？)，并且該節(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值；每一個(gè)葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。分類實(shí)例的方法就是從樹(shù)的根節(jié)點(diǎn)開(kāi)始，測(cè)試這個(gè)節(jié)點(diǎn)指定的屬性，然后按照給定實(shí)例的該屬性值對(duì)應(yīng)的樹(shù)枝向下移動(dòng)。然后這個(gè)過(guò)程在新節(jié)點(diǎn)為根的子樹(shù)上重復(fù)，直到到達(dá)葉子節(jié)點(diǎn)。舉一個(gè)例子，假設(shè)實(shí)例的表示形式為<Outlook,Temperature,Humidity,Wind,PlayTennis>，令某一個(gè)具體的實(shí)例為x=<Rain,Hot,High,Weak,?>，在根節(jié)點(diǎn)上測(cè)試屬性O(shè)utlook，該樣例的Outlook=“Rain”，那么就沿著標(biāo)記“Rain”的樹(shù)枝向下移動(dòng)到達(dá)新的節(jié)點(diǎn)Wind，于是再測(cè)試實(shí)例的屬性Wind=“Weak”，沿著”Weak”樹(shù)枝移動(dòng)到葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)把x分類為Yes，也即目標(biāo)屬性PlayTennis=Yes。這里要注意，上圖中的樹(shù)為一棵多叉樹(shù)，節(jié)點(diǎn)的后繼分支數(shù)由節(jié)點(diǎn)上測(cè)試屬性取值的個(gè)數(shù)決定。然而在計(jì)算機(jī)中，多叉樹(shù)比擬難于表示，而二叉樹(shù)易于表示，且二叉樹(shù)有很多優(yōu)良的屬性，因此在編寫(xiě)程序時(shí)，一般以二叉樹(shù)的形式來(lái)表示決策樹(shù)，稱為二叉決策樹(shù)，也就是上面提到的CART系統(tǒng)。本質(zhì)上，決策樹(shù)代表實(shí)例屬性值約束的合取的析取式。從樹(shù)根到樹(shù)葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹(shù)本身對(duì)應(yīng)這些合取的析取。例如上圖表示的決策樹(shù)對(duì)應(yīng)于以下表達(dá)式：(Outlook=Sunny∧Humidity=Normal)∨(Outlook=Overcast)∨(Outlook=Rain∧Wind=Weak)--------------------------------------------------------------------------------決策樹(shù)學(xué)習(xí)的適用問(wèn)題通常決策樹(shù)學(xué)習(xí)最適合具有以下特征的問(wèn)題：1.實(shí)例是由“屬性-值”對(duì)表示的：實(shí)例是用一系列固定的屬性和它們的值來(lái)描述的〔如上面的例子中的x〕。最簡(jiǎn)單的決策樹(shù)學(xué)習(xí)中，每一個(gè)屬性只取少數(shù)的離散的值〔例如，Temperature取Hot、Mild和Cold〕。然而，很容易擴(kuò)展到也允許處理值域?yàn)閷?shí)數(shù)〔連續(xù)值〕的屬性。2.目標(biāo)函數(shù)具有離散的輸出值，也就是說(shuō)要解決的問(wèn)題是一個(gè)分類問(wèn)題。實(shí)際上，如一開(kāi)始講述的，決策樹(shù)也可以用來(lái)做回歸問(wèn)題。3.可能需要析取的描述。4.訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤。決策樹(shù)對(duì)于噪聲有很好的健壯性。無(wú)論是目標(biāo)值屬性的錯(cuò)誤〔即分類錯(cuò)誤〕還是描述屬性錯(cuò)誤。5.訓(xùn)練樣例可以包含缺少屬性值的實(shí)例：決策樹(shù)學(xué)習(xí)甚至可以在有未知屬性值的訓(xùn)練樣例中使用。這個(gè)問(wèn)題后面會(huì)進(jìn)行討論理解決策樹(shù)算法思路的關(guān)鍵是決策樹(shù)的歸納偏置〔歸納偏置的概念參見(jiàn)機(jī)器學(xué)習(xí)讀書(shū)筆記〔二〕，它是學(xué)習(xí)算法的一個(gè)重要特征〕，這個(gè)偏置被稱為奧坎姆剃刀〔occam’srazor〕。--------------------------------------------------------------------------------根本的決策學(xué)習(xí)算法大多數(shù)已開(kāi)發(fā)的決策樹(shù)學(xué)習(xí)算法是一種核心算法的變體。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹(shù)空間。這種方法是ID3算法〔Quinlan1986〕和后繼的C4.5算法〔Quinlan1993〕的根底。下面給出經(jīng)典的ID3算法的概要：///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////ID3(Examples,Target_attribute,Attributes)輸入：Examples即訓(xùn)練樣例集。Target_attribute是這棵樹(shù)要預(yù)測(cè)的目標(biāo)屬性。Attributes是除目標(biāo)屬性外供學(xué)習(xí)到得決策樹(shù)測(cè)試的屬性列表。輸出：返回一棵能正確分類給定Examples的決策樹(shù)偽代碼表示：{創(chuàng)立樹(shù)的Root節(jié)點(diǎn)if(Examples都為正)//決策樹(shù)增長(zhǎng)終止條件返回label=+的單節(jié)點(diǎn)樹(shù)Rootif(Examples都為反)//決策樹(shù)增長(zhǎng)終止條件返回label=-的單節(jié)點(diǎn)樹(shù)Rootif(Attributes為空)//決策樹(shù)增長(zhǎng)終止條件那么返回單節(jié)點(diǎn)樹(shù)Root,label=Examples中最普遍的Target_attributes值A(chǔ)<-Attributes中分類Examples能力最好的屬性Root的決策屬性<-Aforeach(ainA)//a為屬性A的每個(gè)可能取值a{在Root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=a令Examples(a)為Examples中滿足A屬性值為a的子集在這個(gè)新分支下加一個(gè)子樹(shù)ID3(Examples(a),Target_attribute,Attributes-{A})}返回Root}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////算法的過(guò)程并不復(fù)雜，就是不斷選取某個(gè)屬性對(duì)樣例集劃分直到?jīng)Q策樹(shù)增長(zhǎng)終止條件滿足為止。終止條件為：1.節(jié)點(diǎn)是一個(gè)純節(jié)點(diǎn)，即從某一分支到達(dá)該節(jié)點(diǎn)上所有的樣例〔這些樣例滿足分支上的屬性測(cè)試的值〕屬于同一個(gè)分類。2.所有屬性都已經(jīng)被作為測(cè)試屬性使用過(guò)了?？傊?，上面的算法就是一種自頂向下增長(zhǎng)樹(shù)的貪婪算法，在每個(gè)節(jié)點(diǎn)選取最好地劃分樣例的屬性。繼續(xù)這個(gè)過(guò)程直到這棵樹(shù)完美分類訓(xùn)練樣例，或所有的屬性都已被使用過(guò)?，F(xiàn)在有一個(gè)重要的問(wèn)題是：如何選擇在樹(shù)的每個(gè)節(jié)點(diǎn)要測(cè)試的屬性？這里頂一個(gè)統(tǒng)計(jì)屬性，稱為信息增益，它用來(lái)來(lái)衡量給定的屬性區(qū)分訓(xùn)練樣例的能力。--------------------------------------------------------------------------------熵和信息增益什么樣的屬性才是最好地分類樣例的屬性？直覺(jué)上講，如果訓(xùn)練樣例集被某個(gè)屬性A劃分，得到的所有子樣例集〔每個(gè)子樣例集中的子樣例滿足A的某個(gè)取值a〕如果都是“純潔”的，也就是說(shuō)各個(gè)子樣例集中的子樣例〔根據(jù)目標(biāo)屬性的取值〕都屬于同一個(gè)分類，那么這個(gè)屬性A絕對(duì)是對(duì)能夠最好的區(qū)分樣例的屬性〔因?yàn)橹灰眠@個(gè)屬性對(duì)樣例測(cè)試，那么就可以得到分類的結(jié)果〕。也就是說(shuō)，根據(jù)某個(gè)屬性對(duì)樣例集進(jìn)行劃分后，得到的子樣例集越”純潔“，那么這個(gè)屬性對(duì)樣例集的區(qū)分能力越強(qiáng)。注意，這里不是很嚴(yán)謹(jǐn)，上面一段話中前后兩個(gè)“純潔”并不是相同的含義。第一個(gè)”純潔”是一個(gè)二值判斷，如果樣例集中的子樣例都屬于同一個(gè)分類，那么樣例集就是純潔的，反之那么是不純潔的。上面一段話中第二個(gè)“純潔”是一種程度的描述，把它稱為樣例集的純度〔也就是說(shuō)第一個(gè)“純潔”是第二個(gè)“純潔”的特例，或者說(shuō)極端情況〕。這里把比擬兩個(gè)屬性對(duì)樣例集的區(qū)分能力轉(zhuǎn)化為比擬使用兩個(gè)屬性對(duì)樣例集劃分后得到的子樣例的純度。如何刻畫(huà)樣例集的純度呢？這里引入信息論中廣泛使用的一個(gè)度量標(biāo)準(zhǔn)，稱為熵〔entropy〕。給定樣例集S，目標(biāo)屬性有c個(gè)不同的值，那么S相對(duì)于這c個(gè)分類的熵定義為：在熵的計(jì)算中，我們定義0log0為0。上式中,pi是S中屬于類別i的比例。舉一個(gè)例子：假設(shè)S是一個(gè)關(guān)于某布爾概念〔目標(biāo)屬性的取值有2個(gè)，“+”和“-”表示正樣本和負(fù)樣本〕的有14個(gè)樣例的集合，它包括9個(gè)正例和5個(gè)反例〔我們采用記號(hào)[9+，5-]來(lái)概括這樣的數(shù)據(jù)樣例〕。那么S相對(duì)于這個(gè)布爾分類的熵為：Entropy([9+,5])=–(9/14)log(9/14)–(5/14)log(5/14)=0.94注意，如果S的所有成員屬于同一類，那么S的熵為0。如果S中的正反樣例的數(shù)量相等時(shí)，熵為1。下面的圖刻畫(huà)了布爾分類的熵函數(shù)隨著p+(正樣例占總樣例的比例)從0到1變化的曲線從上面的圖可知道也就是說(shuō)樣例集越“純”的時(shí)候〔對(duì)應(yīng)途中橫軸兩邊的情況〕，熵越小。這個(gè)結(jié)論可以由只有兩個(gè)分類的情況推廣到有多個(gè)分類的情況。(信息論中的熵可以解釋為用二進(jìn)制位0和1對(duì)某個(gè)信息〔如字串〕進(jìn)行編碼所需的二進(jìn)制位的長(zhǎng)度，樣例集越純的時(shí)候，其中包含的信息越少，因此要編碼樣例集的目標(biāo)值的時(shí)候所需的二進(jìn)制位越少，熵就越小。對(duì)于熵的更詳細(xì)解釋會(huì)在后面講到貝葉斯學(xué)習(xí)時(shí)給出)有了這個(gè)結(jié)論之后，我們就可以衡量屬性對(duì)于樣例的區(qū)分能力了。用某個(gè)屬性劃分樣例集后，每個(gè)樣例子集越“純潔”，那么該屬性對(duì)于樣例的區(qū)分能力就越高，這樣每個(gè)子集的熵就越小，這些子集組成的整個(gè)樣例集的期望熵也就越小，也就是期望熵相對(duì)于原樣例集〔在未用該屬性劃分樣例前〕的熵降低地越多。這個(gè)熵降低的大小就稱為信息增益。因此，要求出信息增益，首先求出樣例集S在劃分前的熵Entropy(S)；然后，樣例集S被某個(gè)屬性A劃分為多個(gè)子集，求出每個(gè)子集S(a)的熵Entropy(S(a))，并求出樣例集S被屬性A劃分后熵的期望∑|S(a)|/|S|*Entropy(S(a))；最后用Entropy(S)-∑|S(a)|/|S|*Entropy(S(a))得到由于使用這個(gè)屬性劃分樣例導(dǎo)致的期望熵降低，這個(gè)就是一個(gè)屬性A相對(duì)于集合S的信息增益Gain(S,A)。下面給出精確定義：注意，等式右邊第二項(xiàng)描述的期望熵就是每個(gè)子集的熵的加權(quán)和，權(quán)值為屬于S(a)的樣例占原始樣例S的比例。再次強(qiáng)調(diào)，信息增益Gain(S,A)是由于知道屬性A而導(dǎo)致的期望熵的減少。換句話講，就是給定屬性A，得到的關(guān)于目標(biāo)函數(shù)〔如何分類樣例〕的信息量，或者說(shuō)是知道屬性A的值后對(duì)S的任意一個(gè)成員的目標(biāo)值進(jìn)行編碼時(shí)，可以節(jié)省的二進(jìn)制位數(shù)。--------------------------------------------------------------------------------決策樹(shù)學(xué)習(xí)中的假設(shè)空間搜索機(jī)器學(xué)習(xí)讀書(shū)筆記〔一〕中提到過(guò)，任何一個(gè)歸納學(xué)習(xí)算法可以被描述為從一個(gè)假設(shè)空間〔稱為知識(shí)的表示〕中搜索〔稱為搜索策略〕一個(gè)擬合訓(xùn)練樣例的假設(shè)。上面提到的ID3算法搜索的假設(shè)空間就是可能的決策樹(shù)的集合。ID3算法一種從簡(jiǎn)單到復(fù)雜的爬山算法遍歷這個(gè)假設(shè)空間，引導(dǎo)這種爬山搜索的評(píng)估函數(shù)是信息增益度量。通過(guò)觀察ID3算法的搜索空間和搜索策略，可以深入認(rèn)識(shí)這個(gè)算法的優(yōu)勢(shì)和缺乏。ID3算法中的假設(shè)空間包含所有的決策樹(shù)，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間。因?yàn)槊總€(gè)有限離散值函數(shù)可被表示為某個(gè)決策樹(shù)，所以ID3算法防止了搜索不完整假設(shè)空間的一個(gè)主要風(fēng)險(xiǎn)：假設(shè)空間不包含目標(biāo)函數(shù)。當(dāng)遍歷決策樹(shù)空間時(shí)，ID3僅維護(hù)單一的當(dāng)前假設(shè)。因?yàn)閮H考慮單一的假設(shè)，ID3算法失去了表示所有一致假設(shè)所帶來(lái)的優(yōu)勢(shì)〔這個(gè)與機(jī)器學(xué)習(xí)讀書(shū)筆記〔二〕中變型空間的候選消除算法不同，候選消除算法維護(hù)了與當(dāng)前的訓(xùn)練樣例一致的所有假設(shè)的集合〕它不能判斷有多少個(gè)其他決策樹(shù)也是與現(xiàn)有的訓(xùn)練數(shù)據(jù)一致的。根本的ID3算法在搜索中不進(jìn)行回溯。每當(dāng)在樹(shù)的某一層次選擇了一個(gè)屬性進(jìn)行測(cè)試，它不會(huì)再回溯重新考慮這個(gè)選擇。所以，它易受無(wú)回溯的爬山搜索中的常見(jiàn)風(fēng)險(xiǎn)影響：收斂到局部最優(yōu)的答案，而不是全局最優(yōu)的。后面會(huì)討論一個(gè)擴(kuò)展，增加一種形式的回溯〔后修剪決策樹(shù)〕ID3算法在搜索的每一步都使用當(dāng)前的所有訓(xùn)練樣例，以統(tǒng)計(jì)為根底決定怎樣精化當(dāng)前的假設(shè)。使用所有樣例的統(tǒng)計(jì)屬性〔例如信息增益〕大大降低了對(duì)個(gè)別訓(xùn)練樣例錯(cuò)誤的敏感性。因此，通過(guò)修改ID3算法的終止準(zhǔn)那么以接受不完全擬合訓(xùn)練數(shù)據(jù)的假設(shè)，他可以被很容易地?cái)U(kuò)展到處理含有噪聲的訓(xùn)練數(shù)據(jù)。--------------------------------------------------------------------------------決策樹(shù)學(xué)習(xí)的歸納偏置回憶機(jī)器學(xué)習(xí)讀書(shū)筆記〔二〕中提到的，歸納偏置是一系列前提，這些前提與訓(xùn)練數(shù)據(jù)一起演繹論證未來(lái)實(shí)例的分類。要描述ID3算法的歸納偏置，應(yīng)找到它從所有一致的假設(shè)中選擇一個(gè)的根據(jù)。ID3選擇在使用簡(jiǎn)單到復(fù)雜的爬山算法遍歷可能的樹(shù)空間時(shí)遇到的第一個(gè)可接受的樹(shù)。從上面的描述可知道，ID3的搜索策略為:(a)優(yōu)先選擇較短的樹(shù)而不是較長(zhǎng)的。〔由簡(jiǎn)單到復(fù)雜的自頂向下的貪心算法決定〕(b)選擇那些信息增益高的屬性里根節(jié)點(diǎn)較近的樹(shù)。〔由信息增益的屬性選擇度量決定〕上面的兩點(diǎn)決定了ID3算法的歸納偏置，注意，它們并沒(méi)有先后順序，而是存在一種微妙的相互作用的關(guān)系，也就是說(shuō)，雖然較短的樹(shù)優(yōu)先與較長(zhǎng)的樹(shù)，但I(xiàn)D3算法并不是總是選擇最短的樹(shù)，而又傾向于那些信息增益高的屬性更靠近根節(jié)點(diǎn)的樹(shù)，因此準(zhǔn)確刻畫(huà)ID3歸納偏置是很難的。下面給出一個(gè)近似的刻畫(huà)。ID3歸納偏置的近似：較短的樹(shù)比擬長(zhǎng)的樹(shù)優(yōu)先。那些信息增益高的屬性更靠近根節(jié)點(diǎn)的樹(shù)優(yōu)先。ID3算法的和第二章中討論的候選消除算法顯示出的歸納偏置之間有一個(gè)有趣的差異。1.ID3算法的假設(shè)空間是一個(gè)完整的假設(shè)空間，從ID3的歸納偏置可知，它不徹底搜索這個(gè)空間，而是從簡(jiǎn)單的假設(shè)到復(fù)雜的假設(shè)，直到遇到終止條件。因此ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果。2.變型空間的候選消除算法的搜索范圍是不完整的假設(shè)空間〔只搜索由屬性的合取表示的假設(shè)〕，但它徹底搜索這個(gè)空間，查找所有與訓(xùn)練樣例一致的假設(shè)。它的歸納偏置完全是假設(shè)表示的表達(dá)能力的結(jié)果?？偨Y(jié)一下，ID3算法的歸納偏置來(lái)自它的搜索策略，該策略假定某種假設(shè)勝過(guò)其他假設(shè)〔較短的假設(shè)比擬長(zhǎng)的更優(yōu)〕，因此稱這種歸納偏置為優(yōu)選偏置〔preferencebias〕或搜索偏置(searchbias)。相反，候選消除算法的偏置是對(duì)待考慮假設(shè)的一種限定。這種形式的偏置通常稱為限定偏置(restrictionbias)或語(yǔ)言偏置(language)。通常，優(yōu)先偏置比限定偏置更符合需要，因?yàn)樗ＷC了位置的目標(biāo)函數(shù)被包含在學(xué)習(xí)器工作的假設(shè)空間中〔要不然很可能白忙活一場(chǎng)〕。但在實(shí)際中，綜合使用兩者的學(xué)習(xí)系統(tǒng)是很常見(jiàn)的〔例如使用最小均方差〔優(yōu)選偏