Rule extraction for multi bottom-up tree transducers

Abstract

Following the invention of computers, it was always a dream to obtain translations automatically. If we give a machine a sentence it should return a sentence in another language expressing the same meaning.In the subfield of statistical machine translation (SMT), this translation is achieved with the help of statistical models. Those models use large text collections to automatically learn basic translation units that model the translation from a source sentence into a target sentence. The basic translation units can be single words or phrases consisting of multiple words. Other approaches, called syntax-based SMT, use rules of some formal grammar as their basic translation units. Syntax-based SMT systems easily allow the use of linguistic annotations. Rules can contain nonterminal symbols which can encode linguistic annotations. Furthermore, one can decide whether such annotations are used for both the source and target language, for one language only, or if those annotations are excluded alltogether. The integration of linguistic annotations yielded mixed results. In some cases translation quality significantly improves whereas in others it seems to hurt coverage and thus overall translation quality. While the use of annotations for both languages generally did not result in good translation quality, the use for one language only showed improvements. However, the best results are often obtained by a syntax-based SMT system that excludes all linguistic annotations. The underlying formal grammars vastly vary with respect to their expressive power. Synchronous context-free grammars are widely used but more powerful formalisms like synchronous tree substitution grammars or local multi bottom-up tree transducers (lMBOT) have also been proposed for translation. In this thesis, we introduce a translation model that is based on lMBOTs. Our work focuses on automatically learning the basic translations units for lMBOTs with varying linguistic annotations. We implemented an already existing algorithm that extracts the minimally required basic translation units for an lMBOT model with linguistic annotations for both the source and the target language. Furthermore, we present three implementations of algorithms which extract more than the minimally required basic translation units. These algorithms are designed for lMBOT models with (1) linguistic annotations on both sides, (2) linguistic annotations for the target language, and (3) no linguistic annotations at all. For all lMBOT models, we present an evaluation in terms of translation quality. In addition, we conduct various analyses that illuminate certain positive aspects of an lMBOT system and we explain the impact of these aspects to SMT.

Auf die Erfindung des Computers folgte der Traum, Übersetzungen automatisch zu erhalten. Wenn man einer Maschine einen Satz gibt, soll sie einen Satz in einer anderen Sprache ausgeben, der weiterhin die ursprüngliche Bedeutung hat. In der Teildisziplin der statistischen maschinellen Übersetzung (SMÜ) wird die Übersetzung mit Hilfe statistischer Modelle erreicht. Diese Modelle benutzen große Textsammlungen, um automatisch die Übersetzungseinheiten zu lernen, die die Übersetzung eines Quellsatzes in einen Zielsatz modellieren. Die Übersetzungseinheiten können einzelne Wörter sein oder Phrasen, die aus mehreren Wörtern bestehen. Andere Ansätze, syntax-basierte SMÜ genannt, benutzen Regeln einer formalen Grammatik als ihre Übersetzungseinheiten. Syntax-basierte SMÜ-Systeme erlauben auf einfache Weise das Benutzen von linguistischen Annotationen. Regeln können Nichtterminalsymbole enthalten, welche linguistische Annotationen kodieren können. Linguistische Annotationen können wahlweise für die Quell- und Zielsprache verwendet werden oder nur für eine der beiden Sprachen. Es ist auch möglich, gar keine linguistischen Annotationen zu benutzen. Das Einbinden linguistischer Annotationen führte zu gemischten Ergebnissen. In manchen Fällen wurde die Übersetzungsqualität erheblich verbessert, während in anderen Fällen eine Verschlechterung beobachtet wurde. Das Einbinden von linguistischen Annotationen für Quell- und Zielsprache zeigt generell keine gute Übersetzungsqualität, für das Einbinden für nur eine Sprache hingegen sind Verbesserungen bestätigt worden. Die besten Ergebnisse liefern jedoch meistens syntax-basierte SMÜ-Systeme ohne linguistische Annotationen. Die zugrundeliegenden formalen Grammatiken variieren stark im Hinblick auf ihre Mächtigkeit. Weitestgehend werden synchrone kontext-freie Grammatiken verwendet, aber auch mächtigere Formalismen wie Baumsubstitutionsgrammatiken oder lokale, aufsteigende Mehrfachbaumübersetzer (lMBOT) wurden für die Übersetzung vorgeschlagen. In dieser Arbeit stellen wir ein Übersetzungsmodell basierend auf lMBOTs vor. Unsere Arbeit konzentriert sich auf das automatische Lernen der Übersetzungseinheiten für lMBOTs mit variierenden linguistischen Annotationen. Wir haben einen zuvor vorgeschlagenen Algorithmus implementiert, der das Minimum an benötigten Übersetzungseinheiten für ein lMBOT-Modell mit linguistischen Annotationen für die Quell- und Zielsprache extrahiert. Desweiteren präsentieren wir drei Algorithmen, welche in der Lage sind, sinnvolle zusätzliche Übersetzungseinheiten zu extrahieren. Diese Algorithmen sind auf lMBOT-Modelle mit (1) linguistischen Annotationen für Quell- und Zielsprache, (2) linguistischen Annotationen auf der Zielsprache und (3) keinerlei linguistischen Annotationen zugeschnitten. Für jedes unserer lMBOT-Systeme präsentieren wir eine Auswertung bezüglich der Übersetzungsqualität. Zusätzlich stellen wir verschiedene Analysen vor, die bestimmte positive Aspekte eines lMBOT-Modells beleuchten und aufzeigen, wie SMÜ von diesen Aspekten profitieren kann.