EM算法 | Hexo

EM参考资料就像统计学习方法里讲的一样，从一个三硬币例子讲起。假如有三枚硬币，投掷这三枚硬币正面朝上的概率分别为\(\pi\)，\(p\)，\(q\)。先投第一枚硬币，如果正面朝上，则接下来投第二枚硬币，然后记录该枚硬币的投掷情况，若正面朝上记为1，反面朝上记为0；如果第一枚硬币是反面朝上，则接下来投第三枚硬币，然后同理记录该枚硬币的投掷情况。问题：求最后0、1数据的分布。假设模型背后的参数是\(\theta\)，则就是求\(P(x;\theta)\)，其中\(x\in\{0,1\}\)。 ## 极大似然估计如果只是投一枚硬币，假设正面朝上被一个参数\(q\)指导着。连续投10次，观察到的数据是\([0,1,0,1,0,1,0,1,0,1]\)。然后设此10次投掷为一个事件，虽然该事件已经发生了，但假设我们带着现在观察到的数据，回到该事件尚未发生的时刻，然后找一个\(q\)，使得该事件的结果与我们已经观察到的结果一致。这是一个反推的过程，很好理解，但关键是要用数学表达出这个过程。就这样表达：这个事件就是投10次，这10次投掷的结果分别是\([0,1,0,1,0,1,0,1,0,1]\)。则该事件的概率可以表达成： \[ P(X=0;q) \cdot P(X=1;q)\cdot ...\cdot P(X=1;q) \] 需要我们做的工作是找到一个\(q\)，使得上述公式最大，就可以了。这样的话，可以把上述公式改写成\(q\)的函数，即： \[ l(q)=P(X=0;q) \cdot P(X=1;q)\cdot ...\cdot P(X=1;q) \] 为了最大化上述公式，可以使用导数这个工具，但观察上述公式，连乘的形式不利于导数的运算，所以在效果不变的前提下，再次改写： \[ l(q)=\mathop{\log}{[P(X=0;q) \cdot P(X=1;q)\cdot ...\cdot P(X=1;q)]} \] 也就是： \[ l(q)=\sum_{i=1}^{10}{\mathop{\log}{P(X=x_i;q)}} \] 根据我们日常生活中的经验，一枚硬币，每一次投掷正面朝上的概率是一样的（上帝掷筛子吗），而这里的这个概率正好可以跟前面讲的\(q\)关联起来，所以，顺水推舟地，设 \[ P(X=1)=q\\ P(X=0)=1-q \] 然后： \[ l(q)=\sum_{i=1}^{10}{\mathop{\log}{P(X=x_i)}}=\mathop{\log}{q}\cdot \mathop{\log}{(1-q)} \cdot ... \cdot \mathop{\log}{(1-q)} \] 最大化这个式子，得出\(q=0.5\)。一般化的形式： \[ l(q)=\sum_{i=1}^{N}{\mathop{\log}{[q^{x_i}\cdot (1-q)^{1-x_i}]}} \] 对\(q\)求导： \[ \frac{\partial{l(q)}}{\partial{q}}=\sum_{i}^{N}{\frac{x_i-q}{q(1-q)}} \] 令其等于0，解得\(q=\frac{\sum{x_i}}{N}\)。 ## EM算法回到EM算中当中，设\(Z\)为第一次投币的结果，这是隐变量，不可观测。则部分观测似然函数是： \[ l(\theta)=\sum_{i=1}^{N}{\mathop{\log{P(x_i;\theta)}}} \] 这个式子写不出像上面\(l(q)=\sum_{i=1}^{N}{\mathop{\log}{[q^{x_i}\cdot (1-q)^{1-x_i}]}}\)那样的式子，因为有个\(\pi\)在那里档着。假设能观测到\(Z\)，则完全观测似然函数是： \[ l(\theta)=\sum_{i=1}^{N}{\mathop{\log{\sum_{z}{P(x_i,z;\theta)}}}} \] 按道理来说，到这就可以用极大似然估计那一套去求\(\theta\)的解析解，我估计大前辈们也是这么去做的，但是做的过程中发现有难度，不好做。于是最终就设置了EM这一套，专门用来求解此等问题。 Jensen： \[ E[f(x)]\ge f(E[x]) \] \(\mathop{\log}\)是凹函数，所以\(f(E[x])\ge E[f(x)]\)。就是利用这个方法，把上面似然函数的\(\mathop{\log}\)移到了第二个\(\sum\)后面。为了利用Jensen还得设计一下\(\mathop{\log}\)内部的这个函数，把它写成期望的形式。假设\(Q(z)\)是与\(z\)有关（但不是针对\(z\)）的的一个概率密度： \[ l(\theta)=\sum_{i=1}^{N}{\mathop{\log}{\sum_{z}{Q(z){\frac{P(x_i,z;\theta)}{Q(z)}}}}} \] 然后运行Jensen不等式： \[ l(\theta)\ge \sum_{i=1}^{N}{\sum_{z}{Q(z)\mathop{\log}{\frac{P(x_i,z;\theta)}{Q(z)}}}} \] 取等号时，随机变量是一个常量， \[ \frac{P(x_i,z;\theta)}{Q(z)}=c \] 所以 \[ Q(z)=\frac{P(x_i,z;\theta)}{c} \] 因为之前构造\(Q(z)\)是给它的设定是概率密度，所以有 \[ \sum_{z}{Q(z)}=\sum_{z}{\frac{P(x_i,z;\theta)}{c}}=1 \] 然后，看到这个上面这个形式，它跟softmax非常像，于是自然而然地 \[ \sum_{z}{Q(z)}=\sum_{z}{\frac{P(x_i,z;\theta)}{\sum_{z}{P(x_i,z;\theta)}}}=1 \] 所以 \[ Q(z)=\frac{P(x_i,z;\theta)}{\sum_{z}{P(x_i,z;\theta)}}=\frac{P(x_i,z; \theta)}{P(x_i;\theta)}=P(z|x_i;\theta) \] 至此，\(Q(z)\)就构造出来了。 EM算法： E：根据参数\(\theta\)计算每个样本属于每个\(z\)的概率，这个概率就是\(Q(z)\) M：根据得到的\(Q(z)\)，求出含有\(\theta\)的似然函数的下界并最大化它，得到新的参数\(\theta\)。重复，至收敛。“可以看到，从思想上来说，和最开始没什么两样，只不过直接最大化似然函数不好做，曲线救国而已。”