Linear separierbare Probleme

Nächste Seite: Feature Space Aufwärts: SVMs (Support Vector Machines) Vorherige Seite: Gute Generalisierung Inhalt

Unterabschnitte

Linear separierbare Probleme

Linear separierende Ebene mit Korridor

Wir können einen Vektorraum durch eine Hyperebene eine Dimension tiefer in zwei Teile teilen. Linear sparierbare Probleme lassen sich durch eine Hyperebene in zwei Klassen teilen. Eine solche Hyperebene läßt sich definieren durch

$\begin{displaymath}\{\vec{z}\,\vert(\vec{w}\cdot \vec{z})+b =0\}\end{displaymath}$

Die eine Halbebene ist dann definiert durch

$\begin{displaymath}\{\vec{z}\,\vert(\vec{w}\cdot \vec{z})+b >0\}\end{displaymath}$

die andere durch

$\begin{displaymath}\{\vec{z}\,\vert(\vec{w}\cdot \vec{z})+b <0\}\end{displaymath}$

Für viele separierbare Probleme können wir eine Hyperebene auf verschiedene Art und Weise erstellen

$\includegraphics[scale=0.5]{verschiedeneebenen.eps}$

Wir sehen jedoch, dass viele Ebenen nicht so klug separieren. Wenn wir gerade an einen Rand die Ebene legen, dann können leicht Muster auftauchen, die die Ebene überschreiten. Wir wollen deshalb eine Ebene mit einem Korridor drumherum erstellen

$\includegraphics[scale=0.5]{korridor.eps}$

Wir können $\vec{w}$ und

so einstellen, dass alle Punkte außerhalb des Korridors liegen und die Support Vectors genau auf der Grenze:

$\begin{displaymath}\min_{i=1\ldots l}\vert(\vec{w}\vec{x}_{i})+b\vert=1\end{displaymath}$

Seien $\vec{z_{1}}$ und $\vec{z_{2}}$ die Support Vectors, dann gilt

$\begin{displaymath}\begin{array}{c\vert l} &(\vec{w}\vec{z_{1}})+b=+1\\ -&(\vec... ...1\\ \hline &\vec{w}(\vec{z_{1}}-\vec{z_{2}})=2\\ \end {array}\end{displaymath}$

Wir normieren

$\begin{displaymath}\frac{\vec{w}}{\vert\vert\vec{w}\vert\vert}(\vec{z_{1}}-\vec{z_{2}})=\frac{2}{\vert\vert\vec{w}\vert\vert}\end{displaymath}$

und erhalten ein passendes $\vec{w}$

$\begin{displaymath}\frac{\vec{w}}{\vert\vert\vec{w}\vert\vert}(\vec{z_{1}}-\vec{z_{2}})-\frac{2}{\vert\vert\vec{w}\vert\vert}=0\end{displaymath}$

Decision Function

Unsere Entscheidungsfunktion ist nun

$\begin{displaymath}f_{\vec {w},b}=\underbrace {sgn}_{\mbox{Vorzeichen}}((\vec{w}\cdot\vec{x}_{i})+b)=y_{i}\end{displaymath}$

La Grange

Wir versuchen zwei Ziele zu erfüllen

gute Generalisierung (Extremum)

$\begin{displaymath}\frac{1}{2}\vert\vert\vec{w}\vert\vert^{2}\mbox{ minimieren}\end{displaymath}$
alle Beispiele richtig klassifizieren (Nebenbedingung)

$\begin{displaymath}y_{i}((\vec{w}\cdot\vec{x}_{i})+b)\geq 1\end{displaymath}$

Dies können wir mit dem La-Grange-Ansatz. Die La-Grange-Funktion

hat die Form

$\begin{displaymath}L(\vec{w},b,\vec{\alpha})=\underbrace{\frac{1}{2}\vert\vert w... ...(y_{i}((\vec{w}\cdot\vec{x}_{i})+b)-1)}_{\mbox{Nebenbedingung}}\end{displaymath}$

Nach Einsetzen und Auflösen erhalten wir die sogenannte Duale Form

$\begin{displaymath}D(\vec{\alpha})=\sum^{l}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{l}_{i,j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}(\vec{x}_{i}\cdot\vec{x}_{j})\end{displaymath}$

Die Decision Function wäre dann

$\begin{displaymath}f(\vec{z})=sgn\left(\sum^{l}_{i=1}\alpha_{i}y_{i}(\vec{z}\cdot\vec{x}_{i})+b \right)\end{displaymath}$

Nächste Seite: Feature Space Aufwärts: SVMs (Support Vector Machines) Vorherige Seite: Gute Generalisierung Inhalt