多元全正二序分布于无向图的忠实性.pdf

第 卷第期东 北 师 大 学 报(自 然 科 学 版)V o l N o 年月J o u r n a l o fN o r t h e a s tN o r m a lU n i v e r s i t y(N a t u r a lS c i e n c eE d i t i o n)J u n e 文章编号 ()D O I /j c n k i d s l k x b 收稿日期 基金项目国家自然科学基金资助项目()作者简介李本崇(),男,副教授,主要从事图模型、代数统计研究多元全正二序分布于无向图的忠实性李本崇,王慧,张春妮(西安电子科技大学数学与统计学院,陕西 西安 )摘要考虑了多元全正二序(MT P)分布和无向图问题给定一个无向图G,证明了具有确定样本空间,且可依据d维无向图G分解的严格正的离散(正则正态)MT P分布在d中的勒贝格测度为正因此,几乎所有依据G分解的正的离散(正则正态)MT P分布都忠实于无向图G 关键词忠实性;正的离散MT P分布;正则正态MT P分布;无向图 中图分类号O 文献标志码A引言图可以用来描述概率分布的条件独立结构图中的顶点表示随机变量,它表示的条件独立情形由与其对应的特定类型的分离准则来确定关于概率分布和图之间的联系,基本问题有两个:()给定一个图G,是否存在一个概率分布P(或一族分布),使得两者对应的条件独立情形构成的两个集合是相同的,即P忠实于G;()反过来,给定一个概率分布P,是否存在一个图G,使得P是忠实于G的针对问题(),对于常见的图类和概率分布族,已有一些结果 在结构学习领域,一般假定问题()的答案是肯定的,称之为忠实性假设但事实上,问题()的答案通常是否定的,尽管如此,对问题()的研究,近期也取得了一些理论上的结果随机变量间的正相依关系有不同的定义,MT P(m u l t i v a r i a t et o t a l l yp o s i t i v eo fo r d e r t w o)是一种特殊的形式,它蕴含了大多数别的正相依的定义文献 给出了许多实例并讨论了MT P随机变量的一些性质文献 研究了正态MT P分布文献 提供了一个结构学习的视角,指出正则正态MT P分布忠实于其成对独立图,它是一个无向图文献 中给出了MT P分布与条件独立相关的一些性质,证明了任一无向图存在一个忠实的正态MT P分布文献 证明了每个无向图都存在一个具有固定样本空间的正的忠实的离散MT P分布文献 研究了正态MT P分布的极大似然估计的存在性文献 证明了MT P分布构成的指数族是凸的,并给出了极大似然估计存在的条件本文讨论上面提到的问题()受文献 ,中所用方法的启发,本文将文献 中的两个单个分布存在的结果推广到测度论情形证明了具有固定样本空间,且能依据d维无向图G分解的严格正的离散MT P分布(正则正态MTP分布),在d下的勒贝格测度为正因此,依据G分解但不忠实于G的概率分布的勒贝格测度为零 M e e k指出,这些结果对于以条件独立检验方式学习无向图具有重要意义,因为它们表明结构学习中的忠实性假设在测度论意义下是正确的 定义和记号本文中,N表示非空有限随机变量的集合,N表示N的基数 MT P分布设P是N上的一个概率测度,即对每个XiN,都有一个可测空间(Xi,i),概率测度P定义在可第期李本崇,等:多元全正二序分布于无向图的忠实性测空间XXiNXi,XiNi()上如果一个随机向量(X,X,Xn)的密度函数f对所有的x,yX满足f(x)f(y)f(xy)f(xy),其中xy(m a x(x,y),m a x(x,y),m a x(xn,yn),xy(m i n(x,y),m i n(x,y),m i n(xn,yn),则称该随机向量或其分布是MT P的称n时的MT P分布为全正二序分布独立随机变量的联合密度是MT P的(文献 中命题)MT P性质在适当的支撑条件下只需验证成对的情形特别地,若要验证正的离散MT P分布的性质成立,只需验证x,yX在两个坐标分量上不相同时的情形(文献 中命题)例 考虑两个分别在,r 和,r 中取值的离散随机变量X和X,其中r和r是两个大于或等于的整数根据文献 中命题 的证明,要说明正的联合分布p(x,x)是全正二序分布,需验证(r)(r)个不等式是否成立,即p(x,x)p(x,x)p(x,x)p(x,x),其中x,r,x,r设p(x,x)(rxx)r(r)r(r),由于(rxx)(rxx)(rxx),故这(r)(r)个不等式成立 概率的条件独立结构如果A,B,C是N上两两不交的子集,称三元组A,B|C 是不交的用T(N)表示N上所有的不交三元组的集合,一个条件独立结构是T(N)的一个子集本文用符号(XA,A)表示XiAXi,XiAi()的简写,而对于每个AN,P的边际用PA表示给定A,B|CT(N),如果对每个AAA,BBB,PA B|C(AABB|x)PA|C(AA|x)PB|C(BB|x),对PC下几乎所有的xXC成立,则称于P而言,给定C时,A与B条件独立,记作AB|CPP诱导的条件独立结构为MP A,B|CT(N);AB|CP 无向图本文考虑简单无向图对一般的情形,可参阅文献一个无向图是一个集合对G(N,E),其中N是顶点集,E是边集如果(X,Y)E,则称G中的两个顶点X和Y是相邻的如果X的相邻顶点数为,则称X是孤立的一条路是由不同顶点构成的一个序列XY,Yk,其中(Yi,Yi)E,i,k,k对A,BN,AB,CN(AB),如果G中从XA到YB的每一条路都包含C的一个顶点,则称C分离A与B,记为AB|CGN上的每个无向图G由分离准则可诱导出N上的一个条件独立结构:MG A,B|CT(N);AB|CG 如果对于所有的X,YK,XY,(X,Y)E都成立,则称无向图G的顶点集KN是完全的特别地,空集是完全的用C(G)表示无向图G的非空完全集G中的最大完全集称为团,所有团的集合记为K(G)图一个无向图G例 无向图G:X是孤立点;从X到X的一条路是X,X,X,X;X,X 将X,X 分离;C(G)X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X ;KG中的元素是X,X,X,X,X,X,X如图所示如果一个概率分布与一个无向图诱导出相同的条件独立结构,则称该概率分布忠实于这个无向图介绍把一个无向图G与一个概率分布P联系起来的种定义N上的一个概率分布P满足:()如果对于任意(X,Y)E,有XY|NX,Y P 成立,则称概率分布P相对于G满足成对马尔科夫性;()如果MGMP成立,则称概率分布P相对于G满足全局马尔科夫性;()如果P(x)CKGC(x),()其中xX,C(x)是一个仅通过C中变量的值依赖x的势函数,则称P相对于G满足分解性本文主要讨论正的概率分布文献 中的定理 表明对于正的分布,这种定义等价东 北 师 大 学 报(自 然 科 学 版)第 卷 离散无向图模型假设每个离散变量Xi在ri,r 中取值,其中XiN,ri是一个正整数给定一个无向图G,G对应的图模型是依据()式分解的分布构成的集合图的子模型使用一组顶点势函数和一组边势函数进行成对参数化 设B(G)(bj k)是一个d m的矩阵,其中d(Xi,Xj)Erirj(如果Xk是孤立点,则相应的项是rk),mXiNriB(G)的每一项为或,B(G)的每一列中的个数是G的边和孤立顶点的个数之和B(G)的列由XiNri 标记B(G)的行由边(或一个孤立顶点Xi)和ri rj(或rk)中的元素共同标记于是,新的单项式映射表示为B(G):d m,(s,sd)ajsbjj,jsbjj,jsbj mj()文献 中给出了一种新的链图模型参数化方法特别地,对无向图模型,有P(x)CC(G)C(x)若存在某个XiC,有xi,则参数C(x)设为 如果一个参数可以独立于其他参数而取不同的值,则称它为可自由设定的在参数化时,称可自由设定的参数的个数为无向图G的维数,即dCC(G)XiC(ri)可自由设定的参数的取值范围为(,)d,称其为可自由设定参数空间例 对图中的无向图G,设定ri,i,则个团势函数共有 个值:(),(),(),(),(),(),(),(),(),(),(),(),(),(),(),(),(),(),其中Xi,Xk(xi,xk)简记为i,k(xi,xk)成对参数化下共有 个参数令s(),s(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,(),s,()如果B(G)的列按 ,排列,则单项式映射B(G)为B(G):,(s,s)a(ssss s s,sss s s s)本例中可自由设定的参数为t(),t(),t(),t(),t(),t,(),t,(),t,(),t,(),t,(),t,(),t,(),因此d 对于种参数化方法(分解、成对和文献 中提出的方法),每个概率p(x)x|N|iri()是一个比值,在相 应 的 参 数 化 下,分 子 是 一 个 单 项 式,分 母 是 所 有 单 项 式 的 和换 句 话 说,每 个 概 率p(x)x|N|iri()是相关参数的有理函数事实上,通过将每个势函数分配给包含其所对应变量的一个团,并将分配给每个团的所有势函数相乘,得到一个团势函数,就可以将任意一个依据完全子图分解的分布转换成公式()的形式本文用PD(G)表示依据G分解的正的离散MT P分布的集合注意,MT P性质成立需要满足p(x)p(y)p(xy)p(xy),然而当XiXj|NXi,Xj 时,p(x)p(y)p(xy)p(xy)成立,其中x,yX在由(Xi,Xj)标记的两个坐标中不同基于这个事实,对于每个无向图,文献 中定理构建了一个具有固定样本空间的忠实的正的离散MT P分布 正态无向图模型设N为服从多元正态分布的随机向量,均值为,协方差矩阵为,用i jXi,XjN表示的逆对于Xi,XjN,ij,XiXj|NXi,Xj 成立,当且仅当i jN的分布是MT P分布,当且仅当:()对XiN,有i i;()对Xi,Xj,ij,有i j 用RN(G)表示依据G分解的正则正态MT P分布的集合本文使用中的元素来参数化每个概率分布PRN(G)注意到:()Xi,XjN,ij,有i jj i;()对于任意在G中没有边连的Xi,Xj,i j不是由()和()确定值的参数称为非确定参数然而,非确定参数只能取使是正定的实数满足这一要求的非确定参数值的集合称为RN(G)的非确定参数空间G的维数定义为非确定参数的个数第期李本崇,等:多元全正二序分布于无向图的忠实性与无向图相关的忠实性证明对任一无向图G,PD(G)和RN(G)中几乎所有的概率分布都忠实于它 无向图和正的离散MT P分布给定一个无向图G,可以构造一个忠实的正的离散MT P分布P:若XiXj|NXi,Xj,p(x)p(y)p(xy)p(xy);否则p(x)p(y)p(xy)p(xy)从文献 中定理 的证明可知,p(x)p(y)p(xy)p(xy)是构造MT P分布的关键例 表明这一构造并不困难定理设G是维数为d的无向图,则PD(G)在d下的勒贝格测度为正证明该证明的出发点是,存在一个正的离散MT P分布P,如果有XiXj|NXi,Xj,则p(x)p(y)p(xy)p(xy)成立,否则有p(x)p(y)p(xy)p(xy)如上所述,例 和文献 中定理 的证明表明了该分布存在假设与P相关的可自由设定参数的值为t,td注意,对x,yX只有个坐标分量(Xi,Xj)不同时,p(xy)p(xy)p(x)p(y)是t,td的个有理函数的差值,即t,td的连续函数,其值等于或大于取决于XiXj|NXi,Xj 是否成立由连续函数的保号性(设g在cRd上连续且g(c),则存在一个c的邻域,在此邻域中g与g(c)符号相同),如果XiXj|NXi,Xj 不成立,存在一个,bi(ti,ti),i,d,与ti和bi相对应的概率分布均满足p(xy)p(xy)p(x)p(y)由于完全子图的参数化与无向图诱导的条件独立性一致,如果XiXj|NXi,Xj成立,则p(xy)p(xy)p(x)p(y)di(ti,ti)中的每个元素对应一个正的离散MT P分布,且不同元素对应不同的概率分布(文献 中引理),又di(ti,ti)在d上的勒贝格测度为正,故PD(G)的子集(与di(ti,ti)中的元素相对应的概率分布)在d下的勒贝格测度是正的文献 中定理表明,依据G分解的严格正的概率分布的集合在d下的勒贝格测度是正的,因此PD(G)在d下的勒贝格测度为正由于依据G进行因子分解但不忠实于它的正的离散概率分布的集合在d下的勒贝格测度为零(文献 中定理),而MT P性质是对分布的约束,因此有下面的结果:推论对任意一个无向图G,PD(G)中几乎所有的概率分布都忠实于它 无向图和正则正态MT P分布将 节中的结果扩展到正则正态分布族,其证明借鉴了文献 中引理 证明的核心想法定理设G是维数为d的无向图,RN(G)在d下的勒贝格测度是正的证明如果将对角线上的每个元素设为(|N|,)中的一个实数,中其余的每个非确定参数在,)中取值,则非确定数可以相互独立地取值注意到用这种方法构造的每个都是正定的,它对应于一个正则正态MT P分布(因为它是一个对称、对角元素为正、严格对角占优的实矩阵(文献 中推论 )即在d中,非确定参数的勒贝格测度为正由文献 中引理,RN(G)的一个子集在d下的勒贝格测度是正的文献 中定理 表明,依据G分解的正则正态分布的集合在d下的勒贝格测度是正的因此,RN(G)在d下的勒贝格测度为正文献 中定理 指出,依据G分解但不忠实于它的正则正态概率分布的集合在d下的勒贝格测度为零于是有下面的结论:推论对任意一个无向图G,RN(G)中几乎所有的概率分布都忠实于它结语本文应用文献 中的方法,证明了具有固定样本空间,且依据一个无向图G分解的正的离散MT P分布构成的集合和G对应的正的离散分布族具有相同的维数;正则正态MT P分布族时有相同的结论换句话说,对无向图和这两类MT P分布,本文的研究完全回答了引言中提到的问题()推论和推论对无向图学习很重要,它们表明忠实性假设在测度论意义下是可靠的东 北 师 大 学 报(自 然 科 学 版)第 卷 参考文献L AUR I T Z E NSL G r a p h i c a lm o d e l sM O x f o r d:C l a r e n d o nP r e s s,:S TUD E NY M P r o b a b i l i s t i cc o n d i t i o n a l i n d e p e n d e n c es t r u c t u r e sM L o n d o n:S p r i n g e r V e r l a g,:P E AJM F a i t h f u l n e s s i nc h a i ng r a p h s:t h ed i s c r e t ec a s eJ I n t e r n a t i o n a l J o u r n a l o fA p p r o x i m a t i o nR e a s o n i n g,():P E AJM F a i t h f u l n e s s i nc h a i ng r a p h s:t h eG a u s s i a nc a s eJ/O L Jo fM a c h i n eL e a r n i n gR e s e a r c h,D O I:/a r X i v KA L I S C H M,B HLMANN P E s t i m a t i n gh i g h d i m e n s i o n a ld i r e c t e da c y c l i cg r a p h sw i t ht h eP C a l g o r i t h mJ J o u r n a lo fM a c h i n eL e a r n i n gR e s e a r c h,():S A D E GH IK F a i t h f u l n e s so f p r o b a b i l i t yd i s t r i b u t i o n s a n dg r a p h sJ J o u r n a l o fM a c h i n eL e a r n i n gR e s e a r c h,():L EHMANNEL S o m ec o n c e p t so fd e p e n d e n c eJ A n n a l so fM a t h e m a t i c a lS t a t i s t i c s,():C O L AN G E L OA,S C A R S I N IM,S HAK E D M S o m en o t a t i o n so fm u l t i v a r i a t ep o s i t i v ed e p e n d e n c eJ I n s u r a n c e:M a t h e m a t i c sa n dE c o n o m i c s,():KA R L I NS,R I N O T T Y C l a s s e so fo r d e r i n g so fm e a s u r e sa n dr e l a t e dc o r r e l a t i o ni n e q u a l i t i e sIm u l t i v a r i a t et o t a l l yp o s i t i v ed i s t r i b u t i o n sJ J o u r n a l o fM u l t i v a r i a t eA n a l y s i s,():K A R L I NS,R I N O T T Y M m a t r i c e sa sc o v a r i a n c em a t r i c e so fm u l t i n o r m a ld i s t r i b u t i o n sJ L i n e a rA l g e b r aa n dI t sA p p l i c a t i o n s,:S L AWS K IM,HE I N M E s t i m a t i o no fp o s i t i v ed e f i n i t eM m a t r i c e sa n ds t r u c t u r el e a r n i n gf o ra t t r a c t i v eG a u s s i a n M a r k o vr a n d o mf i e l dJ L i n e a rA l g e b r aa n dI t sA p p l i c a t i o n s,:F A L L A TS,L AUR I T Z E NSL,S A D E GH IK,e t a l T o t a l p o s i t i v i t y i nM a r k o vs t r u c t u r e sJ T h eA n n a l so fS t a t i s t i c s,():L IB,L IY An o t eo nf a i t h f u l n e s sa n dt o t a l p o s i t i v i t yJ S t a t i s t i c s&P r o b a b i l i t yL e t t e r s,:L AUR I T Z E NSL,UHL E RC,ZW I E R N I KP M a x i m u ml i k e l i h o o de s t i m a t i o ni nG a u s s i a nm o d e l su n d e r t o t a lp o s i t i v i t yJT h eA n n a l so fS t a t i s t i c s,():L AUR I T Z E NSL,UHL E RC,ZW I E R N I KP T o t a l p o s i t i v i t y i ne x p o n e n t i a l f a m i l i e sw i t ha p p l i c a t i o nt ob i n a r yv a r i a b l e sJT h eA n n a l so fS t a t i s t i c s,:ME E KC S t r o n gc o m p l e t e n e s sa n d f a i t h f u l n e s s i nB a y e s i a nn e t w o r k sJ/O L a r X i v,h t t p s:d o i o r g/a r X i v K O L L E R D,F R I E DMAN N P r o b a b i l i s t i cg r a p h i c a lm o d e l s:p r i n c i p l e sa n dt e c h n i q u e sM C a m b r i d g e:M I TP r e s s,:G E I G E RD,ME E KC,S TURMF E L SB O nt h et o r i ca l g e b r ao fg r a p h i c a lm o d e l sJ T h eA n n a l so fS t a t i s t i c s,():HO R NRA,J OHN S ONCR M a t r i xa n a l y s i sM C a m b r i d g e:C a m b r i d g eU n i v e r s i t yP r e s s,:F a i t h f u l n e s so fm u l t i v a r i a t e t o t a l l yp o s i t i v eo fo r d e r t w od i s t r i b u t i o n sa n du n d i r e c t e dg r a p h sL IB e n c h o n g,WANG H u i,Z HANGC h u n n i(S c h o o l o fM a t h e m a t i c sa n dS t a t i s t i c s,X i d i a nU n i v e r s i t y,X i a n ,C h i n a)A b s t r a c t:M u l t i v a r i a t et o t a l l yp o s i t i v eo fo r d e rt w o(MT P)d i s t r i b u t i o n sa n du n d i r e c t e dg r a p h si sc o n s i d e r e d G i v e na n u n d i r e c t e d g r a p hG,i ti sp r o v e dt h a tt h es t r i c t l y p o s i t i v ed i s c r e t e MT Pd i s t r i b u t i o n sw i t h f i x e ds a m p l e s p a c e(r e g u l a rG a u s s i a nMT Pd i s t r i b u t i o n s)t h a t f a c t o r i z e a c c o r d i n g t oGw i t hd i m e n s i o ndh a v ep o s i t i v eL e b e s g u em e a s u r ew i t hr e s p e c tt o d C o n s e q u e n t l y,a l m o s ta l lp o s i t i v ed i s c r e t e(r e g u l a rG a u s s i a n)MT Pd i s t r i b u t i o n s t h a t f a c t o r i z e a c c o r d i n g t oGa r e f a i t h f u l t oGK e y w o r d s:f a i t h f u l n e s s;p o s i t i v ed i s c r e t e MT Pd i s t r i b u t i o n;r e g u l a r G a u s s i a n MT Pd i s t r i b u t i o n;u n d i r e c t e dg r a p h(责任编辑:李亚军)