Deterministic Shift-Reduce Parsing for Unification-Based Grammars by Using Default Unification

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 603–611, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Deterministic shift-reduce parsing for unification-based grammars by using default unification Takashi Ninomiya Information Technology Center University of Tokyo, Japan ninomi@r.dl.itc.u-tokyo.ac.jp Takuya Matsuzaki Department of Computer Science University of Tokyo, Japan matuzaki@is.s.u-tokyo.ac.jp Nobuyuki Shimizu Information Technology Center University of Tokyo, Japan shimizu@r.dl.itc.u-tokyo.ac.jp Hiroshi Nakagawa Information Technology Center University of Tokyo, Japan nakagawa@dl.itc.u-tokyo.ac.jp Abstract Many parsing techniques including pa- rameter estimation assume the use of a packed parse forest for efficient and ac- curate parsing. However, they have sev- eral inherent problems deriving from the restriction of locality in the packed parse forest. Deterministic parsing is one of solutions that can achieve simple and fast parsing without the mechanisms of the packed parse forest by accurately choos- ing search paths. We propose (i) deter- ministic shift-reduce parsing for unifica- tion-based grammars, and (ii) best-first shift-reduce parsing with beam threshold- ing for unification-based grammars. De- terministic parsing cannot simply be ap- plied to unification-based grammar pars- ing, which often fails because of its hard constraints. Therefore, it is developed by using default unification, which almost always succeeds in unification by over- writing inconsistent constraints in gram- mars. 1 Introduction Over the last few decades, probabilistic unifica- tion-based grammar parsing has been investi- gated intensively. Previous studies (Abney, 1997; Johnson et al., 1999; Kaplan et al., 2004; Malouf and van Noord, 2004; Miyao and Tsujii, 2005; Riezler et al., 2000) defined a probabilistic model of unification-based grammars, including head-driven phrase structure grammar (HPSG), lexical functional grammar (LFG) and combina- tory categorial grammar (CCG), as a maximum entropy model (Berger et al., 1996). Geman and Johnson (Geman and Johnson, 2002) and Miyao and Tsujii (Miyao and Tsujii, 2002) proposed a feature forest, which is a dynamic programming algorithm for estimating the probabilities of all possible parse candidates. A feature forest can estimate the model parameters without unpack- ing the parse forest, i.e., the chart and its edges. Feature forests have been used successfully for probabilistic HPSG and CCG (Clark and Cur- ran, 2004b; Miyao and Tsujii, 2005), and its parsing is empirically known to be fast and accu- rate, especially with supertagging (Clark and Curran, 2004a; Ninomiya et al., 2007; Ninomiya et al., 2006). Both estimation and parsing with the packed parse forest, however, have several inherent problems deriving from the restriction of locality. First, feature functions can be de- fined only for local structures, which limit the parser’s performance. This is because parsers segment parse trees into constituents and factor equivalent constituents into a single constituent (edge) in a chart to avoid the same calculation. This also means that the semantic structures must be segmented. This is a crucial problem when we think of designing semantic structures other than predicate argument structures, e.g., syn- chronous grammars for machine translation. The size of the constituents will be exponential if the semantic structures are not segmented. Lastly, we need …

Content truncated to 500 words