07EM算法

Lingfeng 2025-05-23

07EM算法

1. EM 算法步骤

Definition (EM 算法)

设观测数据为 $X=\{ X_{1},X_{2},\dots,X_{n} \}$ ，没有观测到的隐含数据为 $Y=\{ Y_{1},Y_{2},\dots,Y_{n} \}$ ，完整数据为 $Z=(X,Y)$ 。完整数据联合分布为 $p(X,Y;\theta)$ ，条件分布记为 $p(Y\mid X;\theta)$ 。EM 迭代算法如下：

E 步：记 $\theta^{(t-1)}$ 表示第 $t-1$ 步得到的参数估计，首先利用 Bayes 公式计算后验概率 $\gamma(y)=P\{ Y=y\mid X;\theta^{(t-1)} \}$ 定义 $Q(\theta)=E_{Y}(\log p(X,Y;\theta)\mid X;\theta^{(t-1)})= \int \log p(X,Y=y;\theta) \gamma(y) \, dy$ 即为极大似然估计
M 步，得到 $\theta^{(t)}=\arg \max_{\theta}Q(\theta)$

假设有 $A$ ， $B$ 两枚硬币，其中正面朝上的概率分别为 $p_{A}$ ， $p_{B}$ ，这两个参数是感兴趣的待估参数。设计 $n$ 组实验，每次实验投掷 $m$ 次硬币，第 $i$ 组实验结果为 $X_{i}=(x_{i1},x_{i2},\dots,x_{im})$ ， $x_{ij} \in \{ 0,1 \}$ ，表示硬币出现正反面结果。
设 $Y_{i}\in\{ 0,1 \}$ 表示 $X_{i}$ 是 $A$ 硬币还是 $B$ 硬币投的结果，给出 EM 算法步骤。

首先 E 步。考虑计算 $\begin{align*} \gamma_{i} &= P\{ Y_{i}=1 \mid X_{i};\theta^{(t-1)} \} \\ & = \frac{P\{ X_{i}\mid Y_{i}=1;\theta^{(t-1)} \}\pi}{P\{ X_{i}\mid Y_{i}=1 ;\theta^{(t-1)}\}\pi+P\{ X_{i}\mid Y_{i}=0;\theta^{(t-1)} \}(1-\pi)} \end{align*}$ 其中 $\pi=P\{ Y_{i}=1 \}$ 表示 $A$ 硬币的先验分布。且设 $s_{i}=\sum_{j = 1}^{m}x_{ij}$ ，有 $\begin{align*} P\{ X_{i}\mid Y_{i}=1 \} & =p_{A}^{(t-1)s_{i}}(1-p_{A}^{(t-1)})^{m-s_{i}} \\ P\{ X_{i}\mid Y_{i}=0 \} & =p_{B}^{(t-1)s_{i}}(1-p_{B}^{(t-1)})^{m-s_{i}} \end{align*}$ 因此计算 $\begin{align*} Q(\theta) & =\sum_{i = 1}^{n} \log p(X,Y_{i}=1;\theta) \gamma_{i} + \log p(X,Y_{i}=0;\theta)(1-\gamma_{i}) \\ & = \sum_{i = 1}^{n} \gamma_{i}(s_{i}\log p_{A}+(m-s_{i})\log(1-p_{A})) \\ & \quad + (1-\gamma_{i})(s_{i}\log p_{B}+(m-s_{i})\log(1-p_{B})) \end{align*}$
再计算 M 步骤。令 $\begin{align*} \frac{ \partial Q(\theta) }{ \partial p_{A} } &= \frac{1}{p_{A}}\left( \sum_{i = 1}^{n} \gamma_{i}s_{i} \right) - \frac{1}{1-p_{A}}\left( \sum_{i = 1}^{n} \gamma_{i}(m-s_{i}) \right)=0 \end{align*}$ 即得 $p_{A}^{(t)}=\frac{\sum_{i = 1}^{n} \gamma_{i}s_{i} }{m\sum_{i = 1}^{n} \gamma_{i}}$ 同理 $p_{B}^{(t)}=\frac{\sum_{i = 1}^{n} (1-\gamma_{i})s_{i} }{m\sum_{i = 1}^{n} (1-\gamma_{i})}$

2.2 多项分布参数的 EM 算法

Example (多项分布的 EM 算法)

设 $X=(X_{1},X_{2},X_{3},X_{4})$ 满足多项分布，参数 $(p_{1},p_{2},p_{3},p_{4})=\left( 0.5-\frac{\theta}{2}, \frac{\theta}{4}, \frac{\theta}{4}, 0.5 \right)$ ，待估参数为 $\theta$ 。观测数据为 $x=(x_{1},x_{2},x_{34})$ ，其中 $x_{34}=x_{3}+x_{4}$ 。
此时隐藏变量为 $X_{3}$ ，给出 EM 算法步骤。

首先 E 步。考虑 $\begin{align*} \gamma(n) & = P\{ X_{3}=n \mid X_{1},X_{2}, X_{34}; \theta^{(t-1)} \} \\ & = \frac{P\{ X_{1},X_{2}, X_{3}=n,X_{4}=x_{34}-n;\theta^{(t-1)} \}}{P\{ X_{1},X_{2}, X_{34}; \theta^{(t-1)} \}} \\ & =\frac{x!}{x_{1}!x_{2}!n!(x_{34}-n)!} \cdot \frac{x_{1}!x_{2}!x_{34}!}{n!}\frac{p_{1}^{x_{1}}p_{2}^{x_{2}}p_{3}^{n}p_{4}^{x_{34}-n}}{p_{1}^{x_{1}}p_{2}^{x_{2}}(p_{3}+p_{4})^{x_{34}}} \\ & = \binom{x_{34}}{n} \left( \frac{p_{3}}{p_{3}+p_{4}} \right)^{n}\left( \frac{p_{4}}{p_{3}+p_{4}} \right)^{x_{34}-n} \\ & = \binom{x_{34}}{n} \left( \frac{\theta^{(t-1)}}{\theta^{(t-1)}+2} \right)^{n}\left( \frac{2}{\theta^{(t-1)}+2} \right)^{x_{34}-n} \end{align*}$ 即 $X_{3}\mid x;\theta^{(t-1)}\sim B\left( x_{34}, \frac{\theta^{(t-1)}}{\theta^{(t-1)}+2} \right)$ 。因此 $\begin{align*} Q(\theta) & = E(\log p(x_{1},x_{2},x_{3},x_{4};\theta) \mid x;\theta^{(t-1)})\\ & = E \left( x_{1}\log \left( \frac{1}{2}-\frac{\theta}{2} \right)+x_{2}\log \frac{\theta}{4}+x_{3}\log \frac{\theta}{4}\mid x;\theta^{(t-1)} \right)+ C \\ & =x_{1}\log\left( \frac{1}{2}-\frac{\theta}{2} \right)+x_{2}\log \frac{\theta}{4}+ E(X_{3}\mid x;\theta^{(t-1)})\log \frac{\theta}{4} + C \end{align*}$

再考虑 M 步。令 $\frac{ \partial Q(\theta) }{ \partial \theta } = -\frac{x_{1}}{1-\theta}+ \frac{x_{2}}{\theta}+ \frac{E(X_{3}\mid x;\theta^{(t-1)})}{\theta}=0$ 得到 $\theta^{(t)}= \frac{x_{2}+E(X_{3}\mid x;\theta^{(t-1)})}{x_{1}+x_{2}+E(X_{3}\mid x;\theta^{(t-1)})}$

2.3 正态分布参数 EM 估计

Example (正态分布的 EM 估计)

设 $z=(x_{1},x_{2},\dots,x_{n})$ ，其中 $x_{i}\sim N(\mu,\sigma^{2})$ ，对于观测数据 $x=(x_{1},x_{2},\dots,x_{m})$ ，未知数据 $y=(x_{m+1},\dots,x_{n})$ ，待估参数为 $\mu$ 和 $\sigma^{2}$ 。给出 EM 算法步骤。

考虑 $\begin{align*} Q(\mu,\sigma^{2}) & =E(\log p(x,y;\mu,\sigma^{2})\mid x;\mu^{(t-1)},\sigma^{2(t-1)}) \\ & = E\left( -\frac{n}{2} \log\sigma^{2} - \sum_{i = 1}^{n} \frac{(x_{i}-\mu)^{2}}{2\sigma^{2}} \mid x;\mu^{(t-1)},\sigma^{2(t-1)}\right)+C \\ & = -\frac{n}{2}\log\sigma^{2}- \sum_{i = 1}^{m} \frac{(x_{i}-\mu)^{2}}{2\sigma^{2}}- \frac{(n-m)\mu^{2}}{2\sigma^{2}} \\ & \quad+ \frac{\mu}{\sigma^{2}}\sum_{i = m+1}^{n}E( x_{i} \mid x;\mu^{(t-1)},\sigma^{2(t-1)} ) -\frac{1}{2\sigma^{2}} \sum_{i = m+1}^{n}E( x_{i}^{2} \mid x;\mu^{(t-1)},\sigma^{2(t-1)} ) \end{align*}$ 令 $\frac{ \partial Q(\mu,\sigma^{2}) }{ \partial \mu } \propto \sum_{i = 1}^{m} (x_{i}-\mu) -(n-m) \mu +\sum_{i = m+1}^{n}E( x_{i} \mid x;\mu^{(t-1)},\sigma^{2(t-1)} ) =0$ 因此 $\mu^{(t)}= \frac{1}{n}\left( \sum_{i = 1}^{m} x_{i}+ \sum_{i = m+1}^{n}E( x_{i} \mid x;\mu^{(t-1)},\sigma^{2(t-1)} ) \right)$

3. 混合模型的 EM 算法

Definition (混合模型的 EM 算法)

设数据集由 $M$ 个总体组成，有 $p(x;\theta)=\sum_{j = 1}^{M} \alpha_{j}p_{j}(x;\theta_{j})$ 若观测数据为 $X=(x_{1},x_{2},\dots,x_{N})$ ，未观测数据为 $Y=(y_{1},y_{2},\dots,y_{N})$ ，其中 $y_{i}\in \{ 1,2,\dots,M \}$ 表示数据的来源。待估参数为 $\theta$ 与 $\alpha$ ，则 $\begin{align*}Q(\theta,\alpha) & =\sum_{i = 1}^{N} \sum_{j = 1}^{M} E(\log \alpha_{j}p_{j}(x_{i},y_{j};\theta_{j})\mid x_{i};\theta^{(t-1)},\alpha^{(t-1)}) \\ & =\sum_{i = 1}^{N} \sum_{j = 1}^{M} \log (\alpha_{j}p_{j}(x_{i};\theta_{j}))p(y_{j}\mid x_{i};\theta^{(t-1)},\alpha^{(t-1)}) \end{align*}$ 其中 $\begin{align*}p(y_{j}\mid x_{i};\theta^{(t-1)},\alpha^{(t-1)})= \frac{\alpha_{j}^{(t-1)}p_{j}(x_{i};\theta_{j}^{(t-1)})}{\sum_{j = 1}^{M}\alpha^{(t-1)}p_{j}(x_{i};\theta_{j}^{(t-1)})}\end{align*}$ $\alpha^{(t)}_{j}$ 更新为 $\alpha_{j}^{(t)}=\frac{1}{N}\sum_{i = 1}^{N}p(y_{j}\mid x_{i};\theta^{(t-1)},\alpha^{(t-1)})$

由于有 $\sum_{j = 1}^{M}\alpha_{j}=1$ 约束，因此引入拉格朗日乘子 $\lambda$ ，有 $\frac{ \partial }{ \partial \alpha_{j} } \left( Q(\theta,\alpha)-\lambda\left( \sum_{j = 1}^{M} \alpha_{j}-1 \right) \right) = \frac{1}{\alpha _{j}} \sum_{i = 1}^{N} p(y_{j}\mid x_{i};\theta^{(t-1)},\alpha^{(t-1)})-\lambda = 0$ 即得 $\alpha_{j}^{(t)}=\frac{1}{\lambda}\sum_{i = 1}^{N}p(y_{j}\mid x_{i};\theta^{(t-1)},\alpha^{(t-1)})$ 代入约束有 $\frac{1}{\lambda}\sum_{i = 1}^{N}\sum_{j = 1}^{M} p(y_{j}\mid x_{i};\theta^{(t-1)},\alpha^{(t-1)})=1$ 从而 $\lambda=N$ ，因此 $\alpha_{j}^{(t)}=\frac{1}{N}\sum_{i = 1}^{N}p(y_{j}\mid x_{i};\theta^{(t-1)},\alpha^{(t-1)})$

Example (高斯混合分布的 EM 算法)

有 $M$ 个 $d$ 维均值为 $\mu_{j}$ ，方差为 $\Sigma_{j}$ 的正态分布，此时 $p(x;\mu_{1},\Sigma_{1},\dots,\mu_{M},\Sigma_{M})=\sum_{j = 1}^{M} \alpha_{j}p_{j}(x;\mu_{j},\Sigma_{j})$ 观测数据为 $X=(x_{1},x_{2},\dots,x_{N})$ ，未观测数据为 $Y=(y_{1},y_{2},\dots,y_{N})$ ，其中 $y_{i}\in \{ 1,2,\dots,M \}$ 表示数据的来源。待估参数为 $\mu_{j}$ ，给出EM算法步骤。

考虑 $Q(\mu) = \sum_{i = 1}^{N} \sum_{j = 1}^{M} \log (\alpha_{j}p_{j}(x_{i};\mu_{j}))p(y_{j}\mid x_{i};\mu^{(t-1)})$ 计算 $\frac{ \partial Q(\mu) }{ \partial \mu_{j} } =\sum_{i = 1}^{n} \frac{ \partial \log p_{j}(x_{i};\mu_{j}) }{ \partial \mu_{j} }p(y_{j}\mid x_{i};\mu^{(t-1)}) = 0$ 注意到 $\begin{align*} \frac{ \partial \log p_{j}(x_{i};\mu_{j}) }{ \partial \mu_{j} } & = \frac{ \partial }{ \partial \mu_{j} } \left( -\frac{1}{2} (x_{i}-\mu_{j})^{\top}\Sigma_{j}^{-1}(x_{i}-\mu_{j}) \right) \\ & = \Sigma^{-1}_{j}(x_{i}-\mu_{j}) \end{align*}$ 因此解得 $\mu_{j}^{(t)}= \frac{\sum_{i = 1}^{N} x_{i}p(y_{j}\mid x_{i};\mu^{(t-1)}))}{\sum_{i = 1}^{N} p(y_{j}\mid x_{i};\mu^{(t-1)})}$

07EM算法

07EM算法

1. EM 算法步骤

2. 特殊分布参数的 EM 算法

2.1 伯努利分布的 EM 算法

2.2 多项分布参数的 EM 算法

2.3 正态分布参数 EM 估计

3. 混合模型的 EM 算法