TL;DR
This paper introduces a novel "mixed-state" dynamic graphical model that combines discrete hidden actions with continuous physical system dynamics. To overcome the computational intractability of exact inference, they propose a structured variational inference technique that learns and infers these complex models, demonstrating its effectiveness in classifying hand gestures.
What Problem Does This Paper Address?
Many real-world time-series phenomena, like human gestures or target motion, are driven by a combination of continuous physical laws and discrete, hidden causes (e.g., muscle actions, control inputs). Modeling these phenomena requires systems that can handle both continuous (like linear dynamic systems) and discrete (like hidden Markov models) states simultaneously. However, combining these in a probabilistic graphical model leads to exponentially complex inference problems, making exact solutions infeasible for practical sequence lengths. Existing approximate methods often fail to consistently improve inference or have limitations. This paper aims to bridge this gap by developing a tractable method for inference and learning in these mixed-state dynamic graphical models.
Methods
The core of the paper is the introduction of a mixed-state dynamic Bayesian network (DBN). This model couples a Hidden Markov Model (HMM) for discrete actions with a Linear Dynamic System (LDS) for continuous physical states.
The key innovation is the structured variational inference technique. Instead of trying to approximate the full posterior distribution directly, this method:
- Decouples the HMM and LDS: The complex mixed-state model is factored into two simpler, independent subgraphs: one for the HMM (Qs) and one for the LDS (Qx). This factorization is inspired by the graphical model's structure.
- Introduces Variational Parameters: A set of variational parameters (η) is introduced to define an approximating distribution Q(X, S|Y, η).
- Minimizes KL Divergence: The goal is to find the parameters η* that minimize the Kullback-Leibler (KL) divergence between the approximating distribution Q and the true posterior P(X, S|Y).
- Fixed-Point Equations: This minimization leads to a set of fixed-point equations that interleave inference steps for the HMM and LDS. Specifically, the HMM's output probabilities (qt) are used to infer the LDS states, and the LDS's estimated states (xt) are used to infer the HMM's input probabilities (ut). This iterative process allows for tractable approximate inference.
- Learning: The paper also outlines how to learn the parameters of the mixed-state DBN using a maximization step derived from the variational inference framework, effectively generalizing parameter updates for LDSs.
Datasets
The paper uses a dataset of hand gestures acquired by a computer mouse. This dataset consists of 136 examples for each of four symbols: arrow, erase, circle, and wiggle. The data was collected with normalized mouse movements sampled at 100ms intervals. For evaluation, a noisy version of this dataset was created by adding i.i.d. zero-mean Gaussian noise with a standard deviation of 0.01 to the original samples.
Key Insights and Ideas
- Bridging Discrete and Continuous Dynamics: The paper elegantly shows how to fuse discrete hidden causes (actions) with continuous physical dynamics (system states) within a single probabilistic framework. This is crucial for modeling many real-world systems.
- Tractability through Structure: The core insight is that by exploiting the specific structure of the mixed-state DBN (decoupling into HMM and LDS), a computationally tractable variational inference algorithm can be derived. This avoids the exponential complexity of exact inference.
- Interplay between Action and Dynamics: The variational inference algorithm reveals an interesting interplay: the HMM's inferred action probabilities (qt) are influenced by the LDS's estimated states, and vice-versa. This suggests that the inferred actions are "tuned" to the observed physical dynamics.
- Structured Variational Inference Advantage: The paper highlights that structured variational inference, by explicitly considering the model's structure, offers a more consistent way to approximate posteriors compared to greedy methods, especially when the HMM provides only subtle distinctions between states or when LDS noise is low.
Key Results
- The proposed mixed-state DBN with structured variational inference achieved significantly better classification performance on noisy mouse gesture data compared to decoupled LDS/HMM models (both fixed and adapted).
- For the "arrow" symbol, the mixed-state HMM achieved an error estimate of 4.36% with a variance of 0.89%, outperforming the best decoupled model (gradient fixed LDS/HMM) which had an error of 9.45% with a variance of 1.25%.
- The iterative scheme for the mixed-state models converged in approximately 5 to 10 iterations on average.
- The paper demonstrates that a greedy approximation (truncated Viterbi) can be suboptimal, while the variational approach consistently finds better solutions.
Limitations and Future Work
- Computational Complexity Tradeoff: While the variational method makes inference tractable, the mixed-state DBN is still computationally more complex than decoupled models. The paper notes this as a tradeoff.
- Unimodal Approximation: The structured variational inference yields a "best unimodal approximation" to the exact polymodal posterior. This means it might not capture all the nuances of a multimodal posterior distribution.
- Future Work: The paper implicitly suggests that exploring more sophisticated variational approximations or extending the model to handle more complex dynamics or non-Gaussian noise could be future directions. The current work focuses on a specific structure (HMM driving LDS) and could be generalized.
Summary updated