Paper: The Problem Of Computing The Most Probable Tree In Data-Oriented Parsing And Stochastic Tree Grammars

ACL ID E95-1015
Title The Problem Of Computing The Most Probable Tree In Data-Oriented Parsing And Stochastic Tree Grammars
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1995
Authors
  • Rens Bod (University of Amsterdam, Amsterdam The Netherlands)

We deal with the question as to whether there exists a polynomial time algorithm for computing the most probable parse tree of a sentence generated by a data-oriented parsing (DOP) model. (Scha, 1990; Bod, 1992, 1993a). Therefore we describe DOP as a stochastic tree-substitution grammar (STSG). In STSG, a tree can be generated by exponentially many derivations involving different elementary trees. The probability of a tree is equal to the sum of the probabilities of all its derivations. We show that in STSG, in contrast with stochastic context-free grammar, the Viterbi algorithm cannot be used for computing a most probable tree of a string. We propose a simple modification of Viterbi which allows by means of a "select-random" search to estimate the most probable tree of a string in polynom...