n－元圈圖模型迭代比例擬合算法中的最優(yōu)分劃

孫聚波， 徐平峰

（長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院，吉林 長春 130012）

0 引 言

近年來，針對分類數(shù)據(jù)的特殊統(tǒng)計方法的應(yīng)用日益廣泛，這個現(xiàn)象一定程度上反映了過去幾十年分類數(shù)據(jù)分析方法的發(fā)展。其中，用列聯(lián)表對分類數(shù)據(jù)進(jìn)行統(tǒng)計分析是一種常用、直觀的方法［1］。

一般來說，觀測數(shù)據(jù)按兩個或多個屬性分類時所列出的頻數(shù)表即為列聯(lián)表。文中令V表示由分類變量構(gòu)成的集合。對任意的分類變量γ∈V，Xγ表示γ對應(yīng)的有限的水平集。表中的一個格子表示集合XV中的一個點x＝（xγ）γ∈V，這里XV＝×γ∈VXγ。假設(shè)把n次觀測數(shù)據(jù)按V進(jìn)行分類，令計數(shù)

n（x）＝落入格子x的觀測頻數(shù)

p（x）＝一個個體落入格子x的概率

在高維列聯(lián)表中，飽和模型的參數(shù)個數(shù)一般大于樣本個數(shù)，不僅統(tǒng)計上無法處理，計算上也不可行。但事實上，很多高維數(shù)據(jù)都具有某種特殊結(jié)構(gòu)，并且結(jié)構(gòu)是稀疏的，通?？梢杂脠D模型表示。

1 圖模型及極大似然估計

1.1 圖模型

圖模型是圖論、概率論、統(tǒng)計學(xué)等學(xué)科的交叉領(lǐng)域［2－3］。在圖模型中，隨機變量由圖的頂點表示，隨機變量之間有直接關(guān)聯(lián)，對應(yīng)的頂點間用邊相連，這樣構(gòu)成一個圖G（V，E），這里V表示頂點集，E表示邊集。相對于圖G滿足馬爾科夫性的概率分布族，即為圖模型，記作P（G）。如此建立的圖模型清晰地表示了條件獨立關(guān)系，從而建立圖與概率分布的對應(yīng)關(guān)系，利用圖的語言表示概率統(tǒng)計相關(guān)問題，并依據(jù)圖論的理論和算法幫助進(jìn)行概率統(tǒng)計推斷，降低推斷的復(fù)雜度。目前，圖模型被廣泛地應(yīng)用于生物信息學(xué)、統(tǒng)計物理、圖像處理、信息檢索、機器學(xué)習(xí)等各個領(lǐng)域［4］。

在圖G中，子集c?V，如果c中任意兩個頂點都是相鄰的，則稱子集c是完全的。如果一個完全子集是最大的（相對于包含運算而言），則稱它為一個團(tuán)。我們用K（G）表示一個圖的所有團(tuán)構(gòu)成的集合。

1.2 極大似然估計的IPS算法

利用圖模型分析高維數(shù)據(jù)，求解參數(shù)的極大似然估計是一個非常重要的方面。設(shè)x1，x2，…，xn為來自多項圖模型P（G）的獨立同分布樣本，對于每個x∈XV，x被觀測到的次數(shù)為n（x）。對于團(tuán)c∈K（G），xc∈Xc＝×γ∈cXγ的觀測數(shù)為。于是，似然函數(shù)為

似然方程為

對所有的xc∈Xc，c∈K（G）。

為求解上述似然方程，Deming［5］等給出了迭代比例擬合（IPS）算法，他們先引入一個邊緣調(diào)整算子Ac，對于任意p（xV），任意c∈K（G），令

其中j＝（tmodk）＋1。取p（0）∈P（G），則概率p的極大似然估計為

收斂性的證明見文獻(xiàn)［3］。

1.3 基于團(tuán)分劃改進(jìn)的IPS算法（IPSP算法）

在圖模型中，IPS算法的復(fù)雜度隨變量個數(shù)的增加呈指數(shù)型增加，求解似然方程的速度變得非常慢。過去十幾年，諸多學(xué)者做了大量工作以降低IPS算法的復(fù)雜度［6－10］。對于多項圖模型，文獻(xiàn)［10］利用團(tuán)分劃的策略實現(xiàn)局部計算和共享計算，從而改進(jìn)了IPS算法，給出了基于團(tuán)分劃改進(jìn)的IPS算法，即IPSP算法。它先找K（G）的一個分劃W＝｛K1，K2，…，Km｝，使得K（G）＝，且對；對i＝1，2，…，m，令Ui＝∪c∈Kic，計算，對c∈Ki，進(jìn)行局部調(diào)整pUi＝AcpUi；利用調(diào)整后的邊緣分布pUi恢復(fù)聯(lián)合分布p（xV），詳見文獻(xiàn)［10］。

在IPSP算法中，給定分劃W，將所有的團(tuán)都調(diào)整一次，共需加法次；需乘法次；需除法次。其中算法的復(fù)雜程度主要體現(xiàn)在乘法上，常用乘法次數(shù)來度量算法的復(fù)雜度。

2 n－元圈圖模型的最優(yōu)分劃

在IPSP算法中，分劃策略影響算法的復(fù)雜度。如何選擇最優(yōu)分劃是一個組合優(yōu)化問題，對于一般的圖模型問題比較復(fù)雜，可采用模擬退火等方法進(jìn)行求解。下面對于具有特殊結(jié)構(gòu)的n－元圈圖模型給出了最優(yōu)分劃策略，如圖1所示。

圖1 n－元圈圖模型

在上面的n－元圈圖G＝（V，E）中，頂點集V＝｛1，2，…，n｝，邊 集E＝｛（1，2），（2，3），…，（n－1，n），（n，1）｝，每個頂點表示隨機變量Xi，Xi為離散的，且所有Xi的取值個數(shù)相同。其中，團(tuán)為：ci＝｛i，i＋1｝，i＝1，2，…，n－1，cn＝｛n，1｝，團(tuán)集K（G）＝｛ci｜i＝1，2，…，n｝。團(tuán)集的分劃為：W＝｛K1，K2，…，Km｝，使得，且對i。分劃W的復(fù)雜度函數(shù)為：

定理1 令W為連續(xù)分劃，｜Ki｜＝ki，n≥6，隨機變量Xi取值個數(shù)皆為定數(shù)a（a≥2），對應(yīng)的復(fù)雜度函數(shù)為：

證明 由Jensen不等式，有

我們構(gòu)造函數(shù)：

m≥3時，若下面不等式組成立

則m≥3時，f關(guān)于m單調(diào)增。下述即證明m≥3時，該不等式組成立。

我們構(gòu)造函數(shù)：

n為偶數(shù)時，連續(xù)二等分劃復(fù)雜度為：

解不等式

整理得：

易求得對任意n≥6，a≥2，都有上式成立，則對任意分劃W都有

g（W）≥f（a，n，3）≥n·an／2＋1＋2·an

n為奇數(shù)時，連續(xù)二等分劃復(fù)雜度為：

解不等式

整理得

構(gòu)造函數(shù)

解不等式組

將t（2，n）≥0整理為：

求得n≥7，滿足該不等式。

成立。

綜上，無論n為偶數(shù)還是奇數(shù)，對任意n≥6，a≥2，任意連續(xù)分劃中二等連續(xù)分劃最優(yōu)。

3 結(jié) 語

給出并證明了隨機變量的取值個數(shù)相等時，n－元圈圖模型中IPSP算法的最優(yōu)分劃為連續(xù)二等分劃。那么若隨機變量的取值不一定相同時，其最優(yōu)分劃是否仍為連續(xù)二等分劃，對于結(jié)構(gòu)一般的圖模型，IPSP算法的最優(yōu)分劃是否也為連續(xù)二等分劃呢，這都是尚未解決的問題。作者旨在拋磚引玉，以待更多人關(guān)注和研究。

［1］ Agresti A.屬性數(shù)據(jù)分析引論［M］.張淑梅，王睿，曾莉，譯.2版.北京：高等教育出版社，2008.

［2］ 王曉飛.圖模型的結(jié)構(gòu)、分解和可壓縮性［D］.長春：東北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，2010.

［3］ Lauritzen S L.Lectures on Contingency Tables［EB／OL］.（2002－05－28）［2015－03－20］.http：／／www.stats.ox.ac.uk／～steffen／papers／cont.pdf.

［4］ Wainwright M J，Jordan M I.Graphical models，exponential families，and variational inference［J］.Foundations and Trends in Machine Learning，2008，1（1／2）：1－305.

［5］ Deming W E，Stephan F F.On a least squares adjustment of a sampled frequency table when the expected marginal totals are known［J］.The Annals of Mathematical Statistics，1940，11（4）：427－444.

［6］ Jirousek R，Preucil S.On the effective implementation of the iterative proportional fitting procedure［J］.Computational Statistics and Data Analysis，1995，19（2）：177－189.

［7］ Badsberg J H，Malvestuto F M.An implementation of the iterative proportional fitting procedure by propagation trees［J］.Computational Statistics and Data Analysis，2001，37（3）：297－322.

［8］ Teh Y W，Welling M.On Improving the efficiency of the Iterative proportional fitting procedure［J］.In Proceedings of the Ninth International Conference on Artificial Intelligence and Statistics，Key West，F(xiàn)L，2003，34（6）：231－240.

［9］ Xu P F，Guo J H，Tang M L.A localized implementation of the iterative proportional scaling procedure for Gaussian graphical models［J］.Journal of Computational and Graphical Statistics，2015，24（1）：205－229.

［10］ Xu P F，Sun J，Shan N.Local computations of the iterative proportional scaling procedure for hierarchical models［J］.Submitted to Computational Statistics Data Analysis，2015，16（2）：195－199.