There are three kinds of probabilistic graph, namely (1) directed graph(Bayesian network); (2) undirected graph(Markov network); (3) hybrid graph(Chain graph). We can represent the joint distribution over a Bayesian network by chain rule, and represent a joint distribution over a Markov network as products of potentials. Then the graph is an I-map of the distribution, and we can use d-separation principles to find conditionally independent variables in the joint distribution. HMM is a typical directed graph and RBM(Restricted Boltzmann Machine) is a typical undirected graphical model. However, in real applications, sometimes we would make use of hybrid graph models. Taking CRF(Conditional Random Field) as an example. For depth estimation in stereo computer vision, CRF is a competing model, which is a hybrid model, with undirected links among depth values and directed links between depth values and features. So CRF in this case is named as Chain graph. How to represent this hybrid graph using probabilities? Usually, we use products of CRF distributions as its joint probability distribution. Then how can we determine whether two groups of variable are conditional independent or not? In the chain graph, we will use c-separation principles. By the way, chain graph is a generalization of directed graph and undirected graph. Therefore, probability representation and independence determination in Bayesian Network and Markov Network are specific cases to those in Chain Graph.
CRF and MRF are two popular graphical models, which is an intuitive model to model all kinds of networks. Recently deep belief network has aroused a huge surge in Machine Learning community, and it got state of the art results in numerous fields, like object recognition, acoustic understanding and topic modeling. DBN is also one kind of graphical models. As we know, CRF is a discriminative model, while MRF is a generative model. Naive Bayes is probably the simplest MRF, while logistic regression is one kind of simple CRFs. The key difference between these two kinds of models is that: MRF is trying to model a joint distribution p(X,Y), however, CRF aims to build a conditional distribution p(Y|X). To be more clear, there are no kinds of potential functions like g(x1,x2) in CRF. Nevertheless, the learning methods procedures are quite the same, and maximum likelihood works for both model. By the way, for parameter learning in DBN, Prof. Hinton developed a method called contrastive divergence, which is pseudo-likelihood. One important theorem in undirected graph is: Hammersley-Clifford theorem: a positive distribution p(y) 0 satisfies the conditional independence properties of an undirected graph G if and only if p can be represented as a product of factors, one per maximal clique.
概述 贝叶斯网(directed acyclic graph), MRF( undirected graph)是两种重要的概率图模型，在日益网络化的世界里，它们能对众多事物、现象合理建模，包括：社交网络（facebook, twitter)、交通网络（transportation,travel,network design)、医疗诊断等等，Russell还用它建立全球的crust vibration network, 用以分析预测 核武器生产地、地震。从马克思哲学的角度讲，运 动着的物质世界是普遍联系和永恒发展的，这种联系正是可以用图模型来模拟，而发展便是图模型的inference,看来Bayesian Network, MRF确实是广泛、客观存在的规律。从计算机视觉、机器学习专业领域来看，它更有着广泛的应用、很大的research community。 Equivalence of Joint Distribution and Graph 本质上来讲，用graphical model解决一个问题，首先是要知道变量间的独立关系（independency among variables),这样才便于建立图（I-Map)。需要说明的是，无论是bayesian network,还是MRF,他们的定义是（P,G),也就是同时定义概率和图，在joint distribution 严格 positive的情况下，联合分布和图是等价的：图是联合分布的I-Map,联合分布也能factorize over the graph。另外，对于贝叶斯图，概率分布在图上的factorization的定义很简单，而对于MRF，factoriztion的定义是：Joint distribution中每个factor都是图H的complete subgraph。注意了： complete subgraph并不是 maximal clique，也就是，如果我们建立的图模型中，每三个变量组成一个clique,这时，与这个图结构compatible的joint distribution完全可以是pairwise的clique potentials相乘而得到的。不过如果我们建立的图结构是每3个variable组成一个clique,我们会随之而建立 tri-order clique potentials相乘的gibbs distribution, 而不是 pairwise Markov models. Drawback 从机器学习的角度来讲，MRF和bayesian network都是parametric methods,他们最大的弊病是对模型要假设，然后训练模型参数；to one extreme， 模型完全符合实际，这样当然很好的解决了问题；to another extreme，先验模型is problematic,now we actually deviate from original problems. 所以William Freeman(MIT)写了一篇文章，用MRF求立体视差，能量低并不代表disparity map is closer to ground truth.换言之，MRF model contructed is not compabible with truth.这个问题怎么解决？ introduction of kernal will work? 下面推荐三篇paper: 1. Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters , 2003, Tappen 2. Robust higher order potentials for enforcing label consistency , 2009, P. Kohli 3. An application of markov random fields to range sensing , 2006, J. Diebel
前一篇博文写到了MRF在视觉中的应用，它实际是对问题建立graphical model, 然后用bayesian probabilistics的方法做Inference。在建立图模型前，要首先定义vertex/edge/neighborhood,而后续的estimation和inference是基于建立好的图模型的，所以如果一个问题中，vertex(也可以说object)是变化而不是固定的（此时的图模型变了），MRF变得不再实用。 然而，point process(也称为object process,因为它是面向对象的）能对number不固定、shape可变化的对象建模，所以能很好的解决视觉中的某些inverse problems,如object extraction/texture synthesis。Point process率属于随机过程理论，能把prior geometry information用概率来建模，但它与MRF不同在于，它把随机理论用到estimation中，所以Object的数量、参数是随着求解过程变化的。虽然概率模型和MRF中的概率一样是definite的，可是求解中的stochastics使得points in the distribution 更flexible.(MRF中的points，也就是objects,是固定的)。 point process涉及到测度理论和随机过程，当应用到视觉中时，常用gibbs energy 来描述这个point process。接下来就是求最小能量，常用的方法是RJMCMC外加simulated annealing 策略，为了加快收敛速度，在高温使用jump策略，低温使用diffusion. 目前看到的point process的成功案例是其在图像特征提取中的应用，法国的一个研究所INRIA在这方面做了大量的工作。 下面是一些资料： RJMCMC: Reversible jump Markov chain Monte Carlo computation and Bayesian model determination ， PJ Green - Biometrika, 1995 stochastic geometric models: Stochastic geometry models in high - level vision, AJ Baddeley, 1993 PAMI 2010: geometric feature extraction by a multi-marked point process, florent lafarge, 2010
Markov Random Fields(MRF)是undirected graph的概率表示，下面说说它在computer vision中的应用。 MRF应用在视觉中，相当于一个Labeling问题，更具体点，是通过MAP inference来确定图中每个节点的label。MRF相比其他方法的优势是：1）提供了一种principled method来对Prior knowledge建模，2）MRF可以很容易用定量的方法描述contextual information。 因此，相比其它pixel-based, 或local-based 方法，它可以考虑到环境知识的影响，如果建立的图模型得当，进而可能获得全局最优解释，这样正是向human vision更靠近了一步。 说到MRF的Inference，首先必须有 graph construction, parameter learning,最后才是Inference，图的创建一般是对问题本身的建模，比如在image restoration 和image segmentation中，常用到4-neighborhood或8-neighborhood的pairwise模型，这样，4-或8-相邻的像素中间便用边连接，这样的模型就是paradigmatic pairwise Markov model,如果要加入高阶（=3)的potential，相当于我们引入了更多的约束，比如：connectivity 约束、非基督分类结果的约束..., 说到非监督分类结果的约束，要注意的是：一定是其他分类方法，而非MRF本身的分类结果累构成新的约束。 MRF中参数学习方法在此略过，后续补充。 下面重点说MRF inference问题，即解求能量函数最小能量的问题。对于经典的只有unary 和 binary potential的MRF模型，graph cut已经能够在Linear time内进行求解，如果加入更高的potential,虽然问题本身可能变成了NP-hard，仍然有很多近似算法，比如Loopy belief propagation(LBP)，tree-reweighted message passing(TRW),Metropolis-Hastings,MCMC等等。撇开这些方法，其实问题的实质是 energy minimization，值得一提的是CVPR现在有个workshop是专门讨论这个问题的，叫做energy minimization methods in computer vision and pattern recognition (EMMcvpr). 组织者是：Yuri Boykov（UWO）, Fredrik Kahl, Victor Lempitsky ,Vladimir Kolmogorov(UCL), Olga Veksler(UWO),个个都活跃在算法、离散数学、变分法、图论等领域的前沿，所以大家对能量最小化的优化方法感兴趣的可以经常关注这些教授的主页，他们也主要做计算机视觉方面的应用，所以他们的publication会多数发表在ICCV,CVPR,ECCV,NIPS上面。 上面粗要的概述了MRF的三个步骤，下面谈谈自己对MRF的看法： 1）虽然它是通过MAP获得整体的maximal likely solution,但是，如果对问题本身建模时，只考虑到了局部约束，则：MRF得到的结果仍然是局部的，比如考虑最经典的影像分割，如果只用到pairwise Model，则很可能把一个完整的物体分割成了2块甚至更多块。2）当引入更多的constaints时，不同的约束如果非独立，而通常，我们使用Gibbs Distribution来描述Markov Network,不同的potential是相加的关系，转化到概率，则是相乘，就是不独立的两个clique直接相乘了，所以此时存在参数的冗余（redundency),所以Parameter learning时，要解决这个问题 （这个问题在测量数据处理中叫 参数的显著性检测）。 下面分享一些好的资料： A tutorial of MRF on CV: Markov random field models in computer vision (E CCV 94, S.Z. Li) MRF inference, Prof. Yuri: http://www.csd.uwo.ca/~yuri/ Prof. Richard Szeliski : A comparative study of energy minimization methods for markov random fields . Richard 的计算机视觉教材 Computer Vision: algorithms and applications 正在被全球很多大学使用，有取代 Computer Vision：a modern approach, multiview geometry in computer vision 等权威教材的趋势。 code: http://vision.middlebury.edu/MRF/
标签: MRF
