多元全正二序分布于无向图的忠实性.pdf
《多元全正二序分布于无向图的忠实性.pdf》由会员分享,可在线阅读,更多相关《多元全正二序分布于无向图的忠实性.pdf(5页珍藏版)》请在咨信网上搜索。
1、第 卷第期东 北 师 大 学 报(自 然 科 学 版)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 收稿日期 基金项目国家自然科学基金资助项目()作者简介李本崇(),男,副教授,主要从事图模型、代数统计研究多元全正二序分布于无向图的忠实性李本崇,王慧,张春妮(西安电子科技大学数学与统计学院,陕西 西安 )摘要考虑了多元全正
2、二序(MT P)分布和无向图问题给定一个无向图G,证明了具有确定样本空间,且可依据d维无向图G分解的严格正的离散(正则正态)MT P分布在d中的勒贝格测度为正因此,几乎所有依据G分解的正的离散(正则正态)MT P分布都忠实于无向图G 关键词忠实性;正的离散MT P分布;正则正态MT P分布;无向图 中图分类号O 文献标志码A引言图可以用来描述概率分布的条件独立结构图中的顶点表示随机变量,它表示的条件独立情形由与其对应的特定类型的分离准则来确定关于概率分布和图之间的联系,基本问题有两个:()给定一个图G,是否存在一个概率分布P(或一族分布),使得两者对应的条件独立情形构成的两个集合是相同的,即P
3、忠实于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
4、 P分布文献 提供了一个结构学习的视角,指出正则正态MT P分布忠实于其成对独立图,它是一个无向图文献 中给出了MT P分布与条件独立相关的一些性质,证明了任一无向图存在一个忠实的正态MT P分布文献 证明了每个无向图都存在一个具有固定样本空间的正的忠实的离散MT P分布文献 研究了正态MT P分布的极大似然估计的存在性文献 证明了MT P分布构成的指数族是凸的,并给出了极大似然估计存在的条件本文讨论上面提到的问题()受文献 ,中所用方法的启发,本文将文献 中的两个单个分布存在的结果推广到测度论情形证明了具有固定样本空间,且能依据d维无向图G分解的严格正的离散MT P分布(正则正态MTP分布)
5、,在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
6、 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(
7、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
8、与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,
9、(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
10、 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的矩
11、阵,其中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)设为 如果一个参数可以独立于其他参数而取不同的值,则称它为可自由设定的在参数化时,称可自由设定的参数的个
12、数为无向图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)的列按 ,排列,
13、则单项式映射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()是相关参数的有理函数事实上,通过将每个势函数分配给包含其所对应变量的一个团,并将分配给每个团的所有势函数相乘,得到一个
14、团势函数,就可以将任意一个依据完全子图分解的分布转换成公式()的形式本文用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
15、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)中几乎所有的概率分布都忠实于它 无向图和正的离散
16、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相关的可自由设定参数
17、的值为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)中的每个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多元 全正二序 分布 忠实
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。