图模型的推断

1.链推断

N个结点表示N个离散变量，每个变量有K个状态，这种情况下，势函数 $\varphi_{n-1,n}(x_{n-1},x_n)$ 是由一个k*k的表组成，因此联合概率分布有 $(N-1)K^2$ 个参数。

让我们来考虑寻找边缘概率分布 $p(x_n)$ 的这一推断问题，其中 $x_n$ 是链上的一个具体的点，根据定义，这个边缘分布可以用好得联合概率分布在除 $x_n$ 以外的所有变量上进行求和得到
$p(x_n)=\sum_{x_1}\dots \sum_{x_{n-1}}\sum_{x_{n+1}}\dots \sum_{x_N}p(x) \space (3)$

通过利用图模型的条件独立性质，我们将联合概率分布的分解表达式(1)代入(3)式中，重新整理加和乘积的顺序，使得需要求解的边缘概率分布可以更加高效地计算。例如，考虑到堆 $x_N$ 的求和，势函数 $\varphi_{N-1,N}(x_{N-1},x_N)$ 是唯一与 $x_N$ 有关的势函数，因此我们可以进行下面的求和
$\sum_{x_N}\varphi_{N-1,N}(x_{N-1},x_N)$
得到一个关于 $x_{N-1}$ 的函数，我们可以使用 $x_{N-1}$ 上的求和，这只涉及到这个新的函数以及势函数 $\varphi_{N-2,N-1}(x_{N-1},x_N)$ 是唯一出现 $x_{N-1}$ 的地方。类似地， $x_1$ 上的求和只涉及到势函数 $\varphi_{1,2}(x_1,x_2)$ ，因此可以单独进行，得到 $x_2$ ，以此类推。因为每个求和都移除了概率分布中的一个变量，因此可以被看成从图中移除了一个结点。
$p(x_n)=\underbrace{\frac{1}{Z}[\sum_{n-1}\varphi_{N-1,N}(x_{N-1},x_N) \dots [\sum_{x_2}\varphi_{2,3}(x_2,x_3)[\sum_{x_1}\varphi_{1,2}(x_1,x_2)]]\dots]}_{\text{$\mu_{\alpha(x_n)}$}}$

$\underbrace{[\sum_{x_{n+1}}\varphi_{n,n+1}(x_n,x_{n+1})\dots [\sum_{x_N}(\varphi_{N-1,N}(x_{N-1},x_N)]\dots ]}_{\text{$\mu_{\beta(x_n)}$}}$

让我们来计算边缘概率分布所需的代价，我们必须进行N-1次求和，每次求和的对象是K个状态，并且每次求和涉及到的两个变量组成的函数，因此计算代价是 $O(k^2)$ ,计算边缘分布 $p(x_n)的总代价还是O(Nk^2)$

马尔科夫链.png

我们现在使用局部信息传递的思想，给出这种计算的一个强大的直观意义
$p(x_n)=\frac{1}{Z}\mu_{\alpha}(x_n)\mu_{\beta}(x_n)$
我们把 $\mu_\alpha(x_n)$ 看成是从结点 $x_{n-1}$ 到结点 $x_n$ 沿着链向前传递的信息类似地，将 $\mu_\beta(x_n)$ 看成从结点 $x_{n+1}$ 到结点 $x_n$ 的沿着链向后传递。注意，每条信息由K个值的构成，每个值对应于 $x_n$ 的一种选择，因此两条信息的乘积可以看做两条信息的元素之间的点积，得到另外K个值的集合。

信息 $\mu_\alpha(x_n)$ 可以递归地计算，因为
$\mu_\alpha(x_n)=\sum_{x_{n-1}}\varphi_{n-1,n}(x_{n-1},x_n)[\sum_{x_{n-1}}\dots]=\sum_{x_{n-1}}\varphi_{n-1,n}(x_{n-1},x_n)\mu_\alpha(x_{n-1})$
因此我们先计算
$\mu_\alpha(x_2)=\sum_{x_1}\varphi(1,2)(x_1,x_2)$

2.树

在无向图中，树被定义为满足下面性质的图：任意一对结点之间有且仅有一条路径。于是这样的图没有环。在有向图的情形中，树的定义为：有一个没有父结点的节点，被称为根结点，其他所有结点都有一个父结点。如果我们将有向树转化成无向图，“伦理“步骤不会增加任何链接，因为所有的节点至多有一个父结点，从而对应的道德图是一个无向图。

如果有向图中存在具有多个父结点的节点，但是任意两个节点之间仍然只有一条路径（忽略箭头方向），那么这个图成为多树。

树.png

3.因子式

有向树和无向树都使得若干变量的一个全局函数能够表示为这些变量的子集上的因子的乘积。因子式显式地表示出了这个分解，方法是：在表示变量的节点的基础上，引入额外的结点表示因子本身。

因子式.png

让我们将一组变量上的联合概率分布写成因子式的乘积形式
$p(x)=\prod_s f_s(x_s)$
其中 $x_s$ 表示变量的一个子集。每个因子 $f_s$ 对应的变量集合 $x_s$ 的函数。

在因子图中，概率分布中的每个变量都有一个结点，还存在其他结点（用小正方形表示），表示联合概率分布中的每个因子 $f_s(x_s)$ ，最后，在每个因子结点和因子所依赖的变量结点之间，存在无向链接。例如，图8.40表示为因子形式的概率分布
$p(x)=f_a(x_1,x_2)f_b(x_1,x_2)f_c(x_2,x_3)f_d(x_3)$
注意， $f_a(x_1,x_2),f_b(x_1,x_2)$ 定义在同一个变量集合上。在一个无向图中，两个这样的因子的乘积可以简单地合并在一个团块势函数中。因子式，显示地写出这些因子，可以表达出关于分解本身更加细节的信息。

有向图、无向图、因子式.png

如果我们将一个有向树或者无向树转化成因子图，那么生成的因子图也是树（即因子图每天环，且任意两个结点之间有且只由一条路径）。在有多树的情形中，由于“伦理”步骤的存在，转化为无向图会引入环，而转化后的因子图仍然是树。事实上，有向图中由于链接父结点和子结点产生的局部环可以转化到因子图时被移除，只需定丢出合适的因子函数即可。

4.加和-乘积算法

我们会使用因子图框架推导以类强大的、高效的精确的推断算法，这些算法适用于树结果的图，这里我们把精力集中于计算结点或者子集上的局部边缘概率分布。

此外，我们假设模型中所有的变量都是离散的，因此求边缘分布对应于求和的过程。然而，这个框架同样适用于线性高斯分布模型，这种情形下求边缘分布涉及到求积分。

我们假设原始的图是一个无向树或者有向树或者多树，从而对应的因子图有一个树结构。首先，我们将原始的图转化为因子图，使得我们可以使用同样的框架处理有向图和无向模型。我们的目标是利用图的结果完成两件事：1.得到一个高效的精确推断算法来寻找边缘概率；2.在需要求解多个边缘概率的情形，计算可以高效地共享。

因子图片段.png

边缘概率分布通过对所有的x之外的变量上的联合概率分布进行求和的方式得到，即
$p(x)=\sum_{\mathbf{x} /\ x}p(x) \space(4.1)$
其中 $\mathbf{x} /\ x$ 表示 $\mathbf{x}$ 的集合中去掉x。算法的思想是使用因子式 $p(x)=\prod_s f_s(X_s)$ 替换p(x)，然后交换加和与乘积的顺序，得到一个高效的算法。树结构可以使得我们将联合概率分布中的因子划分为若干组，每组对应变量结点x的相邻点组成的因子结点集合。我们看到联合概率分布可以写成乘积形式。
$p(x)=\prod_{s \in ne(x)} F_s(x,X_s)\space (4.2)$

其中ne(x)表示与x响铃的因子结点的集合， $X_s$ 表示子树中通过因子结点 $f_s$ 与变量结点x相连的所有变量的几个， $F_s(x,X_s)$ 表示分组中与因子相关联的所有因子的乘积。

将公式4.2代入到4.1，交换加和与乘积的顺序

$\begin{equation} \label{eq1} \begin{split} p(x) & = \prod_{s \in ne(x)}[\sum_{X_s} F_s(x,X_s)] \\ & = \prod_{s \in ne(x)} \mu_{f_s \to s}(x) \end{split} \end{equation} \space (4.3)$

其中 $\mu_{f_s \to s}(x)$ 定义为
$\mu_{f_s \to s}(x) \equiv \sum_{X_s}F_s(x,X_s) \space (4.4)$

这可以用看作因子结点 $f_s$ 到变量结点的信息，需要求解边缘分概率分布p(x)等于所有到达结点x的输入信息的乘积。

每个因子 $F_s(x,X_s)$ 是由一个因子图（因子子图），因此因子本身可以被分解。
$F_s(x,X_s)=f_s(x,x_1,\dots,x_M)G_1(x_1,X_{s1})\dots G_M(x_M,X_M) \space (4.5)$
x之外与因子 $f_s$ 相关的变量记作 $x_1,\dots,x_M$ ，变量集合 $\{ x_,x_2,\dots,x_M \}$ 表示因子结点 $f_s$ 依赖的变量的集合。

将公式4.5代入5.44中，我们有
$\begin{equation} \label{eq1} \begin{split} \mu_{f_s \to x}(x) = \sum_{x_1}\dots \sum_{x_M} f_s(x,x_1,\dots,x_M) G_1(x_1,X_{s_1})[\prod_{m \in ne (f_s) /\ x }\sum_{X_{sm}} G_m(x_m,X_{sm})] \\ = \sum_{x_1}\dots \sum_{x_M} f_s(x,x_1,\dots,x_M) \prod_{m \in ne (f _s) /\ x } \mu_{x_m \to f_s}(x_m) \end{split} \end{equation} \space (8.6)$

其中 $ne(f_s)$ 表示因子结点 $f_s$ 的相邻变量结点的集合， $ne(f_s) /\ x$ 表示同样的集合，但是移除了解点x。这里，我们定义了下面的变量解点到因子结点的信息
$\mu_{x_m \to f_s}(x_m) \equiv \sum_{x_m} g_m(x_m,X_{sm}) \space (8.7)$

于是，我们引入了两类不同的信息。一类信息是从因子结点到变量结点的信息，记作 $\mu_{f \to x}(x)$ ，另一类信息是从变量结点到因子结点的信息，记作 $\mu_{x \to f}(x)$ 。在任何情况下，我们看到沿着一条链接传递的信息总是一个函数，这个函数是与那个链接的变量结点相关的变量的函数。

公式8.6表明，一个变量结点通过一个链接发送到一个因子结点的信息可以按照如下的方式计算：计算沿着所有进入因子结点的其他链接的输入信息的乘积，乘以与那个结点关联的因子，然后对所有输入信息关联的变量进行求和。值得注意的是，一旦一个因子结点从所有其他结点的相邻变量结点的输入信息，那么这个因子结点就可以向变量结点发送信息。

最后我们推导变量结点到因子结点的信息的表达式，再次使用图分解（子图分解）。

变量到因子结点.png

与节点 $x_m$ 关联的项 $G_m(x_m,X_m)$ 由项 $F_l(x_m,X_{lm})$ 的乘积组成，每一个这样的项都与连接到结点 $x_m$ 的一个因子结点 $f_l$ 相关联（不包括结点 $f_s$ ），即
$G_m(x_m,X_m)=\prod_{l \in ne(x_m) /\ f_s} F_l(x_m,X_{lm}) \space (4.8)$

其中求和的对象是结点 $x_m$ 所有相邻结点，排除结点 $f_s$ 。注意，每个因子 $F_l(x_m,X_{lm})$ 表示原始图的一个子图。

将公式4.8代入到4.7，我们可以得到
$\mu_{x_m \to f_s(x_m)} = \prod_{l \in ne(x_m) /\ f_s}[\sum_{X_m} F_l(x_m,X_M)]=\sum_{l \in (x_m) /\ f_s} \mu_{f_l \to x_m}(x_m) \space (4.9)$

为了计算从一个个变量解点到相邻因子结点沿着链接传递的信息，我们只需简单地在其他结点上分对输入信息取乘积。注意，任何只有两个相邻结点的变量结点无需参与计算，值需将信息不变地传递过去即可。此外，我们注意到，一旦一个变量结点接受到了来自所有其他相邻因子结点的输入信息，那么这个变量结点就可以给因子结点发送信息。

我们的目标是计算变量结点x的边缘概率分布，这个边缘概率分布等于沿着所有到达这网结点的链接的输入信息的乘积。这些信息中的每一条信息都可以使用其他结点递归地计算。为了开始这个递归计算的过程，我们可以将结点x看成树的根结点，然后从叶结点开始计算。根据公式(4.9)的定义，我们看到如果一个叶结点是一个变量结点，那么它沿着与它唯一相连的链接发送信息为

$\mu_{x \to f}(x) = 1$
如果叶结点是一个因子结点，那么我们根据干事4.6可以看到，发送的信息形式
$\mu_{f \to x}(x) = f(x)$

图模型的推断