Recursive learning for sparse Markov models

Jie Xiong, Väinö Jääskinen, Jukka Corander

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Markov chains of higher order are popular models for a wide variety of applications in natural language and DNA sequence processing. However, since the number of parameters grows exponentially with the order of a Markov chain, several alternative model classes have been proposed that allow for stability and higher rate of data compression. The common notion to these models is that they cluster the possible sample paths used to predict the next state into invariance classes with identical conditional distributions assigned to the same class. The models vary in particular with respect to constraints imposed on legitime partitions of the sample paths. Here we consider the class of sparse Markov chains for which the partition is left unconstrained a priori. A recursive computation scheme based on Delaunay triangulation of the parameter space is introduced to enable fast approximation of the posterior mode partition. Comparisons with stochastic optimization, k-means and nearest neighbor algorithms show that our approach is both considerably faster and leads on average to a more accurate estimate of the underlying partition. We show additionally that the criterion used in the recursive steps for comparison of triangulation cell contents leads to consistent estimation of the local structure in the sparse Markov model.
Original languageEnglish
JournalBayesian analysis
Volume11
Issue number1
Pages (from-to)247-263
Number of pages17
ISSN1931-6690
DOIs
Publication statusPublished - 2016
MoE publication typeA1 Journal article-refereed

Fields of Science

  • 112 Statistics and probability
  • Clustering
  • Recursive learning
  • Sequence analysis,
  • Sparse Markov chains

Cite this

Xiong, Jie ; Jääskinen, Väinö ; Corander, Jukka. / Recursive learning for sparse Markov models. In: Bayesian analysis. 2016 ; Vol. 11, No. 1. pp. 247-263.
@article{a1c247f49ca449808df44a9b4ad4ecf1,
title = "Recursive learning for sparse Markov models",
abstract = "Markov chains of higher order are popular models for a wide variety of applications in natural language and DNA sequence processing. However, since the number of parameters grows exponentially with the order of a Markov chain, several alternative model classes have been proposed that allow for stability and higher rate of data compression. The common notion to these models is that they cluster the possible sample paths used to predict the next state into invariance classes with identical conditional distributions assigned to the same class. The models vary in particular with respect to constraints imposed on legitime partitions of the sample paths. Here we consider the class of sparse Markov chains for which the partition is left unconstrained a priori. A recursive computation scheme based on Delaunay triangulation of the parameter space is introduced to enable fast approximation of the posterior mode partition. Comparisons with stochastic optimization, k-means and nearest neighbor algorithms show that our approach is both considerably faster and leads on average to a more accurate estimate of the underlying partition. We show additionally that the criterion used in the recursive steps for comparison of triangulation cell contents leads to consistent estimation of the local structure in the sparse Markov model.",
keywords = "112 Statistics and probability, Clustering, Recursive learning, Sequence analysis,, Sparse Markov chains",
author = "Jie Xiong and V{\"a}in{\"o} J{\"a}{\"a}skinen and Jukka Corander",
year = "2016",
doi = "10.1214/15-BA949",
language = "English",
volume = "11",
pages = "247--263",
journal = "Bayesian analysis",
issn = "1931-6690",
publisher = "International Society for Bayesian Analysis",
number = "1",

}

Recursive learning for sparse Markov models. / Xiong, Jie; Jääskinen, Väinö; Corander, Jukka.

In: Bayesian analysis, Vol. 11, No. 1, 2016, p. 247-263.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Recursive learning for sparse Markov models

AU - Xiong, Jie

AU - Jääskinen, Väinö

AU - Corander, Jukka

PY - 2016

Y1 - 2016

N2 - Markov chains of higher order are popular models for a wide variety of applications in natural language and DNA sequence processing. However, since the number of parameters grows exponentially with the order of a Markov chain, several alternative model classes have been proposed that allow for stability and higher rate of data compression. The common notion to these models is that they cluster the possible sample paths used to predict the next state into invariance classes with identical conditional distributions assigned to the same class. The models vary in particular with respect to constraints imposed on legitime partitions of the sample paths. Here we consider the class of sparse Markov chains for which the partition is left unconstrained a priori. A recursive computation scheme based on Delaunay triangulation of the parameter space is introduced to enable fast approximation of the posterior mode partition. Comparisons with stochastic optimization, k-means and nearest neighbor algorithms show that our approach is both considerably faster and leads on average to a more accurate estimate of the underlying partition. We show additionally that the criterion used in the recursive steps for comparison of triangulation cell contents leads to consistent estimation of the local structure in the sparse Markov model.

AB - Markov chains of higher order are popular models for a wide variety of applications in natural language and DNA sequence processing. However, since the number of parameters grows exponentially with the order of a Markov chain, several alternative model classes have been proposed that allow for stability and higher rate of data compression. The common notion to these models is that they cluster the possible sample paths used to predict the next state into invariance classes with identical conditional distributions assigned to the same class. The models vary in particular with respect to constraints imposed on legitime partitions of the sample paths. Here we consider the class of sparse Markov chains for which the partition is left unconstrained a priori. A recursive computation scheme based on Delaunay triangulation of the parameter space is introduced to enable fast approximation of the posterior mode partition. Comparisons with stochastic optimization, k-means and nearest neighbor algorithms show that our approach is both considerably faster and leads on average to a more accurate estimate of the underlying partition. We show additionally that the criterion used in the recursive steps for comparison of triangulation cell contents leads to consistent estimation of the local structure in the sparse Markov model.

KW - 112 Statistics and probability

KW - Clustering

KW - Recursive learning

KW - Sequence analysis,

KW - Sparse Markov chains

U2 - 10.1214/15-BA949

DO - 10.1214/15-BA949

M3 - Article

VL - 11

SP - 247

EP - 263

JO - Bayesian analysis

JF - Bayesian analysis

SN - 1931-6690

IS - 1

ER -