Universität Potsdam Institut für Informatik

Lehrstuhl Maschinelles Lernen

Lineare Klassifikatoren IV

Christoph Sawade, Blaine Nelson, Tobias Scheffer

Maschin

elle

s L

ern

en

Inhalt Klassifikationsproblem

Bayes‘sche Klassenentscheidung

MAP-Modell

Logistische Regression

Empirische Risikominimierung

Perzeptron, Support Vector Machine

Ridge Regression, LASSO

Kernel

Representer Theorem

Duales Perzeptron, Duale SVM

Mercer Map

Lernen mit strukturierter Ein- und Ausgabe

Taxonomie, Sequenzen, Ranking,…

Dekoder, Schnittebenenalgorithmus

2

Maschin

elle

s L

ern

en

3

Review: Binäre SVM

Klassifikation bei mehr als zwei Klassen:

𝑦 𝐱 = sign 𝑓𝛉 𝐱 , 𝑓𝛉 𝐱 = 𝜙 𝐱 T𝛉

Ein Parametervektor 𝛉

Optimierungsproblem:

min𝛉,𝛏

𝜆 𝜉𝑖𝑛𝑖=1 +

1

2𝛉T𝛉

unter den Nebenbedingungen

𝜉𝑖 ≥ 0 und 𝑦𝑖𝜙 𝐱𝑖

T𝛉 ≥ 1 − 𝜉𝑖

Verallgemeinerung für 𝑘 Klassen?

Maschin

elle

s L

ern

en

Review: Multi-Klassen Logistische Regression

In der Multi-Klassen Fall hat das lineare Modell

Entscheidungsfunktion : 𝑓𝛉 𝐱, 𝑦 = 𝜙 𝐱 T𝛉𝑦 + 𝑏𝑦

& Klassifikator : 𝑦 𝐱 = argmax𝑧∈𝑌

𝑓𝛉 𝐱, 𝑧

Logistisches Modell für den Multi-Klassen Fall:

𝑃 𝑦|𝐱, 𝛉 =exp 𝜙 𝐱 T𝛉𝑦 + 𝑏𝑦

exp 𝜙 𝐱 T𝛉𝑧 + 𝑏𝑧𝑧∈𝑌

Der Prior ist eine Normalverteilung; 𝑝 𝛉 = 𝑁 𝛉; 𝟎, 𝚺

Die Maximum-A-Posteriori-Parameter ist

𝛉MAP = argmin𝛉

log Σ𝑧∈𝑌exp 𝑓𝛉 𝑥𝑖 , 𝑧 − 𝑓𝛉 𝐱𝑖 , 𝑦𝑖 +𝛉T𝚺−1𝛉

2

𝑛

𝑖=1

4

Verlustfunktion Regularisierer

Maschin

elle

s L

ern

en

Verallgemeinerung auf Multi-Klassen Probleme

Multi-Klassen logistische Regression

𝑦 𝐱 = sign 𝑓𝛉 𝐱 wurde 𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦

Ein einziger Parametervektor 𝛉 wurde zu 𝛉 =

𝛉1, … , 𝛉𝑘T mit einer Komponente für jede Klasse

Für eine SVM mit 𝑘 Klassen

Regularisierer?

1

2𝛉T𝛉 becomes

1

2 𝛉𝑗

𝑇𝛉𝑗𝑘

𝑗=1

Abstand (Margin) Nebenbedingungen?

5

Maschin

elle

s L

ern

en

Verallgemeinerung auf Multi-Klassen Probleme

Multi-Klassen logistische Regression

𝑦 𝐱 = sign 𝑓𝛉 𝐱 wurde 𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦

Ein einziger Parametervektor 𝛉 wurde zu 𝛉 =

𝛉1, … , 𝛉𝑘T mit einer Komponente für jede Klasse

Für eine SVM mit 𝑘 Klassen

Regularisierer?

1

2𝛉T𝛉 wird

1

2 𝛉𝑗

𝑇𝛉𝑗𝑘

𝑗=1

Abstand (Margin) Nebenbedingungen?

𝑦𝑖𝜙 𝐱𝑖T𝛉 ≥ 1 − 𝜉𝑖 wird

∀𝑦 ≠ 𝑦𝑖 𝑓𝛉 𝐱𝑖 , 𝑦𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝑦 + 1 − 𝜉𝑖

6

Maschin

elle

s L

ern

en

[J.Weston, C.Watkins, 1999]

7

Multi-Klassen SVM

Klassifikation mit mehr als zwei Klassen:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦 , 𝑓𝛉 𝐱, 𝑦 = 𝜙 𝐱 T𝛉𝑦

Parametervektor für jede der möglichen 𝑘 Klassen

𝛉 = 𝛉1, … , 𝛉𝑘T

Optimierungsproblem:

min𝛉,𝛏

𝜆 𝜉𝑖𝑛𝑖=1 +

1

2 𝛉𝑗

𝑇𝛉𝑗𝑘

𝑗=1

unter den Nebenbedingungen

𝜉𝑖 ≥ 0 und ∀𝑦 ≠ 𝑦𝑖 𝑓𝛉 𝐱𝑖 , 𝑦𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝑦 + 1 − 𝜉𝑖

Maschin

elle

s L

ern

en

Multi-Klassen Feature-Mapping

Verschiedene Gewichtsvektoren kann auch als

unterschiedliche Abschnitte eines Gewichtsvektors

gesehen werden (vgl. Logistische Regression):

𝛉 = 𝛉1, … , 𝛉𝑘T

Gemeinsame Repräsentation von Ein- und

Ausgabe:

Φ 𝐱, 𝑦 = 2 =

𝟎𝜙 𝐱⋮𝟎

8

𝑘 gestapelte

Featurevektoren

Maschin

elle

s L

ern

en

9

Multi-Klassen Feature-Mapping

Klassifikation mit mehr als zwei Klassen:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦

Multi-Klassen-Kernel:

𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T𝛉

Λ 𝑦 =I 𝑦 = 1

⋮I 𝑦 = 𝑘

Φ 𝐱, 𝑦 = 𝜙 𝐱 ⨂Λ 𝑦 =𝜙 𝐱 I 𝑦 = 1

⋮𝜙 𝐱 I 𝑦 = 𝑘

Maschin

elle

s L

ern

en

10

Multi-Klassen Kernel-Kodierung

Klassifikation mit mehr als zwei Klassen:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦

Multi-Klassen-Kernel:

𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T𝛉

Φ 𝐱, 𝑦 =𝑥1𝑥2

⨂I 𝑦 = 1

I 𝑦 = 2=

𝑥1I 𝑦 = 1

𝑥2I 𝑦 = 1

𝑥1I 𝑦 = 2

𝑥2I 𝑦 = 2

𝑘 𝐱𝑖 , 𝑦𝑖 , 𝐱𝑗 , 𝑦𝑗 = Φ 𝐱𝑖 , 𝑦𝑖𝑇Φ 𝐱𝑗 , 𝑦𝑗

= I 𝑦𝑖 = 𝑦𝑗1 if𝑦𝑖=𝑦𝑗0 otherwise

Maschin

elle

s L

ern

en

11

Multi-Klassen Kernel-Kodierung

Klassifikation mit mehr als zwei Klassen:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦

Multi-Klassen-Kernel:

𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T𝛉

Φ 𝐱, 𝑦 =𝑥1𝑥2

⨂I 𝑦 = 1

I 𝑦 = 2=

𝑥1I 𝑦 = 1

𝑥2I 𝑦 = 1

𝑥1I 𝑦 = 2

𝑥2I 𝑦 = 2

𝑘 𝐱𝑖 , 𝑦𝑖 , 𝐱𝑗 , 𝑦𝑗 = Φ 𝐱𝑖 , 𝑦𝑖𝑇Φ 𝐱𝑗 , 𝑦𝑗

= I 𝑦𝑖 = 𝑦𝑗1 falls 𝑦𝑖=𝑦𝑗0 sonst

Maschin

elle

s L

ern

en

12

Klassifikation mit Information über Klassen

Klassen haben gewisse Merkmale:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦

𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T𝛉, Φ 𝐱, 𝑦 = 𝜙 𝐱 ⨂Λ 𝑦

𝑘 𝐱𝑖 , 𝑦𝑖 , 𝐱𝑗 , 𝑦𝑗 = Φ 𝐱𝑖 , 𝑦𝑖TΦ 𝐱𝑗 , 𝑦𝑗

= 𝜙 𝐱𝑖T𝜙 𝐱𝑗 Λ 𝑦𝑖

TΛ 𝑦𝑗

= 𝑘 𝐱𝑖 , 𝐱𝑗 Λ 𝑦𝑖TΛ 𝑦𝑗

𝐾𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒𝑛𝑧 𝑧𝑤𝑖𝑠𝑐ℎ𝑒𝑛 𝐾𝑙𝑎𝑠𝑠𝑒𝑛

Maschin

elle

s L

ern

en

13

Klassifikation mit Informationen über Klassen

Klassen haben gewisse Merkmale:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦

𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T𝛉, Φ 𝐱, 𝑦 = 𝜙 𝐱 ⨂Λ 𝑦

𝑘 𝐱𝑖 , 𝑦𝑖 , 𝐱𝑗 , 𝑦𝑗 = Φ 𝐱𝑖 , 𝑦𝑖TΦ 𝐱𝑗 , 𝑦𝑗

= 𝜙 𝐱𝑖T𝜙 𝐱𝑗 Λ 𝑦𝑖

TΛ 𝑦𝑗

= 𝑘 𝐱𝑖 , 𝐱𝑗 Λ 𝑦𝑖TΛ 𝑦𝑗

𝐾𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒𝑛𝑧 𝑧𝑤𝑖𝑠𝑐ℎ𝑒𝑛 𝐾𝑙𝑎𝑠𝑠𝑒𝑛

Korrespondenz der Klassen Λ 𝑦𝑖TΛ 𝑦𝑗 :

z.B. Skalarprodukt der Klassenbeschreibungen.

Λ 𝑦𝑖 : TF-Vektor über alle Wörter.

Maschin

elle

s L

ern

en

14

Multi-Klassen SVM

Klassifikation mit mehr als zwei Klassen:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦 .

𝑓 hat jetzt zwei Parameter.

Gemeinsame Merkmale von Ein- und Ausgabe:

𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T𝛉.

Gleicher Ansatz für Multiklassen, Sequenz- und

Struktur-Lernen, Ranking.

Maschin

elle

s L

ern

en

𝐱 kodiert z.B. ein Dokument

𝑦 = 2 kodiert Klasse

Φ 𝐱, 𝑦 =

I 𝑦 = 1 𝐱

I 𝑦 = 2 𝐱

I 𝑦 = 3 𝐱

I 𝑦 = 4 𝐱

I 𝑦 = 5 𝐱

I 𝑦 = 6 𝐱⋮

=

𝟎𝐱𝟎𝟎𝟎𝟎⋮

Multi-Klassen SVM Beispiel

15

1

2

3

4

5

6

Maschin

elle

s L

ern

en

𝐱 kodiert z.B. ein Dokument

𝑦 = 2 kodiert Klasse

Φ 𝐱, 𝑦 =

I 𝑦 = 1 𝐱

I 𝑦 = 2 𝐱

I 𝑦 = 3 𝐱

I 𝑦 = 4 𝐱

I 𝑦 = 5 𝐱

I 𝑦 = 6 𝐱⋮

=

𝟎𝐱𝟎𝟎𝟎𝟎⋮

Multi-Klassen SVM Beispiel

16

1

2

3

4

5

6

Maschin

elle

s L

ern

en

17

Multi-Klassen SVM

Klassifikation mit mehr als zwei Klassen:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦 , 𝑓𝛉 𝐱, 𝑦 = 𝜙 𝐱 T𝛉𝑦

Parametervektor für jede der möglichen 𝑘 Klassen

𝛉 = 𝛉1, … , 𝛉𝑘T

Optimierungsproblem:

min𝛉,𝛏

𝜆 𝜉𝑖𝑛𝑖=1 +

1

2 𝛉𝑗

𝑇𝛉𝑗𝑘

𝑗=1

unter den Nebenbedingungen

𝜉𝑖 ≥ 0 und ∀𝑦 ≠ 𝑦𝑖 𝑓𝛉 𝐱𝑖 , 𝑦𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝑦 + 1 − 𝜉𝑖

Maschin

elle

s L

ern

en

18

Multi-Klassen SVM

Klassifikation mit mehr als zwei Klassen:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦 , 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T𝛉

Parametervektor für jede der möglichen 𝑘 Klassen

𝛉 = 𝛉1, … , 𝛉𝑘T

Optimierungsproblem:

min𝛉,𝛏

𝜆 𝜉𝑖𝑛𝑖=1 +

1

2𝛉T𝛉

unter den Nebenbedingungen

𝜉𝑖 ≥ 0 und ∀𝑦 ≠ 𝑦𝑖 𝑓𝛉 𝐱𝑖 , 𝑦𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝑦 + 1 − 𝜉𝑖

Maschin

elle

s L

ern

en

STRUKTURIERTE AUSGABE

19

Maschin

elle

s L

ern

en

20

Taxonomien

Angenommen die Ähnlichkeiten der 𝑘 Klassen sind

durch eine Baumstruktur (Tiefe 𝑑) gegeben:

Jede Klasse entspricht einem Pfad im Baum;

𝐲 = 𝑦1, … , 𝑦𝑑 .

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11 Homininae

Hominini Gorillini

Pan Homo Gorilla

Maschin

elle

s L

ern

en

21

Taxonomien

Angenommen die Ähnlichkeiten der 𝑘 Klassen sind

durch eine Baumstruktur (Tiefe 𝑑) gegeben:

Jede Klasse entspricht einem Pfad im Baum;

𝐲 = 𝑦1, … , 𝑦𝑑 .

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11 Homininae

Hominini Gorillini

Pan Homo Gorilla

𝐶ℎ𝑖𝑚𝑝𝑎𝑛𝑧𝑒𝑒 = 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑎𝑒, 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑖, 𝑃𝑎𝑛

Maschin

elle

s L

ern

en

22

Taxonomien

Angenommen die Ähnlichkeiten der 𝑘 Klassen sind

durch eine Baumstruktur (Tiefe 𝑑) gegeben:

Jede Klasse entspricht einem Pfad im Baum;

𝐲 = 𝑦1, … , 𝑦𝑑 .

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11 Homininae

Hominini Gorillini

Pan Homo Gorilla

𝐻𝑢𝑚𝑎𝑛 = 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑎𝑒, 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑖, 𝐻𝑜𝑚𝑜

Maschin

elle

s L

ern

en

23

Taxonomien

Angenommen die Ähnlichkeiten der 𝑘 Klassen sind

durch eine Baumstruktur (Tiefe 𝑑) gegeben:

Jede Klasse entspricht einem Pfad im Baum;

𝐲 = 𝑦1, … , 𝑦𝑑 .

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11 Homininae

Hominini Gorillini

Pan Homo Gorilla

W. Gorilla= 𝐻𝑜𝑚𝑖𝑛𝑖𝑛𝑎𝑒, 𝐺𝑜𝑟𝑖𝑙𝑙𝑖𝑛𝑖, 𝐺𝑜𝑟𝑖𝑙𝑙𝑎

Maschin

elle

s L

ern

en

24

Klassifikation mit Taxonomien

Klassen in Baumstruktur (Tiefe 𝑑)

Die Klasse für ein 𝐱 ist ein Pfad im

Klassenbaum 𝐲 = 𝑦1, … , 𝑦𝑑 .

Kodierung der gemeinsamen Merkmale von Ein-

und Ausgabe?

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11

Maschin

elle

s L

ern

en

25

Klassifikation mit Taxonomien

Klassen in Baumstruktur (Tiefe 𝑑):

𝐲 𝐱 = argmax𝐲

𝑓𝛉 𝐱, 𝐲

𝑓𝛉 𝐱, 𝐲 = Φ 𝐱, 𝐲 T𝛉

𝐲 = 𝑦1, … , 𝑦𝑑

Λ 𝐲 =Λ 𝑦1

⋮Λ 𝑦𝑑

Λ 𝑦𝑖 =

𝐼 𝑦𝑖 = 𝑣1𝑖

⋮𝐼 𝑦𝑖 = 𝑣𝑛𝑖

𝑖

Φ 𝐱, 𝐲 = 𝜙 𝐱 ⨂Λ 𝑦 = 𝜙 𝐱 ⨂Λ 𝑦1

⋮Λ 𝑦𝑑

= 𝜙 𝐱 ⨂

I 𝑦1 = 𝑣11

⋮I 𝑦1 = 𝑣𝑛1

1

⋮I 𝑦𝑑 = 𝑣1

𝑑

⋮I 𝑦𝑑 = 𝑣𝑛𝑑

𝑑

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11

Maschin

elle

s L

ern

en

𝐱 kodiert z.B. ein Dokument

𝐲 = 𝑣11, 𝑣2

2, 𝑣33 T ist ein Pfad z.B. in einem Themenbaum

Φ 𝐱, 𝐲 =

I 𝑦1 = 𝑣11 𝐱

I 𝑦2 = 𝑣12 𝐱

I 𝑦2 = 𝑣22 𝐱

I 𝑦3 = 𝑣13 𝐱

I 𝑦3 = 𝑣23 𝐱

I 𝑦3 = 𝑣33 𝐱

⋮

=

𝐱𝟎𝐱𝟎𝟎𝐱⋮

Klassifikation mit Taxonomien Beispiel

26

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11

Maschin

elle

s L

ern

en

𝐱 kodiert z.B. ein Dokument

𝐲 = 𝑣11, 𝑣2

2, 𝑣33 T ist ein Pfad z.B. in einem Themenbaum

Φ 𝐱, 𝐲 =

I 𝑦1 = 𝑣11 𝐱

I 𝑦2 = 𝑣12 𝐱

I 𝑦2 = 𝑣22 𝐱

I 𝑦3 = 𝑣13 𝐱

I 𝑦3 = 𝑣23 𝐱

I 𝑦3 = 𝑣33 𝐱

⋮

=

𝐱𝟎𝐱𝟎𝟎𝐱⋮

Klassifikation mit Taxonomien Beispiel

27

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11

Maschin

elle

s L

ern

en

28

Klassifikation mit Taxonomien Kernelisierung

Klassen in Baumstruktur (Tiefe 𝑑):

𝐲 𝐱 = argmax𝐲

𝑓𝛉 𝐱, 𝐲

𝑓𝛉 𝐱, 𝐲 = Φ 𝐱, 𝐲 T𝛉

𝐲 = 𝑦1, … , 𝑦𝑑

𝑘 𝐱𝑖 , 𝐲𝑖 , 𝐱𝑗 , 𝐲𝑗 = Φ 𝐱𝑖 , 𝐲𝑖𝑇Φ 𝐱𝑗 , 𝐲𝑗

= 𝜙 𝐱𝑖T𝜙 𝐱𝑗 Λ 𝐲𝑖

𝑇Λ 𝐲𝑗

= 𝑘 𝐱𝑖 , 𝐱𝑗 Λ 𝑦𝑖𝑙 T

Λ 𝑦𝑗𝑙𝑑

𝑙=1

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11

Maschin

elle

s L

ern

en

29

Klassifikation mit Taxonomien: Dekoding / Vorhersage

Klassen in Baumstruktur (Tiefe 𝑑) :

𝑓𝛉 𝐱, 𝐲 = Φ 𝐱, 𝐲 T𝛉

𝐲 𝐱 = argmax𝐲

𝑓𝛉 𝐱, 𝑦

= argmax𝐲

𝛼𝑖𝑘 𝐱𝑖 , 𝐲𝑖 , 𝐱, 𝐲𝑛𝑖=1

= argmax𝐲

𝛼𝑖𝑘 𝐱𝑖 , 𝐱 Λ 𝐲𝑖𝑇Λ 𝐲𝑛

𝑖=1

= argmax𝐲

𝛼𝑖𝑘 𝐱𝑖 , 𝐱 Λ 𝑦𝑖𝑙 𝑇

Λ 𝑦𝑙𝑑𝑙=1

𝑛𝑖=1

𝑣33 𝑣2

3 𝑣13

𝑣12 𝑣2

2

𝑣11

Maschin

elle

s L

ern

en

Klassifikation mit strukturierten Labeln

Die Struktur der Ausgabeklasse 𝑌 wird in der

Definition von Λ 𝐲 kodiert.

Das gemeinsame Featuremap Φ 𝐱, 𝐲 = 𝜙 𝐱 ⨂Λ 𝐲

erfasst die Struktur des Eingabe- und des

Klassenraums und ermöglicht das Lernen auf

diesen Strukturen.

Dies definiert einen Multi-Klassen-Kernel auf dem

Ein- und Ausgaberaum:

𝑘 𝐱𝑖 , 𝐲𝑖 , 𝐱𝑗 , 𝐲𝑗 = 𝑘 𝐱𝑖 , 𝐱𝑗 Λ 𝐲𝑖TΛ 𝐲𝑗

30

Maschin

elle

s L

ern

en

KOMPLEXE STRUKTUREN

31

Maschin

elle

s L

ern

en

Komplexe strukturierte Ausgaben

Ausgaberaum Y beinhaltet komplexe Objekte

Darstellung als Kombination von binären

Vorhersageproblemen?

Beispiele:

Wortart- und Eigennamenerkennung

Natural Language Parsing

Sequence Alignment

…

32

Maschin

elle

s L

ern

en

33

Komplexe Ausgabe Tagging

Sequentielle Ein-/Ausgaben

Wortarterkennung

𝐱 = “Curiosity kills the cat“ → 𝐲 = Noun, Verb, Determiner, Noun

Eigennamenerkennung, Informationsextraktion: 𝐱 = “Barbie meets Ken“ → 𝐲 = 𝑃𝑒𝑟𝑠𝑜𝑛,−, 𝑃𝑒𝑟𝑠𝑜𝑛

Maschin

elle

s L

ern

en

34

Komplexe Ausgabe Parsing

Natural Language Parsing

𝐱 =“Curiosity killed the cat.” →

S

NP VP

N

NP

V Det N

Curiosity killed the cat

Maschin

elle

s L

ern

en

35

Komplexe Ausgabe Alignments

Sequence Alignment

Gegeben seien zwei Sequenzen

Vorhersage ist ein Alignment

s=(ABJLHBNJYAUGAI)

t=(BHJKBNYGU)

AB-JLHBNJYAUGAI

BHJK-BN-YGU 𝐱 = →

Maschin

elle

s L

ern

en

Komplexe strukturierte Ausgaben

Ausgaberaum Y beinhaltet komplexe Objekte

Mehrstufenverfahren propagieren Fehler

Warum ist das kein einfaches Multiklassen-

Problem?

36

The dog chased the cat

…

Det V N V N

NP

VP VP S

𝐲1

Det Det N V N

NP

VP NP S 𝐲2

Det Det N V N

NP

VP S 𝐲𝑘

NP

Maschin

elle

s L

ern

en

37

Beispiel: POS-Tagging (Wortarterkennung)

Satz 𝐱 =“Curiosity killed the cat”

Gewünscht:

argmax𝑦

Φ 𝐱, 𝐲 T𝛉 ≡ N, V, Det, N

Explizit:

Φ 𝐱, N, V, Det, N T𝛉 ≥ Φ 𝐱, N, N, N, N T𝛉

Φ 𝐱, N, V, Det, N T𝛉 ≥ Φ 𝐱, N, N, N, V T𝛉

Φ 𝐱, N, V, Det, N T𝛉 ≥ Φ 𝐱, N, N, V, N T𝛉

Φ 𝐱, N, V, Det, N T𝛉 ≥ Φ 𝐱, N, N, V, V T𝛉

Φ 𝐱, N, V, Det, N T𝛉 ≥ Φ 𝐱, N, V, N, N T𝛉

⋮ ⋮

ZU VIELE!!!

Lernen mit strukturierten Ausgaben

Maschin

elle

s L

ern

en

Ausgaberaum Y beinhaltet komplexe Objekte.

Mehrstufenverfahren propagieren Fehler

Exponentielle Anzahl von Klassen führt potentiell zu

exponentiell vielen zu schätzenden Parametern;

uneffizienter Vorhersage;

uneffizientem Lernalgorithmus.

Komplexe strukturierte Ausgaben

38

Maschin

elle

s L

ern

en

39

Komplexe strukturierte Ausgaben

Exponentielle Anzahl von Klassen führt potentiell zu

exponentiell vielen zu schätzenden Parametern;

uneffizienter Vorhersage;

uneffizientem Lernalgorithmus.

Klassifikation bei mehr als zwei Klassen:

𝐲 𝐱 = argmax𝐲

𝑓𝛉 𝐱, 𝐲 = argmax𝐲

Φ 𝐱, 𝐲 T𝛉

Um Anzahl der Parameter zu reduzieren, benötigt

man effiziente Repräsentation der Ein- und

Ausgabe Φ 𝐱, 𝐲 .

Repräsentation hängt von konkreter

Problemstellung ab.

Maschin

elle

s L

ern

en

Label-label: Φ𝑖 = 𝜙𝑖 𝑦𝑡 , 𝑦𝑡+1𝑡

Label-observation: Φ𝑗 = 𝜙 𝑗 𝑥𝑡 , 𝑦𝑡𝑡

gemeinsames Featurmapping:

Φ 𝐱, 𝐲 = … ,𝜙𝑁,𝑉 𝑦𝑡 , 𝑦𝑡+1 , … , 𝜙 𝑐𝑎𝑡,𝑁 𝑥𝑡 , 𝑦𝑡 , …T

𝑡

Gewichtsvektor 𝐰 = … ,𝑤𝑁,𝑉 , … , 𝑤𝑐𝑎𝑡,𝑁, …T

Attribut für jedes Paar benachbarter

Labels 𝑦𝑡 und 𝑦𝑡+1.

𝜙𝑁,𝑉 𝑦𝑡 , 𝑦𝑡+1 = 𝐈 𝑦𝑡 = Noun ∧ 𝑦𝑡+1 = Verb

Attribut für jedes Paar aus Eingabe und

Ausgabe.

𝜙 𝑐𝑎𝑡,𝑁 𝑥𝑡 , 𝑦𝑡 = 𝐈 𝑥𝑡 = cat ∧ 𝑦𝑡 = Noun

40

Beispiel: Sequentielle Ein-/Ausgaben (Feature-Mapping)

𝑦1 𝑦3

𝑥1 𝑥2

𝑦2

𝑥3

𝑦4

𝑥4

Curiosity killed the cat

Maschin

elle

s L

ern

en

41

Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage)

Um eine Sequenz zu klassifizieren, muss 𝐲 𝐱 = argmax

𝐲𝑓𝛉 𝐱, 𝐲

berechnet werden.

Das argmax geht über alle möglichen Sequenzen (exponentiell viele in der Länge).

𝑓𝛉 𝐱, 𝐲 = Φ 𝐱, 𝐲 T𝛉 summiert über Merkmale benachbarter Label-Paare und Merkmale von 𝐱𝑖 , 𝐲𝑖 -Paaren.

Die Summanden unterscheiden sich nur dort, wo sich auch die 𝐲-Sequenzen unterscheiden.

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

Maschin

elle

s L

ern

en

42

Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage)

Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax

𝐲𝑓𝛉 𝐱, 𝐲

Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi).

Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen

𝑦𝑡−1 =

𝑁 𝛾𝑁𝑡−1

𝑉 𝛾𝑉𝑡−1

𝐷 𝛾𝐷𝑡−1

𝑦𝑡 =

𝑁 𝛾𝑁𝑡

𝑉 𝛾𝑉𝑡

𝐷 𝛾𝐷𝑡

𝑥𝑡 = 𝑐𝑎𝑡

𝛾𝑁𝑡 = max

𝑧𝑤𝑧,𝑁 + 𝛾𝑧

𝑡−1 +𝑤𝑐𝑎𝑡,𝑁

𝑝𝑁𝑡 = argmax

𝑧…

Maschin

elle

s L

ern

en

43

Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage)

Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax

𝐲𝑓𝛉 𝐱, 𝐲

Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi).

Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen

𝑦𝑡−1 =

𝑁 𝛾𝑁𝑡−1

𝑉 𝛾𝑉𝑡−1

𝐷 𝛾𝐷𝑡−1

𝑦𝑡 =

𝑁 𝛾𝑁𝑡

𝑉 𝛾𝑉𝑡

𝐷 𝛾𝐷𝑡

𝑥𝑡 = 𝑐𝑎𝑡

𝛾𝑁𝑡 = max

𝑧𝑤𝑧,𝑁 + 𝛾𝑧

𝑡−1 +𝑤𝑐𝑎𝑡,𝑁

𝑝𝑁𝑡 = argmax

𝑧…

Maschin

elle

s L

ern

en

44

Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage)

Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax

𝐲𝑓𝛉 𝐱, 𝐲

Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi).

Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen

𝑦𝑡−1 =

𝑁 𝛾𝑁𝑡−1

𝑉 𝛾𝑉𝑡−1

𝐷 𝛾𝐷𝑡−1

𝑦𝑡 =

𝑁 𝛾𝑁𝑡

𝑉 𝛾𝑉𝑡

𝐷 𝛾𝐷𝑡

𝑥𝑡 = 𝑐𝑎𝑡

𝛾𝑉𝑡 = max

𝑧𝑤𝑧,𝑉 + 𝛾𝑧

𝑡−1 +𝑤𝑐𝑎𝑡,𝑉

𝑝𝑉𝑡 = argmax

𝑧…

Maschin

elle

s L

ern

en

45

Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage)

Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax

𝐲𝑓𝛉 𝐱, 𝐲

Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi).

Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen

𝑦𝑡−1 =

𝑁 𝛾𝑁𝑡−1

𝑉 𝛾𝑉𝑡−1

𝐷 𝛾𝐷𝑡−1

𝑦𝑡 =

𝑁 𝛾𝑁𝑡

𝑉 𝛾𝑉𝑡

𝐷 𝛾𝐷𝑡

𝑥𝑡 = 𝑐𝑎𝑡

𝛾𝐷𝑡 = max

𝑧𝑤𝑧,𝐷 + 𝛾𝑧

𝑡−1 +𝑤𝑐𝑎𝑡,𝐷

𝑝𝐷𝑡 = argmax

𝑧…

Maschin

elle

s L

ern

en

46

Beispiel: Sequentielle Ein-/Ausgaben (Dekodierung / Vorhersage)

Um eine Sequenz zu klassifizieren, berechnen wir 𝐲 𝐱 = argmax

𝐲𝑓𝛉 𝐱, 𝐲

Mit Hilfe der dynamischen Programmierung berechnen wir dieses argmax in linearer Zeit (Viterbi).

Idee: wir können die Maximalfolgen zum Zeitpunkt 𝑡 mittels der Maximalfolgen bis 𝑡 − 1 berechnen

Sobald 𝛾∗𝑡 für die gesamte Sequenz berechnet wurde,

maximieren wir 𝛾∗𝑇 und folgen den Zeigern 𝑝∗

𝑡 rückwärts, um die maximale Sequenz zu finden.

𝑦1 𝑦3

𝑥1 𝑥2

𝑦2

𝑥3

𝑦4

𝑥4

Curiosity killed the cat

N

D V

N

Maschin

elle

s L

ern

en

Strukturierte Ausgaberäume Sequentielle Ein-/Ausgaben

Dekoderierung: Viterbi-Algorithmus

Feature-Mapping:

Einträge für benachbarte Zustände

𝜙𝑁,𝑉 𝑦𝑡, 𝑦𝑡+1 = 𝐈 𝑦𝑡 = Noun ∧ 𝑦𝑡+1 = Verb

Einträge für Beobachtungen in einem Zustand

𝜙 𝑐𝑎𝑡,𝑁 𝑥𝑡 , 𝑦𝑡 = 𝐈 𝑥𝑡 = cat ∧ 𝑦𝑡 = Noun

47

Maschin

elle

s L

ern

en

48

gemeinsames Featuremapping:

Φ 𝐱, 𝐲 = … , 𝜙𝑁𝑃→𝑁 𝐲 ,… , 𝜙𝑁→𝑐𝑎𝑡(x, y), …T

Gewichtsvektor: 𝐰 = … ,𝑤𝑁𝑃→𝑁, … , 𝑤𝑁→𝑐𝑎𝑡 , …T

Dekodierung mit dynamischer Programmierung

CKY-Parser, 𝑂 𝑛3 .

Strukturierte Ausgaberäume Natural Language Parsing

S

NP VP

N

NP

V Det N

Curiosity killed the cat Φ 𝐱, 𝐲 =

1101⋮01

𝑆 → 𝑁𝑃, 𝑉𝑃𝑁𝑃 → 𝑁𝑉𝑃 → 𝑉𝑉𝑃 → 𝑉,𝑁𝑃

𝑁 → 𝑎𝑡𝑒𝑁 → 𝑐𝑎𝑡

𝐲 =

𝐱 =

𝜙𝑁𝑃→𝑁 𝐲 = 𝐈 𝑦𝑝 = 𝑁𝑃 → 𝑁𝑝∈𝐲

𝜙𝑁→𝑐𝑎𝑡 𝐱, 𝐲 = 𝐈 𝑦𝑝 = 𝑁 → 𝑐𝑎𝑡𝑝∈𝐲

Maschin

elle

s L

ern

en

49

Strukturierte Ausgaberäume Kollektive Klassifikation

Attribut für jedes Paar

benachbarter Labels 𝐲𝑡 und 𝐲𝑡+1.

𝜙123 𝑦𝑖 , 𝑦𝑗

Attribut für jedes Paar aus Eingabe

und Ausgabe.

𝜙 𝑐𝑎𝑡,𝑁 𝑥𝑡 , 𝑦𝑡 = I 𝑦𝑡 = 𝐼𝑛𝑠𝑡𝑖𝑡𝑢𝑡𝑒 ∧ 𝑥𝑡 =

Dekoder: Message Passing Algorithmus.

y1

y3

y4

y2

x1

x3 x2

x4

Maschin

elle

s L

ern

en

50

Komplexe strukturierte Ausgaben

Exponentielle Anzahl von Klassen führt potentiell zu

exponentiell vielen zu schätzenden Parametern;

uneffizienter Vorhersage;

uneffizientem Lernalgorithmus.

Optimierungsproblem:

min𝛉,𝛏

𝜆 𝜉𝑖𝑛𝑖=1 +

1

2𝛉 2

2

unter den Nebenbedingungen

𝜉𝑖 ≥ 0 and ∀𝐲 ≠ 𝐲𝑖 𝑓𝛉 𝐱𝑖 , 𝐲𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝐲 + 1 − 𝜉𝑖

Exponentielle Anzahl

Effiziente Kodierung

Maschin

elle

s L

ern

en

51

Lernen mit strukturierten Ausgaben

Optimierungsproblem:

min𝛉,𝛏

𝜆 𝜉𝑖𝑛𝑖=1 +

1

2𝛉 2

2

unter den Nebenbedingungen

𝜉𝑖 ≥ 0 and ∀𝐲 ≠ 𝐲𝑖 𝑓𝛉 𝐱𝑖 , 𝐲𝑖 ≥ 𝑓𝛉 𝐱𝑖 , 𝐲 + 1 − 𝜉𝑖

Optimierung durch iteratives Training.

Negative Constraints werden

hinzugefügt, wenn beim

Training Fehler auftritt.

[Tsochantaridis et al., 2004]

Exponentielle Anzahl

Maschin

elle

s L

ern

en

52

Lernen mit strukturierten Ausgaben Schnittebenenalgorithmus

Gegeben: 𝐿 = 𝐱1, 𝐲1 , … , 𝐱𝑛, 𝐲𝑛

Wiederhole bis alle Sequenzen korrekt

vorhergesagt werden.

Iteriere über alle Beispiele 𝐱𝑖 , 𝐲𝑖 .

Bestimme 𝐲 = argmax𝐲≠𝐲𝑖

Φ 𝐱𝑖 , 𝐲T𝛉

Wenn Φ 𝐱𝑖 , 𝐲𝑖T𝛉 < Φ 𝐱𝑖 , 𝐲

T𝛉 + 1 (Margin-Verletzung)

dann füge Constraint Φ 𝐱𝑖 , 𝐲𝑖T𝛉 < Φ 𝐱𝑖 , 𝐲

T𝛉 + 1 − 𝜉𝑖 dem Working Set hinzu.

Löse Optimierungsproblem für Eingabe 𝐱𝑖, Ausgabe 𝐲𝑖, und negative Pseudo-Beispiele 𝐲 (working set).

Liefere 𝛉 zurück.

Maschin

elle

s L

ern

en

Strukturierte Ausgaberäume

Allgemeines Framework

Anpassen von

Verlustfunktion

Gemeinsamer Repräsentation der Ein- und Ausgabe

Dekoder

𝐲 = argmax𝐲≠𝐲𝑖

Φ 𝐱𝑖 , 𝐲T𝛉

ggf. mit Verlustfunktion

Implementation: http://www.cs.cornell.edu/People/tj/svm_light/svm_struct.html

53

Maschin

elle

s L

ern

en

Ausgaberaum Y beinhaltet komplexe Objekte.

Mehrstufenverfahren propagieren Fehler

Exponentielle Anzahl von Klassen, aber

weniger zu schätzende Parameter;

effiziente Vorhersage;

effizienter Lernalgorithmus.

Strukturierte Ein-/Ausgaben

54

Feature-Mapping: reduziert

die Anzahl der Parameter

für jede Klasse

Problemspezifische

Kodierung Schnittebenenalgorithmus

Maschin

elle

s L

ern

en

RANKING

55

Maschin

elle

s L

ern

en

Ranking

Können wir das Lernen auch auf andere Arten von

strukturierten Ausgaben erweitern?

Ranking – jede Ausgabe ist eine Sortierung

Wir wollen diese Reihenfolge benutzen, um den

Lernalgorithmus zu verbessern.

56

Maschin

elle

s L

ern

en

57

Ranking

Instanzen sollen in die richtige Reihenfolge

gebracht werden.

z.B. Relevanz-Ranking von Suchergebnissen.

z.B. Relevanz-Ranking von Produktempfehlungen.

Beispiele sind Paare:

𝐿 = 𝑓 𝐱𝑖 ≥ 𝑓 𝐱𝑗 , …

≡ 𝐱𝑖 soll im Ranking vor 𝐱𝑗 stehen

Maschin

elle

s L

ern

en

58

Ranking

Relevanz-Ranking von Suchergebnissen.

Webseiten 𝐱𝑖, Suchanfrage 𝐪.

Gemeinsame Merkmalsrepräsentation Φ 𝐱𝑖 , 𝐪 von

Webseite und Suchanfrage.

Φ 𝐱𝑖 , 𝐪 kann Vektor verschiedener Merkmale der

Übereinstimmung von 𝐱𝑖 und 𝐪 sein.

z.B. Anzahl übereinstimmende, Wörter;

Übereinstimmungen in H1-Umgebung, PageRank, …

Beispiele sind Paare:

𝐿 = 𝑓 𝐱𝑖 , 𝐪 ≥ 𝑓 𝐱𝑗 , 𝐪 , …

≡ 𝐱𝑖 soll für Anfrage 𝐪 im Ranking vor 𝐱𝑗 stehen

Maschin

elle

s L

ern

en

59

Ranking

Relevanz-Ranking von Suchergebnissen.

Beispiele sind Paare:

𝐿 = 𝑓 𝐱𝑖 , 𝐪 ≥ 𝑓 𝐱𝑗 , 𝐪 , …

≡ 𝐱𝑖 soll für Anfrage 𝐪 im Ranking vor 𝐱𝑗 stehen

Beispiele können z.B. aus Klick-Daten gewonnen

werden.

Ein Benutzer stellt Anfrage 𝐪, bekommt

Ergebnisliste, klickt dann auf i-tes Listenelement 𝐱𝑖.

Verwirft damit Listenelemente 1..i-1 implizit.

Für diesen Benutzer und Anfrage 𝐪 hätte 𝐱𝑖 an

erster Stelle stehen sollen.

Maschin

elle

s L

ern

en

60

Ranking

Relevanz-Ranking von Suchergebnissen.

Beispiele sind Paare:

𝐿 = 𝑓 𝐱𝑖 , 𝐪 ≥ 𝑓 𝐱𝑗 , 𝐪 , …

Ein Benutzer stellt Anfrage 𝐪, bekommt

Ergebnisliste, klickt dann auf i-tes Listenelement 𝐱𝑖.

Für diesen Benutzer und Anfrage 𝐪 hätte 𝐱𝑖 an erster

Stelle stehen sollen.

Daraus ergeben sich Beispiele:

𝐿𝐪 = 𝑓 𝐱𝑖 , 𝐪 ≥ 𝑓 𝐱1, 𝐪 , … , 𝑓 𝐱𝑖 , 𝐪 ≥ 𝑓 𝐱𝑖−1, 𝐪

Maschin

elle

s L

ern

en

61

Ranking

Gegeben: Beispiele

𝐿 =

𝑓 𝐱1𝑖1 , 𝐪1 ≥ 𝑓 𝐱11, 𝐪1 , … , 𝑓 𝐱1𝑖1 , 𝐪1 ≥ 𝑓 𝐱1𝑖1−1, 𝐪1

⋮

𝑓 𝐱𝑚𝑖𝑚 , 𝐪𝑚 ≥ 𝑓 𝐱𝑚1, 𝐪𝑚 , … , 𝑓 𝐱𝑚𝑖𝑚 , 𝐪𝑚 ≥ 𝑓 𝐱𝑚𝑖𝑚−1, 𝐪𝑚

Löse

min𝐰,𝛏

12 𝐰 2 + 𝐶 𝜉𝑗𝑖

𝑖𝑗

𝑠. 𝑡. ∀𝑗 ∀ 𝑖 < 𝑖𝑗 𝑤T Φ 𝐱𝑗𝑖𝑗 , 𝐪𝑗 −Φ 𝐱𝑗𝑖 , 𝐪𝑗 ≥ 1 − 𝜉𝑗𝑖

∀𝑗 ∀𝑖 𝜉𝑗𝑖 ≥ 0

Maschin

elle

s L

ern

en

Lernen mit strukturierter Ein- und Ausgabe - Zusammenfassung

Klassifikation bei mehr als zwei Klassen:

𝑦 𝐱 = argmax𝑦

𝑓𝛉 𝐱, 𝑦 , 𝑓𝛉 𝐱, 𝑦 = Φ 𝐱, 𝑦 T𝛉

Lernen formuliert als Multi-Klassen SVM

Struktur der 𝑌 ist durch Λ 𝐲 gegeben: Φ 𝐱, 𝐲 =

𝜙 𝐱 ⨂Λ 𝐲 & 𝑘 𝐱𝑖 , 𝐲𝑖 , 𝐱𝑗 , 𝐲𝑗 = 𝑘 𝐱𝑖 , 𝐱𝑗 Λ 𝐲𝑖TΛ 𝐲𝑗

Strukturierte Ausgabe – hochdimensionale 𝑌

weniger zu schätzende Parameter – Featuremapping

effiziente Vorhersage – problemspezifische

Kodierung

effizienter Lernalgorithmus – Schnittebenenalgorithmus

Andere strukturierte Probleme:

Ranking benutzt Sortierungs-Constraints 62