Advanced search


Joan-Andreu Sánchez, José-Miguel Benedí. Estimation of the probability distributions of stochastic context-free grammars from the k-best derivations. International Conference on Spoken Language Processing, 1998. pp. 2495-2498.

The use of the Inside-Outside (IO) algorithm for the estimation of the probability distributions of Stochastic Context-Free Grammars (SCFGs) in Natural-Language processing is restricted due to the time complexity per iteration and the large number of iterations that it needs to converge. Alternatively, an algorithm based on the Viterbi score (VS) is used. This VS algorithm converges more rapidly, but obtains less competitive models. We describe here a new algorithm that only considers the $k$-best derivations in the estimation process. The experimental results show that this algorithm achieves faster convergence than the IO and better models than the VS algorithm.