Universität Potsdam Institut für Informatik Lehrstuhl Maschinelles Lernen Textklassifikation und...

transcript

Universität PotsdamInstitut für Informatik

Lehrstuhl Maschinelles Lernen

Textklassifikation und Informationsextraktion

Tobias Scheffer

Peter Haider

Paul Prasse

Uwe Dick

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Textklassifikation,Informationsextraktion

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Textklassifikation, Informationsextraktion

Textklassifikator: Ordnet einen Text einer Menge von inhaltlichen Kategorien zu.

Wird aus annotierten Daten gelernt. Anwendungsbeispiel: Posteingangsverarbeitung.

Informationsextraktion: Identifikation definierter Felder in Dokument.

Auch aus Daten gelernt. Anwendungsbeispiel: Automatisierung von

Dokumentenverarbeitungsprozessen.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Textklassifikation: Repräsentation

Nach Tokenisierung wird Text durch Vektor repräsentiert.

Vektorraummodell: Vektor der Worthäufigkeiten für probabilistische

Modelle. TFIDF-Repräsentation für lineare Verfahren.

Wortreihenfolge bleibt unberücksichtigt. Vektorraummodell mit N-Grammen:

Wird für Spamerkennung verwendet. Jedes N-Gramm durch Dimension repräsentiert, oder Sparse Binary Polynomial Hashing oder Orthogonal Sparse N-Grams.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Repräsentation

Jedes N-Gramm durch Dimension repräsentiert, Nur N-Gramme, die auch tatsächlich auftreten.

Sparse Binary Polynomial Hashing Fenster der Breite N wird über Text geschoben, Jede Teilmenge von bis zu N Tokens, die in dieser

Reihenfolge auftauchen und das am weitesten rechts stehende Token beinhalten, ist eine Dimension,

Orthogonal Sparse Bigrams. Fenster der Breite N wird über Text geschoben, Jedes Paar aus einem beliebigen Token im Fenster

und dem am rechten Fensterrand stehenden Token ist ein Merkmal.

SBPH und OSB: N-Gramme mit Platzhaltern.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Klassifikator / Entscheidungsfunktion

Für eine binäre Klassifikation (y= +1 oder -1) wird eine Entscheidungsfunktion f(x) gelernt.

Je größer f(x), desto wahrscheinlicher ist, dass x zur Klasse gehört.

Wenn f(x) , dann entscheide h(x) = +1, sonst h(x) = -1.

Klassifikator h(x), Entscheidungsfunktion f(x). Der Wert für verschiebt „false positives“ zu „false

negatives“. Optimaler Wert hängt von Kosten einer positiven

oder negativen Fehlklassifikation ab.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Evaluation von Textklassifikatoren

Fehlklassifikationswahrscheinlichkeit Häufig nicht aussagekräftig, weil P(+1) sehr klein. Wie gut sind 5% Fehler, wenn P(+1)=3%? Idee: Nicht Klassifikator bewerten, sondern

Entscheidungsfunktion. Precision / Recall

Precision-Recall-Kurve bewertet Entscheidungsfunktion, Jeder Wert für entspricht Punkt auf P-R-Kurve. F-Measure: „Durchschnitt“ aus Precision und Recall.

Receiver Operating Characteristic (ROC-Kurve) Bewertet Entscheidungsfunktion, Fläche unter ROC-Kurve = P(positives Beispiel hat

höheren f-Wert als negatives Beispiel)

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

ROC-Analyse

Entscheidungsfunktion + Schwellwert = Klassifikator.

Großer Schwellwert: Mehr positive Bsp falsch. Kleiner Schwellwert: Mehr negative Bsp falsch. Bewertung der Entscheidungsfunktion unabhängig

vom konkreten Schwellwert. Receiver-Operating-Characteristic-Analyse Kommt aus der Radartechnik, im 2. Weltkrieg

entwickelt. Bewertung der Qualität von

Entscheidungsfunktionen.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

ROC-Kurven Charakterisieren das Verhalten des

Klassifikators für alle möglichen Schwellwerte. X-Achse: „False Positives“: Anzahl negativer

Beispiele, die als positiv klassifiziert werden. Y-Achse: „True Positives“: Anzahl positiver

Beispiele, die als positiv klassifiziert werden.

False Positives

zufälliges Ratenbessere Funktionperfekte Funktion

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Bestimmen der ROC-Kurve von f

Für alle positiven Beispiele xp in Testmenge Füge f(xp) in sortierte Liste Lp ein.

Für alle negativen Beispiele xn in Testmenge Füge f(xn) in sortierte Liste Ln ein.

tp = fp = 0 Wiederhole solange Lp und Ln nicht leer sind.

Wenn Lp Element Ln Element dann increment(tp) und Lp = LP Next.

Wenn Ln Element Lp Element dann increment(fp) und Ln = Ln Next.

Zeichne neuen Punkt (fp, tp)

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Flächeninhalt der ROC-Kurve

Flächeninhalt AUC kann durch Integrieren (Summieren der Trapez-Flächeninhalte) bestimmt werden.

p = zufällig gezogenes Positivbeispiel n = zufällig gezogenes Negativbeispiel Theorem: AUC = P(f(p) > f(n)).

Beweisidee: ROC-Kurve mit nur einem Positiv- und einem Negativbeispiel (Flächeninhalt 0 oder 1); Durchschnitt vieler solcher Kurven = AUC.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Precision / Recall Alternative zur ROC-Analyse. Stammt aus dem Information Retrieval.

Precision: P(richtig | als positiv erkannt) Recall: P(als positiv erkannt | ist positiv)

True positivesPrecision=

True + false positives

True positivesRecall=

True positive + false negatives

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Precision / Recall

Zusammenfassungen der Kurve in einer Zahl: Maximum F-Measure: Maximum über alls (p,r)-Paare

auf der Kurve:

Precision-Recall-Breakeven-Point: Derjenige Wert für den gilt:

Precision() = Recall() = PRBEP.

2 Precision RecallF-measure=

Precision + Recall

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Precision / Recall Trade-Off

Precision-/Recall-Kurven Welcher Klassifikator ist der Beste / Schlechteste

precision

recall

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Bestimmen der Performance-Maße

Performance auf Trainingsmenge extrem optimistischer Schätzer für Performance für unbekannte Texte.

Zum Schätzen der Performance werden Texte verwendet, die nicht zum Trainieren verwendet wurden.

Training-und-Test: Verwende 80% der Daten zum Trainieren, 20% der Daten zum Messen der ROC-Kurve, P-R-Kurve, oder Fehlklassifikationswahrsch.

N-Fold-Cross-Validation: Teile Daten in n Teile, wiederholtes Trainieren mit n-1 Teilen.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Fehlerschätzung

Algorithmus Training-and-Test Aufteilen der Datenbank in Trainingsmenge und

Testmenge. h1 = Lernalgorithmus (Trainingsmenge) Bestimme Ê anhand der Testmenge. h = Lernalgorithmus (alle Beispiele) Liefere Hypothese h zusammen mit Fehlerschätzer

Training-and-Test ist für große Datenbanken gut anwendbar.

Problematisch für kleine Datenbanken

ÊÊÊ

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

N-Fold Cross-Validation Algorithmus N-CV (Beispiele S)

Bilde n etwa gleich große Blöcke S1, ..., Sn von Beispielen, die zusammen S ergeben. Ê=0.

For i = 1 ... N h = Lernalgorithmus (S \ Si) Ê = Ê + empirischer Fehler von h auf Si

Ê = Ê/N h = Lernalgorithmus (S) Liefere Hypothese h mit Fehlerschätzer

Wenn |S| = n, heisst das Verfahren Leave-one-Out. Nur leicht pessimistischer Schätzer.

ÊÊÊ

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Lineare Klassifikatoren

0T)( wf xwx

))(()( xx fsigny

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Lineare Klassifikatoren

Umformulierung mit zusätzlichem, konstanten Eingabeattribut x0=1:

0T)( wf xwx

))(()( xx fsigny

)..0(T

0)..1(T

...)...(...)...(

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Rocchio

: Mittelpunkt der neg. Beispiele : Mittelpunkt der pos. Beispiele Trennebene: Normalenvektor = (x+1-x-1)

Bestimmung von w0: Mittelpunkt (x+1+x-1)/2 muss auf der Ebene liegen.

011 )()( wf xxxx

0111111 02/))(()2/)((

wf xxxxxx

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Rocchio

Trennebenen hat maximalen Abstand von den Mittelpunkten der Klassen.

Trainingsbeispiele können falsch klassifiziert werden.

Differenz der Mittelwerte kann schlechter Normalenvektor fürDiskrimination sein.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Perzeptron

Lineares Modell:

Ziel: Für alle Beispiele (xi, +1):

Für alle Beispiele (xi, -1):

xwx T)( f

0)( T iif xwx

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Perzeptron

Lineares Modell:

Ziel: Für alle Beispiele (xi, +1):

Für alle Beispiele (xi, -1):

Ziel: Für alle Beispiele: = Beispiel liegt auf der richtigen

Seite der Ebene.

0)( T iiii yfy xwx

xwx T)( f

0)( T iif xwx

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Perzeptron

Lineares Modell:

Ziel: Für alle Beispiele:

Perzeptron-Optimierungskriterium:

0)( T iiii yfy xwx

xwx T)( f

T 0,min)(x

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Perzeptron

Lineares Modell:

Ziel: Für alle Beispiele:

Subgradient für Beispiel (xi, yi):

0)( T iiii yfy xwx

xwx T)( f

T 0,min)(x

0wenn,0)(

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Perzeptron

Lineares Modell:

Subgradient für Beispiel (xi, yi):

Gradientenaufstieg: Wiederhole, für alle Beispiele mit

xwx T)( f

T 0,min)(x

0wenn,0)(

iiy xww

0T iiy xw

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Perzeptron-Algorithmus

Lineares Modell:

Perzeptron-Trainingsalgorithmus: Solange noch Beispiele (xi, yi) mit der Hypothese

inkonsistent sind, iteriere über alle Beispiele Wenn dann

xwx T)( f

0T iiy xwiiy xww

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Perzeptron-Algorithmus

Perzeptron findet immer eine Trennebene, wenn eine existiert (Optimierungskriterium ist konkav).

Existiert immer eine Trennebene?

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Margin-Perzeptron

Perzeptron-Klassifikation:

Perzeptron: für alle Beispiele muss gelten = Beispiel liegt auf der richtigen

Seite der Ebene. Margin-Perzeptron:

= Beispiel mindestens von

Trennebene entfernt.

0T iiy xw

xwx T)( f

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Margin-Perzeptron-Algorithmus

Lineares Modell:

Perzeptron-Trainingsalgorithmus: Solange noch Beispiele (xi, yi) mit der Hypothese

inkonsistent sind, iteriere über alle Beispiele

Wenn dann

xwx T)( f

iiy xww

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Margin-Maximierung

Perzeptron: für alle Beispiele muss gelten

Margin-Perzeptron: Finde Ebene, die alle Beispiele

mindestens von Ebene entfernt. Fester, voreingestellter Wert .

Margin-Maximierung: Finde Ebene, die alle Beispiele

mindestens von Ebene entfernt. Für den größtmöglichen Wert .

0T iiy xw

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Margin-Maximierung

Margin-Maximierung: Finde Ebene, die alle Beispiele

mindestens von Ebene entfernt. Für den größtmöglichen Wert .

Maximiere unter der Nebenbedingungen: für alle Beispiele (xi, yi) gelte

= Minimiere |w| unter der Nebenbedingung: für alle Beispiele (xi, yi):

w1T iiy xw

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Soft-Margin-Maximierung

Hard-Margin-Maximierung: Minimiere |w| unter der

Nebenbedingungen: für alle Beispiele (xi, yi):

Soft-Margin-Maximierung: Minimiere unter den

Alle i 0. Soft-Margin-Ebene existiert immer,

Hard-Margin-Ebene nicht!

1T iiy xw

Slack i

Margin 1/|w|

iiiy 1Txw

i iC || w

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Soft-Margin-Maximierung: Minimiere unter den

Alle i 0.

Einsetzen von i in Optimierungskriterium ergibt Minimiere:

Margin 1/|w|

iiiy 1Txw

i iC || w

i iiyC }1,0max{|| Txww

Slack i

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Soft-Margin-Maximierung: Minimiere:

Minimierung mit Gradientenverfahren.

Annäherung durch differenzierbare Variante (Huber- statt Hinge-Loss), dann Newton-Verfahren.

Kriterium ist konvex, es gibt genau ein Minimum.

Primale Support Vector Machine.

Margin 1/|w|

i iiyC }1,0max{|| Txww

Slack i

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Soft-Margin-Maximierung: Minimiere:

Minimierung mit Gradientenverfahren.

Wiederhole:

i iiH yCE }1,0max{||)( Txwww

Enthält Summe über alle Beispiele

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Logistische Regression

SVM: großer Entscheidungsfunktionswert ~ hohe Sicherheit der Vorhersage.

Aber: beim lernen nicht auf korrekte Kalibrierung der Klassenwahrscheinlichkeiten optimiert.

f(x)=18.3 Risiko eines Fehlers?

Logistische Regression: Vorhersage der Klassenwahrscheinlichkeit.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Bayes‘ Regel:

Log-odd ratio:

)()exp(1

)1()1|()1()1|(

)1()1|()|1(

yPypyPyp

yPypyP

)1()1|(

)1()1|(ln

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Likelihood jeder Klasse normalverteilt, gemeinsame Kovarianzmatrix für beide Klassen.

Logg-odds ratio:

1)|( 1T

)1(ln)(

)1(ln)()(

)1()()(21

exp||)2(

)1()()(21

exp||)2(

12/12/

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Likelihood jeder Klasse normalverteilt, gemeinsame Kovarianzmatrix für beide Klassen.

Logg-odds ratio:

1)|( 1T

)1(ln)(

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Wenn zwei klassen jeweils normalverteilte Likelihood mit derselben Kovarianzmatrix haben, dann nimmt P(y|x) diese Form an:

Funktion elogistisch

torKlassifikalinearer

)()exp(1

1)|( wy

P(y|x)

ywx+w0

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Bisher: Motivation der Form des logistischen Klassifikationsmodells.

Falls Klassenverteilungen bekannt wären, könnten wir w und w0 aus +1, -1 und herleiten.

Sind aber nicht bekannt. Verteilungsannahme muss auch nicht stimmen.

Jetzt: Wie finden wir tatsächlich Parameter w und w0?

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Prior über Parameter: Normalverteilung, w ~ N[0,‘].

Posterior:

Verlustfunktion:

[[ 1]] [[ 1]]T T

( | ) ( | , ) ( )

( ) (1 ( )) ( )i i

N y yi ii

P L p y p

w x w w

w x w x w

1 '))(1log(]]1[[)(log]]1[[

)|(log),(

i i yy

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Verlustfunktion ist konvex und differenzierbar. Gradientenabstieg führt zum Minimum.

Verlustfunktionen Logistic Regression und SVM

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Multiklassen-Klassifikation

Binäre Klassifikation: Lineare Klassifikation:

Multiklassen-Klassifikation: Endliche Menge von Klassen-Labels,

Ansatz: Statt jetzt

}1,1{ x

)( 0wsign wxx

)( 0wsign wxx ),(maxarg yfy xx

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Lernen mit strukturierten Ausgaben

Klassifikation bei mehr als zwei Klassen: f bekommt jetzt zwei Parameter.

Gemeinsame Merkmale von Ein- und Ausgabe:

Gleicher Ansatz für Multiklassen, Sequenz- und Struktur-Lernen, Ranking.

),(maxarg* yfy y x

),),( T yyf xwx

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Constraints bei normaler SVM: Für alle (xi, yi):

Constraints mit strukturierten Ausgaben: Für alle (xi, yi): und alle y ≠ yi:

iiiy 1Txw

1),(),(

1),(),(T

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Gegeben: Wiederhole bis alle Sequenzen korrekt

vorhergesagt werden. Iteriere über alle Beispiele (xi, yi).

Bestimme Wenn (Margin-Verletzung) dann

füge Constraint dem Working Set hinzu.

Löse Optimierungsproblem für Eingabe xi, Ausgabe yi, und negative Pseudo-Beispiele y (working set).

Liefere w zurück.

),(),...,,( 11 mmL yxyx

),maxarg T yxwy yy ii

1),), TT yxwyxw iii

iiii 1),), TT yxwyxw

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Multiklassen-SVM

Klassifikation bei mehr als zwei Klassen:

Multiklassen-Merkmale:

),(maxarg* yfy y x

),),( T yyf xwx

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Multiklassen-SVM

Jede Klasse hat privaten Abschnitt des Gewichtsvektors:

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Multiklassen-SVM

Jede Klasse hat privaten Abschnitt des Gewichtsvektors: Beispiel:

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Klassifikation mit Taxonomien

Klassen in Baumstruktur:

),(maxarg* yxy fy

),),( T yxwyx f

),...,( 1 dyyy

]][[...

xxyxyx

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Klassifikation mit Taxonomien

Jeder Knoten hat einen privaten Abschnitt des Gewichtsvektors.

Pfade teilen sich Abschnitte, wenn sie gemeinsame Knoten beinhalten.

y y ( )

, ... ... ...

[[ ]]d

w x w x w x

1 11 1 1

[[ ]]... ...

... ...

......

y n n kd

yi jd d

d dn ky n

w x y y

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Sequentielle Ein-/Ausgaben

Z.B. Wortarterkennung:

Eigennamenerkennung, Informationsextraktion:

Gemeinsame Repräsentation von Ein- und Ausgabe.

),(maxarg* yxfy y

“Curiosity kills the cat.” y=x= <Noun, Verb, Determiner, Noun>→

“Barbie meets Ken.” y=x= <Person, -, Person>→

),),( T yxwx yf

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Label-label: Label-Beobachtung:

Gemeinsamer Merkmalsvektor (x,y)=∑t(…,φ123(yt,yt+1),…,φ234(xt,yt),...)T

Gewichtsvektor w=(…,w123,…,w234,…)T

y1 y3 y4y2

x1 x3x2 x4φ123(yt,yt+1) = [[yt=“Noun” yt+1=“Verb”]]

φ234(xt,yt) = [[yt=“Noun” xt = “cat”]]∑tφi(yt,yt+1).

∑tφi(xt,yt).

Curiosity kills the cat

Sequentielle Ein-/Ausgaben Attribut für jedes Paar benachbarter

Labels yt und yt+1.

Attribut für jedes Paar aus Eingabe und Ausgabe.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Sequentielle Ein-/Ausgaben: Dekodierung

Um eine Sequenz zu klassifizieren, muss

berechnet werden. Das argmax geht über alle möglichen Sequenzen

(exponentiell viele in der Länge). summiert über Merkmale

benachbarter Label-Paare und Merkmale von xi-yi-Paaren.

Mit dynamischer Programmierung kann argmax in linearer Zeit berechnet werden (Viterbi).

),(maxarg* yxy y f

),),( T yxwyx f

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Gemeinsamer Merkmalsvektor (x,y)=∑t(…,φ123(yt,yt+1),…,φ234(xt,yt),...)T

Finde argmaxy wT(x,y) effizient mit Transitionsmatrix A={a,} und Beobachtungsmatrix Bx={bt,(x)}, , {•,N,V,D}:

HM SVM benutzt 2-best Viterbi Dekodierung.

y1 y3 y4y2

x1 x3x2 x4

φ123(yt,yt+1) = [[yt=“Noun” yt+1=“Verb”]]

φ234(xt,yt) = [[yt=“Noun” xt = “John”]]

D DDCuriosity kills the cat

aN,V aV,D

a•,N

b4,N(x)b2,N(x)

b3,N(x)b1,N(x)

Sequentielle Ein-/Ausgaben: Dekodierung

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Viterbi-Algorithmus

Definition: =Score, der in wT(x,y) erzeugt wird, wenn

yt= und yt+1=. Definition: =Score, der in wT(x,y) erzeugt wird, wenn

yt= und Wort xt erscheint.

Gesucht:

),( 1 tt yySa

),()( ttt xySxb

),...,,,...,(maxarg),(maxarg 11,...,T

1 NNyy xxyySN

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Viterbi-Algorithmus, Theorem

Theorem:

Beweis:

Lineare Bestimmung des höchst-scorenden Pfades mit dynamischer Programmierung.

)|,...,,,,...,(max)( 111,..., 11 tttyyt yyyS

)()(max)( 11 ttt ba x

)()(max

)()),...,,,...,((maxmax

,...)|(,...)|(),...,,,...,(max

),...,,,,...,(max)(

111,...,

11111,...,

1111,...,1

ttttttyy

tttyyt

xbaxxyyS

yxSyySxxyyS

xxyyyS

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

wT(x,<N,V,Det,N>) ≥ wT(x,<N,N,N,N>)

wT(x,<N,V,Det,N>) ≥ wT(x,<N,N,N,V>)

wT(x,<N,V,Det,N>) ≥ wT(x,<N,N,V,N>)

wT(x,<N,V,Det,N>) ≥ wT(x,<N,V,N,N>)

Beispiel: POS-Tagging (Wortarterkennung) Satz x=“Curiosity kills the cat” Gewünscht:

Explizit:argmaxy wT( x , y ) = <N,V,Det,N>… …

ZU VIELE!!!

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Hidden Markov Support Vector Machine.

Large-Margin-Ansatz: = 1/|w|.

Iteratives Training. Negative Constraints werden hinzugefügt, wenn

beim Training Fehler auftritt.

s.d. "i "yyi wT((xi,yi) - (xi,y)) ≥ 1

min ½ |w|2 + C∑iξi

"i ξi ≥ 0.

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Gegeben: Wiederhole bis alle Sequenzen korrekt

vorhergesagt werden. Iteriere über alle Beispiele (xi, yi).

Bestimme Wenn (Margin-Verletzung) dann

füge Constraint dem Working Set hinzu.

Löse Optimierungsproblem für Eingabe xi, Ausgabe yi, und negative Pseudo-Beispiele y (working set).

Liefere w zurück.

),(),...,,( 11 mmL yxyx

),maxarg T yxwy yy ii

1),), TT yxwyxw iii

iiii 1),), TT yxwyxw

Scheffer/S

awade: S

prachtechnologie

Scheffer/H

aider/Prasse/D

Fragen?

Universität Potsdam Institut für Informatik Lehrstuhl Maschinelles Lernen Textklassifikation und...

Documents