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.