Post on 20-Jul-2020
transcript
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:
18.10.2009Michael Brückner/Tobias Scheffer4
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:
18.10.2009Michael Brückner/Tobias Scheffer5
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:
18.10.2009Michael Brückner/Tobias Scheffer6
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:
18.10.2009Michael Brückner/Tobias Scheffer7
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:
18.10.2009Michael Brückner/Tobias Scheffer8
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):
18.10.2009Michael Brückner/Tobias Scheffer9
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:
18.10.2009Michael Brückner/Tobias Scheffer10
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:
18.10.2009Michael Brückner/Tobias Scheffer11
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:
18.10.2009Michael Brückner/Tobias Scheffer12
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).
18.10.2009Michael Brückner/Tobias Scheffer13
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.
18.10.2009Michael Brückner/Tobias Scheffer14
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.
18.10.2009Michael Brückner/Tobias Scheffer15
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:
18.10.2009Michael Brückner/Tobias Scheffer16
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:
18.10.2009Michael Brückner/Tobias Scheffer17
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.
18.10.2009Michael Brückner/Tobias Scheffer18
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:
18.10.2009Michael Brückner/Tobias Scheffer19
StochastikWahrscheinlichkeitstheorie
( ) 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:
18.10.2009Michael Brückner/Tobias Scheffer20
StochastikWahrscheinlichkeitstheorie
( ) ( ) ( | ( ) )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:
18.10.2009Michael Brückner/Tobias Scheffer21
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):
18.10.2009Michael Brückner/Tobias Scheffer22
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.
18.10.2009Michael Brückner/Tobias Scheffer23
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.
18.10.2009Michael Brückner/Tobias Scheffer24
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
18.10.2009Michael Brückner/Tobias Scheffer25
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.
18.10.2009Michael Brückner/Tobias Scheffer26
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. .
18.10.2009Michael Brückner/Tobias Scheffer27
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.
18.10.2009Michael Brückner/Tobias Scheffer28
Zusammenfassung