博文
MAP inference
|
MAP是贝叶斯估计中常用的推理算法，是概率图模型的重要组成部分
https://blog.sciencenet.cn/blog-795431-632569.html
上一篇：reading list--语义角色标注
下一篇：MAP inference--[2005 IEEE]MAP estimation via agreement *****
近几年关于MAP的论文有很多，大致可以分为两大类：
1.message passing algorithms
2.dual decomposition
如下图所示：
[2010]Introduction to Dual Decomposition for inference
松弛算法是把原来的组合优化问题看成是约束最优化问题，通过松弛约束条件从而将原问题划分为若干个容易求解的子问题的方法。
本文介绍了一种对偶分解算法:
MAP的目标函数是:
$ （1） MAP(\theta) = \max_x {\sum_{i \in V} \theta_i (x_i) + \sum_{f \in F} \theta_f(x_f)} $
通过引入对偶变量，使用拉格朗日乘数法可以将目标函数转换为：
$ （2） \min_\delta L(\delta) $
$ （3） L(delta) = sum_{i in V} max_{x_i} (theta_i(x_i) + sum_{f:i in f} delta_{fi}(x_i)) +
sum_{f in F} max_{x_f} (theta_f(x_f) - sum_{i in f} delta_{fi}(x_i)) $
#####
下面详细介绍一下如何转换目标函数：
每一个变量都可能会被多个因子使用，用$x^f_i$来表示因子$f$使用了变量$x_i$
用$x^f_f$来表示所有被因子$f$使用的变量,即$x^f_f = \{ x^f_i \}_{i \in f}$
用$x^F$来表示所有变量的拷贝
此时公式（1）可以用下式表示：
$ (5) \max \sum_{i \in V} \theta_i(x_i) + \sum_{f \in F} \theta_f(x^f_f) $
$ s.t. x^f_f = x_i, \forall f, i \in f$
此时公式（5）中仍然包含约束条件。
为了去除约束条件，论文中使用了拉格朗日松弛方法(Lagrangian Relaxation)
引入了拉格朗日乘子: $\delta = \{ \delta_{fi} (x_i) : f \in F, i \in f, x_i \}$
并且定义拉格朗日函数为：
$ (6) L(\delta, x, x^F) = \sum_{i \in V} \theta_i(x_i) + \sum_{f \in F} \theta_f(x^f_f) + \sum_{f \in F} \sum_{i \in f} \sum_{x_j} \delta_{fj} (x_j) (I[x_i = x_j] - I[x^f_i = x_j]) $
此时问题转化为：
$ (7) \max_{x,x^F} L(\delta,x,x^F) s.t. x^f_i = x_i, \forall f, i \in f $
引入函数 $L(\delta)$
其中
$ (8) L(\delta) = \max_{x,x^F} L(\delta,x,x^F) = \sum_{i \in V} \max_{x_i}(\theta_i(x_i) + \sum_{f:i \in f} \delta_{fi}(x_i)) + \sum_{f \in F} \max_{x^f_f}(\theta_f(x^f_f) - \sum_{i \in f} \delta_{fi}(x^f_i))$
很容易看出：
$ (9) MAP(\theta) \leq L(\delta) $
对偶问题就是通过最小化 $L(\delta)$来获得原问题的最小上界！
#####
问题转化后，可以使用次梯度算法(subgradient algorithms)或者共轭下降算法(coordinate descent algorithms)来进行计算！
#####
通过标准的对偶变换可知：LP relaxation就是Lagrangian relaxation！
#############
接下来的工作：
把MAP推理相关的论文复习一下，另外有两三篇ICML 2011和ICML 2012最新的相关论文已经下载下来准备看一下。
https://blog.sciencenet.cn/blog-795431-632569.html
上一篇：reading list--语义角色标注
下一篇：MAP inference--[2005 IEEE]MAP estimation via agreement *****
扫一扫，分享此博文
全部作者的其他最新博文
- • 依存句法分析实验进度
- • 依存句法分析实验进度
- • 依存句法分析实验进度
- • 依存句法实验进度
- • 依存句法实验进度
- • 依存句法分析实验进度