概率图模型用图表示概率分布，分为有向图（贝叶斯网络）和无向图（马尔可夫网络），涉及表示、推断和学习三个理论部分。

概率规则

$$p(x_1)=\int p(x_1,x_2)dx_2$$ $$p(x_1,x_2)=p(x_1|x_2)p(x_2)$$ $$p(x_1|x_2)=\frac{p(x_2|x_1)p(x_1)}{p(x_2)}$$

有向图-贝叶斯网络

因子分解：

$$p(x_1,\cdots,x_p)=\prod_{i=1}^pp(x_i|x_{parent(i)})$$

局部结构

Markov 毯

与 $x_i$ 相关的部分：

$$p(x_i|x_{parents(i)})p(x_{child(i)}|x_i)$$

无向图-马尔可夫网络

条件独立性

• 全局 Markov：$x_A\perp x_B|x_C$
• 局部 Markov：$x\perp (X-Neighbour(x))|Neighbour(x)$
• 成对 Markov：$x_i\perp x_j|x_{-i-j}$（$i,j$ 不相邻）

因子分解

$$p(x)=\frac{1}{Z}\prod_{i=1}^K\phi(x_{c_i})$$

其中 $\phi(x_{c_i})=\exp(-E(x_{c_i}))$，为 Gibbs 分布。

道德图

有向图转无向图：

1. 将每个节点的父节点两两相连
2. 将有向边替换为无向边

推断方法

信念传播 (BP)

$$m_{j\to i}(i)=\sum_j\phi_j(j)\phi_{ij}(ij)\prod_{k\in Neighbour(j)-i}m_{k\to j}(j)$$

Max-Product 算法

$$m_{j\to i}=\max_j\phi_j\phi_{ij}\prod_{k\in Neighbour(j)-i}m_{k\to j}$$

用于 MAP 推断，是 Viterbi 算法的推广。