机器学习笔记(9)-最大期望算法
最大期望算法（Expectation-Maximization algorithm，EM）是一类通过迭代进行极大似然估计的优化算法，常用于高斯混合模型等，主要是用来解决那些样本中存在隐变量的情况。
在采用极大似然估计构造我们的目标函数时，有时我们会假设随机变量(X,Y)的似然函数和先验概率是符合某个分布的，这样我们就能通过得到先验概率和似然函数来确定目标函数。
EM算法虽然同样是使用极大似然估计来估计参数，但是它的思想是认为随机变量(X)是根据隐藏变量(Z)来确定的，参数( heta)是隐藏变量(Z)的参数，于是有：
- (X)：观测数据集（数据样本）
- (Z)：未观察数据集（隐藏变量）
- ((X,Z))：完备数据集
- ( heta)：参数
EM算法核心优化思想：
EM算法分为E-step和M-step两步，通过迭代的思想重复这两步来计算参数( heta)：
E-step：初始化一个参数或根据上一次迭代得到的( heta)，计算得到后验概率，得到完备数据的最大期望：
[P(Z|X; heta^t)
ightarrow E_{Z|X; heta^t}[log P(X,Z)]
]
M-step：计算使期望最大化的参数(hat heta)，代入E步：
[ heta^{t+1}=underset{ heta}{argmax};E_{Z|X; heta^t}[log P(X,Z)]
]
反复迭代E步和M步直到参数( heta)收敛。
EM目标函数推导
接下来我们就来推导一下EM的目标函数，根据贝叶斯定理有：
[P(X| heta)=frac{P(X,Z| heta)}{P(Z|X; heta)}
]
我们两边取对数得到：
[egin{aligned}
log P(X| heta)&=log P(X,Z| heta)-log P(Z|X; heta)\\
&=log frac{P(X,Z| heta)}{q(Z)}-log frac{P(Z|X; heta)}{q(Z)}
end{aligned}
]
设有概率分布(q(Z))，有(int_{Z}^{}q(Z)d_{Z}=1)且(q(Z)
eq 0)。
接下来我们两边对(q(Z))关于(Z)求积分运算，左边为：
[egin{aligned}
int_{Z}^{}log P(X| heta)q(Z)d_{Z}&=log P(X| heta)int_{Z}^{}q(Z)d_{Z}\
&=log P(X| heta)
end{aligned}
]
接下来我们看右边为：
[egin{aligned}
&int_{Z}^{}q(Z)log frac{P(X,Z| heta)}{q(Z)}d_{Z}-int_{Z}^{}q(Z)log frac{P(Z|X; heta)}{q(Z)}d_{Z}\
&=int_{Z}^{}q(Z)log frac{P(X,Z| heta)}{q(Z)}d_{Z}+int_{Z}^{}q(Z)log frac{q(Z)}{P(Z|X; heta)}d_{Z}
end{aligned}
]
上式中左半部分我们称为ELBO（Evidence Lower Bound），右半部分就是KL散度(KL(q(Z)||P(Z|X; heta)))
[log P(X| heta)=ELBO+KL(q(Z)||P(Z|X; heta))\
ELBO=int_{Z}^{}q(Z)log frac{P(X,Z| heta)}{q(Z)}d_{Z}\
KL(q(Z)||P(Z|X; heta))=int_{Z}^{}q(Z)log frac{q(Z)}{P(Z|X; heta)}d_{Z}
]
我们知道散度是大于等于0的，只有当(q(Z)=P(Z|X; heta))时取等号。
EM算法的思想就是让ELBO取最大，从而使(log P(X| heta))最大，并且使(q(Z)=P(Z|X; heta^t))取上一次迭代的参数的到后验概率代入。
于是：
[egin{aligned}
heta^{t+1}&=underset{ heta}{argmax};ELBO\
&=underset{ heta}{argmax};int_{Z}^{}q(Z)log frac{P(X,Z| heta)}{q(Z)}d_{Z}\
&=underset{ heta}{argmax};int_{Z}^{}P(Z|X; heta^t)log frac{P(X,Z| heta)}{P(Z|X; heta^t)}d_{Z}\
&=underset{ heta}{argmax};int_{Z}^{}P(Z|X; heta^t)(log P(X,Z| heta)-log P(Z|X; heta^t))d_{Z}\
&=underset{ heta}{argmax};int_{Z}^{}P(Z|X; heta^t)log P(X,Z| heta)d_{Z}
end{aligned}
]
上式中因为(P(Z|X; heta^t))是定值，( heta^t)是确定的，所以不影响可以去掉。
以上这就是EM的目标函数，通过上一个时间步参数( heta^t)得到下一个时间步( heta^{t+1})，反复迭代直到收敛。
收敛性证明
这一节我们证明经过每个时间步( heta)是收敛的，也就是要证明：
[log P(X| heta^t)leq log P(X| heta^{t+1})
]
也就是说，我们每次迭代一次E步后，得到的新的( heta^{t+1})要使极大似然估计变大一点，直到最大，就把我们的参数给估计出来了，这和梯度下降法是很类似的思想。
我们上一节的结论有：
[log P(X| heta)=ELBO+KL(q(Z)||P(Z|X; heta))\
ELBO=int_{Z}^{}q(Z)log frac{P(X,Z| heta)}{q(Z)}d_{Z}\
KL(q(Z)||P(Z|X; heta))=int_{Z}^{}q(Z)log frac{q(Z)}{P(Z|X; heta)}d_{Z}
]
合在一起就有：
[egin{aligned}
log P(X| heta)&=int_{Z}^{}q(Z)log frac{P(X,Z| heta)}{q(Z)}d_{Z}+int_{Z}^{}q(Z)log frac{q(Z)}{P(Z|X; heta)}d_{Z}\
&=int_{Z}^{}q(Z)log P(X,Z| heta)d_{Z}+int_{Z}^{}q(Z)log frac{1}{P(Z|X; heta)}d_{Z}
end{aligned}
]
分别代入(log P(X| heta^t))和(log P(X| heta^{t+1}))就有：
[log P(X| heta^{t+1})=int_{Z}^{}q(Z)log P(X,Z| heta^{t+1})d_{Z}+int_{Z}^{}q(Z)log frac{1}{P(Z|X; heta^{t+1})}d_{Z}\
log P(X| heta^{t})=int_{Z}^{}q(Z)log P(X,Z| heta^{t}){q(Z)}d_{Z}+int_{Z}^{}q(Z)log frac{1}{P(Z|X; heta^{t})}d_{Z}
]
这里我们令(q(Z)=P(Z|X; heta^t))就变成了：
[log P(X| heta^{t+1})=int_{Z}^{}P(Z|X; heta^t)log P(X,Z| heta^{t+1})d_{Z}+int_{Z}^{}P(Z|X; heta^t)log frac{1}{P(Z|X; heta^{t+1})}d_{Z}\
log P(X| heta^{t})=int_{Z}^{}P(Z|X; heta^t)log P(X,Z| heta^{t})d_{Z}+int_{Z}^{}P(Z|X; heta^t)log frac{1}{P(Z|X; heta^{t})}d_{Z}
]
观察两式的左半边，根据我们上一节得到的结论：
[ heta^{t+1}=underset{ heta}{argmax};int_{Z}^{}P(Z|X; heta^t)log P(X,Z| heta)d_{Z}
]
( heta^{t+1})是取最大值时得到的，所以必然有：
[int_{Z}^{}P(Z|X; heta^t)log P(X,Z| heta^{t+1})d_{Z}geq int_{Z}^{}P(Z|X; heta^t)log P(X,Z| heta^{t})d_{Z}
]
左半边得证，那么我们只要证明右半边也是大于等于就行了：
[egin{aligned}
&int_{Z}^{}P(Z|X; heta^t)log frac{1}{P(Z|X; heta^{t+1})}d_{Z}-int_{Z}^{}P(Z|X; heta^t)log frac{1}{P(Z|X; heta^{t})}d_{Z}\\
&=int_{Z}^{}P(Z|X; heta^t)log frac{P(Z|X; heta^{t})}{P(Z|X; heta^{t+1})}d(Z)\\
&=int_{Z}^{}P(Z|X; heta^t)-log frac{P(Z|X; heta^{t+1})}{P(Z|X; heta^{t})}d(Z)
end{aligned}
]
这里我们借助Jensen不等式，如果g是任意实可测函数且函数(phi)是凸的，那么就有：
[phi (int_{-infty }^{+infty }g(x)f(x)d(x))leq int_{-infty }^{+infty }phi(g(x))f(x)d(x)
]
显然这里的(log)函数是一个凸函数，于是有：
[egin{aligned}
int_{Z}^{}P(Z|X; heta^t)-log frac{P(Z|X; heta^{t+1})}{P(Z|X; heta^{t})}d(Z)geq -log int_{Z}^{}P(Z|X; heta^t)frac{P(Z|X; heta^{t+1})}{P(Z|X; heta^{t})}d(Z)\
=-log int_{Z}^{}P(Z|X; heta^{t+1})d(Z)=0
end{aligned}
]
所以右半边也是大于等于0的数，所以得证，EM算法是收敛的。
[log P(X| heta^t)leq log P(X| heta^{t+1})
]
总结
EM算法的思想就是：
E步：先初始化一个参数( heta)，这样我们就可以得到最大期望的表达式；
M步：根据E步最大期望的表达式，计算参数( heta^{t+1})。
然后反复E步M步使极大似然估计收敛。
所以说EM算法是一种迭代性质的优化算法（不是模型）。