Learning for Deep Language Understanding

Smaranda MuresanIJCAI 2011 · OpenReview

Abstract

Deep language understanding requires mapping natural language sentences to formal logical representations, a task often hindered by the high cost of manual annotation and the computational complexity of expressive formalisms. This paper introduces polynomial-time algorithms for inducing Lexicalized Well-Founded Grammars (LWFGs). By leveraging a small set of "representative examples," these algorithms learn complex linguistic phenomena—such as tense, aspect, and negation—with high accuracy. Evaluation on the TSNLP benchmark demonstrates that this approach provides a computationally practical and data-efficient path toward deep semantic parsing.

Introduction

Deep language understanding involves more than identifying parts of speech; it requires mapping sentences to their underlying logical meanings. Traditional heavy-duty formalisms like HPSG or LFG are linguistically expressive but difficult to learn automatically without massive, manually annotated treebanks. Conversely, simpler models often lack the depth required for complex reasoning.

This research addresses this gap by providing tractable learning algorithms for LWFGs. These grammars offer a middle ground: they are expressive enough for deep understanding while maintaining a mathematical guarantee of learnability in polynomial time.

Methodology

The core of this approach lies in Lexicalized Well-Founded Grammars (LWFGs). The "well-founded" property implies a partial ordering of grammar rules, allowing the system to build complex structures from simpler "building blocks."

The paper introduces two primary algorithms:

  1. Ordered Learning (Algorithm 1): Assumes access to an ordered set of representative examples (from simplest to most complex) to learn and generalize rules.
  2. General Learning (Algorithm 2): A robust "theory revision" approach that does not require a predefined order. It iteratively learns, deletes, and refines rules from an unordered dataset until the grammar converges.
Algorithm 2: The General Learning approach for inducing LWFGs through theory revision.

Both algorithms utilize a Robust Parser as an innate inference engine. This parser decomposes sentences into "chunks" (syntagmas), helping the learner identify which parts of a new sentence are understood and which require the induction of a new grammar rule.

Experimental Setup

The approach was evaluated using a small training set consisting of 20 representative examples and 106 generalization examples derived from A Grammar of Contemporary English (Quirk et al., 1972). The system was then tested against the TSNLP (Test Suites for Natural Language Processing) benchmark, specifically designed to evaluate how well a grammar handles linguistic phenomena like Tense, Aspect, Modality, and Negation.

Key Insights and Results

One of the most significant findings is the proof that deep grammars can be induced in polynomial time, moving deep parsing from a theoretical exercise to a practical tool. Furthermore, the system demonstrates remarkable data efficiency, learning sophisticated rules from a minimal amount of fully annotated data.

Examples of the learned grammar rules and compositional constraints induced by the algorithm.

The induced grammar, consisting of only 20 rules, achieved impressive results on the TSNLP benchmark:

  • Tense, Aspect, and Modality: Correctly recognized all 157 positive examples and rejected all 38 ungrammatical ones.
  • Negation: Covered 288 out of 289 positive examples and successfully rejected all 129 negative examples.
  • Semantic Accuracy: The parser returned rich semantic molecules identifying mood, negation, tense, and semantic roles (e.g., identifying the "agent" in complex passive constructions).

Conclusion and Future Work

While the system is highly efficient, the representative examples currently require "deep" annotation (semantic molecules). Future work aims to mitigate this by developing more advanced annotation tools and exploring probabilistic extensions to handle ambiguity. Additionally, moving from "hard" semantic constraints to "soft" constraints via weighted ontologies could further enhance the model's flexibility. Ultimately, this work paves the way for scaling deep language understanding to new domains where large-scale annotated data is unavailable.

Summary updated

BibTeX
@inproceedings{muresan2011learning,
  author = {Smaranda Muresan},
  title = {{Learning for Deep Language Understanding}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=oMaOvvEIpkZ},
}
Figure