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).
These are multi-class dynamics. To model them effectively, a system must handle:
- Mixed States: Simultaneously tracking continuous variables (like position) and discrete labels (the "mode" or class of motion).
- Hidden Data: The true state is "hidden" behind noisy sensor data, such as pixel noise in a video feed.
- 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.
- 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