Semi-supervised learning

The lecture starts by restating supervised learning in the slides' notation. A data source produces examples from a distribution . An expert (or oracle) knows the true labeling rule and labels each example. The learner sees the labeled sample and must output a rule that is rarely wrong on new data from :

The professor names two core questions for any supervised method (slide 4): computation (how do we optimize? e.g. logistic regression, SVM) and generalization (why should a rule that fits the training data work on test data? e.g. VC dimension, margin bounds).

The motivation for SSL (slides 5–6) is economic. Web pages, images and protein sequences arrive by the billion, but a human expert can label only a tiny fraction. We want methods that use all that raw data while needing as little expert time as possible. Semi-supervised learning adds a second, much larger sample with no labels:

The goal does not change: small error over . What changes is only how many of the training examples carry a label (05:20). The two samples come from the same distribution; that's what lets the unlabeled points say something about the labeled problem.

Slide 11 admits the puzzle: an unlabeled point is "missing the most important info." How can it help? The answer is the lecture's key insight:

Unlabeled data tells you about : where points are dense, where there are gaps, which points are near each other. That is information about the inputs only. It turns into information about labels only through a belief that connects the two. The figure shows why the belief is unavoidable: the same two labeled points, with two different unlabeled samples, lead to two different answers.

Each method in the lecture encodes a different belief. Keep this table in mind; the rest of the guide fills it in.

The transductive SVM (TSVM, Joachims 1999) starts from week 5's SVM. With only a few labeled points, the max-margin line is decided by those few points and can slice straight through a cloud of unlabeled data. The TSVM's belief (slide 13): we want a linear separator, and a good one should have a large margin with respect to all the data, labeled and unlabeled. A line with a large margin over all the points can't pass through a dense region, so it lands in a gap ("low-density separation").

To use the margin idea we need labels for the unlabeled points, so the TSVM makes them optimization variables. The professor calls them "fake labels" (10:54); the usual name is pseudo-labels, written . The hard-margin version (slide 14):

Read the constraints as two SVMs glued together. The labeled points must be on their correct side with margin. The unlabeled points must be on the side of whatever label we give them, with margin. So the optimizer chooses a labeling and a line together, preferring a labeling that a wide-margin line can separate.

Why it's hard

Week 5's SVM is a convex quadratic program with one global optimum. The TSVM is not (slide 16, 13:08). The pseudo-labels are discrete, and they multiply in the constraint . The professor calls this product "bilinear": linear in for fixed labels and linear in the labels for fixed , but not jointly convex. Fix the labels and what's left is an ordinary SVM, convex and easy. But there are possible labelings, and the problem is NP-hard in general. Slide 16 sums it up: "Convex only after you guessed the labels… too many possible guesses."

Joachims' heuristic (slide 17) avoids trying every labeling:

1. Fit on the labeled points. Train an ordinary SVM on alone. This is convex, so it has one answer.
2. Guess the pseudo-labels. Label each unlabeled point by which side of that line it falls on.
3. Flip and re-fit. Try flipping the pseudo-labels of unlabeled points. If the re-fitted SVM has a smaller objective (wider margin, fewer violations), keep the flip.
4. Repeat until no flip helps. The result is a locally optimal solution, not guaranteed global (16:46). The professor's verdict: in practice it's good enough for many applications.

Does it help? (slide 18)

Joachims' experiment classifies Reuters news articles, with the 3,299 test articles serving as the unlabeled data. The x-axis is the number of labeled training examples (17 up to 9,603). The y-axis is the average precision/recall breakeven point, the value where precision equals recall (higher is better). With 17 labeled examples the TSVM scores about 60 against about 48 for the plain SVM and 36 for naive Bayes (week 7). As the labeled set grows, the SVM catches up and the two curves merge above 80 near 1,000 examples, both well above naive Bayes. That's the general pattern: unlabeled data matters most when labels are scarce.

Co-training (Blum & Mitchell 1998) uses a different belief: agreement between parts. Each example splits into two views, . The running example (slide 21) classifies web pages as "faculty member homepage or not":

• = text on the page itself (e.g. the words "I am teaching" are a good sign);
• = links pointing to the page (e.g. anchor text "my advisor" on a link to the page is a good sign).

The assumptions (slide 21): each view is sufficient on its own, and the views are consistent. Formally, there exist rules on view 1 and on view 2 with

The algorithm

Slide 24 gives the loop:

1. Two learners. Pick a learning algorithm for view 1 and for view 2.
2. Initial rules. Train on the labeled 's and on the labeled 's.
3. Look for disagreement in confidence. Scan the unlabeled examples for ones where one is confident and the other is not.
4. Teach the other view. The confident labels that example, and it's added to the training set of the other algorithm, ( just means "1 ↔ 2"). Retrain and repeat.

Examples where neither rule is confident are left alone (24:38). Examples where both are confident already agree, so there's nothing to teach. The professor's summary (21:52–25:26): propagate strong-confidence labels from one view to the other, retrain, and iterate.

The original results (slide 25)

Blum & Mitchell had 12 labeled web pages and 1,000 unlabeled ones. Test error rates (%):

The last row is the trivial baseline: 22% of pages are faculty pages, so predicting "no" for everything is wrong 22% of the time. Co-training cuts the combined error from 11.1% to 5.0%, a reduction of about 55%. The plot on the slide shows the error of each view's classifier dropping over about 40 co-training iterations.

Other applications (slide 35, 30:56): finding cars in traffic-camera images, where the two views are two different kinds of image preprocessing (Levin, Viola & Freund 2003), and named-entity extraction, where in "I arrived in London yesterday" the word itself and the surrounding context ("arrived in ___") are the two views (Collins & Singer 1999). The original Blum & Mitchell classifiers were naive Bayes models, one per view (week 7).

For co-training to work you need assumptions about two things (slide 28): the data distribution and the learning algorithms on each side. The slides give two sets of conditions.

Independence given the label is the same kind of assumption as naive Bayes (week 7), but applied to two blocks of features instead of every single feature. Slide 29 states the main result. Call weakly useful if it says "positive" more often on true positives than on true negatives, by some gap :

Theorem (Blum & Mitchell): if the concept class is learnable from randomly noisy labels, then a weakly useful plus unlabeled data gives a strong learner, under independence given the label. The idea: by independence, 's labels look to view 2 like the true labels with random noise added, and the view-2 learner tolerates that noise.

Why agreement is so informative (slide 30, Balcan & Blum 2005). Under independence given the label, any pair that agrees on almost all the unlabeled data must be close to one of only four pairs: , , or . Wrong rules that are wrong in correlated ways would agree, but independence means each view's mistakes look random from the other side, so they produce lots of disagreement (slide 31). Unlabeled data narrows the search down to four candidates, and a handful of labels picks the right one.

Expansion (slide 27) explains what goes wrong without independence. Suppose the rules learned so far are confident on a set in view 1 and in view 2. Co-training makes progress only if the examples in one confident set reach outside the other. If the two views are perfectly correlated (all positives on a thin diagonal in the plane), then and cover exactly the same examples and neither view ever learns anything new: a "non-expanding (non-helpful)" distribution. If the positives fill a thick band, confident regions keep growing into each other: an "expanding" distribution. The intervals example on slide 26 is this growth: the view-1 interval is widened to by points that view 2 confidently includes, and vice versa.

Co-training as one optimization problem

Slides 32–33 (29:38) rewrite multi-view SSL as a single objective: each view's classifier should fit the labeled data, and the two should agree on the unlabeled data.

The first term is ordinary supervised loss for both classifiers. The second is a regularizer (week 11's idea) that uses only unlabeled data: it penalizes pairs of classifiers that disagree.

The third belief is similarity (slide 37): we have a pairwise similarity function, and very similar examples probably have the same label. With lots of labeled data, that belief just suggests nearest neighbors (week 4). With few labels, the unlabeled points become stepping stones. Slide 37's handwritten digits make the point. A loopy "2" and a plain "2" don't look alike. But a sequence of unlabeled 2's morphs gradually from one to the other, each very similar to the next. The two are "indirectly similar."

The recipe (slides 38 and 40):

1. Build a graph . One node per example (labeled and unlabeled), with an edge between very similar examples, optionally weighted by similarity.
2. Expect some bad edges. may glue together examples of different classes (slide 40's graph links a 2 to a 3, and a 3 to a 4).
3. Partition the graph. Run a graph-partitioning algorithm to cut into pieces, each holding labeled points of only one class, and label every node by its piece. The slide lists minimum/multiway cut, minimum "soft cut," and spectral partitioning. The professor notes these graph algorithms weren't covered earlier in the course (35:32); Section 8 explains the first two from the extra slides.

How to build the graph (slide 45, "what works well empirically"): compute distances between all pairs, connect each point to its k nearest neighbors with k small but still large enough to connect the graph, optionally put weights on just those edges, and tune. This is week 4's k-NN, used to build a graph instead of to vote.

The lecture names min-cut and soft cut but skips the "additional material" slides 42–44 (shown for a second at 35:52). They are short and they turn the graph idea into something you can compute, so here they are. Write for the weight of the edge between and (0 if there's no edge).

Minimum cut (Blum & Chawla 2001, slide 43)

Choose hard labels for the unlabeled nodes to minimize the total weight of edges whose two ends get different labels (the "bad" edges):

With two classes this is solved exactly with a max-flow/min-cut algorithm: add a super-source joined by infinite-weight edges to every + labeled node, a super-sink joined by infinite-weight edges to every − labeled node, and find the minimum-weight – cut. The infinite edges make sure no labeled node is ever cut away from its own class.

Minimum soft cut, a.k.a. label propagation (Zhu, Ghahramani & Lafferty 2003, slide 44)

Relax the labels to real numbers (for more classes, to probability vectors; slide 44's digits use 10-dimensional one-hot vectors for the labeled nodes) and minimize a squared penalty:

One equation per unlabeled node, all linear: that's slide 44's "can be done efficiently by solving a set of linear equations." In matrix form, with (the degree matrix minus the weight matrix, called the graph Laplacian), . You can also just apply the averaging rule over and over; the values converge to the same answer. That repeated averaging is what's usually called label propagation.

A practical rule that follows from all three: always compare against the plain supervised model trained on alone, on held-out labeled data (week 2's validation). If the unlabeled data doesn't satisfy the method's belief, SSL can make things worse, and the comparison is the only way to find out.