Overview
This paper introduces the Dependent Tree-Structured Stick-Breaking Process (dTSSBP), a novel framework for hierarchical clustering where both the tree structure and its parameters evolve over time. By combining nonparametric Bayesian methods with an efficient, parallelizable online inference scheme, the authors successfully model complex, shifting data—such as decades of scientific research and rapidly changing social media trends.
The Challenge of Dynamic Data
Real-world data is rarely static, and it naturally organizes into hierarchies. For example, scientific articles can be categorized under "Computer Science," which branches into "Machine Learning," and further into "Deep Learning."
However, most existing models force a compromise:
- Stationary Trees: These models capture hierarchy but remain frozen in time. They cannot account for the "birth" of new fields (like Genomics) or the "death" of obsolete terminology.
- Dynamic Flat Clusters: These models track clusters as they emerge and fade over time, but they lose the hierarchical relationships between them (e.g., failing to recognize that two new topics are sub-branches of the same parent category).
Combining hierarchical structure with temporal evolution is computationally demanding. The authors set out to create a scalable model that achieves both.
Methods: The dTSSBP Model
The authors build upon the Tree-Structured Stick-Breaking Process (TSSBP). Unlike many tree models that only assign data to "leaf" nodes, the TSSBP allows data to be assigned to internal nodes. For instance, a general paper about "Science" sits at the root, while a specific paper about "CRISPR" sits deep within a branch.
To handle dynamic data, the authors introduce several key innovations:
- Temporal Dependency: They transform the static TSSBP into a dependent version (dTSSBP). The probability of a data point falling into a specific branch at time $t$ is influenced by where data points fell in a previous "window" of time.
- Evolving Parameters: The "location" or definition of a cluster (e.g., the specific words defining a "Politics" topic) isn't fixed. It evolves via an auto-regressive process, allowing the meaning of a category to drift over time.
- Hybrid Inference: To maintain speed, the model uses a mix of Gibbs sampling (to assign data points to branches) and Maximum A Posteriori (MAP) estimation (to quickly update node parameters).
- Parallelization: The tree structure is exploited to update nodes in parallel. By alternating between odd-numbered and even-numbered depths, the algorithm ensures that simultaneously updated nodes are conditionally independent.
Datasets and Key Results
The model was evaluated on four distinct datasets to test its adaptability and accuracy:
- Synthetic Data: A manually created evolving tree with Gaussian-distributed clusters verified the algorithm's ability to recover "ground truth" changes.
- Twitter (NFL): Over 670,000 tweets containing NFL hashtags across 18 weeks, grouped into two-week epochs.
- PNAS Abstracts: Nearly 80,000 paper titles from the Proceedings of the National Academy of Sciences spanning 1915 to 2005.
- State of the Union (SoU): Presidential addresses from 1790 to 2002, broken into 21 ten-year epochs.
Key Insights
- The "Window" Effect: Using a sliding window of past observations allows the model to "remember" recent structures while remaining flexible enough to adapt to sudden data shifts.
- Internal Nodes Matter: Allowing the model to place general documents at higher levels of the tree prevents the "over-splitting" of broad topics.
- Fractal-like Behavior: The model's parameters ensure the distance between a parent and child node decreases deeper in the tree, stabilizing the variance of the "leaves" and making the root easier to identify.
Performance
- Quantitative Superiority: Across all real-world datasets, the dTSSBP achieved higher log-likelihoods on test sets compared to stationary tree models and non-hierarchical dynamic models.
- Capturing History: The model successfully "discovered" historical shifts. In the PNAS dataset, it tracked the mid-1970s surge in Immunology research. In the SoU data, it modeled the emergence of "Cold War" sub-topics branching off from general foreign policy.
- Efficiency: Despite its complexity, the inference scheme allowed trials to complete in under 20 minutes on a single processor core, with significant speedups when parallelized.
Limitations and Future Work
While powerful, the model has a few constraints. For real-world document experiments, tree depth was limited to 3 or 4 levels to maintain reasonable computation times; more complex hierarchies might require deeper structures. Additionally, to save memory, the model approximates a node's history by looking only at its immediate neighbors in the "Markov blanket." Finally, the current inference is designed strictly for online learning (looking forward)—a "backwards pass" to refine historical estimates based on future data was omitted due to computational costs.
Summary updated