Fitting Sparse Markov Models to Categorical Time Series Using Convex Clustering
This work addresses the challenge of parsimonious modeling in categorical time series for researchers and practitioners, representing an incremental improvement over existing methods like VLMCs.
The paper tackles the parameter explosion problem in higher-order Markov chains for categorical time series by proposing a method to fit Sparse Markov Models (SMMs) using convex clustering and regularization, with theoretical consistency and simulation results showing finite sample performance.
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.