第4篇學(xué)習(xí)與發(fā)現(xiàn)

『導(dǎo)語』

學(xué)習(xí)是系統(tǒng)積累經(jīng)驗(yàn)或運(yùn)用規(guī)律指導(dǎo)自己的行為或改進(jìn)自身性能的過程，而發(fā)現(xiàn)則是系統(tǒng)從所接收的信息中發(fā)現(xiàn)規(guī)律的過程。學(xué)習(xí)與發(fā)現(xiàn)相輔相成，關(guān)系密切，以致在不少文獻(xiàn)中二者幾乎是同義語。

知識(shí)是智能的基礎(chǔ)和源泉，知識(shí)靠學(xué)習(xí)和發(fā)現(xiàn)來獲得，而學(xué)習(xí)和發(fā)現(xiàn)本身又是一種智能表現(xiàn)，所以，機(jī)器學(xué)習(xí)和知識(shí)發(fā)現(xiàn)將是人工智能永恒的課題。

第9章機(jī)器學(xué)習(xí)：符號(hào)學(xué)習(xí)與交互學(xué)習(xí)

9.1機(jī)器學(xué)習(xí)概述

9.2幾種經(jīng)典的（符號(hào)）學(xué)習(xí)方法

9.3決策樹學(xué)習(xí)

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

9.1機(jī)器學(xué)習(xí)概述9.1.1機(jī)器學(xué)習(xí)的概念心理學(xué)中對學(xué)習(xí)的解釋是：學(xué)習(xí)是指（人或動(dòng)物）依靠經(jīng)驗(yàn)的獲得而使行為持久變化的過程。Simon認(rèn)為：如果一個(gè)系統(tǒng)能夠通過執(zhí)行某種過程而改進(jìn)它的性能，這就是學(xué)習(xí)。Minsky認(rèn)為：學(xué)習(xí)是在人們頭腦中（心理內(nèi)部）進(jìn)行有用的變化。TomM.Mitchell在《機(jī)器學(xué)習(xí)》一書中對學(xué)習(xí)的定義是：對于某類任務(wù)T和性能度P，如果一個(gè)計(jì)算機(jī)程序在T上以P衡量的性能隨著經(jīng)驗(yàn)E而自我完善，那么，我們稱這個(gè)計(jì)算機(jī)程序從經(jīng)驗(yàn)E中學(xué)習(xí)。當(dāng)前關(guān)于機(jī)器學(xué)習(xí)的許多文獻(xiàn)中也大都認(rèn)為：學(xué)習(xí)是系統(tǒng)積累經(jīng)驗(yàn)以改善其自身性能的過程。9.1.2機(jī)器學(xué)習(xí)的原理

研究發(fā)現(xiàn)：①學(xué)習(xí)與經(jīng)驗(yàn)有關(guān)；②學(xué)習(xí)可以改善系統(tǒng)性能；③學(xué)習(xí)是一個(gè)有反饋的信息處理與控制過程。因?yàn)榻?jīng)驗(yàn)是在系統(tǒng)與環(huán)境的交互過程中產(chǎn)生的，而經(jīng)驗(yàn)中應(yīng)該包含系統(tǒng)輸入、響應(yīng)和效果等信息。因此經(jīng)驗(yàn)的積累、性能的完善正是通過重復(fù)這一過程而實(shí)現(xiàn)的。9.1.3機(jī)器學(xué)習(xí)的分類

1.基于學(xué)習(xí)途徑的分類(1)符號(hào)學(xué)習(xí)

模擬人腦宏觀心理級學(xué)習(xí)過程，以認(rèn)知心理學(xué)原理為基礎(chǔ)，以符號(hào)數(shù)據(jù)為輸入，以符號(hào)運(yùn)算為方法，用推理過程在圖或狀態(tài)空間中搜索，學(xué)習(xí)的目標(biāo)為概念或規(guī)則等。符號(hào)學(xué)習(xí)的典型方法有：記憶學(xué)習(xí)、示例學(xué)習(xí)、演繹學(xué)習(xí)、類比學(xué)習(xí)、規(guī)則學(xué)習(xí)、解釋學(xué)習(xí)等。(2)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)（或連接學(xué)習(xí)）模擬人腦的微觀生理級學(xué)習(xí)過程，以腦和神經(jīng)科學(xué)原理為基礎(chǔ)，以人工神經(jīng)網(wǎng)絡(luò)為拓?fù)浣Y(jié)構(gòu)模型，以數(shù)值數(shù)據(jù)為輸入，以數(shù)值運(yùn)算為方法，用迭代過程在權(quán)向量空間中搜索，學(xué)習(xí)的目標(biāo)為函數(shù)或類別。典型的連接學(xué)習(xí)有權(quán)值修正學(xué)習(xí)、拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)。(3)統(tǒng)計(jì)學(xué)習(xí)運(yùn)用統(tǒng)計(jì)、概率及其他數(shù)學(xué)理論和方法對樣本數(shù)據(jù)進(jìn)行處理，從中發(fā)現(xiàn)相關(guān)模式和規(guī)律的一種機(jī)器學(xué)習(xí)方法。(4)交互學(xué)習(xí)智能體通過與環(huán)境的交互而獲得相關(guān)知識(shí)和機(jī)能的一種機(jī)器學(xué)習(xí)方法。交互學(xué)習(xí)的典型方法就是強(qiáng)化學(xué)習(xí)（增強(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í)目標(biāo)為最優(yōu)行動(dòng)策略。

2.基于學(xué)習(xí)方法的分類

(1)歸納學(xué)習(xí)基于歸納推理的學(xué)習(xí)，又可分為：

符號(hào)歸納學(xué)習(xí)：如目標(biāo)為概念的示例學(xué)習(xí)，目標(biāo)為規(guī)則的決策樹學(xué)習(xí)。

函數(shù)歸納學(xué)習(xí)：如目標(biāo)為函數(shù)的統(tǒng)計(jì)學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)。

類別歸納學(xué)習(xí)：如無監(jiān)督學(xué)習(xí)。(2)演繹學(xué)習(xí)基于演繹推理的學(xué)習(xí)。(3)類比學(xué)習(xí)基于類比推理的學(xué)習(xí)。如案例（范例）學(xué)習(xí)、基于實(shí)例的學(xué)習(xí)、遷移學(xué)習(xí)。(4)分析學(xué)習(xí)利用先驗(yàn)知識(shí)和演繹推理來擴(kuò)大樣例提供的信息的一種學(xué)習(xí)方法。典型的分析學(xué)習(xí)有解釋學(xué)習(xí)。3.

基于樣本數(shù)據(jù)特點(diǎn)的分類

(1)有監(jiān)督學(xué)習(xí)（supervisedlearning，亦稱有導(dǎo)師學(xué)習(xí)）樣本數(shù)據(jù)為一些由向量(x1,x2,...,xn)和一個(gè)對應(yīng)值y組成的序?qū)?。監(jiān)督學(xué)習(xí)就是用當(dāng)前由(x1,x2,...,xn)所求得函數(shù)值y’與原對應(yīng)值y做比較，然后根據(jù)誤差決定是否對所選用的函數(shù)模型的參數(shù)進(jìn)行修正。監(jiān)督學(xué)習(xí)以概率函數(shù)、代數(shù)函數(shù)或者人工神經(jīng)網(wǎng)絡(luò)為基本函數(shù)模型，采用迭代計(jì)算的方法，來擬合相應(yīng)的數(shù)據(jù)集，學(xué)習(xí)結(jié)果為函數(shù)（即隱藏于樣本數(shù)據(jù)中的規(guī)律）。監(jiān)督學(xué)習(xí)被用于分類問題和回歸問題，以對未知進(jìn)行預(yù)測。

(2)

無監(jiān)督學(xué)習(xí)（unsupervisedlearning，亦稱無導(dǎo)師學(xué)習(xí)）

無監(jiān)督學(xué)習(xí)的樣本數(shù)據(jù)僅為一些向量(x1,x2,...,xn)（而無對應(yīng)值y），其學(xué)習(xí)方法就是聚類，即把相似的對象做為一類，學(xué)習(xí)結(jié)果為數(shù)據(jù)類別（即隱藏于樣本數(shù)據(jù)中的模式（類）或結(jié)構(gòu)）。無監(jiān)督學(xué)習(xí)被用于聚類問題，也可用于數(shù)據(jù)降維（dimensionalityreduction）和圖像壓縮（imagecompression）等。聚類學(xué)習(xí)和競爭學(xué)習(xí)都是典型的無監(jiān)督學(xué)習(xí)。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í)、決策樹學(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挖掘等的學(xué)習(xí)。

5.基于學(xué)習(xí)目標(biāo)的分類

(1)概念學(xué)習(xí)即學(xué)習(xí)的目標(biāo)和結(jié)果為概念，或者說是為了獲得概念的一種學(xué)習(xí)。典型的概念學(xué)習(xí)有示例學(xué)習(xí)。(2)規(guī)則學(xué)習(xí)即學(xué)習(xí)的目標(biāo)和結(jié)果為規(guī)則，或者說是為了獲得規(guī)則的一種學(xué)習(xí)。典型的規(guī)則學(xué)習(xí)有決策樹學(xué)習(xí)、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)。(3)函數(shù)學(xué)習(xí)即學(xué)習(xí)的目標(biāo)和結(jié)果為函數(shù)，或者說是為了獲得函數(shù)的一種學(xué)習(xí)。典型的函數(shù)學(xué)習(xí)有神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)和統(tǒng)計(jì)學(xué)習(xí)中的監(jiān)督學(xué)習(xí)。

5.基于學(xué)習(xí)目標(biāo)的分類(4)類別學(xué)習(xí)即學(xué)習(xí)的目標(biāo)和結(jié)果為對象類，或者說是為了獲得類別的一種學(xué)習(xí)。典型的類別學(xué)習(xí)有無監(jiān)督學(xué)習(xí)。(5)貝葉斯網(wǎng)絡(luò)學(xué)習(xí)即學(xué)習(xí)的目標(biāo)和結(jié)果是貝葉斯網(wǎng)絡(luò)，或者說是為了獲得貝葉斯網(wǎng)絡(luò)的一種學(xué)習(xí)。其又可分為結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)。

其他提法：

深度學(xué)習(xí)、遷移學(xué)習(xí)、半監(jiān)督學(xué)習(xí)、集成學(xué)習(xí)、對偶學(xué)習(xí)、稀疏學(xué)習(xí)、懶惰學(xué)習(xí)、概率學(xué)習(xí)、PAC（ProbablyApproximatelyCorrect）學(xué)習(xí)、在線學(xué)習(xí)、分布式學(xué)習(xí)、...

9.2幾種典型的（符號(hào)）學(xué)習(xí)方法9.2.1記憶學(xué)習(xí)

記憶學(xué)習(xí)也稱死記硬背學(xué)習(xí)或機(jī)械學(xué)習(xí)。這種學(xué)習(xí)方法不要求系統(tǒng)具有對復(fù)雜問題求解的能力，也就是沒有推理技能，系統(tǒng)的學(xué)習(xí)方法就是直接記錄問題有關(guān)的信息，然后檢索并利用這些存儲(chǔ)的信息來解決問題。

記憶學(xué)習(xí)方法簡單,但學(xué)習(xí)系統(tǒng)需要幾種能力：

(1)能實(shí)現(xiàn)有組織的存儲(chǔ)信息。

(2)能進(jìn)行信息綜合。

(3)能控制檢索方向

9.2.2示例學(xué)習(xí)

示例學(xué)習(xí)也稱實(shí)例學(xué)習(xí),它是一種歸納學(xué)習(xí)。示例學(xué)習(xí)是從若干實(shí)例(包括正例和反例)中歸納出一般概念或規(guī)則的學(xué)習(xí)方法。圖9-4第一個(gè)拱橋的語義網(wǎng)絡(luò)圖9-5第二個(gè)拱橋的語義網(wǎng)絡(luò)圖9-6學(xué)習(xí)程序歸納出的語義網(wǎng)絡(luò)圖9-7拱橋概念的語義網(wǎng)絡(luò)

例9-1

假設(shè)示例空間中有橋牌中"同花"概念的兩個(gè)示例:

示例1：

花色(c1，梅花)∧花色(c2，梅花)∧花色(c3，梅花)∧花色(c4，梅花)→同花(c1，c2，c3，c4)

示例2：

花色(c1，紅桃)∧花色(c2，紅桃)∧花色(c3，紅桃)∧花色(c4，紅桃)→同花(c1，c2，c3，c4)

學(xué)習(xí)得到的關(guān)于同花的一般性規(guī)則:

花色(c1，x)∧花色(c2，x)∧花色(c3，x)∧花色(c4，x)→同花(c1，c2，c3，c4)9.2.3演繹學(xué)習(xí)

演繹學(xué)習(xí)是基于演繹推理的一種學(xué)習(xí)。演繹推理是一種保真變換，即若前提真則推出的結(jié)論也為真。在演繹學(xué)習(xí)中，學(xué)習(xí)系統(tǒng)由給定的知識(shí)進(jìn)行演繹的保真推理，并存儲(chǔ)有用的結(jié)論。例如，當(dāng)系統(tǒng)能證明

A→B且B→C，則可得到規(guī)則A→C，那么以后再要求證C，就不必再通過規(guī)則A→B和B→C去證明，而直接應(yīng)用規(guī)則A→C即可。演繹學(xué)習(xí)包括知識(shí)改造、知識(shí)編譯、產(chǎn)生宏操作、保持等價(jià)的操作和其他保真變換。9.2.4類比學(xué)習(xí)類比學(xué)習(xí)的過程包括以下主要步驟：(1)回憶與聯(lián)想即當(dāng)遇到新情況或新問題時(shí)，先通過回憶與聯(lián)想，找出與之相似的已經(jīng)解決了的有關(guān)問題，以獲得有關(guān)知識(shí)；(2)建立對應(yīng)關(guān)系即建立相似問題知識(shí)和求解問題之間的對應(yīng)關(guān)系，以獲得求解問題的知識(shí)；(3)驗(yàn)證與歸納即檢驗(yàn)所獲知識(shí)的有效性，如發(fā)現(xiàn)有錯(cuò)，就重復(fù)上述步驟進(jìn)行修正，直到獲得正確的知識(shí)。對于正確的知識(shí)，經(jīng)過推廣、歸納等過程取得一般性知識(shí)。

設(shè)對象的知識(shí)是用框架集來表示，則類比學(xué)習(xí)可描述為把原框架中若干個(gè)槽的值傳遞給另一個(gè)目標(biāo)框架的一些槽中去，

案例（范例）學(xué)習(xí)就是一種典型的類比學(xué)習(xí)。案例學(xué)習(xí)利用問題之間的某種相似關(guān)系，將已有成功案例的參數(shù)、模型、或者方法等用于解決類似的問題。這方面已有不少成功的案例。

近年來在神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)中興起的遷移學(xué)習(xí)（transferlearning）也是一種類比學(xué)習(xí)。9.2.5解釋（分析）學(xué)習(xí)

解釋學(xué)習(xí)（Explanation-BasedLearning,EBL）就是只用一個(gè)實(shí)例，通過運(yùn)用領(lǐng)域知識(shí)，對實(shí)例的詳細(xì)分析來構(gòu)造解釋結(jié)構(gòu)，然后對解釋進(jìn)行推廣而得到一個(gè)關(guān)于實(shí)例的更一般性描述的學(xué)習(xí)方法。解釋學(xué)習(xí)的一般框架是：

給定：領(lǐng)域知識(shí)、目標(biāo)概念、訓(xùn)練實(shí)例和操作性準(zhǔn)則。

找出：滿足操作性準(zhǔn)則的關(guān)于目標(biāo)概念的充分條件。解釋學(xué)習(xí)的學(xué)習(xí)過程是：首先運(yùn)用領(lǐng)域知識(shí)找出訓(xùn)練實(shí)例為什么是目標(biāo)概念的證明（即解釋），然后按操作性準(zhǔn)則對解釋進(jìn)行推廣，從而得出關(guān)于目標(biāo)概念的學(xué)習(xí)描述。假設(shè)要學(xué)習(xí)的目標(biāo)概念是：

年青人總比年紀(jì)大的人更充滿活力。并且已知如下事實(shí)：(1)一個(gè)實(shí)例：張三比他的父親更充滿活力。(2)一組領(lǐng)域知識(shí)：假設(shè)這一組領(lǐng)域知識(shí)能證明給出的實(shí)例就是目標(biāo)概念的例子。由解釋學(xué)習(xí)，可得出結(jié)論：

任何一個(gè)兒子都比他的父親更充滿活力。9.2.6發(fā)現(xiàn)學(xué)習(xí)

發(fā)現(xiàn)學(xué)習(xí)則是系統(tǒng)直接從（數(shù)據(jù)）環(huán)境中歸納總結(jié)出規(guī)律性知識(shí)的一種學(xué)習(xí)。即發(fā)現(xiàn)學(xué)習(xí)是指機(jī)器獲取知識(shí)無須外部擁有該知識(shí)的實(shí)體的幫助，甚至蘊(yùn)含在客觀現(xiàn)象中的這類知識(shí)至今尚未被人所知，因此發(fā)現(xiàn)學(xué)習(xí)也是一種歸納學(xué)習(xí)，而且是一種高級的學(xué)習(xí)過程（這與心理學(xué)中的發(fā)現(xiàn)學(xué)習(xí)概念是一致的）。它要求系統(tǒng)具有復(fù)雜的問題求解能力，包括概念聚類、結(jié)構(gòu)分類、數(shù)據(jù)擬合、建立系統(tǒng)行為等。下面僅就這方面的研究作一點(diǎn)簡要介紹。9.3決策樹學(xué)習(xí)

1．什么是決策樹決策樹(decisiontree)也稱判定樹，它是由對象的若干屬性、屬性值和有關(guān)決策組成的一棵樹。其中的節(jié)點(diǎn)為屬性（一般為語言變量），分枝為相應(yīng)的屬性值（一般為語言值）。從同一節(jié)點(diǎn)出發(fā)的各個(gè)分枝之間是邏輯“或”關(guān)系；根節(jié)點(diǎn)為對象的某一個(gè)屬性；從根節(jié)點(diǎn)到每一個(gè)葉子節(jié)點(diǎn)的所有節(jié)點(diǎn)和邊，按順序串連成一條分枝路徑，位于同一條分枝路徑上的各個(gè)“屬性-值”對之間是邏輯“與”關(guān)系，葉子節(jié)點(diǎn)為這個(gè)與關(guān)系的對應(yīng)結(jié)果，即決策。例9-2

下圖是機(jī)場指揮臺(tái)關(guān)于飛機(jī)起飛的簡單決策樹。例9-3

右圖是一個(gè)描述“兔子”概念的決策樹。

9.3.2怎樣學(xué)習(xí)決策樹

決策樹學(xué)習(xí)的基本方法和步驟：首先，選取一個(gè)屬性，按這個(gè)屬性的不同取值對實(shí)例集進(jìn)行分類；并以該屬性作為根節(jié)點(diǎn)，以這個(gè)屬性的諸取值作為根節(jié)點(diǎn)的分枝，進(jìn)行畫樹。然后，考察所得的每一個(gè)子類，看其中的實(shí)例的結(jié)論是否完全相同。如果完全相同，則以這個(gè)相同的結(jié)論作為相應(yīng)分枝路徑末端的葉子節(jié)點(diǎn)；否則，選取一個(gè)非父節(jié)點(diǎn)的屬性，按這個(gè)屬性的不同取值對該子集進(jìn)行分類，并以該屬性作為節(jié)點(diǎn)，以這個(gè)屬性的諸取值作為節(jié)點(diǎn)的分枝，繼續(xù)進(jìn)行畫樹。如此繼續(xù)，直到所分的子集全都滿足：實(shí)例結(jié)論完全相同，而得到所有的葉子節(jié)點(diǎn)為止。

●決策樹學(xué)習(xí)舉例設(shè)表9-1所示的是某保險(xiǎn)公司的汽車駕駛保險(xiǎn)類別劃分的部分事例。我們將這張表作為一個(gè)實(shí)例集，用決策樹學(xué)習(xí)來歸納該保險(xiǎn)公司的汽車駕駛保險(xiǎn)類別劃分規(guī)則。

將實(shí)例集簡記為S={(1,C),(2,C),(3,C),(4,B),(5,A),(6,A),(7,C),(8,B),(9,A),(10,A),(11,B),(12,B)}

其中每個(gè)元組表示一個(gè)實(shí)例，前面的數(shù)字為實(shí)例序號(hào)，后面的字母為實(shí)例的決策項(xiàng)保險(xiǎn)類別。

用“小”“中”“大”分別代表“＜21”“≥21且≤25”“＞25”

這三個(gè)年齡段。

對于S，我們按屬性“性別”的不同取值將其分類。由表9.1可見，這時(shí)S應(yīng)被分類為兩個(gè)子集：S1={(3,C),(4,B),(7,C),(8,B),(11,B),(12,B)}S2={(1,C),(2,C),(5,A),(6,A),(9,A),(10,A)}

于是，我們得到以性別作為根節(jié)點(diǎn)的部分決策樹（見下圖）。

決策樹生成過程

決策樹生成過程

決策樹生成過程

決策樹生成過程最后生成的決策樹

由決策樹所得的規(guī)則集：①女性且年齡在25歲以上，則給予A類保險(xiǎn)；②女性且年齡在21歲到25歲之間，則給予A類保險(xiǎn)；③女性且年齡在21歲以下，則給予C類保險(xiǎn)；④男性且年齡在25歲以上，則給予B類保險(xiǎn)；⑤男性且年齡在21歲到25歲之間且未婚，則給予C類保險(xiǎn)；⑥男性且年齡在21歲到25歲之間且已婚，則給予B類保險(xiǎn)；⑦男性且年齡在21歲以下且未婚，則給予C類保險(xiǎn)；⑧男性且年齡在21歲以下且已婚，則給予B類保險(xiǎn)。

9.3.3

ID3算法

ID3算法是一個(gè)經(jīng)典的決策樹學(xué)習(xí)算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵為度量，用于決策樹節(jié)點(diǎn)的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值變成最小的屬性，以構(gòu)造一棵熵值下降最快的決策樹，到葉子節(jié)點(diǎn)處的熵值為0。此時(shí)，每個(gè)葉子節(jié)點(diǎn)對應(yīng)的實(shí)例集中的實(shí)例屬于同一類。

1.信息熵和條件熵

設(shè)S是一個(gè)實(shí)例集(S也可以是子實(shí)例集),A為S中實(shí)例的一個(gè)屬性。H(S)和H(S|A)分別稱為實(shí)例集S的信息熵和條件熵,其計(jì)算公式如下:

其中,μi(i=1,2,…,n)為S中各實(shí)例所有可能的結(jié)論；lb即log2。

其中,ak(k=1,2,…,m)為屬性A的取值,Sak為按屬性A對實(shí)例集S進(jìn)行分類時(shí)所得諸子類中與屬性值ak對應(yīng)的那個(gè)子類。

2.基于條件熵的屬性選擇對于一個(gè)待分類的實(shí)例集S，先分別計(jì)算各可取屬性Aj(j=1,2,…,l)的條件熵H(S|Aj)，然后取其中條件熵最小的屬性As作為當(dāng)前節(jié)點(diǎn)。例如對于上例，當(dāng)?shù)谝淮螌?shí)例集S進(jìn)行分類時(shí)，可選取的屬性有：性別、年齡段和婚狀。先分別計(jì)算S的條件熵。按性別劃分,實(shí)例集S被分為兩個(gè)子類:S男={(3,C),(4,B),(7,C),(8,B),(11,B),(12,B)}

S女

={(1,C),(2,C),(5,A),(6,A),(9,A),(10,A)}從而,對子集S男而言,對子集S女而言,于是,由公式(9-1)有:又

將以上3式代入公式(9-2)得:用同樣的方法可求得:可見,條件熵H(S|性別)為最小,所以,應(yīng)取“性別”這一屬性對實(shí)例集進(jìn)行分類,即以“性別”作為決策樹的根節(jié)點(diǎn)。

9.3.4決策樹學(xué)習(xí)的發(fā)展決策樹學(xué)習(xí)是一種很早就出現(xiàn)的歸納學(xué)習(xí)方法，至今仍然在不斷發(fā)展著。據(jù)文獻(xiàn)記載，20世紀(jì)60年代初的“基本的感知器”（ElementaryPerceiverandMemorizer,EPAM）中就使用了決策樹學(xué)習(xí)。稍后的概念學(xué)習(xí)系統(tǒng)CLS則使用啟發(fā)式的前瞻方法來構(gòu)造決策樹。繼1979年的ID3算法之后，人們又于1986、1988年相繼提出了ID4和ID5算法。1993年J.R.Quinlan則進(jìn)一步將ID3發(fā)展成C4.5算法。另一類著名的決策樹學(xué)習(xí)算法稱為CART（ClassificationandRegressionTrees）。隨著決策樹算法的廣泛應(yīng)用，包括C4.5和CART的各種算法得到進(jìn)一步改進(jìn)。例如：多變量決策樹算法、將遺傳算法、神經(jīng)網(wǎng)絡(luò)和C4.5相結(jié)合的GA-NN-C4.5算法和SVM決策樹算法等。這些改進(jìn)算法結(jié)合各種方案的優(yōu)勢，以獲得更合理的分類效果和更通用的決策規(guī)則。

9.4強(qiáng)化學(xué)習(xí)9.4.1簡單原理強(qiáng)化學(xué)習(xí)（reinforcementlearning，亦稱增強(qiáng)學(xué)習(xí)）是針對智能機(jī)器人或更一般的智能體（Agent）在與環(huán)境交互的過程中獲得最優(yōu)動(dòng)作決策和最優(yōu)行動(dòng)策略（policy，即最優(yōu)動(dòng)作序列）的一種機(jī)器學(xué)習(xí)方法。

強(qiáng)化學(xué)習(xí)所解決的一類問題可簡單描述如下：

（1）如圖9-16所示，設(shè)機(jī)器人R在某個(gè)環(huán)境E中工作，E有若干個(gè)不同的狀態(tài)s1,s2,…sn，相鄰兩個(gè)狀態(tài)si與sj之間可通過R的某一動(dòng)作a相聯(lián)系或轉(zhuǎn)換，即在狀態(tài)si下機(jī)器人R執(zhí)行動(dòng)作a后環(huán)境E的狀態(tài)就變?yōu)闋顟B(tài)sj。（2）設(shè)機(jī)器人R要從某個(gè)起始狀態(tài)ss到達(dá)目標(biāo)狀態(tài)sg（假設(shè)從E的任一狀態(tài)s出發(fā)都能到達(dá)目標(biāo)狀態(tài)sg），但他并不知道在當(dāng)前狀態(tài)下該做哪一個(gè)動(dòng)作（即每一步該如何走）才能最快到達(dá)目標(biāo)sg。（3）所幸的是R執(zhí)行一個(gè)動(dòng)作之后，環(huán)境E一般會(huì)立即對其作出評判，給R反饋一個(gè)獎(jiǎng)/懲（reward）值。反饋獎(jiǎng)/懲值的原則和做法是：如果在當(dāng)前狀態(tài)下機(jī)器人R所做的一個(gè)動(dòng)作是在到達(dá)目標(biāo)狀態(tài)sg的正確“路徑”或“方向”上，則就給R反饋一個(gè)正分值，作為“獎(jiǎng)賞”；如果這個(gè)動(dòng)作不在正確“路徑”和“方向”上甚至在錯(cuò)誤的“路徑”或“方向”上，就反饋一個(gè)0值或負(fù)分值，作為“懲罰”。機(jī)器人R與環(huán)境E的這種交互如圖9-17所示。

（4）問題：在與環(huán)境的交互過程中，機(jī)器人R如何能得到一系列最優(yōu)動(dòng)作決策而形成一個(gè)從起始狀態(tài)ss到達(dá)目標(biāo)狀態(tài)sg的最優(yōu)行動(dòng)策略，即一個(gè)最優(yōu)動(dòng)作序列？由圖9-16不難看出，這實(shí)際上就是對任一非目標(biāo)狀態(tài)s，要選擇其下的一個(gè)有利于盡快到達(dá)目標(biāo)狀態(tài)的最優(yōu)動(dòng)作a。用數(shù)學(xué)語言來表述，就是要構(gòu)造環(huán)境E的狀態(tài)集合S到機(jī)器人R的動(dòng)作集合A的一個(gè)映射

：S→A，a=

(s)使得對于任一狀態(tài)s

S，都有一個(gè)最優(yōu)動(dòng)作a

A與之對應(yīng)。例如，下面圖9-18所示的就是一個(gè)這樣的映射

：

(s1,a11),(s2,a22),(s3,a31),(s4,a42),(s5,a51)9.4.2價(jià)值函數(shù)，Q函數(shù)和Q學(xué)習(xí)算法1.價(jià)值函數(shù)

稱為策略

的價(jià)值函數(shù)。它定義了遵循策略

，Agent在狀態(tài)st下所獲得的關(guān)于相應(yīng)動(dòng)作a的（折算）積累獎(jiǎng)/懲值。

*=argmax

V

(s)(

s)稱為最優(yōu)策略。將最優(yōu)策略

*的價(jià)值函數(shù)記為V*(s)。

2.Q函數(shù)

用r(s,a)標(biāo)記狀態(tài)s下動(dòng)作a的即時(shí)獎(jiǎng)/懲值，用s’

標(biāo)記狀態(tài)s下由動(dòng)作a產(chǎn)生的新狀態(tài)，用a’

標(biāo)記狀態(tài)s’下的動(dòng)作。令

Q(s,a)=r(s,a)+

maxa’(s’,a’)稱為Q函數(shù)，其中0

<1為一常數(shù)，稱為折算因子。用Q’來表示學(xué)習(xí)器對實(shí)際Q函數(shù)的估計(jì)，或者說假設(shè)，并用一個(gè)大表表示Q’，其中為每一個(gè)狀態(tài)-動(dòng)作對(s,a)設(shè)置了一個(gè)表項(xiàng)，用來存貯Q’(s,a)的值，即對未知的Q(s,a)值的假設(shè)。此表可被初始化為隨機(jī)值（一般被置為0）。

3.Q學(xué)習(xí)（Q-learning）算法

舉例

從帶箭頭實(shí)線及其方向可以看出，第一輪學(xué)習(xí)時(shí)Agent首先選取s21為當(dāng)前狀態(tài)，并選向右的動(dòng)作執(zhí)行，于是，Agent進(jìn)入狀態(tài)s22，然后用下式更新狀態(tài)s21的Q’值

Q’(s21,aright)=r(s,aright)+

=

0+

0.9max{0,0,0}