Post on 06-Apr-2016
transcript
SS 2011 Maschinelles Lernen und Neural Computation
1
Maschinelles Lernen undNeural Computation
840.042, VO, 1 Std.SS 2011
Georg DorffnerInst. f. Artificial Intelligence
Zentrum für Med. Statistik, Informatik und Intelligente Systeme
Medizinische Universität Wienwww.meduniwien.ac.at/user/georg.dorffner/lv/mlnc.html
SS 2009 Maschinelles Lernen und Neural Computation
2
Überblick
• Grundlagen – ML/NC• Überwachtes Lernen: Klassifikation• Überwachtes Lernen: Regression• Lernen als Optimierung• Komplexe Lerner in der Praxis• Unüberwachtes Lernen• Ensemble Methoden• Kernel Methoden
SS 2009 Maschinelles Lernen und Neural Computation
3
Begleitende Literatur
• Duda R., Hart P.E., Stork D.G.: Pattern Classification, 2nd edition, New York: Wiley, 2001.
• Bishop C.M.: Pattern Recognition and Machine Learning, New York: Springer, 2006.
SS 2009 Maschinelles Lernen und Neural Computation
4
Kapitel1: Grundlagen
SS 2009 Maschinelles Lernen und Neural Computation
5
Maschinelles Lernen – mögliche Definitionen
• Computerprogramme, die sich mit Erfahrung verbessern (Mitchell 1997)(Artificial Intelligence)
• Auf der Basis von Beispielen nichttriviale Strukturen in Daten finden(Mustererkennung, Data Mining)
• Ein Modell der Daten schätzen, die diese beschreiben(Statistische Datenanalyse)
SS 2009 Maschinelles Lernen und Neural Computation
6
Einige Vorausetzungen
• Merkmale (Features)– Beschreiben die Fälle des Problems– Messungen, Daten
• Lerner (Version Space)– Eine Klasse von Modellen
• Lernverfahren– Ein Algorithmus, der das beste Modell findet
• Generalisierung– Struktur/Datenmodell soll neue Daten beschreiben
können
SS 2009 Maschinelles Lernen und Neural Computation
7
Features
• Qualitativ, nominal– z.B.: [Student, Arbeiter, Angestellter]
• Qualitativ, ordinal (enthält Ordnung)– z.B.: [schlecht, mittelmäßig, gut]
• Numerisch, metrisch– Intervallskala: kein natürlicher Nullpunkt, nur Differenzen
bedeutungsvoll (z.B. Temp in °C)– Verhältnisskala: natürlicher Nullpunkt, auch verhältnisse
bedeutungsvoll (z.B. Größe in m)– Diskret: nur endlich viele Werte (z.B. Anzahl)– Stetig: theoretisch unendlich viele Werte (z.B. Länge)
SS 2009 Maschinelles Lernen und Neural Computation
8
Beispiellerner: Perceptron• Features: 2 numerische Werte
(gezeichnet in Ebene)• Aufgabe: Teile in zwei Klassen
(weiß und schwarz)• Lerner (version space): Trenngerade
durch den Ursprung• Lernregel:
– Nimm Normalvektor– Addiere den Punktvektor eines
falsch klassifizierten Beispiels– Drehe Gerade, sodass neuer Vektor
der Normalverktor wird– Solange bis alles richtig klassifiziert
• Generalisierung: neue Punkte richtig klassifiziert
• Konvergenz garantiert, wenn Problem lösbar(Rosenblatt 1962)
SS 2009 Maschinelles Lernen und Neural Computation
9
Arten des Lernens
• Überwachtes Lernen (supervised learning)– Zuordnung der Daten („Label“) bekannt– Finde Zusammenhänge mit Input– Beispiele: medizinische Diagnose, Temperaturvorhersage
• Unüberwachtes Lernen (unsupervised learning)– Finde Struktur in den Daten– Beispiele: Marktsegmentierung, Visualisierung
• Reinforcement Learning– Finde Zusammenhänge anhand von globalem Feedback– Beispiele: Steuerung einer Roboterhand, Lernen von Spielen
SS 2009 Maschinelles Lernen und Neural Computation
10
Neural Computation
• Ursprünglich biologisch motiviert (daher der Name)
• Lerner als Netzwerk einfacher Einheiten beschreibbar
• Stärke: beliebige nichtlineare Modelle (z.B. nicht nur Geraden)
• Voraussetzung: numerische Features– Qualitative Features: als Binärcode (z.B. 1-aus-n)
SS 2009 Maschinelles Lernen und Neural Computation
11
Das einfache mathematische Modell
• Propagierungsregel:– Gewichtete Summe– Euklidischer
Abstand (später)• Transferfunktion f:
– Schwellwertfkt.(McCulloch & Pitts)
– Lineare Fkt.– Sigmoide Fkt.
yj f xj
w1
w2
wi
…
Gewicht
Unit (Neuron)
Aktivierung, Output
(Netto-) Input
n
iiijjj
n
iiijj
xwfyfx
xwy
1
1
SS 2009 Maschinelles Lernen und Neural Computation
12
Perceptron als neuronales Netz
• Inputs sind zufällige „Featuredetektoren“
• Binär kodiert• Perceptron lernt
Klassifikation
• Modell der Wahrnehmung / Objekterkennung
Neuron.eng.wayne.edu
SS 2009 Maschinelles Lernen und Neural Computation
13
Perceptron Learning Rule als Gewichtsadaption
• Rosenblatt (1962)• Zielvorgabe (target)
notwendig = Lehrer• Input wird dazugezählt
(abgezogen), wenn Output falsch
• Verwendung: Klassifikation (Original: Input = visuelle Vorverarbeitung)
target"" sonst0
if
if
j
jji
jjiij
t
txx
txxw
Target:
Nach dem Lernschritt:
SS 2009 Maschinelles Lernen und Neural Computation
14
Bias• Gewichtete Summe nicht vollständig
Trenngerade geht immer durch Ursprung
• Konstante notwendig• Realisierung: zusätzliche Unit,
immer auf 1 gesetzt(Bias Unit)
0021
1
yxxx
xwy
n
n
iiijj
j
n
iiijj wxwy 0
1
w0
SS 2009 Maschinelles Lernen und Neural Computation
15
Vektor- und Matrixnotation
• Lineares Perceptron ist Multiplikation des Input-Vektors mit der Gewichtsmatrix
• Kompakte Schreibweise
• Hilfsmittel aus VektoralgebraWxy
nnmmm
n
n
m
n
iiijj
x
xx
www
wwwwww
y
yy
mjxwy
2
1
21
22212
12111
2
1
1
1for
SS 2009 Maschinelles Lernen und Neural Computation
16
Einschub: Matrixmulitplikation• Multiplikation zweier Matrizen:
elementweise multiplizieren und addieren Spaltenzahl der 1.Matrix = Zeilenzahl der 2. Resultat: Zeilen der 1. X Spalten der 2. Matrix
• Vektoren als Matrizen:
inneres Produkt äußeres Produkt T ... Transpose (um Diagonale kippen)
...
...
...
...
...
...
...
...
...
.....
.....
.....
.....
s
.
.
.
.
....T21xx
....
....
....
....
....
.
.
.
.
2T1 xx
SS 2009 Maschinelles Lernen und Neural Computation
17
Sigmoide Transferfunktion
• Outputs begrenzt auf [0,1]• Quasi-linear um 0• Mögliche Interpretation:
Wahrscheinlichkeit
Immer wahrscheinlicher inout Wxx fe
yfx y
1
1
SS 2009 Maschinelles Lernen und Neural Computation
18
Mehrebenen-Perceptron (MLP)
• 2 (oder mehrere) Schichten (= Verbindungen)
Input Units
Hidden Units (typisch sigmoid)
Output Units(typisch linear)
SS 2009 Maschinelles Lernen und Neural Computation
19
Gewichtsadaption: Backpropagation• Verallgemeinerte Delta-Regel
ijij xw
outout'outjjjj xtyf
out
1
outhid'hidk
n
kjkjj wyf
Whid
Wout
yhid, xhid
yout, xout
out
• Fehler wird rückpropagiert• „Pseudofehler“ an den Hidden
Units
SS 2009 Maschinelles Lernen und Neural Computation
20
Backpropagation als Gradientenverfahren
• Definiere (quadratischen) Fehler (für Muster l):
• Minimiere Fehler• Ändere Gewichte in Richtung des Gradienten
• Kettenregel ergibt Backpropagation
m
kkkl txE
1
2out
ij
lij w
Ew
(partielle Ableitung nach dem Gewicht)
SS 2009 Maschinelles Lernen und Neural Computation
21
Einschub: Kettenregel• Differenzieren von verschachtelten Funktionen:
Äußere Ableitung x innere Ableitung
2
1
outout0
1 1
hid0
inhidout
m
kkj
n
j
m
iiiijjkl twwxwfwfE
xhxhgxhgfxhgfx
'''
nur 1 Summand abh. outout2 kk tx
out'kyf
nur 1 Summand: hidjx
M Wege um Gewicht zu erreichen
outjkw
usf.: inhid'ij xyf
SS 2009 Maschinelles Lernen und Neural Computation
22
Geometrische Interpretation
• Fehler bildet (hochdimensionale) Fläche
• Gradient entspricht der Richtung des steilsten Abstiegs
• Folge dieser Richtung bis zum Minimum
SS 2009 Maschinelles Lernen und Neural Computation
23
Grenzen der Backpropagation
• Gradientenverfahren kann in lokalem Minimum hängenbleiben(abhängig von der Initialisierung)
Es ist nicht garantiert, daß Backpropagation eine existierende Lösung auch findet
• Weitere Probleme: langsam, kann zu oszillieren beginnen (siehe später)
SS 2009 Maschinelles Lernen und Neural Computation
24
Praxis der Backpropagation• Beginne mit zufälligen Gewichten• Wähle kleine Lernrate (da sonst kein Gradientenverfahren)• Nehme Satz von Trainingsmustern, die gelernt werden sollen• Wähle jeweils zufällig ein Musterpaar: 1 Vorwärtsschritt, 1
Backpropagation-Schritt („online learning“)• Eigentlich: definiere Fehler als
(über alle M Musterpaare)• berechne Gewichtsänderungen für alle Musterpaare des
Trainingssatzes, summiere und ändere erst dann („batch learning“)
M
l
m
kkk
M
ll txEE
1 1
2out
1
SS 2009 Maschinelles Lernen und Neural Computation
25
Beispiel: Medizinische Diagnose• Bsp: Pima Indian Diabetes ftp://ftp.ics.uci.edu/pub/machine-learning-
databases/pima-indians-diabetes
Input:1. Number of times pregnant2. Plasma glucose concentration at 2 hours in an oral glucose tolerance test3. Diastolic blood pressure (mm Hg)4. Triceps skin fold thickness (mm)5. 2-Hour serum insulin (mu U/ml)6. Body mass index (weight in kg/(height in m)^2)7. Diabetes pedigree function8. Age (years)
Normalisiert auf Mittelwert 0 und Varianz 1
Output:Diabetes ja/nein
768 Fälle, aufgeteilt auf Training- und Testsatz
• Performanz nach Training auf Testsatz: ca. 70-80%
• Fehler geht nicht auf 0!(siehe später)
Vienet2>uebung3.exe
SS 2009 Maschinelles Lernen und Neural Computation
26
Einige wichtige Prinzipien
• Occam‘s Razor– Wenn zwei Modelle die Daten gleich gut beschreiben, dann wähle
das einfachere→ komplexer (mächtiger) ist nicht automatisch besser
• Fluch der Dimension– Für komplexe Lerner steigt der Bedarf an Beispielen überlinear
(exponentiell) mit der Zahl der Features→ nimm nur Features, die notwendig sind
• No free lunch– Es gibt keinen Lerner, der für alle Probleme die beste Lösung liefert→ wende komplexen Lerner nie blind ohne Wissen über die Daten an
SS 2009 Maschinelles Lernen und Neural Computation
27
Die stochastische Sicht des überwachten Lernens• Realdaten sind „stochastisch“
(von Natur aus mit Rauschen/Streuungen versehen)• 2 Typen von Problemen: Regression, Klassifikation
• Lernen muss mathematisches Modell finden