Abstract
This paper presents a novel unsupervised method for hierarchical topic segmentation. Lexical cohesion—the workhorse of unsupervised linear segmentation—is treated as a multi-scale phenomenon and formalized in a Bayesian setting. Each word token is modeled as a draw from a pyramid of latent topic models, where the structure of the pyramid is constrained to induce a hierarchical segmentation. Inference takes the form of a coordinate-ascent algorithm, iterating between two steps: a novel dynamic program for obtaining the globally-optimal hierarchical segmentation and collapsed variational Bayesian inference over the hidden variables. The resulting system is fast and accurate, and compares well against heuristic alternatives.
Introduction
Most automated text segmentation tools are "linear," identifying where one topic ends and another begins in a flat sequence. However, human discourse is naturally hierarchical: a book is composed of parts, which contain chapters, which are further divided into sections. The challenge in modeling this structure lies in the fact that different words signal boundaries at different scales. For instance, in a document about a city, the word "transportation" might provide global cohesion across a high-level section, while terms like "bus" or "metro" provide local cohesion within specific sub-sections.
This paper addresses the limitations of existing heuristic or supervised hierarchical methods by introducing HIERBAYES, an unsupervised, statistically grounded framework that captures this "multi-scale lexical cohesion."
The HIERBAYES Model
The core of the approach is a generative Bayesian model where each word in a document is generated from a pyramid of latent topic models.
In this pyramid model, high-level topics at the top cover large spans of text, while low-level topics at the base cover small, local segments. Every word token is assigned to a specific level in this pyramid. To prevent overfitting and reduce the search space, the model uses Bayesian marginalization, integrating out exact word distributions via a Dirichlet compound multinomial (DCM) distribution.
Inference and Optimization
To find the optimal segmentation, HIERBAYES employs a coordinate-ascent approach that iterates between two primary steps:
- Dynamic Programming: A novel $O(LT^3)$ algorithm (where $L$ is depth and $T$ is length) finds the globally optimal hierarchical boundaries based on current word-to-level assignments. To maintain efficiency for long texts, potential boundaries are restricted to sentence breaks.
- Collapsed Variational Bayes (CVB): This step updates the probability of a specific word belonging to a high-level versus a low-level topic.
Unlike "greedy" top-down systems that find chapters and then sections independently, HIERBAYES performs joint inference. By considering all levels of the hierarchy simultaneously, it prevents errors at the top level from propagating down and ruining lower-level segments.
Experimental Results
The model was evaluated on a medical textbook consisting of over 17,000 sentences organized into a three-level hierarchy (parts, chapters, and sections). The task was to recover these boundaries without prior training.
As shown in the results table, HIERBAYES achieved superior accuracy on the WindowDiff (WD) metric, a strict measure of boundary matching. While some greedy baselines (like GREEDY-BAYES) achieved competitive $P_k$ scores, they often suffered from creating spurious short segments. HIERBAYES maintained consistent, balanced performance across both chapter and section levels due to its global optimization and use of Markov priors to favor segments of expected lengths.
Conclusion
HIERBAYES demonstrates that treating lexical cohesion as a multi-scale phenomenon allows for the natural emergence of document hierarchies. While the model is highly effective, future work may involve incorporating explicit discourse markers (e.g., "however," "in conclusion") to improve segmentation at finer grains, such as the paragraph level, where word counts become sparse. Despite the $O(LT^3)$ complexity, the system remains practical for large documents when constrained to sentence-level boundaries.
Summary updated