##
Computation of Probabilities for an Island-Driven Parser

Anna Corazza, Renato De Mori, Roberto Gretter and Giorgio Satta

###
IEEE Trans. on Pattern Analysis and Machine Intelligence,

Vol. 13, No. 9, pp. 936-950, September 1991

Abstract
Island-driven parsers have interesting potential applications in
Automatic Speech Understanding (ASU). Most of the recently developed
ASU systems are based on an Acoustic Processor(AP) and a Language Processor(LP).
AP computes the a-priori probability of the acoustic data given a linguistic
interpretation. LP computes the probability of the linguistic interpretation.

This paper describes an effort to adapt island-driven parsers to handle
stochastic context-free grammars. These grammars could then be used as Language
Models (LM's) by
a LP to compute the probability of a linguistic interpretation.

Island-driven parsers applied to ASU are based on the idea of growing islands of recognized
words with an attempt to recognize new words at the edges of an island.

As different islands may compete for growing, it is important to compute the
probability that LM generates a sentence containing islands and gaps between them.
This probability can be used to score competing interpretation hypotheses.

Algorithms for computing these probabilities are introduced in this paper. The complexity
of these algorithms is analyzed both from theoretical and practical points of view.
It is shown that the computation of probabilities in the presence of gaps of unknown length
requires the impractical solution of a non-linear system of equations, while the
computation of probabilities for cases with gaps containing a known
number of unknown words has polynomial time complexity and is practically
feasible.

The use in ASU systems of the results obtained is discussed.