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

孫聚波， 徐平峰

（長春工業大學 基礎科學學院，吉林 長春 130012）

0 引 言

近年來，針對分類數據的特殊統計方法的應用日益廣泛，這個現象一定程度上反映了過去幾十年分類數據分析方法的發展。其中，用列聯表對分類數據進行統計分析是一種常用、直觀的方法［1］。

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

n（x）＝落入格子x的觀測頻數

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

在高維列聯表中，飽和模型的參數個數一般大于樣本個數，不僅統計上無法處理，計算上也不可行。但事實上，很多高維數據都具有某種特殊結構，并且結構是稀疏的，通常可以用圖模型表示。

1 圖模型及極大似然估計

1.1 圖模型

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

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

1.2 極大似然估計的IPS算法

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

似然方程為

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

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

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

收斂性的證明見文獻［3］。

1.3 基于團分劃改進的IPS算法（IPSP算法）

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

在IPSP算法中，給定分劃W，將所有的團都調整一次，共需加法次；需乘法次；需除法次。其中算法的復雜程度主要體現在乘法上，常用乘法次數來度量算法的復雜度。

2 n－元圈圖模型的最優分劃

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

圖1 n－元圈圖模型

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

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

證明 由Jensen不等式，有

我們構造函數：

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

則m≥3時，f關于m單調增。下述即證明m≥3時，該不等式組成立。

我們構造函數：

n為偶數時，連續二等分劃復雜度為：

解不等式

整理得：

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

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

n為奇數時，連續二等分劃復雜度為：

解不等式

整理得

構造函數

解不等式組

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

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

成立。

綜上，無論n為偶數還是奇數，對任意n≥6，a≥2，任意連續分劃中二等連續分劃最優。

3 結 語

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

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

［2］ 王曉飛.圖模型的結構、分解和可壓縮性［D］.長春：東北師范大學數學與統計學院，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，FL，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.