Mathematical Foundations of Graph-Based Bayesian Semi-Supervised Learning
In recent decades, science and engineering have been revolutionized by a
momentous growth in the amount of available data. However, despite the
unprecedented ease with which data are now collected and stored, labeling data
by supplementing each feature with an informative tag remains to be
challenging. Illustrative tasks where the labeling process requires expert
knowledge or is tedious and time-consuming include labeling X-rays with a
diagnosis, protein sequences with a protein type, texts by their topic, tweets
by their sentiment, or videos by their genre. In these and numerous other
examples, only a few features may be manually labeled due to cost and time
constraints. How can we best propagate label information from a small number of
expensive labeled features to a vast number of unlabeled ones? This is the
question addressed by semi-supervised learning (SSL).
  This article overviews recent foundational developments on graph-based
Bayesian SSL, a probabilistic framework for label propagation using
similarities between features. SSL is an active research area and a thorough
review of the extant literature is beyond the scope of this article. Our focus
will be on topics drawn from our own research that illustrate the wide range of
mathematical tools and ideas that underlie the rigorous study of the
statistical accuracy and computational efficiency of graph-based Bayesian SSL.