Markovrandomfield

MarkovRandomFieldTutorial1.WhatisMarkovRandomField?Markovrandomfield(MRF)是PGM(probabilitygraphicmodel)中的一种模型(model)，PGM是用图(graphic)的方式表示了联合概率(jointprobability)的分布。由于表示这个联合概率的图的模型具有马尔科夫性质(MarkovProperty)，因此他叫做Markovrandomfield。接下来首先说Markovrandomfield的构成，然后在说什么是Markovproperty。1.1TheStructureofMRFMRF是PGM中的一类无向图(undirectedgraph)模型，无向意思是指变量之间只有依赖关系(dependence)，没有因果关系(non-causal)。其由节点(node)和边(edge)组成，表示为G=(N,E)，其中N代表结点，E代表边。其中每个节点(node)代表一个随机变量(randomvariables)，边代表节点(随机变量)之间的依赖关系。如下图就是一个MRF，下图中A，B，C，D，E节点都表示一个随机变量，然后A和B之间有边，就表示A和B有依赖关系，C和B之间没边，表示C和B独立。设X是节点随机变量的集合表示，即X=}{iX，对于此例子，X={A,B,C,D,E}，则X就是一个随机场。如果X在满足MarkovProperty，则X代表的就是一个MRF。1.2MarkovProperty1.1中说明了Markov的结构组成，提到一个随机场，如果满足Markovproperty就是一个MRF，那么问题随之而来，什么是Markovproperty？给定一个随机变量当前和过去所有的状态，其未来状态的条件概率分布仅依赖于当前状态；换句话说，在给定现在状态时，它与过去状态（是条件独立的），这就是MarKovProperty。写成数学表示的形式如下：)...,,|()|(12111XXXXXPXXPiiiiii比如我们以天气作为随机变量，那其具有MarkovProperty意思就是明天的天气状况只和今天的天气状况有关系，而和昨天的，乃至前天的等等都没有依赖关系。1.3ConditionalIndependent条件独立在PGM中是一个非常重要的概念，给定三个随机A，B，C。条件独立可以定义为，给定随机变量C的情况下，A和B条件独立表示为：)|()|()|,(CBPCAPCBAP或者表示为)|(),|(CAPCBAP这两者是等价的，可以证明。在PGM中，我们可以写成数学表示：CBA|，表示在给定条件C的情况下，A和B独立。下面知己给出一个图像处理中的表示形式，下图节点都表示每一个像素，给定灰色的节点的时候，黑色的节点和白色的节点之间条件独立。2.TwoPerspectivesofPGM由于Markovrandomfield是PGM中的一种模型。为了因此有必要说明下对PGM的两种理解观点，实际中原理的理解都是从这两个角度来的。（1）PGM就是用图的方式表示随机变量之间的相互关系，PGM的节点代表了随机变量，节点之间的边代表了变量之间的相互依赖性，整个PGM表示了联合概率的分布。（2）复杂的联合概率也可以分解为一系列因子(factor)的乘积(product)，即PGM表示的联合概率分布的图也可以分解因子图，给出一个简单的例子。如：),|()()(),,(212121xxypxpxpyxxP,上式表示了联合概率的一个分解。我们可以令因子)()(111xpx，)()(222xpx，),|()(213xxypy，因此联合概率可以表示为)()()(),|()()(),,(32211212121yxxxxypxpxpyxxP，这个过程叫做PGM的因子化。下图就是对这个例子从表示变量相互依赖的概率图转换为因子图，也叫做Gibbsdistribution。刚才只是粗略的提到了理解PGM的两种概念，因子分解的这种理解在概率图中是非常重要的，因此接下来详细说一下PGM中的无向图如何因子分解。2.1概率无向图模型的因子分解2.2GibbsdistributionofMarkovrandomfield依据2.1中所述，对于一个Markovrandomfield,AGibbsdistributiononthegraphGtakestheform:CccCxZxp)(1)(wheretheproductisoverallmaximalcliquesinthegraph.Acliqueisasubsetofnodesinwhicheverynodeisconnectedtoeveryothernode.Amaximalcliqueisacliquewhichcannotbeextendedbytheadditionofanothernode.Ziscalledthepartitionfunction,andtakestheform:xCccCxZ)(The)(cCxareusuallywritten:)(1)(cCxVTcCexTiscalledthetemperature,andisoftentakentobe1.So)(xPhasthealternateform:)(11)(xUTeZxPWhereCccxVxU)()(iscalledtheenergy,Eitherthe)(cCxorthe)(cCxVmaybereferredtoascliquepotentials.TheHammersley-CliffordtheoremstatesthatthejointprobabilitydistributionofanyMRFcanbewrittenasaGibbsdistribution,andfurthermorethatforanyGibbsdistributionthereexistsanMRFforwhichitisthejoint.Thatistosay,Hammersley-CliffordestablishestheequalityoftheMRFandGibbsmodels.ThissolvestheproblemofhowtospecifythejointdistributionofanMRFintermsoflocalfunctions:itcannowbespecifiedbydefiningthepotentialoneverymaximalclique.3.OptimisationAnoptimisationproblemisonethatinvolvesfindingtheextremumofaquantityorfunction.Suchproblemsoftenariseasaresultofasourceofuncertaintythatprecludesthepossibilityofanexactsolution.OptimisationinanMRFprobleminvolvesfindingthemaximumofthejointprobabilityoverthegraph,usuallywithsomeofthevariablesgivenbysomeobserveddata.Equivalently,ascanbeseenfromtheequationsabove,thiscanbedonebyminimisingthetotalenergy,whichinturnrequiresthesimultaneousminimisationofallthecliquepotentials.TechniquesforminimisationoftheMRFpotentialsareplentiful.ManyofthemarealsoapplicabletooptimisationproblemsotherthanMRF.Forexample,gradientdescentmethodsarewell-knowntechniquesforfindinglocalminima,whiletheclosely-relatedmethodofsimulatedannealingattemptstofindaglobalminimum.AnexampleofatechniqueinventedspecificallyforMRFoptimisationisIteratedConditionalModes(ICM).Thissimplealgorithmproceedsfirstbychoosinganinitialconfigurationforthevariables.Then,ititeratesovereachnodeinthegraphandcalculatesthevaluethatminimisestheenergygiventhecurrentvaluesforallthevariablesinitsneighbourhood.Attheendofaniteration,thenewvaluesforeachvariablebecomethecurrentvalues,andthenextiterationbegins.Thealgorithmisguaranteedtoconverge,andmaybeterminatedaccordingtoachosencriterionofconvergence.Anexampleofthistechniqueinactioncanbeseenbelow.4.MRFApplicationsToVisionProblemsincomputervisionusuallyinvolvenoise,andsoexactsolutionsaremostoftenimpossible.Additionally,thelatentvariablesofinterestoftenhavetheMarkovproperty.Forexample,thepixelvaluesinanimageusuallydependmoststronglyonthoseintheimmediatevicinity,andhaveonlyweakcorrelationswiththosefurtheraway.Therefore,visionproblemsarewellsuitedtotheMRFoptimisationtechnique.SomeexamplesofvisionproblemstowhichMRFshavebeenappliedare:(1)Imagerestoration;(2)Imagereconstruction;(3)Imagesegmentation;(4)Edgedetection;Inthefirst3ofthese,thereisalatentrandomvariableforeachpixel.Thevariablesrangeoverintensityvaluesin1and2,whilein3thevariablestakeonsegmentidentifiers.Inproblem4,thevariablescorrespondtopairsofneighbouringpixels,andtheirvaluesarebinary,indicatingthepresenceorabsenceofanedge.Inallcases,theneighbourhoodconceptoftheMRFmapstothegeometricneighbourhoodoftheimage.Thatistosay,theedgesintheMRFgraphwillconnectgeometri