Hierarchical Semi-Markov Conditional Random Fields for Recursive Sequential Data

Tran The Truyen, Dinh Q. Phung, Hung Hai Bui, Svetha Venkatesh

Abstract

This paper introduces the Hierarchical Semi-Markov Conditional Random Field (HSCRF), a discriminative framework designed to model complex, nested structures in sequential data. By combining the hierarchical depth of Hidden Markov Models with the feature-rich flexibility of Conditional Random Fields, the HSCRF addresses the limitations of cascaded models and generative hierarchical models. We present an efficient Asymmetric Inside-Outside (AIO) algorithm for inference and demonstrate the model's superior performance in human activity recognition and natural language processing, even under conditions of partial supervision.

Introduction

Many real-world sequences, from human activities to natural language, are inherently hierarchical. A high-level activity like "preparing a meal" is composed of sub-activities like "washing vegetables," which are further broken down into primitive movements. Traditionally, these sequences were modeled using cascaded approaches, which suffer from error propagation, or generative models like Hierarchical Hidden Markov Models (HHMMs), which struggle to incorporate long-range, overlapping features.

The Hierarchical Semi-Markov Conditional Random Field (HSCRF) is proposed as a "best of both worlds" solution. It represents hierarchical dependencies jointly to avoid cascading errors while remaining discriminative, focusing only on the labels given the data to allow for rich, complex feature sets.

Methods

The HSCRF architecture is built upon several core innovations:

  • Hierarchical Structure: The model consists of $D$ levels where a state at level $d$ embeds a child Markov chain at level $d+1$. This nesting continues until the production level at the bottom. This allows the model to represent recursive structures explicitly.
  • Semi-Markov Property: Unlike standard CRFs that transition at every time step, the semi-Markov nature allows states to persist for a duration, making it ideal for modeling segments like a 30-second sub-activity.
  • Shared Topology: To prevent parameter explosion, the model allows different parent states to share the same child states (e.g., "making breakfast" and "making lunch" might both share a "wash dishes" sub-activity).
Figure 1: Hierarchical state structure showing nested Markov chains within parent states A and B.

To make learning and inference efficient, the authors developed a generalized Asymmetric Inside-Outside (AIO) Algorithm. This algorithm handles the shared topology and enables the model to learn from partially labeled data, where only certain levels of the hierarchy are annotated. To ensure stability during long sequences, a numerical scaling procedure is implemented to prevent overflow.

Figure 2: The computational trellis structure used by the Asymmetric Inside-Outside algorithm for efficient inference.

Experiments and Results

The HSCRF was evaluated on two distinct domains:

  1. Human Activities of Daily Living (ADLs): Using a dataset of 90 indoor surveillance sequences, the HSCRF achieved 100% accuracy at the complex activity level and 93.9% at the sub-trajectory level. It significantly outperformed Dynamic CRFs (DCRFs) and flat CRFs. Notably, the model remained robust to missing labels, maintaining 80.2% accuracy even with only 50% supervision.
  2. Noun-Phrase (NP) Chunking: On the CoNLL-2000 shared task, the HSCRF consistently outperformed standard CRFs. When Part-of-Speech (POS) tags were provided at test time, the model's F1-score improved, demonstrating its ability to leverage bottom-level constraints to refine higher-level phrase detection.

Discussion and Conclusion

The success of the HSCRF stems from its discriminative power and joint inference. By modeling all levels together, the top-down and bottom-up information flow helps resolve ambiguities that would baffle a layered or flat model. Furthermore, the ability to use features like "average velocity" over an entire segment provides a significant advantage over generative counterparts.

While the model currently faces a cubic time complexity ($O(T^3)$), making it expensive for extremely long sequences, it represents a significant step forward in modeling recursive sequential data. Future work will focus on approximation methods to reduce computational overhead and extending the model to handle non-recursive, purely sequential transitions more gracefully.

Summary updated

BibTeX
@inproceedings{truyen2008hierarchical,
  author = {Tran The Truyen and Dinh Q. Phung and Hung Hai Bui and Svetha Venkatesh},
  title = {{Hierarchical Semi-Markov Conditional Random Fields for Recursive Sequential Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
  url = {https://openreview.net/forum?id=B1bgc_Zd-S},
}
Figure