Bridging Viterbi and Posterior Decoding: A Generalized Risk Approach to Hidden Path Inference Based on Hidden Markov Models

摘要

Motivated by the unceasing interest in hidden Markov models(HMMs), this paper re-examines hidden path inference in thesemodels, using primarily a risk-based framework. While the mostcommon maximum a posteriori (MAP), or Viterbi, pathestimator and the minimum error, or PosteriorDecoder (PD) have long been around, other path estimators,or decoders, have been either only hinted at or applied morerecently and in dedicated applications generally unfamiliar tothe statistical learning community. Over a decade ago, however,a family of algorithmically defined decoders aiming to hybridizethe two standard ones was proposed elsewhere. The present papergives a careful analysis of this hybridization approach,identifies several problems and issues with it and otherpreviously proposed approaches, and proposes practicalresolutions of those. Furthermore, simple modifications of theclassical criteria for hidden path recognition are shown to leadto a new class of decoders. Dynamic programming algorithms tocompute these decoders in the usual forward-backward manner arepresented. A particularly interesting subclass of suchestimators can be also viewed as hybrids of the MAP and PDestimators. Similar to previously proposed MAP-PD hybrids, thenew class is parameterized by a small number of tunableparameters. Unlike their algorithmic predecessors, the new risk-based decoders are more clearly interpretable, and, mostimportantly, work a€?out-of-the boxa€? in practice, which isdemonstrated on some real bioinformatics tasks and data. Somefurther generalizations and applications are discussed in theconclusion. color="gray">