Word re-ordering and dynamic programming based search algorithm for statistical machine translation

Tillmann, Christoph; Ney, Hermann

doi:313

Word re-ordering and dynamic programming based search algorithm for statistical machine translation

Tillmann, Christoph (Author)

2001 & 2002

Verantwortlichkeitsangabevorgelegt von Christoph Tillmann

ImpressumAachen : Publikationsserver der RWTH Aachen University 2001

UmfangVIII, 134 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2001

Prüfungsjahr: 2001. - Publikationsjahr: 2002

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Ney, Hermann (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2001-05-04

Online
URN: urn:nbn:de:hbz:82-opus-3134
URL: http://publications.rwth-aachen.de/record/61621/files/02_052.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Informatik (frei) ; Automatische Übersetzung (frei) ; Wortproblem (frei) ; Dynamische Optimierung (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
In dieser Arbeit wird ein neuer Suchalgorithmus fuer die Statistische Maschinelle Übersetzung vorgestellt. Der Algorithmus beruht auf dem Prinzip der Dynamischen Programmierung (DP). Ausgangspunkt ist eine DP-Lösung für das Traveling-Salesman-Problem, die darauf beruht, dass Untermengen von Städten gemeinsamen bearbeitet werden können, ohne die Reihenfolge, in der die Städte besucht wurden, zu beachten. In der Statistischen Maschinellen Übersetzung entsprechen den Städten Position in dem zu übersetzenden Satz. Unter der Verwendung von geeigneten Einschränkungen der erlaubten Wortumordnungen erhält man einen effizienten DP-basierten Suchalgorithmus. Eine daten-abhängige Suchorganization erlaubt es, unwahrscheinliche Übersetzungshypothesen zu prunen. Sucheinschränkungen, die besonderes nützlich für die Übersetzungsrichtungen Deutsch-Englisch und Englisch-Deutsch sind, werden vorgestellt. Die Umordnungseinschränkungen werden verallgemeinert, wodurch sie auf mehrere unterschiedliche Übersetzungsrichtungen anwendbar sind. Übersetzungsergebnisse werden für ein allgemein verwendetes Übersetzungsmodell und verschiedene Übersetzungsrichtungen vorgestellt.

In this work, a new search procedure for statistical machine translation (SMT) is proposed that is based on dynamic programming (DP). The starting point is a DP solution to the traveling salesman problem that works by jointly processing tours that visit the same subset of cities. For SMT, the cities correspond to source sentence positions to be translated. Imposing restrictions on the order in which the source positions are translated yields a DP algorithm for carrying out the word re-ordering in SMT efficiently. A simple data-driven search organization allows the algorithm to prune unlikely translation hypotheses. Search restrictions especially useful for the translation directions German-to-English and English-to-German are presented. A generalization of these re-ordering restrictions is given that is applicable to several different translation directions. Translation results are reported with a widely used SMT model.

Fulltext:
PDF
(additional files)