Advanced search


Joan-Andreu Sánchez, José-Miguel Benedí. Probabilistic estimation of stochastic context-free grammars from the k-best derivations. VIII Simposium on Pattern Recognition and Image Analysis, 1999. pp. 7-8.

The use of the Inside-Outside (IO) algorithm for the estimation of the probability distributions of Stochastic Context-Free Grammars in Language Modeling is restricted due to the time complexity per iteration and the large number of iterations that it needs to converge. Alternatively, an algorithm which is based on the Viterbi Score (VS) can be used. This VS algorithm converges more rapidly, but obtains less competitive models. Here we describe a new algorithm that only considers the $k$-best derivations in the estimation process. We also report the experiments on a part of the Wall Street Journal task which was processed in the Penn Treebank project. The results show that this algorithm achieves faster convergence than the IO algorithm and achieves better models than the VS algorithm.