Created by potrace 1.13, written by Peter Selinger 2001-2015

EM算法实例

本文列举了几个经典的EM算法实例,对于EM算法不了解的同学可以参考这篇文章-EM算法

三硬币模型

假设有三枚不均匀硬币A、B、C 。进行如下掷硬币试验： 先掷A，如果A是正面则再掷B，如果A是反面则再掷C。对于B或C的结果，如果是正面则记为1，如果是反面则记为0。进行 N 次独立重复实验，实验结果为 y=(y_1,...,y_N) . 求这些硬币正面出现的概率 \pi 、 p 、 q .

在这个问题中，硬币A的结果是不可观测数据 z=(z_1,...,z_N) , 且 z 只有两种可能取值1和0。，估计模型参数 \theta=(\pi,p,q) 。

对于第 j 次试验，

\begin{aligned} P(y_j|\theta)&= \sum_zP(y_j,z|\theta)\\&=\sum_zP(z|\theta)P(y_j|z,\theta)\\&=P(z=1|\theta)P(y_j|z=1,\theta)+P(z=0|\theta)P(y_j|z=0,\theta) \\&=\begin{cases} \pi p+(1-\pi )q, & \text{if }y_j=1;\\ \pi (1-p)+(1-\pi )(1-q), & \text{if }y_j=0. \end{cases} \\&=\pi p^{y_j}(1-p)^{1-y_j}+(1-\pi )q^{y_j}(1-q)^{1-y_j} \end{aligned}

所以有

P(y|\theta)=\prod_{j=1}^NP(y_j|\theta)=\prod_{j=1}^N (\pi p^{y_j}(1-p)^{1-y_j}+(1-\pi )q^{y_j}(1-q)^{1-y_j})

EM算法的E步:确定Q函数

\begin{aligned} Q(\theta|\theta_n)&=\sum_zP(z|y,\theta_n)\ln P(y,z|\theta)\\&=\sum_{j=1}^N\{ \sum_zP(z|y_j,\theta_n)\ln P(y_j,z|\theta) \}\\&=\sum_{j=1}^N\{ P(z=1|y_j,\theta_n)\ln P(y_j,z=1|\theta) + P(z=0|y_j,\theta_n)\ln P(y_j,z=0|\theta) \} \end{aligned}

先求 P(z|y_j,\theta_n) :

P(z|y_j,\theta_n)=\begin{cases} \frac{\pi_n p_n^{y_j}(1-p_n)^{1-y_j}}{\pi_n p_n^{y_j}(1-p_n)^{1-y_j}+(1-\pi_n )q_n^{y_j}(1-q_n)^{1-y_j}}=\mu_{j,n} & \text{if }z=1; \\1-\mu_{j,n} & \text{if }z=0. \end{cases}

再求 P(y_j,z|\theta)=P(z|\theta)P(y_j|z,\theta) :

P(y_j,z|\theta)=\begin{cases} \pi p^{y_j}(1-p)^{1-y_j} &\text{if }z=1;\\ (1-\pi )q^{y_j}(1-q)^{1-y_j} &\text{if }z=0. \end{cases}

因此， Q 函数表达式为：

Q(\theta|\theta_n)=\sum_{j=1}^N\{\mu_{j,n}\ln [\pi p^{y_j}(1-p)^{1-y_j}]+(1-\mu_{j,n})\ln [(1-\pi )q^{y_j}(1-q)^{1-y_j}] \}

EM算法的M步,极大化Q函数:

Q函数只包含 \pi 、 p 、 q 三个变量,分别令其导数为0:

\frac{\partial Q(\theta|\theta_n)}{\partial \pi} = 0

\frac{\partial Q(\theta_|\theta_n)}{\partial p} = 0

\frac{\partial Q(\theta_|\theta_n)}{\partial q} = 0

可得到:

\pi=\frac 1n\sum_{j=1}^N\mu_{j,n}

p=\frac{\sum_{j=1}^N\mu_{j,n}y_j}{\sum_{j=1}^N\mu_{j,n}}

q=\frac{\sum_{j=1}^N(1-\mu_{j,n})y_j}{\sum_{j=1}^N(1-\mu_{j,n})}

两硬币模型

假设有两枚不均匀硬币A、B。按某概率随机选择一个硬币，抛掷10次,记录下正反面结果.五次实验结果如下.问两个硬币正面出现的概率？

实验次数 正 反
实验一 5 5
实验二 9 1
实验三 8 2
实验四 4 6
实验五 7 3

在这个问题中，选择的硬币是隐变量. z=(z_1,z_2,z_3,z_4,z_5) ,当 z_i 为1是选择A硬币,为0时选择B硬币.设模型A,B硬币正面朝上的概率为 p , q .选择A硬币的概率为 \pi ,模型参数为: \theta = [p,q,\pi] .观测数据为 y=(y_1,...,y_5) ,其中 y_j 代表第j次实验正面朝上的次数.

对于第 j 次试验，

\begin{aligned} P(y_j|\theta)&= \sum_zP(y_j,z|\theta)\\&=\sum_zP(z|\theta)P(y_j|z,\theta)\\ &=P(z=1|\theta)P(y_j|z=1,\theta)+P(z=0|\theta)P(y_j|z=0,\theta) \\ &= \pi p^{y_j}(1-p)^{10-y_j} +(1-\pi )q^{y_j}(1-p)^{10-y_j} \end{aligned}

完全数据的对数似然函数:

P(y|\theta)=\prod_{j=1}^NP(y_j|\theta)=\prod_{j=1}^N (\pi p^{y_j}(1-p)^{10-y_j} +(1-\pi )q^{y_j}(1-p)^{10-y_j})

EM算法的E步:确定Q函数

\begin{aligned} Q(\theta|\theta_n)&=\sum_zP(z|y,\theta_n)\ln P(y,z|\theta)\\&=\sum_{j=1}^N\{ \sum_zP(z|y_j,\theta_n)\ln P(y_j,z|\theta) \}\\&=\sum_{j=1}^N\{ P(z=1|y_j,\theta_n)\ln P(y_j,z=1|\theta) + P(z=0|y_j,\theta_n)\ln P(y_j,z=0|\theta) \} \end{aligned}

先求 P(z|y_j,\theta_n) :

P(z|y_j,\theta_n)=\begin{cases} \frac{\pi p^{y_j}(1-p)^{10-y_j}}{\pi p^{y_j}(1-p)^{10-y_j} +(1-\pi )q^{y_j}(1-p)^{10-y_j}}=\mu_{j,n} & \text{if }z=1; \\1-\mu_{j,n} & \text{if }z=0. \end{cases}

再求 P(y_j,z|\theta)=P(z|\theta)P(y_j|z,\theta) :

P(y_j,z|\theta)=\begin{cases} \pi p^{y_j}(1-p)^{10-y_j} &\text{if }z=1;\\ (1-\pi )q^{y_j}(1-p)^{10-y_j} &\text{if }z=0. \end{cases}

因此， Q 函数表达式为：

Q(\theta|\theta_n)=\sum_{j=1}^N\{\mu_{j,n}\ln [\pi p^{y_j}(1-p)^{10-y_j}]+(1-\mu_{j,n})\ln [(1-\pi )q^{y_j}(1-p)^{10-y_j}] \}

EM算法的M步,极大化Q函数

Q函数只包含 \pi 、 p 、 q 三个变量,分别令其导数为0,会得到一个方程组,解方程组即可求出 \pi 、 p 、 q 的值.

posted @ 2018-12-10 14:42:41
评论加载中...
发表评论