機器學習基礎(chǔ)教程課件：其他典型機器學習方法概述

其他典型機器學習方法概述

本章主要對一些新興典型的機器學習方法進行概略性介紹，希望讀者能對這些機器學習方法有個大致了解。對于這些機器學習方法首先應該理解其基本思路，如果擁有足夠的數(shù)學基礎(chǔ)，在理解的基礎(chǔ)上能夠逐漸內(nèi)化，并對其加以應用的話那將是事半功倍。緒論：8.1隱含馬爾科夫模型8.2蒙特卡洛方法8.3組合多學習器8.4近似推斷8.5增強學習方法8.6深度學習方法概述8.1隱含馬爾科夫模型

馬爾科夫過程與馬爾科夫鏈密切相關(guān)，是由俄國數(shù)學家馬爾科夫在1907年提出的。馬爾科夫過程的主要特點是無后效性、或無記憶性。若有一隨機過程

，如果對于任意的

，其當前的分布函數(shù)只與當前的狀態(tài)有關(guān)，而與在此之前的狀態(tài)沒有關(guān)系，即：

如隨機變量為離散型的隨機變量，則也有：

從起始狀態(tài)開始到終端狀態(tài)經(jīng)過全部這么多的狀態(tài)后，整個過程進行完，所以有全部的狀態(tài)轉(zhuǎn)移概率之和為1。即：

（8.4）

另外，馬爾科夫過程也是一個隨機過程，因此，我們無法確定究竟哪個狀態(tài)才是起始狀態(tài)，只能得到該狀態(tài)作為起始狀態(tài)的概率。這樣，可以將各個狀態(tài)作為起始狀態(tài)的情況列成矩陣，稱為轉(zhuǎn)移概率矩陣。

狀態(tài)轉(zhuǎn)移的情況還可以用圖形表示，如圖8.1所示（并未完全標出）。圖8.1馬爾科夫過程轉(zhuǎn)移概率示意圖p12p11P21p44p22p23p33p34p32S3p413p43p14S4S2S1則對于一個可觀測序列，其概率為：

（8.6）

所謂的隱含馬爾科夫模型（HMM，HiddenMarkovModel）是指在整個隨機發(fā)生的序列過程中，狀態(tài)是不能觀測的，所以稱之為“隱含”。但是在這個過程中，最終發(fā)生的結(jié)果是可以被觀測和記錄的?？梢詫懗扇缦滦问剑?/p>

（8.7）

式（8.7）表示在過程處于狀態(tài)X時，能夠觀測到的試驗結(jié)果ri的概率。

在很多情況下，雖然過程處于不同的狀態(tài)，但是可以產(chǎn)生相同的試驗結(jié)果，而只不過其發(fā)生的概率不同罷了。

根據(jù)模型（M）、狀態(tài)（X）和觀測試驗結(jié)果（R）這三個方面就構(gòu)成了基于隱含馬爾科夫模型學習的三個基本問題：一、給定模型，求出在不同狀態(tài)下試驗結(jié)果的概率：二、給定模型及試驗結(jié)果，估計能夠產(chǎn)生這種試驗結(jié)果的最可能的情況，即最大概率的狀態(tài)：三、給定試驗結(jié)果，求出能夠得到這種結(jié)果的最可能的模型，即最可能的模型：

對于模型M，設(shè)從起始時刻開始到時刻t（此時狀態(tài)為Xi）的概率為：

（8.8）

式中，為試驗結(jié)果序列。先得到其初始值：（8.9）

式中，Si為第i個狀態(tài)出現(xiàn)的初始概率。式（8.9）得到了在第一次試驗中，狀態(tài)為第i個狀態(tài)的，試驗結(jié)果

的概率。由此進行遞歸運算可以得到：

（8.10）

這樣一來，按照前向的計算方法就可以得出整個試驗結(jié)果序列的概率：

接著可以進行后向算法。計算從時刻t+1開始到時刻T的概率。

（8.13）

隱含馬爾可夫模型的第二個問題是：對于給定模型及試驗結(jié)果，求出能夠產(chǎn)生這種結(jié)果的最大概率的狀態(tài)。設(shè)為給定模型與試驗結(jié)果的、t時刻的、狀態(tài)為

概率，則有：

從式（8.14）中可以看出，這里也再次引用了前向/后向的計算方法。在進行狀態(tài)的求取過程中可以使用線性動態(tài)規(guī)劃的方法。由于有線性的基本假設(shè)，可以在每一步?jīng)Q策時，選擇最優(yōu)。

設(shè)在馬爾科夫過程中，由狀態(tài)Xi轉(zhuǎn)移到狀態(tài)Xj的頻度為

，共有N個狀態(tài)，則可得其狀態(tài)轉(zhuǎn)移矩陣為：

（8.15）

而過程狀態(tài)隱藏狀態(tài)為Xi時，且試驗結(jié)果為Rs的頻度為，共有M個狀態(tài)，那么狀態(tài)概率矩陣為：

（8.16）

對于非“隱含”馬爾科夫過程，這樣的處理無疑是非常合適的，但是對于隱含馬爾科夫過程，無法獲取中間狀態(tài)的情況，就不能再使用這種方法來進行處理。

這里介紹一種基于期望最大化的算法（EM，Expectation-Maximizationalgorithm），即——Baum-Welch算法。整個算法分為兩個部分：第一步是先計算期望，即E；第二步在此基礎(chǔ)上使得期望達到最大化，即M。

第一步，先求期望。設(shè)M為模型參數(shù)，R為試驗結(jié)果，X為狀態(tài)；則基于條件概率的期望為：

（8.18）

第二步，在此基礎(chǔ)上求出上式的最大值，所得到的模型即為所求。

（8.19）8.2蒙特卡洛方法

蒙特卡洛（MonteCarlo）是摩納哥公國的一座城市，該城市以博彩業(yè)而聞名于世。而蒙特卡洛方法是一種統(tǒng)計模擬的方法，它使用隨機數(shù)來解決計算的問題，因此在某種程度上帶有“賭博、取巧”的意味，因此以之命名。蒙特卡羅方法由美國科學家S.M.烏拉姆和J.馮·諾伊曼首先提出。

蒙特卡洛方法的核心是建立在數(shù)據(jù)均勻分布的基礎(chǔ)上的，因此上可以看作是傳統(tǒng)頻度分析方法的回歸。

如圖8.2所示。在邊長為2R的正方形內(nèi)切一個半徑為R的圓。那么易知正方形面積為：

而內(nèi)切圓的面積為:

則有：(8.20)圖8.2蒙特卡洛方法求圓周率示意圖圖8.3蒙特卡洛方法求定積分示意圖

然后開始對整個區(qū)域開始進行“撒點”，有的文獻也稱為“投針”，即隨機地、均勻地向整個區(qū)域散布隨機點。在均勻分布的前提下，位于圓內(nèi)的點的數(shù)目和整個方形區(qū)域的點數(shù)目之比應該接近于式（8.20）。當撒點的數(shù)目越多，則越接近于真實值?？紤]到涉及到面積的比值，還可以非常自然地推廣到關(guān)于定積分的求取方法。如圖8.3所示，只要求取曲線下方撒點數(shù)目與全部撒點數(shù)目之比就可以了。在機器學習的算法中，還可以對上述的簡單方法進行適當?shù)耐茝V，并不僅僅局限于數(shù)據(jù)的概率分布是均勻分布這個假設(shè)。例如假設(shè)有一個參數(shù)模型的概率密度為p(x)，那么如果要求取參數(shù)x的期望值E(x)，則有：

根據(jù)概率論的基本知識，在實際的工作中可以采用期望的無偏估計值——均值來進行求取，即：

(8.21)

根據(jù)切比雪夫大數(shù)定律，如果樣本是獨立同分布的，即有：(8.22)式中，為所取樣本的總和。這也說明了只要樣本足夠大，樣本的平均值是依概率收斂到其期望值的。如果樣本的方差有界，其方差也會收斂到0，這一點也有中心極限定理保證。另外，利用這一特性還可以通過常見的正態(tài)分布來對期望的置信區(qū)間進行估計。

使用常規(guī)的取樣方法可能會有比較大的誤差，這時就不能再盲目隨機取樣。例如設(shè)置樣本的拒絕域，按照一定的規(guī)則對某些樣本進行拒絕，盡量去逼近實際的分布情況。如圖8.4所示。圖8.4帶有拒絕域的蒙特卡洛取樣示意圖

對于一個馬爾可夫鏈，如果滿足了以下幾個條件，那么馬爾可夫鏈最終會收斂于穩(wěn)定的狀態(tài)，也就是說最終會穩(wěn)定地駐留于某個狀態(tài)，而不會在發(fā)生改變。

對于馬爾可夫鏈的轉(zhuǎn)移過程可以用轉(zhuǎn)移方程來表示，在控制理論里常常稱為狀態(tài)方程：

（8.23）式中，表示轉(zhuǎn)移過后的狀態(tài)，為轉(zhuǎn)移之前的狀態(tài)，稱為狀態(tài)轉(zhuǎn)移矩陣。

從馬爾可夫鏈能夠進入穩(wěn)定狀態(tài)的表述來看，凡是進入收斂域內(nèi)的狀態(tài)，都可以表示為：（8.24）式中，分別表示進入收斂域后在狀態(tài)i和j的概率分布；則表示進入收斂域后從狀態(tài)i到狀態(tài)j、從狀態(tài)j狀態(tài)i的狀態(tài)轉(zhuǎn)移矩陣。但是通過解析方法來尋找這樣的狀態(tài)轉(zhuǎn)移矩陣是比較困難的，也就是說很難滿足式（8.24）的條件。這就需要另外尋找別的方法來確定這個狀態(tài)轉(zhuǎn)移矩陣。

由蒙特卡洛取樣的拒絕域的思路啟發(fā)，可以先引入一個修正因子，使得：

（8.25）這樣，就可以得到馬爾可夫鏈的狀態(tài)轉(zhuǎn)移矩陣：

（8.26）將修正因子的取值控制在[0,1]之間，作為一個概率值。圖8.5添加修正因子進行判別流程圖圖8.6Gibbs取樣算法流程圖

使用這種方法可以獲得馬爾可夫鏈的狀態(tài)轉(zhuǎn)移矩陣，但是在取樣過程中由于接受率比較低，因此效率比較低。為了解決這個問題，可以適當對修正因子進行線性放大、比較和調(diào)整，然后再行接受/拒絕的操作。例如，可以將修正因子取為：

（8.27）

相應的，在圖8.5所示的流程圖中只需要將接受/拒絕轉(zhuǎn)移的判別條件置換為式（8.27）即可。這種取樣方式也稱為M-H（Metropolis-Hastings）取樣。

如果數(shù)據(jù)量發(fā)生改變，例如在二維或者更高維的數(shù)據(jù)情況下，需要進行計算的時間將會變長；另外，這時還需要獲取數(shù)據(jù)的聯(lián)合分布情況。這就需要對取樣算法進行進一步地改進。以二維情況為例，設(shè)聯(lián)合概率分布函數(shù)為。對于其中一維邊緣分布相同的兩個點

、，同時考慮其條件概率，有：

（8.28）式中，為馬爾可夫鏈中狀態(tài)的概率分布，為二維數(shù)據(jù)的條件概率分布。對比式（8.29）和式（8.24）可以發(fā)現(xiàn)如果可以將條件概率分布作為馬爾科夫鏈的狀態(tài)轉(zhuǎn)移概率，就可以滿足馬爾可夫鏈的收斂條件。在二維數(shù)據(jù)情況下，得到數(shù)據(jù)取樣的另一種方法——Gibbs取樣。其流程如圖8.6所示。8.3組合多學習器

組合多學習器的組織形式一般分為兩種：一種是并行方式，一種是串行方式。

在全局型的的決策機制中需要有投票計值來進行決策，這種投票決策不是簡單的壓倒多數(shù)勝出的機制，而類似神經(jīng)網(wǎng)絡(luò)算法的一種形式，其基本拓撲結(jié)構(gòu)如圖8.7所示。圖8.7投票機制示意圖

式中，Y為決策輸出，為各個基學習器的加權(quán)系數(shù)，為各個基學習器的輸出。還可以根據(jù)實際的情況人為指定。圖8.8隨機森林算法基本架構(gòu)

串行算法主要是提升（Boosting）算法。提升算法，顧名思義，是不斷提升學習的效果。這種該算法首先訓練一組弱學習器，然后通過不斷地“提升”、加強，最終成為一個強學習器。AdaBoost算法，這是自適應（Adaptive）算法的縮寫。這種算法并要求有較大的數(shù)據(jù)集，同時弱學習的結(jié)構(gòu)也盡量簡單。除自適應提升（AdaBoost）算法外，還有一種梯度提升樹（GBT：GradientBoostingTree）在擬合（回歸）分析中的應用也很廣泛。梯度提升樹算法的主要思想是：在迭代計算的過程中沿負梯度方向進行擬合，使得損失代價函數(shù)能夠達到最小。也就是要使：（8.29）達到最小。圖8.9AdaBoost算法基本流程圖式中，為前迭代的損失代價函數(shù)，

為前一步迭代的損失代價函數(shù)；

為當前學習器函數(shù)，

為前一步機器學習函數(shù)；為所求的、能夠使損失代價函數(shù)最小化的弱學習器函數(shù)。要按照負梯度方向進行迭代，首先給出損失代價函數(shù)的負梯度形式;（8.30）

針對每一次迭代，要使得擬合過程中每個節(jié)點的輸出值最小，即：

（8.31）

最終得到強學習器：

（8.32）

在組合多學習算法中，還有一種層迭泛化（StackGeneralization）算法。這種算法主要是針對投票決策的算法。8.4近似推斷

在第三章中提到過信息熵，主要是刻畫數(shù)據(jù)或信息的“混亂”程度的。這里在給出相對熵的概念，也稱為KL散度（Kullback–Leiblerdivergence），用來描述兩個概率分布的差異性。KL散度：

(8.33)

下面來確定優(yōu)化的目標（也可也稱為性能指標函數(shù)）。先預先設(shè)定一個關(guān)于隱含變量h概率分布函數(shù),然后來對比所要求取的概率分布函數(shù)與其差異，如果能將差異最小化，就實現(xiàn)了優(yōu)化的目標了。這樣，性能指標可以寫作：

(8.34)

如果當與相當接近，甚至于完全重合時，KL散度為0。這時，式（8.34）就變?yōu)榱耍海?.35）

期望最大化算法分為兩個步驟：首先是先設(shè)定期望（E），然后再使期望最大化（M）。然后兩步交替進行迭代，最終達到要求。

第一步先設(shè)定期望。設(shè)數(shù)據(jù)集樣本為

，其隱含變量為，可觀測變量對于隱含變量的分布函數(shù)為

，則可得：（8.36）

第二步使其達到最大化。則由對數(shù)似然函數(shù)有；

式中，m為隱含變量可能的取值數(shù)目。在此基礎(chǔ)上求出能夠使得期望的對數(shù)似然函數(shù)最大化的參數(shù)

。即：然后以上兩步交替進行，最終達到優(yōu)化的參數(shù)結(jié)果。

散度的衡量有兩種方法，即

和。與矩陣乘法在一般情況下不遵從交換律一樣，這兩個散度并不相等，即：

（8.45）圖8.10變分推斷算法與期望最大化算法對比示意圖8.5增強學習方法增強學習的過程可以表述為以下的幾個要素：第一，基本決策策略（policy）?；緵Q策策略是智能體在接受到環(huán)境的狀態(tài)后，進行運算形成的決策映射。這種映射可以是確定性的決策，也可以是不確定性的。在不確定情況下，可以表示為條件概率的形式。第二，階段性的獎勵評價（Reward）。在每個決策階段或關(guān)鍵時間點時，外部的環(huán)境應該對智能體所做出的決策給出獎勵評價，從而能夠讓智能體在其后的決策中能夠進行滾動優(yōu)化。第三，外部環(huán)境與智能體決策的閉環(huán)系統(tǒng)。外部環(huán)境和智能體所做出的決策應該構(gòu)成一個閉環(huán)系統(tǒng)。外部環(huán)境為智能體提供反饋，智能體輸出決策影響環(huán)境。給出學習要求的性能指標：在此時可以使評價的性能指標達到最優(yōu)。要注意的是，這個評價的型能指標是一個積累的過程，而不是當前時刻的最優(yōu)值。也就是說，應該有：

也就是要使所有的獎勵評價之和達到最優(yōu)。在每次進行獎勵評價時，需要根據(jù)前一步的評價情況來調(diào)整給予評價的大小，即在每次評價的基礎(chǔ)上添加一個獎勵/懲罰因子：

（8.48)

這樣，就有了迭代形式：

結(jié)合性能指標式（8.46）及式（8.47）就有：

(4.50)

參考有模型增強學習時候的性能指標的更新情況式（8.50），是使用當前的值再加上一個增量的形式，即：

(8.51)

對于非確定性的情況，需要進行滑動平均處理。即：

(8.52)8.6深度學習方法概述

下面將列舉幾個深度學習的例子來說明其特點。

首先，從神經(jīng)網(wǎng)絡(luò)談起。神經(jīng)網(wǎng)絡(luò)可以說是人工智能、機器學習初步形成體系的一種學習方法。在神經(jīng)網(wǎng)絡(luò)中曾經(jīng)提到過Hopfield網(wǎng)絡(luò)。如果將Hopfield網(wǎng)絡(luò)進行進一步的改造：將網(wǎng)絡(luò)中隱含層的節(jié)點更改為隨機性的節(jié)點，也就是將輸入隱含層節(jié)點的信息并不是通過活化函數(shù)來直接給出輸出，而是輸出狀態(tài)的轉(zhuǎn)移概率，即：

(8.55)(8.56)

在網(wǎng)絡(luò)中兩個狀態(tài)出現(xiàn)的概率所對應的能量關(guān)系有：

(8.57)

如果規(guī)定了某種狀態(tài)為“期望”的狀態(tài)，還可以使用互熵（Kullback熵，CrossEntropy）來衡量實際的狀態(tài)與期望值之間的偏差程度。即：

(8.58)式中，為期望狀態(tài)的概率。網(wǎng)絡(luò)最終的平衡狀態(tài)服從玻爾茲曼（Boltzmann）分布。圖8.12玻爾茲曼機基本算法流程

受限玻爾茲曼機需要研究輸入層與隱含層之間的概率分布關(guān)系。其聯(lián)合概率分布可以由下式給出：