DFKI Research Report-01-02



Language: English

by Detlef Prescher

Inside-Outside Estimation Meets Dynamic EM

14 Pages


It is an interesting fact that most of the stochastic models used by linguists can be interpreted as probabilistic context-free grammars. In this paper, this result will be accompanied by the formal proof that the inside-outside algorithm, the standard training method for probabilistic context-free grammars, can be regarded as a dynamic-programming variant of the EM algorithm. Even if this result is considered in isolation this means that most of the probabilistic models used by linguists are trained by a version of the EM algorithm. However, this result is even more interesting when considered in a theoretical context because the well-known convergence behavior of the inside-outside algorithm has been confirmed by many experiments but it seems that it never has been formally proved. Furthermore, being a version of the EM algorithm, the inside-outside algorithm also inherits the good convergence behavior of EM. We therefore contend that the as yet imperfect line of argumentation can be transformed into a coherent proof.

This document is not yet available, we expect it from our Printer soon.

The next abstract is here, and the previous abstract is here.

DFKI-Bibliothek (bib@dfki.uni-kl.de)

Note: This page was written to look best with CSS stylesheet support Level 1 or higher. Since you can see this, your browser obviously doesn't support CSS, or you have turned it off. We highly recommend you use a browser that supports and uses CSS, and review this page once you do. However, don't fear, we've tried to write this page to still work and be readable without CSS.