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

2

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Textklassifikation,Informationsextraktion

Scheffer/S

awade: S

prachtechnologie

3

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

4

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

5

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

6

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

7

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

8

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

9

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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.

True

Pos

itive

s

False Positives

zufälliges Ratenbessere Funktionperfekte Funktion

Scheffer/S

awade: S

prachtechnologie

10

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

11

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

12

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

13

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

14

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Precision / Recall Trade-Off

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

precision

recall

Scheffer/S

awade: S

prachtechnologie

15

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

16

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

m

ÊÊÊ

%20

)1(

Scheffer/S

awade: S

prachtechnologie

17

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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.

m

ÊÊÊ

)1(

Scheffer/S

awade: S

prachtechnologie

18

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Lineare Klassifikatoren

||

)(

w

xf

||0

w

w

0T)( wf xwx

))(()( xx fsigny

Scheffer/S

awade: S

prachtechnologie

19

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Lineare Klassifikatoren

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

0T)( wf xwx

))(()( xx fsigny

)..0(T

)..0(

1

0

100

1

1

0)..1(T

)..1(

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

)(

nn

n

n

n

n

nn

x

x

x

wwww

x

x

ww

wf

xw

xwx

Scheffer/S

awade: S

prachtechnologie

20

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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.

+

--

--

++

+

+

x-1

x+1

w

011 )()( wf xxxx

1x

1x

0

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

w

wf xxxxxx

Scheffer/S

awade: S

prachtechnologie

21

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

22

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Perzeptron

Lineares Modell:

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

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

+

--

--

++

+

+

xwx T)( f

0)( T iif xwx

0)( T iif xwx

Scheffer/S

awade: S

prachtechnologie

23

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

0)( T iif xwx

Scheffer/S

awade: S

prachtechnologie

24

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Perzeptron

Lineares Modell:

Ziel: Für alle Beispiele:

Perzeptron-Optimierungskriterium:

0)( T iiii yfy xwx

+

--

--

++

+

+

xwx T)( f

Ly

iiP

ii

yJ),(

T 0,min)(x

xww

Scheffer/S

awade: S

prachtechnologie

25

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Perzeptron

Lineares Modell:

Ziel: Für alle Beispiele:

Perzeptron-Optimierungskriterium:

Subgradient für Beispiel (xi, yi):

0)( T iiii yfy xwx

+

--

--

++

+

+

xwx T)( f

Ly

iiP

ii

yJ),(

T 0,min)(x

xww

sonst

0wenn,0)(

T

ii

iiPi

y

yJ

x

xww

Scheffer/S

awade: S

prachtechnologie

26

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Perzeptron

Lineares Modell:

Perzeptron-Optimierungskriterium:

Subgradient für Beispiel (xi, yi):

Gradientenaufstieg: Wiederhole, für alle Beispiele mit

+

--

--

++

+

+

xwx T)( f

Ly

iiP

ii

yJ),(

T 0,min)(x

xww

sonst

0wenn,0)(

T

ii

iiPi

y

yJ

x

xww

iiy xww

0T iiy xw

Scheffer/S

awade: S

prachtechnologie

27

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

28

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Perzeptron-Algorithmus

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

Existiert immer eine Trennebene?

Scheffer/S

awade: S

prachtechnologie

29

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

+

--

--

++

+

+

+

--

--

++

+

+

iiy x

ww

||

T

xwx T)( f

Scheffer/S

awade: S

prachtechnologie

30

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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 x

w

w

||

T

iiy xww

Scheffer/S

awade: S

prachtechnologie

31

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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 .

+

--

--

++

+

+

+

--

--

++

+

+

iiy x

ww

||

T

0T iiy xw

Scheffer/S

awade: S

prachtechnologie

32

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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):

+

--

--

++

+

+

||

1

w1T iiy xw

iiy x

ww

||

T

iiy x

ww

||

T

+

--

--

++

+

+

Scheffer/S

awade: S

prachtechnologie

33

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Soft-Margin-Maximierung

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

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

Soft-Margin-Maximierung: Minimiere unter den

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

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

||

1

w

Scheffer/S

awade: S

prachtechnologie

34

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Soft-Margin-Maximierung

Soft-Margin-Maximierung: Minimiere unter den

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

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

35

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Soft-Margin-Maximierung

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

36

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Soft-Margin-Maximierung

Soft-Margin-Maximierung: Minimiere:

Minimierung mit Gradientenverfahren.

Wiederhole:

+

--

--

++

+

+

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

w

www

)(HE

Enthält Summe über alle Beispiele

Scheffer/S

awade: S

prachtechnologie

37

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

38

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Logistische Regression

Bayes‘ Regel:

Log-odd ratio:

)()exp(1

1

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

1

1

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

)1()1|()|1(

aa

yPypyPyp

yPypyPyp

yPypyP

xx

xx

xx

)1()1|(

)1()1|(ln

yPyp

yPypa

x

x

Scheffer/S

awade: S

prachtechnologie

39

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Logistische Regression

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

Logg-odds ratio:

)()(

2

1exp

||)2(

1)|( 1T

2/12/

xxx

dyp

0

)1(

)1(ln)(

2

1)(

2

1)(

)1(

)1(ln)()(

2

1)()(

2

1

)1()()(21

exp||)2(

1

)1()()(21

exp||)2(

1

ln

11T

111T

1111

11T

111T

1

11T

12/12/

11T

12/12/

w

d

d

yP

yP

yP

yP

yP

yPa

x

xxxx

xx

xx

w

Scheffer/S

awade: S

prachtechnologie

40

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Logistische Regression

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

Logg-odds ratio:

)()(

2

1exp

||)2(

1)|( 1T

2/12/

xxx

dyp

0

)1(

)1(ln)(

2

1)(

2

1)( 1

1T11

1T111

1

w

yP

yPa

x

w

Scheffer/S

awade: S

prachtechnologie

41

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Logistische Regression

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

Funktion elogistisch

torKlassifikalinearer

00

)()exp(1

1)|( wy

wyyP

wx

wxx

P(y|x)

ywx+w0

Scheffer/S

awade: S

prachtechnologie

42

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Logistische Regression

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

43

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Logistische Regression

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

Posterior:

Verlustfunktion:

1

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

1

( | ) ( | , ) ( )

( ) (1 ( )) ( )i i

N

i ii

N y yi ii

P L p y p

p

w x w w

w x w x w

2

TTT

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

)|(log),(

ww

xwxw

ww

iii

N

i i yy

LpLE

Scheffer/S

awade: S

prachtechnologie

44

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Logistische Regression

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

Verlustfunktionen Logistic Regression und SVM

Scheffer/S

awade: S

prachtechnologie

45

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Multiklassen-Klassifikation

Binäre Klassifikation: Lineare Klassifikation:

Multiklassen-Klassifikation: Endliche Menge von Klassen-Labels,

Ansatz: Statt jetzt

}1,1{ x

)( 0wsign wxx

yx

Yy

)( 0wsign wxx ),(maxarg yfy xx

Scheffer/S

awade: S

prachtechnologie

46

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

47

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Lernen mit strukturierten Ausgaben

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

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

iiiy 1Txw

iiii

iiii

yy

yy

1),(),(

1),(),(T

TT

xxw

xwxw

Scheffer/S

awade: S

prachtechnologie

48

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Lernen mit strukturierten Ausgaben

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

49

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Multiklassen-SVM

Klassifikation bei mehr als zwei Klassen:

Multiklassen-Merkmale:

),(maxarg* yfy y x

),),( T yyf xwx

]])[[

...

]])[[

)()),

]][[

...

]][[

)(

1

1

k

k

yy

yy

yy

yy

yy

y

x

x

xx

Scheffer/S

awade: S

prachtechnologie

50

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Multiklassen-SVM

Jede Klasse hat privaten Abschnitt des Gewichtsvektors:

]][[

...

]][[

...

]][[

...

]][[

...

...

...

]][[

...

]][[

),

1

1

11

T

1

1

1TT

1

1

kn

k

n

ny

y

ny

y

k

yyx

yyx

yyx

yyx

w

w

w

w

yy

yy

y

k

k

xwxw

Scheffer/S

awade: S

prachtechnologie

51

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Multiklassen-SVM

Jede Klasse hat privaten Abschnitt des Gewichtsvektors: Beispiel:

0

0

0

0

]][[

]][[

]][[

),2

1

T

2

1

2

1

2

1

3

2

1

2

1T2

T

3

3

2

2

1

1

x

x

w

w

w

w

w

w

yy

yy

yy

x

xy

y

y

y

y

y

y

wxw

Scheffer/S

awade: S

prachtechnologie

52

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Klassifikation mit Taxonomien

Klassen in Baumstruktur:

),(maxarg* yxy fy

),),( T yxwyx f

),...,( 1 dyyy

)(

...

)(

)(

1

dy

y

y

]][[

...

]][[...

]][[

...

]][[

)(

...

)(

)(),1

11

11

1

1

dn

d

dd

n

d

yy

yy

yy

yy

y

y

xxyxyx

Scheffer/S

awade: S

prachtechnologie

53

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Klassifikation mit Taxonomien

Jeder Knoten hat einen privaten Abschnitt des Gewichtsvektors.

Pfade teilen sich Abschnitte, wenn sie gemeinsame Knoten beinhalten.

1

1 1 1

T T T

1 11

1 1

T

1

y y ( )

, ... ... ...

( )

[[ ]]

...

[[ ]]

...

[[ ]]

...

[[ ]]d

dd d

k

d d

d dk

y

yy y

y y

y y

y y

y y

w x w x w x

w x

11

11

1 11 1 1

1 11

T

1 1

11

[[ ]]... ...

[[ ]]

... ...

[[ ]]

......

[[ ]]

i

ij

ddkd

ddkd

y

y n n kd

yi jd d

ky

d dn ky n

w x y y

w x y y

w x y y

w x y y

w x

Scheffer/S

awade: S

prachtechnologie

54

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

55

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

56

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

57

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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”]]

NNN

VV V

D DDCuriosity kills the cat

N

V

D

aN,V aV,D

aD,N

a•,N

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

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

•

Sequentielle Ein-/Ausgaben: Dekodierung

Scheffer/S

awade: S

prachtechnologie

58

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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

yxwy

Scheffer/S

awade: S

prachtechnologie

59

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Viterbi-Algorithmus, Theorem

Theorem:

Beweis:

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

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

txx

)()(max)( 11 ttt ba x

)()(max

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

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

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

1

111,...,

11111,...,

1111,...,1

11

1

1

tt

tttyy

ttttttyy

tttyyt

xba

xbaxxyyS

yxSyySxxyyS

xxyyyS

t

t

t

Scheffer/S

awade: S

prachtechnologie

60

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

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!!!

Lernen mit strukturierten Ausgaben

Scheffer/S

awade: S

prachtechnologie

61

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Lernen mit strukturierten Ausgaben

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 ξi ≥ 0.

Scheffer/S

awade: S

prachtechnologie

62

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Lernen mit strukturierten Ausgaben

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

63

Scheffer/H

aider/Prasse/D

ick: Sprachtechnologie

Fragen?