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$$

Large margin classifier

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

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.

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$

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.

$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)}$.

$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

• 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).

• 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