高階馬爾科夫鏈的張量模型

1、高階馬爾科夫鏈的張量模型廣州，510631Joint work with Prof. Michael Ng and LB Cui 123提綱引言關(guān)于張量模型平穩(wěn)分布存在與唯一性求解張量模型平穩(wěn)分布的迭代法平穩(wěn)分布的擾動分析數(shù)值例子 4一、引言： Markov鏈的研究有非常悠久的歷史，在建模以及分析實系統(tǒng)時，Markov鏈的應(yīng)用非常廣泛，例如對制造系統(tǒng)，隨機(jī)自動化網(wǎng)絡(luò)（SAMs），排隊系統(tǒng)，生物信息工程，數(shù)據(jù)序列、網(wǎng)頁排序以及其他和計算有關(guān)的應(yīng)用和網(wǎng)絡(luò)決策分析等等, Markov鏈模型能作出很好的預(yù)測和優(yōu)化計劃等作用。 在某些應(yīng)用研究中，例如在生物信息學(xué)中，不同基因之間的相互作用構(gòu)成了復(fù)雜的細(xì)胞

2、活動。對作用于細(xì)胞、組織和器官的基因共同性研究在生物信息學(xué)中是一個重要的課題。代替獨(dú)立看待單細(xì)胞，全局的或歷史性的觀點(diǎn)在理解細(xì)胞作用和控制大量正常功能運(yùn)作的機(jī)制中顯得越來越重要。通過概率布爾網(wǎng)絡(luò)(PBN)建立基因調(diào)控網(wǎng)絡(luò)模型，利用實際的數(shù)據(jù)推斷網(wǎng)絡(luò)結(jié)構(gòu)和5 參數(shù)。這有助于我們理解基因網(wǎng)絡(luò)和理解網(wǎng)絡(luò)中不同的基因的作用。然后提出基因干預(yù)的治療或基因控制策略。然而，網(wǎng)絡(luò)的規(guī)模隨基因數(shù)量的增長而呈指數(shù)階增長。一個PBN可以建立有關(guān)Markov模型，進(jìn)而利用該Markov鏈模型分析該網(wǎng)絡(luò); 在信用危機(jī)模型中的應(yīng)用中，信用等級在信用危機(jī)分析和建模中非常重要。以往建立信用等級和他們之間的轉(zhuǎn)移的常規(guī)的方法就是

3、Markov鏈模型及其概率轉(zhuǎn)移矩陣。當(dāng)今 人們面臨的問題越來越復(fù)雜，復(fù)雜的事物通?？梢杂酶呔S數(shù)據(jù)來刻畫。 最近，高階非負(fù)張量用于建立高階Markov鏈模型，這給研究Markov鏈帶來新的具有挑戰(zhàn)性的課題。 因此，對Markov過程及其應(yīng)用的研究至今仍然是數(shù)學(xué)及許多領(lǐng)域的研究熱點(diǎn)，其研究在生物、醫(yī)學(xué)、計算機(jī)科學(xué)、數(shù)據(jù)分析和數(shù)學(xué)等各方面都要重要的理論和實踐意義。61、 Markov鏈模型 給定一個Markov鏈過程x(t)，設(shè)它在離散的時間段t = 1, 2, 3, . . .內(nèi)在狀態(tài)空間S = 1, 2, . . . , m內(nèi)取值， 的概率只和 有關(guān)。一個Markov過程是由它的概率轉(zhuǎn)移矩陣 刻

4、畫的，其中， (1)這時，P 是列和為1的非負(fù)矩陣。7對某些數(shù)據(jù)序列進(jìn)行分析時， 一階Markov模型不能滿足進(jìn)一步的分析要求，因為在時刻t的概率與它前面的n 個時刻有關(guān)，即需要求如下概率:Raftery于1985年給出了估計方法： 892、高階非負(fù)張量模型 對高階Markov模型的分析也可以利用高階非負(fù)張量的有關(guān)理論，所謂m階n維非負(fù)張量指 張量有非常重要的應(yīng)用. 這里，我們比較感興趣的是與高階Markov鏈有關(guān)的非負(fù)張量的譜理論，張和祁給出張量譜理論的很好的綜述。張量的H-特征值和特征向量定義為 ：10其中而Z-特征值和特征向量定義:11(see Chang and Zhang, manu

5、script, 2012).文Ng,Qi, Zhou, SIMAX, 2009指出，對某些數(shù)據(jù)系列建立高階Markov模型時通常可以計算如下高階轉(zhuǎn)移概率：（5） 在模型（2）和（4）中， 的值分別由某些 的線性組合近似得到。由非負(fù)張量的關(guān)于H-特征值的Perron-Frobenius定理知道N-Q-Z，09可以直接利用非負(fù)張量（5）來計算有關(guān)概率分布向量。12 對計算高階張量的在時刻t概率分布 Qi，2012等給出了如下模型: （6） 其中，P滿足（5），且 則平穩(wěn)概率分布向量可以通過如下模型得到： 13（7） 其中對模型（7）我們有如下需要解決的問題：（a）模型（7）的解向量，即平穩(wěn)分布x是

6、存在嗎？唯一嗎？ 如果不唯一，什么情況下唯一？（b）保證唯一性條件下，如何給出（7）平穩(wěn)概率分布向量 的求解算法？（c） 如何給出（7）的敏感性（擾動）分析？ 14二、關(guān)于模型（7）平穩(wěn)分布存在唯一性1、存在性：文Li, Ng, 2011定理2.2 (p.21) 給出了對不可約非負(fù)張量，方程（7）的存在性證明，即:152、唯一性：文Li, Ng, 2011給出了如果概率轉(zhuǎn)移張量P沒有任何限制，（7）的解不是唯一的（p. 24 Remark 1）。對方程（7）文Li,Ng, 2011首次給出了唯一性的充分條件（見Theorems 2.3 and 2.4, p. 22-35），即 注記 1 定理2

7、.3與2.4所給出的條件不是必要的（see Remark 5 p. 35）；注記 2 對m=3，n=2，文Chang and Zhang和Hu,Qi,2011分別給出 方程（7）的解是唯一的，另外他們也給出了唯一性的另外一些充分 條件。注記 3 實際上，（7）為張量的Z_1 特征值問題。 Chang and Zhang給出 了Z_1 和Z_2 特征值問題的關(guān)系。16問題 ：1、非負(fù)概率轉(zhuǎn)移張量的不可約性是否是（7）有唯一 平穩(wěn)分布的條件？2、能否給出有唯一解的充分必要條件？3、模型（6）的概率分布有極限的充分必要條件是什 么？ 注：問題1對一般非負(fù)矩陣來說是對的，許多數(shù)值例子 也表明問題的答案

8、是肯定的！而對非負(fù)矩陣來說， 唯一性的充分必要條件是基本類等于最后類（注： 類、基本類、最后類的定義可以參考BP，197917三、求解（7）平穩(wěn)分布的迭代法 如下是考慮第一節(jié)中的問題（b），即：保證唯一性條件下，如何給出（7）平穩(wěn)概率分布向量的求解算法？我們給出迭代法如下（見LN2011）：18注記1： t+1步迭代得到的向量x_t+1 不必單位化處理。需討論的問題是：(a) 在（7）有唯一解的條件下，上述算法是否收斂？(b) 如果不收斂，收斂條件是什么？(c) 收斂率如何給出？效果如何？ 問題(a)是否定的， 例如取3階2維不可約概率轉(zhuǎn)移張量（見p.35, Remark 5）, 有唯一解（1

9、/2，1/2）T, 但算法選取初值為（0，1）T，則算法不收斂。盡管可以存在收斂的子序列，但該子序列不一定收斂到（7）的解。19對問題(b)和(c) 當(dāng)滿足唯一性條件下，算法收斂：證明見定理3.1和3.2（p.4449）. 20問題：（1）算法除了給出的收斂條件以外還有更 好的收斂條件？ （2）尋找更好的算法？21四、概率平穩(wěn)分布的擾動分析1、基礎(chǔ) （1）、什么是擾動分析？ （2）、通常擾動分析研究什么？ （3）、問題擾動的形式：加法與乘法2、結(jié)果：本節(jié)給出的結(jié)果是在唯一性條件下給出了 （7）的系數(shù)張量變化對平穩(wěn)分布的影響，即 222324注記：1、由給出的界可以看出問題的解對唯一性條件非常 敏感，后面的數(shù)值例子圖2-7也說明這點(diǎn); 2、界可以取到等號成立（見p66 III）;3、絕對擾動與相對擾動一致.253、一階Markov鏈的擾動分析情況問題：對一般的非負(fù)張量，H-和Z-矩陣的最大特征對擾動界如何給出？26五、算例參考論文：1 W Li, M. Ng, Existence and uniqueness of stationary probability vector of a tra