Ψ Die Informatikseite

Menü
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 $b$ 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
  1. gute Generalisierung (Extremum)

    \begin{displaymath}\frac{1}{2}\vert\vert\vec{w}\vert\vert^{2}\mbox{ minimieren}\end{displaymath}

  2. 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 $L$ 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}