Learning Multi-Class Dynamics

Andrew Blake, Ben North, Michael IsardNeurIPS 1998

This paper by Andrew Blake, Ben North, and Michael Isard (University of Oxford) presents a robust framework for learning the underlying "grammar" of complex, multi-modal motions from noisy visual data. By combining the Expectation-Maximization (EM) algorithm with the CONDENSATION (particle filtering) algorithm, the authors automatically learn "multi-class" dynamics—complex motions that switch between different physical regimes.

The Challenge of Multi-Class Dynamics

Standard tools for analyzing time-varying signals, such as Yule-Walker equations or Kalman filters, excel at modeling simple, linear dynamical processes. However, real-world motion is rarely that simple. Consider a person juggling: the ball follows a parabolic arc (ballistic motion), is caught and moved by a hand (carry), and then accelerated for a release (throw).

Juggling tracking sequence

These are multi-class dynamics. To model them effectively, a system must handle:

  1. Mixed States: Simultaneously tracking continuous variables (like position) and discrete labels (the "mode" or class of motion).
  2. Hidden Data: The true state is "hidden" behind noisy sensor data, such as pixel noise in a video feed.
  3. Non-Linearity: Switching between different motion classes makes the overall system non-linear, rendering standard Kalman-based EM approaches ineffective.

The EM-Condensation Framework

To address these challenges, the paper proposes a probabilistic framework that represents a state as a combination of a continuous vector and a discrete class label.

  • Multi-Class Auto-Regressive Processes (ARP): Each motion class is modeled as an ARP of arbitrary order. The next position is predicted based on a weighted sum of several previous positions plus some stochastic "noise."
  • Particle Filtering for Learning: The core innovation is the EM-Condensation algorithm. While Expectation-Maximization (EM) is standard for finding parameters of hidden variables, its "E-step" is mathematically intractable for multi-class dynamics. The authors use the CONDENSATION algorithm—a particle filter—to approximate this E-step. By propagating random samples (particles) and maintaining a history of those samples via backward chaining, they estimate the complex, multi-modal probability distributions required for learning.

Key Insights and Results

The primary evaluation is performed on a custom dataset of visually observed juggling, tracking a ball in a 2D plane. Training involved approximately 60 EM iterations using 2,048 particles per time step.

Learned state transition diagram for juggling
  • Emergent Physics: Strikingly, the model is not given any prior laws of physics—it does not "know" about gravity. Yet, through learning, it identifies a "Ballistic" class where the learned vertical acceleration is approximately $-9.7 \, \text{m/s}^2$, nearly identical to the actual constant of gravity ($g$).
  • Successful Classification: The algorithm successfully partitions the juggling motion into three distinct, plausible classes: Ballistic (free-fall), Catch/Throw (active manipulation), and Carry (moving with the hand).
  • Directed Transitions: The learned transition matrix demonstrates that the system understands the sequence of juggling. For instance, ballistic motion is much more likely to be followed by a catch/throw than by a carry. It also correctly identified that the ballistic phase is the longest, with a 95% probability of remaining in that state at any given time step.
  • Dynamics as a Classifier: The system uses the quality of the motion to classify what the object is doing, allowing for a healthy separation between the observation model (what the camera sees) and the dynamical model (how the object moves).

Limitations and Future Work

While groundbreaking, the approach has limitations:

  • Computational Cost: The authors note an alternative "forward-backward" smoothing algorithm that converges faster but scales at $O(N^2)$, making it significantly more expensive than their $O(N \log N)$ approach.
  • Initialization: The algorithm requires a reasonable starting point. While data eventually dominates the prior, poor initialization in a highly complex environment could lead to local optima.
  • Dimensionality: Demonstrated on 2D translation, the framework is theoretically applicable to multi-dimensional signals (like EEG or multi-spectral audio). However, the number of particles required might scale poorly as the dimensionality of the state space increases.

Summary updated

BibTeX
@inproceedings{blake1998learning,
  author = {Andrew Blake and Ben North and Michael Isard},
  title = {{Learning Multi-Class Dynamics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1998},
}
Figure