Informatik III - alle Semester Wintersemester 2000/01

Deduktive Datenbanken (4V+2Ü) (C) Mo Do 13-15, HS 1 (Prof. Dr. Rainer Manthey) Übungen: Mi 13-15, A 207 (Prof. Dr. Rainer Manthey, A. Behrend) Informationstheorie (3V) (A,C) Mo 9-11, HS 1, Mi 9-10, HS 1 (Prof. J. Buhmann)

Vorlesung (Hauptstudium)

Mustererkennung

Prof. J. Buhmann

Zeit, Ort	Mi 10-11, Fr 9-11, HS 1
Semesterwochenstunden	3V + 2Ü
Beginn	1. Semesterwoche
Übungen	Mi 13-15, R A 121 (Prof. J. Buhmann und Mitarbeiter)
Voraussetzungen	Infinitesimalrechnung I, II. Wünschenswert: Statistik für Informatiker.
Bereich (alte DPO)	A,C
Prüfungsmöglichkeiten	Als Teil einer A/C-Prüfung über 12 Semesterwochenstunden.
Literatur	Ripley, Brian D.: Pattern recognition and neural networks, Cambridge University Press, Cambridge, New York, 1996. Bishop, Christopher M.: Neural networks for pattern recognition, Oxford University Press, 1995. Fukunaga, Keinosuke: Introduction to statistical pattern recognition, Academic Press, New York, 1990. Duda, Richard O.; Hart, Peter E.: Pattern Classification and Scene Analysis, John Wiley and Sons, New York, 1973. Cover, Thomas M.; Thomas, Joy A.: Elements of information theory, Wiley, New York, 1991. Vapnik, Vladimir N.: The nature of statistical learning theory, Springer, Berlin, 1995.

Weiteres Material

Die Vorlesung in Stichworten

I.1 Datentaxonomie: Designraum, Konfigurationsraum, Skalen, Datentypen (vektoriell, Ähnlichkeitsdaten, Histogramme)
I.2 Datenquellen
I.3 Fragen der Mustererkennung: Klassifikation, Regression
I.4 Unüberwachte Lernprobleme: Datengruppierung, Vektorquantisierung, hierarchische Datenanalyse, Dimensionsreduktion, Visualisierung
I.5 Schwach überwachte Lernprobleme: Reinforcement Learning

II BAYESSCHE ENTSCHEIDUNGSTHEORIE

II.1 Problemstellung
II.2 Kostenfunktionen: Verlustfunktion, erwartetes Risiko, optimaler Klassifikator, Ausreißer
II.3 Bayes-Regel, Diskriminanzfunktionen, Beispiele
II.4: Parameterschätzung: Maximum-Likelihood-Schätzung, Bayessches Lernen

III THEORIE VON SCHÄTZFUNKTIONEN

III.1: Plug-In-Prinzip, Glivenco-Cantelli-Theorem, Konsistenz und Erwartungstreue, erschöpfende Schätzfunktionen, Faktorisierungssatz
III.2: Satz von Rao-Blackwell, Rao-Cramer-Ungleichung
III.3: Hierarchie von Schätzern, Konvergenz von ML-Schätzern, ML-Schätzer als asymptotisch wirksamste Schätzer
III.4: Stein-Schätzer
III.5: Numerische Schätzfunktionen: Crossvalidierung (Leave-One-Out), Bootstrap, Jackknife

IV HYPOTHESENTESTS

IV.1: 2-Klassen-Problem, Fehler 1. und 2. Art
IV.2: Neyman-Pearson-Test
IV.3: Bayes-Fehler, Chernoff-Schranke

V DISKRIMINANZANALYSE

V.1: Fishers lineare Diskriminanzanalyse für 2 und mehr Klassen
V.2: Verallgemeinerte Diskriminanzfunktionen (linear, quadratisch, polynomiell)
V.3: Linear seperabler Fall, Gradientenabstiegsverfahren
V.4: Perzeptron-Kriterium, Lernalgorithmus, Konvergenzbeweis, XOR-Problem, MLP
V.5: Winnow-Algorithmus
V.6: Optimierung quadratischer Kostenfunktionen, Margin-Prinzip
V.7: Nichtseparabler Fall, Widrow-Hoff-Regel (Batch- und Online-Version)
V.8: Support-Vektor-Maschinen: Idee, primäres und duales Optimierungsproblem, Soft-Margin-SVM, Kuhn-Tucker-Bedingung, nicht lineare SVM, Kerne, Satz von Mercer,
V.9: Funktionenzählen: Kapazität von Hyperebenen, Dichotomien und Rekursionsformel
V.10: Backpropagation, McCulloch-Pitts-Neuron, Universelle Approximationseigenschaft neuronaler Netze

VI ALGORITHMISCHE LERNTHEORIE

VI.1: PAC-Lernen
VI.2: Empirische Risikominimierung, punktweise und gleichm. Konvergenz, Chebychev-Ungleichung, Hoeffding-Ungleichung
VI.3: Fehlerschranken für endliche Klassifikatormengen
VI.4: Empirische Risikominimierung (ERM) für Hyperebenen
VI.5: VC-Theorie und Klassifikation, VC-Theorem (1971) mit Beweis, VC-Dimension und Lernbarkeit

VII NICHT PARAMETRISCHE METHODEN

VII.1: Dichteschätzung: Parzen-Fenster
VII.2: K-Nächste-Nachbarn-Methode, erwartete Fehlerrate für K=1 und für beliebiges K

VIII UNÜBERWACHTES LERNEN

VIII.1: Methoden zur Dimensionsreduktion
VIII.2: Lineare Methoden: Hauptachsentransformation (PCA), Projection Pursuit (Projektionsindizes: standardisiertes absolutes Moment, standardisierte Fisher-Information, standardisierte negative Entropie, Friedman-Tukey-Index), PCA als Spezialfall
VIII.3: Nichtlineare Methoden: Principle Curves nach Hastie und Stuetzle bzw. Erweiterungen und Theoreme nach Kégl et al.(PAMI 22(3))
VIII.4: Mehrdimensionale Skalierung (MDL): S-Stress, Sammon, metrische / nicht metrische MDS, Dimensionsstress und effektive Dimension

Übungsblätter