Blackboard-based Dependency Parsing

TL;DR

This paper introduces a novel blackboard-based computational model for dependency parsing of Finnish, an inflectionally rich, free word-order language. By framing parsing as a search problem over partial dependency trees and employing a blackboard system to manage knowledge sources, the model effectively handles ambiguities and long-distance dependencies, demonstrating a practical implementation for Finnish.

What Problem Does This Paper Address?

Parsing free word-order languages like Finnish presents a significant challenge due to the flexible placement of words and the rich inflectional system, which encodes much of the grammatical information. Traditional parsing approaches often struggle with these complexities, particularly in accurately identifying long-distance dependencies and resolving ambiguities. The authors aim to develop a robust parsing system that can effectively model the structural relationships between words in such languages, moving beyond purely procedural or simple constraint-based methods.

Methods

The core of the paper is the proposal of a Blackboard-Based Dependency Parsing model. This approach frames parsing as a search problem within a "forest of partial dependency trees." The process is managed by a blackboard system, which acts as a central communication hub.

Key components of the model include:

  • Blackboard: Stores the active environment descriptions for "regents" (head words) and the partially built dependency trees.
  • Knowledge Sources: These are independent modules containing:
  • Functional Schemata: Describe local dependency environments for regents.
  • Binary Dependency Relations: Boolean expressions defining constraints for permitted dependencies between words.
  • Scheduler: Dynamically determines which knowledge source to apply at each step, guiding the incremental construction of partial solutions.

Parsing proceeds by matching functional schemata with the sentence's environment, using binary relation tests. As schemata are matched, partial dependency trees are built and linked on the blackboard. The system aims to find a complete parse tree covering the entire sentence. The model has been augmented to handle long-distance dependencies.

Datasets

Not discussed in the paper. The paper focuses on the computational model and its implementation for Finnish, but does not specify the datasets used for training or evaluation.

Key Insights and Ideas

  • Blackboard as a Central Hub: Using a blackboard system effectively decouples knowledge sources and allows for dynamic control of the parsing process, which is crucial for complex languages.
  • Parsing as Search: Framing parsing as a search problem in a forest of partial dependency trees provides a flexible framework for exploring possible syntactic structures.
  • Handling Free Word Order and Inflection: The model's ability to manage partial dependency trees and utilize rich binary dependency relations is key to its effectiveness with inflectionally rich, free word-order languages like Finnish.
  • Incremental Solution Building: The dynamic application of knowledge sources leads to the incremental generation of partial solutions, allowing the system to build up a complete parse step-by-step.

Key Results

The paper reports the implementation of a working parser for Finnish based on this model. The authors state that the parser is capable of solving ambiguities and long-distance dependencies. A specific example of parsing a sentence is provided, showing the partial dependency trees being built. The time taken for the example parse was 0.87 seconds on a VAX-11/751.

Limitations and Future Work

  • Computational Efficiency: While the example parse is relatively fast, the paper doesn't provide extensive performance benchmarks across a larger corpus, leaving room for further investigation into computational efficiency for larger-scale applications.
  • Generalizability: The model is specifically tailored for Finnish. Future work could explore its adaptability to other languages with similar or different linguistic properties.
  • Knowledge Source Design: The effectiveness of the system relies heavily on the quality and completeness of the functional schemata and binary dependency relations. Further research could focus on automated methods for acquiring or refining these knowledge sources.

Summary updated

BibTeX
@inproceedings{1987blackboard,
  title = {{Blackboard-based Dependency Parsing}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure