Transductive Classification via Local Learning Regularization

Published 11 March 2007

Mingrui Wu, Bernhard Schölkopf

Citations123

TL;DR

A Local Learning Regularizer (LL-Reg) is formulated which leads to a solution with the property that the label of each data point can be well predicted based on its neighbors and their labels.

Abstract

The idea of local learning, classifying a particular point based on its neighbors, has been successfully applied to supervised learning problems. In this paper, we adapt it for Transductive Classification (TC) problems. Specifically, we formulate a Local Learning Regularizer (LL-Reg) which leads to a solution with the property that the label of each data point can be well predicted based on its neighbors and their labels. For model selection, an efficient way to compute the leave-one-out classification error is provided for the proposed and related algorithms. Experimental results using several benchmark datasets illustrate the effectiveness of the proposed approach.

Keywords

Computer ScienceEngineering

ScienceNonlinear Dimensionality Reduction by Locally Linear Embedding

15,035 Citations2000Sam T. Roweis, Lawrence K. Saul

Locally linear embedding (LLE) is introduced, an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs that learns the global structure of nonlinear manifolds.

The MIT Press eBooksSemi-Supervised Learning

4,308 Citations2006Olivier Chapelle, Schölkopf, B. +1 more

This first comprehensive overview of semi-supervised learning presents state-of-the-art algorithms, a taxonomy of the field, selected applications, benchmark experiments, and perspectives on ongoing and future research.

View PDF

MPG.PuRe (Max Planck Society)Learning with Local and Global Consistency

3,750 Citations2003Dengyong Zhou, Olivier Bousquet +3 more

A principled approach to semi-supervised learning is to design a classifying function which is sufficiently smooth with respect to the intrinsic structure collectively revealed by known labeled and unlabeled points.

View PDF

Semi-supervised learning using Gaussian fields and harmonic functions

3,377 Citations2003Xiaojin Zhu, Zoubin Ghahramani +1 more

Semi-Supervised Classification by Low Density Separation

710 Citations2005Olivier Chapelle, Alexander Zien +1 more

Three semi-supervised algorithms are proposed: deriving graph-based distances that emphazise low density regions between clusters, followed by training a standard SVM, and optimizing the Transductive SVM objective function by gradient descent.

Transductive learning via spectral graph partitioning

649 Citations2003Thorsten Joachims

This work proposes an algorithm that robustly achieves good generalization performance and that can be trained efficiently, and shows a connection to transductive Support Vector Machines, and that an effective Co-Training algorithm arises as a special case.

Neural ComputationLocal Learning Algorithms

544 Citations1992Léon Bottou, Vladimir Vapnik

A single analysis suggests that neither kNN or RBF, nor nonlocal classifiers, achieve the best compromise between locality and capacity.

Lecture notes in computer scienceRegularization and Semi-supervised Learning on Large Graphs

543 Citations2004Mikhail Belkin, Irina Matveeva +1 more

This work considers the problem of labeling a partially labeled graph, which may arise in a number of situations from survey sampling to information retrieval to pattern recognition in manifold settings.

On Manifold Regularization.

323 Citations2005Misha Belkin, Partha Niyogi +1 more

A semisupervised framework that incorporates labeled and unlabeled data in a generalpurpose learner and gives rise to a regularized form of spectral clustering with an out-of-sample extension is proposed.

Label propagation through linear neighborhoods

261 Citations2006Fei Wang, Changshui Zhang

A novel graph-based semi supervised learning approach is proposed based on a linear neighborhood model, which assumes that each data point can be linearly reconstructed from its neighborhood, and can propagate the labels from the labeled points to the whole data set using these linear neighborhoods with sufficient smoothness.