This paper presents a novel L1-norm semisupervised learning algorithm for robust image analysis by giving new L1-norm formulation of Laplacian regularization which is the key step of graph-based semi-supervised learning. Since our L1-norm Laplacian regularization is defined directly over the eigenvectors of the normalized Laplacian matrix, we successfully formulate semi-supervised learning as an L1-norm linear reconstruction problem which can be effectively solved with sparse coding. By working with only a small subset of eigenvectors, we further develop a fast sparse coding algorithm for our L1-norm semi-supervised learning. Due to the sparsity induced by sparse coding, the proposed algorithm can deal with the noise in the data to some extent and thus has important applications to robust image analysis, such as noise-robust image classification and noise reduction for visual and textual bag-ofwords (BOW) models. In particular, this paper is the first attempt to obtain robust image representation by sparse co-refinement of visual and textual BOW models. The experimental results have shown the promising performance of the proposed algorithm.

INTRODUCTION

Semi-supervised learning, i.e., learning from both labeled and unlabeled data, has been widely applied to many challenging image analysis tasks [1]–[6] such as image representation, image classification, and image annotation. In different image analysis tasks, the manual labeling of training data is often tedious, subjective as well as expensive, while the access to unlabeled data is much easier. Through exploiting the large number of unlabeled data with reasonable assumptions, semisupervised learning [7]–[11] can reduce the need for expensive labeled data and thus achieve promising results especially for community-contributed image collections (e.g. Flickr). Among various semi-supervised learning methods, one in- fluential work is graph-based semi-supervised learning [8], [9] which models the entire dataset as a graph. The basic idea behind this semi-supervised learning is label propagation on the graph with the cluster consistency [9] (i.e. two data points on the same geometric structure are likely to have the same class label). Since the graph is at the heart of graph-based semi-supervised learning, graph construction has been extensively studied [12]–[15] in the past years. However, these graph construction methods are not developed directly for noise reduction, and the corresponding semi-supervised learning may suffer from significant performance degradation due to the inaccurate labeling of data points commonly encountered in different image analysis tasks. For example, the annotations of images may be contributed by the community (see Flickr) and we can only obtain noisy tags.