第5章-機(jī)器學(xué)習(xí)

第5章機(jī)器學(xué)習(xí)2023/1/311《人工智能》

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

機(jī)器學(xué)習(xí)概述什么是學(xué)習(xí)？

學(xué)習(xí)是人類具有的一種重要智能行為，但究竟什么是學(xué)習(xí)，長(zhǎng)期以來(lái)卻眾說(shuō)紛紜。關(guān)于“學(xué)習(xí)”這一概念的主要觀點(diǎn)：學(xué)習(xí)是系統(tǒng)改進(jìn)其性能的過(guò)程。這是西蒙的觀點(diǎn)。西蒙的觀點(diǎn)：學(xué)習(xí)就是系統(tǒng)在不斷重復(fù)的工作中對(duì)本身能力的增強(qiáng)或者改進(jìn)，使得系統(tǒng)在下一次執(zhí)行同樣任務(wù)或類似任務(wù)時(shí)，會(huì)比現(xiàn)在做得更好或效率更高。學(xué)習(xí)是獲取知識(shí)的過(guò)程。這是從事專家系統(tǒng)研究的人們的觀點(diǎn)。學(xué)習(xí)是技能的獲取。這是心理學(xué)家的觀點(diǎn)。學(xué)習(xí)是事物規(guī)律的發(fā)現(xiàn)過(guò)程。2023/1/314《人工智能》基本的學(xué)習(xí)形式有2種：（1）知識(shí)獲取和技能求精。

例如，我們說(shuō)某人學(xué)過(guò)物理。我們的意思是，此人已經(jīng)掌握了有關(guān)物理學(xué)的基本概念，并且理解其含義，同時(shí)還懂得這些概念之間以及它們與物理世界之間的關(guān)系。

一般地，知識(shí)獲取可看作學(xué)習(xí)新的符號(hào)信息，而這些符號(hào)信息是以有效方式與應(yīng)用這種信息的能力相適應(yīng)的。（2）第二類學(xué)習(xí)形式是通過(guò)實(shí)踐逐步改進(jìn)機(jī)制和認(rèn)知技能。

學(xué)習(xí)的很多過(guò)程都是由改進(jìn)所學(xué)的技能組成。這些技能包括意識(shí)的或者機(jī)制的協(xié)調(diào)，而這種改進(jìn)又是通過(guò)反復(fù)實(shí)踐和從失敗的行為中糾正偏差來(lái)進(jìn)行的。例如騎自行車或彈鋼琴等等。知識(shí)獲取的本質(zhì)可能是一個(gè)自覺的過(guò)程，其結(jié)果產(chǎn)生新的符號(hào)知識(shí)結(jié)構(gòu)和智力模型。而技能求精則是下意識(shí)地借助于反復(fù)實(shí)踐來(lái)實(shí)現(xiàn)的。人類的學(xué)習(xí)一般表現(xiàn)為這兩種活動(dòng)的結(jié)合。2023/1/315《人工智能》5.1.1機(jī)器學(xué)習(xí)的定義

至今，還沒有統(tǒng)一的“機(jī)器學(xué)習(xí)”定義，而且也很難給出一個(gè)公認(rèn)的和準(zhǔn)確的定義。

一般認(rèn)為機(jī)器學(xué)習(xí)是研究如何使用機(jī)器來(lái)模擬人類學(xué)習(xí)活動(dòng)的一門學(xué)科。更為嚴(yán)格的提法是：機(jī)器學(xué)習(xí)是一門研究機(jī)器獲取新知識(shí)和新技能，并識(shí)別現(xiàn)有知識(shí)的學(xué)問(wèn)。最早的具有學(xué)習(xí)能力的程序：

1959年美國(guó)的塞繆爾(Samuel)設(shè)計(jì)了一個(gè)下棋程序，這個(gè)程序具有學(xué)習(xí)能力，它可以在不斷的對(duì)奕中改善自己的棋藝。4年后，這個(gè)程序戰(zhàn)勝了設(shè)計(jì)者本人。又過(guò)了3年，這個(gè)程序戰(zhàn)勝了美國(guó)一個(gè)保持8年之久的常勝不敗的冠軍。2023/1/316《人工智能》5.1.2機(jī)器學(xué)習(xí)的發(fā)展史

機(jī)器學(xué)習(xí)的發(fā)展過(guò)程大體上可分為4個(gè)時(shí)期：1、第一階段是在50年代中葉到60年代中葉，屬于熱烈時(shí)期。

在這個(gè)時(shí)期，所研究的是“沒有知識(shí)”的學(xué)習(xí)，即“無(wú)知”學(xué)習(xí)；其研究目標(biāo)是各類自組織系統(tǒng)和自適應(yīng)系統(tǒng)；指導(dǎo)本階段研究的理論基礎(chǔ)是早在40年代就開始研究的神經(jīng)網(wǎng)絡(luò)模型。在這個(gè)時(shí)期，我國(guó)研制了數(shù)字識(shí)別學(xué)習(xí)機(jī)。2、第二階段在60年代中葉至70年代中葉，被稱為機(jī)器學(xué)習(xí)的冷靜時(shí)期。

本階段的研究目標(biāo)是模擬人類的概念學(xué)習(xí)過(guò)程，并采用邏輯結(jié)構(gòu)或圖結(jié)構(gòu)作為機(jī)器內(nèi)部描述。這個(gè)時(shí)期正是我國(guó)“史無(wú)前例”的十年，對(duì)機(jī)器學(xué)習(xí)的研究不可能取得實(shí)質(zhì)進(jìn)展。

2023/1/317《人工智能》5.1.2機(jī)器學(xué)習(xí)的發(fā)展史（2）3、第三階段從70年代中葉至80年代中葉，稱為復(fù)興時(shí)期。

在這個(gè)時(shí)期，人們從學(xué)習(xí)單個(gè)概念擴(kuò)展到學(xué)習(xí)多個(gè)概念，探索不同的學(xué)習(xí)策略和各種學(xué)習(xí)方法。1980年,在美國(guó)召開了第一屆國(guó)際機(jī)器學(xué)習(xí)研討會(huì);1984年,《機(jī)器學(xué)習(xí)》雜志問(wèn)世。我國(guó)于1987年召開了第一屆全國(guó)機(jī)器學(xué)習(xí)研討會(huì);1989年成立了以中國(guó)科技大學(xué)蔡慶生教授為理事長(zhǎng)的理事會(huì)。4、機(jī)器學(xué)習(xí)的最新階段始于1986年。

一方面，由于神經(jīng)網(wǎng)絡(luò)研究的重新興起，另一方面，對(duì)實(shí)驗(yàn)研究和應(yīng)用研究得到前所未有的重視。我國(guó)的機(jī)器學(xué)習(xí)研究開始進(jìn)入穩(wěn)步發(fā)展和逐漸繁榮的新時(shí)期。2023/1/318《人工智能》機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘

知識(shí)發(fā)現(xiàn)(KnowledgeDiscoveringinDatabase)與數(shù)據(jù)挖掘(DataMining)是人工智能、機(jī)器學(xué)習(xí)(MachineLearning)與數(shù)據(jù)庫(kù)技術(shù)相結(jié)合的產(chǎn)物。

KDD一詞是在1989年于美國(guó)底特律市召開的第一屆KDD國(guó)際學(xué)術(shù)會(huì)議上正式形成的。1995年，在加拿大召開了第一屆知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘國(guó)際學(xué)術(shù)會(huì)議。由于數(shù)據(jù)庫(kù)中的數(shù)據(jù)被形象地喻為礦床，因此數(shù)據(jù)挖掘一詞很快流傳開來(lái)。數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)的研究已形成熱潮，并在生物醫(yī)學(xué)、金融管理、商業(yè)銷售等領(lǐng)域得到成功應(yīng)用，給機(jī)器學(xué)習(xí)注入新的活力。2023/1/319《人工智能》5.1.3機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)環(huán)境是指系統(tǒng)外部信息的來(lái)源，它可以是系統(tǒng)的工作對(duì)象，也可以包括工作對(duì)象和外界條件。學(xué)習(xí)單元處理環(huán)境提供的信息，相當(dāng)于各種學(xué)習(xí)算法。學(xué)習(xí)單元利用環(huán)境提供的信息，并與執(zhí)行單元的反饋信息進(jìn)行比較，獲取相關(guān)知識(shí)，對(duì)知識(shí)庫(kù)進(jìn)行修改。知識(shí)庫(kù)用于存放由學(xué)習(xí)環(huán)節(jié)所得到的知識(shí)。知識(shí)庫(kù)中知識(shí)的表示方法可以是：謂詞、產(chǎn)生式、特征向量、神經(jīng)網(wǎng)絡(luò)等。執(zhí)行單元處理系統(tǒng)所面臨的現(xiàn)實(shí)問(wèn)題，即應(yīng)用知識(shí)庫(kù)中的知識(shí)求解問(wèn)題。機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)如圖2023/1/3110《人工智能》影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的重要因素(1)影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的最重要的因素是環(huán)境向系統(tǒng)提供的信息。更具體地說(shuō)是信息的質(zhì)量。(2)知識(shí)庫(kù)是影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的第二個(gè)因素。知識(shí)的表示有多種形式，在選擇時(shí)要兼顧以下4個(gè)方面：表達(dá)能力強(qiáng)。所選擇的表示方式能很容易地表達(dá)有關(guān)的知識(shí)。易于推理。為了使學(xué)習(xí)系統(tǒng)的計(jì)算代價(jià)比較低，希望知識(shí)表示方式能使推理較為容易。容易修改知識(shí)庫(kù)。學(xué)習(xí)系統(tǒng)的本質(zhì)要求它不斷地修改自己的知識(shí)庫(kù)，當(dāng)推廣得出一般執(zhí)行規(guī)則后，要加到知識(shí)庫(kù)中。知識(shí)表示易于擴(kuò)展。每一個(gè)學(xué)習(xí)系統(tǒng)都要求具有某些知識(shí)理解環(huán)境提供的信息，分析比較，做出假設(shè)，檢驗(yàn)并修改這些假設(shè)。因此，更確切地說(shuō)，學(xué)習(xí)系統(tǒng)是對(duì)現(xiàn)有知識(shí)的擴(kuò)展和改進(jìn)。2023/1/3111《人工智能》5.1.4機(jī)器學(xué)習(xí)的分類按學(xué)習(xí)方法分類（溫斯頓在1977年提出的分類方法）

①機(jī)械式學(xué)習(xí)：機(jī)械學(xué)習(xí)就是記憶。②指導(dǎo)式學(xué)習(xí)：采用示教式學(xué)習(xí)策略，也稱為示教學(xué)習(xí)。③示例學(xué)習(xí)：通過(guò)工作例子學(xué)習(xí)。④類比學(xué)習(xí)：應(yīng)用類似任務(wù)的知識(shí)求解當(dāng)前問(wèn)題。⑤解釋學(xué)習(xí)：根據(jù)領(lǐng)域知識(shí)對(duì)當(dāng)前實(shí)例分析和求解。按學(xué)習(xí)的綜合屬性分類（綜合考慮知識(shí)表示、推理方法、應(yīng)用領(lǐng)域等多種因素）：

①歸納學(xué)習(xí)：從個(gè)體的特征歸納出它們的共性②分析學(xué)習(xí)：從領(lǐng)域理論出發(fā)演繹出更有效的規(guī)則。③連接學(xué)習(xí)：人工神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)④遺傳學(xué)習(xí)：模擬自然界遺傳與變異機(jī)制2023/1/3112《人工智能》5.2

機(jī)械學(xué)習(xí)機(jī)械學(xué)習(xí)的模式

機(jī)械學(xué)習(xí)是最簡(jiǎn)單的機(jī)器學(xué)習(xí)方法。機(jī)械學(xué)習(xí)就是記憶，即把新的知識(shí)存儲(chǔ)起來(lái)，供需要時(shí)檢索調(diào)用，而不需要計(jì)算和推理。機(jī)械學(xué)習(xí)又是最基本的學(xué)習(xí)過(guò)程。任何學(xué)習(xí)系統(tǒng)都必須記住它們獲取的知識(shí)。在機(jī)械學(xué)習(xí)系統(tǒng)中，知識(shí)的獲取是以較為穩(wěn)定和直接的方式進(jìn)行的，不需要系統(tǒng)進(jìn)行過(guò)多的加工。(X1,X2,…,Xn)(Y1,Y2,…,Yn)f((X1,X2,…,Xn),(Y1,Y2,…,Yn))存儲(chǔ)2023/1/3113《人工智能》數(shù)據(jù)化簡(jiǎn)

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

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

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

歸納學(xué)習(xí)是目前研究得最多的學(xué)習(xí)方法，其學(xué)習(xí)目的是為了獲得新的概念、構(gòu)造新的規(guī)則或發(fā)現(xiàn)新的理論。這種方法對(duì)領(lǐng)域理論沒有要求，甚至可以沒有領(lǐng)域理論，但其需要大量的訓(xùn)練例子，而且歸納性能受到描述語(yǔ)言、概念類型、信噪比、實(shí)例空間分布、歸納模式等的影響。

（1）歸納（induction）是人類拓展認(rèn)識(shí)能力的重要方法，是一種從個(gè)別到一般的，從部分到整體的推理行為。（2）歸納推理是應(yīng)用歸納方法，從足夠多的具體事例中歸納出一般性知識(shí)，提取事物的一般規(guī)律；它是一種從個(gè)別到一般的推理。（3）歸納學(xué)習(xí)（inductionlearning）是應(yīng)用歸納推理進(jìn)行學(xué)習(xí)的一種方法。根據(jù)歸納學(xué)習(xí)有無(wú)教師指導(dǎo)，可把它分為示例學(xué)習(xí)和觀察與發(fā)現(xiàn)學(xué)習(xí)。前者屬于有師學(xué)習(xí)，后者屬于無(wú)師學(xué)習(xí)。2023/1/3116《人工智能》5.3.1歸納學(xué)習(xí)的模式和規(guī)則歸納學(xué)習(xí)的模式給定：觀察陳述（事實(shí)）F，用以表示有關(guān)某些對(duì)象、狀態(tài)、過(guò)程等的特定知識(shí)；假定的初始?xì)w納斷言（可能為空），是關(guān)于目標(biāo)的泛化項(xiàng)或泛化描述。背景知識(shí)，用于定義有關(guān)觀察陳述、候選歸納斷言以及任何相關(guān)問(wèn)題領(lǐng)域知識(shí)、假設(shè)和約束，其中包括能夠刻畫所求歸納斷言的性質(zhì)的優(yōu)先準(zhǔn)則。求：歸納斷言（假設(shè)）H，能重言蘊(yùn)涵或弱蘊(yùn)涵觀察陳述，并滿足背景知識(shí)。2023/1/3117《人工智能》

假設(shè)H永真蘊(yùn)涵事實(shí)F，說(shuō)明F是H的邏輯推理，則有：

H|>F

（讀作H特殊化為F）或F|<H

（讀作F一般化或消解為H）這里，從H推導(dǎo)F是演繹推理，因此是保真的；而從事實(shí)F推導(dǎo)出假設(shè)H是歸納推理，因此不是保真的。

歸納學(xué)習(xí)系統(tǒng)的模型如圖所示。

2023/1/3118《人工智能》歸納概括規(guī)則

設(shè)CTX表示任一描述，K表示結(jié)論，則有下列幾條常用的選擇性概括規(guī)則：(1)取消部分條件：

設(shè)S是對(duì)事例的一種限制，這種限制可能不必要，因此可以去除。即：

CTX∧S→K=>CTX→K

(2)放松條件：

一個(gè)事例的原因可能不止一條，當(dāng)出現(xiàn)新的原因時(shí)，應(yīng)該把新的原因包含進(jìn)去。

CTX1→K=>(CTX1∨CTX2)→K

2023/1/3119《人工智能》(3)沿概念樹上溯：

設(shè)L是一結(jié)構(gòu)性描述項(xiàng)，S代表所有條件中的L值在概念分層樹上最近的共同祖先，則：(4)形成閉合區(qū)域：

設(shè)L是一個(gè)具有顯性關(guān)系的描述項(xiàng)，a,b是它的特殊值，則：(5)將常量轉(zhuǎn)化成變量：2023/1/3120《人工智能》5.3.2歸納學(xué)習(xí)方法1、示例學(xué)習(xí)

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

觀察發(fā)現(xiàn)學(xué)習(xí)又稱為描述性概括，其目標(biāo)是確定一個(gè)定律或理論的一般性描述，刻畫觀察集，指定某類對(duì)象的性質(zhì)。觀察發(fā)現(xiàn)學(xué)習(xí)可分為觀察學(xué)習(xí)與機(jī)器發(fā)現(xiàn)兩種。前者用于對(duì)事例進(jìn)行聚類，形成概念描述；后者用于發(fā)現(xiàn)規(guī)律，產(chǎn)生定律或規(guī)則。2023/1/3121《人工智能》5.3.3歸納學(xué)習(xí)示例--決策樹學(xué)習(xí)

決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散值函數(shù)的方法。在這種方法中學(xué)習(xí)到的函數(shù)被表示為一顆決策樹。學(xué)習(xí)得到的決策樹也能再被表示為多個(gè)if-then規(guī)則，以提高可讀性。決策樹學(xué)習(xí)方法對(duì)噪聲數(shù)據(jù)有很好的健壯性且能夠?qū)W習(xí)析取表達(dá)式。決策樹學(xué)習(xí)算法有很多，比如ID3、C4.5、ASSISTANT等等。這些決策樹學(xué)習(xí)方法搜索一個(gè)完整表示的假設(shè)空間，從而避免了受限假設(shè)空間的不足。決策樹學(xué)習(xí)的歸納偏置是優(yōu)先選擇較小的樹。2023/1/3122《人工智能》決策樹表示法決策樹通過(guò)把實(shí)例從根節(jié)點(diǎn)排列(sort)到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。樹上的每一個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性(attribute)的測(cè)試，并且該節(jié)點(diǎn)的每一個(gè)后繼分枝對(duì)應(yīng)于該屬性的一個(gè)可能值。分類實(shí)例的方法是從這顆樹的根節(jié)點(diǎn)開始，測(cè)試這個(gè)節(jié)點(diǎn)指定的屬性，然后按照給定實(shí)例的該屬性值對(duì)應(yīng)的樹枝向下移動(dòng)。然后這個(gè)過(guò)程再以新節(jié)點(diǎn)為根的子樹上重復(fù)。例子：在一個(gè)水果的分類問(wèn)題中，采用的特征向量為：{顏色,尺寸,形狀,味道}，其中：顏色取值為{紅,綠,黃}，尺寸取值為{大,中,小}，味道取值為{甜,酸}，形狀取值為{圓,細(xì)}。樣本集：一批水果，知道其特征向量及類別問(wèn)題：一個(gè)新的水果，觀測(cè)到了其特征向量，將其分類2023/1/3123《人工智能》2023/1/3124《人工智能》通常決策樹代表實(shí)例屬性值約束的合取(conjunction)的析取式(disjunction)。從樹根到樹葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹本身對(duì)應(yīng)這些合取的析取。上述例子可對(duì)應(yīng)如下析取式：

(color=green∧size=big) ∨(color=green∧size=medium) ∨(color=green∧size=small) ∨(color=yellow∧shape=round∧size=big) ∨(color=yellow∧shape=round∧size=small) ∨(color=yellow∧shape=thin) ∨(color=red∧size=medium) ∨(color=red∧size=small∧taste=sweet) ∨(color=red∧size=small∧taste=sour)2023/1/3125《人工智能》決策樹的適用問(wèn)題決策樹學(xué)習(xí)適合解決具有以下特征的問(wèn)題實(shí)例是由“屬性-值”對(duì)表示的：實(shí)例是用一系列固定的屬性和它們的值來(lái)描述的。目標(biāo)函數(shù)具有離散的輸出值：決策樹給每個(gè)實(shí)例賦予一個(gè)布爾型的分類。決策樹方法很容易擴(kuò)展到學(xué)習(xí)有兩個(gè)以上輸出值的函數(shù)。可能需要析取的描述：決策樹很自然地代表了析取表達(dá)式。訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤：決策樹學(xué)習(xí)對(duì)錯(cuò)誤有很好的健壯性，無(wú)論是訓(xùn)練樣例所屬的分類錯(cuò)誤，還是描述這些樣例的屬性值錯(cuò)誤。訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例：決策樹甚至可以再有未知屬性值的訓(xùn)練樣例中使用。2023/1/3126《人工智能》決策樹學(xué)習(xí)的常見問(wèn)題確定決策樹增長(zhǎng)的深度，避免過(guò)度擬合；處理連續(xù)值的屬性；選擇一個(gè)適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)；處理屬性值不完整的訓(xùn)練數(shù)據(jù)；處理不同代價(jià)的屬性；提高計(jì)算效率。

2023/1/3127《人工智能》ID3算法大多數(shù)已開發(fā)的決策樹學(xué)習(xí)算法是一種核心算法（CLS算法）的變體。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。這種方法是ID3算法(Quinlan1986)和后繼的C4.5(Quinlan1993)的基礎(chǔ)。ID3是一種自頂向下增長(zhǎng)樹的貪婪算法，在每個(gè)節(jié)點(diǎn)選取能最好分類樣例的屬性。繼續(xù)這個(gè)過(guò)程指導(dǎo)這棵樹能完美分類訓(xùn)練樣例，或所有的屬性都已被使用過(guò)。構(gòu)造過(guò)程是從“哪一個(gè)屬性將在樹的根節(jié)點(diǎn)被測(cè)試”這個(gè)問(wèn)題開始。為了回答這個(gè)問(wèn)題，使用統(tǒng)計(jì)測(cè)試來(lái)確定每一個(gè)實(shí)例屬性單獨(dú)分類訓(xùn)練樣例的能力。分類能力最好的屬性被選作樹的根節(jié)點(diǎn)的測(cè)試。然后為根節(jié)點(diǎn)屬性的每個(gè)可能值產(chǎn)生一個(gè)分枝，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种Γㄒ簿褪?，樣例的該屬性值?duì)應(yīng)的分枝）之下。然后重復(fù)整個(gè)過(guò)程，用每個(gè)分枝節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例來(lái)選取在該點(diǎn)被測(cè)試的最佳屬性。這形成了對(duì)合格決策樹的貪婪搜索，也就是算法從不回溯重新考慮以前的選擇。2023/1/3128《人工智能》決策樹的構(gòu)建已知訓(xùn)練樣本集，構(gòu)造決策樹需要解決以下幾個(gè)問(wèn)題（考慮BinaryDecisionTrees）：（1）最佳提問(wèn)的選擇：應(yīng)該先對(duì)哪一個(gè)屬性提出問(wèn)題？應(yīng)該按什么樣的順序提出問(wèn)題？每一個(gè)問(wèn)題都是一個(gè)YES/NO問(wèn)題。（2）葉結(jié)點(diǎn)的確定：什么時(shí)候可以結(jié)束提問(wèn)，并判定模式的類別？（3）決策樹修剪：如果決策樹過(guò)大，應(yīng)該如何修剪決策樹，以保證其泛化能力？2023/1/3129《人工智能》最佳提問(wèn)的選擇（1）（1）決策樹中的每一個(gè)結(jié)點(diǎn)（葉結(jié)點(diǎn)除外）對(duì)應(yīng)于一個(gè)提問(wèn)。每一個(gè)葉結(jié)點(diǎn)給出最終的分類。決策樹的構(gòu)建從根結(jié)點(diǎn)開始。（2）根結(jié)點(diǎn)的構(gòu)建：根結(jié)點(diǎn)對(duì)應(yīng)于訓(xùn)練樣本集D。通過(guò)選擇針對(duì)某一屬性的一個(gè)問(wèn)題進(jìn)行提問(wèn)，可以根據(jù)對(duì)該問(wèn)題的回答，將訓(xùn)練樣本集D分類兩個(gè)部分：Dy及Dn（其中，Dy為回答YES的樣本，Dn為回答NO的樣本），并建立與之相對(duì)應(yīng)的兩個(gè)子結(jié)點(diǎn)。我們希望選擇一個(gè)這樣問(wèn)題進(jìn)行提問(wèn)：使得Dy及Dn盡可能純凈。（3）中間結(jié)點(diǎn)的構(gòu)造：對(duì)于每一個(gè)中間結(jié)點(diǎn)（結(jié)點(diǎn)N），都有一個(gè)與之對(duì)應(yīng)的子集DN。同樣，根據(jù)結(jié)點(diǎn)N的提問(wèn)，可以將DN進(jìn)一步劃分為兩個(gè)部分DNy及DNn（其中，DNy為回答YES的樣本，DNn為回答NO的樣本），并得到與之相對(duì)應(yīng)的兩個(gè)子結(jié)點(diǎn)。我們希望根據(jù)結(jié)點(diǎn)N提出的問(wèn)題，能夠使DNy及DNn盡可能純凈。2023/1/3130《人工智能》最佳提問(wèn)的選擇（2）（4）當(dāng)如上得到的某一個(gè)子結(jié)點(diǎn)足夠純凈時(shí)，就可以確定該結(jié)點(diǎn)為葉結(jié)點(diǎn)，并給出其類別。（5）當(dāng)決策樹中的每一條路徑都對(duì)應(yīng)于一個(gè)葉結(jié)點(diǎn)時(shí)，學(xué)習(xí)過(guò)程結(jié)束，決策樹構(gòu)建完畢。（6）根據(jù)上述準(zhǔn)則（純凈度準(zhǔn)則）構(gòu)建決策樹，可以保證決策樹的復(fù)雜度較小（結(jié)點(diǎn)數(shù)量少、深度?。?。（7）在對(duì)訓(xùn)練集分類能力相近的條件下，復(fù)雜度小的決策樹（分類器）優(yōu)于復(fù)雜度大的決策樹（分類器）。復(fù)雜度小的分類器通常具有較好的泛化能力。這一原則稱為Occam’srazor。2023/1/3131《人工智能》最佳提問(wèn)的選擇（3）（8）結(jié)點(diǎn)n非純凈度的定義其中，i(n)為結(jié)點(diǎn)n的非純凈度，Nn

為結(jié)點(diǎn)n對(duì)應(yīng)的樣本的數(shù)量，Njn為結(jié)點(diǎn)n中屬于j的樣本的數(shù)量，C為類別的個(gè)數(shù)。2023/1/3132《人工智能》最佳提問(wèn)的選擇（4）其中，ny為結(jié)點(diǎn)n的YES子結(jié)點(diǎn)，nn

為NO子結(jié)點(diǎn)，Nny為YES子結(jié)點(diǎn)對(duì)應(yīng)的樣本的數(shù)量，Nnn為NO子結(jié)點(diǎn)對(duì)應(yīng)的樣本的數(shù)量。結(jié)點(diǎn)n的最佳選擇問(wèn)題：使△i(n)取得最大值。（9）結(jié)點(diǎn)n最佳問(wèn)題的選擇：對(duì)于結(jié)點(diǎn)n，通過(guò)提出并回答某個(gè)問(wèn)題，可以得到如下的純凈度的提高（不純凈度的降低）：2023/1/3133《人工智能》最佳提問(wèn)的選擇（5）（10）結(jié)點(diǎn)n最佳問(wèn)題的選擇范圍：需要枚舉出所有可以提出的問(wèn)題，從中選出有效的問(wèn)題，并在這些有效的問(wèn)題中選擇一個(gè)最佳的問(wèn)題。由于特征的數(shù)量是有限的，每個(gè)特征的可能取值也是有限的，所以所有可能提出的問(wèn)題是可以枚舉的。所提問(wèn)題通常限制為針對(duì)某個(gè)特征提出的簡(jiǎn)單問(wèn)題，問(wèn)題的形式如前面的二叉數(shù)所示。2023/1/3134《人工智能》葉結(jié)點(diǎn)的確定問(wèn)題

決策樹結(jié)點(diǎn)劃分的原則是使其子結(jié)點(diǎn)盡可能純凈（指兩個(gè)子結(jié)點(diǎn)的平均純凈度最高）。對(duì)于任意一個(gè)結(jié)點(diǎn)n，可以出現(xiàn)以下三種情況：（1）結(jié)點(diǎn)n中的樣本屬于同一類，即結(jié)點(diǎn)n絕對(duì)純凈。此時(shí)結(jié)點(diǎn)n不可進(jìn)一步劃分。（2）結(jié)點(diǎn)n中的樣本不屬于同一類，但是不存在任何一個(gè)劃分（即提出一個(gè)問(wèn)題并根據(jù)該問(wèn)題對(duì)結(jié)點(diǎn)n的樣本進(jìn)行劃分）可以使其子結(jié)點(diǎn)的平均純凈度高于結(jié)點(diǎn)n。此時(shí)結(jié)點(diǎn)n不可進(jìn)一步劃分。（3）可以提出一個(gè)問(wèn)題對(duì)結(jié)點(diǎn)n進(jìn)行劃分，從而使結(jié)點(diǎn)n的子結(jié)點(diǎn)具有更高的純凈度。此時(shí)結(jié)點(diǎn)n可以進(jìn)一步劃分。2023/1/3135《人工智能》葉結(jié)點(diǎn)的確定問(wèn)題問(wèn)題：在構(gòu)建決策樹的過(guò)程中，確定葉節(jié)點(diǎn)的一個(gè)策略是：對(duì)于每一個(gè)可以進(jìn)一步劃分的結(jié)點(diǎn)都進(jìn)行劃分，直到得到一個(gè)不可劃分的子結(jié)點(diǎn)，并將該子結(jié)點(diǎn)定為葉結(jié)點(diǎn)。這樣構(gòu)造的決策樹，其葉結(jié)點(diǎn)均為不可再進(jìn)一步劃分的結(jié)點(diǎn)。這種葉結(jié)點(diǎn)的確定方法是否可行？答案：決策樹是根據(jù)訓(xùn)練樣本的集合構(gòu)成的。該集合中的樣本是隨機(jī)的。不同的隨機(jī)實(shí)驗(yàn)會(huì)得到不同的樣本集合。因此，該集合并不能完全描述樣本(即特征向量)真實(shí)分布。當(dāng)葉結(jié)點(diǎn)按上述方法確定時(shí)，所得決策樹雖然對(duì)訓(xùn)練樣本集合給出了最優(yōu)的分類，但是卻背離了樣本的真實(shí)分布，因此削弱了對(duì)未來(lái)新樣本的分類能力。這一現(xiàn)象稱為過(guò)度擬合(指決策數(shù)對(duì)訓(xùn)練樣本過(guò)度擬合，從而背離了樣本的真實(shí)分布)。2023/1/3136《人工智能》葉結(jié)點(diǎn)確定的基本思路（1）并不絕追求對(duì)訓(xùn)練樣本的正確劃分。并不絕對(duì)追求葉結(jié)點(diǎn)的純凈度。絕對(duì)追求葉結(jié)點(diǎn)的純凈度導(dǎo)致過(guò)度擬合。此時(shí)決策樹的復(fù)雜度偏高。（2）要適度保證葉結(jié)點(diǎn)的純凈度，適度保證對(duì)訓(xùn)練樣本的正確分類能力。葉結(jié)點(diǎn)的不純凈度過(guò)高，對(duì)訓(xùn)練樣本的正確分類能力過(guò)低稱為欠學(xué)習(xí)（此時(shí)，決策樹不能夠充分提取樣本集合中蘊(yùn)涵的有關(guān)樣本真實(shí)分布的信息。欠學(xué)習(xí)同樣不能保證對(duì)未來(lái)新樣本的正確分類能力）。此時(shí)決策樹的復(fù)雜度偏低。（3）因此，在決策樹的構(gòu)建過(guò)程中，需要在過(guò)度擬合與欠學(xué)習(xí)之間尋求合理的平衡，即尋求復(fù)雜度適中的決策樹。具體方法為：在結(jié)點(diǎn)還可以進(jìn)一步劃分的時(shí)候，可根據(jù)預(yù)先設(shè)定的準(zhǔn)則停止對(duì)其劃分，并將其設(shè)置為葉結(jié)點(diǎn)。2023/1/3137《人工智能》確定葉結(jié)點(diǎn)的基本方法（1）方法1：采用測(cè)試集的方法。將樣本集合分為訓(xùn)練集與測(cè)試集。根據(jù)訓(xùn)練集構(gòu)建決策樹，決策樹中的結(jié)點(diǎn)逐層展開。每展開一層子結(jié)點(diǎn)，并將其設(shè)為葉結(jié)點(diǎn)，就得到一棵決策樹，然后采用測(cè)試集對(duì)所得決策樹的分類性能進(jìn)行統(tǒng)計(jì)。重復(fù)上述過(guò)程，可以得到?jīng)Q策樹在測(cè)試集上的學(xué)習(xí)曲線。根據(jù)學(xué)習(xí)曲線，選擇在測(cè)試集上性能最佳的決策樹為最終的決策樹。方法2：在決策樹開始訓(xùn)練以前，首先設(shè)定一個(gè)閾值A(chǔ)。在決策樹的訓(xùn)練過(guò)程中，對(duì)于任意一個(gè)結(jié)點(diǎn)n，如果該結(jié)點(diǎn)的最優(yōu)劃分（即最優(yōu)問(wèn)題對(duì)該結(jié)點(diǎn)的樣本集合所作的劃分）所導(dǎo)致的純凈度的提高小于A，則將該結(jié)點(diǎn)定為葉結(jié)點(diǎn)。采用該方法不需要將樣本集合分為訓(xùn)練集及測(cè)試集。決策樹直接采用全體樣本集合構(gòu)建。2023/1/3138《人工智能》確定葉結(jié)點(diǎn)的基本方法（2）方法3：在決策樹開始訓(xùn)練以前，首先設(shè)定一個(gè)閾值A(chǔ)。在決策樹的訓(xùn)練過(guò)程中，對(duì)于任意一個(gè)結(jié)點(diǎn)n，如果Nn/N<A，則確定結(jié)點(diǎn)n為葉結(jié)點(diǎn)。其中，Nn為結(jié)點(diǎn)n對(duì)應(yīng)的樣本的數(shù)量，N為全體樣本的數(shù)量。采用該方法同樣不需要將樣本集合分為訓(xùn)練集及測(cè)試集。決策樹直接采用全體樣本集合構(gòu)建。方法4：采用如下的性能準(zhǔn)則函數(shù)：

其中size代表決策樹的復(fù)雜度，i(n)為結(jié)點(diǎn)n

的非純凈度。該準(zhǔn)則函數(shù)表達(dá)出了過(guò)度擬合與欠學(xué)習(xí)之間的相互關(guān)系。決策樹的優(yōu)化準(zhǔn)則為：使該準(zhǔn)則函數(shù)取得最小值。2023/1/3139《人工智能》決策樹修剪（1）

決策樹的修剪是決策樹學(xué)習(xí)的另外一種有效的方法。其基本思路是，首先使決策樹得到充分生長(zhǎng)，然后再通過(guò)修剪降低決策樹的復(fù)雜度，從而保證決策樹的泛化能力。具體方法如下：（1）決策樹的構(gòu)建：在決策樹的構(gòu)建過(guò)程中，對(duì)于每一個(gè)可以進(jìn)一步劃分的結(jié)點(diǎn)都進(jìn)行劃分，直到得到一個(gè)不可進(jìn)一步劃分的子結(jié)點(diǎn)，并將該子結(jié)點(diǎn)定為葉結(jié)點(diǎn)。這樣構(gòu)造的決策樹，其葉結(jié)點(diǎn)均為不可再進(jìn)一步劃分的結(jié)點(diǎn)。2023/1/3140《人工智能》決策樹修剪（2）（2）在上述決策樹構(gòu)建完畢后，從葉結(jié)點(diǎn)一層開始，考察兄弟葉結(jié)點(diǎn)是否可以合并。如果可以合并，則對(duì)這些兄弟結(jié)點(diǎn)進(jìn)行合并，并將其父結(jié)點(diǎn)設(shè)為葉結(jié)點(diǎn)。在對(duì)所有可以合并的兄弟葉結(jié)點(diǎn)進(jìn)行合并后，可以形成一棵新的決策樹。對(duì)于新形成的決策樹，可以重復(fù)上述兄弟結(jié)點(diǎn)的合并過(guò)程，直到最后得到一棵決策樹，其中任意兩個(gè)兄弟葉結(jié)點(diǎn)都不再滿足合并的條件。這棵決策樹，就是我們最終選擇的決策樹。2023/1/3141《人工智能》決策樹修剪（3）（3）兄弟葉結(jié)點(diǎn)合并的條件為其中，ny及nn為兄弟葉結(jié)點(diǎn)，n為其父結(jié)點(diǎn)。Nn

為父結(jié)點(diǎn)中樣本的數(shù)量，Nny及Nnn

為兩個(gè)子結(jié)點(diǎn)中樣本的數(shù)量。上述合并條件中，△i(n)代表了由于合并所導(dǎo)致的不純凈度的損失。A為閾值，在修剪過(guò)程開始前預(yù)先設(shè)定。葉結(jié)點(diǎn)的類別設(shè)分類問(wèn)題為C類的分類問(wèn)題。對(duì)于葉結(jié)點(diǎn)n，如果在該結(jié)點(diǎn)對(duì)應(yīng)的樣本中，屬于第

i類的樣本數(shù)量最多，則判該葉結(jié)點(diǎn)為第i類。2023/1/3142《人工智能》討論（1）根據(jù)決策樹可以得出若干條規(guī)則。一條從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路途對(duì)應(yīng)于一條IF-THEN規(guī)則。其中，路徑的非葉結(jié)點(diǎn)部分構(gòu)成了規(guī)則的條件部分（IF部分），葉結(jié)點(diǎn)給出了規(guī)則的結(jié)論（THEN部分）。例子：IFCOLOR=REDANDSIZE=MEDIUMTHENITISANAPPLE

用途：知識(shí)的獲取。（2）決策樹方法同樣可用于連續(xù)取值的特征量。當(dāng)特征向量空間為歐氏空間時(shí)，同樣可以采用決策樹方法來(lái)構(gòu)造分類器。當(dāng)然，一般情況下在歐氏空間中通常采用神經(jīng)網(wǎng)絡(luò)來(lái)構(gòu)造分類器。2023/1/3143《人工智能》5.4

類比學(xué)習(xí)

類比(analogy)是一種很有用的和有效的推理方法，它能夠清晰簡(jiǎn)潔地描述對(duì)象間的相似性；也是人類認(rèn)識(shí)世界的一種重要方法。類比學(xué)習(xí)(learningbyanalogy)就是通過(guò)類比，即通過(guò)相似事物加以比較所進(jìn)行的一種學(xué)習(xí)。例如，當(dāng)人們遇到一個(gè)新問(wèn)題需要進(jìn)行處理，但又不具備處理這個(gè)問(wèn)題的知識(shí)時(shí)，通常采用的辦法就是回憶一下過(guò)去處理過(guò)的類似問(wèn)題，找出一個(gè)與目前情況最接近的處理方法來(lái)處理當(dāng)前問(wèn)題。2023/1/3144《人工智能》5.4.1類比推理和類比學(xué)習(xí)類比推理

類比推理是由新情況與已知情況在某些方面的相似來(lái)推出它們?cè)谄渌嚓P(guān)方面的相似。顯然，類比推理是在兩個(gè)相似域之間進(jìn)行的：類比推理的目的是從源域中選出與當(dāng)前問(wèn)題最近似的問(wèn)題及其求解方法以求解決當(dāng)前的問(wèn)題，或者建立起目標(biāo)域中已有命題間的聯(lián)系，形成新知識(shí)。

類比推理過(guò)程如下：

(1)回憶與聯(lián)想遇到新情況或新問(wèn)題時(shí)，首先通過(guò)回憶與聯(lián)想在S中找出與當(dāng)前情況相似的情況，這些情況是過(guò)去已經(jīng)處理過(guò)的，有現(xiàn)成的解決方法及相關(guān)的知識(shí)。2023/1/3145《人工智能》

(2)選擇從找出的相似情況中選出與當(dāng)前情況最相似的情況及其有關(guān)知識(shí)。

(3)建立對(duì)應(yīng)映射在S與T的相似情況之間建立相似元素的對(duì)應(yīng)關(guān)系，并建立起相應(yīng)的映射。

(4)轉(zhuǎn)換在上一步建立的映射下，把S中的有關(guān)知識(shí)引到T中來(lái)，從而建立起求解當(dāng)前問(wèn)題的方法或者學(xué)習(xí)到關(guān)于T的新知識(shí)。2023/1/3146《人工智能》類比學(xué)習(xí)

類比學(xué)習(xí)是基于類比推理的。類比學(xué)習(xí)的過(guò)程主要分為兩步：首先歸納找出源問(wèn)題和目標(biāo)問(wèn)題的公共性質(zhì)，然后再演繹推出從源問(wèn)題到目標(biāo)問(wèn)題的映射，得出目標(biāo)問(wèn)題的新的性質(zhì)。所以類比學(xué)習(xí)既有歸納過(guò)程，又有演繹過(guò)程。

類比學(xué)習(xí)的主要過(guò)程可描述如下：(1)輸入一組已知條件（已解決問(wèn)題）和一組未完全確定的條件（新問(wèn)題）。(2)對(duì)輸入的兩組條件，根據(jù)其描述，按某種相似性的定義尋找兩者可類比的對(duì)應(yīng)關(guān)系。(3)按相似變換的方法，將已有問(wèn)題的概念、特性、方法、關(guān)系等映射到新問(wèn)題上，以獲得待求解新問(wèn)題所需的新知識(shí)。(4)對(duì)類推得到的新問(wèn)題的知識(shí)進(jìn)行校驗(yàn)。驗(yàn)證正確的知識(shí)存入知識(shí)庫(kù)中，而暫時(shí)還無(wú)法驗(yàn)證的知識(shí)只能作為參考性知識(shí)，置于數(shù)據(jù)庫(kù)中。2023/1/3147《人工智能》5.4.2基于范例的學(xué)習(xí)范例（case）：“范例是一段帶有上下文信息的知識(shí)，該知識(shí)表達(dá)了推理機(jī)在達(dá)到其目標(biāo)的過(guò)程中能起關(guān)鍵作用的經(jīng)驗(yàn)”。具體來(lái)說(shuō)，一個(gè)范例應(yīng)具有如下特性：范例表示了與某個(gè)上下文有關(guān)的具體知識(shí)，這種知識(shí)具有可操作性。范例可以是各式各樣的，可有不同的形狀和粒度，可涵蓋或大或小的時(shí)間片，可帶有問(wèn)題的解答或動(dòng)作執(zhí)行后的效應(yīng)。范例記錄了有用的經(jīng)驗(yàn)，這種經(jīng)驗(yàn)?zāi)軒椭评頇C(jī)在未來(lái)更容易地達(dá)到目標(biāo)，或提醒推理機(jī)失敗發(fā)生的可能性有多大等等。2023/1/3148《人工智能》基于范例的推理

人們?yōu)榱私鉀Q一個(gè)新問(wèn)題，先是進(jìn)行回憶，從記憶中找到一個(gè)與新問(wèn)題相似的范例，然后把該范例中的有關(guān)信息和知識(shí)復(fù)用到新問(wèn)題的求解之中。這種推理就是基于范例的推理(Case-BasedReasoning,CBR)，也簡(jiǎn)稱為范例推理。在基于范例推理中，把當(dāng)前所面臨的問(wèn)題或情況稱為目標(biāo)范例(targetcase)，而把記憶的問(wèn)題或情況稱為源范例(basecase)。粗略地說(shuō)，基于范例推理就是由目標(biāo)范例的提示而獲得記憶中的源范例，并由源范例來(lái)指導(dǎo)目標(biāo)范例求解的一種策略。2023/1/3149《人工智能》范例推理基本流程提出解決方案確認(rèn)解決方案以前案例新案例學(xué)過(guò)的案例取回案例新案例解決的案例修改案例

一般知識(shí)提取使用修改保留問(wèn)題2023/1/3150《人工智能》基于范例推理中知識(shí)表示是以范例為基礎(chǔ)，范例的獲取比規(guī)則獲取要容易，大大簡(jiǎn)化知識(shí)獲取。對(duì)過(guò)去的求解結(jié)果進(jìn)行復(fù)用，而不是再次從頭推導(dǎo)，可以提高對(duì)新問(wèn)題的求解效率。過(guò)去求解成功或失敗的經(jīng)歷可以指導(dǎo)當(dāng)前求解時(shí)該怎樣走向成功或避開失敗，這樣可以改善求解的質(zhì)量。對(duì)于那些目前沒有或根本不存在的問(wèn)題，可以通過(guò)計(jì)算推導(dǎo)來(lái)解決的問(wèn)題。如在法律中的判例，基于范例推理能很好發(fā)揮作用。范例推理的特點(diǎn)2023/1/3151《人工智能》基于范例的學(xué)習(xí)

基于范例的推理系統(tǒng)經(jīng)過(guò)不斷的積累經(jīng)驗(yàn)（案例），同時(shí)合適地對(duì)其進(jìn)行索引，系統(tǒng)的推理效率和問(wèn)題求解能力會(huì)隨之增加。因此在CBR中，學(xué)習(xí)的主要任務(wù)是對(duì)案例庫(kù)的豐富和優(yōu)化。在CBR中，大多數(shù)學(xué)習(xí)是通過(guò)如下兩種方式體現(xiàn)的：一個(gè)是新范例的積累，推理系統(tǒng)的范例對(duì)問(wèn)題的覆蓋越多，其功能越強(qiáng)；另一個(gè)是設(shè)計(jì)覆蓋了成功事例也覆蓋了失敗事例的推理要比只設(shè)計(jì)成功情況的推理系統(tǒng)要好，索引的重新賦值，調(diào)節(jié)索引可使得范例能在更合適的時(shí)機(jī)被回憶。2023/1/3152《人工智能》基于范例學(xué)習(xí)的一般過(guò)程新問(wèn)題

新范例檢索歷史范例范例庫(kù)復(fù)用保存修正范例修正解答范例

確認(rèn)解建議解2023/1/3153《人工智能》范例的內(nèi)容(1)問(wèn)題或情景描述：是對(duì)要求解的問(wèn)題或要理解的情景的描述，一般要包括這些內(nèi)容：當(dāng)范例發(fā)生時(shí)推理器的目標(biāo)，完成該目標(biāo)所要涉及的任務(wù)，周圍世界或環(huán)境與可能解決方案相關(guān)的所有特征。(2)解決方案：是問(wèn)題如何在一特定情形下得到解決。它可能是對(duì)問(wèn)題的簡(jiǎn)單解答，也可能是得出解答的推導(dǎo)過(guò)程。(3)結(jié)果：記錄了實(shí)施解決方案后的結(jié)果情況，是失敗還是成功。有了結(jié)果內(nèi)容，CBR在給出建議解時(shí)有能給出曾經(jīng)成功地工作的范例，同時(shí)也能利用失敗的范例來(lái)避免可能會(huì)發(fā)生的問(wèn)題。當(dāng)對(duì)問(wèn)題還缺乏足夠的了解時(shí)，通過(guò)在范例的表示上加上結(jié)果部分能取得較好的效果。2023/1/3154《人工智能》范例的索引建立范例索引有三個(gè)原則：①索引與具體領(lǐng)域有關(guān)。數(shù)據(jù)庫(kù)中的索引是通用的，目的僅僅是追求索引能對(duì)數(shù)據(jù)集合進(jìn)行平衡的劃分從而使得檢索速度最快；而范例索引則要考慮是否有利于將來(lái)的范例檢索，它決定了針對(duì)某個(gè)具體的問(wèn)題哪些范例被復(fù)用；②索引應(yīng)該有一定的抽象或泛化程度，這樣才能靈活處理以后可能遇到的各種情景，太具體則不能滿足更多的情況；③索引應(yīng)該有一定的具體性，這樣才能在以后被容易地識(shí)別出來(lái)，太抽象則各個(gè)范例之間的差別將被消除。2023/1/3155《人工智能》范例學(xué)習(xí)的主要問(wèn)題（1）

(1)范例表示：基于范例推理方法的效率和范例表示緊密相關(guān)。范例表示涉及這樣幾個(gè)問(wèn)題:選擇什么信息存放在一個(gè)范例中；如何選擇合適的范例內(nèi)容描述結(jié)構(gòu)；范例庫(kù)如何組織和索引。對(duì)于那些數(shù)量達(dá)到成千上萬(wàn)、而且十分復(fù)雜的范例,組織和索引問(wèn)題尤其重要。

(2)分析模型：分析模型用于分析目標(biāo)范例，從中識(shí)別和抽取檢索源范例庫(kù)的信息。

(3)范例檢索：利用檢索信息從源范例庫(kù)中檢索并選擇潛在可用的源范例。這步非常關(guān)鍵。一般講，范例匹配不是精確的，只能是部分匹配或近似匹配。因此，它要求有一個(gè)相似度的評(píng)價(jià)標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)定義得好，會(huì)使得檢索出的范例十分有用，否則將會(huì)嚴(yán)重影響后面的過(guò)程。2023/1/3156《人工智能》范例學(xué)習(xí)的主要問(wèn)題（2）

(4)類比映射:

尋找目標(biāo)范例同源范例之間的對(duì)應(yīng)關(guān)系。

(5)類比轉(zhuǎn)換:

轉(zhuǎn)換源范例中同目標(biāo)范例相關(guān)的信息，以便應(yīng)用于目標(biāo)范例的求解過(guò)程中。把檢索到的源范例的解答復(fù)用于新問(wèn)題或新范例之中需要解決的問(wèn)題分別是：源范例與目標(biāo)范例間有何不同之處；源范例中的哪些部分可以用于目標(biāo)范例。需要根據(jù)它們之間的不同對(duì)復(fù)用的求解方案進(jìn)行調(diào)整。

(6)解釋過(guò)程:

對(duì)把轉(zhuǎn)換過(guò)的源范例的求解方案應(yīng)用到目標(biāo)范例時(shí)所出現(xiàn)的失敗做出解釋，給出失敗的因果分析報(bào)告。有時(shí)對(duì)成功也同樣做出解釋?；诮忉尩乃饕彩且环N重要的方法。

(7)范例修補(bǔ):

有些類似于類比轉(zhuǎn)換，區(qū)別在于修補(bǔ)過(guò)程的輸入是解方案和一個(gè)失敗報(bào)告，而且也許還包含一個(gè)解釋，然后修改這個(gè)解以排除失敗的因素。2023/1/3157《人工智能》范例學(xué)習(xí)的主要問(wèn)題（3）

(8)類比驗(yàn)證:

驗(yàn)證目標(biāo)范例和源范例進(jìn)行類比的有效性。

(9)范例保存:

新問(wèn)題得到了解決，則形成了一個(gè)可能用于將來(lái)情形與之相似的問(wèn)題。這時(shí)有必要把它加入到范例庫(kù)中。這是學(xué)習(xí)也是知識(shí)獲取。此過(guò)程涉及選取哪些信息保留，以及如何把新范例有機(jī)集成到范例庫(kù)中。修改和精化源范例庫(kù),其中包括泛化和抽象等過(guò)程。在決定選取范例的哪些信息進(jìn)行保留時(shí)，一般要考慮以下幾點(diǎn)：和問(wèn)題有關(guān)的特征描述；問(wèn)題的求解結(jié)果；以及解答為什么成功或失敗的原因及解釋。把新范例加入到范例庫(kù)中，需要對(duì)它建立有效的索引，這樣以后才能對(duì)之作出有效的回憶。為此，可能要對(duì)范例庫(kù)的索引內(nèi)容甚至結(jié)構(gòu)進(jìn)行調(diào)整，如改變索引的強(qiáng)度或特征權(quán)值。2023/1/3158《人工智能》5.5

解釋學(xué)習(xí)基于解釋的學(xué)習(xí)：一種從單個(gè)觀察中抽象出通用規(guī)則的方法目標(biāo)是下次可以快速地解決類似的問(wèn)題通過(guò)保存結(jié)果和避免從零開始解決問(wèn)題來(lái)提高速度更進(jìn)一步EBL從觀察到規(guī)則

解釋學(xué)習(xí)(Explanation-BasedLearning,簡(jiǎn)稱EBL)是一種分析學(xué)習(xí)方法，在領(lǐng)域知識(shí)指導(dǎo)下,通過(guò)對(duì)單個(gè)問(wèn)題求解實(shí)例的分析,構(gòu)造出求解過(guò)程的因果解釋結(jié)構(gòu),并獲取控制知識(shí),以便用于指導(dǎo)以后求解類似問(wèn)題。2023/1/3159《人工智能》解釋學(xué)習(xí)過(guò)程和算法

解釋學(xué)習(xí)一般包括下列3個(gè)步驟：

(1)利用基于解釋的方法對(duì)訓(xùn)練例子進(jìn)行分析與解釋。

(2)對(duì)例子的結(jié)構(gòu)進(jìn)行概括性解釋。

(3)從解釋結(jié)構(gòu)中識(shí)別出訓(xùn)練例子的特性，獲取一般控制知識(shí)。

1986年米切爾（Mitchell）等人為基于解釋的學(xué)習(xí)提出了一個(gè)統(tǒng)一的算法EBG，該算法建立了基于解釋的概括過(guò)程，并運(yùn)用知識(shí)的邏輯表示和演繹推理進(jìn)行問(wèn)題求解。下圖表示EBG問(wèn)題。2023/1/3160《人工智能》

EBG求解問(wèn)題的形式描述:給定：

(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。圖EBG問(wèn)題2023/1/3161《人工智能》5.6

強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)(reinforcementlearning--RL，又稱再勵(lì)學(xué)習(xí)，評(píng)價(jià)學(xué)習(xí))在智能控制機(jī)器人及分析預(yù)測(cè)等領(lǐng)域有許多應(yīng)用。在傳統(tǒng)的機(jī)器學(xué)習(xí)分類中沒有提及到過(guò)強(qiáng)化學(xué)習(xí)。而在連接主義學(xué)習(xí)中，把學(xué)習(xí)算法分為非監(jiān)督學(xué)習(xí)(unsupervisedlearning)、監(jiān)督學(xué)習(xí)(supervisedlearning)和強(qiáng)化學(xué)習(xí)三種。所謂強(qiáng)化學(xué)習(xí)就是智能系統(tǒng)從環(huán)境到行為映射的學(xué)習(xí)，以使獎(jiǎng)勵(lì)信號(hào)(強(qiáng)化信號(hào))函數(shù)值最大。強(qiáng)化學(xué)習(xí)不同于連接主義學(xué)習(xí)中的監(jiān)督學(xué)習(xí)，主要表現(xiàn)在教師信號(hào)上，強(qiáng)化學(xué)習(xí)中由環(huán)境提供的強(qiáng)化信號(hào)是對(duì)產(chǎn)生動(dòng)作的好壞作一種評(píng)價(jià)(通常為標(biāo)量信號(hào))，而不是告訴強(qiáng)化學(xué)習(xí)系統(tǒng)如何去產(chǎn)生正確的動(dòng)作。2023/1/3162《人工智能》強(qiáng)化學(xué)習(xí)通常包括兩個(gè)方面的含義：一方面是將強(qiáng)化學(xué)習(xí)作為一類問(wèn)題；另一方面是指解決這類問(wèn)題的一種技術(shù)。

如果將強(qiáng)化學(xué)習(xí)作為一類問(wèn)題，目前的學(xué)習(xí)技術(shù)大致可分成兩類：其一是搜索智能系統(tǒng)的行為空間，以發(fā)現(xiàn)系統(tǒng)最優(yōu)的行為。典型的技術(shù)如遺傳算法等搜索技術(shù)；另一類是采用統(tǒng)計(jì)技術(shù)和動(dòng)態(tài)規(guī)劃方法來(lái)估計(jì)在某一環(huán)境狀態(tài)下的行為的效用函數(shù)值，從而通過(guò)行為效用函數(shù)來(lái)確定最優(yōu)行為。我們特指這種學(xué)習(xí)技術(shù)為強(qiáng)化學(xué)習(xí)技術(shù)。2023/1/3163《人工智能》強(qiáng)化學(xué)習(xí)的產(chǎn)生與發(fā)展

強(qiáng)化思想最先來(lái)源于心理學(xué)的研究。1911年Thorndike提出了效果律（LawofEffect）：一定情景下讓動(dòng)物感到舒服的行為，就會(huì)與此情景增強(qiáng)聯(lián)系（強(qiáng)化），當(dāng)此情景再現(xiàn)時(shí)，動(dòng)物的這種行為也更易再現(xiàn)；相反，讓動(dòng)物感覺不舒服的行為，會(huì)減弱與情景的聯(lián)系，此情景再現(xiàn)時(shí)，此行為將很難再現(xiàn)。換個(gè)說(shuō)法，哪種行為會(huì)“記住”，會(huì)與刺激建立聯(lián)系，取決于行為產(chǎn)生的效果。動(dòng)物的試錯(cuò)學(xué)習(xí)，包含兩個(gè)含義：選擇和聯(lián)系，對(duì)應(yīng)計(jì)算上的搜索和記憶。所以，1954年，Minsky在他的博士論文中實(shí)現(xiàn)了計(jì)算上的試錯(cuò)學(xué)習(xí)。同年，F(xiàn)arley和Clark也在計(jì)算上對(duì)它進(jìn)行了研究。強(qiáng)化學(xué)習(xí)一詞最早出現(xiàn)于科技文獻(xiàn)是1961年Minsky

的論文“StepsTowardArtificialIntelligence”，此后開始廣泛使用。1969年，Minsky因在人工智能方面的貢獻(xiàn)而獲得計(jì)算機(jī)圖靈獎(jiǎng)。2023/1/3164《人工智能》強(qiáng)化學(xué)習(xí)的發(fā)展過(guò)程可粗略分為兩個(gè)階段：

強(qiáng)化學(xué)習(xí)的形成階段（50年代~60年代）Minsky首次提出“強(qiáng)化”和“強(qiáng)化學(xué)習(xí)”這些術(shù)語(yǔ)；Samuel的下棋程序采用類似值迭代、瞬時(shí)差分和Q學(xué)習(xí)的訓(xùn)練機(jī)制，來(lái)學(xué)習(xí)用線性函數(shù)表示的值函數(shù)；Saridis

把強(qiáng)化控制系統(tǒng)的控制器看成一個(gè)隨機(jī)自動(dòng)機(jī)，首次系統(tǒng)提出了采用強(qiáng)化學(xué)習(xí)來(lái)解決隨機(jī)控制系統(tǒng)的學(xué)習(xí)控制問(wèn)題。強(qiáng)化學(xué)習(xí)的發(fā)展階段（70年代~）1972年，Klopf把試錯(cuò)學(xué)習(xí)和時(shí)序差分結(jié)合在一起。1978年開始，Sutton、Barto、Moore等對(duì)這兩者結(jié)合開始進(jìn)行深入研究。1989年Watkins提出了Q-學(xué)習(xí)，也把強(qiáng)化學(xué)習(xí)的三條主線扭在了一起。1992年，Tesauro用強(qiáng)化學(xué)習(xí)成功了應(yīng)用到西洋雙陸棋中，稱為TD-Gammon。2023/1/3165《人工智能》5.6.1強(qiáng)化學(xué)習(xí)的原理

強(qiáng)化學(xué)習(xí)把學(xué)習(xí)看作試探過(guò)程，基本過(guò)程如圖所示。在強(qiáng)化學(xué)習(xí)中，Agent選擇一個(gè)動(dòng)作作用于環(huán)境，環(huán)境接收該動(dòng)作后發(fā)生變化，同時(shí)產(chǎn)生一個(gè)強(qiáng)化信號(hào)（獎(jiǎng)或罰）反饋給Agent，Agent再根據(jù)強(qiáng)化信號(hào)和環(huán)境的當(dāng)前狀態(tài)再選擇下一個(gè)動(dòng)作，選擇的原則是使受到正的報(bào)酬的概率增大。選擇的動(dòng)作不僅影響立即強(qiáng)化值而且還影響下一時(shí)刻的狀態(tài)及最終強(qiáng)化值。強(qiáng)化學(xué)習(xí)的目的就是尋找一個(gè)最優(yōu)策。1、強(qiáng)化學(xué)習(xí)的結(jié)構(gòu)

Agent環(huán)境狀態(tài)s獎(jiǎng)賞r動(dòng)作a2023/1/3166《人工智能》強(qiáng)化學(xué)習(xí)模型由以下部分組成：2、強(qiáng)化學(xué)習(xí)模型

一個(gè)離散的狀態(tài)集S={s0,s1,s2,?,sn

}；動(dòng)作集A={a0,a1,a2,?,an}；一個(gè)強(qiáng)化值集r∈R；agent和環(huán)境交互的狀態(tài)—?jiǎng)幼餍蛄?si,ai)→ri，表示agent在狀態(tài)si

下執(zhí)行動(dòng)作ai

獲得的立即獎(jiǎng)賞值ri。agent執(zhí)行一個(gè)動(dòng)作除了獲得立即獎(jiǎng)賞信號(hào)外，還有從后續(xù)狀態(tài)—?jiǎng)幼饔成涞难舆t獎(jiǎng)賞。agent獲得的總獎(jiǎng)賞值為:其中∈[0,1]為折扣因子。Agent的任務(wù)就是學(xué)習(xí)控制策略π:S→A，能夠最大化期望獎(jiǎng)賞值的總和。2023/1/3167《人工智能》強(qiáng)化學(xué)習(xí)技術(shù)的基本原理是：如果系統(tǒng)某個(gè)動(dòng)作導(dǎo)致環(huán)境正的獎(jiǎng)賞，那么系統(tǒng)以后產(chǎn)生這個(gè)動(dòng)作的趨勢(shì)便會(huì)加強(qiáng)。反之系統(tǒng)產(chǎn)生這個(gè)動(dòng)作的趨勢(shì)便減弱。這和生理學(xué)中的條件反射原理是接近的。

如果假定環(huán)境是馬爾可夫型的，則順序型強(qiáng)化學(xué)習(xí)問(wèn)題可以通過(guò)馬氏決策過(guò)程（MarkovDecisionProcess，MDP）建模。下面首先給出馬氏決策過(guò)程的形式化定義。馬氏決策過(guò)程由四元組<S,A,R,P>定義。包含一個(gè)環(huán)境狀態(tài)集S，系統(tǒng)行為集合A，獎(jiǎng)賞函數(shù)R：S×A→?和狀態(tài)轉(zhuǎn)移函數(shù)P：S×A→PD(S)。記R(s,a,s’)為系統(tǒng)在狀態(tài)s采用a動(dòng)作使環(huán)境狀態(tài)轉(zhuǎn)移到s’獲得的瞬時(shí)獎(jiǎng)賞值，簡(jiǎn)記為Rass’；記P(s,a,s’)為系統(tǒng)在狀態(tài)s采用a動(dòng)作使環(huán)境狀態(tài)轉(zhuǎn)移到s’的概率，簡(jiǎn)記為Pass’。

2023/1/3168《人工智能》

馬氏決策過(guò)程的本質(zhì)是：當(dāng)前狀態(tài)向下一狀態(tài)轉(zhuǎn)移的概率和獎(jiǎng)賞值只取決于當(dāng)前狀態(tài)和選擇的動(dòng)作，而與歷史狀態(tài)和歷史動(dòng)作無(wú)關(guān)。因此在已知狀態(tài)轉(zhuǎn)移概率函數(shù)P和獎(jiǎng)賞函數(shù)R的環(huán)境模型知識(shí)下，可以采用動(dòng)態(tài)規(guī)劃技術(shù)求解最優(yōu)策略。而強(qiáng)化學(xué)習(xí)著重研究在P函數(shù)和R函數(shù)未知的情況下，系統(tǒng)如何學(xué)習(xí)最優(yōu)行為策略。由于模型中P函數(shù)和R函數(shù)未知，系統(tǒng)只能夠依賴于每次試錯(cuò)所獲得的瞬時(shí)獎(jiǎng)賞來(lái)選擇策略。但由于在選擇行為策略過(guò)程中，要考慮到環(huán)境模型的不確定性和目標(biāo)的長(zhǎng)遠(yuǎn)性，因此在策略和瞬時(shí)獎(jiǎng)賞之間構(gòu)造值函數(shù)（即狀態(tài)的效用函數(shù)），用于策略的選擇。2023/1/3169《人工智能》

首先通過(guò)下式構(gòu)造一個(gè)返回函數(shù)Rt，用于反映系統(tǒng)在某個(gè)策略π指導(dǎo)下的一次學(xué)習(xí)循環(huán)中，從st狀態(tài)往后所獲得的所有獎(jiǎng)賞的累計(jì)折扣和。

由于環(huán)境是不確定的，系統(tǒng)在某個(gè)策略π指導(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)遵循π策略，所能獲得的期望的累計(jì)獎(jiǎng)賞折扣和。2023/1/3170《人工智能》

根據(jù)Bellman最優(yōu)策略公式，在最優(yōu)策略π*下，系統(tǒng)在s狀態(tài)下的值函數(shù)定義為：

所以，強(qiáng)化學(xué)習(xí)的任務(wù)就是求解π*。

由于強(qiáng)化學(xué)習(xí)中，P函數(shù)和R函數(shù)未知，系統(tǒng)無(wú)法直接求解上面的值函數(shù)。因而實(shí)際中常采用逼近的方法進(jìn)行值函數(shù)的估計(jì)，其中最主要的方法之一是MonteCarlo采樣。2023/1/3171《人工智能》5.6.2強(qiáng)化學(xué)習(xí)算法

到目前為止，研究者們提出了很多強(qiáng)化學(xué)習(xí)算法，近年來(lái)對(duì)強(qiáng)化學(xué)習(xí)算法的研究已由算法本身逐漸轉(zhuǎn)向研究經(jīng)典算法在各種復(fù)雜環(huán)境中的應(yīng)用，較有影響的強(qiáng)化學(xué)習(xí)算法有TD算法，Q學(xué)習(xí)算法，Sarsa算法，Dyan算法，R學(xué)習(xí)算法，H學(xué)習(xí)等，還有一些改進(jìn)算法，如滯后更新多步Q-學(xué)習(xí)算法等。2023/1/3172《人工智能》1、蒙特卡羅算法

蒙特卡羅算法(MonteCarlomethod,MC)通過(guò)評(píng)估值函數(shù)來(lái)發(fā)現(xiàn)最優(yōu)策略，且不需要環(huán)境的全部信息，它只需要經(jīng)驗(yàn)知識(shí)。如部分有關(guān)狀態(tài)序列、動(dòng)作行為集以及同環(huán)境交互產(chǎn)生的獎(jiǎng)賞值的信息。

MC算法基于平均化取樣回報(bào)來(lái)解決強(qiáng)化學(xué)習(xí)問(wèn)題，它將解決的問(wèn)題分解成幕(episode)。當(dāng)環(huán)境狀態(tài)為終止?fàn)顟B(tài)時(shí)，將得到積累回報(bào)賦予開始狀態(tài)s的值函數(shù)V。從s出發(fā)到終止?fàn)顟B(tài)t的過(guò)程中，s可能不止出現(xiàn)一次。對(duì)s的值函數(shù)的更新有兩種方法：

(1)firstvisitMC將回報(bào)賦予第一次訪問(wèn)的s；

(2)everyvisitMC將每次訪問(wèn)s到t的回報(bào)平均后賦予s。2023/1/3173《人工智能》MC算法中，值函數(shù)更新規(guī)則為：其中，Rt為t時(shí)刻的獎(jiǎng)賞值，α為步長(zhǎng)參數(shù)。控制過(guò)程采用貪心搜索策略。TTTTTTTTTTTTTTTTTTTT2023/1/3174《人工智能》2、瞬時(shí)差分學(xué)習(xí)算法(TD算法)

TD(TemporalDifferences)算法是一種增量式學(xué)習(xí)算法，它不用建立環(huán)境的動(dòng)態(tài)信息模型，也不必等到最終輸出結(jié)果產(chǎn)生之后再修改以往學(xué)到的經(jīng)驗(yàn),而是直接從交互經(jīng)驗(yàn)中學(xué)習(xí)，在學(xué)習(xí)過(guò)程中逐步修改。

最簡(jiǎn)單的算法為一步TD算法，即TD(0)算法，是一種自適應(yīng)的策略迭代算法。所謂一步TD算法，是指Agent獲得的瞬時(shí)報(bào)酬值僅回退一步，也就是說(shuō)只是修改了相鄰狀態(tài)的估計(jì)值。TD(0)算法如式：

與MC算法相比，上式中用回報(bào)的估計(jì)值rt+1+V(st+1)代替了實(shí)際回報(bào)值Rt。2023/1/3175《人工智能》

TD算法可擴(kuò)充到TD()算法，即Agent獲得的瞬時(shí)報(bào)酬值可回退任意步。TD()算法的收斂速度有很大程度上的提高。

顯然，強(qiáng)化學(xué)習(xí)方法將需要更多次學(xué)習(xí)循環(huán)才能逼近實(shí)際的值函數(shù)。因此，我們考慮：能否在值函數(shù)更新中，不僅僅依賴當(dāng)前狀態(tài)的瞬時(shí)獎(jiǎng)賞值，也可以利用下一狀態(tài)的瞬時(shí)獎(jiǎng)賞值，一直到終結(jié)狀態(tài)？為此，構(gòu)造一個(gè)新的λ-返回函數(shù)Rt′：

其中假定系統(tǒng)在此次學(xué)習(xí)循環(huán)中第T步后進(jìn)入終結(jié)狀態(tài)。λ-返回函數(shù)Rt′的物理意義如圖所示（見下頁(yè)）。2023/1/3176《人工智能》那么值函數(shù)迭代為：2023/1/3177《人工智能》

由于強(qiáng)化學(xué)習(xí)算法中值函數(shù)的更新是在每一學(xué)習(xí)步進(jìn)行的，為使學(xué)習(xí)算法能在一次學(xué)習(xí)循環(huán)中值函數(shù)滿足上式迭代，設(shè)計(jì)TD(λ)算法如右邊所示。其中通過(guò)構(gòu)造e(s)函數(shù)，即可以保證在一次學(xué)習(xí)循環(huán)中值函數(shù)正確更新。2023/1/3178《人工智能》3、Q-學(xué)習(xí)算法

Q-

學(xué)習(xí)算法是由Watkins在1989年提出的一種無(wú)模型強(qiáng)化學(xué)習(xí)算法。Q-學(xué)習(xí)可以看作一種增量式動(dòng)態(tài)規(guī)劃，它通過(guò)直接優(yōu)化一個(gè)可迭代計(jì)算的動(dòng)作值函數(shù)Q(s,a)來(lái)找到一個(gè)策略，使得期望折扣報(bào)酬總和最大，而非TD算法中的狀態(tài)值V(s)。

Watkins定義Q函數(shù)為在狀態(tài)st下執(zhí)行動(dòng)作at

，且此后按最優(yōu)動(dòng)作序列執(zhí)行時(shí)的折扣累計(jì)強(qiáng)化值，即：Q函數(shù)的迭代公式為：(其中[0,1]為學(xué)習(xí)因子)2023/1/3179《人工智能》

算法在初始過(guò)程中初始化每個(gè)Q(s,a)值，然后根據(jù)貪心策略選擇最大的Q值，再通過(guò)迭代式得到實(shí)際迭代值，當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時(shí)此次迭代過(guò)程結(jié)束，再繼續(xù)從初始狀態(tài)進(jìn)行迭代，直至學(xué)習(xí)過(guò)程結(jié)束。2023/1/3180《人工智能》5.7

知識(shí)發(fā)現(xiàn)

近年來(lái)，

隨著大型數(shù)據(jù)庫(kù)不斷地涌現(xiàn)，如何迅速而準(zhǔn)確地獲得其中有用的信息和知識(shí),以預(yù)測(cè)模式和發(fā)現(xiàn)趨勢(shì)、創(chuàng)建和測(cè)試假設(shè)、產(chǎn)生形象化的表示等,已成為數(shù)據(jù)庫(kù)系統(tǒng)和機(jī)器學(xué)習(xí)中一個(gè)關(guān)鍵性的研究課題。數(shù)據(jù)庫(kù)系統(tǒng)雖然提供了對(duì)數(shù)據(jù)的管理和分析處理，但無(wú)法從中尋找和發(fā)現(xiàn)某些規(guī)律和模式。而人工智能處理方式很難對(duì)龐大的數(shù)據(jù)進(jìn)行有效的處理和應(yīng)用。機(jī)器學(xué)習(xí)能夠通過(guò)對(duì)數(shù)據(jù)及其關(guān)系的分析，提取出隱含在海量數(shù)據(jù)中的知識(shí)。數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)(knowledgediscovery

anddatabase,簡(jiǎn)稱KDD)技術(shù)就是在這種背景下應(yīng)運(yùn)而生的，我們把KDD簡(jiǎn)稱為知識(shí)發(fā)現(xiàn)。2023/1/3181《人工智能》5.7.1知識(shí)發(fā)現(xiàn)的發(fā)展和定義

知識(shí)發(fā)現(xiàn)最早是于1989年8月在第11屆國(guó)際人工智能聯(lián)合會(huì)議的專題討論會(huì)上提出。知識(shí)發(fā)現(xiàn)的產(chǎn)生和發(fā)展與數(shù)據(jù)處理的發(fā)展有密切的聯(lián)系。1960s:Datacollection,databasecreation,IMSandnetworkDBMS.1970s:Relationaldatamodel,relationalDBMSimplementation.1980s:RDBMS,advanceddatamodels(extended-relational,OO,deductive,etc.)andapplication-orientedDBMS(spatial,scientific,engineering,etc).1990s:Datamininganddatawarehousing,multimediadatabases,andWebtechnology.2023/1/3182《人工智能》1989IJCAIWorkshoponKDDKnowledgeDiscoveryinDatabases(G.Piatetsky-ShapiroandW.Frawley,eds.,1991)1991-1994WorkshopsonKDDAdvancesinKnowledgeDiscoveryandDataMining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy,eds.,1996)1995-1998AAAIInt.Conf.onKDDandDM(KDD’95-98)JournalofDataMiningandKnowledgeDiscovery(1997)1998ACMSIGKDD1999SIGKDD’99Conf.Importantdatesofdatamining2023/1/3183《人工智能》定義：KDD是從大量數(shù)據(jù)集中辨識(shí)出有效的、新穎的、潛在有用的、并可被理解的模式的高級(jí)處理過(guò)程。

對(duì)此定義的進(jìn)一步解釋：(1)數(shù)據(jù)集：是指一個(gè)有關(guān)事實(shí)F的集合，它是用來(lái)描述事物有關(guān)方面的信息，是進(jìn)一步發(fā)現(xiàn)知識(shí)的原材料。(2)新穎：經(jīng)過(guò)知識(shí)發(fā)現(xiàn)提取出的模式E必須是新穎的。通常可以用一個(gè)函數(shù)N(E,F)來(lái)表示模式的新穎程度。(3)潛在有用：提取出的模式應(yīng)該是有意義的，這可以通過(guò)某些函數(shù)的值來(lái)衡量。(4)可被人理解：知識(shí)發(fā)現(xiàn)的一個(gè)目標(biāo)就是將數(shù)據(jù)庫(kù)中隱含的模式以容易被人理解的形式表現(xiàn)出來(lái)，從而幫助人們更好地了解數(shù)據(jù)庫(kù)中所包含的信息。2023/1/3184《人工智能》(5)模式：對(duì)于集合F中的數(shù)據(jù)，可以用語(yǔ)言L以表達(dá)式E描述其中某些數(shù)據(jù)的特性。一個(gè)表達(dá)式E所描述的數(shù)據(jù)是F一個(gè)子集FE，只有當(dāng)表達(dá)式E比列舉出FE中所有元素的描述方法更簡(jiǎn)單時(shí)，才可稱為E為一個(gè)模式。

如：“成績(jī)優(yōu)良={80,81,82,83,84,85,86,87,88,89}”不是模式；而“IF成績(jī)≥80and成績(jī)＜90THEN成績(jī)優(yōu)良”可稱為一個(gè)模式。(6)高級(jí)過(guò)程：知識(shí)發(fā)現(xiàn)是對(duì)數(shù)據(jù)進(jìn)行更深層次處理的過(guò)程，而不僅僅是對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)單的運(yùn)算或查詢，需要一定程度的智能性和自主性。2023/1/3185《人工智能》5.7.2知識(shí)發(fā)現(xiàn)的處理過(guò)程Knowledge原始數(shù)據(jù)目標(biāo)數(shù)據(jù)整理后數(shù)據(jù)變換后數(shù)據(jù)模式/模型知識(shí)數(shù)據(jù)選擇數(shù)據(jù)預(yù)處理降維/轉(zhuǎn)換數(shù)據(jù)挖掘解釋評(píng)價(jià)2023/1/3186《人工智能》1、數(shù)據(jù)選擇。一個(gè)數(shù)據(jù)倉(cāng)庫(kù)包含了各種數(shù)據(jù),所以有必要根據(jù)用戶的需求從中提取與KDD相關(guān)的數(shù)據(jù)。2、數(shù)據(jù)預(yù)處理。主要是對(duì)上述數(shù)據(jù)進(jìn)行再加工，包括消除“噪聲”或去掉無(wú)用的數(shù)據(jù)，彌補(bǔ)遺漏數(shù)據(jù)，說(shuō)明時(shí)間序列信息和已知的變化等。3、數(shù)據(jù)降維和轉(zhuǎn)換所謂降維指在考慮了數(shù)據(jù)的不變表示的情況下,減少變量的實(shí)際數(shù)目。轉(zhuǎn)換包括對(duì)數(shù)據(jù)組織、數(shù)據(jù)類型轉(zhuǎn)換、數(shù)據(jù)屬性轉(zhuǎn)換等。4.數(shù)據(jù)挖掘。根據(jù)用戶要求，確定KDD的目標(biāo)，利用一種或多種技術(shù)，相繼地挖掘已轉(zhuǎn)換的數(shù)據(jù)，抽取感興趣的信息。5、知識(shí)評(píng)價(jià)。這一過(guò)程主要用于對(duì)所獲得的知識(shí)進(jìn)行價(jià)值評(píng)定，以決定所得的規(guī)則是否存入基礎(chǔ)知識(shí)庫(kù)。2023/1/3187《人工智能》5.7.3知識(shí)發(fā)現(xiàn)的方法

知識(shí)發(fā)現(xiàn)的方法有統(tǒng)計(jì)方法、機(jī)器學(xué)習(xí)、神經(jīng)計(jì)算和可視化方法等。

1、統(tǒng)計(jì)方法

統(tǒng)計(jì)方法是從事物的外在數(shù)量上的表現(xiàn)去推斷該事物可能的規(guī)律性。與統(tǒng)計(jì)學(xué)有關(guān)的知識(shí)發(fā)現(xiàn)方法有：(1)傳統(tǒng)方法

常見的統(tǒng)計(jì)方法有回歸分析、判別分析、聚類分析等。(2)模糊集(3)支持向量機(jī)

針對(duì)兩類分類問(wèn)題，在高維空間中尋找一個(gè)超平面作為兩類的分割，以保證最小的錯(cuò)誤分類率。(4)粗糙集2023/1/3188《人工智能》

2、機(jī)器學(xué)習(xí)方法

可能用于知識(shí)發(fā)現(xiàn)的機(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)的測(cè)試或決策。(3)范例推理。范例推理是直接使用過(guò)去的經(jīng)驗(yàn)或解法來(lái)求解給定的問(wèn)題。(4)貝葉斯信念網(wǎng)絡(luò)。貝葉斯信念網(wǎng)是概率分布的圖表示。(5)科學(xué)發(fā)現(xiàn)?？茖W(xué)發(fā)現(xiàn)是在實(shí)驗(yàn)環(huán)境下發(fā)現(xiàn)科學(xué)定律。(6)遺傳算法。在求解過(guò)程中，通過(guò)最好解的選擇和彼此組合，使期望解的集合愈來(lái)愈好。2023/1/3189《人工智能》

3、神經(jīng)網(wǎng)絡(luò)方法

人工神經(jīng)網(wǎng)絡(luò)建立在可以自學(xué)習(xí)的數(shù)學(xué)模型的基礎(chǔ)之上，它可以對(duì)大量復(fù)雜的數(shù)據(jù)進(jìn)行分析，并可以完成對(duì)人腦或其他計(jì)算機(jī)來(lái)說(shuō)極為復(fù)雜的模式抽取及趨勢(shì)分析。4、可視化方法

可視化（visualization）就是把數(shù)據(jù)、信息和知識(shí)轉(zhuǎn)化為可視的表示形式的過(guò)程?？梢暬瘮?shù)據(jù)分析技術(shù)拓寬了傳統(tǒng)的圖表功能，使用戶對(duì)數(shù)據(jù)的剖析更清楚。2023/1/3190《人工智能》5.7.4數(shù)據(jù)挖掘

數(shù)據(jù)挖掘是知識(shí)發(fā)現(xiàn)處理過(guò)程的一個(gè)核心環(huán)節(jié)，其任務(wù)就是從數(shù)據(jù)中發(fā)現(xiàn)模式。

定義：數(shù)據(jù)挖掘(Datamining--DM

)是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中提取隱含在其中的、人們事先不知道的但又是潛在有用的信息和知識(shí)的過(guò)程。

數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)這兩個(gè)術(shù)語(yǔ)的內(nèi)涵大致相同。嚴(yán)格地講，知識(shí)發(fā)現(xiàn)是從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)知識(shí)的全部過(guò)程，而數(shù)據(jù)挖掘則是此全部過(guò)程的一個(gè)特定的、關(guān)鍵步驟。在通常情況下，許多人把數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)廣泛地認(rèn)為是同一個(gè)概念，一般在科研領(lǐng)域中稱為知識(shí)發(fā)現(xiàn)，而在工程領(lǐng)域則稱為數(shù)據(jù)挖掘。2023/1/3191《人工智能》數(shù)據(jù)挖掘的類型

數(shù)據(jù)挖掘按其功能劃分主要包括以下幾類：①關(guān)聯(lián)分析

若兩個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的取值重復(fù)出現(xiàn)且概率很高時(shí)，它就存在著某種關(guān)聯(lián)，可以建立起這些數(shù)據(jù)項(xiàng)的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫(kù)中隱藏的