关于近似消息传递(AMP)中因子图的浅析
1.1图相关概念
- 图：由定点有穷非空集合和节点之间的边集合组成，其表示为G=(V,E)。G表示一个图，V是节点组合，E是边集合。
- 连接点：给定一条边e属于E，两个节点与之相连，可定义e=（v1,v2），则v1和v2互为邻节点，边e依附于节点v1和v2，二者相关联。
- 度：节点的度就是与之相关联的边数量
- 二分图：一个图中的所有节点可以分为两个子集Vx，Vy，且二者之间的节点没有相连的边。
- 路径：节点的序列，两节点存在路径则称之为连通。一条长度为N的路径含有N+1个节点。
- 环：如果一条路径最终回到起点，则为环。
- 连通图：如果一个图所有节点都是连通的，则为连通图。
森林、树、叶：一个图没有环则为森林，连通图没有环则为树。度为1的节点为叶。
1.2因式分解
节点一般用圆圈和方框表示，而变量则用边表示。
则可得
因此可以进一步简单地表示为：
（1）非环图因式分解
（2）连通图因式分解
1.3因子图
因子图是一种表达函数因式分解的图。给定的因式分解，其中一个因子fk，定义其邻接区为所有出现在fk内的变量集合N(fk)。同样，变量Xn的邻接区则为包含变量Xn的因子集合N(Xn)。
给定函数：
其对应的因子图为二分图，则建立过程为：
假设：
表示为因子图如下：
1.4基于因子图的边缘分布与和积算法
计算qx1(X1)需要对
求解边缘分布的方法就是和积算法：
思路：
（1）将式子写成详尽的表达式；（2）用递归的方式来求解边缘分布。
具体步骤：
第一步：划分变量
方法1：数学方法：
首先划分，找到除
之外在所涉及到的所有变量，并找到这些变量涉及的因子，以此循环往复。
方法2：因子图方法
对于变量节点，
，在这三个因子节点中去除
。因此可以得到包含
的因子图有变量节点
，然后对
采用方式得到
，
，
。
根据变量节点，则可以分为
，
第二步：因子分组
方法1：数学方式：
其中，
，
每个相邻的变量对应的因子相乘，每个因子在不同变量节点上相乘，通过递归相乘获得最终的结果。
方法2：因子图方法求解：
从目标的变量节点出发，寻找与之相邻的因子节点，然后沿着因子节点传递，寻找其对应的变量节点，每一层的因子变量节点进行一次乘积，并按照这种搜寻方式不断向下搜寻，直至到达最后的叶节点。
第三步：计算边缘分布
定义：结合和
，可得如下形似：
方法1：数学方法
计算变量的边缘分布，需要引入两个函数:即在任意都有
因此可得边缘分布如下：
方法2：因子图方式