1、 The Principles of AI-Wang Wenjie Machine Learning: 2 Graduate School , Chinese academy of Sciences. Fall 2005 機(jī)器學(xué)習(xí) Machine Learning Artificial Intelligence Machine Learning: 3 Graduate University , Chinese academy of Sciences. Agenda 機(jī)器學(xué)習(xí)概述 歸納學(xué)習(xí) 決策樹學(xué)習(xí) 基于范例的學(xué)習(xí)(CBR) 解釋學(xué)習(xí) 強(qiáng)化學(xué)習(xí) Artificial Intelligence

2、Machine Learning: 4 Graduate University , Chinese academy of Sciences. 機(jī)器學(xué)習(xí)概述機(jī)器學(xué)習(xí)概述(1)(1) 什么是機(jī)器學(xué)習(xí)？ 學(xué)習(xí)是使系統(tǒng)在不斷重復(fù)的工作中對本身能力的增強(qiáng)和改進(jìn)，使得系統(tǒng)下 一次完成同樣或類似的任務(wù)時比上一次更有效，即通過對人類學(xué)習(xí)過程和 特點的研究，建立學(xué)習(xí)理論和方法，并應(yīng)用于機(jī)器，以改進(jìn)機(jī)器的行為和 性能。 1、學(xué)習(xí)是一個過程。學(xué)習(xí)是經(jīng)驗積累的過程，這個過程可能很快，也 可能很漫長； 2、學(xué)習(xí)是對一個系統(tǒng)而言。這個系統(tǒng)可能是一個計算機(jī)系統(tǒng)，或一個人 機(jī)系統(tǒng)； 3、學(xué)習(xí)能夠改變系統(tǒng)的性能。這只說明對系統(tǒng)

3、性能的改進(jìn)，但是并未 限制改進(jìn)的方法。 從人工智能的角度看，機(jī)器學(xué)習(xí)是一門研究使用計算機(jī)獲取新的知識和技 能，提高現(xiàn)有計算機(jī)求解問題能力的科學(xué) Artificial Intelligence Machine Learning: 5 Graduate University , Chinese academy of Sciences. 機(jī)器學(xué)習(xí)概述機(jī)器學(xué)習(xí)概述(2)(2) 什么要研究機(jī)器學(xué)習(xí)？ 必要性： 理解學(xué)習(xí)的本質(zhì)和建立學(xué)習(xí)系統(tǒng)是AI研究的目標(biāo)之一 現(xiàn)有的大多數(shù)AI系統(tǒng)都是演繹的，沒有歸納推理，因而 不能自動獲取和生成知識 可行性： 學(xué)習(xí)的過程是信息處理的過程，這包括直接記憶和經(jīng)過 推理 已有

4、工作說明可以實現(xiàn)一定程度的機(jī)器學(xué)習(xí) Artificial Intelligence Machine Learning: 6 Graduate University , Chinese academy of Sciences. 機(jī)器學(xué)習(xí)概述機(jī)器學(xué)習(xí)概述(3)(3) 機(jī)器學(xué)習(xí)的研究目標(biāo)和困難 研究目標(biāo)： 通用學(xué)習(xí)算法：理論分析任務(wù)和開發(fā)用于非實用學(xué)習(xí) 任務(wù)的算法 認(rèn)知模型：研究人的學(xué)習(xí)的計算模型和實驗?zāi)Ｐ?工程目標(biāo)：解決專門的實際問題，并開發(fā)完成這些任 務(wù)的工程系統(tǒng) 困難： 學(xué)習(xí)系統(tǒng)性能的預(yù)測更加困難 獲取知識的本質(zhì)還是猜想。由特定的觀察和 類比生成的知識不可能證明其正確性。 Artificial

5、 Intelligence Machine Learning: 7 Graduate University , Chinese academy of Sciences. 機(jī)器學(xué)習(xí)概述機(jī)器學(xué)習(xí)概述(4)(4) 學(xué)習(xí)的一種模型 環(huán)境：外部信息的來源，它將為系統(tǒng)的學(xué)習(xí)提供有關(guān)信息 知識庫：代表系統(tǒng)已經(jīng)具有的知識 學(xué)習(xí)環(huán)節(jié)：系統(tǒng)的學(xué)習(xí)機(jī)構(gòu)，它通過對環(huán)境的感知取得外部信息，然后經(jīng)分析 、綜合、類比、歸納等思維過程獲得知識，生成新的知識或改進(jìn)知識庫的組織 結(jié)構(gòu)。 執(zhí)行環(huán)節(jié)：基于學(xué)習(xí)后得到的新的知識庫，執(zhí)行一系列任務(wù)，并將運行結(jié)果報 告學(xué)習(xí)環(huán)節(jié)，以完成對新知識庫的評價，指導(dǎo)進(jìn)一步的學(xué)習(xí)工作,是該模型的核 心

6、。 環(huán)境環(huán)境 學(xué)習(xí)環(huán)節(jié)學(xué)習(xí)環(huán)節(jié)知識庫知識庫執(zhí)行環(huán)節(jié)執(zhí)行環(huán)節(jié) Artificial Intelligence Machine Learning: 8 Graduate University , Chinese academy of Sciences. 機(jī)器學(xué)習(xí)概述機(jī)器學(xué)習(xí)概述(5)(5) 機(jī)器學(xué)習(xí)的研究大致可以分為三個階段：機(jī)器學(xué)習(xí)的研究大致可以分為三個階段： 五六十年代的探索階段： 主要受神經(jīng)生理學(xué)、生理學(xué)和生物學(xué)的影響，研究主要側(cè)重于非符號 的神經(jīng)元模型的研究，主要研制通用學(xué)習(xí)系統(tǒng)，即神經(jīng)網(wǎng)絡(luò)或自組織系 統(tǒng)。 主要成果有： 感知機(jī)（Perceptron） Friedberg等模擬隨機(jī)突變和自

7、然選擇過程的程序， Hunt等的決策樹歸納程序CLS。 Artificial Intelligence Machine Learning: 9 Graduate University , Chinese academy of Sciences. 機(jī)器學(xué)習(xí)概述機(jī)器學(xué)習(xí)概述(6)(6) 七十年代的發(fā)展階段： 由于當(dāng)時專家系統(tǒng)的蓬勃發(fā)展，知識獲取成為當(dāng)務(wù)之急，這給機(jī)器學(xué) 習(xí)帶來了契機(jī)，主要側(cè)重于符號學(xué)習(xí)的研究。機(jī)器學(xué)習(xí)的研究脫離了基 于統(tǒng)計的以優(yōu)化理論為基礎(chǔ)的研究方法，提出了基于符號運算為基礎(chǔ)的 機(jī)器學(xué)習(xí)方法，并產(chǎn)生了許多相關(guān)的學(xué)習(xí)系統(tǒng)， 主要系統(tǒng)和算法包括： Winston的積木世界學(xué)習(xí)系統(tǒng)； M

8、ichalski基于邏輯的歸納學(xué)習(xí)系統(tǒng)AQVAL； Michalski和Chilausky的AQ11； Quinlan的ID3程序 Mitchell的版本空間方法。 Artificial Intelligence Machine Learning: 10 Graduate University , Chinese academy of Sciences. 機(jī)器學(xué)習(xí)概述機(jī)器學(xué)習(xí)概述(7)(7) 八九十年代至今的鼎盛階段。 理論研究和應(yīng)用研究也有了新的突破，機(jī)器學(xué)習(xí)的研究進(jìn)入了全面的 、系統(tǒng)化的時期。 主要成果有： 一方面?zhèn)鹘y(tǒng)的符號學(xué)習(xí)的各種方法已日臻完善。Michalski等將AQ11擴(kuò) 充為一

9、個多功能學(xué)習(xí)系統(tǒng)AQ15，ID3算法中使用了熵，從而使決策樹歸 納得到了很大的改進(jìn)。 科學(xué)發(fā)現(xiàn)系統(tǒng)BACON開辟了無導(dǎo)師學(xué)習(xí)的兩個重要研究領(lǐng)域。 神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)在消沉了一段時期后又重新蓬勃發(fā)展起來了，同時計算 機(jī)硬件技術(shù)的高速發(fā)展也為開展大規(guī)模和高性能的人工神經(jīng)網(wǎng)絡(luò)提供了 保障，使得基于神經(jīng)網(wǎng)絡(luò)的連接學(xué)習(xí)從低谷走出，發(fā)展迅猛。其中 Rumelhart等人提出的BP模型，提供了一個訓(xùn)練多層網(wǎng)絡(luò)的實際可行的 方法，克服了Perceptron的大部分局限性。 Artificial Intelligence Machine Learning: 11 Graduate University , Chine

10、se academy of Sciences. 機(jī)器學(xué)習(xí)概述機(jī)器學(xué)習(xí)概述(8)(8) 另一方面，機(jī)器學(xué)習(xí)的基礎(chǔ)理論的研究越來越引起人們的重視。 1984年美國學(xué)者Valiant提出了基于概率近似正確性的學(xué)習(xí)理論（PAC學(xué)習(xí) ），對布爾函數(shù)的一些特殊子類的可學(xué)習(xí)性進(jìn)行了探討，將可學(xué)習(xí)性與 計算復(fù)雜性聯(lián)系在一起，并由此派生出了“計算學(xué)習(xí)理論”（COLT） 我國學(xué)者洪家榮教授證明了兩類布爾表達(dá)式：析取范式和合取范式都是 PAC不可學(xué)習(xí)的，揭示了PAC方法的局限性 1995年，Vapnik出版了“統(tǒng)計學(xué)習(xí)理論”一書。 對PAC的研究是一種理論性，存在性的；Vapnik的研究卻是構(gòu)造性的， 他將這類研究

11、模型稱為支持向量機(jī)SVM（Support Vector Machine）。 Artificial Intelligence Machine Learning: 12 Graduate University , Chinese academy of Sciences. 機(jī)器學(xué)習(xí)概述機(jī)器學(xué)習(xí)概述(9)(9) 機(jī)器學(xué)習(xí)的研究方法 按推理策略分類按推理策略分類 。 1、演繹學(xué)習(xí) ：是一種常規(guī)的邏輯推理方法。其推理的過程就是從公理出 發(fā)，經(jīng)過邏輯變換，推導(dǎo)出結(jié)論。 2、歸納學(xué)習(xí) ：環(huán)境或教師提供一系列正例和反例，通過歸納推理，機(jī)器 將這些例子進(jìn)行推廣，產(chǎn)生一個或一組一般的概念描述。 3、類比學(xué)習(xí) ：利用

12、兩個不同領(lǐng)域（目標(biāo)域和源域）知識的相似性，從源 域的知識（包括相似的特征和其他特征）推斷出目標(biāo)域的相應(yīng)知識的推 理方法。 4、基于解釋的學(xué)習(xí) ：系統(tǒng)已知某個理論及該理論的一個實例，通過解釋 為什么這一實例可以用理論來解決，從而產(chǎn)生關(guān)于待學(xué)概念的一個解釋 。 Artificial Intelligence Machine Learning: 13 Graduate University , Chinese academy of Sciences. Agenda 機(jī)器學(xué)習(xí)概述 歸納學(xué)習(xí) 決策樹學(xué)習(xí) 基于范例的學(xué)習(xí)(CBR) 解釋學(xué)習(xí) 強(qiáng)化學(xué)習(xí) Artificial Intelligence Mac

13、hine Learning: 14 Graduate University , Chinese academy of Sciences. 歸納學(xué)習(xí)(1) 歸納學(xué)習(xí)（歸納學(xué)習(xí)（Inductive LearningInductive Learning） 就是從個別到一般，根據(jù)某個概念的一系列已知的正例和反例，從中就是從個別到一般，根據(jù)某個概念的一系列已知的正例和反例，從中 歸納出一個一般的概念描述歸納出一個一般的概念描述 旨在從大量的經(jīng)驗數(shù)據(jù)中歸納抽取出一般的判定規(guī)則和模式。旨在從大量的經(jīng)驗數(shù)據(jù)中歸納抽取出一般的判定規(guī)則和模式。 是機(jī)器學(xué)習(xí)中最核心、最成熟的分支。是機(jī)器學(xué)習(xí)中最核心、最成熟的分支。

14、 歸納學(xué)習(xí)也稱為：歸納學(xué)習(xí)也稱為： 經(jīng)驗學(xué)習(xí)：歸納學(xué)習(xí)依賴于經(jīng)驗數(shù)據(jù)經(jīng)驗學(xué)習(xí)：歸納學(xué)習(xí)依賴于經(jīng)驗數(shù)據(jù) 基于相似性的學(xué)習(xí)：歸納學(xué)習(xí)依賴于數(shù)據(jù)間的相似形基于相似性的學(xué)習(xí)：歸納學(xué)習(xí)依賴于數(shù)據(jù)間的相似形 歸納的操作：歸納的操作： 泛化泛化( (Generalization)Generalization)：擴(kuò)展某假設(shè)的語義信息，使其能夠包含更擴(kuò)展某假設(shè)的語義信息，使其能夠包含更 多的正例多的正例 特化特化( (Specialization)Specialization)：泛化的相反操作，用于限制概念描述的應(yīng)泛化的相反操作，用于限制概念描述的應(yīng) 用范圍用范圍 Artificial Intelligence

15、 Machine Learning: 15 Graduate University , Chinese academy of Sciences. 歸納學(xué)習(xí)(2) 歸納學(xué)習(xí)的分類和研究領(lǐng)域：歸納學(xué)習(xí)的分類和研究領(lǐng)域： 符號學(xué)習(xí)符號學(xué)習(xí) 有導(dǎo)師學(xué)習(xí)：有導(dǎo)師學(xué)習(xí)： 實例學(xué)習(xí)：導(dǎo)師事先將訓(xùn)練例子（經(jīng)驗數(shù)據(jù)）分類：正、負(fù)例實例學(xué)習(xí)：導(dǎo)師事先將訓(xùn)練例子（經(jīng)驗數(shù)據(jù)）分類：正、負(fù)例 子。由于它產(chǎn)生規(guī)則，所以也稱為概念學(xué)習(xí)子。由于它產(chǎn)生規(guī)則，所以也稱為概念學(xué)習(xí) 無導(dǎo)師學(xué)習(xí)：事先不知道訓(xùn)練例子的分類無導(dǎo)師學(xué)習(xí)：事先不知道訓(xùn)練例子的分類 概念聚類：概念聚類： 機(jī)器發(fā)現(xiàn)機(jī)器發(fā)現(xiàn) 神經(jīng)網(wǎng)絡(luò)：本質(zhì)上是實例學(xué)習(xí)，為區(qū)別起見

16、，稱為聯(lián)結(jié)學(xué)習(xí)（？）神經(jīng)網(wǎng)絡(luò)：本質(zhì)上是實例學(xué)習(xí)，為區(qū)別起見，稱為聯(lián)結(jié)學(xué)習(xí)（？） 學(xué)習(xí)的計算理論學(xué)習(xí)的計算理論 傳統(tǒng)的算法復(fù)雜性分析傳統(tǒng)的算法復(fù)雜性分析 概率近似正確性學(xué)習(xí)研究（計算學(xué)習(xí)理論）概率近似正確性學(xué)習(xí)研究（計算學(xué)習(xí)理論） Artificial Intelligence Machine Learning: 16 Graduate University , Chinese academy of Sciences. 實例學(xué)習(xí)(1) 基本思想：基本思想： 環(huán)境提供給系統(tǒng)一些特殊的實例，這些例子事先由施教者劃分為正例環(huán)境提供給系統(tǒng)一些特殊的實例，這些例子事先由施教者劃分為正例 和反例。和反例。

17、實例學(xué)習(xí)由此進(jìn)行歸納推理，產(chǎn)生適用于更大范圍的一般實例學(xué)習(xí)由此進(jìn)行歸納推理，產(chǎn)生適用于更大范圍的一般 性知識，得到一般的規(guī)則性知識，得到一般的規(guī)則 ，它將覆蓋所有的正例并排除所有的反例，它將覆蓋所有的正例并排除所有的反例 。 環(huán)境提供給學(xué)習(xí)環(huán)境的例子是低水平的信息，這是在特殊情況下執(zhí)行環(huán)境提供給學(xué)習(xí)環(huán)境的例子是低水平的信息，這是在特殊情況下執(zhí)行 環(huán)節(jié)的行為。學(xué)習(xí)環(huán)節(jié)歸納出的規(guī)則是高水平的信息，可以在一般情環(huán)節(jié)的行為。學(xué)習(xí)環(huán)節(jié)歸納出的規(guī)則是高水平的信息，可以在一般情 況下用這些規(guī)則指導(dǎo)執(zhí)行環(huán)節(jié)的工作況下用這些規(guī)則指導(dǎo)執(zhí)行環(huán)節(jié)的工作 Artificial Intelligence Machine

18、Learning: 17 Graduate University , Chinese academy of Sciences. 實例學(xué)習(xí)(2) 兩個空間模型： 例子空間要考慮的問題： 示教例子的質(zhì)量 例子空間的組織和搜索方法 規(guī)則空間要考慮的問題 形成知識的歸納推理方法 搜索規(guī)則空間的方法 對規(guī)則空間的要求 例子空間例子空間規(guī)則空間規(guī)則空間 選擇例子選擇例子 解釋例子解釋例子 Artificial Intelligence Machine Learning: 18 Graduate University , Chinese academy of Sciences. 實例學(xué)習(xí)(3) 按規(guī)則空間搜

19、索方法分類： 數(shù)據(jù)驅(qū)動方法： 變形空間方法：采用統(tǒng)一的形式表示規(guī)則和例子。 改進(jìn)假設(shè)方法：例子和規(guī)則的表示不統(tǒng)一。程序根據(jù) 例子選擇一種操作，用該操作修改H中的規(guī)則 模型驅(qū)動方法： 產(chǎn)生和測試方法：針對示教例子反復(fù)產(chǎn)生和測試假設(shè) 的規(guī)則。利用基于模型的知識產(chǎn)生假設(shè)的規(guī)則，便于 只產(chǎn)生可能合理的假設(shè) 方案示例方法：使用規(guī)則方案的集合來限制可能合理 的規(guī)則形式，最符合示教例子的規(guī)則被認(rèn)為是最合理 的規(guī)則 Artificial Intelligence Machine Learning: 19 Graduate University , Chinese academy of Sciences. 實例

20、學(xué)習(xí)(4) 按任務(wù)的復(fù)雜性劃分為： 學(xué)習(xí)單個概念：由系統(tǒng)提供的某個概念的正例和反例，只 要求系統(tǒng)歸納出一個概念的描述規(guī)則 學(xué)習(xí)多個概念：要求歸納出多個相互獨立的概念 學(xué)習(xí)執(zhí)行多步任務(wù)：執(zhí)行環(huán)節(jié)使用一個操作序列去完成任 務(wù)，即執(zhí)行環(huán)節(jié)進(jìn)行任務(wù)規(guī)劃。因此，歸納出的規(guī)則應(yīng)該 是進(jìn)行任務(wù)規(guī)劃的規(guī)則 Artificial Intelligence Machine Learning: 20 Graduate University , Chinese academy of Sciences. 變形空間方法(1) 基本思想：以整個規(guī)則空間為初始的假設(shè)規(guī)則集合H，根據(jù) 示教例子中的信息，對集合H進(jìn)行一般化或特殊

21、化處理，逐 步縮小集合H，最后使H收斂為只含要求的規(guī)則。 規(guī)則空間中的偏序關(guān)系：它是按一般性和特殊性來建立的一 種概念之間的關(guān)系 排序后的變形空間： 最上面：是最一般的 規(guī)則(概念)，是沒有描述的點，所有的例子都符 合這一概念 最下面一行的各點：是示教正例對應(yīng)的概念，每個點的概念只符合一 個正例 Artificial Intelligence Machine Learning: 21 Graduate University , Chinese academy of Sciences. 變形空間方法(2) 假設(shè)規(guī)則的集合H： H是規(guī)則空間的子集 H中最一般的元素組成的子集稱為G集合 H中最特殊的

22、元素組成的子集稱為S集合 在規(guī)則空間中，H是G和S中間的一段。 可以用G和S來表示H 變形空間方法： 初始：G是最上面一個點，S是最下面的直線（示教正例），H為整 個規(guī)則空間 搜索過程：G下移，S上移，H逐步縮小。 結(jié)果：H收斂為只含一個要求的概念 Artificial Intelligence Machine Learning: 22 Graduate University , Chinese academy of Sciences. 變形空間方法(3) 消除侯選元素算法 (1)正規(guī)的初始H集是整個規(guī)則空間，這時S包含所有可能的示教正例（ 最特殊的概念）。 (2)接收一個新的示教例子。 如果

23、是正例：去掉G中不覆蓋新正例的概念，然后修改S為由新 正例和S原有的元素共同歸納出的最特殊的結(jié)果 如果是反例：從S中去掉覆蓋該反例的概念；然后修改G為由新 反例和G原有元素共同特殊化為最一般的結(jié)果 (3)若G=S，且是單元集合，則轉(zhuǎn)(4)，否則轉(zhuǎn)(2) (4)輸出H中的概念（即G和S） Artificial Intelligence Machine Learning: 23 Graduate University , Chinese academy of Sciences. 變形空間方法(4) 變形空間法的缺點 (1)抗干擾能力差 變形空間法是數(shù)據(jù)驅(qū)動的方法，所有數(shù)據(jù)驅(qū)動的方法都難以處理有干

24、擾的訓(xùn)練例子 算法得到的概念應(yīng)滿足每個示教例子的要求，所以一個錯誤的例子會 造成很大的影響 (2)無法發(fā)現(xiàn)析取概念 Artificial Intelligence Machine Learning: 24 Graduate University , Chinese academy of Sciences. Agenda 機(jī)器學(xué)習(xí)概述 歸納學(xué)習(xí) 決策樹學(xué)習(xí) 基于范例的學(xué)習(xí)(CBR) 解釋學(xué)習(xí) 強(qiáng)化學(xué)習(xí) Artificial Intelligence Machine Learning: 25 Graduate University , Chinese academy of Sciences. 決策

25、樹學(xué)習(xí)(1) 決策樹 通過把實例從根節(jié)點排列到某個葉子節(jié)點來分類實例。 葉子節(jié)點即為實例所屬的分類 樹上每個節(jié)點說明了對實例的某個屬性的測試 節(jié)點的每個后繼分支對應(yīng)于該屬性的一個可能值 正實例：產(chǎn)生正值決策的實例 負(fù)實例：產(chǎn)生負(fù)值決策的實例 決策樹代表實例屬性值約束的合取的析取式。從樹根到樹 葉的每一條路徑對應(yīng)一組屬性測試的合取，樹本身對應(yīng)這 些合取的析取 Artificial Intelligence Machine Learning: 26 Graduate University , Chinese academy of Sciences. 決策樹學(xué)習(xí)(2) InstancesNo. of

26、 wings Broken wings Living statusWing area/ weight Fly 120Alive2.5True 221Alive2.5False 322Alive2.6False 420Alive3.0True 520Dead3.2False 600Alive0False 710Alive0False 820Alive3.4True 920alive2.0False Artificial Intelligence Machine Learning: 27 Graduate University , Chinese academy of Sciences. 決策樹學(xué)

27、習(xí)(3) ID3ID3算法算法 1、是利用信息論原理對大量樣本的屬性進(jìn)行分析和歸納而產(chǎn) 生的。 2、決策樹的根結(jié)點是所有樣本中信息量最大的屬性。樹的中 間結(jié)點是該結(jié)點為根的子樹所包含的樣本子集中信息量最 大的屬性。決策樹的葉結(jié)點是樣本的類別值。 3、用信息增益（即信息論中的互信息）來選擇屬性作為決策 樹的結(jié)點。 Artificial Intelligence Machine Learning: 28 Graduate University , Chinese academy of Sciences. 決策樹學(xué)習(xí)(4) 熵(entropy)：給定有關(guān)某概念的正例和負(fù)例的集合S。對 此BOOLEA

28、N分類的熵為： Entropy(S)= - pos log2(pos) neg log2(neg) “pos”和”neg”分別表示S中正例和負(fù)例的比例。并定義： 0log2(0)=0 如果分類器有c個不同的輸出，則： Entropy(S)= - ci=1pi log2(pi) pi表示S中屬于類i的比例 Artificial Intelligence Machine Learning: 29 Graduate University , Chinese academy of Sciences. 決策樹學(xué)習(xí)(5) 例1：p1 = p2 = 1/2 H1 = -(1/2)*log2(1/2) - (

29、1/2)*log2(1/2) = 1 例2：p1 = 1/4 p2 = 3/4 H2 = -(1/4)* log2(1/4) - (3/4)*log2(3/4)=0.81 例3：p1 = 1 p2 = 0 H3 = -1 * log21 = 0 Artificial Intelligence Machine Learning: 30 Graduate University , Chinese academy of Sciences. 決策樹學(xué)習(xí)(5) 實例集合S中屬性A的信息增益為： Gain(S, A)= Entropy(S) - （|SV|/|S|）Entropy(Sv) vvalues

30、of A Sv表示S的子集，其屬性A的值為V Artificial Intelligence Machine Learning: 31 Graduate University , Chinese academy of Sciences. 決策樹學(xué)習(xí)(6) 思路： 考察任一個屬性，計算其熵值； 對這個特定屬性，考察根據(jù)其不同的屬性值分成的若干子集； 對任意子集，考察不同的類別，計算其熵值并求和； 從所有屬性中，選擇熵值最小（ 或增益最大）的屬性作為當(dāng)前決 策節(jié)點。 Artificial Intelligence Machine Learning: 32 Graduate University ,

31、 Chinese academy of Sciences. 歸納偏置(1) 成功的歸納主要決定于： 經(jīng)驗數(shù)據(jù) 先驗知識 對要學(xué)習(xí)的概念本質(zhì)的假定 歸納偏置是指學(xué)習(xí)程序用來限制概念空間或者在這個空間 中選擇概念的任何標(biāo)準(zhǔn)。它是指概念學(xué)習(xí)中除了正、反例 子外，影響假設(shè)選擇的所有因素。 描述假設(shè)的語言。 程序考慮假設(shè)的空間。 按什么順序假設(shè)的過程。 承認(rèn)定義的準(zhǔn)則，即研究過程帶有已知假設(shè)可以終止還是應(yīng)該繼續(xù) 挑選一個更好的假設(shè)。 Artificial Intelligence Machine Learning: 33 Graduate University , Chinese academy of

32、Sciences. 歸納偏置(2) 必要性： (1)學(xué)習(xí)空間變得越來越大；如果沒有一些方法來修剪它們， 基于搜索的學(xué)習(xí)就沒有實用性。 (2)歸納泛化自身的本質(zhì)：泛化并不保真。 Artificial Intelligence Machine Learning: 34 Graduate University , Chinese academy of Sciences. 歸納偏置(3) 歸納偏置的目標(biāo)是用這樣一種方式來限制目標(biāo)概念集：我 們既可以有效的搜索集合，還可以找到高質(zhì)量的概念定義 可以將概念的質(zhì)量定義為它們能對不包含在訓(xùn)練實例集合 中的物體正確分類的能力。 歸納偏置不是特定的學(xué)習(xí)算法的屬性，

33、而概念表示語言的 屬性可以包括效率和正確性。 - 學(xué)習(xí)算法搜索概念空間；如果這個空間可管理，并且包含性能 很好的概念，則任何合理的學(xué)習(xí)算法應(yīng)該能找到這些定義；如果空 間非常復(fù)雜，算法的成功完成就會受到限制。 Artificial Intelligence Machine Learning: 35 Graduate University , Chinese academy of Sciences. Agenda 機(jī)器學(xué)習(xí)概述 歸納學(xué)習(xí) 決策樹學(xué)習(xí) 基于范例的學(xué)習(xí)(CBR) 解釋學(xué)習(xí) 強(qiáng)化學(xué)習(xí) Artificial Intelligence Machine Learning: 36 Graduat

34、e University , Chinese academy of Sciences. CBR(1) 人們?yōu)榱私鉀Q一個新問題，先是進(jìn)行回憶，從記憶中找到 一個與新問題相似的范例，然后把該范例中的有關(guān)信息和 知識復(fù)用到新問題的求解之中。 在基于范例推理 (Case-Based Reasoning, 簡稱CBR)中， 把當(dāng)前所面臨的問題或情況稱為目標(biāo)范例(target case)， 而把記憶的問題或情況稱為源范例(base case)。粗略地說 ，基于范例推理就是由目標(biāo)范例的提示而獲得記憶中的源 范例，并由源范例來指導(dǎo)目標(biāo)范例求解的一種策略。 Artificial Intelligence Mac

35、hine Learning: 37 Graduate University , Chinese academy of Sciences. CBR(2) 范例（范例（case）：“范例是一段帶有上下文信息的知識，該 知識表達(dá)了推理機(jī)在達(dá)到其目標(biāo)的過程中能起關(guān)鍵作用的 經(jīng)驗”。 具體來說，一個范例應(yīng)具有如下特性： 范例表示了與某個上下文有關(guān)的具體知識，這種知識具有可操作性 。 范例可以是各式各樣的，可有不同的形狀和粒度，可涵蓋或大或小 的時間片，可帶有問題的解答或動作執(zhí)行后的效應(yīng)。 范例記錄了有用的經(jīng)驗，這種經(jīng)驗?zāi)軒椭评頇C(jī)在未來更容易地達(dá) 到目標(biāo)，或提醒推理機(jī)失敗發(fā)生的可能性有多大等等。 Art

36、ificial Intelligence Machine Learning: 38 Graduate University , Chinese academy of Sciences. CBR(3) 傳統(tǒng)的推理觀點是把推理理解為通過前因后果鏈(如規(guī)則鏈)演繹出結(jié)論 的一個過程。許多專家系統(tǒng)使用的就是這種規(guī)則鏈?zhǔn)降耐评矸椒ā?于知識易于表示成啟發(fā)式規(guī)則形式的問題來說，基于規(guī)則的方法比較 適合，如分類問題和診斷問題等。但是人們在遇到一個新的問題的時 候，一般先是回憶，從記憶中找到一個與新的問題相似的案例，然后 把該案例中的有關(guān)信息和知識復(fù)用到新問題的求解之中。 基于范例推理中知識表示是以范例為基

37、礎(chǔ)，范例的獲取比規(guī)則獲取要 容易,大大簡化知識獲取。對過去的求解結(jié)果進(jìn)行復(fù)用，而不是再次從 頭推導(dǎo)，可以提高對新問題的求解效率。過去求解成功或失敗的經(jīng)歷 可以指導(dǎo)當(dāng)前求解時該怎樣走向成功或避開失敗，這樣可以改善求解 的質(zhì)量。對于那些目前沒有或根本不存在可以通過計算推導(dǎo)來解決的 問題。如在法律中的判例，基于范例推理能很好發(fā)揮作用。 Artificial Intelligence Machine Learning: 39 Graduate University , Chinese academy of Sciences. CBR(4) CBR采用的是和基于規(guī)則鏈推理完全不同的觀點，在CBR 中，使

38、用的主要知識不是規(guī)則而是范例(case)，這些范例 記錄了過去發(fā)生的種種相關(guān)情況。 對CBR來講，求解一個問題的結(jié)論不是通過鏈?zhǔn)酵评懋a(chǎn)生 的，而是從記憶里或范例庫中找到與當(dāng)前問題最相關(guān)的范 例，然后對該范例作必要的改動以適合當(dāng)前問題。 CBR的基本思想是：人們的推理過程是基于特殊的經(jīng)驗而 不是一組總的指導(dǎo)原則。 和其他基于AI的推理方法比較，CBR是通過聯(lián)想（或類 比），從過去的案例出發(fā)，把過去的案例和當(dāng)前面臨的問 題相比較做出決策的過程。問題的解答來自于過去的經(jīng)驗 而不是規(guī)則，這些經(jīng)驗以案例的方式存貯 Artificial Intelligence Machine Learning: 40

39、Graduate University , Chinese academy of Sciences. CBR的過程模型 新問題 新范例檢索 保存 修正范例解答范例 確認(rèn)解建議解 檢索 建議粗略解 調(diào)整辯護(hù) 評批 實際評估 存儲 歷史范例 歷史范例 范例庫 基于范例的推理是一個“回憶和調(diào)整”或“回憶和比較”的過程。在范例推理中，范 例用于輔助理解和分析情景并用于輔助解決問題。我們的日常推理中，情景的理解、 分析和問題的解決過程一般是相輔相成的。當(dāng)我們還沒有理解一個問題所處的情景時 ，是不可能解決該問題的；另一方面，我們又需要通過解決某個問題才能充分理解與 它有關(guān)的情況。我們常常通過采用一些評估方

40、法去檢驗結(jié)果來評價求解結(jié)論的好壞； 同時我們在評估的過程中又需要解決新的問題。 Artificial Intelligence Machine Learning: 41 Graduate University , Chinese academy of Sciences. Agenda 機(jī)器學(xué)習(xí)概述 歸納學(xué)習(xí) 決策樹學(xué)習(xí) 基于范例的學(xué)習(xí)(CBR) 解釋學(xué)習(xí)解釋學(xué)習(xí) 強(qiáng)化學(xué)習(xí) Artificial Intelligence Machine Learning: 42 Graduate University , Chinese academy of Sciences. 解釋學(xué)習(xí)解釋學(xué)習(xí)(1) 實例中進(jìn)

41、行學(xué)習(xí)歷來是機(jī)器學(xué)習(xí)領(lǐng)域研究的焦點，早期的工作基本上局實例中進(jìn)行學(xué)習(xí)歷來是機(jī)器學(xué)習(xí)領(lǐng)域研究的焦點，早期的工作基本上局 限于歸納學(xué)習(xí)的范疇，相應(yīng)的研究成果很少或基本沒有考慮背景知識對限于歸納學(xué)習(xí)的范疇，相應(yīng)的研究成果很少或基本沒有考慮背景知識對 學(xué)習(xí)過程的影響。因此，這些方法從根本上來說是以數(shù)據(jù)為第一位的，學(xué)習(xí)過程的影響。因此，這些方法從根本上來說是以數(shù)據(jù)為第一位的， 沒有反映出人工智能領(lǐng)域基于知識的研究和發(fā)展傾向。沒有反映出人工智能領(lǐng)域基于知識的研究和發(fā)展傾向。 從從20世紀(jì)世紀(jì)80年代中期開始，機(jī)器學(xué)習(xí)研究重點開始由以歸納方法為主的年代中期開始，機(jī)器學(xué)習(xí)研究重點開始由以歸納方法為主的 數(shù)據(jù)密

42、集型學(xué)習(xí)方法的研究向多樣化方法發(fā)展，開始研究分析方法、遺數(shù)據(jù)密集型學(xué)習(xí)方法的研究向多樣化方法發(fā)展，開始研究分析方法、遺 傳算法、連接學(xué)習(xí)等。其中分析學(xué)習(xí)利用豐富的領(lǐng)域知識為背景，只需傳算法、連接學(xué)習(xí)等。其中分析學(xué)習(xí)利用豐富的領(lǐng)域知識為背景，只需 要通過分析很少的幾個例子（通常是一個例子），就能將例子泛化為對要通過分析很少的幾個例子（通常是一個例子），就能將例子泛化為對 目標(biāo)概念的解釋目標(biāo)概念的解釋(通過泛化實例的解釋，而不是泛化實例自身通過泛化實例的解釋，而不是泛化實例自身 ). 分析方法主要依賴于演繹推理，以產(chǎn)生更有效的問題求解知識，如搜索分析方法主要依賴于演繹推理，以產(chǎn)生更有效的問題求解知

43、識，如搜索 控制知識。因此，分析學(xué)習(xí)的主要目的是提高問題的求解效率，而不是控制知識。因此，分析學(xué)習(xí)的主要目的是提高問題的求解效率，而不是 獲取新的概念描述。獲取新的概念描述。 Artificial Intelligence Machine Learning: 43 Graduate University , Chinese academy of Sciences. 解釋學(xué)習(xí)解釋學(xué)習(xí)(2) 基于解釋的學(xué)習(xí)是分析學(xué)習(xí)的主要方式，基于解釋的學(xué)習(xí)（基于解釋的學(xué)習(xí)是分析學(xué)習(xí)的主要方式，基于解釋的學(xué)習(xí)（ 簡稱簡稱EBL）是將大量的成果匯集在一個統(tǒng)一、簡單的框架內(nèi)）是將大量的成果匯集在一個統(tǒng)一、簡單的框架內(nèi)

44、 ，通過分析為什么實例是某個目標(biāo)概念的一個具體例子，通過分析為什么實例是某個目標(biāo)概念的一個具體例子， EBL對分析過程（一個解釋）加以推廣，剔去與具體例子有對分析過程（一個解釋）加以推廣，剔去與具體例子有 關(guān)的成分，從而產(chǎn)生目標(biāo)概念的一個描述。關(guān)的成分，從而產(chǎn)生目標(biāo)概念的一個描述。 EBL的初始狀態(tài)： DT（Domain Theory）包含一組事實和規(guī)則，用于證明（解釋）訓(xùn)練 實例如何滿足目標(biāo)概念。 TC（Target Concept）是待學(xué)概念的一個非操作性描述。 E為目標(biāo)概念的一個例子。 C（Operationality Criterion）是定義在概念描述上的一個二階謂詞， 用以表示學(xué)習(xí)

45、得到的目標(biāo)概念可用哪些基本的、可操作的概念表示， 以使這些知識能用于問題求解活動。 Artificial Intelligence Machine Learning: 44 Graduate University , Chinese academy of Sciences. 解釋學(xué)習(xí)解釋學(xué)習(xí)(3) 基于解釋的學(xué)習(xí)過程基于解釋的學(xué)習(xí)過程:可劃分為下面兩個步驟：可劃分為下面兩個步驟： （1） 分析階段：使用領(lǐng)域理論建立一個證明訓(xùn)練例子滿足分析階段：使用領(lǐng)域理論建立一個證明訓(xùn)練例子滿足 目標(biāo)概念定義（初始描述）的解釋結(jié)構(gòu)，該結(jié)構(gòu)可表示為一目標(biāo)概念定義（初始描述）的解釋結(jié)構(gòu)，該結(jié)構(gòu)可表示為一 棵證明樹，又稱為解釋樹，它用于解釋為什么實例是目標(biāo)概棵證明樹，又稱為解釋樹，它用于解釋為什么實例是目標(biāo)概 念的一個實例，其每個分枝的葉結(jié)點上的表達(dá)式都必須滿足念的一個實例，其每個分枝的葉結(jié)點上的表達(dá)式都必須滿足 可操作性準(zhǔn)則。可操作性準(zhǔn)則。 （2） 基于解釋的泛化（基于解釋的泛化（Explanation-Based Generalization ，簡稱，簡稱EBG）階段：通過將實例證明樹中的常量用變量進(jìn)行）階段：通過將實例證明樹中的常量用變量進(jìn)行 替換，從而完成解釋的泛化，并