From Shallow to Deep Parsing Using Constraint Satisfaction

Jean-Marie Balfourier, Philippe Blache, Tristan van RullenCOLING 2002

TL;DR

This paper introduces "Property Grammars," a novel constraint-based formalism that allows for flexible parsing granularity within a single linguistic resource. This approach enables systems to switch between shallow chunking and deep syntactic analysis without needing separate grammars, offering a unified solution for applications like text-to-speech that require adaptable parsing depth.

What Problem Does This Paper Address?

Many Natural Language Processing (NLP) applications require syntactic analysis, but the depth of this analysis varies significantly. For instance, text-to-speech (TTS) systems often need shallow parsing to identify intonative phrases based on simple chunks. However, some constructions might benefit from a more detailed, deep syntactic analysis. Current approaches typically use distinct methods for shallow and deep parsing, requiring separate linguistic resources and making it difficult to integrate both levels of analysis within a single system. This paper addresses the challenge of creating a unified parsing framework that can adapt its granularity—from simple bracketing to complex phrase structure—using a single grammar.

Methods

The core of the paper is the introduction of Property Grammars, a constraint-based formalism. In this framework, all linguistic information is represented as constraints between linguistic objects. These constraints are categorized into types like linearity, dependency, obligation, exclusion, requirement, and uniqueness. The key innovation is that the parsing granularity is controlled by selecting which types of constraints are verified.

  • Shallow Parsing: This technique leverages a subset of constraints, primarily focusing on linearity, requirement, and exclusion, to identify hierarchical and grammatical information while maintaining robustness and efficiency. It can be seen as a bracketing technique.
  • Deep Parsing: This approach utilizes the entire set of constraints to build all possible syntactic structures for a sentence. It generates "edges" representing segments of the sentence and progressively combines them to form higher-level structures until no new edges can be created.

The parsing strategy itself is based on constraint satisfaction, allowing the system to verify either the full set of constraints or a subset thereof, thereby controlling the parsing depth.

Datasets

The paper mentions parsing a French corpus of 13,236 sentences from the newspaper Le Monde for complexity analysis. For evaluating the deep parser, a smaller corpus of 620 sentences from the same source was used. No new benchmarks were introduced; existing corpora were utilized for evaluation.

Key Insights and Ideas

  • Unified Linguistic Resource: The most significant insight is the ability to use a single grammar for both shallow and deep parsing. This drastically reduces the effort in developing and maintaining linguistic resources for systems that need flexible parsing capabilities.
  • Granularity Control via Constraint Selection: The paper demonstrates that controlling parsing depth is as simple as selecting which constraint types to enforce. This offers a principled and elegant way to adapt parsing to different application needs.
  • Characterization over Grammaticality: Property Grammars replace the strict notion of grammaticality with a more general concept of "characterization," which is the set of satisfied properties. This allows the system to handle both grammatical and ungrammatical inputs by describing their syntactic properties.
  • Potential for Text-to-Speech: The authors highlight the direct applicability of this approach to TTS systems, where a flexible parsing granularity can improve prosodic modeling and overall speech synthesis quality.

Key Results

The paper presents a qualitative comparison of the different parsing techniques using a French example sentence.

  • Chink/Chunk Approach: This shallow parsing method, inspired by Liberman and Church, provides a basic bracketing and segmentation. It's efficient but can make errors, such as misclassifying conjunctions as adverbial phrases.
  • Shallow Parsing with PG: This approach, using Property Grammars, offers a more hierarchical representation and better detection of syntactic boundaries compared to the basic chink/chunk method. Its complexity is polynomial.
  • Deep Parsing with PG: This method produces a detailed, hierarchical representation and can handle ambiguities like PP attachment. While theoretically exponential in worst-case complexity, its observed average complexity on corpora is polynomial (around $O(N^{2.4})$ where $N$ is the number of words).

The paper also discusses complexity, noting that while the deep parser has an exponential maximal complexity, its average complexity is polynomial, making it practical for many applications.

Limitations and Future Work

  • Complexity of Deep Parsing: The authors acknowledge that the maximal complexity of the deep parser is exponential. While average complexity is polynomial, handling extremely complex or ambiguous sentences might still be computationally intensive.
  • Combining Approaches: The paper suggests that combining or multiplexing different approaches (e.g., using shallow parsing for common boundaries and deep parsing for specific constructions) is a promising avenue for future research.
  • Parameterizing Granularity: The authors propose that future work could involve parameterizing the granularity by balancing the relative importance of different constraint types, allowing for even finer control over the parsing process.

Summary updated

BibTeX
@inproceedings{balfourier2002from,
  author = {Jean-Marie Balfourier and Philippe Blache and Tristan van Rullen},
  title = {{From Shallow to Deep Parsing Using Constraint Satisfaction}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}
Figure