A Continuation Method for Semi-Supervised SVMs

by Olivier Chapelle, Mingmin Chi, Alexander Zien

Fantastic thing, the scond author is now a teacher in our department, a pretty young lady :-) Yes, last time I saw her and talked about semi-supervised learning. So there's nothing strange that she knew little about Belkins' work in this area. Their starting points differ.

The basic idea of the proposed S³VM algorithm originates from Joachims seminal work on transductive SVM, in which a brute method is adopted to search for a separating plane over low density area. Now, Chapelle find an alternative by adding a regularizer to the original objective function. This regularizer is punishing all unlabelled samples if they are near the separating plane. It simply uses the loss function of the original objective function. Now the objective function looks like following

quadratic form of w + punishment of misclassification + punishment of near unlabelled samples

But now the optimization problem will tend to put unlabelled samples in one class. So a constraint is added to force the separating plane yield a balanced cut,

b = sum_{over labelled indices} y_i / n

Still the optimization is difficult due to its non-convexity. Hence a global optimization technique is applied, whose name is continuation.

In continuation, a series of functions(usu. adjusted by a parameter, e.g. the pdf of normal distr with the variation parameter sigma²) are convolved with the objective function respectively. The first one of the resulted sequence is the easist to optimize and yield an initial value for the next function. The last one of the sequence is the original objective function. As is seen, convolving with a Gaussian will mollify the multimodal objective function.

There are several related work on this topic:
Semi-supervised classification by low density separation, by Chapelle and Zien
Transductive inference for text classification using support vector machines, by Joachims, ICML1999
Transductive learning via spectral graph partitioning, by Joachims, ICML 2003
And about continuation:
The effective energy transformation scheme as a special continuation approach to global optimization with application to molecular conformation.