EM（Expectation-Maximum）算法

简介

EM算法的核心分为两步

  1. E步（Expection-Step）

  2. M步（Maximization-Step）

因为在最大化过程中存在两个参量 r,\theta，其中若知道 r，则知道 \theta；若知道 \theta，则知道 r。且两个量未存在明显的关系，但又互相依存可以采用EM算法

其中主要思想为：

  1. 首先随机初始化参数 r

  2. 然后求的在参数 r下按照极大似然估计求得参数 \theta

  3. 然后根据参数 \theta按照极大似然估计求得参数 r

  4. 循环至收敛

算法示例

如下图所示存在A，B两种硬币，其中抛出正反面的概率未知，其中H表示正面，F表示反面

image-20231218003257513

根据统计可得

image-20231218003323615

可得

P(H|X=A)=\frac{24}{24+6}=0.8\\ P(H|X=B)=\frac{9}{9+11}=0.45


若更改条件，不知道此时抛出是哪一枚硬币，只知道抛出的结果，即

image-20231218003706672

首先初始化，设

P(H|X=A)=0.6\\ P(H|X=B)=0.5


若当抛出的第一枚硬币为A时

此时的出现该情况的概率为 P_1(A)=0.6^5*(1-0.6)^5=0.0007962624

若当抛出的第一枚硬币为B时

此时的出现该情况的概率为 P_1(B)=0.5^5*(1-0.5)^5=0.0009765625

其中

P^1(A)=\frac{P_1(A)}{P_1(A)+P_1(B)}\approx0.45\\ P^1(B)=\frac{P_1(B)}{P_1(A)+P_1(B)}\approx0.55


同理可得

P^2(A)\approx0.80,P^2(B)\approx0.20\\ P^3(A)\approx0.73,P^3(B)\approx0.27\\ P^4(A)\approx0.35,P^4(B)\approx0.65\\ P^5(A)\approx0.65,P^5(B)\approx0.35


计算其数学期望

\begin{aligned} &E_1(H|X=A)=0.45*5=2.2\\ &E_1(T|X=A)=0.45*5=2.2\\ &E_1(H|X=B)=0.55*5=2.75\\ &E_1(T|X=B)=0.55*5=2.75\\ &E_2(H|X=A)=0.80*9=7.2\\ &E_2(T|X=A)=0.45*5=2.2\\ &E_2(H|X=B)=0.20*9=1.8\\ &E_2(T|X=B)=0.20*1=0.2\\ &E_3(H|X=A)=0.73*8=5.8\\ &E_3(T|X=A)=0.73*2=1.46\\ &E_3(H|X=B)=0.27*8=2.16\\ &E_3(T|X=B)=0.27*2=0.54\\ &E_4(H|X=A)=0.35*4=1.4\\ &E_4(T|X=A)=0.35*6=2.1\\ &E_4(H|X=B)=0.65*4=2.6\\ &E_4(T|X=B)=0.65*6=3.9\\ &E_5(H|X=A)=0.65*7=4.55\\ &E_5(T|X=A)=0.65*3=1.95\\ &E_5(H|X=B)=0.35*7=2.45\\ &E_5(T|X=B)=0.35*3=1.05\\ \end{aligned}


并计算其总共的期望

E(H|X=A)=\sum_{i=1}^5E_i(H|X=A)\approx21.3\\ E(H|X=A)=\sum_{i=1}^5E_i(T|X=A)\approx8.6\\ E(H|X=B)=\sum_{i=1}^5E_i(H|X=B)\approx11.7\\ E(H|X=B)=\sum_{i=1}^5E_i(T|X=B)\approx8.4\\


可得

P(H|X=A)=\frac{21.3}{21.3+8.6}=0.71\\ P(H|X=B)=\frac{11.7}{11.7+8.4}=0.58


由此循环直至收敛

EM-Figure1-1

得到最终

P(H|X=A)=0.80\\ P(H|X=B)=0.58