本章開始對學(xué)習(xí)進(jìn)行討論，首先介紹機(jī)器學(xué)習(xí)和解釋歸納范式。決策樹是廣泛應(yīng)用的歸納學(xué)習(xí)方法，由于它們不能很好泛化，預(yù)測能力很差，因此有大約10年的時(shí)間，它們都沒有得到人們的支持。但是如果采用很多樹，就可以消除很多分歧。最終所謂的隨機(jī)森林（或決策林）促使最近這種學(xué)習(xí)方式得以復(fù)興。本章最后闡釋了熵及其與決策樹構(gòu)造的關(guān)系。
教室
10.0 引言
無論是牙科領(lǐng)域還是小提琴演奏領(lǐng)域，人們都能通過學(xué)習(xí)提升專業(yè)技能。牙科學(xué)校的學(xué)生在修復(fù)牙齒方面變得日漸精通；而在紐約市茱莉亞學(xué)校學(xué)習(xí)的小提琴家，經(jīng)過多年的培訓(xùn)，可以演奏出藝術(shù)性更強(qiáng)的莫扎特小提琴協(xié)奏曲。類似地，機(jī)器學(xué)習(xí)也是一個(gè)過程，在這個(gè)過程中，計(jì)算機(jī)通過閱讀訓(xùn)練數(shù)據(jù)提煉意義。在研究早期，我們提出了一個(gè)問題：機(jī)器可以思考嗎？如果發(fā)現(xiàn)計(jì)算機(jī)能夠執(zhí)行學(xué)習(xí)所需的分析推理的算法（超出了第5章中概述的演繹原理的應(yīng)用），那么這將對解決這個(gè)問題大有裨益——因?yàn)榇蠖鄶?shù)人認(rèn)為學(xué)習(xí)是思維的一種重要組成部分。此外，毫無疑問，機(jī)器學(xué)習(xí)有助于克服人類在知識和常識方面的瓶頸，而我們認(rèn)為這些瓶頸會阻礙人類層次人工智能的發(fā)展，因此許多人將機(jī)器學(xué)習(xí)視為人工智能的夢想。
10.1 機(jī)器學(xué)習(xí)：簡要概述
機(jī)器學(xué)習(xí)的根源可以追溯到亞瑟·塞繆爾（Arthur Samuel）。[1] 他在IBM工作了20年（從1949年開始），教計(jì)算機(jī)玩跳棋。他所編寫的程序用的是填鴨式學(xué)習(xí)，即程序?qū)⒂涀∫郧坝螒蛑械暮米叻ā８腥さ氖牵奶逵螒虺绦蛑姓狭瞬呗浴amuel通過訪問人類跳棋選手，獲得了對跳棋的深刻見解，并將其解植入程序中。
- 始終努力保持對棋盤中央的控制。
- 盡可能地跳過對手的棋子。
- 尋求方法成王。
為了能夠增強(qiáng)在某些游戲中的博弈能力，人們會反復(fù)玩這個(gè)游戲。同樣，Samuel也有不同版本的程序互相競爭。博弈的失敗者將從獲勝者那里學(xué)習(xí)并獲得啟發(fā)式（詳見第16章）。
這個(gè)列表絕對不是詳盡無遺的，而是作為討論的一個(gè)切入點(diǎn)。機(jī)器學(xué)習(xí)這個(gè)主題內(nèi)容豐富，即便用整本書，也不一定能夠囊括所有內(nèi)容。我們鼓勵(lì)有興趣的讀者查閱關(guān)于這個(gè)主題的眾多優(yōu)秀文章。[3,4,5]
下面列出了五大機(jī)器學(xué)習(xí)（ML）范例。
（1）神經(jīng)網(wǎng)絡(luò)。
（2）基于案例推理。
（3）遺傳算法。
（4）規(guī)則歸納。
（5）分析學(xué)習(xí)[2] 。
隱喻就是打比方，將兩個(gè)事實(shí)上不同的事物進(jìn)行互相對比，找出共同點(diǎn)。因此，第二個(gè)事物的屬性就可以轉(zhuǎn)移到第一個(gè)事物中。例如：“他像馬一樣吃飯。”
聚焦于人工神經(jīng)網(wǎng)絡(luò)的ML社區(qū)從人腦和神經(jīng)系統(tǒng)的隱喻中獲得靈感，人腦和神經(jīng)系統(tǒng)可能是地球上最具有智慧自然智能的連接。在人工神經(jīng)網(wǎng)絡(luò)（ANN）中，人工神經(jīng)元按照所規(guī)定的拓?fù)浣Y(jié)構(gòu)進(jìn)行鏈接。網(wǎng)絡(luò)的輸入信號通常會導(dǎo)致互聯(lián)強(qiáng)度的變化，最終超過閾值，產(chǎn)生輸出信號。訓(xùn)練集是精心挑選的一組輸入示例，通常用于教授神經(jīng)網(wǎng)絡(luò)某些概念。我們將用第11章一整章來講述這種機(jī)器學(xué)習(xí)方法。
基于案例的推理與人類記憶中真正起作用的部分進(jìn)行類比。這種方法維護(hù)了一個(gè)過去案例或場景的文件，人們有效地將這些案例或場景編入索引，以便即時(shí)訪問。人們還用了現(xiàn)有案例中一些相似性的量度。例如，對于一位抱怨有嚴(yán)重頭痛并表現(xiàn)出失語癥、伴有周邊視力喪失的患者，醫(yī)生可能會回想起類似案例，進(jìn)而診斷為病毒性腦膜炎。施用適當(dāng)?shù)目拱d癇藥物后，患者的最終療效良好。有了處理過的先前案例的文件，醫(yī)生可以在當(dāng)前的案例中更快地做出診斷。當(dāng)然，醫(yī)生還必須通過一些測試排除其他具有相似癥狀但具有非常不同的原因和（或）結(jié)果的疾病。例如，醫(yī)生可以預(yù)約核磁共振MRI來確認(rèn)腦腫脹，并排除腫瘤的存在，抑或通過脊椎抽液排除細(xì)菌性腦膜炎的可能。關(guān)于案例推理的進(jìn)一步討論參見第9章。
在基于遺傳算法的機(jī)器學(xué)習(xí)中，自然進(jìn)化是這種機(jī)器學(xué)習(xí)方法的靈感。19世紀(jì)中葉，達(dá)爾文提出了自然選擇學(xué)說。無論是植物還是動物，只要物種變異產(chǎn)生了生存優(yōu)勢，那么這種變異在下一代中出現(xiàn)的頻率就會更高。例如，在19世紀(jì)初的倫敦，淺色飛蛾比深色飛蛾具有生態(tài)優(yōu)勢。當(dāng)時(shí)在倫敦及其周邊地區(qū)，樺樹盛行，樹的顏色比較淺，這為淺色飛蛾提供了自然偽裝，從而避免了鳥類的捕食。工業(yè)革命開始后，污染變得普遍了。結(jié)果，英國的樹木變得越來越暗，深色飛蛾具有了偽裝優(yōu)勢，它們在飛蛾種群中的比例就上升了。遺傳算法和遺傳程序的內(nèi)容參見第12章。
規(guī)則歸納是依賴于產(chǎn)生式規(guī)則（見第6章）和決策樹（見第7章）的機(jī)器學(xué)習(xí)分支。適用于教機(jī)器人包裝雜貨的一個(gè)產(chǎn)生式規(guī)則是：
IF[物品是冷凍食品]
THEN[在將物品放在購物袋之前，先放置在冷凍袋中][6]
我們很快就會發(fā)現(xiàn)產(chǎn)生式規(guī)則和決策樹之間信息內(nèi)容的相似性。圖10.1描繪了雜貨包裝機(jī)器人決策樹的一部分。
圖10.1 雜貨包裝機(jī)器人決策樹。請注意這與本文中給出的產(chǎn)生式規(guī)則的相似性
規(guī)則歸納的動力來自于啟發(fā)式搜索。在本章中，決策樹得到了廣泛的研究。
10.2 機(jī)器學(xué)習(xí)系統(tǒng)中反饋的作用
假設(shè)有一個(gè)智能體，這個(gè)智能體希望能夠在大聯(lián)盟級別上打棒球。要達(dá)到這個(gè)級別，通常需要15年或更長的培訓(xùn)時(shí)間。盡管規(guī)則極其簡單，但是一個(gè)冗長的學(xué)習(xí)周期：“扔球，抓球，擊球。”
這句話引自1988年由Ron Shelton執(zhí)導(dǎo)的電影《Bull Durham》。
在訓(xùn)練早期，智能體必須了解棒球比賽中的諸多可能狀態(tài)。
（1）我們的團(tuán)隊(duì)是否領(lǐng)先？
（2）如果我處在防守的位置，并且球向我飛來，那么我必須知道現(xiàn)在跑到第一壘的跑壘者速度是不是很快？如果是，那么我必須快點(diǎn)拋球。
（3）對方的投手是否拋出了一個(gè)旋轉(zhuǎn)球（這種球很難擊中！）？如果是，那么也許今天我應(yīng)該假裝生病了。
這個(gè)年輕的智能體所接受的這種類型的反饋是學(xué)習(xí)過程的核心。在機(jī)器學(xué)習(xí)中，有3種反饋：監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)。
使用監(jiān)督學(xué)習(xí)的方式學(xué)習(xí)功能是最直接、簡單的方法。智能體在做了一些動作后，可以馬上收到適當(dāng)?shù)姆答仭＠纾?dāng)一位敏捷的跑壘者給他一個(gè)滾地球時(shí)，如果他要花點(diǎn)時(shí)間將球傳給第一壘，那么在這些情況下，在幾分鐘之內(nèi)，他就會得到提醒，加快速度。第11章介紹了神經(jīng)網(wǎng)絡(luò)使用監(jiān)督學(xué)習(xí)來學(xué)習(xí)布爾函數(shù)的方法。我們給網(wǎng)絡(luò)提供了一個(gè)列表，其中列出了每種可能輸入的正確輸出。
在無監(jiān)督的學(xué)習(xí)過程中，培訓(xùn)期間沒有提供具體的反饋。但是，如果要學(xué)習(xí)，那么智能體必須收到一些反饋。假設(shè)智能體進(jìn)攻失利，例如他沒有擊中壘，但是他的防守截然不同——他成功地實(shí)現(xiàn)了兩個(gè)撲接，并截獲了一個(gè)全壘打。這是一場比分接近的比賽，他所在的隊(duì)贏了。比賽后，隊(duì)友們向他祝賀，他由此得出結(jié)論：好的防守也是值得贊賞的。
在強(qiáng)化學(xué)習(xí)過程中，沒有老師為智能體提供正確的答案。事實(shí)上，智能體甚至不能提前知道行動的后果。為了進(jìn)一步將問題復(fù)雜化，假設(shè)即使智能體知道行動的影響，但是也不知道影響有多大，因此智能體必須通過試錯(cuò)法來學(xué)習(xí)。由于獎(jiǎng)勵(lì)被推遲，智能體很難確定行動效果的好壞。試圖使用中指平衡傘（沒打開的）的人都明白強(qiáng)化學(xué)習(xí)的基礎(chǔ)，如圖10.2所示。
圖10.2 平衡傘，需要在x-y平面上進(jìn)行小幅度的移動以保持傘的平衡
如果傘向左傾斜，那么你要向左大幅度移動，不久你會發(fā)現(xiàn)這是矯枉過正。讓我們回到棒球智能體的例子。假設(shè)他是一名投手，當(dāng)對方打出了一個(gè)全壘打時(shí)，智能體傾向于將棒球投擲給對方的擊球手。當(dāng)對方的投手朝他的腿投出一個(gè)時(shí)速約145千米的快球時(shí)，幾局過后，他需要將酸痛的膝蓋骨與可能過度激進(jìn)的打法聯(lián)系起來。這里我們將討論嚴(yán)格限制在監(jiān)督學(xué)習(xí)中。在巴拉德（Ballard）的著作中[7]，你可以找到關(guān)于非監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)的極好討論。
通過監(jiān)督學(xué)習(xí)，你可以看到一組有序?qū)Γ?/p>
我們將這組有序?qū)ΨQ為訓(xùn)練集。其中
是輸入的n維空間向量，即
是這個(gè)函數(shù)在
處的值，也就是學(xué)習(xí)到的值。函數(shù)f將每個(gè)輸入向量映射到正確的輸出響應(yīng)。一般說來，在m維的空間中
，每個(gè)分量tk(k = 1,…, m) 都來自一個(gè)事先規(guī)定的集合，例如整數(shù)集、實(shí)數(shù)集等（輸入集和輸出集可能有所不同）。
10.3 歸納學(xué)習(xí)
歸納學(xué)習(xí)中的任務(wù)是找到最接近真實(shí)函數(shù)f ()的函數(shù)h。我們將h稱為f ()的假設(shè)。學(xué)習(xí)算法認(rèn)為假設(shè)空間H是近似正確函數(shù)f ()的一個(gè)函數(shù)集。在這個(gè)學(xué)習(xí)中，目標(biāo)是對于訓(xùn)練集中的所有點(diǎn)找到與f一致的h。人們將這種嘗試稱為曲線擬合，如圖10.3所示。
圖10.3 如果h在所有點(diǎn)上都與f符合，則認(rèn)為h與f是一致的
在圖10.4中，有3種不同的假設(shè)。乍一看，h3似乎是最好的假設(shè)。但是，我們要記住學(xué)習(xí)的目的（這很重要），即學(xué)習(xí)不是為了讓智能體在訓(xùn)練集上表現(xiàn)得完美，而是要讓智能體在驗(yàn)證集上表現(xiàn)良好。
圖10.4 3種不同的假設(shè)。注意，由于只有h3通過了所有的6個(gè)點(diǎn)，因此只有h3與f一致
驗(yàn)證集是測試智能體程序的示例集。如果智能體真正學(xué)到了一些概念，那么它不應(yīng)該只是記住輸入和輸出的對應(yīng)關(guān)系，而是應(yīng)該獲得概括能力，例如對它還沒有遇到過的輸入做出適當(dāng)?shù)捻憫?yīng)。通常來說，在訓(xùn)練集上表現(xiàn)完美的假設(shè)是過度訓(xùn)練了，不能很好地概括概念。實(shí)現(xiàn)概括能力的一種方法是交替訓(xùn)練和驗(yàn)證，并應(yīng)注意，在驗(yàn)證期間，智能體的學(xué)習(xí)機(jī)制應(yīng)該是關(guān)閉的。當(dāng)驗(yàn)證錯(cuò)誤最小化而不是訓(xùn)練錯(cuò)誤最小化時(shí)，訓(xùn)練終止。在第11章中，我們將深度解析這種訓(xùn)練的方法。最后再說一下棒球智能體。如果他真的學(xué)到了進(jìn)行棒球比賽的方法，那么即使首次遇到某種比賽情況，也應(yīng)該做出合理的響應(yīng)，例如首次遇到一場比賽有三人出局的三殺。
再次參考圖10.4（c）。這個(gè)函數(shù)經(jīng)過了所有的6個(gè)點(diǎn)。我們可以使用拉格朗日插值法找到具有這個(gè)屬性的許多其他函數(shù)，例如階數(shù)為7、8、9的多項(xiàng)式等。在學(xué)習(xí)領(lǐng)域（機(jī)器和人類學(xué)習(xí)）中，一個(gè)指導(dǎo)原則是，當(dāng)對同一個(gè)觀察到的現(xiàn)象存在多個(gè)解釋時(shí)，選擇最簡單的解釋才是明智的。這個(gè)原則就是所謂的奧卡姆剃刀（Occam’s Razor）原則。以下是這個(gè)原則的一些例子。
（1）在遙遠(yuǎn)的天空中，看見一條細(xì)小明亮的光線移動。解釋一，一架飛機(jī)從附近機(jī)場起飛或準(zhǔn)備著陸。解釋二，一顆星星離開了它的星系，正準(zhǔn)備進(jìn)入我們的星系。解釋一是比較可取的一個(gè)。
（2）你在圣誕節(jié)早晨醒來，看到了窗外街道上的雪——你昨晚睡覺的時(shí)候，這些雪不在那里。解釋一，因?yàn)槟憬衲甑谋憩F(xiàn)非常好，圣誕老人委托精靈將雪從北極帶到你附近。解釋二，你睡覺時(shí)下雪了。解釋二更有可能。
（3）幾年前，一個(gè)九月的早晨，你經(jīng)過布萊克街和曼哈頓第六大道時(shí)，看到了數(shù)千名紐約人離開城市市區(qū)向北走。解釋一，地鐵有電氣故障，列車沒有運(yùn)行。解釋二，恐怖分子劫持了兩架飛機(jī)，撞入世界貿(mào)易中心。解釋一更有可能，但不幸的是，正確的是解釋二。
大多數(shù)科學(xué)家都同意，當(dāng)有兩個(gè)理論來解釋同樣的現(xiàn)象時(shí)，更簡單的理論相對較好。但是，正如我們所知，這并不總是能保證正確。這可能只是一個(gè)更好的探索起點(diǎn)，直到發(fā)現(xiàn)新證據(jù)。
2001年某個(gè)星期二上午，其中一位作者（SL）約會時(shí)遲到了，未能聽到早晨的新聞播報(bào)。
還有一種特性適用于學(xué)習(xí)方法，它們要么歸為懶惰（lazy），要么歸為急切（eager）。懶惰的學(xué)習(xí)者被認(rèn)為是懶惰的，因?yàn)槠渫七t了超過訓(xùn)練數(shù)據(jù)外的概括，直到新的查詢出現(xiàn)。懶惰的學(xué)習(xí)者從不做出任何努力壓縮數(shù)據(jù)，結(jié)果，當(dāng)模型被調(diào)用時(shí)，所有的數(shù)據(jù)都可用。這與急切的學(xué)習(xí)者不同，急切的學(xué)習(xí)者在出現(xiàn)新詢問時(shí)，已經(jīng)抽象出可以應(yīng)用的一般規(guī)則。但是這樣一來，訓(xùn)練數(shù)據(jù)本身不會被保留。一般來說，訓(xùn)練懶惰的學(xué)習(xí)者更快，但是使用它們需要花更多時(shí)間。急切的學(xué)習(xí)者堅(jiān)持單一的假設(shè)，因此比起懶惰的學(xué)習(xí)者相對更不靈活。
基于案例的推理（見第9章）被歸為懶惰的學(xué)習(xí)者。在這種情況下，優(yōu)點(diǎn)是我們可用整個(gè)案例，因此這可能具有更廣泛的適用性。相反，神經(jīng)網(wǎng)絡(luò)被歸類為急切的學(xué)習(xí)者。在反向傳播網(wǎng)絡(luò)（BPN）中，網(wǎng)絡(luò)學(xué)習(xí)的是權(quán)重，并且我們認(rèn)為權(quán)重是訓(xùn)練數(shù)據(jù)的壓縮版本。為了將BPN應(yīng)用于新的樣本，你需要簡單地將新查詢作為輸入應(yīng)用到網(wǎng)絡(luò)中，但是先前用于訓(xùn)練網(wǎng)絡(luò)的數(shù)據(jù)就檢索不到了。
10.4 利用決策樹進(jìn)行學(xué)習(xí)
對于概念學(xué)習(xí)，決策樹是被廣泛使用的歸納方法。決策樹中的節(jié)點(diǎn)對應(yīng)于關(guān)于某些屬性所做出的查詢。從節(jié)點(diǎn)發(fā)出的分支表示假定的屬性值，如圖10.5所示。
圖10.5 描述了其中一位作者（SL）對意大利面食偏好的決策樹
任何熟悉意大利餐館的人都會很快發(fā)現(xiàn)，意大利面有許多形狀和大小。
這棵樹可能用于將意大利面實(shí)例分為兩個(gè)類——SL喜歡的類和SL不喜歡的類。查詢總是從樹的根節(jié)點(diǎn)開始，終止于葉節(jié)點(diǎn)，在葉節(jié)點(diǎn)中我們找到了類標(biāo)簽。考慮以下意大利面食清單。
（1）Spaghetti and Meatballs——紅醬肉丸意大利面。
（2）Spaghetti Arrabbiata——紅醬意大利面。
（3）Linguine calm red sauce Vongole——蛤蜊紅醬扁意面。
（4）Linguine calm white sauce Vongole——蛤蜊白醬扁意面。
（5）伏特加粗紋通心面。
如圖10.5所示，為了從這個(gè)清單中對意大利面和肉丸進(jìn)行分類，我們從根節(jié)點(diǎn)開始。這道菜的醬汁是紅色的，所以我們選擇這棵樹的左分支。根的左子樹問：這道菜“含”有肉嗎？這當(dāng)然含肉。這棵樹就將Spaghetti and Meatballs歸類為SL喜歡的意大利面。試使用相同的決策樹追蹤其他4個(gè)實(shí)例。你將會注意到，所有5種面食食譜都分為兩個(gè)不同的類別。
第一類——SL喜歡的意大利面食，包含了實(shí)例1、4和5。
第二類——SL不喜歡的意大利面食，包含了實(shí)例2和3。
免責(zé)聲明——其中一位作者（SL）選擇了這些屬性值，僅作為教學(xué)之用。SL在曼哈頓下城紐約市的“小意大利”長大，不幸的是（對于他的腰圍而言），他喜歡每種面食！事實(shí)上，他品嘗了最喜歡的兩家餐館的大部分菜肴，這兩家餐館分別是位于漢斯特街189號的普利亞和位于“小意大利”邁寶瑞街164號的達(dá)尼科。
如圖10.5所示，從決策樹根節(jié)點(diǎn)開始到葉節(jié)點(diǎn)結(jié)束的任何路徑，表示的是路徑上屬性值的合取（AND）。例如，到達(dá)Spaghetti Arrabbiata分類的路徑是（醬汁= 紅色）∧（肉=否）。SL所喜歡的意大利面菜肴的概念對應(yīng)于所有合取項(xiàng)的析取（OR），這些合取項(xiàng)是沿著路徑到達(dá)一個(gè)回答為是（Yes）的節(jié)點(diǎn)。在例子中，我們有：[（醬汁=紅色）∧（肉=是）]∨[（醬汁=白色）∧（海鮮=否）]∨[（醬汁=粉紅色）]。
10.5 適用于決策樹的問題
能夠有效使用決策樹進(jìn)行學(xué)習(xí)的一些問題的特征如下。
（1）屬性應(yīng)該只有少量幾個(gè)值，例如醬汁=紅色、白色或粉紅色；實(shí)例用一組屬性值表示，例如實(shí)例=意粉和肉丸。我們?yōu)橐恍傩再x予某個(gè)值，例如醬汁是紅色的，是否配有肉=是。
（2）一般來說，目標(biāo)函數(shù)只有少量的幾個(gè)離散值。在意大利面食的例子中，值為是（Yes）和否（No）。
（3）訓(xùn)練數(shù)據(jù)中可能存在錯(cuò)誤。當(dāng)在屬性值中或是在實(shí)例分類中出現(xiàn)錯(cuò)誤的情況下，決策樹的表現(xiàn)依然優(yōu)秀（可將此與第11章中神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的魯棒性進(jìn)行對比）。
這些是理想條件。通過參考這一領(lǐng)域的文獻(xiàn)，你可以學(xué)到許多規(guī)避這些局限性的途徑。
在訓(xùn)練數(shù)據(jù)過程中，可能會出現(xiàn)屬性值缺失的情況。例如，假設(shè)決策樹的用戶知道Spaghetti Arrabbiata不含肉類，這個(gè)屬性也就缺失了。
許多現(xiàn)實(shí)世界的問題滿足了上一列表所施加的約束。在醫(yī)療應(yīng)用中，屬性對應(yīng)于可見的癥狀或患者的描述（皮膚顏色=黃色、鼻子=流涕、出現(xiàn)頭痛）或測試結(jié)果（體溫升高、血壓或血糖水平高、心臟酶異常）醫(yī)療應(yīng)用中的目標(biāo)函數(shù)可能表明存在某種疾病或病癥：病人出現(xiàn)花粉癥、肝炎或最近修復(fù)的心臟瓣膜有點(diǎn)問題。
決策樹廣泛應(yīng)用于醫(yī)療行業(yè)。
在金融領(lǐng)域，從信用卡價(jià)值決定到房地產(chǎn)投資的有利條件，也都應(yīng)用了決策樹。商業(yè)界中的一個(gè)基本應(yīng)用是期權(quán)交易。期權(quán)是一種合約，賦予個(gè)人以給定價(jià)格或在特定日期買賣某些資產(chǎn)（例如股票）的權(quán)利。
10.6 熵
熵量化了存在于樣本集合中的均勻性。為了簡化討論，假設(shè)待學(xué)習(xí)的概念在本質(zhì)上是二元的——例如，一個(gè)人是否喜歡面食。給定集合S，相對于這個(gè)二元分類，S的熵為
{-:-}熵= -p(+) log2 p(+)-p(-) log2 p(-)
其中，p（+）表示喜歡的部分，即喜歡面食；p（-）表示不喜歡的部分。在熵的討論中，對數(shù)總是以2為底，即使在分類不是二元的情況下也是如此。
圖10.5中的決策樹描述了意大利面的首選項(xiàng)。假設(shè)有一個(gè)包含4種意大利面食的集合，某人都喜歡吃這4種面——我們將這種情況表示為[4（+），0（-）]，則這個(gè)集合中的熵為
熵[4（+），0（-）] = -4 / 4×log2（4/4）- 0/4×log2（0/4）
= -1×log2（1）- 0×log2（0）
= -1×0 - 0× 0
= 0
如果某人喜歡其中的兩種面食，不喜歡另外兩種面食，那么有
熵[2（+），2（-）] = -2/4×log2（2/4）-2/4×log2（2/4）
= -1/2×（-1）-1/2×（-1）
= 1/2 -（-1/2）
= 1
我們觀察到，當(dāng)所有成員屬于同一組時(shí)，該集合的熵為0。這個(gè)0值表示在這個(gè)集合中沒有雜質(zhì)，這個(gè)示例中所有的成員均為真。在第二個(gè)例子中，有一半的成員是正值，一半的成員是負(fù)值，這種情況下熵的值最大，為1。在二元分類中，集合熵的范圍是從0到1，如圖10.6所示。
圖10.6 二元分類中，熵函數(shù)隨著正樣本
比例的變化在區(qū)間[0,1]上變化
集合的熵可以視為確定所選項(xiàng)來自哪個(gè)類所需的比特?cái)?shù)目。例如，對于集合[2（+），2（-）]，需要一個(gè)比特來指定從哪個(gè)類別中選出哪個(gè)項(xiàng)，其中1的意思是某人喜歡該項(xiàng)，0表示某人不喜歡該項(xiàng)。相反，當(dāng)某人喜歡所有的項(xiàng)時(shí)，在集合[4（+），0（-）]，不需要比特來標(biāo)記項(xiàng)，因此某人喜歡所有的項(xiàng)時(shí)，熵為0。
10.7 使用ID3構(gòu)建決策樹
1986年，昆蘭（Quinlan）開發(fā)了ID3算法。ID3是決策樹學(xué)習(xí)中應(yīng)用最廣泛的算法之一，它是以自上而下的方式構(gòu)建決策樹的。它首先搜索盡可能地將訓(xùn)練集分成相等子集的那個(gè)屬性。如果要成功地應(yīng)用決策樹，必須了解它們是如何構(gòu)建的。在意大利面食的例子中，有三個(gè)屬性——醬汁色、含肉、含海鮮，見表10.1。
表10.1 用于決策樹學(xué)習(xí)的數(shù)據(jù)
其中有3種不同的屬性，因此，對于哪種屬性首先出現(xiàn)有不同的選擇，如圖10.7所示。
如果根據(jù)該屬性的值可以將樣本一分為二，那么就認(rèn)為這個(gè)屬性是好的，例如，對應(yīng)于某個(gè)屬性值所有的實(shí)例都為正，對于其他屬性值所有的實(shí)例都為負(fù)。相反，如果某個(gè)屬性不包含具有判別力的屬性值，則認(rèn)為這個(gè)屬性是沒用的。在示例中，好的屬性意味著對于每個(gè)屬性值，喜歡的面食和不喜歡的面食數(shù)量相等。
ID3使用信息增益來對屬性進(jìn)行位置安排。如果該屬性能獲得最大預(yù)期的熵減，那么這個(gè)屬性的位置更接近于根節(jié)點(diǎn)。如圖10.7所示，為了確定3棵子樹中最先選擇哪個(gè)子樹，ID3對所示的每棵子樹先計(jì)算出其平均信息，然后選擇能夠產(chǎn)生信息增益最大的那棵子樹。其中，屬性A產(chǎn)生的信息增益，指的是利用A對集合S進(jìn)行分割，從而導(dǎo)致熵的減少。
式中，v是屬性A采用的一個(gè)值。這個(gè)公式對v的所有值對應(yīng)的Sv（具有值v的S子集）進(jìn)行求和。如圖10.8～圖10.10所示，理解ID3必須完成的計(jì)算。
圖10.7 決策樹可以按照3種屬性中的任意一種開始。在（a）中，在醬汁顏色是紅色的情況下，作者喜歡兩種意大利面，不喜歡3種意大利面。對于其他方框，也可以進(jìn)行類似的解釋
仔細(xì)觀察圖10.8～圖10.10，很明顯，由于“含有海鮮”的屬性，其相關(guān)的信息增益為0.32，是對應(yīng)3種屬性中最大的值，因此ID3選擇“含有海鮮”的屬性作為決策樹中的第一種屬性。
接下來，ID3必須在圖10.11繪制的兩棵樹之間進(jìn)行選擇。
一旦選擇了第二個(gè)屬性，接下來在需要的時(shí)候就會應(yīng)用未選擇的屬性。本書要求你在練習(xí)中完成這些計(jì)算。
圖10.8 如果首先選擇醬汁顏色，那么信息增益等于0.29
圖10.9 如果首先選擇含有肉類的屬性，那么信息增益等于0.17
圖10.10 如果首先選擇含有海鮮的屬性，那么信息增益等于0.32
圖10.11 ID3必須選擇哪個(gè)屬性作為第二個(gè)屬性——是醬汁顏色，還是含有肉類？
本文截選自《人工智能》（第2版）
