1、1機器學習第1章 引言2自我介紹 張偉，東北大學信息學院教授。 電子郵箱： 3機器學習簡介 “機器學習”一般被定義為一個系統(tǒng)自我改進的過程。 從最初的基于神經(jīng)元模型以及函數(shù)逼近論的方法研究，到以符號演算為基礎(chǔ)的學習, 至最新的統(tǒng)計學習的興起，機器學習一直都在相關(guān)學科的實踐應(yīng)用中起著主導作用。 研究人員們借鑒了各個學科的思想來發(fā)展機器學習，但關(guān)于機器學習問題的實質(zhì)究竟是什么尚無定論尚無定論。不同的機器學習方法也各有優(yōu)缺點，只在其適用的領(lǐng)域內(nèi)才有良好的效果。 機器學習算法在很多應(yīng)用領(lǐng)域被證明有很大的實用價值：（a）數(shù)據(jù)挖掘問題；（b）在某些人們可能還不具有開發(fā)出高效的算法所需的知識（比如，從圖像庫

2、中識別出人臉）。 因此，以枚舉的方法描述機器學習中的各個理論和算法可能是最合適的途徑。 4機器學習簡介 機器學習一書正是以枚舉的方式來介紹機器學習的。其主要涵蓋了目前機器學習中各種最實用的理論和算法，包括概念學習、決策樹、神經(jīng)網(wǎng)絡(luò)、貝葉斯學習、遺傳算法、SVM學習等。 對每一個主題，作者不僅進行了十分詳盡和直觀的解釋，還給出了實用的算法流程。在卡內(nèi)基梅隆卡內(nèi)基梅隆 CMU等許多大學，本書都被作為機器學習課程的教材。 本書的作者Tom MMitchell在機器學習領(lǐng)域享有盛名。他是卡內(nèi)基梅隆大學的教授。他還是美國人工智能協(xié)會(AAAI)的主席，并且是機器學習雜志和國際機器學習年會(ICML)的創(chuàng)

3、始人。 本課程的目的：使學生掌握基本的機器學習算法，能夠應(yīng)用解決于文本分類等實際問題.激發(fā)興趣,期末考試。 5什么是機器學習什么是機器學習計算機程序如何隨著經(jīng)驗積累自動提高性能，即系統(tǒng)自我改進的過程1。歷史上成功應(yīng)用學習識別人類講話(Sphinx系統(tǒng))學習駕駛車輛(ALVINN系統(tǒng))學習分類新的天文結(jié)構(gòu)學習對弈西洋雙陸棋6相關(guān)學科人工智能人工智能學習概念的符號表示。作為搜索問題的機器學習。作為提高問題求解能力途徑的學習。使用先驗的知識和訓練數(shù)據(jù)一起引導學習。(八數(shù)碼)貝葉斯方法貝葉斯方法作為計算假設(shè)概率的基礎(chǔ)的貝葉斯法則。樸素貝葉斯分類器。估計未觀測到變量的值的算法。計算復雜性理論計算復雜性理

4、論不同學習任務(wù)中固有的復雜性的理論邊界，以計算量、訓練樣例數(shù)量、出錯數(shù)量等衡量。控制論控制論為了優(yōu)化預定目標，學習對各種處理過程進行控制，學習預測被控制的過程的下一個狀態(tài)。信息論信息論熵是信息內(nèi)容的度量。學習的最小描述長度方法。編碼假設(shè)時，它的最佳編碼和與最佳訓練序列的關(guān)系。哲學哲學“奧坎姆的剃刀”（Occams razor）1：最簡單的假設(shè)是最好的。從觀察到的數(shù)據(jù)泛化的理由分析。 7學習問題的標準描述 定義 如果一個計算機針對某類任務(wù)T的用P衡量的性能根據(jù)經(jīng)驗E來自我完善，那么我們稱這個計算機程序在從經(jīng)驗E中學習2 。 西跳棋學習問題的解釋 E，和自己下棋 T，參與比賽 P，比賽成績（或贏棋

5、能力，擊敗對手的百分比）8 手寫識別學習問題：手寫識別學習問題： 任務(wù)T：識別和分類圖像中的手寫文字 性能標準P：分類的正確率 訓練經(jīng)驗E：已知分類的手寫文字數(shù)據(jù)庫 機器人駕駛學習問題：機器人駕駛學習問題： （link） 任務(wù)T：通過視覺傳感器在四車道高速公路上駕駛 性能標準P：平均無差錯行駛里程（差錯由人類的監(jiān)督裁定） 訓練經(jīng)驗E：注視人類駕駛時錄制的一系列圖像和駕駛指令 9西洋跳棋 譯注：為了更好理解本例，下面簡要介紹一下這種跳棋。棋盤為88方格，深色棋格不可著子。1、可單步行走，2、亦可每步跨對方一子單跳或連跳，被跨越的子被殺出局。3、到達對方底線的子成為王，可回向行走（成為王前只可前行

6、），又可隔空格飛行。下圖為西洋跳棋棋盤示例（起始狀態(tài)）。10動態(tài)下棋11學習問題的標準描述（2） 定義很寬泛 這種行為與“學習”這個詞日常談?wù)摰暮x相接近。甚至包括了以非常直接的方式通過經(jīng)驗自我提高的計算機程序(如,數(shù)據(jù)庫查詢)。需要更加細化。 實際的機器學習問題往往比較復雜，需要設(shè)計一個學習系統(tǒng)才能解決此類問題.12設(shè)計一個學習系統(tǒng) 基本設(shè)計方法和學習途徑（以西洋跳棋為例） 選擇訓練經(jīng)驗 選擇目標函數(shù) 選擇目標函數(shù)的表示 選擇函數(shù)逼近算法 最終設(shè)計13設(shè)計一個學習系統(tǒng) 西洋跳棋學習問題 任務(wù)T，下西洋跳棋 性能標準P，擊敗對手的百分比 訓練經(jīng)驗E，和自己進行訓練對弈 細化的設(shè)計學習系統(tǒng)首先要

7、選擇經(jīng)驗E 明確三個關(guān)鍵屬性14選擇訓練經(jīng)驗 第一個關(guān)鍵屬性，訓練經(jīng)驗?zāi)芊駷橄到y(tǒng)的決策提供直接或間接的反饋（間接+信用分配） 第二個重要屬性，學習器在多大程度上控制樣例序列（完全自我控制，“自我博奕”） 第三個重要屬性，訓練樣例的分布能多好地表示實例分布，通過樣例來衡量最終系統(tǒng)的性能（無限逼近） 于是我們的學習任務(wù)變成：15設(shè)計一個學習系統(tǒng) 西洋跳棋學習問題3 任務(wù)T，下西洋跳棋 性能標準P，擊敗對手的百分比 訓練經(jīng)驗E，和自己進行訓練對弈 要學習的知識的確切類型 對于這個目標知識的表示 一種學習機制16選擇目標函數(shù) 目標函數(shù)ChooseMove ChooseMove: BM，接受合法棋局集合

8、中的棋盤狀態(tài)作為輸入，并從合法走子集合中選擇某個走子作為輸出 于是提高P變成學習ChooseMove: 我們把提高任務(wù)T的性能P的問題轉(zhuǎn)化（或簡化）為學習像ChooseMove這樣某個特定的目標函數(shù).17選擇目標函數(shù)（2） ChooseMove的評價 學習問題很直觀地轉(zhuǎn)化成這個函數(shù) 這個函數(shù)的學習很困難，因為提供給系統(tǒng)的是間接訓練經(jīng)驗 另一個目標函數(shù)V 一個評估函數(shù)，V: BR，它為任何給定棋局賦予一個數(shù)值評分，給好的棋局賦予較高的評分 優(yōu)點: 表示統(tǒng)一, 學習簡單 V的應(yīng)用 根據(jù)V能夠輕松地找到當前棋局的最佳走法。18選擇目標函數(shù)（3） V的設(shè)計，對于集合B中的任意棋局b，V(b)定義如下

9、如果b是一最終的勝局，那么V(b)=100 如果b是一最終的負局，那么V(b)= -100 如果b是一最終的和局，那么V(b)=0 如果b不是最終棋局，那么V(b)=V(b)，其中b是從b開始雙方都采取最優(yōu)對弈后可達到的終局19選擇目標函數(shù)（4） 上面設(shè)計的分析 遞歸定義 運算效率低 不可操作(b要決定它的值V（b）需要向前搜索到達終局的所有路線! ) 簡評 學習任務(wù)簡化成發(fā)現(xiàn)一個理想目標函數(shù)V的可操作描述。 通常要完美地學習這樣一個V的可操作的形式是非常困難的。 一般地，我們僅希望學習算法得到近似的目標函數(shù)V，因此學習目標函數(shù)的過程常稱為函數(shù)逼近。20選擇目標函數(shù)的表示 函數(shù)的表示 一張大表

10、，對于每個唯一的棋盤狀態(tài)，表中有唯一的表項來確定它的狀態(tài)值 規(guī)則集合 二項式函數(shù) 人工神經(jīng)網(wǎng)絡(luò)21選擇目標函數(shù)的表示（2） 重要的權(quán)衡過程 一方面，我們總希望選取一個非常有表現(xiàn)力的描述，以最大可能地逼近理想的目標函數(shù) 另一方面，越有表現(xiàn)力的描述需要越多的訓練數(shù)據(jù)，使程序能從它表示的多種假設(shè)中選擇22選擇目標函數(shù)的表示（3） 本案例中我們選擇一個簡單的表示法，對于任何給定的棋盤狀態(tài)，函數(shù)V可以通過以下棋盤參數(shù)的線性組合線性組合來計算。 x1，黑子的數(shù)量 x2，白子的數(shù)量 x3，黑王的數(shù)量 x4，白王的數(shù)量 x5，被白子威脅的黑子數(shù)量 x6，被黑子威脅的白子數(shù)量23選擇目標函數(shù)的表示（4） 目標函

11、數(shù) V(b)=w0+w1x1+w2x2+w6x6 其中，w0w6是權(quán)值，表示不同棋局特征的相對重要性 實際, b=(x1,x6), b給定,則x1,x6是常量 至此，問題轉(zhuǎn)化為學習目標函數(shù)中的系數(shù)（即權(quán)值w0w6 ）24選擇函數(shù)逼近算法 每個訓練樣例表示成二元對 b是棋盤狀態(tài)，Vtrain(b)是訓練值 比如，,100 訓練過程 從學習器可得到的間接訓練經(jīng)驗中導出上面的訓練樣例 調(diào)整系數(shù)wi，最佳擬合這些訓練樣例25選擇函數(shù)逼近算法（3） 有了Vtrain, 怎么求出V? 因為V(b)=w0+w1x1+w2x2+w3x3+w4x4+w5x5+w6x6 所以,剩下的事情就是選擇權(quán)權(quán)wi使V(b)

12、與訓練樣例的誤差達到最小（擬合）： 調(diào)整權(quán)值 最佳擬合的定義，常用的最佳是誤差平方和最小: 有算法可以得到線性函數(shù)的權(quán)使此定義的E最小化。2)(,)()(bVbVEtrainbVbtrain訓練樣例V是是V的近似擬合函的近似擬合函數(shù)數(shù)(因為因為Vtrain也是也是間接的近似的間接的近似的)26選擇函數(shù)逼近算法（3） 訓練樣例集合：， ， ， ， 調(diào)整權(quán)值 V(b)=w0+w1x1+w2x2+w3x3+w4x4+w5x5+w6x6 這時，在訓練樣例集合上，x1,x6都是常數(shù)，w0w6是可調(diào)整的變量。27選擇函數(shù)逼近算法（4） 最小均方方法（least mean squares），或叫LMS訓練法

13、則： 對于每一訓練樣例，它把權(quán)值向減小這個訓練數(shù)據(jù)誤差的方向略為調(diào)整。 LMS 權(quán)值更新法則權(quán)值更新法則對于每一個訓練樣例 do： 使用當前的權(quán)wi計算V(b) 對每一個權(quán)值wi進行如下更新 wi wi +(Vtrain(b)-V(b) xi (其推導依據(jù))幾何意義28V-train初值V1V2V3V4V15V51V-b01001008596 101.2 103.5102.799.01V-b21001008089.594.3 96.76100.3 100.6V-b41001007581 84.35 86.3693.4299.99假設(shè)有直接反饋的情況下，運行梯度下降法的運行假設(shè)有直接反饋的情況下

14、，運行梯度下降法的運行結(jié)果，約循環(huán)結(jié)果，約循環(huán)51次收斂。次收斂。29選擇函數(shù)逼近算法（5） 估計訓練值 困難處(給對弈結(jié)束時的棋盤狀態(tài)評分是容易的) 一個簡單的方法，Vtrain(b)=V(Successor(b) 這個簡單的方法是合理的看起來有點離奇，用V來估計訓練值Vtrain，而Vtrain又被用來更新V。但請注意，我們是在用后續(xù)棋局Successor(b)的V來估計棋局b的值。憑直覺，我們可以看到越接近游戲結(jié)束的棋局的越趨向精確。 30估計訓練值Vtrain(b)的例子 b4(終局): ，+100, 設(shè)此時V的系數(shù)為: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w

15、6=5. V(b4) = w0+w1*0+w2*0+w3*1+w4*0+w5*0+w6*0 = 75 b2(中間棋局): ，? , 此時V的系數(shù)為: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.此時?的訓練值Vtrain(b2) = V(successor(b2) = V(b4) = 75 V(b2) = w0+w1*0+w2*1+w3*1+w4*0+w5*0+w6*0 = 80 b0(中間棋局): ，? , 此時V的系數(shù)為: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.此時?的訓練值Vtrain(b0) = V(successor(b0

16、) = V(b2) = 80 V(b0) = w0+w1*1+w2*1+w3*1+w4*0+w5*0+w6*0 = 85b0 (我方一兵一后,對手一兵,我走一步兵)b1(吃我兵)b2 (我走后)b3 (他走兵)b4 (吃他一兵,勝)我方一后,對手一兵我方一后,對手無子31估計訓練值Vtrain(b)與V(b)誤差 b4(終局): ，+100, 設(shè)此時V的系數(shù)為: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.error(b4) = Vtrain(b4) - V(b4) = 100 wi*xi = 100-75=25 b2(中間棋局): ，75 , 設(shè)此時V的系數(shù)為:

17、w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.此時?的訓練值Vtrain(b2) = 75 error(b2) = Vtrain(b2) - V(b2) = 75 wi*xi = 75-80= -5 b0(中間棋局): ，80 , 設(shè)此時V的系數(shù)為: w0=5,w1=5,w2=5,w3=70,w4=5,w5=5,w6=5.此時?的訓練值Vtrain(b0) = V(successor(b0) = V(b2)= w0+w1*0+w2*1+w3*1+w4*0+w5*0+w6*0 = 80 error(b0) = Vtrain(b0) - V(b0) = 80 wi*xi

18、= 80-85= -5b0(我方一兵一后,對手一兵)b1b2b3b4我方一后,對手一兵我方一后,對手無子32選擇函數(shù)逼近算法（5） 一個調(diào)整權(quán)值的例子(棋局為b4): 假設(shè)當前wi=5（for i=0,1,2,4,5,6）,w3=70則依訓練樣本，+100，需調(diào)整wi如下： Error=100-(5+5*0+5*0+70*1+5*0+5*0+5*0) =25 W3=70+0.1*(25)*1=72.5 其他系數(shù)無變化, 即,w0=5, ,w1=5,w2=5,w3=72.5,w4=5,w5=5,w6=5. 于是新的Error=100-(5+5*0+5*0+72.5*1+5*0+5*0+5*0)=

19、22.5 多個樣本訓練后,這種簡單的權(quán)值調(diào)整方法被證明可以收斂到Vtrain 值的最小誤差平方點。計算程序見后頁。 33V-train初值V1V2V3V4V15V36V-b0808585.585.279.59299.1V-b2758080.581.1581.991.399V-b41007576.57885.592.599.4w0w1w2w3w4w5w65557055515次循環(huán)后51.14-0.638755510010010034V-train初值V1V2V3V4V15V36V-b080.58585.585.279.59299.1V-b276.58080.581.1581.991.399V-b

20、41007576.57885.592.599.4w0w1w2w3w4w5w65557055515次循環(huán)后51.14-0.6387555計算程序10010010035設(shè)計一個學習系統(tǒng) 基本設(shè)計方法和學習途徑（以西洋跳棋為例） 選擇訓練經(jīng)驗 選擇目標函數(shù) 選擇目標函數(shù)的表示 選擇函數(shù)逼近算法 最終設(shè)計36設(shè)計一個學習系統(tǒng) 西洋跳棋學習問題4 任務(wù)T，下西洋跳棋 性能標準P，擊敗對手的百分比 訓練經(jīng)驗E，和自己進行訓練對弈：間接反饋，信用分配規(guī)則為，Vtrain(b)=V(Successor(b) 知識類型：函數(shù)（目標函數(shù)：V：B） 目標函數(shù)的表示，線形函數(shù)：V(b)=w0+w1x1+w2x2+w3

21、x3+w4x4+w5x5+w6x6 一種學習機制: LMS算法。有了以上核心思想，怎么變成一個軟件系統(tǒng)？有了以上核心思想，怎么變成一個軟件系統(tǒng)？37最終設(shè)計實驗生成器執(zhí)行系統(tǒng)泛化器鑒定器新問題解答路線假設(shè)訓練樣例38最終設(shè)計（2） 執(zhí)行系統(tǒng) 用學會的目標函數(shù)來解決給定的任務(wù) 鑒定器 以對弈的路線或歷史記錄作為輸入，輸出目標函數(shù)的一系列訓練樣例。 泛化器 以訓練樣例為輸入，產(chǎn)生一個輸出假設(shè)，作為它對目標函數(shù)的估計。 實驗生成器 以當前的假設(shè)作為輸入，輸出一個新的問題，供執(zhí)行系統(tǒng)去探索。39Design ChoicesDesign Choices29Determine type of traini

22、ng experienceDetermine target functionDetermine representation of learned functionDetermine learning algorithmCompleted designGradient descentLinear programmingpolynomialLinear function of six featuresBoard moveBoard valueGames against expertsGames against selfTable of correct moves40西洋跳棋學習的更多討論 理論上

23、的保證(如果目標函數(shù)真在假設(shè)空間中，這種學習技術(shù)是否確保發(fā)現(xiàn)一個非常接近的近似). 更復雜的目標函數(shù)（e.g. ANN） 其他學習算法 最近鄰算法，存儲訓練樣例，尋找保存的最接近的情形來匹配新的情況 遺傳算法，產(chǎn)生大量候選的西洋跳棋程序，讓它們相互比賽，保留最成功的程序并進一步用模擬進化的方式來培育或變異它們 基于解釋的學習，分析每次成敗的原因41對于有兩個權(quán)值的線性單元，假設(shè)空間H就是w0,w1平面。縱軸表示與固定的訓練樣例集合相應(yīng)的權(quán)向量假設(shè)的誤差。箭頭顯示了該點梯度的相反方向，指出了在w0，w1平面中沿誤差曲面最陡峭下降的方向。 BACK42機器學習的一些觀點 一個有效的觀點 機器學習問

24、題歸結(jié)于搜索問題 本書給出了對一些基本表示（例如，線性函數(shù)、邏輯描述、決策樹、人工神經(jīng)元網(wǎng)絡(luò)）定義的假設(shè)空間的搜索算法。這些不同的假設(shè)表示法適合于學習不同的目標函數(shù)。 通過搜索策略和搜索空間的內(nèi)在結(jié)構(gòu)來刻畫學習方法43機器學習的問題存在什么樣的算法能從特定的訓練數(shù)據(jù)學習一般的目標函數(shù)呢？如果提供了充足的訓練數(shù)據(jù)，什么樣的條件下，會使特定的算法收斂到期望的函數(shù)？哪個算法對哪些問題和表示的性能最好？多少訓練數(shù)據(jù)是充足的？怎樣找到學習到假設(shè)的置信度與訓練數(shù)據(jù)的數(shù)量及提供給學習器的假設(shè)空間特性之間的一般關(guān)系？學習器擁有的先驗知識是怎樣引導從樣例進行泛化的過程的？當先驗知識僅僅是近似正確時，它們會有幫助嗎？怎樣把學習任務(wù)簡化為一個或多個函數(shù)逼近問題？換一種方式，系統(tǒng)該試圖學習哪些函數(shù)？這個過程本身能自動化嗎？學習器怎樣自動地改變表示法來提高表示和學習目標函數(shù)的能力？44全書內(nèi)容簡介第2章，基于符號和邏輯表示的概念學習第3章，決策樹第4章，人工神經(jīng)網(wǎng)絡(luò)第5章，統(tǒng)計和估計理論的基礎(chǔ)概念第6章，貝葉斯理論第7章，計算學習第8章，基于實例的學習第9章，遺傳算法第10章，規(guī)則學習（we will learn VSM）第11章，基于解釋的學習第12章，近似知識與現(xiàn)有數(shù)據(jù)的結(jié)合第13章，增強學習45小結(jié) 機器學習算法在很多應(yīng)用領(lǐng)域被證明有很大的實用價值