Machine Learning 2

Dieser Artikel beschäftigt sich mit der Vorlesung „Machine Learning 2“ am KIT. Er dient als Prüfungsvorbereitung. Ich habe die Vorlesungen bei Herrn Prof. Dr. Marius Zöllner im Sommersemester 2015 gehört.
Es gibt auch einen Artikel zu Machine Learning 1.

Behandelter Stoff

Einführung

Slides: 01_Einfu__hrung_MLII.pdf

Rückblick auf ML 1. MLNN steht übrigens für Multi-Layer Neural Network.

Semi-Supervised Learning

Slides: 02_Semi-supervised-learning.pdf

Überwachtes Lernen (engl. Supervised Learning)
Alle Trainingsdaten liegen mit Labels vor.
Unüberwachtes Lernen (engl. Unsupervised Learning)
Alle Trainingsdaten liegen ohne Labels vor.
Semi-Supervised Learning (SSL)
Die meisten Trainingsdaten liegen ohne Labels vor, jedoch gibt es für jede Klasse auch gelabelte Daten.
Self-Learning (Self-Training, Self-Labeling, Decision-directed learning)
Self-Training ist ein Algorithmus zum Semi-supervised Learning. Er geht wie folgt vor:
  1. Trainiere mit gelabelten Daten.
  2. Werte ungelabelte Daten aus.
  3. Füge Daten, bei denen sich der Klassifizierer sicher ist, zu den Trainingsdaten hinzu.
  4. Zurück zu Schritt 1.
Dabei sind folgende Variationen vorstellbar:
  • Füge alle Daten hinzu.
  • Füge nur Daten hinzu, bei denen sich der Klassifizierer sicher ist.
  • Gewichte Daten mit der Sicherheit.
Co-Training (Mit-Lernen)
Co-Training ist ein Algorithmus zum Semi-supervised Learning. Er geht wie folgt vor:
  1. Splitte jeden Feature-Vektor auf die gleiche Art in zwei Feature-Vektoren mit disjunkten Features auf.
  2. Trainiere zwei unterschiedliche Klassifizierer auf den beiden unterschiedlichen Feature-Mengen der gelabelten Daten.
  3. Label mit den beiden Klassifizieren die ungelabelten Daten.
  4. Füge ungelabelte Daten dem Trainingsdatensatz (also den gelabelten Daten) hinzu, falls die Klassifizierer für diese eine hohe Konfidenz aufweisen.
  5. Zurück zu Schritt 2.
Dabei sind folgende Variationen vorstellbar:
  • Demokratisches Voting: Bei mehr als 2 Klassifizierern.
  • Schwellwert: Nur hinzufügen, wenn alle Klassifizierer jeweils eine Schwelle überschreiten.
  • Gewichtes Voting: Alle Klassifizierer zusammen müssen eine Schwelle überschreiten.
Low Density Separation
Methoden, welche Low Density separation benutze versuchen die Entscheidungsgrenze in eine Region niedriger Dichte zu legen. Ein Beispiel ist die Transductive SVM.

Weiteres:

Hier könnte ich mir gut vorstellen, dass man eine Bachelor / Master-Arbeit macht. Man könnte sich große gelabelte Datensätze suchen, einen gewissen Teil der Labels weglassen (also einige Trainingsdaten als "ungelabelt" behandeln) und die verschiedenen SSL-Methoden untersuchen. Bis zu 20% gelabelte Daten hoch wäre es interessant; also z.B. (0.5%, 1%, 2%, 3%, 5%, 10%, 15%, 20% gelabelte Daten). Mit mehr gelabelten Daten könnte man argumentieren, dass man es sich vermutlich leisten könnte auch den Rest noch zu labeln. Siehe Folie 28-31.

SSL and Active Learning

Slides: 03_Semi-supervised+Active-learning.pdf

Lagrange-Multiplikator
Lagrange-Multiplikatoren sind ein Verfahren der Optimierungstheorie. Sie werden genutzt, wenn ein Optimierungsproblem mit Nebenbedingungen vorliegt. Durch sie kann die Nebenbedingung eliminiert werden.
Active Learning (Aktives Lernen)
Die Lernmaschine wählt die zu lernenden Daten selbst aus.

Verfahren:
Query Synthesis (siehe Active Learning Literature Survey)
Der Lerner kann Feature-Vektoren (Querys) de novo, also von Grund auf neu / selbst erzeugen. Er kann für diesen neuen Query ein Orakel befragen, was das Label ist.
Selective Sampling (Selektive Entnahme, siehe Selective sampling and active learning from single and multiple teachers)
Selective Sampling ist eine Methode des aktiven Lernens. Dabei wird jede Runde $t$ dem Lerner ein Feature-Vektor $x_t \in \mathbb{R}^n$ präsentiert. Der Lerner muss sich jede Runde entscheiden, ob er einen Preis bezahlt um das Label zu sehen. Der Lerner hat also zwei Ziele, die miteinander in Konflikt stehen: Er will alles richtig klassifizieren, aber zugleich die Kosten so niedrig wie möglich halten.
Pool-Based Active Learning
Pool-Based Active Learning ist eine Methode des aktiven Lernens. Dabei wird von einem Pool an ungelabelten Daten $\mathcal{U}$ ausgegangen und einem deutlich kleineren Pool $\mathcal{L}$ an gelabelten Daten. Queries werden aus $\mathcal{U}$ gezogen. Dabei wird ganz $\mathcal{U}$ evaluiert und für den hilfreichsten Feature-Vektor $x \in \mathcal{U}$ nach einem Label gefragt.
Hinge-Funktion
$$f(x) = \max(x, 0)$$
Query-by-Committee (QBC)
Es wird ein Committee $\mathcal{C}$ an Klassifikatoren trainiert, welches gemeinsam (z.B. durch majority vote) eine Klassifikation trifft. Allgemeiner Ansatz:
  • Trainiere eine Menge $\mathcal{C}$ an Klassifikatoren
  • Wähle neue Daten, wenn die Hypothesen Wiedersprüchlich sind
Selektive Entnahme:
  1. Beobachte neue Instanz $x$ und werte diese mit $\mathcal{C}$ aus
  2. Frage das Label ab, falls es einen Wiederspruch in den Hypothesen von $\mathcal{C}$ für $x$ gibt.
  3. Neu trainiren, zurück zu 1
Pool-based Active Learning:
  1. Messung des Wiederspruchs der Hypothesen für alle Instanzen $x$
  2. Ranking (z.B. Entropie)
  3. Abfrage der Labels für die $k$ widersprüchlichsten Instanzen
  4. Neu trainiren, zurück zu 1

Weiteres:

  • Ausreißerproblem: Ausreißer sollten im QBC nicht genommen werden. Dazu könnte die Dichte im Datenraum gemessen werden.

Reinforcement Learning

Slides: 04_Reinforcement_Learning_II.pdf

Siehe auch:

Markov Decision Process (MDP)
Ein Markovscher Entscheidungsprozess ist ein 5-Tupel $(S, A, T, r, p_0)$, wobei
  • $S$ eine endliche Zustandsmenge,
  • $A$ eine endliche Menge von Aktionen,
  • $T_a(s, s') = T(s_{t+1}=s'|s_t = s, a_t = a)$ die Wahrscheinlichkeit zu einem beliebigen Zeitpunkt von Zustand $s$ mit der Aktion $a$ in den Zustand $a'$ zu kommen (engl. Transition),
  • $r_a(s, s')$ ist die Belohnung (Reward), die man direkt erhält wenn man erhält wenn man von Zustand $s$ mit Aktion $a$ in Zustand $s'$ kommt,
  • $p_0$ ist die Startverteilung auf die Zustände $S$
Partially observable Markov decision process (POMDP)
Ein partially observable Markov decision process ist ein 7-tupel $S, A, T, R, \Omega, O, \gamma$, wobei
  • $S$ die Zustandsmenge,
  • $A$ die Aktionsmenge,
  • $T: S \times A \times S \rightarrow \mathbb{R}$ die probabilisitische Zustandsübergangsfunktion (transition function) ist,
  • $R: S \times A \rightarrow \mathbb{R}$ die Reward-Funktion,
  • $\Omega$ die Menge der möglichen Beobachtungen,
  • $O$ die Wahrscheinlichkeit der Beobachtungen, gegeben ein Zustand und eine Aktion und
  • $\gamma \in [0, 1]$ der Diskontierungsfaktor
ist.
Options
Eine Option ist wohl-definiertes Verhalten, welches im hierarchischen RL eingesetzt werden kann. Es ist ein Baustein für komplexe Pläne. Options werden in Semi-MDPs eingesetzt und ersetzen dort die Aktionen.
Hierarchien Abstrakter Maschinen (HAM)
Ein MDP wird mit Maschinen $\{M_i\}$ kombiniert. Jede Maschine repräsentiert einen Teil der Policy. Jede Maschine verwendet eigene Zustände $m_t^i$ und globale Zustände $s_t$. Maschinen werden durch Zustandsautomaten abgebildet.
MaxQ-Dekomposition (siehe [Die00])
Das zu lösende MDP $M$ wird als Menge von Unteraufgaben $\{M_0, \dots, M_n\}$ interpretiert. Dabei ist $M_0$ das Haupt-MDP. TODO.

Folie 35:

  • NODO: Was heißt hier "mit festen Knoten"?

Dynamische Bayessche Netze

Slides: 05_DynamischeBayesscheNetze.pdf

Multiplikationssatz
Seien $A, B, X_i$ Ereignisse. Dann gilt: $$P(X_1, \dots, X_n) = P(X_1) \cdot \prod_{k=2}^n P(X_k | X_{k-1}, \dots, X_1)$$ und insbesondere $$P(A\cap B) = P(A, B) = P(A\mid B) \cdot P(B)$$
Gesetz der totalen Wahrscheinlichkeit
Seien $A_1, \dots, A_n$ paarweise disjunkte Ereignisse mit $A = \sum_{i=1}^n A_i$. Dann gilt für jedes beliebige Ereignis $B$: $$P(B) = \sum_{i=1}^n P(B | A_i) \cdot P(A_i) = P(A_i, B)$$
Satz von Bayes
Seinen $A, B$ Ereignisse mit $P(B) > 0$. Dann gilt $$P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$$ Hierbei heißt $P(A|B)$ die a posteriori Wahrscheinlichkeit, $P(B|A)$ die likelihood, $P(A)$ die a priori Verteilung über $A$ und $P(B)$ die a priori Verteilung über $B$.
Bayessches Netz (Siehe Lecture 13: Bayes Nets)
Ein Bayessches Netz ist ein DAG, bei dem die Knoten Zufallsvariablen und die Kanten bedingte Abhängigkeiten beschreiben. Bayessche Netze sind zur Modellierung kausaler Zusammenhänge geeignet.
Markov Random Field
Siehe ML 1
Dynamisches Bayessches Netz
Dynamische Bayessche Netze sind Bayessche Netze zur Beschreibung dynamischer Prozesse.
Markov Blanket
Sei $G=(V,E)$ ein DAG zu einem Bayesschen Netz und $v_S \in V$. Dann ist der Markov Blanket die folgende Knotenmenge $B \subseteq V \setminus \{v_S\}$:
  • Die Elternknoten von $v_S$ sind in $B$.
  • Die Kindknoten $K = \{v_{K_1}, \dots, v_{K_n}\}$ sind in $B$
  • Die Elternknoten von $K$, ausgenommen von $v_S$, sind in $B$
Diese Knotenmenge macht $v_S$ unabhängig von anderen Knoten.
Naive Bayes Spam Filter
Ein naiver Bayes Spamfilter nutzt häufig Bag-of-Words Features. Man berechnet die Wahrscheinlichkeit, dass eine gegebene E-Mail Spam ist. Dazu geht man davon aus, dass die Wörter in einer E-Mail unabhängig von einander sind und nutzt den Satz von Bayes. Siehe Bayes-Klassifikator für eine detailiertere Beschreibung.
Bayes Filter
Ein Bayes Filter ist eine Familie von Zufallsvariablen. Das könnte z.B. die $(x,y,z)$ Position eines GPS-Sensors sein. Diese Position ist verrauscht. Nun gibt es drei mögliche Anfragen:
  • Filtern: Es liegen Messungen $Z_0, \dots, Z_t$ vor, sage die aktuelle Position $X_t$ vorher. Also filtere das Rauschen aus $Z_t$ unter berücksichtigung, dass wir uns noch nicht teleportieren können: $$P(X_t | Z_t, \dots, Z_0)$$
  • Prädizieren: Es liegen Messungen $Z_0, \dots, Z_t$ vor, sage die Position $X_{t+k}$ vorher: $$P(X_{t+k} | Z_t, \dots, Z_0)$$
  • Glätten: Es liegen Messungen $Z_0, \dots, Z_t$ vor, sage die Position $P(X_{t-k} | Z_t, \dots, Z_0)$ vorher.
Beispiele für Bayes-Filter sind
Naiver Bayes'scher Spam Filter
Ein probabilistischer Klassifikator welcher die Unabhängigkeit der Features vorraussetzt wird naiv genannt.

Der naive bayessche Spam Filter nutzt Bayes Theorem um die Wahrscheinlichkeit zu berechnen, dass eine E-Mail Spam ist.
Kalman-Filter
Der Kalman-Filter ist ein Bayes-Filter. Er wird z.B. zum Schätzen einer Fahrzeugtrajektorie eingesetzt. Der Kalman-Filter besteht aus zwei Schritten:
  • Predict the next step of the system given the previous measurements.
  • Update the estimate of the current state given the measurement of this time step.
Siehe Kalman-Filter Artikel für Details.
Expectation Maximizaion Algorithm (EM-Algorithmus)
Der EM-Algorithmus ist ein Clusteringalgorithmus mit weicher Clusterzugehörigkeit. Er findet die Parameter für gegebene Verteilungen (üblicherweise multivariate Normalverteilungen). Er löst das Henne-Ei Problem
  • Wenn man weiß wie genau die Wahrscheinlichkeitsverteilungen der Cluster parametrisiert sind ist es leicht die Daten den Clustern zuzuordnen.
  • Wenn man die Daten einem Cluster zuordnen kann, dann ist es leicht die Parameter der Wahrscheinlichkeitsverteilung zu schätzen.
Wenn man sowohl Clusterzugehörigkeit als auch die Parameter der Verteilung schätzen muss ist es schwer. Man kann "zufällig" die initialen Parameter wählen, dann die Zuordnung machen. Der EM-Algorithmus iteriert nach der initialisierung der Parameter:
  • Expectation: Schätze für jeden Datenpunkte die Clusterzugehörigkeit.
  • Maximization: Parameter der Cluster neu berechnen. Also für jeden Cluster $A$
    • $\mu_A = \frac{\sum_{i=1}^N w_{i, A} \cdot x_i}{\sum_{i=1}^N w_{i, A}}$
    • $\sigma_A^2 = \frac{\sum_{i=1}^N w_{i,A} (x_i + \mu_A)^2}{\sum_{i=1}^N w_{i,A}}$
    wobei $w_{i,A}$ die Wahrscheinlichkeit der Zugehörigkeit des Punktes $i$ zu Cluster $A$ ist.
Der EM-Algorithmus ist mit $k$-means verwandt. Siehe Mixture Models 1: the EM algorithm

Typische Fragestellungen:

  • Gegeben ist die Struktur eines Bayesschen Netzes: Wie lautet die Verteilung?
  • Dies wird üblicherweise mit dem EM-Algorithmus gelöst.

Anwendungsfälle:

  • Automatische Diagnose, gegeben die Symptome (Bayessches Netz)
  • Fahrzeugverfolgung: Vorhersage von Routen, welche die Fahrzeuge nehmen werden (Dynamisches Bayessches Netz)

Anmerkungen: Die Folien sind hier sehr gut! Insbesondere Folie 14-23 sollte man sich ansehen.

Es scheint folgende Beziehung zu gelten: HMMs, Kalman-Filter, Extended Kalman-Filter, Partikel Filter sind Beispiele für Bayes-Filter. Bayes-Filter sind Beispiele für dynamische Bayessche Netze.

Siehe auch:

  • Tracking Robots
  • Probabilistic Graphical Models

Probablistisch Relationale Modelle

Slides: 06_Probablistisch_Relationale_Modelle.pdf

Siehe auch:

Objektorientierte Probablistisch Relationales Modelle (OPRM)
Ein OPRM besteht nach [Schu15] aus
  • Eine Klassenmenge $\mathbf{C} = \{C_1, \dots, C_n\}$,
  • einer partiellen Ordnung über C, welche die Klassenhierarchie definiert,
  • einer Menge einfacher, nicht probabilisitscher Attribute $\Lambda_C = \{\lambda_1, \dots, \lambda_n \forall C \in \mathbf{C}\}$,
  • einer Menge beschreibender Attribute $\Delta_C = \{\delta_1, \dots, \delta_n\} \forall C \in \mathbf{C}$,
  • einer Menge komplexer Attribute $\Phi_C = \{\phi_1, \dots, \phi_n\} \forall C \in \mathbf{C}$. Die komplexen Attribute beschreiben funktionale Beziehungen zwischen Klassen.
Dieses Modell wurde in libDAI umgesetzt.

Gaussche Prozesse

Slides: 07_Gaussche_Prozesse.pdf

I suggest reading the first two chapters of the online book gaussianprocess.org before starting to read the slides.

See also:

Lineare Regression
Die lineare Regression ist ein Modell zur approximation von Datenpunkten $(x, y) \in \mathbb{R}^n \times \mathbb{R}$ durch eine lineare Funktion, d.h. einer Funktion der Form $f(x) = x^T \cdot w$. Dabei ist $w \in \mathbb{R}^n$.

Wenn man als Optimierungskriterium den quadratischen Abstand $$E(f, data) = \sum_{(x,y) \in data} (f(x) - y)^2$$ nimmt, dann ist eine optimale Lösung durch $$w = (X^T X)^{-1} X^T y$$ gegeben.

Siehe auch: Proof of when is $A=X^T X$ invertible? sowie Does a transformation + linear regression give the same regression as fitting a quadratic function?
Affine Regression
Die affine Regression ist ein Modell zur approximation von Datenpunkten $(x, y) \in \mathbb{R}^n \times \mathbb{R}$ durch eine affine Funktion, d.h. einer Funktion der Form $f(x) = x^T \cdot w + b$. Dabei ist $w \in \mathbb{R}^n, b \in \mathbb{R}$. Um das Problem auf ein lineares zu reduzieren kann man den Feature-Vektor $x$ durch ein konstantes Feature $x_0 = 1$ erweitern.
Korrelationskoeffizient
Der Korrelationskoeffizient $\kappa(X, Y) \in [-1, 1]$ ist ein Maß für den linearen Zusammenhang zwischen zwei Zufallsvariablen $X, Y$. Er ist definiert als $$\kappa(X, Y) := \frac{Cov(X, Y)}{\sigma(X) \cdot \sigma(Y)}$$
Gausscher Prozess (Kriging, Machine learning - Introduction to Gaussian processes by Nando De Freitas)
Gaussche Prozesse approximieren eine Funktion dadurch, dass sie an jedem Punkt eine Normalverteilung (Gauss-Verteilung) annehmen.

Siehe Gaussian process regression.

Deep Learning

Slides: 08_DeepLearning.pdf

Siehe auch:

Deep Belief Netz (DBN)
Ein Deep Belief Netz ist ein gerichtetes, azyklisches, probabilistisches graphisches Modell.
Restricted Boltzmann machine (RBM)
Siehe Neuronale Netze
Contrastive Divergence (CD, CD-$k$)
Siehe Neuronale Netze
Contrastive Wake-Sleep Algorithm (siehe The wake-sleep algorithm von Hinton - Lecture 13d aus "Neural Networks for Machine Learning")
Der Wake-Sleep Algorithmus ist ein Trainingsalgorithmus für gerichtete graphische Modelle wie Sigmoid Belief Networks. Er ist nicht für RBMs. Man hat im Grunde zwei Netzwerke mit der gleichen Topologie, jedoch ist die Richtung vertauscht: Das eine Netz stellt die Hypothese aus den Daten auf, das andere Netz geniert neue Daten aus einer gegebenen Hypothese. In der wake phase wird die Eingabe genutzt um die Hypothese zu erzeugen. In dieser Phase werden die Gewichte für das Generative Modell trainiert. Dieses soll die Aktivierung der vorhergehenden Schicht rekonstruieren. In der sleep phase wird das generative Modell genutzt um aus dem Modell samples zu erzeugen. Dann trainiert man die Gewichte des erkennenden Netzes (also vergleichbar mit der wake phase, nur anders rum).
Siehe A Fast Learning Algorithm for Deep Belief Nets

Probleme von Tiefen Netzen und wie man sie lösen kann:

  • Lange Trainingsdauer: GPUs / mehr Rechenpower / weniger Parameter durch Parameter sharing, z.B. in CNNs / TDNNs
  • Extrem viele gelabelte Trainingsdaten werden benötigt: Internet (z.B. Wikipedia, Soziale Netzwerke, Amazon Mechanical Turk) reduziert dieses Problem; Nutzen ungelabelter Daten durch SSL in Auto-Encodern
  • Lokale Minima
  • Overfitting: Regularisation

Siehe auch

  • MNIST Demo (Flash): Neuronales Netz welches Ziffern generiert
  • Geoffry Hinton: Deep Learning on YouTube, 2015. 43 minutes. (Topics: RBMs)

Convolutional Neural Networks

Slides: 09_ConvolutionalNeuralNetworks.pdf

Siehe auch: Neuronale Netze Vorlesung

Convolutional Neural Networks (CNNs)
CNNs sind neuronale Netze welche weight sharing einsetzen. Sie setzen eine diskrete Faltung um. Ein CNN muss mindestens einen Convolutional Layer haben. Dieser hat folgende Parameter:
  • Padding: None, Zero, Copy
  • Stride: $s \in \mathbb{N}_{> 0}$
  • Filter Size: $(x,y) \in \mathbb{N}^2$
  • Number of filters: How many filters should get learned?
Feature Map
Nach einem Convolutional Layer hat man die Ausgabe der Filter, welche auf die Eingabe angewandt wurden. Diese nennt man Feature Map. Für jeden Filter bekommt man eine Feature Map. Die Feature Maps sind wiederum Eingaben für die nächsten Schichten.
Pooling Layer
Ein pooling layer ist eine Schicht in einem CNN, welche Features zusammenfasst. Pooling Schichten haben folgende Parameter:
  • Größe: Typischerweise $3 \times 3$
  • Stride $s \in \mathbb{N}$: Typischerweise gleich der Größe des Pooling-Bereichs (also 3).
  • Art: max, mean
Typischerweise reduziert sie die Anzahl der Features, da typischerweise ein $s > 1$ gewählt wird.

Spiking Neural Nets

Slides: 10_SpikingNeuralNets.pdf

Spiking Neural Networks
Gepulste neuronale Netze versuchen natürliche neuronen realistisch abzubilden. Das Hodgkin-Huxley Neuronenmodell wurde bereits 1952 vorgestellt.
Hodgkin-Huxley Neuronenmodell
Das Hodgkin-Huxley Neuronenmodell modelliert die elektrochemischen Vorgänge innerhalb eines Neurons mit elektrischen Baugliedern. Dies resultiert in Differenzialgleichungen mit 4 Variablen (Kapazität der Membran, Widerstände der Ionenkanäle, Gleichgewichtspotentiale, Öffnung der Ionenkanäle). Das Modell ist realistisch, aber sehr komplex.
LIF Neuronenmodell (Leaky integrate and Fire)
Das LIF Neuronenmodell modelliert ein Neuron durch eine gewöhnliche Differentialgleichung erster Ordnung.
SRM Neuronenmodell (Spike Response Model)
Das SRM Neuronenmodell modelliert die Refraktionszeit. Das ist die Zeit, in der kein neues Aktionspotential aufgebaut werden kann. Das SRM ist ein rein phänomenologisches Modell, welches trotz der Einfachheit allgemeiner ist als das LIF-Modell.

Evaluation

Slides: 11_Evaluation.pdf

Für Klassifikation:

Konfusionsmatrix
Eine Konfusionsmatrix ist eine Tabelle, in welcher die Spalten angeben, welche Hypothese gemacht wurde (Testentscheid) und die Zeilen den wahren Wert angeben. So kann für beliebig viele Klassen gezeigt werden, wie gut der Klassifikator ist und welche Art der Verwechslung er macht.
Klassifikationsfehler
$\text{Klassifikationsfehler} = \frac{\text{Fehlerhafte Hypothesen}}{\text{Anzahl aller Beispiele}} \in [0, 1]$
Klassifikationsgüte
Klassifikationsgüte = 1 - Klassifikationsfehler
False Alarm Rate (FA, Falsch Positiv Rate, FPR)
Es sei FP die Anzahl der False Positive Testdaten, also der Testdaten für welche Positive vorhergesagt wurde, die aber negative sind. Weiter sei TN die Anzahl der True Negatives, also der Testdaten, für welche korrekterweise negative vorhergesagt wurde. Dann ist die FPR definiert als $$\text{FPR} := \frac{FP}{FP + TN} \in [0, 1]$$ Die FPR gibt also den Anteil an, wie viele der tatsächlich negativen fälschlicherweise als positiv erkannt wurden.
Miss-Rate (MR, Falsch Negativ Rate, FNR)
$$FNR := \frac{FN}{TP + FN} \in [0, 1]$$
Recall (True Positive Rate, TPR, Sensitivität)
$$TPR = \frac{TP}{TP + FN} = 1 - FNR \in [0, 1]$$ Der Recall gibt den Anteil der erkannten positiven aus allen positiven an. Sensitivität ist ein in der Medizin üblicher Begriff.
Precision (Genauigkeit)
$$Precision = \frac{TP}{TP + FP} \in [0, 1]$$ Die Precision gibt den Anteil der real positiven aus den als positiv erkannten an.
ROC-Graph (Receiver-Operator Curve)
Der ROC-Graph gibt für einen Klassifikator, bei dem man einen Parameter einstellen kann, den Fehler an. Die $x$-Achse ist dabei die FPR, die $y$-Achse die TPR.
Spezifität
Der Begriff der Spezifität ist in der Medizin üblich und ist definiert durch $$Spezifität = \frac{TN}{TN + FP} = 1 - FPR$$ Es ist eine Art recall für die negative Klasse. Im Beispiel eines medizinischen Tests wäre das der Anteil der Gesunden, bei denen tatsächlich auch die Diagnose "Gesund" gestellt wurde.
PRC-Graph (Precision-Recall-Graph)
Die $x$-Achse ist Recall, die $y$-Achse ist Precision.
F-Maß
$$F_\alpha = \frac{precision \cdot recall}{\alpha^2 \cdot precision + recall}$$

Alternative:

  • Aufstellen einer Kostenfunktion und optimieren nach Kosten.
  • Plotten der Anzahl der Trainingsdaten (\(x\)-Achse) und des Fehlers (\(y\)-Achse). Die Kurven sollten der Test-Fehler sowie der Trainingsfehler sein. Damit lässt sich abschätzen, ob mehr Trainingsdaten ohne eine Veränderung des Modells hilfreich sind.

Für Regression

Mittlerer Quadratischer Fehler (MSE, Mean Squared Error)
$$E(f, data) = \frac{1}{|data|} \sum_{(x, y) \in data} (f(x) - y)^2$$
Relativer Quadratischer Fehler
$$E(f, data) = \frac{\sum_{(x, y) \in data} (f(x) - y)^2}{\sum_{(x,y) \in data} (y - \mu)^2}$$
Mittlerer Absoluter Fehler
$$E(f, data) = \frac{1}{|data|} \sum_{(x, y) \in data} |f(x) - y|$$

Siehe auch

Prüfungsfragen

  • Was versteht man unter einer "Transductive SVM"?
    → Eine Transductive SVM ist eine SVM welche neben gelabelten Daten auch noch ungelabelte benutzt. Sie versucht die Trennebene durch eine Region geringer Dichte zu legen.
  • Wie lautet die Optimierungsformel der transductive SVM?
    → $$\text{minimize}_{w, b, y^*} \frac{1}{2} \|w\|^2$$ unter den Nebenbedingungen $$\forall i \in 1, \dots, n: y_i (w \cdot x_i - b) \geq 1$$ und $$\forall j \in 1, \dots, k: y_j^* (w \cdot x_j^* -b) \geq 1\text{ with }y_j^* \in \{-1, 1\}$$ Dabei sind $D^* = \{x_i^* | i = 1, \dots, k\}$ ungelabelte Daten.
  • Was macht man im Reinforcement Learning, wenn Aktionen länger dauern?
    → Options verwenden (TODO: Wie ändert sich die Value Iteration Formel nun bzgl. der Zeit?)
  • Warum heißen POMDPs "Partially Observable"?
    → Weil der Agent zwar Feedback über die Umgebung bekommt, aber nicht direkt erfährt in welchem Zustand er ist. Siehe Definition.
  • Welche Active Learning Techniken gibt es?
    → Query / Selective / Pool-based (vgl. Query-by-Committee)
  • Wie nennt man ein instanziiertes OPRM?
    → TODO (Skelett?)
  • Wie funktioniert aktives Lernen bei SVMs?
    → Bei SVMs gibt es die Dualität zwischen dem Feature-Space und dem Hypothesenraum. In dem Feature-Space stellen die Achsen $x_i$ die Features dar, Trainingsdaten Punkte sind und die SVM durch die Trennebene visualisiert wird. Im Hypothesenraum sind die Achsen $w_i$ zusammen der Normalenvektor der SVM, die verschiedenen Trennebenen der SVMs sind hier Punkte. Die Daten geben Bedingungen an die SVM vor, welche in diesem Raum als Hyperebenen dargestellt werden können. Der Margin ist in diesem Raum ein Kreis, der die Bedingungs-Hyperebenen berührt. Beim aktiven lernen versucht man den Version-Space im Inneren der Bedungungs-Hyperebenen so schnell zu verkleinern wie möglich.
  • Was versteht man unter Transduktivem Lernen?
    → Unter Transduktiver Inferenz versteht man das Schließen von Trainingsbeispielen direkt auf auf spezifische Testfälle.
  • Wie nennt man die Wahrscheinlichkeit des aktiellen Zustands in POMDPs?
    → Belief.

Literatur

Übungsbetrieb

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

Vorlesungsempfehlungen

Folgende Vorlesungen sind ähnlich:

Kontakt

Termine und Klausurablauf

Datum: Freitag, der 29.07.2016 von 12:30-13:30 Uhr
Ort: Hörsäle Hertz, Gr. HS und MTI
Zeit: 60 min
Übungsschein: gibt es nicht
Bonuspunkte: gibt es nicht
Ergebnisse: werden ca. 5 - 10 min. nach der mündlichen Prüfung gesagt
Erlaubte Hilfsmittel: keine

Published


by

Category

German posts

Tags

Contact