EM算法的计算复杂度是多少？

Question

一般来说，更具体的伯努利混合模型（又称潜类分析）。

Answer 1

由于EM算法本质上是迭代的，所以您必须决定终止标准。如果您修复了步数的上限，运行时分析显然很容易。对于其他终止标准（如收敛到恒定差异），必须对情况进行具体分析。长话短说，“EM”的描述不包括终止标准，所以这个问题不能这样回答。

Answer 2

EM与K-means的劳埃德变体几乎相同。所以每次迭代需要O(n*k)距离计算。它们是更复杂的距离计算，但最终它们是马哈拉诺比斯距离的一些变体。

但是，k-means具有相当不错的终止行为。只有k^n个可能的群集分配。现在，如果在每一步中，您选择一个更好的，它将不得不尝试所有k^n后终止最新。但实际上，它通常会在最多几十步后终止。

对于EM，这并不容易。对象没有被分配到一个单一的聚类，但如在模糊C均值相对于所有聚类分配。那就是当你失去这个终止保证。

因此，如果没有任何停止阈值，EM将无限优化集群分配，达到无限精度（假设您将以无限精度实现它）。

因此，EM的理论运行时间为：无限。

任何阈值（如果它只是硬件浮点精度）将使它更早完成。但是这里很难获得理论上的极限，这里的值不同于O(n*k*i)，其中i是迭代次数（可能是无限的，但如果您不想进行单次迭代，也可以将其设置为0）。

Answer 3

这就是我的想法： 如果我们假设的EM algorithm使用linear algebra，这确实如此，那么它的复杂性应该是O（MN^3），其中m是 迭代次数，n是参数数量。

迭代次数将受到起始值质量的影响。良好的起始值意味着小米。

由于收敛到本地解决方案，不太好的起始值意味着更大的m甚至失败。局部解决方案可以存在，因为EM用于可能性函数nonlinear。

良好的起始值意味着您从围绕全局最优解的轨迹的凸起吸引区开始。