因子图与和-积算法

因子图与和-积算法Factorgraphandsum-productalgorithm孙伟概述：图模型（graphicalmodel）、因子图（factorgraph）、和-积算法（sum-productalgorithm）:1）常见的电路图、信号流程图、格子图以及各种框图都属于图模型的范畴；2）因子图（factorgraph）是图模型的一种；3）因子图的典型代表是Forney-stylefactorgraph，简称FFG。4）和-积算法又称“概率传播(probabilitypropagation)算法”或“置信传播(beliefpropagation)算法”,意味着图模型（graphicalmodel）中的信息传递；5）编码领域、信号处理、人工智能方面的大量算法实际上都可看作和-积算法的实例；检测、估计方面的一些新算法也可看作和-积算法的衍生实例。编码领域、信号处理、人工智能等方面的大量算法实际上都可看作和-积算法的实例：具体的应用实例：1）卡尔曼滤波（Kalmanfiltering）（especiallyintheformoftheRLSalgorithm）；2）隐马尔可夫模型的前向-后向算法（forward-backwardalgorithmforhiddenMarkovmodels）;3）贝叶斯网络中的概率传播（probabilitypropagationinBayesiannetworks）;4）解码算法：例如针对纠错码的Viterbi算法，BCJR算法等解码算法；例如针对turbocodes，LDPCcodes等的循环解码算法。1.因子图（factorgraph）：1）典型代表FFG（Forney-stylefactorgraph）FFG优点：支持分层建模，兼容标准框图；以后都用FFG来描述;2）FFG：代表对一个函数的因子分解（一个全局函数分解为若干个局部函数）例：函数f(u,w,x,y,z)可以分解成下面三个因子式，其FFG如下图所示。𝑓(𝑢,𝑤,𝑥,𝑦,𝑧)=𝑓1(𝑢,𝑤,𝑥)𝑓2(𝑥,𝑦,𝑧)𝑓3(𝑧)3）FFG的定义规则一般而言，FFG由结点，边缘，半边缘（只与一个结点连接）组成；FFG的定义规则如下：a)每个因子对应唯一的结点；b)每个变量对应唯一的边缘或者半边缘；c)代表因子g的结点与代表变量x的边缘（或半边缘）相连，当且仅当g是关于x的函数。例：在左图中,3个结点对应3个因子2个边缘对应2个变量x,z;3个半边缘对应3个变量u,w,y;123,,fff123(,,,,)(,,)(,,)()fuwxyzfuwxfxyzfz割集独立原理（Cut-SetIndependenceTheorem）:假设一个FFG代表关于若干随机变量的联合概率分布（或联合概率密度），进一步假设对应于其中一些变量的边缘组成了一个割集（换言之，移除这些边缘将图表分割成了不相连的两部分）。在这种情况下，以（即任何确定值）为条件，一部分图表中的每个随机变量（或这些随机变量组成的任意集合）与另一部分图表中的每个随机变量（或这些随机变量组成的任意集合）都是相互独立的。例：下图是一个表示一个马尔可夫链的FFG。变量x,y,z的联合概率密度若将边缘Y移除，则图表被分割成不相连的两部分，运用割集独立原理，则有1n,...,YY11n,...,nYyYy1n,...,yy||(,,)()(|)(|)XYZXYXZYpxyzpxpyxpzy(,|)(|)(|)pxzypxypzyFFG应用举例：线性状态空间模型（linearstate-spacemodel）注1：若假定U[.]和W[.]是高斯白噪声过程，则图表中的相应结点就代表高斯概率分布函数（例：如果U[.]是个标量，则左图中最左上方的结点就代表函数）注2：由此例可看出，在一个FFG中，“可见的”外部变量由半边缘表示，“隐藏的”内部变量由（全）边缘表示。显然，一个子系统的外部变量可能是整个大系统的内部变量。[][1][][][][]XkAXkBUkYkCXkWk22(1/2)([]/2)fukexp-2.和-积算法（sum-productalgorithm）汇总传播算法（summarypropagationalgorithm）:1)和-积算法（sum-productalgorithm）；2)最大值-积算法（max-productalgorithm）(ormin-sumalgorithm)这里重点讲述和-积算法；和-积算法的推导：由求解边缘函数推导出和-积算法前面的例子说明引入辅助变量（状态变量）可以得到结构更优的模型，现在我们考虑消除某些变量。实际上，求解边缘函数就是通过汇总运算（”summaryoperator”）实现对变量的消除。由求解边缘函数推导出和-积算法：例：假设函数f可用如下左图所示的FFG表示，即考虑边缘函数（边缘概率），即则可用如下右图所示公式表示。1235678418,,,,,,()(,...,)xxxxxxxpxfxx4()px4()px18112231234445655667877(,...,)(()()(,,,))((,,)()((,,)()))fxxfxfxfxxxxfxxxfxfxxxfx求解边缘函数的思路：对内部变量分别进行汇总计算，“关闭”盒子（closingthebox），即分块消除内部变量。因子：对左图中左边虚线所围盒子的内部变量的信息汇总；因子：对左图中右边虚线所围小盒子的内部变量的信息汇总；因子：对左图中右边虚线所围大盒子的内部变量的信息汇总；最终，“关闭”所有盒子（即消掉了除以外的其他所有内部变量）之后，得到局部消除性质（LocalEliminationProperty）：一个全局的信息汇总（通过求和或者积分）可以由连续的子系统的局部信息汇总得到。34fxu44fxu66fxu3444444()()()fxfxpxuxux4x现在考虑信息的传递，如上图所示，有三种情况：从“关闭”盒子流出的信息：是盒子内部的信息汇总；从结点（例）流出的信息：是结点对应的函数本身；半边缘（例）携带的信息：不携带任何信息，或者可认为代表常数因子1；3x1f由上面的分析可推得和-积算法和-积算法(sum-productrule)：沿着边缘x从结点（因子）g传递出的信息是g和沿着除x以外其余所有边缘传入的信息的乘积，然后对除x以外其余所有相关变量进行求和的结果。即：其中，代表沿着边缘到达g的信息。1n111()(,,...,)()()ngxnygygnyyuxgxyyuyuykyguky由sum-productrule计算边缘函数：1），即边缘概率为沿着边缘的两个方向的信息的乘积；2）对于所有k，边缘函数能够同时得到；(分析：在非循环因子图中，初始信息从叶子结点或半边缘传入，在两个方向上信息各传递一遍，因而所有边缘对应的边缘概率都能同时得到)()kpxkx()kpx11,...,except()(,...,)()()nxkknkkxxpxfxxuxux()()()kkkpxuxux注：1）和-积算法适用于任何非循环因子图；2）半边缘（openhalf-edges）不携带任何的传入信息，或者说携带的信息为常数因子1；3）已知变量（例如前面提到的，可理解为常数）只是简单地融入相应的因子，并不作为相关变量参与到算法中；4）一般而言，得到正比于一个比例因子（uptoascalefactor）的边缘函数就可以满足需求，在这种情况下，信息只取决于一个比例因子。KKYy补充：最大值-积算法（max-productrule）：沿着边缘x从结点（因子）传递出的信息是g和沿着除x以外其余所有边缘传入的信息的乘积，然后对除x以外其余所有相关变量进行最大化的结果。即：实际上，sum-productrule和max-productrule都符合下面同一个规则：summary-productrule:沿着边缘x从结点（因子）传递出的信息是g和沿着除x以外其余所有边缘流入的信息的乘积，然后对除x以外其余所有相关变量进行信息汇总的结果。注：运用这个规则的前提条件是因子图没有循环。11n11()maxmax(,,...,)()()ngxyynygygnuxgxyyuyuy3.因子图MATLAB程序3.1因子图MATLAB程序设计流程非循环因子图：1）instantiatenodes：即用唯一的整数标注每一个结点，让每一个结点拥有唯一的ID；2）defineconnections：用setup_link()函数和connect()函数定义连接；3）initializeparameters：例如对cpt_node的参数cpt进行初始化，对Is_gain2_node的参数gain进行初始化；4）giveevident：通过setup_init_msg()函数给予结点(evident_node)相应的已观测事件的信息（这种信息称为“evident”，承载这种信息的结点称为“evident_node”）；5）getmarginalvalues：通过marginal()函数或者Is_marginal()函数计算得到边缘概率。循环因子图：1）初始化全局变量loopy，将其置为1；2）对于线性标量因子图，初始化linear_scalar，将其置为1；3）instantiatenodes：即用唯一的整数标注每一个结点，让每一个结点拥有唯一的ID；4）defineconnections：用setup_link()函数和connect()函数定义连接；5）initializeparameters：例如对cpt_node的参数cpt进行初始化，对Is_gain2_node的参数gain进行初始化；6）giveevident：通过setup_init_msg()函数给予结点(evident_node)相应的已观测事件的信息（这种信息称为“evident”，承载这种信息的结点称为“evident_node”）；7）通过update_node()函数对每一个结点进行更新；8）通过设置迭代终止条件或者完成预设的迭代次数之后，终止更新。3.2具体实例应用分析1）因子图测试程序（factorgraphtest）；2）隐马尔可夫链（hiddenmarkovchain）;3）卡尔曼滤波（kalmanfiltering）程序段1程序段2程序段3这是一个因子图的测试程序，目的是实现偶校验:1）p,q,r,s四个结点都是代表相应已观测事件的evident_node（如前所述，这种结点只是为了承载相应事件的观测信息，并非因子结点）；m,n二个因子结点都是偶校验结点(even_parity_node);2）从程序段3和程序段4可以看出，对p,q,r,s四个evident_node赋予的初始观测信息为“0,0,1,0”，即evidents：p,q,r,s=0,0,1,0时，计算每个边缘对应的边缘概率；3）从程序段5可以看出，将q重置为1，即evidents：p,q,r,s=0,1,1,0时，计算每个边缘对应的边缘概率。程序段4程序段51）：factorgraphtest程序运行结果：实验结果分析：从边缘概率来看，1）在p,q,r,s=0,0,1,0时，linkmn:0.5000,0.5000，即上面两个叶子结点的偶校验结果和下面两个叶子结点的偶校验结果为1,0（或0,1）的概率相等，即上下两部分偶校验的结果必然为：一个是偶数个1，另一个是奇数个1。2）在p,q,r,s=0,1,1,0时，linkmn:0.0460,0.9540，即上面和下面的偶检验的结果都是1的可能性非常大（0.04600.9540），可判定为1，即上下都是奇数个1。3）下图以p,q,r,s=0,0,1,0为例呈现了因子图中的信息传递过程，即通过和-积算法计算边缘概率。2）：隐马尔可夫链（hiddenmarkovchain）问题