A joint translation model with integrated reordering

Abstract

This dissertation aims at combining the benefits and to remedy the flaws of the two popular frameworks in statistical machine translation, namely Phrase-based MT and N-gram-based MT.

Phrase-based MT advanced the state-of-the art towards translating phrases than words. By memorizing phrases, phrasal MT, is able to learn local reorderings, and handling of other local dependencies such as insertions, deletions etc. Inter-phrasal reorderings are handled through the lexicalized reordering model, which remains the state-of-the-art model for reordering in phrase-based SMT till date. However, phrase-based MT has some drawbacks:

• Dependencies across phrases are not directly represented in the translation model • Discontinuous phrases cannot be represented and used • The reordering model is not designed to handle long range reorderings • Search and modeling problems require the use of a hard reordering limit • The presence of many different equivalent segmentations increases the search space • Source word deletion and target word insertion outside phrases is not allowed during decoding

N-gram-based MT exists as an alternate to the more commonly used Phrase-based MT. Unlike Phrasal MT, N-gram-based MT uses minimal translation units called as tuples. Using minimal translation units, enables N-gram systems to avoid the spurious phrasal segmentation problem in the phrase-based MT. However, it also gives up the ability to memorize dependencies such as short reorderings that are local to the phrases. Reordering in N-gram MT is carried out by source linearization and POS-based rewrite rules. The search graph for decoding is constructed as a preprocessing step using these rules. N-gram-based MT has the following drawbacks:

• Only the pre-calculated orderings are hypothesized during decoding • The N-gram model can not use lexical triggers • Long distance reorderings can not be performed • Unaligned target words can not be handled • Using tuples presents a more difficult search problem than that in phrase-based SMT

In this dissertation, we present a novel machine translation model based on a joint probability model, which represents translation process as a linear sequence of operations. Our model like the N-gram model uses minimal translation units, but has the ability to memorize like the phrase-based model. Unlike the “N-gram” model, our operation sequence includes not only translation but also reordering operations. The strong coupling of reordering and translation into a single generative story provides a mechanism to better restrict the position to which a word or phrase can be moved, and is able to handle short and long distance reorderings effectively. This thesis remedies the problems in phrasal MT and N-gram-based MT by making the following contributions:

• We proposed a model that handles both local and long distance dependencies uniformly and effectively • Our model is able to handle discontinuous source-side units • During the decoding, we are able to remove the hard reordering constraint which is necessary in the phrase-based systems • Like the phrase-based and unlike the N-gram model, our model exhibits the ability to memorize phrases • In comparison to the N-gram-based model, our model performs search on all possible reorderings and has the ability to learn lexical triggers and apply them to unseen contexts

A secondary goal of this thesis is to challenge the belief that conditional probability models work better than the joint probability models in SMT and that the source-side context is less helpful in the translation process.

Diese Dissertation setzt sich zum Ziel, die Vorteile der beiden populärsten Methoden in der statistische maschinellen Übersetzung, nämlich der phrasenbasierten Übersetzung und der N-Gramm-basierten Übersetzung zu kombinieren und ihre Nachteile zu vermeiden.

Phrasenbasierte maschinelle Übersetzung (PBMÜ) erzielte eine zuvor unerreichte Genauigkeit, indem ganze Wortfolgen (genannt Phrasen) statt einzelner Wörtern übersetzt werden. Durch Abspeicherung von phrasalen Übersetzungen ist PBMÜ in der Lage, lokale Umordnungen zu lernen wie auch die Behandlung anderer lokaler Abhängigkeiten, die bei Einfügungen und Löschungen auftreten. Phrasenübergreifende Umordnungen werden mit Hilfe des lexikalisierten Umordnungsmodelles behandelt, das im Bereich der PBMÜ nach wie vor Stand der Technik ist. PBMÜ hat jedoch einige Nachteile:

• Abhängigkeiten zwischen Phrasen werden nicht direkt im Modell repräsentiert. • Diskontinuierliche Phrasen können nicht repräsentiert und verwendet werden. • Das Umordnungsmodell ist ungeeignet für die Behandlung von Umordnungen über weite Distanzen. • Probleme bei der Modellierung und Suche erfordern eine harte maximale Grenze für die Umordnungsdistanz. • Die Existenz vieler verschiedener äquivalenter Segmentierungen lässt den • Suchraum anwachsen. • Die Löschung von Wörtern im Ausgangssatz und die Einfügung von Wörtern in der Übersetzung ist nur innerhalb von (größeren) Phrasen erlaubt.

N-Gramm-basierte maschinelle Übersetzung (NGMÜ) stellt eine Alternative zu der weiter verbreiteten phrasenbasierten Übersetzung dar. Im Gegensatz zur PBMÜ verwendet die NGMÜ minimale Übersetzungseinheiten, die “Tupel” genannt werden. Dadurch vermeidet die NGMÜ das Problem der PBMÜ mit vermeintlichen Ambiguitäten in der Segmentierung. Allerdings verliert es damit auch die Fähigkeit, lokale Abhängigkeiten bei Umordnungen über kurze Distanzen mit Hilfe der Phrasen abzuspeichern. Die Umordnung erfolgt in der NGMÜ mit Wortart-basierten Umordnungsregeln. Der Suchgraph für die Übersetzung wird mit Hilfe dieser Regeln bereits in einem Vorverarbeitungsschritt aufgebaut. NGMÜ hat folgende Nachteile:

• Der Übersetzer erlaubt nur die vorausberechneten Umordnungen. • NGMÜ kann keine lexikalischen Trigger für Umordnungen berücksichtigen. • Nicht alignierte Wörter in der Übersetzung sind nicht möglich. • Die Verwendung von Tupeln vergrößert das Suchproblem im Vergleich zur PBMÜ.

In dieser Dissertation stelle ich ein neuartiges Modell für die maschinelle Übersetzung vor, das die gemeinsame Wahrscheinlichkeit von Quell- und Zielsatz beschreibt und den Übersetzungsprozess als eine lineare Folge von Operationen repräsentiert. Wie die NGMÜ verwendet auch dieses Modell minimale Übersetzungseinheiten, ist aber dennoch wie die PBMÜ in der Lage, kurze Übersetzungsteile abzuspeichern. Im Gegensatz zur NGMÜ hat das Modell nicht nur Operationen für Übersetzungen sondern auch für Umordnungen. Die starke Kopplung von Übersetzung und Umordnung in einem einzigen NGramm-Modell liefert einen Mechanismus, mit dem die Position, zu der ein Wort oder eine Wortfolge verschoben wird, besser eingeschränkt werden kann, und mit dem Umordnungen über kurze wie lange Distanzen effektiver behandelt werden können. Diese Arbeit löst die Probleme in PBMÜ und NGMÜ durch die folgenden wissenschaftlichen Beiträge:

• Es wird ein Modell präsentiert, das Umordnungen über kurze wie lange Distanzen einheitlich und effektiv behandelt. • Das Modell erlaubt diskontinuierliche Übersetzungseinheiten auf der quellsprachlichen Seite. • Im Gegensatz zur PBMÜ erfordert der Übersetzer keine harte Begrenzung der maximalen Umordnungsdistanz. • Wie die PBMÜ und im Gegensatz zur NGMÜ hat dasModell die Fähigkeit, Phrasen abzuspeichern. • Im Unterschied zur NGMÜ wird der Suchraum nicht im voraus eingeschränkt, und es können lexikalische Trigger für die Umordnung gelernt und auf neue Kontexte angewendet werden.

Die Arbeit stellt die Meinung in Frage, dass bedingte Wahrscheinlichkeitsmodelle in der maschinelle Übersetzung generell besser funktionieren, und dass Kontextinformation auf der quellsprachlichen Seite weniger nützlich für den Übersetzungsprozess ist.