Chaîne stochastique à mémoire de longueur variable
Une chaîne stochastique à mémoire de longueur variable fait partie d'une famille de chaînes stochastiques d'ordre fini dans un alphabet fini. L'idée est que, pour chaque passé, seul un suffixe fini du passé, appelé le contexte, est nécessaire pour être capable de prévoir le prochain symbole. Ces modèles ont été introduits dans la théorie de l'information par Jorma Rissanen, en 1983, comme un outil universel pour la compression des données[1]. Récemment, ces chaînes ont été utilisées pour modéliser des données dans différents domaines tels que la biologie[2], la linguistique[3] et la musique[4].
Définition
Une chaîne stochastique à mémoire de longueur variable est une chaîne stochastique , prenant des valeurs de l'alphabet fini et représentée par un arbre probabiliste de contextes , tel que[5]:
- est l'ensemble de tous les contextes. Un contexte , étant la taille du contexte, est une portion finite du passé qui est nécessaire pour prédire le prochain symbole ;
- est une famille de probabilités de transition associée à chaque contexte.
Histoire
La classe de chaînes stochastiques à mémoire de longueur variable a été introduite en 1983 par Jorma Rissanen, dans l'article A universal system for data compression system[1]. Cette classe de chaînes stochastiques a été popularisée dans la communauté des probabilités et statistiques par P. Bühlmann et Abraham J. Wyner, en 1999, dans l'article longueur Variable Length Markov Chains. Bühlmann et Wyner ont alors appelé cet objet mathématique de « chaînes de Markov à longueur variable ». Ces chaînes sont également connues sous le nom de « modèles de Markov d'ordre variable », « arbres probabilistes de suffixes »[2] et « modèles générés par des arbres de contexte »[6].
Notions liées
Références
- J. Rissanen, « A universal data compression system », IEEE Transactions on Information Theory, vol. 29, no 5, , p. 656–664 (ISSN 0018-9448, DOI 10.1109/TIT.1983.1056741, lire en ligne, consulté le )
- Gill Bejerano et Golan Yona, « Variations on probabilistic suffix trees: statistical modeling and prediction of protein families », Bioinformatics, vol. 17, no 1, , p. 23–43 (ISSN 1367-4803, DOI 10.1093/bioinformatics/17.1.23, lire en ligne, consulté le )
- (en) Antonio Galves, Charlotte Galves, Jesús E. García et Nancy L. Garcia, « Context tree selection and linguistic rhythm retrieval from written texts », The Annals of Applied Statistics, vol. 6, no 1, , p. 186–209 (ISSN 1932-6157 et 1941-7330, DOI 10.1214/11-AOAS511, lire en ligne, consulté le )
- S. Dubnov, G. Assayag, O. Lartillot et G. Bejerano, « Using machine-learning methods for musical style modeling », Computer, vol. 36, no 10, , p. 73–80 (ISSN 0018-9162, DOI 10.1109/MC.2003.1236474, lire en ligne, consulté le )
- (en) Galves, Antonio et Löcherbach, Eva, « Stochastic chains with memory of variable length », ArXiv, (lire en ligne, consulté le )
- (en) Antonio Galves, Aurélien Garivier et Elisabeth Gassiat, « Joint Estimation of Intersecting Context Tree Models », Scandinavian Journal of Statistics, vol. 40, no 2, , p. 344–362 (ISSN 1467-9469, DOI 10.1111/j.1467-9469.2012.00814.x, lire en ligne, consulté le )