Compressed Inference for Probabilistic Sequential Models
This work addresses a specific bottleneck in sequential modeling for applications where only functional outputs are needed, offering an incremental improvement over existing methods.
The paper tackles the problem of directly inferring functions of state sequences in probabilistic sequential models like HMMs and CRFs, rather than estimating full state sequences, and presents a novel polynomial-time algorithm that outperforms conventional inference techniques in applications such as robot tracking and character recognition.
Hidden Markov models (HMMs) and conditional random fields (CRFs) are two popular techniques for modeling sequential data. Inference algorithms designed over CRFs and HMMs allow estimation of the state sequence given the observations. In several applications, estimation of the state sequence is not the end goal; instead the goal is to compute some function of it. In such scenarios, estimating the state sequence by conventional inference techniques, followed by computing the functional mapping from the estimate is not necessarily optimal. A more formal approach is to directly infer the final outcome from the observations. In particular, we consider the specific instantiation of the problem where the goal is to find the state trajectories without exact transition points and derive a novel polynomial time inference algorithm that outperforms vanilla inference techniques. We show that this particular problem arises commonly in many disparate applications and present experiments on three of them: (1) Toy robot tracking; (2) Single stroke character recognition; (3) Handwritten word recognition.