Safe Semi-Supervised Learning with Sparse Graphs

There has been substantial interest from both computer science and statistics in developing methods for graph-based semi-supervised learning. The attraction to the area involves several challenging applications brought forth from academia and industry where little data are available with training responses while lots of data are available overall. Ample evidence has demonstrated the value of several of these methods on real data applications, but it should be kept in mind that they heavily rely on some smoothness assumptions. The general frame- work for graph-based semi-supervised learning is to optimize a smooth function over the nodes of the proximity graph constructed from the feature data which is extremely time consuming as the conventional methods for graph construction in general create a dense graph. Lately the interest has shifted to developing faster and more efficient graph-based techniques on larger data, but it comes with a cost of reduced prediction accuracies and small areas of application. The focus of this research is to generate a graph-based semi-supervised model that attains fast convergence without losing its performance and with a larger applicability. The key feature of the semi-supervised model is that it does not fully rely on the smoothness assumptions and performs adequately on real data. Another model is proposed for the case with availability of multiple views. Empirical analysis with real and simulated data showed the competitive performance of the methods against other machine learning algorithms