MCMC for Hierarchical Semi-Markov Conditional Random Fields
This addresses a scalability bottleneck for researchers and practitioners working with large-scale nested sequential data, though it appears incremental as it builds on existing methods like Gibbs sampling and Rao-Blackwellisation.
The paper tackles the high computational cost of exact inference in hierarchical semi-Markov models for nested sequential data, proposing a new approximation technique that potentially reduces time complexity to sub-cubic in length and linear in depth, with some quality loss, as evaluated through simulations.
Deep architecture such as hierarchical semi-Markov models is an important class of models for nested sequential data. Current exact inference schemes either cost cubic time in sequence length, or exponential time in model depth. These costs are prohibitive for large-scale problems with arbitrary length and depth. In this contribution, we propose a new approximation technique that may have the potential to achieve sub-cubic time complexity in length and linear time depth, at the cost of some loss of quality. The idea is based on two well-known methods: Gibbs sampling and Rao-Blackwellisation. We provide some simulation-based evaluation of the quality of the RGBS with respect to run time and sequence length.