Max Markov Chain

Yu Zhang, Mitchell Bucklew

Abstract

The Max Markov Chain (MMC) is a novel stochastic model designed to capture long-term, sparse dependencies in sequential data without the exponential parameter explosion characteristic of High-order Markov Chains (HMCs). By employing a "winner-take-all" mechanism where only the most "influential" past state generates the next one, MMC achieves superior sample efficiency and computational scaling. This paper demonstrates MMC's effectiveness on synthetic and real-world financial datasets, outperforming traditional baselines in both accuracy and speed.

Introduction

Modeling sequences with long-term dependencies is a fundamental challenge in time-series analysis. Standard First-order Markov Chains (FMC) are computationally efficient but "forgetful," as they only consider the immediate past state. To capture longer history, High-order Markov Chains (HMCs) are often used; however, their complexity grows exponentially with the history length (the "order"), leading to the "curse of dimensionality" and prohibitive data requirements.

Existing approximations, such as the Mixture Transition Distribution (MTD), attempt to simplify HMCs by averaging the influences of past states. Yet, these models often assume context-independent influence—where a specific lag always carries the same weight regardless of the actual state value. The Max Markov Chain (MMC) addresses this gap by modeling sparse, long-term, and context-dependent correlations efficiently.

Methodology

The core innovation of the MMC is the "max" assumption, which governs state transitions through two primary mechanisms:

  1. Winner-Take-All Generation: Instead of combining or averaging all previous states, the MMC assumes the next state is generated by one and only one previous lag. Specifically, the model selects the lag that has the highest "priority" or generation probability in the current context.
  2. Skipping Links: This selection mechanism naturally creates "skipping links," allowing the model to ignore the immediate past and focus on a more relevant state from several steps ago.
Comparison of FMC, HMC, and MMC architectures. The MMC uses skipping links to focus on the most relevant past state, avoiding the dense connections of HMC.

To manage these priorities, the authors introduce a State Generation Order (SGO). If multiple past states could potentially influence the future, the one with the highest SGO rank "wins" the generation process. While finding the absolute optimal parameters is NP-hard, the authors provide an analytical solution for fixed rankings and a Greedy Heuristic that reduces training complexity to $O(|D||S|)$, where $|D|$ is the data size and $|S|$ is the state space size.

Key Insights

Parsimony via Selection

Unlike MTD, which uses a weighted sum of past influences, MMC selects the single best generator. This allows it to maintain the parameter count of a first-order chain ($O(M^2)$) while effectively modeling dependencies of order $K$.

Context-Dependency

In MMC, which past state matters is entirely dependent on the values of those past states. This mirrors real-world scenarios where a specific significant event in the past overrides the immediate routine. For example, in a library visit sequence, an earlier arrival event might be more predictive of a later checkout than the immediate preceding activity.

Illustration of the context-dependent selection in MMC. The probability distribution for the next state $S_4$ is determined by the "winning" past state $S_1$ based on its priority in the current context.

Implicit Regularization

By relating state priorities to their maximum generation probabilities, the model naturally avoids overfitting on rare states. It associates higher uncertainty with states that appear less frequently as "generators," providing a form of implicit regularization.

Experimental Results

The authors evaluated MMC against FMC, HMC, and MTD using synthetic data, US Inflation data (CPI rates from 1821–1999), and Apple stock price movements.

  • Superior Accuracy: On the US Inflation dataset, MMC achieved 50.76% testing accuracy, significantly outperforming HMC (37.86%) and MTD (48.15%). Similar gains were observed in Apple stock price prediction.
  • Computational Scaling: MMC's training time remains linear relative to the state space size. In experiments, MMC was orders of magnitude faster than MTD as the state space or order increased.
  • Sample Efficiency: MMC requires far fewer data points than HMC. On synthetic "Causal" data, MMC's performance remained stable as the order increased, while HMC's performance plummeted due to data sparsity.

Conclusion

The Max Markov Chain offers a scalable and accurate alternative for modeling sequences with sparse, long-term dependencies. By replacing averaging with a priority-based selection mechanism, it avoids the curse of dimensionality while capturing context-dependent relationships. Future work includes extending the model to handle Partial Observability (similar to Hidden Markov Models) and exploring Factored Representations for high-dimensional state variables.

Summary updated

Abstract

In this paper, we introduce Max Markov Chain (MMC), a novel representation for a useful subset of High-order Markov Chains (HMCs) with sparse correlations among the states. MMC is parsimony while retaining the expressiveness of HMCs. Even though parameter optimization is generally intractable as with HMC approximate models, it has an analytical solution, better sample efficiency, and the desired spatial and computational advantages over HMCs and approximate HMCs. Simultaneously, efficient approximate solutions exist for this type of chains as we show empirically, which allow MMCs to scale to large domains where HMCs and approximate HMCs would struggle to perform. We compare MMC with HMC, first-order Markov chain, and an approximate HMC model in synthetic domains with various data types to demonstrate that MMC is a valuable alternative for modeling stochastic processes and has many potential applications.
BibTeX
@inproceedings{zhang2023max,
  author = {Yu Zhang and Mitchell Bucklew},
  title = {{Max Markov Chain}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/639},
}
Figure