02 — Probabilistic models and the learning problem

Defining "structure" with a probabilistic model

The popular way to specify what structure to look for is a probabilistic model: it takes parameters and tells you how to generate points; the parameters are the structure you want 6:14.
Informal definition: a function mapping a parameter θ to a data distribution D(θ) 7:04.
Simplest instance — a single Gaussian: parameters are mean and variance; learning = estimate them from samples 7:04, 8:05.
Key framing: the learning problem is the inverse of the data-generating process 8:36.

Generative story with k = 3: pick a Gaussian with probabilities 0.4 / 0.3 / 0.3, then sample a point from it 9:12, 9:40, 10:05.

The hardness: the learner sees only the points, never which Gaussian produced each one 10:05, 10:28.

Parameters:

Parameter	Meaning	Reference
`k`	number of Gaussians	`10:28`
`μᵢ`, i ∈ [k]	means (centers) of the Gaussians	`11:06`
`wᵢ`, i ∈ [k]	mixing weights — fraction of points from each Gaussian	`12:04`, `12:30`

Simplifying assumption used here: all Gaussians are spherical with the same known covariance, so covariance is not part of θ 11:46.

Given polynomially many samples from D(θ) for unknown θ, recover θ 13:05.
Better framing (in reply to a student question): the algorithm has oracle access to a sampler for D(θ); the sample count need not be polynomial — it depends on how strong a theorem you want 14:13, 14:42, 15:33.
Runtime spectrum for mixtures of Gaussians: D^k time (already non-trivial) vs. poly(D, k) time (much harder), where D is the dimension 14:42, 15:08.

Exact recovery of θ is generally impossible even ignoring computation time — averaging samples to estimate a Gaussian mean still leaves error depending on the sample count 16:08.
And only with high probability, since the samples drawn may happen to be uninformative 16:33.