Zhu X. Semi-Supervised Learning with Graphs

Dissertation. — Carnegie Mellon University, 2005. — 174 p.In traditional machine learning approaches to classification, one uses only a labeled set to train the classifier. Labeled instances however are often difficult, expensive, or time consuming to obtain, as they require the efforts of experienced human annotators. Meanwhile unlabeled data may be relatively easy to collect, but there has been few ways to use them. Semi-supervised learning addresses this problem by using large amount of unlabeled data, together with the labeled data, to build better classifiers. Because semi-supervised learning requires less human effort and gives higher accuracy, it is of great interest both in theory and in practice. We present a series of novel semi-supervised learning approaches arising from a graph representation, where labeled and unlabeled instances are represented as vertices, and edges encode the similarity between instances. They address the following questions: How to use unlabeled data? (label propagation); What is the probabilistic interpretation? (Gaussian fields and harmonic functions); What if we can choose labeled data? (active learning); How to construct good graphs? (hyperparameter learning); How to work with kernel machines like SVM? (graph kernels); How to handle complex data like sequences? (kernel conditional random fields); How to handle scalability and induction? (harmonic mixtures). An extensive literature review is included at the end.Label Propagation
What is a Good Graph?
Gaussian Random Fields
Active Learning
Connection to Gaussian Processes
Graph Hyperparameter Learning
Kernels from the Spectrum of Laplacians
Sequences and Beyond
Harmonic Mixtures
Literature Review
Discussions
A: Update Harmonic Function
B: Matrix Inverse
C: Laplace Approximation for Gaussian Processes
D: Evidence Maximization
E: Mean Field Approximation
F: Comparing Iterative Algorithms