CODEWITHSUNDEEP
machine-learningtime-complexitycluster-analysisdata-miningspace-complexity
Jessica
Jessica

Reputation: 99

What is the computational complexity of the EM algorithm?

In general, and more specifically for Bernoulli mixture model (aka Latent Class Analysis).

Upvotes: 3

Views: 10657

Answers (3)

user75573
user75573

Reputation: 1

This is what I think: If we presume that the EM algorithm uses linear algebra, which it does, then its complexity should be O(m.n^3), where m is the number of iterations and n is the number of parameters.

The number of iterations will be influenced by the quality of the starting values. Good starting values means small m.

Not-so-good starting values means larger m or even failure because of convergence to a local solution. Local solutions can exist because EM is used on likelihood functions which are nonlinear.

Good starting values means that you start in the convex zone of attraction that surrounds the locus of the globally optimal solution.

Upvotes: 0

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77474

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).

Upvotes: 8

Dino
Dino

Reputation: 1576

Since the EM algorithm is by nature iterative, you must decide on a termination criterion. If you fix an upper bound on the number of steps, runtime analysis is obviously easy. For other termination criteria (like convergence up to a constant difference), the situation must be analyzed specifically.

Long story short, the description "EM" does not include a termination criterion, so the question can't be answered as such.

Upvotes: 0

Related Questions