Production probability estimtors for context-free grammars

K. Humenik, R. S. Pinkham

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

This paper examines the problem of production probability estimation. The relative production probabilities of a nonterminal in a probabilistic context-free granular can sometimes be used to determine the most efficient parse. We shall examine the estimation of production probabilities of probabilistic context-free grammars. This will be done by generating random samples of strings using a probabilistic context-free grammar, and by using ratio estimators to estimate the production probabilities. It is shown that the problem becomes much less complex algebraically by introducing the theory of random walks and showing that a derivation in a m-nonterminal probabilistic context-free grarmmar is equivalent to a m-dimensional random walk. The main result of the paper shows that the biases and variances of all ratio estimators for any Chomsky Normal Form probabilistic context-free grammar are approximately directly proportional to n-1, when n is the size of the random sample. The estimators can be used to increase the efficiency of parsing strings in the language. The ability to parse strings efficiently is extremely useful in compiler theory and the theory of artificial intelligence.

Original languageEnglish
Title of host publicationProceedings of the 1986 ACM 14th Annual Conference on Computer Science, CSC 1986
Pages173-181
Number of pages9
ISBN (Electronic)0897911776, 9780897911771
DOIs
StatePublished - 1 Feb 1986
Event1986 ACM 14th Annual Conference on Computer Science, CSC 1986 - Cincinnati, United States
Duration: 4 Feb 19866 Feb 1986

Publication series

NameProceedings of the 1986 ACM 14th Annual Conference on Computer Science, CSC 1986

Conference

Conference1986 ACM 14th Annual Conference on Computer Science, CSC 1986
Country/TerritoryUnited States
CityCincinnati
Period4/02/866/02/86

Fingerprint

Dive into the research topics of 'Production probability estimtors for context-free grammars'. Together they form a unique fingerprint.

Cite this