PARSIMONIOUS HIGH-ORDER MULTIVARIATE MARKOV CHAIN MODELS

Markov chains are popular models for studying categorical data sequences which occur frequently in many real-world applications. In the conventional Markov chain model of m possible states (e.g. data point), the number of parameters grows exponentially with respect to the number of categorical data sequences and/or the order of the Markov chain. This large number of parameters creates a major difficulty in using such a model directly. We have proposed parsimonious multivariate Markov chain models with the number of parameters grows linearly or quadratically and have developed efficient methods for estimating the modal parameters based on Linear Programming and Perron–Frobenius theorem for Markov chains.

In [1], a parsimonious multivariate Markov chain model for s categorical data sequences was proposed, and the number of parameters of the model is only O(s²m²) which is much better than O(mˢ) using the conventional model. The model was then applied to describe the dynamics of multiple gene expression sequences in a genetic regulatory network [2] and also credit rating sequences in a credit risk measurement problem [3].

In [4], a parsimonious n-th order Markov chain model was proposed and the number of parameters of the model is only O(nm²), which is much better than O((m-1)mⁿ) using conventional model.  The model was then applied successfully to different types of data such as

DNA sequence and financial time series analysis.

Upon the success of the parsimonious high-dimensional Markov chains in [1-4], the idea was further generalized to the case of high-order multivariate Markov chain (HOMMC) and an RGC grant was secured for the study. In a conventional nth order multivariate Markov chain model of s chains, and each chain has m possible states, the number of states is O(mⁿˢ) which grows exponentially in n and s. In [5], a parsimonious HOMMC model was proposed for multiple categorical data sequences whose number of parameters is O(ns²m²), which grows linearly in n.

A further simplified HOMMC model was proposed in [6] to deal with the case when the data sequences are too short for parameter estimation. The simplified model was referenced by Google in a patented event prediction method for mobile interaction.

The parsimonious HOMMC models are both effective (small number of parameters) and efficient (fast parameter estimation methods) in capturing the correlations among multiple sequences and their past states. These nice properties make the models excellent choices for real-time prediction in many complex real-world problems.

References to the research

Ching, W., Fung, E., & Ng, M. (2002). A multivariate Markov chain model for categorical data sequences and its applications in demand predictions. IMA Journal of Management Mathematics, 13, 187-199. [Citations in Google Scholar: 101]

Ching, W., Ng, M., Fung, E., & Akutsu, T. (2005). On construction of stochastic genetic networks based on gene expression sequences. International Journal of Neural Systems 15(4), 297-310. [Citations in Google Scholar: 62]

Siu, T., Ching, W., Ng, M., & Fung, E. (2005). On a multivariate Markov chain model for credit risk measurement. Quantitative Finance, 5, 543-556. [Citations in Google Scholar: 34]

Ching, W., Fung, E., & Ng, M. (2004). Higher-order Markov chain models for categorical data sequences. Naval Research Logistics, 51, 557-574. [Citations in Google Scholar: 69]

Ching, W., Ng, M., & Fung, E. (2008). Higher-order multivariate Markov chains and their applications. Linear Algebra and Its Applications, 428(2-3), 492-507. [Citations in Google Scholar: 92]

Ching, W., Zhang, S., & Ng, M. (2007). On multi-dimensional Markov chain models. Pacific Journal of Optimization, 3, 235-243. [Citations in Google Scholar: 17]

RGC (Hong Kong) Fundings:

“On Perron-Frobenius Theory for Multivariate Markov Chains with Applications”, 2007-2010, 267,000HKD, Principal Investigator.