Guest lecturer Rong Ge (postdoc at Microsoft Research, standing in for Jelani Nelson) frames the lecture as an exercise in applying theoretical-CS algorithm design to machine learning problems 0:00, 0:36.

Supervised learning

  • Input: data points and labels; output: a function predicting the label of a new point 2:12, 2:36.
  • Canonical example: a spam filter trained on many emails labelled spam / not-spam 1:48.
  • Studied for decades under the name computational learning theory; explicitly out of scope for this lecture 2:36, 2:54.

Unsupervised learning (the lecture's setting)

  • Motivation: labels are expensive — a human has to label every document or email 3:23.
  • Input is only the data points x, with no labels; the question is what can still be recovered 2:54, 3:23.
  • Answer: learn the structure hidden in the data — a pattern the points were generated from 3:53, 4:29.
  • Classical example — clustering: find k groups so that points inside a cluster are similar and points across clusters are far apart 4:49.

The open question this raises

Clustering is one structure, but structure in general is hard to pin down — which is exactly what forces the move to probabilistic models in the next section 5:22, 5:52.