Non-negative Sparse Graph Based Semi-Supervised Learning

Semi-Supervised learning (SSL) is one of the most important research areas in machine learning. To avoid using much manual work, semi-supervised learning tries to improve the learners’ performance by using a few labeled data and an amount of unlabeled data simultaneously. Among existing semi-supervised learning methods, graph-based semi-supervised learning algorithms have received much attentions because of its intuition, interpretability and performance. These algorithms try to construct a graph which can represent the relationship between data samples, followed by traditional label propagation algorithms to label the unlabeled data.This dissertation proposes two algorithms to deal with single-view and multi-view cases respectively based on nonnegative sparse representation (NSR). The main work and contribution of this paper can be summarized as follows:(1) In the single-view case, we propose a graph construction algorithm (SBM-graph) based on non-negative sparse representation via reformulating the original non-negative sparse representation optimization problem The experimental results on three real world image datasets demonstrate that the proposed algorithm can better capture the latent data structure than competing algorithms.(2) In the multi-view case, we propose the multi-view non-negative sparse graph construction algorithm (MVNSR-graph). The main idea of the proposed algorithm is to formulate a joint multi-view non-negative sparse representation problem to integrate the information across multiple views as much as possible. The experimental results on an artificial dataset and three real world multi-view image datasets show that the proposed algorithm can better integrate the information of multiple views.