Learning a Concept Hierarchy from Multi-labeled Documents

Viet-An Nguyen, Jordan L. Boyd-Graber, Philip Resnik, Jonathan D. Chang

The Challenge of Noisy, Multi-Labeled Text

Probabilistic topic models like Latent Dirichlet Allocation (LDA) excel at discovering latent themes in text. However, they struggle to integrate human-provided labels when the label space is large (e.g., hundreds or thousands of tags). Most existing "labeled" topic models assume tags are independent, but in reality, labels are highly correlated. For instance, a document tagged with "Medicare" is almost certainly related to the broader category of "Health."

Furthermore, human tagging is notoriously noisy. Annotators often forget relevant tags or apply them inconsistently. This paper addresses the challenge of learning a meaningful, hierarchical structure from these noisy, multi-labeled datasets to improve search, browsing, and automated classification in massive text corpora.

Introducing L2H: Label to Hierarchy

To solve this, the authors introduce L2H (Label to Hierarchy), a model that combines hierarchical topic modeling with label supervision. By capturing the dependencies between labels and the words associated with them, the model becomes robust to missing human tags and significantly improves document modeling.

Graphical model of L2H

Key technical innovations of L2H include:

  • Concept Nodes & Topic Inheritance: Each node in the learned hierarchy represents a "concept," consisting of a user-generated label and a latent topic (a distribution over words). To model relationships, a child node’s topic is drawn from a Dirichlet distribution centered on its parent’s topic. This mimics "backoff" in language modeling, where specific terms (like "pedagogy") inherit the broader context of their parents ("education").
  • Candidate Set Expansion: To handle missing labels, L2H expands a document's observed labels into a "candidate set" that includes all ancestors in the tree. This allows the model to associate a document with a general category even if the human annotator only provided a specific sub-tag.
  • Stochastic Switching: The model uses a switching variable to decide whether a word should be generated from the relevant labels (the candidate set) or the remaining labels (the complementary set), providing a soft preference rather than a hard restriction.
  • Structure Learning: Unlike models that require a pre-defined taxonomy, L2H learns the tree structure itself using a Markov chain Monte Carlo (MCMC) algorithm. It iteratively refines which labels serve as parents based on both label co-occurrence and word usage.

Datasets and Key Results

The model was evaluated using data from GovTrack, comprising bill text and official policy area tags from the 109th through 112th U.S. Congresses (2005–2012). The datasets included roughly 12,000 to 14,000 bills and 200 to 400 unique labels per Congress.

Dataset statistics and perplexity results across Congresses
  • Lower Perplexity: In document modeling tasks (predicting held-out words), L2H significantly outperformed Labeled-LDA (L-LDA) and a flat version of the model (L2F). This proves that the hierarchical structure captures the data's underlying distribution more accurately.
  • Better Classification: When used as a feature extractor for multi-label classification, L2H features led to higher Macro-F1 and Micro-F1 scores than standard TF-IDF or Labeled-LDA features.
  • Qualitative Success: The hierarchy isn't just built on how often tags appear together; it's built on the content those tags describe. A political scientist noted that the model did an "excellent job" of capturing key distinctions in policy areas, such as separating traditional military issues from thematic policies like human rights.

Limitations and Future Work

While highly effective, L2H has a few limitations:

  • The Tree Constraint: Currently, L2H is restricted to a tree structure (one parent per node). In reality, many concepts are "poly-hierarchical" and might better fit a Directed Acyclic Graph (DAG) where a label can have multiple parents.
  • Scalability: Searching the space of all possible tree structures using MCMC is computationally expensive as the number of labels grows into the tens of thousands.
  • Human-in-the-loop: Future work could allow domain experts to "nudge" the hierarchy during the learning process to ensure the resulting taxonomy aligns with specific institutional needs.

Summary updated

Abstract

While topic models can discover patterns of word usage in large corpora, it is difficult to meld this unsupervised structure with noisy, human-provided labels, especially when the label space is large. In this paper, we present a model-Label to Hierarchy (L2H)-that can induce a hierarchy of user-generated labels and the topics associated with those labels from a set of multi-labeled documents. The model is robust enough to account for missing labels from untrained, disparate annotators and provide an interpretable summary of an otherwise unwieldy label set. We show empirically the effectiveness of L2H in predicting held-out words and labels for unseen documents.
BibTeX
@inproceedings{nguyen2014learning,
  author = {Viet-An Nguyen and Jordan L. Boyd-Graber and Philip Resnik and Jonathan D. Chang},
  title = {{Learning a Concept Hierarchy from Multi-labeled Documents}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure