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

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

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

3、關(guān)物理學(xué)的基本概念，并且理解其含義，同時還懂得這些概念之間以及它們與物理世界之間的關(guān)系。 一般地，知識獲取可看作學(xué)習(xí)新的符號信息，而這些符號信息是以有效方式與應(yīng)用這種信息的能力相適應(yīng)的。（2）第二類學(xué)習(xí)形式是通過實踐逐步改進機制和認(rèn)知技能。 學(xué)習(xí)的很多過程都是由改進所學(xué)的技能組成。這些技能包括意識的或者機制的協(xié)調(diào)，而這種改進又是通過反復(fù)實踐和從失敗的行為中糾正偏差來進行的。例如騎自行車或彈鋼琴等等。 知識獲取的本質(zhì)可能是一個自覺的過程，其結(jié)果產(chǎn)生新的符號知識結(jié)構(gòu)和智力模型。而技能求精則是下意識地借助于反復(fù)實踐來實現(xiàn)的。人類的學(xué)習(xí)一般表現(xiàn)為這兩種活動的結(jié)合。2022/8/85人工智能第5頁，共1

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

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

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

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

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

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

10、憶。 指導(dǎo)式學(xué)習(xí)：采用示教式學(xué)習(xí)策略，也稱為示教學(xué)習(xí)。 示例學(xué)習(xí)：通過工作例子學(xué)習(xí)。 類比學(xué)習(xí)：應(yīng)用類似任務(wù)的知識求解當(dāng)前問題。 解釋學(xué)習(xí)：根據(jù)領(lǐng)域知識對當(dāng)前實例分析和求解。按學(xué)習(xí)的綜合屬性分類（綜合考慮知識表示、推理方法、應(yīng)用領(lǐng)域等多種因素）： 歸納學(xué)習(xí)：從個體的特征歸納出它們的共性 分析學(xué)習(xí)：從領(lǐng)域理論出發(fā)演繹出更有效的規(guī)則。 連接學(xué)習(xí)：人工神經(jīng)網(wǎng)絡(luò)學(xué)習(xí) 遺傳學(xué)習(xí)：模擬自然界遺傳與變異機制2022/8/812人工智能第12頁，共102頁。5.2 機械學(xué)習(xí)機械學(xué)習(xí)的模式機械學(xué)習(xí)是最簡單的機器學(xué)習(xí)方法。機械學(xué)習(xí)就是記憶，即把新的知識存儲起來，供需要時檢索調(diào)用，而不需要計算和推理。機械學(xué)習(xí)又是最

11、基本的學(xué)習(xí)過程。任何學(xué)習(xí)系統(tǒng)都必須記住它們獲取的知識。在機械學(xué)習(xí)系統(tǒng)中，知識的獲取是以較為穩(wěn)定和直接的方式進行的，不需要系統(tǒng)進行過多的加工。(X1,X2,Xn)(Y1,Y2,Yn)f(X1,X2,Xn),(Y1,Y2,Yn)存儲2022/8/813人工智能第13頁，共102頁。數(shù)據(jù)化簡 Lenat,Hayes Roth，和Klahr等人于1979年關(guān)于機械學(xué)習(xí)提出一種有趣的觀點。他們指出，可以把機械學(xué)習(xí)看成是數(shù)據(jù)化簡分級中的第一級。數(shù)據(jù)化簡與計算機語言編譯類似；其目的是把原始信息變成可執(zhí)行的信息。在機械學(xué)習(xí)中我們只記憶計算的輸入輸出，忽略了計算過程，這樣就把計算問題化簡成存取問題。 2022/

12、8/814人工智能第14頁，共102頁。機械學(xué)習(xí)的主要問題 對于機械學(xué)習(xí)，需要注意3個重要的問題：存儲組織，穩(wěn)定性和存儲與計算之間的權(quán)衡。（1）存儲組織信息：采用適當(dāng)?shù)拇鎯Ψ绞剑箼z索速度盡可能地快，是機械學(xué)習(xí)中的重要問題。（2）環(huán)境的穩(wěn)定性與存儲信息的適用性問題：機械學(xué)習(xí)系統(tǒng)必須保證所保存的信息適應(yīng)于外界環(huán)境變化的需要，這也就是所謂的信息適用性問題。（3）存儲與計算之間的權(quán)衡：對于機械學(xué)習(xí)來說很重要的一點是它不能降低系統(tǒng)的效率。2022/8/815人工智能第15頁，共102頁。5.3 歸納學(xué)習(xí) 歸納學(xué)習(xí)是目前研究得最多的學(xué)習(xí)方法，其學(xué)習(xí)目的是為了獲得新的概念、構(gòu)造新的規(guī)則或發(fā)現(xiàn)新的理論。這種

13、方法對領(lǐng)域理論沒有要求，甚至可以沒有領(lǐng)域理論，但其需要大量的訓(xùn)練例子，而且歸納性能受到描述語言、概念類型、信噪比、實例空間分布、 歸納模式等的影響。 （1）歸納（induction）是人類拓展認(rèn)識能力的重要方法，是一種從個別到一般的，從部分到整體的推理行為。 （2）歸納推理是應(yīng)用歸納方法，從足夠多的具體事例中歸納出一般性知識，提取事物的一般規(guī)律；它是一種從個別到一般的推理。（3）歸納學(xué)習(xí)（induction learning）是應(yīng)用歸納推理進行學(xué)習(xí)的一種方法。根據(jù)歸納學(xué)習(xí)有無教師指導(dǎo)，可把它分為示例學(xué)習(xí)和觀察與發(fā)現(xiàn)學(xué)習(xí)。前者屬于有師學(xué)習(xí)，后者屬于無師學(xué)習(xí)。2022/8/816人工智能第16頁，

14、共102頁。5.3.1 歸納學(xué)習(xí)的模式和規(guī)則歸納學(xué)習(xí)的模式給定：觀察陳述（事實）F，用以表示有關(guān)某些對象、狀態(tài)、過程等的特定知識；假定的初始?xì)w納斷言（可能為空），是關(guān)于目標(biāo)的泛化項或泛化描述。背景知識，用于定義有關(guān)觀察陳述、候選歸納斷言以及任何相關(guān)問題領(lǐng)域知識、假設(shè)和約束，其中包括能夠刻畫所求歸納斷言的性質(zhì)的優(yōu)先準(zhǔn)則。求：歸納斷言（假設(shè)）H，能重言蘊涵或弱蘊涵觀察陳述，并滿足背景知識。2022/8/817人工智能第17頁，共102頁。 假設(shè)H永真蘊涵事實F，說明F是H的邏輯推理，則有： H | F （讀作H特殊化為F） 或 F | CTXK (2) 放松條件： 一個事例的原因可能不止一條，當(dāng)出

15、現(xiàn)新的原因時，應(yīng)該把新的原因包含進去。 CTX1K = (CTX1CTX2)K 2022/8/819人工智能第19頁，共102頁。(3) 沿概念樹上溯： 設(shè)L是一結(jié)構(gòu)性描述項，S代表所有條件中的L值在概念分層樹上最近的共同祖先，則：(4) 形成閉合區(qū)域： 設(shè)L是一個具有顯性關(guān)系的描述項，a,b是它的特殊值，則：(5) 將常量轉(zhuǎn)化成變量：2022/8/820人工智能第20頁，共102頁。5.3.2 歸納學(xué)習(xí)方法1、示例學(xué)習(xí) 示例學(xué)習(xí)（learning from examples）又稱為實例學(xué)習(xí)，它是通過環(huán)境中若干與某概念有關(guān)的例子，經(jīng)歸納得出一般性概念的一種學(xué)習(xí)方法。在這種學(xué)習(xí)方法中，外部環(huán)境提

16、供的是一組例子（正例和反例），示例學(xué)習(xí)就是要從這些特殊知識中歸納出適用于更大范圍的一般性知識，以覆蓋所有的正例并排除所有反例。2、觀察發(fā)現(xiàn)學(xué)習(xí) 觀察發(fā)現(xiàn)學(xué)習(xí)又稱為描述性概括，其目標(biāo)是確定一個定律或理論的一般性描述，刻畫觀察集，指定某類對象的性質(zhì)。觀察發(fā)現(xiàn)學(xué)習(xí)可分為觀察學(xué)習(xí)與機器發(fā)現(xiàn)兩種。前者用于對事例進行聚類，形成概念描述；后者用于發(fā)現(xiàn)規(guī)律，產(chǎn)生定律或規(guī)則。2022/8/821人工智能第21頁，共102頁。5.3.3 歸納學(xué)習(xí)示例-決策樹學(xué)習(xí) 決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散值函數(shù)的方法。在這種方法中學(xué)習(xí)到的函數(shù)被表示為一顆決策樹。學(xué)習(xí)得到的決策樹也能再被表示為多個if

17、-then規(guī)則，以提高可讀性。 決策樹學(xué)習(xí)方法對噪聲數(shù)據(jù)有很好的健壯性且能夠?qū)W習(xí)析取表達式。決策樹學(xué)習(xí)算法有很多，比如ID3、C4.5、ASSISTANT等等。這些決策樹學(xué)習(xí)方法搜索一個完整表示的假設(shè)空間，從而避免了受限假設(shè)空間的不足。決策樹學(xué)習(xí)的歸納偏置是優(yōu)先選擇較小的樹。 2022/8/822人工智能第22頁，共102頁。決策樹表示法決策樹通過把實例從根節(jié)點排列(sort)到某個葉子節(jié)點來分類實例，葉子節(jié)點即為實例所屬的分類。樹上的每一個節(jié)點說明了對實例的某個屬性(attribute)的測試，并且該節(jié)點的每一個后繼分枝對應(yīng)于該屬性的一個可能值。分類實例的方法是從這顆樹的根節(jié)點開始，測試這個

18、節(jié)點指定的屬性，然后按照給定實例的該屬性值對應(yīng)的樹枝向下移動。然后這個過程再以新節(jié)點為根的子樹上重復(fù)。 例子：在一個水果的分類問題中，采用的特征向量為：顏色,尺寸,形狀,味道，其中：顏色取值為紅,綠,黃，尺寸取值為大,中,小，味道取值為甜,酸，形狀取值為圓,細(xì)。樣本集：一批水果，知道其特征向量及類別問 題：一個新的水果，觀測到了其特征向量，將其分類2022/8/823人工智能第23頁，共102頁。2022/8/824人工智能第24頁，共102頁。 通常決策樹代表實例屬性值約束的合取(conjunction)的析取式(disjunction)。從樹根到樹葉的每一條路徑對應(yīng)一組屬性測試的合取，樹本

19、身對應(yīng)這些合取的析取。 上述例子可對應(yīng)如下析取式：(color=greensize=big)(color=greensize=medium)(color=greensize=small)(color=yellowshape=roundsize=big)(color=yellowshape=roundsize=small)(color=yellowshape=thin)(color=redsize=medium)(color=redsize=smalltaste=sweet)(color=redsize=smalltaste=sour)2022/8/825人工智能第25頁，共102頁。決策樹的適

20、用問題決策樹學(xué)習(xí)適合解決具有以下特征的問題實例是由“屬性-值”對表示的：實例是用一系列固定的屬性和它們的值來描述的。目標(biāo)函數(shù)具有離散的輸出值：決策樹給每個實例賦予一個布爾型的分類。決策樹方法很容易擴展到學(xué)習(xí)有兩個以上輸出值的函數(shù)。可能需要析取的描述：決策樹很自然地代表了析取表達式。訓(xùn)練數(shù)據(jù)可以包含錯誤：決策樹學(xué)習(xí)對錯誤有很好的健壯性，無論是訓(xùn)練樣例所屬的分類錯誤，還是描述這些樣例的屬性值錯誤。訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實例：決策樹甚至可以再有未知屬性值的訓(xùn)練樣例中使用。 2022/8/826人工智能第26頁，共102頁。決策樹學(xué)習(xí)的常見問題確定決策樹增長的深度，避免過度擬合；處理連續(xù)值的屬性

21、；選擇一個適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)；處理屬性值不完整的訓(xùn)練數(shù)據(jù)；處理不同代價的屬性；提高計算效率。 2022/8/827人工智能第27頁，共102頁。ID3算法大多數(shù)已開發(fā)的決策樹學(xué)習(xí)算法是一種核心算法（CLS算法）的變體。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。這種方法是ID3算法(Quinlan 1986)和后繼的C4.5(Quinlan 1993)的基礎(chǔ)。ID3是一種自頂向下增長樹的貪婪算法，在每個節(jié)點選取能最好分類樣例的屬性。繼續(xù)這個過程指導(dǎo)這棵樹能完美分類訓(xùn)練樣例，或所有的屬性都已被使用過。構(gòu)造過程是從“哪一個屬性將在樹的根節(jié)點被測試”這個問題開始。為了回答這個問題，使用統(tǒng)計

22、測試來確定每一個實例屬性單獨分類訓(xùn)練樣例的能力。分類能力最好的屬性被選作樹的根節(jié)點的測試。然后為根節(jié)點屬性的每個可能值產(chǎn)生一個分枝，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种Γㄒ簿褪牵瑯永脑搶傩灾祵?yīng)的分枝）之下。然后重復(fù)整個過程，用每個分枝節(jié)點關(guān)聯(lián)的訓(xùn)練樣例來選取在該點被測試的最佳屬性。這形成了對合格決策樹的貪婪搜索，也就是算法從不回溯重新考慮以前的選擇。 2022/8/828人工智能第28頁，共102頁。決策樹的構(gòu)建已知訓(xùn)練樣本集，構(gòu)造決策樹需要解決以下幾個問題（考慮Binary Decision Trees）：（1）最佳提問的選擇：應(yīng)該先對哪一個屬性提出問題？應(yīng)該按什么樣的順序提出問題？ 每一個問題

23、都是一個YES/NO問題。（2）葉結(jié)點的確定：什么時候可以結(jié)束提問，并判定模式的類別？（3）決策樹修剪：如果決策樹過大，應(yīng)該如何修剪決策樹，以保證其泛化能力？2022/8/829人工智能第29頁，共102頁。最佳提問的選擇（1）（1）決策樹中的每一個結(jié)點（葉結(jié)點除外）對應(yīng)于一個提問。每一個葉結(jié)點給出最終的分類。決策樹的構(gòu)建從根結(jié)點開始。（2）根結(jié)點的構(gòu)建：根結(jié)點對應(yīng)于訓(xùn)練樣本集D。通過選擇針對某一屬性的一個問題進行提問，可以根據(jù)對該問題的回答，將訓(xùn)練樣本集D分類兩個部分：Dy及Dn （其中， Dy為回答YES的樣本， Dn為回答NO的樣本） ，并建立與之相對應(yīng)的兩個子結(jié)點。我們希望選擇一個這樣

24、問題進行提問：使得Dy及Dn盡可能純凈。（3）中間結(jié)點的構(gòu)造：對于每一個中間結(jié)點（結(jié)點N），都有一個與之對應(yīng)的子集DN。同樣，根據(jù)結(jié)點N的提問，可以將DN進一步劃分為兩個部分DNy及DNn（其中， DNy為回答YES的樣本， DNn為回答NO的樣本），并得到與之相對應(yīng)的兩個子結(jié)點。我們希望根據(jù)結(jié)點N提出的問題，能夠使DNy及DNn盡可能純凈。2022/8/830人工智能第30頁，共102頁。最佳提問的選擇（2）（4）當(dāng)如上得到的某一個子結(jié)點足夠純凈時，就可以確定該結(jié)點為葉結(jié)點，并給出其類別。（5）當(dāng)決策樹中的每一條路徑都對應(yīng)于一個葉結(jié)點時，學(xué)習(xí)過程結(jié)束，決策樹構(gòu)建完畢。（6）根據(jù)上述準(zhǔn)則（純凈

25、度準(zhǔn)則）構(gòu)建決策樹，可以保證決策樹的復(fù)雜度較?。ńY(jié)點數(shù)量少、深度?。＃?）在對訓(xùn)練集分類能力相近的條件下，復(fù)雜度小的決策樹（分類器）優(yōu)于復(fù)雜度大的決策樹（分類器）。復(fù)雜度小的分類器通常具有較好的泛化能力。這一原則稱為Occams razor。2022/8/831人工智能第31頁，共102頁。最佳提問的選擇（3）（8）結(jié)點n非純凈度的定義 其中，i(n)為結(jié)點n的非純凈度，Nn 為結(jié)點n對應(yīng)的樣本的數(shù)量，Njn為結(jié)點n中屬于j的樣本的數(shù)量，C為類別的個數(shù)。2022/8/832人工智能第32頁，共102頁。最佳提問的選擇（4） 其中，ny為結(jié)點n的YES子結(jié)點，nn 為NO子結(jié)點，Nny為YES

26、子結(jié)點對應(yīng)的樣本的數(shù)量，Nnn為NO子結(jié)點對應(yīng)的樣本的數(shù)量。 結(jié)點n的最佳選擇問題：使i(n)取得最大值。（9）結(jié)點n最佳問題的選擇： 對于結(jié)點n，通過提出并回答某個問題，可以得到如下的純凈度的提高（不純凈度的降低）：2022/8/833人工智能第33頁，共102頁。最佳提問的選擇（5）（10）結(jié)點n最佳問題的選擇范圍： 需要枚舉出所有可以提出的問題，從中選出有效的問題，并在這些有效的問題中選擇一個最佳的問題。 由于特征的數(shù)量是有限的，每個特征的可能取值也是有限的，所以所有可能提出的問題是可以枚舉的。 所提問題通常限制為針對某個特征提出的簡單問題，問題的形式如前面的二叉數(shù)所示。2022/8/8

27、34人工智能第34頁，共102頁。葉結(jié)點的確定問題 決策樹結(jié)點劃分的原則是使其子結(jié)點盡可能純凈（指兩個子結(jié)點的平均純凈度最高）。對于任意一個結(jié)點n，可以出現(xiàn)以下三種情況：（1）結(jié)點n中的樣本屬于同一類，即結(jié)點n絕對純凈。此時結(jié)點n不可進一步劃分。（2）結(jié)點n中的樣本不屬于同一類，但是不存在任何一個劃分（即提出一個問題并根據(jù)該問題對結(jié)點n的樣本進行劃分）可以使其子結(jié)點的平均純凈度高于結(jié)點n。此時結(jié)點n不可進一步劃分。（3）可以提出一個問題對結(jié)點n進行劃分，從而使結(jié)點n的子結(jié)點具有更高的純凈度。此時結(jié)點n可以進一步劃分。2022/8/835人工智能第35頁，共102頁。葉結(jié)點的確定問題問題：在構(gòu)建

28、決策樹的過程中，確定葉節(jié)點的一個策略是：對于每一個可以進一步劃分的結(jié)點都進行劃分，直到得到一個不可劃分的子結(jié)點，并將該子結(jié)點定為葉結(jié)點。這樣構(gòu)造的決策樹，其葉結(jié)點均為不可再進一步劃分的結(jié)點。這種葉結(jié)點的確定方法是否可行？答案：決策樹是根據(jù)訓(xùn)練樣本的集合構(gòu)成的。該集合中的樣本是隨機的。不同的隨機實驗會得到不同的樣本集合。因此，該集合并不能完全描述樣本(即特征向量)真實分布。當(dāng)葉結(jié)點按上述方法確定時，所得決策樹雖然對訓(xùn)練樣本集合給出了最優(yōu)的分類，但是卻背離了樣本的真實分布，因此削弱了對未來新樣本的分類能力。這一現(xiàn)象稱為過度擬合(指決策數(shù)對訓(xùn)練樣本過度擬合，從而背離了樣本的真實分布)。2022/8/

29、836人工智能第36頁，共102頁。葉結(jié)點確定的基本思路（1）并不絕追求對訓(xùn)練樣本的正確劃分。并不絕對追求葉結(jié)點的純凈度。絕對追求葉結(jié)點的純凈度導(dǎo)致過度擬合。此時決策樹的復(fù)雜度偏高。（2）要適度保證葉結(jié)點的純凈度，適度保證對訓(xùn)練樣本的正確分類能力。葉結(jié)點的不純凈度過高，對訓(xùn)練樣本的正確分類能力過低稱為欠學(xué)習(xí)（此時，決策樹不能夠充分提取樣本集合中蘊涵的有關(guān)樣本真實分布的信息。欠學(xué)習(xí)同樣不能保證對未來新樣本的正確分類能力）。此時決策樹的復(fù)雜度偏低。（3）因此，在決策樹的構(gòu)建過程中，需要在過度擬合與欠學(xué)習(xí)之間尋求合理的平衡，即尋求復(fù)雜度適中的決策樹。具體方法為：在結(jié)點還可以進一步劃分的時候，可根據(jù)預(yù)

30、先設(shè)定的準(zhǔn)則停止對其劃分，并將其設(shè)置為葉結(jié)點。2022/8/837人工智能第37頁，共102頁。確定葉結(jié)點的基本方法（1）方法1：采用測試集的方法。將樣本集合分為訓(xùn)練集與測試集。根據(jù)訓(xùn)練集構(gòu)建決策樹，決策樹中的結(jié)點逐層展開。每展開一層子結(jié)點，并將其設(shè)為葉結(jié)點，就得到一棵決策樹，然后采用測試集對所得決策樹的分類性能進行統(tǒng)計。重復(fù)上述過程，可以得到?jīng)Q策樹在測試集上的學(xué)習(xí)曲線。根據(jù)學(xué)習(xí)曲線，選擇在測試集上性能最佳的決策樹為最終的決策樹。方法2：在決策樹開始訓(xùn)練以前，首先設(shè)定一個閾值A(chǔ)。在決策樹的訓(xùn)練過程中，對于任意一個結(jié)點n，如果該結(jié)點的最優(yōu)劃分（即最優(yōu)問題對該結(jié)點的樣本集合所作的劃分）所導(dǎo)致的純凈

31、度的提高小于A，則將該結(jié)點定為葉結(jié)點。采用該方法不需要將樣本集合分為訓(xùn)練集及測試集。決策樹直接采用全體樣本集合構(gòu)建。2022/8/838人工智能第38頁，共102頁。確定葉結(jié)點的基本方法（2）方法3：在決策樹開始訓(xùn)練以前，首先設(shè)定一個閾值A(chǔ)。在決策樹的訓(xùn)練過程中，對于任意一個結(jié)點n，如果Nn/NA，則確定結(jié)點n為葉結(jié)點。其中，Nn為結(jié)點n對應(yīng)的樣本的數(shù)量，N 為全體樣本的數(shù)量。采用該方法同樣不需要將樣本集合分為訓(xùn)練集及測試集。決策樹直接采用全體樣本集合構(gòu)建。方法4：采用如下的性能準(zhǔn)則函數(shù)： 其中size 代表決策樹的復(fù)雜度，i(n)為結(jié)點n 的非純凈度。該準(zhǔn)則函數(shù)表達出了過度擬合與欠學(xué)習(xí)之間的

32、相互關(guān)系。決策樹的優(yōu)化準(zhǔn)則為：使該準(zhǔn)則函數(shù)取得最小值。2022/8/839人工智能第39頁，共102頁。決策樹修剪（1） 決策樹的修剪是決策樹學(xué)習(xí)的另外一種有效的方法。其基本思路是，首先使決策樹得到充分生長，然后再通過修剪降低決策樹的復(fù)雜度，從而保證決策樹的泛化能力。具體方法如下：（1）決策樹的構(gòu)建：在決策樹的構(gòu)建過程中，對于每一個可以進一步劃分的結(jié)點都進行劃分，直到得到一個不可進一步劃分的子結(jié)點，并將該子結(jié)點定為葉結(jié)點。這樣構(gòu)造的決策樹，其葉結(jié)點均為不可再進一步劃分的結(jié)點。2022/8/840人工智能第40頁，共102頁。決策樹修剪（2）（2）在上述決策樹構(gòu)建完畢后，從葉結(jié)點一層開始，考察兄

33、弟葉結(jié)點是否可以合并。如果可以合并，則對這些兄弟結(jié)點進行合并，并將其父結(jié)點設(shè)為葉結(jié)點。在對所有可以合并的兄弟葉結(jié)點進行合并后，可以形成一棵新的決策樹。對于新形成的決策樹，可以重復(fù)上述兄弟結(jié)點的合并過程，直到最后得到一棵決策樹，其中任意兩個兄弟葉結(jié)點都不再滿足合并的條件。這棵決策樹，就是我們最終選擇的決策樹。2022/8/841人工智能第41頁，共102頁。決策樹修剪（3）（3）兄弟葉結(jié)點合并的條件為 其中，ny及nn為兄弟葉結(jié)點，n為其父結(jié)點。Nn 為父結(jié)點中樣本的數(shù)量，Nny及Nnn 為兩個子結(jié)點中樣本的數(shù)量。 上述合并條件中，i(n)代表了由于合并所導(dǎo)致的不純凈度的損失。A為閾值，在修剪過

34、程開始前預(yù)先設(shè)定。 葉結(jié)點的類別 設(shè)分類問題為C類的分類問題。對于葉結(jié)點n，如果在該結(jié)點對應(yīng)的樣本中，屬于第 i 類的樣本數(shù)量最多，則判該葉結(jié)點為第i類。2022/8/842人工智能第42頁，共102頁。討論（1）根據(jù)決策樹可以得出若干條規(guī)則。一條從根結(jié)點到葉結(jié)點的路途對應(yīng)于一條IF-THEN規(guī)則。其中，路徑的非葉結(jié)點部分構(gòu)成了規(guī)則的條件部分（IF部分），葉結(jié)點給出了規(guī)則的結(jié)論（THEN部分）。 例子：IF COLOR=RED AND SIZE=MEDIUM THEN IT IS AN APPLE 用途：知識的獲取。（2）決策樹方法同樣可用于連續(xù)取值的特征量。當(dāng)特征向量空間為歐氏空間時，同樣可

35、以采用決策樹方法來構(gòu)造分類器。當(dāng)然，一般情況下在歐氏空間中通常采用神經(jīng)網(wǎng)絡(luò)來構(gòu)造分類器。2022/8/843人工智能第43頁，共102頁。5.4 類比學(xué)習(xí) 類比(analogy)是一種很有用的和有效的推理方法，它能夠清晰簡潔地描述對象間的相似性；也是人類認(rèn)識世界的一種重要方法。 類比學(xué)習(xí)(learning by analogy)就是通過類比，即通過相似事物加以比較所進行的一種學(xué)習(xí)。 例如，當(dāng)人們遇到一個新問題需要進行處理，但又不具備處理這個問題的知識時，通常采用的辦法就是回憶一下過去處理過的類似問題，找出一個與目前情況最接近的處理方法來處理當(dāng)前問題。2022/8/844人工智能第44頁，共10

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

37、應(yīng)映射在S與T的相似情況之間建立相似元素的對應(yīng)關(guān)系，并建立起相應(yīng)的映射。 (4) 轉(zhuǎn)換在上一步建立的映射下，把S中的有關(guān)知識引到T中來，從而建立起求解當(dāng)前問題的方法或者學(xué)習(xí)到關(guān)于T的新知識。2022/8/846人工智能第46頁，共102頁。類比學(xué)習(xí) 類比學(xué)習(xí)是基于類比推理的。類比學(xué)習(xí)的過程主要分為兩步：首先歸納找出源問題和目標(biāo)問題的公共性質(zhì)，然后再演繹推出從源問題到目標(biāo)問題的映射，得出目標(biāo)問題的新的性質(zhì)。所以類比學(xué)習(xí)既有歸納過程，又有演繹過程。 類比學(xué)習(xí)的主要過程可描述如下：(1) 輸入一組已知條件（已解決問題）和一組未完全確定的條件（新問題）。(2) 對輸入的兩組條件，根據(jù)其描述，按某種相似

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

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

40、地說，基于范例推理就是由目標(biāo)范例的提示而獲得記憶中的源范例，并由源范例來指導(dǎo)目標(biāo)范例求解的一種策略。2022/8/849人工智能第49頁，共102頁。范例推理基本流程提出解決方案確認(rèn)解決方案以前案例新案例學(xué)過的案例取回案例新案例解決的案例修改案例 一般知識提取使用修改保留問題2022/8/850人工智能第50頁，共102頁。基于范例推理中知識表示是以范例為基礎(chǔ)，范例的獲取比規(guī)則獲取要容易，大大簡化知識獲取。對過去的求解結(jié)果進行復(fù)用，而不是再次從頭推導(dǎo)，可以提高對新問題的求解效率。過去求解成功或失敗的經(jīng)歷可以指導(dǎo)當(dāng)前求解時該怎樣走向成功或避開失敗，這樣可以改善求解的質(zhì)量。對于那些目前沒有或根本不

41、存在的問題，可以通過計算推導(dǎo)來解決的問題。如在法律中的判例，基于范例推理能很好發(fā)揮作用。范例推理的特點2022/8/851人工智能第51頁，共102頁。基于范例的學(xué)習(xí) 基于范例的推理系統(tǒng)經(jīng)過不斷的積累經(jīng)驗（案例），同時合適地對其進行索引，系統(tǒng)的推理效率和問題求解能力會隨之增加。因此在CBR中，學(xué)習(xí)的主要任務(wù)是對案例庫的豐富和優(yōu)化。 在CBR中，大多數(shù)學(xué)習(xí)是通過如下兩種方式體現(xiàn)的：一個是新范例的積累，推理系統(tǒng)的范例對問題的覆蓋越多，其功能越強；另一個是設(shè)計覆蓋了成功事例也覆蓋了失敗事例的推理要比只設(shè)計成功情況的推理系統(tǒng)要好，索引的重新賦值，調(diào)節(jié)索引可使得范例能在更合適的時機被回憶。2022/8/

42、852人工智能第52頁，共102頁。基于范例學(xué)習(xí)的一般過程新問題 新范例檢索歷史范例范例庫復(fù)用保存修正范例修正解答范例 確認(rèn)解建議解2022/8/853人工智能第53頁，共102頁。范例的內(nèi)容(1) 問題或情景描述：是對要求解的問題或要理解的情景的描述，一般要包括這些內(nèi)容：當(dāng)范例發(fā)生時推理器的目標(biāo)，完成該目標(biāo)所要涉及的任務(wù)，周圍世界或環(huán)境與可能解決方案相關(guān)的所有特征。(2) 解決方案：是問題如何在一特定情形下得到解決。它可能是對問題的簡單解答，也可能是得出解答的推導(dǎo)過程。(3) 結(jié)果：記錄了實施解決方案后的結(jié)果情況，是失敗還是成功。有了結(jié)果內(nèi)容，CBR在給出建議解時有能給出曾經(jīng)成功地工作的范例

43、，同時也能利用失敗的范例來避免可能會發(fā)生的問題。當(dāng)對問題還缺乏足夠的了解時，通過在范例的表示上加上結(jié)果部分能取得較好的效果。2022/8/854人工智能第54頁，共102頁。范例的索引建立范例索引有三個原則： 索引與具體領(lǐng)域有關(guān)。數(shù)據(jù)庫中的索引是通用的，目的僅僅是追求索引能對數(shù)據(jù)集合進行平衡的劃分從而使得檢索速度最快；而范例索引則要考慮是否有利于將來的范例檢索，它決定了針對某個具體的問題哪些范例被復(fù)用； 索引應(yīng)該有一定的抽象或泛化程度，這樣才能靈活處理以后可能遇到的各種情景，太具體則不能滿足更多的情況； 索引應(yīng)該有一定的具體性，這樣才能在以后被容易地識別出來，太抽象則各個范例之間的差別將被消除

44、。2022/8/855人工智能第55頁，共102頁。范例學(xué)習(xí)的主要問題（1） (1) 范例表示：基于范例推理方法的效率和范例表示緊密相關(guān)。范例表示涉及這樣幾個問題: 選擇什么信息存放在一個范例中；如何選擇合適的范例內(nèi)容描述結(jié)構(gòu)；范例庫如何組織和索引。對于那些數(shù)量達到成千上萬、而且十分復(fù)雜的范例, 組織和索引問題尤其重要。 (2) 分析模型：分析模型用于分析目標(biāo)范例，從中識別和抽取檢索源范例庫的信息。 (3) 范例檢索：利用檢索信息從源范例庫中檢索并選擇潛在可用的源范例。這步非常關(guān)鍵。一般講，范例匹配不是精確的，只能是部分匹配或近似匹配。因此，它要求有一個相似度的評價標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)定義得好，會使得

45、檢索出的范例十分有用，否則將會嚴(yán)重影響后面的過程。 2022/8/856人工智能第56頁，共102頁。范例學(xué)習(xí)的主要問題（2） (4) 類比映射: 尋找目標(biāo)范例同源范例之間的對應(yīng)關(guān)系。 (5) 類比轉(zhuǎn)換: 轉(zhuǎn)換源范例中同目標(biāo)范例相關(guān)的信息，以便應(yīng)用于目標(biāo)范例的求解過程中。把檢索到的源范例的解答復(fù)用于新問題或新范例之中需要解決的問題分別是：源范例與目標(biāo)范例間有何不同之處；源范例中的哪些部分可以用于目標(biāo)范例。需要根據(jù)它們之間的不同對復(fù)用的求解方案進行調(diào)整。 (6) 解釋過程: 對把轉(zhuǎn)換過的源范例的求解方案應(yīng)用到目標(biāo)范例時所出現(xiàn)的失敗做出解釋，給出失敗的因果分析報告。有時對成功也同樣做出解釋。基于解

46、釋的索引也是一種重要的方法。 (7) 范例修補: 有些類似于類比轉(zhuǎn)換，區(qū)別在于修補過程的輸入是解方案和一個失敗報告，而且也許還包含一個解釋，然后修改這個解以排除失敗的因素。 2022/8/857人工智能第57頁，共102頁。范例學(xué)習(xí)的主要問題（3） (8) 類比驗證: 驗證目標(biāo)范例和源范例進行類比的有效性。 (9) 范例保存: 新問題得到了解決，則形成了一個可能用于將來情形與之相似的問題。這時有必要把它加入到范例庫中。這是學(xué)習(xí)也是知識獲取。此過程涉及選取哪些信息保留，以及如何把新范例有機集成到范例庫中。修改和精化源范例庫, 其中包括泛化和抽象等過程。 在決定選取范例的哪些信息進行保留時，一般要

47、考慮以下幾點：和問題有關(guān)的特征描述；問題的求解結(jié)果；以及解答為什么成功或失敗的原因及解釋。 把新范例加入到范例庫中， 需要對它建立有效的索引，這樣以后才能對之作出有效的回憶。為此，可能要對范例庫的索引內(nèi)容甚至結(jié)構(gòu)進行調(diào)整，如改變索引的強度或特征權(quán)值。2022/8/858人工智能第58頁，共102頁。5.5 解釋學(xué)習(xí)基于解釋的學(xué)習(xí)：一種從單個觀察中抽象出通用規(guī)則的方法目標(biāo)是下次可以快速地解決類似的問題通過保存結(jié)果和避免從零開始解決問題來提高速度更進一步EBL從觀察到規(guī)則 解釋學(xué)習(xí)(Explanation-Based Learning, 簡稱EBL)是一種分析學(xué)習(xí)方法，在領(lǐng)域知識指導(dǎo)下, 通過對單

48、個問題求解實例的分析, 構(gòu)造出求解過程的因果解釋結(jié)構(gòu), 并獲取控制知識,以便用于指導(dǎo)以后求解類似問題。2022/8/859人工智能第59頁，共102頁。解釋學(xué)習(xí)過程和算法 解釋學(xué)習(xí)一般包括下列3個步驟：(1) 利用基于解釋的方法對訓(xùn)練例子進行分析與解釋。(2) 對例子的結(jié)構(gòu)進行概括性解釋。(3) 從解釋結(jié)構(gòu)中識別出訓(xùn)練例子的特性，獲取一般控制知識。1986年米切爾（Mitchell）等人為基于解釋的學(xué)習(xí)提出了一個統(tǒng)一的算法EBG，該算法建立了基于解釋的概括過程，并運用知識的邏輯表示和演繹推理進行問題求解。下圖表示EBG問題。2022/8/860人工智能第60頁，共102頁。 EBG求解問題的形

49、式描述:給定：(1) 目標(biāo)概念描述TC；(2) 訓(xùn)練實例TE；(3) 領(lǐng)域知識DT；(4) 操作準(zhǔn)則OC。求解：訓(xùn)練實例的一般化概括，使之滿足：(1) 目標(biāo)概念的充分概括描述TC；(2) 操作準(zhǔn)則OC。圖 EBG問題 2022/8/861人工智能第61頁，共102頁。5.6 強化學(xué)習(xí) 強化學(xué)習(xí)(reinforcement learning-RL，又稱再勵學(xué)習(xí)，評價學(xué)習(xí)) 在智能控制機器人及分析預(yù)測等領(lǐng)域有許多應(yīng)用。 在傳統(tǒng)的機器學(xué)習(xí)分類中沒有提及到過強化學(xué)習(xí)。而在連接主義學(xué)習(xí)中，把學(xué)習(xí)算法分為非監(jiān)督學(xué)習(xí)(unsupervised learning) 、監(jiān)督學(xué)習(xí)(supervised learn

50、ing) 和強化學(xué)習(xí)三種。 所謂強化學(xué)習(xí)就是智能系統(tǒng)從環(huán)境到行為映射的學(xué)習(xí)，以使獎勵信號(強化信號) 函數(shù)值最大。 強化學(xué)習(xí)不同于連接主義學(xué)習(xí)中的監(jiān)督學(xué)習(xí)，主要表現(xiàn)在教師信號上，強化學(xué)習(xí)中由環(huán)境提供的強化信號是對產(chǎn)生動作的好壞作一種評價(通常為標(biāo)量信號) ，而不是告訴強化學(xué)習(xí)系統(tǒng)如何去產(chǎn)生正確的動作。2022/8/862人工智能第62頁，共102頁。強化學(xué)習(xí)通常包括兩個方面的含義：一方面是將強化學(xué)習(xí)作為一類問題；另一方面是指解決這類問題的一種技術(shù)。 如果將強化學(xué)習(xí)作為一類問題，目前的學(xué)習(xí)技術(shù)大致可分成兩類：其一是搜索智能系統(tǒng)的行為空間，以發(fā)現(xiàn)系統(tǒng)最優(yōu)的行為。典型的技術(shù)如遺傳算法等搜索技術(shù)；另一

51、類是采用統(tǒng)計技術(shù)和動態(tài)規(guī)劃方法來估計在某一環(huán)境狀態(tài)下的行為的效用函數(shù)值，從而通過行為效用函數(shù)來確定最優(yōu)行為。 我們特指這種學(xué)習(xí)技術(shù)為強化學(xué)習(xí)技術(shù)。 2022/8/863人工智能第63頁，共102頁。強化學(xué)習(xí)的產(chǎn)生與發(fā)展 強化思想最先來源于心理學(xué)的研究。1911年Thorndike提出了效果律（Law of Effect）：一定情景下讓動物感到舒服的行為，就會與此情景增強聯(lián)系（強化），當(dāng)此情景再現(xiàn)時，動物的這種行為也更易再現(xiàn)；相反，讓動物感覺不舒服的行為，會減弱與情景的聯(lián)系，此情景再現(xiàn)時，此行為將很難再現(xiàn)。換個說法，哪種行為會“記住”，會與刺激建立聯(lián)系，取決于行為產(chǎn)生的效果。動物的試錯學(xué)習(xí)，包含

52、兩個含義：選擇和聯(lián)系，對應(yīng)計算上的搜索和記憶。所以，1954年，Minsky在他的博士論文中實現(xiàn)了計算上的試錯學(xué)習(xí)。同年，F(xiàn)arley和Clark也在計算上對它進行了研究。強化學(xué)習(xí)一詞最早出現(xiàn)于科技文獻是1961年Minsky 的論文“Steps Toward Artificial Intelligence”，此后開始廣泛使用。1969年， Minsky因在人工智能方面的貢獻而獲得計算機圖靈獎。2022/8/864人工智能第64頁，共102頁。強化學(xué)習(xí)的發(fā)展過程可粗略分為兩個階段： 強化學(xué)習(xí)的形成階段（50 年代60年代）Minsky首次提出“強化”和“強化學(xué)習(xí)”這些術(shù)語；Samuel的下棋程

53、序采用類似值迭代、瞬時差分和Q 學(xué)習(xí)的訓(xùn)練機制，來學(xué)習(xí)用線性函數(shù)表示的值函數(shù)；Saridis 把強化控制系統(tǒng)的控制器看成一個隨機自動機，首次系統(tǒng)提出了采用強化學(xué)習(xí)來解決隨機控制系統(tǒng)的學(xué)習(xí)控制問題。強化學(xué)習(xí)的發(fā)展階段（70 年代 ）1972年，Klopf把試錯學(xué)習(xí)和時序差分結(jié)合在一起。1978年開始，Sutton、Barto、 Moore等對這兩者結(jié)合開始進行深入研究。1989年Watkins提出了Q-學(xué)習(xí)，也把強化學(xué)習(xí)的三條主線扭在了一起。1992年，Tesauro用強化學(xué)習(xí)成功了應(yīng)用到西洋雙陸棋中，稱為TD-Gammon 。2022/8/865人工智能第65頁，共102頁。5.6.1 強化學(xué)

54、習(xí)的原理 強化學(xué)習(xí)把學(xué)習(xí)看作試探過程，基本過程如圖所示。在強化學(xué)習(xí)中，Agent 選擇一個動作作用于環(huán)境，環(huán)境接收該動作后發(fā)生變化，同時產(chǎn)生一個強化信號（獎或罰）反饋給Agent，Agent 再根據(jù)強化信號和環(huán)境的當(dāng)前狀態(tài)再選擇下一個動作，選擇的原則是使受到正的報酬的概率增大。選擇的動作不僅影響立即強化值而且還影響下一時刻的狀態(tài)及最終強化值。強化學(xué)習(xí)的目的就是尋找一個最優(yōu)策。1、強化學(xué)習(xí)的結(jié)構(gòu) Agent環(huán)境狀態(tài)s獎賞r動作a2022/8/866人工智能第66頁，共102頁。 強化學(xué)習(xí)模型由以下部分組成：2、強化學(xué)習(xí)模型 一個離散的狀態(tài)集S = s0 , s1 , s2 , , sn ；動作集

55、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 的任務(wù)就是學(xué)習(xí)控制策略: S A，能夠最大化期望獎賞值的總和。2022/8/867人工智能第67頁，共102頁。 強化學(xué)習(xí)技術(shù)的基本原理是：如果系統(tǒng)某個動作導(dǎo)致環(huán)境正的獎賞，那么系統(tǒng)以后產(chǎn)生這個動作的趨勢便會加強。反之系統(tǒng)產(chǎn)生這個動作的趨勢便減弱。這和

56、生理學(xué)中的條件反射原理是接近的。 如果假定環(huán)境是馬爾可夫型的，則順序型強化學(xué)習(xí)問題可以通過馬氏決策過程（Markov Decision Process，MDP）建模。下面首先給出馬氏決策過程的形式化定義。馬氏決策過程 由四元組定義。包含一個環(huán)境狀態(tài)集S，系統(tǒng)行為集合A，獎賞函數(shù)R：SA 和狀態(tài)轉(zhuǎn)移函數(shù)P：SAPD(S)。記R(s, a, s)為系統(tǒng)在狀態(tài)s采用a動作使環(huán)境狀態(tài)轉(zhuǎn)移到s獲得的瞬時獎賞值，簡記為Rass；記P(s, a, s)為系統(tǒng)在狀態(tài)s采用a動作使環(huán)境狀態(tài)轉(zhuǎn)移到s的概率，簡記為Pass 。 2022/8/868人工智能第68頁，共102頁。 馬氏決策過程的本質(zhì)是：當(dāng)前狀態(tài)向下一

57、狀態(tài)轉(zhuǎn)移的概率和獎賞值只取決于當(dāng)前狀態(tài)和選擇的動作，而與歷史狀態(tài)和歷史動作無關(guān)。因此在已知狀態(tài)轉(zhuǎn)移概率函數(shù)P和獎賞函數(shù)R的環(huán)境模型知識下，可以采用動態(tài)規(guī)劃技術(shù)求解最優(yōu)策略。 而強化學(xué)習(xí)著重研究在P函數(shù)和R函數(shù)未知的情況下，系統(tǒng)如何學(xué)習(xí)最優(yōu)行為策略。 由于模型中P函數(shù)和R函數(shù)未知，系統(tǒng)只能夠依賴于每次試錯所獲得的瞬時獎賞來選擇策略。但由于在選擇行為策略過程中，要考慮到環(huán)境模型的不確定性和目標(biāo)的長遠性，因此在策略和瞬時獎賞之間構(gòu)造值函數(shù)（即狀態(tài)的效用函數(shù)），用于策略的選擇。 2022/8/869人工智能第69頁，共102頁。 首先通過下式構(gòu)造一個返回函數(shù)Rt，用于反映系統(tǒng)在某個策略指導(dǎo)下的一次學(xué)習(xí)

58、循環(huán)中，從st狀態(tài)往后所獲得的所有獎賞的累計折扣和。 由于環(huán)境是不確定的，系統(tǒng)在某個策略指導(dǎo)下的每一次學(xué)習(xí)循環(huán)中所得到的Rt有可能是不同的。因此在s狀態(tài)下的值函數(shù)要考慮不同學(xué)習(xí)循環(huán)中所有返回函數(shù)的數(shù)學(xué)期望。因此在策略下，系統(tǒng)在s狀態(tài)下的值函數(shù)由下式定義，其反映了如果系統(tǒng)遵循策略，所能獲得的期望的累計獎賞折扣和。 2022/8/870人工智能第70頁，共102頁。 根據(jù)Bellman最優(yōu)策略公式，在最優(yōu)策略*下，系統(tǒng)在s狀態(tài)下的值函數(shù)定義為： 所以，強化學(xué)習(xí)的任務(wù)就是求解* 。 由于強化學(xué)習(xí)中，P函數(shù)和R函數(shù)未知，系統(tǒng)無法直接求解上面的值函數(shù)。因而實際中常采用逼近的方法進行值函數(shù)的估計 ，其中最

59、主要的方法之一是Monte Carlo采樣 。2022/8/871人工智能第71頁，共102頁。5.6.2 強化學(xué)習(xí)算法 到目前為止，研究者們提出了很多強化學(xué)習(xí)算法，近年來對強化學(xué)習(xí)算法的研究已由算法本身逐漸轉(zhuǎn)向研究經(jīng)典算法在各種復(fù)雜環(huán)境中的應(yīng)用，較有影響的強化學(xué)習(xí)算法有TD 算法，Q 學(xué)習(xí)算法，Sarsa算法，Dyan 算法，R 學(xué)習(xí)算法，H 學(xué)習(xí)等，還有一些改進算法，如滯后更新多步Q-學(xué)習(xí)算法等。2022/8/872人工智能第72頁，共102頁。1、蒙特卡羅算法 蒙特卡羅算法( Monte Carlo method , MC)通過評估值函數(shù)來發(fā)現(xiàn)最優(yōu)策略，且不需要環(huán)境的全部信息，它只需要經(jīng)

60、驗知識。如部分有關(guān)狀態(tài)序列、動作行為集以及同環(huán)境交互產(chǎn)生的獎賞值的信息。 MC算法基于平均化取樣回報來解決強化學(xué)習(xí)問題，它將解決的問題分解成幕( episode) 。當(dāng)環(huán)境狀態(tài)為終止?fàn)顟B(tài)時，將得到積累回報賦予開始狀態(tài)s 的值函數(shù)V。 從s 出發(fā)到終止?fàn)顟B(tài)t 的過程中，s 可能不止出現(xiàn)一次。 對s 的值函數(shù)的更新有兩種方法： (1) first visit MC 將回報賦予第一次訪問的s； (2) every visit MC 將每次訪問s 到t 的回報平均后賦予s。2022/8/873人工智能第73頁，共102頁。MC算法中，值函數(shù)更新規(guī)則為： 其中，Rt 為t 時刻的獎賞值，為步長參數(shù)。控制