7.PGMIntro

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

概率规则

$p(x_1)=\int p(x_1,x_2)d{x}_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}^{p}p(x_i|x_{parent(i)})$

局部结构

结构	条件独立性
$A\to B\to C$	$C\perp A\Vert B$
$B\to A,B\to C$	$A\perp C\Vert B$
$A\to B,C\to B$	$A\perp C$，但给定 $B$ 不独立

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\varphi (x_{c_i})$

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

道德图

有向图转无向图：

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

推断方法

类型	方法
精确推断	VE、BP、Junction Tree
近似推断	Loop BP、MCMC、变分推断

信念传播 (BP)

$m_{j\to i}(i)={\sum }_j{\varphi }_j(j){\varphi }_{ij}(ij){\prod }_{k\in Neighbour(j)-i}{m}_{k\to j}(j)$

Max-Product 算法

$m_{j\to i}={\max }_j{\varphi }_j{\varphi }_{ij}{\prod }_{k\in Neighbour(j)-i}{m}_{k\to j}$

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