SS 2009 Maschinelles Lernen und Neural Computation
1
Kapitel 2: Klassifikation
SS 2009 Maschinelles Lernen und Neural Computation
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?
SS 2009 Maschinelles Lernen und Neural Computation
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)
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
7
Beispiel: 2 Variablen, 2 Klassen
• 2-dim. Gaussverteilungen
• Lineare Entscheidungsgrenze
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
10
Visualisierung: Normalverteilungen
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
15
Beliebige Klassifikationen
• Jede Hidden Unit teilt Raum in 2 Hälften
• Output Units wirken wie “AND”
• Sigmoide: verlaufende Bereiche
SS 2009 Maschinelles Lernen und Neural Computation
16
Beispiel: MLP• MLP mit 5 Hidden und 2
Output Units• Lineare Transferfunktion
am Output• Quadratischer Fehler
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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!
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
25
Beispiel
• Class-conditionals:
• Posterior:
(90 gedreht)
• Entscheidungsgrenze:
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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
SS 2009 Maschinelles Lernen und Neural Computation
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!
SS 2009 Maschinelles Lernen und Neural Computation
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 ¾)
SS 2009 Maschinelles Lernen und Neural Computation
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