人工智能第6章機(jī)器學(xué)習(xí)課件

1、人工智能第六章 機(jī)器學(xué)習(xí)第1頁(yè)，共85頁(yè)。第6章機(jī)器學(xué)習(xí)6.1 機(jī)器學(xué)習(xí)概述6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）6.3 決策樹(shù)學(xué)習(xí)6.4 基于實(shí)例的學(xué)習(xí)6.5 強(qiáng)化學(xué)習(xí)6.6 小結(jié)第2頁(yè)，共85頁(yè)。 6.1.1 機(jī)器學(xué)習(xí)的概念心理學(xué)中對(duì)學(xué)習(xí)的解釋是：學(xué)習(xí)是指（人或動(dòng)物）依靠經(jīng)驗(yàn)的獲得而使行為持久變化的過(guò)程。Simon認(rèn)為：如果一個(gè)系統(tǒng)能夠通過(guò)執(zhí)行某種過(guò)程而改進(jìn)它的性能，這就是學(xué)習(xí)。Minsky認(rèn)為：學(xué)習(xí)是在人們頭腦中（心理內(nèi)部）進(jìn)行有用的變化。Tom M. Mitchell在機(jī)器學(xué)習(xí)一書(shū)中對(duì)學(xué)習(xí)的定義是：對(duì)于某類任務(wù)T和性能度P，如果一個(gè)計(jì)算機(jī)程序在T上以P衡量的性能隨著經(jīng)驗(yàn)E而自我完善

2、，那么，我們稱這個(gè)計(jì)算機(jī)程序從經(jīng)驗(yàn)E中學(xué)習(xí)。當(dāng)前關(guān)于機(jī)器學(xué)習(xí)的許多文獻(xiàn)中也大都認(rèn)為：學(xué)習(xí)是一個(gè)有特定目的的知識(shí)獲取和能力增長(zhǎng)過(guò)程，其內(nèi)在行為是獲得知識(shí)、積累經(jīng)驗(yàn)、發(fā)現(xiàn)規(guī)律等，其外部表現(xiàn)是改進(jìn)性能、適應(yīng)環(huán)境、實(shí)現(xiàn)自我完善等。6.1 機(jī)器學(xué)習(xí)概述第3頁(yè)，共85頁(yè)。一個(gè)學(xué)習(xí)系統(tǒng)應(yīng)具有以下特點(diǎn)：1.具有適當(dāng)?shù)膶W(xué)習(xí)環(huán)境 學(xué)習(xí)系統(tǒng)中環(huán)境并非指通常的物理?xiàng)l件，而是指學(xué)習(xí)系統(tǒng)進(jìn)行學(xué)習(xí)時(shí)所必需的信息來(lái)源。2.具有一定的學(xué)習(xí)能力 一個(gè)好的學(xué)習(xí)方法和一定的學(xué)習(xí)能力是取得理想的學(xué)習(xí)效果的重要手段。所以，學(xué)習(xí)系統(tǒng)應(yīng)模擬人的學(xué)習(xí)過(guò)程，使系統(tǒng)通過(guò)與環(huán)境反復(fù)多次相互作用，逐步學(xué)到有關(guān)知識(shí)，并且要使系統(tǒng)在學(xué)習(xí)過(guò)程中通過(guò)實(shí)踐驗(yàn)證

3、、評(píng)價(jià)所學(xué)知識(shí)的正確性。6.1 機(jī)器學(xué)習(xí)概述第4頁(yè)，共85頁(yè)。3.能用所學(xué)的知識(shí)解決問(wèn)題 學(xué)習(xí)的目的在于應(yīng)用，學(xué)習(xí)系統(tǒng)能把學(xué)到的信息用于對(duì)未來(lái)的估計(jì)、分類、決策和控制。4.能提高系統(tǒng)的性能 提高系統(tǒng)的性能是學(xué)習(xí)系統(tǒng)最終目標(biāo)。通過(guò)學(xué)習(xí)，系統(tǒng)隨之增長(zhǎng)知識(shí)，提高解決問(wèn)題的能力，使之能完成原來(lái)不能完成的任務(wù)，或者比原來(lái)做得更好。 6.1 機(jī)器學(xué)習(xí)概述第5頁(yè)，共85頁(yè)。 由此看來(lái): 學(xué)習(xí)系統(tǒng)至少應(yīng)有環(huán)境、知識(shí)庫(kù)、學(xué)習(xí)環(huán)節(jié)和執(zhí)行環(huán)節(jié)四個(gè)基本部分。一種典型的學(xué)習(xí)系統(tǒng)（迪特里奇（Dietterich）學(xué)習(xí)模型）如下圖所示。環(huán)境向系統(tǒng)的學(xué)習(xí)部件提供某些信息，學(xué)習(xí)環(huán)節(jié)利用這些信息修改知識(shí)庫(kù)，增進(jìn)執(zhí)行部件的效能；執(zhí)

4、行環(huán)節(jié)根據(jù)知識(shí)庫(kù)完成任務(wù)，同時(shí)把獲得的信息反饋給學(xué)習(xí)部件。環(huán)境學(xué)習(xí)單元知識(shí)庫(kù)執(zhí)行單元簡(jiǎn)單的學(xué)習(xí)模型6.1 機(jī)器學(xué)習(xí)概述第6頁(yè)，共85頁(yè)。1神經(jīng)元模型研究階段 這個(gè)時(shí)期主要技術(shù)是神經(jīng)元模型以及基于該模型的決策論和控制論;機(jī)器學(xué)習(xí)方法通過(guò)監(jiān)督（有教師指導(dǎo)的）學(xué)習(xí)來(lái)實(shí)現(xiàn)神經(jīng)元間連接權(quán)的自適應(yīng)調(diào)整，產(chǎn)生線性的模式分類和聯(lián)想記憶能力。 具有代表性的工作有FRosenblaft的感知機(jī)（1958年）；NRashevsky數(shù)學(xué)生物物理學(xué)（1948年）；WSMcCullouch與WPitts的模擬神經(jīng)元的理論（1943年）;RMFriedberg對(duì)生物進(jìn)化過(guò)程的研究6.1.2 機(jī)器學(xué)習(xí)的發(fā)展簡(jiǎn)史6.1 機(jī)器學(xué)

5、習(xí)概述第7頁(yè)，共85頁(yè)。2符號(hào)概念獲取研究階段 60年代初期，機(jī)器學(xué)習(xí)的研究進(jìn)入了第二階段，在這個(gè)階段，心理學(xué)和人類學(xué)習(xí)的模擬占有主導(dǎo)地位，其特點(diǎn)是使用符號(hào)而不是數(shù)值表示來(lái)研究學(xué)習(xí)問(wèn)題，其目標(biāo)是用學(xué)習(xí)來(lái)表達(dá)高級(jí)知識(shí)的符號(hào)描述。在這一觀點(diǎn)的影響下，主要技術(shù)是概念獲取和各種模式識(shí)別系統(tǒng)的應(yīng)用；研究人員一方面深入探討學(xué)習(xí)的簡(jiǎn)單概念，另一方面則把大量的領(lǐng)域知識(shí)并入學(xué)習(xí)系統(tǒng)，以便它們發(fā)現(xiàn)高深的概念。 這個(gè)階段代表性的工作是溫斯頓（P.H. Winston，1975）的基于示例歸納的結(jié)構(gòu)化概念學(xué)習(xí)系統(tǒng)。6.1 機(jī)器學(xué)習(xí)概述第8頁(yè)，共85頁(yè)。3基于知識(shí)的各種學(xué)習(xí)系統(tǒng)研究階段 機(jī)器學(xué)習(xí)發(fā)展的第三個(gè)階段始于70

6、年代中期，這個(gè)階段不再局限于構(gòu)造概念學(xué)習(xí)系統(tǒng)和獲取上下文知識(shí)，結(jié)合了問(wèn)題求解中的學(xué)習(xí)、概念聚類、類比推理及機(jī)器發(fā)現(xiàn)的工作。 相應(yīng)的有關(guān)學(xué)習(xí)方法相繼推出，比如示例學(xué)習(xí)、示教學(xué)習(xí)、 觀察和發(fā)現(xiàn)學(xué)習(xí)、類比學(xué)習(xí)、基于解釋的學(xué)習(xí)。工作特點(diǎn)強(qiáng)調(diào)應(yīng)用面向任務(wù)的知識(shí)和指導(dǎo)學(xué)習(xí)過(guò)程的約束，應(yīng)用啟發(fā)式知識(shí)于學(xué)習(xí)任務(wù)的生成和選擇，包括提出收集數(shù)據(jù)的方式、選擇要獲取的概念、控制系統(tǒng)的注意力等。6.1 機(jī)器學(xué)習(xí)概述第9頁(yè)，共85頁(yè)。4聯(lián)結(jié)學(xué)習(xí)和符號(hào)學(xué)習(xí)共同發(fā)展階段 80年代后期以來(lái)，形成了聯(lián)結(jié)學(xué)習(xí)和符號(hào)學(xué)習(xí)共同發(fā)展的局的第四個(gè)階段。在這個(gè)時(shí)期，發(fā)現(xiàn)了用隱單元來(lái)計(jì)算和學(xué)習(xí)非線性函數(shù)的方法，從而克服了早期神經(jīng)元模型的局限性

7、，同時(shí)，由于計(jì)算機(jī)硬件的迅速發(fā)展，使得神經(jīng)網(wǎng)絡(luò)的物理實(shí)現(xiàn)變成可能，在聲音識(shí)別、圖像處理等領(lǐng)域，神經(jīng)網(wǎng)絡(luò)取得了很大的成功。 在這個(gè)進(jìn)期，符號(hào)學(xué)習(xí)伴隨人工智能的進(jìn)展也日益成熟，應(yīng)用領(lǐng)域不斷擴(kuò)大，最杰出的工作有分析學(xué)習(xí)（特別是解釋學(xué)習(xí)）、遺傳算法、決策樹(shù)歸納等?，F(xiàn)在基于計(jì)算機(jī)網(wǎng)絡(luò)的各種自適應(yīng)、具有學(xué)習(xí)功能的軟件系統(tǒng)的研制和開(kāi)發(fā),將機(jī)器學(xué)習(xí)的研究推向新的高度。6.1 機(jī)器學(xué)習(xí)概述第10頁(yè)，共85頁(yè)。1. 基于學(xué)習(xí)策略的分類 （1）模擬人腦的機(jī)器學(xué)習(xí)符號(hào)學(xué)習(xí)：模擬人腦的宏觀心理級(jí)學(xué)習(xí)過(guò)程，以認(rèn)知心理學(xué)原理為基礎(chǔ)，以符號(hào)數(shù)據(jù)為輸入，以符號(hào)運(yùn)算為方法，用推理過(guò)程在圖或狀態(tài)空間中搜索，學(xué)習(xí)的目標(biāo)為概念或規(guī)則等

8、。符號(hào)學(xué)習(xí)的典型方法有：記憶學(xué)習(xí)、示例學(xué)習(xí)、演繹學(xué)習(xí)、類比學(xué)習(xí)、解釋學(xué)習(xí)等。神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)（或連接學(xué)習(xí)）：模擬人腦的微觀生理級(jí)學(xué)習(xí)過(guò)程，以腦和神經(jīng)科學(xué)原理為基礎(chǔ)，以人工神經(jīng)網(wǎng)絡(luò)為函數(shù)結(jié)構(gòu)模型，以數(shù)值數(shù)據(jù)為輸入，以數(shù)值運(yùn)算為方法，用迭代過(guò)程在系數(shù)向量空間中搜索，學(xué)習(xí)的目標(biāo)為函數(shù)。典型的連接學(xué)習(xí)有權(quán)值修正學(xué)習(xí)、拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)。 （2）直接采用數(shù)學(xué)方法的機(jī)器學(xué)習(xí) 主要有統(tǒng)計(jì)機(jī)器學(xué)習(xí)。6.1.3 機(jī)器學(xué)習(xí)的分類6.1 機(jī)器學(xué)習(xí)概述第11頁(yè)，共85頁(yè)。2. 基于推理策略的分類 （1）歸納學(xué)習(xí) 符號(hào)歸納學(xué)習(xí)：典型的符號(hào)歸納學(xué)習(xí)有示例學(xué)習(xí)，決策樹(shù)學(xué)習(xí)。 函數(shù)歸納學(xué)習(xí)（發(fā)現(xiàn)學(xué)習(xí)）：典型的函數(shù)歸納學(xué)習(xí)有神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)

9、、示例學(xué)習(xí)，發(fā)現(xiàn)學(xué)習(xí)，統(tǒng)計(jì)學(xué)習(xí)。 （2）演繹學(xué)習(xí) （3）類比學(xué)習(xí)：典型的類比學(xué)習(xí)有案例（范例）學(xué)習(xí)。 （4）分析學(xué)習(xí)：典型的分析學(xué)習(xí)有案例（范例）學(xué)習(xí)、解釋學(xué)習(xí)。6.1 機(jī)器學(xué)習(xí)概述第12頁(yè)，共85頁(yè)。3. 基于學(xué)習(xí)方式的分類（1）有導(dǎo)師學(xué)習(xí)（監(jiān)督學(xué)習(xí)）：輸入數(shù)據(jù)中有導(dǎo)師信號(hào)，以概率函數(shù)、代數(shù)函數(shù)或人工神經(jīng)網(wǎng)絡(luò)為基函數(shù)模型，采用迭代計(jì)算方法，學(xué)習(xí)結(jié)果為函數(shù)。（2）無(wú)導(dǎo)師學(xué)習(xí)（非監(jiān)督學(xué)習(xí)）：輸入數(shù)據(jù)中無(wú)導(dǎo)師信號(hào)，采用聚類方法，學(xué)習(xí)結(jié)果為類別。典型的無(wú)導(dǎo)師學(xué)習(xí)有發(fā)現(xiàn)學(xué)習(xí)、聚類、競(jìng)爭(zhēng)學(xué)習(xí)等。（3）強(qiáng)化學(xué)習(xí)（增強(qiáng)學(xué)習(xí)）：以環(huán)境反饋（獎(jiǎng)/懲信號(hào)）作為輸入，以統(tǒng)計(jì)和動(dòng)態(tài)規(guī)劃技術(shù)為指導(dǎo)的一種學(xué)習(xí)方法。6.1

10、 機(jī)器學(xué)習(xí)概述第13頁(yè)，共85頁(yè)。4. 基于數(shù)據(jù)形式的分類（1）結(jié)構(gòu)化學(xué)習(xí)：以結(jié)構(gòu)化數(shù)據(jù)為輸入，以數(shù)值計(jì)算或符號(hào)推演為方法。典型的結(jié)構(gòu)化學(xué)習(xí)有神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)、統(tǒng)計(jì)學(xué)習(xí)、決策樹(shù)學(xué)習(xí)、規(guī)則學(xué)習(xí)。（2）非結(jié)構(gòu)化學(xué)習(xí)：以非結(jié)構(gòu)化數(shù)據(jù)為輸入，典型的非結(jié)構(gòu)化學(xué)習(xí)有類比學(xué)習(xí)、案例學(xué)習(xí)、解釋學(xué)習(xí)、文本挖掘、圖像挖掘、Web挖掘等。6.1 機(jī)器學(xué)習(xí)概述第14頁(yè)，共85頁(yè)。 5. 基于學(xué)習(xí)目標(biāo)的分類 （1）概念學(xué)習(xí)：即學(xué)習(xí)的目標(biāo)和結(jié)果為概念，或者說(shuō)是為了獲得概念的一種學(xué)習(xí)。典型的概念學(xué)習(xí)有示例學(xué)習(xí)。 （2）規(guī)則學(xué)習(xí)：即學(xué)習(xí)的目標(biāo)和結(jié)果為規(guī)則，或者說(shuō)是為了獲得規(guī)則的一種學(xué)習(xí)。典型的規(guī)則學(xué)習(xí)有決策樹(shù)學(xué)習(xí)。 （3）函數(shù)學(xué)

11、習(xí)：即學(xué)習(xí)的目標(biāo)和結(jié)果為規(guī)則，或者說(shuō)是為了獲得函數(shù)的一種學(xué)習(xí)。典型的函數(shù)學(xué)習(xí)有神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)。 （4）類別學(xué)習(xí)：即學(xué)習(xí)的目標(biāo)和結(jié)果為對(duì)象類，或者說(shuō)是為了獲得類別的一種學(xué)習(xí)。典型的類別學(xué)習(xí)有聚類分析。 （5）貝葉斯網(wǎng)絡(luò)學(xué)習(xí)：即學(xué)習(xí)的目標(biāo)和結(jié)果是貝葉斯網(wǎng)絡(luò)，或者說(shuō)是為了獲得貝葉斯網(wǎng)絡(luò)的一種學(xué)習(xí)。其又可分為結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)。6.1 機(jī)器學(xué)習(xí)概述第15頁(yè)，共85頁(yè)。 機(jī)器學(xué)習(xí)的應(yīng)用非常廣泛，利用這門(mén)技術(shù)，計(jì)算機(jī)已經(jīng)能夠成功地識(shí)別人類的講話(Waibel 1989, Lee 1989)，在高速公路上自動(dòng)駕駛汽車(Pomerleau 1989)，學(xué)習(xí)分類新的天文結(jié)構(gòu)(Fayyad et al. 1995)

12、，以接近人類世界冠軍的水平對(duì)弈西洋雙陸棋（Tesauro 1992,1995）6.1.4 機(jī)器學(xué)習(xí)的應(yīng)用與研究目標(biāo)：6.1 機(jī)器學(xué)習(xí)概述第16頁(yè)，共85頁(yè)。研究目標(biāo)有三個(gè)： (1)人類學(xué)習(xí)過(guò)程的認(rèn)知模型。研究人類學(xué)習(xí)機(jī)理的認(rèn)知模型，這種研究對(duì)人類的教育，以及對(duì)開(kāi)發(fā)機(jī)器學(xué)習(xí)系統(tǒng)都有重要的意義。(2)通用學(xué)習(xí)算法。通過(guò)對(duì)人類學(xué)習(xí)過(guò)程的研究，探索各種可能的學(xué)習(xí)方法，建立起具體應(yīng)用領(lǐng)域的通用學(xué)習(xí)算法。(3)構(gòu)造面向任務(wù)的專用學(xué)習(xí)系統(tǒng)。研究智能系統(tǒng)的建造，解決專門(mén)的實(shí)際問(wèn)題，并開(kāi)發(fā)完成這些專門(mén)任務(wù)的學(xué)習(xí)系統(tǒng)。6.1 機(jī)器學(xué)習(xí)概述第17頁(yè)，共85頁(yè)。 歸納學(xué)習(xí)(概念學(xué)習(xí)、經(jīng)驗(yàn)學(xué)習(xí)）是符號(hào)學(xué)習(xí)中研究的最為廣

13、泛的一種方法。給定關(guān)于某個(gè)概念的一系列已知的正例與反例，其任務(wù)是從中歸納出一個(gè)一般的概念描述。歸納學(xué)習(xí)能夠獲得新的概念，創(chuàng)立新的規(guī)則，發(fā)現(xiàn)新的理論。它的一般操作是泛化(Generalization)和特化(Specialization)。泛化用來(lái)擴(kuò)展一假設(shè)的語(yǔ)義信息，以使其能夠包含更多的正例，應(yīng)用于更多的情況。特化是泛化的相反的操作，用于限制概念描述的應(yīng)用范圍。 6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第18頁(yè)，共85頁(yè)。6.2.1 歸納學(xué)習(xí)的基本概念歸納學(xué)習(xí)指在從大量的經(jīng)驗(yàn)數(shù)據(jù)中歸納抽取出一般的判定規(guī)則和模式，是從特殊情況推導(dǎo)出一般規(guī)則的學(xué)習(xí)方法。歸納學(xué)習(xí)的目標(biāo)是形成合理的能解釋已知事實(shí)和

14、預(yù)見(jiàn)新事實(shí)的一般性結(jié)論。歸納學(xué)習(xí)由于依賴于經(jīng)驗(yàn)數(shù)據(jù)，因此又稱為經(jīng)驗(yàn)學(xué)習(xí)(Empirical Learning)，由于歸納依賴于數(shù)據(jù)間的相似性，所以也稱為基于相似性的學(xué)習(xí)(Similarity Based Learning)。6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第19頁(yè)，共85頁(yè)。歸納學(xué)習(xí)的雙空間模型如圖所示。1.歸納學(xué)習(xí)的雙空間模型6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第20頁(yè)，共85頁(yè)。 首先由施教者給實(shí)例空間提供一些初始示教例子，由于示教例子在形式上往往和規(guī)則形式不同，因此需要對(duì)這些例子進(jìn)行轉(zhuǎn)換，解釋為規(guī)則空間接受的形式。然后利用解釋后的例子搜索規(guī)則空間，由于一般情況下不能一次就

15、從規(guī)則空間中搜索到要求的規(guī)則，因此還要尋找一些新的示教例子，這個(gè)過(guò)程就是選擇例子。程序會(huì)選擇對(duì)搜索規(guī)則空間最有用的例子，對(duì)這些示教例子重復(fù)上述循環(huán)。如此循環(huán)多次，直到找到所要求的例子。執(zhí)行過(guò)程描述6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第21頁(yè)，共85頁(yè)。歸納學(xué)習(xí)方法可以劃分為單概念學(xué)習(xí)和多概念學(xué)習(xí)兩類。這里，概念指用某種描述語(yǔ)言表示的謂詞，當(dāng)應(yīng)用于概念的正實(shí)例時(shí)，謂詞為真，應(yīng)用于負(fù)實(shí)例時(shí)為假。從而概念謂詞將實(shí)例空間劃分為正、反兩個(gè)子集。對(duì)于單概念學(xué)習(xí)，學(xué)習(xí)的目的是從概念空間（即規(guī)則空間）中尋找某個(gè)與實(shí)例空間一致的概念；對(duì)于多概念學(xué)習(xí)任務(wù)，是從概念空間中找出若干概念描述，對(duì)于每個(gè)概念描述，實(shí)

16、例空間中均有相應(yīng)的空間與之對(duì)應(yīng)。2.歸納學(xué)習(xí)方法的分類6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第22頁(yè)，共85頁(yè)。典型的單概念學(xué)習(xí)系統(tǒng)包括米切爾(Tom Mitchell)的基于數(shù)據(jù)驅(qū)動(dòng)的變型空間法，昆蘭(J.R. Quinlan)的ID3方法，狄特利希(T.G. Dietterich)和米哈爾斯基(R.S. Michalski)提出的基于模型驅(qū)動(dòng)的Induce算法。典型的多概念學(xué)習(xí)方法和系統(tǒng)有米哈爾斯基的AQ11、DENDRAL和AM程序等。多概念學(xué)習(xí)任務(wù)可以劃分成多個(gè)單概念學(xué)習(xí)任務(wù)來(lái)完成。多概念學(xué)習(xí)與單概念學(xué)習(xí)的差別在于多概念學(xué)習(xí)方法必須解決概念之間的沖突問(wèn)題。2.歸納學(xué)習(xí)方法的分類6.

17、2 歸納學(xué)習(xí)（變型空間和候選消除算法）第23頁(yè)，共85頁(yè)。變型空間學(xué)習(xí)方法(Learning by Version Space)，也稱為變型空間學(xué)習(xí)法。變型空間法是TMMitchell于1977年提出的一種數(shù)據(jù)驅(qū)動(dòng)型的學(xué)習(xí)方法。該方法以整個(gè)規(guī)則空間為初始的假設(shè)規(guī)則集合H。依據(jù)示教例子中的信息，系統(tǒng)對(duì)集合H進(jìn)行一般化或特殊化處理，逐步縮小集合H。最后使得H收斂到只含有要求的規(guī)則。由于被搜索的空間H逐漸縮小，故稱為變型空間法。6.2.2 變型空間學(xué)習(xí)6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第24頁(yè)，共85頁(yè)。在變型空間中，表示規(guī)則的點(diǎn)與點(diǎn)之間存在著一種由一般到特殊的偏序關(guān)系。我們定義為覆蓋，例如

18、，color(X,Y)覆蓋color(ball,Z)，于是又覆蓋color(ball,red)。(more general than)作為一個(gè)簡(jiǎn)單的例子，考慮有這樣一些屬性和值的對(duì)象域： Sizes=large,small Colors=red,white,blue Shapes=ball,brick,cube這些對(duì)象可以用謂詞obj(Sizes,Color,Shapes)來(lái)表示。用變量替換常量這個(gè)泛化操作定義 1變型空間的結(jié)構(gòu)6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第25頁(yè)，共85頁(yè)。 假設(shè)空間H由兩個(gè)子集G和S所限定，子集G中的元素表示H中的最一般的概念，子集S中的元素表示H中的最特殊的

19、概念，假設(shè)空間H的確切組成是：G中包含的假設(shè)，S中包含的假設(shè)以及G和S之間偏序結(jié)構(gòu)所規(guī)定的假設(shè)。即： H=GSk|GKS 式中“”表示變型空間中的偏序關(guān)系。 示例: Colors=red, ,blue Shapes=ball, cube這些對(duì)象可以用謂詞obj(Colors, Shapes)來(lái)表示。6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第26頁(yè)，共85頁(yè)。G:S:(x, y)(red, y)(blue, y)(x, ball)(x, cube)(blue, cube)(blue, ball)(red, cube)(red, ball)6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第27頁(yè)，共8

20、5頁(yè)。GSH沒(méi)有描述一般示教例子特殊6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第28頁(yè)，共85頁(yè)。算法6.1 候選項(xiàng)刪除算法（1）把H初始化為整個(gè)規(guī)則空間。這時(shí)G僅包含空描述。S包含所有最特殊的概念。實(shí)際上，為避免S集合過(guò)大，算法把S初化為僅包含第一個(gè)示教正例。（2）接受一個(gè)新的示教例子。如果這個(gè)例子是正例，則從G中刪除不包含新例的概念，然后修改S為由新正例和S原有元素同歸納出最特殊化的泛化。這個(gè)過(guò)程稱為對(duì)集合S的修改過(guò)程。如果這個(gè)例子是反例，則從S中刪去包含新例的概念，再對(duì)G作盡量小的特殊化，使之不包含新例。這個(gè)過(guò)程稱為集合G的修改過(guò)程。（3）重復(fù)步驟，直到G=S，且使這兩個(gè)集合都只含有一個(gè)

21、元素為止。（4）輸出H中的概念（即輸出G或S）。6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第29頁(yè)，共85頁(yè)。（sm squ）（sm cir）（lg squ）（lg cir）（sm tri）（sm y）（lg y）（x squ）（x cir）（x tri）（x y）（lg tri）示例：G0=（x，y ）S0=（sm squ）,（sm cir）,（sm tri）,（lg squ）,（lg cir）,（lg tri）G1=（x y）S1=（sm cir）G2=（x cir），（x squ），（sm y）S2=（sm cir）G3=（x cir）S3=（x cir）6.2 歸納學(xué)習(xí)（變型空間和候選

22、消除算法）第30頁(yè)，共85頁(yè)。6.2.3 歸納偏置 候選消除算法的說(shuō)明候選消除算法收斂到正確的假設(shè)訓(xùn)練樣例中沒(méi)有錯(cuò)誤H中確實(shí)包含描述目標(biāo)概念的正確假設(shè)如果樣例中存在錯(cuò)誤如果給定足夠的訓(xùn)練數(shù)據(jù)，我們會(huì)發(fā)現(xiàn)S和G邊界收斂得到一個(gè)空的變型空間如果目標(biāo)概念不能由假設(shè)表示方式所描述相似情況出現(xiàn)6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第31頁(yè)，共85頁(yè)。歸納偏置: 指學(xué)習(xí)程序用來(lái)限制概念空間或者在這 個(gè)空間中選擇概念的任何標(biāo)準(zhǔn)。 歸納偏置的強(qiáng)化 : (1) 經(jīng)過(guò)啟發(fā)式，推薦新概念描述加到概念描述語(yǔ)言，以確定一個(gè)更好的偏置。 （2）變換推薦的描述成為概念描述語(yǔ)言中已形式化表示的新概念描述，同化任何新概念進(jìn)

23、入假設(shè)的限定空間，保持假設(shè)空間機(jī)制，使得新概念描述語(yǔ)言較前面的語(yǔ)言更好。6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第32頁(yè)，共85頁(yè)。 學(xué)習(xí)正例時(shí)，對(duì)S進(jìn)行泛化，這往往擴(kuò)大S。學(xué)習(xí)反例時(shí)，對(duì)G進(jìn)行特化，這往往擴(kuò)大G。G和S的規(guī)模過(guò)大會(huì)給算法的實(shí)用造成困難。算法是在訓(xùn)練例子引導(dǎo)下，對(duì)規(guī)則空間進(jìn)行寬度優(yōu)先搜索。對(duì)大的規(guī)則空間，算法慢得無(wú)法接受。主要缺點(diǎn)6.2 歸納學(xué)習(xí)（變型空間和候選消除算法）第33頁(yè)，共85頁(yè)。 決策樹(shù)學(xué)習(xí)是離散函數(shù)的一種樹(shù)型表示，表示能力強(qiáng)，可以表示任意的離散函數(shù)，是一種重要的歸納學(xué)習(xí)方法。決策樹(shù)是實(shí)現(xiàn)分治策略的數(shù)據(jù)結(jié)構(gòu)，通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例，可用于分

24、類和回歸。決策樹(shù)代表實(shí)例屬性值約束的合取的析取式，從樹(shù)根到樹(shù)葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹(shù)本身對(duì)應(yīng)這些合取的析取。 6.3 決策樹(shù)學(xué)習(xí)第34頁(yè)，共85頁(yè)。6.3.1 決策樹(shù)的組成及分類1決策樹(shù)的組成決策樹(shù)由一些決策節(jié)點(diǎn)和終端樹(shù)葉組成，每個(gè)決策節(jié)點(diǎn)m實(shí)現(xiàn)一個(gè)具有離散輸出的測(cè)試函數(shù)fm(x)標(biāo)記分支。給定一個(gè)輸入，在每個(gè)節(jié)點(diǎn)應(yīng)用一個(gè)測(cè)試，并根據(jù)測(cè)試的輸出確定一個(gè)分支。這一過(guò)程從根節(jié)點(diǎn)開(kāi)始，并遞歸地重復(fù)，直到到達(dá)一個(gè)樹(shù)葉節(jié)點(diǎn)。該樹(shù)葉中的值形成輸出。每個(gè)fm(x)定義了一個(gè)d維輸入空間中的判別式，將空間劃分成較小區(qū)域，在從根節(jié)點(diǎn)沿一條路徑向下時(shí)，這些較小的區(qū)域被進(jìn)一步劃分。每個(gè)樹(shù)葉節(jié)點(diǎn)有一個(gè)

25、輸出標(biāo)號(hào)，對(duì)于分類，該標(biāo)號(hào)是類代碼，對(duì)于回歸，則是一個(gè)數(shù)值。一個(gè)樹(shù)葉節(jié)點(diǎn)定義了輸入空間的一個(gè)局部區(qū)域，落入該區(qū)域的實(shí)例具有相同的輸出。依據(jù)每個(gè)節(jié)點(diǎn)所測(cè)試的屬性的個(gè)數(shù)，決策樹(shù)可分為單變量樹(shù)和多變量樹(shù)。6.3 決策樹(shù)學(xué)習(xí)第35頁(yè)，共85頁(yè)。2單變量樹(shù) 在單變量樹(shù)中，每個(gè)節(jié)點(diǎn)的測(cè)試值使用一個(gè)輸入維，也就是只測(cè)試一個(gè)屬性。w20 x2C1x1w10C2x1w10 x2w20C2C2C1C1YesYesNoNo圖6.6單變量樹(shù)舉例6.3 決策樹(shù)學(xué)習(xí)第36頁(yè)，共85頁(yè)。3多變量樹(shù) 在樹(shù)的各結(jié)點(diǎn)選擇多個(gè)屬性的組合進(jìn)行測(cè)試，一般表現(xiàn)為通過(guò)數(shù)學(xué)或邏輯算子將一些屬性組合起來(lái)，形成新的屬性作為測(cè)試屬性，因而稱這樣形

26、成的決策樹(shù)為多變量決策樹(shù)。 X2C1C2X1w11x1+w12x2+w100YesNoC2C1圖6.7 線性多變量樹(shù)6.3 決策樹(shù)學(xué)習(xí)第37頁(yè)，共85頁(yè)。如果學(xué)習(xí)的任務(wù)是對(duì)一個(gè)大的實(shí)例集做概念分類的歸納定義，而這些例子都是用一些無(wú)結(jié)構(gòu)的“屬性-值”對(duì)來(lái)表示，那么可以采用決策樹(shù)學(xué)習(xí)算法。亨特(Hunt)于1966年研制了一個(gè)概念學(xué)習(xí)系統(tǒng)CLS，可以學(xué)習(xí)單個(gè)概念，并用此學(xué)到的概念分類新的實(shí)例。這是一種早期的基于決策樹(shù)的歸納學(xué)習(xí)系統(tǒng)。 昆蘭(Quinlan)于1983年此進(jìn)行了發(fā)展，研制了ID3算法。該算法不僅能方便地表示概念屬性-值信息的結(jié)構(gòu)，而且能從大量實(shí)例數(shù)據(jù)中有效地生成相應(yīng)的決策樹(shù)模型。6.

27、3.2 決策樹(shù)的構(gòu)造算法CLS6.3 決策樹(shù)學(xué)習(xí)第38頁(yè)，共85頁(yè)。 算法6.2 決策樹(shù)構(gòu)造算法CLS：(1)如果TR中所有實(shí)例分類結(jié)果均為Ci，則返回Ci；(2)從屬性表中選擇某一屬性Ai作為檢測(cè)屬性；(3)不妨假設(shè)|ValueType(Ai)|=k，根據(jù)Ai取值的不同,將TR劃分為k個(gè)訓(xùn)練集TR1，TR2，TRk，其中： TRi=|TR且V(X,A)為屬性A的第i個(gè)值(4)從屬性表中去掉已做檢測(cè)的屬性Ai；(5)對(duì)每一個(gè)i(1ik)，用TRi和新的屬性表遞歸調(diào)用CLS生成子分支決策樹(shù)DTRi；(6)返回以屬性Ai為根，DTR1，DTRk為子樹(shù)的決策樹(shù)。6.3 決策樹(shù)學(xué)習(xí)第39頁(yè)，共85頁(yè)。

28、NoNoNoNoYesNoNo210210alivedead2.52.5No. of WingsBroken WingsStatusArea/weight圖6.8 鳥(niǎo)飛的決策樹(shù) 6.3 決策樹(shù)學(xué)習(xí)第40頁(yè)，共85頁(yè)。6.3.3基本的決策樹(shù)算法ID3ID3的思想自頂向下構(gòu)造決策樹(shù)從“哪一個(gè)屬性將在樹(shù)的根節(jié)點(diǎn)被測(cè)試”開(kāi)始使用統(tǒng)計(jì)測(cè)試來(lái)確定每一個(gè)實(shí)例屬性單獨(dú)分類訓(xùn)練樣例的能力ID3的過(guò)程分類能力最好的屬性被選作樹(shù)的根節(jié)點(diǎn)根節(jié)點(diǎn)的每個(gè)可能值產(chǎn)生一個(gè)分支訓(xùn)練樣例排列到適當(dāng)?shù)姆种е貜?fù)上面的過(guò)程6.3 決策樹(shù)學(xué)習(xí)第41頁(yè)，共85頁(yè)。ID3(Examples, Target_attribute, Attrib

29、utes)創(chuàng)建樹(shù)的root節(jié)點(diǎn)如果Examples都為正,返回label=+的單節(jié)點(diǎn)樹(shù)root如果Examples都為反,返回label=-的單節(jié)點(diǎn)樹(shù)root如果Attributes為空，那么返回單節(jié)點(diǎn)root，label=Examples中最普遍的Target_attribute值否則開(kāi)始AAttributes中分類examples能力最好的屬性root的決策屬性A對(duì)于A的每個(gè)可能值vi在root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個(gè)新分支下加一個(gè)葉子節(jié)點(diǎn)，節(jié)點(diǎn)的label=Examples中最普遍

30、的Target_attribute值否則在新分支下加一個(gè)子樹(shù)ID3（ Examplesvi,Target_attribute,Attributes-A）結(jié)束返回root6.3 決策樹(shù)學(xué)習(xí)第42頁(yè)，共85頁(yè)。ID3算法是一種自頂向下增長(zhǎng)樹(shù)的貪婪算法，在每個(gè)節(jié)點(diǎn)選取能最好地分類樣例的屬性。繼續(xù)這個(gè)過(guò)程直到這棵樹(shù)能完美分類訓(xùn)練樣例，或所有的屬性都已被使用過(guò)。那么，在決策樹(shù)生成過(guò)程當(dāng)中，應(yīng)該以什么樣的順序來(lái)選取實(shí)例集中實(shí)例的屬性進(jìn)行擴(kuò)展呢？即如何選擇具有最高信息增益的屬性為最好的屬性？6.3 決策樹(shù)學(xué)習(xí)第43頁(yè)，共85頁(yè)。為了評(píng)價(jià)屬性的重要性，昆蘭根據(jù)檢驗(yàn)每一屬性所得到的信息量的多少，給出了擴(kuò)展屬性的

31、選取方法，其中信息量的多少和熵有關(guān)。信息論簡(jiǎn)介6.3 決策樹(shù)學(xué)習(xí)第44頁(yè)，共85頁(yè)。ID3算法-最佳分類屬性-信息熵，簡(jiǎn)稱熵(1)自信息量I(a):設(shè)信源X發(fā)出符號(hào)a的概率為p(a),則I(a)定義為: I(a)=-logp(a) (單位:bit) 表示收信者在收到符號(hào)a之前，對(duì)a的不確定性，收到后獲得的關(guān)于a的信息量。(2)信息熵H(X):設(shè)信源X的概率分布為(X,p(x),則H(X)定義為: H(X)=-p(x)logp(x) 表示信源X的整體不確定性，反應(yīng)了信源每發(fā)出一個(gè)符號(hào)所提供的平均信息量。(3)條件熵H(X|Y):設(shè)信源X,Y的聯(lián)合概率分布為p(x,y),則 H(X|Y)定義為:

32、H(X|Y)=- p(x,y)logp(x|y) 表示收信者在收到Y(jié)后對(duì)X的不確定性估計(jì).6.3 決策樹(shù)學(xué)習(xí)第45頁(yè)，共85頁(yè)。設(shè)給定正負(fù)實(shí)例的集合為S,構(gòu)成訓(xùn)練窗口。ID3算法視S為一個(gè)離散信息系統(tǒng)，并用信息熵表示該系統(tǒng)的信息量。當(dāng)決策有k個(gè)不同的輸出時(shí)，S的熵為:其中Pi表示第i類輸出所占訓(xùn)練窗口中總的輸出數(shù)量的比例。ID3算法-最佳分類屬性6.3 決策樹(shù)學(xué)習(xí)第46頁(yè)，共85頁(yè)。為了檢測(cè)每個(gè)屬性的重要性，可以通過(guò)屬性的信息增益Gain來(lái)評(píng)估起重要性。對(duì)于屬性A，假設(shè)其值域?yàn)?v1,v2,vn)，則訓(xùn)練實(shí)例S中屬性A的信息增益Gain可以定義為：式中，Si表示S中屬性A的值為vi的子集；|S

33、i|表示集合的勢(shì)。ID3算法-最佳分類屬性-信息增益6.3 決策樹(shù)學(xué)習(xí)第47頁(yè)，共85頁(yè)。昆蘭建議選取獲得信息量最大的屬性作為擴(kuò)展屬性。這一啟發(fā)式規(guī)則又稱最小熵原理。因?yàn)楂@得信息量最大，即信息增益Gain最大，等價(jià)于使不確定性最小，即使得熵最小，即條件熵H(S|Ai)為最小。因此也可以條件熵H(S|Ai)為最小作為選擇屬性重要性標(biāo)準(zhǔn)。H(S|Ai)越小，說(shuō)明Ai引入的信息最多，系統(tǒng)熵下降的越快。ID3算法是一種貪婪搜索(Greedy Search)算法，即選擇信息量最大的屬性進(jìn)行決策樹(shù)分裂，計(jì)算中表現(xiàn)為使訓(xùn)練例子集的熵下降最快。ID3算法-最佳分類屬性-信息增益6.3 決策樹(shù)學(xué)習(xí)第48頁(yè)，共8

34、5頁(yè)?，F(xiàn)考慮鳥(niǎo)是否能飛的實(shí)例，InstancesNo. of WingsBroken WingsLiving statusarea/weightFly120alive2.5T221alive2.5F322alive2.6F420alive3.0T520dead3.2F600alive0F710alive0F820alive3.4T920alive2.0F6.3 決策樹(shù)學(xué)習(xí)第49頁(yè)，共85頁(yè)。對(duì)于上表給出的例子,選取整個(gè)訓(xùn)練集為訓(xùn)練窗口,有3個(gè)正實(shí)例,6個(gè)負(fù)實(shí)例,采用記號(hào)3+,6-表示總的樣本數(shù)據(jù)。則S的熵為計(jì)算屬性Living Status的信息增益，該屬性為值域?yàn)?alive, dead),

35、則 S=3+,6-, Salive=3+,5-, Sdead=0+,1- 先計(jì)算Entropy(Salive), Entropy(Sdead)如下:ID3算法-最佳分類屬性-例子分析6.3 決策樹(shù)學(xué)習(xí)第50頁(yè)，共85頁(yè)。ID3算法-最佳分類屬性-例子分析所以,living status的信息增益為6.3 決策樹(shù)學(xué)習(xí)第51頁(yè)，共85頁(yè)。ID3算法-最佳分類屬性-例子分析同樣可計(jì)算其他屬性的信息增益，然后根據(jù)最小熵原理，選取信息量最大的屬性作為決策樹(shù)的根節(jié)點(diǎn)屬性。6.3 決策樹(shù)學(xué)習(xí)第52頁(yè)，共85頁(yè)。ID3算法的優(yōu)點(diǎn)：分類和測(cè)試速度快，特別適用于大數(shù)據(jù)庫(kù)的分類問(wèn)題。ID3算法的缺點(diǎn)： 第一：決策樹(shù)

36、的知識(shí)表示沒(méi)有規(guī)則易于理解。 第二：兩顆決策樹(shù)比較是否等價(jià)問(wèn)題是子圖匹配問(wèn)題，是NP完全的。 第三：不能處理未知屬性值的情況。 第四：對(duì)噪聲問(wèn)題沒(méi)有好的處理辦法。ID3算法-最佳分類屬性-優(yōu)缺點(diǎn)6.3 決策樹(shù)學(xué)習(xí)第53頁(yè)，共85頁(yè)。6.3.4 決策樹(shù)的偏置 構(gòu)造好的決策樹(shù)的關(guān)鍵在于選擇好的屬性，屬性選擇依賴于信息增益、信息增益比、Gini-index、距離度量、J-度量、最小描述長(zhǎng)度、正交法度量等等。比如上述的ID3算法優(yōu)先選取信息增益最大的屬性作為擴(kuò)展屬性。 決策樹(shù)還可以通過(guò)剪枝來(lái)尋找最小的樹(shù)。通常，如果到達(dá)一個(gè)節(jié)點(diǎn)的訓(xùn)練實(shí)例數(shù)小于訓(xùn)練集的某個(gè)百分比(如5%)，則無(wú)論是否不純或是否有錯(cuò)誤，該

37、節(jié)點(diǎn)都不進(jìn)一步分裂。因?yàn)榛谶^(guò)少實(shí)例的決策樹(shù)導(dǎo)致較大方差，從而導(dǎo)致較大泛化誤差。在樹(shù)完全構(gòu)造出來(lái)之前提前停止樹(shù)構(gòu)造稱作樹(shù)的先剪枝。6.3 決策樹(shù)學(xué)習(xí)第54頁(yè)，共85頁(yè)。6.3.4 決策樹(shù)的偏置 得到較小樹(shù)的另一種可能做法是后剪枝。樹(shù)完全增長(zhǎng)直到所有的樹(shù)葉都是純的并具有零訓(xùn)練誤差之后，找出導(dǎo)致過(guò)分?jǐn)M合的子樹(shù)并剪掉它們。從最初的被標(biāo)記的數(shù)據(jù)集中保留一個(gè)剪枝集，在訓(xùn)練階段不使用，對(duì)于每顆子樹(shù)，用一個(gè)被該子樹(shù)覆蓋的訓(xùn)練實(shí)例標(biāo)記的樹(shù)葉節(jié)點(diǎn)替換它，如果該樹(shù)葉在剪枝集上的性能不比該子樹(shù)差，則剪掉該子樹(shù)并保留樹(shù)葉節(jié)點(diǎn)，因?yàn)樽訕?shù)的附加的復(fù)雜性是不必要的，否則保留子樹(shù)。 剪枝還可以依據(jù)最小長(zhǎng)度等其它準(zhǔn)則。先剪枝較

38、快，但后剪枝通常導(dǎo)致更準(zhǔn)確的樹(shù)。6.3 決策樹(shù)學(xué)習(xí)第55頁(yè)，共85頁(yè)。 基于實(shí)例的學(xué)習(xí)采用保存實(shí)例本身的方法來(lái)表達(dá)從實(shí)例集里提取出的知識(shí)，并將類未知的新實(shí)例與現(xiàn)有的類已知的實(shí)例聯(lián)系起來(lái)進(jìn)行操作。這種方法直接在樣本上工作，不需要建立規(guī)則。基于實(shí)例的學(xué)習(xí)方法包括最近鄰法、局部加權(quán)回歸法、基于范例的推理法等等。基于實(shí)例的學(xué)習(xí)只是簡(jiǎn)單地把訓(xùn)練樣例存儲(chǔ)起來(lái)，從這些實(shí)例中泛化的工作被推遲到必須分類新的實(shí)例時(shí)，所以有時(shí)被稱為消極學(xué)習(xí)法。6.4 基于實(shí)例的學(xué)習(xí)第56頁(yè)，共85頁(yè)。6.4.1 K-近鄰算法 基于實(shí)例的機(jī)器學(xué)習(xí)方法把實(shí)例表示為n維歐式空間Rn中的實(shí)數(shù)點(diǎn)，使用歐氏距離函數(shù)，把任意的實(shí)例x表示為這樣的

39、特征向量：，那么兩個(gè)實(shí)例xi和xj之間的距離定義為d(xi,xj),則 d(xi,xj)=6.4 基于實(shí)例的學(xué)習(xí)第57頁(yè)，共85頁(yè)。算法6.4 逼近離散值函數(shù)f: RnV的k-近鄰算法：訓(xùn)練算法：將每個(gè)訓(xùn)練樣例加入到列表 training_examples分類算法： （1）給定一個(gè)要分類的查詢實(shí)例xq （2）在training_examples中選出最靠近xq 的k個(gè)實(shí)例，并用x1.xk表示 （3）返回6.4 基于實(shí)例的學(xué)習(xí)第58頁(yè)，共85頁(yè)。 離散的k-近鄰算法作簡(jiǎn)單修改后可用于逼近連續(xù)值的目標(biāo)函數(shù)。即計(jì)算k個(gè)最接近樣例的平均值，而不是計(jì)算其中的最普遍的值，為逼近f：RnR，計(jì)算式如下： 6

40、.4 基于實(shí)例的學(xué)習(xí)第59頁(yè)，共85頁(yè)。6.4.2 距離加權(quán)最近鄰法 對(duì)k-近鄰算法的一個(gè)改進(jìn)是對(duì)k個(gè)近鄰的貢獻(xiàn)加權(quán)，越近的距離賦予越大的權(quán)值，比如：也可以用類似的方式對(duì)實(shí)值目標(biāo)函數(shù)進(jìn)行距離加權(quán) 6.4 基于實(shí)例的學(xué)習(xí)第60頁(yè)，共85頁(yè)。6.4.3 基于范例的學(xué)習(xí) 人們?yōu)榱私鉀Q一個(gè)新問(wèn)題，先是進(jìn)行回憶，從記憶中找到一個(gè)與新問(wèn)題相似的范例，然后把該范例中的有關(guān)信息和知識(shí)復(fù)用到新問(wèn)題的求解之中。 基于范例的學(xué)習(xí)采用更復(fù)雜的符號(hào)表示，因此檢索實(shí)例的方法也更加復(fù)雜。在基于范例推理 (Case-Based Reasoning, 簡(jiǎn)稱CBR)中，把當(dāng)前所面臨的問(wèn)題或情況稱為目標(biāo)范例(target case

41、)，而把記憶的問(wèn)題或情況稱為源范例(base case)，基于范例推理就是由目標(biāo)范例的提示而獲得記憶中的源范例，并由源范例來(lái)指導(dǎo)目標(biāo)范例求解的一種策略. 基于范例的推理是人工智能領(lǐng)域中的一種重要的基于知識(shí)的問(wèn)題求解和學(xué)習(xí)的方法?；诜独评碇兄R(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í)該怎樣走向成功或避開(kāi)失敗，這樣可以改善求解的質(zhì)量。對(duì)于那些目前沒(méi)有或根本不存在可以通過(guò)計(jì)算推導(dǎo)來(lái)解決的問(wèn)題，基于范例推理能很好發(fā)揮作用。6.4 基于實(shí)例的學(xué)習(xí)第61頁(yè)，共

42、85頁(yè)。1.基于范例推理的一般過(guò)程（1）聯(lián)想記憶（2）類比映射（3）獲得求解方案（4）評(píng)價(jià)6.4 基于實(shí)例的學(xué)習(xí)第62頁(yè)，共85頁(yè)。圖6.9 基于范例推理的結(jié)構(gòu)6.4 基于實(shí)例的學(xué)習(xí)第63頁(yè)，共85頁(yè)。在基于范例的學(xué)習(xí)中要解決的主要問(wèn)題有 (1) 范例表示 (2) 分析模型 (3) 范例檢索 (4) 類比映射 (5) 類比轉(zhuǎn)換 (6) 解釋過(guò)程 (7) 范例修補(bǔ) (8) 類比驗(yàn)證(9) 范例保存 6.4 基于實(shí)例的學(xué)習(xí)第64頁(yè)，共85頁(yè)。2.范例的表示 一個(gè)記憶網(wǎng)便是以語(yǔ)義記憶單元（SMU）為結(jié)點(diǎn)，以語(yǔ)義記憶單元間的各種關(guān)系為連接建立起來(lái)的網(wǎng)絡(luò)。 SMU = SMU_NAME slot Con

43、straint slots Taxonomy slots Causality slots Similarity slots Partonomy slots Case slots Theory slots 6.4 基于實(shí)例的學(xué)習(xí)第65頁(yè)，共85頁(yè)。3范例組織 (1)范例內(nèi)容 問(wèn)題或情景描述。是對(duì)要求解的問(wèn)題或要理解的情景的描述，一般要包括這些內(nèi)容：當(dāng)范例發(fā)生時(shí)推理器的目標(biāo)，完成該目標(biāo)所要涉及的任務(wù)，周圍世界或環(huán)境與可能解決方案相關(guān)的所有特征。解決方案的內(nèi)容是問(wèn)題如何在一特定情形下得到解決。它可能是對(duì)問(wèn)題的簡(jiǎn)單解答，也可能是得出解答的推導(dǎo)過(guò)程。結(jié)果。記錄了實(shí)施解決方案后的結(jié)果情況，是失敗還是成功。

44、有了結(jié)果內(nèi)容，CBR在給出建議解時(shí)有能給出曾經(jīng)成功地工作的范例，同時(shí)也能利用失敗的范例來(lái)避免可能會(huì)發(fā)生的問(wèn)題。當(dāng)對(duì)問(wèn)題還缺乏足夠的了解時(shí)，通過(guò)在范例的表示上加上結(jié)果部分能取得較好的效果。6.4 基于實(shí)例的學(xué)習(xí)第66頁(yè)，共85頁(yè)。 (2)范例索引 建立范例索引有三個(gè)原則：索引與具體領(lǐng)域有關(guān)。數(shù)據(jù)庫(kù)中的索引是通用的，目的僅僅是追求索引能對(duì)數(shù)據(jù)集合進(jìn)行平衡的劃分從而使得檢索速度最快；而范例索引則要考慮是否有利于將來(lái)的范例檢索，它決定了針對(duì)某個(gè)具體的問(wèn)題哪些范例被復(fù)用；索引應(yīng)該有一定的抽象或泛化程度。這樣才能靈活處理以后可能遇到的各種情景，太具體則不能滿足更多的情況；索引應(yīng)該有一定的具體性。這樣才能在

45、以后被容易地識(shí)別出來(lái)，太抽象則各個(gè)范例之間的差別將被消除。6.4 基于實(shí)例的學(xué)習(xí)第67頁(yè)，共85頁(yè)。4范例的檢索范例檢索從范例庫(kù)(Case Base)中找到一個(gè)或多個(gè)與當(dāng)前問(wèn)題最相似的范例；CBR系統(tǒng)中的知識(shí)庫(kù)不是以前專家系統(tǒng)中的規(guī)則庫(kù)，它是由領(lǐng)域?qū)＜乙郧敖鉀Q過(guò)的一些問(wèn)題組成。范例庫(kù)中的每一個(gè)范例包括以前問(wèn)題的一般描述即情景和解法。一個(gè)新范例并入范例庫(kù)時(shí)，同時(shí)也建立了關(guān)于這個(gè)范例的主要特征的索引。當(dāng)接受了一個(gè)求解新問(wèn)題的要求后，CBR利用相似度知識(shí)和特征索引從范例庫(kù)中找出與當(dāng)前問(wèn)題相關(guān)的最佳范例，由于它所回憶的內(nèi)容，即所得到的范例質(zhì)量和數(shù)量直接影響著問(wèn)題的解決效果，所以此項(xiàng)工作比較重要。范例檢

46、索通過(guò)三個(gè)子過(guò)程，即特征辯識(shí)、初步匹配，最佳選定來(lái)實(shí)現(xiàn)。6.4 基于實(shí)例的學(xué)習(xí)第68頁(yè)，共85頁(yè)。5范例的復(fù)用(1)替換法 替換法是把舊解中的相關(guān)值，做相應(yīng)替換而形成新解。有重新例化、參數(shù)調(diào)整、局部搜索、查詢、特定搜索、基于范例的替換等。(2)轉(zhuǎn)換法 常識(shí)轉(zhuǎn)換法（common-sense transformation）是使用明白易懂的常識(shí)性啟發(fā)式從舊解中替換、刪除或增加某些組成部分。模型制導(dǎo)修補(bǔ)法（model-guided repair）是另一種轉(zhuǎn)換法，它是通過(guò)因果模型來(lái)指導(dǎo)如何轉(zhuǎn)換。故障診斷中就經(jīng)常使用這種方法。 6.4 基于實(shí)例的學(xué)習(xí)第69頁(yè)，共85頁(yè)。5范例的復(fù)用(3)特定目標(biāo)驅(qū)動(dòng)法 特

47、定目標(biāo)驅(qū)動(dòng)的修正啟發(fā)式知識(shí)一般通過(guò)評(píng)價(jià)近似解作用，并通過(guò)使用基于規(guī)則的產(chǎn)生式系統(tǒng)來(lái)控制。 (4)派生重演 重演方法則是使用過(guò)去的推導(dǎo)出舊解的方法來(lái)推導(dǎo)出新解。這種方法關(guān)心的是解是如何求出來(lái)的。同前面的基于范例替換相比，派生重演使用的則是一種基于范例的修正手段。6.4 基于實(shí)例的學(xué)習(xí)第70頁(yè)，共85頁(yè)。強(qiáng)化學(xué)習(xí)(reinforcement learning，又稱再勵(lì)學(xué)習(xí)，評(píng)價(jià)學(xué)習(xí))是一種重要的機(jī)器學(xué)習(xí)方法。根據(jù)學(xué)習(xí)方式的不同，可以把學(xué)習(xí)算法分為三種類型，即非監(jiān)督學(xué)習(xí)(unsupervised learning)、監(jiān)督學(xué)習(xí)(supervised leaning)和強(qiáng)化學(xué)習(xí)。所謂強(qiáng)化學(xué)習(xí)就是智能系統(tǒng)

48、從環(huán)境到行為映射的學(xué)習(xí)，目的是使獎(jiǎng)勵(lì)信號(hào)(強(qiáng)化信號(hào))函數(shù)值最大。強(qiáng)化學(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)RLS(reinforcement learning system)如何去產(chǎn)生正確的動(dòng)作。由于外部環(huán)境提供的信息很少，RLS必須靠自身的經(jīng)歷進(jìn)行學(xué)習(xí)。通過(guò)這種方式，RLS在行動(dòng)-評(píng)價(jià)的環(huán)境中獲得知識(shí)，改進(jìn)行動(dòng)方案以適應(yīng)環(huán)境強(qiáng)化學(xué)習(xí)要解決的問(wèn)題：主體怎樣通過(guò)學(xué)習(xí)選擇能達(dá)到其目標(biāo)的最優(yōu)動(dòng)作。當(dāng)主體在其環(huán)境中做出每個(gè)動(dòng)作，施教者提供獎(jiǎng)勵(lì)或懲罰信息，以表示結(jié)果狀態(tài)的正確與否。例如，在訓(xùn)練主體進(jìn)行

49、棋類對(duì)弈時(shí)，施教者可在游戲勝利時(shí)給出正回報(bào)，在游戲失敗時(shí)給出負(fù)回報(bào)，其他時(shí)候給出零回報(bào)。主體的任務(wù)是從這個(gè)非直接的有延遲的回報(bào)中學(xué)習(xí)，以便后續(xù)動(dòng)作產(chǎn)生最大的累積回報(bào)。6.5 強(qiáng)化學(xué)習(xí)第71頁(yè)，共85頁(yè)。6.5.1 強(qiáng)化學(xué)習(xí)模型si+1ri+1報(bào)酬ri主體環(huán)境狀態(tài)si行動(dòng)ai 圖6.10 強(qiáng)化學(xué)習(xí)模型6.5 強(qiáng)化學(xué)習(xí)第72頁(yè)，共85頁(yè)。 Agent狀態(tài)回報(bào)動(dòng)作 環(huán) 境a0a2a1s1s0s2r1r0r2目標(biāo)：學(xué)習(xí)選擇動(dòng)作使下式最大化 r0 + r1 + 2r2 + 其中01Agent 的任務(wù)是學(xué)習(xí)一個(gè)控制策略 ：S A 它使這些回報(bào)的和的期望值最大。6.5 強(qiáng)化學(xué)習(xí)第73頁(yè)，共85頁(yè)。6.5.2 馬爾可夫決策過(guò)程基于馬爾科夫決策過(guò)程定義學(xué)習(xí)控制策略問(wèn)題的一般形式為：主體可感知到其環(huán)境的不同狀態(tài)集合S，可執(zhí)行的動(dòng)作集合A。在每個(gè)離散時(shí)間步t，主體感知到當(dāng)前狀態(tài)st，選擇當(dāng)前動(dòng)作at，環(huán)境給出回報(bào)函數(shù)rt=r(st,at)，并產(chǎn)生后繼狀態(tài)函數(shù)st+1=(st,at)，此函數(shù)也叫狀態(tài)轉(zhuǎn)移函數(shù)。在MDP中，函數(shù)(st,at)，r(st,at)只依賴于當(dāng)前動(dòng)作和狀態(tài)，這里先考慮它們?yōu)榇_定性的情形。主體的任務(wù)是學(xué)習(xí)一個(gè)策略 ：S A，它基于當(dāng)前的狀態(tài)st選擇下一步動(dòng)作at，即（st）at，要求此策略對(duì)主體產(chǎn)生最大的累積回報(bào)。6.5 強(qiáng)化學(xué)習(xí)第74頁(yè)，共85頁(yè)。定義1：策略從