====== Support Vector Machine ======

Manchmal sauberer Ansatz um nicht-lineare Zusammenhänge zu lernen.

Betrachtung von Kostenfkt. bei y=1 und y=0. Stückweise Approximierung (2 Teile). 

$\text{cost}_0(z), \text{cost}_1(z)$

$$\min_\theta \frac{1}{m} \sum_{i=1}^m y^{(i)} \text{cost}_1(z) + (1-y^{(i)}) \text{cost}_0(z) + \frac{\lambda}{2m} \sum_{j=1}^n \theta_j^2\\

z=\theta^Tx^{(i)}$$

Vereinfacht (ohne $\frac{1}{m}$), und mit Umformung $A + \lambda B$ => $C A + B$ mit $C = 1 / \lambda$:
$$\min_\theta C \sum_{i=1}^m y^{(i)} \text{cost}_1(z) + (1-y^{(i)}) \text{cost}_0(z) + \frac{\lambda}{2} \sum_{j=1}^n \theta_j^2$$

===== Lineare Separierbarkeit =====

Large margin classifier

Bei großem C: Anfällig für Ausreißer.

===== Mathematische Sicht =====

Vector Inner Product

$u^T v$

$||u|| = \sqrt{u_1^2 + u_2^2}$

p = Länger der Projektion von v auf u.

$u^Tv = p * ||u|| = u_1 v_1 + u_2 v_2$

$\theta^T x^{(i)} = p^{(i)} ||\theta||$ mit $p^{(i)}$ als Projektion von $x^{(i)}$ auf Vektor $\theta$.

$p \in R$ positive oder negativ (abhängig von Winkel)


$\min_\theta 1/2 \sum_{j=1}^n \theta_j^2 = 1/2 ||\theta||^2$

Bei größeren $p^{(i)}$ können kleinere $||\theta||$ gewählt werden. $p^{(i)}$ Abstände Large Margin Classifier.

===== Kernel =====

Nicht-lineare Decision Boundary

Gegeben x, berechne neue Features abhängig von der Nähe zu Landmarks $l^{(1)}, l^{(2)}, l^{(3)}$.

Gegeben x: 
$$f_1 = \text{similarity}(x,l^{(1)}) = \exp(-\frac{||x-l^{(1)}||^2}{2 \sigma^2}) \\
f_2 = \text{similarity}(x,l^{(2)}) = \exp(-\frac{||x-l^{(2)}||^2}{2 \sigma^2}) \\ 
$$

Ähnlichkeitsfunktionen = Kernel $k(x,l^{(i)})$

Hier Gaussian Kernel.


Wenn $x \approx l^{(1)}$: $f_1 \approx 1$

Wenn $x$ weit entfernt von $l^{(1)}$: $f_1 \approx 0$


Anpassen von $\sigma$

===== Landmarks =====

Sage $y=1$ vorher wenn $\theta_0 + \theta_1 f_1 + \theta_2 f_2 + \theta_3 f_3 \geq 0$

Wie $l^{(1)}, l^{(2)}, l^{(3)}, ...$ wählen?

$l^{(1)} = x^{(1)}$ usw.

==== Feature Vector f ====

$f_1 = \text{similarity}(x,l^{(1)})$ usw.

Für $x^{(i)}$ muss entsprechend berechnet werden:

$$
f_1^{(i)} = \text{sim}(x^{(i)}, l^{(1)}) \\
f_2^{(i)} = \text{sim}(x^{(i)}, l^{(2)}) \\
\dots \\
f_m^{(i)} = \text{sim}(x^{(i)}, l^{(m)})
$$

Sage y=1 vorher, wenn $\theta^T f \geq 0$

Wie bekommt man $\theta$?

Durch Minimierung der Kostenfunktion, jetzt mit $\theta^T f^{(i)}$ anstelle von $\theta^T f^{(i)}$.

==== Parameterwahl ====

$C = \frac{1}{\lambda}$

  * Großes C: Niedriger Bias, hohe Varianz => Overfitting
  * Niedriges C: Hoher Bias, niedrige Varianz => Underfitting

$\sigma^2$

  * Groß: Features variieren sanfter => Hoher Bias, niedrige Varianz
  * Niedrig: Features varrieren abrupter => Niedriger Bias, hohe Varianz

===== Kernelwahl =====

  * Kein Kernel (linear Kernel): n groß, m klein
  * Gaussian Kernel: n klein, m groß
    * Implementierung der Ähnlichkeitsfunktion (bzw. Features $f_i$)
    * Feature Scaling vor Verwendung des Gaussian Kernel $||v||^2 = v_1^2 + v_2^2 + \dots + v_n^2$
    * Polynomial Kernels: Eher selten benutzt
    * Weitere

Manche Ähnlichkeitsfunktionen erzeugen keine gültigen Kernel. Diese müssen Mercer's Theorem erfüllen (aufgrund Optimierungen und Konvergenz).

===== Algowahl =====

  * Wenn n groß gegenüber m: Log Reg oder SVM ohne Kernel
  * Wenn n klein (1-1000) und m mittelgroß (10-10000): SVM mit Gaussian Kernel
  * Wenn n klein (1-1000) und m groß (50000+): Mehr Features + Log Reg oder SVM ohne Kernel