人工智能第7章 機(jī)器學(xué)習(xí)課件

第7章機(jī)器學(xué)習(xí)

學(xué)習(xí)是人類獲取知識(shí)的重要途徑和自然智能的重要標(biāo)志，機(jī)器學(xué)習(xí)則是機(jī)器獲取知識(shí)的重要途徑和人工智能的重要標(biāo)志。7.1機(jī)器學(xué)習(xí)的基本概念7.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)7.1.2機(jī)器學(xué)習(xí)的發(fā)展過程7.1.3學(xué)習(xí)系統(tǒng)7.1.4機(jī)器學(xué)習(xí)的主要策略7.2記憶學(xué)習(xí)7.3歸納學(xué)習(xí)7.4解釋學(xué)習(xí)7.5神經(jīng)學(xué)習(xí)1第7章機(jī)器學(xué)習(xí)學(xué)習(xí)是人類獲取知識(shí)的重要途徑和自然7.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)1.學(xué)習(xí)的概念代表性觀點(diǎn)(1)西蒙（Simon,1983）：學(xué)習(xí)就是系統(tǒng)中的適應(yīng)性變化，這種變化使系統(tǒng)在重復(fù)同樣工作或類似工作時(shí)，能夠做得更好。(2)明斯基（Minsky,1985）：學(xué)習(xí)是在人們頭腦里（心理內(nèi)部）有用的變化。(3)邁克爾斯基（Michalski,1986）：學(xué)習(xí)是對(duì)經(jīng)歷描述的建立和修改。一般性解釋：學(xué)習(xí)是一個(gè)有特定目的知識(shí)獲取和能力增長(zhǎng)過程，其內(nèi)在行為是獲得知識(shí)、積累經(jīng)驗(yàn)、發(fā)現(xiàn)規(guī)律等，其外部表現(xiàn)是改進(jìn)性能、適應(yīng)環(huán)境、實(shí)現(xiàn)自我完善等。

27.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)代表性觀點(diǎn)27.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)2.機(jī)器學(xué)習(xí)的概念一般性解釋機(jī)器學(xué)習(xí)就是讓機(jī)器（計(jì)算機(jī)）來模擬和實(shí)現(xiàn)人類的學(xué)習(xí)功能。主要研究?jī)?nèi)容認(rèn)知模擬

主要目的是要通過對(duì)人類學(xué)習(xí)機(jī)理的研究和模擬，從根本上解決機(jī)器學(xué)習(xí)方面存在的種種問題。理論性分析主要目的是要從理論上探索各種可能的學(xué)習(xí)方法，并建立起獨(dú)立于具體應(yīng)用領(lǐng)域的學(xué)習(xí)算法。面向任務(wù)的研究

主要目的是要根據(jù)特定任務(wù)的要求，建立相應(yīng)的學(xué)習(xí)系統(tǒng)。

37.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)一般性解釋3神經(jīng)元模型研究20世紀(jì)50年代中期到60年代初期，也被稱為機(jī)器學(xué)習(xí)的熱烈時(shí)期，最具有代表性的工作是羅森勃拉特1957年提出的感知器模型。符號(hào)概念獲取20世紀(jì)60年代中期到70年代初期。其主要研究目標(biāo)是模擬人類的概念學(xué)習(xí)過程。這一階段神經(jīng)學(xué)習(xí)落入低谷，稱為機(jī)器學(xué)習(xí)的冷靜時(shí)期。知識(shí)強(qiáng)化學(xué)習(xí)20世紀(jì)70年代中期到80年代初期。人們開始把機(jī)器學(xué)習(xí)與各種實(shí)際應(yīng)用相結(jié)合，尤其是專家系統(tǒng)在知識(shí)獲取方面的需求，也有人稱這一階段為機(jī)器學(xué)習(xí)的復(fù)興時(shí)期。連接學(xué)習(xí)和混合型學(xué)習(xí)20世紀(jì)80年代中期至今。把符號(hào)學(xué)習(xí)和連接學(xué)習(xí)結(jié)合起來的混合型學(xué)習(xí)系統(tǒng)研究已成為機(jī)器學(xué)習(xí)研究的一個(gè)新的熱點(diǎn)。7.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)3.機(jī)器學(xué)習(xí)的發(fā)展過程4神經(jīng)元模型研究7.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)47.1.3學(xué)習(xí)系統(tǒng)環(huán)境學(xué)習(xí)環(huán)節(jié)知識(shí)庫(kù)執(zhí)行環(huán)節(jié)環(huán)境

是學(xué)習(xí)系統(tǒng)所感知到的外界信息集合，也是學(xué)習(xí)系統(tǒng)的外界來源。信息的水平（一般化程度）和質(zhì)量（正確性）對(duì)學(xué)習(xí)系統(tǒng)影響較大。學(xué)習(xí)環(huán)節(jié)

對(duì)環(huán)境提供的信息進(jìn)行整理、分析歸納或類比，形成知識(shí)，并將其放入知識(shí)庫(kù)。知識(shí)庫(kù)

存儲(chǔ)經(jīng)過加工后的信息（即知識(shí)）。其表示形式是否合適非常重要。執(zhí)行環(huán)節(jié)

根據(jù)知識(shí)庫(kù)去執(zhí)行一系列任務(wù)，并將執(zhí)行結(jié)果或執(zhí)行過程中獲得的信息反饋給學(xué)習(xí)環(huán)節(jié)。學(xué)習(xí)環(huán)節(jié)再利用反饋信息對(duì)知識(shí)進(jìn)行評(píng)價(jià)，進(jìn)一步改善執(zhí)行環(huán)節(jié)的行為。57.1.3學(xué)習(xí)系統(tǒng)環(huán)境學(xué)習(xí)環(huán)節(jié)知識(shí)庫(kù)執(zhí)行環(huán)節(jié)環(huán)境7.1.4機(jī)器學(xué)習(xí)的主要策略按學(xué)習(xí)策略來分類即按學(xué)習(xí)中所使用的推理方法來分，可分為記憶學(xué)習(xí)、傳授學(xué)習(xí)、演繹學(xué)習(xí)、歸納學(xué)習(xí)等。按應(yīng)用領(lǐng)域分類專家系統(tǒng)學(xué)習(xí)、機(jī)器人學(xué)習(xí)、自然語(yǔ)言理解學(xué)習(xí)等。按對(duì)人類學(xué)習(xí)的模擬方式

符號(hào)主義學(xué)習(xí)、連接主義學(xué)習(xí)等。67.1.4機(jī)器學(xué)習(xí)的主要策略按學(xué)習(xí)策略來分類6第7章機(jī)器學(xué)習(xí)7.1機(jī)器學(xué)習(xí)的基本概念7.2記憶學(xué)習(xí)7.3歸納學(xué)習(xí)7.4解釋學(xué)習(xí)7.5神經(jīng)學(xué)習(xí)7第7章機(jī)器學(xué)習(xí)7.1機(jī)器學(xué)習(xí)的基本概念77.2記憶學(xué)習(xí)概念記憶學(xué)習(xí)(Rotelearning)也叫死記硬背學(xué)習(xí)，是一種最基本的學(xué)習(xí)過程，它沒有足夠的能力獨(dú)立完成智能學(xué)習(xí)，但對(duì)學(xué)習(xí)系統(tǒng)來說都是十分重要的一個(gè)組成部分，原因是任何學(xué)習(xí)系統(tǒng)都必須記住它們所獲取的知識(shí)，以便將來使用。記憶學(xué)習(xí)的基本過程是：執(zhí)行元素每解決一個(gè)問題，系統(tǒng)就記住這個(gè)問題和它的解，當(dāng)以后再遇到此類問題時(shí)，系統(tǒng)就不必重新進(jìn)行計(jì)算，而可以直接找出原來的解去使用

87.2記憶學(xué)習(xí)記憶學(xué)習(xí)(Rotelearnin若把執(zhí)行元素比作一個(gè)函數(shù)f，由環(huán)境得到的輸入模式記為(x1,x2,…,xn)，由該輸入模式經(jīng)F計(jì)算后得到的輸出模式記為(y1,y2,…,ym)，則機(jī)械學(xué)習(xí)系統(tǒng)就是要把這一輸入輸出模式對(duì)：[(x1,x2,…,xn)，(y1,y2,…,ym)]保存在知識(shí)庫(kù)中，當(dāng)以后再需要計(jì)算f(x1,x2,…,xn)時(shí)，就可以直接從存儲(chǔ)器把(y1,y2,…,ym)檢索出來，而不需要再重新進(jìn)行計(jì)算。(x1,x2,…,xn)(y1,y2,…,yn)[(x1,x2,…,xn),(y1,y2,…,yn)]f存儲(chǔ)輸入模式執(zhí)行函數(shù)輸出模式輸入輸出模式對(duì)機(jī)械式學(xué)習(xí)的學(xué)習(xí)模型7.2記憶學(xué)習(xí)模型9若把執(zhí)行元素比作一個(gè)函數(shù)f，由環(huán)境得到的輸入模式記7.3歸納學(xué)習(xí)

歸納學(xué)習(xí)是指以歸納推理為基礎(chǔ)的學(xué)習(xí)，其任務(wù)是要從關(guān)于某個(gè)概念的一系列已知的正例和反例中歸納出一個(gè)一般的概念描述。7.3.1示例學(xué)習(xí)是歸納學(xué)習(xí)的一種特例。它給學(xué)習(xí)者提供某一概念的一組正例和反例，學(xué)習(xí)者歸納出一個(gè)總的概念描述，并使這個(gè)描述適合于所有的正例，排除所有的反例。7.3.2決策樹學(xué)習(xí)

是一種以示例為基礎(chǔ)的歸納學(xué)習(xí)方法，也是目前最流行的歸納學(xué)習(xí)方法之一。在現(xiàn)有的各種決策樹學(xué)習(xí)算法中，影響較大的是ID3算法。本節(jié)主要討論決策樹的概念和決策樹學(xué)習(xí)的ID3算法。107.3歸納學(xué)習(xí)歸納學(xué)習(xí)是指以歸納推理為基礎(chǔ)的學(xué)按例子的來源分類①例子來源于教師的示例學(xué)習(xí)②例子來源于學(xué)習(xí)者本身的示例學(xué)習(xí)學(xué)習(xí)者明確知道自己的狀態(tài)，但完全不清楚所要獲取的概念。③例子來源于學(xué)習(xí)者以外的外部環(huán)境的示例學(xué)習(xí)例子的產(chǎn)生是隨機(jī)的。按例子的類型分類①僅利用正例的示例學(xué)習(xí)這種學(xué)習(xí)方法會(huì)使推出的概念的外延擴(kuò)大化。②利用正例和反例的示例學(xué)習(xí)這是示例學(xué)習(xí)的一種典型方式，它用正例用來產(chǎn)生概念，用反例用來防止概念外延的擴(kuò)大。7.3.1示例學(xué)習(xí)1.示例學(xué)習(xí)的類型11按例子的來源分類7.3.1示例學(xué)習(xí)11示例空間規(guī)則空間驗(yàn)證過程解釋過程

示例空間

是我們向系統(tǒng)提供的示教例子的集合。研究問題：例子質(zhì)量，搜索方法。解釋過程

是從搜索到的示例中抽象出一般性的知識(shí)的歸納過程。解釋方法：常量轉(zhuǎn)換為變量，去掉條件，增加選擇，曲線擬合等。規(guī)則空間

是事務(wù)所具有的各種規(guī)律的集合。研究問題：對(duì)空間的要求，搜索方法驗(yàn)證過程

是要從示例空間中選擇新的示例，對(duì)剛剛歸納出的規(guī)則做進(jìn)一步的驗(yàn)證和修改。7.3.1示例學(xué)習(xí)2.示例學(xué)習(xí)的模型12示例空間規(guī)則空間驗(yàn)證過程解釋過程示例空間7.3.1是指解釋過程從具體示例形成一般性知識(shí)所采用的歸納推理方法。最常用的解釋方法有以下4種：(1)把常量轉(zhuǎn)換為變量把示例中的常量換成變量而得到一個(gè)一般性的規(guī)則。(2)去掉條件把示例中的某些無關(guān)的子條件舍去。(3)增加選擇在析取條件中增加一個(gè)新的析取項(xiàng)。常用的增加析取項(xiàng)的方法有前件析取法和內(nèi)部析取法兩種(4)曲線擬合對(duì)數(shù)值問題的歸納可采用最小二乘法進(jìn)行曲線擬合7.3.1示例學(xué)習(xí)3.示例學(xué)習(xí)的解釋方法(1/5)13是指解釋過程從具體示例形成一般性知識(shí)所采用的歸納推理例：假設(shè)例子空間中有以下兩個(gè)關(guān)于撲克牌中“同花”概念的示例：

示例1：花色(c1，梅花)∧花色(c2，梅花)∧花色(c3，梅花)∧花色(c4，梅花)∧花色(c5，梅花)→同花(c1,c2,c3,c4,c5)示例2：花色(c1，紅桃)∧花色(c2，紅桃)∧花色(c3，紅桃)∧花色(c4，紅桃)∧花色(c5，紅桃)→同花(c1,c2,c3,c4,c5)其中，示例1表示5張梅花牌是同花，示例2表示5張紅桃牌是同花。解釋過程：(1)把常量化為變量

例如，對(duì)這兩個(gè)示例，只要把“梅花”和“紅桃”用變量x代換，就可得到如下一般性的規(guī)則：規(guī)則1：花色(c1，x)∧花色(c2，x)∧花色(c3，x)∧花色(c4，x)∧花色(c5，x)→同花(c1,c2,c3,c4,c5)7.3.1示例學(xué)習(xí)3.示例學(xué)習(xí)的解釋方法(2/5)14例：假設(shè)例子空間中有以下兩個(gè)關(guān)于撲克牌中“同花”概念(2)去掉條件

這種方法是要把示例中的某些無關(guān)的子條件舍去。例如，有如下示例：示例3：花色(c1,紅桃)∧點(diǎn)數(shù)(c1，2)∧花色(c2,紅桃)∧點(diǎn)數(shù)(c2，3)∧花色(c3,紅桃)∧點(diǎn)數(shù)(c3，4)∧花色(c4,紅桃)∧點(diǎn)數(shù)(c4，5)∧花色(c5,紅桃)∧點(diǎn)數(shù)(c5，6)→同花(c1,c2,c3,c4,c5)7.3.1示例學(xué)習(xí)3.示例學(xué)習(xí)的解釋方法(3/5)為了學(xué)習(xí)同花的概念，除了需要把常量變?yōu)樽兞客猓€需要把與花色無關(guān)的“點(diǎn)數(shù)”子條件舍去。這樣也可得到上述規(guī)則1：規(guī)則1：花色(c1，x)∧花色(c2，x)∧花色(c3，x)∧花色(c4，x)∧花色(c5，x)→同花(c1,c2,c3,c4,c5)15(2)去掉條件7.3.1示例學(xué)習(xí)為了學(xué)習(xí)7.3.1示例學(xué)習(xí)3.示例學(xué)習(xí)的解釋方法(4/5)

(3)增加選擇在析取條件中增加一個(gè)新的析取項(xiàng)。包括前件析取法和內(nèi)部析取法。前件析取法：是通過對(duì)示例的前件的析取來形成知識(shí)的。例如：

示例4：點(diǎn)數(shù)(c1,J)→臉(c1)

示例5：點(diǎn)數(shù)(c1,Q)→臉(c1)

示例6：點(diǎn)數(shù)(c1,K)→臉(c1)將各示例的前件進(jìn)行析取，就可得到所要求的規(guī)則：規(guī)則2：點(diǎn)數(shù)(c1,J)∨點(diǎn)數(shù)(c1,Q)∨點(diǎn)數(shù)(c1,K)→臉(c1)內(nèi)部析取法：是在示例的表示中使用集合與集合的成員關(guān)系來形成知識(shí)的。例如，有如下關(guān)于“臉牌”的示例：

示例7：點(diǎn)數(shù)c1∈{J}→臉(c1)

示例8：點(diǎn)數(shù)c1∈{Q}→臉(c1)

示例9：點(diǎn)數(shù)c1∈{K}→臉(c1)用內(nèi)部析取法，可得到如下規(guī)則：

規(guī)則3：點(diǎn)數(shù)(c1)∈{J,Q,K}→臉(c1)167.3.1示例學(xué)習(xí)(3)增加選擇16

(4)曲線擬合

對(duì)數(shù)值問題的歸納可采用曲線擬合法。假設(shè)示例空間中的每個(gè)示例(x,y,z)都是輸入x,y與輸出z之間關(guān)系的三元組。例如，有下3個(gè)示例：

示例10：(0,2,7)示例11：(6,-1,10)示例12：(-1,-5,-16)用最小二乘法進(jìn)行曲線擬合，可得x,y,z之間關(guān)系的規(guī)則如下：規(guī)則4：z=2x+3y+1說明：在上述前三種方法中，方法(1)是把常量轉(zhuǎn)換為變量；方法(2)是去掉合取項(xiàng)（約束條件）；方法(3)是增加析取項(xiàng)。它們都是要擴(kuò)大條件的適用范圍。從歸納速度上看，方法(1)的歸納速度快，但容易出錯(cuò)；方法(2)歸納速度慢，但不容易出錯(cuò)。因此，在使用方法(1)時(shí)應(yīng)特別小心。例如：對(duì)示例4、示例5及示例6，若使用方法(1),則會(huì)歸納出如下的錯(cuò)誤規(guī)則：規(guī)則5：（錯(cuò)誤）點(diǎn)數(shù)(c1,x)→臉(c1)它說明，歸納過程是很容易出錯(cuò)的。7.3.1示例學(xué)習(xí)3.示例學(xué)習(xí)的解釋方法(5/5)17(4)曲線擬合7.3.1示例學(xué)習(xí)17是一種由節(jié)點(diǎn)和邊構(gòu)成的用來描述分類過程的層次數(shù)據(jù)結(jié)構(gòu)。該樹的根接點(diǎn)表示分類的開始，葉節(jié)點(diǎn)表示一個(gè)實(shí)例的結(jié)束，中間節(jié)點(diǎn)表示相應(yīng)實(shí)例中的某一屬性，而邊則代表某一屬性可能的屬性值。在決策樹中，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑都代表一個(gè)具體的實(shí)例，并且同一路徑上的所有屬性之間為合取關(guān)系，不同路徑（即一個(gè)屬性的不同屬性值）之間為析取關(guān)系。決策樹的分類過程就是從這棵樹的根接點(diǎn)開始，按照給定的事例的屬性值去測(cè)試對(duì)應(yīng)的樹枝，并依次下移，直至到達(dá)某個(gè)葉節(jié)點(diǎn)為止。圖7.4是一個(gè)非常簡(jiǎn)單的用來描述對(duì)鳥類進(jìn)行分類的決策樹。在該圖中：根節(jié)點(diǎn)包含各種鳥類，葉節(jié)點(diǎn)是所能識(shí)別的各種鳥的名稱；中間節(jié)點(diǎn)是鳥的一些屬性，邊是鳥的某一屬性的屬性值；從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑都描述了一種鳥，它包括該種鳥的一些屬性及相應(yīng)的屬性值。7.3.2決策樹學(xué)習(xí)1.決策樹的概念(1/2)18是一種由節(jié)點(diǎn)和邊構(gòu)成的用來描述分類過程的層次數(shù)據(jù)結(jié)構(gòu)鳥類家養(yǎng)可能是和平鴿可能是信天翁游泳可能是企鵝可能是鴕鳥圖7.4一個(gè)簡(jiǎn)單的鳥類識(shí)別決策樹會(huì)飛不會(huì)飛是不是會(huì)不會(huì)決策樹還可以表示成規(guī)則的形式。上圖的決策樹可表示為如下規(guī)則集：IF鳥類會(huì)飛AND是家養(yǎng)的THEN該鳥類是和平鴿IF鳥類會(huì)飛AND不是家養(yǎng)的THEN該鳥類是信天翁IF鳥類不會(huì)飛AND會(huì)游泳THEN該鳥類是企鵝IF鳥類不會(huì)飛AND不會(huì)游泳THEN該鳥類是鴕鳥決策樹學(xué)習(xí)過程實(shí)際上是一個(gè)構(gòu)造決策樹的過程。當(dāng)學(xué)習(xí)完成后，就可以利用這棵決策樹對(duì)未知事物進(jìn)行分類。7.3.2決策樹學(xué)習(xí)1.決策樹的概念(2/2)19鳥類家養(yǎng)可能是和平鴿可能是信天翁游泳可能是企鵝可能是鴕鳥圖77.3.2決策樹學(xué)習(xí)2.ID3算法(1/11)

D3算法是昆蘭（J.R.Quinlan）于1979年提出的一種以信息熵（entropy）的下降速度作為屬性選擇標(biāo)準(zhǔn)的一種學(xué)習(xí)算法。其輸入是一個(gè)用來描述各種已知類別的例子集，學(xué)習(xí)結(jié)果是一棵用于進(jìn)行分類的決策樹。主要討論：ID3算法的數(shù)學(xué)基礎(chǔ)ID3算法機(jī)器舉例207.3.2決策樹學(xué)習(xí)D3算法是昆蘭（J.R.Q7.3.2決策樹學(xué)習(xí)2.ID3算法(2/11)

(1)ID3算法的數(shù)學(xué)基礎(chǔ)下面討論信息熵和條件熵的數(shù)學(xué)概念

信息熵信息熵是對(duì)信息源整體不確定性的度量。假設(shè)X為信源，xi為X所發(fā)出的單個(gè)信息，P(xi)為X發(fā)出xi的概率，則信息熵可定義為：其中，k為信源X發(fā)出的所有可能的信息類型，對(duì)數(shù)可以是以各種數(shù)為底的對(duì)數(shù)，在ID3算法中，我們?nèi)∫?為底的對(duì)數(shù)。信息熵反應(yīng)的是信源每發(fā)出一個(gè)信息所提供的平均信息量。217.3.2決策樹學(xué)習(xí)(1)ID3算法的數(shù)學(xué)基條件熵條件熵是收信者在收到信息后對(duì)信息源不確定性的度量。若假設(shè)信源為X，收信者收到的信息為Y，P(xi/yj)為當(dāng)Y為yj時(shí)X為xi的條件概率，則條件熵可定義為：它表示收信者收到Y(jié)后對(duì)X不確定性的估計(jì)。

7.3.2決策樹學(xué)習(xí)2.ID3算法(3/11)22條件熵7.3.2決策樹學(xué)習(xí)227.3.2決策樹學(xué)習(xí)2.ID3算法(4/11)(2)ID3算法及舉例ID3算法的學(xué)習(xí)過程：首先以整個(gè)例子集作為決策樹的根節(jié)點(diǎn)S，并計(jì)算S關(guān)于每個(gè)屬性的期望熵（即條件熵）；然后選擇能使S的期望熵為最小的一個(gè)屬性對(duì)根節(jié)點(diǎn)進(jìn)行分裂，得到根節(jié)點(diǎn)的一層子節(jié)點(diǎn)；接著再用同樣的方法對(duì)這些子節(jié)點(diǎn)進(jìn)行分裂，直至所有葉節(jié)點(diǎn)的熵值都下降為0為止。這時(shí)，就可得到一棵與訓(xùn)練例子集對(duì)應(yīng)的熵為0的決策樹，即ID3算法學(xué)習(xí)過程所得到的最終決策樹。該樹中每一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑，都代表了一個(gè)分類過程，即決策過程。237.3.2決策樹學(xué)習(xí)(2)ID3算法及舉例23例7.1

用ID3算法完成下述學(xué)生選課的例子假設(shè)將決策y分為以下３類：y1：必修AIy2：選修AIy3：不修AI做出這些決策的依據(jù)有以下3個(gè)屬性：x1：學(xué)歷層次x1=1研究生，x1=2本科x2：專業(yè)類別x2=1電信類，x2=2機(jī)電類x3：學(xué)習(xí)基礎(chǔ)x3=1修過AI，x3=2未修AI表7.1給出了一個(gè)關(guān)于選課決策的訓(xùn)練例子集S。

7.3.2決策樹學(xué)習(xí)2.ID3算法(5/11)24例7.1用ID3算法完成下述學(xué)生選課的例子7.3.表7-1關(guān)于選課決策的訓(xùn)練例子集在該表中，訓(xùn)練例子集S的大小為８。ID3算法是依據(jù)這些訓(xùn)練例子，以S為根節(jié)點(diǎn)，按照信息熵下降最大的原則來構(gòu)造決策樹的。序號(hào)屬性值決策方案yix1x2x31111y32112y13121y34122y25211y36212y27221y38222y37.3.2決策樹學(xué)習(xí)2.ID3算法(6/11)25表7-1關(guān)于選課決策的訓(xùn)練例子集序號(hào)屬性值決策方案x1x2解：首先對(duì)根節(jié)點(diǎn)，其信息熵為：其中，３為可選的決策方案數(shù)，且有

P(y1)=1/8，P(y2)=2/8，P(y3)=5/8即有：H(S)=-(1/8)log2(1/8)-(2/8)log2(2/8)-(5/8)log2(5/8)=1.2988按照ID3算法，需要選擇一個(gè)能使S的期望熵為最小的一個(gè)屬性對(duì)根節(jié)點(diǎn)進(jìn)行擴(kuò)展，因此我們需要先計(jì)算S關(guān)于每個(gè)屬性的條件熵：其中，t為屬性xi的屬性值，St為xi=t時(shí)的例子集，|S|和|Si|分別是例子集S和Si的大小。7.3.2決策樹學(xué)習(xí)2.ID3算法(7/11)26解：首先對(duì)根節(jié)點(diǎn)，其信息熵為：7.3.2決策樹學(xué)下面先計(jì)算S關(guān)于屬性x1的條件熵：在表7-1中，x1的屬性值可以為1或2。當(dāng)x1=1時(shí)，t=1時(shí)，有：S1={1，2，3，4}當(dāng)x1=2時(shí)，t=2時(shí)，有：S2={5，6，7，8}其中，S1和S2中的數(shù)字均為例子集S中的各個(gè)例子的序號(hào)，且有|S|=8，|S1|=|S2|=4。由S1可知：

Ps1(y1)=1/4,Ps1(y2)=1/4,Ps1(y3)=2/4則有：H(S1)=-Ps1(y1)log2Ps1(y1)-Ps1(y2)log2Ps1(y2)-Ps1(y3)log2Ps1(y3)=-(1/4)log2(1/4)-(1/4)log2(1/4)-(2/4)log2(2/4)=1.57.3.2決策樹學(xué)習(xí)2.ID3算法(8/11)27下面先計(jì)算S關(guān)于屬性x1的條件熵：7.3.2決策再由S2可知：Ps2(y1)=0/4,Ps2(y2)=1/4,Ps2(y3)=3/4則有：H(S2)=–Ps2(y2)log2Ps2(y2)-Ps2(y3)log2Ps2(y3)=-(1/4)log2(1/4)-(3/4)log2(3/4)=0.8113將H(S1)和H(S2)代入條件熵公式，有：H(S/x1)=(|S1|/|S|)H(S1)+(|S2|/|S|)H(S2)=(4/8)﹡1.5+(4/8)﹡0.8113=1.1557同樣道理，可以求得：H(S/x2)=1.1557H(S/x3)=0.75可見，應(yīng)該選擇屬性x3對(duì)根節(jié)點(diǎn)進(jìn)行擴(kuò)展。用x3對(duì)S擴(kuò)展后所得到的得到部分決策樹如圖7.5所示。7.3.2決策樹學(xué)習(xí)2.ID3算法(9/10)28再由S2可知：7.3.2決策樹學(xué)習(xí)28Sx3=1,y3x3=2,x1,x2圖7.5部分決策樹x3=1x3=2在該樹中，節(jié)點(diǎn)“x3=1,y3”表示當(dāng)x3的屬性值為1時(shí)，得到?jīng)Q策方案y3。由于y3已是具體的決策方案，故該節(jié)點(diǎn)的信息熵為0，已經(jīng)為葉節(jié)點(diǎn)。節(jié)點(diǎn)“x3=2，x1,x2”的含義是“當(dāng)x3的屬性值為2時(shí)，還需要考慮屬性x1,x2”，它是一個(gè)中間節(jié)點(diǎn)，還需要繼續(xù)擴(kuò)展。至于節(jié)點(diǎn)“x3=2，x1,x2”，其擴(kuò)展方法與上面的過程類似。通過計(jì)算可知，該節(jié)點(diǎn)對(duì)屬性x1和x2，其條件熵均為1。由于它對(duì)屬性x1和x2的條件熵相同，因此可以先選擇x1，也可以先選擇x2，本例是先選擇x2。依此進(jìn)行下去，可得到如圖7.6所示的最終的決策樹。在該決策樹中，各節(jié)點(diǎn)的含義與圖7.5類似。

7.3.2決策樹學(xué)習(xí)2.ID3算法(10/11)29Sx3=1,y3x3=2,x1,x2圖7.Sx3=1,y3x3=2,x1,x2圖7.6最終的決策樹x3=1x3=21x2=1,x1x2=2,x1x1=1,y1x1=2,y2x1=1,y2x1=2,y3x2=1x2=2x1=1x1=2x1=2x1=17.3.2決策樹學(xué)習(xí)2.ID3算法(11/11)30Sx3=1,y3x3=2,x1,x2圖7.6第7章機(jī)器學(xué)習(xí)7.1機(jī)器學(xué)習(xí)的基本概念7.2記憶學(xué)習(xí)7.3歸納學(xué)習(xí)7.4解釋學(xué)習(xí)

解釋學(xué)習(xí)(Explanation-BasedLearning)是一種分析學(xué)習(xí)方法。它是在領(lǐng)域知識(shí)的指導(dǎo)下，通過對(duì)單個(gè)問題求解例子的分析來進(jìn)行學(xué)習(xí)的。

7.1.1解釋學(xué)習(xí)概述7.1.2解釋的基本原理7.1.3解釋學(xué)習(xí)的基本過程7.1.4領(lǐng)域知識(shí)的完善性7.5神經(jīng)學(xué)習(xí)31第7章機(jī)器學(xué)習(xí)7.1機(jī)器學(xué)習(xí)的基本概念31解釋學(xué)習(xí)涉及三個(gè)不同的空間：例子空間，概念空間和概念描述空間。三個(gè)空間及它們之間的關(guān)系如圖7.7所示。C1不可操作的可操作的D1D2?I1?I2?I3概念描述空間概念空間例子空間

概念描述空間是所有概念描述的集合，其中的概念描述可分為兩大類，一類是可操作的，另一類是不可操作的。所謂可操作是指一個(gè)概念描述能有效的用于識(shí)別相應(yīng)概念的例子。否則是不可操作的。解釋學(xué)習(xí)的任務(wù)就是要把不可操作的概念描述轉(zhuǎn)化為可操作的概念描述。概念空間是學(xué)習(xí)過程能夠描述的所有概念的集合

例子空間是用于問題求解的例子集合

7.4.1解釋學(xué)習(xí)概述解釋學(xué)習(xí)的空間描述32解釋學(xué)習(xí)涉及三個(gè)不同的空間：例子空間，概念空間和概念模型：KBEXL

為學(xué)習(xí)系統(tǒng)KB

為領(lǐng)域知識(shí)庫(kù)，它是不同概念描述之間進(jìn)行轉(zhuǎn)換所使用的規(guī)則集合PS

為執(zhí)行系統(tǒng)

D1

是輸入的概念描述，一般為不可操作的；D2

是學(xué)習(xí)結(jié)束時(shí)輸出的概念描述，它是可操作的。執(zhí)行過程：先由EXL接受輸入的概念描述D1，然后再根據(jù)KB中的知識(shí)對(duì)D1進(jìn)行不同描述的轉(zhuǎn)換，并由PS對(duì)每個(gè)轉(zhuǎn)換結(jié)果進(jìn)行測(cè)試，直到被PS所接受，即為可操作的概念描述D2為止；最后輸出D2。結(jié)果是否可操作PSD2NYEXL概念描述的轉(zhuǎn)換KBD17.4.1解釋學(xué)習(xí)概述解釋學(xué)習(xí)的模型33模型：KBEXL為學(xué)習(xí)系統(tǒng)結(jié)果是否PSD本節(jié)主要討論米切爾等人提出的解釋泛化學(xué)習(xí)方法。其基本思想：先對(duì)某一情況建立一個(gè)解釋結(jié)構(gòu)，然后在對(duì)此解釋結(jié)構(gòu)進(jìn)行概括，獲取一般性控制知識(shí)。其一般性描述為：

已知：目標(biāo)概念GC(GoalConcept)；訓(xùn)練實(shí)例TE(TrainingExample)；領(lǐng)域理論DT(DomainTheory)；操作性標(biāo)準(zhǔn)OC(OperationalityCriterion)。求出：滿足OC的關(guān)于GC的充分概念描述。其中：目標(biāo)概念GC是要學(xué)習(xí)概念的描述；訓(xùn)練實(shí)例TE是為學(xué)習(xí)系統(tǒng)提供的一個(gè)實(shí)例；領(lǐng)域理論DT是相關(guān)領(lǐng)域的事實(shí)和規(guī)則，即為背景知識(shí)；操作性標(biāo)準(zhǔn)OC

用于指導(dǎo)學(xué)習(xí)系統(tǒng)對(duì)用來描述目標(biāo)的概念進(jìn)行舍取等的控制性知識(shí)。7.4.3解釋學(xué)習(xí)的基本原理34本節(jié)主要討論米切爾等人提出的解釋泛化學(xué)習(xí)方法。7.4

其任務(wù)是要證明提供給系統(tǒng)的訓(xùn)練實(shí)例為什么是目標(biāo)概念的一個(gè)實(shí)例。為此，系統(tǒng)應(yīng)從目標(biāo)開始反向推理，根據(jù)知識(shí)庫(kù)中已有的事實(shí)和規(guī)則分解目標(biāo)，直到求解結(jié)束。一旦得到解，便完成了該問題的證明，同時(shí)也獲得了一個(gè)解釋結(jié)構(gòu)。

例如，假設(shè)要學(xué)習(xí)的目標(biāo)是“一個(gè)物體x可以安全地放置在另一個(gè)物體y的上面”。即

目標(biāo)概念：Safe-to-Stack(x,y)

訓(xùn)練實(shí)例（是一些描述物體obj1與obj2的事實(shí)）：On(obj1,obj2)物體1在物體2的上面Isa(obj1,book)物體1是書Isa(obj2,table)物體2是桌子Volume(obj1,1)物體1的體積是1Density(obj1,0.1)物體1的密度是0.17.4.3解釋學(xué)習(xí)的基本過程1.產(chǎn)生解釋結(jié)構(gòu)(1/3)35其任務(wù)是要證明提供給系統(tǒng)的訓(xùn)練實(shí)例為什么是目標(biāo)概念的領(lǐng)域知識(shí)是把一個(gè)物體安全地放置在另一個(gè)物體上面的準(zhǔn)則：﹁Fragile(y)→Safe-to-stack(x,y)如果y不是易碎的，則x可以安全地放到y(tǒng)的上面Lighter(x,y)→Safe-to-stack(x,y)如果x比y輕，則x可以安全地放到y(tǒng)的上面Volume(p,v)∧Density(p,d)∧Product(v,d,w)→Weight(p,w)如果p的體積是v、密度是d、v乘以d的積是w，則p的重量是wIs-a(p,table)→Weight(p,5)如果p是桌子，則p的重量是5Weight(p1,w1)∧Weight(p2,w2)∧Smaller(w1,w2)→Lighter(p1,p2)

如果p1的重量是w1、p2的重量是w2、w1比w2小，則p1比p2輕

其證明過程是一個(gè)由目標(biāo)引導(dǎo)的逆向推理，最終得到的解釋樹就是該例的解釋結(jié)構(gòu)（如下圖）。7.4.3解釋學(xué)習(xí)的基本過程1.產(chǎn)生解釋結(jié)構(gòu)(2/3)36領(lǐng)域知識(shí)是把一個(gè)物體安全地放置在另一個(gè)物體上面Safe-to-Stack(obj1,obj2)Lighter(obj1,obj2)Weight(obj1,0.1)Weight(obj2,5)Smaller(0.1,5)Is-a(obj2,table)Volume(obj1,1)Density(obj1,0.1)Product(1,0.1,0.1)7.4.3解釋學(xué)習(xí)的基本過程1.產(chǎn)生解釋結(jié)構(gòu)(3/3)37Safe-to-Stack(obj1,obj2)Light

這一步的主要任務(wù)是對(duì)上一步得到的解釋結(jié)構(gòu)進(jìn)行概括化處理，從而得到關(guān)于目標(biāo)概念的一般性知識(shí)。進(jìn)行概括化處理的常用方法是把常量轉(zhuǎn)換為變量，即把某些具體數(shù)據(jù)換成變量，并略去某些不重要的信息，只保留求解所必須的那些關(guān)鍵信息即可。對(duì)上圖的解釋結(jié)構(gòu)進(jìn)行概括化處理以后所得到的概括化解釋結(jié)構(gòu)如下：

7.4.3解釋學(xué)習(xí)的基本過程2.獲取一般性控制知識(shí)(1/2)38這一步的主要任務(wù)是對(duì)上一步得到的解釋結(jié)構(gòu)進(jìn)行概括化Safe-to-Stack(O1,O2)Lighter(O1,O2)Weight(O1,w1)Weight(O2,5)Smaller(w1,5)Is-a(O2,table)Volume(O1,v1)Density(O1,d1)Product(v1,d1,w1)

將該解釋結(jié)構(gòu)中所有的葉節(jié)點(diǎn)的合取作為前件，頂點(diǎn)的目標(biāo)概念做為后件，略去解釋結(jié)構(gòu)的中間部件，就可得到概括化的一般性知識(shí)：Volume(O1,v1)∧Density(O1,d1)∧Product(v1,d1,w1)∧Is-a(O2,table)∧Smaller(w1,5)→Safe-to-stack(O1,O2)7.4.3解釋學(xué)習(xí)的基本過程2.獲取一般性控制知識(shí)(2/2)39Safe-to-Stack(O1,O2)Lighter(O第7章機(jī)器學(xué)習(xí)7.1機(jī)器學(xué)習(xí)的基本概念7.2記憶學(xué)習(xí)7.3歸納學(xué)習(xí)7.4解釋學(xué)習(xí)7.5神經(jīng)學(xué)習(xí)神經(jīng)學(xué)習(xí)是一種基于人工神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)方法。

7.1.1神經(jīng)學(xué)習(xí)的概念7.1.2感知器學(xué)習(xí)7.1.3BP網(wǎng)絡(luò)學(xué)習(xí)7.1.4Hopfield網(wǎng)絡(luò)學(xué)習(xí)40第7章機(jī)器學(xué)習(xí)7.1機(jī)器學(xué)習(xí)的基本概念40神經(jīng)生理學(xué)研究表明，人腦的神經(jīng)元既是學(xué)習(xí)的基本單位，同是也是記憶的基本單位。目前，關(guān)于人腦學(xué)習(xí)和記憶機(jī)制的研究有兩大學(xué)派：化學(xué)學(xué)派：認(rèn)為人腦經(jīng)學(xué)習(xí)所獲得的信息是記錄在某些生物大分子之上的。例如，蛋白質(zhì)、核糖核酸、神經(jīng)遞質(zhì)，就像遺傳信息是記錄在DNA（脫氧核糖核酸）上一樣。突觸修正學(xué)派：認(rèn)為人腦學(xué)習(xí)所獲得的信息是分布在神經(jīng)元之間的突觸連接上的。按照突觸修正學(xué)派的觀點(diǎn)，人腦的學(xué)習(xí)和記憶過程實(shí)際上是一個(gè)在訓(xùn)練中完成的突觸連接權(quán)值的修正和穩(wěn)定過程。其中，學(xué)習(xí)表現(xiàn)為突觸連接權(quán)值的修正，記憶則表現(xiàn)為突觸連接權(quán)值的穩(wěn)定。突觸修正假說已成為人工神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)和記憶機(jī)制研究的心理學(xué)基礎(chǔ)，與此對(duì)應(yīng)的權(quán)值修正學(xué)派也一直是人工神經(jīng)網(wǎng)絡(luò)研究的主流學(xué)派。突觸修正學(xué)派認(rèn)為，人工神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過程就是一個(gè)不斷調(diào)整網(wǎng)絡(luò)連接權(quán)值的過程。

7.5.1神經(jīng)學(xué)習(xí)的概念1.神經(jīng)學(xué)習(xí)的心理學(xué)基礎(chǔ)41神經(jīng)生理學(xué)研究表明，人腦的神經(jīng)元既是學(xué)習(xí)的基本單位，所謂學(xué)習(xí)規(guī)則可簡(jiǎn)單地理解為學(xué)習(xí)過程中聯(lián)結(jié)權(quán)值的調(diào)整規(guī)則。按照學(xué)習(xí)規(guī)則，神經(jīng)學(xué)習(xí)可分為Hebb學(xué)習(xí)、糾錯(cuò)學(xué)習(xí)、競(jìng)爭(zhēng)學(xué)習(xí)及隨機(jī)學(xué)習(xí)等。(1)Hebb學(xué)習(xí)基本思想：如果神經(jīng)網(wǎng)絡(luò)中某一神經(jīng)元同另一直接與它連接的神經(jīng)元同時(shí)處于興奮狀態(tài)，那么這兩個(gè)神經(jīng)元之間的連接強(qiáng)度將得到加強(qiáng)，反之應(yīng)該減弱。Hebb學(xué)習(xí)對(duì)連接權(quán)值的調(diào)整可表示為：其中，wij(t+1)表示對(duì)時(shí)刻t的權(quán)值修正一次后所得到的新的權(quán)值；η是一正常量，也稱為學(xué)習(xí)因子，它取決于每次權(quán)值的修正量；xi(t)、xj(t)分別表示t時(shí)刻第i個(gè)和第j個(gè)神經(jīng)元的狀態(tài)。Hebb學(xué)習(xí)規(guī)則在人工神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)中的影響比較大，但不符合生物機(jī)理。例如習(xí)慣化。

7.5.1神經(jīng)學(xué)習(xí)的概念2.神經(jīng)學(xué)習(xí)規(guī)則(1/3)42所謂學(xué)習(xí)規(guī)則可簡(jiǎn)單地理解為學(xué)習(xí)過程中聯(lián)結(jié)權(quán)值的調(diào)整規(guī)(2)糾錯(cuò)學(xué)習(xí)是一種有導(dǎo)師的學(xué)習(xí)過程，其基本思想：利用神經(jīng)網(wǎng)絡(luò)的期望輸出與實(shí)際輸出之間的偏差作為連接權(quán)值調(diào)整的參考，并最終減少這種偏差。

最基本的誤差修正規(guī)則為：連接權(quán)值的變化與神經(jīng)元希望輸出和實(shí)際輸出之差成正比。其聯(lián)結(jié)權(quán)值的計(jì)算公式為：其中，wij(t)表示時(shí)刻t的權(quán)值；wij(t+1)表示對(duì)時(shí)刻t的權(quán)值修正一次后所得到的新的權(quán)值；η是一正常量，也稱為學(xué)習(xí)因子；yj(t)為神經(jīng)元j的實(shí)際輸出;dj(t)為神經(jīng)元j的希望輸出；dj(t)-yj(t)表示神經(jīng)元j的輸出誤差；xi(t)為第i個(gè)神經(jīng)元的輸入7.5.1神經(jīng)學(xué)習(xí)的概念2.神經(jīng)學(xué)習(xí)規(guī)則(2/3)43(2)糾錯(cuò)學(xué)習(xí)7.5.1神經(jīng)學(xué)習(xí)的概念437.5.1神經(jīng)學(xué)習(xí)的概念2.神經(jīng)學(xué)習(xí)規(guī)則(3/3)(3)競(jìng)爭(zhēng)學(xué)習(xí)

基本思想：網(wǎng)絡(luò)中某一組神經(jīng)元相互競(jìng)爭(zhēng)對(duì)外界刺激模式響應(yīng)的權(quán)力，在競(jìng)爭(zhēng)中獲勝的神經(jīng)元，其連接權(quán)會(huì)向著對(duì)這一刺激模式競(jìng)爭(zhēng)更為有利的方向發(fā)展。(4)隨機(jī)學(xué)習(xí)基本思想：結(jié)合隨機(jī)過程、概率和能量（函數(shù)）等概念來調(diào)整網(wǎng)絡(luò)的變量，從而使網(wǎng)絡(luò)的目標(biāo)函數(shù)達(dá)到最大（或最?。?。他不僅可以接受能量函數(shù)減少（性能得到改善）的變化，而且還可以以某種概率分布接受使能量函數(shù)增大（性能變差）的變化。447.5.1神經(jīng)學(xué)習(xí)的概念(3)競(jìng)爭(zhēng)學(xué)習(xí)44單層感知器學(xué)習(xí)實(shí)際上是一種基于糾錯(cuò)學(xué)習(xí)規(guī)則，采用迭代的思想對(duì)連接權(quán)值和閾值進(jìn)行不斷調(diào)整，直到滿足結(jié)束條件為止的學(xué)習(xí)算法。假設(shè)X(k)和W(k)分別表示學(xué)習(xí)算法在第k次迭代時(shí)輸入向量和權(quán)值向量，為方便，把閾值θ作為權(quán)值向量W(k)中的第一個(gè)分量，對(duì)應(yīng)地把“-1”固定地作為輸入向量X(k)中的第一個(gè)分量。即W(k)和X(k)可分別表示如下：X(k)=[-1,x1(k),x2(k),…,xn(k)]W(k)=[θ(k),w1(k),w2(k),…,wn(k)]即x0(k)=-1，w0(k)=θ(k)。單層感知器學(xué)習(xí)是一種有導(dǎo)師學(xué)習(xí)，它需要給出輸入樣本的期望輸出。假設(shè)一個(gè)樣本空間可以被劃分為A、B兩類。其功能函數(shù)的定義為：對(duì)屬于A類輸入樣本，其功能函數(shù)的輸出為+1，否則其輸出為-1。對(duì)應(yīng)地也可將期望輸出定義為：當(dāng)輸入樣本屬于A類時(shí)，其期望輸出為+1，否則為-1。7.5.2感知器學(xué)習(xí)1.單層感知器學(xué)算法習(xí)(1/2)45單層感知器學(xué)習(xí)實(shí)際上是一種基于糾錯(cuò)學(xué)習(xí)規(guī)則，采用迭代單層感知器學(xué)習(xí)算法描述：(1)設(shè)t=0，初始化連接權(quán)和閾值。即給wi(0)(i=1,2,…,n)及θ(0)分別賦予一個(gè)較小的非零隨機(jī)數(shù)，作為初值。其中，wi(0)是第0次迭代時(shí)輸入向量中第i個(gè)輸入的連接權(quán)值；θ(0)是第0次迭代時(shí)輸出節(jié)點(diǎn)的閾值；(2)提供新的樣本輸入xi(t)(i=1,2,…,n)和期望輸出d(t)；(3)計(jì)算網(wǎng)絡(luò)的實(shí)際輸出：(4)若y(t)=1，不需要調(diào)整連接權(quán)值，轉(zhuǎn)(6)。否則，轉(zhuǎn)(5)調(diào)整連接權(quán)值其中，η是一個(gè)增益因子，用于控制修改速度，其值如果太大，會(huì)影響wi(t)的收斂性；如果太小，又會(huì)使wi(t)的收斂速度太慢;(6)判斷是否滿足結(jié)束條件，若滿足，算法結(jié)束；否則，將t值加1，轉(zhuǎn)(2)重新執(zhí)行。這里的結(jié)束條件一般是指wi(t)對(duì)一切樣本均穩(wěn)定不變。

如果輸入的兩類樣本是線性可分的，則該算法就一定會(huì)收斂。否則，該算法將不收斂。7.5.2感知器學(xué)習(xí)1.單層感知器學(xué)算法習(xí)(2/2)46單層感知器學(xué)習(xí)算法描述：7.5.2感知器學(xué)習(xí)46例7.3用單層感知器實(shí)現(xiàn)邏輯“與”運(yùn)算。解：根據(jù)“與”運(yùn)算的邏輯關(guān)系，可將問題轉(zhuǎn)換為：輸入向量：X1=[0,0,1,1]X2=[0,1,0,1]輸出向量：Y=[0,0,0,1]為減少算法的迭代次數(shù)，設(shè)初始連接權(quán)值和閾值取值如下：w1(0)=0.5,w2(0)=0.7,θ(0)=0.6并取增益因子η=0.4。算法的學(xué)習(xí)過程如下：設(shè)兩個(gè)輸入為x1(0)=0和x2(0)=0，其期望輸出為d(0)=0，實(shí)際輸出為：y(0)=f(w1(0)x1(0)+w2(0)x2(0)-θ(0))=f(0.5*0+0.7*0-0.6)=f(-0.6)=0實(shí)際輸出與期望輸出相同，不需要調(diào)節(jié)權(quán)值。7.5.2感知器學(xué)習(xí)2.單層感知器學(xué)的例子(1/4)47例7.3用單層感知器實(shí)現(xiàn)邏輯“與”運(yùn)算。7.5.2再取下一組輸入：x1(0)=0和x2(0)=1，期望輸出d(0)=0，實(shí)際輸出：y(0)=f(w1(0)x1(0)+w2(0)x2(0)-θ(0))=f(0.5*0+0.7*1-0.6)=f(0.1)=1實(shí)際輸出與期望輸出不同，需要調(diào)節(jié)權(quán)值，其調(diào)整如下：

θ(1)=θ(0)+η(d(0)-y(0))*(-1)=0.6+0.4*(0-1)*(-1)=1w1(1)=w1(0)+η(d(0)-y(0))x1(0)=0.5+0.4*(0-1)*0=0.5w2(1)=w2(0)+η(d(0)-y(0))x2(0)=0.7+0.4*(0-1)*1=0.3取下一組輸入：x1(1)=1和x2(1)=0，其期望輸出為d(1)=0，實(shí)際輸出為：y(1)=f(w1(1)x1(1)+w2(1)x2(1)-θ(1))=f(0.5*1+0.3*0-1)=f(-0.51)=0實(shí)際輸出與期望輸出相同，不需要調(diào)節(jié)權(quán)值。7.5.2感知器學(xué)習(xí)2.單層感知器學(xué)的例子(2/4)48再取下一組輸入：x1(0)=0和x2(0)=1，期再取下一組輸入：x1(1)=1和x2(1)=1，其期望輸出為d(1)=1，實(shí)際輸出為：y(1)=f(w1(1)x1(1)+w2(1)x2(1)-θ(1))=f(0.5*1+0.3*1-1)=f(-0.2)=0實(shí)際輸出與期望輸出不同，需要調(diào)節(jié)權(quán)值，其調(diào)整如下：

θ(2)=θ(1)+η(d(1)-y(1))*(-1)=1+0.4*(1-0)*(-1)=0.6w1(2)=w1(1)+η(d(1)-y(1))x1(1)=0.5+0.4*(1-0)*1=0.9w2(2)=w2(1)+η(d(1)-y(1))x2(1)=0.3+0.4*(1-0)*1=0.7取下一組輸入：x1(2)=0和x2(2)=0，其期望輸出為d(2)=0，實(shí)際輸出為：y(2)=f(0.9*0+0.7*0-0.6)=f(-0.6)=0實(shí)際輸出與期望輸出相同，不需要調(diào)節(jié)權(quán)值.7.5.2感知器學(xué)習(xí)2.單層感知器學(xué)的例子(3/4)49再取下一組輸入：x1(1)=1和x2(1)=1，其期再取下一組輸入：x1(2)=0和x2(2)=1，期望輸出為d(2)=0，實(shí)際輸出為：y(2)=f(0.9*0+0.7*1-0.6)=f(0.1)=1實(shí)際輸出與期望輸出不同，需要調(diào)節(jié)權(quán)值，其調(diào)整如下：

θ(3)=θ(2)+η(d(2)-y(2))*(-1)=0.6+0.4*(0-1)*(-1)=1w1(3)=w1(2)+η(d(2)-y(2))x1(2)=0.9+0.4*(0-1)*0=0.9w2(3)=w2(2)+η(d(2)-y(2))x2(2)=0.7+0.4*(0-1)*1=0.3

實(shí)際上，由上一章關(guān)于與運(yùn)算的閾值條件可知，此時(shí)的閾值和連接權(quán)值以滿足結(jié)束條件，算法可以結(jié)束。對(duì)此，可檢驗(yàn)如下：對(duì)輸入：“00”有y=f(0.9*0+0.3*0-1)=f(-1)=0

對(duì)輸入：“01”有y=f(0.9*0+0.3*0.1-1)=f(-0.7)=0

對(duì)輸入：“10”有y=f(0.9*1+0.3*0-1)=f(-0.1)=0

對(duì)輸入：“11”有y=f(0.9*1+0.3*1-1)=f(0.2)=07.5.2感知器學(xué)習(xí)2.單層感知器學(xué)的例子(4/4)50再取下一組輸入：x1(2)=0和x2(2)=1，期望BP網(wǎng)絡(luò)學(xué)習(xí)過程是一個(gè)對(duì)給定訓(xùn)練模式，利用傳播公式，沿著減小誤差的方向不斷調(diào)整網(wǎng)絡(luò)連接權(quán)值和閾值的過程。需要用到以下幾個(gè)符號(hào)：Oi：節(jié)點(diǎn)i的輸出；Ij：接點(diǎn)j的輸入；wij：從節(jié)點(diǎn)i到節(jié)點(diǎn)j的連接權(quán)值；θj：節(jié)點(diǎn)j的閾值；yk：輸出層上節(jié)點(diǎn)k的實(shí)際輸出；dk：輸出層上節(jié)點(diǎn)k的期望輸出。顯然，對(duì)隱含節(jié)點(diǎn)j有：

在BP算法學(xué)習(xí)過程中，可以采用如下公式計(jì)算各輸出節(jié)點(diǎn)的誤差：7.5.3BP網(wǎng)絡(luò)學(xué)習(xí)1.BP算法的傳播公式(1/5)51BP網(wǎng)絡(luò)學(xué)習(xí)過程是一個(gè)對(duì)給定訓(xùn)練模式，利用傳播公式，連接權(quán)值的修改由下式計(jì)算：其中，wjk(t)和wjk(t+1)分別是時(shí)刻t和t+1時(shí)，從節(jié)點(diǎn)j到節(jié)點(diǎn)k的連接權(quán)值；Δwjk是連接權(quán)值的變化量。為了使連接權(quán)值能沿著E的梯度變化方向逐漸改善，網(wǎng)絡(luò)逐漸收斂，BP算法按如下公式計(jì)算Δwjk：

其中，η為增益因子，由下式計(jì)算：7.5.3BP網(wǎng)絡(luò)學(xué)習(xí)1.BP算法的傳播公式(2/5)52連接權(quán)值的修改由下式計(jì)算：7.5.3BP網(wǎng)絡(luò)學(xué)習(xí)52由于故有令局部梯度故有7.5.3BP網(wǎng)絡(luò)學(xué)習(xí)1.BP算法的傳播公式(3/5)53由于7.5.3BP網(wǎng)絡(luò)學(xué)習(xí)53計(jì)算時(shí)，需要區(qū)分節(jié)點(diǎn)k是輸出層上的節(jié)點(diǎn)，還是隱含層上的節(jié)點(diǎn)。如果節(jié)點(diǎn)k是輸出層上的節(jié)點(diǎn)，則有Ok=yk，因此由于所以7.5.3BP網(wǎng)絡(luò)學(xué)習(xí)1.BP算法的傳播公式(4/5)54計(jì)算時(shí)，需要區(qū)分節(jié)點(diǎn)k是輸出層上的節(jié)點(diǎn)，還是隱含層上如果節(jié)點(diǎn)k不是輸出層上的節(jié)點(diǎn)，則它是隱含層上的節(jié)點(diǎn)的，此時(shí)：

其中，是一個(gè)隱函數(shù)求導(dǎo)問題，略去推導(dǎo)過程，其結(jié)果為：

所以這說明，低層節(jié)點(diǎn)的δ值是通過上一層節(jié)點(diǎn)的δ值來計(jì)算的。這樣，我們就可以先計(jì)算出輸出層上的δ值，然后把它返回到較低層上，并計(jì)算出各較低層上節(jié)點(diǎn)的δ值。7.5.3BP網(wǎng)絡(luò)學(xué)習(xí)1.BP算法的傳播公式(5/5)55如果節(jié)點(diǎn)k不是輸出層上的節(jié)點(diǎn)，則它是隱含層上的節(jié)點(diǎn)的(1)初始化網(wǎng)絡(luò)及學(xué)習(xí)參數(shù)，將各節(jié)點(diǎn)的連接權(quán)值、閾值賦予[-1，1]區(qū)間的一個(gè)隨機(jī)數(shù)；(2)提供訓(xùn)練模式，即從訓(xùn)練模式集合中選出一個(gè)訓(xùn)練模式送入網(wǎng)絡(luò)；(3)正向傳播過程，即對(duì)給定輸入模式，計(jì)算輸出模式，并將其與期望模式比較，若有誤差則執(zhí)行(4)，否則返回(2)，提供下一個(gè)訓(xùn)練模式；(4)反向傳播過程，即從輸出層反向計(jì)算到第一隱含層，按以下方式逐層修正各單元的連接權(quán)值：①計(jì)算同一層單元的誤差②按下式修正連接權(quán)值和閾值對(duì)連接權(quán)值，修正公式為：對(duì)閾值，可按照連接權(quán)值的學(xué)習(xí)方式進(jìn)行，只是要把閾值設(shè)想為神經(jīng)元的連接權(quán)值，并假定其輸入信號(hào)總為單位值1即可。反復(fù)執(zhí)行上述修正過程，直到滿足期望的輸出模式為止。(5)返回第(2)步，對(duì)訓(xùn)練模式集中的每一個(gè)訓(xùn)練模式重復(fù)第(2)到第(3)步，直到訓(xùn)練模式集中的每一個(gè)訓(xùn)練模式都滿足期望輸出為止。7.5.3BP網(wǎng)絡(luò)學(xué)習(xí)1.BP網(wǎng)絡(luò)學(xué)習(xí)算法56(1)初始化網(wǎng)絡(luò)及學(xué)習(xí)參數(shù)，將各節(jié)點(diǎn)的連接權(quán)值、閾7.5.4Hopfield網(wǎng)絡(luò)學(xué)習(xí)

Hopfield網(wǎng)絡(luò)學(xué)習(xí)的過程實(shí)際上是一個(gè)從網(wǎng)絡(luò)初始狀態(tài)向其穩(wěn)定狀態(tài)過渡的過程。而網(wǎng)絡(luò)的穩(wěn)定性又是通過能量函數(shù)來描述的。這里主要針對(duì)離散Hopfield網(wǎng)絡(luò)討論其能量函數(shù)和學(xué)習(xí)算法。577.5.4Hopfield網(wǎng)絡(luò)學(xué)習(xí)Hopfiel離散Hopfield網(wǎng)絡(luò)的能量函數(shù)可定義為：式中，n是網(wǎng)絡(luò)中的神經(jīng)元個(gè)數(shù)，wij是第i個(gè)神經(jīng)元和第j個(gè)神經(jīng)元之間的連接權(quán)值，且有wij=wji；vi和vj分別是第i個(gè)神經(jīng)元和第j個(gè)神經(jīng)元的輸出；θi是第i個(gè)神經(jīng)元的閾值?？梢宰C明，當(dāng)一神經(jīng)元k的狀態(tài)由“0”變?yōu)椤?”時(shí)，網(wǎng)絡(luò)能量的變化為：此時(shí)，由于神經(jīng)元k的狀態(tài)由“0”變?yōu)椤?”，因此有即ΔE<0。7.5.4Hopfield網(wǎng)絡(luò)學(xué)習(xí)1.Hopfield網(wǎng)絡(luò)的能量函數(shù)(1/3)58離散Hopfield網(wǎng)絡(luò)的能量函數(shù)可定義為：7.5.同理可證，若神經(jīng)元k的狀態(tài)由“1”變?yōu)椤?”時(shí)，網(wǎng)絡(luò)能量函數(shù)的變化為：

此時(shí)，由于神經(jīng)元k的狀態(tài)由“1”變?yōu)椤?”，因此有即ΔE<0。可見，無論神經(jīng)元的狀態(tài)由“0”變?yōu)椤?”，還是由“1”變?yōu)椤?”，都總有ΔE<0。它說明離散Hopfield網(wǎng)絡(luò)在運(yùn)行中，其能量函數(shù)總是在不斷降低的，最終將趨于穩(wěn)定狀態(tài)。7.5.4Hopfield網(wǎng)絡(luò)學(xué)習(xí)1.Hopfield網(wǎng)絡(luò)的能量函數(shù)(2/3)59同理可證，若神經(jīng)元k的狀態(tài)由“1”變?yōu)椤?”時(shí)，網(wǎng)絡(luò)7.5.4Hopfield網(wǎng)絡(luò)學(xué)習(xí)1.Hopfield網(wǎng)絡(luò)的能量函數(shù)(3/3)例7.3如圖所示的三個(gè)節(jié)點(diǎn)的Hopfield網(wǎng)絡(luò)，若給定的初始狀態(tài)為：V0={1,0,1}各節(jié)點(diǎn)之間的聯(lián)結(jié)權(quán)值為：w12=w21=1，w13=w31=-2，w23=w32=3各節(jié)點(diǎn)的閾值為

θ1=-1，θ2=2，θ3=1請(qǐng)計(jì)算在此狀態(tài)下的網(wǎng)絡(luò)能量。解：E=-(1/2)(w12v1v2+w13v1v3+w21v2v1+w23v2v3+w31v3v1+w32v3v2)+θ1v1+θ2v2+θ3v3=-(w12v1v2+w13v1v3+w23v2v3)+θ1v1+θ2v2+θ3v3=-(1×1×0+(-2)×1×1+3×0×1)+(-1)×1+2×0+1×1=2Q1Q2Q3v1v2v3w12w13w23607.5.4Hopfield網(wǎng)絡(luò)學(xué)習(xí)例7.3如圖所(1)設(shè)置互連權(quán)值其中，xis為S型樣例（即記憶模式）的第i個(gè)分量，它可以為1或0（或-1），樣例類別數(shù)為m，節(jié)點(diǎn)數(shù)為n。

(2)對(duì)未知類別的樣例初始化其中，yi(t)為節(jié)點(diǎn)i時(shí)刻t的輸出，yi(0)是節(jié)點(diǎn)的初值；xi為輸入樣本的第i個(gè)分量。

(3)迭代運(yùn)算其中，函數(shù)f為閾值型。重復(fù)這一步驟，直到新的迭代不能再改變節(jié)點(diǎn)的輸出為止，即收斂為止。這時(shí)，各節(jié)點(diǎn)的輸出與輸入樣例達(dá)到最佳匹配。否則(4)轉(zhuǎn)第(2)步繼續(xù)。7.5.4Hopfield網(wǎng)絡(luò)學(xué)習(xí)1.Hopfield網(wǎng)絡(luò)學(xué)習(xí)算法61(1)設(shè)置互連權(quán)值7.5.4Hopfield網(wǎng)絡(luò)作業(yè)題7.9假設(shè)w1(0)=0.2,w2(0)=0.4,θ(0)=0.3,η=0.4，請(qǐng)用單層感知器完成邏輯或運(yùn)算的學(xué)習(xí)過程。62作業(yè)題7.9假設(shè)w1(0)=0.2,w2(0第7章機(jī)器學(xué)習(xí)

學(xué)習(xí)是人類獲取知識(shí)的重要途徑和自然智能的重要標(biāo)志，機(jī)器學(xué)習(xí)則是機(jī)器獲取知識(shí)的重要途徑和人工智能的重要標(biāo)志。7.1機(jī)器學(xué)習(xí)的基本概念7.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)7.1.2機(jī)器學(xué)習(xí)的發(fā)展過程7.1.3學(xué)習(xí)系統(tǒng)7.1.4機(jī)器學(xué)習(xí)的主要策略7.2記憶學(xué)習(xí)7.3歸納學(xué)習(xí)7.4解釋學(xué)習(xí)7.5神經(jīng)學(xué)習(xí)63第7章機(jī)器學(xué)習(xí)學(xué)習(xí)是人類獲取知識(shí)的重要途徑和自然7.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)1.學(xué)習(xí)的概念代表性觀點(diǎn)(1)西蒙（Simon,1983）：學(xué)習(xí)就是系統(tǒng)中的適應(yīng)性變化，這種變化使系統(tǒng)在重復(fù)同樣工作或類似工作時(shí)，能夠做得更好。(2)明斯基（Minsky,1985）：學(xué)習(xí)是在人們頭腦里（心理內(nèi)部）有用的變化。(3)邁克爾斯基（Michalski,1986）：學(xué)習(xí)是對(duì)經(jīng)歷描述的建立和修改。一般性解釋：學(xué)習(xí)是一個(gè)有特定目的知識(shí)獲取和能力增長(zhǎng)過程，其內(nèi)在行為是獲得知識(shí)、積累經(jīng)驗(yàn)、發(fā)現(xiàn)規(guī)律等，其外部表現(xiàn)是改進(jìn)性能、適應(yīng)環(huán)境、實(shí)現(xiàn)自我完善等。

647.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)代表性觀點(diǎn)27.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)2.機(jī)器學(xué)習(xí)的概念一般性解釋機(jī)器學(xué)習(xí)就是讓機(jī)器（計(jì)算機(jī)）來模擬和實(shí)現(xiàn)人類的學(xué)習(xí)功能。主要研究?jī)?nèi)容認(rèn)知模擬

主要目的是要通過對(duì)人類學(xué)習(xí)機(jī)理的研究和模擬，從根本上解決機(jī)器學(xué)習(xí)方面存在的種種問題。理論性分析主要目的是要從理論上探索各種可能的學(xué)習(xí)方法，并建立起獨(dú)立于具體應(yīng)用領(lǐng)域的學(xué)習(xí)算法。面向任務(wù)的研究

主要目的是要根據(jù)特定任務(wù)的要求，建立相應(yīng)的學(xué)習(xí)系統(tǒng)。

657.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)一般性解釋3神經(jīng)元模型研究20世紀(jì)50年代中期到60年代初期，也被稱為機(jī)器學(xué)習(xí)的熱烈時(shí)期，最具有代表性的工作是羅森勃拉特1957年提出的感知器模型。符號(hào)概念獲取20世紀(jì)60年代中期到70年代初期。其主要研究目標(biāo)是模擬人類的概念學(xué)習(xí)過程。這一階段神經(jīng)學(xué)習(xí)落入低谷，稱為機(jī)器學(xué)習(xí)的冷靜時(shí)期。知識(shí)強(qiáng)化學(xué)習(xí)20世紀(jì)70年代中期到80年代初期。人們開始把機(jī)器學(xué)習(xí)與各種實(shí)際應(yīng)用相結(jié)合，尤其是專家系統(tǒng)在知識(shí)獲取方面的需求，也有人稱這一階段為機(jī)器學(xué)習(xí)的復(fù)興時(shí)期。連接學(xué)習(xí)和混合型學(xué)習(xí)20世紀(jì)80年代中期至今。把符號(hào)學(xué)習(xí)和連接學(xué)習(xí)結(jié)合起來的混合型學(xué)習(xí)系統(tǒng)研究已成為機(jī)器學(xué)習(xí)研究的一個(gè)新的熱點(diǎn)。7.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)3.機(jī)器學(xué)習(xí)的發(fā)展過程66神經(jīng)元模型研究7.1.1學(xué)習(xí)和機(jī)器學(xué)習(xí)47.1.3學(xué)習(xí)系統(tǒng)環(huán)境學(xué)習(xí)環(huán)節(jié)知識(shí)庫(kù)執(zhí)行環(huán)節(jié)環(huán)境

是學(xué)習(xí)系統(tǒng)所感知到的外界信息集合，也是學(xué)習(xí)系統(tǒng)的外界來源。信息的水平（一般化程度）和質(zhì)量（正確性）對(duì)學(xué)習(xí)系統(tǒng)影響較大。學(xué)習(xí)環(huán)節(jié)

對(duì)環(huán)境提供的信息進(jìn)行整理、分析歸納或類比，形成知識(shí)，并將其放入知識(shí)庫(kù)。知識(shí)庫(kù)

存儲(chǔ)經(jīng)過加工后的信息（即知識(shí)）。其表示形式是否合適非常重要。執(zhí)行環(huán)節(jié)

根據(jù)知識(shí)庫(kù)去執(zhí)行一系列任務(wù)，并將執(zhí)行結(jié)果或執(zhí)行過程中獲得的信息反饋給學(xué)習(xí)環(huán)節(jié)。學(xué)習(xí)環(huán)節(jié)再利用反饋信息對(duì)知識(shí)進(jìn)行評(píng)價(jià)，進(jìn)一步改善執(zhí)行環(huán)節(jié)的行為。677.1.3學(xué)習(xí)系統(tǒng)環(huán)境學(xué)習(xí)環(huán)節(jié)知識(shí)庫(kù)執(zhí)行環(huán)節(jié)環(huán)境7.1.4機(jī)器學(xué)習(xí)的主要策略按學(xué)習(xí)策略來分類即按學(xué)習(xí)中所使用的推理方法來分，可分為記憶學(xué)習(xí)、傳授學(xué)習(xí)、演繹學(xué)習(xí)、歸納學(xué)習(xí)等。按應(yīng)用領(lǐng)域分類專家系統(tǒng)學(xué)習(xí)、機(jī)器人學(xué)習(xí)、自然語(yǔ)言理解學(xué)習(xí)等。按對(duì)人類學(xué)習(xí)的模擬方式

符號(hào)主義學(xué)習(xí)、連接主義學(xué)習(xí)等。687.1.4機(jī)器學(xué)習(xí)的主要策略按學(xué)習(xí)策略來分類6第7章機(jī)器學(xué)習(xí)7.1機(jī)器學(xué)習(xí)的基本概念7.2記憶學(xué)習(xí)7.3歸納學(xué)習(xí)7.4解釋學(xué)習(xí)7.5神經(jīng)學(xué)習(xí)69第7章機(jī)器學(xué)習(xí)7.1機(jī)器學(xué)習(xí)的基本概念77.2記憶學(xué)習(xí)概念記憶學(xué)習(xí)(Rotelearning)也叫死記硬背學(xué)習(xí)，是一種最基本的學(xué)習(xí)過程，它沒有足夠的能力獨(dú)立完成智能學(xué)習(xí)，但對(duì)學(xué)習(xí)系統(tǒng)來說都是十分重要的一個(gè)組成部分，原因是任何學(xué)習(xí)系統(tǒng)都必須記住它們所獲取的知識(shí)，以便將來使用。記憶學(xué)習(xí)的基本過程是：執(zhí)行元素每解決一個(gè)問題，系統(tǒng)就記住這個(gè)問題和它的解，當(dāng)以后再遇到此類問題時(shí)，系統(tǒng)就不必重新進(jìn)行計(jì)算，而可以直接找出原來的解去使用

707.2記憶學(xué)習(xí)記憶學(xué)習(xí)(Rotelearnin若把執(zhí)行元素比作一個(gè)函數(shù)f，由環(huán)境得到的輸入模式記為(x1,x2,…,xn)，由該輸入模式經(jīng)F計(jì)算后得到的輸出模式記為(y1,y2,…,ym)，則機(jī)械學(xué)習(xí)系統(tǒng)就是要把這一輸入輸出模式對(duì)：[(x1,x2,…,xn)，(y1,y2,…,ym)]保存在知識(shí)庫(kù)中，當(dāng)以后再需要計(jì)算f(x1,x2,…,xn)時(shí)，就可以直接從存儲(chǔ)器把(y1,y2,…,ym)檢索出來，而不需要再重新進(jìn)行計(jì)算。(x1,x2,…,xn)(y1,y2,…,yn)[(x1,x2,…,xn),(y1,y2,…,yn)]f存儲(chǔ)輸入模式執(zhí)行函數(shù)輸出模式輸入輸出模式對(duì)機(jī)械式學(xué)習(xí)的學(xué)習(xí)模型7.2記憶學(xué)習(xí)模型71若把執(zhí)行元素比作一個(gè)函數(shù)f，由環(huán)境得到的輸入模式記7.3歸納學(xué)習(xí)

歸納學(xué)習(xí)是指以歸納推理為基礎(chǔ)的學(xué)習(xí)，其任務(wù)是要從關(guān)于某個(gè)概念的一系列已知的正例和反例中歸納出一個(gè)一般的概念描述。7.3.1示例學(xué)習(xí)是歸納學(xué)習(xí)的一種特例。它給學(xué)習(xí)者提供某一概念的一組正例和反例，學(xué)習(xí)者歸納出一個(gè)總的概念描述，并使這個(gè)描述適合于所有的正例，排除所有的反例。7.3.2決策樹學(xué)習(xí)

是一種以示例為基礎(chǔ)的歸納學(xué)習(xí)方法，也是目前最流行的歸納學(xué)習(xí)方法之一。在現(xiàn)有的各種決策樹學(xué)習(xí)算法中，影響較大的是ID3算法。本節(jié)主要討論決策樹的概念和決策樹學(xué)習(xí)的ID3算法。727.3歸納學(xué)習(xí)歸納學(xué)習(xí)是指以歸納推理為基礎(chǔ)的學(xué)按例子的來源分類①例子來源于教師的示例學(xué)習(xí)②例子來源于學(xué)習(xí)者本身的示例學(xué)習(xí)學(xué)習(xí)者明確知道自己的狀態(tài)，但完全不清楚所要獲取的概念。③例子來源于學(xué)習(xí)者以外的外部環(huán)境的示例學(xué)習(xí)例子的產(chǎn)生是隨機(jī)的。按例子的類型分類①僅利用正例的示例學(xué)習(xí)這種學(xué)習(xí)方法會(huì)使推出的概念的外延擴(kuò)大化。②利用正例和反例的示例學(xué)習(xí)這是示例學(xué)習(xí)的一種典型方式，它用正例用來產(chǎn)生概念，用反例用來防止概念外延的擴(kuò)大。7.3.1示例學(xué)習(xí)1.示例學(xué)習(xí)的類型73按例子的來源分類7.3.1示例學(xué)習(xí)11示例空間規(guī)則空間驗(yàn)證過程解釋過程

示例空間

是我們向系統(tǒng)提供的示教例子的集合。研究問題：例子質(zhì)量，搜索方法。解釋過程

是從搜索到的示例中抽象出一般性的知識(shí)的歸納過程。解釋方法：常量轉(zhuǎn)換為變量，去掉條件，增加選擇，曲線擬合等。規(guī)則空間

是事務(wù)所具有的各種規(guī)律的集合。研究問題：對(duì)空間的要求，搜索方法驗(yàn)證過程

是要從示例空間中選擇新的示例，對(duì)剛剛歸納出的規(guī)則做進(jìn)一步的驗(yàn)證和修改。7.3.1示例學(xué)習(xí)2.示例學(xué)習(xí)的模型74示例空間規(guī)則空間驗(yàn)證過程解釋過程示例空間7.3.1是指解釋過程從具體示例形成一般性知識(shí)所采用的歸納推理方法。最常用的解釋方法有以下4種：(1)把常量轉(zhuǎn)換為變量把示例中的常量換成變量而得到一個(gè)一般性的規(guī)則。(2)去掉條件把示例中的某些無關(guān)的子條件舍去。(3)增加選擇在析取條件中增加一個(gè)新的析取項(xiàng)。常用的增加析取項(xiàng)的方法有前件析取法和內(nèi)部析取法兩種(4)曲線擬合對(duì)數(shù)值問題的歸納可采用最小二乘法進(jìn)行曲線擬合7.3.1示例學(xué)習(xí)3.示例學(xué)習(xí)的解釋方法(1/5)75是指解釋過程從具體示例形成一般性知識(shí)所采用的歸納推理例：假設(shè)例子空間中有以下兩個(gè)關(guān)于撲克牌中“同花”概念的示例：

示例1：花色(c1，梅花)∧花色(c2，梅花)∧花色(c3，梅花)∧花色(c4，梅花)∧花色(c5，梅花)→同花(c1,c2,c3,c4,c5)示例2：花色(c1，紅桃)∧花色(c2，紅桃)∧花色(c3，紅桃)∧花色(c4，紅桃)∧花色(c5，紅桃)→同花(c1,c2,c3,c4,c5)其中，示例1表示5張梅花牌是同花，示例2表示5張紅桃牌是同花。解釋過程：(1)把常量化為變量

例如，對(duì)這兩個(gè)示例，只要把“梅花”和“紅桃”用變量x代換，就可得到如下一般性的規(guī)則：規(guī)則1：花色(c1，x)∧花色(c2，x)∧花色(c3，x)∧花色(c4，x)∧花色(c5，x)→同花(c1,c2,c3,c4,c5)7.3.1示例學(xué)習(xí)3.示例學(xué)習(xí)的解釋方法(2/5)76例：假設(shè)例子空間中有以下兩個(gè)關(guān)于撲克牌中“同花”概念(2)去掉條件

這種方法是要把示例中的某些無關(guān)的子條件舍去。例如，有如下示例：示例3：花色(c1,紅桃)∧點(diǎn)數(shù)(c1，2)∧花色(c2,紅桃)∧點(diǎn)數(shù)(c2，3)∧花色(c3,紅桃)∧點(diǎn)數(shù)(c3，4)∧花色(c4,紅桃)∧點(diǎn)數(shù)(c4，5)∧花色(c5,紅桃)∧點(diǎn)數(shù)(c5，6)→同花(c1,c2,c3,c4,c5)7.3.1示例學(xué)習(xí)3.示例學(xué)習(xí)的解釋方法(3/5)為了學(xué)習(xí)同花的概念，除了需要把常量變?yōu)樽兞客?，還需要把與花色無關(guān)的“點(diǎn)數(shù)”子條件舍去。這樣也可得到上述規(guī)則1：規(guī)則1：花色(c1，x)∧花色(c2，x)∧花色(c3，x)∧花色(c4，x)∧花色(c5，x)→同花(c1,c2,c3,c4,c5)77(2)去掉條件7.3.1示例學(xué)習(xí)為了學(xué)習(xí)7.3.1示例學(xué)習(xí)3.示例學(xué)習(xí)的解釋方法(4/5)

(3)增加選擇在析取條件中增加一個(gè)新的析取項(xiàng)。包括前件析取法和內(nèi)部析取法。前件析取法：是通過對(duì)示例的前件的析取來形成知識(shí)的。例如：

示例4：點(diǎn)數(shù)(c1,J)→臉(c1)

示例5：點(diǎn)數(shù)(c1,Q)→臉(c1)

示例6：點(diǎn)數(shù)(c1,K)→臉(c1)將各示例的前件進(jìn)行析取，就可得到所要求的規(guī)則：規(guī)則2：點(diǎn)數(shù)(c1,J)∨點(diǎn)數(shù)(c1,Q)∨點(diǎn)數(shù)(c1,K)→臉(c1)內(nèi)部析取法：是在示例的表示中使用集合與集合的成員關(guān)系來形成知識(shí)的。例如，有如下關(guān)于“臉牌”的示例：

示例7：點(diǎn)數(shù)c1∈{J}→臉(c1)

示例8：點(diǎn)數(shù)c1∈{Q}→臉(c1)

示例9：點(diǎn)數(shù)c1∈{K}→臉(c1)用內(nèi)部析取法，可得到如下規(guī)則：

規(guī)則3：點(diǎn)數(shù)(c1)∈{J,Q,K}→臉(c1)787.3.1示例學(xué)習(xí)(3)增加選擇16

(4)曲線擬合

對(duì)數(shù)值問題的歸納可采用曲線擬合法。假設(shè)示例空間中的每個(gè)示例(x,y,z)都是輸入x,y與輸出z之間關(guān)系