最近学习了机器学习中的马尔科夫链蒙特卡洛(Markov Chain Monte Carlo, 简称MCMC) 相关的知识。

主要内容包括：

【1】蒙特卡洛原则，及其应用于采样的必要性（已经发布在头条）

【2】用于求解最大似然、近似推断、期望问题的经典采样算法：Metropolis-Hastings，Rejection，Importan，Metropolis和Gibbs算法。（本文属于此部分）

【3】马尔可夫链各个性质在蒙特卡洛采样问题中的应用，包括同质性，平移不变性

—————【2】—————

在上一篇【2.1】中已经讨论了拒绝采样和重要性采样两种应用了蒙特卡洛原则的采样算法，接下来讨论采样算法和EM优化算法的关系。

【EM期望最大算法Expectation Maximization】

EM算法是一种同时学习模型参数和隐变量的优化算法，执行时分为E步骤和M步骤，不断迭代。EM算法不是采样算法而是优化算法。EM算法包括两个步骤，交替迭代计算：1、计算隐藏变量的条件概率分布的期望，利用隐藏变量的现有估计值，计算其最大似然估计值 2、最大化上一步求得的最大似然估计值，得到此时的参数值，这个参数值用于下一轮期望的计算

最大似然估计值，是已经知道结果，反推使该结果出现的可能性最大的条件。通常 :

θ_= argmaxθ ln(P(x|θ)) 求得θ_为极大似然估计量。

在EM算法中，我们已知观测到的随机变量数据Y，隐随机变量数据Z未知，Y和Z一起被成为完全数据，只有Y则是不完全数据。

假设有m个样本x1-xm，每个样本有隐含类别z，p(x,z)有极大似然估计 L(θ)=sum_m(ln(p(x|θ)))=sum_m(ln(sum_z(p(x,z|θ))))。

将目前手上观测样本的极大似然表示为上式后，问题就转化成怎么求使得该值最大的z和θ。直接求偏导不可行是因为ln项内部还有和式，难以计算。

已知隐藏变量z必然存在一个概率分布函数Q(z)，构造上式似然可证明严格大于等于下界 sum_i(sum_zi(Q(zi)*log(p(x,z|θ)/Q(zi)))),使用了金森不等式（金森不等式：如果函数f是凸函数，x是随机变量，那么E(f(x))>=f(E(x))）。而这个下界函数，log项内部没有和式，可以方便地通过拉格朗日乘子法求出最大值，且这个 sum_zi(Q(zi)*log(p(x,z|θ)/Q(zi))) 也就是 【p(xi,zi|θ)/Q(zi)】的期望，也就是 P(x,z|θ) 对 Q(z) 的条件概率的期望。即：

目标是最大化，转化为使得下界式子(3)最大化

上式也就是L(θ)>= J(z,Q),不断提高下界来逼近L(θ)的最大值。这也就是EM算法的核心思路。

因此，E步-期望：固定参数值θ，调整Q(z)使得下界J(期望)上升至与似然函数L在这个θ处相等，此使Qi(Zi)=p(Zi|Xi,θ)，即每个样本属于某个隐状态的概率。

M步-最大化：固定Q(z)，调整θ直到J取得最大值，以此时的θ为新的θ。

这就是EM算法的完整推导步骤和迭代方式。

因此，E步中Qi(Zi)=p(Zi|Xi,θ)，即每个样本属于某个隐状态的概率的计算是EM算法，能否使用的关键。如果此后验概率不能用分析式直接计算，可以使用采样算法来帮助计算。