MCMC for Hierarchical Semi-Markov Conditional Random fields

Truyen Tran, Dinh Phung, Svetha Venkatesh, Hung BuieSpace 2009

TL;DR

This paper introduces a novel MCMC approximation technique called Rao-Blackwellised Gibbs Sampling (RBGS) for Hierarchical Semi-Markov Conditional Random Fields (HSCRFs). RBGS aims to overcome the prohibitive cubic time complexity of exact inference in HSCRFs, enabling efficient analysis of long and deep sequential data.

What Problem Does This Paper Address?

Hierarchical Semi-Markov Conditional Random Fields (HSCRFs) are powerful models for nested sequential data, like text or DNA, where data has a hierarchical structure. However, exact inference in these models is computationally expensive, typically requiring cubic time in sequence length. This makes them impractical for large-scale, real-world applications. Existing methods either struggle with deep hierarchies or are still too slow. The authors aim to develop an approximation technique that is significantly faster while maintaining reasonable accuracy.

Methods

The core contribution is the Rao-Blackwellised Gibbs Sampling (RBGS) method. This technique combines two established ideas:

  • Gibbs Sampling: This is an MCMC method where variables are sampled one at a time, conditioned on the current values of all other variables. It's effective if the conditional distributions are easy to compute, but can be slow to converge.
  • Rao-Blackwellisation: This is a variance reduction technique that improves sampling efficiency by analytically integrating out some variables. If a joint distribution $P(v, h)$ can be decomposed, and the marginal $P(v) = \sum_h P(v, h)$ can be computed efficiently, sampling from $P(v)$ yields lower variance than sampling from $P(v, h)$.

In RBGS for HSCRFs, the authors propose to sample the transition variables (which indicate when a state transition occurs at each level) while analytically integrating out the state variables. This is possible because the HSCRF structure allows for efficient computation of the marginal distribution of transition variables. The integration over state variables is done using an efficient "walking-chain" approach, generalizing the forward-backward procedure.

Datasets

The paper uses simulated data generated from a Hierarchical Hidden Markov Model (HHMM) simulator. The experiments involve generating training and testing sequences with specific parameters and a defined topology (D=4, T=30, with varying state sizes for semantic levels). No new benchmark datasets are introduced.

Key Insights and Ideas

  • The Trade-off Between Complexity and Accuracy: The paper explicitly acknowledges that RBGS is an approximation method and that the price for faster inference is some degradation in accuracy. This is a common theme in MCMC methods for complex models.
  • Leveraging Model Structure for Efficiency: The nested structure of HSCRFs, where parent states only transition after child chains terminate, is crucial. This property allows the model to be viewed as a Markov tree under certain conditions, enabling efficient evaluation.
  • Rao-Blackwellisation as a Key Enabler: By integrating out the state variables, RBGS significantly reduces the sampling space and computational burden, making inference feasible for longer sequences.
  • "Walking-Chain" for Efficient Transition Sampling: The use of a walking-chain approach is highlighted as a way to efficiently obtain samples of the transition variables, avoiding a naive, computationally prohibitive summation over all possible state sequences.

Key Results

  • Speedup: RBGS demonstrates significant speed improvements over exact inference (Inside-Outside algorithm). The paper shows that RBGS can achieve linear run-time with respect to sequence length (O(T)) with a fixed number of iterations, or quadratic run-time (O(T²)) if the number of iterations scales linearly with T. This contrasts with the cubic complexity (O(T³)) of exact inference.
  • Accuracy: While RBGS introduces some loss of quality, the experiments show that it can achieve high accuracy in terms of maximal state marginals quickly (within 10 iterations). The KL-divergence and L1-norm difference between estimated and true marginals decrease over iterations, albeit slowly, indicating convergence towards the true distribution.
  • Scalability: The RBGS method scales much better with sequence length compared to exact inference, making it suitable for longer sequences.

Limitations and Future Work

  • Accuracy Degradation: The authors acknowledge that RBGS is an approximation and there is a loss of quality compared to exact inference. The paper focuses on demonstrating the speedup and acceptable accuracy for practical purposes.
  • MCMC Mixing Rate: The paper suggests that techniques to speed up the mixing rate of the MCMC sampler could further improve RBGS.
  • Stochastic Gradient Learning: RBGS could be combined with Contrastive Divergence for stochastic gradient learning, opening up possibilities for training deep HSCRFs.
  • Real-World Applications: The authors emphasize the need to test these ideas on real, large-scale applications with arbitrary length and depth to fully validate their effectiveness.

Summary updated

Abstract

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.
BibTeX
@inproceedings{tran2009mcmc,
  author = {Truyen Tran and Dinh Phung and Svetha Venkatesh and Hung Bui},
  title = {{MCMC for Hierarchical Semi-Markov Conditional Random fields}},
  booktitle = {eSpace},
  year = {2009},
}

Loading related content...

Figure