Semi-Supervised Classification Using Linear Neighborhood Propagation

In this paper, we address the general problem of learning from both labeled and unlabeled data. Based on the reasonable assumption that the label of each data can be linearly reconstructed from its neighbors’ labels, we develop a novel approach, called Linear Neighborhood Propagation (LNP), to learn the linear construction weights and predict the labels of the unlabeled data from the labeled data. The main procedure is composed of two steps: (1) it computes the local neighborhood geometry according to the image information by solving a constrained least squares problem, (2) the obtained geometry will be used to predict the labels of unlabeled data by solving a linearly constrained quadratic optimization problem. LNP has at least three characteristics. Firstly, it is much practical in that only one free parameter, the size of neighborhood, requires user-tuning. Secondly it can be easily extended to out-of-sample examples. Finally the labels achieved from LNP can be sufficiently smooth with respect to the intrinsic structure collectively revealed by the labeled and unlabeled points. Many promising experimental results, such as object recognition, data ranking and interactive image segmentation, demonstrate the effectiveness and efficiency of the proposed approach.