Humans naturally organize the world into hierarchies (e.g., Living Thing → Animal → Mammal → Dog). In AI and cognitive science, these structures are vital for reasoning and data compression. This paper introduces a generative probabilistic model for "annotated hierarchies"—structures that not only organize objects into a tree but also identify which specific levels of that tree best explain different features and relations. By combining Bayesian inference with efficient dynamic programming, the model can automatically discover interpretable, multi-level organizational structures from raw relational and attribute data.
The Core Concept: Annotated Hierarchies
Historically, two major gaps existed in hierarchical modeling:
- Learning vs. Engineering: Most hierarchical models were hand-engineered by experts rather than learned directly from data.
- Features vs. Relations: Existing models usually focused on "features" (properties of a single object, like "has fur") rather than "relations" (interactions between two objects, like "A is the parent of B").
The authors tackle the challenge of learning these hierarchies from scratch. Crucially, they recognize that different features "live" at different levels of a tree. For example, "has a heart" is a feature relevant at the high-level "Animal" node, while "is a Golden Retriever" is only relevant at a specific leaf node. An "annotated" hierarchy explicitly maps each feature or relation to its most appropriate level of abstraction.
How the Model Works
The authors propose a generative model that builds the hierarchy and its annotations simultaneously:
- The Tree ($T$): They define a prior over rooted, weighted binary trees where objects live at the leaves.
- Tree-Consistent (t-c) Partitions: This is the "secret sauce." A t-c partition is a way to slice the tree into disjoint categories. For any given feature, the model picks a partition that best explains the data. High-weight nodes in the tree are more likely to be chosen as part of a partition.
- Relational Extension: For relations (like kinship or interactions), the model partitions the pairs of objects. This results in a 2D grid-like partition of the relation matrix, where each block corresponds to a pair of nodes in the hierarchy.
- Inference: Learning the "best" tree is computationally hard because there are exponentially many ways to partition a tree. The authors use Markov chain Monte Carlo (MCMC) to search for the best tree structure. To make this efficient, they use dynamic programming to "sum out" (marginalize) all possible partitions for a given tree, allowing them to evaluate tree quality quickly.
Key Results Across Domains
The model was evaluated on three distinct types of data, demonstrating its versatility:
1. Object Features (Domain Discovery)
Tested on a dataset of 60 common objects and 100 features, the model perfectly recovered the four main domains (Animals, Food, Tools, Vehicles). More importantly, it correctly identified the scale of groupings. It learned that "is edible" is a feature of a broad category (Food), while "is juicy" applies specifically to the fruit subtree.
2. Biomedical Ontology (Relational Generalization)
Using data from the Unified Medical Language System (UMLS) consisting of 30 entities and 49 binary relations, the model discovered a hierarchy that outperformed standard non-hierarchical baselines like the Infinite Relational Model (IRM). By treating relations as 2D partitions of a tree, the model discovered that "Chemicals" (a high-level node) "cause" "Diseases" (another high-level node), effectively learning an ontology of interactions. It showed that while some relations (like "affects") are broad, others (like "analyzes") are highly specific to certain branches.
3. Social Structure (Kinship Relations)
Applied to a complex dataset of kinship terms from the Alyawarra tribe in Australia (64 individuals and their social ties), the model successfully recovered the four distinct kinship sections of the tribe. It further subdivided them by age and gender, proving it can handle highly structured, real-world social data.
Insights and Limitations
A major takeaway is the model's embodiment of the Bayesian Occam’s Razor. By marginalizing over all possible partitions during the search for the tree, the model naturally prefers simpler, more robust hierarchies that explain many features at once without overfitting.
However, the authors note several limitations for future work:
- Binary Constraints: The current model is designed for binary (true/false) data and needs extension to handle continuous variables.
- Strict Tree Structure: The model assumes data fits into a single, clean tree. Real-world data often has "factorial" structures (e.g., an object is defined by its species and its age and its gender simultaneously), which a single tree might struggle to represent.
- Computational Scaling: While dynamic programming helps, MCMC on large trees remains slow. Exploring particle filters for faster, online learning is a proposed next step.
Summary updated