Granice uogólnienia na SVM

11

Interesują mnie teoretyczne wyniki zdolności uogólniających maszyn wektorów podporowych, np. Granice prawdopodobieństwa błędu klasyfikacji i wymiaru Vapnika-Chervonenkisa (VC) tych maszyn. Jednak czytając literaturę, miałem wrażenie, że niektóre podobne powtarzające się wyniki różnią się nieznacznie w zależności od autora, szczególnie jeśli chodzi o warunki techniczne wymagane dla danego obowiązku.

W dalszej części przypomnę strukturę problemu SVM i stan 3 głównych wyników uogólnienia, które wielokrotnie odnajdywałem w takiej czy innej formie podam 3 główne odniesienia w całej prezentacji.

Ustawienie problemu :

Załóżmy, że mamy próbkę danych niezależnych i identycznie rozmieszczonych (iid) par (xi,yi)1in gdzie dla wszystkich i , xiRp i yi{1,1} . Konstruujemy maszynę wektorów nośnych (SVM), która maksymalizuje minimalny margines m między hiperpłaszczyzną oddzielającą zdefiniowaną przez {x:wx+b=0} ,wRp ibR , i najbliższy punkt spośródx1,,xn , aby oddzielić dwie klasy zdefiniowane przezy=1 iy=1 . Pozwalamy, aby SVM przyznał pewne błędy poprzez miękki margines, wprowadzając zmienne luzuξ1,,ξn ale dla uproszczenia notacji ignorujemy możliwość jądra. Parametry rozwiązaniaw ib są uzyskiwane przez rozwiązanie następującego wypukłego programu optymalizacji kwadratowej:

minw,b,ξ1,,ξn12w2+Ci=1nξis.t.:yi(wxi+b)1ξi,i{1,,n}ξi0,i{1,,n}

Interesuje nas możliwość uogólnienia tej maszyny.

Wymiar Vapnik-Chervonenkis VC :

Pierwszy wynik wynika z (Vapnik, 2000), w którym ogranicza wymiar VC oddzielającej hiperpłaszczyzny, twierdzenie 5.1. Niech R=maxxixi, mamy:

VCmin((Rm)2,p)+1

Ten wynik można ponownie znaleźć w (Burges, 1998), twierdzenie 6. Wydaje się jednak, że twierdzenie Burgesa jest bardziej restrykcyjne niż ten sam wynik Vapnika, ponieważ musi on zdefiniować specjalną kategorię klasyfikatorów, znaną jako klasyfikatory tolerujące odstępy do którego należy SVM , aby stwierdzić twierdzenie.

Ograniczenia prawdopodobieństwa błędów :

W (Vapnik, 2000) twierdzenie 5.2 na stronie 139 określa następujące ograniczenie możliwości generalizacji SVM:

E[Perror]1nE[min(p,nSV,(Rw)2)]

gdzie to liczba wektorów pomocniczych SVM. Wyniki te wydają się znaleźć ponownie odpowiednio w (Burges, 1998), równaniach (86) i (93). Ale znowu Burges wydaje się różnić od Vapnika, ponieważ oddziela komponenty w ramach powyższej funkcji minimum w różnych twierdzeniach, z różnymi warunkami.nSV

Kolejny wynik pojawiający się w (Vapnik, 2000), s. 133, jest następujący. Zakładając ponownie, że dla wszystkich , i pozwalając i , definiujemy jako równe:ixi2R2hVCϵ[0,1]ζ

ζ=4h(ln2nh+1)lnϵ4n

Definiujemy również jako liczbę błędnie sklasyfikowanych przykładów szkolenia przez SVM. Następnie z prawdopodobieństwem możemy stwierdzić, że prawdopodobieństwo, że przykładowy test nie zostanie poprawnie rozdzielony przez hiperpłaszczyznę -margin tj. SVM z marginesem ma granicę:nerror1ϵmm

Perrornerrorn+ζ2(1+1+4nerrornζ)

Jednak w (Hastie, Tibshirani i Friedman, 2009), s. 438 znaleziono bardzo podobny wynik:

ErrorTestζ

Wniosek :

Wydaje mi się, że między tymi wynikami istnieje pewien stopień konfliktu. Z drugiej strony dwa z tych odniesień, choć kanoniczne w literaturze SVM, zaczynają być nieco stare (1998 i 2000), szczególnie jeśli weźmiemy pod uwagę, że badania nad algorytmem SVM rozpoczęły się w połowie lat dziewięćdziesiątych.

Moje pytania to:

  • Czy wyniki te są nadal aktualne, czy też okazały się błędne?
  • Czy od tego czasu uzyskano ściślejsze granice przy stosunkowo luźnych warunkach? Jeśli tak, to kto i gdzie mogę je znaleźć?
  • Wreszcie, czy jest jakiś materiał referencyjny, który syntetyzuje główne wyniki uogólnienia dotyczące SVM?

Referencje :

Burges, JC (1998). „Samouczek na temat maszyn wektorowych pomocniczych do rozpoznawania wzorców”, Data Mining i Knowledge Discovery , 2: 121-167

Hastie, T., Tibshirani, R. and Friedman, J. (2009). Elementy uczenia statystycznego , wydanie drugie, Springer

Vapnik, VN (1998). Statystyczna teoria uczenia się , 1. wydanie, John Wiley & Sons

Vapnik, VN (1999). „Przegląd statystycznej teorii uczenia się”, Transakcje IEEE w sieciach neuronowych , 10 (5): 988–999

Vapnik, VN (2000). Natura statystycznej teorii uczenia się , wydanie drugie, Springer

Daneel Olivaw
źródło
odniesienie podsumowujące najnowsze granice ryzyka dla SVM: „Support Vector Machines” (Ingo Steinwart, Andreas Christmann, Springer 2008) .
zarejestrować się

Odpowiedzi:

3

Nie znam szczegółowo literatury, do której się odwołujesz, ale uważam, że wyczerpujące streszczenie granic uogólnienia, które powinny być aktualne, można znaleźć w Boucheron i in. (2004) (Link: https://www.researchgate.net/profile/Olivier_Bousquet/publication/238718428_Advanced_Lectures_on_Machine_Learning_ML_Summer_Schools_2003_Canberra_Australia_February_2-14_2003_Tubingen_Germany_August_4-16_2003_Revised_Lectures/links/02e7e52c5870850311000000/Advanced-Lectures-on-Machine-Learning-ML-Summer-Schools-2003- Canberra-Australia-luty-2-14-2003-Tybinga-Niemcy-sierpień-4-16-2003-Revised-Lectures.pdf # page = 176 )

Naszkicuję część SVM związaną z poniższym, pomijając szczegóły i dowody.

Przed opracowaniem konkretnie związanym z SVM, musimy zrozumieć, co starają się osiągnąć granice uogólnienia.

Najpierw załóżmy, że prawdziwe prawdopodobieństwo jest znane, wówczas najlepszym możliwym klasyfikatorem byłby klasyfikator Bayesa, tj. P(Y=+1|X=x)

g={+1  ifP(Y=1|X=x)>0.51  otherwise

Celem teorii uczenia statystycznego jest teraz znalezienie różnicy między klasyfikatorem klasy (np. SVM) i klasyfikator Bayesa, tj. Należy zauważyć, że jest oczekiwane utraty danych i jest najlepszym klasyfikatora w model klasy . Termin nazywa się błędem oszacowania i często jest fokusowany, ponieważ można go znacznie łatwiej ograniczyć niż błąd aproksymacji (drugi termin). Pominę również błąd przybliżenia tutaj.C

g^n=argmingCLn(g)
L(g^n)L(g)=L(g^n)L(gc)+L(gc)L(g).
L(g)=El(g(X),Y)gcCZ=:L(g)L(g^n)

Błąd oszacowania można dodatkowo rozłożyć za pomocą Teraz można to ograniczyć dwoma krokami:Z

Z=ZEZ+EZ.
  1. Związane przy użyciu nierówności McDiarmidZEZ

  2. Związane ze złożonością RademacheraEZRn(C)=EsupgC|1/ni=1nl(g(Xi),Yi)|

Używając nierówności McDiarmids można pokazać, że jeśli funkcja utraty mieści się w przedziale nie większym niż , krok pierwszy skutkuje granicą gdzie to poziom ufności. W drugim kroku możemy pokazać, że Jeśli masz dyskretną funkcję straty, tj. Nie-Lipschitz, taką jak 0-1 -tracenie, potrzebowałbyś Wymiaru VC do dalszego ograniczenia złożoności Rademachera. Jednak w przypadku funkcji L-lipschitz, takich jak utrata zawiasów, można to dodatkowo ograniczyć przez gdzieB

ZEZ2Bln(1/δ)2n,
δ
EZ2Rn(C),
Rn(C)λLR/n,

λoznacza regulizator. Ponieważ dla utraty zawiasu i (udowodnij przy nierówności Gauchy'ego-Schwartza), to jeszcze bardziej upraszcza. Na koniec, zestawiając wszystkie wyniki razem, możemy połączyć L=1B=1+λR
L(g^n)L(gc)2(1+λR)ln(1/δ)2n+4λLR/n
dkoehn
źródło