Un calcul de Viterbi pour un Modèle de Markov Caché Contraint

Matthieu Petit, Henning Christiansen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

A hidden Markov model (HMM) is a statistical model in which the system being modeled is assumed to be a Markov process with hidden states. This model has been widely used in speech recognition and biological sequence analysis. Viterbi algorithm has been proposed to compute the most probable value of these hidden states in regards to an observed data sequence. Constrained HMM extends this framework by adding some constraints on a HMM process run.

In this paper, we propose to introduce constrained HMMs into Constraint Programming. We propose new version of the Viterbi algorithm for this new framework. Several constraint techniques are used to reduce the search of the most probable value of hidden states of a constrained HMM. An implementation based on PRISM, a logic programming language for statistical modeling, is presented.

Original languageFrench
Title of host publicationProceedings des 5ème Journée Francophone de Programmation par Contraintes
Publication date2009
Publication statusPublished - 2009
Event5ème Journée Francophone de Programmation par Contraintes - Orléans, France
Duration: 3 Jun 20095 Jun 2009

Conference

Conference5ème Journée Francophone de Programmation par Contraintes
CountryFrance
CityOrléans
Period03/06/200905/06/2009

Keywords

  • Constrained Hidden Markov Model
  • Constraint Programming
  • Viterbi Computation

Cite this

Petit, M., & Christiansen, H. (2009). Un calcul de Viterbi pour un Modèle de Markov Caché Contraint. In Proceedings des 5ème Journée Francophone de Programmation par Contraintes
Petit, Matthieu ; Christiansen, Henning. / Un calcul de Viterbi pour un Modèle de Markov Caché Contraint. Proceedings des 5ème Journée Francophone de Programmation par Contraintes. 2009.
@inproceedings{305fb8c0782b11debfff000ea68e967b,
title = "Un calcul de Viterbi pour un Mod{\`e}le de Markov Cach{\'e} Contraint",
abstract = "A hidden Markov model (HMM) is a statistical model in which the system being modeled is assumed to be a Markov process with hidden states. This model has been widely used in speech recognition and biological sequence analysis. Viterbi algorithm has been proposed to compute the most probable value of these hidden states in regards to an observed data sequence. Constrained HMM extends this framework by adding some constraints on a HMM process run.In this paper, we propose to introduce constrained HMMs into Constraint Programming. We propose new version of the Viterbi algorithm for this new framework. Several constraint techniques are used to reduce the search of the most probable value of hidden states of a constrained HMM. An implementation based on PRISM, a logic programming language for statistical modeling, is presented.",
keywords = "Constrained Hidden Markov Model, Constraint Programming, Viterbi Computation",
author = "Matthieu Petit and Henning Christiansen",
year = "2009",
language = "Fransk",
booktitle = "Proceedings des 5{\`e}me Journ{\'e}e Francophone de Programmation par Contraintes",

}

Petit, M & Christiansen, H 2009, Un calcul de Viterbi pour un Modèle de Markov Caché Contraint. in Proceedings des 5ème Journée Francophone de Programmation par Contraintes., Orléans, France, 03/06/2009.

Un calcul de Viterbi pour un Modèle de Markov Caché Contraint. / Petit, Matthieu; Christiansen, Henning.

Proceedings des 5ème Journée Francophone de Programmation par Contraintes. 2009.

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - Un calcul de Viterbi pour un Modèle de Markov Caché Contraint

AU - Petit, Matthieu

AU - Christiansen, Henning

PY - 2009

Y1 - 2009

N2 - A hidden Markov model (HMM) is a statistical model in which the system being modeled is assumed to be a Markov process with hidden states. This model has been widely used in speech recognition and biological sequence analysis. Viterbi algorithm has been proposed to compute the most probable value of these hidden states in regards to an observed data sequence. Constrained HMM extends this framework by adding some constraints on a HMM process run.In this paper, we propose to introduce constrained HMMs into Constraint Programming. We propose new version of the Viterbi algorithm for this new framework. Several constraint techniques are used to reduce the search of the most probable value of hidden states of a constrained HMM. An implementation based on PRISM, a logic programming language for statistical modeling, is presented.

AB - A hidden Markov model (HMM) is a statistical model in which the system being modeled is assumed to be a Markov process with hidden states. This model has been widely used in speech recognition and biological sequence analysis. Viterbi algorithm has been proposed to compute the most probable value of these hidden states in regards to an observed data sequence. Constrained HMM extends this framework by adding some constraints on a HMM process run.In this paper, we propose to introduce constrained HMMs into Constraint Programming. We propose new version of the Viterbi algorithm for this new framework. Several constraint techniques are used to reduce the search of the most probable value of hidden states of a constrained HMM. An implementation based on PRISM, a logic programming language for statistical modeling, is presented.

KW - Constrained Hidden Markov Model

KW - Constraint Programming

KW - Viterbi Computation

M3 - Konferencebidrag i proceedings

BT - Proceedings des 5ème Journée Francophone de Programmation par Contraintes

ER -

Petit M, Christiansen H. Un calcul de Viterbi pour un Modèle de Markov Caché Contraint. In Proceedings des 5ème Journée Francophone de Programmation par Contraintes. 2009