A Treebank Query System Based on an Extracted Tree Grammar

Seth Kulick, Ann BiesNAACL 2010

TL;DR

This paper introduces an enhanced treebank query system that allows for more expressive searches by incorporating lexical information and the structure of how elementary syntactic trees are combined. This addresses limitations in previous work, enabling more nuanced comparisons of linguistic annotations and parser outputs.

What Problem Does This Paper Address?

Linguistic treebanks are invaluable resources for natural language processing research, but querying them effectively can be challenging. Previous approaches to treebank search, particularly those based on extracted "elementary trees" (small, lexicalized syntactic structures), had two significant limitations:

  1. Lack of Lexical Information: Queries couldn't specify properties of the words (tokens) within these elementary trees, such as their part-of-speech tags. This meant you couldn't ask for things like "find all verb phrases where the head word is a noun."
  2. Inability to Search Derivation Structure: Queries couldn't examine how these elementary trees were assembled to form the complete syntactic tree. This made it impossible to ask questions about attachment decisions, a crucial aspect for understanding disagreements between annotators or between human annotations and parser outputs.

The authors aim to overcome these limitations to enable more precise and insightful treebank analysis.

Methods

The core of the system relies on an extracted tree grammar, inspired by Tree Adjoining Grammar (TAG). Here's a breakdown of their approach:

  • Elementary Trees (Etrees): Full syntactic trees from a treebank are decomposed into smaller, lexicalized "elementary trees" (etrees). Each etree is associated with one or more tokens.
  • Derivation Tree: A separate structure, the "derivation tree," explicitly represents how these etrees are combined to reconstruct the original full tree. This is implemented using an adjacency list representation for efficient database storage.
  • Database Storage: The extracted etrees, their templates (recurrent structures), etree instances, and derivation trees are stored in a MySQL database with appropriate indexing.
  • Query Language: They introduce two types of queries:
  • Etree Queries: These focus on matching specific elementary tree structures, now enhanced to include:
  • Lexical Restrictions: The ability to specify conditions on tokens within the etree (e.g., "the head token must be a NOUN_NUM").
  • Derivation Tree Addresses (dta): The ability to mark specific nodes within an etree that will be referenced later in derivation tree searches.
  • Dtree Queries: These queries operate on the derivation tree, allowing users to specify relationships between etrees. For example, a query can ask for a parent-child relationship in the derivation tree where the parent etree matches one query and the child etree matches another.
  • Query Processing:
    1. Etree Template Matching: Queries are first matched against etree templates. Lexical restrictions are stored for later filtering.
  • Etree Instance Filtering: The system then finds actual etree instances that match the templates and filters them based on the stored lexical restrictions.
  • Dtree Reporting: Finally, dtree queries are used to report results based on the relationships between etree instances as defined in the derivation tree.

Datasets

  • Arabic Treebank (ATB): The system is demonstrated using data from the Arabic Treebank (specifically, Part 3, v3.1 - LDC2008E22).
  • Buckwalter Arabic Transliteration Scheme: Used for representing Arabic text.

No new benchmarks were introduced; the focus is on enhancing query capabilities over an existing treebank.

Key Insights and Ideas

  • Bridging the Gap: The most significant insight is the successful integration of both lexical information and derivation structure into a unified query system. This moves beyond simple structural matching to capture more semantic and relational aspects of syntactic analysis.
  • Derivation Tree as a First-Class Citizen: Representing and querying the derivation tree explicitly is crucial for understanding how syntactic structures are built and where disagreements might arise. This is particularly useful for analyzing attachment ambiguities.
  • Etree Templates for Efficiency: The concept of "etree templates" highlights the inherent redundancy in treebank structures and allows for a form of "normalization" in the database, improving efficiency.
  • Handling Arabic's "Construct State": The paper notes a specific linguistic phenomenon in Arabic ("construct state") that requires etrees to sometimes contain multiple anchors, demonstrating the system's adaptability to linguistic nuances.

Key Results

The paper describes the implementation and functionality of the system rather than presenting quantitative evaluation results. However, it demonstrates how the system can now perform queries that were previously impossible, such as:

  • Finding all ADVP elementary trees where the head is a specific part of speech.
  • Identifying verb frames with specific types of prepositional phrase (PP) attachments.
  • Pinpointing disagreements between annotators on attachment decisions by comparing two sets of trees.

The authors state that searching for etree instances with lexical restrictions is very efficient. Complex derivation tree searches are expected to be less so but are still considered manageable for typical local (parent, child, sister) relationships.

Limitations and Future Work

  • Limitations:
    • The derivation tree search, while functional, is noted as potentially less efficient than etree instance searching.
  • The paper mentions that the derivation tree representation is slightly simplified regarding the direction and order of attachment in sister-adjunction.
  • Future Work:
    • Integration with ATB Team: Closer collaboration with the Arabic Treebank team to ensure queries are practical and integrated into their workflow.
  • Query Specification: Further specification of how queries select etree templates, potentially leveraging localized search spaces for tasks like verb valency.
  • Performance Evaluation: Conducting a formal evaluation of the system's speed and comparing it to existing systems like Ghodke and Bird (2008) and Corpus Search.
  • Optimization: Making derivation tree searches more efficient by optimizing the search process to only consider relevant parts of the derivation tree.

Summary updated

BibTeX
@inproceedings{kulick2010treebank,
  author = {Seth Kulick and Ann Bies},
  title = {{A Treebank Query System Based on an Extracted Tree Grammar}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure