The approach

  • The practitioner's standard method for learning a probabilistic model is maximum likelihood: pick the parameter within the family whose model has the best probability of generating the observed data 17:01, 17:35, 18:04.

  • Assuming i.i.d. samples v₁ … vₙ, the optimization is

    max over θ of Σᵢ₌₁ⁿ log p_θ(vᵢ)

    where p_θ is the density of D(θ) 18:04, 21:46, 22:21.

  • Sum-of-logs is used purely for convenience — it is equivalent to maximizing the product of probabilities, and a sum is conceptually easier to reason about 19:16.

Where it works

  • Effective for very simple distributions. For a single Gaussian the optimization is easy and yields the intuitive answer: the estimated mean is the sample mean 20:00.

Where it breaks

  • For a mixture of Gaussians, maximum likelihood is at least as hard as k-means clustering, which is itself NP-hard 20:34.
  • Important caveat about what the hardness means: NP-hardness refers to the worst case, where the vᵢ are arbitrary points not drawn from D(θ) 21:03.
  • The actual learning problem — data really generated by D(θ) — is not a worst-case problem, so it cannot straightforwardly be called NP-hard 21:46. This gap is the opening the rest of the lecture exploits.
flowchart TD
    A[Maximum likelihood] --> B[Single Gaussian:<br/>easy, mean = sample mean]
    A --> C[Mixture of Gaussians:<br/>≥ k-means → NP-hard]
    C --> D[But NP-hardness is worst case:<br/>arbitrary data points]
    D --> E[Learning problem is average case:<br/>data really from D of theta]
    E --> F[Room for better algorithms]