Abstract
Due to the difficulty of comprehensive data collection, created by factors such as privacy protection and sensor device limitations, we often need to analyze incomplete transition data where some information is missing from the ideal (complete) transition data. In this paper, we propose a new method that can estimate, in a unified manner, Markov chain parameters from incomplete transition data that consist of hidden transition data (data from which visited state information is partially hidden) and dropped transition data (data from which some state visits are dropped). A key to developing the method is regarding the hidden and dropped transition data as labeled and unlabeled multi-step transition data, where the labels represent the number of steps required for each transition. This allows us to describe the generative process of multi-step transition data, and thus develop a new probabilistic model. We confirm the effectiveness of the proposal by experiments on synthetic and real data.
What Problem Does This Paper Address?
Markov Chains (MCs) are fundamental for modeling sequential processes, from web browsing patterns to urban traffic flow. Ideally, estimating an MC requires complete transition data—a perfect record of every state visited (e.g., $a \to b \to c$). However, real-world data collection is frequently hampered by privacy constraints or hardware limitations, leading to "incomplete" datasets.
The authors identify two pervasive types of incomplete data:
- Hidden Transitions: You know a transition occurred, but the intermediate state is missing (e.g., a GPS signal drop). You observe $a \to ? \to c$, knowing exactly 2 steps were taken.
- Dropped Transitions: Intermediate visits are filtered out entirely, often for storage efficiency or privacy (e.g., only recording stays longer than a certain threshold). You observe $a \to c$, but the number of intermediate steps is unknown.
Standard estimation methods often fail here; they either assume every recorded transition is a single step (introducing significant bias) or can only handle "hidden" data via standard Expectation-Maximization (EM). This paper introduces a unified framework to recover 1-step transition probabilities from both types of messy data simultaneously.
Methods
The core innovation lies in reframing the problem through the lens of multi-step transitions.
- The Generative Model: The process is modeled as a two-stage choice. First, the number of steps $k$ is drawn from a distribution (e.g., Poisson or Geometric). Second, the destination state is determined by the $k$-step transition probability, which is the 1-step transition matrix $P$ raised to the power of $k$.
- Labeled vs. Unlabeled Data: "Hidden" data is treated as labeled multi-step data because the step count $k$ is known. "Dropped" data is treated as unlabeled, where $k$ is a latent variable.
- The MM Algorithm: To optimize the complex log-likelihood, the authors employ a Majorization-Minimization (MM) algorithm. This generalization of EM iteratively optimizes a surrogate function, ensuring the objective function improves at every step.
- Handling Infinite Horizons: Since a dropped transition could theoretically represent any number of steps, the authors use a truncation strategy. For large $k$, they leverage the Markov Chain's convergence to its steady-state distribution ($\pi$) to approximate the tail of the infinite mixture, making computation feasible.
Key Insights and Results
- Unlabeled Data as a Signal: A major finding is that even when the number of steps is unknown, the mere occurrence of a transition between states provides structural information that helps refine the 1-step transition matrix.
- Performance Gains: In both synthetic (15-state) and real-world (Tokyo GPS probe data) experiments, the proposed method consistently outperformed baselines in lowering negative test log-likelihood.
- Robustness: The model proved stable regarding the truncation level ($K$). Performance stabilized once the model considered at least 10 possible steps for unlabeled transitions, validating the effectiveness of the steady-state approximation.
- Accuracy: Visualization of the estimated transition matrices demonstrates that the proposed method recovers the true underlying transition structure much more accurately than traditional approaches that ignore the multi-step nature of the data.
Conclusion
By framing hidden and dropped data as a semi-supervised learning problem involving labeled and unlabeled multi-step transitions, the authors provide a mathematically rigorous way to utilize data that is typically discarded. Future work includes extending this to Bayesian frameworks to better handle uncertainty and incorporating more complex features into the transition models.
Reference: Kohjima, M., Kurashima, T., & Toda, H. (2020). Learning with Labeled and Unlabeled Multi-Step Transition Data for Recovering Markov Chain from Incomplete Transition Data. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20).
Summary updated