Algorithmen des Maschinellen Lernens - uni-potsdam.de€¦ · Konvexe & konkave Funktionen f tx...

MASCHINELLES LERNEN TOBIAS SCHEFFER, NIELS LANDWEHR, MATTHIAS BUSSAS

Mathematische Grundlagen

Lineare Algebra:

Vektoren, Matrizen, …

Analysis & Optimierung:

Distanzen, konvexe Funktionen, Lagrange-Ansatz, …

Stochastik:

Wahrscheinlichkeitstheorie, Statistik, …

Überblick

2

Vektor:

Vektorsumme:

Skalarprodukt:

Lineare Algebra Vektoren

1

T

1[ ]m

m

x

x x

x

x

11 1

1

1

nn

i

i

m nm

x x

x x

x

T

1

, ,

, cos

m

i i

i

x y

y x x y x y

x y x y

1x 2x

3x

1 2 3 x x x

x

x

y

3

Matrix:

Matrixsumme:

Matrixprodukt:

Lineare Algebra Matrizen

T

11 1 11 1

1

1 1

[ ]

n m

n

m mn n mn

x x x x

x x x x

X x x

11 11 1 1

1 1

n n

m m mn mn

x y x y

x y x y

X Y

1 1 1

1 111 1 11 1

1 1

1

1 1

n n

i i i ik

i in k

n nm mn n nk

mi i mi ik

i i

x y x yx x y y

x x y yx y x y

YX XY

4

Eins-Vektor/-Matrix:

Einheitsvektor:

Diagonalmatrix:

Einheitsmatrix:

Lineare Algebra Spezielle Matrizen

1

1 1

0

( ) [ ]

0

m m

m

a

diag a a

a

a e e

1 0

( )

0 1

diag

I 1

1 1 1

,

1 1 1

1 1

T[0 0 1 0 0]i e

1i

5

Hyperebene:

Lineare Algebra Geometrie

T

0{ | ( ) 0}H f w w x x x w

w

Hw

z( )f z

w

0w

w

6

Quadratisch:

Symmetrisch:

Spur (trace):

Rang (rank):

Determinante:

Positiv definit:

Lineare Algebra Matrix-Eigenschaften

n m11 1

1

n

m mn

a a

a a

ATA A

T 0 x Ax x 0

1

( )m

ii

i

tr a

A

( ) 0 falls alle Zeilen/Spalten linear unabh. det A

( ) #linear unabhänger Zeilen/Spaltenrk A

7

Cholesky-Zerlegung (m = n):

Eigenwert-Zerlegung (m = n):

Lineare Algebra Matrix-Faktorisierung

TA GGexistiert nur falls Matrix A

symmetrisch und positiv definit

1

T T T

1 1

01 falls

[ ] [ ] 0 falls

0

m m i j

m

i j

i j

A VΣV v v v v v v

Eigenwerte Eigenvektoren

8

falls Matrix A symmetrisch

Singulärwert-Zerlegung (m > n):

Berechnung durch Eigenwert-Zerlegung:

Lineare Algebra Matrix-Faktorisierung

1 T

T T

1 1

T

0 1 falls

0 falls [ ] [ ]

0 1 falls

0 falls

i j

m nn

i j

i j

i j

i j

i j

v v

A UΩV u u v v

u u0

Singulärwerte

1

1

T T T T

00

, , 0

0

i in

n

0A A U U AA V V

0 0

9

Definition:

Beispiele für Vektor-Distanzen bzw. Normen:

Minkowski-Distanz:

Manhattan-Distanz:

Euklidische Distanz:

Beispiel für Matrix-Distanzen:

Schatten-Distanz:

Trace-Distanz:

Frobenius-Distanz:

Analysis Distanzen

( , ) 0 ( , ) ( , ) ( , ) ( , ) ( , )d x y x y d x y d y x d x y d x z d z y

1

mp

pi ip

i

x y

x y

1x y

1

mppip

i

X Y

Singulärwerte

der Matrix

2x y

1tr X Y X Y

2F X Y X Y

X Y

Norm von x:

( , )dx x 0

Norm von X:

( ,0)dX X

10

Erste Ableitung einer Funktion:

Nach einem Skalar x:

Nach einem Vektor x:

Zweite Ableitung einer Funktion:

Nach einem Skalar x:

Nach einem Vektor x:

Analysis Differentialrechnung

T

1

( )m

f ff grad f

x x

x

d

d

ff

x

Gradient Partielle Ableitung

2 2

2

1 1

2

2 2

2

1

( )

m

m m

f f

x x x

f H f

f f

x x x

x

2

2

d

d

ff

x

Hesse-Matrix

11

Integral einer Funktion:

Über einem Skalar x:

Über einem Vektor x:

Bestimmtes Integral:

Umkehroperation:

Berechnung analytisch durch Integrationsregeln

oder numerische Approximation (Quadraturformeln).

Analysis Integralrechnung

1( )d ( )d d mF f f x x x x x x

( )dxF f x x

( )d ( ) ( )

b

x x

a

f x x F b F a

d( )

d

xFf x

x

12

Konvexe Funktion:

Konkave Funktion:

Streng konvex bzw. konkav:

„“ bzw. „“ wird zu „“ bzw. „“.

Es existiert maximal ein Minimum bzw. Maximum.

Zweite Ableitung ist überall positiv bzw. negativ.

Tangente an f(x) ist untere bzw. obere Schranke von f.

Analysis Konvexe & konkave Funktionen

( (1 ) ) ( ) (1 ) ( )f tx t y tf x t f y

( (1 ) ) ( ) (1 ) ( )f tx t y tf x t f y

13

Optimierungsaufgabe (OA):

f Zielfunktion.

S zulässiger Bereich (definiert durch Nebenbedingungen).

f* Optimalwert.

x* optimale Lösung.

Ein x S wird zulässige Lösung genannt.

Konvexe Optimierungsaufgabe:

Zielfunktion und zulässiger Bereich konvex.

Lokales Optimum = globales Optimum.

Optimierung Definitionen

* *min ( ) mit arg min ( )x S x S

f f x x f x

14

Notwendige Optimalitätskriterien für x*:

Wenn f in x* differenzierbar ist, dann ist .

Wenn f in x* zweimal differenzierbar ist, dann ist

eine positiv definite Matrix.

OA ohne Nebenbedingungen:

OA mit n Nebenbedingungen:

Optimierung Eigenschaften

*( ) 0x f x

2 *( )x f x

mS

{ | ( ) 0, ( ) 0, 1... , 1... }m

i jS g g i k j k n x x x

15

Ziel: Finden von mit .

Newtonsches Näherungsverfahren (Newton-Verfahren):

Anwendung: Lösen von Optimierungsaufgabe ohne NB;

für optimale Lösung x* gilt :

Gradientenabstieg: Benutze Konstante α anstatt

bzw.

Optimierung Newton Verfahren

0( ) 0h x 0x

0 0 0 1 0

1 ( ) ( )t t t tx x h x h x

*( ) 0 ( ) : ( )x xf x h x f x

* * 2 * 1 *

1 ( ) ( )t t x t x tx x f x f x

1( )H f ( )grad f

1h

1( )H f

16

Lagrange-Ansatz für konvexe Optimierungsaufgabe

mit Nebenbedingungen:

Zulässiger Bereich:

Lagrange-Funktion:

Dualität:

Primale OA:

Duale OA:

Optimierung Lagrange-Ansatz

{ | ( ) 0, ( ) 0, 1... , 1... }m

i jS g g i k j k n x x x

1

( , ) ( ) ( )n

i i

i

L f g

x α x x

*

0 0min ( ) min max ( , ) max min ( , )

m mi iS

f f L L

x x x

x x α x α

( )pf x ( )df α

( ) falls min ( ) mit ( )

falls m p px

f Sf f

S

x xx x

x

0max ( ) mit ( ) min ( , )

mi

d dx

f f L

α α x α

Wegen Konvexität

von f, gi und gj

17

Zufallsexperiment: Definierter Prozess in dem eine

Beobachtung ω erzeugt wird (Elementarereignis).

Ereignisraum Ω: Menge aller möglichen Elementar-

ereignisse; Anzahl aller Elementarereignisse ist |Ω|.

Ereignis A: Teilmenge des Ereignisraums.

Wahrscheinlichkeit P: Funktion welche Wahr-

scheinlichkeitsmasse auf Ereignisse A aus Ω verteilt.

Stochastik Wahrscheinlichkeitstheorie

( ) :P A P A

18

Wahrscheinlichkeitsfunktion = normiertes Maß

definiert durch Kolmogorow-Axiome.

Wahrscheinlichkeit von Ereignis :

Sicheres Ereignis:

Wahrscheinlichkeit dass Ereignis oder Ereignis

eintritt mit (beide Ereignisse sind

inkompatibel):

Allgemein gilt:

Stochastik Wahrscheinlichkeitstheorie

( ) 1P

0 ( ) 1P A

A

B A B

( ) ( ) ( )P A B P A P B

A

( ) ( ) ( ) ( )P A B P A P B P A B 19

Für zwei unabhängige Zufallsexperimente gilt:

Wahrscheinlichkeit dass Ereignis (im ersten

Experiment) und Ereignis (im zweiten Experiment)

eintritt ist

Allgemein gilt:

Satz von Bayes:

Stochastik Satz von Bayes

B

( , ) ( | ) ( )P A B P A B P B

Bedingte Wahrscheinlichkeit: Wahrscheinlichkeit

von A unter der Bedingung dass B eingetreten ist.

( | ) ( )( , ) ( , ) ( | ) ( ) ( | ) ( ) ( | )

( )

P B A P AP A B P B A P A B P B P B A P A P A B

P B

A

( , ) ( ) ( )P A B P A P B

Wahrscheinlichkeit dass

Ereignis B eintritt.

20

Zufallsvariable X ist Abbildung eines elementaren

Ereignisses auf einen numerischen Wert,

bzw. auf einen m-dimensionalen Vektor, .

Verteilungsfunktion einer Zufallsvariable X:

Dichtefunktion einer Zufallsvariable X:

Für endlichen Ereignisraum (|Ω| < ∞) gilt:

Stochastik Zufallsvariablen

( ) : ( ) : ({ | ( ) })XP x P X x P X x

( ) : ( ) : ({ | ( ) })Xp x P X x P X x

:X x

( ) ( ) : ( ) ( )d

a

XX X X

x a

P xp a P a p x x

x

: mX x

21

Informationsgehalt der Realisierung x eines Zufalls-

experiments (mit Zufallsvariable X):

Information der Realisierungen x, y zweier unabhängiger

Zufallsexperimente (mit Zufallsvariablen X, Y):

Aus folgt:

wobei .

Informationsgehalt: .

Stochastik Informationstheorie

( ) : ( )Xh x h X x

( , ) ( ) ( )XYh x y h X x h Y y

( , ) ( , ) ( ) ( )XYp x y P X x Y y P X x P Y y

log ( , ) log ( ) log ( )XYp x y P X x P Y y

( ) : log ( )X Xh x p x

0 log ( , )XYp x y

22

Verteilungs- und Dichtefunktion.

Wertebereich: stetig/diskret, endlich/unendlich, ...

Erwartungswert (erwartete Realisierung):

Varianz (erwartete Abweichung vom Erwartungswert):

Entropie (erwarteter Informationsgehalt):

Stochastik Kenngrößen von Zufallsvariablen

H E[ ( )] log ( ) ( )d log ( ) ( )X X X X i X i

i

h X p x p x x p x p x

E[ ] ( )d ( )X X i X i

i

X xp x x x p x

2 22 2E ( ) ( )d ( )X X X X i X X i

i

X x p x x x p x

23

Annahmen:

Datenpunkt xi ist eine Belegung der Zufallsvariable X (Realisierung des dazugehörigen Zufallsexperiments).

Stichprobe von n Datenpunkten xi resultiert aus n-maliger Wiederholung des Zufallsexperiments.

Ziel: Bestimmung der Eigenschaften von X (bspw. Verteilungsfunktion) basierend auf Stichprobe.

Entwicklung von Schätz- und Testverfahren für solche Aussagen, z.B.:

Schätzer für Parameter von Verteilungsfunktionen.

Signifikanztests für Aussagen.

Stochastik Mathematische Statistik

24

Idee: Ersetzen der Dichtefunktion durch empirische

Dichte .

Erwartungswert-Schätzer = Empirischer

Erwartungswert (Mittelwert bzw. mittlere Realisierung):

Varianz-Schätzer = Empirische Varianz

(mittlere quadratische Abweichung vom Mittelwert):

Erwartungstreuer Schätzer:

Stochastik Schätzer

1

1ˆ ˆ( )d ( )d

n

X X X X i

i

xp x x xp x x xn

2 22 2 2

1

1ˆ ˆ ˆ( )d ( )d ( )

n

X X X X X X i X

i

x p x x x p x x xn

ˆlim X Xn

f f

( )Xp x

1ˆ ( ) :X i

i

p x x xn

25

Maschinelles Lernen ist zum großen Teil die Anwendung

von Mathematik aus zahlreichen Gebieten,

insbesondere der Statistik & Optimierung.

Inhalt der Veranstaltung ist

Verstehen, Implementieren und Anwenden von Algorithmen

des Maschinellen Lernens.

Inhalt der Veranstaltung ist NICHT

Herleiten der zugrunde liegenden Mathematik.

Zusammenfassung

26