论EM和K-Means算法的收敛性

标签（空格分隔）： 机器学习

---

最近接受了成波次的笔试与面试考核，在其中两次面试均围绕K-Means算法的收敛性展开。通过多方查阅资料后仍未能获得令人信服的答案，并希望能够从两者间的关联性入手分析，并结合EM算法收敛性的理论基础来寻找解题思路。

EM算法的收敛性

1.通过极大似然估计建立目标函数：

l(\theta) = \sum_{i=1}^{m}log\ p(x;\theta) = \sum_{i=1}^{m}log\sum_{z}p(x,z;\theta)

采用EM算法以求解模型参数的最大似然估计

如图所示

• 在绿色线位置，找到一个\gamma函数，能够使得该函数最接近目标函数，

  • 固定函数，找到最大值，然后更新,得到红线；

• 对于红线位置的参数：

确定最优的一个函数, 使其能够使该函数与目标函数更加接近. 然后反复执行这一过程直至达到局部最大值的位置.

2. 从Jensen不等式的角度来推导

令Q_{i}是的一个分布，$Q_{i} \geq