Präsentiert von Torben Pastucham Seminar für Computerlinguistik der Uni Heidelberg

Datum: 01.07.2002

Machine Learning Verfahren X

CXT verwendet „Support Vector Machines“...

Neuronale Netzwerke

Genetische Algorithmen

SUPPORT VECTOR MACHINES

Erstmals Thema 1992 auf der COLT-92

Praxisrelevante Forschung seit 1995

Findet Verwendung in folgenden Gebieten...

Biometrie (z.B. Gesichtserkennung)

Computerlinguistik (z.B. Textkategorisierung)

Allgemein gesprochen ... „Mustererkennung“

Kombination von mehreren bekannten Konzepten

Ermöglicht das Lernen von Klassifizierungen

Eine Einführung in „Support Vector Machines“

SVMs & Chunking

Praxis-Demonstration: „Proof of Concept“

Fand erste Anwendung im „Perceptron“ (1956)

Hyperebene :

0b

Σ

w x

Hyperebene :

0b

Σ

w x

w

x

b

0

0

0

0

b

b

x b w

w x w b

w x

w x

0

0

0

0

b

b

x b w

w x w b

w x

w x

x-b

0

Wenn

dann

1 2

1 2

x x

x x 0

Wenn

dann

1 2

1 2

x x

x x

Es existieren relativ einfache Algorithmen

Algorithmen sind schnell und massendatentauglich

Nur linear separable Klassen können gelernt werdenLösung ist nicht immer ideal

Gesucht ist also

x

y

vx

y

v

x

y

2 2( )R x y

xR

y

v

2 2( )R x y

xR

y

v

R

R

Hyperebene (Punkt)

: n m

SVM hängen ausschließlich von den Skalarproduktender Trainingsdaten ab

x y ( ) ( ) x y s

n m

( , )K x y

Kernel-Funktion

Ein Beispiel für einen Kernel: Der Polynomial-Kernel2

( , )K x y x y

2

1 1

2 2

x y

x y

2 21 1

1 2 1 22 2

2 2

2 2

x y

x x y y

x y

21

1 22

2

2

x

x x

x

1

2

x

x

( ) x

Polynomialer Kernel

( , )d

K x y x y

Radial Basis Function Kernel (RBF)2

22( , )K e

x y

x y

Sigmoider Kernel

, tanhK x y x y

Nur linear separable Klassen können gelernt werdenLösung ist nicht immer ideal

: 0b w x

Example bw x

w

< 0 > 0-1

+1

Berechnung der „wirklichen Breite“

1

1

b

b

w x

w x

1w

1

2

1

2

1

w wx x

w w

w x w xw

w

b

b

wx

w

wx

w

Formalisierung der Trainingsdaten

1

, 1 1

i

i iin

x

y oder

x

x

Nun ist folgendes zu erreichen:

w w

1i iy b w xUnter der Bedingung, dass:

Minimiere:

…diese Funktion

1 , 1

( )l l

i i j i j i ji i j

L y y

α x x

1 , 1

( ) ( , )l l

i i j i j i ji i j

L y y K

α x x

1

0

0, 1,...,

l

i ii

i

y

i l

Maximiere

unter diesen Bedingungen

Für die Lösung gilt…

0

0i

i

liegt auf demRand

für alleanderen

x

x

Die Trainingsdaten sind folgendermaßen aufgebaut

Wort: wi-2 wi-1 wi wi+1 wi+2

POS: ti-2 ti-2 ti-2 ti-2 ti-2

vi

yiz.B.: +1, wenn „wi ist Anfang einer NP“

Und -1, wenn „wi ist nicht Anf. einer NP“

Für die Trainingsdaten wurde der Negr@-Korpus (V2)verwendet. (ca. 10000 Sätze ca. 170000 Wörter)

Was verursacht die Probleme beim Chunken?

Es muss der „passende“ Kernel gefunden werdenEs gilt, alle Parameter ideal zu wählen

Der Algorithmus ist vergleichsweise langsamKomplexität: O(n2) bis O(n3)

Die CSVM-Klasse ist aufgabenunabhängig.Möglichst allgemeine und effiziente Implementierung

IRChunker

CSVM

IRTagger

Output

CPoCDemo