前言:学生时代入门机器学习的时候接触的EM算法,当时感觉这后面应该有一套数学逻辑来约束EM算法的可行性。最近偶然在知乎上拜读了史博大佬的《EM算法理解的九层境界》[1],顿时感觉自己还是局限了。重新学习思考了一段时间,对EM算法有了更深的理解。这里顺着大佬的境界路径,看自己能够探索到第几层。
一、EM算法的形式
通常印象中EM算法一般应用于有隐变量的极大似然估计中。对于没有隐变量的极大似然来说,我们需要最大化似然估计
p(X∣θ)。但是当问题中有了隐变量的时候,我们就需要把隐变量给积分掉(遍历隐变量的所有可能性),这个时候的似然估计为:
L(θ∣X)=p(X∣θ)=∫p(X,Z∣θ)dZ
一般而言,因为式子中需要将隐变量给积分掉,直接求解这个式子会非常复杂,这个时候EM算法就派上用场了。EM算法是个迭代算法,它由交替进行的两个部分组成:E-step和M-step。在迭代过程中,待估计参数
θ会逐步接近、到达最优解。
形式上说,EM算法的E-step就是利用上一步迭代得到的待估计参数
θ(t)来“估计”隐变量
Z的“近似”分布,借由
Z的“近似”分布,将隐变量
Z给积分掉,从而得到待估计变量
θ的“似然”期望值:
Q(θ∣θ(t))=EZ∣X,θ(t)[logL(θ;X,Z)]=∫p(Z∣X,θ(t))logL(θ;X,Z)dZ
EM算法的M-step就比较直接了,最大化这个变量
θ的“似然”,得到这一轮迭代变量
θ的估计值
θ(t+1):
θ(t+1)=θargmaxQ(θ∣θ(t))
二、经典例子
最为经典简单的隐变量求解问题就是三硬币问题。给定A、B、C三枚硬币,它们抛出正面的概率分别为
θA、
θB、
θC。对于每一个轮次,先抛硬币C来决定使用A、B中的哪枚硬币,正面(
θC)使用硬币A,反面(
1−θC)则使用硬币B,接下来将硬币连续抛
δ次,记录每次正反面情况。然后将上述轮次进行
n轮,得出如图1中所示的结果。
图1:EM算法三硬币例子[2]
如果我们知道每个轮次使用的是哪一枚硬币,那么可以直接使用极大似然(maximum likelihood)来求解A、B两枚硬币的正面概率
θA、
θB,如图1中情景a所示。
但是如果我们并不知道每个轮次使用的是哪一枚硬币,那么就必须引入隐变量来求解这个问题。
这里我们将例子中的问题形式化一下,方面后面理解EM算法的形式。一共进行了
n论次抛硬币游戏,每个轮次抛
δ次选定的硬币,观测结果记为
X=[x1,x2,...,xn],xi∈{0,1,2,...,δ},即轮次
i抛硬币观察到有
xi次正面,
δ−xi次反面。所有的待求解参数
θ=[θA,θB,θC],θA∈[0,1],θB∈[0,1],θC∈[0,1]。
接下来就是隐变量的表示,这里我们可以引入硬币C的正面概率
θC作为隐变量,但是为了与图1中的例子对应起来,我们引入隐变量
Z=[z1,z2,...,zn],zi∈{0,1}表示每一轮次(
i)是硬币A(
zi=1)还是硬币B(
zi=0)。
三、直觉上理解EM算法的形式
下面我们直觉上来套用EM算法的形式来求解图1中的三硬币问题。
首先是EM算法的E-step,我们需要依据上一轮的参数估计
[θ^A(t),θ^B(t)]来“估计”隐变量
Z。这里我们依据直觉来,对于轮次
i,隐变量
zi有
P(zi=1∣xi)+P(zi=0∣xi)=1,而依据上一轮的参数估计,我们有在第
i轮是硬币A时出现
xi次正面和
δ−xi次反面的概率:
P(xi∣zi=1)=(θ^A(t))xi∗(1−θ^A(t))δ−xi,在第
i轮是硬币B时出现
xi次正面和
δ−xi次反面的概率
P(xi∣zi=0)=(θ^B(t))xi∗(1−θ^B(t))δ−xi,这样我们就可以"估计"出轮次
i中
zi的概率分布:
P(zi=1∣∗)=P(xi∣zi=1)/(P(xi∣zi=1)+P(xi∣zi=0))=(θ^A(t))xi∗(1−θ^A(t))δ−xi+(θ^B(t))xi∗(1−θ^B(t))δ−xi(θ^A(t))xi∗(1−θ^A(t))δ−xi
P(zi=0∣∗)=P(xi∣zi=0)/(P(xi∣zi=1)+P(xi∣zi=0))=(θ^A(t))xi∗(1−θ^A(t))δ−xi+(θ^B(t))xi∗(1−θ^B(t))δ−xi(θ^B(t))xi∗(1−θ^B(t))δ−xi
接下来是EM算法的M-setp,在上面得到的隐变量
Z的分布之后,我们可以用来估计参数
θA和
θB。对于硬币A而言,它在轮次
i中抛硬币的次数期望为
δ∗P(zi=1),抛硬币为正面的次数期望为
xi∗P(zi=1);对于硬币B而言,它在轮次
i中抛硬币的次数期望为
δ∗P(zi=0),抛硬币为正面的次数期望为
xi∗P(zi=0)。将所有轮次的总的次数期望和跑正面的次数期望加起来,我们有:
θ^A(t+1)=∑i=1nδ∗P(zi=1∣∗)∑i=1nxi∗P(zi=1∣∗)
θ^B(t+1)=∑i=1nδ∗P(zi=0∣∗)∑i=1nxi∗P(zi=0∣∗)
最后硬币
C,我们将其估计为所有轮次为硬币
A的"期望",即:
θ^C(t+1)=∑i=1n[P(zi=0∣∗)+P(zi=1∣∗)]∑i=1nP(zi=1∣∗)=n1i=1∑nP(zi=1∣∗)
我们凭借直觉理解,将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.
评论(0)