CMU10-708的Lecture3，主要内容是介绍概率图模型中的因子图和精确推理等内容
因子图Factor Graph
因子图提供了一种同时可以用来表示有向图模型和无向图模型的方法，它将概率图模型中不同变量之间的联合分布转化成因子的势能函数之间的乘积。它可以用在马尔可夫随机场(无向图模型)，条件随机场和贝叶斯网络(有向图模型)等多种不同的概率图中，非常General
因子图的生成方式如下图所示，对于有向图模型，我们可以将图模型中所有的联合概率分布转换成对应的因子，同时入度为0的节点(即不受其他点的概率分布的约束)还有自己对应的因子，因为这些节点自己就是一个边缘分布，而在无向图模型中，所有的最大团可以转换成一个对应的因子。
我们可以将一系列因子表示为
例子1如下图所示，这是一个有向图模型，再转化成因子图之后，原本的联合分布中一定会出现的条件概率分布就可以转化成因子对应的势能函数
因子图的一个好处是可以把原本绕来绕去的图结构转化成了树形结构，无向图模型对应一个无向树(需要我们自己选择根节点)，而有向图模型对应一个有向树。有向树的联合分布可以进一步表示成：
MRF和CRF的区别
MRF是马尔可夫随机场，它就代表了一个变量y的概率分布，在因子图表示中，势能函数以及配分函数都是概率图模型参数的函数，即：
Exact Inference
下面我们来考虑如何在概率图模型上进行Exact Inference，即精确地计算某个变量的概率分布情况。我们首先从最简单的方法开始。
Naive Inference
我们用一个简单例子，如下图所示，概率图中一共有5个变量，我们要精确地计算某个变量的概率分布，就需要知道Partition Function(配分函数)的值，即上面说的Z函数。
我们在计算这个概率图模型的配分函数的时候，就需要计算：
变量消去法
变量消去法(Variable Elimination)是一种Exact Inference的简化算法，对于上面这个例子，使用变量消去法的计算过程如下：
我个人的理解是变量消去法是通过对Z的求和表达式进行变形，将每个变量对应的Factor进行组合，然后一边计算一边化简表达式的过程，比如上面这个例子中，变量消去法首先合并了
实际上，变量消去对应到概率图中，就是将一个变量和与它有关的因子构成的子图，用一个新的因子来替换，比如上面的例子中，完成第一步
信任传播法
信任传播法(Belief Propagation)是另一种用在Exact Inference上的方法。它依赖一种被称为消息传递(Message Passing)的机制，消息传递机制可以用下面的图来表示：
我们发现，如果3号节点想要知道全局的信息，只需要通过24发送给他的消息，再加上自己就可以得出，即2+3+1=6，可以推测出一共有6个点，对于其他点来说，也是类似的。
概率图模型也上也可以进行更复杂的消息传播，比如下面这个例子：
在概率图模型中，消息传递的内容是变量/Factor的概率分布，如果一个变量X周围有几个因子，那么就可以把这几个Factor传递过来的消息的乘积作为X处的belief，这个过程叫做Sum-Product Belief Propagation
Belief和Message的区别在于，Belief是概率图中的一个点/因子聚合了周围所有传递过来的消息计算出的，而Message的计算过程中不包括目标节点，如下表所示：
变量的Belief可以表示为：
总结
变量消去和信任传播两种Exact Inference方法的总结如下：
| 方法 | 变量消去 | 信任传播 |
|---|---|---|
| 使用场景 | 计算任何概率图模型的配分函数Z，计算任何概率图模型中的一个变量的边缘概率分布 | 计算任何无环概率图模型的配分函数，对于一个无环概率图模型，可以一次性计算所有变量的边缘概率分布 |
| 使用限制 | 计算边缘概率的时候一次只能计算一个，消去的顺序会影响运行所需要的时间 | 只能用在无环图上面，消息传递的顺序会影响运行时间 |
