概率图模型 | 您所在的位置:网站首页 › 口琴内部结构分解图 › 概率图模型 |
概率图模型–精确推断算法的原理
本文主要内容 本文从可分解图出发,逐渐引入弦图,三角化图,然后揭示了为什么引入可分解图,因为可分解图是在连接树算法中最终得到的,还讲解了为什么要使用连接树算法,因为连接树算法可以解决不是树的图结构的推断问题,还可以获得团上变量的联合概率分布,从而对单个变量的边际分布的推断就只在包含查询变量的团上进行即可,这也远远减少了计算步骤。本文最后附带了我写这个博客的时候使用的简答R代码阅读本文可能需要对概率图模型有一定了解的人(当然我也是学习阶段,小白一个) 可分解图的引入读论文的时候先遇到的可分解图,那首先给出分解的定义: 修改gRbase包里面的mpd()函数是找出对应的分解,只利用到下面的分解的概念,不要理解成mpd()里面的图必须是弦图 图存在分解与图是可分解图是不一样的概念,我的论文里面要求的是可分解图,用mcs()函数进行可分解图的检验
在第一个可分解图当中,可以有两个真分解,分别为 A1={A},S1={B},B1={C,D} A2={A,B},S2={C},B2={D}, 最大团有三个,分别为C1(A,B),C1(B,C),C1(C,D),分离集分别为S1={B},S2={C} 其中还有重要的一步,不是存在真分解就一定是可分解图,还要求真分解之后的子图也存在真分解或者子图是完全图,只有再满足这个条件,才可以说原来的图是可分解图 ,大家可以自已验证满足这个条件 以上的处理是为了得到联合概率的简单表示,对于无向图来说联合概率可以分解为定义在最大团上的势能函数的乘积再进行归一化,公式为 那么如果我们的无向图是可分解图的话,联合概率就可以表示为
首先我们要知道弦图和可分解图是等价的 弦:如下图,下图是一个节点为5的环,这个环中A,C之间,A,D之间,B,E之间,C,E之间没有连接,如果加入边集AC在这个图里面,那么AC就称为该图的一条弦,同理加入边集AD在这个图里面,那么AD也称为该图的一条弦,注意BD之间加边就不叫弦了。 如果有个无向环图中,任意大于等于四个节点的环都有一个弦,那么这个图就称为弦图,如下图所示,下面这个图就是弦图,首先第一步是在5个节点的环中添加弦AC,添加弦AC之后又形成了新的环ACDE,所以又添加了新的弦AD,此时形成的图就满足了定义,大于三个节点的环中都有了弦,这个图为弦图,
因此我们的目的就可以换成检验一个图是不是弦图,检验弦图我们有方法, 检验图是不是弦图,就是检验这个图有没有完美消元序 那么真正的判定方法是什么呢,这里引用博客,先从最朴素的算法理解,说的是每次找出一个单纯点,然后把相关的边都删除,重复进行,如果最后所有的点都被删除了,那么就说明得到的删除节点的序列是最优的,那么该图也就是弦图 引用博客当中对单纯点进行了介绍,单纯点就是如果一个节点的邻居节点是全连接的,那么这个节点就是单纯点正如上面的那个图节点1就是单纯点,因为2,3有连接,同理节点2就不是单纯点,因为1,4没有连接,那么现在就利用这样原始的朴素的办法进行判断,1,4,5都是单纯点,假设第一次删除的是1,那么把1和相对应的边删除以后,得到的新的图的单纯点为2,4,5,假设删除的是2,那么得到的新图的单纯点为4,5,假设删除的是4,那么剩下的图只有3,5,3,5都是单纯点,随便删掉一个,剩下 的那个点自已也是单纯点,所以按照每一步都删除单纯点的方法,可以把图中的点全部删除,所以该图是弦图 还有用的最多的算法是MCS算法(最大势搜索算法)利用最大势搜索 最大势搜索算法可以给出一个节点的消元顺序,注意不管是不是弦图都可以给出一个消元顺序,给出的这个消元顺序应该是代价最小的(当然这是我理解的),然后对这个消元顺序再利用最优消元顺序的定义进行判断,若满足,那么给出的这个节点顺序就是最优的节点顺序,拥有了最优的节点顺序,那么它就一定是弦图。 所以在我看来,逻辑是这样的,我们想要判断是不是弦图,判断弦图需要利用节点的最优消元顺序,那么最大势搜索算法(MCS)给出我们一个节点的消元顺序,就对这个顺序进行定义的判断,若符合,那么这个次序就是最优节点顺序,该图就是弦图 由此可以最优节点顺序不唯一,只有有一个这样的最优节点顺序,那么这个图就是弦图 上面谈到了弦图,我们知道弦图就是可分解图,利用可分解图我们可以更好的写出联合概率分布,可分解图还是针对无向图来说的,我们下面把有向图上的联合概率串起来 下面给一个复杂一点的有向图 这个有向图的端正图(道德图)为下图,道德图的意思是把有向图当中的箭头变成无向的,然后把配偶节点用无向边相连。如A,B之间,C,D之间是配偶。 道德图就是结构图,在结构图当中进行消元代价的计算,比如为了计算p(A),需要消除B,D,C,E,F,G,H, 假设我们就按照这样的顺序进行消元,消除B时,我们从下图可以看出B的邻居节点为A,C有两个,加上B自已有三个变量,假设每个变量都是二值离散变量,那么消除B的代价为2^3=8,消除B的具体过程为 在下面这个最原始的结构图中把与B节点相邻的节点两两相连,A,C相连,由于AC本来就是相连的可能会忽略这个过程,如果AC之间原来没有无向边相连,那么在消除B时也需要首先把他们连在一起在结构图中把B节点去掉,那B节点不在了,与B节点连接的边自然而然就不在了消除B之后就会形成新的结构图,在新的结构图上计算消除节点的代价,下一个消除的是D,消除C时同样按照这样的过程 首先与D相邻的节点为C,E,检查CE之间是不是有边相连,若没边则加边删除D节点和与D相连的边消除节点D一共涉及了三个变量C,D,E,所以消除D的代价为2^3=8 对于有向图来说 . 首先进行道德化得到结构图(道德图) 然后对得到的无向图,给出一个节点顺序(可以通过MCS算法),利用这个节点顺序进行加边操作(三角化操作) 三角化之后得到的图就是弦图,也就是可分解图,对这最终的无向图可以转换成一个聚类树的形式,(我认为转换成聚类树是为了让我们直观的看出来最大团集合分离集是什么样的 对于无向图来说自然没有上面的道德化的过程,只有三角化的过程和转换成聚类树的过程 最终得到的无向图为 大家可以看一下,普通树上的信念传播算法方便了计算边际分布,把每个消息储存起来,不用重复计算,但是我们要知道普通树结构非常有局限,只能适用于部分有向图和无向图(默认大家知道什么是数结构),为了加深记忆,我还是写一下树结构吧,树结构可分为有向树和无向树 如果一个有向图满足任意两个变量只有一条路径(忽略方向)且只有一个没有父节点的节点,那么这个有向图为树结构,其中唯一没有父节点的节点称为根节点如果一个无向图满足任意两个变量只有一条路径,那么这个无向图也为树结构,在树结构的无向图当中,任意一个节点都可以作为根节点下面展示一下普通的有向树(左)和普通的无向树(右) 本篇文章应该算是我对概率图模型里面的精确推断算法的完整总结了,可能以后用的也不多,主要用的是近似推断算法里面的MCMC算法,但是自已进行梳理以后发现知识真的是融汇贯通的。 参考文献图模型的结构_分解和可压缩性_王晓飞 probabilistic graphical models principles and applications by luis enrique sucar (z-lib.org) Learning Probabilistic Graphical Models in R by David Bellot (z-lib.org) https://blog.csdn.net/u011815404/article/details/99188055 代码本文的简单R代码,因为有些图是自已生成的 library("parallel") library("BiocGenerics") library("gRbase") library("gRain") library("graph") library("grid") library("Rgraphviz") p1=ug(~A:B+B:C+C:D) plot(p1) p2=ug(~A:B:D+B:C:D) plot(p2) p3=ug(~A:B+B:C+C:D+D:E+E:A) plot(p3) p4=ug(~A:B:C+A:C:D+A:D:E) plot(p4) p5=dag(~A+B:A+C:B+D:C) plot(p5) p6=dag(~A+B+D+C:A:B+E:C:D+F:C+G:E+H:E) plot(p6) p7=moralize(p6) plot(p7) |
CopyRight 2018-2019 实验室设备网 版权所有 |