A Polynomial - Order Algorithm for Optimal Phrase Sequence Selection From a Phrase Lattice and Its Parallel Layered Implementation

Kazuhiko OzekiCOLING 1990

TL;DR

This paper introduces a polynomial-time algorithm for selecting the optimal phrase sequence from a Japanese phrase lattice, simultaneously determining its dependency structure. This approach offers a more efficient and integrated solution for linguistic ambiguity resolution in speech recognition and natural language processing compared to traditional methods.

What Problem Does This Paper Address?

In Japanese language processing, particularly for speech recognition and word processing, a common challenge is resolving ambiguities arising from multiple possible phrase sequences within a "phrase lattice." A phrase lattice represents a set of potential phrases with varying start and end points. The goal is to select the single phrase sequence that forms the most linguistically acceptable sentence. Traditional methods that enumerate all possible combinations become computationally intractable due to their exponential complexity. This paper aims to tackle this problem by formulating it as a combinatorial optimization task and developing an efficient, polynomial-time algorithm.

Methods

The core of the paper's contribution lies in a dynamic programming approach to solve the combinatorial optimization problem. The authors define a "dependency structure" for Japanese sentences, where phrases modify each other. They introduce an "objective function" that combines a "global penalty" (P(X)) representing the linguistic acceptability of a dependency structure X, and a "reliability function" (S(X)) derived from the input phrase lattice.

The algorithm is built upon recurrence relations that recursively compute the minimum objective function value for subproblems. Specifically, they define opt(i,j;p) as the minimum objective function value for a dependency structure on phrases from index i to j, with the p-th phrase in the j-th set being the final phrase. opts(i,j;p) stores the actual dependency structure that achieves this minimum. The algorithm proceeds by filling a triangular matrix (tablel) with opt values and another (table2) with the corresponding optimal segmentation points and phrase indices.

The paper also discusses extensions to handle general phrase lattices (not just simple matrices) and proposes a parallel, layered implementation strategy. This implementation uses a 2D array of computing elements, where each element computes sub-problems, allowing for parallel processing and efficient computation.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic development and theoretical formulation rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Simultaneous Optimization: The algorithm finds the optimal phrase sequence and its dependency structure concurrently, which is a significant advantage for integrated linguistic analysis.
  • Polynomial Time Complexity: By framing the problem as dynamic programming, the authors achieve a polynomial-time solution, making it practical for real-world applications where exponential complexity is prohibitive.
  • Unified Objective Function: Combining linguistic acceptability (penalty) and input reliability (score) into a single objective function provides a robust criterion for selection.
  • Parallel and Layered Architecture: The proposed parallel implementation is well-suited for hardware acceleration (e.g., DSPs) and efficient computation, especially for large phrase lattices.
  • Generalizability: The core algorithm is presented for a simplified "phrase matrix" but is discussed as being extendable to more general phrase lattices, increasing its applicability.

Key Results

The paper presents a polynomial-order algorithm for optimal phrase sequence selection. While specific quantitative results (e.g., accuracy improvements or speedup percentages) are not detailed, the primary result is the development of an algorithm with a time complexity of O(M²N³) for phrase matrices (where M is the number of phrases per set and N is the number of sets) and O(M²N⁵) for general phrase lattices. The proposed parallel implementation is designed to leverage computational resources effectively.

Limitations and Future Work

  • Pair-wise Relation Limitation: The authors acknowledge that the current method only considers pair-wise relationships between phrases. This might lead to a broader class of acceptable sentences than what is linguistically preferred, suggesting that more sophisticated criteria might be needed.
  • Penalty Function Definition: The paper highlights that establishing a robust method for computing the "penalty" for phrase pairs is crucial and remains an area for further research. They suggest two potential approaches: deterministic (syntactic/semantic) and statistical (frequency-based).
  • General Dependency Structures: While the presented algorithm focuses on a specific type of dependency structure common in Japanese, the authors mention that it can be extended to handle more general dependency structures.
  • Hardware Implementation: The paper suggests that the parallel and layered structure is well-suited for LSI implementation, implying future work in hardware design.

Summary updated

BibTeX
@inproceedings{ozeki1990polynomial,
  author = {Kazuhiko Ozeki},
  title = {{A Polynomial - Order Algorithm for Optimal Phrase Sequence Selection From a Phrase Lattice and Its Parallel Layered Implementation}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1990},
}
Figure