EM算法理解的第一层境界:期望E和最大化M(一)

举报
人工智障研究员 发表于 2022/06/20 23:01:59 2022/06/20
【摘要】 本文介绍了EM算法的第一层境界的第一部分内容:形式上理解EM算法的期望和最大化,以经典的三硬币问题作为例子,直觉上介绍了EM算法的形式和内容。

前言:学生时代入门机器学习的时候接触的EM算法,当时感觉这后面应该有一套数学逻辑来约束EM算法的可行性。最近偶然在知乎上拜读了史博大佬的《EM算法理解的九层境界》[1],顿时感觉自己还是局限了。重新学习思考了一段时间,对EM算法有了更深的理解。这里顺着大佬的境界路径,看自己能够探索到第几层。

一、EM算法的形式

通常印象中EM算法一般应用于有隐变量的极大似然估计中。对于没有隐变量的极大似然来说,我们需要最大化似然估计 p ( X θ ) p(X|\theta) 。但是当问题中有了隐变量的时候,我们就需要把隐变量给积分掉(遍历隐变量的所有可能性),这个时候的似然估计为:

L ( θ X ) = p ( X θ ) = p ( X , Z θ ) d Z L(\theta|X)=p(X|\theta)=\int p(X, Z|\theta)dZ

一般而言,因为式子中需要将隐变量给积分掉,直接求解这个式子会非常复杂,这个时候EM算法就派上用场了。EM算法是个迭代算法,它由交替进行的两个部分组成:E-step和M-step。在迭代过程中,待估计参数 θ \theta 会逐步接近、到达最优解。
形式上说,EM算法的E-step就是利用上一步迭代得到的待估计参数 θ ( t ) \theta^{(t)} 来“估计”隐变量 Z Z 的“近似”分布,借由 Z Z 的“近似”分布,将隐变量 Z Z 给积分掉,从而得到待估计变量 θ \theta 的“似然”期望值:

Q ( θ θ ( t ) ) = E Z X , θ ( t ) [ log L ( θ ; X , Z ) ] = p ( Z X , θ ( t ) ) log L ( θ ; X , Z ) d Z Q(\theta|\theta^{(t)})=E_{Z|X,\theta^{(t)}}[\log L(\theta;X,Z)]=\int p(Z|X,\theta^{(t)})\log L(\theta;X,Z)dZ

EM算法的M-step就比较直接了,最大化这个变量 θ \theta 的“似然”,得到这一轮迭代变量 θ \theta 的估计值 θ ( t + 1 ) \theta^{(t+1)} :

θ ( t + 1 ) = arg max θ Q ( θ θ ( t ) ) \theta^{(t+1)}=\argmax_{\theta}Q(\theta|\theta^{(t)})

二、经典例子

最为经典简单的隐变量求解问题就是三硬币问题。给定A、B、C三枚硬币,它们抛出正面的概率分别为 θ A \theta_A θ B \theta_B θ C \theta_C 。对于每一个轮次,先抛硬币C来决定使用A、B中的哪枚硬币,正面( θ C \theta_C )使用硬币A,反面( 1 θ C 1-\theta_C )则使用硬币B,接下来将硬币连续抛 δ \delta 次,记录每次正反面情况。然后将上述轮次进行 n n 轮,得出如图1中所示的结果。

EM算法三个硬币例子

图1:EM算法三硬币例子[2]

如果我们知道每个轮次使用的是哪一枚硬币,那么可以直接使用极大似然(maximum likelihood)来求解A、B两枚硬币的正面概率 θ A \theta_A θ B \theta_B ,如图1中情景a所示。

但是如果我们并不知道每个轮次使用的是哪一枚硬币,那么就必须引入隐变量来求解这个问题。

这里我们将例子中的问题形式化一下,方面后面理解EM算法的形式。一共进行了 n n 论次抛硬币游戏,每个轮次抛 δ \delta 次选定的硬币,观测结果记为 X = [ x 1 , x 2 , . . . , x n ] , x i { 0 , 1 , 2 , . . . , δ } X=[x_1, x_2, ..., x_n], x_i\in\{0, 1, 2, ..., \delta\} ,即轮次 i i 抛硬币观察到有 x i x_i 次正面, δ x i \delta-x_i 次反面。所有的待求解参数 θ = [ θ A , θ B , θ C ] , θ A [ 0 , 1 ] , θ B [ 0 , 1 ] , θ C [ 0 , 1 ] \theta=[\theta_A, \theta_B, \theta_C], \theta_A\in[0,1], \theta_B\in[0,1], \theta_C\in[0,1]

接下来就是隐变量的表示,这里我们可以引入硬币C的正面概率 θ C \theta_C 作为隐变量,但是为了与图1中的例子对应起来,我们引入隐变量 Z = [ z 1 , z 2 , . . . , z n ] , z i { 0 , 1 } Z=[z_1, z_2,...,z_n], z_i\in\{0,1\} 表示每一轮次( i i )是硬币A( z i = 1 z_i=1 )还是硬币B( z i = 0 z_i=0 )。

三、直觉上理解EM算法的形式

下面我们直觉上来套用EM算法的形式来求解图1中的三硬币问题。
首先是EM算法的E-step,我们需要依据上一轮的参数估计 [ θ ^ A ( t ) , θ ^ B ( t ) ] [\hat\theta_A^{(t)}, \hat\theta_B^{(t)}] 来“估计”隐变量 Z Z 。这里我们依据直觉来,对于轮次 i i ,隐变量 z i z_i P ( z i = 1 x i ) + P ( z i = 0 x i ) = 1 P(z_i=1|x_i)+P(z_i=0|x_i)=1 ,而依据上一轮的参数估计,我们有在第 i i 轮是硬币A时出现 x i x_i 次正面和 δ x i \delta-x_i 次反面的概率: P ( x i z i = 1 ) = ( θ ^ A ( t ) ) x i ( 1 θ ^ A ( t ) ) δ x i P(x_i|z_i=1)=(\hat\theta_A^{(t)})^{x_i}*(1-\hat\theta_A^{(t)})^{\delta-x_i} ,在第 i i 轮是硬币B时出现 x i x_i 次正面和 δ x i \delta-x_i 次反面的概率 P ( x i z i = 0 ) = ( θ ^ B ( t ) ) x i ( 1 θ ^ B ( t ) ) δ x i P(x_i|z_i=0)=(\hat\theta_B^{(t)})^{x_i}*(1-\hat\theta_B^{(t)})^{\delta-x_i} ,这样我们就可以"估计"出轮次 i i z i z_i 的概率分布:

P ( z i = 1 ) = P ( x i z i = 1 ) / ( P ( x i z i = 1 ) + P ( x i z i = 0 ) ) = ( θ ^ A ( t ) ) x i ( 1 θ ^ A ( t ) ) δ x i ( θ ^ A ( t ) ) x i ( 1 θ ^ A ( t ) ) δ x i + ( θ ^ B ( t ) ) x i ( 1 θ ^ B ( t ) ) δ x i \begin{aligned} P(z_i=1|*) & = P(x_i|z_i=1)/(P(x_i|z_i=1)+P(x_i|z_i=0)) \\ & = \frac{(\hat\theta_A^{(t)})^{x_i}*(1-\hat\theta_A^{(t)})^{\delta-x_i}}{(\hat\theta_A^{(t)})^{x_i}*(1-\hat\theta_A^{(t)})^{\delta-x_i}+(\hat\theta_B^{(t)})^{x_i}*(1-\hat\theta_B^{(t)})^{\delta-x_i}} \end{aligned}

P ( z i = 0 ) = P ( x i z i = 0 ) / ( P ( x i z i = 1 ) + P ( x i z i = 0 ) ) = ( θ ^ B ( t ) ) x i ( 1 θ ^ B ( t ) ) δ x i ( θ ^ A ( t ) ) x i ( 1 θ ^ A ( t ) ) δ x i + ( θ ^ B ( t ) ) x i ( 1 θ ^ B ( t ) ) δ x i \begin{aligned} P(z_i=0|*) & = P(x_i|z_i=0)/(P(x_i|z_i=1)+P(x_i|z_i=0)) \\ & = \frac{(\hat\theta_B^{(t)})^{x_i}*(1-\hat\theta_B^{(t)})^{\delta-x_i}}{(\hat\theta_A^{(t)})^{x_i}*(1-\hat\theta_A^{(t)})^{\delta-x_i}+(\hat\theta_B^{(t)})^{x_i}*(1-\hat\theta_B^{(t)})^{\delta-x_i}} \end{aligned}

接下来是EM算法的M-setp,在上面得到的隐变量 Z Z 的分布之后,我们可以用来估计参数 θ A \theta_A θ B \theta_B 。对于硬币A而言,它在轮次 i i 中抛硬币的次数期望为 δ P ( z i = 1 ) \delta * P(z_i=1) ,抛硬币为正面的次数期望为 x i P ( z i = 1 ) x_i * P(z_i=1) ;对于硬币B而言,它在轮次 i i 中抛硬币的次数期望为 δ P ( z i = 0 ) \delta * P(z_i=0) ,抛硬币为正面的次数期望为 x i P ( z i = 0 ) x_i * P(z_i=0) 。将所有轮次的总的次数期望和跑正面的次数期望加起来,我们有:

θ ^ A ( t + 1 ) = i = 1 n x i P ( z i = 1 ) i = 1 n δ P ( z i = 1 ) \begin{aligned} \hat\theta_A^{(t+1)} & = \frac{\sum_{i=1}^{n}x_i * P(z_i=1|*)}{\sum_{i=1}^{n}\delta * P(z_i=1|*)} \end{aligned}

θ ^ B ( t + 1 ) = i = 1 n x i P ( z i = 0 ) i = 1 n δ P ( z i = 0 ) \begin{aligned} \hat\theta_B^{(t+1)} & = \frac{\sum_{i=1}^{n}x_i * P(z_i=0|*)}{\sum_{i=1}^{n}\delta * P(z_i=0|*)} \end{aligned}

最后硬币 C C ,我们将其估计为所有轮次为硬币 A A 的"期望",即:

θ ^ C ( t + 1 ) = i = 1 n P ( z i = 1 ) i = 1 n [ P ( z i = 0 ) + P ( z i = 1 ) ] = 1 n i = 1 n P ( z i = 1 ) \begin{aligned} \hat\theta_C^{(t+1)} & = \frac{\sum_{i=1}^{n} P(z_i=1|*)}{\sum_{i=1}^{n} [P(z_i=0|*)+P(z_i=1|*)]}=\frac{1}{n}\sum_{i=1}^{n} P(z_i=1|*) \end{aligned}

我们凭借直觉理解,将EM算法的形式套用在三硬币问题上面,得出了每个迭代轮次E-step和M-step的计算过程,两个计算过程都可以与图1中情形b中的例子过程对应起来。

EM算法理解的第一层境界:期望E和最大化M(二)

References

[1] https://www.zhihu.com/question/40797593/answer/275171156
[2] Do C B, Batzoglou S. What is the expectation maximization algorithm?[J]. Nature biotechnology, 2008, 26(8): 897-899.

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。