Tensorized algorithms and scalable filtering methods for hidden Markov and factorial hidden Markov models

2026-07-09 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, extended

Summary

This work introduces novel tensorized algorithms and scalable filtering methods for analyzing time-series data using factorial hidden Markov models (fHMMs). While fHMMs offer a richer representation for systems influenced by multiple independent factors, their traditional reformulation as equivalent HMMs leads to a prohibitively large state-space and high computational cost, particularly for the forward filtering algorithm. The new approach directly exploits the multidimensional structure of fHMMs via tensor algebra, bypassing intermediate HMM representations. Benchmarking tests demonstrate that these tensorized methods maintain numerical accuracy while achieving substantial computational performance gains, including an asymptotic speed-up of approximately 4500x in subsystem size tests and 45x in time-series length tests. The approach also significantly improves memory efficiency, enabling analysis of much larger systems than traditional vectorized methods.

Key takeaway

For Machine Learning Engineers and Research Scientists developing models for complex time-series data, this work provides a critical advancement. If you are using or considering factorial hidden Markov models (fHMMs), you should adopt tensorized filtering algorithms. This approach offers substantial speed-ups (e.g., up to 4500x) and significantly reduces memory footprint, enabling the analysis of much larger and more intricate systems previously deemed computationally infeasible. Prioritize placing larger state-spaces at earlier tensor modes for optimal performance.

Key insights

Tensor algebra directly exploits fHMM's multidimensional structure, drastically improving filtering scalability and memory efficiency.

Principles

• fHMMs can be reformulated as HMMs with larger state-spaces.
• Tensor operations enable direct fHMM processing, avoiding HMM conversion.
• Largest fHMM state-spaces should be placed at earlier tensor modes.

Method

The method involves defining adapted filters as tensors, computing initial iterations via tensor stretches, and subsequent iterations via tensor contractions, all while preserving numerical accuracy.

In practice

• Analyze larger fHMM systems previously limited by memory.
• Implement fHMM filtering using optimized tensor packages like NumPy/MATLAB.
• Optimize fHMM performance by ordering subsystem dimensions.

Topics

• Hidden Markov Models
• Factorial Hidden Markov Models
• Tensor Algebra
• Time-series Analysis
• Forward Filtering
• Computational Performance
• Scalability

Best for: AI Scientist, Machine Learning Engineer, Research Scientist

Related on AIssential

• Tensorized algorithms and scalable filtering methods for hidden Markov and factorial hidden Markov models — Tensor algebra directly addresses fHMM computational complexity, enabling scalable time-series analysis without HMM reformulation.
• Tensor Train Diffusion: Leveraging Low-Rank Structures for High-Dimensional Score-Based Sampling — Tensor Train Diffusion efficiently samples high-dimensional distributions by solving HJB PDEs using low-rank functional tensor train approximations.
• Efficient frequent directions algorithms for approximate decomposition of matrices and higher-order tensors — New frequent directions algorithms enhance low-rank matrix and tensor approximations for efficiency and accuracy.
• Efficient Online Prediction for High-Dimensional Time Series via Joint Tensor Tucker Decomposition — TOPA-AAW offers efficient, accurate online prediction for high-dimensional streaming tensor time series via adaptive tensor factorization.
• Smoothness-Based Derandomization of PAC-Bayes Bounds — Derandomizing PAC-Bayes bounds for deterministic predictors leverages loss and predictor smoothness.
• Empirical Minimal-Realisation Compression of Deep Neural Networks via Controllability-Observability Tests — Deep neural network compression can be achieved by applying controllability-observability tests to identify and reduce redundant internal states.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.