INTELLIGENTE DATENANALYSE IN MATLAB · Entwicklung von Schätz- und Testverfahren für solche Aussagen, z.B.: Schätzer für Parameter von Verteilungsfunktionen. Signifikanztests

Michael Brückner/Tobias Scheffer

INTELLIGENTE DATENANALYSE

IN MATLAB

Mathematische Grundlagen

A. Fischer, K. Vetters: Lineare Algebra – Eine

Einführung für Ingenieure und Naturwissenschaftler.

H. Amann, J. Escher: Analysis I-III.

S. Boyd, L. Vandenbergh: Convex Optimization.

R. Schlittgen: Einführung in die Statistik.

H. R. Schwarz: Numerische Mathematik.

18.10.2009Michael Brückner/Tobias Scheffer2

Literatur

Lineare Algebra.

Analysis & Optimierung.

Stochastik.

Numerik.

Überblick

18.10.20093 Michael Brückner/Tobias Scheffer

Vektor:

Vektorsumme:

Skalarprodukt:


Lineare AlgebraVektoren

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 yy x x y x y

x y x y

1x 2x

3x1 2 3x x x

x

x

y

Matrix:

Matrixsumme:

Matrixprodukt:


Lineare AlgebraMatrizen

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

Hyperebene:

Ellipsoid:


Lineare AlgebraGeometrie

T

0 | ( ) 0H f ww x x x ww

Hw

z ( )f z

w

0w

w

T | ( ) 1E gA x x x Ax

Quadratisch:

Symmetrisch:

Spur (trace):

Rang (rank):

Determinante:

Positiv definit:


Lineare AlgebraMatrix-Eigenschaften

n m11 1

1

n

m mn

a a

a a

ATA A

T: 0x 0 x Ax

1

( )m

ii

i

tr aA

2( ) ( )det vol EAA gilt nur falls A positiv definit

äquivalent giltT:G A GG

( ) #linear unabhänger Zielen/Spaltenrk A

Eins-Vektor/-Matrix:

Einheitsvektor:

Diagonalmatrix:

Einheitsmatrix:


Lineare AlgebraSpezielle Matrizen

1

1 1

0

( ) [ ]

0

m m

m

a

diag a a

a

a e e

1 0

( )

0 1

diagI 1

1 1 1

,

1 1 1

1 1

T[0 0 1 0 0]ie

1i

LU-Zerlegung (m = n):

Cholesky-Zerlegung (m = n):

Eigenwert-Zerlegung (m = n):


Lineare AlgebraMatrix-Faktorisierung

T

11 11 1

1

0

0

m

m mm mm

l u u

l l u

A LU

TA GG existiert nur falls

A positiv definit

1

T T T

1 1

01 falls

[ ] [ ] 0 falls

0

m m i j

m

i j

i jA VΣV v v v v v v

EigenwerteEigenvektoren

Singulärwert-Zerlegung (m > n):

Berechnung durch Eigenwert-Zerlegung:


Lineare AlgebraMatrix-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

Definition:

Beispiele für Vektor-Distanzen

Minkowski-Distanz:

Manhattan-Distanz:

Euklidische Distanz:

Beispiel für Matrix-Distanzen:

Schatten-Distanz:

Trace-Distanz:

Frobenius-Distanz:


AnalysisDistanzen

( , ) 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 yx y

1x y

1

mpp

ipi

X Y

Singulärwerte

der Matrix

2x y

1trX Y X Y

2FX Y X Y

X Y

Norm von x:( ,0)x d x

Erste Ableitung einer Funktion f :

Nach einem Skalar x:

Nach einem Vektor x:

Zweite Ableitung einer Funktion f :

Nach einem Skalar x:

Nach einem Vektor x:


AnalysisDifferentialrechnung

T

1

( )m

f ff grad f

x xx

d

dx

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

22

2

d

dx

ff

x

Hesse-Matrix

Integral einer Funktion f :

Über einem Skalar x:

Über einem Vektor x:

Bestimmtes Integral:

Umkehroperation:

Berechnung analytisch durch Integrationsregeln

oder numerische Approximation (Quadraturformeln).


AnalysisIntegralrechnung

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

( )dxF f x x

( )d ( ) ( )

b

x x

a

f x x F b F a

d( )

d

xFf x

x

Konvexe Funktion f :

Konkave Funktion f :

Streng konvex bzw. konkav:

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

Es existiert genau ein Minimum bzw. Maximum.

Zweite Ableitung ist überall positiv bzw. negativ.

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


AnalysisKonvexe & konkave Funktionen

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

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

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 OA:

Zielfunktion und zulässiger Bereich konvex.

Lokales Optimum = Globales Optimum.


OptimierungDefinitionen

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

f f x x f x

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 (semi-)definite Matrix.

OA ohne Nebenbedingungen:

OA mit n Nebenbedingungen:


OptimierungEigenschaften

*( ) 0x f x

2 *( )x f x

mS

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

i jS g g i k j k nx x x

Lagrange-Ansatz für OA mit Nebenbedingungen:

Zulässiger Bereich:

Lagrange-Funktion:

Dualität:

Primale OA:

Duale OA:


OptimierungLagrange-Ansatz

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

i jS g g i k j k nx x x

1

( , ) ( ) ( )n

i i

i

L f gx α x x

* min ( ) min max ( , ) max min ( , )m mS

f f L Lx α 0 α 0x x

x x α x α

Dualitätslücke

( )pf x ( )df α

( ) falls min ( ) mit ( )

falls m p px

f Sf f

S

x xx x

x

max ( ) mit ( ) min ( , )md d

xf f L

α 0α α x α

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.

Wahrscheinlichkeitsfunktion P: Funktion welche Wahr-

scheinlichkeitsmasse auf Ereignisse A aus Ω verteilt.


StochastikWahrscheinlichkeitstheorie

Wahrscheinlichkeitsfunktion (Kolmogorow‐Axiome):

Wahrscheinlichkeit von Ereignis :

Sicheres Ereignis:

Für die Wahrscheinlichkeit zweier unabhängiger

(inkompatibler) Ereignisse und (d.h. )

gilt:

Summenregel:

Produktregel:

Satz von Bayes:



( ) 1P

0 ( ) 1P A

A B A B

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

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

( ) ( )i

i

P A P A B

Bi ist Partitionierung

von Ω

( | ) ( )( | ) ( ) ( | ) ( ) ( | )

( )

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

P B

A

Zufallsvariable X: Abbildung eines elementaren

Ereignisses auf einen numerischen Wert, .

Elementarereignis ω ↔ Belegung der Zufallsvariable X(ω) = x.

Verteilungsfunktion einer Zufallsvariable X:

Dichtefunktion einer Zufallsvariable X (für |Ω| < ∞):

Zusammenhang von Verteilungs- und Dichtefunktion:



( ) ( ) ( | ( ) )XF x P X x P X x

( ) ( ) ( | ( ) )Xf x P X x P X x

:X x

d ( )( ) ( )d ( )

d

a

XX X X

F aF a f x x f a

x

Informationsgehalt der Realisierung x einer

Zufallsvariable X:

Idee: Information zweier unabhängiger Ereignisse

soll sich addieren, .

Für zwei unabhängige Ereignisse gilt

und somit mit .

Für bedingte Ereignisse gilt:

Analog zum Satz von Bayes gilt:


StochastikInformationstheorie

( ) ( )h x I X x

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

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

( , ) log ( , )h x y p x y ( ) ( ) log ( )h x I X x P X x

( | ) ( ) ( | ) ( ) ( | ) ( , ) ( )h x y h y h y x h x h x y h x y h y

( , ) ( | ) ( )h x y h x y h y

Verteilung/Dichte.

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

Erwartungswert (mittlere Realisierung):

Varianz (mittlere quadratische Abweichung vom

Erwartungswert):

Entropie (mittlerer Informationsgehalt):


StochastikKenngrößen von Zufallsvariablen

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

x

h X p x p x

E[ ] ( )X

x

X p x x

2 2 2E ( ) ( )( )X X X

x

X p x x

Annahme: Daten (Stichprobe) = Realisierungen bzw.

Belegungen von Zufallsvariablen.

Ziel: Aussagen über Eigenschaften der Grund-

gesamtheit (alle möglichen Belegungen) treffen.

Entwicklung von Schätz- und Testverfahren für solche

Aussagen, z.B.:

Schätzer für Parameter von Verteilungsfunktionen.

Signifikanztests für Aussagen.


StochastikMathematische Statistik

Ziel: Konstruktion und Analyse von Algorithmen für kontinuierliche mathematische Probleme, falls

Keine exakte Lösung für ein Problem existiert,

Exakte Lösung nicht effizient gefunden werden kann.

Konstruktionsprinzipien:

Exakte Verfahren: Exakte Lösung bei unendlicher Rechnergenauigkeit.

Näherungsverfahren: Approximative Lösung.

Analysen:

Laufzeit, Stabilität/Fehleranalyse und Robustheit.


NumerikÜberblick

Fehlerarten:

Eingabefehler, Messfehler, Rundung auf Maschinengenauigkeit.

Systematische Fehler (z.B. Diskretisierung), Rundungsfehler.

Beispiele:

Addition von x und y mit :

Logarithmieren/Potenzrechnen:

Fehlerfortpflanzung: Summieren n ähnlich großer Zahlen


NumerikFehler

x y

4040 ln 1 e

1

n

i

i

y x

(1, ) mit ( , ) , 1, und ( , )2 2

a

a b a by f n f a b f a f b f a a x

20 20 2010 10 10

Lösung linearer Gleichungssysteme.

Interpolation/Approximation von reellen Funktionen.

Finden von Extremwerten (Nullstellen, Minima, Maxima,

Sattelpunkte, …) nichtlinearer Gleichungen.

Numerische Differentiation/Integration.

Anfangswert-/Randwertprobleme für Differential-

gleichungen.

Eigenwertprobleme und Matrix-Faktorisierung.


NumerikAnwendungen

Ziel: Finden von mit .

Newtonsches Näherungsverfahren:

Anwendung: Lösen von Optimierungsproblemen;

für optimale Lösung x* gilt :

Quasi-Newton-Verfahren:

Approximation von bzw. .


NumerikBeispiel Nullstellenproblem

0( ) 0g x0x

0 0 0 1 0

1 ( ) ( )t t x t tx x g x g x

*( ) 0 ( ) ( )x xf x g x f x

* * 2 * 1 *

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

1( )H f ( )grad f

0 1( )x tg x 1( )H f

Maschinelles Lernen ist zum großen Teil die Anwendung von Mathematik aus zahlreichen Gebieten, insbesondere der Statistik & Optimierung.

Inhalt dieser Vorlesung ist

Das Verstehen und Implementieren von Algorithmen des Maschinellen Lernens.

Inhalt dieser Vorlesung ist NICHT

Das Herleiten/Erklären der zugrunde liegenden Mathematik.


Zusammenfassung

Documents

INTELLIGENTE DATENANALYSE IN MATLAB · Entwicklung von Schätz- und Testverfahren für solche Aussagen, z.B.: Schätzer für Parameter von Verteilungsfunktionen. Signifikanztests