© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/ 1 15.01.03 1 Determinisierung / Sequentialisierung nicht- sequentieller Transduktoren Karin

© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03

1

Determinisierung /

Sequentialisierung nicht-sequentieller Transduktoren

Karin Haenelt

Transduktoren für die Sprachverarbeitung


2

Determinisierung: Definition

Wir nennen einen Algorithmus,der es ermöglicht,einen nicht-sequentiellenTransduktorin einen endlich-subsequentiellen Transduktor zu überführen,Determinisierung (Mohri 1996)

• Ziel– Zusammenfassung aller Startzustände zu einem Startzustand– Zusammenfassung aller ausgehenden Kanten mit demselben

Symbol zu einer einzigen Kante– Eliminierung von Epsilonkanten


3

Beispiel 1nicht-sequentiellerTransduktor

endlich-subsequentiellerTransduktor

0 1b

b2 3 4 5

e hr c

a hr c

6 7 8 9i gr n

a hr c

10 11 12 13e nr n

a nr n

0,ε 1,εb

b

r

a hr c

ech

ing

12,ε 13,εen n

n n

3,e7,i

11,e

4,ec8,in

5,ech9,ing

2,ε6,ε

10,ε

ε ε ε


4

Beispiel 2nicht-sequentiellerTransduktor

endlich-subsequentiellerTransduktor

0 1b

b2 3 4 5

e hr c

a hr c

6 7 8i gn

a cc

9 10 11 12e nr n

a nr n

0,ε 1,εb

b

r

a hr c

ech

ing

11,ε 12,εen n

n n

3,e6,i

10,e13,a

4,ec7,in

5,ech8,ing

2,ε9,ε

1413u

u

a

a

14,εau

u


5

Prinzip

• Kombination der lokal ambigen Pfade zu einem Pfad, der keine Ausgabe erzeugt

• Verzögerung der Ausgabe bis zur Auflösung der Ambiguität• Verzögerte Ausgabe kann mit einer Mehrzeichen-Ausgabe an

einer Kante zusammengefasst werden

0 1b

b2 3 4 5

e hr c

a hr c

6 7 8 9i gr n

a hr c

0,ε 1,εb

b

r

a hr c

ech

ing

3,e7,i

4,ec8,in

5,ech9,ing

2,ε6,ε


6

Konstruktion

• ähnlich wie Potenzmengen-Konstruktion zur Determinisierung nicht-deterministischer Automaten

• mit lazy implementation• hier zusätzlich:

– Verzögerung der Ausgabe, falls zu einer Eingabe verschiedene Ausgaben vorkommen

– neue Zustände gebildet aus Mengen von Paaren (stateT1,string)

• stateT1: Zustand in T1

• string: weitergereichte, d.h. verzögerte Ausgabe

4,ec8,in

{(4,ec),(8,in)}


7

Nicht-sequentieller Transduktor ),*,,,,,( 111111 BAFIVT

1V Zustandsmenge

11 VI Menge der Startzustände

11 VF Menge der Endzustände

A Eingabe-Alphabet, endliche Menge von Symbolen B Ausgabe-Alphabet, endliche Menge von Symbolen

1 Zustandsübergangsfunktion 121VAV

1 Ausgabefunktion *11 BVAV

Endlich-Subsequentieller Transduktor ),,*,,,,,( 2222222 BAFiVT

2i einziger Startzustand

2 Zustandsübergangsfunktion 22 VAV

2 Ausgabefunktion *2 BAV

2 Endausgabefunktion *BF

Notationskonventionen, 1

Mohri, 1996


8

weitere Notationen yx längstes gemeinsames Präfix zweier Zeichenreihen )(1 xyx

Zeichenreihe y, als Resultat der Abtrennung von x von xy

Q Queue Q zu Verwaltung der Zustandsmengen des resultierenden Transduktors T2

),( wq Element einer Zustandsmenge von T2: q: Zustand aus T1, w: verzögerte Ausgabe

Notationskonventionen, 2

Mohri, 1996


9

Notationskonventionen, 3} ),(|),{()( 11 2q(q,w)anddefinedaqwqaJ

)},('),(),(|)',,{()( 1212 aqq and qwq and defined aqqwqaJ

Zustände einer zusammengefassten Zustandsmenge in T2

für die Eingabe a in T1 definiert ist

Abkürzungen

3,e 4c:c

7,i 8c:n

3,ec:c

7,ic:n

Kanten einer zusammengefassten Zustandsmenge in T2

für die Eingabe a mit Zielzustand q‘ in T1 definiert ist

alle Elemente des Repräsentanten {(3,e),(7,i)},in denen gemäß T1 Eingabe c definiert ist

J1(c) = {(3,e),(7,i)}

alle Kanten des Repräsentanten {(3,e),(7,i)},in denen gemäß T1 Eingabe c mit Zielzustand q‘ definiert ist

J2(c) = {(3,e,4),(7,i,8)},


10

1 2F 2

1

)},{(2Ii

ii

3 }{ 2iQ 4 while Q 5 do ][2 Qheadq 6 if (there exists 2),( qwq such that 1Fq ) 7 then }{ 222 qFF 8 wq )( 22 9 for each a such that 2),( qwq and ),(1 aq defined

10 do ),( 22 aq )(),( 1 aJwq

)',,(),('

[ 1

1

qaqaqq

w

]

11 ),( 22 aq ))}',,()('),,(

)],([,'{( 1

2

122 qaqw

aJqwqaqq

12 if ( ),( 22 aq is a new state) 13 then ENQUEUE( ),(, 22 aqQ ) 14 DEQUEUE(Q)

*BwhabetAusgabealp BfunktionEndausgabe ktionAusgabefun

tionrgangsfunk ÜbeeEndzuständ F

ndStartzusta

i

)},('),(),(|)',,{()()(),(|),{()(

1212

11

aqq and qwq and defined aqqwqaJ}qwq, and defined aqwqaJ 2

DETERMINIZATION_TRANSDUCER(T1,T2), Mohri 1996

Mohri, 1996Eberhard/Niemann/Sejane, 2004

Algorithmus

xy) von x vonAbtrennungder Resultat (i.e.y Kette )(x -1 xy

y undKetten x der Präfix sgemeinsame längstes yx


11

1 2F 2

1

)},{(2Ii

ii

3 }{ 2iQ 4 while Q 5 { ][2 Qheadq 6 if (there exists 2),( qwq such that 1Fq ) 7 { }{ 222 qFF 8 wq )( 22

} 9 for each a such that 2),( qwq and ),(1 aq defined

10 { ),( 22 aq )(),( 1 aJwq

)',,(),('

[ 1

1

qaqaqq

w

]

11 ),( 22 aq ))}',,()('),,(

)],([,'{( 1

2

122 qaqw

aJqwqaqq

12 if ( ),( 22 aq is a new state) 13 then ENQUEUE( ),(, 22 aqQ )

} 14 DEQUEUE(Q)

}


Mohri, 1996

Eberhard/Niemann/Sejane, 2004

Startzustände vereinigen2

Repräsentant für Startzustände in Queue3Schleife über Queue4-14

nächster Repräsentant aus Queue14

Algorithmus: Struktur

Endzustände 7verzögerte Ausgabeals Endausgabe

8

Ausgabe berechnen10

Repräsentant fürZielzustand berechnen

11

Repräsentant fürZielzustand in Queue

12


12

9 for each a such that 2),( qwq and ),(1 aq defined 10 do ),( 22 aq

)(),( 1 aJwq)',,(

),('[ 1

1

qaqaqq

w

]

11 ),( 22 aq ))}',,()('),,(

)],([,'{( 1

2

122 qaqw

aJqwqaqq

*BwhabetAusgabealp BfunktionEndausgabe ktionAusgabefun

tionrgangsfunk ÜbeeEndzuständ F

ndStartzusta

i

)},('),(),(|)',,{()()(),(|),{()(

1212

11

aqq and qwq and defined aqqwqaJ}qwq, and defined aqwqaJ 2

xy von x vonAbtrennungder Resultat e. (i. y, Kette )(x

y undKetten x der Präfix sgemeinsame längstes 1- xy

yx


Kern des Determinisierungsalgorithmus


13

Zustandsübergänge für {(0,ε)}S (q2)

(q,w)

S

δ1(q1,a) σ2(q2,a) Kommentar

q1 a q1’

(q,w)

J1(a)

[w q1’

δ1(q1,a)

σ1(q1,a,q1’)]

1 2 3 4 5 9 8 7 6 Spalte Erläuterung {(0,ε)} (0,ε) 0 b 1 b 6 Ausgabe einer b-Kante

σ1(0,b,1) b 7 längstes gemeinsames

Präfix der Ausgaben aller b-Kanten σ1(0,b,q1‘)

ε 8 verzögerte Ausgabe (0,ε) εb = b 8-6 Konkatenation Sp. 8 •7 b längstes gemeinsames Präfix aller Zeichenketten

(verzögerte Ausgabe • aktuelle Ausgaben) für alle b-

Kanten, die von allen Paaren (q,w) S ausgehen:

längstes gemeinsames Präfix aller Zeichenketten über die Spalten 8-6

0 1b

b0,εT2 T1


14

S (q2)

(q,w)

S

δ1(q1,a) σ2(q2,a) δ2(q2,a)

q1 a q1’ (q,w)

J1(a)

[w q1’

δ1(q1,a)

σ1(q1,a,q1’)]

(q,w,q’)

J2(a)

(q’, [σ2(q2,a)]-1

w σ1(q1,a,q1’))

1 2 3 4 5 9 8 7 6 (0,ε) 0 b 1 b

b ε εb = b (1,b-1b) = (1,ε)

{ (0,ε)}

b {(1,ε)}

Zustandsübergänge für {(0,ε)}

0 1b

b0,εT2 T1

Zustand q‘, verzögerte Ausgabe)

bisher verzögerter Ausgabe w,verkettet mit aktueller Ausgabe

wird links abgeschnitten von

[längste gemeinsame Ausgabe]-1∙angesammelte Gesamtausgabe[σ2(q2,a)]-1 w σ1(q1,a,q1’))


15

),(1 aq 2q 2

),(q

wq q a 'q

),( 22 aq ),( 22 aq

)(),( 1 aJwq

[ w

),(' 1 aqq

)',,(1 qaq ] ))',,()],([

,'(

11

22 qaqwaqq

1 2 3 4 5 9 8 7 6 11 10 ),3( e 3 c 4 c (4, ec1][ ) = ),4( ec

e c ec

),7( i 7 c 8 n (8, in1][ ) = ),8( in i n in

{ ),3( e , ),7( i , ),11( e }

= = { ),8(),,4( inec }

Transitionen für {(3,e),(7,i),(11,e)}, c

4 5hchc

8 9gnhc

12 13nnnn

0,ε 1,εb

b

r

ar

3,e7,i

11,e

2,ε6,ε

10,ε

3

7

11

T2 T1

c

4,ec8,in


16

Beispiel 1

nicht-sequentiellerTransduktor

p-subsequentiellerTransduktor

0 1b

b2 3 4 5

e hr c

a hr c

6 7 8 9i gr n

a hr c

10 11 12 13e nr n

a nr n

0,ε 1,εb

b

r

a hr c

ech

ing

12,ε 13,εen n

n n

3,e7,i

11,e

4,ec8,in

5,ech9,ing

2,ε6,ε

10,ε


17

6 Paar ),3( e Ausgabe )4,,3(1 c 7 Paar ),3( e längstes gemeinsames Präfix aller Ausgaben )',,3(1 qc 8 Paar ),3( e verzögerte Ausgabe w, verkettet mit Spalte 7 9 alle Paare ),3( e , ),7( i längstes gemeinsames Präfix aller Zeichenreihen in Spalte 8

σ2(q2,c) für {(3,e),(7,i),(11,e)}),(1 aq 2q

2

),(q

wq q a 'q

),( 22 aq ),( 22 aq

)(),( 1 aJwq

[ w

),(' 1 aqq

)',,(1 qaq ] ))',,()],([

,'(

11

22 qaqwaqq

1 2 3 4 5 9 8 7 6 11 10 ),3( e 3 c 4 c (4, ec1][ ) = ),4( ec

e = c = ec

),7( i 7 c 8 n (8, in1][ ) = ),8( in i = n = in

{ ),3( e , ),7( i , ),11( e }

= = { ),8(),,4( inec }

)(),( 1 aJwq )',,(1 qaqw

),(' 1 aqq


18

6 Paar ),3( e Ausgabe )4,,3(1 c 7 Paar ),3( e alle Ausgaben )',,3(1 qc 8 Paar ),3( e Präfix w alle Ausgaben )',,3(1 qc 9 alle Paare ),7)(,3( ie Präfix w alle Ausgaben )',,3(1 qc und )',,7(1 qc

σ2(q2,c) für {(3,e),(7,i),(11,e)}

längstesgemein-samesPräfixvon

)(),( 1 aJwq )',,(1 qaqw

),(' 1 aqq

),(1 aq 2q 2

),(q

wq q a 'q

),( 22 aq ),( 22 aq

)(),( 1 aJwq

[ w

),(' 1 aqq

)',,(1 qaq ] ))',,()],([

,'(

11

22 qaqwaqq

1 2 3 4 5 9 8 7 6 11 10 ),3( e 3 c 4 c (4, ec1][ ) = ),4( ec

e = c = ec

),7( i 7 c 8 n (8, in1][ ) = ),8( in i = n = in

{ ),3( e , ),7( i , ),11( e }

= = { ),8(),,4( inec }


19

Erweiterung des Algorithmus für endlich-subsequentielle

Transduktoren• nicht nur eine, sondern endlich viele Endausgaben• Endausgabe muss eine Menge sein

6 for each 2),( qwq such that 1Fq 7 do }{ 222 qFF 8 ),,(_ 22 wqOUTPUTADD

Mohri, 1996


20

Komplexität des subsequentiellen Transduktors

• Zeit– allgemeine Form der Komplexitätskurve ist linear– Laufzeit

• hängt nur von der Länge der Eingabezeichenreihe ab• nicht von der Größe des Automaten

– keine Ambiguitäten zu verwalten


21

Komplexität des subsequentiellen Transduktors

• Platz– theoretisch können Transduktoren mit mehr als 2Q Zuständen

entstehen(Anzahl der Teilmengen, die aus n Zuständen gebildet werden kann, beträgt 2n, zusätzlich: Kombinationen mit verzögerten Ausgaben)

– kommt in der Praxis der Sprachverarbeitung kaum vor, da• durch Abfolgebeschränkungen der Zeichen zur Modellierung

menschlicher Sprachen (Laute, Buchstaben, Worte, Kategorien)nicht jeder Zustand mit jedem anderen durch eine Kante verbunden werden kann.

• die Anzahl und Länge der Ambiguitäten praktisch begrenzt ist– praktisch sind die entstehenden endlich-subsequentiellen

Transduktoren oft kleiner als die originalen nicht-sequentiellen Transduktoren

– daher lazy implementation sinnvoll (Zustände nur bilden, wenn sie das Ergebnis einer Transition sind, die von einem bereits hinzugefügten Zustand ausgehen)


22

Komplexität: Beispiel 1Name DELAPF

Phonetisch V.3

FDELAF Französisch V.7

EDELAF Englisch

IDELAF Italienisch

Anzahl der Zeilen 472.000 672.000 145.000 612.000

Wörterbücher

Größe 9,6 MB 21,2 MB 3,6 MB 20 MB Anzahl der Zustände 46.750 67.000 47.540 64.390 Anzahl der Kanten 130.125 191.300 115.450 194.606 p 4 7 8 8 Ausgabesymbole, Anzahl

13.490 22.790 14.150 21.870

Ausgabealphabet, Platz

85 KB 116 KB 154 KB 109 KB

Größe 2,1 MB 3,6 MB 2 MB 3,5 MB

Transduktoren

Größe minimiert 870 KB 1,3 MB 790 KB 1,3 MB Konstruktion auf HP-Rechner

9’30’’ 20’ 11’35’’ 19’

Konstruktion auf NEXT-Rechner

38’ 1h21’ 30’ 1h35’

Zeit

Nachschlagen auf HP-Rechner

80 w/ms 80 w/ms 80 w/ms 80 w/ms

(Mohri, 1996)


23

Komplexität: Beispiel 2Word lattice W1: Which flights leave Detroit and arrive at Saint-Petersburg around nine a.m.?

Word lattice W2: Determinisierung von W1

Word lattice W3: Minimierung von W2

Mohri, 1997


24

Ersparnis durch Determinisierung

• Ein gewichteter Transduktor word lattice für die Spracherkennung auf einem 2.000 Wörter Lexikon für den Satz Which flights leave Detroit and arrive at Saint-Petersburg around nine am?

(Mohri, 1997: 32ff. über ARPA ATIS)

Zustände Übergänge Pfade

WL 106 359 83 Mio.

WL determiniert 38 51 18

WL determiniert und minimiert

25 33 18

Folie von:Eberhard/Niemann/Sejane, 2004: 26


25

Komplexität: Determinisierungsalgorithmus

• zeitbestimmender Faktor des Algorithmus:Hashing-Methode, mit der festgestellt wird, ob ein erzeugter Repräsentant eines Zustandes neu oder bekannt ist:if ( is a new state)then ENQUEUE(Q, )),( 22 aq ),( 22 aq


26

Determinisierbarkeit

• alle azyklischen Transduktoren können determinisiert werden• zyklische Transduktoren können determinisiert werden, wenn

die Zyklen eine Twins-Property haben• für nicht-determinisierbare Transduktoren können

deterministische Bi-Maschinen konstruiert werden


27

Twins-Property / Zwillingseigenschaft

• Choffrut, 1977, 1978– allgemeiner Algorithmus– Nachweis der Entscheidbarkeit

• Allauzen/Mohri– Algorithmus auf der Basis der Komposition von

Transduktoren und einer Charakterisierung der Twins-Property über die Kombinatorik von Worten


28

Definition Zwei Zustände eines string-to-weight-Transduktors

),,,,,,,( FIQT , nicht unbedingt sequentiell, heißen Zwillinge, wenn gilt:

)',,'(),,(

)),'('),,(),,(}',({,*)(),( 2

qvqqvqvqqvqquIqqvu

Zwillingseigenschaft

Mohri, 1997:310


29

• q1 und q2 sind Geschwister,– wenn sie vom Startzustand über dieselbe Zeichenreihe x erreicht

werden können– wenn es am Zustand q1 und q2 einen Zyklus mit Eingabe y gibt

• Zwei Geschwister q1 und q2 sind Zwillinge– wenn die Minimalausgabe einer Schleife mit Eingabe y bei q1 und

q2 identisch ist• ein Tranduktor T hat die Zwillingseigenschaft, wenn alle Geschwister

Zwillinge sind

Zwillingseigenschaft

Allauzen/Mohri, 2003


30

Nicht-sequentialisierbare Transduktoren

Allauzen/Mohri 2003


31

Nicht-sequentialisierbare Transduktoren

• Beispiel für eine Funktion, für die es keinen sequentiellen Transduktor gibt:

x:a

x:b0

3

1

4

2x:a

x:a

x:b

x:b

)(,}{ wfxw ist gerade |w| falls a w|| sandernfall b w||

• Bedingung für sequentielle Funktion (Theorem von Ginsburg und Rose, 1966):

dass soexistiert, K Integer positives ein g.d.w. ll sequentieist f.**:f Funktion rationale eine f Sei

f(u)w f(ua):K |w|*,w au ,*,

Mohri, 1997:303


32

BiMaschinen

• Geeignet zur Aufteilung eines funktionalen aber nicht sequentiellen Transduktors

• Zwei sequentielle Transduktoren, die in Serie angewendet werden– 1. Hälfte der Bi-Maschine verarbeitet Eingabe von

links nach rechts– 2. Hälfte der Bi-Maschine verarbeitet Ausgabe der

1. Hälfte von rechts nach links

Karttunen 2003:353


33

BiMaschine: Beispiel

x:a

x:b0

3

1

4

2x:a

x:a

x:b

x:bx:x1

0 1 2x:x1

x:x2

Nicht-sequentiellerTransduktor LRT

1. Hälfte R

1 0

x2:b

2. Hälfte L

x1:b

x2:a

x1:a

Mohri, 1997:304

x:x10 1

x:x11

x:x22

b:x11 0

b:x10

b:x21

R

L


34

Vielen Dank

Für das Aufspüren von Fehlern in früheren Versionen und für Verbesserungsvorschläge danke ich

Simone Eberhardt, Arndt Faulhaber, Julian Kunkel, Katja Niemann, Ineta Sejane

Versionen22.05.2007, 17.05.2007, 23.06.2005,07.05.2005,05.05.2005, 15.01.03


35

Literatur• Allauzen, Cyril und Mehryar Mohri (2003). Efficient Algorithms for Testing the

Twins Property. In: Journal of Automata, Languages and Combinatorics 8, 2, S. 117-144.

• Choffrut, Christian (1978). Contributions à l’étude de quelques familles remarquables de fonctions rationelles. PhD thesis (thèse de doctorat d’État), Université Paris 7, LITP: Paris.

• Choffrut, Christian (1977). Une charactérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationelles. In: Theoretical Computer Science, 5, S. 325-338.

• Eberhard, Simone; Niemann, Katja und Ineta Sejane (2004). Determinisierung von Transduktoren. Seminarrreferat 28.06.2004. http://kontext.fraunhofer.de/haenelt/kurs/Referate/Eberhard_Niemann_Sejane_S2004/AlgorithmusMohri.ppt bzw. pdf

• Haenelt, Karin (2004). Determinisierung von Transducern. Eine Erläuterung des Algorithmus von Mohri. http://kontext.fraunhofer.de/haenelt/kurs/folien/FstDetermMohri.pdf

• Haenelt, Karin (2004). Operationen auf endlichen Automaten und Transduktoren. Definitionen, Algorithmen, Erläuterungen und Beispiele – eine Übersicht. http://kontext.fraunhofer.de/haenelt/kurs/folien/FSOperationenDef.pdf


36

Literatur• Karttunen, Lauri (2003): Finite-State Technology. In: Ruslan Mitkov (Hg.): The

Oxford Handbook of Computational Linguistics. Oxford University Press.• Mohri, Mehryar (1997): Finite State Transducers in Language and Speech

Processing. In: Computational Linguistics, 23, 2, 1997, S. 269-311. http://citeseer.nj.nec.com/mohri97finitestate.html

• Mohri, Mehryar (1996): On some Applications of finite-state automata theory to natural language processing. In: Journal of Natural Language Egineering, 2, S. 1-20.

• Mohri, Mehryar und Michael Riley (2002). Weighted Finite-State Transducers in Speech Recognition (Tutorial). Teil 1: http://www.research.att.com/~mohri/postscript/icslp.ps, Teil 2: http://www.research.att.com/~mohri/postscript/icslp-tut2.ps

Documents

© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/ 1 15.01.03 1 Determinisierung / Sequentialisierung nicht- sequentieller Transduktoren Karin