第5章機(jī)器學(xué)習(xí)與知識發(fā)現(xiàn)（一）

5.1概述

5.2基本原理與分類

5.3符號學(xué)習(xí)

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

延伸學(xué)習(xí)導(dǎo)引

6.1概述學(xué)習(xí)是系統(tǒng)積累經(jīng)驗或運(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)中二者幾乎是同義語。當(dāng)今人工智能中的機(jī)器學(xué)習(xí)主要指機(jī)器對自身行為的修正或性能的改善（這類似于人類的技能訓(xùn)練和對環(huán)境的適應(yīng)）和機(jī)器對客觀規(guī)律的發(fā)現(xiàn)（這類似于人類的科學(xué)發(fā)現(xiàn)）。機(jī)器學(xué)習(xí)從20世紀(jì)50年代就開始被研究，現(xiàn)在已取得了不少成就，并分化出了許多研究方向，主要有符號學(xué)習(xí)、連接學(xué)習(xí)（即神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)）、統(tǒng)計學(xué)習(xí)和交互學(xué)習(xí)等。

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

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

機(jī)器學(xué)習(xí)原理圖解15.2.3機(jī)器學(xué)習(xí)的分類

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

模擬人腦的宏觀心理級學(xué)習(xí)過程，以認(rèn)知心理學(xué)原理為基礎(chǔ)，以符號數(shù)據(jù)為輸入，以符號運(yùn)算為方法，用推理過程在圖或狀態(tài)空間中搜索，學(xué)習(xí)的目標(biāo)為概念或規(guī)則等。符號學(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)計學(xué)習(xí)運(yùn)用統(tǒng)計、概率及其他數(shù)學(xué)理論和方法對樣本數(shù)據(jù)進(jìn)行處理，從中發(fā)現(xiàn)相關(guān)模式和規(guī)律的一種機(jī)器學(xué)習(xí)方法。(4)交互學(xué)習(xí)智能體通過與環(huán)境的交互而獲得相關(guān)知識和機(jī)能的一種機(jī)器學(xué)習(xí)方法。交互學(xué)習(xí)的典型方法就是強(qiáng)化學(xué)習(xí)（增強(qiáng)學(xué)習(xí)）。強(qiáng)化學(xué)習(xí)以環(huán)境反饋（獎/懲信號）作為輸入，以統(tǒng)計和動態(tài)規(guī)劃技術(shù)為指導(dǎo)，學(xué)習(xí)目標(biāo)為最優(yōu)行動策略。

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

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

函數(shù)歸納學(xué)習(xí)：如目標(biāo)為函數(shù)的統(tǒng)計學(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í)、基于實例的學(xué)習(xí)、遷移學(xué)習(xí)。(4)分析學(xué)習(xí)利用先驗知識和演繹推理來擴(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)和一個對應(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ù)模型，采用迭代計算的方法，來擬合相應(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ù)值計算或符號推演為方法。典型的結(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é)習(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)計學(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í)、...

5.3符號學(xué)習(xí)5.3.1概述符號學(xué)習(xí)是一種模擬人腦的宏觀心理級學(xué)習(xí)過程，以認(rèn)知心理學(xué)原理為基礎(chǔ)，以符號數(shù)據(jù)為輸入，以符號運(yùn)算亦即邏輯推理為方法，學(xué)習(xí)的目標(biāo)為語言表述的概念或規(guī)則等。符號學(xué)習(xí)的典型方法有：記憶學(xué)習(xí)、示例學(xué)習(xí)、演繹學(xué)習(xí)、類比學(xué)習(xí)、規(guī)則學(xué)習(xí)、解釋學(xué)習(xí)等。5.3.2記憶學(xué)習(xí)

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

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

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

(3)能控制檢索方向。5.3.3示例學(xué)習(xí)

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

例6-1

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

示例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)6.3.4演繹學(xué)習(xí)

演繹學(xué)習(xí)是基于演繹推理的一種學(xué)習(xí)。演繹推理是一種保真變換，即若前提真則推出的結(jié)論也為真。在演繹學(xué)習(xí)中，學(xué)習(xí)系統(tǒng)由給定的知識進(jìn)行演繹的保真推理，并存儲有用的結(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í)包括知識改造、知識編譯、產(chǎn)生宏操作、保持等價的操作和其他保真變換。6.3.5類比學(xué)習(xí)類比學(xué)習(xí)的過程包括以下主要步驟：(1)回憶與聯(lián)想即當(dāng)遇到新情況或新問題時，先通過回憶與聯(lián)想，找出與之相似的已經(jīng)解決了的有關(guān)問題，以獲得有關(guān)知識；(2)建立對應(yīng)關(guān)系即建立相似問題知識和求解問題之間的對應(yīng)關(guān)系，以獲得求解問題的知識；(3)驗證與歸納即檢驗所獲知識的有效性，如發(fā)現(xiàn)有錯，就重復(fù)上述步驟進(jìn)行修正，直到獲得正確的知識。對于正確的知識，經(jīng)過推廣、歸納等過程取得一般性知識。6.3.6決策樹學(xué)習(xí)

1．什么是決策樹

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

下圖所示是機(jī)場指揮臺關(guān)于飛機(jī)起飛的簡單決策樹。

例5-3

下圖是一個描述“兔子”概念的決策樹。

2.

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

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

決策樹學(xué)習(xí)舉例

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

將實例集簡記為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)}

其中每個元組表示一個實例，前面的數(shù)字為實例序號，后面的字母為實例的決策項保險類別。

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

這三個年齡段。

對于S，我們按屬性“性別”的不同取值將其分類。由表9.1可見，這時S應(yīng)被分類為兩個子集：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類保險；②女性且年齡在21歲到25歲之間，則給予A類保險；③女性且年齡在21歲以下，則給予C類保險；④男性且年齡在25歲以上，則給予B類保險；⑤男性且年齡在21歲到25歲之間且未婚，則給予C類保險；⑥男性且年齡在21歲到25歲之間且已婚，則給予B類保險；⑦男性且年齡在21歲以下且未婚，則給予C類保險；⑧男性且年齡在21歲以下且已婚，則給予B類保險。

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

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

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

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

：S→A，a=

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

S，都有一個最優(yōu)動作a

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

：

(s1,a11),(s2,a22),(s3,a31),(s4,a42),(s5,a51)5.4.2

Q學(xué)習(xí)算法

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

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

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

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

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

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

舉例

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

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

=

0+

0.9max{0,0,0}（r(s,aright)=0,

=0.9）=

0然后，Agent將s22作為當(dāng)前狀態(tài)，并選向右的動作執(zhí)行，于是，Agent進(jìn)入狀態(tài)s23，接著用下式更新狀態(tài)s22的Q’值

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

=

0+

0.9max{0,100}=

90然后，Agent將s23作為當(dāng)前狀態(tài)，并選向上的動作執(zhí)行，于是，Agent進(jìn)入狀態(tài)s13。由于已是目標(biāo)