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

Question

一般来说，更具体地说是伯努利混合模型(又名潜在类分析)。

Answer 1

EM 与 k 均值的 Lloyds 变体几乎相同。因此每次迭代都需要 O(n*k) 距离计算。它们是更复杂的距离计算，但最终它们是马氏距离的某种变体。

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

对于新兴市场来说，这并不容易。对象不会分配给单个集群，而是像模糊 C 均值一样相对地分配给所有集群。那时您就失去了终止保证。

因此，在没有任何停止阈值的情况下，EM 将无限优化集群分配，直至无限精度(假设您将以无限精度实现它)。

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

任何阈值(如果只是硬件浮点精度)都会使其提前完成。但这里很难得到与 O(n*k*i) 不同的理论极限，其中 i 是迭代次数(可能是无限的，但如果您不想进行单次迭代，也可以设置为 0)。