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

Question

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

Answer 1

EM is pretty much the same as Lloyds variant of k-means. So each iteration takes O(n*k) distance computations. They are more complex distance computations, but in the end they are some variant of Mahalanobis distance.

However, k-means has a quite nice termination behavior. There are only k^n possible cluster assignments. Now if in each step, you choose one that is better, it will have to terminate the latest after trying out all k^n. But in reality, it usually terminates after at most a few dozen steps.

For EM, this is not as easy. Objects are not assigned to a single cluster, but as in fuzzy-c-means are assigned relatively to all clusters. And that's when you lose this termination guarantee.

So without any stopping threshold, EM would infinitely optimize the cluster assignments, up to an infinite precision (assuming you would implement it with infinite precision).

As such, the theoretical runtime of EM is: infinite.

Any threshold (and if it's just hardware floating point precision) will make it finish earlier. But it will be hard to get a theoretical limit here different than O(n*k*i) where i is the number of iterations (which could be infinite, but which you can also set to 0 if you don't want to do a single iteration).

Answer 2

由于 EM 算法本质上是迭代的，因此您必须确定终止标准。如果您确定步数的上限，运行时分析显然很容易。对于其他终止标准（如收敛到恒定差异），必须具体分析情况。

长话短说，“EM”的描述不包括终止标准，所以这个问题不能这样回答。

Answer 3

这就是我的想法：如果我们假设EM algorithmuses linear algebra，它确实如此，那么它的复杂度应该是O(mn^3)，其中 m 是迭代次数，n 是参数的数量。

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

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

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