SS 2009Maschinelles Lernen und Neural Computation 28 Kapitel 2: Klassifikation

SS 2009 Maschinelles Lernen und Neural Computation

1

Kapitel 2: Klassifikation


2

1x

C1 C2

‘nein’ ‘ja’

Ein einfacher Fall

• Ein Feature, Histogramme für beide Klassen(z.B. Glukosewert, Diabetes ja/nein)

• Keine perfekte Trennung möglich

• Entscheidung: Schwellwert

• Frage: Wo setze ich ihn am besten hin?


3

Der allgemeine Fall: Bayes‘sches Theorem• Ann: Daten fallen in k Klassen, • wähle für eine Beobachtung xj die Wahrscheinlichste aus

j

iij

ji p

cPcpcPx

xx ||

Wahrscheinlichkeit für Beobachtung,wenn in Klasse i(„likelihood“, „class-conditional“)

Wahrscheinlichkeit für Klasse ivor der Beobachtung („a priori“)

Wahrscheinlichkeit, dass BeobachtungZur Klasse i gehört(„a posteriori“)

Wahrscheinlichkeit für das Auftretender Beobachtung

k

iii

jj cPcpp1

|xx

Nenner ist Summe aller möglichen Zähler (aller Fälle)


4

Der optimale Klassifikator

• Klassifikation: wähle die Klasse i mit der höchsten a-posteriori Wahrscheinlichkeit

• Erzielt das bestmögliche Resultat• Bayes‘sche Formel erleichtert das Problem, da

Wahrscheinlichkeiten auf der rechten Seite meist leichter zu bestimmen sind

• Da p(x) für alle Klassen gleich ist, kann es oft weggelassen werden


5

Einschub: Wahrscheinlichkeitsdichten

• Für diskrete Variablen (endliche Werte): Wahrscheinlichkeit,z.B.: P(ci)

• Für kontinuierliche Variablen nicht möglich: P(xj)=0• Stattdessen: Wahrscheinlichkeitsdichtefunktion p(x)

p(xj) ... Dichte an diesem Punkt (kann größer als 1 sein)

• Wahrscheinlichkeit, dass x in einem kleinen Intervall liegt

• Dichte kann wie Wahrscheinlichkeit behandelt werden

1

xx dp

jPdpj

j

xxxxxx

xx


6

Beispiel: 1 Variable, 2 Klassen

• Annahme: in beiden Klassen sind Beobachtungen normalverteilt

Verteilung der Werte für Klasse 1 („class-conditional“)

für Klasse 2

Entscheidungsgrenze

• Entscheidungsgrenze: Schnittpunkt der beiden Kurven

• Multiplikation mit a-priori Wahrscheinlichkeiten: Entscheidungsgrenze verschiebt sich

• Durchdividieren durch Summe ergibt Wahrscheinlichkeit für Klasse


7

Beispiel: 2 Variablen, 2 Klassen

• 2-dim. Gaussverteilungen

• Lineare Entscheidungsgrenze


8

Klassifikatoren

• Problem: Dichteverteilungen meist unbekannt• Lösung:

– Schätzen der Verteilungen

– Schätzen der Entscheidungsgrenze– Schätzen von Diskriminanzfunktionen:

Wähle für jede Klasse Fkt. gi(x)Klasse ci, wenn gi(x)>gj(x) für alle jiz.B.:

iii

iii

cPcpgcPcpg

log|log|

xxxx

KeineWahrscheinlichkeitenmehr


9

Diskriminanzfunktionen für Normalverteilungen

• Streuung in alle Richtungen gleich („sphärisch“):

• Log-Fkt. Und multiplikative Faktoren ändern nichts an Größenverhältnis:

• Quadratische Funktion• Entscheidungsgrenze: g1(x)=g2(x), auch quadratisch

wenn 1= 2: linear

ii

i

ii cPg

2

2

2exp

21

μx

x

ii

ii cPg log

2 2

2

μx

x


10

Visualisierung: Normalverteilungen


11

Allgemeiner Ansatz: Diskriminanzanalyse

• Lineare Diskriminanzfunktion:

entspricht dem Perceptron mit 1 Output Unit pro Klasse

• Quadratisch linear:

entspricht einer „Vorverarbeitung“ der Daten,Parameter (w,v) noch immer linear

n

iii wxwg

10x

n

i

p

i

p

jjiijii wxxvxwg

10

1 1

x


12

Der Schritt zum neuronalen Netz

• Allgemein linear:

beliebige Vorverarbeitungsfunktionen, lineare Verknüpfung

• Neuronales Netz:

NN implementiert adaptive Vorverarbeitungnichtlinear in Parametern (w)

01

wywgp

iiii

xx

Gauss ...

Sigmoide ... ffy

ffy

ii

ii

xwxxwx T

MLP

RBFN


13

Beispiel: XOR

• (0 0) 0(1 0) 1(0 1) 1(1 1) 0

Exklusives Oder• 4. Muster ist Summe des

2. und 3. (lineare Abhängigkeit)

• Punkte lassen sich durch keine Gerade trennen


14

0

0 00 0

0 0

Hidden Units

• Zwei Perceptrons + nichtlineare Transferfunktion:

1

1 01 -1

1 0

1

0 1-1 1

0 1

0

0 00 0

1 1

• Schwellwertfunktion bricht lineare Abhängigkeit


15

Beliebige Klassifikationen

• Jede Hidden Unit teilt Raum in 2 Hälften

• Output Units wirken wie “AND”

• Sigmoide: verlaufende Bereiche


16

Beispiel: MLP• MLP mit 5 Hidden und 2

Output Units• Lineare Transferfunktion

am Output• Quadratischer Fehler


17

MLP zur Diskriminanzanalyse

• MLP (und RBFN) ist direkte Erweiterung klassischer Modelle

• Stärke: beliebige nichtlineare Diskriminanzfunktionen

• Hidden Units: Adaptive Vorverarbeitung des Inputs

• Form der Diskriminanzfunktion außerhalb der Entscheidungsgrenze belanglos

• Perceptron ist identisch mit linearer Diskriminanzanalyse


18

Alternativer Ansatz: Schätzung der Verteilungen

• Beim Ansatz mittels Diskriminanzfunktionen geht ein wesentlicher Aspekt verloren: Wahrscheinlichkeiten der Klassenzugehörigkeit

mehr an Bayes halten, Dichtefunktion schätzen(vor allem p(x|ci))

• Parametrisch: Form ist bekannt, weniger Parameter zu schätzen

• Nichtparametrisch: Form ist unbekannt, theoretisch beliebig


19

Parametrisch: Maximum Likelihood (ML)• Ann.: Verteilung hat eine bestimmte, analytisch

beschreibbare Form (z.B. Normalverteilung) mit Parametern (z.B. Zentrum und Weite)

• Likelihood:

• Entspricht der „Wahrscheinlichkeit“, dass Daten beobachtet werden, wenn die Verteilung richtig ist

• ML: Finde jenes , das die Beobachtungen am wahrscheinlichsten macht: Maximiere L()

• Vor: Beobachtungen (Daten) sind unabhängig voneinander

n

i

ippL1

| θxθ|

Menge aller Datenpunkte


20

Beispiel: eindimensionale Normalverteilung

• Vereinfachung (ähnlich wie zuvor):logarithmieren, Vorzeichen ändern, Konstante weglassen, minimierenminimiere die negative log-Likelihood

n

i

in

i

i xxpLL1

2

2

1 2exp

21,|,

θ

n

i

ixL1

2

2

2loglog

• Minimierung: 1. Ableitung auf 0 setzen

n

i

in

i

i xn

xn 1

22

1

ˆ1ˆ 1ˆ Erwartetes Ergebnis:Mittelwert und Varianz


21

Likelihood-Funktionen für die Normalverteilung

• L() für Punkte 1, 2 und 3, =1 • L() für Punkte 1, 2 und 3, =1

(wieder Gauss-Fkt.)

• L() für einen Punkt 1, =1:

ML nicht immer sinnvoll!


22

Nichtparametrisch: Parzen-Windows

• Wenn Form beliebig, keine Likelihood angebbar• Wähle einen kleinen (Hyper-)Würfel, zähle wieviel

Punkte drin liegen (ki)Geschätzte Dichte:

i

i

i Vn

kxp

• Wenn n, Vi0, dann immer genauer

• Entspricht einem normalisiertenHistogramm

Volumen


23

Der Fluch der Dimensionalität

• (Bellman 1961):bei nichtparametrischen Fällen steigt die Anzahl der benötigten Beispiele exponentiell mit der Dimensionalität des Input!

• Parzen: – wenn Fenster klein, muss es noch genügend Beispiele

enthalten– je mehr Dimensionen, desto dünner gesät

möglichst wenige Inputs, viele Daten


24

Semiparametrisch: Gaussian Mixtures (GMM)

• Nähere beliebige Verteilung durch eine Mischung von Normalverteilungen an

• Gleiches Prinzip wie bei neuronalen Netzen

• Maximum Likelihood:

k

i i

i

i

il

xcxp1

2

2

2exp

2|

n

ji

n cxpL1

,| σμ,π,σμ,π, -logL, Gradientenverfahren


25

Beispiel

• Class-conditionals:

• Posterior:

(90 gedreht)

• Entscheidungsgrenze:


26

MLP zur Klassifikation

• Beweis existiert:MLP nähert die a-posteriori Wahrscheinlichkeit an

• Aktivierungsfunktion: Softmax(eigene Fehlerfunktion notwendig; siehe später)

• A-priori Wahrscheinlichkeiten:Verteilungen im Trainingsset

k

ii

jj

x

xy

1

exp

exp


27

Die Softmax-Funktion

• Erzwingt, dass Outputs als Wahrscheinlichkeiten interpretierbar sind

• Bezug zum Bayes’schen Theorem

• Spezialfall: Sigmoide Funktionnur 2 Klassen, 1 Output Unit: durchdividieren

1 ,10 exp

exp

1

outout

1

out

outout

k

jjjk

ij

jj xx

y

yx

k

iii

iii

cPcp

cPcpcP

1

in

inin

|

||x

xx Wenn Expontentialverteilung SoftmaxNettoinput ist log. von Dichte

out

1

1out

jyje

x


28

Warum Wahrscheinlichkeiten?

• Mehr Information• Ablehnung von unsicheren Fällen: Performanz

steigt, aber einige Fälle unentscheidbar• Einfache Berücksichtigung von anderen a-priori

Wahrscheinlichkeiten• Berücksichtigung von Kosten für Fehler• Verknüpfung mit anderen Quellen


29

NN als semiparametrische Methoden

• Semiparametrisch:Form relative beliebig, aber dennoch durch Anzahl der Hidden Units („Modellkomplexität“) beschränkt

• Fluch der Dimension abgeschwächt, aber immer noch gegeben: Bedarf steigt ungefähr quadratisch

NN haben gute Eigenschaften, wenn Dichten unbekannt, aber immer noch gilt:wenige Inputs, viele Daten!


30

Nachtrag: k-nearest neighbor• Speichere alle Trainingssätze mit zugehöriger Klasse• Neuer Fall: wähle die k nähesten Trainingsfälle, nimm Klasse, die am

häufigsten vorkommt

• Duda & Hart 1974:Nearest Neighbor (k=1) hat maximal den doppelten Fehler des bayesoptimalen Klassifizierers (für große Fallzahl)

kann als Benchmark verwendet werden• Approximiert auch die a-priori Wahrscheinlichkeit direkt• nichtparametrisch

k=4:3 Klasse 21 Klasse 1 Klasse 2(posterior ¾)


31

Zusammenfassung

• NN sind semiparametrische Methoden zur Klassifikation

• Lt. Bayes sind Wahrscheinlichkeiten angebbar, bringt mehr Information

• Es existieren gleichmächtige Alternativen (z.B. GMM)

• Nearest Neighbor als Benchmark

Documents

SS 2009Maschinelles Lernen und Neural Computation 28 Kapitel 2: Klassifikation