Applying Grammar Induction to Text Mining

Andrew Salway, Samia TouilebACL 2014 · DOI

Abstract

Traditional text mining often struggles to balance scalability with semantic depth. While bag-of-words models are scalable but shallow, Information Extraction (IE) systems provide depth but lack portability. This paper presents an adaptation of the ADIOS grammar induction algorithm to automatically extract meaningful semantic structures from large, unannotated social media corpora. By focusing on local text snippets around specific key terms, the proposed method identifies structured patterns that capture the nuances of public discourse on complex topics like climate change.

Introduction

The explosion of social media content presents a challenge for researchers seeking to understand public sentiment and discourse. Current text mining techniques typically fall into two categories: shallow "bag-of-words" methods, which identify topic prevalence but fail to capture context, and deep Information Extraction (IE) systems, which are often domain-specific and expensive to develop.

To bridge this gap, we explore an unsupervised approach to "mine" information structures. Our goal is to develop a method that is both portable across domains and richer than simple keyword analysis, enabling social scientists to identify canonical statements and diverse perspectives within large-scale online debates.

Methodology

Our approach builds upon the Automatic Distillation of Structure (ADIOS) algorithm. ADIOS identifies two primary linguistic structures:

  • H-groups: Sequential patterns representing common phrases (e.g., "to combat [X]").
  • V-groups: Equivalence classes of words that are interchangeable within a specific slot (e.g., "[combat | fight | tackle]").

To adapt ADIOS for large-scale text mining, we introduced several key modifications:

  1. Key-Term Snippets: Instead of processing entire documents, we focus on small "snippets" or clauses surrounding specific key terms.
  2. Incremental Learning: The algorithm is presented with increasingly larger snippets (starting with a window of 2 words on either side of a term), focusing on the most immediate and meaningful linguistic context first.
  3. Iterative Substitution: Frequent and semantically tight patterns are identified and replaced with unique identifiers in each pass, allowing for the discovery of higher-level hierarchical structures.
  4. V-group Filtering: To reduce noise, we filter out H-groups containing overly large V-groups (more than 6 elements), which are often semantically nebulous.

Experimental Setup

The study utilized the NTAP blog corpus, consisting of approximately 1.4 million English-language blog posts from 3,000 different blogs related to climate change. We selected 17 domain-specific key terms for the experiment, ranging from high-frequency terms like "climate change" to lower-frequency terms like "emissions trading scheme."

Results and Discussion

The adapted ADIOS algorithm successfully induced complex, nested structures that elucidate semantic content. For instance, patterns describing the causes of global warming or predictions about sea-level rise were automatically extracted.

A critical finding was the efficiency of the snippet-based approach. Quantitative analysis, summarized in Table 1, demonstrates how the number of different H-groups and their total instances vary across different window sizes (i) and clause-based snippets. The data suggests that smaller snippets (i=2 or i=3) are particularly effective at generating a high volume of distinct patterns compared to larger fixed windows like i=4 or clauses-10.

Table 1: Number of different H-groups and total instances across various key terms and snippet sizes.

Beyond structural extraction, the method proved useful for:

  • Template Generation: Induced H-groups function as automatically generated IE templates (e.g., quantifying carbon taxes).
  • Sentiment and Belief Capture: V-groups naturally highlight polarized views (e.g., grouping "confuse," "mislead," and "educate" in discussions of public communication) without requiring pre-defined sentiment lexicons.
  • Synonym Discovery: The algorithm identifies near-synonyms based on distributional properties, which is valuable for query expansion.

Conclusion and Future Work

This research demonstrates that grammar induction can be effectively repurposed for text mining by focusing on local linguistic contexts. While the results are promising, several areas for future work remain. The current approach lacks a rigorous quantitative evaluation of recall, and the raw output often requires manual cleanup to merge logically related V-groups. Future research will investigate the sensitivity of ADIOS parameters and compare these structural patterns against standard n-gram language models to further refine the extraction process.

Summary updated

BibTeX
@inproceedings{salway2014applying,
  author = {Andrew Salway and Samia Touileb},
  title = {{Applying Grammar Induction to Text Mining}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2014},
  doi = {10.3115/v1/p14-2116},
}
Figure