Dana jest próbka treningowa

0.5 0.58 \column

• Klasyfikatorem liniowym nazywamy funkcję

  fw,b⁢x=sgn⁢w⋅x+b

• Próbka D jest liniowo seperowana jeśli istnieje klasyfikator liniowy fw,b⁢ taki, że

  	w⋅xi+b≥+1, gdy ⁢yi=+1
  	w⋅xi+b<-1, gdy ⁢yi=-1

0.5 0.5 \column

• Uproszczony warunek:

  yi⁢w⋅xi+b≥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

0.5

• Niech H1, H2 będą brzegami marginesu;

• Powiniśmy oprzeć brzegi o punkty z próbki treningowej

• Te punkty nazywamy wektorami podpierającymi

• Równanie H1 i H2:

  	H1:	w⋅x+b=1
  	H2:	w⋅x+b=-1

0.5

Odległość między H1 a H2:

Maksymalizujemy d⁢H1,H2 lub minimalizujemy w2.

Zadanie LSVM Znaleźć w i b które minimalizują

przy ograniczeniach

Q: Jak rozwiązać tego typu zagadnienia?

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

• Znaleźć

  arg⁢maxu⁡c+dT⁢u+uT⁢R⁢u2

• przy założeniach:

  A1⁢u≤b1

• oraz

  A2⁢u=b2

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

• Rozwiązywanie zagadnienia LSVM ⇔ znalezienie punktu siodłowego wielomianu Lagrange'a:

  L⁢w,b,α=12⁢w⋅w-∑i=1nαi⁢xi⋅w-b⁢yi-1

  gdzie α=α1,…,αn jest wektorem nieujemnych współczynników Lagrange'a

• Punkt siodłowy = maksimum funkcji względem αi≥0 i minimum funkcji względem w i b.

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

• zerowanie się gradientu wzg. w, czyli

  w=∑i=1nyi⁢αi⁢xi

  (10.1)

• zerowanie się pochodnej wzg. b, czyli

  ∑i=1nαi⁢yi=0

  (10.2)

• spełnienie warunku:

  αi⁢xi⋅w0-b0⁢yi-1=0, for ⁢i=1,…,n

  (10.3)

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

• Znaleźć wektor α będący maksimum funkcji

  W⁢α=∑i=1nαi-12⁢∑i⁢j=1nαi⁢αj⁢yi⁢yj⁢xi⋅xj

  (10.4)

• przy ograniczeniach

  αi≥0,i=1,..,noraz∑i=1nαiyi=0

  (10.5)

Niech wektor α10,…,αn0 będzie rozwiązaniem maksymalizującym (4) przy ograniczeniach (5).

• Z (3) wynika, że jeśli xi nie jest wektorem podpierającym to αi0=0;

• Równania (4) i (5) odbywają się faktycznie tylko po wektorach podpierających.

• Hyperpłaszczyzna rozdzielająca ma postać w0⁢x-b0=0 gdzie

  w0=∑wektory podp.yi⁢αi0⁢xi⁢⁢b0=12⁢w0⋅x1+w0⋅x-1

  tu x1 i x-1 są dowolnymi wektorami podpierającymi z każdej z klas.

Ostateczna funkcja decyzyjna:

Problem

Wejście:

D=x1,y1,…,xn,yn; K: funkcja jądrowa.

Wyjście:

wektor α10,…,αn0 będący maksimum funkcji

W⁢α=∑i=1nαi-12⁢∑i⁢j=1nαi⁢αj⁢yi⁢yj⁢K⁢xi⋅xj

przy ograniczeniach

C≥αi≥0,i=1,..,noraz∑i=1nαiyi=0