Synchronous Dependency Insertion Grammars: A Grammar Formalism for Syntax Based Statistical MT

It is proved that DIG nevertheless has a generation capacity weakly equivalent to that of CFG, and a probabilistic extension of SDIG is introduced, which shows how such formalisms are linguistically motivated.

Abstract

This paper introduces a grammar formalism specifically designed for syntax-based statistical machine translation. The synchronous grammar formalism we propose in this paper takes into consideration the pervasive structure divergence between languages, which many other synchronous grammars are unable to model. A Dependency Insertion Grammars (DIG) is a generative grammar formalism that captures word order phenomena within the dependency representation. Synchronous Dependency Insertion Grammars (SDIG) is the synchronous version of DIG which aims at capturing structural divergences across the languages. While both DIG and SDIG have comparatively simpler mathematical forms, we prove that DIG nevertheless has a generation capacity weakly equivalent to that of CFG. By making a comparison to TAG and Synchronous TAG, we show how such formalisms are linguistically motivated. We then introduce a probabilistic extension of SDIG. We finally evaluated our current implementation of a simplified version of SDIG for syntax based statistical machine translation.