機(jī)器學(xué)習(xí)講義

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

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

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

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

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