  Structured prediction is ubiquitous in applications of machine learning such
as knowledge extraction and natural language processing. Structure often can be
formulated in terms of logical constraints. We consider the question of how to
perform efficient active learning in the presence of logical constraints among
variables inferred by different classifiers. We propose several methods and
provide theoretical results that demonstrate the inappropriateness of employing
uncertainty guided sampling, a commonly used active learning method.
Furthermore, experiments on ten different datasets demonstrate that the methods
significantly outperform alternatives in practice. The results are of practical
significance in situations where labeled data is scarce.
