SS 2011Maschinelles Lernen und Neural Computation 1 Maschinelles Lernen und Neural Computation 840.042, VO, 1 Std. SS 2011 Georg Dorffner Inst. f. Artificial

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


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


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.


4

Kapitel1: Grundlagen


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)


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


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)


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)


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


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)


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


12

Perceptron als neuronales Netz

• Inputs sind zufällige „Featuredetektoren“

• Binär kodiert• Perceptron lernt

Klassifikation

• Modell der Wahrnehmung / Objekterkennung

Neuron.eng.wayne.edu


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:


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


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


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


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


18

Mehrebenen-Perceptron (MLP)

• 2 (oder mehrere) Schichten (= Verbindungen)

Input Units

Hidden Units (typisch sigmoid)

Output Units(typisch linear)


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


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)


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


22

Geometrische Interpretation

• Fehler bildet (hochdimensionale) Fläche

• Gradient entspricht der Richtung des steilsten Abstiegs

• Folge dieser Richtung bis zum Minimum


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)


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


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


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


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

Documents

SS 2011Maschinelles Lernen und Neural Computation 1 Maschinelles Lernen und Neural Computation 840.042, VO, 1 Std. SS 2011 Georg Dorffner Inst. f. Artificial