Klassifikation

Binäre Klassifikation: $y \in \{0,1\}$

Beispiele

• Haus ist in der Stadt oder auf dem Land?
• Tumor ist bösartig oder nicht?
• Email ist Spam oder nicht?

Können wir das gut mit linearer Regression lösen?

Zwischenschritt: Perceptron

Wir wollen, dass $h_w(x) \in [0,1]$

\[ h_w(x) = {\color{red} g(}w \cdot \phi(x){\color{red})} \\\ \]

\[ g(z) = \begin{cases} 1 & \text{if } z \geq 0 \\ 0 & \text{else} \end{cases} \]

\[ g(z) = \begin{cases} 1 & \text{if } z \geq 0 \\ 0 & \text{else} \end{cases} \]

Beispiel

\[ \phi(x) = \left[ {\begin{array}{c} 1 \\ x \end{array}} \right] \quad w = \left[ {\begin{array}{c} 1 \\ -2 \end{array}} \right] \\[3mm] h(x) = 1 - 2 x \]

Die Punkte wo $h(x) = 0$ ist, nennen wir "decision boundary"
$w$ ist ein "Normalenvektor" zur decision boundary

Wenn wir mehr Dimensionen haben definiert der Normalenvektor eine (Hyper-) Ebene.

Der Normalenvektor zeigt in die Richtung, in der $h(x) > 0$ wird.

Zurück zum Perceptron:

Wir verwenden die gleiche Update Regel wie in der linearen Regression: \[ w \gets w - \eta (h_w(x) - y) \phi(x) \]

\[ h_w(x) - y = \begin{cases} 0 & \text{Korrekte Vorhersage} \\ 1 & \text{Falsch, } y = 0 \\ -1 & \text{Falsch, } y = 1 \end{cases} \]

Das Perceptron war eines der ersten (1958) implementierten Classifier Modelle

https://en.wikipedia.org/wiki/File:Mark_I_perceptron.jpeg

Heutzutage wird das Perceptron als Modell praktisch nicht mehr verwendet.

Logistische Regression

Wir nehmen eine andere Aktivierungsfunktion $g$: \[ h_w(x) = g(w \cdot \phi(x)) = \frac{1}{1+e^{- w \cdot \phi(x)}} \\ \]

$g(z) = \frac{1}{1+e^{- z}}$

"Sigmoid" oder "logistische Funktion"

Wir wollen direkt mehr Interpretierbarkeit von $h_w(x)$

\[ P(y=1 | x; w) = h_w(x) \\ P(y=0 | x; w) = 1-h_w(x) \]

Kombiniere zu \[ P(y | x; w) = h_w(x)^y \cdot (1-h_w(x))^{1-y} \]

$P(y | x; w)$ ist Bernoulli-verteilt

Analog zur linearen Regression: Maximiere Likelihood

\[ \mathcal{L}(w) = \prod_{(x,y) \in \mathcal{D}_\text{train}} h_w(x)^y \cdot (1-h_w(x))^{1-y} \]

\[ l(w) = \sum_{(x,y) \in \mathcal{D}_\text{train}} \log(h_w(x)^y) + \log((1-h_w(x))^{1-y})\\ \]

\[ = \sum_{(x,y) \in \mathcal{D}_\text{train}} y \log(h_w(x)) + (1-y)\log((1-h_w(x))) \]

Suche $w$, welches $l(w)$ maximiert.

Mit ein paar Tricks erhält man die Ableitung \[ \nabla l(w) = \sum_{(x,y) \in \mathcal{D}_\text{train}} (y - g(w \cdot \phi(x))) \phi(x) \]

Zur Erinnerung, bei linearer Regression galt:

\[ \nabla \operatorname{TrainLoss}(w) = \frac{1}{m} \sum_{(x,y)\in\mathcal{D}_\text{train}} 2 ({\color{red} \underbrace{w \cdot \phi(x)}_\text{prediction}} - {\color{blue} \underbrace{y}_\text{target}}) \phi(x) \]

Unser Update Schritt kann also gleich bleiben um die Likelihood zu maximieren: \[ w \gets w - \eta (\underbrace{g(w \cdot phi(x))}_{h_w(x)} - y) \phi(x) \]

Zur Erinnerung: Die Loss Funktion, die wir verwenden ist

\[ \operatorname{Loss}(x, y, w) = - (y \log(h_w(x)) + (1-y)\log(1 - h_w(x))) \]

(Cross Entropy)

Vorteil gegenüber Perceptron:
Wir können den Output vom Classifier als Wahrscheinlichkeit interpretieren.

Wie bei linearer Regression wird Gradient Descent (mit ordentlicher Lernrate) immer zum Optimum konvergieren

(Loss ist konvex)

Anders als bei linearer Regression haben wir hier keine Analytische Lösung.

Newtons method

Alternative zu Gradient Descent

Idee: Finde $x$ mit $\nabla f(x) = 0$

Nutze 2. Ableitung um 0 Stelle der 1. Ableitung zu finden

Vorteil: Braucht meistens viel weniger Iterationen als Gradient Descent

Nachteil: Braucht Inverse der 2. Ableitung
\[ w \gets w + H^{-1} \nabla h \]

Mit wenigen (< 1000) Features wahrscheinlich besser als Gradient Descent.

In sklearn: LogisticRegression

Wie bewerten wir eine Klassifikation?

Die Likelihood bzw. Cross Entropy lässt sich schwer interpretieren.

Confusion Matrix

Accuracy

\[ \frac{\text{TP+TN}}{\text{TP} + \text{TN} + \text{FP} + \text{FN}} \]

Welcher Anteil der Vorhersagen waren korrekt?

Recall
(True Positive Rate)

\[ \frac{\text{TP}}{\text{TP} + \text{FN}} \]

Welchen Anteil der echt positiven Beispiele haben wir gefunden?

Specificity
(True Negative Rate)

\[ \frac{\text{TN}}{\text{TN} + \text{FP}} \]

Welchen Anteil der echt negativen Beispiele haben wir gefunden?

Fall-out
(False Positive Rate)

\[ \frac{\text{FP}}{\text{TN} + \text{FP}} \]

Welchen Anteil der echt negativen Beispiele haben wir falsch vorhergesagt?

Precision

\[ \frac{\text{TP}}{\text{TP} + \text{FP}} \]

Welcher Anteil der positiven Vorhersagen waren korrekt?

Eine Metrik alleine kann täuschen

• Wir sagen immer "positiv" voraus: Recall ist 100%
• Wir sagen immer "negativ" voraus: Specificity ist 100% (und Precision ist undefiniert)
• Wenn 98% der Beispiele negativ sind, bekommen wir 98% Accuracy wenn wir immer "negativ" vorhersagen

Metriken brauchen Kontext: ELISA HIV Test

Test mit 99.9% Accuracy, 99.9% Recall und 99.9% Specificity.

https://de.wikipedia.org/w/index.php?title=Beurteilung_eines_bin%C3%A4ren_Klassifikators&oldid=223284084

Tradeoff zwischen

• Recall ($\frac{\text{TP}}{\text{TP} + \text{FN}}$)
• Specificity ($\frac{\text{TN}}{\text{TN} + \text{FP}}$) / Precision ($\frac{\text{TP}}{\text{TP} + \text{FP}}$)

$\text{F}_1$ Score

\[ \frac{2 \cdot \text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}} \]

Harmonisches Mittel aus Precision und Recall

Oft haben wir den Trade-off selber in der Hand.

Logistischen Regression: $h_w(x)$ nicht binär, sondern eine Wahrscheinlichkeit von 0 bis 1.

Wir müssen den Threshold bestimmen, ab dem wir "positiv" vorhersagen wollen.

• Hoher Threshold → Bessere Specificity
• Kleiner Threshold → Besserer Recall

Was wir wollen hängt vom Problem ab.

Beispiel: Spam Filter

Wenn eine Spam Email im Posteingang landet ist das weniger schlimm, als wenn eine richtige Email als Spam klassifiziert wird.

Specificity wichtiger als Recall

Receiver operating characteristic (ROC)

Für alle Thresholds plotte Recall gegen Fall-out.

https://commons.wikimedia.org/wiki/File:Roc_curve.svg

Beispiel (Wikipedia):

https://commons.wikimedia.org/wiki/File:Roccurves.png

AUROC
(Area under operating characteristic)

Berechne Fläche unter der ROC Kurve

• 1: Perfekter Classifier
• 0.5: Münzwurf
• 0: Jedes einzelne Beispiel falsch.

In sklearn: Metrics