Universität PotsdamInstitut für Informatik
Lehrstuhl Maschinelles Lernen
Übersetzung
Tobias SchefferPeter HaiderPaul Prasse
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
2
Maschinelle Übersetzung
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
3
Maschinelle Übersetzung
Gegeben Text in Quellsprache, Generiere äquivalenten Text in Zielsprache.
Anwendungen: Übersetzung von Webseiten (Genauigkeit muss nicht
sehr hoch sein). Ermöglicht Verstehen eines fremdsprachlichen
Textes, auch wenn Übersetzung nicht genau ist. Assistenz, Vorschlag für menschlichen Übersetzer. Schriftverkehr von EU-Behörden wird in alle EU-
Sprachen übersetzt, erforderliche Genauigkeit ist aber höher als die heutiger Übersetzungssoftware.
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Statistische Übersetzung
Problemstellung: Gegeben Satz in Quellsprache Q, finde den besten Satz in Zielsprache Z: argmaxZ P(Z|Q)
Modellierung von gemeinsamer latenter Struktur: P(Z|Q) = ΣStruktur P(Z, Struktur | Q) Meistens vereinfachend statt Summe über alle
latenten Strukturen: argmaxZ,Struktur P(Z, Struktur | Q)
Oft: Aufteilung in (inverses) Übersetzungsmodell und Sprachmodell Satz von Bayes:
argmaxZ P(Z|Q) = argmaxZP(Q|Z) P(Z) 4
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Teilprobleme
Modellierung: Welche Klasse von Strukturen, welche Parametrisierung
Trainingsdaten: Zweisprachige Korpora mit Alignment
Parameterschätzung: Suchen der besten Parameterwerte gegeben die Trainingsdaten
Dekodierung: Effiziente Berechnung von argmaxZ,Struktur P(Z, Struktur | Q)
5
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Finite State Transducers
Stark vereinfachtes Modell: Basieren auf synchroner regulärer Grammatik:
erzeugt simultan 2 Sätze in 2 verschiedenen Sprachen
Definition: endliche Menge von Nichtterminalen N, Startsymbol
N1, Endsymbol Ne
Terminalsymbole in Quellsprache {qk} (Eingabe) und in Zielsprache {zk} (Ausgabe)
Regeln {Ni → <qk/zl>,Nj} Wahrscheinlichkeiten für Regeln, P(Ni → <qk/zl>,Nj)
6
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Finite State Transducers
Dekodierung: wahrscheinlichste Regelsequenz auf Quellsatz bestimmen (Viterbi); Zielsatz ableiten
Beispiel: Regel 1: P(S1→<The/Das>,S2) = 0,5 Regel 2: P(S1→<A/Ein>,S3) = 0,5 Regel 3: P(S2→<red/rote>,S4) = 1 Regel 4: P(S3→<red/rotes>,S4) = 1 Regel 5: P(S4→<car/Auto>,Se) = 1
Übersetzung von „The red car“: Finden der besten Regelsequenz mit Viterbi-
Algorithmus: R1, R3, R5 Ausführen der „Zielsprachenhälfte“ der
Regelsequenz: „Das rote Auto“ 7
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Finite State Transducers
Nachteil: 1-zu-1-Beziehung zwischen den Wörtern im Quellsatz und den Wörtern im Zielsatz (trotzdem nicht das selbe wie jedes Wort für sich
genommen zu übersetzen) Reihenfolge bleibt gleich
Verschiedene Möglichkeiten, Reihenfolge zu ändern: nachträgliches Umsortieren anhand Sprachmodell
der Zielsprache Einlesen der Eingabe in beliebiger Reihenfolge
erlauben
8
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Finite State Transducers mit variabler Reihenfolge
Keine 1-zu-1-Beziehung zwischen den Wörtern mehr → Beziehung und Reihenfolge muss explizit modelliert werden
3-stufiges generatives Modell für die Erzeugung des Quellsatzes aus dem Zielsatz:
1. Fertilität: für jedes Wort im Zielsatz wählen, wie viele Wörter im Quellsatz daraus erzeugt werden (Wörter kopieren)
2. Wort-Übersetzung: Für jede Wortkopie im Zielsatz wählen, zu welchem Wort in der Quellsprache es übersetzt wird
3. Position: Für jedes übersetzte Wort Position im Quellsatz wählen
9
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Finite State Transducers mit variabler Reihenfolge
10
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Finite State Transducers mit variabler Reihenfolge
Dekodierung wieder Suche nach wahrscheinlichster
Zustandssequenz jeder Zustand kodiert, welche Quellwörter bereits
erzeugt wurden und das letzte Zielwort riesiger Zustandsraum (zwar immer noch endlich),
daher Viterbi zu teuer Kompromiss: Beam-Search
in jedem Zeitschritt nur die k besten Zustände merken alle anderen wegwerfen
11
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Finite State Transducers mit variabler Reihenfolge
12
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
13
Trainieren des Übersetzungsmodells
Trainingsdaten: Parallele Korpora, z.B. Parlamentsreden aus Kanada, EU, Hong Kong. Multilinguale Zeitungsmeldungen (etwas weniger gut)
Paralleles Korpus muss „aligniert“ sein, Zuordnung von Textpositionen, soweit die Terme
einander entsprechen. Kann man theoretisch von Hand machen, es gibt
aber auch Verfahren, die Texte alignieren; so bekommen wir mehr Trainingsdaten.
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
14
Text-Alignment
Satzalignment: 1:1 – Satz im Quelldokument entspricht einem Satz
im Zieldokument. n:m – n Sätze im Quelldokument entsprechen m
Sätzen im Zieldokument. n, m im Bereich 0...3.
Verschiedene Ansätze zum Schätzen der Wahrscheinlichkeit eines Satz-Alignments: Längenbasiert Buchstaben-N-Gramm-basiert Lexikalisch
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
15
Text-Alignment Längenbasiert
Finde Alignment ((Q1, Z1), ..., (Qn, Zn)), wobei Qi und Zi 0, 1 oder 2 Sätze enthalten, so dass Qi und Zimöglichst gleich groß sind.
Bestes Alignment wird mit dynamischer Programmierung bestimmt.
Buchstaben-N-Gramme Finde Alignment, bei dem die Q1, Z1 möglichst viele
gleiche Buchstaben-N-Gramme enthalten. Lexikalisch
Basierend auf Wort-zu-Wort-Übersetzung; Zi soll möglichst viele wörtliche Übersetzungen aus Qienthalten.
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
16
Lernen des Übersetzungsmodells
Wahrscheinlichkeiten P(QJ | Zi) müssen jetzt aus parallelem Korpus mit alignierten Sätzen gelernt werden.
Problem: Schätzen der Parameter des generativen Modells erfordert Wort-Alignierung. Für Wort-Alignierung braucht man Übersetzungswahrscheinlichkeiten.
EM-Algorithmus.
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
17
Lernen des Übersetzungsmodells
EM-Algorithmus. Starte mit heuristisch initialisiertem generativen
Modell Wiederhole
Finde wahrscheinlichste Zustandssequenzen Zustandssequenzen liefern gleichzeitig Alignment
Schätze Parameter für Fertilität, Wortübersetzungen und Positionen (alles Multionomialverteilungen) durch Abzählen
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Wortsalat
Bisher: wortbasierte Modelle Problem: exponentiell viele Möglichkeiten, Wörter
anzuordnen Modellierung der Positionsverteilung für die
übersetzten Wörter große Schwachstelle → Wortsalat Besser: direkt größere Einheiten bearbeiten
Phrasenbasierte Modelle Phrasen sind Paare von Wortsequenzen in Quell-
und Zielsatz, die nur innerhalb aligniert sind
18
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Phrasen-basierte Modelle
Punkte: Wort-Alignment Rechtecke: Phrasen
19
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Phrasen-basierte Modelle
Konstruktion von Phrasen formell: Gegeben ein Satzpaar <Q,Z> mit Alignierung ~, so
dass gilt qk ~ zk‘ gdw. das k-te Wort im Quellsatz mit dem k‘-ten Wort im Zielsatz aligniert ist
Dann ist <qi…qj,zi‘…zj‘> ein Phrasenpaar, wenn gilt1. qk ~ zk‘ für irgendein k ∈ [i,j] und k‘∈ [i‘,j‘] 2. qk ~ zk‘ für alle k ∈ [i,j] und k‘∈ [i‘,j‘] 3. qk ~ zk‘ alle k ∈ [i,j] und k‘∈ [i‘,j‘]
20
//
//
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Phrasen-basierte Modelle
Statt Wahrscheinlichkeiten für Wort-zu-Wort-Übersetzung Phrasen-zu-Phrasen-Übersetzungen lernen
Funktioniert besser als wortbasierte Modelle Wörter sind Spezialfälle von Phrasen, daher immer
Fallback möglich bei unbekannten Phrasen Trotzdem: Reihenfolge der Phrasen immer noch
schwierig („Phrasensalat“) Lösung: Umsortierung direkt in die latente Struktur
übernehmen
21
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Synchrone PCFGs
Simultane Erzeugung von 2 Sätzen aus 2 kontextfreien Sprachen
Definition: endliche Menge von Nichtterminalen N, Startsymbol
N1
Terminalsymbole in Quellsprache {qk} und in Zielsprache {zk}
Regeln {Ni → <α/β/∼>}, wobei α Folge aus Quellterminalen und Nichterminalen ist, β eine Folge aus Zielterminalen und Nichtterminalen, ~ ein Alignment zwischen den Nichtterminalen in α und β
Wahrscheinlichkeiten für Regeln, P(Ni → <α/β/∼>)
22
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Synchrone PCFGs
23
Beispiel:
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Synchrone PCFGs: Parameterschätzung
Regeln müssen gegeben sein Wort-Alignment muss bekannt sein
zB mit einfacherem Übersetzungsmodell berechnet EM-Algorithmus: abwechselnd
Wahrscheinlichkeiten für Auftreten von Regeln berechnen mit Inside-Outside-Algorithmus
Parameter schätzen durch Abzählen
24
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Synchrone PCFGs: Dekodierung
Gegeben Satz in Quellsprache: wahrscheinlichsten Parse-Baum finden, unter
Berücksichtigung nur des Quellsprachenteils der Regeln
Zielsprachenteil ableiten unter Berücksichtigung des Alignments
25
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Synchrone PCFGs
Vorteil: elegante Handhabung von Reihenfolgenänderung
Nachteil: Regeln müssen bekannt sein Definition von synchronen Regeln schwierig besonders für Sprachen mit stark unterschiedlicher
Grammatik Erweiterung: synchrone PCFGs auf Phrasenbasis
mit automatisch generierten Regeln
26
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Hierarchische Phrasenübersetzung
Ein einziges generisches Nichtterminalsymbol Regeln werden aus Phrasenpaaren automatisch
extrahiert
Beispiel:
27
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Hierarchische Phrasenübersetzung
28
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Hierarchische Phrasenübersetzung
Algorithmus zum Generieren der Regeln:1. Für alle Phrasenpaare <qi…qj,zi‘…zj‘>:
füge die Regel X → < qi…qj / zi‘…zj / ∅ > hinzu2. Für alle Regeln X → <α/β/~>: Wenn <qi…qj,zi‘…zj‘>
ein Phrasenpaar ist, so dass gilt α = α1qi…qjα2 und β = β1zi‘…zj‘β2, dann füge die Regel X → < α1Xkα2 / β1Xk‘β2 / ~ ∪ {Xk ~ Xk‘} >
hinzu3. Wiederhole Schritt 2, bis keine neuen Regeln mehr
hinzukommen In der Praxis: hinterher mit Hilfe von Heuristiken
Regeln filtern (sonst zu viele)29
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Regelerzeugung: Beispiel
Ausgangspunkt: Alignment und Phrasen
Nach 2 Ersetzungsschritten:
30
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Methoden: Überblick und Ausblick
Phrasenbasierte Modelle fast immer überlegen Sowohl Übersetzung mit Finite State Transducern
als auch hierarchische Übersetzung wird weiterentwickelt
Schwierigkeit: nicht-lokale Kontextinformation prinzipiell Einbeziehung von beliebigen Features
möglich diskriminatives Lernen ihrer Gewichte aber: erschwert Dekodierung Tradeoff zwischen Ausdrucksstärke der Modelle und
effizienter Dekodierbarkeit
31
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
32
Evaluierung von Übersetzern Evaluierung
Menschliche Übersetzer sehen sich die maschinellen Übersetzungen an und vergeben Punkte.
N-Gramm-Co-Occurrence-Statistik: Wie viele N-Gramme einer Referenzübersetzung tauchen in der maschinellen Übersetzung auf?
Jährlicher gemeinsamer Wettbewerb: NIST (National Institute for Standards and
Technology): MetricsMATR Workshop on Statistical Machine Translation (WMT) Evaluierung von Übersetzungssystemen und
Metriken
Scheffer/S
awade: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Fragen?
33