Graph-Based Semi-Supervised Learning

Description

While labeled data is expensive to prepare, ever increasing amounts of unlabeled data is becoming widely available. In order to adapt to this phenomenon, several semi-supervised learning (SSL) algorithms, which learn from labeled as well as unlabeled data, have been developed. In a separate line of work, researchers have started to realize that graphs provide a natural way to represent data in a variety of domains. Graph-based SSL algorithms, which bring together these two lines of work, have been shown to outperform the state-of-the-art in many applications in speech processing, computer vision, natural language processing, and other areas of Artificial Intelligence. Recognizing this promising and emerging area of research, this synthesis lecture focuses on graph-based SSL algorithms (e.g., label propagation methods). Our hope is that after reading this book, the reader will walk away with the following: (1) an in-depth knowledge of the current state-of-the-art in graph-based SSL algorithms, and the ability to implement them; (2) the ability to decide on the suitability of graph-based SSL methods for a problem; and (3) familiarity with different applications where graph-based SSL methods have been successfully applied. Table of Contents: Introduction / Graph Construction / Learning and Inference / Scalability / Applications / Future Work / Bibliography / Authors' Biographies / Index Introduction Unsupervised Learning Supervised Learning Semi-Supervised learning (SSL) Graph-based Semi-Supervised Learning Inductive vs. Transductive SSL Book Organization Graph Construction Problem Statement Task-Independent Graph Construction k-Nearest Neighbor (k-NN) and -Neighborhood Methods Graph Construction using b-Matching Graph Construction using Local Reconstruction Task-Dependent Graph Construction Inference-Driven Metric Learning (IDML) Graph Kernels by Spectral Transform Conclusion Learning and Inference Seed Supervision Transductive Methods Graph Cut Gaussian Random Fields (GRF) Local and Global Consistency (LGC) Adsorption Modified Adsorption (MAD) Quadratic Criteria (QC) Transduction with Confidence (TACO) Information Regularization Measure Propagation Inductive Methods Manifold Regularization Results on Benchmark SSL Data Sets Conclusions Scalability Large-Scale Graph Construction Approximate Nearest Neighbor Other Methods Large-Scale Inference Graph Partitioning Inference Scaling to Large Number of Labels Conclusions Applications Text Classification Phone Classification Part-of-Speech Tagging Class-Instance Acquisition Knowledge Base Alignment Conclusion Future Work Graph Construction Learning & Inference Scalability Notations Solving Modified Adsorption (MAD) Objective Alternating Minimization Software Junto Label Propagation Toolkit Bibliography Authors' Biographies Index Blank Page