1、第5章 機器學習,2020/9/12,人工智能,2,學習能力是人類智能的根本特征。人類通過學習來提高和改進自己的能力。學習的基本機制是把一種情況下成功的表現(xiàn)行為轉移到另一種類似的新情況中。人的認識能力和智慧才能就是在畢生的學習中逐步形成、發(fā)展和完善。任何自然的智能系統(tǒng)都具備學習的能力。 機器學習是繼專家系統(tǒng)之后人工智能應用的又一重要研究領域。本章主要介紹機器學習的有關知識及其主要的幾種學習方法。,2020/9/12,人工智能,3,5.1 機器學習概述 5.2 機械學習 5.3 歸納學習 5.4 類比學習 5.5 解釋學習 5.6 強化學習 5.7 知識發(fā)現(xiàn),本章主要內容：,2020/9/12,

2、人工智能,4,5.1 機器學習概述,什么是學習？ 學習是人類具有的一種重要智能行為，但究竟什么是學習，長期以來卻眾說紛紜。 關于“學習”這一概念的主要觀點： 學習是系統(tǒng)改進其性能的過程。這是西蒙的觀點。 西蒙的觀點：學習就是系統(tǒng)在不斷重復的工作中對本身能力的增強或者改進，使得系統(tǒng)在下一次執(zhí)行同樣任務或類似任務時，會比現(xiàn)在做得更好或效率更高。 學習是獲取知識的過程。這是從事專家系統(tǒng)研究的人們的觀點。 學習是技能的獲取。這是心理學家的觀點。 學習是事物規(guī)律的發(fā)現(xiàn)過程。,2020/9/12,人工智能,5,基本的學習形式有2種： （1）知識獲取和技能求精。 例如，我們說某人學過物理。我們的意思是，此人

3、已經掌握了有關物理學的基本概念，并且理解其含義，同時還懂得這些概念之間以及它們與物理世界之間的關系。 一般地，知識獲取可看作學習新的符號信息，而這些符號信息是以有效方式與應用這種信息的能力相適應的。 （2）第二類學習形式是通過實踐逐步改進機制和認知技能。 學習的很多過程都是由改進所學的技能組成。這些技能包括意識的或者機制的協(xié)調，而這種改進又是通過反復實踐和從失敗的行為中糾正偏差來進行的。例如騎自行車或彈鋼琴等等。 知識獲取的本質可能是一個自覺的過程，其結果產生新的符號知識結構和智力模型。而技能求精則是下意識地借助于反復實踐來實現(xiàn)的。人類的學習一般表現(xiàn)為這兩種活動的結合。,2020/9/12,人

4、工智能,6,5.1.1 機器學習的定義,至今，還沒有統(tǒng)一的“機器學習”定義，而且也很難給出一個公認的和準確的定義。 一般認為機器學習是研究如何使用機器來模擬人類學習活動的一門學科。 更為嚴格的提法是：機器學習是一門研究機器獲取新知識和新技能，并識別現(xiàn)有知識的學問。 最早的具有學習能力的程序： 1959年美國的塞繆爾(Samuel)設計了一個下棋程序，這個程序具有學習能力，它可以在不斷的對奕中改善自己的棋藝。4年后，這個程序戰(zhàn)勝了設計者本人。又過了3年，這個程序戰(zhàn)勝了美國一個保持8年之久的常勝不敗的冠軍。,2020/9/12,人工智能,7,5.1.2 機器學習的發(fā)展史,機器學習的發(fā)展過程大體上可

5、分為4個時期： 1、第一階段是在50年代中葉到60年代中葉，屬于熱烈時期。 在這個時期，所研究的是“沒有知識”的學習，即“無知”學習；其研究目標是各類自組織系統(tǒng)和自適應系統(tǒng)；指導本階段研究的理論基礎是早在40年代就開始研究的神經網絡模型。在這個時期，我國研制了數(shù)字識別學習機。 2、第二階段在60年代中葉至70年代中葉，被稱為機器學習的冷靜時期。 本階段的研究目標是模擬人類的概念學習過程，并采用邏輯結構或圖結構作為機器內部描述。這個時期正是我國“史無前例”的十年，對機器學習的研究不可能取得實質進展。,2020/9/12,人工智能,8,5.1.2 機器學習的發(fā)展史（2）,3、第三階段從70年代中葉

6、至80年代中葉，稱為復興時期。 在這個時期，人們從學習單個概念擴展到學習多個概念，探索不同的學習策略和各種學習方法。 1980年,在美國召開了第一屆國際機器學習研討會;1984年,機器學習雜志問世。 我國于1987年召開了第一屆全國機器學習研討會;1989年成立了以中國科技大學蔡慶生教授為理事長的理事會。 4、機器學習的最新階段始于1986年。 一方面，由于神經網絡研究的重新興起，另一方面，對實驗研究和應用研究得到前所未有的重視。我國的機器學習研究開始進入穩(wěn)步發(fā)展和逐漸繁榮的新時期。,2020/9/12,人工智能,9,機器學習、知識發(fā)現(xiàn)與數(shù)據挖掘,知識發(fā)現(xiàn)(Knowledge Discover

7、ing in Database)與數(shù)據挖掘(Data Mining)是人工智能、機器學習 (Machine Learning)與數(shù)據庫技術相結合的產物。 KDD一詞是在1989年于美國底特律市召開的第一屆KDD國際學術會議上正式形成的。 1995年，在加拿大召開了第一屆知識發(fā)現(xiàn)和數(shù)據挖掘國際學術會議。由于數(shù)據庫中的數(shù)據被形象地喻為礦床，因此數(shù)據挖掘一詞很快流傳開來。 數(shù)據挖掘和知識發(fā)現(xiàn)的研究已形成熱潮，并在生物醫(yī)學、金融管理、商業(yè)銷售等領域得到成功應用，給機器學習注入新的活力。,2020/9/12,人工智能,10,5.1.3 機器學習系統(tǒng)的基本結構,環(huán)境是指系統(tǒng)外部信息的來源，它可以是系統(tǒng)的工

8、作對象，也可以包括工作對象和外界條件。 學習單元處理環(huán)境提供的信息，相當于各種學習算法。學習單元利用環(huán)境提供的信息，并與執(zhí)行單元的反饋信息進行比較，獲取相關知識，對知識庫進行修改。 知識庫用于存放由學習環(huán)節(jié)所得到的知識。知識庫中知識的表示方法可以是：謂詞、產生式、特征向量、神經網絡等。 執(zhí)行單元處理系統(tǒng)所面臨的現(xiàn)實問題，即應用知識庫中的知識求解問題。,機器學習系統(tǒng)的基本結構如圖,2020/9/12,人工智能,11,影響學習系統(tǒng)設計的重要因素,(1) 影響學習系統(tǒng)設計的最重要的因素是環(huán)境向系統(tǒng)提供的信息。更具體地說是信息的質量。 (2) 知識庫是影響學習系統(tǒng)設計的第二個因素。 知識的表示有多種形

9、式，在選擇時要兼顧以下4個方面：,表達能力強。所選擇的表示方式能很容易地表達有關的知識。 易于推理。為了使學習系統(tǒng)的計算代價比較低，希望知識表示方式能使推理較為容易。 容易修改知識庫。學習系統(tǒng)的本質要求它不斷地修改自己的知識庫，當推廣得出一般執(zhí)行規(guī)則后，要加到知識庫中。 知識表示易于擴展。每一個學習系統(tǒng)都要求具有某些知識理解環(huán)境提供的信息，分析比較，做出假設，檢驗并修改這些假設。因此，更確切地說，學習系統(tǒng)是對現(xiàn)有知識的擴展和改進。,2020/9/12,人工智能,12,5.1.4 機器學習的分類,按學習方法分類（溫斯頓在1977年提出的分類方法） 機械式學習：機械學習就是記憶。 指導式學習：采用

10、示教式學習策略，也稱為示教學習。 示例學習：通過工作例子學習。 類比學習：應用類似任務的知識求解當前問題。 解釋學習：根據領域知識對當前實例分析和求解。 按學習的綜合屬性分類（綜合考慮知識表示、推理方法、應用領域等多種因素）： 歸納學習：從個體的特征歸納出它們的共性 分析學習：從領域理論出發(fā)演繹出更有效的規(guī)則。 連接學習：人工神經網絡學習 遺傳學習：模擬自然界遺傳與變異機制,2020/9/12,人工智能,13,5.2 機械學習,機械學習的模式 機械學習是最簡單的機器學習方法。機械學習就是記憶，即把新的知識存儲起來，供需要時檢索調用，而不需要計算和推理。機械學習又是最基本的學習過程。任何學習系統(tǒng)

11、都必須記住它們獲取的知識。在機械學習系統(tǒng)中，知識的獲取是以較為穩(wěn)定和直接的方式進行的，不需要系統(tǒng)進行過多的加工。,2020/9/12,人工智能,14,數(shù)據化簡,Lenat,Hayes Roth，和Klahr等人于1979年關于機械學習提出一種有趣的觀點。他們指出，可以把機械學習看成是數(shù)據化簡分級中的第一級。數(shù)據化簡與計算機語言編譯類似；其目的是把原始信息變成可執(zhí)行的信息。在機械學習中我們只記憶計算的輸入輸出，忽略了計算過程，這樣就把計算問題化簡成存取問題。,2020/9/12,人工智能,15,機械學習的主要問題,對于機械學習，需要注意3個重要的問題：存儲組織，穩(wěn)定性和存儲與計算之間的權衡。 （

12、1）存儲組織信息：采用適當?shù)拇鎯Ψ绞?，使檢索速度盡可能地快，是機械學習中的重要問題。 （2）環(huán)境的穩(wěn)定性與存儲信息的適用性問題：機械學習系統(tǒng)必須保證所保存的信息適應于外界環(huán)境變化的需要，這也就是所謂的信息適用性問題。 （3）存儲與計算之間的權衡：對于機械學習來說很重要的一點是它不能降低系統(tǒng)的效率。,2020/9/12,人工智能,16,5.3 歸納學習,歸納學習是目前研究得最多的學習方法，其學習目的是為了獲得新的概念、構造新的規(guī)則或發(fā)現(xiàn)新的理論。這種方法對領域理論沒有要求，甚至可以沒有領域理論，但其需要大量的訓練例子，而且歸納性能受到描述語言、概念類型、信噪比、實例空間分布、 歸納模式等的影響。

13、 （1）歸納（induction）是人類拓展認識能力的重要方法，是一種從個別到一般的，從部分到整體的推理行為。 （2）歸納推理是應用歸納方法，從足夠多的具體事例中歸納出一般性知識，提取事物的一般規(guī)律；它是一種從個別到一般的推理。 （3）歸納學習（induction learning）是應用歸納推理進行學習的一種方法。根據歸納學習有無教師指導，可把它分為示例學習和觀察與發(fā)現(xiàn)學習。前者屬于有師學習，后者屬于無師學習。,2020/9/12,人工智能,17,5.3.1 歸納學習的模式和規(guī)則,歸納學習的模式,給定： 觀察陳述（事實）F，用以表示有關某些對象、狀態(tài)、過程等的特定知識； 假定的初始歸納斷言（

14、可能為空），是關于目標的泛化項或泛化描述。 背景知識，用于定義有關觀察陳述、候選歸納斷言以及任何相關問題領域知識、假設和約束，其中包括能夠刻畫所求歸納斷言的性質的優(yōu)先準則。 求：歸納斷言（假設）H，能重言蘊涵或弱蘊涵觀察陳述，并滿足背景知識。,2020/9/12,人工智能,18,假設H永真蘊涵事實F，說明F是H的邏輯推理，則有： H | F （讀作H特殊化為F） 或 F | H （讀作F一般化或消解為H） 這里，從H推導F是演繹推理，因此是保真的；而從事實F推導出假設H是歸納推理，因此不是保真的。 歸納學習系統(tǒng)的模型如圖所示。,2020/9/12,人工智能,19,歸納概括規(guī)則,設CTX表示任一

15、描述，K表示結論，則有下列幾條常用的選擇性概括規(guī)則：,(1) 取消部分條件： 設S是對事例的一種限制，這種限制可能不必要，因此可以去除。即： CTXSK = CTXK,(2) 放松條件： 一個事例的原因可能不止一條，當出現(xiàn)新的原因時，應該把新的原因包含進去。 CTX1K = (CTX1CTX2)K,2020/9/12,人工智能,20,(3) 沿概念樹上溯： 設L是一結構性描述項，S代表所有條件中的L值在概念分層樹上最近的共同祖先，則：,(4) 形成閉合區(qū)域： 設L是一個具有顯性關系的描述項，a,b是它的特殊值，則：,(5) 將常量轉化成變量：,2020/9/12,人工智能,21,5.3.2 歸

16、納學習方法,1、示例學習 示例學習（learning from examples）又稱為實例學習，它是通過環(huán)境中若干與某概念有關的例子，經歸納得出一般性概念的一種學習方法。在這種學習方法中，外部環(huán)境提供的是一組例子（正例和反例），示例學習就是要從這些特殊知識中歸納出適用于更大范圍的一般性知識，以覆蓋所有的正例并排除所有反例。 2、觀察發(fā)現(xiàn)學習 觀察發(fā)現(xiàn)學習又稱為描述性概括，其目標是確定一個定律或理論的一般性描述，刻畫觀察集，指定某類對象的性質。觀察發(fā)現(xiàn)學習可分為觀察學習與機器發(fā)現(xiàn)兩種。前者用于對事例進行聚類，形成概念描述；后者用于發(fā)現(xiàn)規(guī)律，產生定律或規(guī)則。,2020/9/12,人工智能,22,

17、5.3.3 歸納學習示例-決策樹學習,決策樹學習是應用最廣的歸納推理算法之一。它是一種逼近離散值函數(shù)的方法。在這種方法中學習到的函數(shù)被表示為一顆決策樹。學習得到的決策樹也能再被表示為多個if-then規(guī)則，以提高可讀性。 決策樹學習方法對噪聲數(shù)據有很好的健壯性且能夠學習析取表達式。決策樹學習算法有很多，比如ID3、C4.5、ASSISTANT等等。這些決策樹學習方法搜索一個完整表示的假設空間，從而避免了受限假設空間的不足。決策樹學習的歸納偏置是優(yōu)先選擇較小的樹。,2020/9/12,人工智能,23,決策樹表示法,決策樹通過把實例從根節(jié)點排列(sort)到某個葉子節(jié)點來分類實例，葉子節(jié)點即為實例

18、所屬的分類。樹上的每一個節(jié)點說明了對實例的某個屬性(attribute)的測試，并且該節(jié)點的每一個后繼分枝對應于該屬性的一個可能值。 分類實例的方法是從這顆樹的根節(jié)點開始，測試這個節(jié)點指定的屬性，然后按照給定實例的該屬性值對應的樹枝向下移動。然后這個過程再以新節(jié)點為根的子樹上重復。,例子：在一個水果的分類問題中，采用的特征向量為：顏色,尺寸,形狀,味道，其中：顏色取值為紅,綠,黃，尺寸取值為大,中,小，味道取值為甜,酸，形狀取值為圓,細。 樣本集：一批水果，知道其特征向量及類別 問 題：一個新的水果，觀測到了其特征向量，將其分類,2020/9/12,人工智能,24,2020/9/12,人工智能

19、,25,通常決策樹代表實例屬性值約束的合取(conjunction)的析取式(disjunction)。從樹根到樹葉的每一條路徑對應一組屬性測試的合取，樹本身對應這些合取的析取。 上述例子可對應如下析取式： (color=greensize=big) (color=greensize=medium) (color=greensize=small) (color=yellowshape=roundsize=big) (color=yellowshape=roundsize=small) (color=yellowshape=thin) (color=redsize=medium) (color=

20、redsize=smalltaste=sweet) (color=redsize=smalltaste=sour),2020/9/12,人工智能,26,決策樹的適用問題,決策樹學習適合解決具有以下特征的問題 實例是由“屬性-值”對表示的：實例是用一系列固定的屬性和它們的值來描述的。 目標函數(shù)具有離散的輸出值：決策樹給每個實例賦予一個布爾型的分類。決策樹方法很容易擴展到學習有兩個以上輸出值的函數(shù)。 可能需要析取的描述：決策樹很自然地代表了析取表達式。 訓練數(shù)據可以包含錯誤：決策樹學習對錯誤有很好的健壯性，無論是訓練樣例所屬的分類錯誤，還是描述這些樣例的屬性值錯誤。 訓練數(shù)據可以包含缺少屬性值的實

21、例：決策樹甚至可以再有未知屬性值的訓練樣例中使用。,2020/9/12,人工智能,27,決策樹學習的常見問題,確定決策樹增長的深度，避免過度擬合； 處理連續(xù)值的屬性； 選擇一個適當?shù)膶傩院Y選度量標準； 處理屬性值不完整的訓練數(shù)據； 處理不同代價的屬性； 提高計算效率。,2020/9/12,人工智能,28,ID3算法,大多數(shù)已開發(fā)的決策樹學習算法是一種核心算法（CLS算法）的變體。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。這種方法是ID3算法(Quinlan 1986)和后繼的C4.5(Quinlan 1993)的基礎。 ID3是一種自頂向下增長樹的貪婪算法，在每個節(jié)點選取能最好分類樣例

22、的屬性。繼續(xù)這個過程指導這棵樹能完美分類訓練樣例，或所有的屬性都已被使用過。 構造過程是從“哪一個屬性將在樹的根節(jié)點被測試”這個問題開始。為了回答這個問題，使用統(tǒng)計測試來確定每一個實例屬性單獨分類訓練樣例的能力。分類能力最好的屬性被選作樹的根節(jié)點的測試。然后為根節(jié)點屬性的每個可能值產生一個分枝，并把訓練樣例排列到適當?shù)姆种Γㄒ簿褪?，樣例的該屬性值對應的分枝）之下。然后重復整個過程，用每個分枝節(jié)點關聯(lián)的訓練樣例來選取在該點被測試的最佳屬性。這形成了對合格決策樹的貪婪搜索，也就是算法從不回溯重新考慮以前的選擇。,2020/9/12,人工智能,29,決策樹的構建,已知訓練樣本集，構造決策樹需要解決以

23、下幾個問題（考慮Binary Decision Trees）： （1）最佳提問的選擇：應該先對哪一個屬性提出問題？應該按什么樣的順序提出問題？ 每一個問題都是一個YES/NO問題。 （2）葉結點的確定：什么時候可以結束提問，并判定模式的類別？ （3）決策樹修剪：如果決策樹過大，應該如何修剪決策樹，以保證其泛化能力？,2020/9/12,人工智能,30,最佳提問的選擇（1）,（1）決策樹中的每一個結點（葉結點除外）對應于一個提問。每一個葉結點給出最終的分類。決策樹的構建從根結點開始。 （2）根結點的構建：根結點對應于訓練樣本集D。通過選擇針對某一屬性的一個問題進行提問，可以根據對該問題的回答，將

24、訓練樣本集D分類兩個部分：Dy及Dn （其中， Dy為回答YES的樣本， Dn為回答NO的樣本） ，并建立與之相對應的兩個子結點。我們希望選擇一個這樣問題進行提問：使得Dy及Dn盡可能純凈。 （3）中間結點的構造：對于每一個中間結點（結點N），都有一個與之對應的子集DN。同樣，根據結點N的提問，可以將DN進一步劃分為兩個部分DNy及DNn（其中， DNy為回答YES的樣本， DNn為回答NO的樣本），并得到與之相對應的兩個子結點。我們希望根據結點N提出的問題，能夠使DNy及DNn盡可能純凈。,2020/9/12,人工智能,31,最佳提問的選擇（2）,（4）當如上得到的某一個子結點足夠純凈時，就

25、可以確定該結點為葉結點，并給出其類別。 （5）當決策樹中的每一條路徑都對應于一個葉結點時，學習過程結束，決策樹構建完畢。 （6）根據上述準則（純凈度準則）構建決策樹，可以保證決策樹的復雜度較?。ńY點數(shù)量少、深度?。?。 （7）在對訓練集分類能力相近的條件下，復雜度小的決策樹（分類器）優(yōu)于復雜度大的決策樹（分類器）。復雜度小的分類器通常具有較好的泛化能力。這一原則稱為Occams razor。,2020/9/12,人工智能,32,最佳提問的選擇（3）,（8）結點n非純凈度的定義,其中，i(n)為結點n的非純凈度，Nn 為結點n對應的樣本的數(shù)量，Njn為結點n中屬于j的樣本的數(shù)量，C為類別的個數(shù)。,

26、2020/9/12,人工智能,33,最佳提問的選擇（4）,其中，ny為結點n的YES子結點，nn 為NO子結點，Nny為YES子結點對應的樣本的數(shù)量，Nnn為NO子結點對應的樣本的數(shù)量。 結點n的最佳選擇問題：使i(n)取得最大值。,（9）結點n最佳問題的選擇： 對于結點n，通過提出并回答某個問題，可以得到如下的純凈度的提高（不純凈度的降低）：,2020/9/12,人工智能,34,最佳提問的選擇（5）,（10）結點n最佳問題的選擇范圍： 需要枚舉出所有可以提出的問題，從中選出有效的問題，并在這些有效的問題中選擇一個最佳的問題。 由于特征的數(shù)量是有限的，每個特征的可能取值也是有限的，所以所有可能

27、提出的問題是可以枚舉的。 所提問題通常限制為針對某個特征提出的簡單問題，問題的形式如前面的二叉數(shù)所示。,2020/9/12,人工智能,35,葉結點的確定問題,決策樹結點劃分的原則是使其子結點盡可能純凈（指兩個子結點的平均純凈度最高）。對于任意一個結點n，可以出現(xiàn)以下三種情況： （1）結點n中的樣本屬于同一類，即結點n絕對純凈。此時結點n不可進一步劃分。 （2）結點n中的樣本不屬于同一類，但是不存在任何一個劃分（即提出一個問題并根據該問題對結點n的樣本進行劃分）可以使其子結點的平均純凈度高于結點n。此時結點n不可進一步劃分。 （3）可以提出一個問題對結點n進行劃分，從而使結點n的子結點具有更高的

28、純凈度。此時結點n可以進一步劃分。,2020/9/12,人工智能,36,葉結點的確定問題,問題：在構建決策樹的過程中，確定葉節(jié)點的一個策略是：對于每一個可以進一步劃分的結點都進行劃分，直到得到一個不可劃分的子結點，并將該子結點定為葉結點。這樣構造的決策樹，其葉結點均為不可再進一步劃分的結點。這種葉結點的確定方法是否可行？ 答案：決策樹是根據訓練樣本的集合構成的。該集合中的樣本是隨機的。不同的隨機實驗會得到不同的樣本集合。因此，該集合并不能完全描述樣本(即特征向量)真實分布。當葉結點按上述方法確定時，所得決策樹雖然對訓練樣本集合給出了最優(yōu)的分類，但是卻背離了樣本的真實分布，因此削弱了對未來新樣本

29、的分類能力。這一現(xiàn)象稱為過度擬合(指決策數(shù)對訓練樣本過度擬合，從而背離了樣本的真實分布)。,2020/9/12,人工智能,37,葉結點確定的基本思路,（1）并不絕追求對訓練樣本的正確劃分。并不絕對追求葉結點的純凈度。絕對追求葉結點的純凈度導致過度擬合。此時決策樹的復雜度偏高。 （2）要適度保證葉結點的純凈度，適度保證對訓練樣本的正確分類能力。葉結點的不純凈度過高，對訓練樣本的正確分類能力過低稱為欠學習（此時，決策樹不能夠充分提取樣本集合中蘊涵的有關樣本真實分布的信息。欠學習同樣不能保證對未來新樣本的正確分類能力）。此時決策樹的復雜度偏低。 （3）因此，在決策樹的構建過程中，需要在過度擬合與欠學

30、習之間尋求合理的平衡，即尋求復雜度適中的決策樹。具體方法為：在結點還可以進一步劃分的時候，可根據預先設定的準則停止對其劃分，并將其設置為葉結點。,2020/9/12,人工智能,38,確定葉結點的基本方法（1）,方法1：采用測試集的方法。將樣本集合分為訓練集與測試集。根據訓練集構建決策樹，決策樹中的結點逐層展開。每展開一層子結點，并將其設為葉結點，就得到一棵決策樹，然后采用測試集對所得決策樹的分類性能進行統(tǒng)計。重復上述過程，可以得到決策樹在測試集上的學習曲線。根據學習曲線，選擇在測試集上性能最佳的決策樹為最終的決策樹。 方法2：在決策樹開始訓練以前，首先設定一個閾值A。在決策樹的訓練過程中，對于

31、任意一個結點n，如果該結點的最優(yōu)劃分（即最優(yōu)問題對該結點的樣本集合所作的劃分）所導致的純凈度的提高小于A，則將該結點定為葉結點。采用該方法不需要將樣本集合分為訓練集及測試集。決策樹直接采用全體樣本集合構建。,2020/9/12,人工智能,39,確定葉結點的基本方法（2）,方法3：在決策樹開始訓練以前，首先設定一個閾值A。在決策樹的訓練過程中，對于任意一個結點n，如果Nn/NA，則確定結點n為葉結點。其中，Nn為結點n對應的樣本的數(shù)量，N 為全體樣本的數(shù)量。采用該方法同樣不需要將樣本集合分為訓練集及測試集。決策樹直接采用全體樣本集合構建。 方法4：采用如下的性能準則函數(shù)：,其中size 代表決策

32、樹的復雜度，i(n)為結點n 的非純凈度。該準則函數(shù)表達出了過度擬合與欠學習之間的相互關系。決策樹的優(yōu)化準則為：使該準則函數(shù)取得最小值。,2020/9/12,人工智能,40,決策樹修剪（1）,決策樹的修剪是決策樹學習的另外一種有效的方法。其基本思路是，首先使決策樹得到充分生長，然后再通過修剪降低決策樹的復雜度，從而保證決策樹的泛化能力。具體方法如下： （1）決策樹的構建：在決策樹的構建過程中，對于每一個可以進一步劃分的結點都進行劃分，直到得到一個不可進一步劃分的子結點，并將該子結點定為葉結點。這樣構造的決策樹，其葉結點均為不可再進一步劃分的結點。,2020/9/12,人工智能,41,決策樹修剪

33、（2）,（2）在上述決策樹構建完畢后，從葉結點一層開始，考察兄弟葉結點是否可以合并。如果可以合并，則對這些兄弟結點進行合并，并將其父結點設為葉結點。在對所有可以合并的兄弟葉結點進行合并后，可以形成一棵新的決策樹。對于新形成的決策樹，可以重復上述兄弟結點的合并過程，直到最后得到一棵決策樹，其中任意兩個兄弟葉結點都不再滿足合并的條件。這棵決策樹，就是我們最終選擇的決策樹。,2020/9/12,人工智能,42,決策樹修剪（3）,（3）兄弟葉結點合并的條件為,其中，ny及nn為兄弟葉結點，n為其父結點。Nn 為父結點中樣本的數(shù)量，Nny及Nnn 為兩個子結點中樣本的數(shù)量。 上述合并條件中，i(n)代表

34、了由于合并所導致的不純凈度的損失。A為閾值，在修剪過程開始前預先設定。,葉結點的類別,設分類問題為C類的分類問題。對于葉結點n，如果在該結點對應的樣本中，屬于第 i 類的樣本數(shù)量最多，則判該葉結點為第i類。,2020/9/12,人工智能,43,討論,（1）根據決策樹可以得出若干條規(guī)則。一條從根結點到葉結點的路途對應于一條IF-THEN規(guī)則。其中，路徑的非葉結點部分構成了規(guī)則的條件部分（IF部分），葉結點給出了規(guī)則的結論（THEN部分）。 例子：IF COLOR=RED AND SIZE=MEDIUM THEN IT IS AN APPLE 用途：知識的獲取。 （2）決策樹方法同樣可用于連續(xù)取值

35、的特征量。當特征向量空間為歐氏空間時，同樣可以采用決策樹方法來構造分類器。當然，一般情況下在歐氏空間中通常采用神經網絡來構造分類器。,2020/9/12,人工智能,44,5.4 類比學習,類比(analogy)是一種很有用的和有效的推理方法，它能夠清晰簡潔地描述對象間的相似性；也是人類認識世界的一種重要方法。 類比學習(learning by analogy)就是通過類比，即通過相似事物加以比較所進行的一種學習。 例如，當人們遇到一個新問題需要進行處理，但又不具備處理這個問題的知識時，通常采用的辦法就是回憶一下過去處理過的類似問題，找出一個與目前情況最接近的處理方法來處理當前問題。,2020/

36、9/12,人工智能,45,5.4.1 類比推理和類比學習,類比推理,類比推理是由新情況與已知情況在某些方面的相似來推出它們在其它相關方面的相似。顯然，類比推理是在兩個相似域之間進行的：類比推理的目的是從源域中選出與當前問題最近似的問題及其求解方法以求解決當前的問題，或者建立起目標域中已有命題間的聯(lián)系，形成新知識。 類比推理過程如下： (1) 回憶與聯(lián)想 遇到新情況或新問題時，首先通過回憶與聯(lián)想在S中找出與當前情況相似的情況，這些情況是過去已經處理過的，有現(xiàn)成的解決方法及相關的知識。,2020/9/12,人工智能,46,(2) 選擇 從找出的相似情況中選出與當前情況最相似的情況及其有關知識。 (

37、3) 建立對應映射 在S與T的相似情況之間建立相似元素的對應關系，并建立起相應的映射。 (4) 轉換 在上一步建立的映射下，把S中的有關知識引到T中來，從而建立起求解當前問題的方法或者學習到關于T的新知識。,2020/9/12,人工智能,47,類比學習,類比學習是基于類比推理的。類比學習的過程主要分為兩步：首先歸納找出源問題和目標問題的公共性質，然后再演繹推出從源問題到目標問題的映射，得出目標問題的新的性質。所以類比學習既有歸納過程，又有演繹過程。 類比學習的主要過程可描述如下：,(1) 輸入一組已知條件（已解決問題）和一組未完全確定的條件（新問題）。 (2) 對輸入的兩組條件，根據其描述，按

38、某種相似性的定義尋找兩者可類比的對應關系。 (3) 按相似變換的方法，將已有問題的概念、特性、方法、關系等映射到新問題上，以獲得待求解新問題所需的新知識。 (4) 對類推得到的新問題的知識進行校驗。驗證正確的知識存入知識庫中，而暫時還無法驗證的知識只能作為參考性知識，置于數(shù)據庫中。,2020/9/12,人工智能,48,5.4.2 基于范例的學習,范例（case）：“范例是一段帶有上下文信息的知識，該知識表達了推理機在達到其目標的過程中能起關鍵作用的經驗”。具體來說，一個范例應具有如下特性：,范例表示了與某個上下文有關的具體知識，這種知識具有可操作性。 范例可以是各式各樣的，可有不同的形狀和粒度

39、，可涵蓋或大或小的時間片，可帶有問題的解答或動作執(zhí)行后的效應。 范例記錄了有用的經驗，這種經驗能幫助推理機在未來更容易地達到目標，或提醒推理機失敗發(fā)生的可能性有多大等等。,2020/9/12,人工智能,49,基于范例的推理,人們?yōu)榱私鉀Q一個新問題，先是進行回憶，從記憶中找到一個與新問題相似的范例，然后把該范例中的有關信息和知識復用到新問題的求解之中。這種推理就是基于范例的推理(Case-Based Reasoning, CBR)，也簡稱為范例推理。 在基于范例推理中，把當前所面臨的問題或情況稱為目標范例(target case)，而把記憶的問題或情況稱為源范例(base case)。粗略地說，

40、基于范例推理就是由目標范例的提示而獲得記憶中的源范例，并由源范例來指導目標范例求解的一種策略。,2020/9/12,人工智能,50,范例推理基本流程,2020/9/12,人工智能,51,基于范例推理中知識表示是以范例為基礎，范例的獲取比規(guī)則獲取要容易，大大簡化知識獲取。 對過去的求解結果進行復用，而不是再次從頭推導，可以提高對新問題的求解效率。 過去求解成功或失敗的經歷可以指導當前求解時該怎樣走向成功或避開失敗，這樣可以改善求解的質量。 對于那些目前沒有或根本不存在的問題，可以通過計算推導來解決的問題。如在法律中的判例，基于范例推理能很好發(fā)揮作用。,范例推理的特點,2020/9/12,人工智能

41、,52,基于范例的學習,基于范例的推理系統(tǒng)經過不斷的積累經驗（案例），同時合適地對其進行索引，系統(tǒng)的推理效率和問題求解能力會隨之增加。因此在CBR中，學習的主要任務是對案例庫的豐富和優(yōu)化。 在CBR中，大多數(shù)學習是通過如下兩種方式體現(xiàn)的：一個是新范例的積累，推理系統(tǒng)的范例對問題的覆蓋越多，其功能越強；另一個是設計覆蓋了成功事例也覆蓋了失敗事例的推理要比只設計成功情況的推理系統(tǒng)要好，索引的重新賦值，調節(jié)索引可使得范例能在更合適的時機被回憶。,2020/9/12,人工智能,53,基于范例學習的一般過程,2020/9/12,人工智能,54,范例的內容,(1) 問題或情景描述：是對要求解的問題或要理解

42、的情景的描述，一般要包括這些內容：當范例發(fā)生時推理器的目標，完成該目標所要涉及的任務，周圍世界或環(huán)境與可能解決方案相關的所有特征。 (2) 解決方案：是問題如何在一特定情形下得到解決。它可能是對問題的簡單解答，也可能是得出解答的推導過程。 (3) 結果：記錄了實施解決方案后的結果情況，是失敗還是成功。有了結果內容，CBR在給出建議解時有能給出曾經成功地工作的范例，同時也能利用失敗的范例來避免可能會發(fā)生的問題。當對問題還缺乏足夠的了解時，通過在范例的表示上加上結果部分能取得較好的效果。,2020/9/12,人工智能,55,范例的索引,建立范例索引有三個原則： 索引與具體領域有關。數(shù)據庫中的索引是

43、通用的，目的僅僅是追求索引能對數(shù)據集合進行平衡的劃分從而使得檢索速度最快；而范例索引則要考慮是否有利于將來的范例檢索，它決定了針對某個具體的問題哪些范例被復用； 索引應該有一定的抽象或泛化程度，這樣才能靈活處理以后可能遇到的各種情景，太具體則不能滿足更多的情況； 索引應該有一定的具體性，這樣才能在以后被容易地識別出來，太抽象則各個范例之間的差別將被消除。,2020/9/12,人工智能,56,范例學習的主要問題（1）,(1) 范例表示：基于范例推理方法的效率和范例表示緊密相關。范例表示涉及這樣幾個問題: 選擇什么信息存放在一個范例中；如何選擇合適的范例內容描述結構；范例庫如何組織和索引。對于那些

44、數(shù)量達到成千上萬、而且十分復雜的范例, 組織和索引問題尤其重要。 (2) 分析模型：分析模型用于分析目標范例，從中識別和抽取檢索源范例庫的信息。 (3) 范例檢索：利用檢索信息從源范例庫中檢索并選擇潛在可用的源范例。這步非常關鍵。一般講，范例匹配不是精確的，只能是部分匹配或近似匹配。因此，它要求有一個相似度的評價標準。該標準定義得好，會使得檢索出的范例十分有用，否則將會嚴重影響后面的過程。,2020/9/12,人工智能,57,范例學習的主要問題（2）,(4) 類比映射: 尋找目標范例同源范例之間的對應關系。 (5) 類比轉換: 轉換源范例中同目標范例相關的信息，以便應用于目標范例的求解過程中。

45、把檢索到的源范例的解答復用于新問題或新范例之中需要解決的問題分別是：源范例與目標范例間有何不同之處；源范例中的哪些部分可以用于目標范例。需要根據它們之間的不同對復用的求解方案進行調整。 (6) 解釋過程: 對把轉換過的源范例的求解方案應用到目標范例時所出現(xiàn)的失敗做出解釋，給出失敗的因果分析報告。有時對成功也同樣做出解釋?；诮忉尩乃饕彩且环N重要的方法。 (7) 范例修補: 有些類似于類比轉換，區(qū)別在于修補過程的輸入是解方案和一個失敗報告，而且也許還包含一個解釋，然后修改這個解以排除失敗的因素。,2020/9/12,人工智能,58,范例學習的主要問題（3）,(8) 類比驗證: 驗證目標范例和源

46、范例進行類比的有效性。 (9) 范例保存: 新問題得到了解決，則形成了一個可能用于將來情形與之相似的問題。這時有必要把它加入到范例庫中。這是學習也是知識獲取。此過程涉及選取哪些信息保留，以及如何把新范例有機集成到范例庫中。修改和精化源范例庫, 其中包括泛化和抽象等過程。 在決定選取范例的哪些信息進行保留時，一般要考慮以下幾點：和問題有關的特征描述；問題的求解結果；以及解答為什么成功或失敗的原因及解釋。 把新范例加入到范例庫中， 需要對它建立有效的索引，這樣以后才能對之作出有效的回憶。為此，可能要對范例庫的索引內容甚至結構進行調整，如改變索引的強度或特征權值。,2020/9/12,人工智能,59

47、,5.5 解釋學習,基于解釋的學習： 一種從單個觀察中抽象出通用規(guī)則的方法 目標是下次可以快速地解決類似的問題 通過保存結果和避免從零開始解決問題來提高速度 更進一步EBL從觀察到規(guī)則,解釋學習(Explanation-Based Learning, 簡稱EBL)是一種分析學習方法，在領域知識指導下, 通過對單個問題求解實例的分析, 構造出求解過程的因果解釋結構, 并獲取控制知識,以便用于指導以后求解類似問題。,2020/9/12,人工智能,60,解釋學習過程和算法,解釋學習一般包括下列3個步驟： (1) 利用基于解釋的方法對訓練例子進行分析與解釋。 (2) 對例子的結構進行概括性解釋。 (3

48、) 從解釋結構中識別出訓練例子的特性，獲取一般控制知識。 1986年米切爾（Mitchell）等人為基于解釋的學習提出了一個統(tǒng)一的算法EBG，該算法建立了基于解釋的概括過程，并運用知識的邏輯表示和演繹推理進行問題求解。下圖表示EBG問題。,2020/9/12,人工智能,61,EBG求解問題的形式描述: 給定： (1) 目標概念描述TC； (2) 訓練實例TE； (3) 領域知識DT； (4) 操作準則OC。 求解：訓練實例的一般化概括，使之滿足： (1) 目標概念的充分概括描述TC； (2) 操作準則OC。,圖 EBG問題,2020/9/12,人工智能,62,5.6 強化學習,強化學習(rei

49、nforcement learning-RL，又稱再勵學習，評價學習) 在智能控制機器人及分析預測等領域有許多應用。 在傳統(tǒng)的機器學習分類中沒有提及到過強化學習。而在連接主義學習中，把學習算法分為非監(jiān)督學習(unsupervised learning) 、監(jiān)督學習(supervised learning) 和強化學習三種。 所謂強化學習就是智能系統(tǒng)從環(huán)境到行為映射的學習，以使獎勵信號(強化信號) 函數(shù)值最大。 強化學習不同于連接主義學習中的監(jiān)督學習，主要表現(xiàn)在教師信號上，強化學習中由環(huán)境提供的強化信號是對產生動作的好壞作一種評價(通常為標量信號) ，而不是告訴強化學習系統(tǒng)如何去產生正確的動作。

50、,2020/9/12,人工智能,63,強化學習通常包括兩個方面的含義： 一方面是將強化學習作為一類問題； 另一方面是指解決這類問題的一種技術。,如果將強化學習作為一類問題，目前的學習技術大致可分成兩類： 其一是搜索智能系統(tǒng)的行為空間，以發(fā)現(xiàn)系統(tǒng)最優(yōu)的行為。典型的技術如遺傳算法等搜索技術； 另一類是采用統(tǒng)計技術和動態(tài)規(guī)劃方法來估計在某一環(huán)境狀態(tài)下的行為的效用函數(shù)值，從而通過行為效用函數(shù)來確定最優(yōu)行為。 我們特指這種學習技術為強化學習技術。,2020/9/12,人工智能,64,強化學習的產生與發(fā)展,強化思想最先來源于心理學的研究。1911年Thorndike提出了效果律（Law of Effect

51、）：一定情景下讓動物感到舒服的行為，就會與此情景增強聯(lián)系（強化），當此情景再現(xiàn)時，動物的這種行為也更易再現(xiàn)；相反，讓動物感覺不舒服的行為，會減弱與情景的聯(lián)系，此情景再現(xiàn)時，此行為將很難再現(xiàn)。換個說法，哪種行為會“記住”，會與刺激建立聯(lián)系，取決于行為產生的效果。 動物的試錯學習，包含兩個含義：選擇和聯(lián)系，對應計算上的搜索和記憶。所以，1954年，Minsky在他的博士論文中實現(xiàn)了計算上的試錯學習。同年，F(xiàn)arley和Clark也在計算上對它進行了研究。強化學習一詞最早出現(xiàn)于科技文獻是1961年Minsky 的論文“Steps Toward Artificial Intelligence”，此后開

52、始廣泛使用。1969年， Minsky因在人工智能方面的貢獻而獲得計算機圖靈獎。,2020/9/12,人工智能,65,強化學習的發(fā)展過程可粗略分為兩個階段：,強化學習的形成階段（50 年代60年代） Minsky首次提出“強化”和“強化學習”這些術語； Samuel的下棋程序采用類似值迭代、瞬時差分和Q 學習的訓練機制，來學習用線性函數(shù)表示的值函數(shù)； Saridis 把強化控制系統(tǒng)的控制器看成一個隨機自動機，首次系統(tǒng)提出了采用強化學習來解決隨機控制系統(tǒng)的學習控制問題。 強化學習的發(fā)展階段（70 年代 ） 1972年，Klopf把試錯學習和時序差分結合在一起。1978年開始，Sutton、Bar

53、to、 Moore等對這兩者結合開始進行深入研究。 1989年Watkins提出了Q-學習，也把強化學習的三條主線扭在了一起。 1992年，Tesauro用強化學習成功了應用到西洋雙陸棋中，稱為TD-Gammon 。,2020/9/12,人工智能,66,5.6.1 強化學習的原理,強化學習把學習看作試探過程，基本過程如圖所示。在強化學習中，Agent 選擇一個動作作用于環(huán)境，環(huán)境接收該動作后發(fā)生變化，同時產生一個強化信號（獎或罰）反饋給Agent，Agent 再根據強化信號和環(huán)境的當前狀態(tài)再選擇下一個動作，選擇的原則是使受到正的報酬的概率增大。選擇的動作不僅影響立即強化值而且還影響下一時刻的狀

54、態(tài)及最終強化值。強化學習的目的就是尋找一個最優(yōu)策。,1、強化學習的結構,2020/9/12,人工智能,67,強化學習模型由以下部分組成：,2、強化學習模型,一個離散的狀態(tài)集S = s0 , s1 , s2 , , sn ； 動作集A= a0 , a1 , a2 , , an ； 一個強化值集r R； agent 和環(huán)境交互的狀態(tài)動作序列 (si,ai) ri，表示agent 在狀態(tài)si 下執(zhí)行動作ai 獲得的立即獎賞值ri。 agent 執(zhí)行一個動作除了獲得立即獎賞信號外，還有從后續(xù)狀態(tài)動作映射的延遲獎賞。agent 獲得的總獎賞值為:,其中0,1 為折扣因子。 Agent 的任務就是學習控制

55、策略: S A，能夠最大化期望獎賞值的總和。,2020/9/12,人工智能,68,強化學習技術的基本原理是：如果系統(tǒng)某個動作導致環(huán)境正的獎賞，那么系統(tǒng)以后產生這個動作的趨勢便會加強。反之系統(tǒng)產生這個動作的趨勢便減弱。這和生理學中的條件反射原理是接近的。 如果假定環(huán)境是馬爾可夫型的，則順序型強化學習問題可以通過馬氏決策過程（Markov Decision Process，MDP）建模。下面首先給出馬氏決策過程的形式化定義。 馬氏決策過程 由四元組定義。包含一個環(huán)境狀態(tài)集S，系統(tǒng)行為集合A，獎賞函數(shù)R：SA 和狀態(tài)轉移函數(shù)P：SAPD(S)。記R(s, a, s)為系統(tǒng)在狀態(tài)s采用a動作使環(huán)境狀態(tài)

56、轉移到s獲得的瞬時獎賞值，簡記為Rass；記P(s, a, s)為系統(tǒng)在狀態(tài)s采用a動作使環(huán)境狀態(tài)轉移到s的概率，簡記為Pass 。,2020/9/12,人工智能,69,馬氏決策過程的本質是：當前狀態(tài)向下一狀態(tài)轉移的概率和獎賞值只取決于當前狀態(tài)和選擇的動作，而與歷史狀態(tài)和歷史動作無關。因此在已知狀態(tài)轉移概率函數(shù)P和獎賞函數(shù)R的環(huán)境模型知識下，可以采用動態(tài)規(guī)劃技術求解最優(yōu)策略。 而強化學習著重研究在P函數(shù)和R函數(shù)未知的情況下，系統(tǒng)如何學習最優(yōu)行為策略。 由于模型中P函數(shù)和R函數(shù)未知，系統(tǒng)只能夠依賴于每次試錯所獲得的瞬時獎賞來選擇策略。但由于在選擇行為策略過程中，要考慮到環(huán)境模型的不確定性和目標的

57、長遠性，因此在策略和瞬時獎賞之間構造值函數(shù)（即狀態(tài)的效用函數(shù)），用于策略的選擇。,2020/9/12,人工智能,70,首先通過下式構造一個返回函數(shù)Rt，用于反映系統(tǒng)在某個策略指導下的一次學習循環(huán)中，從st狀態(tài)往后所獲得的所有獎賞的累計折扣和。,由于環(huán)境是不確定的，系統(tǒng)在某個策略指導下的每一次學習循環(huán)中所得到的Rt有可能是不同的。因此在s狀態(tài)下的值函數(shù)要考慮不同學習循環(huán)中所有返回函數(shù)的數(shù)學期望。因此在策略下，系統(tǒng)在s狀態(tài)下的值函數(shù)由下式定義，其反映了如果系統(tǒng)遵循策略，所能獲得的期望的累計獎賞折扣和。,2020/9/12,人工智能,71,根據Bellman最優(yōu)策略公式，在最優(yōu)策略*下，系統(tǒng)在s狀態(tài)

58、下的值函數(shù)定義為：,所以，強化學習的任務就是求解* 。,由于強化學習中，P函數(shù)和R函數(shù)未知，系統(tǒng)無法直接求解上面的值函數(shù)。因而實際中常采用逼近的方法進行值函數(shù)的估計 ，其中最主要的方法之一是Monte Carlo采樣 。,2020/9/12,人工智能,72,5.6.2 強化學習算法,到目前為止，研究者們提出了很多強化學習算法，近年來對強化學習算法的研究已由算法本身逐漸轉向研究經典算法在各種復雜環(huán)境中的應用，較有影響的強化學習算法有TD 算法，Q 學習算法，Sarsa算法，Dyan 算法，R 學習算法，H 學習等，還有一些改進算法，如滯后更新多步Q-學習算法等。,2020/9/12,人工智能,7

59、3,1、蒙特卡羅算法,蒙特卡羅算法( Monte Carlo method , MC)通過評估值函數(shù)來發(fā)現(xiàn)最優(yōu)策略，且不需要環(huán)境的全部信息，它只需要經驗知識。如部分有關狀態(tài)序列、動作行為集以及同環(huán)境交互產生的獎賞值的信息。 MC算法基于平均化取樣回報來解決強化學習問題，它將解決的問題分解成幕( episode) 。當環(huán)境狀態(tài)為終止狀態(tài)時，將得到積累回報賦予開始狀態(tài)s 的值函數(shù)V。 從s 出發(fā)到終止狀態(tài)t 的過程中，s 可能不止出現(xiàn)一次。 對s 的值函數(shù)的更新有兩種方法： (1) first visit MC 將回報賦予第一次訪問的s； (2) every visit MC 將每次訪問s 到t 的回報平均后賦予s。,2020/9/12,人工智能,74,MC算法中，值函數(shù)更新規(guī)則為：,其中，Rt 為t 時刻的獎賞值，為步長參數(shù)?？刂七^程采用貪心搜索策略。,2020/9/12,人工智能,75,2、瞬時