Denoising the Future: Top-p Distributions for Moving Through Time
This addresses a bottleneck in inference for dynamic models, offering significant speed improvements with bounded error, though it is incremental as it builds on existing methods.
The paper tackles the computational inefficiency in dynamic probabilistic models like Hidden Markov Models by proposing to use only the top-p states for inference, resulting in speedups of at least an order of magnitude while keeping error below 0.09 in total variation distance.
Inference in dynamic probabilistic models is a complex task involving expensive operations. In particular, for Hidden Markov Models, the whole state space has to be enumerated for advancing in time. Even states with negligible probabilities are considered, resulting in computational inefficiency and increased noise due to the propagation of unlikely probability mass. We propose to denoise the future and speed up inference by using only the top-p states, i.e., the most probable states with accumulated probability p. We show that the error introduced by using only the top-p states is bound by p and the so-called minimal mixing rate of the underlying model. Moreover, in our empirical evaluation, we show that we can expect speedups of at least an order of magnitude, while the error in terms of total variation distance is below 0.09.