TL;DR
This paper introduces a "temporally abstracted Viterbi algorithm" (TAV) that significantly speeds up finding the most likely sequence of states in Hidden Markov Models (HMMs) by reasoning over longer time intervals. TAV achieves dramatic computational savings, especially for problems with variables that change at vastly different rates, by intelligently pruning large portions of the state-time trellis.
What Problem Does This Paper Address?
The Viterbi algorithm is a cornerstone for finding the most likely sequence of hidden states in HMMs, crucial for applications like speech recognition and bioinformatics. However, its computational complexity grows rapidly with the number of states (N) and the length of the observation sequence (T), becoming prohibitive for large-scale problems (e.g., N=2^30, T=1 million). Existing methods like coarse-to-fine dynamic programming (CFDP) use state abstraction to reduce complexity by grouping states. While effective, CFDP still processes each time step individually. This paper addresses the limitation of processing time step-by-step by introducing temporal abstraction, allowing the algorithm to consider longer time intervals and thus prune more of the search space, especially when system dynamics vary significantly over time.
Methods
The core innovation is the Temporally Abstracted Viterbi (TAV) algorithm. TAV extends the Viterbi algorithm by introducing temporally abstract links. These links represent entire trajectories between states at different time points, rather than just single time-step transitions. TAV uses two main refinement strategies:
- Spatial Refinement: Similar to CFDP, this refines abstract states into their constituent finer states. This is applied when a direct link (representing a trajectory staying within an abstract state) is part of the optimal path or when the time span is only one step.
- Temporal Refinement: This is the novel aspect. When a cross link (trajectory moving between different abstract states) or a re-entry link (trajectory leaving and returning to an abstract state) is selected for refinement, TAV splits the time interval into smaller sub-intervals. This allows reasoning over longer periods and is particularly effective when variables have different timescales.
TAV also employs a modified Viterbi algorithm (BestPath) to compute scores and backtrack through the abstracted state-time trellis, considering both abstract and concrete states at each time step. The algorithm iteratively refines links along the current best path until the entire path is composed of fully refined (original) states.
Datasets
The paper does not introduce new datasets. Instead, it uses synthetic data generated from Dynamic Bayesian Networks (DBNs) to simulate systems with variables evolving at different timescales. These DBNs are parameterized by e, representing the ratio of timescales between successive variables, and by the state space size N. Experiments are conducted with varying T (time horizon), e (timescale separation), N (state space size), and different abstraction hierarchy structures.
Key Insights and Ideas
- Temporal Abstraction is Key for Timescale Separation: The most significant insight is that explicitly modeling longer time intervals (temporal abstraction) provides substantial computational benefits when system variables change at vastly different rates. This is where TAV truly shines compared to methods that only use spatial abstraction.
- Direct Links Enable Reasoning Over Trajectories: The introduction of "direct links" allows TAV to reason about entire trajectories within an abstract state over a time interval, a capability missing in previous DP approaches.
- Adaptive Refinement is Crucial: TAV's ability to adaptively choose between spatial and temporal refinement based on the nature of the selected link and the time span is critical for its efficiency.
- Hierarchy Matters: The structure of the abstraction hierarchy significantly impacts performance. Deeper hierarchies generally lead to better performance for TAV, especially when timescale separation is large.
Key Results
- Orders of Magnitude Speedup: TAV demonstrates improvements of several orders of magnitude over the standard Viterbi algorithm and one to two orders of magnitude faster than CFDP for problems with widely differing timescales.
- Effect of Timescale Separation: The computational benefit of TAV increases significantly as the timescale separation (
e) decreases (i.e., variables change at more different rates). - Hierarchy Impact: Deeper abstraction hierarchies lead to better performance for TAV, with improvements being more pronounced than for CFDP.
- Limitations with Fast Timescales: For systems with very fast timescales (small temporal separation), TAV can be slower than CFDP due to the cost of temporal refinements.
Limitations and Future Work
- Performance with Fast Timescales: TAV's performance degrades when the system has frequent state transitions and fast timescales, where it may be more efficient to revert to the conventional Viterbi algorithm.
- Heuristic Computation Trade-off: The paper discusses a trade-off between the accuracy of heuristics (Viterbi heuristic vs. cheaper heuristic) and computation time. While a more accurate heuristic can lead to fewer iterations, it requires more computation.
- Hierarchy Induction: The paper assumes the abstraction hierarchy is given but briefly mentions spectral clustering as a method for inducing hierarchies, noting its high computational cost (O(N³)).
- Future Work: The authors suggest designing an algorithm that can dynamically switch between temporal abstraction and the conventional Viterbi algorithm when heuristic scores of direct links are low. They also highlight the need for efficient hierarchy induction methods.
Summary updated