Efficient Non-Parametric Function Induction in Semi-Supervised Learning

Abstract

Il y a eu un regain d'intérêt récemment pour l'apprentissage semi-supervisé, à cause du grand nombre de bases de données comportant de très nombreux exemples non étiquetés et seulement quelques exemples étiquetés. Cet article poursuit le travail fait sur les algorithmes non paramétriques qui fournissent une étiquette continue estimée pour les exemples non-étiquetés. Il les étend à des algorithmes d'induction fonctionnelle qui correspondent à la minimisation d'un critère de régularisation appliqué à un exemple hors-échantillon, et qui ont la forme d'un régresseur à fenêtre de Parzen. L'avantage de cette extension est qu'elle permet de prédire l'étiquette d'un nouvel exemple sans avoir à résoudre de nouveau un système de dimension 'n' (le nombre d'exemples d'entraînement total), qui peut être de l'ordre de O(n^3). Les expériences montrent que l'extension fonctionne bien, en ce sens que l'étiquette prédite est proche de celle qui aurait été obtenue si l'exemple de test avait fait partie de l'ensemble non étiqueté. Cette procédure d'induction fonctionnelle relativement efficace peut également être utilisée, lorsque 'n' est grand, pour estimer la solution en l'écrivant seulement en fonction d'une expansion à noyau avec 'm' << 'n', et en la réduisant à un système linéaire avec 'm' équations et 'm' inconnues.

There has been an increase of interest for semi-supervised learning recently, because of the many datasets with large amounts of unlabeled examples and only a few labeled ones. This paper follows up on proposed non-parametric algorithms which provide an estimated continuous label for the given unlabeled examples. It extends them to function induction algorithms that correspond to the minimization of a regularization criterion applied to an out-of-sample example, and happens to have the form of a Parzen windows regressor. The advantage of the extension is that it allows predicting the label for a new example without having to solve again a linear system of dimension 'n' (the number of unlabeled and labeled training examples), which can cost O(n^3). Experiments show that the extension works well, in the sense of predicting a label close to the one that would have been obtained if the test example had been included in the unlabeled set. This relatively efficient function induction procedure can also be used when 'n' is large to approximate the solution by writing it only in terms of a kernel expansion with 'm' << 'n' terms, and reducing the linear system to 'm' equations in 'm' unknowns.