高階馬爾科夫鏈張量方程的一種反迭代算法

周 藝，呂來水，喻高航

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2.南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210094)

0 引 言

高階馬爾科夫鏈[1]是一個(gè)具有馬爾科夫性質(zhì)的離散時(shí)間隨機(jī)過程。該過程中，在給定當(dāng)前狀態(tài)的條件下，未來的狀態(tài)也依賴于其過去臨近幾個(gè)時(shí)刻的狀態(tài)，而不止當(dāng)前狀態(tài)[2]。高階馬爾可夫鏈應(yīng)用于許多不同的背景，如DNA序列分析[3]、Multilinear PageRank[4]等。高階馬爾科夫鏈的極限概率分布問題可轉(zhuǎn)換為求解一個(gè)帶有約束的轉(zhuǎn)移概率張量方程[5]。2014年,Li等[6]提出求解高階馬爾科夫鏈的極限概率分布問題的高階冪法，并在一定條件下建立了算法的收斂性；2019年，Liu等[7]在冪法的基礎(chǔ)上，提出了一種非精確的反迭代算法，通過引入松弛參數(shù)，在一定程度上提高了算法效率。冪法可看做是固定步長的梯度法，梯度法在機(jī)器學(xué)習(xí)中常見的改進(jìn)是添加“動(dòng)量項(xiàng)”[8-9]，這樣能夠充分利用歷史梯度信息，從而改善傳統(tǒng)梯度法效率。本文結(jié)合動(dòng)量梯度法，提出一種新的反迭代算法——具有動(dòng)量項(xiàng)的帶位移的反迭代算法(簡稱Inv-PMM)，并給出算法的收斂性分析和誤差估計(jì)。

1 預(yù)備知識

假設(shè)存在一個(gè)與時(shí)間無關(guān)的固定概率pi1i2…im，滿足：

0≤ai1i2…im=prob(Xt+1=i1|Xt=i2,…,Xt-m+2=im)≤1

其中，i1,i2,…,im∈〈n〉，稱{Xt}為一個(gè)m-1階馬爾可夫鏈。概率ai1i2…im構(gòu)成的張量=(ai1i2…im)稱為轉(zhuǎn)移概率張量，顯然≥0且特別地，當(dāng)m=2時(shí)，序列就是一個(gè)標(biāo)準(zhǔn)的一階馬爾可夫鏈，就退化為一個(gè)概率轉(zhuǎn)移矩陣。

向量x表示馬爾可夫鏈{Xt}的概率分布向量，文獻(xiàn)[6]將高階馬爾科夫鏈極限概率分布問題近似成如下張量模型：

x=

(1)

2 反迭代動(dòng)量算法及收斂性分析

2.1 反迭代動(dòng)量算法

一階優(yōu)化中的動(dòng)量梯度算法主要是在梯度下降算法的基礎(chǔ)上添加動(dòng)量項(xiàng)，從而達(dá)到加速優(yōu)化的效果。基于動(dòng)量梯度算法的思想，本文提出一種具有動(dòng)量項(xiàng)的帶位移的反迭代算法Inv-PMM用于求解張量方程(1)，算法主要步驟如下。

2.2 收斂性分析

為了分析Inv-PMM算法的收斂性，給出如下引理。

引理1[6]如果是一個(gè)m階n維非負(fù)轉(zhuǎn)移概率張量，令δm滿足：

(2)

引理2[7]如果是一個(gè)m階n維非負(fù)轉(zhuǎn)移概率張量，x,y∈Rn是n維隨機(jī)向量。則有：

(3)

(4)

(5)

(6)

式中，κm=1-δm，0<κm≤1。

基于上述3個(gè)引理，得到Inv-PMM算法的收斂性定理。

定理如果是一個(gè)m階n維非負(fù)轉(zhuǎn)移概率張量，滿足是方程(1)的解，則對于任意的初始向量x0，當(dāng)參數(shù)滿足且算法生成的序列收斂，并且有如下誤差界：

(7)

(1)當(dāng)k不被2整除時(shí)，通過Inv-PMM算法步驟1中的(λI-得到：

(8)

(9)

聯(lián)立式(8)和式(9)，得：

(10)

由式(3)得：

(11)

令zk-1=(通過式(6)得到：

(12)

則有：

(13)

(14)

通過引理3，可得到：

(15)

故：

(16)

(2)當(dāng)k被2整除時(shí)，Inv-PMM算法的迭代格式可寫成：

(λI-

(17)

即：

(18)

(19)

由式(3)、式(4)、式(6)分別得：

(20)

(21)

(22)

則有：

(23)

(24)

故：

(25)

綜合上述2種情況，對于?k=1,2,3,…，由式(16)、式(25)推得：

(26)

3 數(shù)值實(shí)驗(yàn)

實(shí)驗(yàn)在Windows 10操作系統(tǒng)下的MATLAB R2016a中完成，硬件配置為Intel(R) Xeon(R)E-2176M CPU @2.71GHz。

對4個(gè)非負(fù)不可約轉(zhuǎn)移概率張量的極限概率分布向量進(jìn)行求解。例1是一個(gè)3階3維張量，來自于文獻(xiàn)[10]中的表6；例2是一個(gè)4階3維張量，來自于文獻(xiàn)[11]；例3是一個(gè)3階3維張量，來自于文獻(xiàn)[12]中的表3；例4是一個(gè)4階4維張量，來自于文獻(xiàn)[12]中的表2。實(shí)驗(yàn)中，HOPM算法不涉及自由參數(shù)的選取，其他3種算法的參數(shù)如表1所示。從算法的迭代步數(shù)、計(jì)算時(shí)間及相對殘差3個(gè)方面進(jìn)行比較分析，實(shí)驗(yàn)結(jié)果如表2所示。

表1 不同算法的實(shí)驗(yàn)參數(shù)

從表2可以看出，4種算法中，Inv-PMM算法的相對范數(shù)更小、誤差迭代步數(shù)更少、運(yùn)行時(shí)間短，說明Inv-PMM算法的收斂速度最快，算法效果最優(yōu)。

4 結(jié)束語

針對高階馬爾科夫鏈極限概率分布問題，本文提出一種具有動(dòng)量項(xiàng)的帶位移的反迭代算法Inv-PMM，采用周期間隔的動(dòng)量外推，使得算法生成的序列能夠更快地收斂到問題的平穩(wěn)分布。如何自適應(yīng)選取位移參數(shù)和動(dòng)量參數(shù)是下一步研究重點(diǎn)。