Hidden Markov Models with Confidence

Giovanni Cherubin, Ilia Nouretdinov

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the problem of training a Hidden Markov Model
(HMM) from fully observable data and predicting the hidden states of an
observed sequence. Our attention is focused to applications that require
a list of potential sequences as a prediction. We propose a novel method
based on Conformal Prediction (CP) that, for an arbitrary confidence
level 1 − ε, produces a list of candidate sequences that contains the correct
sequence of hidden states with probability at least 1−ε. We present
experimental results that confirm this holds in practice. We compare our
method with the standard approach (i.e.: the use of Maximum Likelihood
and the List–Viterbi algorithm), which suffers from violations to
the assumed distribution. We discuss advantages and limitations of our
method, and suggest future directions.
Original languageEnglish
Title of host publicationConformal and Probabilistic Prediction with Applications
Subtitle of host publication5th International Symposium, COPA 2016 Madrid, Spain, April 20–22, 2016 Proceedings
Number of pages17
ISBN (Electronic)978-3-319-33395-3
ISBN (Print)978-3-319-33394-6
Publication statusPublished - 17 Apr 2016

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743

Cite this