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

Jupyter