EM算法

@[EM, Jensen不等式]

EM算法EM算法Jensen不等式EM算法迭代思想以及收敛性EM伪代码

EM算法

例子：假设有三个硬币，分别为ABC,他们正面的概率分别为c,p,q;先掷A,正面选择掷B,反面选择掷C，照此投出一个观测序列： 1，1，0，1，0，0，1，0，1，1 问：如何估计三个硬币的概率c,p,q? 分析：此题目中含有隐藏状态，即每次投掷结果由哪个硬币掷出，有可能他的隐藏状态为：B,C,B,B,C,B,C,C,C,B 因为还有隐藏状态，不能直接使用极大似然估计来求,但是可以借助极大似然的思想来求解。 模型表述: 我们默认投出每一个观测状态的概率是： P(y|Θ)−−−−每一个观测状态出现的概率，y=0，1,Θ是(c,p,q)模型参数 $$P(y|/Theta) ----每一个观测状态出现的概率，y=0，1,/Theta 是(c,p,q)模型参数$$ 极大似然的思想： 我们观测序列的概率： P=∏ip(yi|Θ) $$P = /<a href="http://pr.VeVb.com/">PR</a>od_{i} P(y_{i}|/Theta)$$ 根据极大释然左右取对数： max=∑ilog(P(yi|Θ)) $$max = /sum_{i} log(P(y_{i}|/Theta))$$ max=∑ilog(∑ziP(yi,zi|Θ)) $$max = /sum_{i}log(/sum_{z_{i}}P(y_{i},z_{i}|/Theta))$$ max=∑ilog(∑ziQ(zi)×P(yi,zi|Θ)Q(zi)) $$max =/sum_{i}log(/sum_{z_{i}}Q(z_{i}) /times /frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})} )$$ 分子分母同时乘以Q(z)，该表示隐藏状态zi$z_{i}$的概率 Q(zi)×P(yi,zi|Θ)Q(zi)$Q(z_{i}) /times /frac{P(y_{i},z_{i}|/Theta)}{ Q(z_{i})}$表示着某一个期望；

Jensen不等式

对于凸函数：特有的性质，对于凸函数，二次凸优化，海森矩阵，我会新起一篇去解释。凸就是二次导数>0. 记住两个公式： 1.E[f(X)]>=f(E[X])$E[f(X)]>=f(E[X])$ 2.f(x1)+f(x2)2>=f(x1+x22)$/frac{f(x_{1})+f(x_{2})}{2} >=f(/frac{x_{1}+x_{2}}{2})$ 3.logx函数是一个凹函数，当f为严格凹函数，则-f为严格凸函数

log(∑ziQ(zi)×P(yi,zi|Θ)Q(zi)）$log(/sum_{z_{i}}Q(z_{i}) /times /frac{P(y_{i},z_{i}|/Theta)}{{Q(z_{i})}}）$相当于是f(E(x))$f(E(x))$所以：

log(∑ziQ(zi)×P(yi,zi|Θ)Q(zi))<=∑ziQ(zi)×log(P(yi,zi|Θ)Q(zi)) $$log(/sum_{z_{i}}Q(z_{i}) /times /frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})} ) <= /sum_{z_{i}}Q(z_{i}) /times log(/frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})})$$ 带入： max=∑ilog(∑ziQ(zi)×P(yi,zi|Θ)Q(zi))>=∑i∑ziQ(zi)×log(P(yi,zi|Θ)Q(zi))) $$max =/sum_{i}log(/sum_{z_{i}}Q(z_{i}) /times /frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})} ) >= /sum_{i}/sum_{z_{i}}Q(z_{i})/times log(/frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})}))$$

此事很屌，我们求目标函数的max，却得到一个>=的一个式子，我们需要不断最大化右边的式子来不断优化，这就是所谓的EM迭代，E是指求出期望，M是指不断迭代

EM算法迭代思想以及收敛性：

EM算法的迭代还是很考验人的： maxP=∏iP(yi|Θ)>=∑i∑ziQ(zi)×log(P(yi,zi|Θ)Q(zi)))$max P = /prod_{i} P(y_{i}|/Theta)>= /sum_{i}/sum_{z_{i}}Q(z_{i})/times log(/frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})}))$ 因为yi$y_{i}$是观测变量，实际上式子可以抽象成L(θ)>=J(z,Q)

他迭代的思想就是通过初始化θ,然后固定θ，使得Q(z)在同一个θ上表现的尽可能贴近L(θ),(从绿色到蓝色)，这就是E步，然后M步是更新θ；

怎么证明算法收敛？这里的学问还是很大的！ L(θ)>=J(z,Q)取=号意味着取得最大了。

如何取=？ 根据Jensen不等式，当x为常数时，取=； 故： max=∑ilog(∑ziQ(zi)×P(yi,zi|Θ)Q(zi))>=∑i∑ziQ(zi)×log(P(yi,zi|Θ)Q(zi))) $$max =/sum_{i}log(/sum_{z_{i}}Q(z_{i}) /times /frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})} ) >= /sum_{i}/sum_{z_{i}}Q(z_{i})/times log(/frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})}))$$ 的变量为P(yi,zi|Θ)Q(zi)=C时； $$/frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})} =C时；$$ ∑ziQ(zi)=1概率密度函数 $$/sum_{z_{i}}Q(z_{i})=1 概率密度函数$$ 分子分母统一比例，分子加分子，必上分母加分母还是改比例； ∑ziP(yi,zi|Θ)∑ziQ(zi)=C=>∑ziP(yi,zi|Θ)=C $$/frac{/sum_{z_{i}}P(y_{i},z_{i}|/Theta) }{/sum_{z_{i}}Q(z_{i})} =C =>/sum_{z_{i}}P(y_{i},z_{i}|/Theta) = C$$ 带入故： Q(zi)=P(yi,zi|Θ)∑ziP(yi,zi|Θ)=P(yi,zi|Θ)P(yi|Θ)=P(zi|yi,Θ) $$Q(z_{i}) = /frac{P(y_{i},z_{i}|/Theta)}{/sum_{z_{i}}P(y_{i},z_{i}|/Theta) } =/frac{P(y_{i},z_{i}|/Theta)}{P(y_{i}|/Theta) } =P(z_{i}|y_{i},/Theta)$$

EM伪代码：

E步骤：根据参数初始值或上一次迭代的模型参数来计算出隐性变量的后验概率，其实就是隐性变量的期望。作为隐藏变量的现估计值： Q(zi):=P(zi|yi,Θ) $$Q(z_{i}):=P(z_{i}|y_{i},/Theta)$$

M步骤：将似然函数最大化以获得新的参数值 Θ:=argmax∑i∑ziQ(zi）×log(P(yi,zi|Θ)Q(zi)) $$/Theta :=argmax/sum_{i}/sum_{z_{i}}Q(z_{i}）/times log(/frac{P(y_{i},z_{i}|/Theta)}{Q(z_{i})})$$

搞定！