A Stochastic Parser Based on a Structural Word Prediction Model

Shinsuke Mori, Masafumi Nishimura, Nobuyasu Itoh, Shiho Ogino, Hideo WatanabeCOLING 2000

TL;DR

This paper introduces a novel stochastic parser for Japanese that models word prediction based on dependency structures rather than just sequential word order. By leveraging a finite-state model that considers the dependency relationships between words, the parser achieves state-of-the-art accuracy for Japanese dependency parsing.

What Problem Does This Paper Address?

Traditional statistical language models for parsers often rely on n-gram models, which consider only the local word sequence. However, human language understanding and sentence structure are heavily influenced by dependencies between words that can be distant in the sequence. This paper addresses the limitation of sequential models by proposing a parser that explicitly models these dependency relationships. The challenge lies in efficiently representing and learning these complex structural dependencies within a statistical framework, especially given the potential for data sparsity with longer-range dependencies.

Methods

The core of the paper is a stochastic language model based on dependency. Unlike traditional models, it treats sentence prediction word-by-word from left to right, but the "state" at each step is not just the preceding words, but a sequence of partial parse trees representing words whose modification is not yet complete.

Key methodological contributions include:

  • Dependency-based State Representation: The state is a sequence of partial parse trees, capturing the structural context of words that are awaiting their dependents.
  • Word Prediction from Partial Parse Trees: The model predicts the next word by considering the partial parse trees that have a dependency relation with it.
  • Finite State Model: The model is designed to be a finite-state model, inspired by psycholinguistic limits on short-term memory (7±2 items), which helps manage the complexity of states.
  • Lexicalization Algorithm: A novel algorithm is proposed to select which words to "lexicalize" (i.e., treat as distinct entities in the model) based on their impact on parsing accuracy on a held-out corpus. This addresses data sparsity by focusing on the most informative words.
  • Unknown Word Model: A character bi-gram model is incorporated to handle words not present in the training vocabulary.
  • Interpolation Technique: To combat data sparsity and improve generalization, the model interpolates seven different models with varying levels of generalization (from lexicon-based to POS-based to uniform distribution).

Datasets

The paper uses a corpus of 1,072 sentences from a financial newspaper for training and a separate set of 119 sentences from the same newspaper for testing. These sentences were excluded from the training data.

Key Insights and Ideas

  • Dependency is Key: The paper strongly suggests that explicitly modeling word dependencies, rather than just word order, is crucial for achieving high accuracy in parsing, especially for languages like Japanese where word order can be flexible.
  • Partial Parse Trees as State: Representing the model's state as a collection of partial parse trees is an effective way to capture the structural context needed for accurate prediction.
  • Selective Lexicalization is Powerful: Not all words need to be treated as unique entities. A data-driven approach to select which words to lexicalize significantly improves performance and combats sparsity, outperforming full lexicalization.
  • Psycholinguistic Inspiration: Grounding the model in psycholinguistic limits on memory provides a theoretical basis for the finite-state approach and helps manage model complexity.

Key Results

The selectively lexicalized parser achieved an accuracy of 89.9% for dependency relations, which was the highest obtained by any Japanese stochastic parser at the time of publication. This significantly outperformed a baseline model (linear structure, where each word depends on the next) which achieved 78.7% accuracy. The completely lexicalized model had the lowest cross-entropy, suggesting it might be the best language model for speech recognition, but the selectively lexicalized model was superior for parsing.

Limitations and Future Work

  • Data Sparsity: While addressed through lexicalization and interpolation, data sparsity remains a challenge, especially for languages with larger vocabularies or more complex sentence structures. The authors note that the accuracy tends to improve with larger corpora.
  • Generalization to Other Languages: The model is presented for Japanese. While the authors suggest it can be extended to other languages due to its dependency-based nature, further research would be needed to confirm this.
  • Criterion for Lexicalization: The paper uses parsing accuracy on a held-out corpus as the criterion for lexicalization. The authors suggest that for other applications (like speech recognition), a different criterion might be more appropriate.
  • Future Work: The authors imply that further exploration of lexicalization criteria and extending the model to other languages are promising directions. They also suggest that their model's psycholinguistic grounding makes it a strong candidate for further research.

Summary updated

BibTeX
@inproceedings{mori2000stochastic,
  author = {Shinsuke Mori and Masafumi Nishimura and Nobuyasu Itoh and Shiho Ogino and Hideo Watanabe},
  title = {{A Stochastic Parser Based on a Structural Word Prediction Model}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2000},
}
Figure