Dana jest próbka treningowa
![]() |
0.5
0.58
\column
Klasyfikatorem liniowym nazywamy funkcję
![]() |
Próbka jest liniowo seperowana jeśli istnieje
klasyfikator liniowy
taki, że
![]() |
||
![]() |
0.5
0.5
\column
Uproszczony warunek:
![]() |
dla każdego .
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 ,
będą brzegami marginesu;
Powiniśmy oprzeć brzegi o punkty z próbki treningowej
Te punkty nazywamy wektorami podpierającymi
Równanie i
:
![]() |
![]() |
||
![]() |
![]() |
0.5
Odległość między a
:
![]() |
Maksymalizujemy lub minimalizujemy
.
Zadanie LSVM
Znaleźć i
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źć
![]() |
przy założeniach:
![]() |
oraz
![]() |
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:
![]() |
gdzie jest wektorem nieujemnych współczynników Lagrange'a
Punkt siodłowy = maksimum funkcji względem i minimum funkcji względem
i
.
Twierdzenie Karusha-Kuhna-Tuckera: warunkiem koniecznym istnienia punktu siodlowego jest
zerowanie się gradientu wzg. , czyli
![]() |
(10.1) |
zerowanie się pochodnej wzg. , czyli
![]() |
(10.2) |
spełnienie warunku:
![]() |
(10.3) |
Po uwzględnieniu tych warunków (na istnienie punktu siodłowego) mamy nowy problem optymalizacyjny:
Znaleźć wektor będący maksimum funkcji
![]() |
(10.4) |
przy ograniczeniach
![]() |
(10.5) |
Niech wektor będzie rozwiązaniem
maksymalizującym (4) przy ograniczeniach (5).
Z (3) wynika, że jeśli nie jest wektorem podpierającym to
;
Równania (4) i (5) odbywają się faktycznie tylko po wektorach podpierających.
Hyperpłaszczyzna rozdzielająca ma postać
gdzie
![]() |
tu i
są dowolnymi
wektorami podpierającymi z każdej z klas.
Ostateczna funkcja decyzyjna:
![]() |
(10.6) |
Założenie o separowalności klas jest nienaturalna;
Modyfikacja:
![]() |
|||
![]() |
gdzie stałe spełniają warunki:
![]() |
Zmodyfikowana funkcja do minimalizacji
![]() |
jest stałą “karą” za niespełnienie idealnych warunków.
Ogólne zadanie SVM
Znaleźć i
które minimalizują
![]() |
przy ograniczeniach
![]() |
|||
![]() |
|||
![]() |
Można pokazać, że zarówno i w tym przypadku, możemy sprowadzić do problemu
Znaleźć wektor będący maksimum funkcji
![]() |
(10.7) |
przy ograniczeniach
![]() |
(10.8) |
A następnie stosować funkcję decyzyjną: \block
![]() |
(10.9) |
Przekształcimy dane do bogatszej przetrzeni cech:
![]() |
Wystarczy zamienić iloczyny skalarne we wszystkich wzorach
na
PROBLEM OBLICZENIOWY: czas wykonania iloczynu skalarnego
wynosi
TRIK: Kernel functions
![]() |
Zmieniona funkcja:
![]() |
![]() |
||
![]() |
Problem
;
: funkcja jądrowa.
wektor będący maksimum funkcji
![]() |
przy ograniczeniach
![]() |
![]() |
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
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.