概率图模型--最大后验概率状态推理MAP

作者: pdnbplus | 发布时间: 2024/06/25 | 阅读量: 239

# 概率图模型--最大后验概率状态推理MAP -- 潘登同学的Machine Learning笔记 @

简单回顾概率图模型的推理

三大任务

  • 求解边缘概率 $$ p(\bf{x_a}) = \sum_{\bf{x \diagdown x_{\alpha}}} $$

  • 求最大后验概率状态 $$ X^{*} = \argmax_{\bf{x}\in \chi} p(\bf{x}) $$

  • 求归一化因子 $$ Z = \sum_{\bf{x}} \prod_{c} \phi_c(\bf{x}_c) $$

最大后验概率状态推理MAP

最大后验概率状态推理的最主要目的就是找到正确答案;

考虑这样一个例子, 一个smoker, 如果今天突然间死了, 我们想推导他的死因, 想知道到底是身体的哪个部分衰竭导致的死亡, 简单的常识告诉我们, 他有可能是心脏病、肺癌、肾衰竭、脑休克、破伤风感染...

然后我们构建了一个宏大的概率图网络来研究他的死法(~~会不会太没人性~~), 然后现在我们要推导他的最可能死法, 这就是最大后验状态推理的目的;

上面的推理也很简单, 就把我们知道的先验知识带进去, 再计算在什么状态下会先验知识发生最可能发生;(也就是说固定住smoke和death, 最大概率会发生的事情(如:肺癌))

  • 由状态概率导出最大后验概率

$$ P(x)\propto \prod_k \phi_k(D_k)\ \Rightarrow x^{*} = \argmax \prod_k \phi_k(D_k)\ $$

  • 上面取对数, 变连加为连乘

$$ x^{*} = \argmax \sum_k \theta_k(D_k) $$

  • 上面取最小, 变最大为最小

$$ x^{*} = \argmin \sum_k \theta'_k(D_k) $$

注意求最大的和求最小的都可以用, 在这一篇文章中, 主要用求最大来算

变量消元法求与团树传播算法求MAP

举个栗子(以三个变量为例)

  • 分开列报势函数表
A B $\theta(A,B)$
$a^0$ $b^0$ 3
$a^0$ $b^1$ 0
$a^1$ $b^0$ -1
$a^1$ $b^1$ 1
B C $\theta(B,C)$
$b^0$ $c^0$ 4
$b^0$ $c^1$ 1.5
$b^1$ $c^0$ 0.2
$b^1$ $c^1$ 2
  • 合并势函数表
A B C $\theta(A,B)$
$a^0$ $b^0$ $c^0$ 3+4=7
$a^0$ $b^0$ $c^1$ 3+1.5=4.5
$a^0$ $b^1$ $c^0$ 0+0.2=0.2
$a^0$ $b^1$ $c^1$ 0+2=2
$a^1$ $b^0$ $c^0$ -1+4=3
$a^1$ $b^0$ $c^1$ -1+1.5=0.5
$a^1$ $b^1$ $c^0$ 1+0.2=1.2
$a^1$ $b^1$ $c^1$ 1+2=3

很容易就看出, 最大后验概率状态就是${a^0,b^0,c^0}$

但是一旦变量多了, 这种概率分布表的形式就不好使了, 我们需要一个系统性的执行算法--还是变量消元团树传播;

MRF应用变量消元算法求MAP

对这样一个MRF, 求最大后验概率; 链式MRF的图

根据上面的例子, 可以有序地对变量进行消元

$$ \begin{aligned} &\max_E\max_D\max_C\max_B\max_A(\theta_1(A,B)+\theta_2(B,C)+\theta_3(C,D)+\theta_4(D,E))\ &= \max_E\max_D\max_C\max_B(\theta_2(B,C)+\theta_3(C,D)+\theta_4(D,E)+\max_A\theta_1(A,B)) \ &= \max_E\max_D\max_C\max_B(\theta_2(B,C)+\theta_3(C,D)+\theta_4(D,E)+\lambda_1(B)) \ &= \max_E\max_D\max_C(\theta_3(C,D)+\theta_4(D,E)+\max_B(\theta_2(B,C)+\lambda_1(B))) \ &= \max_E\max_D\max_C(\theta_3(C,D)+\theta_4(D,E)+\lambda_2(C)) \ &= \max_E\max_D(\theta_4(D,E)+\max_C(\theta_3(C,D)+\lambda_2(C)) \ &= \max_E\max_D(\theta_4(D,E)+\lambda_3(D)) \ &= \max_E\lambda_4(E) \ \end{aligned} $$

而$\max_E\lambda_4(E)$是比较容易求解出来的, 把最大的E固定再往回求D, 再固定... 再往回推...:

$$ \begin{aligned} &\max_E\lambda_4(E)\Rightarrow 确定了\tilde{E}\ &\Rightarrow \max_D(\theta_4(D,\tilde{E})+\lambda_3(D))\Rightarrow 确定了\tilde{D}\ &\Rightarrow \max_C(\theta_3(C,\tilde{D})+\theta_4(\tilde{D},\tilde{E})+\lambda_2(C))\Rightarrow 确定了\tilde{C}\ &\Rightarrow \max_B(\theta_2(B,\tilde{C})+\theta_3(\tilde{C},\tilde{D})+\theta_4(\tilde{D},\tilde{E})+\lambda_1(B))\Rightarrow 确定了\tilde{B}\ &\Rightarrow \max_A(\theta_1(A,\tilde{B})+\theta_2(\tilde{B},\tilde{C})+\theta_3(\tilde{C},\tilde{D})+\theta_4(\tilde{C},\tilde{E}))\Rightarrow 确定了\tilde{A}\ \end{aligned} $$

所以最终结果就是${\tilde{A},\tilde{B},\tilde{C},\tilde{D},\tilde{E}}$

MRF应用团树传播算法求MAP

还是刚才的例子:

链式MRF的图

求解流程如图:

在这里插入图片描述

  • 1:A,B2:B,C的消息传播为例

关键是理解: $$\lambda_{1\to2}(B)=\max_A\theta_1(A,B)$$

先看两个节点的势函数

A B $\theta(A,B)$
$a^0$ $b^0$ 3
$a^0$ $b^1$ 0
$a^1$ $b^0$ -1
$a^1$ $b^1$ 1
B C $\theta(B,C)$
$b^0$ $c^0$ 4
$b^0$ $c^1$ 1.5
$b^1$ $c^0$ 0.2
$b^1$ $c^1$ 2

想顺利的把消息从1:A,B传到2:B,C, 那么显然B的所有取值都得保留下来,则有

$$\lambda_{1\to2}(B)=\max_A\theta_1(A,B)\ = \begin{cases} 3, & b^0 \ 1, & b^1 \ \end{cases}$$

  • 再看2:B,C3:C,D的消息传播

$$\lambda_{2\to3}(C)=\max_B(\theta_2(B,C)+\lambda_{1\to2})$$

关键是理解: $$\theta_2(B,C)+\lambda_{1\to2}$$

再把势函数拿过来

B C $\theta(B,C)$
$b^0$ $c^0$ 4
$b^0$ $c^1$ 1.5
$b^1$ $c^0$ 0.2
$b^1$ $c^1$ 2

那么,

B C $\theta(B,C)+\lambda_{1\to2}$
$b^0$ $c^0$ 7
$b^0$ $c^1$ 4.5
$b^1$ $c^0$ 1.2
$b^1$ $c^1$ 3

而这个$\theta_2(B,C)+\lambda_{1\to2}$就是信念值

按照这样的方式, 继续往下传播, 直到所有点都有信念值;

我们要求的状态就是所有节点信念值的最大的那个状态的并集

  • 1:A,B传到2:B,C再传回来为例

1:A,B传到2:B,C后, 2:B,C处的信念值:

B C $\theta(B,C)+\lambda_{1\to2}$
$b^0$ $c^0$ 7
$b^0$ $c^1$ 4.5
$b^1$ $c^0$ 1.2
$b^1$ $c^1$ 3

2:B,C传回1:A,B处的信念值:

A B $\theta(B,C)+\lambda_{2\to1}$
$a^0$ $b^0$ 7
$a^0$ $b^1$ 2
$a^1$ $b^0$ 3
$a^1$ $b^1$ 3

两个都选最大的, 那不就是${a^0,b^0} \cup {b^0,c^0} = {a^0,b^0,c^0}$

总结

  • 一句话概括MAP, 就是找最可能的那个答案;

  • 一句话概括变量消元法求MAP, 变量消元消剩下一个变量, 从最后一个开始往前推各个变量的状态;

  • 一句话概括团树传播求MAP, 每个节点往旁边节点互传消息,计算信念值,对最大信念值的状态求并集;

(其实求最大后验概率是非常简单的, 不一定非得用什么变量消元, 遗传算法、蒙特卡洛其实更好用)

最大后验概率状态推理MAP就是这样了, 继续下一章吧!pd的Machine Learning