# 概率图模型--最大后验概率状态推理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， 求最大后验概率；
根据上面的例子, 可以有序地对变量进行消元
$$ \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
还是刚才的例子:
求解流程如图:
- 以
1：A,B到2：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,C到3：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
