基于PGM 的態(tài)勢(shì)預(yù)測(cè)技術(shù)*

劉俊波，黃 斌，鄧 蕾

(中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041)

0 引言

機(jī)器學(xué)習(xí)[1]是現(xiàn)階段實(shí)現(xiàn)人工智能應(yīng)用的主要方法。機(jī)器學(xué)習(xí)最重要的任務(wù)是根據(jù)已觀察到的數(shù)據(jù)對(duì)感興趣的未知數(shù)據(jù)進(jìn)行估計(jì)或推測(cè)。

概率模型（probabilistic model）提供了一種描述框架，將學(xué)習(xí)任務(wù)歸結(jié)于計(jì)算變量的概率分布，即如何基于已知變量推測(cè)出未知變量的條件分布。

概率圖模型[2][3]（probabilistic graphical model）是一類用圖來(lái)表達(dá)變量相關(guān)關(guān)系的概率模型。概率圖模型大致可分為兩類：第一類是使用有向無(wú)環(huán)圖表示變量間的依賴關(guān)系，稱為有向圖模型或貝葉斯網(wǎng)；第二類是使用無(wú)向圖表示變量間的相互關(guān)系，稱為無(wú)向圖模型或馬爾可夫網(wǎng)[4]。

隱馬爾可夫模型[5]（Hidden Markov Model，簡(jiǎn)稱HMM）是結(jié)構(gòu)最簡(jiǎn)單的動(dòng)態(tài)貝葉斯網(wǎng)，它是一種著名的有向圖模型。

本文基于HMM 采用兩種方法實(shí)現(xiàn)系統(tǒng)的態(tài)勢(shì)預(yù)測(cè)。這兩種方法在不同的場(chǎng)景中預(yù)測(cè)效果良好。

1 隱馬爾可夫模型（HMM）

隱馬爾可夫模型可以計(jì)算出一個(gè)系統(tǒng)每一時(shí)刻處于各種狀態(tài)的概率以及這些狀態(tài)之間的轉(zhuǎn)移概率。

系統(tǒng)有n種互斥的狀態(tài)（狀態(tài)1，狀態(tài)2，狀態(tài)3，…），即系統(tǒng)的狀態(tài)可以構(gòu)成集合

設(shè)在t時(shí)刻系統(tǒng)的狀態(tài)為zt，它是一個(gè)離散型隨機(jī)變量。從時(shí)刻1 開始到時(shí)刻T為止，系統(tǒng)所有時(shí)刻的狀態(tài)值構(gòu)成一個(gè)隨機(jī)變量序列：

系統(tǒng)在不同時(shí)刻可以處于同一種狀態(tài)，但在任何一個(gè)時(shí)刻，系統(tǒng)只能有一種狀態(tài)。不同時(shí)刻的狀態(tài)之間是有關(guān)系的。時(shí)刻t的狀態(tài)由它之前時(shí)刻的狀態(tài)決定，這可以表示為如下的條件概率：

即在從1 到t-1 時(shí)刻系統(tǒng)的狀態(tài)值分別為z1,z2,…,zt-1的前提下，時(shí)刻t系統(tǒng)的狀態(tài)為zt的概率。如果要考慮之前所有的狀態(tài)，數(shù)學(xué)模型太復(fù)雜。因此，可以做一個(gè)簡(jiǎn)化，假設(shè)t時(shí)刻系統(tǒng)的狀態(tài)只與t-1時(shí)刻系統(tǒng)的狀態(tài)有關(guān)，與更早的時(shí)刻無(wú)關(guān)。上面的概率可簡(jiǎn)化為

系統(tǒng)狀態(tài)的取值有n種可能，在t時(shí)刻取任何一個(gè)值與t-1 時(shí)刻取任何一個(gè)值的條件概率構(gòu)成一個(gè)n×n的矩陣A，稱為狀態(tài)轉(zhuǎn)移概率矩陣，其元素為

這個(gè)矩陣的元素表示t-1 時(shí)刻系統(tǒng)的狀態(tài)為i，t時(shí)刻系統(tǒng)的狀態(tài)為j的概率，即從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率。如果知道了每一時(shí)刻的狀態(tài)轉(zhuǎn)移矩陣，就可以計(jì)算出任意時(shí)刻系統(tǒng)狀態(tài)取每個(gè)值的概率。狀態(tài)轉(zhuǎn)移矩陣的值通過(guò)訓(xùn)練樣本學(xué)習(xí)。

狀態(tài)轉(zhuǎn)移概率矩陣的元素必須滿足如下約束：

第一條是因?yàn)楦怕实闹当仨殲閇0,1]，第二條是因?yàn)闊o(wú)論t時(shí)刻的狀態(tài)值是什么，在下一個(gè)時(shí)刻一定會(huì)轉(zhuǎn)向n個(gè)狀態(tài)中的一個(gè)，因此，它們的轉(zhuǎn)移概率和為1。另外，還需要為系統(tǒng)指定初始狀態(tài)z0=s0。

由該模型產(chǎn)生一個(gè)狀態(tài)序列z1,z2,…,zT的概率為

結(jié)果就是狀態(tài)轉(zhuǎn)移矩陣的元素乘積。在這里，假設(shè)任何一個(gè)時(shí)刻的狀態(tài)轉(zhuǎn)移矩陣都是相同的，即狀態(tài)轉(zhuǎn)移矩陣與時(shí)間無(wú)關(guān)。

狀態(tài)轉(zhuǎn)移矩陣通過(guò)訓(xùn)練樣本學(xué)習(xí)得到，訓(xùn)練時(shí)的損失函數(shù)使用對(duì)數(shù)似然函數(shù)。給定一個(gè)狀態(tài)序列z，定義馬爾可夫過(guò)程的對(duì)數(shù)似然函數(shù)為

因?yàn)闋顟B(tài)轉(zhuǎn)移矩陣要滿足上面的兩條約束，因此，要求解的是如下帶約束的最優(yōu)化問(wèn)題：

由于對(duì)數(shù)函數(shù)的定義域要求自變量大于0，所以可以去掉不等式約束，上面的最優(yōu)化問(wèn)題是一個(gè)帶等式約束的優(yōu)化問(wèn)題，可以用拉格朗日乘數(shù)法求解。構(gòu)造拉格朗日函數(shù)：

對(duì)aij求偏導(dǎo)數(shù)并令導(dǎo)數(shù)為0，可以得到

解得

對(duì)ai求偏導(dǎo)數(shù)并令導(dǎo)數(shù)為0，可以得到

將aij帶入上式可以得到

解得

合并后得到下面的結(jié)果：

也就是說(shuō)，從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率估計(jì)值，就是在訓(xùn)練樣本中從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的次數(shù)除以從狀態(tài)i轉(zhuǎn)移到下一個(gè)狀態(tài)的總次數(shù)。

2 實(shí)驗(yàn)方案

實(shí)驗(yàn)的核心技術(shù)思想為采用PGM 算法對(duì)系統(tǒng)的歷史狀態(tài)數(shù)據(jù)即訓(xùn)練樣本進(jìn)行學(xué)習(xí)，求出狀態(tài)轉(zhuǎn)移矩陣，從而對(duì)系統(tǒng)的未來(lái)狀態(tài)進(jìn)行預(yù)測(cè)。

實(shí)驗(yàn)分為三個(gè)階段：

（1）樣本預(yù)處理。一個(gè)系統(tǒng)包含多個(gè)子系統(tǒng)。子系統(tǒng)的狀態(tài)有四種，分別記為狀態(tài)1、狀態(tài)2、狀態(tài)3、狀態(tài)4。分別查詢每個(gè)時(shí)刻（間隔1 小時(shí)或間隔固定時(shí)長(zhǎng)）各個(gè)子系統(tǒng)的狀態(tài)，并統(tǒng)計(jì)整個(gè)系統(tǒng)各個(gè)時(shí)刻、各個(gè)狀態(tài)的總數(shù)量。

（2）計(jì)算狀態(tài)轉(zhuǎn)移矩陣。根據(jù)預(yù)處理結(jié)果，取前80%的數(shù)據(jù)作為樣本集，統(tǒng)計(jì)各個(gè)狀態(tài)轉(zhuǎn)移次數(shù)，求出各個(gè)狀態(tài)轉(zhuǎn)移概率，得到狀態(tài)轉(zhuǎn)移矩陣。

（3）預(yù)測(cè)。取欲處理結(jié)果的后20%作為測(cè)試集，根據(jù)狀態(tài)轉(zhuǎn)移矩陣，計(jì)算未來(lái)某一時(shí)刻系統(tǒng)的各個(gè)狀態(tài)的數(shù)量。

3 實(shí)驗(yàn)結(jié)果

本文給出兩種預(yù)測(cè)方法。其中，狀態(tài)轉(zhuǎn)移矩陣的選取不同。

第一種，狀態(tài)轉(zhuǎn)移矩陣不隨時(shí)間變化。分別統(tǒng)計(jì)出各個(gè)狀態(tài)在各個(gè)時(shí)刻的預(yù)測(cè)數(shù)量和實(shí)際數(shù)量。實(shí)驗(yàn)結(jié)果如表1 和圖1 所示。

表1 第一種方法結(jié)果

其中，四張圖分別表示各個(gè)狀態(tài)的預(yù)測(cè)數(shù)量和實(shí)際數(shù)量的對(duì)比圖，藍(lán)色線表示預(yù)測(cè)結(jié)果，紅色線表示實(shí)際結(jié)果。

第二種，狀態(tài)轉(zhuǎn)移矩陣隨時(shí)間變化。狀態(tài)轉(zhuǎn)移矩陣每時(shí)刻修正一次，且采用貝葉斯權(quán)重模擬計(jì)算狀態(tài)轉(zhuǎn)移概率，即系統(tǒng)當(dāng)前的狀態(tài)和它前一時(shí)刻的狀態(tài)相關(guān)性最大，往前依次根據(jù)貝葉斯系數(shù)遞減。貝葉斯函數(shù)為

貝葉斯函數(shù)圖像如圖2 所示。

實(shí)驗(yàn)結(jié)果如表2 和圖3 所示。

圖1 方法一結(jié)果

圖2 貝葉斯函數(shù)

第一種方法，只能預(yù)測(cè)前幾個(gè)時(shí)刻，隨著時(shí)間推移，預(yù)測(cè)效果不理想，但是由于狀態(tài)轉(zhuǎn)移矩陣固定，所以該方法計(jì)算量小。第二種方法，由于狀態(tài)轉(zhuǎn)移矩陣隨時(shí)間不斷變化，計(jì)算量有所增加，但可以較好地預(yù)測(cè)未來(lái)任意時(shí)刻系統(tǒng)的狀態(tài)。

4 結(jié)語(yǔ)

本文基于PGM 算法，給出了兩種預(yù)測(cè)系統(tǒng)狀態(tài)的方法。第一種方法可以快速預(yù)測(cè)未來(lái)前幾個(gè)時(shí)刻的狀態(tài)，具有計(jì)算量小的優(yōu)點(diǎn)；第二種方法，通過(guò)不斷調(diào)整狀態(tài)轉(zhuǎn)移矩陣，雖然增加了計(jì)算量，但可以預(yù)測(cè)未來(lái)任意時(shí)刻系統(tǒng)的狀態(tài)。這兩種方法與神經(jīng)網(wǎng)絡(luò)方法預(yù)測(cè)相比，具有計(jì)算量小的優(yōu)點(diǎn)，均具有可行性。