Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Systemy decyzyjne – 10. SVM: Maszyny wektorów podpieraja̧cych – MIM UW

Zagadnienia

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.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.