第4篇學習與發(fā)現(xiàn)

『導語』

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

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

第9章機器學習：符號學習與交互學習

9.1機器學習概述

9.2幾種經(jīng)典的（符號）學習方法

9.3決策樹學習

9.4強化學習

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

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

1.基于學習途徑的分類(1)符號學習

模擬人腦宏觀心理級學習過程，以認知心理學原理為基礎，以符號數(shù)據(jù)為輸入，以符號運算為方法，用推理過程在圖或狀態(tài)空間中搜索，學習的目標為概念或規(guī)則等。符號學習的典型方法有：記憶學習、示例學習、演繹學習、類比學習、規(guī)則學習、解釋學習等。(2)神經(jīng)網(wǎng)絡學習（或連接學習）模擬人腦的微觀生理級學習過程，以腦和神經(jīng)科學原理為基礎，以人工神經(jīng)網(wǎng)絡為拓撲結(jié)構模型，以數(shù)值數(shù)據(jù)為輸入，以數(shù)值運算為方法，用迭代過程在權向量空間中搜索，學習的目標為函數(shù)或類別。典型的連接學習有權值修正學習、拓撲結(jié)構學習。(3)統(tǒng)計學習運用統(tǒng)計、概率及其他數(shù)學理論和方法對樣本數(shù)據(jù)進行處理，從中發(fā)現(xiàn)相關模式和規(guī)律的一種機器學習方法。(4)交互學習智能體通過與環(huán)境的交互而獲得相關知識和機能的一種機器學習方法。交互學習的典型方法就是強化學習（增強學習）。強化學習以環(huán)境反饋（獎/懲信號）作為輸入，以統(tǒng)計和動態(tài)規(guī)劃技術為指導，學習目標為最優(yōu)行動策略。

2.基于學習方法的分類

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

符號歸納學習：如目標為概念的示例學習，目標為規(guī)則的決策樹學習。

函數(shù)歸納學習：如目標為函數(shù)的統(tǒng)計學習和神經(jīng)網(wǎng)絡學習。

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

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

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

(2)

無監(jiān)督學習（unsupervisedlearning，亦稱無導師學習）

無監(jiān)督學習的樣本數(shù)據(jù)僅為一些向量(x1,x2,...,xn)（而無對應值y），其學習方法就是聚類，即把相似的對象做為一類，學習結(jié)果為數(shù)據(jù)類別（即隱藏于樣本數(shù)據(jù)中的模式（類）或結(jié)構）。無監(jiān)督學習被用于聚類問題，也可用于數(shù)據(jù)降維（dimensionalityreduction）和圖像壓縮（imagecompression）等。聚類學習和競爭學習都是典型的無監(jiān)督學習。4.

基于數(shù)據(jù)形式的分類(1)結(jié)構化學習以結(jié)構化數(shù)據(jù)為輸入，以數(shù)值計算或符號推演為方法。典型的結(jié)構化學習有神經(jīng)網(wǎng)絡學習、統(tǒng)計學習、決策樹學習、規(guī)則學習。(2)非結(jié)構化學習以非結(jié)構化數(shù)據(jù)為輸入，典型的非結(jié)構化學習有類比學習、案例學習、解釋學習、以及用于文本挖掘、圖像挖掘、Web挖掘等的學習。

5.基于學習目標的分類

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

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

其他提法：

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

9.2幾種典型的（符號）學習方法9.2.1記憶學習

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

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

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

(2)能進行信息綜合。

(3)能控制檢索方向

9.2.2示例學習

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

例9-1

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

示例1：

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

示例2：

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

學習得到的關于同花的一般性規(guī)則:

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

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

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

設對象的知識是用框架集來表示，則類比學習可描述為把原框架中若干個槽的值傳遞給另一個目標框架的一些槽中去，

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

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

解釋學習（Explanation-BasedLearning,EBL）就是只用一個實例，通過運用領域知識，對實例的詳細分析來構造解釋結(jié)構，然后對解釋進行推廣而得到一個關于實例的更一般性描述的學習方法。解釋學習的一般框架是：

給定：領域知識、目標概念、訓練實例和操作性準則。

找出：滿足操作性準則的關于目標概念的充分條件。解釋學習的學習過程是：首先運用領域知識找出訓練實例為什么是目標概念的證明（即解釋），然后按操作性準則對解釋進行推廣，從而得出關于目標概念的學習描述。假設要學習的目標概念是：

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

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

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

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

下圖是機場指揮臺關于飛機起飛的簡單決策樹。例9-3

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

9.3.2怎樣學習決策樹

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

●決策樹學習舉例設表9-1所示的是某保險公司的汽車駕駛保險類別劃分的部分事例。我們將這張表作為一個實例集，用決策樹學習來歸納該保險公司的汽車駕駛保險類別劃分規(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應被分類為兩個子集：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é)點的部分決策樹（見下圖）。

決策樹生成過程

決策樹生成過程

決策樹生成過程

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

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

9.3.3

ID3算法

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

1.信息熵和條件熵

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

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

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

2.基于條件熵的屬性選擇對于一個待分類的實例集S，先分別計算各可取屬性Aj(j=1,2,…,l)的條件熵H(S|Aj)，然后取其中條件熵最小的屬性As作為當前節(jié)點。例如對于上例，當?shù)谝淮螌嵗疭進行分類時，可選取的屬性有：性別、年齡段和婚狀。先分別計算S的條件熵。按性別劃分,實例集S被分為兩個子類: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|性別)為最小,所以,應取“性別”這一屬性對實例集進行分類,即以“性別”作為決策樹的根節(jié)點。

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

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

強化學習所解決的一類問題可簡單描述如下：

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

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

：S→A，a=

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

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

A與之對應。例如，下面圖9-18所示的就是一個這樣的映射

：

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

稱為策略

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

，Agent在狀態(tài)st下所獲得的關于相應動作a的（折算）積累獎/懲值。

*=argmax

V

(s)(

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

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

2.Q函數(shù)

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

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

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

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

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

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

3.Q學習（Q-learning）算法

舉例

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

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

=

0+

0.9max{0,0,0}