Abstract
We review Bayesian active learning methods for graph signal recovery with a focus on discrete signals (e.g., binary). Bayesian models assume a generative model in which the node labels (signals) are "smooth" along the edges in the graph. In other words, two nodes with an edge in between are likely to have the same label and even more so if the edge weight is large. Ultimately, one would like to accurately predict unobserved labels based on observed node labels. In active learning, a learning algorithm is able to sequentially and adaptively select nodes, with the goal of minimizing the total number of labels needed in order to make accurate predictions for all nodes. Because we assume the label generation process is known to us, one can compute the expected error rate after observing some node labels. Thus, a natural strategy is to choose the nodes that would minimize the expected error rate. This way, one can reduce the number of labeled nodes required to achieve the same level of error rate when compared to choosing the nodes uniformly at random. A popular label-generation model for continuous labels is a Gaussian distribution over the labels with a covariance matrix that encodes the graph structure, where the one-step optimal active learning has an efficient closed-form solution. For discrete labels, natural analogs of the Gaussian distribution are used. In this case, there is no known polynomial time algorithm for active learning. For this reason, there has recently been a number of studies on efficient approximations. In this chapter, we review various algorithms that overcome the computational difficulty of active learning for discrete signals on graphs. This includes relaxation and approximation techniques for marginal distributions, which results in different behaviors and characteristics such as adaptivity. We also present empirical results on toy and real-world datasets to compare various algorithms.
Original language | English (US) |
---|---|
Title of host publication | Cooperative and Graph Signal Processing |
Subtitle of host publication | Principles and Applications |
Publisher | Elsevier |
Pages | 283-297 |
Number of pages | 15 |
ISBN (Electronic) | 9780128136782 |
ISBN (Print) | 9780128136775 |
DOIs | |
State | Published - Jun 20 2018 |
Externally published | Yes |
Keywords
- Active learning
- Classification
- Expected error minimization
- Semisupervised learning
- Transduction
ASJC Scopus subject areas
- Medicine (miscellaneous)
- General Computer Science