Zagadnienia

10.1 SVM: Maszyny wektorów podpieraja̧cych

10. SVM: Maszyny wektorów podpieraja̧cych

10.1. SVM: Maszyny wektorów podpieraja̧cych

10.1.1. Wprowadzenie

Dana jest próbka treningowa

$D=\{(\mathbf{x}_{1},y_{1}),...,(\mathbf{x}_{n},y_{n})\}\text{ gdzie $y_{i}\in\{-1,1\}$, $\mathbf{x}_{i}\in\Re^{p}$}$

\columns\column

0.5 0.58 \column

Klasyfikatorem liniowym nazywamy funkcję

$f_{{\mathbf{w},b}}(\mathbf{x})=\mathrm{sgn}(\mathbf{w}\cdot\mathbf{x}+b)$
Próbka $D$ jest liniowo seperowana jeśli istnieje klasyfikator liniowy $f_{{\mathbf{w},b}}(\ )$ taki, że

$\displaystyle\mathbf{w}\cdot\mathbf{x}_{i}+b\geq+1,\text{ gdy }y_{i}=+1$

$\displaystyle\mathbf{w}\cdot\mathbf{x}_{i}+b<-1,\text{ gdy }y_{i}=-1$

\columns\column

0.5 0.5 \column

Uproszczony warunek:

$y_{i}(\mathbf{w}\cdot\mathbf{x}_{i}+b)\geq 1,$

dla każdego $i$ .
Każda z tych linii dobrze seperuje punkty;
Która z nich jest najlepsza?

Margines = szerokość bezpiecznego obszaru po obu stronach hiperpłaszczyzny;
Margines jest wyznaczony przez 2 hiperpłaszczyzny.
Chcemy znaleźć klasyfikator z maksymalnym marginesem

\columns\column

0.5

Niech $H_{1}$ , $H_{2}$ będą brzegami marginesu;
Powiniśmy oprzeć brzegi o punkty z próbki treningowej
Te punkty nazywamy wektorami podpierającymi
Równanie $H_{1}$ i $H_{2}$ :

$\displaystyle H_{1}:$ $\displaystyle\mathbf{w}\cdot\mathbf{x}+b=1$

$\displaystyle H_{2}:$ $\displaystyle\mathbf{w}\cdot\mathbf{x}+b=-1$

\column

0.5

Odległość między $H_{1}$ a $H_{2}$ :

$d(H_{1},H_{2})=\cfrac{2}{||\mathbf{w}||}$

Maksymalizujemy $d(H_{1},H_{2})$ lub minimalizujemy $\cfrac{||\mathbf{w}||}{2}$ .

\block

Zadanie LSVM Znaleźć $\mathbf{w}$ i $b$ które minimalizują

$\frac{||\mathbf{w}||^{2}}{2}$

przy ograniczeniach

$y_{i}(\mathbf{w}\cdot\mathbf{x}_{i}+b)-1\geq 0;i=1,...,n$

Q: Jak rozwiązać tego typu zagadnienia?

A: Metodą gradientu?, symulowanego wyżrzania?, odwracanie macierzy? EM? Newton? PROGRAMOWANIE KWADRATOWE?

Znaleźć

$\arg\max _{{\mathbf{u}}}c+\mathbf{d}^{T}\mathbf{u}+\frac{\mathbf{u}^{T}R\mathbf{u}}{2}$
przy założeniach:

$A_{1}\mathbf{u}\leq\mathbf{b}_{1}$
oraz

$A_{2}\mathbf{u}=\mathbf{b}_{2}$

To zagadnienie jest dobrze zbadane i istnieją bardzo efektywne algorytmy rozwiązujące ten problem

Rozwiązywanie zagadnienia LSVM $\Leftrightarrow$ znalezienie punktu siodłowego wielomianu Lagrange'a:

$L(\mathbf{w},b,\alpha)=\frac{1}{2}(\mathbf{w}\cdot\mathbf{w})-\sum _{{i=1}}^{n}\alpha _{i}\left\{[(\mathbf{x}_{i}\cdot\mathbf{w})-b]y_{i}-1\right\}$

gdzie $\alpha=(\alpha _{1},...,\alpha _{n})$ jest wektorem nieujemnych współczynników Lagrange'a
Punkt siodłowy = maksimum funkcji względem $\alpha _{i}\geq 0$ i minimum funkcji względem $\mathbf{w}$ i $b$ .

Twierdzenie Karusha-Kuhna-Tuckera: warunkiem koniecznym istnienia punktu siodlowego jest

zerowanie się gradientu wzg. $\mathbf{w}$ , czyli

$\mathbf{w}=\sum _{{i=1}}^{n}y_{i}\alpha _{i}\mathbf{x}_{i}$ (10.1)
zerowanie się pochodnej wzg. $b$ , czyli

$\sum _{{i=1}}^{n}\alpha _{i}y_{i}=0$ (10.2)
spełnienie warunku:

$\alpha _{i}\left\{[(\mathbf{x}_{i}\cdot\mathbf{w}_{0})-b_{0}]y_{i}-1\right\}=0,\text{ for }i=1,...,n$ (10.3)

Po uwzględnieniu tych warunków (na istnienie punktu siodłowego) mamy nowy problem optymalizacyjny:

Znaleźć wektor $\alpha$ będący maksimum funkcji

$W(\alpha)=\sum _{{i=1}}^{n}\alpha _{i}-\frac{1}{2}\sum _{{ij=1}}^{n}\alpha _{i}\alpha _{j}y_{i}y_{j}(\mathbf{x}_{i}\cdot\mathbf{x}_{j})$ (10.4)
przy ograniczeniach

$\alpha _{i}\geq 0,i=1,..,n\quad oraz\quad\sum _{{i=1}}^{n}\alpha _{i}y_{i}=0$ (10.5)

\block

Niech wektor $(\alpha^{0}_{1},...,\alpha^{0}_{n})$ będzie rozwiązaniem maksymalizującym (4) przy ograniczeniach (5).

Z (3) wynika, że jeśli $\mathbf{x}_{i}$ nie jest wektorem podpierającym to $\alpha^{0}_{i}=0$ ;
Równania (4) i (5) odbywają się faktycznie tylko po wektorach podpierających.
Hyperpłaszczyzna rozdzielająca ma postać $\mathbf{w}_{0}\mathbf{x}-b_{0}=0$ gdzie

$\mathbf{w}_{0}=\sum _{{\text{wektory podp.}}}y_{i}\alpha _{i}^{0}\mathbf{x}_{i}\quad b_{0}=\frac{1}{2}[(\mathbf{w}_{0}\cdot\mathbf{x}^{{(1)}})+(\mathbf{w}_{0}\cdot\mathbf{x}^{{(-1)}})]$

tu $\mathbf{x}^{{(1)}}$ i $\mathbf{x}^{{(-1)}}$ są dowolnymi wektorami podpierającymi z każdej z klas.

\block

Ostateczna funkcja decyzyjna:

$f(\mathbf{x})=\mathrm{sgn}(\sum _{{\text{wektory podp.}}}y_{i}\alpha _{i}^{0}(\mathbf{x}_{i}\cdot\mathbf{x})+b_{0})$

(10.6)

10.1.2. Brak liniowej separowalności danych

10.1.2.1. Nieznaczna nieseparowalność

Założenie o separowalności klas jest nienaturalna;
Modyfikacja:

$\displaystyle\mathbf{w}\cdot\mathbf{x}_{i}+b\geq 1-\xi _{i},\text{ gdy }y_{i}=+1$

$\displaystyle\mathbf{w}\cdot\mathbf{x}_{i}+b\leq-1+\xi _{i},\text{ gdy }y_{i}=-1$

gdzie stałe $\xi _{i}$ spełniają warunki:

$\xi _{i}\geq 0,i=1,...,n.$
Zmodyfikowana funkcja do minimalizacji

$\frac{||\mathbf{w}||^{2}}{2}+C\sum _{{i=1}}^{{n}}\xi _{i}$

$C$ jest stałą “karą” za niespełnienie idealnych warunków.

\block

Ogólne zadanie SVM Znaleźć $\mathbf{w}$ i $b$ które minimalizują

$\frac{||\mathbf{w}||^{2}}{2}+C\sum _{{i=1}}^{{n}}\xi _{i}$

przy ograniczeniach

		$\displaystyle\mathbf{w}\cdot\mathbf{x}_{i}+b\geq 1-\xi _{i},\text{ gdy }y_{i}=+1$
		$\displaystyle\mathbf{w}\cdot\mathbf{x}_{i}+b\leq-1+\xi _{i},\text{ gdy }y_{i}=-1$
		$\displaystyle\xi _{i}\geq 0,i=1,...,n.$

Można pokazać, że zarówno i w tym przypadku, możemy sprowadzić do problemu

Znaleźć wektor $(\alpha^{0}_{1},...,\alpha _{n}^{0})$ będący maksimum funkcji

$W(\alpha)=\sum _{{i=1}}^{n}\alpha _{i}-\frac{1}{2}\sum _{{ij=1}}^{n}\alpha _{i}\alpha _{j}y_{i}y_{j}(\mathbf{x}_{i}\cdot\mathbf{x}_{j})$ (10.7)
przy ograniczeniach

$C\geq\alpha _{i}\geq 0,i=1,..,n\quad oraz\quad\sum _{{i=1}}^{n}\alpha _{i}y_{i}=0$ (10.8)

A następnie stosować funkcję decyzyjną: \block

$f(\mathbf{x})=\mathrm{sgn}\left(\sum _{{\text{wektory podp.}}}y_{i}\alpha _{i}^{0}(\mathbf{x}_{i}\cdot\mathbf{x})+b_{0}\right)$

(10.9)

10.1.2.2. Zmiana przetrzeni atrybutów

Przekształcimy dane do bogatszej przetrzeni cech:

$\phi:\Re^{p}\rightarrow\mathcal{F}\subseteq\Re^{N},\ \ N\gg p$
Wystarczy zamienić iloczyny skalarne $(\mathbf{x_{i}}\cdot\mathbf{x_{j}})$ we wszystkich wzorach na $(\mathbf{\phi(x_{i})}\cdot\mathbf{\phi(x_{j})})$

PROBLEM OBLICZENIOWY: czas wykonania iloczynu skalarnego $(\mathbf{\phi(x_{i})}\cdot\mathbf{\phi(x_{j})})$ wynosi $O(N^{2})$
TRIK: Kernel functions

$K((\mathbf{x_{i}}\cdot\mathbf{x_{j}}))=(\mathbf{\phi(x_{i})}\cdot\mathbf{\phi(x_{j})})$
Zmieniona funkcja:

$\displaystyle W(\alpha)$ $\displaystyle=\sum _{{i=1}}^{n}\alpha _{i}-\frac{1}{2}\sum _{{ij=1}}^{n}\alpha _{i}\alpha _{j}y_{i}y_{j}(\phi(\mathbf{x}_{i})\cdot\phi(\mathbf{x}_{j}))$

$\displaystyle=\sum _{{i=1}}^{n}\alpha _{i}-\frac{1}{2}\sum _{{ij=1}}^{n}\alpha _{i}\alpha _{j}y_{i}y_{j}K(\mathbf{x}_{i}\cdot\mathbf{x}_{j})$

10.1.3. Implementacja

\block

Problem

Wejście:

$D=\{(\mathbf{x}_{1},y_{1}),...,(\mathbf{x}_{n},y_{n})\}$ ; $K$ : funkcja jądrowa.

Wyjście:

wektor $(\alpha^{0}_{1},...,\alpha _{n}^{0})$ będący maksimum funkcji

$W(\alpha)=\sum _{{i=1}}^{n}\alpha _{i}-\frac{1}{2}\sum _{{ij=1}}^{n}\alpha _{i}\alpha _{j}y_{i}y_{j}K(\mathbf{x}_{i}\cdot\mathbf{x}_{j})$

przy ograniczeniach

$C\geq\alpha _{i}\geq 0,i=1,..,n\quad oraz\quad\sum _{{i=1}}^{n}\alpha _{i}y_{i}=0$

\block

$f(\mathbf{x})=\mathrm{sgn}\left(\sum _{{\text{wektory podp.}}}y_{i}\alpha _{i}^{0}K(\mathbf{x}_{i}\cdot\mathbf{x})+b_{0}\right)$

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

	$\displaystyle H_{1}:$	$\displaystyle\mathbf{w}\cdot\mathbf{x}+b=1$
	$\displaystyle H_{2}:$	$\displaystyle\mathbf{w}\cdot\mathbf{x}+b=-1$

	$\displaystyle W(\alpha)$	$\displaystyle=\sum _{{i=1}}^{n}\alpha _{i}-\frac{1}{2}\sum _{{ij=1}}^{n}\alpha _{i}\alpha _{j}y_{i}y_{j}(\phi(\mathbf{x}_{i})\cdot\phi(\mathbf{x}_{j}))$
		$\displaystyle=\sum _{{i=1}}^{n}\alpha _{i}-\frac{1}{2}\sum _{{ij=1}}^{n}\alpha _{i}\alpha _{j}y_{i}y_{j}K(\mathbf{x}_{i}\cdot\mathbf{x}_{j})$

Systemy decyzyjne

Zagadnienia

10. SVM: Maszyny wektorów podpieraja̧cych

10.1. SVM: Maszyny wektorów podpieraja̧cych

10.1.1. Wprowadzenie

10.1.2. Brak liniowej separowalności danych

10.1.2.1. Nieznaczna nieseparowalność

10.1.2.2. Zmiana przetrzeni atrybutów

10.1.3. Implementacja