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

1、第六章 機(jī)器學(xué)習(xí)主要內(nèi)容機(jī)器學(xué)習(xí)概述歸納學(xué)習(xí)決策樹學(xué)習(xí)基于實例的學(xué)習(xí)強(qiáng)化學(xué)習(xí)小結(jié) 6.1.1 學(xué)習(xí)與機(jī)器學(xué)習(xí) 學(xué)習(xí)的概念，代表性觀點(1)心理學(xué)的解釋學(xué)習(xí)是指（人或動物）依靠經(jīng)驗的獲得而使行為持久變化的過程。(2)西蒙（Simon,1983） 學(xué)習(xí)就是系統(tǒng)中的適應(yīng)性變化，這種變化使系統(tǒng)在重復(fù)同樣工作或類似工作時，能夠做得更好。(3) Tom M. Mitchell（機(jī)器學(xué)習(xí)） 對于某類任務(wù)T和性能度P，如果一個計算機(jī)程序在T上以P衡量的性能隨著經(jīng)驗E而自我完善，那么，我們稱這個計算機(jī)程序從經(jīng)驗E中學(xué)習(xí)。6.1 機(jī)器學(xué)習(xí)概述 6.1.1 機(jī)器學(xué)習(xí)的概念學(xué)習(xí)的一般性解釋學(xué)習(xí)是對某一個特定目標(biāo)的知識

2、獲取的智能過程，系統(tǒng)的內(nèi)部表現(xiàn)為獲得知識、積累經(jīng)驗、發(fā)現(xiàn)規(guī)律，外部表現(xiàn)為改進(jìn)性能、適應(yīng)環(huán)境、實現(xiàn)自我完善。機(jī)器學(xué)習(xí)機(jī)器模擬人類的學(xué)習(xí)活動獲取知識和技能的理論和方法改善系統(tǒng)性能6.1 機(jī)器學(xué)習(xí)概述* 1. 具有適當(dāng)?shù)膶W(xué)習(xí)環(huán)境指學(xué)習(xí)系統(tǒng)進(jìn)行學(xué)習(xí)時所必需的信息來源。 2. 具有一定的學(xué)習(xí)能力學(xué)習(xí)系統(tǒng)應(yīng)模擬人的學(xué)習(xí)過程，使系統(tǒng)通過與環(huán)境反復(fù)多次相互作用，逐步學(xué)到有關(guān)知識，要使系統(tǒng)在學(xué)習(xí)過程中通過實踐驗證、評價所學(xué)知識的正確性。 3. 能用所學(xué)的知識解決問題學(xué)習(xí)系統(tǒng)能把學(xué)到的信息用于對未來的估計、分類、決策和控制。一個機(jī)器學(xué)習(xí)系統(tǒng)應(yīng)具有特點*4. 能提高系統(tǒng)的性能 提高系統(tǒng)的性能是學(xué)習(xí)系統(tǒng)最終目標(biāo)。通過

3、學(xué)習(xí)，系統(tǒng)隨之增長知識，提高解決問題的能力，使之能完成原來不能完成的任務(wù)，或者比原來做得更好。學(xué)習(xí)系統(tǒng)至少應(yīng)有環(huán)境、知識庫、學(xué)習(xí)環(huán)節(jié)和執(zhí)行環(huán)節(jié)四個基本部分。一種典型的機(jī)器學(xué)習(xí)系統(tǒng)-迪特里奇(Dietterich)學(xué)習(xí)模型 迪特里奇（Dietterich）學(xué)習(xí)模型 環(huán)境向系統(tǒng)的學(xué)習(xí)部件提供某些信息， 學(xué)習(xí)環(huán)節(jié)對環(huán)境提供的信息進(jìn)行整理、分析歸納或類比，形成知識，放入/修改知識庫。 知識庫存儲經(jīng)過加工后的信息（即知識）。 執(zhí)行環(huán)節(jié)根據(jù)知識庫完成任務(wù)，同時把獲得的信息反饋給學(xué)習(xí)部件。學(xué)習(xí)環(huán)節(jié)再利用反饋信息對知識進(jìn)行評價，進(jìn)一步改善執(zhí)行環(huán)節(jié)的行為。環(huán)境學(xué)習(xí)單元知識庫執(zhí)行單元簡單的學(xué)習(xí)模型 1神經(jīng)元模型研

4、究階段神經(jīng)元模型以及基于該模型的決策論和控制論;機(jī)器學(xué)習(xí)方法通過監(jiān)督（有教師指導(dǎo)的）學(xué)習(xí)來實現(xiàn)神經(jīng)元間連接權(quán)的自適應(yīng)調(diào)整，產(chǎn)生線性的模式分類和聯(lián)想記憶能力。代表性的工作FRosenblaft的感知機(jī)（1958年）WSMcCullouch與WPitts的模式擬神經(jīng)元理論（1943年）6.1.2 機(jī)器學(xué)習(xí)的發(fā)展簡史*神經(jīng)元模型*神經(jīng)網(wǎng)絡(luò)圓圈代表神經(jīng)元x1x2x3y2隱含層WiWiy12符號概念獲取研究階段心理學(xué)和人類學(xué)習(xí)的模似占有主導(dǎo)地位，其特點是使用符號而不是數(shù)值表示來研究學(xué)習(xí)問題，其目標(biāo)是用學(xué)習(xí)來表達(dá)高級知識的符號描述。主要技術(shù)是概念獲取和各種模式識別系統(tǒng)的應(yīng)用代表性的工作是溫斯頓的基于示例

5、歸納的結(jié)構(gòu)化概念學(xué)習(xí)系統(tǒng)。3基于知識的各種學(xué)習(xí)系統(tǒng)研究階段第三階段始于70年代中期不再局限于構(gòu)造概念學(xué)習(xí)系統(tǒng)和獲取上下文知識結(jié)合了問題求解中的學(xué)習(xí)、概念聚類、類比推理及機(jī)器發(fā)現(xiàn)的工作有關(guān)學(xué)習(xí)方法: 示例學(xué)習(xí)、示教學(xué)習(xí)、 觀察和發(fā)現(xiàn)學(xué)習(xí)、類比學(xué)習(xí)、基于解釋的學(xué)習(xí)。工作特點強(qiáng)調(diào)應(yīng)用面向任務(wù)的知識和指導(dǎo)學(xué)習(xí)過程的約束，應(yīng)用啟發(fā)式知識于學(xué)習(xí)任務(wù)的生成和選擇，包括提出收集數(shù)據(jù)的方式、選擇要獲取的概念、控制系統(tǒng)的注意力。4聯(lián)結(jié)學(xué)習(xí)和符號學(xué)習(xí)共同發(fā)展階段80年代后期以來，發(fā)現(xiàn)了用隱單元來計算和學(xué)習(xí)非線性函數(shù)的方法，克服了早期神經(jīng)元模型的局限性神經(jīng)網(wǎng)絡(luò)的物理實現(xiàn)(計算機(jī)硬件)，在聲音識別、圖像處理等領(lǐng)域，取得

6、了很大成功符號學(xué)習(xí)杰出的工作有分析學(xué)習(xí)（特別是解釋學(xué)習(xí)）、遺傳算法、決策樹歸納等。*發(fā)現(xiàn)了用隱單元來計算和學(xué)習(xí)非線性函數(shù)的方法，克服了早期神經(jīng)元模型的局限性60 75 6910 x1x2x3y2隱含層WiWiy11. 基于學(xué)習(xí)策略的分類 （1）模擬人腦的機(jī)器學(xué)習(xí)符號學(xué)習(xí)：模擬人腦的宏觀心理級學(xué)習(xí)過程，以認(rèn)知心理學(xué)原理為基礎(chǔ)，以符號數(shù)據(jù)為輸入，以符號運算為方法，用推理過程在圖或狀態(tài)空間中搜索，學(xué)習(xí)的目標(biāo)為概念或規(guī)則等。符號學(xué)習(xí)的典型方法有：記憶學(xué)習(xí)、示例學(xué)習(xí)、演繹學(xué)習(xí)、類比學(xué)習(xí)、解釋學(xué)習(xí)等。神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)（或連接學(xué)習(xí)）：模擬人腦的微觀生理級學(xué)習(xí)過程，以腦和神經(jīng)科學(xué)原理為基礎(chǔ)，以人工神經(jīng)網(wǎng)絡(luò)為函數(shù)結(jié)

7、構(gòu)模型，以數(shù)值數(shù)據(jù)為輸入，以數(shù)值運算為方法，用迭代過程在系數(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ī)器學(xué)習(xí)。6.1.3 機(jī)器學(xué)習(xí)的分類2. 基于推理策略的分類 （1）歸納學(xué)習(xí)：應(yīng)用歸納推理進(jìn)行學(xué)習(xí)的方法。是從個別到一般的推理。 （2）解釋學(xué)習(xí)：根據(jù)任務(wù)所在領(lǐng)域的知識和概念，對當(dāng)前示例進(jìn)行分析和求解。 （3）神經(jīng)學(xué)習(xí)：基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)。BP神經(jīng)網(wǎng)絡(luò)，Hopfield網(wǎng)絡(luò)。 （4）知識發(fā)現(xiàn)：從大量數(shù)據(jù)中識別出有效的，新穎的，潛在有用的，可被理解的模式的高級處理過程。3. 基于學(xué)習(xí)方式的分類（1）有導(dǎo)師學(xué)習(xí)（監(jiān)督

8、學(xué)習(xí)）：輸入數(shù)據(jù)中有導(dǎo)師信號，以概率函數(shù)、代數(shù)函數(shù)或人工神經(jīng)網(wǎng)絡(luò)為基函數(shù)模型，采用迭代計算方法，學(xué)習(xí)結(jié)果為函數(shù)。如神經(jīng)學(xué)習(xí)，分類學(xué)習(xí)。（2）無導(dǎo)師學(xué)習(xí)（非監(jiān)督學(xué)習(xí)）：輸入數(shù)據(jù)中無導(dǎo)師信號，采用聚類方法，學(xué)習(xí)結(jié)果為類別。典型的無導(dǎo)師學(xué)習(xí)有發(fā)現(xiàn)學(xué)習(xí)、聚類、競爭學(xué)習(xí)等。（3）強(qiáng)化學(xué)習(xí)（增強(qiáng)學(xué)習(xí)）：以環(huán)境反饋（獎/懲信號）作為輸入，以統(tǒng)計和動態(tài)規(guī)劃技術(shù)為指導(dǎo)的一種學(xué)習(xí)方法。4. 基于數(shù)據(jù)形式的分類（1）結(jié)構(gòu)化學(xué)習(xí)：以結(jié)構(gòu)化數(shù)據(jù)為輸入，以數(shù)值計算或符號推演為方法。典型的結(jié)構(gòu)化學(xué)習(xí)有神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)、統(tǒng)計學(xué)習(xí)、決策樹學(xué)習(xí)、規(guī)則學(xué)習(xí)。（2）非結(jié)構(gòu)化學(xué)習(xí)：以非結(jié)構(gòu)化數(shù)據(jù)為輸入，典型的非結(jié)構(gòu)化學(xué)習(xí)有類比學(xué)習(xí)、案例學(xué)

9、習(xí)、解釋學(xué)習(xí)、文本挖掘、圖像挖掘、Web挖掘等。 5. 基于學(xué)習(xí)目標(biāo)的分類 （1）概念學(xué)習(xí)： 學(xué)習(xí)的目標(biāo)和結(jié)果為概念，典型的概念學(xué)習(xí)有示例學(xué)習(xí)。 （2）規(guī)則學(xué)習(xí)： 學(xué)習(xí)的目標(biāo)和結(jié)果為規(guī)則，典型的規(guī)則學(xué)習(xí)有決策樹學(xué)習(xí)。 （3）函數(shù)學(xué)習(xí)： 學(xué)習(xí)的目標(biāo)和結(jié)果為規(guī)則，典型的函數(shù)學(xué)習(xí)有神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)。 （4）類別學(xué)習(xí)： 學(xué)習(xí)的目標(biāo)和結(jié)果為對象類，典型的類別學(xué)習(xí)有聚類分析。 （5）貝葉斯網(wǎng)絡(luò)學(xué)習(xí)： 學(xué)習(xí)的目標(biāo)和結(jié)果是貝葉斯網(wǎng)絡(luò)，又分為結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)。機(jī)器學(xué)習(xí)的應(yīng)用：文本分類模型自動挖掘和生成以及動態(tài)優(yōu)化 與自然語言處理的結(jié)合在專家系統(tǒng)和智能決策系統(tǒng)的應(yīng)用 語音識別自動駕駛技術(shù)學(xué)習(xí)分類新的天文結(jié)構(gòu)人機(jī)對弈

10、：深藍(lán)，阿爾法狗6.1.4 機(jī)器學(xué)習(xí)的應(yīng)用與研究目標(biāo)：研究目標(biāo)有三個： (1)人類學(xué)習(xí)過程的認(rèn)知模型研究人類學(xué)習(xí)機(jī)理的認(rèn)知模型。(2)通用學(xué)習(xí)算法通過對人類學(xué)習(xí)過程的研究，探索各種可能的學(xué)習(xí)方法，建立起具體應(yīng)用領(lǐng)域的通用學(xué)習(xí)算法。(3)構(gòu)造面向任務(wù)的專用學(xué)習(xí)系統(tǒng)。研究智能系統(tǒng)的建造，解決專門的實際問題。主要內(nèi)容機(jī)器學(xué)習(xí)概述歸納學(xué)習(xí)決策樹學(xué)習(xí)基于實例的學(xué)習(xí)強(qiáng)化學(xué)習(xí)小結(jié)歸納學(xué)習(xí) 歸納學(xué)習(xí)(概念學(xué)習(xí)、經(jīng)驗學(xué)習(xí)）是符號學(xué)習(xí)中研究的最為廣泛的一種方法。 給定關(guān)于某個概念的一系列已知的正例與反例，其任務(wù)是從中歸納出一個一般的概念描述。 歸納學(xué)習(xí)能夠獲得新的概念，創(chuàng)立新的規(guī)則，發(fā)現(xiàn)新的理論。它的一般操作是泛

11、化和特化。 泛化用來擴(kuò)展一假設(shè)的語義信息，以使其能夠包含更多的正例，應(yīng)用于更多的情況。 特化是泛化的相反的操作，用于限制概念描述的應(yīng)用范圍。 6.2.1 歸納學(xué)習(xí)的基本概念歸納學(xué)習(xí)指在從大量的經(jīng)驗數(shù)據(jù)中歸納抽取出一般的判定規(guī)則和模式，是從特殊情況推導(dǎo)出一般規(guī)則的學(xué)習(xí)方法。歸納學(xué)習(xí)的目標(biāo)是形成合理的能解釋已知事實和預(yù)見新事實的一般性結(jié)論。歸納學(xué)習(xí)由于依賴于經(jīng)驗數(shù)據(jù)，因此又稱為經(jīng)驗學(xué)習(xí)，也稱為基于相似性的學(xué)習(xí)。歸納學(xué)習(xí)的雙空間模型如圖所示。1.歸納學(xué)習(xí)的雙空間模型*示教者給實例空間提供一些初始示教例子，程序?qū)κ窘汤舆M(jìn)行解釋（由于示教例子的形式往往不同于規(guī)則形式）再利用被解釋的示教例子搜索規(guī)則空間

12、。 一般不能一次就從規(guī)則空間中搜索到要求的規(guī)則，還要找一些新的示教例子，這個過程是選擇例子。此過程如此循環(huán)，直到搜索到要求的規(guī)則。麻雀從地上飛到樹枝上鳥會飛鴿子從窗臺飛到樹上鳥會走歸納學(xué)習(xí)根據(jù)有無導(dǎo)師分成示例學(xué)習(xí)和觀察與發(fā)現(xiàn)學(xué)習(xí)。歸納學(xué)習(xí)按學(xué)習(xí)的概念劃分為單概念學(xué)習(xí)和多概念學(xué)習(xí)兩類。概念指用某種描述語言表示的謂詞，當(dāng)應(yīng)用于概念的正實例時，謂詞為真，應(yīng)用于負(fù)實例時為假。從而概念謂詞將實例空間劃分為正、反兩個子集。2.歸納學(xué)習(xí)方法的分類*基于內(nèi)容的圖像檢索正例反例* 按例子的來源分類 例子來源于教師的示例學(xué)習(xí) 例子來源于學(xué)習(xí)者本身的示例學(xué)習(xí) 知道自己的狀態(tài)，但不清楚所要獲取的概念。 例子來源于學(xué)習(xí)

13、者以外的外部環(huán)境的示例學(xué)習(xí) 按例子的類型分類（哪種好？） 僅利用正例的示例學(xué)習(xí) 這種學(xué)習(xí)方法會使推出的概念的外延擴(kuò)大化。 利用正例和反例的示例學(xué)習(xí) 這是典型方式，它用正例用來產(chǎn)生概念，用反例來防止概念外延的擴(kuò)大。 *陳佩斯 孟飛 樂嘉典型的單概念學(xué)習(xí)系統(tǒng)包括基于數(shù)據(jù)驅(qū)動的變型空間法，ID3方法，基于模型驅(qū)動的Induce算法。典型的多概念學(xué)習(xí)方法和系統(tǒng)有AQ11、DENDRAL和AM程序等。多概念學(xué)習(xí)任務(wù)可以劃分成多個單概念學(xué)習(xí)任務(wù)來完成。多概念學(xué)習(xí)與單概念學(xué)習(xí)的差別在于多概念學(xué)習(xí)方法必須解決概念之間的沖突問題。歸納學(xué)習(xí)方法的分類主要內(nèi)容機(jī)器學(xué)習(xí)概述歸納學(xué)習(xí)決策樹學(xué)習(xí)基于實例的學(xué)習(xí)強(qiáng)化學(xué)習(xí)小結(jié)

14、決策樹學(xué)習(xí) 決策樹學(xué)習(xí)是離散函數(shù)的一種樹型表示，表示能力強(qiáng)，可以表示任意的離散函數(shù)，是一種重要的歸納學(xué)習(xí)方法。 決策樹是實現(xiàn)分治策略的數(shù)據(jù)結(jié)構(gòu)，通過把實例從根節(jié)點排列到某個葉子節(jié)點來分類實例，可用于分類和回歸。 決策樹一個屬性節(jié)點的輸出分枝和該節(jié)點的所有可能的檢驗結(jié)果相對應(yīng) 決策樹學(xué)習(xí)過程實際上是一個構(gòu)造決策樹的過程。當(dāng)學(xué)習(xí)完成后，就可以利用這棵決策樹對未知事物進(jìn)行分類決策樹決策樹是一種依托決策而建立起來的一種樹。在機(jī)器學(xué)習(xí)中，決策樹是一種預(yù)測模型，代表的是一種對象屬性與對象值之間的一種映射關(guān)系.每一個節(jié)點代表某個對象，樹中的每一個分叉路徑代表某個可能的屬性值，而每一個葉子節(jié)點則對應(yīng)從根節(jié)點到

15、該葉子節(jié)點所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出，如果有多個輸出，可以分別建立獨立的決策樹以處理不同的輸出。* 兩個輸出屬性X和Y的樣本分類決策樹 所有屬性值X1和Y=B的樣本屬于類2 值X1的樣本都屬于類1。 對于樹中的非葉節(jié)點， 可以沿著分枝繼續(xù)分 區(qū)樣本ID3算法是決策樹的一種，它是基于奧卡姆剃刀原理的，即用盡量用較少的東西做更多的事。在信息論中，期望信息越小，那么信息增益就越大，從而純度就越高。ID3算法的核心思想就是以信息增益來度量屬性的選擇，選擇分裂后信息增益最大的屬性進(jìn)行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策空間。信息熵在信息增益中，重要性的衡量標(biāo)準(zhǔn)就是看特征

16、能夠為分類系統(tǒng)帶來多少信息，帶來的信息越多，該特征越重要。熵,最早起源于物理學(xué)，用來度量一個熱力學(xué)系統(tǒng)的無序程度。在信息學(xué)里面，熵是對不確定性的度量。1948年，香農(nóng)引入了信息熵，將其定義為離散隨機(jī)事件出現(xiàn)的概率，一個系統(tǒng)越是有序，信息熵就越低，反之一個系統(tǒng)越是混亂，它的信息熵就越高。所以信息熵可以被認(rèn)為是系統(tǒng)有序化程度的一個度量。信息熵假設(shè)X是一個取值個數(shù)有限的離散隨機(jī)變量，概率分布為P(X=Xi)=pi,i=1,2,.,n則隨機(jī)變量X的熵定義為意思是一個變量的變化情況可能越多，那么它攜帶的信息量就越大。對于分類系統(tǒng)來說，類別C是變量，它的取值是C1,C2,Cn，每一個類別出現(xiàn)的概率分別是P

17、(C1),P(C2),P(Cn).條件熵是收信者在收到信息后對信息源不確定性的度量。條件熵H(Y|X)表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性。隨機(jī)變量X給定的條件下隨機(jī)變量Y的條件熵H(Y|X)，定義為X給定條件下Y的條件概率分布的熵對X的數(shù)學(xué)期望：它表示收信者收到Y(jié)后對X不確定性的估計。 信息增益信息增益是針對一個一個特征而言的，就是看一個特征，系統(tǒng)有它和沒有它時的信息量各是多少，兩者的差值就是這個特征給系統(tǒng)帶來的信息量，即信息增益。特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的經(jīng)驗嫡H(D)與特征A給定條件下D的經(jīng)驗條件嫡H(D|A)之差6.3.3基本的決策樹算法ID

18、3ID3的思想自頂向下構(gòu)造決策樹從“哪一個屬性將在樹的根節(jié)點被測試”開始使用統(tǒng)計測試來確定每一個實例屬性單獨分類訓(xùn)練樣例的能力ID3的過程分類能力最好的屬性被選作樹的根節(jié)點根節(jié)點的每個可能值產(chǎn)生一個分支訓(xùn)練樣例排列到適當(dāng)?shù)姆种е貜?fù)上面的過程*ID3算法的學(xué)習(xí)過程首先以整個例子集作為決策樹的根節(jié)點S，并計算S關(guān)于每個屬性的期望熵（即條件熵）；然后選擇能使S的期望熵為最小的一個屬性對根節(jié)點進(jìn)行分裂，得到根節(jié)點的一層子節(jié)點；接著再用同樣的方法對這些子節(jié)點進(jìn)行分裂，直至所有葉節(jié)點的熵值都下降為0為止。得到一棵與訓(xùn)練例子集對應(yīng)的熵為0的決策樹，該樹中每一條從根節(jié)點到葉節(jié)點的路徑，都代表了一個分類過程，即

19、決策過程。*節(jié)點優(yōu)先選擇哪個屬性值的原理根據(jù)的假設(shè)：決策樹的復(fù)雜度和所給屬性值表達(dá)的信息量是密切相關(guān)的。采用信息論方法：對樣本分類時，節(jié)點應(yīng)選的分類屬性是給出最高信息增益的屬性，即信息熵最小化的屬性。*2C4.5算法（分類屬性擴(kuò)展到數(shù)字）C4.5算法最重要的部分是由一組訓(xùn)練樣本生成一個初始決策樹的過程。該算法生成一個決策樹形式的分類器，決策樹節(jié)點具有兩種類型的結(jié)構(gòu)：一個葉節(jié)點，表示一個類，一個決策點，它指定要在單個屬性值上進(jìn)行的檢驗，對檢驗的每個可能輸出有一個分枝和子樹。*從該樹的根節(jié)點開始，移動樣本直至達(dá)葉節(jié)點。在每個非葉節(jié)點處，確定屬性檢驗結(jié)果，選擇子樹。例如，圖6-7a中的決策樹的分類模

20、型問題，待分類的樣本如圖6-7b所示，然后，該算法將生成一條通過節(jié)點A，C，F(xiàn)（葉節(jié)點）的路徑直到得出最終分類決策，即類2為止。決策樹用來對一個新樣本進(jìn)行分類* 圖6-7 基于決策樹模型的一個新樣本的分類銀行貸款不貸沒欠款貸現(xiàn)考慮鳥是否能飛的實例，InstancesNo. of WingsBroken WingsLiving statusarea/weightFly120alive2.5T221alive2.5F322alive2.6F420alive3.0T520dead3.2F600alive0F710alive0F820alive3.4T920alive2.0F對于上表給出的例子,選取整

21、個訓(xùn)練集為訓(xùn)練窗口,有3個正實例,6個負(fù)實例,采用記號3+,6-表示總的樣本數(shù)據(jù)。則S的熵為計算屬性Living Status的信息增益，該屬性為值域為(alive, dead),則 S=3+,6-, Salive=3+,5-, Sdead=0+,1- 先計算Entropy(Salive), Entropy(Sdead)如下:ID3算法-最佳分類屬性-例子分析ID3算法-最佳分類屬性-例子分析所以,living status的信息增益為ID3算法-最佳分類屬性-例子分析同樣可計算其他屬性的信息增益，然后根據(jù)最小熵原理，選取信息量最大的屬性作為決策樹的根節(jié)點屬性。NoNoNoNoYesNoNo2

22、10210alivedead2.52.5No. of WingsBroken WingsStatusArea/weight圖6.8 鳥飛的決策樹 ID3算法的優(yōu)點：分類和測試速度快，特別適用于大數(shù)據(jù)庫的分類問題。ID3算法的缺點： 第一：決策樹的知識表示沒有規(guī)則易于理解。 第二：兩顆決策樹比較是否等價問題是子圖匹配問題，是NP完全的。 第三：不能處理未知屬性值的情況。 第四：對噪聲問題沒有好的處理辦法。ID3算法-最佳分類屬性-優(yōu)缺點主要內(nèi)容機(jī)器學(xué)習(xí)概述歸納學(xué)習(xí)(變型空間和候選消除算法)決策樹學(xué)習(xí)基于實例的學(xué)習(xí)強(qiáng)化學(xué)習(xí)小結(jié) 采用保存實例本身的方法來表達(dá)從實例集里提取出的知識，并將類未知的新實例

23、與現(xiàn)有的類已知的實例聯(lián)系起來進(jìn)行操作。 直接在樣本上工作，不需要建立規(guī)則。 基于實例的學(xué)習(xí)方法包括最近鄰法、局部加權(quán)回歸法、基于范例的推理法等等。 基于實例的學(xué)習(xí)只是簡單地把訓(xùn)練樣例存儲起來，沒有提取訓(xùn)練數(shù)據(jù)的模型，稱為消極學(xué)習(xí)法Lazy?；趯嵗膶W(xué)習(xí)6.4.1 K-近鄰算法 基于實例的機(jī)器學(xué)習(xí)方法把實例表示為n維歐式空間Rn中的實數(shù)點，使用歐氏距離函數(shù)，把任意的實例x表示為這樣的特征向量：，那么兩個實例xi和xj之間的距離定義為d(xi,xj),則 d(xi,xj)=算法6.4 逼近離散值函數(shù)f: RnV的k-近鄰算法：訓(xùn)練算法：將每個訓(xùn)練樣例加入到列表 training_examples

24、分類算法： （1）給定一個要分類的查詢實例xq （2）在training_examples中選出最靠近xq 的k個實例，并用x1.xk表示 （3）返回 離散的k-近鄰算法作簡單修改后可用于逼近連續(xù)值的目標(biāo)函數(shù)。即計算k個最接近樣例的平均值，而不是計算其中的最普遍的值，為逼近f：RnR，計算式如下： 6.4.2 距離加權(quán)最近鄰法 對k-近鄰算法的一個改進(jìn)是對k個近鄰的貢獻(xiàn)加權(quán)，越近的距離賦予越大的權(quán)值，比如：也可以用類似的方式對實值目標(biāo)函數(shù)進(jìn)行距離加權(quán) 6.4.3 基于范例的學(xué)習(xí) 解決一個新問題：回憶，找到一個范例，復(fù)用到新問題中。 基于范例推理：把當(dāng)前所面臨的問題或情況稱為目標(biāo)范例，把記憶的問

25、題或情況稱為源范例，由目標(biāo)范例的提示而獲得記憶中的源范例，并由源范例來指導(dǎo)目標(biāo)范例求解的一種策略. 1.范例的獲取比規(guī)則獲取要容易，大大簡化了知識獲取。 2.對過去的求解結(jié)果的復(fù)用，不再從頭推導(dǎo)，提高問題的求解效率。 3.過去求解成功或失敗的經(jīng)歷指導(dǎo)當(dāng)前求解，改善了求解的質(zhì)量。 適用于目前沒有或根本不存在可以通過計算推導(dǎo)來解決的問題，基于范例推理能很好發(fā)揮作用。1.基于范例推理的一般過程（1）聯(lián)想記憶（2）類比映射（3）獲得求解方案（4）評價圖6.9 基于范例推理的結(jié)構(gòu)在基于范例的學(xué)習(xí)中要解決的主要問題有 (1) 范例表示 (2) 分析模型 (3) 范例檢索 (4) 類比映射 (5) 類比轉(zhuǎn)換

26、 (6) 解釋過程 (7) 范例修補(bǔ) (8) 類比驗證(9) 范例保存 2.范例的表示 一個記憶網(wǎng)便是以語義記憶單元（SMU）為結(jié)點，以語義記憶單元間的各種關(guān)系為連接建立起來的網(wǎng)絡(luò)。 SMU = SMU_NAME slot Constraint slots Taxonomy slots Causality slots Similarity slots Partonomy slots Case slots Theory slots 3范例組織 (1)范例內(nèi)容 問題或情景描述。包括：推理器的目標(biāo)，任務(wù)，周圍世界或環(huán)境與可能解決方案相關(guān)的所有特征。解決方案的內(nèi)容是問題如何在一特定情形下得到解決。它可

27、能是對問題的簡單解答，也可能是得出解答的推導(dǎo)過程。結(jié)果。記錄了實施解決方案后的結(jié)果情況，是失敗還是成功。用于給出建議解。(2)范例索引 建立范例索引有三個原則：索引與具體領(lǐng)域有關(guān)。范例索引則要考慮是否有利于將來的范例檢索，它決定了針對某個具體的問題哪些范例被復(fù)用；索引應(yīng)該有一定的抽象或泛化程度。能靈活處理以后可能遇到的各種情景。索引應(yīng)該有一定的具體性。能在以后被容易地識別出來，太抽象則各個范例之間的差別將被消除。4范例的檢索范例檢索從范例庫中找到一個或多個與當(dāng)前問題最相似的范例；知識庫不是以前專家系統(tǒng)中的規(guī)則庫，它是由領(lǐng)域?qū)＜乙郧敖鉀Q過的一些問題組成。范例庫中的每一個范例包括以前問題的一般描述

28、即情景和解法。一個新范例并入范例庫時，同時也建立了關(guān)于這個范例的主要特征的索引。當(dāng)接受了一個求解新問題的要求后，CBR利用相似度知識和特征索引從范例庫中找出與當(dāng)前問題相關(guān)的最佳范例。范例檢索通過三個子過程，即特征辯識、初步匹配，最佳選定來實現(xiàn)。5范例的復(fù)用(1)替換法 替換法是把舊解中的相關(guān)值，做相應(yīng)替換而形成新解。有重新例化、參數(shù)調(diào)整、局部搜索、查詢、特定搜索、基于范例的替換等。(2)轉(zhuǎn)換法 常識轉(zhuǎn)換法（common-sense transformation）是使用明白易懂的常識性啟發(fā)式從舊解中替換、刪除或增加某些組成部分。模型制導(dǎo)修補(bǔ)法（model-guided repair）是另一種轉(zhuǎn)換

29、法，它是通過因果模型來指導(dǎo)如何轉(zhuǎn)換。故障診斷中就經(jīng)常使用這種方法。 5范例的復(fù)用(3)特定目標(biāo)驅(qū)動法通過評價近似解，修正特定目標(biāo)驅(qū)動的啟發(fā)式知識。 (4)派生重演使用過去的推導(dǎo)來推導(dǎo)出新解。同基于范例替換相比，派生重演使用的則是一種基于范例的修正手段。主要內(nèi)容機(jī)器學(xué)習(xí)概述歸納學(xué)習(xí)(變型空間和候選消除算法)決策樹學(xué)習(xí)基于實例的學(xué)習(xí)強(qiáng)化學(xué)習(xí)小結(jié)強(qiáng)化學(xué)習(xí)(再勵學(xué)習(xí)，評價學(xué)習(xí))是一種重要的機(jī)器學(xué)習(xí)方法。分為三種類型：非監(jiān)督學(xué)習(xí)、監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)強(qiáng)化學(xué)習(xí)：從環(huán)境到行為映射的學(xué)習(xí)，目的是使獎勵信號(強(qiáng)化信號)函數(shù)值最大。不同于監(jiān)督學(xué)習(xí)的教師信號，強(qiáng)化學(xué)習(xí)中由環(huán)境提供的強(qiáng)化信號是對產(chǎn)生動作的好壞作一種評價

30、，而不是告訴強(qiáng)化學(xué)習(xí)系統(tǒng)如何去產(chǎn)生正確的動作。外部環(huán)境提供的信息很少，RLS必須靠自身的經(jīng)歷進(jìn)行學(xué)習(xí)。通過這種方式，RLS在行動-評價的環(huán)境中獲得知識，改進(jìn)行動方案以適應(yīng)環(huán)境強(qiáng)化學(xué)習(xí)RLS強(qiáng)化學(xué)習(xí)要解決的問題：主體怎樣通過學(xué)習(xí)選擇能達(dá)到其目標(biāo)的最優(yōu)動作。當(dāng)主體在其環(huán)境中做出每個動作，施教者提供獎勵或懲罰信息，以表示結(jié)果狀態(tài)的正確與否。例如，在進(jìn)行棋類對弈時，施教者可在游戲勝利時給出正回報，在游戲失敗時給出負(fù)回報，其他時候給出零回報。主體的任務(wù)是從這個非直接的有延遲的回報中學(xué)習(xí)，以便后續(xù)動作產(chǎn)生最大的累積回報。強(qiáng)化學(xué)習(xí)RLS6.5.1 強(qiáng)化學(xué)習(xí)模型si+1ri+1報酬ri主體環(huán)境狀態(tài)si行動ai 圖6.10 強(qiáng)化學(xué)習(xí)模型 Agent狀態(tài)回報動作 環(huán) 境a0a2a1s1s0s2r1r0r2目標(biāo)：學(xué)習(xí)選擇動作使下式最大化 r0 + r1 + 2r2 + 其中01Agent 的任務(wù)是學(xué)習(xí)一個控制策略 ：S A 它使這些回報的和的期望值最大。6.5.2 馬爾可夫決策過程主體可感知到其環(huán)境的不同狀態(tài)集合S，可執(zhí)行的動作集合A。在每個離散時間步t，主體感知