高級(jí)人工智能第5講機(jī)器學(xué)習(xí)

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室1/89高級(jí)人工智能機(jī)器學(xué)習(xí)

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室2/891機(jī)器學(xué)習(xí)概述

學(xué)習(xí)的基本概念

學(xué)習(xí)是人類具有的一種重要的智能行為。

西蒙的觀點(diǎn)：學(xué)習(xí)就是系統(tǒng)在不斷重復(fù)的工作中對(duì)本身能力的增強(qiáng)或者改進(jìn)，使得系統(tǒng)在下一次執(zhí)行同樣任務(wù)或類似任務(wù)時(shí)，會(huì)比現(xiàn)在做得更好或效率更高。1959年Samuel下棋程序，具有學(xué)習(xí)能力。4年后程序戰(zhàn)勝了設(shè)計(jì)者，又3年后戰(zhàn)勝了美國(guó)一個(gè)冠軍。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室3/891機(jī)器學(xué)習(xí)概述

機(jī)器學(xué)習(xí)的定義

機(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)。

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室4/891機(jī)器學(xué)習(xí)概述如果一個(gè)計(jì)算機(jī)程序要完成某類任務(wù)T，其完成任務(wù)的性能可以用P衡量，該程序根據(jù)經(jīng)驗(yàn)E改進(jìn)P，則稱該程序針對(duì)任務(wù)T以性能P衡量從經(jīng)驗(yàn)E中學(xué)習(xí)(T.Mitchell，機(jī)器學(xué)習(xí))對(duì)于一個(gè)學(xué)習(xí)系統(tǒng)，必須明確：任務(wù)的種類衡量性能提高的標(biāo)準(zhǔn)經(jīng)驗(yàn)的來(lái)源2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室5/891機(jī)器學(xué)習(xí)概述

機(jī)器學(xué)習(xí)的發(fā)展

機(jī)器學(xué)習(xí)是人工智能應(yīng)用研究較為重要的分支，它的發(fā)展過(guò)程大體上可分為4個(gè)時(shí)期：（1）第一階段是在50年代中葉到60年代中葉，屬于熱烈時(shí)期。在這個(gè)時(shí)期，所研究的是“沒(méi)有知識(shí)”的學(xué)習(xí)，即“無(wú)知”學(xué)習(xí)；其研究目標(biāo)是各類自組織系統(tǒng)和自適應(yīng)系統(tǒng)；指導(dǎo)本階段研究的理論基礎(chǔ)是早在40年代就開(kāi)始研究的神經(jīng)網(wǎng)絡(luò)模型。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室6/895.1機(jī)器學(xué)習(xí)概述（2）第二階段在60年代中葉至70年代中葉，被稱為機(jī)器學(xué)習(xí)的冷靜時(shí)期。本階段的研究目標(biāo)是模擬人類的概念學(xué)習(xí)過(guò)程，并采用邏輯結(jié)構(gòu)或圖結(jié)構(gòu)作為機(jī)器內(nèi)部描述。（3）第三階段從70年代中葉至80年代中葉，稱為復(fù)興時(shí)期。在這個(gè)時(shí)期，人們從學(xué)習(xí)單個(gè)概念擴(kuò)展到學(xué)習(xí)多個(gè)概念，探索不同的學(xué)習(xí)策略和各種學(xué)習(xí)方法。本階段已開(kāi)始把學(xué)習(xí)系統(tǒng)與各種應(yīng)用結(jié)合起來(lái)。（4）機(jī)器學(xué)習(xí)的最新階段始于1986年。一方面，由于神經(jīng)網(wǎng)絡(luò)研究的重新興起，另一方面，對(duì)實(shí)驗(yàn)研究和應(yīng)用研究得到前所未有的重視。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室7/895.1機(jī)器學(xué)習(xí)概述

機(jī)器學(xué)習(xí)研究與應(yīng)用的發(fā)展趨勢(shì)（1）

從有教師指導(dǎo)的歸納學(xué)習(xí)向無(wú)教師指導(dǎo)的發(fā)現(xiàn)學(xué)習(xí)轉(zhuǎn)變。以數(shù)據(jù)挖掘?yàn)楹诵募夹g(shù)的發(fā)現(xiàn)學(xué)習(xí)成為最有價(jià)值的機(jī)器學(xué)習(xí)技術(shù)。

（2）

從面向確定性環(huán)境的觀察學(xué)習(xí)到面向不確定性環(huán)境的統(tǒng)計(jì)學(xué)習(xí)轉(zhuǎn)變。概率理論和統(tǒng)計(jì)分析處理不確定問(wèn)題。

（3）

從缺乏堅(jiān)實(shí)理論的經(jīng)驗(yàn)性學(xué)習(xí)到具有嚴(yán)密數(shù)學(xué)基礎(chǔ)的學(xué)習(xí)理論轉(zhuǎn)變。粗糙集和統(tǒng)計(jì)學(xué)習(xí)理論。

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室8/895.2學(xué)習(xí)的一般形式在學(xué)習(xí)智能體中，對(duì)執(zhí)行元件進(jìn)行反饋并加以修正的元件是學(xué)習(xí)元件執(zhí)行器環(huán)境傳感器智能體性能標(biāo)準(zhǔn)評(píng)論元件學(xué)習(xí)元件問(wèn)題產(chǎn)生器執(zhí)行元件反饋學(xué)習(xí)的目標(biāo)知識(shí)變化2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室9/895.2學(xué)習(xí)的一般形式學(xué)習(xí)元件的設(shè)計(jì)影響學(xué)習(xí)元件設(shè)計(jì)的主要因素：執(zhí)行元件的哪個(gè)組成部分進(jìn)行學(xué)習(xí)—誰(shuí)要學(xué)習(xí)(who)組成部分從學(xué)習(xí)中得到什么反饋—怎么學(xué)習(xí)(how)組成部分是如何表示的—學(xué)習(xí)什么(what)決定智能體學(xué)習(xí)本質(zhì)的最重要因素是學(xué)習(xí)中的反饋類型2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室10/895.2學(xué)習(xí)的一般形式學(xué)習(xí)的三種類型有監(jiān)督(有指導(dǎo))學(xué)習(xí)—從其輸入/輸出的實(shí)例中學(xué)習(xí)一個(gè)函數(shù)無(wú)監(jiān)督(無(wú)指導(dǎo))學(xué)習(xí)—在未提供明確的輸出值情況下，學(xué)習(xí)輸入的模式主要在概率推理系統(tǒng)的上下文中研究無(wú)監(jiān)督學(xué)習(xí)強(qiáng)化學(xué)習(xí)—從強(qiáng)化物中學(xué)習(xí)，而不是根據(jù)指導(dǎo)進(jìn)行學(xué)習(xí)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室11/895.2學(xué)習(xí)的一般形式學(xué)習(xí)過(guò)程中的知識(shí)表示如何表示學(xué)到的信息(各種方案—智能體的任何組成部分)邏輯公式(學(xué)到的規(guī)則)貝葉斯網(wǎng)絡(luò)(學(xué)到的概率描述)線性加權(quán)函數(shù)(作為學(xué)習(xí)得到的啟發(fā)函數(shù))先驗(yàn)知識(shí)的可用性—大部分人類學(xué)習(xí)發(fā)生在具有大量背景知識(shí)的上下文環(huán)境中不同的背景知識(shí)會(huì)導(dǎo)致對(duì)同一事物的不同認(rèn)識(shí)(如物理學(xué)家和畫(huà)家對(duì)云室照片的看法)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室12/895.2學(xué)習(xí)的一般形式關(guān)于學(xué)習(xí)的幾個(gè)一般性問(wèn)題是否可能獨(dú)立于學(xué)習(xí)算法確定學(xué)習(xí)問(wèn)題中的固有難度？能否知道需要多少訓(xùn)練樣例才能必要地或者充分地保證學(xué)習(xí)成功？(必要或充分條件)如果允許學(xué)習(xí)系統(tǒng)與施教者(人類)提問(wèn)，而不是僅僅觀察訓(xùn)練集中的隨機(jī)樣本，會(huì)對(duì)所需樣例有什么影響？能否刻畫(huà)出學(xué)習(xí)系統(tǒng)在學(xué)到目標(biāo)函數(shù)之前出錯(cuò)的概率？能否刻畫(huà)出一類學(xué)習(xí)問(wèn)題的固有計(jì)算復(fù)雜度？2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室13/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.1機(jī)械學(xué)習(xí)1.機(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ò)多的加工。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室14/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.1機(jī)械學(xué)習(xí)2.數(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/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室15/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.1機(jī)械學(xué)習(xí)存儲(chǔ)計(jì)算推導(dǎo)歸納算法與理論機(jī)械記憶搜索規(guī)則2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室16/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.1機(jī)械學(xué)習(xí)3.主要問(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/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室17/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.2基于解釋的學(xué)習(xí)解釋學(xué)習(xí)（explanation最初是由美國(guó)Illinois大學(xué)的DeJong于1983年提出來(lái)的。在經(jīng)驗(yàn)學(xué)習(xí)的基礎(chǔ)上，運(yùn)用領(lǐng)域知識(shí)對(duì)單個(gè)例子的問(wèn)題求解作出解釋，這是一種關(guān)于知識(shí)間因果關(guān)系的推理分析，可產(chǎn)生一般的控制策略。

解釋學(xué)習(xí)根據(jù)任務(wù)所在領(lǐng)域知識(shí)和正在學(xué)習(xí)的概念知識(shí)，對(duì)當(dāng)前實(shí)例進(jìn)行分析和求解，得出一個(gè)表征求解過(guò)程的因果解釋樹(shù)，以獲取新的知識(shí)。在獲取新的知識(shí)過(guò)程中，通過(guò)對(duì)屬性、表征現(xiàn)象和內(nèi)在關(guān)系等進(jìn)行解釋而學(xué)習(xí)到新的知識(shí)。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室18/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.2基于解釋的學(xué)習(xí)

解釋學(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，Keller和Kedar-Cabelli等人為基于解釋的學(xué)習(xí)提出了一個(gè)統(tǒng)一的算法EBG(Explanation-Based

Generalization)，該算法建立了基于解釋的概括過(guò)程，并運(yùn)用知識(shí)的邏輯表示和演繹推理進(jìn)行問(wèn)題求解。

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室19/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.2基于解釋的學(xué)習(xí)

操作規(guī)則目標(biāo)概念訓(xùn)練實(shí)例新規(guī)則領(lǐng)域知識(shí)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室20/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.2基于解釋的學(xué)習(xí)

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。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室21/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.2基于解釋的學(xué)習(xí)

其中，領(lǐng)域知識(shí)DT是相關(guān)領(lǐng)域的實(shí)施和規(guī)則，在學(xué)習(xí)系統(tǒng)中作為背景知識(shí)，用于證明訓(xùn)練實(shí)例TE為什么可以作為目標(biāo)概念的一個(gè)實(shí)例，從而形成相應(yīng)的解釋。訓(xùn)練實(shí)例TE是為學(xué)習(xí)系統(tǒng)提供一個(gè)例子，在學(xué)習(xí)過(guò)程中起著重要的作用，它應(yīng)能充分地說(shuō)明目標(biāo)概念TC。操作規(guī)則OC用于指導(dǎo)學(xué)習(xí)系統(tǒng)對(duì)目標(biāo)概念進(jìn)行取舍，使得通過(guò)學(xué)習(xí)產(chǎn)生的關(guān)于目標(biāo)概念TC的一般性描述成為可用的一般性知識(shí)?；诮忉尩膶W(xué)習(xí)從本質(zhì)上說(shuō)屬于演繹學(xué)習(xí)，它是根據(jù)給定的領(lǐng)域知識(shí)，進(jìn)行保真的演繹推理，存儲(chǔ)有用結(jié)論，經(jīng)過(guò)知識(shí)的求精和編輯，產(chǎn)生適合以后求解類似問(wèn)題的控制知識(shí)。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室22/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.3基于事例的學(xué)習(xí)

當(dāng)無(wú)法建立好的模型時(shí)，可通過(guò)記錄事例進(jìn)行學(xué)習(xí)。

采用基于事例的學(xué)習(xí)：首先，任何時(shí)候都可以應(yīng)用相容啟發(fā)方法，把某個(gè)預(yù)先觀察過(guò)的事物的特性賦予一個(gè)從未見(jiàn)過(guò)的新事物；其次，學(xué)會(huì)如何用于k維樹(shù)結(jié)構(gòu)迅速找到特征空間內(nèi)的最近鄰物體。

相容啟發(fā)：無(wú)論何時(shí)要猜測(cè)某事物的特性，除了提供一套參考事例外不知道其他情況；通過(guò)測(cè)量其他事物的已知特性，找到最相近的事例，該事例的特性特性是已知的。作為猜測(cè)：所求未知特性是與最相似事例的已知特性一樣的。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室23/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.3基于概念的學(xué)習(xí)

歸納學(xué)習(xí)的定義（1）歸納（induction）是人類拓展認(rèn)識(shí)能力的重要方法，是一種從個(gè)別到一般的，從部分到整體的推理行為。（2）歸納推理是應(yīng)用歸納方法，從足夠多的具體事例中歸納出一般性知識(shí)，提取事物的一般規(guī)律；它是一種從個(gè)別到一般的推理。（3）歸納學(xué)習(xí)（inductionlearning）是應(yīng)用歸納推理進(jìn)行學(xué)習(xí)的一種方法。

從應(yīng)用角度看，歸納學(xué)習(xí)可分為概念學(xué)習(xí)、概念聚集和啟發(fā)學(xué)習(xí)三種。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室24/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.3基于概念的學(xué)習(xí)

概念學(xué)習(xí)研究的路線：

（1）基于工程方法的概念學(xué)習(xí)，它從可能的學(xué)習(xí)機(jī)理出發(fā)，試圖試驗(yàn)并確定概念學(xué)習(xí)的工程方法。

（2）基于認(rèn)知建模的概念學(xué)習(xí)，開(kāi)發(fā)出人類概念學(xué)習(xí)的計(jì)算理論。概念學(xué)習(xí)的任務(wù)：構(gòu)造類型定義、分類程序（分類）2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室25/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.4基于類比的學(xué)習(xí)

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í)。

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室26/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.4基于類比的學(xué)習(xí)

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

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

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

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室27/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.4基于類比的學(xué)習(xí)

(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/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室28/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.4基于類比的學(xué)習(xí)

2.類比學(xué)習(xí)過(guò)程與研究類型類比學(xué)習(xí)主要包括如下四個(gè)過(guò)程：

(1)輸入一組已知條件（已解決問(wèn)題）和一組未完全確定的條件（新問(wèn)題）。

(2)對(duì)輸入的兩組條件，根據(jù)其描述，按某種相似性的定義尋找兩者可類比的對(duì)應(yīng)關(guān)系。

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室29/895.3常見(jiàn)的幾種學(xué)習(xí)方法5.3.5基于類比的學(xué)習(xí)

(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/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室30/895.4

歸納學(xué)習(xí)歸納學(xué)習(xí)也可以稱作歸納推理或簡(jiǎn)稱歸納，其任務(wù)是：給定函數(shù)f(未知)的實(shí)例集合，返回一個(gè)近似于f的函數(shù)h—h稱為假設(shè)，所有h的集合稱為假設(shè)空間一個(gè)好的假設(shè)應(yīng)該能夠預(yù)測(cè)未見(jiàn)過(guò)的實(shí)例—這就是基本的歸納問(wèn)題問(wèn)題實(shí)例—用一個(gè)單變量函數(shù)來(lái)擬合若干數(shù)據(jù)點(diǎn)，選擇最高次數(shù)為k的多項(xiàng)式集合作為假設(shè)h的集合，即假設(shè)空間H2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室31/895.4

歸納學(xué)習(xí)數(shù)據(jù)擬合2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室32/895.4

歸納學(xué)習(xí)Ockham剃刀原則上圖中顯示了擬合兩兩一組數(shù)據(jù)的不同函數(shù)—與所有數(shù)據(jù)一致的函數(shù)稱為一致假設(shè)如何在多個(gè)一致假設(shè)之間進(jìn)行選擇？答案—奧卡姆剃刀原則(Ockham’srazor)—優(yōu)先選擇與數(shù)據(jù)一致的最簡(jiǎn)單假設(shè)原因—比數(shù)據(jù)本身更復(fù)雜的假設(shè)不能從數(shù)據(jù)中提取任何模式此外，對(duì)于非確定性函數(shù)，在假設(shè)的復(fù)雜度和數(shù)據(jù)擬合度之間進(jìn)行折中不可避免2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室33/895.4

歸納學(xué)習(xí)假設(shè)空間的選擇如果假設(shè)空間包含真實(shí)函數(shù)，那么學(xué)習(xí)的問(wèn)題就是可實(shí)現(xiàn)的，否則是不可實(shí)現(xiàn)的—但是真實(shí)函數(shù)是未知的，因此不能確定一個(gè)給定的學(xué)習(xí)問(wèn)題是否可實(shí)現(xiàn)解決方案：使用先驗(yàn)知識(shí)得到一個(gè)假設(shè)空間，真實(shí)的函數(shù)一定包含在該假設(shè)空間采用最大可能的假設(shè)空間—在假設(shè)空間的表達(dá)能力和在該空間中找到簡(jiǎn)單的一致假設(shè)之間存在一個(gè)折中—也要考慮較強(qiáng)的表示能力2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室34/895.4

歸納學(xué)習(xí)歸納學(xué)習(xí)假設(shè)和歸納偏置歸納學(xué)習(xí)假設(shè)—任一假設(shè)如果在足夠大的訓(xùn)練樣例集中很好地逼近目標(biāo)函數(shù)，它也能在未見(jiàn)實(shí)例中很好地逼近目標(biāo)函數(shù)歸納偏置—?dú)w納學(xué)習(xí)需要某種形式的預(yù)先假定如果學(xué)習(xí)器不對(duì)目標(biāo)概念的形式作預(yù)先假定，它從根本上無(wú)法對(duì)未見(jiàn)實(shí)例進(jìn)行分類歸納學(xué)習(xí)算法的有偏性是對(duì)未見(jiàn)數(shù)據(jù)分類的依據(jù)—有偏性越強(qiáng)，則歸納能力越強(qiáng)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室35/895.5決策樹(shù)決策樹(shù)歸納是歸納學(xué)習(xí)算法中最簡(jiǎn)單也是最成功的算法之一—好的入門決策樹(shù)以事物的屬性描述集合作為輸入，輸出通常是一個(gè)分類(離散的輸出)—一般是二值分類(真或假)例子：星期六上午是否適合打網(wǎng)球?qū)傩?{outlook，humidity，wind}屬性值={sunny,overcast,rain,high,normal,strong,weak}2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室36/895.5決策樹(shù)OutlookWindHumiditySunnyOvercastRainHighNormal StrongWeakYesNoYesNoYes2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室37/895.5決策樹(shù)決策樹(shù)學(xué)習(xí)的適用問(wèn)題決策樹(shù)適合具有以下特征的學(xué)習(xí)：實(shí)例是由“屬性-值”對(duì)表示的—固定的屬性+離散或連續(xù)的取值目標(biāo)函數(shù)具有離散的輸出值析取表達(dá)式訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤—決策樹(shù)學(xué)習(xí)的魯棒性好訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室38/895.5決策樹(shù)

決策樹(shù)算法決策樹(shù)學(xué)習(xí)包括2個(gè)步驟：從實(shí)例中歸納出決策樹(shù)(建立決策樹(shù))利用決策樹(shù)對(duì)新實(shí)例進(jìn)行分類判斷如何建立決策樹(shù)：如果存在一些正例和反例，選擇劃分它們的最佳屬性如果剩下的都是正例或者反例，則分類已經(jīng)完成，回答Yes或No如果沒(méi)有剩下實(shí)例，則返回一個(gè)缺省值如果沒(méi)有剩下的屬性但還有剩下的實(shí)例，則數(shù)據(jù)中含有噪聲2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室39/895.5決策樹(shù)決策樹(shù)建樹(shù)算法

FunctionDecision-Tree-Learning(examples,attributes,default)returnadecisiontree

Input:{examples},{attributes},default

if{examples}=emptythenreturndefault

elseif{examples}=sameclassthenreturntheclassification

elseif{attributes}=emptythenreturnMajority-value(examples)

elseBest←Choose-Attr(attributes,examples) Tree←anewdecisiontreewithrootattr-test=Best M←Majority-Value(examples)

foreachBest=Vido Examplesi←{examplesofBest=Vi} Subtree←Decision-Tree-Learning(Examplesi,attributes-Best,M) addabranchBest=Vi&SubtreetoTree

returnTree2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室40/895.5決策樹(shù)TheTDIDTfamilytreeCLS(1963)ACLS(1981)ID3(1979)ASSISTANT(1984)ID3(Quinlan,1979,1985)是一種自頂向下增長(zhǎng)樹(shù)的貪婪算法，在每個(gè)節(jié)點(diǎn)選取能最好的分類樣例的屬性。繼續(xù)這個(gè)過(guò)程直到這棵樹(shù)能完美分類訓(xùn)練樣例，或所有的屬性都已被使用過(guò)。Hunt’sConceptLearningSystemframework,CLSconstructsadecisiontreethatattemptstominimizethecostofclassifyinganobject.ACLS(PatersonandNiblett)是ID3的推廣。允許用于描述事例的每個(gè)屬性取任意多個(gè)整數(shù)值。而ID3和CLS只允許每個(gè)屬性取有限個(gè)離散值。使得算法可以處理圖像識(shí)別等更復(fù)雜問(wèn)題。ASSISTANT(Kononenko,BratkoandRoskar)允許事例的屬性取連續(xù)的實(shí)數(shù)值；某些分類值可以屬于另一個(gè)分類；還可以從所提供的數(shù)據(jù)中選擇一個(gè)“較好”的訓(xùn)練集。用于醫(yī)學(xué)診斷問(wèn)題。基本的決策樹(shù)學(xué)習(xí)算法2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室41/895.5決策樹(shù)最為典型的決策樹(shù)學(xué)習(xí)算法是由J.RossQuinlan1979年提出的ID3算法。ID3（IterativeDichotomiser，迭代的二分器)算法是一種基于信息熵的決策樹(shù)算法，以Shannon的信息論為依據(jù)。ID3改進(jìn)、優(yōu)化：C4.5算法：1993年，Quinlan出版了專著《機(jī)器學(xué)習(xí)規(guī)劃》對(duì)C4.5算法進(jìn)行詳細(xì)描述。CART(ClassificationandRegressionTree)算法：描述了二叉決策樹(shù)的產(chǎn)生，可對(duì)連續(xù)型因變量進(jìn)行處理。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室42/895.5決策樹(shù)決策樹(shù)（又稱判定樹(shù)decisiontree)是一種樹(shù)結(jié)構(gòu)，其節(jié)點(diǎn)分為兩類：一類是內(nèi)節(jié)點(diǎn)，另一類是葉節(jié)點(diǎn)。

內(nèi)節(jié)點(diǎn)：一般用一個(gè)屬性名來(lái)標(biāo)記，代表對(duì)該屬性的測(cè)試。與內(nèi)節(jié)點(diǎn)連接的邊表示對(duì)該屬性測(cè)試的輸出。

葉節(jié)點(diǎn)：每個(gè)葉節(jié)點(diǎn)表示分類結(jié)果，一般用類標(biāo)號(hào)屬性值來(lái)標(biāo)記。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室43/895.5決策樹(shù)如何構(gòu)造一顆具有較高分類準(zhǔn)確率的決策樹(shù)？

關(guān)鍵：如何確定當(dāng)前要以哪個(gè)屬性作為測(cè)試屬性？1948年Shannon提出并發(fā)展了信息論，研究以數(shù)學(xué)的方法度量并研究信息。通過(guò)通信后對(duì)信源中各種符號(hào)出現(xiàn)的不確定程度的消除來(lái)度量信息量的大小。

（1）自信息量

設(shè)系統(tǒng)S中有多個(gè)可能發(fā)生的事件：a1,a2,…an，事件ai發(fā)生的概率為p(ai),i=1,2,…,n，p(ai)∈[0,1]p(ai)越大，事件ai不確定程度越低，反之，則越高。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室44/895.5決策樹(shù)用-logp(ai)表示事件ai的不確定程度，稱為ai的自信息量I(ai)I(ai)=-logp(ai)//log以2為底

（2）信息熵（entropy）如果將S看作一個(gè)信源，a1,a2,…an看成信源S發(fā)出的n種類型的信息，則信源S的不確定性可以用平均自信息量來(lái)度量，記為H(S)，定義：

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室45/895.5決策樹(shù)決策樹(shù)的學(xué)習(xí)

決策樹(shù)學(xué)習(xí)的過(guò)程是從空樹(shù)開(kāi)始，從訓(xùn)練集中不斷選擇測(cè)試屬性，逐步創(chuàng)建決策樹(shù)的過(guò)程。

設(shè)X為訓(xùn)練集，分為m類，第i類中的訓(xùn)練實(shí)例集合記為Ci，i=1,2,,…,m，那么X中任意一個(gè)實(shí)例屬于類Ci的概率估計(jì)值為：p(Ci)=|Ci|/|X|其中|X|表示集合X中的元素個(gè)數(shù)。訓(xùn)練集X關(guān)于類簇C={C1,C2,…,Cm}的分類不確定性可用下列的信息熵來(lái)度量：2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室46/895.5決策樹(shù)

在C已知的情況下（訓(xùn)練集中已確定），H(X,C)簡(jiǎn)寫為H(X)。

構(gòu)造決策樹(shù)的目的：將訓(xùn)練集X的不確定程度H(X)降至最低。從而可以對(duì)未知數(shù)據(jù)（X集以外的數(shù)據(jù)）進(jìn)行分類預(yù)測(cè)。

構(gòu)造決策樹(shù)的過(guò)程是從空樹(shù)開(kāi)始不斷添加節(jié)點(diǎn)的過(guò)程，關(guān)鍵是選擇測(cè)試屬性，使得構(gòu)造起來(lái)的“半”決策樹(shù)最大限度減低訓(xùn)練集X的信息熵H(X)。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室47/895.5決策樹(shù)

IDcolorsizeactageinflated1YELLOWSMALLSTRETCHADULTT2YELLOWSMALLSTRETCHCHILDT3YELLOWSMALLDIPCHILDF4YELLOWLARGESTRETCHADULTT5YELLOWLARGEDIPADULTT6YELLOWLARGEDIPCHILDF7PURPLESMALLSTRETCHCHILDT8PURPLESMALLDIPADULTT9PURPLESMALLDIPCHILDF10PURPLELARGESTRETCHCHILDT2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室48/895.5決策樹(shù)設(shè)A={a1,a2,…,ar}為候選的測(cè)試屬性，那么屬性A對(duì)X形成一個(gè)劃分{[a1],[a2],…,[ar]}，其中[ai]表示X中在屬性A上取值為ai的實(shí)例集合，i=1,2,…,r?，F(xiàn)對(duì)任意i∈{1,2,…,r}，考慮類[ai]。令則{}形成[ai]的一個(gè)劃分，于是類[ai]關(guān)于類簇{}的分類不確定性程度為：2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室49/895.5決策樹(shù)其中，表示類[ai]中任意一個(gè)實(shí)例屬于的概率，令稱E(A)為由屬性A劃分成子集的信息熵。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室50/895.5決策樹(shù)當(dāng)選擇A作為測(cè)試屬性時(shí)，導(dǎo)致訓(xùn)練集X的信息熵的壓縮量為H(X,C)-E(A)該壓縮量成為信息增益（informationgain），記為gain(A)gain(A)=H(X,C)-E(A)構(gòu)造決策樹(shù)時(shí)，選擇當(dāng)前具有最大信息增益的屬性作為當(dāng)前節(jié)點(diǎn)的測(cè)試屬性，這使得X的信息熵下降最快，構(gòu)造的決策樹(shù)高度也相對(duì)較低。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室51/895.5決策樹(shù)示例：

（1）創(chuàng)建根節(jié)點(diǎn)

先計(jì)算gain(color)。inflated為類標(biāo)號(hào)屬性，對(duì)X的劃分為C={[T],[F]}={{1,2,3,4,5,7,8,10},{3,6,9}}={C1,C2}

其中

C1={1,2,3,4,5,7,8,10}=[T]C2={3,6,9}=[F]2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室52/895.5決策樹(shù)

H(X,C)=-p(C1)logp(C1)-p(C2)logp(C2)

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室53/895.5決策樹(shù)屬性color對(duì)X形成的劃分為{{1,2,3,4,5,6},{7,8,9,10}}={[YELLOW],[PURPLE]}其中

[YELLOW]={1,2,3,4,5,6},[PURPLE]={7,8,9,10}與是

=[YELLOW]∩C1={1,2,3,4,5,6}∩{1,2,4,5,7,8,10}={1,2,4,5}=[YELLOW]∩C2={1,2,3,4,5,6}∩{3,6,9}={3,6}2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室54/895.5決策樹(shù)=[PURPLE]∩C1={7,8,9,10}∩{1,2,4,5,7,8,10}={7,8,10}=[PURPLE]∩C2={7,8,9,10}∩{3,6,9}={9}2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室55/895.5決策樹(shù)

這樣

gain(color)=H(X,C)-E(color)=0.88-0.88=0同樣的方法，可得

gain(size)=0gain(act)=0.88gain(age)=0.28act具有最高信息增益，選為根節(jié)點(diǎn)。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室56/895.5決策樹(shù)IDcolorsizeageinflated1YELLOWSMALLADULTT2YELLOWSMALLCHILDT4YELLOWLARGEADULTT7PURPLESMALLCHILDT10PURPLELARGECHILDT

actDIPSTRETCHIDcolorsizeageinflated3YELLOWSMALLCHILDF5YELLOWLARGEADULTT6YELLOWLARGECHILDF8PURPLESMALLADULTT9PURPLESMALLCHILDF2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室57/895.5決策樹(shù)（2）創(chuàng)建子節(jié)點(diǎn)

左邊的表類標(biāo)號(hào)屬性均為T，故創(chuàng)建葉節(jié)點(diǎn)。

右邊的表，作為新數(shù)據(jù)集，依據(jù)步驟（1），計(jì)算信息增益，選擇測(cè)試屬性，構(gòu)造內(nèi)節(jié)點(diǎn)，直到得到一顆完整的決策樹(shù)。actTageFTDIPSTRECHADULTCHILD2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室58/895.5決策樹(shù)

決策樹(shù)剪枝

噪聲數(shù)據(jù)和獨(dú)立（異常)點(diǎn)造成產(chǎn)生的分枝異常，過(guò)少的實(shí)例失去了統(tǒng)計(jì)意義，分枝不具代表性。

剪枝：減少異常分枝出現(xiàn)。

先剪枝技術(shù)：提前終止決策樹(shù)的“生長(zhǎng)”

后剪枝技術(shù)：對(duì)創(chuàng)建完畢的決策樹(shù)進(jìn)行剪枝，剪去“畸形發(fā)展”的分枝。

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室59/895.5決策樹(shù)

從決策樹(shù)提取分類規(guī)則

決策樹(shù)：分類規(guī)則集act=STRETCH→inflated=Tact=DIP∧age=CHILD→inflated=Fact=DIP∧age=ADULT→inflated=T2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室60/895.5決策樹(shù)

決策樹(shù)學(xué)習(xí)的問(wèn)題過(guò)度擬合（運(yùn)用剪枝技術(shù)）連續(xù)值屬性（連續(xù)值域分割為離散區(qū)間集合）屬性選擇度量（信息增益偏袒具有較多值的屬性）2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室61/895.5決策樹(shù)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室62/895.5決策樹(shù)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室63/895.5決策樹(shù)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室64/895.5決策樹(shù)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室65/895.5決策樹(shù)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室66/89屬性的選擇（174個(gè)）5.5決策樹(shù)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室67/895.5決策樹(shù)在機(jī)器人足球傳球應(yīng)用首先設(shè)定傳球隊(duì)員的位置，隨機(jī)設(shè)置接球和其他隊(duì)員的位置；傳球隊(duì)員確認(rèn)要傳球；其他隊(duì)員進(jìn)行跑位；傳球隊(duì)員根據(jù)決策樹(shù)確定接球隊(duì)員。接球隊(duì)員和其他隊(duì)員（指對(duì)手球員）都采用已經(jīng)訓(xùn)練好的截球動(dòng)作去獲得控球權(quán)。接球隊(duì)員獲得控球權(quán)就認(rèn)為是一次成功的傳球，否則，就認(rèn)為失敗。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室68/895.5決策樹(shù)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室69/89傳球決策樹(shù)的生成：5.5決策樹(shù)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室70/89序號(hào)屬性有否其他選擇餓否價(jià)格餐館類型餐館顧客人數(shù)等待時(shí)間（分鐘）決策：是否等待1是是$$$法式有人0-10是2是是$中餐客滿30~60否3否否$快餐有人0~10是4是是$中餐客滿10~30是5是否$$$法式客滿〉60否6否是$$意大利式有人0~10是7否否$快餐無(wú)人0~10否8否是$$中餐有人0~10是9否否$快餐客滿〉60否10是是$$$意大利式客滿10~30否11是否$中餐無(wú)人0~10否12否是$快餐客滿30~60是練習(xí)5.5決策樹(shù)2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室71/895.6強(qiáng)化學(xué)習(xí)概述

人類通常從與外界環(huán)境的交互中學(xué)習(xí)。所謂強(qiáng)化（reinforcement）學(xué)習(xí)是指從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)，以使系統(tǒng)行為從環(huán)境中獲得的累積獎(jiǎng)勵(lì)值最大。在強(qiáng)化學(xué)習(xí)中，我們?cè)O(shè)計(jì)算法來(lái)把外界環(huán)境轉(zhuǎn)化為最大化獎(jiǎng)勵(lì)量的方式的動(dòng)作。我們并沒(méi)有直接告訴主體要做什么或者要采取哪個(gè)動(dòng)作,而是主體通過(guò)看哪個(gè)動(dòng)作得到了最多的獎(jiǎng)勵(lì)來(lái)自己發(fā)現(xiàn)。主體的動(dòng)作的影響不只是立即得到的獎(jiǎng)勵(lì)，而且還影響接下來(lái)的動(dòng)作和最終的獎(jiǎng)勵(lì)。試錯(cuò)搜索(trial-and-errorsearch)和延期強(qiáng)化(delayedreinforcement)這兩個(gè)特性是強(qiáng)化學(xué)習(xí)中兩個(gè)最重要的特性。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室72/895.6強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)技術(shù)是從控制理論、統(tǒng)計(jì)學(xué)、心理學(xué)等相關(guān)學(xué)科發(fā)展而來(lái)，最早可以追溯到巴甫洛夫的條件反射實(shí)驗(yàn)。但直到上世紀(jì)八十年代末、九十年代初強(qiáng)化學(xué)習(xí)技術(shù)才在人工智能、機(jī)器學(xué)習(xí)和自動(dòng)控制等領(lǐng)域中得到廣泛研究和應(yīng)用，并被認(rèn)為是設(shè)計(jì)智能系統(tǒng)的核心技術(shù)之一。特別是隨著強(qiáng)化學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)研究取得突破性進(jìn)展后，對(duì)強(qiáng)化學(xué)習(xí)的研究和應(yīng)用日益開(kāi)展起來(lái)，成為目前機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)之一。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室73/895.6強(qiáng)化學(xué)習(xí)強(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)物感覺(jué)不舒服的行為，會(huì)減弱與情景的聯(lián)系，此情景再現(xiàn)時(shí)，此行為將很難再現(xiàn)。換個(gè)說(shuō)法，哪種行為會(huì)“記住”，會(huì)與刺激建立聯(lián)系，取決于行為產(chǎn)生的效果。動(dòng)物的試錯(cuò)學(xué)習(xí),包含兩個(gè)含義：選擇（selectional）和聯(lián)系（associative），對(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”，此后開(kāi)始廣泛使用。1969年，Minsky因在人工智能方面的貢獻(xiàn)而獲得計(jì)算機(jī)圖靈獎(jiǎng)。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室74/895.6強(qiáng)化學(xué)習(xí)1953到1957年，Bellman提出了求解最優(yōu)控制問(wèn)題的一個(gè)有效方法：動(dòng)態(tài)規(guī)劃（dynamicprogramming）Bellman于1957年還提出了最優(yōu)控制問(wèn)題的隨機(jī)離散版本，就是著名的馬爾可夫決策過(guò)程（MDP,Markovdecisionprocesse），1960年Howard提出馬爾可夫決策過(guò)程的策略迭代方法，這些都成為現(xiàn)代強(qiáng)化學(xué)習(xí)的理論基礎(chǔ)。1972年，Klopf把試錯(cuò)學(xué)習(xí)和時(shí)序差分結(jié)合在一起。1978年開(kāi)始，Sutton、Barto、Moore，包括Klopf等對(duì)這兩者結(jié)合開(kāi)始進(jìn)行深入研究。1989年Watkins提出了Q-學(xué)習(xí)[Watkins1989]，也把強(qiáng)化學(xué)習(xí)的三條主線扭在了一起。1992年，Tesauro用強(qiáng)化學(xué)習(xí)成功了應(yīng)用到西洋雙陸棋（backgammon）中，稱為TD-Gammon。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室75/895.6強(qiáng)化學(xué)習(xí)

基本模型：Agent環(huán)境狀態(tài)s獎(jiǎng)勵(lì)r動(dòng)作a2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室76/895.6強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)系統(tǒng)接受環(huán)境狀態(tài)的輸入s，根據(jù)內(nèi)部的推理機(jī)制，系統(tǒng)輸出相應(yīng)的行為動(dòng)作a。環(huán)境在系統(tǒng)動(dòng)作作用a下，變遷到新的狀態(tài)s′。系統(tǒng)接受環(huán)境新?tīng)顟B(tài)的輸入，同時(shí)得到環(huán)境對(duì)于系統(tǒng)的瞬時(shí)獎(jiǎng)懲反饋r。對(duì)于強(qiáng)化學(xué)習(xí)系統(tǒng)來(lái)講，其目標(biāo)是學(xué)一個(gè)行為策略π：S→A，使系統(tǒng)選擇的動(dòng)作能夠獲得環(huán)境獎(jiǎng)勵(lì)的累計(jì)值最大。

在學(xué)習(xí)過(guò)程中，強(qiáng)化學(xué)習(xí)技術(shù)的基本原理是：如果系統(tǒng)某個(gè)動(dòng)作導(dǎo)致環(huán)境正的獎(jiǎng)勵(lì)，那么系統(tǒng)以后產(chǎn)生這個(gè)動(dòng)作的趨勢(shì)便會(huì)加強(qiáng)。反之系統(tǒng)產(chǎn)生這個(gè)動(dòng)作的趨勢(shì)便減弱。這和生理學(xué)中的條件反射原理是接近的。2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室77/895.6強(qiáng)化學(xué)習(xí)強(qiáng)化學(xué)習(xí)分類

強(qiáng)化學(xué)習(xí)算法可劃分為兩類：一類算法是先進(jìn)行模型的學(xué)習(xí)，再根據(jù)模型知識(shí)推導(dǎo)最優(yōu)策略，這類算法被稱為模型相關(guān)算法(Model-based)；另一類算法是直接計(jì)算最優(yōu)策略，這類算法被稱為模型無(wú)關(guān)算法(Model-free)。模型相關(guān)的強(qiáng)化學(xué)習(xí)算法包括時(shí)序差分算法(TD)、Sarsa算法和Dyna算法等。模型無(wú)關(guān)的強(qiáng)化學(xué)習(xí)算法包括蒙特卡羅算法(MonteCarlo)、Q學(xué)習(xí)算法和R學(xué)習(xí)算法等。

2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室78/895.6強(qiáng)化學(xué)習(xí)ReinforcementLearning–Learnfrominteractionlearnfromitsownexperience,andtheobjectiveistogetasmuchrewardaspossible.Thelearnerisnottoldwhichactionstotake,butinsteadmustdiscoverwhichactionsyieldthemostrewardbytryingthem.RLSystemInputsOutputs(“actions”)TrainingInfo=evaluations(“rewards”/“penalties”)與監(jiān)督學(xué)習(xí)對(duì)比SupervisedLearning–Learnfromexamplesprovidedbyaknowledgableexternalsupervisor.2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室79/895.6強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)的應(yīng)用

（1）

在游戲比賽中應(yīng)用Samuel在跳棋游戲中應(yīng)用了時(shí)序差分的思想。

（2）在控制系統(tǒng)中應(yīng)用

倒立擺控制過(guò)程控制2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室80/895.6強(qiáng)化學(xué)習(xí)

（3）

在機(jī)器人中應(yīng)用機(jī)器人導(dǎo)航系統(tǒng)

機(jī)器人協(xié)調(diào)動(dòng)作

機(jī)器人路徑規(guī)劃

機(jī)器人足球比賽中的2vs.1問(wèn)題2023/4/3合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室81/895.7

集體學(xué)習(xí)—Boosting方法歸納學(xué)習(xí)通常是從假設(shè)空間中選出一個(gè)假設(shè)對(duì)新實(shí)例進(jìn)行分類預(yù)測(cè)集體學(xué)習(xí)是從假設(shè)空間中選擇一個(gè)作為整體的假設(shè)集合稱為集體，將它們對(duì)新實(shí)例的分類預(yù)測(cè)進(jìn)行合成，然后再輸出結(jié)果動(dòng)機(jī)—多個(gè)分類器出錯(cuò)的概率總會(huì)比