第七章機(jī)器學(xué)習(xí)7.1機(jī)器學(xué)習(xí)的定義和發(fā)展歷史7.2機(jī)器學(xué)習(xí)的主要策略與基本結(jié)構(gòu)7.3歸納學(xué)習(xí)7.4決策樹學(xué)習(xí)7.5類比學(xué)習(xí)7.6解釋學(xué)習(xí)7.7神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)7.8知識(shí)發(fā)現(xiàn)7.1機(jī)器學(xué)習(xí)的定義和發(fā)展歷史機(jī)器學(xué)習(xí)的定義機(jī)器學(xué)習(xí)的基本概念：按照人工智能大師西蒙的觀點(diǎn)，學(xué)習(xí)就是系統(tǒng)在不斷重復(fù)的工作中對本身能力的增強(qiáng)或者改進(jìn)，使得系統(tǒng)在下一次執(zhí)行同樣任務(wù)或類似任務(wù)時(shí)，會(huì)比現(xiàn)在做得更好或效率更高。機(jī)器學(xué)習(xí)的定義:機(jī)器學(xué)習(xí)是研究如何使用機(jī)器來模擬人類學(xué)習(xí)活動(dòng)的一門學(xué)科。稍為嚴(yán)格的提法是：機(jī)器學(xué)習(xí)是一門研究機(jī)器獲取新知識(shí)和新技能，并識(shí)別現(xiàn)有知識(shí)的學(xué)問。機(jī)器學(xué)習(xí)的發(fā)展史機(jī)器學(xué)習(xí)是人工智能應(yīng)用研究較為重要的分支，它的發(fā)展過程大體上可分為4個(gè)時(shí)期：1.第一階段是在50年代中葉到60年代中葉，屬于熱烈時(shí)期。2.第二階段在60年代中葉至70年代中葉，被稱為機(jī)器學(xué)習(xí)的冷靜時(shí)期。3.第三階段從70年代中葉至80年代中葉，稱為復(fù)興時(shí)期。4.機(jī)器學(xué)習(xí)的最新階段始于1986年。一方面，由于神經(jīng)網(wǎng)絡(luò)研究的重新興起，另一方面，對實(shí)驗(yàn)研究和應(yīng)用研究得到前所未有的重視。我國的機(jī)器學(xué)習(xí)研究開始進(jìn)入穩(wěn)步發(fā)展和逐漸繁榮的新時(shí)期。7.1機(jī)器學(xué)習(xí)的定義和發(fā)展歷史機(jī)器學(xué)習(xí)進(jìn)入新階段的表現(xiàn)機(jī)器學(xué)習(xí)已經(jīng)成為新的邊緣學(xué)科并在高校形成課程綜合各種學(xué)習(xí)方法機(jī)器學(xué)習(xí)與人工智能問題的統(tǒng)一性觀點(diǎn)正在形成各種學(xué)習(xí)方法的應(yīng)用范圍不斷擴(kuò)大數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)的研究已經(jīng)形成熱潮與機(jī)器學(xué)習(xí)有關(guān)的學(xué)術(shù)活動(dòng)空前活躍7.1機(jī)器學(xué)習(xí)的定義和發(fā)展歷史7.2機(jī)器學(xué)習(xí)的主要策略與基本結(jié)構(gòu)四種學(xué)習(xí)策略機(jī)械學(xué)習(xí)示教學(xué)習(xí)類比學(xué)習(xí)示例學(xué)習(xí)學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)

環(huán)境向系統(tǒng)的學(xué)習(xí)部分提供某些信息，學(xué)習(xí)部分利用這些信息修改知識(shí)庫，以增進(jìn)系統(tǒng)執(zhí)行部分完成任務(wù)的效能，執(zhí)行部分根據(jù)知識(shí)庫完成任務(wù)，同時(shí)把獲得的信息反饋給學(xué)習(xí)部分。在具體的應(yīng)用中，環(huán)境，知識(shí)庫和執(zhí)行部分決定了具體的工作內(nèi)容，學(xué)習(xí)部分所需要解決的問題完全由上述3部分確定。影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的重要因素

(1)影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的最重要的因素是環(huán)境向系統(tǒng)提供的信息。(2)知識(shí)庫是影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的第二個(gè)因素。知識(shí)的表示有多種形式，在選擇表示方式時(shí)要兼顧以下4個(gè)方面：表達(dá)能力強(qiáng)易于推理容易修改知識(shí)庫知識(shí)表示易于擴(kuò)展。7.3機(jī)械學(xué)習(xí)1、機(jī)械學(xué)習(xí)的模式

機(jī)械學(xué)習(xí)是最簡單的機(jī)器學(xué)習(xí)方法。機(jī)械學(xué)習(xí)就是記憶，即把新的知識(shí)存儲(chǔ)起來，供需要時(shí)檢索調(diào)用，而不需要計(jì)算和推理。

機(jī)械學(xué)習(xí)又是最基本的學(xué)習(xí)過程。任何學(xué)習(xí)系統(tǒng)都必須記住它們獲取的知識(shí)。在機(jī)械學(xué)習(xí)系統(tǒng)中，知識(shí)的獲取是以較為穩(wěn)定和直接的方式進(jìn)行的，不需要系統(tǒng)進(jìn)行過多的加工。2、數(shù)據(jù)化簡

Lenat,HayesRoth，和Klahr等人于1979年關(guān)于機(jī)械學(xué)習(xí)提出一種有趣的觀點(diǎn)。他們指出，可以把機(jī)械學(xué)習(xí)看成是數(shù)據(jù)化簡分級中的第一級。數(shù)據(jù)化簡與計(jì)算機(jī)語言編譯類似；其目的是把原始信息變成可執(zhí)行的信息。在機(jī)械學(xué)習(xí)中我們只記憶計(jì)算的輸入輸出，忽略了計(jì)算過程，這樣就把計(jì)算問題化簡成存取問題。見下圖數(shù)據(jù)化簡級別圖2、數(shù)據(jù)化簡

比方說第一次要我們解一個(gè)一元二次方程的時(shí)候，我們必須使用很長的一段推導(dǎo)才能得出解方程的求根公式。但是一旦有了求根公式，以后再解一元二次方程時(shí)，就不必重復(fù)以前的推導(dǎo)過程，可以直接使用求根公式計(jì)算出根，這樣就把推導(dǎo)問題簡化成計(jì)算問題。同樣地，歸納過程可以簡化成推導(dǎo)過程。

正像計(jì)算問題可以簡化成存取問題一樣，其它的推理過程也可以簡化成較為簡單的任務(wù)。例如推導(dǎo)可以簡化成計(jì)算。3、主要問題

對于機(jī)械學(xué)習(xí)，需要注意3個(gè)重要的問題：存儲(chǔ)組織，穩(wěn)定性和存儲(chǔ)與計(jì)算之間的權(quán)衡。（1）存儲(chǔ)組織信息：采用適當(dāng)?shù)拇鎯?chǔ)方式，使檢索速度盡可能地快，是機(jī)械學(xué)習(xí)中的重要問題。（2）環(huán)境的穩(wěn)定性與存儲(chǔ)信息的適用性問題：機(jī)械學(xué)習(xí)系統(tǒng)必須保證所保存的信息適應(yīng)于外界環(huán)境變化的需要，這也就是所謂的信息適用性問題。（3）存儲(chǔ)與計(jì)算之間的權(quán)衡：對于機(jī)械學(xué)習(xí)來說很重要的一點(diǎn)是它不能降低系統(tǒng)的效率?？紤]一個(gè)決定受損汽車修理費(fèi)用的汽車保險(xiǎn)程序

這個(gè)程序的輸入是被損壞的汽車的描述，包括制造廠家、生產(chǎn)年代、汽車的種類以及記錄汽車被損壞部位和損壞程度的一個(gè)表，程序的輸出是保險(xiǎn)公司應(yīng)付的修理費(fèi)用。這個(gè)系統(tǒng)是個(gè)機(jī)械記憶系統(tǒng)。為了估算損壞汽車的修理費(fèi)用，程序系統(tǒng)必須在存儲(chǔ)器中查找同一廠家、同一生產(chǎn)年代、損壞的部位和程度相同的汽車，然后把對應(yīng)的費(fèi)用提交給用戶。如果系統(tǒng)沒有發(fā)現(xiàn)這樣的汽車，則它使用保險(xiǎn)公司公布的賠償規(guī)則估算出一個(gè)修理費(fèi)用，然后把廠家、生產(chǎn)日期和損壞情況等特征與估算出的費(fèi)用保存起來，以便將來查找使用。

7.3歸納學(xué)習(xí)歸納學(xué)習(xí)的定義（1）歸納（induction）是人類拓展認(rèn)識(shí)能力的重要方法，是一種從個(gè)別到一般的，從部分到整體的推理行為。（2）歸納推理是應(yīng)用歸納方法，從足夠多的具體事例中歸納出一般性知識(shí)，提取事物的一般規(guī)律；它是一種從個(gè)別到一般的推理。在進(jìn)行歸納時(shí)，一般不可能考慮全部相關(guān)實(shí)例，因而歸納出的結(jié)論不是絕對為真的，只能以某種程度相信它為真。（3）歸納學(xué)習(xí)（inductionlearning）是應(yīng)用歸納推理進(jìn)行學(xué)習(xí)的一種方法。根據(jù)歸納學(xué)習(xí)有無教師指導(dǎo)，可把它分為示例學(xué)習(xí)和觀察與發(fā)現(xiàn)學(xué)習(xí)。前者屬于有師學(xué)習(xí)，后者屬于無師學(xué)習(xí)。

7.3歸納學(xué)習(xí)

我們先看一個(gè)“公雞歸納法”的故事。

某農(nóng)婦養(yǎng)小雞十只，公母各半。她預(yù)備將母雞養(yǎng)大留著生蛋，公雞則養(yǎng)到一百天就陸續(xù)殺以佐餐。天天早晨她拿米喂雞。到第一百天的早晨，其中的一只公雞正在想：“第一天早晨有米吃，第二天早晨有米吃，……第九十九天早晨有米吃，所以今天，第一百天的早晨一定有米吃?！边@時(shí)，該農(nóng)婦來了，正好把這只公雞抓去殺了。這只公雞在第一百天的早晨不但沒有吃著米，反而被殺了，雖然它已有九十九天吃米的經(jīng)驗(yàn)，但不能證明第一百天一定有米。7.3歸納學(xué)習(xí)

我們再回顧中學(xué)數(shù)學(xué)就涉及到的“數(shù)學(xué)歸納法”。用數(shù)學(xué)歸納法證明一個(gè)命題的正確性，必須要求兩條（一）當(dāng)n=1時(shí)，這個(gè)命題是正確的；（二）假設(shè)n=k時(shí)，這個(gè)命題是正確的，那么當(dāng)n=k+1時(shí)，這個(gè)命題也是正確的。

7.3.1歸納學(xué)習(xí)的模式和規(guī)則歸納學(xué)習(xí)的一般模式為：給定：(1)觀察陳述（事實(shí)）F；(表示有關(guān)某些對象、狀態(tài)、過程等的特定知識(shí))

(2)假定的初始?xì)w納斷言（可能為空）；

(3)背景知識(shí)。(用于定義有關(guān)觀察陳述、候選歸納斷言以及任何相關(guān)問題領(lǐng)域知識(shí)、假設(shè)和約束)求：歸納斷言（假設(shè)）H，能重言蘊(yùn)涵或弱蘊(yùn)涵觀察陳述，并滿足背景知識(shí)。假設(shè)H永真蘊(yùn)涵事實(shí)F，說明F是H的邏輯推理，則有：H|>F（讀作H特殊化為F）或F|<H（讀作F一般化或消解為H）這里，從H推導(dǎo)F是演繹推理，因此是保真的；而從事實(shí)F推導(dǎo)出假設(shè)H是歸納推理，因此不是保真的，而是保假的。實(shí)例空間規(guī)則空間解釋過程規(guī)劃過程7.3.1歸納學(xué)習(xí)的模式和規(guī)則歸納學(xué)習(xí)系統(tǒng)模型

實(shí)驗(yàn)規(guī)劃過程通過對實(shí)例空間的搜索完成實(shí)例選擇，并將這些選中的活躍實(shí)例提交給解釋過程，解釋過程對實(shí)例加以適當(dāng)轉(zhuǎn)換，把活躍實(shí)例變換為規(guī)劃空間的特定概念，以引導(dǎo)規(guī)劃空間的搜索。歸納概括規(guī)則選擇性概括規(guī)則取消部分條件放松條件沿概念樹上溯形成閉合區(qū)域?qū)⒊Ａ哭D(zhuǎn)化為變量構(gòu)造性概括規(guī)則7.3.1歸納學(xué)習(xí)的模式和規(guī)則7.3.2歸納學(xué)習(xí)方法1、示例學(xué)習(xí)

示例學(xué)習(xí)（learningfromexamples）又稱為實(shí)例學(xué)習(xí)，它是通過環(huán)境中若干與某概念有關(guān)的例子，經(jīng)歸納得出一般性概念的一種學(xué)習(xí)方法。在這種學(xué)習(xí)方法中，外部環(huán)境提供的是一組例子（正例和反例），示例學(xué)習(xí)就是要從這些特殊知識(shí)中歸納出適用于更大范圍的一般性知識(shí)，以覆蓋所有的正例并排除所有反例。

例如，如果我們用一批動(dòng)物作為示例，并且告訴學(xué)習(xí)系統(tǒng)哪一個(gè)動(dòng)物是“馬”，哪一個(gè)動(dòng)物不是，當(dāng)示例足夠多時(shí)，學(xué)習(xí)系統(tǒng)就能概括出關(guān)于“馬”的概念模型，使自己能識(shí)別馬，并且能把馬與其它動(dòng)物區(qū)別開來，這一學(xué)習(xí)過程就是示例學(xué)習(xí)。7.3.2歸納學(xué)習(xí)方法1、示例學(xué)習(xí)

血沉=正?！?聽診=干鳴音∨水泡音)->診斷=肺炎血沉=快->診斷=肺結(jié)核

7.3.2歸納學(xué)習(xí)方法2、觀察發(fā)現(xiàn)學(xué)習(xí)

觀察發(fā)現(xiàn)學(xué)習(xí)又稱為描述性概括，其目標(biāo)是確定一個(gè)定律或理論的一般性描述，刻畫觀察集，指定某類對象的性質(zhì)。觀察發(fā)現(xiàn)學(xué)習(xí)可分為觀察學(xué)習(xí)與機(jī)器發(fā)現(xiàn)兩種。前者用于對事例進(jìn)行聚類，形成概念描述；后者用于發(fā)現(xiàn)規(guī)律，產(chǎn)生定律或規(guī)則。7.5類比學(xué)習(xí)類比學(xué)習(xí)（learningbyanalogy）就是通過類比，即通過對相似事物加以比較所進(jìn)行的一種學(xué)習(xí)7.5.1類比推理和類比學(xué)習(xí)形式類比推理是在兩個(gè)相似域之間進(jìn)行的目的是從源域中選出與當(dāng)前問題最近似的問題及其求解方法以求解決當(dāng)前的問題，或者建立起目標(biāo)域中已有命題間的聯(lián)系，形成新知識(shí)。推理過程 (1)回憶與聯(lián)想(2)選擇(3)建立對應(yīng)映射(4)轉(zhuǎn)換7.5.2類比學(xué)習(xí)過程與研究類型類比學(xué)習(xí)主要包括如下四個(gè)過程：

(1)輸入一組已知條件和一組未完全確定的條件(2)對輸入的兩組條件，尋找兩者可類比的對應(yīng)關(guān)系。(3)按相似變換的方法，進(jìn)行映射(4)對類推得到的新問題的知識(shí)進(jìn)行校驗(yàn)。類比學(xué)習(xí)研究可分為兩大類問題求解型的類比學(xué)習(xí)預(yù)測推定型的類比學(xué)習(xí)傳統(tǒng)的類比法因果關(guān)系型的類比7.5.2類比學(xué)習(xí)過程與研究類型7.6解釋學(xué)習(xí)解釋學(xué)習(xí)根據(jù)任務(wù)所在領(lǐng)域知識(shí)和正在學(xué)習(xí)的概念知識(shí)，對當(dāng)前實(shí)例進(jìn)行分析和求解，得出一個(gè)表征求解過程的因果解釋樹，以獲取新的知識(shí)。7.6.1解釋學(xué)習(xí)過程和算法解釋學(xué)習(xí)一般包括下列3個(gè)步驟：

(1)利用基于解釋的方法對訓(xùn)練例子進(jìn)行分析與解釋。(2)對例子的結(jié)構(gòu)進(jìn)行概括性解釋。(3)從解釋結(jié)構(gòu)中識(shí)別出訓(xùn)練例子的特性，獲取一般控制知識(shí)。1986年米切爾（Mitchell）等人為基于解釋的學(xué)習(xí)提出了一個(gè)統(tǒng)一的算法EBG，該算法建立了基于解釋的概括過程，并運(yùn)用知識(shí)的邏輯表示和演繹推理進(jìn)行問題求解。7.6.1解釋學(xué)習(xí)過程和算法EBG求解問題的形式可描述于下:給定：(1)目標(biāo)概念描述TC；(2)訓(xùn)練實(shí)例TE；(3)領(lǐng)域知識(shí)DT；(4)操作準(zhǔn)則OC。求解：訓(xùn)練實(shí)例的一般化概括，使之滿足：(1)目標(biāo)概念的充分概括描述TC；(2)操作準(zhǔn)則OC。7.6.1解釋學(xué)習(xí)過程和算法解釋學(xué)習(xí)舉例：

通過解釋學(xué)習(xí)獲取一個(gè)物體（x）可以安全地放置到另一個(gè)物體（y）上的概念。

已知：目標(biāo)概念為一對物體（x，y），使safe-to-stack（x，y），有：訓(xùn)練例子是描述兩物體的下列事實(shí)：

on（a，b）

isa（a，brick）

volumn（a，1）

density（a，1）

weight（brick，5）

times（1，1，1）物體的體積為1，物體密度為1，物體的重量為1.

less（1，5）

…

知識(shí)庫中的領(lǐng)域知識(shí)是把一個(gè)物體放置到另一個(gè)物體上的安全性準(zhǔn)則：其證明樹如圖所示。7.6.1解釋學(xué)習(xí)過程和算法7.6.1解釋學(xué)習(xí)過程和算法“想當(dāng)國王”規(guī)則

If貴族是軟弱的

貴族與女人結(jié)婚

女人是貪婪地

Then貴族很可能想當(dāng)國王7.7神經(jīng)學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)通過學(xué)習(xí)，改善網(wǎng)絡(luò)性能7.7.1基于反向傳播網(wǎng)絡(luò)的學(xué)習(xí)

反向傳播算法是一種計(jì)算單個(gè)權(quán)值變化引起網(wǎng)絡(luò)性能變化值的較為簡單的方法。由于BP算法過程包含從輸出節(jié)點(diǎn)開始，反向地向第一隱含層(即最接近輸入層的隱含層)傳播由總誤差引起的權(quán)值修正，所以稱為“反向傳播”。反向傳播特性與所求解問題的性質(zhì)和所作細(xì)節(jié)選擇有極為密切的關(guān)系。7.7.2基于Hopfield網(wǎng)絡(luò)的學(xué)習(xí)反饋神經(jīng)網(wǎng)絡(luò)，它是一種動(dòng)態(tài)反饋系統(tǒng)，比前饋網(wǎng)絡(luò)具有更強(qiáng)的計(jì)算能力。Hopfield網(wǎng)絡(luò)是一種具有正反相輸出的帶反饋人工神經(jīng)網(wǎng)絡(luò)。Hopfield網(wǎng)絡(luò)系統(tǒng)不僅能夠?qū)崿F(xiàn)聯(lián)想記憶，而且能夠執(zhí)行線性和非線性規(guī)劃等優(yōu)化求解任務(wù)。7.8知識(shí)發(fā)現(xiàn)智能信息處理的瓶頸——知識(shí)獲取機(jī)器學(xué)習(xí)能夠通過對數(shù)據(jù)及其關(guān)系的分析，提取出隱含在海量數(shù)據(jù)中的知識(shí)7.8.1知識(shí)發(fā)現(xiàn)的發(fā)展和定義1.知識(shí)發(fā)現(xiàn)的產(chǎn)生和發(fā)展

知識(shí)發(fā)現(xiàn)最早是于1989年8月在第11屆國際人工智能聯(lián)合會(huì)議的專題討論會(huì)上提出。隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)上已設(shè)立了不少研究KDD的網(wǎng)站、論壇和新聞報(bào)導(dǎo)。在研究的基礎(chǔ)上，也出現(xiàn)一些KDD產(chǎn)品和應(yīng)用系統(tǒng)，引起企業(yè)界的關(guān)注。2.定義：數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)是從大量數(shù)據(jù)中辨識(shí)出有效的、新穎的、潛在有用的、并可被理解的模式的高級處理過程。數(shù)據(jù)集：是指一個(gè)有關(guān)事實(shí)F的集合，它是用來描述事物有關(guān)方面的信息，是進(jìn)一步發(fā)現(xiàn)知識(shí)的原材料。新穎：經(jīng)過知識(shí)發(fā)現(xiàn)提取出的模式必須是新穎的。潛在有用：提取出的模式應(yīng)該是有意義的，這可以通過某些函數(shù)的值來衡量?？杀蝗死斫猓褐R(shí)發(fā)現(xiàn)的一個(gè)目標(biāo)就是將數(shù)據(jù)庫中隱含的模式以容易被人理解的形式表現(xiàn)出來，從而幫助人們更好地了解數(shù)據(jù)庫中所包含的信息。模式高級過程7.8.1知識(shí)發(fā)現(xiàn)的發(fā)展和定義7.8.2知識(shí)發(fā)現(xiàn)的處理過程數(shù)據(jù)選擇：根據(jù)用戶的需求從數(shù)據(jù)庫中提取與KDD相關(guān)的數(shù)據(jù)。數(shù)據(jù)預(yù)處理：主要是對上述數(shù)據(jù)進(jìn)行再加工，檢查數(shù)據(jù)的完整性及數(shù)據(jù)的一致性，對丟失的數(shù)據(jù)利用統(tǒng)計(jì)方法進(jìn)行填補(bǔ)，形成挖掘數(shù)據(jù)庫。數(shù)據(jù)變換：即從挖掘數(shù)據(jù)庫里選擇數(shù)據(jù)。數(shù)據(jù)挖掘：根據(jù)用戶要求，確定KDD的目標(biāo)是發(fā)現(xiàn)何種類型的知識(shí)。知識(shí)評價(jià)：這一過程主要用于對所獲得的規(guī)則進(jìn)行價(jià)值評定，以決定所得的規(guī)則是否存入基礎(chǔ)知識(shí)庫?？蓺w納為三個(gè)步驟，即數(shù)據(jù)挖掘預(yù)處理、數(shù)據(jù)挖掘、數(shù)據(jù)挖掘后處理。7.8.3知識(shí)發(fā)現(xiàn)的方法統(tǒng)計(jì)方法統(tǒng)計(jì)方法是從事物的外在數(shù)量上的表現(xiàn)去推斷該事物可能的規(guī)律性。機(jī)器學(xué)習(xí)方法

(1)規(guī)則歸納。規(guī)則反映數(shù)據(jù)項(xiàng)中某些屬性或數(shù)據(jù)集中某些數(shù)據(jù)項(xiàng)之間的統(tǒng)計(jì)相關(guān)性。

(2)決策樹。決策樹的每一個(gè)非終葉節(jié)點(diǎn)表示所考慮的數(shù)據(jù)項(xiàng)的測試或決策。

(3)范例推理。范例推理是直接使用過去的經(jīng)驗(yàn)或解法來求解給定的問題。

(4)貝葉斯信念網(wǎng)絡(luò)。貝葉斯信念網(wǎng)絡(luò)是概率分布的圖表示。

(5)科學(xué)發(fā)現(xiàn)?？茖W(xué)發(fā)現(xiàn)是在實(shí)驗(yàn)環(huán)境下發(fā)現(xiàn)科學(xué)定律。

(6)遺傳算法。在求解過程中，通過最好解的選擇和彼此組合，使期望解的集合愈來愈好。神經(jīng)計(jì)算方法可視化方法可視化（vis