1、人工智能第六章 機器學習第1頁，共85頁。第6章機器學習6.1 機器學習概述6.2 歸納學習（變型空間和候選消除算法）6.3 決策樹學習6.4 基于實例的學習6.5 強化學習6.6 小結第2頁，共85頁。 6.1.1 機器學習的概念心理學中對學習的解釋是：學習是指（人或動物）依靠經驗的獲得而使行為持久變化的過程。Simon認為：如果一個系統能夠通過執行某種過程而改進它的性能，這就是學習。Minsky認為：學習是在人們頭腦中（心理內部）進行有用的變化。Tom M. Mitchell在機器學習一書中對學習的定義是：對于某類任務T和性能度P，如果一個計算機程序在T上以P衡量的性能隨著經驗E而自我完善

2、，那么，我們稱這個計算機程序從經驗E中學習。當前關于機器學習的許多文獻中也大都認為：學習是一個有特定目的的知識獲取和能力增長過程，其內在行為是獲得知識、積累經驗、發現規律等，其外部表現是改進性能、適應環境、實現自我完善等。6.1 機器學習概述第3頁，共85頁。一個學習系統應具有以下特點：1.具有適當的學習環境 學習系統中環境并非指通常的物理條件，而是指學習系統進行學習時所必需的信息來源。2.具有一定的學習能力 一個好的學習方法和一定的學習能力是取得理想的學習效果的重要手段。所以，學習系統應模擬人的學習過程，使系統通過與環境反復多次相互作用，逐步學到有關知識，并且要使系統在學習過程中通過實踐驗證

3、、評價所學知識的正確性。6.1 機器學習概述第4頁，共85頁。3.能用所學的知識解決問題 學習的目的在于應用，學習系統能把學到的信息用于對未來的估計、分類、決策和控制。4.能提高系統的性能 提高系統的性能是學習系統最終目標。通過學習，系統隨之增長知識，提高解決問題的能力，使之能完成原來不能完成的任務，或者比原來做得更好。 6.1 機器學習概述第5頁，共85頁。 由此看來: 學習系統至少應有環境、知識庫、學習環節和執行環節四個基本部分。一種典型的學習系統（迪特里奇（Dietterich）學習模型）如下圖所示。環境向系統的學習部件提供某些信息，學習環節利用這些信息修改知識庫，增進執行部件的效能；執

4、行環節根據知識庫完成任務，同時把獲得的信息反饋給學習部件。環境學習單元知識庫執行單元簡單的學習模型6.1 機器學習概述第6頁，共85頁。1神經元模型研究階段 這個時期主要技術是神經元模型以及基于該模型的決策論和控制論;機器學習方法通過監督（有教師指導的）學習來實現神經元間連接權的自適應調整，產生線性的模式分類和聯想記憶能力。 具有代表性的工作有FRosenblaft的感知機（1958年）；NRashevsky數學生物物理學（1948年）；WSMcCullouch與WPitts的模擬神經元的理論（1943年）;RMFriedberg對生物進化過程的研究6.1.2 機器學習的發展簡史6.1 機器學

5、習概述第7頁，共85頁。2符號概念獲取研究階段 60年代初期，機器學習的研究進入了第二階段，在這個階段，心理學和人類學習的模擬占有主導地位，其特點是使用符號而不是數值表示來研究學習問題，其目標是用學習來表達高級知識的符號描述。在這一觀點的影響下，主要技術是概念獲取和各種模式識別系統的應用；研究人員一方面深入探討學習的簡單概念，另一方面則把大量的領域知識并入學習系統，以便它們發現高深的概念。 這個階段代表性的工作是溫斯頓（P.H. Winston，1975）的基于示例歸納的結構化概念學習系統。6.1 機器學習概述第8頁，共85頁。3基于知識的各種學習系統研究階段 機器學習發展的第三個階段始于70

6、年代中期，這個階段不再局限于構造概念學習系統和獲取上下文知識，結合了問題求解中的學習、概念聚類、類比推理及機器發現的工作。 相應的有關學習方法相繼推出，比如示例學習、示教學習、 觀察和發現學習、類比學習、基于解釋的學習。工作特點強調應用面向任務的知識和指導學習過程的約束，應用啟發式知識于學習任務的生成和選擇，包括提出收集數據的方式、選擇要獲取的概念、控制系統的注意力等。6.1 機器學習概述第9頁，共85頁。4聯結學習和符號學習共同發展階段 80年代后期以來，形成了聯結學習和符號學習共同發展的局的第四個階段。在這個時期，發現了用隱單元來計算和學習非線性函數的方法，從而克服了早期神經元模型的局限性

7、，同時，由于計算機硬件的迅速發展，使得神經網絡的物理實現變成可能，在聲音識別、圖像處理等領域，神經網絡取得了很大的成功。 在這個進期，符號學習伴隨人工智能的進展也日益成熟，應用領域不斷擴大，最杰出的工作有分析學習（特別是解釋學習）、遺傳算法、決策樹歸納等?，F在基于計算機網絡的各種自適應、具有學習功能的軟件系統的研制和開發,將機器學習的研究推向新的高度。6.1 機器學習概述第10頁，共85頁。1. 基于學習策略的分類 （1）模擬人腦的機器學習符號學習：模擬人腦的宏觀心理級學習過程，以認知心理學原理為基礎，以符號數據為輸入，以符號運算為方法，用推理過程在圖或狀態空間中搜索，學習的目標為概念或規則等

8、。符號學習的典型方法有：記憶學習、示例學習、演繹學習、類比學習、解釋學習等。神經網絡學習（或連接學習）：模擬人腦的微觀生理級學習過程，以腦和神經科學原理為基礎，以人工神經網絡為函數結構模型，以數值數據為輸入，以數值運算為方法，用迭代過程在系數向量空間中搜索，學習的目標為函數。典型的連接學習有權值修正學習、拓撲結構學習。 （2）直接采用數學方法的機器學習 主要有統計機器學習。6.1.3 機器學習的分類6.1 機器學習概述第11頁，共85頁。2. 基于推理策略的分類 （1）歸納學習 符號歸納學習：典型的符號歸納學習有示例學習，決策樹學習。 函數歸納學習（發現學習）：典型的函數歸納學習有神經網絡學習

9、、示例學習，發現學習，統計學習。 （2）演繹學習 （3）類比學習：典型的類比學習有案例（范例）學習。 （4）分析學習：典型的分析學習有案例（范例）學習、解釋學習。6.1 機器學習概述第12頁，共85頁。3. 基于學習方式的分類（1）有導師學習（監督學習）：輸入數據中有導師信號，以概率函數、代數函數或人工神經網絡為基函數模型，采用迭代計算方法，學習結果為函數。（2）無導師學習（非監督學習）：輸入數據中無導師信號，采用聚類方法，學習結果為類別。典型的無導師學習有發現學習、聚類、競爭學習等。（3）強化學習（增強學習）：以環境反饋（獎/懲信號）作為輸入，以統計和動態規劃技術為指導的一種學習方法。6.1

10、 機器學習概述第13頁，共85頁。4. 基于數據形式的分類（1）結構化學習：以結構化數據為輸入，以數值計算或符號推演為方法。典型的結構化學習有神經網絡學習、統計學習、決策樹學習、規則學習。（2）非結構化學習：以非結構化數據為輸入，典型的非結構化學習有類比學習、案例學習、解釋學習、文本挖掘、圖像挖掘、Web挖掘等。6.1 機器學習概述第14頁，共85頁。 5. 基于學習目標的分類 （1）概念學習：即學習的目標和結果為概念，或者說是為了獲得概念的一種學習。典型的概念學習有示例學習。 （2）規則學習：即學習的目標和結果為規則，或者說是為了獲得規則的一種學習。典型的規則學習有決策樹學習。 （3）函數學

11、習：即學習的目標和結果為規則，或者說是為了獲得函數的一種學習。典型的函數學習有神經網絡學習。 （4）類別學習：即學習的目標和結果為對象類，或者說是為了獲得類別的一種學習。典型的類別學習有聚類分析。 （5）貝葉斯網絡學習：即學習的目標和結果是貝葉斯網絡，或者說是為了獲得貝葉斯網絡的一種學習。其又可分為結構學習和參數學習。6.1 機器學習概述第15頁，共85頁。 機器學習的應用非常廣泛，利用這門技術，計算機已經能夠成功地識別人類的講話(Waibel 1989, Lee 1989)，在高速公路上自動駕駛汽車(Pomerleau 1989)，學習分類新的天文結構(Fayyad et al. 1995)

12、，以接近人類世界冠軍的水平對弈西洋雙陸棋（Tesauro 1992,1995）6.1.4 機器學習的應用與研究目標：6.1 機器學習概述第16頁，共85頁。研究目標有三個： (1)人類學習過程的認知模型。研究人類學習機理的認知模型，這種研究對人類的教育，以及對開發機器學習系統都有重要的意義。(2)通用學習算法。通過對人類學習過程的研究，探索各種可能的學習方法，建立起具體應用領域的通用學習算法。(3)構造面向任務的專用學習系統。研究智能系統的建造，解決專門的實際問題，并開發完成這些專門任務的學習系統。6.1 機器學習概述第17頁，共85頁。 歸納學習(概念學習、經驗學習）是符號學習中研究的最為廣

13、泛的一種方法。給定關于某個概念的一系列已知的正例與反例，其任務是從中歸納出一個一般的概念描述。歸納學習能夠獲得新的概念，創立新的規則，發現新的理論。它的一般操作是泛化(Generalization)和特化(Specialization)。泛化用來擴展一假設的語義信息，以使其能夠包含更多的正例，應用于更多的情況。特化是泛化的相反的操作，用于限制概念描述的應用范圍。 6.2 歸納學習（變型空間和候選消除算法）第18頁，共85頁。6.2.1 歸納學習的基本概念歸納學習指在從大量的經驗數據中歸納抽取出一般的判定規則和模式，是從特殊情況推導出一般規則的學習方法。歸納學習的目標是形成合理的能解釋已知事實和

14、預見新事實的一般性結論。歸納學習由于依賴于經驗數據，因此又稱為經驗學習(Empirical Learning)，由于歸納依賴于數據間的相似性，所以也稱為基于相似性的學習(Similarity Based Learning)。6.2 歸納學習（變型空間和候選消除算法）第19頁，共85頁。歸納學習的雙空間模型如圖所示。1.歸納學習的雙空間模型6.2 歸納學習（變型空間和候選消除算法）第20頁，共85頁。 首先由施教者給實例空間提供一些初始示教例子，由于示教例子在形式上往往和規則形式不同，因此需要對這些例子進行轉換，解釋為規則空間接受的形式。然后利用解釋后的例子搜索規則空間，由于一般情況下不能一次就

15、從規則空間中搜索到要求的規則，因此還要尋找一些新的示教例子，這個過程就是選擇例子。程序會選擇對搜索規則空間最有用的例子，對這些示教例子重復上述循環。如此循環多次，直到找到所要求的例子。執行過程描述6.2 歸納學習（變型空間和候選消除算法）第21頁，共85頁。歸納學習方法可以劃分為單概念學習和多概念學習兩類。這里，概念指用某種描述語言表示的謂詞，當應用于概念的正實例時，謂詞為真，應用于負實例時為假。從而概念謂詞將實例空間劃分為正、反兩個子集。對于單概念學習，學習的目的是從概念空間（即規則空間）中尋找某個與實例空間一致的概念；對于多概念學習任務，是從概念空間中找出若干概念描述，對于每個概念描述，實

16、例空間中均有相應的空間與之對應。2.歸納學習方法的分類6.2 歸納學習（變型空間和候選消除算法）第22頁，共85頁。典型的單概念學習系統包括米切爾(Tom Mitchell)的基于數據驅動的變型空間法，昆蘭(J.R. Quinlan)的ID3方法，狄特利希(T.G. Dietterich)和米哈爾斯基(R.S. Michalski)提出的基于模型驅動的Induce算法。典型的多概念學習方法和系統有米哈爾斯基的AQ11、DENDRAL和AM程序等。多概念學習任務可以劃分成多個單概念學習任務來完成。多概念學習與單概念學習的差別在于多概念學習方法必須解決概念之間的沖突問題。2.歸納學習方法的分類6.

17、2 歸納學習（變型空間和候選消除算法）第23頁，共85頁。變型空間學習方法(Learning by Version Space)，也稱為變型空間學習法。變型空間法是TMMitchell于1977年提出的一種數據驅動型的學習方法。該方法以整個規則空間為初始的假設規則集合H。依據示教例子中的信息，系統對集合H進行一般化或特殊化處理，逐步縮小集合H。最后使得H收斂到只含有要求的規則。由于被搜索的空間H逐漸縮小，故稱為變型空間法。6.2.2 變型空間學習6.2 歸納學習（變型空間和候選消除算法）第24頁，共85頁。在變型空間中，表示規則的點與點之間存在著一種由一般到特殊的偏序關系。我們定義為覆蓋，例如

18、，color(X,Y)覆蓋color(ball,Z)，于是又覆蓋color(ball,red)。(more general than)作為一個簡單的例子，考慮有這樣一些屬性和值的對象域： Sizes=large,small Colors=red,white,blue Shapes=ball,brick,cube這些對象可以用謂詞obj(Sizes,Color,Shapes)來表示。用變量替換常量這個泛化操作定義 1變型空間的結構6.2 歸納學習（變型空間和候選消除算法）第25頁，共85頁。 假設空間H由兩個子集G和S所限定，子集G中的元素表示H中的最一般的概念，子集S中的元素表示H中的最特殊的

19、概念，假設空間H的確切組成是：G中包含的假設，S中包含的假設以及G和S之間偏序結構所規定的假設。即： H=GSk|GKS 式中“”表示變型空間中的偏序關系。 示例: Colors=red, ,blue Shapes=ball, cube這些對象可以用謂詞obj(Colors, Shapes)來表示。6.2 歸納學習（變型空間和候選消除算法）第26頁，共85頁。G:S:(x, y)(red, y)(blue, y)(x, ball)(x, cube)(blue, cube)(blue, ball)(red, cube)(red, ball)6.2 歸納學習（變型空間和候選消除算法）第27頁，共8

20、5頁。GSH沒有描述一般示教例子特殊6.2 歸納學習（變型空間和候選消除算法）第28頁，共85頁。算法6.1 候選項刪除算法（1）把H初始化為整個規則空間。這時G僅包含空描述。S包含所有最特殊的概念。實際上，為避免S集合過大，算法把S初化為僅包含第一個示教正例。（2）接受一個新的示教例子。如果這個例子是正例，則從G中刪除不包含新例的概念，然后修改S為由新正例和S原有元素同歸納出最特殊化的泛化。這個過程稱為對集合S的修改過程。如果這個例子是反例，則從S中刪去包含新例的概念，再對G作盡量小的特殊化，使之不包含新例。這個過程稱為集合G的修改過程。（3）重復步驟，直到G=S，且使這兩個集合都只含有一個

21、元素為止。（4）輸出H中的概念（即輸出G或S）。6.2 歸納學習（變型空間和候選消除算法）第29頁，共85頁。（sm squ）（sm cir）（lg squ）（lg cir）（sm tri）（sm y）（lg y）（x squ）（x cir）（x tri）（x y）（lg tri）示例：G0=（x，y ）S0=（sm squ）,（sm cir）,（sm tri）,（lg squ）,（lg cir）,（lg tri）G1=（x y）S1=（sm cir）G2=（x cir），（x squ），（sm y）S2=（sm cir）G3=（x cir）S3=（x cir）6.2 歸納學習（變型空間和候選

22、消除算法）第30頁，共85頁。6.2.3 歸納偏置 候選消除算法的說明候選消除算法收斂到正確的假設訓練樣例中沒有錯誤H中確實包含描述目標概念的正確假設如果樣例中存在錯誤如果給定足夠的訓練數據，我們會發現S和G邊界收斂得到一個空的變型空間如果目標概念不能由假設表示方式所描述相似情況出現6.2 歸納學習（變型空間和候選消除算法）第31頁，共85頁。歸納偏置: 指學習程序用來限制概念空間或者在這 個空間中選擇概念的任何標準。 歸納偏置的強化 : (1) 經過啟發式，推薦新概念描述加到概念描述語言，以確定一個更好的偏置。 （2）變換推薦的描述成為概念描述語言中已形式化表示的新概念描述，同化任何新概念進

23、入假設的限定空間，保持假設空間機制，使得新概念描述語言較前面的語言更好。6.2 歸納學習（變型空間和候選消除算法）第32頁，共85頁。 學習正例時，對S進行泛化，這往往擴大S。學習反例時，對G進行特化，這往往擴大G。G和S的規模過大會給算法的實用造成困難。算法是在訓練例子引導下，對規則空間進行寬度優先搜索。對大的規則空間，算法慢得無法接受。主要缺點6.2 歸納學習（變型空間和候選消除算法）第33頁，共85頁。 決策樹學習是離散函數的一種樹型表示，表示能力強，可以表示任意的離散函數，是一種重要的歸納學習方法。決策樹是實現分治策略的數據結構，通過把實例從根節點排列到某個葉子節點來分類實例，可用于分

24、類和回歸。決策樹代表實例屬性值約束的合取的析取式，從樹根到樹葉的每一條路徑對應一組屬性測試的合取，樹本身對應這些合取的析取。 6.3 決策樹學習第34頁，共85頁。6.3.1 決策樹的組成及分類1決策樹的組成決策樹由一些決策節點和終端樹葉組成，每個決策節點m實現一個具有離散輸出的測試函數fm(x)標記分支。給定一個輸入，在每個節點應用一個測試，并根據測試的輸出確定一個分支。這一過程從根節點開始，并遞歸地重復，直到到達一個樹葉節點。該樹葉中的值形成輸出。每個fm(x)定義了一個d維輸入空間中的判別式，將空間劃分成較小區域，在從根節點沿一條路徑向下時，這些較小的區域被進一步劃分。每個樹葉節點有一個

25、輸出標號，對于分類，該標號是類代碼，對于回歸，則是一個數值。一個樹葉節點定義了輸入空間的一個局部區域，落入該區域的實例具有相同的輸出。依據每個節點所測試的屬性的個數，決策樹可分為單變量樹和多變量樹。6.3 決策樹學習第35頁，共85頁。2單變量樹 在單變量樹中，每個節點的測試值使用一個輸入維，也就是只測試一個屬性。w20 x2C1x1w10C2x1w10 x2w20C2C2C1C1YesYesNoNo圖6.6單變量樹舉例6.3 決策樹學習第36頁，共85頁。3多變量樹 在樹的各結點選擇多個屬性的組合進行測試，一般表現為通過數學或邏輯算子將一些屬性組合起來，形成新的屬性作為測試屬性，因而稱這樣形

26、成的決策樹為多變量決策樹。 X2C1C2X1w11x1+w12x2+w100YesNoC2C1圖6.7 線性多變量樹6.3 決策樹學習第37頁，共85頁。如果學習的任務是對一個大的實例集做概念分類的歸納定義，而這些例子都是用一些無結構的“屬性-值”對來表示，那么可以采用決策樹學習算法。亨特(Hunt)于1966年研制了一個概念學習系統CLS，可以學習單個概念，并用此學到的概念分類新的實例。這是一種早期的基于決策樹的歸納學習系統。 昆蘭(Quinlan)于1983年此進行了發展，研制了ID3算法。該算法不僅能方便地表示概念屬性-值信息的結構，而且能從大量實例數據中有效地生成相應的決策樹模型。6.

27、3.2 決策樹的構造算法CLS6.3 決策樹學習第38頁，共85頁。 算法6.2 決策樹構造算法CLS：(1)如果TR中所有實例分類結果均為Ci，則返回Ci；(2)從屬性表中選擇某一屬性Ai作為檢測屬性；(3)不妨假設|ValueType(Ai)|=k，根據Ai取值的不同,將TR劃分為k個訓練集TR1，TR2，TRk，其中： TRi=|TR且V(X,A)為屬性A的第i個值(4)從屬性表中去掉已做檢測的屬性Ai；(5)對每一個i(1ik)，用TRi和新的屬性表遞歸調用CLS生成子分支決策樹DTRi；(6)返回以屬性Ai為根，DTR1，DTRk為子樹的決策樹。6.3 決策樹學習第39頁，共85頁。

28、NoNoNoNoYesNoNo210210alivedead2.52.5No. of WingsBroken WingsStatusArea/weight圖6.8 鳥飛的決策樹 6.3 決策樹學習第40頁，共85頁。6.3.3基本的決策樹算法ID3ID3的思想自頂向下構造決策樹從“哪一個屬性將在樹的根節點被測試”開始使用統計測試來確定每一個實例屬性單獨分類訓練樣例的能力ID3的過程分類能力最好的屬性被選作樹的根節點根節點的每個可能值產生一個分支訓練樣例排列到適當的分支重復上面的過程6.3 決策樹學習第41頁，共85頁。ID3(Examples, Target_attribute, Attrib

29、utes)創建樹的root節點如果Examples都為正,返回label=+的單節點樹root如果Examples都為反,返回label=-的單節點樹root如果Attributes為空，那么返回單節點root，label=Examples中最普遍的Target_attribute值否則開始AAttributes中分類examples能力最好的屬性root的決策屬性A對于A的每個可能值vi在root下加一個新的分支對應測試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個新分支下加一個葉子節點，節點的label=Examples中最普遍

30、的Target_attribute值否則在新分支下加一個子樹ID3（ Examplesvi,Target_attribute,Attributes-A）結束返回root6.3 決策樹學習第42頁，共85頁。ID3算法是一種自頂向下增長樹的貪婪算法，在每個節點選取能最好地分類樣例的屬性。繼續這個過程直到這棵樹能完美分類訓練樣例，或所有的屬性都已被使用過。那么，在決策樹生成過程當中，應該以什么樣的順序來選取實例集中實例的屬性進行擴展呢？即如何選擇具有最高信息增益的屬性為最好的屬性？6.3 決策樹學習第43頁，共85頁。為了評價屬性的重要性，昆蘭根據檢驗每一屬性所得到的信息量的多少，給出了擴展屬性的

31、選取方法，其中信息量的多少和熵有關。信息論簡介6.3 決策樹學習第44頁，共85頁。ID3算法-最佳分類屬性-信息熵，簡稱熵(1)自信息量I(a):設信源X發出符號a的概率為p(a),則I(a)定義為: I(a)=-logp(a) (單位:bit) 表示收信者在收到符號a之前，對a的不確定性，收到后獲得的關于a的信息量。(2)信息熵H(X):設信源X的概率分布為(X,p(x),則H(X)定義為: H(X)=-p(x)logp(x) 表示信源X的整體不確定性，反應了信源每發出一個符號所提供的平均信息量。(3)條件熵H(X|Y):設信源X,Y的聯合概率分布為p(x,y),則 H(X|Y)定義為:

32、H(X|Y)=- p(x,y)logp(x|y) 表示收信者在收到Y后對X的不確定性估計.6.3 決策樹學習第45頁，共85頁。設給定正負實例的集合為S,構成訓練窗口。ID3算法視S為一個離散信息系統，并用信息熵表示該系統的信息量。當決策有k個不同的輸出時，S的熵為:其中Pi表示第i類輸出所占訓練窗口中總的輸出數量的比例。ID3算法-最佳分類屬性6.3 決策樹學習第46頁，共85頁。為了檢測每個屬性的重要性，可以通過屬性的信息增益Gain來評估起重要性。對于屬性A，假設其值域為(v1,v2,vn)，則訓練實例S中屬性A的信息增益Gain可以定義為：式中，Si表示S中屬性A的值為vi的子集；|S

33、i|表示集合的勢。ID3算法-最佳分類屬性-信息增益6.3 決策樹學習第47頁，共85頁。昆蘭建議選取獲得信息量最大的屬性作為擴展屬性。這一啟發式規則又稱最小熵原理。因為獲得信息量最大，即信息增益Gain最大，等價于使不確定性最小，即使得熵最小，即條件熵H(S|Ai)為最小。因此也可以條件熵H(S|Ai)為最小作為選擇屬性重要性標準。H(S|Ai)越小，說明Ai引入的信息最多，系統熵下降的越快。ID3算法是一種貪婪搜索(Greedy Search)算法，即選擇信息量最大的屬性進行決策樹分裂，計算中表現為使訓練例子集的熵下降最快。ID3算法-最佳分類屬性-信息增益6.3 決策樹學習第48頁，共8

34、5頁。現考慮鳥是否能飛的實例，InstancesNo. of WingsBroken WingsLiving statusarea/weightFly120alive2.5T221alive2.5F322alive2.6F420alive3.0T520dead3.2F600alive0F710alive0F820alive3.4T920alive2.0F6.3 決策樹學習第49頁，共85頁。對于上表給出的例子,選取整個訓練集為訓練窗口,有3個正實例,6個負實例,采用記號3+,6-表示總的樣本數據。則S的熵為計算屬性Living Status的信息增益，該屬性為值域為(alive, dead),

35、則 S=3+,6-, Salive=3+,5-, Sdead=0+,1- 先計算Entropy(Salive), Entropy(Sdead)如下:ID3算法-最佳分類屬性-例子分析6.3 決策樹學習第50頁，共85頁。ID3算法-最佳分類屬性-例子分析所以,living status的信息增益為6.3 決策樹學習第51頁，共85頁。ID3算法-最佳分類屬性-例子分析同樣可計算其他屬性的信息增益，然后根據最小熵原理，選取信息量最大的屬性作為決策樹的根節點屬性。6.3 決策樹學習第52頁，共85頁。ID3算法的優點：分類和測試速度快，特別適用于大數據庫的分類問題。ID3算法的缺點： 第一：決策樹

36、的知識表示沒有規則易于理解。 第二：兩顆決策樹比較是否等價問題是子圖匹配問題，是NP完全的。 第三：不能處理未知屬性值的情況。 第四：對噪聲問題沒有好的處理辦法。ID3算法-最佳分類屬性-優缺點6.3 決策樹學習第53頁，共85頁。6.3.4 決策樹的偏置 構造好的決策樹的關鍵在于選擇好的屬性，屬性選擇依賴于信息增益、信息增益比、Gini-index、距離度量、J-度量、最小描述長度、正交法度量等等。比如上述的ID3算法優先選取信息增益最大的屬性作為擴展屬性。 決策樹還可以通過剪枝來尋找最小的樹。通常，如果到達一個節點的訓練實例數小于訓練集的某個百分比(如5%)，則無論是否不純或是否有錯誤，該

37、節點都不進一步分裂。因為基于過少實例的決策樹導致較大方差，從而導致較大泛化誤差。在樹完全構造出來之前提前停止樹構造稱作樹的先剪枝。6.3 決策樹學習第54頁，共85頁。6.3.4 決策樹的偏置 得到較小樹的另一種可能做法是后剪枝。樹完全增長直到所有的樹葉都是純的并具有零訓練誤差之后，找出導致過分擬合的子樹并剪掉它們。從最初的被標記的數據集中保留一個剪枝集，在訓練階段不使用，對于每顆子樹，用一個被該子樹覆蓋的訓練實例標記的樹葉節點替換它，如果該樹葉在剪枝集上的性能不比該子樹差，則剪掉該子樹并保留樹葉節點，因為子樹的附加的復雜性是不必要的，否則保留子樹。 剪枝還可以依據最小長度等其它準則。先剪枝較

38、快，但后剪枝通常導致更準確的樹。6.3 決策樹學習第55頁，共85頁。 基于實例的學習采用保存實例本身的方法來表達從實例集里提取出的知識，并將類未知的新實例與現有的類已知的實例聯系起來進行操作。這種方法直接在樣本上工作，不需要建立規則?；趯嵗膶W習方法包括最近鄰法、局部加權回歸法、基于范例的推理法等等?；趯嵗膶W習只是簡單地把訓練樣例存儲起來，從這些實例中泛化的工作被推遲到必須分類新的實例時，所以有時被稱為消極學習法。6.4 基于實例的學習第56頁，共85頁。6.4.1 K-近鄰算法 基于實例的機器學習方法把實例表示為n維歐式空間Rn中的實數點，使用歐氏距離函數，把任意的實例x表示為這樣的

39、特征向量：，那么兩個實例xi和xj之間的距離定義為d(xi,xj),則 d(xi,xj)=6.4 基于實例的學習第57頁，共85頁。算法6.4 逼近離散值函數f: RnV的k-近鄰算法：訓練算法：將每個訓練樣例加入到列表 training_examples分類算法： （1）給定一個要分類的查詢實例xq （2）在training_examples中選出最靠近xq 的k個實例，并用x1.xk表示 （3）返回6.4 基于實例的學習第58頁，共85頁。 離散的k-近鄰算法作簡單修改后可用于逼近連續值的目標函數。即計算k個最接近樣例的平均值，而不是計算其中的最普遍的值，為逼近f：RnR，計算式如下： 6

40、.4 基于實例的學習第59頁，共85頁。6.4.2 距離加權最近鄰法 對k-近鄰算法的一個改進是對k個近鄰的貢獻加權，越近的距離賦予越大的權值，比如：也可以用類似的方式對實值目標函數進行距離加權 6.4 基于實例的學習第60頁，共85頁。6.4.3 基于范例的學習 人們為了解決一個新問題，先是進行回憶，從記憶中找到一個與新問題相似的范例，然后把該范例中的有關信息和知識復用到新問題的求解之中。 基于范例的學習采用更復雜的符號表示，因此檢索實例的方法也更加復雜。在基于范例推理 (Case-Based Reasoning, 簡稱CBR)中，把當前所面臨的問題或情況稱為目標范例(target case

41、)，而把記憶的問題或情況稱為源范例(base case)，基于范例推理就是由目標范例的提示而獲得記憶中的源范例，并由源范例來指導目標范例求解的一種策略. 基于范例的推理是人工智能領域中的一種重要的基于知識的問題求解和學習的方法。基于范例推理中知識表示是以范例為基礎，范例的獲取比規則獲取要容易，大大簡化了知識獲取。對過去的求解結果進行復用，而不是再次從頭推導，可以提高對新問題的求解效率。過去求解成功或失敗的經歷可以指導當前求解時該怎樣走向成功或避開失敗，這樣可以改善求解的質量。對于那些目前沒有或根本不存在可以通過計算推導來解決的問題，基于范例推理能很好發揮作用。6.4 基于實例的學習第61頁，共

42、85頁。1.基于范例推理的一般過程（1）聯想記憶（2）類比映射（3）獲得求解方案（4）評價6.4 基于實例的學習第62頁，共85頁。圖6.9 基于范例推理的結構6.4 基于實例的學習第63頁，共85頁。在基于范例的學習中要解決的主要問題有 (1) 范例表示 (2) 分析模型 (3) 范例檢索 (4) 類比映射 (5) 類比轉換 (6) 解釋過程 (7) 范例修補 (8) 類比驗證(9) 范例保存 6.4 基于實例的學習第64頁，共85頁。2.范例的表示 一個記憶網便是以語義記憶單元（SMU）為結點，以語義記憶單元間的各種關系為連接建立起來的網絡。 SMU = SMU_NAME slot Con

43、straint slots Taxonomy slots Causality slots Similarity slots Partonomy slots Case slots Theory slots 6.4 基于實例的學習第65頁，共85頁。3范例組織 (1)范例內容 問題或情景描述。是對要求解的問題或要理解的情景的描述，一般要包括這些內容：當范例發生時推理器的目標，完成該目標所要涉及的任務，周圍世界或環境與可能解決方案相關的所有特征。解決方案的內容是問題如何在一特定情形下得到解決。它可能是對問題的簡單解答，也可能是得出解答的推導過程。結果。記錄了實施解決方案后的結果情況，是失敗還是成功。

44、有了結果內容，CBR在給出建議解時有能給出曾經成功地工作的范例，同時也能利用失敗的范例來避免可能會發生的問題。當對問題還缺乏足夠的了解時，通過在范例的表示上加上結果部分能取得較好的效果。6.4 基于實例的學習第66頁，共85頁。 (2)范例索引 建立范例索引有三個原則：索引與具體領域有關。數據庫中的索引是通用的，目的僅僅是追求索引能對數據集合進行平衡的劃分從而使得檢索速度最快；而范例索引則要考慮是否有利于將來的范例檢索，它決定了針對某個具體的問題哪些范例被復用；索引應該有一定的抽象或泛化程度。這樣才能靈活處理以后可能遇到的各種情景，太具體則不能滿足更多的情況；索引應該有一定的具體性。這樣才能在

45、以后被容易地識別出來，太抽象則各個范例之間的差別將被消除。6.4 基于實例的學習第67頁，共85頁。4范例的檢索范例檢索從范例庫(Case Base)中找到一個或多個與當前問題最相似的范例；CBR系統中的知識庫不是以前專家系統中的規則庫，它是由領域專家以前解決過的一些問題組成。范例庫中的每一個范例包括以前問題的一般描述即情景和解法。一個新范例并入范例庫時，同時也建立了關于這個范例的主要特征的索引。當接受了一個求解新問題的要求后，CBR利用相似度知識和特征索引從范例庫中找出與當前問題相關的最佳范例，由于它所回憶的內容，即所得到的范例質量和數量直接影響著問題的解決效果，所以此項工作比較重要。范例檢

46、索通過三個子過程，即特征辯識、初步匹配，最佳選定來實現。6.4 基于實例的學習第68頁，共85頁。5范例的復用(1)替換法 替換法是把舊解中的相關值，做相應替換而形成新解。有重新例化、參數調整、局部搜索、查詢、特定搜索、基于范例的替換等。(2)轉換法 常識轉換法（common-sense transformation）是使用明白易懂的常識性啟發式從舊解中替換、刪除或增加某些組成部分。模型制導修補法（model-guided repair）是另一種轉換法，它是通過因果模型來指導如何轉換。故障診斷中就經常使用這種方法。 6.4 基于實例的學習第69頁，共85頁。5范例的復用(3)特定目標驅動法 特

47、定目標驅動的修正啟發式知識一般通過評價近似解作用，并通過使用基于規則的產生式系統來控制。 (4)派生重演 重演方法則是使用過去的推導出舊解的方法來推導出新解。這種方法關心的是解是如何求出來的。同前面的基于范例替換相比，派生重演使用的則是一種基于范例的修正手段。6.4 基于實例的學習第70頁，共85頁。強化學習(reinforcement learning，又稱再勵學習，評價學習)是一種重要的機器學習方法。根據學習方式的不同，可以把學習算法分為三種類型，即非監督學習(unsupervised learning)、監督學習(supervised leaning)和強化學習。所謂強化學習就是智能系統

48、從環境到行為映射的學習，目的是使獎勵信號(強化信號)函數值最大。強化學習不同于監督學習，主要表現在教師信號上，強化學習中由環境提供的強化信號是對產生動作的好壞作一種評價(通常為標量信號)，而不是告訴強化學習系統RLS(reinforcement learning system)如何去產生正確的動作。由于外部環境提供的信息很少，RLS必須靠自身的經歷進行學習。通過這種方式，RLS在行動-評價的環境中獲得知識，改進行動方案以適應環境強化學習要解決的問題：主體怎樣通過學習選擇能達到其目標的最優動作。當主體在其環境中做出每個動作，施教者提供獎勵或懲罰信息，以表示結果狀態的正確與否。例如，在訓練主體進行

49、棋類對弈時，施教者可在游戲勝利時給出正回報，在游戲失敗時給出負回報，其他時候給出零回報。主體的任務是從這個非直接的有延遲的回報中學習，以便后續動作產生最大的累積回報。6.5 強化學習第71頁，共85頁。6.5.1 強化學習模型si+1ri+1報酬ri主體環境狀態si行動ai 圖6.10 強化學習模型6.5 強化學習第72頁，共85頁。 Agent狀態回報動作 環 境a0a2a1s1s0s2r1r0r2目標：學習選擇動作使下式最大化 r0 + r1 + 2r2 + 其中01Agent 的任務是學習一個控制策略 ：S A 它使這些回報的和的期望值最大。6.5 強化學習第73頁，共85頁。6.5.2 馬爾可夫決策過程基于馬爾科夫決策過程定義學習控制策略問題的一般形式為：主體可感知到其環境的不同狀態集合S，可執行的動作集合A。在每個離散時間步t，主體感知到當前狀態st，選擇當前動作at，環境給出回報函數rt=r(st,at)，并產生后繼狀態函數st+1=(st,at)，此函數也叫狀態轉移函數。在MDP中，函數(st,at)，r(st,at)只依賴于當前動作和狀態，這里先考慮它們為確定性的情形。主體的任務是學習一個策略 ：S A，它基于當前的狀態st選擇下一步動作at，即（st）at，要求此策略對主體產生最大的累積回報。6.5 強化學習第74頁，共85頁。定義1：策略從