TY - GEN
T1 - Production probability estimtors for context-free grammars
AU - Humenik, K.
AU - Pinkham, R. S.
N1 - Publisher Copyright:
© 1986 ACM.
PY - 1986/2/1
Y1 - 1986/2/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84915313273&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84915313273&partnerID=8YFLogxK
U2 - 10.1145/324634.325234
DO - 10.1145/324634.325234
M3 - Conference contribution
AN - SCOPUS:84915313273
T3 - Proceedings of the 1986 ACM 14th Annual Conference on Computer Science, CSC 1986
SP - 173
EP - 181
BT - Proceedings of the 1986 ACM 14th Annual Conference on Computer Science, CSC 1986
T2 - 1986 ACM 14th Annual Conference on Computer Science, CSC 1986
Y2 - 4 February 1986 through 6 February 1986
ER -