Max Markov Chain

Yu Zhang, Mitchell Bucklew

TL;DR

The Max Markov Chain (MMC) is a novel approach to modeling high-order stochastic processes by assuming "sparse correlations" among states. By using a "winner-take-all" priority system instead of the computationally expensive weighted sums used in traditional models, MMC achieves high sample efficiency and scalability while maintaining the expressiveness needed for complex, real-world dependencies.

What Problem Does This Paper Address?

Markov Chains (MCs) are the bread and butter of stochastic modeling, but they face a massive scaling problem. A standard First-order MC assumes the next state depends only on the current one. To model long-term dependencies, we use High-order Markov Chains (HMCs). However, HMCs suffer from the "curse of dimensionality": the number of parameters grows exponentially with the "order" (how far back you look). For a system with $M$ states and an order of $K$, you need $M^K(M-1)$ parameters.

Existing approximations, like the Mixture Transition Distribution (MTD) model, try to reduce this by using a weighted combination of previous states. While MTD is more parsimonious, it is notoriously difficult to optimize and often requires intense computational resources. The authors identify a gap: we need a model that captures long-term dependencies but is simple enough to learn quickly from limited data and scale to large state spaces.

Methods

The authors introduce the Max Markov Chain (MMC). The core intuition is a "winner-take-all" mechanism. Instead of every previous state in the history (the "lags") contributing a little bit to the next state, the MMC assumes that only one previous state—the one with the highest "priority"—actually generates the next state.

Key components include:

  • State Generation Order (SGO): A priority ranking of all possible states.
  • The "Max" Rule: At any time step, the model looks at the last $K$ states. The state among those $K$ that has the highest rank in the SGO is the one that determines the probability distribution for the next state.
  • Parameter Estimation: The authors provide an analytical solution for finding the best parameters if the SGO is known. However, finding the optimal SGO is a combinatorial nightmare (factorial in the number of states).
  • Optimization Heuristics: To make it practical, they propose two search methods:
  • Hill Climbing: Incrementally swapping state priorities to improve data likelihood.
  • Greedy Heuristic: Ordering states based on their maximum generation probabilities estimated directly from the data. This allows the model to scale to very large domains.

Datasets

The researchers evaluated the MMC using three types of synthetic data to test different assumptions:

  1. HMC Data: Randomly generated data following a standard high-order Markov process (the "worst-case" for MMC).
  2. MMC Data: Data generated specifically using the MMC "winner-take-all" assumption.
  3. Causal Data: Data designed to mimic real-world logic (e.g., a "disruption" event at a library taking priority over "studying" when determining if a person leaves). This represents the "sparse correlation" the authors aim to capture.

Key Insights and Ideas

  • Structural Parsimony: Most approximate models (like MTD) keep the model structure dense but simplify the parameters. MMC simplifies the structure itself by assuming sparse correlations. This prevents overfitting and makes the model much more "sample efficient"—it learns more from less data.
  • The Priority Logic: The MMC effectively models "interrupt" or "precedence" logic. In many real-world sequences, a specific past event (like a "system failure" or "user command") overrides the general flow of the process. MMC captures this naturally through the SGO.
  • Efficiency vs. Complexity: While MMC has the same number of parameters as a first-order Markov chain ($M(M-1)$), it can represent a subset of high-order processes that a first-order chain simply cannot.

Key Results

  • Scalability: In tests varying the state space size, the MTD model's training time exploded exponentially. In contrast, the MMC (using the greedy heuristic) remained nearly flat, showing it can handle much larger systems.
  • Sample Efficiency: On "Causal" and "MMC" data, the MMC reached high prediction accuracy with far fewer training samples than HMC or MTD.
  • Performance on Causal Data: This was the "aha" moment. Even though Causal data only approximately fits the MMC assumptions, the MMC outperformed all other models as the state space or order increased. It proved to be a more robust generalizer for structured, logical sequences.
  • HMC Performance: As expected, on purely random HMC data, the MTD model performed better because the data lacked the sparse, priority-based structure that MMC exploits.

Limitations and Future Work

The primary limitation is that MMC is a "subset" model. If a process truly requires a dense, weighted combination of all past states to predict the future, MMC will be biased and underperform.

The authors suggest several promising directions for future research:

  • Partial Observability: Extending MMC to work with Hidden Markov Models (HMMs).
  • Multiple Generation States: Relaxing the "winner-take-all" rule to allow the top $N$ priority states to influence the outcome, creating a spectrum between MMC and HMC.
  • Real-world Applications: Applying the model to fields like intention recognition or multi-agent task planning, where "priority" events are common.

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},
}

Loading related content...

Figure