Stochastic Definite Clause Grammars

International Conference RANLP 2009 - Borovets, Bulgaria, pages 139–143 Stochastic Definite Clause Grammars Christian Theil Have Research group PLIS: Programming, Logic and Intelligent Systems Department of Communication, Business and Information Technologies Roskilde University, P.O.Box 260, DK-4000 Roskilde, Denmark cth@ruc.dk Abstract This paper introduces Stochastic Definite Clause Grammars, a stochastic variant of the well- known Definite Clause Grammars. The grammar formalism supports parameter learning from an- notated or unannotated corpora and provides a mechanism for parse selection by means of sta- tistical inference. Unlike probabilistic context- free grammars, it is a context-sensitive gram- mar formalism and it has the ability to model cross-serial dependencies in natural language. SDCG also provides some syntax extensions which makes it possible to write more compact grammars and makes it straight-forward to add lexicalization schemes to a grammar. 1 Introduction and background We describe a stochastic variant of the well-known Def- inite Clause Grammars [12], which we call Stochastic Definite Clause Grammars (SDCG). Definite Clause Grammars (DCG) is a grammar for- malism built on top of Prolog, which was developed by Pereira and Warren [12] and was based the principles from Colmerauers metamorphis grammars [6]. The grammars are expressed as rewrite rules which may include logic variables, like normal Prolog rules. DCG exploit Prologs unification semantics, which assures equality between different instances of the same logic- variable. DCG also allows modeling of cross-serial of dependencies, which is known to be beyond the capa- bility of context-free grammars [4]. In stochastic grammar formalisms such as proba- bilistic context-free grammars (PCFG), every rewrite rule has an associated probability. For a particular sentence, a grammar can produce an exponential number of derivations. In parsing, we are usually only interested in one derivation which best reflects the intended sentence structure. In stochas- tic grammars, a statistical inference algorithm can be used to find the most probable derivation, and this is a very successful method for parse disambiguation. This is especially true variants of PCFGs which condition rule expansions on lexical features. Charniak [3] re- ports that ”a vanilla PCFG will get around 75% preci- sion/recall whereas lexicalized models achieve 87-88% precision recall”. The reason for the impressive preci- sion/recall of stochastic grammars is that the proba- bilities governing the likelihood of rule expansions are normally derived from corpora using parameter esti- mation algorithms. Estimation with complete data, where corpus annotations dictate the derivations, can be done by counting expansions used in the annota- tions. Estimation with incomplete data can be ac- complished using the Expectation-Maximization (EM) algorithm [8]. In stochastic unification grammars, the choice of rules to expand is stochastic and the values assigned to unification variables are determined implicitly by rule selection. This means that in some derivations, instances of the same logic variable may get different values and unification will fail as result. Some of the first attempts to define stochastic uni- fication grammars did not address the issue of how they should be trained. Brew [2] and Eisele [9] tries to address this problem using EM, but …

Content truncated to 500 words