DTW - Warpfunktionen

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

DTW - Warpfunktionen

Beitrag von marluwie »

In der Sprechstunde wurde nach der Anwendung und dem Unterschied der komplexeren Warp-Funktionen gefragt. Zum besseren Verständnis beziehe ich mich auf die Folie 27 im Foliensatz Sprache. Die Warp-Funktionen sind dort mit (a), (b), usw. bezeichnet.

Allgemeines:
Die Warp-Funktion gibt an, wie ein Wort auf ein Anderes gemapt werden darf. Die einfachste Funktion ist die Diagonale, die nur ein lineares Mapping (1:1) zulässt (es können dann nur Wörter gleicher Länge gemapt werden). (a) bildet jedes Element der Feature-Vektoren (z.B. Buchstaben, Zahlen oder Phoneme) auf ein Anderes ab. Es wird kein Element ausgelassen, sondern höchstens vervielfacht. Auch (b) lässt kein Feature aus. Allerdings ist Duplizieren nur dann erlaubt, wenn vorher ein lineares Mapping stattgefunden hat. Mit (f) kann man nun Elemente auslassen. Dies dient z.B. dazu Ausreißer durch Messstörungen zu unterdrücken.

Berechnung der akkumulierten Distanzmatrix:
Die akkumulierte Distanzmatrix (Akk) wird in jedem Fall über die Distanzmatrix (Dist) ermittelt. Den Wert einer Zelle berechnet man in dem man den schwarzen Knoten ("Anker") in die Zelle legt, das Minimum seiner erlaubten Vorgänger ermittelt und zu diesem den entsprechenden Distanzwert addiert. Für (f) bedeutet dies relativ zum Ankerpunkt: Akk(i,j) = min{Akk(i-1,j-2),Akk(i-1,j-1),Akk(i-2,j-1)} + Dist(i,j). Für (b) gilt, dass zwar der erlaubte Weg vor einer Duplizierung ein lineares Mapping fordert; die Berechnung ist aber äquivalent zu (a), da man nur über einen direkten Nachbarn zur momentanen Zelle gelangen kann. Hier gingen also als Beispiel Ausreißer im Gegensatz zu (f) mit ein.

Randbehandlung:
Die Zelle links unten kann immer berechnet werden. Hier gilt Akk(i,j) = Dist(i,j). Im Weiteren können nur für Zellen Werte berechnet werden, die durch den gesamten Weg, den die Warp-Funktion vorgibt erreicht werden können. Es reicht bei (b) also nicht aus, dass ein horizontales Mapping möglich ist. Die Funktion fordert, dass zuvor stets ein lineares Mapping stattfindet. Es müssen aber alle zutreffenden Bedinungen beachtet werden. Wenn bei (d) die langen Äste nicht angewendet werden können, muss trotzdem sofern möglich das kurze, lineare Mapping durchgeführt werden.

Wegfindung:
Benötigt man nach dem Warping auch noch das Mapping der beiden Wörter. So beginnt man in der Zelle rechts oben und folgt rückwärts dem Minimum, dass durch die Warpfunktion erreichbar ist. Im Gegensatz zu (f) gibt es bei (b) also keinen großen Sprung und im Gegensatz zu (a) muss bei (b) nach einem geraden Schritt ein Diagonaler folgen (können). In der Praxis ist dieser Weg eindeutig, da durch Verwendung von reellen Zahlen fast nie zwei Zellen den gleichen Wert enthalten. Würde man von links unten beginnen, bräuchte man einen Weg-Finde-Algorithmus. Häufig benötigt man aber sogar nur die Distanz zwischen zwei Feature-Vektoren (<- gilt nicht für die Klausur), die sich direkt aus Rechts-Oben ablesen lässt.

Ich hoffe, dass die Erklärungen verständlich genug waren.
Viele Grüße, Marian!

Benutzeravatar
Buchinho
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 21. Okt 2006 15:23

Re: DTW - Warpfunktionen

Beitrag von Buchinho »

Eine Frage bleibt trotzdem noch unbeantwortet. Werden bei Funktion b) c) d) g) und h) die Zwischenschritte hinzuaddiert für den vergleich der minimalen Strecke? :roll:
Si hoc legere scis nimium eruditionis habes

Benutzeravatar
mba
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 13. Jul 2007 19:16

Re: DTW - Warpfunktionen

Beitrag von mba »

Etwas genauer, die gleiche Frage:

Bild

Um den schwarzen Punk zu berechnen muss man MIN(rot1+rot2, gelb, grün1+grün2) berechnen?
»Es ist noch kein Meister vom Himmel gefallen«
Wenn doch, wär er jetzt tot.
Bild

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

Re: DTW - Warpfunktionen

Beitrag von marluwie »

In der Zelle, deren Wert ermittelt werden soll, steht die akkumulierte Distanz bis zu diesem Mapping. Die Warp-Funktion gibt an, auf welchem Weg man dieses erreichen darf. Im Falle der zuletzt geposteten Funktion hat man bereits den Weg bis zu den, dem Anker nächstgelegenen Zellen berechnet. Für die nächste Zelle ist also nur zum Minimum der direkten Nachbarknoten (sofern der entsprechende Pfad durch die Warp-Funktion zugelassen wird) die Distanz zu addieren. Werden durch die Warp-Funktion Features ausgelassen, gehen diese auch nicht in die Wegberechnung ein.

Beispiel an (g):
Für den Wert der Zelle (i,j) gilt Akk(i,j) = min{Akk(i,j-1),Akk(i-1,j-1),Akk(i-1,j-2),Akk(i-1,j-3)} + Dist(i,j), sofern kein Index des entsprechenden Pfads negativ ist (die Zelle links unten sei (0,0)). Die akkumulierte Distanzmatrix ist dann wiefolgt besetzt:

Code: Alles auswählen

. . . x x x x x x x
. . x x x x x x x x
. . x x x x x x x x
. . x x x x x x x x
. x x x x x x x x x
. x x x x x x . . .
. x x x . . . . . .
x . . . . . . . . .
Die Punkte sind mit unendlich belegt die Xe können mit der gesamten oder "Teilen" der Warp-Funktion erreicht und berechnet werden. Hier wird vielleicht auch noch mal delta_max und delta_min deutlich.

Viele Grüße, Marian!
"You can't change anything by fighting or resisting it. You change something by making it obsolete through superior methods." (Buckminster Fuller)

Benutzeravatar
tony
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 24. Okt 2005 11:12
Wohnort: Darmstadt

Re: DTW - Warpfunktionen

Beitrag von tony »

Lieber Marian,

Wärst du so lieb um das Beispiel auf den Zusatzfolien uns zu erklären?

Ich habe versucht deine Anweisungen zu befolgen und kam auf das folgende Ergebnis für die akkumulierte Distanzmatrix:

Code: Alles auswählen

b . 6 5 4 4 4
a . 5 4 3 4 4
a . 4 3 3 3 4
a . 3 2 3 3 3
a . 2 2 2 3 3
a . 1 2 2 2 3
a . 1 1 2 3 4
a 0 . . . . .
_ a b b b b b
Ist es richtig so?

Denn auf den Folien sieht es so aus:

Code: Alles auswählen

b ? ? ? ? 6 6
a ? ? ? 6 6 6
a ? ? ? 5 5 5
a ? ? 4 4 4 5
a ? ? 3 3 4 5
a ? 2 2 3 4 ?
a ? 1 2 ? ? ? 
a 0 ? ? ? ? ?
_ a b b b b b

Danke,
tony.

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

Re: DTW - Warpfunktionen

Beitrag von marluwie »

Hallo!

Ich komme auf die gleiche Matrix wie in den Zusatzfolien. Du kannst für (3,1) keinen Wert setzen. Laut der Warp-Funktion brauchst du dafür einen Weg entweder von (2,-1), was unmöglich ist, von (2,0), wohin auch bei dir kein Pfad (Warping) führt, oder (1,0), was dem Fall (2,0) entspricht. Das Mapping durch (3,1) ist also verboten und der Wert wird in der Matrix auf unendlich gesetzt. Auf diese Weise kann man verhindern, dass bei der Wegsuche ein solches Mapping in Betracht gezogen wird.

Du hast in der Zelle (2,1) den Wert 1 statt 2 stehen. Ein Pfad kann durch die Warp-Funktion gefunden werden (diagonal und dann hoch oder zur Seite. Je nach dem wie du die Indizes interpretierst). Dieser Pfad ist zusätzlich der Einzige. Somit gilt Akk(2,1) = Akk(1,1) + Dist(2,1) = 1 + 1 = 2. Der Wert wäre 1, wenn du die Warp-Funktion benutzen würdest, die eine direkte Kante vom Anker zum Knoten (i-2,j-1) hätte. Dann ergäbe sich der Wert durch Akk(2,1) = A(0,0) + Dist(2,1) = 0 + 1 = 1. So musst du beim Mapping über den Knoten (1,1) gehen, für den du die länge des kürzesten Weges dorthin aber bereits berechnet hast und somit benutzen kannst.

Ein vollständiges Beispiel noch mal für die Zelle (3,3). Da die Werte in der akkumulierten Distanzmatrix für (2,1), (3,2), (2,2), (2,3) und (1,2) existieren, ist jeder Pfad der Warpfunktion zur Zelle (3,3) möglich. Der kürzeste Weg ist bereits für die Knoten (3,2), (2,2) und (2,3) bekannt. Daher: Akk(3,3) = min{Akk(3,2), Akk(2,2), Akk(2,3)} + Dist(3,3) = min{2, 2, 2} + 1 = 3.

Zusammenfassend:
Es muss zu einem Pfad der Warp-Funktion für jeden Knoten (jedes Mapping) eine akkumulierte Distanz vorhanden sein (außer dem Ankerpunkt natürlich). Ansonsten darf der Pfad nicht benutzt werden. Ist kein Pfad der Warp-Funktion anwendbar, wird der Wert der akkumulierten Distanzmatrix auf unendlich gesetzt. Es gilt immer Akk(0,0) = Dist(0,0). Ist ein Pfad anwendbar, berechnet sich die akkumulierte Distanz der aktuellen Zelle aus der kürzesten Distanz zum nächsten Nachbarn + Distanz von diesem Nachbarn zum aktuellen Knoten.

Viele Grüße, Marian!
"You can't change anything by fighting or resisting it. You change something by making it obsolete through superior methods." (Buckminster Fuller)

Benutzeravatar
tony
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 24. Okt 2005 11:12
Wohnort: Darmstadt

Re: DTW - Warpfunktionen

Beitrag von tony »

Ahh... jetzt klappt's!

Danke schön!

Benutzeravatar
apulix
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 152
Registriert: 21. Nov 2004 23:54
Wohnort: Darmstadt
Kontaktdaten:

Re: DTW - Warpfunktionen

Beitrag von apulix »

marluwie hat geschrieben:Wegfindung:
Benötigt man nach dem Warping auch noch das Mapping der beiden Wörter. So beginnt man in der Zelle rechts oben und folgt rückwärts dem Minimum, dass durch die Warpfunktion erreichbar ist. Im Gegensatz zu (f) gibt es bei (b) also keinen großen Sprung und im Gegensatz zu (a) muss bei (b) nach einem geraden Schritt ein Diagonaler folgen (können). In der Praxis ist dieser Weg eindeutig, da durch Verwendung von reellen Zahlen fast nie zwei Zellen den gleichen Wert enthalten. Würde man von links unten beginnen, bräuchte man einen Weg-Finde-Algorithmus. Häufig benötigt man aber sogar nur die Distanz zwischen zwei Feature-Vektoren (<- gilt nicht für die Klausur), die sich direkt aus Rechts-Oben ablesen lässt.
Die Wegfindung verstehe ich noch nicht ganz. Z. B. ist in der Weg bei dem Beispiel aus den Zusatzfolien doch nicht klar definiert, weil schon beim ersten Schritt (von oben rechts aus), weil dort alle Werte gleich sind. Wie verfährt man in einem solchen Fall?
Alumni-Netzwerk der TU Darmstadt: http://alumni.tu-darmstadt.de/ (auch für Studierende)

Benutzeravatar
mba
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 13. Jul 2007 19:16

Re: DTW - Warpfunktionen

Beitrag von mba »

Manchmal ist es so, dass man zwischen zwei oder mehr Werten auswählen kann, weil alle die minimalen sind. Dabei ist es egal welchen der Werte du für deinen Weg nimmst (dies ist lediglich die Frage der Implementierung). Am Ende hast du den gleichen Wert raus für den Weg, wenn du alle Wegpunkte addierst und dies ist der entscheidende Punkt.
»Es ist noch kein Meister vom Himmel gefallen«
Wenn doch, wär er jetzt tot.
Bild

Benutzeravatar
apulix
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 152
Registriert: 21. Nov 2004 23:54
Wohnort: Darmstadt
Kontaktdaten:

Re: DTW - Warpfunktionen

Beitrag von apulix »

mba hat geschrieben:Manchmal ist es so, dass man zwischen zwei oder mehr Werten auswählen kann, weil alle die minimalen sind. Dabei ist es egal welchen der Werte du für deinen Weg nimmst (dies ist lediglich die Frage der Implementierung). Am Ende hast du den gleichen Wert raus für den Weg, wenn du alle Wegpunkte addierst und dies ist der entscheidende Punkt.
Das funktioniert aber am Beispiel aus den Zusatzfolien nicht. Wenn das erste Mapping (wieder von oben rechts aus gesehen) nach links geht, also von b auf b, dann kriegt man einen anderen Wert raus als wenn man nach unten oder nach unten links geht.
Alumni-Netzwerk der TU Darmstadt: http://alumni.tu-darmstadt.de/ (auch für Studierende)

Benutzeravatar
mba
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 13. Jul 2007 19:16

Re: DTW - Warpfunktionen

Beitrag von mba »

Interessant. Intuitive Lösung des Problems, die ich vorschlagen würde ist es bei einer Verzweigung (mehrere Werte die gleich sind) quasi beide Pfade zu berechnen und zu schauen, welcher der Pfade minimal ist und diesen auswählen. Wenn in der Aufgabenstellung jedoch steht, man soll einen beliebigen Pfad finden und nicht den minimalsten, dann würde ich mir die Mühe nicht machen. Hauptsache der Pfad ist durch die Warpfunktion entstanden.
»Es ist noch kein Meister vom Himmel gefallen«
Wenn doch, wär er jetzt tot.
Bild

Benutzeravatar
apulix
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 152
Registriert: 21. Nov 2004 23:54
Wohnort: Darmstadt
Kontaktdaten:

Re: DTW - Warpfunktionen

Beitrag von apulix »

Da hätte ich aber gerne eine Stellungnahme vom Veranstalter. Laut Marian ist nämlich kein Weg-Finde-Algorithmus notwendig, wenn man von oben rechts anfängt. Zum Glück ist morgen nochmal Sprechstunde. =)
Alumni-Netzwerk der TU Darmstadt: http://alumni.tu-darmstadt.de/ (auch für Studierende)

Benutzeravatar
mba
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 13. Jul 2007 19:16

Re: DTW - Warpfunktionen

Beitrag von mba »

Yep, können wir morgen dann genau klären, ob der Weg eindeutig ist.
»Es ist noch kein Meister vom Himmel gefallen«
Wenn doch, wär er jetzt tot.
Bild

triality
Erstie
Erstie
Beiträge: 12
Registriert: 13. Jun 2007 17:19

Re: DTW - Warpfunktionen

Beitrag von triality »

Abgehakt
Zuletzt geändert von triality am 23. Jul 2008 22:31, insgesamt 1-mal geändert.

Benutzeravatar
mba
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 13. Jul 2007 19:16

Re: DTW - Warpfunktionen

Beitrag von mba »

Dies ist ein möglicher, korrekter Weg. Andere Warpfunktionen, andere Möglichkeiten einen Weg zu finden, also auch ein anderer Weg möglich.

In der Praxis ist der Weg eindeutig, weil dort nicht mit Int gerechnet wird und die Wahrscheinlichkeit zwei gleicher Floats viel zu gering ist.
»Es ist noch kein Meister vom Himmel gefallen«
Wenn doch, wär er jetzt tot.
Bild

Antworten

Zurück zu „Archiv“