# Fitting Sparse Markov Models to Categorical Time Series Using Convex Clustering

arXiv: https://arxiv.org/abs/2202.05485 · HTML: https://mlsanity.com/paper/2202.05485/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 28 references that are in the map.
- First posted on arXiv 11 Feb 2022.

## Builds on (most cited first, 6 of 6)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Splitting Methods for Convex Clustering](https://mlsanity.com/paper/1304.0499/) (2013)
- [Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm](https://mlsanity.com/paper/1810.02677/) (2018)
- [Bayesian Context Trees: Modelling and exact inference for discrete time series](https://mlsanity.com/paper/2007.14900/) (2020)
- [Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization](https://mlsanity.com/paper/1901.01477/) (2019)
- [Integrative Generalized Convex Clustering Optimization and Feature Selection for Mixed Multi-View Data](https://mlsanity.com/paper/1912.05449/) (2019)

## Abstract (arXiv)

Higher-order Markov chains are frequently used to model categorical time series. However, a major problem with fitting such models is the exponentially growing number of parameters in the model order. A popular approach to parsimonious modeling is to use a Variable Length Markov Chain (VLMC), which determines relevant contexts (recent pasts) of variable orders and forms a context tree. A more general parsimonious modeling approach is given by Sparse Markov Models (SMMs), where all possible histories of order m are partitioned such that the transition probability vectors are identical for the histories belonging to any particular group. In this paper, we develop an elegant method of fitting SMMs based on convex clustering and regularization. The regularization parameter is selected using the BIC criterion. Theoretical results establish model selection consistency of our method for large sample size. Extensive simulation results under different set-ups are presented to study finite sample performance of the method. Real data analysis on modelling and classifying disease sub-types demonstrates the applicability of our method as well.