Sparse semi-supervised learning on low-rank kernel

作者：Zhang Kai^*; Wang Qiaojun; Lan Liang; Sun Yu; Marsic Ivan

来源：Neurocomputing, 2014, 129: 265-272.

DOI：10.1016/j.neucom.2013.09.033

• Semi-supervised learning
• Regularized least squares
• Manifold regularization
• Graph Laplacian
• Sparse regression
• Low-rank approximation

Advances of modern science and engineering lead to unprecedented amount of data for information processing. Of particular interest is the semi-supervised learning, where very few training samples are available among large volumes of unlabeled data. Graph-based algorithms using Laplacian regularization have achieved state-of-the-art performance, but can induce huge memory and computational costs. In this paper, we introduce L-1-norm penalization on the low-rank factorized kernel for efficient, globally optimal model selection in graph-based semi-supervised learning. An important novelty is that our formulation can be transformed to a standard LASSO regression. On one hand, this makes it possible to employ advanced sparse solvers to handle large scale problems; on the other hand, a globally optimal subset of basis can be chosen adaptively given desired strength of penalizing model complexity, in contrast to some current endeavors that pre-determine the basis without coupling it with the learning task. Our algorithm performs competitively with state-of-the-art algorithms on a variety of benchmark data sets. In particular, it is orders of magnitude faster than exact algorithms and achieves a good trade-off between accuracy and scalability.

• 出版日期2014-4-10