depth first search

The next algorithm in my continuing series of short, hackable implementations of common machine learning algorithms is fitting a Gaussian mixture model through expectation maximization.

This example follows section 9.2 in Bishop’s PRML. You can think of this kind of EM as “soft” clustering. We assume that the data has clusters, and that the cluster that any particular data point belongs to is missing information. It is precisely this kind of hidden information that EM attempts to recover.

You can think of the algorithm as guessing the hidden cluster for each point, then assuming that guess is correct, figuring out what the remaining distribution parameters should be. Then guess again, and recompute. Repeating this process often yields a useful estimate of the hidden parameters, as well explaining the visible data.

It turns out that optimizing warehouse tasks is hard.

Do shorter hypotheses result in more generalization?

We have Occam’s razor as borrowed from Statistical Learning Theory:

Entities should not be multiplied beyond necessity.

Vapnik provides two reinterpretations, the common:

The simplest explanation is the best.

And the structural risk minimization version:

The explanation by the machine with the smallest capacity (VC dimension) is the best.