機器學習課件參考chap4

1、第4章 機器學習朝樂門 中國人民大學 內(nèi)容簡介數(shù)據(jù)科學中的基礎(chǔ)知識圖4-1數(shù)據(jù)科學中的機器學習（1）目錄目錄圖4-1數(shù)據(jù)科學中的機器學習（1）學習目的了解機器學習在數(shù)據(jù)科學中的重要地位；機器學習領(lǐng)域的代表性人物及其著作；理解機器學習的定義、機器學習的4個基本活動和機器學習系統(tǒng)的4個組成部分；掌握機器學習的主要類型和典型算法；熟練掌握讀者自己所在專業(yè)領(lǐng)域中常用的機器學習方法、技術(shù)與工具。學習目的機器學習的主要議題是如何實現(xiàn)和優(yōu)化機器的自我學習。從語義層次看，機器學習是指計算機能模擬人的學習行為，通過學習獲取知識和技能，不斷改善性能，實現(xiàn)自我完善。例4-1 TD-Gammon系統(tǒng)西洋雙陸棋學習該系

2、統(tǒng)通過100多萬次以上與自己對弈的方法學習了下西洋雙陸棋的策略，并已達到人類世界冠軍的水平，成為博弈類機器學習領(lǐng)域的最典型的應(yīng)用案例之一。圖4-2 西洋雙陸棋例4-2 ALVINN系統(tǒng)機器人駕駛學習該系統(tǒng)使用學習到的策略在高速公路上以每小時70英里的速度自動行駛了90英里，成為動態(tài)控制類機器學習的成功案例之一。圖4-3自動駕駛圖4-4 機器學習的基本思路目錄目錄圖4-1數(shù)據(jù)科學中的機器學習（1）4.1.1定義如果一個計算機系統(tǒng)在完成某一類任務(wù)T的性能P能夠隨著經(jīng)驗E而改進，則稱該系統(tǒng)在從經(jīng)驗E中學習，并將此系統(tǒng)稱為一個學習系統(tǒng)。4.1基本概念圖4-5 機器學習的3個關(guān)鍵要素以上述TD-Gamm

3、on學習系統(tǒng)為例，其3個關(guān)鍵要素如下：任務(wù)T：下西洋跳棋性能指標P：比賽中擊敗對手的百分比經(jīng)驗來源E：與自己進行對弈以上述機器人駕駛學習為例，其3個關(guān)鍵要素如下：任務(wù)T：通過視覺傳感器在四車道高速公路上駕駛；性能指標P：平均無差錯行使里程；經(jīng)驗來源E：注視人類駕駛時錄制的一系列圖像和價值指令。需要注意的是，與其他人工智能技術(shù)不同，機器學習中的“智能”并不是“預(yù)定義”的，而是計算機系統(tǒng)自己從“經(jīng)驗”中通過自主學習后得到。4.1基本概念4.1基本概念表4-1 機器學習的相關(guān)學科4.1.2應(yīng)用（1）數(shù)據(jù)挖掘：從大量數(shù)據(jù)中發(fā)現(xiàn)可能包含的有價值的規(guī)律。例如，生物DNA信息挖掘；（2）自動化處理：在某些困

4、難的領(lǐng)域中，人們可能還不具有開發(fā)高效算法所需的知識。例如，人臉識別；（3）動態(tài)控制：計算機程序必須動態(tài)地適應(yīng)變化的領(lǐng)域。例如，生產(chǎn)過程控制；（4）推薦與過濾：垃圾郵件的過濾、個性化推薦、廣告投放等；（5）人機協(xié)同：汽車輔助自動駕駛與人工駕駛的結(jié)合等。4.1基本概念目錄目錄圖4-1數(shù)據(jù)科學中的機器學習（1）4.2機器學習活動4.2機器學習活動圖4-6機器學習的基本活動4.2.1訓練經(jīng)驗的選擇（1）訓練經(jīng)驗?zāi)芊駷橄到y(tǒng)的決策提供直接或間接的反饋（2）訓練經(jīng)驗?zāi)芊癖粚W習系統(tǒng)控制。（3）訓練集的分布是否與實際數(shù)據(jù)集具有相似的 分布。4.2機器學習活動（1）訓練經(jīng)驗?zāi)芊駷橄到y(tǒng)的決策提供直接或間接的反饋。直

5、接反饋：機器從直接經(jīng)驗（直接給出的訓練經(jīng)驗）中學習。以TD-Gammon系統(tǒng)（西洋雙陸棋學習）為例，我們可以找到一個由各種棋盤狀態(tài)和相應(yīng)的正確走子組成的數(shù)據(jù)集作為訓練經(jīng)驗，并讓機器從直接訓練經(jīng)驗中學習。間接反饋：機器從間接經(jīng)驗（間接給出的訓練經(jīng)驗）中學習。以TD-Gammon系統(tǒng)（西洋雙陸棋學習）為例，我們可能找到一個由過去對弈序列及其勝負結(jié)果組成的數(shù)據(jù)集作為訓練經(jīng)驗，并讓機器通過評估“每一次走子對最終結(jié)果的貢獻度”的方式間接地達到學習目的。4.2機器學習活動（2）訓練經(jīng)驗?zāi)芊癖粚W習系統(tǒng)控制。根據(jù)對訓練經(jīng)驗的控制程度（即對施教者的依賴程度），可以將學習中的控制活動分為：不控制：以TD-Gamm

6、on系統(tǒng)（西洋雙陸棋學習）為例，可以由施教者決定考慮何種棋盤態(tài)勢及其正確走步。部分控制：以TD-Gammon系統(tǒng)（西洋雙陸棋學習）為例，也可以由機器自己感到困難的棋盤態(tài)勢時，才向施教者詢問其正確走步；完全控制：以TD-Gammon系統(tǒng)（西洋雙陸棋學習）為例，還可以是計算機自己跟自己下跳棋，它對棋盤態(tài)勢及其訓練分類有著完全的控制，可以選擇兩種方式進行學習：一種是實驗還未考慮過的全新盤局；另一種是對它目前發(fā)現(xiàn)的最有效的路線的基礎(chǔ)上進行微小的改進。4.2機器學習活動（3）訓練集的分布是否與實際數(shù)據(jù)集具有相似的分布。一般情況下，訓練集的分布與實際數(shù)據(jù)集的分布越相似，學習的結(jié)果就越為可靠。以TD-Gam

7、mon系統(tǒng)（西洋雙陸棋學習）為例，假如計算機下跳棋學習系統(tǒng)的目的是參加世界錦標賽（即P為該系統(tǒng)將來在世界錦標賽上的勝率），那么用計算機自己跟自己下跳棋的方式進行學習是不夠的，其訓練集（所用的訓練例）不能代表實際數(shù)據(jù)集（在世界錦標賽上遇到的可能棋局）。4.2機器學習活動4.2.2目標函數(shù)的選擇我們可以把機器學習的任務(wù)歸結(jié)為發(fā)現(xiàn)目標函數(shù)(T)的可操作描述。在許多實際問題的結(jié)果過程中，學習目標函數(shù)(T)是一個十分困難的任務(wù)，無法找到準確的目標函數(shù)(T)因此，我們一般采用函數(shù)逼近（Function approximation）的方法，僅希望學習到一個近似的目標函數(shù)V。所以，學習目標函數(shù)的算法通常稱為函

8、數(shù)近似算法。4.2機器學習活動以TD-Gammon系統(tǒng)（西洋雙陸棋學習系統(tǒng)）為例，經(jīng)過目標函數(shù)的選擇活動之后的系統(tǒng)描述如下：4.2機器學習活動任務(wù)T:下西洋跳棋性能標準P: 擊敗對手的百分比訓練經(jīng)驗E: 和自己進行訓練對弈目標函數(shù)：V: BoardR4.2.3目標函數(shù)的表示由于理想的目標函數(shù)(T)很難找到。目標函數(shù)(T)的表示是指它的近似函數(shù)(V)的表示方法。以TD-Gammon系統(tǒng)（西洋雙陸棋學習）為例，我們可以采用線性組合、決策表、二次多項式函數(shù)、人工神經(jīng)網(wǎng)絡(luò)等多種方式。4.2機器學習活動采用棋盤特性的一個線性組合來表示V：V(b) = w0 + w1x1 + w2x2 + w3x3 +

9、w4x4 + w5x5 + w6x6 式中， x1為棋盤b上黑子的個數(shù) x2為棋盤b上紅子的個數(shù) x3為棋盤b上黑王的個數(shù) x4為棋盤b上紅王的個數(shù) x5為棋盤b上受紅方威脅的黑子的個數(shù) x6為棋盤b上受黑方威脅的紅子的個數(shù) w0 , w1 , w2 , w3 , w4 , w5 , w6為待定系數(shù)?？梢?，系數(shù)wi ( i = 1,2,6 )表達棋盤特性xi的相對重要性，確定系數(shù)wi的值是該算法的關(guān)鍵所在。4.2機器學習活動以TD-Gammon系統(tǒng)（西洋雙陸棋學習系統(tǒng)）為例，經(jīng)過目標函數(shù)的表示活動之后的系統(tǒng)描述如下：4.2機器學習活動4.2.4函數(shù)逼近算法的選擇目標函數(shù)的表示的關(guān)鍵在找出確定系

10、數(shù)wi的算法函數(shù)逼近算法。如果我們采用V(b)作為目標函數(shù)(T)的近似表達，棋盤態(tài)勢b就可以表達為元組。第1步，估計訓練值第2步，調(diào)整權(quán)值4.2機器學習活動第1步，估計訓練值從間接訓練經(jīng)驗提取形如 (b, Vtrain(b) 的直接訓練樣本。其中Vtrain(b)稱為訓練值，即V(b)的估計值。第2步，調(diào)整權(quán)值用一組(b, Vtrain(b)樣本調(diào)節(jié)系數(shù)wi的值。一種常用的方法是把最佳的假設(shè)定義為使訓練值和假設(shè)V預(yù)測的值之間的誤差平方和（E）最小。4.2機器學習活動4.2機器學習活動LMS系數(shù)調(diào)整規(guī)則對每一個訓練例(b, Vtrain(b)： 使用當前系數(shù)值計算V(b) 對每一個系數(shù)wi：以T

11、D-Gammon系統(tǒng)（西洋雙陸棋學習系統(tǒng)）為例，經(jīng)過函數(shù)逼近算法的選擇活動之后的系統(tǒng)描述如下：4.2機器學習活動任務(wù)T:下西洋跳棋性能標準P: 擊敗對手的百分比訓練經(jīng)驗E: 和自己進行訓練對弈目標函數(shù)：V: BoardR目標函數(shù)的表示: V(b) = w0 + w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + w6x6，函數(shù)逼近算法:（1）估計訓練值：Vtrain(b) V(Successor(b)（2）調(diào)整權(quán)值目錄目錄圖4-1數(shù)據(jù)科學中的機器學習（1）4.3機器學習系統(tǒng)4.3機器學習系統(tǒng)圖4-7學習系統(tǒng)的4個核心模塊4.3.1執(zhí)行器執(zhí)行器（又稱執(zhí)行系統(tǒng)）負責用學會的目標函

12、數(shù)來解決給定任務(wù)，如對弈西洋跳棋。執(zhí)行器把新問題（新一盤棋）的實例作為輸入，產(chǎn)生一組解答路線（對弈歷史記錄）作為輸出，即接受感知信息（輸入），決定系統(tǒng)所要采取的行動。4.3機器學習系統(tǒng)4.3.2評價器評價器（又稱批評模塊）的輸入為對弈的路線或歷史記錄，而其輸出為目標函數(shù)的一系列訓練樣本。根據(jù)系統(tǒng)外固定的性能標準，接受關(guān)于系統(tǒng)行為后果的感知信息，評價系統(tǒng)的性能，并將評價意見反饋給學習模塊。一般來說，我們可以采用：有指導的學習：目標函數(shù)（即要改進的行動成分的數(shù)學表達）的輸入和輸出（實際輸出和正確的輸出）都是可以感知；強化學習（獎懲式學習）：只有對實際輸出的評價，卻不給出正確的輸出值，計算機下跳棋問

13、題是一個典型的強化學習問題；無指導的學習：對正確的輸出值沒有任何提示。4.3機器學習系統(tǒng)4.3.3泛化器泛化器（又稱推廣模塊）以訓練樣本作為輸入，產(chǎn)生一個輸出假設(shè)，作為它對目標函數(shù)的估計。在計算機下跳棋系統(tǒng)中，學習模塊以評價模塊的輸出（形如 (bi, Vtrain(bi) 的直接訓練樣本）作為自己的輸入，用以改進目標函數(shù)V（即改進它的各個系數(shù)wi）以及在下一盤棋中系統(tǒng)能顯示更好的性能。4.3機器學習系統(tǒng)4.3.4實驗生成器實驗生成器（又稱問題生成模塊）以當前的假設(shè)（當前學到的函數(shù)）作為輸入，輸出一個新的問題供執(zhí)行系統(tǒng)去探索。在計算機下跳棋系統(tǒng)中，問題生成模塊可簡單地建議“用新的目標函數(shù)V從頭再

14、下一盤”，以遞推地改進；也可以根據(jù)學習模塊提供的其它改進意見生成特殊的殘局讓行動模塊學習，以探索新的經(jīng)驗，從而提高系統(tǒng)的整體性能。4.3機器學習系統(tǒng)目錄目錄圖4-1數(shù)據(jù)科學中的機器學習（1）4.4主要類型4.4主要類型圖4-8機器學習的類型4.4.1基于實例學習基于實例學習方法（Instance-based Learning）的基本思路是事先將訓練樣本存儲下來，然后每當遇到一個新增查詢實例時，學習系統(tǒng)分析此新增實例與以前存儲的實例之間的關(guān)系，并據(jù)此把一個目標函數(shù)值賦給新增實例。基于實例學習方法的特點是將從實例中泛化工作推遲到必需分類新的實例時，并為不同的待分類查詢實例建立不同的目標函數(shù)逼近。4

15、.4主要類型基于實例學習方法有時被稱為消極（Lazy）學習法。消極學習方法的優(yōu)點在于并不是在整個實例空間上一次性地估計目標函數(shù)，而是針對每個待分類新實例做出局部性且相異性的估計?；趯嵗龑W習方法包括最近鄰（Nearest Neighbor）法、局部加權(quán)回歸（Locally Weighted Regression）法和基于案例的推理（Case-based Reasoning）等?；趯嵗椒ǖ牟蛔阒幵谟诜诸愋聦嵗拈_銷可能很大幾乎所有的計算都發(fā)生在分類時，而不是在第一次遇到訓練樣本時完成4.4主要類型基于實例學習的常用方法有3種：k-近鄰：用來逼近實數(shù)值或離散值目標函數(shù)的基于實例算法，它假定實

16、例對應(yīng)于n維歐氏空間中的點。一個新查詢的目標函數(shù)值是由k個與其最近的訓練樣本的值估計。關(guān)于k-近鄰方法，請參加本書2.4部分。局部加權(quán)回歸法：k-近鄰方法的推廣，為每個查詢實例建立一個明確的目標函數(shù)的局部逼近。目標函數(shù)的局部逼近不僅可以基于像常數(shù)、線性函數(shù)或二次函數(shù)形式表示，而且也可以基于空間局部化的核函數(shù)形式表示?；诎咐耐评恚菏且环N基于實例學習方法，但這種方法使用復(fù)雜的邏輯描述而不是歐氏空間中的點來表示實例。4.4主要類型4.4.2概念學習概念學習（Concept Learning）的本質(zhì)是從有關(guān)某個布爾函數(shù)的輸入/輸出訓練樣本中推斷出該布爾函數(shù)。也就是說，概念學習主要解決的是在已知的樣

17、本集合以及每個樣本是否屬于某一概念的標注的前提下，推斷出該概念的一般定義的問題。例 概念學習。已知：訓練樣本（表4-2）；求：學習概念EnjoySport。4.4主要類型ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes表4-2目標概念EnjoySport的正例和反例4.4主要類型已知：（1）實例集

18、X：可能的日子，每個日子由下面的屬性描述：Sky：可取值為Sunny，Cloudy和Rainy；AirTemp：可取值為Warm和Cold；Humidity：可取值為Normal和High；Wind：可取值為Strong和Weak；Water：可取值為Warm和Cool；Forecast：可取值為Same和Change；圖4-9 EnjoySport 概念學習任務(wù)4.4主要類型（2）候選假設(shè)集H：每個假設(shè)描述為6個屬性Sky，AirTemp，Humidity，Wind，Water和Forecast的值約束的合取。約束可以為“?”（表示接受任意值），“”（表示拒絕所有值），或一特定值。（3）目標

19、概念c: EnjoySport: X0, 1（4）訓練樣本集D：目標函數(shù)的正例和反例（見表2-1）求解：假設(shè)集H中的一個假設(shè)h，使對于X中任意x，h(x)=c(x)。續(xù) 圖4-9 EnjoySport 概念學習任務(wù)在機器學習領(lǐng)域，概念學習的實現(xiàn)過程可看作為一種搜索過程搜索范圍是假設(shè)的表示所隱含定義的整個空間；搜索的目的是為了尋找能最好地擬合訓練樣本的假設(shè)?？梢?，搜索策略的選擇是概念學習的核心問題。為了便于假設(shè)空間的搜索，一般定義假設(shè)的一般到特殊偏序結(jié)構(gòu)，具體方法有：Find-S算法候選消除算法4.4主要類型Find-S算法：使用一般到特殊序，在偏序結(jié)構(gòu)的一個分支上執(zhí)行的一般到特殊搜索，以尋找與

20、樣本一致的特殊假設(shè)，如圖4-10所示。4.4主要類型圖4-10 Find-S算法候選消除算法利用一般到特殊序，通過極大特殊假設(shè)集合（S）和極大一般假設(shè)集合（G）計算變型空間（即所有與訓練數(shù)據(jù)一致的假設(shè)集）。候選消除算法解決了Find-S 中的不足之處Find-S 輸出的假設(shè)只是H中能夠擬合訓練樣本的多個假設(shè)中的一個，然而，候選消除算法輸出的是與訓練樣本一致的所有假設(shè)的集合4.4主要類型4.4.3決策樹學習4.4主要類型圖4-11一個簡單的鳥類識別決策樹根節(jié)點：代表分類的開始；葉節(jié)點：代表一個實例的結(jié)束；中間節(jié)點：代表相應(yīng)實例的某一個屬性；節(jié)點之間的邊：代表某一個屬性的屬性值；從根節(jié)點到葉節(jié)點的

21、每條路徑：代表一個具體的實例，同一個路徑上的所有屬性之間是“邏輯與”關(guān)系4.4主要類型4.4主要類型圖4-12決策樹學習實例決策樹學習的使用有著較為嚴格的前提條件和特定的應(yīng)用場景，主要包括：以“屬性-值”形式表示的實例。當被分類的實例是用一系列固定的屬性（如Temperature）和它們的值（如Hot）來描述時可以考慮使用決策樹學習方法。目標函數(shù)具有離散的輸出值。圖4-12的決策樹給每個實例賦予一個布爾型的分類。當然，決策樹方法也可以擴展到學習有兩個以上離散輸出值的函數(shù)。4.4主要類型訓練數(shù)據(jù)中允許包含錯誤。決策樹學習對錯誤有較高的魯棒性，無論是訓練樣本所屬的分類錯誤還是描述這些樣本的屬性值錯

22、誤。訓練數(shù)據(jù)中允許包含缺少屬性值的實例。決策樹學習甚至可以在有未知屬性值的訓練樣本中使用，例如，僅有一部分訓練樣本中含有當天的濕度信息。4.4主要類型4.4.4人工神經(jīng)網(wǎng)絡(luò)學習與生物學習系統(tǒng)類似，人工神經(jīng)網(wǎng)絡(luò)也是由一系列比較簡單的“人工神經(jīng)元”相互連接的方式形成網(wǎng)狀結(jié)構(gòu)。“人工神經(jīng)元”是人工神經(jīng)網(wǎng)絡(luò)的最基本的組成部分。在人工神經(jīng)網(wǎng)絡(luò)中，實現(xiàn)“人工神經(jīng)元”的方法有很多種，如感知器（Perceptron）、線性單元（Linear Unit）和Sigmoid單元（Sigmoid Unit）等。以“感知器”為例，所對應(yīng)的每個人工神經(jīng)元可以表示為圖4-13所示：4.4主要類型4.4主要類型圖4-13感知

23、器感知器是以一個實數(shù)值向量作為輸入，并計算這些輸入的線性組合，而輸出結(jié)果為1或-1。如果計算結(jié)果大于某個閾值就輸出1，否則輸出-1。因此，如果輸入為x1到xn，那么感知器的輸出（o）為：式中，wi是一個實數(shù)常量，通常稱之為權(quán)重（weight），用來決定輸入xi對感知器輸出的貢獻率。需要注意的是，常量(w0)是一個閾值，它是為了使感知器輸出1，輸入的加權(quán)和 必須超過的閾值?？梢?，學習一個感知器的任務(wù)就是確定權(quán)重wi的取值。4.4主要類型人工神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元之間的連接方式對于選擇具體學習算法具有重要影響。根據(jù)聯(lián)接方式不同，通常把神經(jīng)人工網(wǎng)絡(luò)分為：無反饋的前向網(wǎng)絡(luò)相互連接型網(wǎng)絡(luò)4.4主要類型無反饋

24、的前向網(wǎng)絡(luò)：分為輸出層、隱含層和輸出層。各個層所含神經(jīng)元數(shù)量可以不同。隱含層可以有若干層，每一層的神經(jīng)元只接收前一層神經(jīng)元的輸出。4.4主要類型圖4-14前向神經(jīng)網(wǎng)絡(luò)相互連接型網(wǎng)絡(luò)：其神經(jīng)元相互之間都可能有連接，因此，輸入信號要在神經(jīng)元之間反復(fù)往返傳遞，從某一初態(tài)開始，經(jīng)過若干次變化，漸漸趨于某一穩(wěn)定狀態(tài)或進入周期振蕩等其它狀態(tài)。4.4主要類型圖4-15反饋型神經(jīng)網(wǎng)絡(luò)在實際應(yīng)用中，人工神經(jīng)網(wǎng)絡(luò)的學習算法有兩種 ：一類是單個神經(jīng)單元的學習算法，另一類是由單元組成的多層網(wǎng)絡(luò)的學習算法。單元學習算法：主要采用梯度下降算法；多層網(wǎng)絡(luò)學習：主要采用反向傳播算法4.4主要類型從以上原理可以看出，人工神經(jīng)網(wǎng)

25、絡(luò)方法適合于解決具有以下特征的問題：實例是采用“屬性-值”對表示。目標函數(shù)的輸出可能是離散值、實數(shù)值或者由若干實數(shù)屬性或離散屬性組成的向量。訓練數(shù)據(jù)可能包含錯誤?？扇萑涕L時間的訓練。需要快速求出目標函數(shù)值。不需要人類理解目標函數(shù)。4.4.5貝葉斯學習貝葉斯學習是一種以貝葉斯法則為基礎(chǔ)的通過概率手段進行學習的方法。貝葉斯概率分析是相對于頻數(shù)概率(Frequency Probabi1ity )的一種分析方法，二者區(qū)別在于：貝葉斯概率引入先驗知識和邏輯推理來處理不確定命題；頻數(shù)概率只從數(shù)據(jù)本身獲得結(jié)論，并不考慮邏輯推理及先驗知識。4.4主要類型貝葉斯法則是貝葉斯學習方法的基礎(chǔ)。貝葉斯法則提供了從先驗

26、概率P(h)、P(D)和P(D|h)，計算后驗概率P(h|D)的方法。P(h)：通常被稱為h的先驗概率（Prior Probability ），它反映了我們所擁有的關(guān)于h是一正確假設(shè)的機會的背景知識。也就是說，P(h)代表的是尚未進行訓練操作之前，假設(shè)h成立的初始概率。一般情況下，如果無法確定先驗知識，那么可以簡單地將每一候選假設(shè)賦予相同的先驗概率。P(D)：代表將要觀察的訓練集（D）的先驗概率，即在沒有確定某一假設(shè)成立時，D的概率。4.4主要類型P(D|h)：代表假設(shè)h成立的情況下觀察到數(shù)據(jù)D的概率，有時還稱之為給定h時數(shù)據(jù)D的似然度（likelihood）。P(h|D)：需要注意的是，P(

27、D|h)與P(h|D)是兩個不同的概念。P(h|D)被稱為h的后驗概率（posterior probability），即給定訓練集（D）時h成立的概率，它反映了在看到訓練集（D）后h成立的置信度?？梢姡篁灨怕蔖(h|D)反映了訓練集（D）的影響；相反，先驗概率P(h)往往獨立于訓練集（D）。4.4主要類型4.4主要類型從本質(zhì)上看，貝葉斯準則告訴我們一種交換條件概率中的條件與結(jié)果的方法，如果用公式表達則：4.4主要類型極大后驗假設(shè)（Maximum a Posteriori, MAP）是貝葉斯學習的另一個重要概念。MAP假設(shè)是指具有最大可能性的假設(shè)，也就是說在候選假設(shè)集合H中，當給定數(shù)據(jù)D時可能

28、性最大的假設(shè)hH。確定MAP假設(shè)主要采用貝葉斯公式計算每個候選假設(shè)的后驗概率，即當下式成立時，稱hMAP為MAP假設(shè)：4.4主要類型當假定H中每個假設(shè)有相同的先驗概率（即對H中任意hi和hj，P(hi)=P(hj)）時，可把等式6-2進一步簡化，只需考慮P(D|h)來尋找極大可能假設(shè)。通常P(D|h)被稱為給定h時數(shù)據(jù)D的“似然度（Likelihood）”，而使P(D|h)最大的假設(shè)被稱為“極大似然（Maximum Likelihood，ML）假設(shè)hML。4.4主要類型樸素貝葉斯分類器（Naive Bayes Classifier）是最基本的也是最常用貝葉斯學習方法之一，其性能可達到人工神經(jīng)網(wǎng)

29、絡(luò)和決策樹學習的水平。樸素貝葉斯分類器基于一個簡單的假定：在給定目標值時屬性值之間相互條件獨立。該假定說明給定實例的目標值情況下，觀察到聯(lián)合的a1, a2an的概率等于對每個單獨屬性的概率乘積 樸素是指整個形式化過程只做最原始、最簡單的假設(shè)。因此，樸素貝葉斯分類器所使用的方法：其中vNB表示樸素貝葉斯分類器輸出的目標值。 樸素貝葉斯學習方法需要估計不同的P(vj)和P(ai|vj)項，對應(yīng)了待學習的假設(shè)。然后，使用vNB公式的規(guī)則來分類新實例?？梢?，只要所需的條件獨立性能夠被滿足，樸素貝葉斯分類vNB等于MAP分類。樸素貝葉斯學習方法和其他已介紹的學習方法之間的區(qū)別在于：沒有明確的搜索假設(shè)空間

30、的過程。假設(shè)的形成不需要搜索，只是簡單地計算訓練樣本中不同數(shù)據(jù)組合的出現(xiàn)頻率。4.4主要類型4.4.6遺傳算法遺傳算法（Genetic Algorithm，GA）主要研究的問題是“從候選假設(shè)空間中搜索出最佳假設(shè)”。此處，“最佳假設(shè)”是指是“適應(yīng)度（Fitness）”指標為最優(yōu)的假設(shè)。其中，“適應(yīng)度”是為當前問題預(yù)先定義的一個評價度量值。例如，如學習下國際象棋的策略時，可以將“適應(yīng)度”定義為該個體在當前總體中與其他個體對弈的獲勝率。4.4主要類型遺傳算法的實現(xiàn)方式可以有多種，但均具備一個共同結(jié)構(gòu)“遺傳算法的總體（Population）”?！斑z傳算法的總體”（以下簡稱“總體”）是指被遺傳算法不斷迭

31、代更新的一個假設(shè)池。在每一次迭代中，根據(jù)“適應(yīng)度”函數(shù)評估當前總體中的所有成員，并從當前總體中用概率方法選取適應(yīng)度最高的個體產(chǎn)生下一代總體。在這些被選中的個體中，一部分保持原樣地進入下一代總體，其余的被用來產(chǎn)生后代個體的基礎(chǔ)，產(chǎn)生后一代的常用方法有3種：選擇、交叉和變異。4.4主要類型圖4-16描述了一個遺傳算法原型，算法的主要參數(shù)如下：用來排序候選假設(shè)的適應(yīng)度函數(shù)；定義算法終止時適應(yīng)度的閾值；要維持的總體大??；決定如何產(chǎn)生后繼總體的參數(shù)；每一代總體中被淘汰的比例和變異率。4.4主要類型4.4主要類型GA(Fitness, Fitness_threshold, p, r, m)Fitness：

32、適應(yīng)度評分函數(shù)，為給定假設(shè)賦予一個評估得分。Fitness_threshold：指定終止判據(jù)的閾值。p：總體中包含的假設(shè)數(shù)量。r：每一步中通過交叉取代總體成員的比例。m：變異率。初始化總體：P隨機產(chǎn)生的p個假設(shè)評估：對于P中的每一個h，計算Fitness(h)圖4-16 遺傳算法原型4.4主要類型當 Fitness(h)Fitness_threshold，做：產(chǎn)生新的一代PS：1.選擇：用概率方法選擇P的(1-r)p個成員加入PS。從P中選擇假設(shè)hi的概率Pr(hi)通過下面公式計算：2.交叉：根據(jù)上面給出的Pr(hi)，從P中按概率選擇rp/2對假設(shè)。對于每一對假設(shè)應(yīng)用交叉算子產(chǎn)生兩個后代。

33、把所有的后代加入PS。續(xù) 圖4-16 遺傳算法原型3.變異：使用均勻的概率從PS中選擇m百分比的成員。對于選出的每個成員，在它的二進制表示中隨機選擇一個位取反。4.更新：PPS。5.評估：對于P中的每一個h計算Fitness(h)從P中返回適應(yīng)度最高的假設(shè)。續(xù) 圖4-16 遺傳算法原型在每一次迭代中，后繼總體PS的形成通過兩種途徑：根據(jù)假設(shè)的適應(yīng)度用概率方法“選擇”已有假設(shè)以及加入新假設(shè)。新假設(shè)的產(chǎn)生方法有兩種：交叉算子：對高適應(yīng)度最高的兩個雙親假設(shè)進行“交叉”操作；變異算子：對通過選擇和交叉產(chǎn)生的下一代總體中的部分假設(shè)進行單點“變異”，并重復(fù)這個迭代過程，直到發(fā)現(xiàn)適應(yīng)度足夠好的假設(shè)。4.4主

34、要類型遺傳算法的每一次迭代總是以“當前總體”為輸入，并以“下一代總體”為輸出，而其轉(zhuǎn)換過程包括3種基本算子：選擇交叉變異4.4主要類型4.4主要類型選擇。采用概率方法從“當前總體”中選擇一定數(shù)量的假設(shè)包含在下一代中。一個假設(shè)被選擇的概率與其自己的適應(yīng)度成正比，并且與當前總體中其他競爭假設(shè)的適應(yīng)度成反比。因此，選擇假設(shè)hi的被選擇概率 的計算公式如下：交叉。對“當前總體”進行選擇操作，得到“下一代總體”的部分成員之后，再使用“交叉算子”產(chǎn)生其他成員?！敖徊嫠阕印睆漠斍按腥蓚€雙親假設(shè)，并通過重新組合雙親的各部分產(chǎn)生兩個后代假設(shè)。雙親假設(shè)是從當前總體中按概率選出的，也使用公式（9.1）的概率函數(shù)

35、。在通過這種交叉操作產(chǎn)生新的成員后，下一代總體已經(jīng)包含了所需數(shù)量的成員。4.4主要類型變異。從這些成員中隨機選出一定比例（m），并進行隨機變異。在具體實現(xiàn)時，假設(shè)常被編碼為位串形式，并在位串上進行隨機變異。遺傳算法借鑒的生物進化的3個基本原則適者生存、兩性繁衍及突變，分別對應(yīng)遺傳算法的3個基本算子：選擇、交叉和突變。遺傳算法維護一個由競爭假設(shè)組成的多樣化總體，而其每一次迭代選出總體中適應(yīng)度最高的成員來產(chǎn)生后代，替代總體中適應(yīng)度最差的成員。4.4主要類型4.4.7分析學習分析學習的特點是使用先驗知識來分析或解釋每個訓練樣本，以推理出樣本的哪些特征與目標函數(shù)相關(guān)或不相關(guān)。4.4主要類型表4-3分析

36、學習和歸納學習的比較已知：實例空間X：每個實例描述了一對對象，描述謂詞為Type, Color, Volume, Owner, Material, Density和On。假設(shè)空間H：每個假設(shè)是一組Horn子句規(guī)則。每個Horn子句的頭部為一個包含目標謂詞SafeToStack的文字。Horn子句體為文字的合取，這些文字基于描述實例的謂詞，以及謂詞LessThan, Equal, GreaterThan和函數(shù)plus, minus和times。例如下面的Horn子句是假設(shè)空間中的一員：SafeToStack(x, y)Volume(x, vx)Volume(y, vy) LessThan(vx,

37、 vy)4.4主要類型圖4-17 SafeToStack(x, y)的分析學習問題目標概念：SafeToStack(x,y)訓練樣本：下面顯示了一個典型的正例SafeToStack(Obj1, Obj2)：On(Obj1, Obj2) Owner(Obj1, Fred)Type(Obj1, Box) Owner(Obj2, Louise)Type(Obj2, Endtable) Density(Obj1, 0.3)Color(Obj1, Red) Material(Obj1, Cardboard)Color(Obj2, Blue) Material(Obj2, Wood)Volume(Obj1

38、, 2)4.4主要類型續(xù) 圖4-17 SafeToStack(x, y)的分析學習問題領(lǐng)域理論B： SafeToStack(x, y)Fragile(y) SafeToStack(x, y) Lighter(x, y) Lighter(x, y) Weight(x, wx) Weight(y, wy) LessThan(wx, wy) Weight(x, w) Volume(x, v) Density(x, d)Equal(w, times(v, d) Weight(x, 5) Type(x, Endtable) Fragile(x) Material(x, Glass) 求解：H中一個假設(shè)，

39、與訓練樣本和領(lǐng)域理論一致。4.4主要類型續(xù) 圖4-17 SafeToStack(x, y)的分析學習問題Prolog-EBG算法是基于解釋學習的代表，它是一序列覆蓋算法，它的基本思路如下（圖4-16）：學習單個Horn子句規(guī)則，移去此規(guī)則覆蓋的正例，再在剩余正例上重復(fù)這一過程，直到?jīng)]有未覆蓋的正例為止。若給定一完整并正確的領(lǐng)域理論，Prolog-EBG保證輸出一個假設(shè)（規(guī)則集），它本身是正確的并能覆蓋觀察到的正例。對任意正例集合，由Prolog-EBG輸出的假設(shè)包含一組對應(yīng)于領(lǐng)域理論的目標概念的邏輯充分條件。4.4主要類型Prolog-EBG(TargetConcept, TrainingEx

40、amples, DomainTheory)LearnedRulesPosTrainingExamples中的正例對Pos中沒有被LearnedRules覆蓋的每個PositiveExample，做以下操作：1.解釋Explanation一個以DomainTheory表示的解釋（證明），說明為何PositiveExample滿足TargetConcept4.4主要類型圖4-18 Prolog-EBG算法2.分析SuffcientConditions按照Explanation，能夠充分滿足TargetConcept的PositiveExample的最一般特征集合3.改進LearnedRulesLe

41、arnedRules+NewHornClause，其中NewHornClause形式為：TargetConceptSufficientConditions返回LearnedRules4.4主要類型續(xù) 圖4-18 Prolog-EBG算法可見，Prolog-EBG算法中對每個還沒被學習到的Horn 子句集(LearnedRules)覆蓋的正例，建立一個新Horn 子句。該新的Horn 子句的創(chuàng)建是通過：（1）按領(lǐng)域理論解釋訓練樣本（2）分析此解釋以確定樣本的相關(guān)特征（3）建立一新的Horn 子句，它在該組特征滿足時得到目標概念。Prolog-EBG算法的要點如下：與歸納學習方法不同的是，Prol

42、og-EBG通過運用先驗知識分析單個樣本以產(chǎn)生合理的（justified）一般假設(shè)。4.4主要類型Prolog-EBG隱含假定了領(lǐng)域理論是正確且完整的，如果領(lǐng)域理論不正確或不完整，學到的概念也將不正確。學習到的Horn子句的泛性將依賴于領(lǐng)域理論的形式以及訓練樣本被考慮的序列。每個學習到的Horn子句對應(yīng)于滿足目標概念的一個充分條件。學習到的Horn子句集覆蓋了學習系統(tǒng)遇到的正例，以及其他與此共享同樣解釋的實例。4.4主要類型圖4-19學習任務(wù)的分布數(shù)據(jù)科學中往往需要在近似的先驗知識以及可用數(shù)據(jù)的基礎(chǔ)上形成一般假設(shè)，比較常用的方法有：使用先驗知識得到初始假設(shè)，如KBANN（Knowledge-B

43、ased Artificial Neural Network，基于知識的人工神經(jīng)網(wǎng)絡(luò)）算法；使用先驗知識改變搜索目標，如TangentProp算法；使用先驗知識來擴展搜索算子，如FOCL算法。4.4主要類型4.4.8增強學習增強學習主要研究的是如何協(xié)助自治Agent（或機器人）的學習活動，進而達到選擇最優(yōu)動作的目的。增強學習中討論的Agent需要具備與環(huán)境的交互能力和自治能力，4.4主要類型圖4-20 Agent狀態(tài)：通常，將一個Agent的生存環(huán)境被描述為某可能的狀態(tài)集合S。動作：Agent可執(zhí)行的可能動作集合A?；貓螅寒斣跔顟B(tài)st下執(zhí)行動作at時，Agent收到的一個實值回報rt，表示此狀

44、態(tài)-動作轉(zhuǎn)換的立即值。學習任務(wù)：Agent的任務(wù)是學習一個控制策略:SA，使回報總和的期望值最大，其中后面的回報值隨著他們的延遲指數(shù)減小。4.4主要類型控制策略的學習問題形式化表示方法有多種，其中最常用的是基于馬爾可夫決策過程定義方法。在馬爾可夫決策過程（Markov decision process，MDP）中Agent 可感知到其環(huán)境的不同狀態(tài)集合S，并且有它可執(zhí)行的動作集合A。在每個離散時間步t，Agent 感知到當前狀態(tài)st ，選擇當前動作at 并執(zhí)行它。環(huán)境將響應(yīng)此Agent，并給出回報 rt=r(st, at)，并產(chǎn)生一個后繼狀態(tài)St+1=(st, at)。函數(shù)和r是環(huán)境的一部分，

45、Agent 不必知道。在MDP中，函數(shù)(st, at)和r(st, at)只依賴于當前狀態(tài)和動作，而不依賴于以前的狀態(tài)和動作。Agent的任務(wù)是學習一個策略:SA，以基于當前觀察到的狀態(tài)st選擇下的一步動作at；即(st)=at。4.4主要類型在機器學習中，如何精確指定此Agent要學習的策略是一個核心問題。Q函數(shù)是最基本的方法之一。表4-21給出了一種Q學習算法，其中,Agent估計的 在極限時收斂到實際Q函數(shù)，只要系統(tǒng)可被建模為一個確定性馬爾可夫決策過程，回報函數(shù)r有界，并且動作的選擇可使每個狀態(tài)-動作對被無限頻率的訪問。在Q學習中，的計算方法如下：通常，用 函數(shù)來代替實際Q函數(shù)的估計，即

46、4.4主要類型Q學習算法對每個s,a，初始化表項 (s,a)為0觀察當前狀態(tài)s;重復(fù)以下操作：選擇一個動作a并執(zhí)行它接收到立即回報r觀察新狀態(tài)s對 (s,a)按照下式更新表項： ss折算因子為任意常量滿足01。4.4主要類型圖4-21在確定性回報和動作假定下的Q學習算法目錄目錄圖4-1數(shù)據(jù)科學中的機器學習（1）4.5.1K-Means算法K-means 算法是一個經(jīng)典的聚類算法，它接受輸入量 k，然后將n個數(shù)據(jù)對象劃分為 k個聚類，以便使得所獲得的聚類滿足兩個條件：同一聚類中的對象相似度較高；不同聚類中的對象相似度較小。其中，聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”來進行計算。

47、k-means 算法的基本步驟如圖4-22所示：4.5典型算法4.5典型算法圖4-22 k-means 算法的基本步驟4.5典型算法續(xù) 圖4-22 k-means 算法的基本步驟4.5典型算法續(xù) 圖4-22 k-means 算法的基本步驟第1步，在原始數(shù)據(jù)集中任意選擇 k 個對象作為“初始聚類中心對象”；第2步，計算其他對象與這些初始聚類中心對象之間的距離，并根據(jù)最小距離，將其他結(jié)點合并入對應(yīng)的最小聚類中心結(jié)點所在的聚類，形成k=2個“中間聚類結(jié)果”；第3步，計算每個“中間聚類結(jié)果”的均值，在k中間聚類中找出k=2個“新的聚類中心對象”；第4步，重新計算每個對象與這些“新的聚類中心對象”之間的

48、距離，并根據(jù)最小距離，重新分類，形成k=2個“中間聚類結(jié)果”；第5步，重復(fù)執(zhí)行步驟34。當所有對象的聚類情況不再變化或已達到規(guī)定的循環(huán)次數(shù)時，結(jié)束執(zhí)行，并得到最重聚類結(jié)果。4.5典型算法4.5.2k-近鄰算法k-近鄰算法主要解決的是在訓練樣本集中的每個樣本的分類標簽為已知的條件下，如何為一個新增數(shù)據(jù)找出其分類標簽。k-近鄰算法的計算過程如圖4-23所示。4.5典型算法4.5典型算法圖4-23 k-近鄰算法的基本步驟從圖4-23可以看出，k-近鄰算法的基本原理如下：在訓練集及其每個樣本的分類標簽信息為已知前提條件下，當輸入一個分類標簽為未知的新增數(shù)據(jù)時，將新增數(shù)據(jù)的特征與樣本集中的樣本特征進行對

49、比分析，并計算出特征最為相似的k個樣本（即k個近鄰）。最后，選擇k個最相似樣本數(shù)據(jù)中出現(xiàn)最多的分類標簽作為新增數(shù)據(jù)的分類標簽。可見，k-近鄰算法的關(guān)鍵在于“計算新增數(shù)據(jù)特征與已有樣本特征之間的相似度”。計算特征之間的相似度的方法有很多，最基本且最常用的方法就是歐氏距離法。 通常，k為不大于20的整數(shù)。4.5典型算法假如，我們把任意的實例x表示為下面的特征向量： 式中，ar(x)表示實例x的第r個屬性值。那么，兩個實例xi和xj間的距離定義為d(xi, xj)，其中： d(xi, xj) 4.5典型算法k-近鄰算法廣泛應(yīng)用于相似性推薦中。例如，我們可以采用k近鄰算法，通過對電影中出現(xiàn)的親吻或打斗

50、次數(shù)，自動劃分新上映電影的題材類型。假如，我們已知6部電影的類型（樣本集及每個樣本的分類標簽）及其中出現(xiàn)的親吻次數(shù)和打斗次數(shù)（特征信息），如表4-4所示。4.5典型算法電影名稱打斗鏡頭接吻鏡頭電影類型California Man 3104愛情片Hes Not Really into Dudes2100愛情片Beautiful Woman181愛情片Kevin Longblade10110動作片Robo Slayer 3000995動作片Amped II982動作片表4-4 已知6部電影的類型及其中出現(xiàn)的親吻次數(shù)和打斗次數(shù)那么，當遇到一部未看過的電影（不知道劇情，但知道其中的打斗次數(shù)和接吻次數(shù)分

51、別為18和90）時，如何知道它是愛情片還是動作片？我們可以k-近鄰算法找出該片的類型，具體方法如下：首先，計算未知電影與樣本集中的其他電影之間的歐式距離，計算結(jié)果如表4-5所示。例如，未知電影（18，90）與電影California Man（3，104）之間的距離的計算公式為： = = =20.54.5典型算法4.5典型算法表4-5 已知電影與未知電影的距離其次，按照距離遞增排序，并找到k個距離最近的電影。例如，k=4，則最靠近的電影依次是Hes Not Really into Dudes、 Beautiful Woman、California Man和Kevin Longblade。接著，按

52、照k-近鄰算法，確定未知電影的類型。因為這四部電影中出現(xiàn)最多的分類標簽為愛情片（3次），所以，我們可以推斷未知電影也是愛情片。最后，給出未知電影的類型愛情片。4.5典型算法4.5.3ID3算法ID3算法是決策樹學習的基本算法，其他多數(shù)決策樹學習方法都是ID3算法的變體。ID3算法的數(shù)學基礎(chǔ)是信息熵和條件熵，并以“信息熵下降速度最快”作為屬性選擇的標準，該算法的：輸入：已知類別的樣本集；輸出：決策樹。4.5典型算法ID3算法的具體學習過程如下：首先，以整個樣本集作為決策樹的根節(jié)點S，并計算S對每個屬性的條件熵；然后，選擇能使S的條件熵為最小的一個屬性，對根節(jié)點進行分裂，得到根節(jié)點下的子節(jié)點；接著

53、，再用同樣方法對這些子節(jié)點進行分裂，直至所有葉節(jié)點的熵值都下降為0為止；最后，得到一顆與訓練樣本集對應(yīng)的熵為0的決策樹。4.5典型算法需要注意的是，決策樹的生成和基于決策樹的數(shù)據(jù)分析是兩個不同概念，本節(jié)討論的是決策樹的生成過程，而不是其應(yīng)用環(huán)節(jié)：決策樹的生成：根據(jù)實例數(shù)據(jù)生成決策樹；決策樹的應(yīng)用：采用已生成的決策樹進行對新增數(shù)據(jù)的分類分析。4.5典型算法ID3(Examples，Target_attribute，Attributes)Examples即訓練樣本集。Target_attribute是這棵樹要預(yù)測的目標屬性。Attributes是除目標屬性外供學習到的決策樹測試的屬性列表。返回能正

54、確分類給定Examples的決策樹。創(chuàng)建樹的Root結(jié)點如果Examples都為正，那么返回label =+ 的單結(jié)點樹Root如果Examples都為反，那么返回label =- 的單結(jié)點樹Root如果Attributes為空，那么返回單結(jié)點樹Root，label=Examples中最普遍的Target_attribute值4.5典型算法圖4-24學習布爾函數(shù)的ID3算法否則AAttributes中分類Examples能力最好*的屬性Root的決策屬性A對于A的每個可能值vi在Root下加一個新的分支對應(yīng)測試A= vi令 為Examples中滿足A屬性值為vi的子集如果 為空在這個新分支下加

55、一個葉子結(jié)點，結(jié)點的label=Examples中最普遍的Target_attribute值否則在這個新分支下加一個子樹ID3（ , Target_attribute, Attributes-A）結(jié)束返回Root4.5典型算法續(xù) 圖4-24學習布爾函數(shù)的ID3算法決策樹學習的關(guān)鍵在于“如何從候選屬性集中選擇一個最有助于分類實例的屬性”，而其選擇是以信息熵（條件熵）為依據(jù)的 “信息熵下降速度最快的屬性就是最好的屬性”。信息熵：是對信源整體不確定性的度量，假設(shè)X為信源，xi為X發(fā)出的單個信息，P(xi）為X發(fā)出xi的概率，則X的信息熵H（X）為：4.5典型算法條件熵：是接收者在收到信息后對信源不確定性的度量，假設(shè)Y為接收者，X為信源， 為當Y為yi時，X為xi的條件概率，則條件熵 的定義為：4.5典型算法ID3算法中存在的主要問題如下：信息增益的計算依賴于特征數(shù)目較多的特征，而屬性取值最多的屬性并不一定最優(yōu)。ID3是非遞增算法。ID3是單變量決策樹(在分枝節(jié)點上只考慮單個屬性)，許多復(fù)雜概念的表達困難，屬性相互關(guān)系強調(diào)不夠，容易導致決策樹中子樹的重復(fù)或有些屬性在決策樹的某一路徑上被檢驗多次?？乖胄圆睿柧毨又姓头蠢谋壤^難控制。4.5典型算法由于ID3算法在實際應(yīng)用中存在一些問題，于是Quilan提出了C4.5算法，嚴格上說C4.5是ID3