第5章機器學習與知識發(fā)現(xiàn)（一）

5.1概述

5.2基本原理與分類

5.3符號學習

5.4強化學習

延伸學習導引

6.1概述學習是系統(tǒng)積累經(jīng)驗或運用規(guī)律指導自己的行為或改進自身性能的過程，而發(fā)現(xiàn)則是系統(tǒng)從所接收的信息中發(fā)現(xiàn)規(guī)律的過程。學習與發(fā)現(xiàn)相輔相成，關系密切，以致在不少文獻中二者幾乎是同義語。當今人工智能中的機器學習主要指機器對自身行為的修正或性能的改善（這類似于人類的技能訓練和對環(huán)境的適應）和機器對客觀規(guī)律的發(fā)現(xiàn)（這類似于人類的科學發(fā)現(xiàn)）。機器學習從20世紀50年代就開始被研究，現(xiàn)在已取得了不少成就，并分化出了許多研究方向，主要有符號學習、連接學習（即神經(jīng)網(wǎng)絡學習）、統(tǒng)計學習和交互學習等。

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

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

機器學習原理圖解15.2.3機器學習的分類

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

模擬人腦的宏觀心理級學習過程，以認知心理學原理為基礎，以符號數(shù)據(jù)為輸入，以符號運算為方法，用推理過程在圖或狀態(tài)空間中搜索，學習的目標為概念或規(guī)則等。符號學習的典型方法有：記憶學習、示例學習、演繹學習、類比學習、規(guī)則學習、解釋學習等。(2)神經(jīng)網(wǎng)絡學習（或連接學習）模擬人腦的微觀生理級學習過程，以腦和神經(jīng)科學原理為基礎，以人工神經(jīng)網(wǎng)絡為拓撲結(jié)構(gòu)模型，以數(shù)值數(shù)據(jù)為輸入，以數(shù)值運算為方法，用迭代過程在權向量空間中搜索，學習的目標為函數(shù)或類別。典型的連接學習有權值修正學習、拓撲結(jié)構(gòu)學習。(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é)構(gòu)）。無監(jiān)督學習被用于聚類問題，也可用于數(shù)據(jù)降維（dimensionalityreduction）和圖像壓縮（imagecompression）等。聚類學習和競爭學習都是典型的無監(jiān)督學習。4.

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

其他提法：

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

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

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

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

(2)能進行信息綜合。

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

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

例6-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)6.3.4演繹學習

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

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

1．什么是決策樹

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

下圖所示是機場指揮臺關于飛機起飛的簡單決策樹。

例5-3

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

2.

怎樣學習決策樹

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

決策樹學習舉例

設表6.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類保險。

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

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

（1）如圖5-12所示，設機器人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的這種交互如圖6-13所示。

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

：S→A，a=

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

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

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

：

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

Q學習算法

用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）。

舉例

從帶箭頭實線及其方向可以看出，第一輪學習時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}（r(s,aright)=0,

=0.9）=

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

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

=

0+

0.9max{0,100}=

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