人工智能與專家系統(tǒng)-第七章

第七章機(jī)器學(xué)習(xí)7.1概述7.2歸納學(xué)習(xí)7.3決策樹學(xué)習(xí)7.4基于實(shí)例的學(xué)習(xí)本章小結(jié)課后練習(xí)題普通高等院校“十二五”規(guī)劃教材第七章機(jī)器學(xué)習(xí)機(jī)器能否像人類一樣具有學(xué)習(xí)能力呢？1959年美國的塞繆爾設(shè)計(jì)了一個(gè)下棋程序，這個(gè)程序具有學(xué)習(xí)能力，它可以在不斷的對弈中改善自己的棋藝。4年后，這個(gè)程序戰(zhàn)勝了設(shè)計(jì)者本人。又過了3年，這個(gè)程序戰(zhàn)勝了美國一個(gè)保持8年之久的常勝不敗的冠軍。它向人們展示了機(jī)器學(xué)習(xí)的能力。本章主要介紹機(jī)器學(xué)習(xí)的基本概念和歸納學(xué)習(xí)、決策樹學(xué)習(xí)、基于實(shí)例的學(xué)習(xí)等具體的機(jī)器學(xué)習(xí)方法，希望讀者能對這一領(lǐng)域有一個(gè)初步的了解和認(rèn)識(shí)。普通高等院?！笆濉币?guī)劃教材7.1

概述機(jī)器學(xué)習(xí)的研究是根據(jù)生理學(xué)、認(rèn)知科學(xué)等對人類學(xué)習(xí)機(jī)理的了解，建立人類學(xué)習(xí)過程的計(jì)算模型或認(rèn)識(shí)模型，發(fā)展各種學(xué)習(xí)理論和學(xué)習(xí)方法，研究通用的學(xué)習(xí)算法并進(jìn)行理論上的分析，建立面向任務(wù)的具有特定應(yīng)用的學(xué)習(xí)系統(tǒng)。這些研究目標(biāo)相互影響相互促進(jìn)。自從1980年在卡內(nèi)基-梅隆大學(xué)召開第一屆機(jī)器學(xué)術(shù)研討會(huì)以來，機(jī)器學(xué)習(xí)的研究工作發(fā)展很快，已成為中心課題之一。普通高等院?！笆濉币?guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)1．關(guān)于機(jī)器學(xué)習(xí)的定義Langley(1996)定義的“機(jī)器學(xué)習(xí)是一門人工智能的科學(xué)，該領(lǐng)域的主要研究對象是人工智能，特別是如何在經(jīng)驗(yàn)學(xué)習(xí)中改善具體算法的性能?！盩omMitchell的機(jī)器學(xué)習(xí)(1997)對信息論中的一些概念有詳細(xì)的解釋,其中定義機(jī)器學(xué)習(xí)時(shí)提到，“機(jī)器學(xué)習(xí)是對能通過經(jīng)驗(yàn)自動(dòng)改進(jìn)的計(jì)算機(jī)算法的研究”Alpaydin(2004)也提出自己對機(jī)器學(xué)習(xí)的定義，“機(jī)器學(xué)習(xí)是用數(shù)據(jù)或以往的經(jīng)驗(yàn)，以此優(yōu)化計(jì)算機(jī)程序的性能標(biāo)準(zhǔn)?！鳖櫭剂x，機(jī)器學(xué)習(xí)是研究如何使用機(jī)器來模擬人類學(xué)習(xí)活動(dòng)的一門學(xué)科。普通高等院?！笆濉币?guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)稍為嚴(yán)格的提法是：機(jī)器學(xué)習(xí)是一門研究機(jī)器獲取新知識(shí)和新技能，并識(shí)別現(xiàn)有知識(shí)的學(xué)問。這里所說的“機(jī)器”，指的就是計(jì)算機(jī)，現(xiàn)在是電子計(jì)算機(jī)，以后還可能是中子計(jì)算機(jī)、光子計(jì)算機(jī)或神經(jīng)計(jì)算機(jī)等等。普通高等院?！笆濉币?guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)2．機(jī)器學(xué)習(xí)的發(fā)展簡史最早的具有學(xué)習(xí)能力的程序是

年美國的

設(shè)計(jì)的跳棋程序。第一階段是20世紀(jì)50到60年代的探索階段。主要成果有：感知機(jī)(Perceptron)；Friedberg等模擬隨機(jī)突變和自然選擇過程的程序；Hunt等的決策樹歸納程序CLS。第二階段是20世紀(jì)70年代的發(fā)展階段。主要系統(tǒng)和算法包括：Winston的積木世界學(xué)習(xí)系統(tǒng)；Michalski基于邏輯的歸納學(xué)習(xí)系統(tǒng)AQVAL；Michalski和Chilausky的AQII；Quinlan的ID3程序；Mitchell的版本空間方法。普通高等院?！笆濉币?guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)第三階段是20世紀(jì)80年代至今的鼎盛階段。主要成果有：

一方面?zhèn)鹘y(tǒng)的符號(hào)學(xué)習(xí)的各種方法已日臻完善。

另一方面，機(jī)器學(xué)習(xí)的基礎(chǔ)理論的研究越來越引起人們的重視。3．機(jī)器學(xué)習(xí)的一般步驟圖7.1.1機(jī)器學(xué)習(xí)的基本系統(tǒng)結(jié)構(gòu)模型普通高等院?！笆濉币?guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)“環(huán)境”是指外部信息的來源，它為系統(tǒng)的學(xué)習(xí)提供有關(guān)信息；“學(xué)習(xí)”是系統(tǒng)的學(xué)習(xí)結(jié)構(gòu)，從環(huán)境中取得外部信息，然后經(jīng)分析、綜合、類比和歸納等思維過程獲得知識(shí)，并存入知識(shí)庫中更新知識(shí)庫；“知識(shí)庫”用于存放由學(xué)習(xí)得到的知識(shí)，在存儲(chǔ)時(shí)要適當(dāng)?shù)慕M織，便于應(yīng)用和維護(hù)；“執(zhí)行”環(huán)節(jié)是基于學(xué)習(xí)得到的新的知識(shí)庫，它執(zhí)行一系列的任務(wù)。此外還需將執(zhí)行結(jié)果信息反饋給學(xué)習(xí)環(huán)節(jié)，以完成對新“知識(shí)庫”的評價(jià)，指導(dǎo)進(jìn)一步的學(xué)習(xí)工作。普通高等院?！笆濉币?guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)圖7.1.2機(jī)器系統(tǒng)學(xué)習(xí)環(huán)節(jié)的一般過程普通高等院校“十二五”規(guī)劃教材7.1.2機(jī)器學(xué)習(xí)方法的分類1．按學(xué)習(xí)時(shí)所用的分類方法進(jìn)行分類：（1）機(jī)械式學(xué)習(xí)（2）示教學(xué)習(xí)（3）類比學(xué)習(xí)（4）解釋學(xué)習(xí)2．按推理的策略分類（1）演繹學(xué)習(xí)（2）歸納學(xué)習(xí)3．按綜合因素分類（1）連接學(xué)習(xí)（2）分析學(xué)習(xí)（3）分類器系統(tǒng)普通高等院?！笆濉币?guī)劃教材7.1.3機(jī)器學(xué)習(xí)中的推理方法（1）演繹推理演繹推理是結(jié)論可從叫做前提的已知事實(shí)必然的得出的推理。如果前提為真，則結(jié)論必然為真。（2）歸納推理所謂歸納推理，就是從個(gè)別性知識(shí)推出一般性結(jié)論的推理。歸納推理的前提是其結(jié)論的必要條件。（3）類比推理類比推理是根據(jù)兩個(gè)或兩類對象有部分屬性相同，從而推出它們的其他屬性也相同的推理。簡稱類推、類比。它是以關(guān)于兩個(gè)事物某些屬性相同的判斷為前提，推出兩個(gè)事物的其他屬性相同的結(jié)論的推理。普通高等院校“十二五”規(guī)劃教材7.2歸納學(xué)習(xí)歸納學(xué)習(xí)是人工智能中發(fā)展較為成熟，并得到廣泛的研究和應(yīng)用的學(xué)習(xí)方法。它是是由一些實(shí)例或反例，通過歸納推理得出該概念的一般描述。實(shí)現(xiàn)實(shí)例到規(guī)則的歸納推理過程就是歸納學(xué)習(xí)過程。它的一般操作是泛化和特化，泛化用來擴(kuò)展假設(shè)的語義信息，以使其能夠包含更多的正例，應(yīng)用于更多的情況。特化是泛化的相反的操作，用于限制概念描述的應(yīng)用范圍。普通高等院?！笆濉币?guī)劃教材7.2.1歸納學(xué)習(xí)的基本概念歸納是指從個(gè)別到一般，從部分到整體的推論行為。歸納推理是應(yīng)用歸納方法所進(jìn)行的推理，即從足夠多的實(shí)例中歸納出一般性的知識(shí)，它是一種從個(gè)別到一般的推理。歸納學(xué)習(xí)是應(yīng)用歸納推理進(jìn)行學(xué)習(xí)的一種學(xué)習(xí)方法。歸納學(xué)習(xí)旨在從大量的經(jīng)驗(yàn)數(shù)據(jù)中歸納抽取出一般的判定規(guī)則和模式，是從特殊情況推導(dǎo)出一般規(guī)則的學(xué)習(xí)方法。它的目標(biāo)是形成合理的能解釋已知事實(shí)和預(yù)見新事實(shí)的一般性結(jié)論。歸納學(xué)習(xí)由于依賴于經(jīng)驗(yàn)數(shù)據(jù)，因此又被稱為經(jīng)驗(yàn)學(xué)習(xí)；由于依賴于數(shù)據(jù)間的相似性，因此也被稱為基于相似性的學(xué)習(xí)。普通高等院?！笆濉币?guī)劃教材7.2.1歸納學(xué)習(xí)的基本概念1．歸納學(xué)習(xí)的雙空間模型圖7.2.1雙空間模型普通高等院校“十二五”規(guī)劃教材7.2.1歸納學(xué)習(xí)的基本概念2．歸納學(xué)習(xí)的分類歸納學(xué)習(xí)按其有無教師指導(dǎo)可分為示例學(xué)習(xí)和觀察與發(fā)現(xiàn)學(xué)習(xí)。示例學(xué)習(xí)，又叫做概念獲取——它的任務(wù)是確定概念的一般描述，這個(gè)描述應(yīng)能解釋所有給定的正例，并排除所有給定的反例，由于學(xué)習(xí)是根據(jù)教師分好類的正反例進(jìn)行學(xué)習(xí)，因此是有教師學(xué)習(xí)。觀察與發(fā)現(xiàn)學(xué)習(xí)又稱為描述的泛化——這類學(xué)習(xí)沒有教師的幫助，它要產(chǎn)生解釋所有或大多數(shù)觀察的規(guī)律和規(guī)則，這些都是未經(jīng)分類的觀察學(xué)習(xí)或是由系統(tǒng)自身的功能去發(fā)現(xiàn)。普通高等院校“十二五”規(guī)劃教材7.2.1歸納學(xué)習(xí)的基本概念歸納學(xué)習(xí)還可以劃分為單概念學(xué)習(xí)和多概念學(xué)習(xí)兩類。典型的單概念學(xué)習(xí)系統(tǒng)包括米切爾的基于數(shù)據(jù)驅(qū)動(dòng)的變型空間法，昆蘭的ID3方法，狄特利希和米哈爾斯基提出的基于模型驅(qū)動(dòng)的Induce算法。典型的多概念學(xué)習(xí)方法和系統(tǒng)有米哈爾斯基的

、元

和

程序等。多概念學(xué)習(xí)任務(wù)可以劃分成多個(gè)單概念學(xué)習(xí)的任務(wù)來完成。多概念學(xué)習(xí)與單概念學(xué)習(xí)的差別在于多概念學(xué)習(xí)必須處理概念之間的沖突問題。普通高等院校“十二五”規(guī)劃教材7.2.2變型空間學(xué)習(xí)1．變型空間的結(jié)構(gòu)7.2.2變型空間排序的關(guān)系普通高等院?！笆濉币?guī)劃教材7.2.2變型空間學(xué)習(xí)2.候選項(xiàng)刪除算法算法過程：（1）初始化H為整個(gè)概念空間（規(guī)則空間）。（2）接受一個(gè)新的示教例子。（3）重復(fù)步驟（2），直到G=S，且使這兩個(gè)集合都只含有一個(gè)元素為止。（4）輸出H中的概念，即輸出G或S。普通高等院?！笆濉币?guī)劃教材7.3決策樹學(xué)習(xí)決策樹學(xué)習(xí)是應(yīng)用最廣泛的歸納學(xué)習(xí)，特別是在專家系統(tǒng)、工業(yè)控制過程、金融保險(xiǎn)預(yù)測以及醫(yī)療診斷等領(lǐng)域。如果學(xué)習(xí)的任務(wù)是對一個(gè)大的實(shí)例集合做概念分類的歸納定義，而這些例子都是用一些無結(jié)構(gòu)的屬性值對來表示，那么可以采用決策樹學(xué)習(xí)算法。亨特(Hunt)的概念學(xué)習(xí)系統(tǒng)CLS是一種早期的基于決策樹的歸納學(xué)習(xí)系統(tǒng)。1979年，昆蘭對此進(jìn)行了發(fā)展，提出了ID3算法，該算法不僅能方便地表示概念屬性值信息的結(jié)構(gòu)，而且能從大量實(shí)例數(shù)據(jù)中有效地生成相應(yīng)的決策樹模型。普通高等院校“十二五”規(guī)劃教材7.3.1決策樹及構(gòu)造算法所謂決策樹是一個(gè)類似流程圖的樹結(jié)構(gòu)，其中樹的每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)特征（屬性）變量值的檢驗(yàn)，每個(gè)分枝表示檢驗(yàn)結(jié)果，樹枝上的葉結(jié)點(diǎn)代表所關(guān)心的因變量的取值，最頂端的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)用矩形框表示，葉結(jié)點(diǎn)用橢圓框表示。從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)都有唯一的一條路徑，這條路徑就是一條決策“規(guī)則”。如果每個(gè)內(nèi)結(jié)點(diǎn)都恰好有兩個(gè)分枝，則稱為二叉樹，類似可定義多叉樹，在所有的決策樹中，二叉樹最為常用。普通高等院?！笆濉币?guī)劃教材7.3.1決策樹及構(gòu)造算法

普通高等院?！笆濉币?guī)劃教材7.3.2基本的決策樹學(xué)習(xí)算法

普通高等院校“十二五”規(guī)劃教材7.3.2基本的決策樹學(xué)習(xí)算法

普通高等院?！笆濉币?guī)劃教材7.4基于實(shí)例的學(xué)習(xí)基于實(shí)例的學(xué)習(xí)采用保存實(shí)例本身的方法來表達(dá)從實(shí)例集提取出的知識(shí)，并將未知的新實(shí)例與現(xiàn)有的類已知的實(shí)例聯(lián)系起來進(jìn)行操作。這種方法直接在樣本上工作，不需要建立規(guī)則?；趯?shí)例的學(xué)習(xí)方法包括最近鄰法、局部加權(quán)回歸法、基于范例的推理法等等。基于實(shí)例的學(xué)習(xí)只是簡單地把訓(xùn)練樣例存儲(chǔ)起來，對這些實(shí)例進(jìn)行泛化的工作被推遲到必須分類新的實(shí)例時(shí)，所以也被稱為消極學(xué)習(xí)法。普通高等院校“十二五”規(guī)劃教材7.4.1k-近鄰算法最近鄰法通過距離函數(shù)來判