Mustererkennung - Klausur

Behandelter Stoff

Vorlesung

Folien

ME-Kap1_V31.pdf

Einleitendes Kapitel welches erklärt, was Klassifikation ist.

• Beispiele für Klassifikation: Blumen/Schmetterlinge in Arten; Schrauben in Schraubentypen; Schüttgut in Mineralien, Pflanzen, Glasscheiben, Diamante, ...
• Formalismen
• Domäne \(\Omega \subseteq\) Welt, Elemente der Domäne heißen Objekte, Objekte werden in paarweise disjunkte Äquivalenzklassen \(\omega_i\) gruppiert, sodass jedes Objekt genau eine Äquivalenzklasse hat.
• Man beobachtet / misst Eigenschaften realer Objekte. Dies kann als Funktion m aufgefasst werden, die von der Domäne in den Merkmalsraum abbildet. Optimalerweise ist diese Abbildung injektiv, bei ungünstig gewählten Merkmalen jedoch nicht. Klassifikatoren arbeiten auf dem Merkmalsraum und finden eine Partition des Merkmalsraumes in Klassen
• Muster: Gesamtheit der beobachteten / gemessenen Werte einer einzelnen Stichprobe (eines einzelnen Objekts).
• Erkennung: (Wieder)erkennung von etwas, was bereits bekannt ist.
• Merkmale: eruirbare, charakteristische Eigenschaften, die als Basis für die Untersuchung von Mustern dienen soll.
• Mustererkennungsschritte: Sensierung ergibt Muster; Vorverarbeitung; Segmentierung; Merkmalsextraktion ergibt Merkmale; Klassifikation ergibt Äquivalenzklassen
• Überwachtes lernen: Vorklassifizierte Beispiele sowie die Klassenstruktur sind gegeben; eventuell auch Auftrittswahrscheinlichkeiten \(P(\omega_i)\) der Klassen
• Gesamtstichprobe wird in die disjunkten Mengen Lernstrichprobe, Validierungsstichprobe und Teststichprobe zerlegt.

Merkmale

Slides: ME-Kap2_V84.pdf

In diesem Foliensatz geht es um Merkmale und ihre Eigenschaften.

Der Merkmalsraum ist häufig ein \(\mathbb{R}^n\) mit \(n>3\). Er kann auf vorhandene Strukturen analysiert werden, indem er auf einen 2- oder 3-dimensionalen unterraum projeziert wird. Dies kann bei einfachen Projektionen jedoch nicht erfolgreich sein, wenn beispielsweise zwei Klassen Schalenförmig um den Urspruch angeordnet sind.

Um Stichproben im Merkmalsraum zu vergleichen können Metriken benutzt werden. Eine Metrik ist eine Abbildung \(d(m_1, m_2)\), für die gilt:

• Positive Definitheit: \(d(m_1, m_2) \geq 0\) und \(d(m_1, m_2) = 0 \Leftrightarrow m_1 = m_2\),
• Symmetrie: \(d(m_1, m_2) = d(m_2, m_1)\),
• Dreiecksungleichung: \(d(m_1, m_2) \leq d(m_1, m_3) + d(m_3, m_2)\)

Metriken können durch Normen erzeugt werden, indem \(d(m_1, m_2) := \|m_1 - m_2\|\) definiert wird. Eine Norm ist eine Abbildung \(\| \cdot \|: V \rightarrow \mathbb{R}_0^+, x \mapsto \|x\|\) für die gilt:

• Definitheit: \(\|x\| = 0 \Rightarrow x = 0\)
• Absolute Homogenität: \(\|\alpha \cdot x \| = \alpha \cdot \| x \|\)
• Dreiecksungleichung: \(\|x+y\| \leq \|x\| + \|y\|\)

Typische Normen sind die euklidische Norm und die Mahalanobis Norm \(\|m\| := \sqrt{m^T A m}\) mit \(A\) positiv definit.

Hauptkomponentenanalyse (HKA, engl. PCA)

1. Finde \(m_0\), sodass \(J_0(m) := \sum_{k=1}^N \|m - m_k\|^2\) minimal ist, also \(m_0 = \frac{1}{N} \sum_{k=1}^N m_k\)
2. Finde Gerade \(h: m = \bar{m} + ae\), welche die Punkte optimal repräsentiert.
   1. Finden der \(a_k\) (TODO: Was ist das?)
      Fehlermaß \(J_1(a_1, \dots, a_N, e) = \sum_{k=1}^N \|\bar{m} + a_k e - m_k \|^2\).
      Ergibt: \(a_k = e^T (m_k - \bar{m})\)
   2. Berechnung des optimalen Richtungsvektors
      Streumatrix \(S := \sum_{k=1}^N (m_k - \bar{m}) (m_k - \bar{m})^T\)
3. Finden eines affinen \(d'\)-dimensionalen Unterraumes des Merkmalsraumes, welcher die Daten \(D\) mit minimalen quadratischem Fehler repräsentiert.

Siehe gist für eine kurze Python-Implementierung. Keine Garantie für die Korrektheit!

• Kernelized PCA
• Independent Component Analysis (ICA)
• Multiple Discriminant Analysis (MDA)

ME-Kap3_V52.pdf

Bayessche Klassifikatoren wählen die Klasse aus, die die größte Wahrscheinlichkeit besitzt. Dazu verfolgt man den Ansatz

Dabei wird \(P(\omega|m)\) die A Posteriori Wahrscheinlichkeitsverteilung und \(P(\omega)\) die A Priori Wahrscheinlichkeitsverteilung genannt.

ME-Kap4_V33.pdf

Parameterschätzung kann entweder mit der Likelihood-Methodik oder mit der Bayesschen Methodik durchgeführt werden. Die Idee der Likelihood-Methodik ist es, den Parameter \(\theta\) als unbekannte konstante (d.h. nicht-stochastische) Größe anzusehen. Man wählt \(\theta\) also so, dass die Wahrscheinlichkeit der Beobachtungen gegeben \(\theta\) maximiert wird.

Die Bayessche Methodik geht dagegen davon aus, dass \(\theta\) auch eine Zufallsvariable ist und über eine Wahrscheinlichkeitsverteilung beschrieben werden kann.

Schätzer können verschiedene Qualitätskriterien erfüllen, z.B. Erwartungstreue oder Konsistenz.

Bei der Parameterschätzung können folgende Fehler passieren:

• Bayesscher Fehler: (TODO: Was ist das?)
• Modellfehler: Unpassendes Modell gewählt (Falsche Verteilungsannahme?)
• Schätzfehler: Zu wenige Daten um Parameter korrekt zu bestimmen

ME-Kap5_V31.pdf

Parameterfreie Methoden heißen "parameterfrei", weil sie keine konkrete Wahrscheinlichkeitsverteilung parametrisieren und den Parameter schätzen. Die Parameterfreien Methoden können sehr wohl Parameter benutzen. Beispiele sind:

• Parzen Window
• Nächste Nachbarn

ME-Kap6_V18.pdf

Allgemeine Problemstellungen:

• Dimension des Merkmalsraumes
• Overfitting

ME-Kap7_V54.pdf

Spezielle Klassifikatoren:

• Lineare Diskriminanzfunktionen: Linear bezieht sich hier auf die Kombination der Merkmale. Man kann allerdings Merkmale wählen, die z.B. das quadrat eines gemessenen wertes sind.
• Perzeptron
• Lineare Regression
• Künstliche Neuronale Netze
• Support Vector Machines (SVMs)
• Matched Filter
• HMMs (Sequenzen)
• Klassifikation mit Rückweisung (Maximum / Minimum / Differenz / Abstand)

ME-Kap8_V21.pdf

Klassifikation bei nominalen Merkmalen:

• Entscheidungsbäume
• String-Verfahren
• Grammatiken

ME-Kap9_V27.pdf

Klassifikatorunabhängige Prinzipien:

• Generalisierung / Generalisierungsfähigkeit
• VC-Konfidenz / VC-Dimension
• Structural Risc Minimization
• Kreuzvalidierungsverfahren / Leave-one-out
• Boosting

Prüfungsfragen

• Warum ist ein hochdimensionaler Merkmalsraum schlecht (curse of dimensionality)?
• Je nach Klassifikator, viele zu lernende Parameter
• Daten haben einen sehr hohen Abstand zueinander → Gefahr des Overfittings
• Wie kann man die Dimension des Merkmalsraumes reduzieren?
  → Merkmalsauswahl, suboptimales iteratives Verfahren, HKA (Varianzen maximieren), MDA (Klassentrennbarkeit maximieren), ICA
• Wie viele Möglichkeiten gibt es 5 Merkmale aus 10 auszuwählen? → Binomialkoeffizient
• Was ist Overfitting?
  → Siehe ML 1
• Welche Probleme gibt es, wenn man Länge, Masse und Temperatur als Merkmale hat?
• Unterschiedliche Einheiten (→ Entdimensionalisieren)
• Unterschiedliche Skalen (→ Teilen durch Varianz oder durch Wertebereich)
• Unterschiedliche Wertebereiche (→ Durchschnitt abziehen)
• Wie funktioniert MDA?
  → Sie maximiert \(J(w) = \frac{|m'_1 - m'_2|^2}{{s'}_1^2 - {s'}_2^2}\) (im 2-Klassen Fall, wobei \(w\) die Ebene ist, auf die projeziert wird)
• Wie unterscheidet sich PCA/MDA von dem suboptimalen Algorithmus zur Merkmalsauswahl?
  → PCA/MDA sind Klassifikatorunabhängig, aber der suboptimale Algorithmus benötigt bereits einen Klassifikator.
• Wie lautet die Fundamentalformel der Bayesschen Klassifikation?
  → \(P(A|B) = \frac{P(A)\, P(B | A)}{P(B)}\) (wobei üblicherweise B das Merkmal ist und A die Klasse)
• Wie lautet die Hauptformel der PCA?
  \(m' = A^T \cdot (m - \bar{m})\), wobei \(A\) die Basiswechselmatrix ist.
• Wie kann man invariante Merkmale erzeugen?
  → Integration über eine Transformationsgruppe, Differentielle Methode, Normalisierung
• Wie kann man normalisieren?
  → Fourierdeskriptoren kann man invariant bzgl. Translation und Rotation und radialer Streckung (Skalierung) machen
• Wie lauten die Prinzipien (A) - (E) der SVMs?
  • (A) Lineare Trennung mit maximalen Abstand der Trennebenen zu den nächstgelegenen Stichproben (Support Vektoren)
  • (B) Duale Formulierung des linearen Klassifikators. (vgl. Wiki, \(k(m) = w^T m + b = \langle w, m \rangle + b = \sum_{j=1}^N \alpha_j z_j \langle m_j, m \rangle + b\))
  • (C) Nichtlineare Abbildung der primären Merkmale in einen hochdimensionalen Merkmalsraum \(\Phi\)
  • (D) Implizite Nutzung des unter Umständen \(\infty\)-dimensionalen Eigenfunktionsraumes einer sog. Kernfunktion \(K\) als transformierten Merkmalsraum \(\Phi\). Dabei müssen die transformierten Merkmale nicht explizit berechnet werden und der Klassifikator hat trotz der hohen Dimension von \(\Phi\) nur eine niedrige Zahl von freien Parametern (Kernel-Trick).
  • (E) Relaxation der Forderung nach linearer Trennbarkeit durch Einführung von Schlupfvariablen (slack variables).
• Wie lautet die Dichtefunktion der \(d\)-dimensionale Gaußverteilung? \(f_X(x) = \frac{1}{\sqrt{((2\pi)^d \det{\Sigma})}} \exp(-\frac{1}{2}(x-\mu)^T \Sigma^{-1} (x-\mu))\)
• Wie lautet Mercers Theorem? → wiki
• Wie ist die Kullback-Leibler-Divergenz defininiert?

Material und Links

• Vorlesungswebsite: Ist passwortgeschützt. Das Passwort (das ausnahmsweise mal nicht zu erraten ist) kann ich hier natürlich nicht schreiben. Aber der Benutzername ist asbstudent.
• SVMs
• Why bother with the dual problem when fitting SVM?
• A Tutorial on Support Vector Machines for Pattern Recognition

Übungsbetrieb

Es gibt keine Übungsblätter, keine Übungen, keine Tutorien und keine Bonuspunkte.

Vorlesungsempfehlungen

Folgende Vorlesungen sind ähnlich:

• Analysetechniken großer Datenbestände
• Informationsfusion
• Machine Learning 1
• Machine Learning 2
• Mustererkennung
• Neuronale Netze
• Lokalisierung Mobiler Agenten
• Probabilistische Planung

Termine und Klausurablauf

Datum: Donnerstag, der 10.09.2015 von 11:00-13:00 Uhr (Quelle: Wurde in der Vorlesung vom 22.04.2015 gesagt)
Ort: Gerthsen-Hörsal
Punkte: 90
Zeit: 90 min
Punkteverteilung: ?

• ab 60.5: 1.7

Bestehensgrenze: ?
Übungsschein: gibt es nicht
Bonuspunkte: gibt es nicht
Ergebnisse: Am 30.09.2015 war die (vorläufige) Note im Notenauszug
Einsicht: Montag 12.10.2015, 9:00-15:00 Uhr im Geb. 50.21, Raum 015.1
Erlaubte Hilfsmittel: keine

Notenverteilung

Wenn ihr mir schreibt was ihr habt, kann ich das updaten:

• 1,3: min 1
• 2,0: min 1