0%

白板推导 - 机器学习 - 概率图模型

1. 概率图模型 - 背景介绍

  • 表示(Representation)

    • 有向图(Bayesian Network)
    • 无向图(Markov Network)
  • 推断(Inference)

    • 精确推断
    • 近似推断 [确定性近似(变分推断), 随机近似(MCMC)]
  • 学习(learning)

    • 参数学习(完备数据,隐变量)
    • 结构学习
  • 规则:

    • Sum Rule: $P(x_1) = \int P(x_1, x_2) dx_2$
    • Product Rule: $P(x_1, x_2) = P(x_1)P(x_2|x_1) = P(x_2)P(x_1|x_2)$
    • chain Rule: $P(x_1,…,x_p) = \prod_{i=1}^p P(x_i|x_1,…,x_{p-1})$
    • bayesian Rule: $P(x_2|x_1) = \frac{P(x_2, x_1)}{P(x_1)} = \frac{P(x_1, x_2)}{\int P(x_1, x_2)dx_2} = \frac{P(x_2)P(x_2|x_1)}{\int P(x_2)P(x_1|x_2)dx_2}$
  • 高维随机变量 $P(x_1,…,x_p)$ 的困境: 维度高,计算复杂

    • 简化: 特征相互独立, $P(x_1,…,x_p)=\prod_{i=1}^p P(x_i)$

2. 概率图模型 - 贝叶斯网络 - 条件独立性

  • 原高纬随机变量计算:$P(x_1,…,x_p) = p(x_1)\prod_{i=2}^N p(x_i|x_1,…,x_{i-1})$

  • 条件独立性: $x_A\perp x_C | x_B$

  • 因子分解: $P(x_1, …, x_p) = \prod_{i=1}^pP(x_i|x_{parent}(i))$

3. 概率图模型 - 贝叶斯网络 - 例子 - 具体模型 (从单一到混合, 从有限到无限 [ 空间,时间])

  • 单一:Naive Bayes : $P(x|y) = \prod_{i=1}^p P(x_i|y=1)$

  • 混合:GMM

  • 时间:

    • Markov Chain
    • Gaussian Process
  • 连续:Gaussian Bayesian Network

4. 概率图模型 - 马尔科夫随机场 -Representation- 条件独立性和因子分解

  • 条件独立性体现在三个方面:

    • 全局马尔科夫性: $x_A \perp x_C | x_B$

    • 局部马尔科夫性:$a \perp {全集 -a-a 的邻居} | a 的邻居 $

    • 成对马尔科夫性:$x_i \perp x_j | x_{1…ij}$

  • 因子分解:(Hammesley-Clifford 定理)

    • 团, 最大团(节点的集合,集合中的节点两两有连接)

    • $P(x) = \frac{1}{Z}\prod_{i=1}^K \phi(X_{c_i}), Z 是归一化因子 $

    • $C_i: 最大团, X_{c_i}:最大团随机变量集合,\phi(X_{c_i}):势函数,必须为正 $

    • $Z = \sum_{x}\prod_{i=1}^K \phi(X_{c_i}) = \sum_{x_1}\sum_{x_2}\sum_{x_p}\prod_{i=1}^K \phi(X_{c_i})$

    • $\phi(X_{c_i}) = exp{-E(X_{c_i})} > 0, P(x) 是 Gibbs Distribution$

5. 概率图模型 - 推断 Inference- 总体介绍

  • 求概率: P(x_1, x_2, …, x_p)

    • 边缘概率: $P(x_i) = \sum_{x_1}…\sum_{x_{i-1}}\sum_{x_{i+1}}…\sum_{x_p} P(x)$
    • 条件概率: $P(x_A | x_B), x = x_A 与 x_B 的交集 $
    • MAP Inference: $\hat{z} = \argmax_z P(z|x) 正比于 \argmax P(z, x)$
  • 精确推断

    • variable elimination(VE)
    • Belief Propagation(BP) -> Sum-Product Algorithm(针对树结构)
    • Junction Tree Algorithm (普通图结构)
  • 近似推断

    • Loop Belief Propagation (有环图)
    • Mente Carlo Inference: Importance Sampling, MCMC
    • Variational Inference

6. 概率图模型 - 推断 Inference-Variable Elimination

在一个 4 个节点的链式有向图中(a -> b -> c -> d), 假设 a, b, c, d 都是离散的二值,即 $a, b, c, d \in {0, 1}$
则:
$$P(d) = \sum_{a,b,c} P(a, b, c, d)$$
$$= \sum_{a,b,c} P(a) P(b|a) P(c|b) P(d|c)$$
$$ = P(a=0) P(b=0|a=0) P(c=0|b=0) P(d=0|c=0)+…+P(a=1) P(b=1|a=1) P(c=1|b=1) P(d=1|c=1)$$
$$= \sum_{b,c} P(c|b) P(d|c) \sum_a P(a) P(b|a)$$
$$= \sum_c P(d|c) \sum_b P(c|b) \phi_a(b) = \phi_c(d)$$

7. 概率图模型 - 推断 Inference-Belief Propagation

BP 算法 = VE + Caching

Belief Propagation: 不要直接求边缘概率 ($P(a), P(b), P(c), P(d)$), 只需要求 边上的概率 $m_{i\to j}$

结论:
$$m_{j\to i}(x_i) = \sum_{x_j} \phi_{ij}\phi_j \prod_{k\in NB(j) - i} m_{k\to j}(x_j)$$
$$P(x_i) = \phi_i \prod_{k \in NB(i)} m_{k\to i} (x_i)$$

8. 概率图模型 - 概念补充 - 因子图(Factor Graph)

  • 有向图: $P(x) = \prod_x P(x_i|x_{pa(i)})$

  • 无向图: $P(x) = \frac{1}{Z}\prod_{i=1}^K \phi_{i} (X_{c_i}), c_i 为最大团集合 $

  • 道德图 (Moral Graph): 有向图(树)$\to$ 无向图(引入环, Tree-like Graph)

坚持原创技术分享,您的支持将鼓励我继续创作!