Computation of Upper-Bounds for Stochastic Context-Free Languages

Anna Corazza, Renato de Mori, Giorgio SattaAAAI 1992

Abstract

This paper presents a mathematical framework for calculating optimal upper bounds on the probability of the most likely derivation in Stochastic Context-Free Grammars (SCFGs). By decoupling grammar-specific analysis from real-time string processing, the authors enable efficient, admissible $A^*$ search for speech understanding systems. This approach supports diverse parsing strategies, including left-to-right and island-driven recognition, by providing tight heuristics that minimize search space exploration.

Introduction: The Search for Efficient Speech Understanding

In the early 1990s, speech technology development diverged into two primary objectives: Automatic Speech Recognition (ASR), focused on identifying the most likely word sequence, and Automatic Speech Understanding (ASU), which seeks the most likely grammatical interpretation or "derivation" of an utterance.

The computational cost of searching through all possible grammatical structures for a given audio signal is prohibitive. To mitigate this, the $A^*$ search algorithm is employed, requiring a "heuristic function" to estimate the maximum possible score a partial sentence might achieve upon completion. The effectiveness of $A^*$ depends on this estimate being an "admissible" upper bound—tight enough to prune the search space effectively without ever underestimating the true maximum. This paper addresses the challenge of computing these optimal upper bounds efficiently for SCFGs.

Methodology: Two-Stage Probability Computation

The proposed framework splits the computation into an off-line grammar analysis and an on-line string processing stage.

Off-line Grammar Analysis

Before processing any speech, the system analyzes the SCFG to calculate the maximum probability that any non-terminal symbol (e.g., a "Noun Phrase") can derive any terminal string or a string containing a "gap." Using a dynamic programming approach similar to the CYK algorithm, the system populates four primary arrays:

  • $M_g[i]$: Max probability of non-terminal $H_i$ deriving any terminal string.
  • $L_p[i,j], L_s[i,j], L_i[i,j]$: Max probabilities for prefix, suffix, and "island" (middle-out) derivations involving non-terminals $H_i$ and $H_j$.
Visual representation of off-line grammar-specific probability arrays $M_g, L_p, L_s,$ and $L_i$.

On-line String Processing

During real-time recognition, as a word sequence $u$ is identified, the system utilizes the pre-calculated grammar values to rapidly determine the upper bound for the complete sentence. The framework calculates the best way to integrate $u$ into a full derivation, whether it serves as a prefix, a suffix, or an internal "island."

On-line string-specific probability calculations for a word sequence $u$ in various derivation contexts.

The core innovation lies in optimizing for the "best derivation" (the Viterbi path) rather than the sum of all possible derivations. This distinction makes the computation of tight heuristics mathematically and computationally feasible.

Key Insights and Theoretical Contributions

  • ASU vs. ASR Scoring: The authors argue that for speech understanding, the single most likely derivation tree is the relevant metric. Finding the maximum of a set in probabilistic grammars is often more computationally tractable than calculating the sum, which is required for ASR-style language modeling.
  • Optimality of the Heuristic: The paper proves that the proposed scoring functions provide the tightest possible upper bounds. In $A^*$ search theory, a tighter bound ensures that the algorithm explores the absolute minimum number of nodes required to find the optimal solution.
  • Island-Driven Flexibility: Unlike traditional left-to-right parsers, this framework explicitly supports "island-driven" parsing. This allows a system to begin recognition from a clearly identified word in the middle of a noisy signal and expand the interpretation outwards.
  • Complexity Management: By offloading grammar analysis to a pre-processing step, the on-line computational cost is kept to $O(|u|^3)$, matching the complexity of standard Viterbi-style CYK recognizers.

Conclusion

The authors demonstrate that while ASR-style scoring (summing probabilities) presents significant computational hurdles for real-time systems, ASU-style scoring (finding the maximum) is highly feasible. The provided framework offers a mathematically rigorous way to generate optimal heuristics for $A^*$ search, significantly improving the efficiency of speech understanding systems without sacrificing accuracy.

Summary updated

BibTeX
@inproceedings{corazza1992computation,
  author = {Anna Corazza and Renato de Mori and Giorgio Satta},
  title = {{Computation of Upper-Bounds for Stochastic Context-Free Languages}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure