  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.
