  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.
