A Stochastic Parser Based on an SLM with Arboreal Context Trees

Shinsuke MoriCOLING 2002

TL;DR

This paper introduces a novel structured language model (SLM) for speech recognition that leverages "arboreal context trees" (ACTs) to flexibly reference syntactic history. This approach significantly improves parsing accuracy compared to previous SLMs with fixed history mechanisms, demonstrating the importance of flexible history referencing for robust language understanding.

What Problem Does This Paper Address?

Modern speech recognition systems are adept at transcribing spoken words, but understanding the meaning of that transcription remains a significant challenge. Traditional language models, like n-gram models, predict the next word based on a fixed sequence of preceding words. While effective for transcription, they don't inherently capture the underlying grammatical structure of a sentence. Structured Language Models (SLMs) aim to address this by predicting not just words but also their syntactic relationships, producing parse trees. However, existing SLMs, like n-gram models, often rely on a limited and fixed history of these syntactic structures, which can lead to data-sparseness issues and limit their predictive power. This paper tackles the problem of how to make SLMs more effective by introducing a more flexible way to utilize the syntactic history for prediction.

Methods

The core innovation in this paper is the Arboreal Context Tree (ACT). Unlike traditional context trees used for linear word sequences, ACTs are designed to handle tree-shaped histories, which are inherent to SLMs. An ACT allows the model to dynamically select which parts of the syntactic history are most relevant for predicting the next word and its associated structure. This is achieved by creating a tree-like data structure where nodes are labeled with subtrees of the history.

The authors then integrate this ACT mechanism into a Structured Language Model (SLM) for Japanese dependency grammar. In this SLM, the probability of a sentence is modeled as the product of probabilities of predicting each word and its associated partial parse tree. The ACT is used to classify the conditional parts of these probabilities, effectively making the history reference mechanism adaptive.

Finally, they propose a stochastic parser based on this SLM with ACTs. The parser aims to find the parse tree with the highest probability for a given sequence of words. It utilizes a Viterbi-like search algorithm, similar to those used in hidden Markov models, to efficiently find the best parse.

Datasets

The experiments were conducted using a corpus of articles from the Nihon Keizai Shinbun (a financial newspaper).

  • Training Data: 9,108 syntactically annotated sentences.
  • Testing Data: 1,011 sentences from the same newspaper.

Each sentence in the corpus was segmented into words, and each word was annotated with its part-of-speech (POS) and its dependency relationship.

Key Insights and Ideas

  • Flexible History is Key: The most significant insight is that a flexible mechanism for referencing syntactic history (ACTs) dramatically improves parsing accuracy over fixed history approaches in SLMs. This highlights that the structure of the past matters, but which parts of that structure matter can vary.
  • ACTs for Tree Structures: The paper successfully extends the concept of context trees, previously used for linear sequences, to handle the tree-structured histories of SLMs, demonstrating a novel way to manage complex dependencies.
  • SLMs for Language Understanding: The work reinforces the idea that SLMs are crucial for moving beyond simple transcription towards true language understanding, as they inherently capture grammatical structure.
  • Dependency Grammar Suitability: The paper shows that SLMs with ACTs are well-suited for dependency grammars, particularly for languages like Japanese where dependencies are directional and non-crossing.

Key Results

  • Improved Parsing Accuracy: The SLM-based parser with ACTs achieved a parsing accuracy of 92.8%. This is a significant improvement over a parser based on an SLM with a fixed history reference mechanism, which achieved 89.8%.
  • Outperforming Baseline: The ACT-based parser also significantly outperformed a baseline model where each word depends only on the next one (79.4% accuracy).
  • Bunsetsu-based Comparison: When compared to the state-of-the-art Japanese parser JUMAN+KNP on a bunsetsu (phrase) level, the authors' model showed comparable performance, though the difference was not statistically significant due to limitations in the experimental setup.

Limitations and Future Work

  • Lexicalization Focus: The current model's lexicalization is limited to grammatical function words due to data-sparseness issues with content words. The authors suggest that more efficient use of lexical information for content words could further improve accuracy.
  • Experimental Environment Differences: When comparing to JUMAN+KNP, differences in the test corpus size, the detail of POS tagging, and the absence of commercial dictionaries for KNP were noted as potential confounding factors.
  • Future Work: The authors imply that further model refinement, particularly in handling lexical information for content words, is a promising direction for future improvements. They also suggest that the word-level dependency output of their parser can be readily extended to other languages and integrated with existing post-parser processing systems.

Summary updated

BibTeX
@inproceedings{mori2002stochastic,
  author = {Shinsuke Mori},
  title = {{A Stochastic Parser Based on an SLM with Arboreal Context Trees}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2002},
}
Figure