機器學習講義

1一月二月三月產(chǎn)品名稱數(shù)量金額利潤產(chǎn)品名稱數(shù)量金額利潤產(chǎn)品名稱數(shù)量金額利潤合計合計合計四月五月六月產(chǎn)品名稱數(shù)量金額利潤產(chǎn)品名稱數(shù)量金額利潤產(chǎn)品名稱數(shù)量金額利潤機器學習講義(2010年春碩士課程試用)第一章緒論序機器學習通常被認為是人工智能領域的一個分支，但和人工智能一樣，實際上是多學科的融合。為了說明什么是機器學習，我們來看一下“自動”(automation)和“自主”(autonomy)這兩個概念的區(qū)別。在通常的“自動化”系統(tǒng)中，所有的“智能”都是系統(tǒng)設計者預先注入的。當系統(tǒng)放入它的運行環(huán)境中去之后，將按照預定的程序進行活動。但是如果設計者對環(huán)境的了解是不全面的，系統(tǒng)就有可能陷入無所適從的境地(系統(tǒng)中的知識是由人工編程輸入的，知識中的錯誤也不能自動改正。)。這時“學習”的能力就成為唯一可依靠的解決方法，也是實現(xiàn)機器超過人這個終極智能的唯一手段。具有學習能力的系統(tǒng)稱為是“自主的”。學習意味著根據(jù)經(jīng)驗改進自身。學習的真諦在于：感知不僅用于當前的行動，而且用于改進以后的行動。學習是系統(tǒng)和環(huán)境交互的結果，也來自于系統(tǒng)對自己決策過程的觀察。學習的范圍極廣，從僅僅記住經(jīng)驗，到創(chuàng)造整個的科學理論，所有這些活動都是學習的過程。簡而言之，機器學習意味著通過編程使計算機進行學習。比如，讓計算機從醫(yī)療記錄中學到治療新疾病的最佳方案；使智能房屋根據(jù)經(jīng)驗學到基于主人生活習慣的能源消耗優(yōu)化方案；開發(fā)個人軟件助手為用戶從在線晨報中摘出該用戶特別感興趣的內(nèi)容；等等。機器學習研究的進展對社會經(jīng)濟的影響將是巨大的，它能使計算機的應用領域大為擴展，并使個人和組織的竟爭力提高到新的水平，甚至形成人類全新的生活方式。另外，對機器學習的信息處理算法的研究將導致對人腦學習能力（及其缺陷）的更好的理解。就機器學習研究的現(xiàn)狀而言，我們必須承認，目前還不能使計算機具有類似人那樣的學習能力。但是，對某些類型的學習任務已經(jīng)發(fā)明了有效的算法，對學習的理論研究也已經(jīng)開始，人們已經(jīng)開發(fā)出許多計算機程序，它們顯示了有效的學習能力，有商業(yè)價值的應用系統(tǒng)也已經(jīng)開始出現(xiàn)。在理論方面，關于觀察例的數(shù)目，所考慮的假設的數(shù)目和學習到的假設的預計誤差之間的基本關系的刻畫已經(jīng)取得成果。我們已經(jīng)獲得人類和動物學習的初步模型，開始了解它們與計算機學習算法之間的關系。在應用方面，近十年來的進展尤為迅速。下面是一些突出的應用實例：語音識別：所有最成功的語音識別系統(tǒng)都以某種形式使用了機器學習技術。例如，SPHINX系統(tǒng)學習針對具體講話人的策略從接受到的語音信號中識別單音和單詞。神經(jīng)網(wǎng)絡學習方法和學習隱藏的Markov模型的方法可有效地應用于對個別講話人，詞匯表，麥克風的特性，背景噪音等的自動適應。類似的技術也可用于許多其他的信號解釋問題。自動車駕駛：機器學習方法已用于訓練計算機控制的車輛在各種類型的道路上的正確行駛。例如，ALVINN系統(tǒng)使用學習到的策略在高速公路上與別的車輛一起以每小時70英里的速度自動行駛了90英里。類似的技術也可用于許多其他的基于傳感器的控制問題。新天體的分類：機器學習方法已用于各種各樣的大型數(shù)據(jù)庫以發(fā)現(xiàn)隱藏在數(shù)據(jù)中的一般規(guī)律。例如，NASA用決策樹學習算法對天體進行分類。該系統(tǒng)現(xiàn)在被用來對所有的對象進行分類，所用的數(shù)據(jù)庫含有三兆字節(jié)的圖象數(shù)據(jù)。計算機弈棋：大多數(shù)成功的計算機弈棋程序均基于機器學習算法。例如,TD-GAMMON通過與自己對弈100多萬次來學習下backgammon棋的策略。該系統(tǒng)目前已達到人類世界冠軍的水平。類似的技術也可用于許多其他的涉及具有非常大搜索空間的實際問題?？傊?，隨著我們對計算機研究的進一步加深，機器學習將不可避免地在計算機科學技術中起到越來越重要的作用。機器學習本質上是一個多學科的領域。下面我們列出主要的相關學科及其影響機器學習領域的主要思想。人工智能：概念的符號表達的學習，作為搜索問題的機器學習，學習作為改善問題求解的方法，將先驗知識和訓練數(shù)據(jù)結合起來指導學習。貝葉斯方法：貝葉斯定理是做猜想的概率計算的基礎，簡單貝葉斯分類器，計算未觀察到的變量值的算法。計算復雜性理論：各種學習任務的內(nèi)在復雜性的理論邊界，而復雜性是以學習所需的計算量，訓練例數(shù)，錯誤數(shù)等來度量的?？刂普摚簩W習控制進程以優(yōu)化預定義對象，學習預測所控制的進程的下一狀態(tài)。信息論：熵和信息內(nèi)容的度量，哲學。心理學與神經(jīng)生物學。統(tǒng)計學。1.1學習問題的一般表達定義如果一個計算機系統(tǒng)在完成某一類任務T時的性能P能夠隨著經(jīng)驗E而改進，則稱該系統(tǒng)為一個學習系統(tǒng)。顯然，要討論一個學習系統(tǒng)，首先必須確定它的三個關鍵成分：任務T,性能指標P和經(jīng)驗來源E。例子：1下跳棋：T：下跳棋P：勝率E：自弈2手跡辨認：T：手寫字圖象的識別與分類P：正確分類率E：手寫字及其已知分類的數(shù)據(jù)庫3行車機器人：T：使用視覺傳感器在四道高速公路上行駛P：平均無錯誤行駛的里程E：人類駕駛員行車的路況和操作的系列記錄學習系統(tǒng)的設計學習系統(tǒng)的設計要作四個關鍵的設計選擇（訓練經(jīng)驗的選擇，目標函數(shù)的選擇，目標函數(shù)表示的選擇，函數(shù)近似算法即學習算法的選擇），從而確定系統(tǒng)的四個核心模塊（行動模塊，評價模塊，學習模塊，知識生成模塊）所使用的策略和算法。2.1訓練經(jīng)驗的選擇訓練經(jīng)驗的類型對學習系統(tǒng)的成敗具有重要的影響。訓練經(jīng)驗的關鍵特征有:訓練經(jīng)驗對行為模塊的選擇提供直接的還是間接的反饋。比如在計算機下跳棋系統(tǒng)中，如果例子集由各種棋盤態(tài)勢及其正確走步組成,這種訓練經(jīng)驗就是直接的（因為例子集直接地告訴行為模塊遇到什么情況走什么步）；如果例子集由各盤比賽的走步序列及其勝負結果組成，這種訓練經(jīng)驗就是間接的（因為例子集不能直接地告訴行為模塊遇到什么情況走什么步，而只是提供一些間接的下跳棋經(jīng)驗）。從直接經(jīng)驗的學習顯然要比從間接經(jīng)驗的學習容易,因為在間接經(jīng)驗的情況下，走步序列中的每一走步的“得分”（即它對比賽最終勝負的影響）需要另作推敲，而且得分的估計有時是十分困難的。學習系統(tǒng)對訓練例子序列能夠控制到何種程度。比如在計算機下跳棋系統(tǒng)中，可能是由教師決定考慮何種棋盤態(tài)勢及其正確走步；也可能是由系統(tǒng)提出自己感到困難的棋盤態(tài)勢并向教師詢問其正確走步；還可能是計算機自己跟自己下跳棋，它對棋盤態(tài)勢及其訓練分類有著完全的控制（它可以試驗嶄新的棋盤態(tài)勢以學習新的技術，也可以對它迄今所知的最好棋局略作改變以改進自己的技術）。在本書中我們將考慮各種各樣的學習系統(tǒng)。訓練經(jīng)驗與最終用來測試系統(tǒng)性能P的那些例子之間的關系。訓練例與測試例的分布越相似，學習的結果就越可靠。假如計算機下跳棋學習系統(tǒng)的目的是參加世界錦標賽（即P為該系統(tǒng)將來在世界錦標賽上的勝率），那么用計算機自己跟自己下跳棋的方式進行學習就可能是不夠的，因為這時所用的訓練例難以代表在世界錦標賽上所遇到的可能棋局。在目前的有關機器學習的書中，人們通常假定訓練例與測試例的分布是一致的，這樣才能獲得一定的理論成果。但是，我們要記住，現(xiàn)實中這兩者的分布是有差別的。在下面關于學習系統(tǒng)設計的討論中，我們以計算機通過自己跟自己下跳棋的方式進行學習的系統(tǒng)作為實例。注意，這意味著沒有外部訓練者，而系統(tǒng)能夠生成足夠多的訓練數(shù)據(jù)。2.2目標函數(shù)的選擇學習系統(tǒng)的目的是改進在完成某一類任務T時的性能P。我們通常把這一目的轉換成對某目標函數(shù)的學習。于是，目標函數(shù)的選擇就成了學習系統(tǒng)設計的一個關鍵問題。例如，在計算機下跳棋問題里，目標函數(shù)可為：ChooseMove:BM其中,B為合法棋盤態(tài)勢集,M為合法走步集。給定任一棋盤態(tài)勢m，ChooseMove(m)給出m下的最佳走步。對于計算機下跳棋問題，顯然ChooseMove是一個合適的目標函數(shù)。但是，如果訓練例是間接的(即給出各盤比賽的走步序列及其勝負結果)，ChooseMove的學習將是十分困難的。另一個可能的目標函數(shù)可為：V::BR其中，B為合法棋盤態(tài)勢集，R為實數(shù)集。給定任一棋盤態(tài)勢m，V(m)給出m的估價值(估價值V(m)越高，棋盤態(tài)勢m越有利)。根據(jù)這個估價函數(shù)V,不難求出最佳走步。最簡單的方法是：對當前棋盤態(tài)勢m，可生成所有可能的后繼態(tài)勢m1,m2,mn，選擇具有最大的V(mJ值的后繼態(tài)勢m，達到m.的走步就是最佳走步。若采取向前看幾步的策略，可使用人工智能中熟知的-過程。于是，機器學習的任務就歸結為發(fā)現(xiàn)目標函數(shù)V的可操作的描述。在許多實際問題里，這是一個十分困難的任務，所以僅要求描述V的一個近似V。因此，學習目標函數(shù)的算法通常稱為函數(shù)近似算法。2.3目標函數(shù)的表示的選擇這里所說的目標函數(shù)V的表示即它的近似V的表示方法。越是表達力強的方法越能夠接近理想的目標函數(shù)V,但也就需要越多的訓練數(shù)據(jù)來確定它的值。在計算機下跳棋問題里，我們可用下面的棋盤特性的一個線性組合來表示V：V(b=W0+WiXi+W2X2+W3X3+W4X4+W5X5+W6X6這顯然是目標函數(shù)V的一個可操作的近似描述。其中，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ù)w.(i=1,2,...,6)表達棋盤特性x.的相對重要性，w0則是為整個棋盤附加的一個常數(shù)。系統(tǒng)的學習任務(由函數(shù)近似算法完成)就是通過訓練例來設置這些系數(shù)。一旦這些系數(shù)被確定，對任何棋盤態(tài)勢b，計算機下跳棋系統(tǒng)很容易計算V(b)的值，從而選擇最佳走步。當然，真的讓該系統(tǒng)參加世界錦標賽，其表現(xiàn)不見得就一定令人滿意。影響系統(tǒng)性能的因素有：V(b丿表示的精密度，函數(shù)近似算法(它負責從訓練例學習系數(shù)w.的值)的質量，以及訓練例的數(shù)量和質量。實際上，系數(shù)w,的值并非是一次性確定的。開始時，不妨按某種策略設定它們的初值，然后在學習過程中不斷對它們進行調整和改進。2.4函數(shù)近似算法的選擇如果我們采用V(b丿作為目標函數(shù)的近似表達，棋盤態(tài)勢b就可以表達為元組<?,x2,x3,x4,x5,x6>。假設計算機下跳棋系統(tǒng)所用的間接訓練經(jīng)驗為各盤比賽的走步序列及其勝負結果。我們現(xiàn)在的任務是要通過訓練例來設置V函數(shù)中的那些系數(shù)w,。這可以通過兩個步驟完成：從間接訓練經(jīng)驗提取形如(b,Vtran(b))的直接訓練例子。其中Vtrain(b)稱為訓練值，是V(b丿的估計值。用一組(b,Vtran(b))例子調節(jié)系數(shù)w,的值。下面我們分別對這兩個步驟進行說明。估計訓練值Vtan(b)的方法既然v的系數(shù)待定(或待改進)，ve丿值的估計必定是一個含糊的任務。我們可以這樣想，當前的系數(shù)值(不管它們是否仍待改進)用于接近尾盤時的精度總比用于較早期棋局時的精度高。考慮當前棋局b和經(jīng)過計算機和對手的兩次走步(各走一次)后的棋局succ(b)(間接訓練例可給出succ(b))。使用當前系數(shù)值可求出V(succ(b))。如果把它作為V(b)值的估計，即：Vtrain(b)-V(succ(b))，我們可以期待它比用當前系數(shù)值算出的V(b)更精確。(當然，對于終局b,若為勝局，可設Vtran(b)+；若為負局，可設Vtrain(b)-；若為和局，可設嶺問爐丿0)。實踐證明這個簡單的方法頗為有效。理論上可以證明，在一定條件下，這種用后繼狀態(tài)的估計值遞推改進前面狀態(tài)的估計值的方法可收斂于精確的估計值。調節(jié)系數(shù)的方法我們已有了一組直接訓練例(b,vtrain(b))，b取一盤比賽歷史中各個輪到機器走步時的狀態(tài)?，F(xiàn)在的任務是確定(或改進)函數(shù)近似V(即它的系數(shù)叫)，使之與訓練例達到最好的匹配。嚴格地說，就是求氣?，使方差E=2(V(b)-V(b))2train(bStrain))訓練例集達到最小。在一定條件下，最小方差E對應于(對觀察到的訓練數(shù)據(jù)來說)最可能的關于叫的假設。求使E達到最小值的線性函數(shù)的系數(shù)的算法有多種。我們需要的算法應能隨著訓練例的逐個出現(xiàn)步進地改進系數(shù)，并對估計的訓練值中的錯誤具有抵抗性。最小均方系數(shù)調整規(guī)則(LMS系數(shù)調整規(guī)則)就是這樣的一個算法：LMS系數(shù)調整規(guī)則對每一個訓練例(b,Vtran(b))：使用當前系數(shù)值計算V(b)對每一個系數(shù)叫：①j①+耳(V(b)-V(b))xiitraini這里為一個小常數(shù)(如)，使系數(shù)的每次改變不至于太大。該算法的合理性在直觀上可作如下理解：.若(Vtan(b)-V(b))為正數(shù)，說明當前V(b)值偏低，而按算法Wj將增大，從而使V(b丿值增加。.若(Vtan(b)-V(b))為負數(shù)，說明當前V(b)值偏高，而按算法Wj將減少，從而使V(b丿值減少。.若(Vtran(b)-V(b))為0,說明當前V(b)值合適，而按算法w.將不變，從而使V(b丿值不變。.各系數(shù)w.變化的大小與其相應特性在棋盤中出現(xiàn)的次數(shù)(即Xj的值)成正比。特別地，若某棋盤特性不出現(xiàn)在b中(即x.=0)，它的系數(shù)w.不變。理論上，這屬于隨機梯度下降搜索方法，在系數(shù)空間里搜索使E達到最小值的系數(shù)?？勺C明，在一定的條件下，這個簡單的微調算法確實收斂于vtaain(b)的最小方差估計。2.5學習系統(tǒng)的最終設計學習系統(tǒng)含有四個核心模塊，上面講解的四個設計選擇決定了各個模塊內(nèi)部的策略和算法。也就是說，針對某個具體問題，作出四個具體的設計選擇，產(chǎn)生四個核心模塊的具體版本，從而設計出解決該具體問題的學習系統(tǒng)。以計算機下跳棋系統(tǒng)為例，四個核心模塊為：1.行動模塊(又稱行為系統(tǒng))。接受感知信息(輸入)，決定系統(tǒng)所要采取的行動。在計算機下跳棋問題中，行動就是走步。該模塊的輸入為一局新棋(連同當前學習到的目標函數(shù)V),輸出為本局棋的走步序列(產(chǎn)生一個新的間接訓練例)。其基本策略是：根據(jù)學習到的目標函數(shù)V決定每一步的走法。顯然，隨著匕的不斷精密化，系統(tǒng)的性能將不斷改善。一般來說，學習的目的是改進行動模塊的性能，所以我們首先要弄清楚行動模塊中哪些成分需要改進。行動模塊可能有以下各種成分，它們都能夠被學習改進：從當前狀態(tài)(的條件)到行動的直接映射從感知信息序列推斷出環(huán)境的有關性質的手段關于環(huán)境演變方式的信息關于系統(tǒng)可采取的可能行動的后果信息指示狀態(tài)是否良好的輔助信息指示在特定狀態(tài)采取特定行動是否合適的“行動一值”信息目標，它描述一組使系統(tǒng)能力得到最大發(fā)揮的狀態(tài)行動模塊需要改進的成分的表達方式有確定性描述，邏輯公式，概率描述，等等，都可以抽象地描述為函數(shù)(稱為目標函數(shù)，學習的任務就是要獲得目標函數(shù)的定義，使之與訓練例最為匹配(在滿足系統(tǒng)的一般約束條件下)。2?評價模塊(又稱批評模塊)。根據(jù)系統(tǒng)外固定的性能標準，接受關于系統(tǒng)行為后果的感知信息，評價系統(tǒng)的性能，并將評價意見反饋給學習模塊。在計算機下跳棋系統(tǒng)中，評價模塊以行動模塊的輸出(新的棋局歷史，即新的間接訓練例)作為自己的輸入，產(chǎn)生一組形如bvtrain(b))的直接訓練例子，其中b為棋局歷史中出現(xiàn)的各個棋盤態(tài)勢，訓練值Vtrain(b)的計算使用我們上面講過的公式Vtrain(b)-V(succ(b))。將這些新的直接訓練例子反饋給學習模塊，以改進目標函數(shù)V。一般來說，我們可以有以下幾種可以使用的反饋：若目標函數(shù)(即要改進的行動成分的數(shù)學表達)的輸入和輸出(實際輸出和正確的輸出)都是可以感知的，稱為有指導的學習若只有對實際輸出的評價，卻不給出正確的輸出值，稱為強化學習(又稱獎懲式學習)；若對正確的輸出值沒有任何提示，稱為無指導的學習。計算機下跳棋問題是一個典型的強化學習問題。3?學習模塊(又稱推廣模塊)。了解行動模塊的工作特性，接受評價模塊發(fā)來的關于系統(tǒng)性能的反饋信息，決定并告訴行動模塊應如何改進以圖在將來更好地工作。在計算機下跳棋系統(tǒng)中，學習模塊以評價模塊的輸出（形如（b,Vtrain（b））的直接訓練例子）作為自己的輸入，用以改進目標函數(shù)V（即改進它的各個系數(shù)叫），以圖在下一盤棋中系統(tǒng)能顯示更好的性能。按照我們前面的選擇，采用的學習算法是LMS系數(shù)調整規(guī)則。4?問題生成模塊（又稱試驗生成模塊）。根據(jù)學習模塊給出的學習目標，向行動模塊建議進行某種偏離常規(guī)的探索性行動，試圖獲得新的有價值的經(jīng)驗。在計算機下跳棋系統(tǒng)中，問題生成模塊可簡單地建議“用新的目標函數(shù)V從頭再下一盤”，以遞推地改進V也可以根據(jù)學習模塊提供的其它改進意見生成特殊的殘局讓行動模塊去下，以探索新的經(jīng)驗（即搜索狀態(tài)空間中了解得還不夠充分的特定部分），從而提高系統(tǒng)的整體性能。1.3機器學習所研究的主要問題將上面討論的計算機下跳棋問題一般化，我們可以看到，研究一個機器學習問題或設計一個機器學習系統(tǒng)，需要弄清楚如下要點：學習任務T性能度量P訓練例E抽象的目標函數(shù)F（代表系統(tǒng)行為中需要學習改進的成分）目標函數(shù)的具體（近似）表示F（如系數(shù)待定的數(shù)學函數(shù)）從訓練例E導出F值的方法根據(jù)F的特殊輸入/輸出對子，學習改進F的定義的方法我們可將機器學習看成是搜索問題。作為搜索問題，我們要考察搜索空間，搜索空間的結構，搜索目的，搜索策略及其收斂性，等等。機器學習問題的搜索空間（又稱假設空間）是所有可能的目標函數(shù)（又稱假設）；目標函數(shù)的表達方式?jīng)Q定了搜索空間的結構；搜索目的是尋找與訓練例最為匹配的（且滿足系統(tǒng)的一般約束條件的）假設；搜索策略就是針對各種不同結構的搜索空間的學習算法，是機器學習領域的主要研究對象。理論上，主要問題是學習算法的收斂性，以及關于訓練例的數(shù)量，搜索空間的大小和特性，對學習到的假設的信任度（它能正確解釋未來實例的能力）這三者之間關系的定量分析?！皩W習即搜索”是本書的基本觀點，從這個觀點出發(fā)，我們可以總結出機器學習所研究的主要問題：從特殊訓練例學習一般性目標函數(shù)的算法有哪些一個特定的算法在何種條件下能夠收斂到所求的函數(shù)（當然要給予它充分多的訓練數(shù)據(jù)）各種算法最適用于何種學習問題和何種表達方式多少訓練例算是充分的訓練例的數(shù)量，搜索空間的大小和特性，對學習到的假設的信任度這三者之間有何定量關系學習系統(tǒng)掌握的先驗知識在什么情況下及如何指導學習過程近似正確的先驗知識也能被利用嗎學習過程中選用下一個訓練例的最佳策略是什么選例策略對系統(tǒng)的復雜度有什么影響如何將學習任務化為函數(shù)近似問題（即如何找出特定的函數(shù)）這一過程能夠自動化嗎系統(tǒng)如何自動地改變自己的表達方式以加強表示和學習目標函數(shù)的能力本書后面的章節(jié)將根據(jù)機器學習領域的研究成果，對這些問題進行回答。第二章概念學習1導言概念學習是一種有指導的學習。設有對象集合X（如所有動物），一個概念c（如鳥類）定義了一個對象類，即X的一個子集。概念學習意味著從概念的正例（屬于該類的一些對象）和負例（不屬于該類的一些對象）導出概念的定義。參考機器學習問題的一般表述格式，概念學習問題的要點為：學習任務門判別任一對象是否屬于概念c性能度量P：用該定義判別訓練例之外的對象是否屬于c的準確率訓練例E：＜對象，屬于或不屬于C＞抽象的目標函數(shù)F:XBool目標函數(shù)的具體(近似)表示F:施加于對象的各個屬性的約束的合取式從訓練例E導出F值的方法：此處為直接訓練例，無需轉換根據(jù)F的特殊輸入/輸出事例，學習改進F的定義的方法：2?2概念學習任務為了敘述的方便，我們把概念學習任務表達為與上面的格式等價的形式：給定：對象集合X,每一個對象xX由n個屬性A】,A2,…,An描述目標概念c:XBool訓練例集E：每個訓練例形如＜x,c(x)＞。E分為正例集E+和負例集E-oc(x)=true的例子稱為正例，c(x)=false的例子稱為負例。假設空間H：每個假設hH和c一樣是布爾函數(shù)XBool。我們暫時只考慮一種簡單的表示方法，將h表達為施加于對象的各個屬性的約束的合取式。若對象x滿足所有的約束，則h(x)=true，即：h判定x屬于目標概念c,為一個正例。為閱讀的方便，我們將假設h寫成W],v2,…,vn＞的形式，讀作：“亠的值為v1且A2的值為v2且…且An的值為vn”。vi可取特殊值“”，表示屬性Ai可取任意值；若某vi為，則表示屬性Ai取任意值均不容許，此時h將所有對象均判定為負例。確定：H中與目標概念c完全一致的假設h：xXh(x)=c(x)注意，上面要求找到與目標概念c在全體對象集X一致的假設札但是，除了在訓練例集E上,c(x)的值是系統(tǒng)所不知道的，我們無法斷定假設h是否達到了要求。我們能保證的只是：假設h與目標概念c在訓練例集E上是一致的。因此機器學習領域通常采用所謂“歸納學習假說'：任何在充分大的訓練例集E上對目標概念C作出良好近似的假設7亦將在其它未見例子上對目標概念作出良好近似。2?3假設空間上的一個偏序概念學習是對假設空間H的搜索。H的元素是假設，每一個假設h是一個布爾函數(shù)。在假設空間H上有一個偏序(稱為一般化序g),它使假設空間H具有格的結構，有利于對H的搜索。因此在講任何搜索算法之前，我們先來討論這個偏序。定義。設h1,h2是定義在對象集X上的兩個布爾函數(shù)。我們說h比h2更一般(亦稱h2比h更特殊)，記為h1gh2,當且僅當xx(h2(x)h](x))直觀上說，“h比h2更一般”意味著：滿足h2的對象也滿足錢，所以h劃定的對象子集包含著h2劃定的對象子集。定義。設h1,h2是定義在對象集X上的兩個布爾函數(shù)。我們說h1比h2嚴格地更一般記為h1>gh2,當且僅當(h1gh2)(h2gh1)2?4尋找與正例一致的最特殊假設的算法Find-S機器學習文獻中利用一般化序g的搜索算法有很多，我們現(xiàn)在要講的第一個O搜索算法是尋找與正例一致的最特殊假設的算法Find-S。所謂“與正例一致的最特殊假設”是指覆蓋所有觀察到的正例(即對所有觀察到的正例均能正確判定)的最特殊的假設(其它覆蓋所有觀察到的正例的假設均比此假設更一般)，又稱“極大特殊假設"(maximallyspecifichypothesis)或“極小一般假設”(leastgeneralgeneralizatin--lgg)。Find-S算法從最特殊的假設h開始，沿著偏序g的一條鏈對h進行一般化。O在每一步(處理一個新的正例X)，只做最必要的一般化使h覆蓋x。從而，在算法的任意時刻，h總是覆蓋迄今所觀察到的所有正例的最特殊的假設。Find-S算法的形式化描述如下:算法：Find-S。將h初始化為最特殊的假設對每一個觀察到的正例x對h中的每一個屬性約束a.如果約束a.被x滿足則什么也不做否則a.被x滿足的下一個更一般的約束3?輸出假設h下面給出算法Find-S的運行例子并加以討論。Find-S算法的的一個運行例:對于概念學習，我們目前只考慮最簡單的一種假設表示方法：將h表達為施加于對象的各個屬性的約束的合取式。我們將假設h寫成＜V],v2,…,vn＞的形式，讀作：劃的值為V]且A2的值為v且…且An的值為vn”。v可取特殊值“”，表示屬性Ai可取任意值；若某V.為，則表示屬性Ai取任意值均不容許，此時h將所有對象均判定為負例。下面是這種簡單表達方式的一個例子：對象：日子目標概念：適合沖浪運動：日子集DBool訓練例：日子屬性表A1A2A3AAA4A5A6正/負例陰晴氣溫濕度風力水溫明日預報X1SunnyWarmNormalStrongWarmSame正X2SunnyWarmHighStrongWarmSame正X3RainyColdHighStrongWarmChange負

X4SunnyX4SunnyWarmHighStrongCoolChangeFind-S算法運行歷史:h0遇正例x1:h1<SunnyWarmNormalStrongWarmSame>遇正例x2:h2<遇正例x1:h1<SunnyWarmNormalStrongWarmSame>遇正例x2:h2<SunnyWarmStrongWarmSame>遇負例x3:h3<SunnyWarmStrongWarmSame>h2遇正例x4:h4<SunnyWarmStrong輸出覆蓋所有正例的最特殊的假設h4，此假設斷言：“晴朗，溫暖，有強風的天氣適合沖浪運動"。注：假設h4是與所有觀察到的正例一致的最特殊假設，也與負例一致。關于算法Find-S的討論：簡單表達方式下算法中一些操作的具體實現(xiàn)：“最特殊的假設”為<,,…，>p的被x滿足的下一個更一般的約束”next（a）：若a=貝Vnext（a）=（即當前正例x的屬性值v）若a=u（貝Unext（a）=（即任意值均可）算法的關鍵性質：對于簡單表達方式（將h表達為施加于對象的各個屬性的約束的合取式），算法必定輸出覆蓋所有觀察到的正例的最特殊的假設；并且，若H含有正確的目標概念:且訓練例無誤，則結果與負例也一致（盡管算法中遇到負例時什么也未做）。證明：在任何時刻，h總是覆蓋迄今所觀察到的所有正例的最特殊的假設，而因為H含有正確的目標概念c,故c也可看成是一個覆蓋迄今所觀察到的所有正例的假設。因此，cgh。另一方面，正確的c不覆蓋負例，所以h也不會覆O蓋負例。（反之，若訓練例為x1SunnyWarmNormalStrongWarmSame正X2SunnyWarmHighStrongWarmSame正X3SunnyWarmMiddleStrongWarmSame負則H中不含有正確的目標概念c（即c無法用簡單的表達方式表示），算法的結果不能保證與負例一致。）算法存在的問題：不能保證結果收斂到目標概念c（只知道結果h與訓練例一致，不知h是否為唯一的與訓練例一致的假設）。只能找到與訓練例一致的最特殊假設。有時我們可能希望得到與訓練例一致的最一般假設或某中間假設，F(xiàn)ind-S算法不能滿足這些需要。不能識別和處理訓練例中的錯誤和噪音。此算法根本不檢查負例，而假定數(shù)據(jù)的完全正確性。這樣，實際問題中通常存在的錯誤和噪音將嚴重影響算法結果的有效性。不能處理多個極大特殊假設的情況。在簡單表達方式下，只有一個極大特殊假設，F(xiàn)ind-S算法沿著偏序的一個分支搜索即可。若表達方式復雜一些，可能有多個極大特殊假設，而目標概念c是其中的一個。這時算法應具有回溯功能。另外，有的問題可能不存在極大特殊的一致性假設。我們在后面講解別的學習算法時，將要考慮這些問題。2.5版本空間與候選剪除算法第二個利用一般化序G的搜索算法是候選剪除算法。Find-S算法僅給出一個O特定的與訓練例一致的假設，而候選剪除算法給出所有與訓練例一致的假設（并非列舉，而是給出一致假設集合的一個描述）。候選剪除算法的策略是維持一致假設集合的一個簡潔表示，并力圖通過訓練例不斷地改進這個表示。候選剪除算法雖比Find-S算法好，但仍不能處理噪音問題。我們講解這兩個算法的主要目的不是為了實用，而是為了引入機器學習的一些重要概念。5?1版本空間及其結構定義。假設h與訓練例集E一致，記為consistent(h,E),當且僅當：(艸))eh(x)=c(x)定義。對于假設空間H和訓練例集E的版本空間是所有與E一致的假設的集合(此集合中的每一個假設均是目標概念c的一個可能的版本)，記為VShe：VShe={hH|consistent(h,E)}定義。對于假設空間H和訓練例集E的一般化界G是H中與E一致的極大一般化成員的集合：G={gH|consistent?E)g,H[g，>ggconsistent(g：E)]}定義。對于假設空間H和訓練例集E的特殊化界S是H中與E一致的極小一般化成員的集合：S={sH|consistent^,E)s，H[s>gs'consistent(s：E)]}定理。只要G和S能夠合適地定義，版本空間就完全被它們所確定：VSH,E={hH1(sS)(gG)(gghgs)}證明：5.2候選剪除算法下面的候選剪除算法計算G和S,從而計算出整個的版本空間(由上面的定理)。算法適用于所有的概念學習問題，但其中有幾個操作依賴于對象和假設的具體表示方法。在下面的算法描述中，我們特意指出這些依賴于具體表示的操作,并在注解中說明在本章所考慮的簡單表示方式下它們的具體形式：算法：候選剪除。將G初始化為H中的最一般假設的集合%%{<,,…，>}將S初始化為H中的最特殊假設的集合%%{<,，…,>}對每一個訓練例x如果X是正例則從G中剪除所有與X不一致的假設對S中每一個與X不一致的假設s將s從S中剪除S'$|s，為s的最小一般化s'與X一致G中某成員比s'M（嚴格）一般}SSS，從S中剪除比S中另一個假設更（嚴格）一般的所有假設如果X是負例則從S中剪除所有與X不一致的假設對G中每一個與X不一致的假設g將g從G中剪除G'?Ig，為g的最小特殊化g，與X一致S中某成員比g'更（嚴格）特殊}GGG'從G中剪除比G中另一個假設更（嚴格）特殊的所有假設例子：再次考慮本章前面的簡單表示方式的例子:X1SunnyWarmNormalStrongWarmSame正X2SunnyWarmHighStrongWarmSame正X3RainyColdHighStrongWarmChange負X4SunnyWarmHighStrongCoolChange正候選剪除算法的運行歷史如下:G0={<,，…,>}S0={<,,…,>}

遇正例x1:G]=G0（不變）s=<,,…，>S'={<SunnyWarmNormalStrongWarmSame>}S]={<SunnyWarmNormalStrongWarmSame>}遇正例x2:G2=G]（不變）s=<SunnyWarmNormalStrongWarmSame>S'={<SunnyWarmStrongWarmSame>}S2={<SunnyWarmStrongWarmSame>}遇負例x3:S3=S2（不變）g=<,,…,>G'={<Sunny>,<Warm>,<_Normal><Weak>,<Cool>,<Same〉}標記x3為負例的比G2特殊一點的假設集合利用第3個條件,去掉不能覆蓋前面正例的那些假設）={<Sunny>,<Warm>,<Same>}G3={<Sunny>,<Warm>,<Same>}遇正例x4:G4={<Sunny>,<Warm>,<Same>}s=<s=<SunnyWarmStrongWarmSame>>}S'={<SunnyWarmStrong>}S4={<SunnyWarmStrong>}輸出S4和G4，這兩個界集合劃定了整個的版本空間（含6個與訓練例一致的假設）：特殊界中間S4={<SunnyWarmStrong特殊界中間S4={<SunnyWarmStrong>}{<SunnyStrong><SunnyWarm><WarmStrong>}G4={<Sunny>,<Warm>}一般界本例的結果與訓練例的次序無關。當遇到更多的訓練例時，S和G將單調地越來越靠近，劃定越來越小的版本空間。算法的討論收斂性。若訓練例無錯，且目標概念包含在H中，則此算法計算出的版本空間收斂于目標概念。（因為每一個訓練例均排除一些對目標概念的模糊認識，當充分多的訓練例被觀察到時，G和S這兩個界將收斂于同一個假設，它就是那個包含在H中的目標概念）。噪音處理。此算法不能處理噪音。例如，若正例e被錯標為負例，則目標概念與e不一致，按算法步驟目標概念將被剪除，從而不可能計算出正確的目標概念。關于噪音，本算法只有一點可以做到：若訓練例中有噪音或目標概念不包含在H中（假設h的表示方式無法描述目標概念），當有充分多的訓練例被觀察到時，G和S這兩個界將收斂于空集，即版本空間為空，表明H中沒有與所有訓練例一致的假設。訓練例的次序。如果學習系統(tǒng)能夠自己做實驗生成例子并通過請教外部教師知道生成的例子是正是負，我們說該系統(tǒng)能夠查詢。假定系統(tǒng)已經(jīng)計算出上面的含有6個假設的版本空間，下一步應該查詢什么（即生成什么例子來請教外部教師）最理想的例子x*應被版本空間中一半的假設判為真，被另一半的假設判為假。無論教師說x*是正例還是負例，算法必將把版本空間縮小一半。例如在我們的簡單實例中，x*為＜SunnyWarmNormalweakWarmSame＞。如果這樣的x*總是可以確定，系統(tǒng)只要做log2HVII次實驗就能發(fā)現(xiàn)目標概念。可惜，在多數(shù)問題里難以確定恰與版本空間中一半的假設匹配的實例，所以通常要做多于log2IVII次實驗才能找到目標概念。4．未完全學習出的概念的應用。當版本空間尚含有多個假設時，目標概念尚未完全學習出來。但是，仍然可以用這個部分學習出的概念來判別新的例子。在特殊情況下判別的可信度如同用真正的目標概念來判別時一樣；多數(shù)情況下可信度會降低，但我們可以給出可信度的度量。例如在我們的簡單實例中，用部分學習到的含6個假設版本空間來判別下面4個新例子：X5SunnyWarmNormalStrongCoolChange正/負X6RainyColdNormalLightWarmSame正/負X7SunnyWarmNormalLightWarmSame正/負X8SunnyColdNormalStrongWarmSame正/負因為版本空間的所有假設均認為X5是正例，所以目標概念也將判它為正例。因為版本空間的所有假設均認為是負例，所以目標概念也將判它為負例。因為版本空間的假設一半認為X7是正例，一半認為X7是負例，所以X7應該被選擇為下一個查詢x*。因為版本空間的假設1/3認為X8是正例，2/3認為X8是負例，所以X8應該按多數(shù)的意見被判定為負的，其可信度可置為（若H中所有假設具有相等的先驗概率）。2．6歸納偏向本節(jié)在候選剪除算法的框架下討論歸納學習的幾個根本問題，但結論對任何概念小系統(tǒng)均有效。這些根本問題為：目標概念不在假設空間里怎么辦是否應該使用包含一切可能假設的空間假設空間的大小如何影響必須觀察到的例子的數(shù)量假設空間的大小如何影響算法判別非訓練例子的能力6?1有偏向與無偏向的概念學習在我們簡單的表示方式中，對假設空間已經(jīng)有了偏向：只認為那些表達為施加于對象的各個屬性的約束（A=v〃）的合取式是可能的假設。在此偏向下，很普通的概念如（A1=v1A1=v2,sky=sunnyorsky=cloudy）也表達不了?；氐揭郧拔覀兛疾爝^的訓練例：x1SunnyWarmNormalStrongWarmSame正x2CloudyWarmNormalStrongWarmSame正x3RainyWarmNormalStrongWarmSame負則H中不含有正確的目標概念t（即c無法用簡單的表達方式表示），候選剪除算法返回空版本空間。我們來看一看這個偏向究竟有多大。設實例問題中對象的六個屬性分別可取2,2,3,2,2,2個值。對象空間X中共有2*2*3*2*2*2=96個對象，即11X11=96。每一個可能的概念是X的一個子集，所有可能的概念總數(shù)為X的子集的個數(shù)=2961028。而簡單的表示方式（合取式）只能表達3*3*4*3*3*3+1=973種可能的假設（即可能的概念），即偏向的假設空間H只是完全的假設空間川（可用簡單假設的任意合取，析取，非操作聯(lián)合操作來表達）極小的一部分，亦即偏向是極為嚴重的。如果我們使用無偏向的假設空間川，目標概念的表達問題是解決了，但又會出來另一個同樣麻煩的問題：候選剪除算法對訓練例將不能做任何一般化工作。換句話說，版本空間不能判定任何非訓練例，為了收斂到目的概念，只有將所有的例子均作為訓練例！因為在H伯勺情況下，特殊界S中只有一個假設觀察到的正例的析取，一般界G中也只有一個假設觀察到的負例的析取式的非。如果用這樣的版本空間V去判別任何非訓練例x,VS中總是一半假設將x判為正例，另一半將x判為負例（設hVS判x為正，則有hH食它判x為負，此外與h毫無二致，故X和h一樣也與所有訓練例一致，即hVS），我們沒有得到任何信息。只有將所有的例子均作為訓練例，才能得到目標概念。這樣的學習顯然是毫無用處的。6?2歸納偏向的形式化定義從上面的討論我們可得出所謂歸納學習的基本性質無偏見即無預言。（學習系統(tǒng)若對目標概念無任何偏見，它也就沒有任何依據(jù)去判別未見實例）?？梢娖妼τ跉w納學習來說是必不可少，至關重要的。首先，我們需要給歸納偏見一個更嚴格的定義。定義。設有X：對象集c：X上的任一目標概念Dc：c的任意（無錯的）訓練數(shù)據(jù)集{"c（x）＞}L：概念學習算法（包括它所搜索的假設空間H）X：任一個對象XL（x,Dc）:學習算法L完成在Dc上的訓練之后對x的明確判定cc則滿足下面條件的最小限制B稱為L的歸納偏向：Xc,d（BDcX）卜L（XtDc）簡單地說，學習算法L的歸納偏向B是使L對非訓練例x的判別結果可靠的附加條件。對未見例子的判別結果本是歸納推理的結果，一般不能保證是演繹推理的結果。但是，用歸納偏向作為附加前提，歸納成為演繹。也就是說，如果歸納偏向成立，學習算法對未見例所做出的判別都是正確的；但如果歸納偏向不成立，則不僅不能保證這一點，學習算法甚至可能學不出任何假設！對于候選剪除算法，無論它的假設空間H如何定義，我們有：X：對象集c：X上的任一目標概念Dc：c的任意（無錯的）訓練數(shù)據(jù)集{＜x,c（x）＞}L：候選剪除算法（包括它所搜索的假設空間H）X：任一個對象XL（x,DC）:若學習出的版本空間的所有假設均一致判別x為正（負）則判別x為正（負），否則“不知道”B：目標概念c在假設空間H內(nèi)下面我們來證明：x,c,DcBDcx)卜L(x,Dc)即證明：B(c(x)=L(x,Dc))證明：?/cH(B)?cVS（VS的定義，訓練例無錯）???c（x）=L（x,Dc）（L（x,DJ是根據(jù)“一致投票”，包括c的判別）這樣，候選剪除算法的歸納偏向是“目標概念c在假設空間H內(nèi)”，亦即“假設的表示方式能夠表示目標概念”。6?3歸納偏向的分類和用途不同的歸納學習算法采用不同的歸納偏向。有的歸納偏向如“目標概念c在假設空間H內(nèi)”屬于范疇假定；有的歸納偏向如“特殊的假設優(yōu)先于一般的假設”僅規(guī)定了假設的優(yōu)先次序；迄今講到偏向均為隱含的，不能被學習系統(tǒng)改變的偏向，以后我們將遇到另外一種歸納偏向系統(tǒng)可以表達和處理的顯式斷言。歸納偏向可被用來對學習算法預測未見例子的策略進行非過程性刻畫。我們還可以比較各種學習算法所用的歸納偏向的強度，偏向越強的算法歸納步子越大,它所敢于判別的未見例子的比例越大。下面我們比較三個偏向越來越強的算法：死記硬背的算法：歸納偏向：無方法：僅僅記住訓練數(shù)據(jù)；新例若與某訓練例一樣，判別之，否則不判別能判別的未見例子的比例：0%候選剪除算法：歸納偏向：目標概念c在假設空間H內(nèi)方法：計算出版本空間VS；新例若被皿一致“表決”，判別之，否則不判能判別的未見例子的比例：在0%與100%之間3.Find-S算法：歸納偏向：目標概念c在假設空間H內(nèi)任何對象x,除非能夠用別的知識證明它為正例，均為負例方法：計算出最特殊的一致假設力；任何新例均被h判別能判別的未見例子的比例：100%遺留問題：偏向與搜索效率的關系“偏向是對假設空間的限制”與這里的歸納偏向定義之間的關系第三章決策樹學習決策樹學習是一種歸納學習方法，它的特點有：它是學習離散值目標函數(shù)的近似表達的方法。學習出的函數(shù)表示為決策樹，但也可改寫為易讀的ifthen規(guī)則。實用性強，許多著名的學習系統(tǒng)（ID3,ASSISTANT,等）皆基于此方法,并成功應用到許多實際領域（學習疾病的診斷，信貸風險的評價，等）。3.它能較好地抵抗噪音。4.它能學習析取表達式。5.它搜索完全的假設空間。6.它的歸納偏向是小樹優(yōu)先于大樹。3.1決策樹表示方法定義。決策樹決策樹是定義布爾函數(shù)的一種方法，其輸入為由一組屬性描述的對象，輸出為yes/no決策。樹的每一個內(nèi)部節(jié)點（包括根節(jié)點）是對輸入的某個屬性的測試,此節(jié)點下面的各個分支被標記該屬性性質的各個值。每一個葉節(jié)點指示：達到該節(jié)點時布爾函數(shù)應返回的yes/no值。一棵決策樹代表一個假設，可以寫成邏輯公式。設輸入的屬性集為｛勺‘a(chǎn)2…,An｝，則決策樹可寫成：所有以yes結束的路I°(A1=vii)(A2=v2^…(An=v所有以yes結束的路I決策樹的表達能力限于命題邏輯（因為這里隱含地只涉及一個對象），該對象的任一個屬性的任一次測試是一個命題。在命題邏輯范圍內(nèi)，決策樹的表達能力是完全的。即：任何布爾函數(shù)均可寫成決策樹。有的布爾函數(shù)適合用決策樹表示，有的布爾函數(shù)不適合用決策樹表示（引起組合爆炸）。實際上，根本不存在一種表達，它對所有布爾函數(shù)都是高效的。就實際應用來說，分類問題（將實例劃歸為若干個可能的類的問題）最適合決策樹學習方法。實際上具有下列特征的問題都適合用決策樹學習方法解決：對象由屬性-值的對子序列表示。對象具有確定個數(shù)的屬性，屬性可取若干離散值（取值個數(shù)越小越好）。我們將看到，有些新的改進的算法還可以處理實數(shù)型屬性。目標函數(shù)具有離散型輸出值。最常見的是布爾型目標函數(shù)，但基本的決策樹學習算法很容易推廣到一般的具有離散型輸出值的目標函數(shù)。我們將看到，有些新的改進的算法還可以處理實數(shù)型目標函數(shù)?？赡苄枰鋈”磉_式描述的問題。顯然決策樹可自然地表達邏輯析取式。訓練例有噪音。決策樹學習對訓練數(shù)據(jù)中的噪音具有抵抗力。噪音包括：訓練例的分類錯；訓練例的屬性值錯；訓練例的屬性值不全；等2基本的決策樹學習算法決策樹學習的核心算法（如Quinlan的ID3算法）是在所有可能的決策樹的空間中的一種自頂向下，貪婪的搜索方法。我們先講解以ID3為代表的核心算法，然后再介紹以ID3的后繼算法為代表的各種改進。2?1決策樹學習核心算法(ID3)的簡化描述算法。ID3輸入：Es:訓練例集c:目標概念As:屬性表輸出：能夠正確判別Es的決策樹遞歸算法：Q3fEs,c,As)建立決策樹的根節(jié)點root若Es均為正例，則返回單節(jié)點樹root,root標記+若Es均為負例，則返回單節(jié)點樹root,root標記-若As為空，則返回單節(jié)點樹root,root標記為Es中占多數(shù)的c值root的決策屬性As中可對Es進行最佳分類的屬性4對4的每一可能的值v從root射出一條弧，代表測試A=vEsvEs中屬性A取值為v的那些例子組成的子集若Esv為空則在此弧下加一節(jié)點，該節(jié)點標記為Es中占多數(shù)的c值否則在此弧下加一子樹ID3(Esv,c,As-{A})返回以root為根的決策樹2.2最佳分類屬性的確定ID3算法的關鍵是確定As中可對ES進行最佳分類的屬性A,即在樹的每一個節(jié)點上確定一個候選屬性，它的測試對訓練例的分類最有利。對這個看起來含糊的選擇標準，我們首先需要一個量化的尺度。下面我們分兩步講解這個尺度。?訓練例分類純度的度量熵信息論中通常用熵度量一組實例在某方面的純度。給定訓練例集Es,其中正例的比例為耳，負例的比例為p_=1-p+。Es的關于這個布爾分類的純度可用熵定義為：Entropy（Es）=-p+log2p+-plog2p它稱為Es關于布爾分類的熵。（我們約定olog2o=0）。為了粗略地解釋熵如何指示實例集Es在布爾分類方面的純度，讓我們考察幾個極端的情況。當純度最高時，即Es中的實例均為正例（p+=1）或均為負例（p_=1）,在任何一種情況下，熵均為極小值0當純度最低時，即Es中的正例和負例各占一半時（p+=），熵均為極大值1;在其他情況下，熵的值在0和1之間。這就是說，實例集在目標分類方面越模糊越雜亂越無序，它的熵就越高；實例集在目標分類方面越清晰越純潔越有序，它的熵就越低。信息論對熵的解釋是“為Es中的任意實例的分類結果進行編碼所需的最少比特數(shù)”。若p=1,所有實例均為正例，無需編碼，比特數(shù)為0；若p=，需要一個比特編碼；比特數(shù)為1；若p=（正例多而負例少），比特數(shù)小于1。熵的概念可擴充到多值目標函數(shù)。若目標函數(shù)可取n個不同的值，則Es關于n值分類的熵定義為：Entropy（Es）=i=i2.：,n（-卩皿p,）其中p,?為Es中屬于第i類的實例所占的比例。注意此時熵的極大值可達log2n。?預計熵減弱的度量信息贏取設Es當前的熵為E，若用一個屬性A將Es分組（A=v的實例分在同一組Esv），E將會降低（因為這是一個從無序向有序的轉變過程）。預計E降低的數(shù)量稱為屬性A相對于實例集Es的信息贏取Gain（Es,A）,定義為：Gain（Es,A）=Entropy（Es）-vVaiue（A）（lEsvl/|Es|）Entropy（Esv）屬性A的信息贏取可以從幾個方面進行解釋：預計由于了解分析A的值而引起的熵減弱（有序化）；預計由于了解分析A的值而獲得的關于目標分類的信息；預計由于了解分析A的值而節(jié)省的為Es中的任意實例的分類結果進行編碼所需的比

特數(shù)?？傊畔②A取越大的屬性對訓練例的分類越有利。3?如何確定As中可對Es進行最佳分類的屬性ID3算法就是根據(jù)“信息贏取越大的屬性對訓練例的分類越有利”的原則在算法的每一步選取“As中可對Es進行最佳分類的屬性。因此，計算各個屬性的信息贏取并加以比較是ID3算法的關鍵操作。3.2.3ID3算法運行實例考慮下面的概念學習問題:日子目標概念：適合打網(wǎng)球:日子集DBool日子目標概念：適合打網(wǎng)球:日子集DBool訓練例:日子屬性表A1陰晴A2氣溫A3濕度A4風力正/負例x1SunnyHotHighWeak負X2SunnyHotHighStrong負X3OvercastHotHighWeak正X4RainyMildHighWeak正X5RainyCoolNormalWeak正X6RainyCoolNormalStrong負X7OvercastCoolNormalStrong正X8SunnyMildHighWeak負X9SunnyCoolNormalWeak正X10RainyMildNormalWeak正X11SunnyMildNormalStrong正X12OvercastMildHighStrong正

13OvercastHotNormalWeak14RainyMildHighStrong13OvercastHotNormalWeak14RainyMildHighStrong下圖顯示了ID3算法的前幾步運行的歷史。ID3算法運行歷史：Es=[x,x,A,x][9+,5-]1214Entropy(Es)=0.940;Gain(Es,A”—0.248;Gain(Es,A?)=0.151;Gain(Es,A3)=0.048;Gain(Es,A4)=0.029;,x10,x10,x14]3．2．4決策樹學習的搜索空間和搜索策略ID3搜索的假設空間是所有可能的決策樹的集合。ID3搜索的目的是構造與訓練數(shù)據(jù)一致的一棵決策樹（即能夠對訓練例進行正確分類的一棵決策樹）。ID3的搜索策略是爬山法，在構造決策樹時從簡單到復雜，用信息贏取作為指導爬山法的評價函數(shù)。與我們學過的候選剪除等方法比較，ID3式的基本決策樹學習算法有優(yōu)點，也有缺點：優(yōu)點：其搜索空間是完全的假設空間，目標函數(shù)必在搜索空間中，不存在無解的危險。全盤使用訓練數(shù)據(jù)，而不是象候選剪除算法一個一個地考慮訓練例。這樣做的優(yōu)點是可以利用全部訓練例的統(tǒng)計性質進行決策，從而抵抗噪音（個別例子中的錯誤數(shù)據(jù)）?？梢院苋菀椎匦薷腎D3算法的終止條件，使之能夠獲得與訓練數(shù)據(jù)不完全一致的假設。缺點：搜索中只維持一個解，不能象候選剪除算法那樣返回所有可能的與訓練例集一致的假設，并優(yōu)化地查詢新例以獲得收斂于目標函數(shù)的解。其搜索無回溯。如同一般的無回溯爬山搜索一樣，它可能收斂于局部最優(yōu)解而丟掉全局最優(yōu)解。ID3沿著一條路選擇的決策樹可能沒有在各個分支上搜索所遇到的一些決策樹好。后面我們將介紹增加回溯的方法（決策樹的后剪除方法）。因為不是一個一個地考慮訓練例，不容易象候選剪除算法那樣使用新例步進式地改進決策樹。2.5決策樹學習的歸納偏向第二章給出了歸納偏向的形式化定義：XC,Dc（BDcX）卜l.（XtDC）這就是說，學習算法的歸納偏向B是一組隱式或顯式的條件。歸納偏向決定了學習算法對未見實例進行分類的策略（包括對何種未見實例能夠進行正確的分類）。若歸納偏向的條件被滿足，學習算法對未見實例給出的分類結果總與目標函數(shù)一致。在下面關于ID3算法的歸納偏向的討論中，未能嚴格遵循上述形式化的定義。ID3的歸納偏向是在許多與訓練數(shù)據(jù)一致的決策樹中選擇一棵特定樹的搜索優(yōu)先級方面的偏向。而且，由于ID3算法每一步在選擇屬性時使用的誘導函數(shù)（學習贏取）與當時對應的實例集之間的相互作用相當微妙，很難給出它的準確的歸納偏向的描述。但是，不難給出ID3近似的歸納偏向：短樹優(yōu)先于長樹；信息贏取越高的屬性越靠近樹根的樹優(yōu)先于其他樹。下面我們對歸納偏向問題再做一點更深入的討論：1．兩種不同的偏向：有的歸納學習算法的假設空間不完全而搜索卻是完全的（如候選剪除算法），此時的歸納偏向完全是關于假設的表達方面的問題，稱為限制性偏向（或語言偏向）。有的歸納學習算法的假設空間是完全的而搜索卻是不完全的（如ID3算法），此時的歸納偏向完全是關于搜索策略方面的問題，稱為優(yōu)先性偏向（或搜索偏向）。第一章講的計算機下跳棋問題則綜合運用兩種偏向：將棋盤評價函數(shù)定為線性函數(shù)是一種語言偏向，而在調節(jié)系數(shù)時使用的最小均方系數(shù)調整規(guī)則（LMS系數(shù)調整規(guī)則）是一種搜索偏向。2．Occam剃刀原理（為何偏向簡短的假設）。ID3的短樹優(yōu)先于長樹的偏向是所謂Occam剃刀原理的一種體現(xiàn)。Occam剃刀原理的一般表達為：偏向與數(shù)據(jù)一致的最簡單假設現(xiàn)在的問題是“為什么”這是幾百年來哲學家們爭論不休的問題。一般的解釋是，與數(shù)據(jù)一致的簡單假設的數(shù)量大大少于與數(shù)據(jù)一致的復雜假設的數(shù)量，所以簡單假設與數(shù)據(jù)統(tǒng)計巧合的機會比復雜假設要小得多，從而選取簡單假設更為保險。當然可以想出許多理由反對Occam剃刀原理，但是象貝葉斯統(tǒng)計和演化計算等理論可為Occam剃刀原理提供一定的解釋和支持，我們再此不予詳述。3．3基本決策樹學習算法的擴充ID3算法在實際應用中提出了許多問題，多數(shù)問題已有較好的解決方法，ID3也被其作者Quinlan自己擴充為算法。本節(jié)介紹基本決策樹學習算法的問題和解決方法。3.1與訓練例過分吻合問題基本算法在展開樹的分支時，只要達到對訓練例的正確分類，就及時停止?？雌饋磉@個簡單策略是合適的，但在實際應用中可能需要更早地停止決策樹的生長，因為在訓練例含有噪音或訓練例的數(shù)太小不足以成為目標函數(shù)的樣本時，這種簡單策略將會發(fā)生與訓練例過分吻合問題。定義。給定一個假設空間H。若存在兩個假設hH和hH,如果在訓練例上h比X的錯誤少，但在全部實例上X比h的錯誤少，則稱假設hH與訓練例過分吻合。首先我們來看含有隨機誤差（噪音）的訓練例是如何產(chǎn)生過分吻合的決策樹的。在前面的ID3運行實例中，根據(jù)給定的14個無噪音的訓練例，得出決策樹h。若增加一個分類錯誤的訓練例：x15SunnyHotNormalStrong負則ID3將產(chǎn)生比原例更大一點的決策樹h。對于訓練例X】...x15,h完全一致，而h與x5不一致，所以說“在訓練例上h比h，的錯誤少”。但是我們可以預計“在全部實例上X比h的錯誤少”，因為h新增加的節(jié)點純粹是錯誤數(shù)據(jù)的結果。實際上即使訓練例無噪音，仍然可能發(fā)生過分吻合的問題（特別是當與葉節(jié)點對應訓練例的數(shù)量太小時）。這實際上是一種無法完全避免的巧合。避免過分吻合的方法就是比基本算法生成更短的決策樹。這有兩個途徑：在達到對訓練例完全的正確分類之前就停止決策樹的生長。按基本算法進行（可能產(chǎn)生了過分吻合的決策樹），然后對樹進行后剪除。第一種方法看起來更直接，但第二種方法在應用中更成功。不過無論哪一種方法，關鍵在于確定決策樹大小的標準是什么。確定該標準的方法有：使用與訓練例互相獨立的另一組實例，評價后剪除的效果。這是最常用的方法，通常稱為訓練集與驗證集分離方去。即使訓練例的噪音或巧合使學習算法被誤導，獨立的驗證集不太可能顯示相同的隨機波動，故可用來檢查對訓練例的過分吻合。當然驗證例集要足夠大以形成對全部實例有統(tǒng)計意義的樣本。通常將所有能夠得到的數(shù)據(jù)分為三份，兩份用于訓練，一份用于驗證。使用所有能夠得到的數(shù)據(jù)作為訓練例，但用統(tǒng)計方法（如Chi平方測試）估計一個節(jié)點的加入或剪除是否對訓練例以外的數(shù)據(jù)分類有所改進。對訓練例和決策樹編碼復雜度進行度量，當編碼復雜度達到最小時停止樹的增長（最小描述長度原理）。下面我們詳述訓練集與驗證集分離方法的兩個變體，它們都用于對樹進行后剪除。減錯剪除將每一個中間節(jié)點（亦稱為決策節(jié)點）均當作剪除的候選。剪除Node意味著將以它為根的子樹剪除，代之為一個葉節(jié)點，將它標記為與Node相關的那些訓練例的最常見分類（正或負）。節(jié)點剪除的標準是：剪除后的決策樹在驗證例上的分類效果不低于原來的樹。節(jié)點剪除是一個遞推過程，總是選取對驗證例分類的精度改進貢獻最大的節(jié)點先刪除。當進一步剪除有害時（降低對驗證例分類的精度），節(jié)點剪除的過程終止。此方法的關鍵在于將數(shù)據(jù)集分為訓練集和驗證集。它成功的前提是有大量的數(shù)據(jù)。它的主要缺點是，當數(shù)據(jù)太少時，用于訓練的數(shù)據(jù)就更加不足了。下面的方法適合于小數(shù)據(jù)量的情況。（機器學習文獻中還提出了其他更復雜的方法，此處不予詳述）。規(guī)則的后剪除所用的規(guī)則后剪除勺步驟為：用基本算法生成與訓練例盡可能一致的決策樹（容許過分吻合）2．將決策樹轉換為一組規(guī)則（一條路對應一條規(guī)則）。這樣做的好處是：可以對樹進行更細致的剪裁（前面講過的決策樹上的剪除只能以子樹為單位進行）；規(guī)則的剪除易于實現(xiàn)（無需復雜的簿記工作）；易于被人理解。3．對每一條規(guī)則進行剪除（一般化）：刪除規(guī)則的某個前提，使估計精度得以最大改進；再刪除另一個前提，使估計精度得以進一步改進；等等，直到繼續(xù)刪除將降低估計精度為止。4．將剪除后的規(guī)則按估計精度排序，以后在對新例分類時按此順序使用規(guī)則。此方法的關鍵是如何估計精度。在有大量數(shù)據(jù)的情況下，可將數(shù)據(jù)集分為訓練集和驗證集，用驗證集進行估計。使用了一個適合于小數(shù)據(jù)量的方法：基于訓練例自身的性能估計。當然用訓練例進行估計很可能產(chǎn)生偏向于規(guī)則的結果。為克服這一點，采用保守估計。它所采用的具體方法是：計算規(guī)則對其適用的各個訓練例分類的精度a,然后計算這個精度的二項分布的標準差s,最后對給定信任度（95%），取下界（）為該規(guī)則的性能度量pa。在有大量數(shù)據(jù)的情況下，s接近于0，pa接近于a；隨著數(shù)據(jù)量的減少，pa與a的差別將增大。（這種誘導方法雖然在統(tǒng)計學上無根據(jù)，但在實踐中卻很成功。等我們講評價假設的統(tǒng)計方法時再回到的誘導方法）。3．3．2連續(xù)型屬性問題ID3要求離散型的屬性值。對于實際應用中可能遇到的連續(xù)值屬性，解決辦法是動態(tài)地定義將連續(xù)值劃分為幾個區(qū)間的新的離散值屬性（離散化）。這里的兩個關鍵詞是“動態(tài)”和“劃分點”?！皠討B(tài)”是指在ID3算法執(zhí)行中，每當連續(xù)值屬性成為候選屬性時，就要依據(jù)當時當?shù)氐那闆r將它離散化；“劃分點”的確定則仍要根據(jù)最大信息贏取的原則。對于兩個值的離散化，其過程如下：1.設在ID3算法的某一步，相關訓練例集為Es,候選屬性集As中有一個連續(xù)型屬性A。2.將Es的實例按A值升序排列。找到此序列中實例的分類發(fā)生變動的地方，用A值對子何,a+1)表示，說明在A值從a.增加到a+1時實例的正負發(fā)生了變化。(a+ai+1)/2成為A的離散化的一個候選閾值c。2.我們對每一個候選的閾值c定義一個二值離散屬性Ac。對每一個新的離散屬性計算它的信息贏取gain(Es,AJ,然后選取信息贏取最大的屬性Ac為原屬性A離散化的結果。ID3讓新選定的離散化屬性Ac代替連續(xù)型屬性A與AS中其他的離散屬性竟爭當前步驟的最佳分類屬性。針對連續(xù)屬性問題的進一步的課題包括：將連續(xù)屬性離散化為多值離散屬性，幾個連續(xù)屬性用線性組合方法離散化為一個離散屬性，等等。3.3屬性選擇的其他標準信息贏取作為選取最佳分類屬性的標準有一定的道理，但不難指出它的弊病。實際上，這個標準偏向有許多值的屬性。在極端的情況下，在前面關于ID3運行的例子中，若增加一個屬性Date，則它有非常多的值，以至于Date本身就可以確定訓練例的分類。必然地，Date具有最大的信息贏取，從而占據(jù)了根節(jié)點。由此產(chǎn)生的決策樹只有一層，與訓練例完全一致?？上г陬A測未見例時此決策樹毫無用處。因此除了信息贏取，我們還需要別的關于屬性評價的度量。贏取率就是一個這樣的度量。它用屬性A分離數(shù)據(jù)集ES的能力SplitInfo(Es,A)去除信息贏取。對于Date這樣的屬性，由于它分離數(shù)據(jù)集的能力太強，盡管它的信息贏取很高，但它的贏取率卻不高。這就在竟爭中懲罰了Date這樣的屬性。具體定義如下：設屬性A有n個值，將數(shù)據(jù)集Es劃分為n個子集Es1,ES2,?…EsnSplitInfo(Es,A)=-日n(lEsil/|Es|)log2(lEsil/|Es|)GainRatio(Es,A)=Gain(Es,A)/Splitlnfo(Es,A)對于Date這樣的屬性，設Es含m個實例，則Splitlnfo(Es,Date)=log2m；對于兩值的將Es均分的屬性A,SplitInfo(Es,A)=丄。若兩個屬性具有相同的信息贏取，按贏取率競爭，屬性A將排除屬性Date。注意，SplitInfo(Es,A丿實際上是Es對屬性A的熵(前面講過的Entropy(Es)是Es對目標分類的熵)。我們已經(jīng)遇到熵的兩種用法。當然，贏取率度量也不是絕對合理。比如，若Es中幾乎所有實例的A屬性均取同樣的值，SplitInfo(Es,A)將接近于0,從而使A的贏取率極大。實際上所有研究文獻中提出的度量標準都有各自的適應范圍，迄今還沒有在任何情況下均為最佳的度量標準。3.3.4屬性值丟失問題現(xiàn)實問題中，有些實例的某些屬性值(如某些病人的血檢結果)可能沒有給出。處理這個問題的通常辦法是用該屬性在訓練例中最常出現(xiàn)的值充當未見的值，也有更復雜的方法。具體做法有：1?設在ID3計算的某一步相應的實例集為Es，我們需要知道對象xEs的A屬性的值A(x),而這個值沒有給出。這時可用A屬性在Es中最常出現(xiàn)的值充當未見的A(x)。也可用A屬性在Es中分類與x一樣的那些實例中最常出現(xiàn)的值充當未見的A(x)。使用更復雜的方法：為屬性A的各種取值賦以概率(此概率的計算基于當前訓練例中各值的出現(xiàn)頻率)。具有未知A值的實例x按概率值分成大小不等的碎片，沿相應A值的分支向樹的下方分布。實例的碎片將用于計算信息贏取。這個實例碎片法在學習后，還可以用來對屬性值不全的新實例進行分類。(詳情待補充)。3.3.5屬性值的獲取代價問題不同屬性值的獲取代價可以有巨大的差別。例如在病人的情況下，測體溫的代價極小而做b超的代價極大。若考慮到整個學習過程的代價，應盡量先使用代價低的屬性，僅在必要時才使用代價高的屬性。在ID3算法中，這可以通過在屬性選擇時考慮代價因素而實現(xiàn)。例如，不是僅根據(jù)信息贏取，而是根據(jù)信息贏取和屬性代價的比值來選擇最佳屬性。機器學習文獻中提出了許多不同的考慮代價因素的評價屬性的公式。它們的共同特點是，總歸要用在某一領域的實用效果來說明所提出的公式的價值。抽象地爭論那一個公式更好似乎沒有意義。第四章人工神經(jīng)網(wǎng)絡4.1導言神經(jīng)網(wǎng)絡學習為求實數(shù)值，離散值和向量值的目標函數(shù)提供了一種魯棒的近似方法。對于解釋復雜的現(xiàn)實世界中的傳感數(shù)據(jù)這類問題，人工神經(jīng)網(wǎng)絡（ANN）是迄今為止最有效的學習方法之一。例如，本章介紹的BackPropagation算法就已在許多實際應用領域中獲得了成功，如手寫字母識別，語音識別，人臉檢測等。人工神經(jīng)網(wǎng)絡的研究部分地來源于生物學。人們發(fā)現(xiàn)，生物學習系統(tǒng)是極為復雜的神經(jīng)元交互網(wǎng)絡。用最粗略的對比，ANN是一個密集交互的簡單元件的集合，每一個元件接受一組實數(shù)值輸入（它們可能是別的一些元件的輸出），產(chǎn)生一個實數(shù)值輸出（它可能作為別的一些元件的輸入）。為了感受這一對比的含義，讓我們來看一看神經(jīng)生物學的一些事實。人腦含有大約1011個神經(jīng)元，每一個神經(jīng)元平均與104個別的神經(jīng)元連接。神經(jīng)元活動主要是由于和別的神經(jīng)元的連接而觸發(fā)或禁止的。最快的神經(jīng)元開關時間大約為10-3秒，大大低于計算機的10-10秒的開關速度。但是，人能夠以極快的速度作出極為復雜的決策。例如，人大約只需要10-1秒就能認出自己的母親。按照單個神經(jīng)元的開關速度，在10-1秒內(nèi)最多只有幾百次順序的神經(jīng)元觸發(fā)。這就使人猜測，生物學習系統(tǒng)之所以具有極為強大的信息處理能力，可能是因為有高度并行的進程處理分布于許多神經(jīng)元上的信息表示。ANN系統(tǒng)的一個出發(fā)點就是模仿這種基于分布式表達的高度并行計算。大多數(shù)ANN軟件在串行機上運行，效法分布式進程。但有關算法也有在高度并行機或ANN專用硬件上實現(xiàn)的更快的版本。雖然ANN的發(fā)展受到生物學習系統(tǒng)的啟發(fā)，但ANN仍未能模擬生物學習系統(tǒng)中許多復雜的方面；因為我們所討論的ANN的許多性質與生物系統(tǒng)并不一致。例如，在ANN中，元件的輸出是單個的常數(shù)值，而生物神經(jīng)元的輸出是復雜的尖鋒狀時間序列。歷史上，ANN的研究分為兩類。一類是使用ANN研究和模擬生物學習進程；另一類是為了獲得高效的機器學習算法，不管這些算法是否反映了生物進程。我們在這里講的屬于后一類，因此以后不再多談生物模型問題。4.2神經(jīng)網(wǎng)絡表示方法ANN學習的一個成功范例是ALVINN系統(tǒng)，它能夠使用學習過的ANN在高速公路上以正常速度駕駛機動車。車頭上裝有一臺攝象機，為神經(jīng)網(wǎng)絡提供前方場景（像素強度的30*32柵格）。神經(jīng)網(wǎng)絡的輸出是駕車的命令。ANN被訓練大約5分鐘，模仿人的駕駛命令。然后ALVINN系統(tǒng)使用學習過的ANN在高速公路的左車道上，在有其它車輛的情況下，以每小時70英里的速度行使了90英里。圖視網(wǎng)膜3神經(jīng)網(wǎng)絡學習的適用范圍ANN學習非常適合那些訓練數(shù)據(jù)中包含從照相機和麥克風輸入的有噪聲，復雜傳感數(shù)據(jù)的問題學習。它適合具有如下特征問題的學習：事例被用多個屬性-值對表示：要學習的目標函數(shù)是定義在能被預先定義的特征矢量描述的事例上。這些輸入屬性既可以是高度相關也是彼此相互獨立。輸入值可以是任意實數(shù)。目標函數(shù)的輸出可以是離散、實數(shù)、或是一些具有離散、實數(shù)值屬性的矢量。訓練例中可能包含錯誤。ANN學習方法對于數(shù)據(jù)中的噪聲是非常魯棒的。能夠接受長的訓練時間。對所學得的目標函數(shù)能夠進行快速評價。方便應用不必對所學得的目標函數(shù)進行深入理解。4.4感知元學習4.4.1感知元的定義有一類ANN系統(tǒng)的基本元件是感知元一個感知元以一組實數(shù)匕x2…,xn）為輸入，計算這組實數(shù)的一個線性組合（使用系數(shù)w’w2…,wn）,若結果大于某閾值-w。，輸出1，否則輸出-1。我們可以用下面的公式表達輸出與輸入的關系：0（X],…,xn）=ifw1x1+w2x2+...+wnxn>-w0%%閾值then1else-1=ifw0+w1x1+w2x2+...+wnxn>0then1else-1=ifwoxo+w1x1+w：x2+…+wnxn>0%%x0為常數(shù)1then1else-1=ifW?x'>0%%改寫為向量的內(nèi)積then1else-1=sign(W?x)%%改寫為向量內(nèi)積的符號函數(shù)感知元的學習就是為線性組合的實數(shù)系數(shù)w.（稱為權，除了w0代表閾值，其余的w.代表輸入x.對感知元輸出的貢獻率）選取適當?shù)闹?，因此相應的搜索空間是n+1維的實數(shù)向量空間H={WIWRn+i}。4.4.2感知元的表達能力感知元可以看成在n維空間上（空間點為（x”x2…,xn））由方程f=0定義的一個超平面（稱為決策曲面）。對于在超平面的某一邊的所有點（學習問題的正例），感知元的輸出為1；對于在超平面的另一邊的所有點（學習問題的負例），感知元的輸出為-1。當然，并非所有學習問題里的正負例都能用一個超平面分開,而可以用超平面分開的正負例集稱為線性可拆分的例子集單個的感知元就能實現(xiàn)AND,OR,NAND（AND）,NOR（OR）等初等布爾函數(shù)。例如令n=2，x1和x2取1（真）和-1（假）值，則用w0=,w1=,w2=構造的感知元就實現(xiàn)了AND函數(shù)，則用w0=w眉,”2=構造的感知元就實現(xiàn)了OR函數(shù)。（問：AND和OR的實現(xiàn)）可惜并非所有布爾函數(shù)均能用單個的感知元實現(xiàn)。例如，XOR函數(shù)就不能用單個的感知元實現(xiàn)。實際上，XOR的輸入點集不是線性可拆分的（有圖），當然無法用單個的感知元實現(xiàn)。但是，任意復雜的布爾函數(shù)均可用兩層的感知元網(wǎng)絡實現(xiàn)首先，上面說過的用單個感知元實現(xiàn)二元AND,OR,NAND（AND）,NOR（OR）布爾函數(shù)的方法可推廣到多元的情況（令w1=w2=^=，并選擇合適的w0值）；其次，任意布爾表達式均能化為某種范式，例如合取范式AND（ORx..）o這樣，我們可以在第一層上設置n個多元OR感知元，每一個感知元接受若干個輸入并產(chǎn)生一個中間輸出；在第二層上設置一個n元AND感知元，接受第一層的n個中間輸出作為自己的輸入，并產(chǎn)生一個最后的輸出。從以上的簡單討論中不難看出，研究單個感知元的意義遠沒有研究感知元的多層網(wǎng)絡的意義大。但是網(wǎng)絡的研究還得從節(jié)點開始。特別地，為了研究多層感知元網(wǎng)絡的學習，我們先要研究單個感知元的學習，即：如何確定權向量，使感知元對給定的每一個訓練例均能輸出正確的或1的值。下面我們講幾個有關的算法。4.4.3算法1一感知元訓練規(guī)則隨機給出初始的權值叫；repeat用感知元對各個訓練例進行分類：對每一個訓練例(XpX2…,x)：設：其目標分類為r,而感知元對它的分類結果為。，用下面的感知元訓練規(guī)則修改各個權值：叫二叫+wi=叫+(t-o)Xj其中為一個小正數(shù)，稱為學習速率until感知元能夠對所有的訓練例進行正確分類可以證明：若訓練例是線性可拆分的且充分小，則在有限