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 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.
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