next up previous contents index
Next: Ergebnisse bei der Satzzordnung Up: Satzzuordnung für lange Texte Previous: Texte mit Vorsegmentierung

Dynamische Programmierung

Viele statistische Probleme können dadurch gelöst werden, daß man sie in Teilprobleme zerlegt und deren Lösungen in geeigneter Weise zusammenfügt. Die aus der Informatik bekannte dynamische Programmierung (siehe Sedgewick, 1992, S. 673) eignet sich zur Lösung solcher Probleme, bei denen es sehr viel weniger Teilprobleme als mögliche Zerlegungen gibt. (Beispielsweise gibt es Arten von Problemen, bei denen es in Bezug auf die Größe der betrachteten Datenmenge nur polynomiell viele Teilprobleme, aber exponentiell viele Zuordnungen gibt). In diesen Fällen ist es günstig, die gefundenen Teillösungen in einer Tabelle zu speichern und so sicherzustellen, daß jedes Teilproblem nur einmal gelöst wird.

Nach Sankoff & Kruskal (1983) ist die dynamische Programmierung für Zuordnungsprobleme verschiedenster Art geeignet. Dazu gehören etwa der Vergleich der genetischen Codes unterschiedlicher Arten von Lebewesen oder die Zuordnung eines elektroakustischen Sprachsignales zu einem geschriebenen Text (Dynamic Time Warping ). Nach Gale & Church (1993) kann auch die hier betrachtete Satzzuordnung bei zweisprachigen Texten mit Hilfe der dynamischen Programmierung erfolgreich angegangen werden. Die folgenden Ausführungen zeigen, wie dies in der Praxis umgesetzt werden kann.gif

In Abb. gif wird das Problem der Satzzuordnung dadurch veranschaulicht, daß man die Zuordnungspositionen der Sätze eines Ausgangstextes O und der Übersetzung T als Positionen in einem zweidimensionalen Koordinatensystem auffaßt. In diesem Koordinatensystem soll nun ein Weg von links unten nach rechts oben gefunden werden, der zum einen gewissen Vorgaben enspricht (hier: ein Satz des Ausgangstextes darf entweder 0, 1 oder 2 Sätzen der Übersetzung zugewiesen werden) und zum zweiten eine Kostenfunktion  minimiert. Als Kostenfunktion für die Satzzuordnung eignet sich die Summe der Längenunterschiede der einander zugeordneten Sätze, wobei eine vorherige Normalisierung der Satzlängen vorausgesetzt wird.

Die Vorgehensweise besteht nun darin, daß für jeden Punkt im Koordinatensystem die Kosten des optimalen Pfades vom Ursprung bis zu diesem Punkt eingetragen werden. Dabei sind für jeden Punkt nur die Werte derjenigen anderen Punkte relevant, die näher zum Ursprung liegen. Deshalb kann dieser Vorgang systematisch vom Ursprung aus in fortschreitenden Diagonalen vorgenommen werden. Gelangt man an den rechten

   figure15506
Abbildung: Satzzuordnung eines Ausgangstextes O und einer Übersetzung T mittels dynamischer Programmierung.

oberen Punkt des Koordinatensystems, hat man die Kosten des optimalen Pfades, und kann den Pfad selbst von rechts oben nach links unten rekonstruieren. Schneller ist es, schon beim Vorwärts-Durchlauf geeignete Rückwärts-Pointer abzuspeichern, was aber zusätzlichen Speicherplatz benötigt.

In Abb. gif ist für einen Ausgangstext mit vier und eine Übersetzung mit fünf Sätzen das Diagramm der Kostenfunktion dargestellt. Die Kosten jedes Punktes ergeben sich durch Addition der Kosten des Vorgängerpunktes mit den Kosten, die sich durch die gerade betrachtete Zuordnung ergeben. Da viele Punkte des Koordinatensystems von mehreren Vorgängerpositionen erreicht werden können (gekennzeichnet durch die Verbindungslinien), wurden für jeden möglichen Weg die Kosten berechnet. Zur Berechnung der Kosten der nachfolgenden (weiter rechts liegenden) Positionen wurde jeweils der niedrigste - durch Fettdruck gekennzeichnete - Wert verwendet. Einige der Pfade im rechten unteren Bereich der Abbildung erreichen den Endpunkt rechts oben nicht, das heißt, daß nicht alle Sätze der Übersetzung Zuordnungspartner finden. Solche Pfade sind unzulässig und brauchen nicht vollständig berechnet zu werden.

Wie sich aus dem niedrigsten Wert des rechten oberen Punktes ablesen läßt, hat der optimale Pfad Kosten von 41. Der Weg zum Ursprung führt entlang der eingezeichneten Linien über den jeweils niedrigsten, also fett gedruckten Wert. Von rechts oben nach links unten ergeben sich also für die Kostenfunktion die Werte 41, 30, 12, 11 und 0. Dem entspricht die folgende Zuordnung der Sätze:

tex2html_wrap24944


next up previous contents index
Next: Ergebnisse bei der Satzzordnung Up: Satzzuordnung für lange Texte Previous: Texte mit Vorsegmentierung

Reinhard Rapp
Fri Jul 18 19:19:31 MET DST 1997