Sparse Forward-Backward Using Minimum Divergence Beams for Fast Training Of Conditional Random Fields

By C. Pal, Charles Sutton, Andrew McCallum. 2006

68 citations recorded by the source corpus.

Hidden Markov models and linear-chain conditional random fields (CRFs) are applicable to many tasks in spoken language processing. In large state spaces, however, training can be expensive, because it often requires many iterations of forward-backward. Beam search is a standard heuristic for controlling complexity during Viterbi decoding, but during forward-backward, standard beam heuristics can be dangerous, as they can make training unstable. We introduce sparse forward-backward, a variational perspective on beam methods that uses an approximating mixture of Kronecker delta functions. This motivates a novel minimum-divergence beam criterion based on minimizing KL divergence between the respective marginal distributions. Our beam selection approach is not only more efficient for Viterbi decoding, but also more stable within sparse forward-backward training. For a standard text-to-speech problem, we reduce CRF training time fourfold - from over a day to six hours - with no loss in accuracy

Subfields: Artificial Intelligence, Natural Language Processing, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Natural Language Processing

In Optimization & Training

Citations in the corpus

The Curious Case of Neural Text Degeneration (2019, methodology): “Work on neural dialog systems have proposed methods for diverse beam search, using a task-speciﬁc diversity scoring function or constraining beam hypotheses to be sufﬁciently different (Li et al., 2016a; Vijayakumar et al., 2018; Kulikov et al., 2019; Pal et al., 2006).”
Conditional random fields for activity recognition (2007, background): “loopy belief propagation) [81].”
Efficient Inference in Large Conditional Random Fields (2006, methodology): “Other approximate inference techniques have been used to reduce CRF training time, such as beam-search during sum-product or max-product inference [16], or using the voted perceptron algorithm [17].”
An Introduction to Conditional Random Fields (2010, background): “[102] for an example of the difficulties that can arise when trying to naively incorporate beam search within CRF training.”
Practical Very Large Scale CRFs (2010, methodology): “Our results compare favorably with those reported in (Pal et al., 2006), where the accuracy attains 91.7% using 19075 examples for training and 934 for testing, and with those in (Jeong et al., 2009) (88.4% accuracy with 18,000 (2,000) training (test) instances).”