NEAR-OPTIMALITY AND ROBUSTNESS OF GREEDY ALGORITHMS FOR BAYESIAN POOL-BASED ACTIVE LEARNING

Abstract

We study pool-based active learning in the Bayesian setting. To facilitate the analyses of active learning algorithms in this setting, we develop two powerful theoretical tools: (1) an equivalence between probabilistic hypothesis spaces and deterministic hypothesis spaces, and (2) a near-optimality guarantee for greedy algorithms when maximizing pointwise monotone submodular functions. Using these tools, we analyze and prove novel theoretical properties of two commonly used greedy algorithms for active learning: the maximum entropy and the least confidence algorithms. Then we propose a new greedy criterion called the maximum Gibbs error criterion, which can be proven to have near-optimality guarantees in the average case. The criterion can be approximated more easily even for complex structured models like the Bayesian conditional random fields, and it can be shown to perform well in practice. We also generalize the maximum Gibbs error criterion to include general loss functions into the criteria. We prove near-optimality guarantees for these new criteria and show that they also perform well in our experiments. Finally, we analyze the robustness of active learning algorithms against prior misspecification in both the average case and the worst case. We propose the use of mixture prior for more robust active learning and show in our experiments that it can achieve good performance even when the correct prior is unknown.