Fast Inference and Learning with Sparse Belief Propagation
Even in trees, exact probabilistic inference can be expensi v when the cardinality of the variables is large. This is especially tr oublesome for learning, because many standard estimation techniques, su ch a EM and conditional maximum likelihood, require calling an infere nce algorithm many times. In max-product inference, a standard heuristic for ontrolling this complexity in linear chains is beam search, that is , to ignore variable configurations during inference once their estima ted probability becomes sufficiently low. Although quite effective for m ax-product, during sum-product inference beam search discards probabi lity mass in a way that makes learning unstable. In this paper, we introdu ce a variational perspective on beam search that uses a approximating mixture of Kronecker delta functions. This motivates a novel variatio nal approximation for arbitrary tree-structured models, which maintain s a adaptivelysized sparse belief state—thus extending beam search from m ax-product to sum-product, and from linear chains to arbitrary trees. W e report efficiency improvements for max-product inference over other b eam search techniques. Also, unlike heuristic methods for discarding probability mass, our method can be used effectively for conditional max i um likelihood training. On both synthetic and real-world problems , we report four-fold increases in learning speed with no loss in accura cy.