TL;DR
This paper introduces a novel description language designed for both annotating and querying syntactically annotated corpora. It strikes a balance between traditional linguistic grammar formalisms and efficient query languages, enabling researchers to express complex linguistic phenomena and retrieve specific structures from treebanks.
What Problem Does This Paper Address?
Extracting meaningful information from syntactically annotated corpora, like the Penn Treebank, requires powerful query languages. Existing methods often fall into two camps: scripting languages that are difficult to manage for complex queries, or high-level grammar formalisms that can be computationally inefficient. The authors aim to bridge this gap by creating a language that is both linguistically intuitive and computationally tractable, allowing for the expression of complex syntactic structures and efficient retrieval. Specifically, they address the limitation of traditional tree structures in representing non-local dependencies like topicalization and extraposition, which require more flexible graph-based representations.
Methods
The paper proposes a description language that uses a graph-based representation for syntactic annotations, extending traditional trees with the possibility of "crossing edges." This allows for more natural representation of non-local dependencies. The language supports:
- Feature Records: For encoding morphosyntactic information (part-of-speech, case, gender, number) using typed, feature-based structures. Boolean formulas are allowed for feature values.
- Node Relations: A set of basic and derived relations to describe the structural relationships between nodes in the graph, including dominance and precedence with varying path lengths.
- Graph Descriptions: Restricted Boolean expressions (conjunction and disjunction, but no negation) over node relations to formulate queries.
- Types: A mechanism for defining type hierarchies to simplify queries, allowing for more abstract references to linguistic categories.
- Templates: A macro-like system for organizing complex queries into reusable units, promoting tractability and reusability.
The language is designed to be a compromise between linguistic expressiveness and computational efficiency, drawing inspiration from typed, feature-based grammar formalisms.
Datasets
The paper refers to existing syntactically annotated corpora such as the Penn Treebank, the NeGra corpus, and statistically disambiguated parses from Beil et al. (1999). No new datasets are introduced; rather, the language is designed to work with these existing resources.
Key Insights and Ideas
- Syntax Graphs for Non-Local Dependencies: The adoption of "syntax graphs" (trees with crossing edges) is a key innovation that allows for a more natural and simpler representation of phenomena like topicalization and extraposition, which are difficult to capture with pure tree structures.
- Bridging Linguistic Intuition and Computational Efficiency: The language successfully balances the need for linguistic expressiveness (making it understandable to linguists) with the demand for efficient query evaluation, a common challenge in corpus linguistics.
- Unified Language for Annotation and Querying: The proposed language serves a dual purpose: it can be used to encode the syntactic annotation itself and also to query that annotation, streamlining the workflow.
- Formal Semantics for Rigor: The paper emphasizes that the language comes with a formal and clear operational semantics, enabling a precise definition of the relationship between a corpus and a query, akin to a Prolog database and query.
Key Results
The paper presents the design of the description language and its components. It demonstrates how the language can be used to formulate queries for specific linguistic structures, such as retrieving proper nouns or verbs with their complements. An example of automatically generated corpus annotation code for a simple sentence is provided, showcasing the language's application in practice. The implementation is described as being developed in Java to support popular platforms.
Limitations and Future Work
- Restrictions for Corpus Annotation: When used for corpus annotation (as opposed to querying), the language has several restrictions: only basic node relations, conjunction as the sole logical connective, no regular expressions, and no types or templates. This is to ensure tractability for the annotation process.
- Future Work: The authors mention the long-term goal of retrieving co-indexed substructures (co-reference phenomena) and the development of a domain-specific implementation of the search engine for optimizations specific to linguistic applications. They also highlight the need for a preprocessing tool to convert existing corpus formats (like NeGra, Penn Treebank, or XML) into their description language format for query evaluation.
Summary updated