Simultaneous Learning of Affinity Matrix and Laplacian Regularized Least Squares for Semi-Supervised Classification

Graph based Semi-Supervised Learning (G-SSL) methods usually include the stages of the construction of affinity matrix and the mechanism of inferring unknown labels. However, solving each of the stages individually does not fully exploit the potential relationship between the affinity matrix and the labels of samples. In this paper, we formulate the global self-expressiveness induced affinity and Laplacian Regularized Least Squares (LapRLS) into a single optimization model, called as Self-Taught LapRLS (ST-LapRLS). In the unified model, both the given labels and the estimated labels are used to build a better affinity matrix and to facilitate the LapRLS classifer. The proposed ST-LapRLS classifier is explicit, and can be easily extended to deal with out-of-sample problem. We propose an efficient algorithm which combines the alternating direction method of multiplier and LapRLS to solve the unified optimization problem. Experiments on several Benchmark datasets show the superior performance of our method in classification applications.