Martin Thoma A blog about Code, Politics, and my life

Mustererkennung - Klausur

· by

Inhalt
Dieser Artikel beschäftigt sich mit der Vorlesung „Mustererkennung“ am KIT. Er dient als Prüfungsvorbereitung. Ich habe die Vorlesungen bei Herrn Prof. Dr.-Ing. Jürgen Beyerer im Sommersemester 2015 gehört und einige Abschnitte direkt aus den Folien übernommen.

Behandelter Stoff

Vorlesung

Datum Kapitel Inhalt
15.04.2015 Einleitung $\hat{w}$ - das ^ bedeutet, dass die Klasse geschätzt ist.
22.04.2015 Kapitel 2 - Merkmale: 1-31? Welt; Domäne; Objekte; Klassen; Merkmalsraum; Merkmalsvektor; Klassifikation; Skalen (nominal, ordinal, intervall-, verhältnis- und absolutskaliert); Projektionen; Norm (Minkowski, Euklidisch, Chebychev, Mahalanobis); Metrik (Tanimoto)
14.07.2015 Kapitel 8 - Klassifikatoren (1-28), Kapitel 9: 1-? Entscheidungsbäume, Grammatiken; Lernen nach Vapnik, VC-Dimension, Kreuzvalidierung und Leave-One-Out, Boosting

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, Diamanten, ...
  • 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 zu genau einer Äquivalenzklasse gehört.
  • 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: eruierbare, charakteristische Eigenschaften, die als Basis für die Untersuchung von Mustern dienen sollen.
  • 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 Lernstichprobe, Validierungsstichprobe und Teststichprobe zerlegt.

Merkmale

Slides: ME-Kap2_V84.pdf

In diesem Foliensatz geht es um Merkmale und ihre Eigenschaften.

  Skala
qualitativ (kategorial) quantitativ (metrisch)
Nominal- Ordinal- Intervall- Verhältnis- Absolut
Empirische Relation ~ Äquivalenz ~ Äquivalenz
Ordnung		 ~ Äquivalenz
Ordnung
Emp. Addition		 ~ Äquivalenz
Ordnung
Emp. Addition
Emp. Multiplikation		 ~ Äquivalenz
Ordnung
Emp. Addition
Emp. Multiplikation
Zulässige Transformationen m' = f(m)
f bijektiv		 m' = f(m)
f streng monoton		 m' = am+b
mit a>0		 m' = am
mit a>0		 m' = m
Beispiele zugehörige Merkmale Telefonnummern, Kfz-Kennz., Typen, PLZ, Geschlecht Güteklassen, Härtegrad, Windstärke Temp. in °C, °F, Kalenderzeit, geografische Höhe Masse, Länge, el. Strom Quantenzahlen, Teilchenanzahl, Fehlerzahl
Werte von m Zahlen, Namen, Symbole in der Regel natürliche Zahlen in der Regel reelle Zahlen in der Regel reelle Zahlen > 0 in der Regel natürliche Zahlen

Der Merkmalsraum ist häufig ein \(\mathbb{R}^n\) mit \(n>3\). Er kann auf vorhandene Strukturen hin analysiert werden, indem er auf einen 2- oder 3-dimensionalen Unterraum projiziert wird. Dies kann bei einfachen Projektionen jedoch nicht erfolgreich sein, wenn beispielsweise zwei Klassen schalenförmig um den Ursprung 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\): \(a_k\) ist die Koordinate des auf die Gerade projizierten Punktes \(m_k\) (mit \(\|e\| = 1\)).
      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\)
      Der optimale Richtungsvektor \(e\) ist der Eigenvektor von \(S\) zum größten Eigenwert.
  3. Finden eines affinen \(d'\)-dimensionalen Unterraumes des Merkmalsraumes, welcher die Daten \(D\) mit minimalem 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

$$P(\omega|m) = \frac{p(m|\omega) \cdot P(\omega)}{p(m)}$$

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: Der Fehler, den selbst der optimale Bayes-Klassifikator mit der wahren Verteilung macht, weil sich die Klassen im Merkmalsraum überlappen. Er lässt sich nicht reduzieren.
  • 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:

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:

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: $\binom{10}{5} = 252$
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 Standardabweichung oder durch Wertebereich; teilt man eine normalverteilte Variable durch ihre Standardabweichung, erhält man eine standardisierte Variable)
  • 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 Richtung der Geraden ist, auf die projiziert 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 maximalem 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$-dimensionalen 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

Übungsbetrieb

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

Vorlesungsempfehlungen

Folgende Vorlesungen sind ähnlich:

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örsaal
Punkte: 90
Zeit: 90 min
Punkteverteilung: ?
Notenschlüssel (unvollständig): ab 60,5 Punkten: 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