Hierarchical Voting Experts: An Unsupervised Algorithm for Segmenting Hierarchically Structured Sequences

Matthew Miller, Alexander StoytchevAAAI 2008

Abstract

Hierarchical Voting Experts (HVE) is an unsupervised algorithm designed to discover nested structures in sequences, such as characters forming words and words forming phrases. By recursively applying segmentation and introducing a "third expert" that utilizes higher-level patterns to refine lower-level boundaries, HVE significantly improves the accuracy of unsupervised sequence chunking. This paper details the HVE framework and demonstrates its effectiveness on both synthetic and natural language datasets.

Introduction

In fields ranging from linguistics to robotics, data often arrives as a continuous stream with an inherent, nested structure. Humans naturally "chunk" this information, perceiving phonemes as words and words as sentences. The original Voting Experts (VE) algorithm provided a breakthrough in unsupervised segmentation by using information-theoretic metrics—low internal entropy and high boundary entropy—to identify breaks in sequences. However, VE was limited to "flat" sequences and could not leverage higher-level patterns to resolve ambiguities at lower levels. Hierarchical Voting Experts (HVE) generalizes this framework to handle multiple layers, using "top-down" knowledge to improve "bottom-up" segmentation.

Methodology

The HVE framework extends the original VE algorithm through two primary mechanisms: recursive segmentation and the introduction of a third voting expert.

Recursive Segmentation

HVE first runs the standard VE algorithm on a sequence of tokens (e.g., characters) to produce initial "chunks." These chunks are then treated as unique tokens by imposing a lexicographical ordering. The algorithm is subsequently run on this new sequence of chunks to identify "chunks of chunks." This process can be repeated for any number of hierarchical levels.

The hierarchical structure of HVE, showing how sequences are grouped into Level 1 chunks and subsequently into Level 2 chunks.

The Third Voting Expert

The core innovation of HVE is the "third expert." In standard VE, two experts vote on potential split points within a sliding window: one minimizes internal entropy, and the other maximizes boundary entropy. HVE adds a third expert that consults a model built from the higher level of the hierarchy. If the current window contains a sequence recognized as a common chunk by the higher-level model, the third expert votes for a break at that location. This feedback loop allows higher-level structural knowledge to reinforce and refine lower-level segmentation.

Experimental Results

The researchers evaluated HVE using the first 35,000 words of George Orwell’s 1984. They tested the algorithm on a synthetic hierarchical dataset (mapping characters to random three-digit sequences) and the original base text.

Improved Accuracy and Efficiency

In synthetic tests, the addition of the third expert improved the Level 1 F-measure from 0.916 to 0.945 and the Level 2 F-measure from 0.734 to 0.756. On standard text, the third expert improved the "hit rate" of correct boundary placements from 0.797 to 0.818, demonstrating that higher-order models capture useful context even in non-synthetic data.

F-Measure performance comparison showing that HVE with a third expert consistently outperforms standard HVE across varying amounts of training data.

As shown in the figure above, the performance gap between standard HVE and the version with the third expert remains consistent as training data increases. Notably, the third expert provides a significant boost even when training data is limited.

Conclusion

HVE demonstrates that segmentation is not merely a bottom-up process; information about successful higher-level chunks is invaluable for refining lower-level boundaries. While the current model is batch-processed and sensitive to significant noise, it establishes a robust framework for unsupervised hierarchical learning. Future work will focus on developing an "online" version of HVE for real-time processing and applying the algorithm to more complex modalities such as audio and speech.

Summary updated

BibTeX
@inproceedings{miller2008hierarchical,
  author = {Matthew Miller and Alexander Stoytchev},
  title = {{Hierarchical Voting Experts: An Unsupervised Algorithm for Segmenting Hierarchically Structured Sequences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure