Granice uogólnienia na SVM

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 $(x_i,y_i)_{1\leq i\leq n}$ gdzie dla wszystkich $i$ , $x_i \in \mathbb{R}^p$ i $y_i \in \{-1,1\}$ . Konstruujemy maszynę wektorów nośnych (SVM), która maksymalizuje minimalny margines $m^*$ między hiperpłaszczyzną oddzielającą zdefiniowaną przez $\{x : w \cdot x + b = 0\}$ , $w \in \mathbb{R}^p$ i $b \in \mathbb{R}$ , i najbliższy punkt spośród $x_1,\cdots,x_n$ , aby oddzielić dwie klasy zdefiniowane przez $y = -1$ i $y = 1$ . Pozwalamy, aby SVM przyznał pewne błędy poprzez miękki margines, wprowadzając zmienne luzu $\xi_1,\cdots,\xi_n$ $-$ ale dla uproszczenia notacji ignorujemy możliwość jądra. Parametry rozwiązania $w^*$ i $b^*$ są uzyskiwane przez rozwiązanie następującego wypukłego programu optymalizacji kwadratowej:

\begin{aligned} min_{w, b, ξ_{1}, \dots, ξ_{n}} & \frac{1}{2} ‖ w ‖^{2} + C \sum_{i = 1}^{n} ξ_{i} \\ s.t. : & y_{i} (w \cdot x_{i} + b) \geq 1 - ξ_{i} & , \forall i \in {1, \dots, n} \\ ξ_{i} \geq 0 & , \forall i \in {1, \dots, n} \end{aligned}

$\begin{align} \min_{w, \, b, \, \xi_1, \, \cdots, \, \xi_n} \; & \; \frac{1}{2}\|w\|^2 + C\sum_{i=1}^n\xi_i \\ \text{s.t.} \; : \; & \; y_i(w\cdot x_i+b) \geq 1 - \xi_i \, & , \, \forall \, i \in \{1,\cdots,n\} \\ & \; \xi_i \geq 0\, & , \, \forall \, i \in \{1,\cdots,n\} \end{align}$

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 = \max_{x_i} \|x_i\|$ , mamy:

V C \leq min ({(\frac{R}{m^{*}})}^{2}, p) + 1

$VC \leq \min \left( \left( \frac{R}{m^*}\right)^2, \, p\right) + 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 [P_{error}] \leq \frac{1}{n} E [min (p, n_{S V}, (R ‖ w ‖)^{2})]

$\mathbb{E}[P_{\text{error}}] \leq \frac{1}{n}\mathbb{E} \left[ \min\left(p,n_{SV},(R \, \|w\|)^2 \right) \right]$

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. $n_{SV}$

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: $i$ $\|x_i\|^2 \leq R^2$ $h \equiv VC$ $\epsilon \in [0,1]$ $\zeta$

ζ = 4 \frac{h (ln \frac{2 n}{h} + 1) - ln \frac{ϵ}{4}}{n}

$\zeta = 4 \frac{h\left( \text{ln}\frac{2n}{h} + 1\right) - \text{ln}\frac{\epsilon}{4}}{n}$

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ę: $n_{\text{error}}$ $1-\epsilon$ $m^*$ $-$ $m^*$ $-$

P_{error} \leq \frac{n_{error}}{n} + \frac{ζ}{2} (1 + \sqrt{1 + \frac{4 n_{error}}{n ζ}})

$P_{\text{error}} \leq \frac{n_{\text{error}}}{n} + \frac{\zeta}{2} \left( 1 + \sqrt{1+ \frac{4 \, n_{\text{error}}}{n \, \zeta}} \right)$

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

{Error}_{Test} \leq ζ

$\text{Error}_{\text{Test}} \leq \zeta$

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

machine-learning svm vc-dimension

— Daneel Olivaw
źródło

odniesienie podsumowujące najnowsze granice ryzyka dla SVM: „Support Vector Machines” (Ingo Steinwart, Andreas Christmann, Springer 2008) .

— zarejestrować się

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)$

\begin{aligned} g * = {\begin{cases} + 1 i f P (Y = 1 | X = x) > 0.5 \\ - 1 o t h e r w i s e \end{cases} \end{aligned}

$\begin{align} g* = \begin{cases} + 1 \ \ if P(Y = 1| X = x) > 0.5 \\ -1 \ \ otherwise \end{cases} \end{align}$

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$

\begin{aligned} {\hat{g}}_{n} = a r g min_{g \in C} L_{n} (g) \end{aligned}

$\begin{align} \hat{g}_n = arg \min_{g \in C} L_n(g) \end{align}$

\begin{aligned} L ({\hat{g}}_{n}) - L (g *) = L ({\hat{g}}_{n}) - L (g_{c}^{*}) + L (g_{c}^{*}) - L (g *) . \end{aligned}

$\begin{align} L(\hat{g}_n) - L(g*) = L(\hat{g}_n) - L(g^{*}_c) + L(g^{*}_c) - L(g*). \end{align}$

L (g) = E l (g (X), Y)

$L(g) = \mathbb{E}l(g(X),Y)$

g_{c}^{*}

$g^{*}_c$

C

$C$

Z =: L (g *) - L ({\hat{g}}_{n})

$Z =: L(g*) - L(\hat{g}_n)$

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

\begin{aligned} Z = Z - E Z + E Z . \end{aligned}

$\begin{align} Z = Z - \mathbb{E}Z + \mathbb{E}Z. \end{align}$

Związane przy użyciu nierówności McDiarmid $Z - \mathbb{E}Z$
Związane ze złożonością Rademachera $\mathbb{E}Z$ $R_n(C) = \mathbb{E}sup_{g \in C}|1/n \sum_{i=1}^{n} l(g(X_i),Y_i)|$

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 gdzie $B$

\begin{aligned} Z - E Z \leq 2 B \sqrt{\frac{l n (1 / δ)}{2 n}}, \end{aligned}

$\begin{align} Z - \mathbb{E}Z \leq 2 B \sqrt{\dfrac{ln(1/\delta)}{2n}}, \end{align}$

δ

$\delta$

\begin{aligned} E Z \leq 2 R_{n} (C), \end{aligned}

$\begin{align} \mathbb{E}Z \leq 2R_n(C), \end{align}$

\begin{aligned} R_{n} (C) \leq λ L R / \sqrt{n}, \end{aligned}

$\begin{align} R_n(C) \leq \lambda L R/\sqrt{n}, \end{align}$

λ

$\lambda$ 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 = 1

$L = 1$

B = 1 + λ R

$B = 1 + \lambda R$

\begin{aligned} L ({\hat{g}}_{n}) - L (g_{c}^{*}) \leq 2 (1 + λ R) \sqrt{\frac{l n (1 / δ)}{2 n}} + 4 λ L R / \sqrt{n} \end{aligned}

$\begin{align} L(\hat{g}_n) - L(g^{*}_c) \leq 2(1 + \lambda R) \sqrt{\dfrac{ln(1/\delta)}{2n}} + 4 \lambda L R/\sqrt{n} \end{align}$

— dkoehn
źródło