Title: Best-Choice Edge Grafting for Efficient Structure Learning of Markov Random Fields,
Abstract: Incremental methods for structure learning of pairwise Markov random fields
(MRFs), such as grafting, improve scalability by avoiding inference over the
entire feature space in each optimization step. Instead, inference is performed
over an incrementally grown active set of features. In this paper, we address
key computational bottlenecks that current incremental techniques still suffer
by introducing best-choice edge grafting, an incremental, structured method
that activates edges as groups of features in a streaming setting. The method
uses a reservoir of edges that satisfy an activation condition, approximating
the search for the optimal edge to activate. It also reorganizes the search
space using search-history and structure heuristics. Experiments show a
significant speedup for structure learning and a controllable trade-off between
the speed and quality of learning.