Constrained Kronecker Deltas for Fast Approximate Inference and Estimation
We are interested in constructing fast, principled algorithms for scaling up decoding and parameter estimation in probability models such as Hidden Markov Models (HMMs) and linear-chain Conditional Random Fields (CRFs) with large state spaces. In this paper we present a principled extension of beam search to beam inference and learning. We present a new approach for approximate inference based on approximating single variable potentials with a constrained, lower complexity, adaptively sized sum or mixture of Kronecker delta functions. We present inference and optimization results on synthetic and real data for HMMs and CRFs. In a number of cases, we demonstrate potential speed increases of close to an order of magnitude with little or no degradation in accuracy over exact methods for decoding and parameter estimation. We also demonstrate speed, accuracy and robustness improvements over traditional, n-best and threshold based beam methods. While we focus experiments on HMMs and CRFs, these methods should be widely applicable for inference in many factorized representations of probability distributions with large state spaces.