108

Jak działa maszyna wektorów nośnych (SVM) i co ją odróżnia od innych klasyfikatorów liniowych, takich jak liniowy perceptron , liniowa analiza dyskryminacyjna lub regresja logistyczna ? *

(* Myślę o podstawowych motywach algorytmu, strategiach optymalizacji, możliwościach generalizacji i złożoności w czasie wykonywania )

— tdc
źródło

4

Zobacz także: stats.stackexchange.com/questions/3947/…

patrz także stats.stackexchange.com/questions/80398/…

126

Maszyny wektorów pomocniczych skupiają się tylko na punktach, które najtrudniej odróżnić, podczas gdy inni klasyfikatorzy zwracają uwagę na wszystkie punkty.

Intuicyjne podejście oparte na maszynie wektora nośnego jest takie, że jeśli klasyfikator jest dobry w najtrudniejszych porównaniach (punkty B i A, które znajdują się najbliżej siebie na ryc. 2), to klasyfikator będzie jeszcze lepszy w łatwych porównaniach ( porównywanie punktów B i A, które są daleko od siebie).

Perceptrony i inne klasyfikatory:

Perceptrony buduje się, biorąc jeden punkt na raz i odpowiednio dostosowując linię podziału. Gdy tylko wszystkie punkty zostaną rozdzielone, algorytm perceptronu zatrzymuje się. Ale może się zatrzymać wszędzie. Rysunek 1 pokazuje, że istnieje szereg różnych linii podziału, które oddzielają dane. Kryteria zatrzymania perceptronu są proste: „rozdziel punkty i przestań poprawiać linię, gdy uzyskasz 100% separacji”. Perceptron nie ma wyraźnego polecenia znalezienia najlepszej linii podziału. Model regresji logistycznej i liniowe modele dyskryminacyjne są zbudowane podobnie jak perceptrony.

Najlepsza linia podziału maksymalizuje odległość między punktami B najbliższymi A i punktami A najbliższymi B. W tym celu nie trzeba patrzeć na wszystkie punkty. W rzeczywistości uwzględnienie informacji zwrotnych z punktów, które są daleko, może nieco zahaczyć linię, jak pokazano poniżej.

wprowadź opis zdjęcia tutaj

Obsługa maszyn wektorowych:

W przeciwieństwie do innych klasyfikatorów, maszyna wektora pomocniczego jest wyraźnie zalecana, aby znaleźć najlepszą linię podziału. W jaki sposób? Maszyna wektora podporowego szuka najbliższych punktów (rysunek 2), które nazywa „wektorami podporowymi” (nazwa „maszyna wektora podporowego” wynika z faktu, że punkty są jak wektory i że najlepsza linia „zależy od” lub jest „obsługiwany przez” najbliższe punkty).

Po znalezieniu najbliższych punktów SVM rysuje linię łączącą je (patrz linia oznaczona „w” na rysunku 2). Rysuje tę linię łączącą, odejmując wektor (punkt A - punkt B). Maszyna wektora nośnego następnie deklaruje najlepszą linię oddzielającą jako linię, która przecina - i jest prostopadła do - linii łączącej.

Maszyna wektora podporowego jest lepsza, ponieważ kiedy otrzymasz nową próbkę (nowe punkty), utworzysz już linię, która utrzymuje B i A tak daleko od siebie, jak to możliwe, a więc jest mniej prawdopodobne, że jedna się rozleje linia na terytorium drugiej osoby.

wprowadź opis zdjęcia tutaj

Uważam się za ucznia wizualnego i przez długi czas walczyłem z intuicją stojącą za maszynami wektorów wsparcia. Artykuł Duality and Geometry in SVM Classifiers w końcu pomógł mi dostrzec światło; stąd mam obrazy.

— Ryan Zotti
źródło

4

+1 od innego wizualnego ucznia! Dla czytelnika chciałbym zauważyć, że te granice widoczne na powyższym rysunku oparte są na zestawie danych, który został już przekształcony. Nie surowy zestaw danych.

— Kingz

Czytając svm przez ponad dwa lata, dzisiaj zrozumiałem, w jaki sposób identyfikowana jest linia separacji i kilka innych rzeczy. Dzięki za czystą odpowiedź.

— user123

53

Odpowiedź Ryana Zottiego wyjaśnia motywację maksymalizacji granic decyzyjnych, odpowiedź Carlosdc daje pewne podobieństwa i różnice w stosunku do innych klasyfikatorów. Podaję w tej odpowiedzi krótki matematyczny przegląd tego, w jaki sposób SVM są szkolone i używane.

Notacje

$y,\, b$ $\mathbf{w},\, \mathbf{x}$ $W$ $\mathbf{w^T}$ $\mathbf{w}$ $\|\mathbf{w}\| = \mathbf{w}^T\mathbf{w}$

Pozwolić:

$\mathbf{x}$ być wektorem cech (tj. wejściem SVM). , gdzie jest wymiarem wektora cechy. $\mathbf{x} \in \mathbb{R}^n$ $n$
$y$ będzie klasą (tzn. wyjściem SVM). , tzn. zadanie klasyfikacji jest binarne. $y \in \{ -1,1\}$
$\mathbf{w}$ i są parametry SVM: musimy nauczyć się je za pomocą zestawu treningowego. $b$
$(\mathbf{x}^{(i)}, y^{(i)})$ jest próbką w zestawie danych. Załóżmy, że mamy w zestawie treningowym próbek. $i^ {\text {th}}$ $N$

Przy można reprezentować granice decyzji SVM w następujący sposób: $n=2$

Klasa jest określana w następujący sposób: $y$

y^{(i)} = {\begin{cases} - 1 & if w^{T} x^{(i)} + b \leq - 1 \\ 1 & if w^{T} x^{(i)} + b \geq 1 \end{cases}

$y^{(i)}=\left\{ \begin{array}{ll} -1 &\text{ if } \mathbf{w^T}\mathbf{x}^{(i)}+b \leq -1 \\ 1 &\text{ if } \mathbf{w^T}\mathbf{x}^{(i)}+b \ge 1 \\ \end{array} \right.$

które można bardziej zwięźle zapisać jako . $y^{(i)} (\mathbf{w^T}\mathbf{x}^{(i)}+b) \ge 1$

Cel

SVM ma na celu spełnienie dwóch wymagań:

SVM powinien maksymalizować odległość między dwiema granicami decyzyjnymi. Matematycznie oznacza to, że chcemy zmaksymalizować odległość między hiperpłaszczyzną zdefiniowaną przez a hiperpłaszczyzną zdefiniowaną przez . Odległość ta jest równa . Oznacza to, że chcemy rozwiązać . Równie dobrze chcemy . $\mathbf{w^T}\mathbf{x}+b = -1$ $\mathbf{w^T}\mathbf{x}+b = 1$ $\frac{2}{\|\mathbf{w}\|}$ $\underset{\mathbf{w}}{\operatorname{max}} \frac{2}{\|\mathbf{w}\|}$ $\underset{\mathbf{w}}{\operatorname{min}} \frac{\|\mathbf{w}\|}{2}$
SVM powinien również poprawnie sklasyfikować wszystkie , co oznacza $\mathbf{x}^{(i)}$ $y^{(i)} (\mathbf{w^T}\mathbf{x}^{(i)}+b) \ge 1, \forall i \in \{1,\dots,N\}$

Co prowadzi nas do następującego kwadratowego problemu optymalizacji:

\begin{aligned} min_{w, b} & \frac{‖ w ‖}{2}, \\ s . t . & y^{(i)} (w^{T} x^{(i)} + b) \geq 1 & \forall i \in {1, \dots, N} \end{aligned}

$\begin{align} \min_{\mathbf{w},b}\quad &\frac{\|\mathbf{w}\|}{2}, \\ s.t.\quad&y^{(i)} (\mathbf{w^T}\mathbf{x}^{(i)}+b) \ge 1 &\forall i \in \{1,\dots,N\} \end{align}$

Jest to SVM z twardym marginesem , ponieważ ten kwadratowy problem optymalizacji dopuszcza rozwiązanie, jeśli dane można rozdzielić liniowo.

Ograniczenia można złagodzić, wprowadzając tak zwane zmienne luzu . Zauważ, że każda próbka zestawu treningowego ma swoją własną zmienną luzu. To daje nam następujący kwadratowy problem optymalizacji: $\xi^{(i)}$

\begin{aligned} min_{w, b} & \frac{‖ w ‖}{2} + C \sum_{i = 1}^{N} ξ^{(i)}, \\ s . t . & y^{(i)} (w^{T} 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_{\mathbf{w},b}\quad &\frac{\|\mathbf{w}\|}{2}+ C \sum_{i=1}^{N} \xi^{(i)}, \\ s.t.\quad&y^{(i)} (\mathbf{w^T}\mathbf{x}^{(i)}+b) \ge 1 - \xi^{(i)},&\forall i \in \{1,\dots,N\} \\ \quad&\xi^{(i)}\ge0, &\forall i \in \{1,\dots,N\} \end{align}$

Jest to SVM z miękkim marginesem . jest hiperparametrem zwanym karą za błąd . ( Jaki jest wpływ C na SVM z jądrem liniowym? I jaki zakres wyszukiwania dla określenia optymalnych parametrów SVM? ). $C$

Można dodać jeszcze większą elastyczność, wprowadzając funkcję która odwzorowuje oryginalną przestrzeń cech na przestrzeń cech wyższego wymiaru. Pozwala to na nieliniowe granice decyzyjne. Kwadratyczny problem optymalizacji staje się: $\phi$

\begin{aligned} min_{w, b} & \frac{‖ w ‖}{2} + C \sum_{i = 1}^{N} ξ^{(i)}, \\ s . t . & y^{(i)} (w^{T} ϕ (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_{\mathbf{w},b}\quad &\frac{\|\mathbf{w}\|}{2}+ C \sum_{i=1}^{N} \xi^{(i)}, \\ s.t.\quad&y^{(i)} (\mathbf{w^T}\phi \left(\mathbf{x}^{(i)}\right)+b) \ge 1 - \xi^{(i)},&\forall i \in \{1,\dots,N\} \\ \quad&\xi^{(i)}\ge0, &\forall i \in \{1,\dots,N\} \end{align}$

Optymalizacja

Kwadratyczny problem optymalizacji można przekształcić w inny problem optymalizacji zwany podwójnym problemem Lagrangian (poprzedni problem nazywa się pierwotnym ):

\begin{aligned} max_{α} & min_{w, b} \frac{‖ w ‖}{2} + C \sum_{i = 1}^{N} α^{(i)} (1 - w^{T} ϕ (x^{(i)}) + b)), \\ s . t . & 0 \leq α^{(i)} \leq C, & \forall i \in {1, \dots, N} \end{aligned}

$\begin{align} \max_{\mathbf{\alpha}} \quad &\min_{\mathbf{w},b} \frac{\|\mathbf{w}\|}{2}+ C \sum_{i=1}^{N} \alpha^{(i)} \left(1-\mathbf{w^T}\phi \left(\mathbf{x}^{(i)}\right)+b)\right), \\ s.t. \quad&0 \leq \alpha^{(i)} \leq C, &\forall i \in \{1,\dots,N\} \end{align}$

Ten problem optymalizacji można uprościć (ustawiając niektóre gradienty na ) na: $0$

\begin{aligned} max_{α} & \sum_{i = 1}^{N} α^{(i)} - \sum_{i = 1}^{N} \sum_{j = 1}^{N} (y^{(i)} α^{(i)} ϕ {(x^{(i)})}^{T} ϕ (x^{(j)}) y^{(j)} α^{(j)}), \\ s . t . & 0 \leq α^{(i)} \leq C, & \forall i \in {1, \dots, N} \end{aligned}

$\begin{align} \max_{\mathbf{\alpha}} \quad & \sum_{i=1}^{N} \alpha^{(i)} - \sum_{i=1}^{N}\sum_{j=1}^{N} \left( y^{(i)}\alpha^{(i)}\phi\left(\mathbf{x}^{(i)}\right)^T \phi\left(\mathbf{x}^{(j)}\right) y^{(j)}\alpha^{(j)} \right), \\ s.t. \quad&0 \leq \alpha^{(i)} \leq C, &\forall i \in \{1,\dots,N\} \end{align}$

$\mathbf{w}$ nie pojawia się jako (zgodnie z twierdzeniem o reprezentatorze ). $\mathbf{w}=\sum_{i =1}^{N}\alpha^{(i)}y^{(i)}\phi\left(x^{(i)}\right)$

Dlatego uczymy się za pomocą zestawu szkoleniowego. $\alpha^{(i)}$ $(\mathbf{x}^{(i)}, y^{(i)})$

(FYI: Po co zawracać sobie głowę podwójnym problemem przy dopasowywaniu SVM? Krótka odpowiedź: szybsze obliczenia + pozwala na użycie sztuczki jądra, chociaż istnieją pewne dobre metody trenowania SVM w pierwotnej postaci, np. Patrz {1})

Dokonanie prognozy

Po nauczeniu się można przewidzieć klasę nowej próbki za pomocą wektora cech w następujący sposób: $\alpha^{(i)}$ $\mathbf{x}^{\text {test}}$

\begin{aligned} y^{test} & = sign (w^{T} ϕ (x^{test}) + b) \\ = sign (\sum_{i = 1}^{N} α^{(i)} y^{(i)} ϕ {(x^{(i)})}^{T} ϕ (x^{test}) + b) \end{aligned}

$\begin{align*} y^{\text {test}}&=\text {sign}\left(\mathbf{w^T}\phi\left(\mathbf{x}^{\text {test}}\right)+b\right) \\ &= \text {sign}\left(\sum_{i =1}^{N}\alpha^{(i)}y^{(i)}\phi\left(x^{(i)}\right)^T\phi\left(\mathbf{x}^{\text {test}}\right)+b \right) \end{align*}$

Podsumowanie może wydawać się przytłaczające, ponieważ oznacza, że trzeba sumować wszystkie próbki treningowe, ale ogromna większość ma wartość (zobacz Dlaczego są Mnożniki Lagrange'a rzadkie dla SVM? ), Więc w praktyce nie stanowi to problemu. (zauważ, że można konstruować specjalne przypadki, w których wszystkie ) iff to wektor wsparcia . Powyższa ilustracja ma 3 wektory pomocnicze. $\sum_{i =1}^{N}$ $\alpha^{(i)}$ $0$ $\alpha^{{(i)}} > 0$ $\alpha^{{(i)}}=0$ $x^{{(i)}}$

Sztuczka jądra

Można zauważyć, że problem optymalizacji używa tylko w produkcie wewnętrznym . Funkcja odwzorowująca do produktu wewnętrznego jest nazywany jądro , aka funkcji jądra, często oznaczany przez . $\phi\left(\mathbf{x}^{(i)}\right)$ $\phi\left(\mathbf{x}^{(i)}\right)^T \phi\left(\mathbf{x}^{(j)}\right)$ $\left(\mathbf{x}^{(i)},\mathbf{x}^{(j)}\right)$ $\phi\left(\mathbf{x}^{(i)}\right)^T \phi\left(\mathbf{x}^{(j)}\right)$ $k$

Można wybrać aby produkt wewnętrzny był wydajny w obliczeniach. Pozwala to na użycie potencjalnie wysokiej przestrzeni funkcji przy niskich kosztach obliczeniowych. To się nazywa sztuczka jądra . Aby funkcja jądra była poprawna , tzn. Możliwa do użycia z trikiem jądra, powinna spełniać dwie kluczowe właściwości . Istnieje wiele funkcji jądra do wyboru . Na marginesie, sztuczka jądra może być zastosowana do innych modeli uczenia maszynowego , w którym to przypadku są one nazywane jądrem . $k$

Idąc dalej

Kilka interesujących kontroli jakości SVM:

Inne linki:

Maszyna wektorowa obsługująca najmniejsze kwadraty

Bibliografia:

{1} Chapelle, Olivier. „Trenowanie maszyny wektora podporowego w pierwotnej postaci”. Obliczenia neuronowe 19, nie. 5 (2007): 1155–1178. https://scholar.google.com/scholar?cluster=469291847682573606&hl=pl&as_sdt=0,22 ; http://www.chapelle.cc/olivier/pub/neco07.pdf

— Franck Dernoncourt
źródło

2

Cześć Franck, wielkie dzięki za odpowiedź. Czy mógłbyś wyjaśnić, dlaczego wektor jest ortogonalny do hiperpłaszczyzny generowanej przez SVM? Jak obliczyłeś odległość między dwiema granicami decyzyjnymi, która ma być równa

w

$w$

\frac{2}{‖ w ‖}

$\frac{2}{\lVert w \rVert}$

— tosik

3

Oprócz tej świetnej odpowiedzi, chcę polecić ten film, który omawia matematykę stojącą za SVM, a szczególnie wyjaśnia pytanie skomentowane przez @tosik youtube.com/watch?v=_PwhiWxHK8o

— Nikolas Rieble

Bardzo miła odpowiedź. Tylko jedna uwaga na temat tej części: iff to wektor wsparcia . W celu klasyfikacji sumowanie efektywnie dotyczy wektorów pomocniczych (tj. ).

α^{(i)} = 0

$\alpha^{{(i)}}=0$

x^{(i)}

$x^{{(i)}}$

α^{(i)} \geq 0

$\alpha^{{(i)}} \ge 0$

— 989

13

Skupię się na podobieństwach i różnicach między innymi klasyfikatorami:

Z perceptronu: SVM wykorzystuje utratę zawiasów i regulację L2, perceptron wykorzystuje utratę perceptronu i mógłby użyć wczesnego zatrzymania (lub innych technik) do regularyzacji, tak naprawdę nie ma terminu regularyzacji w perceptronie. Ponieważ nie ma terminu regularyzacji, perceptron musi być przetrenowany, dlatego możliwości generalizacji mogą być dowolnie złe. Optymalizacja odbywa się za pomocą stochastycznego spadku, dlatego jest bardzo szybka. Pozytywną stroną tego artykułu jest to, że wykonując wczesne zatrzymanie z nieco zmodyfikowaną funkcją utraty, wydajność może być na równi z SVM.
Z regresji logistycznej: regresja logistyczna używa terminu straty logistycznej i może wykorzystywać regularyzację L1 lub L2. Możesz myśleć o regresji logistycznej jako o dyskryminującym bracie generatywnego naiwnego Bayesa.
Z LDA: LDA można również postrzegać jako algorytm generatywny, który zakłada, że funkcje gęstości prawdopodobieństwa (p (x | y = 0) i p (x | y = 1) są normalnie rozłożone. Jest to idealne, gdy dane są w fakt jest normalnie dystrybuowany. Ma jednak tę wadę, że „szkolenie” wymaga inwersji macierzy, która może być duża (gdy masz wiele funkcji). W przypadku homocedastyczności LDA staje się QDA, co jest optymalne dla Bayesa dla normalnie dystrybuowanych danych. Oznacza to, że jeśli założenia są spełnione, że tak naprawdę nie można zrobić nic lepszego.

W czasie wykonywania (czas testu), gdy model został przeszkolony, złożoność wszystkich tych metod jest taka sama, jest to iloczyn kropkowy między hiperpłaszczyzną znalezionej procedury szkolenia a punktem danych.

— carlosdc
źródło

1

Ponieważ wydajesz się bardzo kompetentny w SVM, pozwól, że wyjaśnię ci moje wątpliwości: kiedy znajdziemy najlepszą oddzielającą hiperpłaszczyznę, do czego ją wykorzystujemy? Możemy zdefiniować SVM jako metodę, która po pierwsze wybiera najlepszą hiperpłaszczyznę do prawidłowej klasyfikacji punktów danych, a po drugie używa tej hiperpłaszczyzny do przecinania nowych punktów danych w dwóch klasach. Dobrze? (Mam wątpliwości co do drugiej części)

— DavideChicco.it

1

@ DavideChicco.it Tak, możemy użyć funkcji wskaźnika do klasyfikacji nowych danych, co jest często głównym celem klasyfikatora. (Nie wierz mi jednak na słowo, jestem nowy w tym wszystkim).

— keyser

12

Technika opiera się na narysowaniu linii granicznej decyzji, pozostawiając wystarczający margines dla pierwszych pozytywnych i negatywnych przykładów, jak to możliwe:

Jak na powyższej ilustracji, jeśli wybierzemy wektor ortogonalny taki, że , możemy ustalić kryterium decyzyjne dla dowolnego nieznanego przykładu który zostanie skatalogowany jako pozytywny z postaci: $\lVert w \rVert=1$ $\mathbf u$

w \cdot u \geq C

$\color{blue}{\mathbf w} \cdot {\mathbf u} \geq C$

odpowiadające wartości, która umieściłaby rzut poza linią decyzyjną na środku ulicy. Zauważ, że . $\color{blue}{\mathbf w} \cdot {\mathbf u} = {\mathbf u} \cdot \color{blue}{\mathbf w}$

Równoważnym warunkiem dla próbki dodatniej byłoby:

\begin{matrix} (1) & w \cdot u + b \geq 0 \end{matrix}

$\color{blue}{\mathbf w}\cdot \mathbf u + b \geq 0 \tag 1$

z $C = - b.$

Potrzebujemy i aby mieć regułę decyzyjną i aby się tam dostać, potrzebujemy ograniczeń . $b$ $\color{blue}{\mathbf w}$

Pierwsze ograniczenie , że będą nakładać się, że dla dowolnej pozytywnej próbki , ; a dla próbek ujemnych . W granicy podziału lub hiperpłaszczyźnie ( medianie ) wartość wynosiłaby , podczas gdy wartości w rynnach wyniosłyby i : $\mathbf x_+,$ $\color{blue}{\mathbf w}\cdot \mathbf x_+ + b \geq 1$ $\color{blue}{\mathbf w}\cdot \mathbf x_- + b \leq -1$ $0$ $1$ $-1$

Wektor jest wektorem wag , podczas gdy to odchylenie . $\bf w$ $b$

Aby połączyć te dwie nierówności razem, możemy wprowadzić zmienną , aby dla pozytywnych przykładów, i jeśli przykłady są negatywne, i podsumować $y_i$ $y_i=+1$ $y_i=-1$

y_{i} (x_{i} \cdot w + b) - 1 \geq 0.

$y_i (x_i\cdot \color{blue}{\mathbf w} + b) -1\geq 0.$

Ustalamy więc, że musi to być większa od zera, ale jeśli przykład znajduje się na hiperpłaszczyznach („rynnach”), które maksymalizują margines separacji między hiperpłaszczyzną decyzyjną a wierzchołkami wektorów podporowych, w tym przypadku liniami), następnie:

\begin{matrix} (2) & y_{i} (x_{i} \cdot w + b) - 1 = 0 \end{matrix}

$y_i \,(x_i\cdot \color{blue}{\mathbf w} + b) -1 = 0\tag 2$

Zauważ, że jest to równoważne z wymaganiem, aby $y_i \,(x_i\cdot \color{blue}{\mathbf w} + b) = 1.$

Drugie ograniczenie : odległość hiperpłaszczyzny decyzji do wierzchołków wektorów nośnych zostanie zmaksymalizowana. Innymi słowy margines separacji („ulica”) zostanie zmaksymalizowany:

Zakładając wektor jednostkowy prostopadły do granicy decyzyjnej, , iloczynem kropki z różnicą między dwoma „graniczącymi” przykładami plus i minus jest szerokość „ulicy” : $\mathbf w$

width = (x_{+} - x_{-}) \cdot \frac{w}{‖ w ‖}

$\text{width}= (x_+ \,{\bf -}\, x_-) \cdot \frac{w}{\lVert w \rVert}$

Na równaniu powyżej i znajdują się w rynnie (na hiperpłaszczyznach maksymalizujących separację). Dlatego dla pozytywnego przykładu: lub ; i dla negatywnego przykładu: . Tak więc przeformułowanie szerokości ulicy: $x_+$ $x_-$ $({\mathbf x_i}\cdot \color{blue}{\mathbf w} + b) -1 = 0$ ${\mathbf x_+}\cdot \color{blue}{\mathbf w} = 1 - b$ ${\mathbf x_-}\cdot \color{blue}{\mathbf w} = -1 - b$

\begin{aligned} width & = (x_{+} - x_{-}) \cdot \frac{w}{‖ w ‖} \\ = \frac{x_{+} \cdot w - x_{-} \cdot w}{‖ w ‖} \\ = \frac{1 - b - (- 1 - b)}{‖ w ‖} \\ (3) & = \frac{2}{‖ w ‖} \end{aligned}

$\begin{align}\text{width}&=(x_+ \,{\bf -}\, x_-) \cdot \frac{w}{\lVert w \rVert}\\[1.5ex] &= \frac{x_+\cdot w \,{\bf -}\, x_-\cdot w}{\lVert w \rVert}\\[1.5ex] &=\frac{1-b-(-1-b)}{\lVert w \rVert}\\[1.5ex] &= \frac{2}{\lVert w \rVert}\tag 3 \end{align}$

Teraz musimy zmaksymalizować szerokość ulicy - tzn. zminimalizować lub zminimalizować: $\frac{2}{\lVert w \rVert},$ $\lVert w \rVert$

\begin{matrix} (4) & \frac{1}{2} ‖ w ‖^{2} \end{matrix}

$\frac{1}{2}\;\lVert w \rVert^2 \tag 4$

co jest matematycznie wygodne.

Więc chcemy:

Zminimalizuj z ograniczeniem: $\lVert x\rVert^2$
$y_i(\mathbf w \cdot \mathbf x_i + b )-1=0$

Ponieważ chcemy zminimalizować to wyrażenie w oparciu o pewne ograniczenia, potrzebujemy mnożnika Lagrange'a (wracając do równań 2 i 4):

\begin{matrix} (5) & L = \frac{1}{2} ‖ w ‖^{2} - \sum λ_{i} [y_{i} (x_{i} \cdot w + b) - 1] \end{matrix}

$\mathscr{L} = \frac{1}{2} \lVert \mathbf w \rVert^2 - \sum \lambda_i \Big[y_i \, \left( \mathbf x_i\cdot \color{blue}{\mathbf w} + b \right) -1\Big]\tag 5$

Różnicowanie,

\frac{\partial L}{\partial w} = w - \sum λ_{i} y_{i} x_{i} = 0

$\frac{\partial \mathscr{L}}{\partial \color{blue}{\mathbf w} }= \color{blue}{\mathbf w} - \sum \lambda_i \; y_i \; \mathbf x_i = 0$ .

W związku z tym,

\begin{matrix} (6) & w = \sum λ_{i} y_{i} x_{i} \end{matrix}

$\color{blue}{\mathbf w} = \sum \lambda_i \; y_i \; \mathbf x_i\tag 6$

I różnicowanie w odniesieniu do $b:$

\frac{\partial L}{\partial b} = - \sum λ_{i} y_{i} = 0,

$\frac{\partial \mathscr{L}}{\partial b}=-\sum \lambda_i y_i = 0,$

co oznacza, że mamy iloczyn sumy zerowej mnożników i etykiet:

\begin{matrix} (7) & \sum λ_{i} y_{i} = 0 \end{matrix}

$\sum \lambda_i \, y_i = 0\tag 7$

Podłączając równanie Eq (6) z powrotem do Eq (5),

L = \frac{1}{2} (\sum λ_{i} y_{i} x_{i}) (\sum λ_{j} y_{j} x_{j}) - (\sum λ_{i} y_{i} x_{i}) \cdot (\sum λ_{j} y_{j} x_{j}) - \sum λ_{i} y_{i} b + \sum λ_{i}

$\mathscr{L} = \frac{1}{2} \color{purple}{\left(\sum \lambda_i y_i \mathbf x_i \right) \,\left(\sum \lambda_j y_j \mathbf x_j \right)}- \color{green}{\left(\sum \lambda_i y_i \mathbf x_i\right)\cdot \left(\sum \lambda_j y_j \mathbf x_j \right)} - \sum \lambda_i y_i b +\sum \lambda_i$

Przedostatni termin wynosi zero zgodnie z równaniem Eq (7).

W związku z tym,

\begin{matrix} (8) & L = \sum λ_{i} - \frac{1}{2} \sum_{i} \sum_{j} λ_{i} λ_{j} y_{i} y_{j} x_{i} \cdot x_{j} \end{matrix}

$\mathscr{L} = \sum \lambda_i - \frac{1}{2}\displaystyle \sum_i \sum_j \lambda_i \lambda_j\,\, y_i y_j \,\, \mathbf x_i \cdot \mathbf x_j\tag 8$

Eq (8) jest ostatnim Lagrangianem.

Dlatego optymalizacja zależy od iloczynu kropek par przykładów.

Wracając do „reguły decyzyjnej” w równaniu (1) powyżej i używając równania (6):

\begin{matrix} (9) & \sum λ_{i} y_{i} x_{i} \cdot u + b \geq 0 \end{matrix}

$\sum\; \lambda_i \; y_i \; \mathbf x_i\cdot \mathbf u + b \geq 0\tag 9$

będzie ostateczną regułą decyzyjną dla nowego wektora $\mathbf u.$

— Antoni Parellada
źródło

Nic oryginalnego ... Tylko moje notatki na bardziej podstawowym poziomie. Zasadniczo z tego filmu z MIT z moimi własnymi ilustracjami. W przypadku błędów daj mi znać. Aby uzyskać wnikliwe odpowiedzi i dalsze szczegóły, przejdź do poziomu eksperta (post Francka i inni).

— Antoni Parellada,

Jak obliczyć b ?

— mike

1

@ mike gdzie jest zbiorem wskaźników wektorów pomocniczychMożesz go znaleźć tutaj .

b = y_{s} - \sum_{m \in S} α_{m} y_{m} x_{m} \cdot x_{s}

$b= y_s -\displaystyle \sum_{m\in S} \alpha_m y_m \mathbf{x}_m\cdot \mathbf {x}_s$

S

$S$

(α_{i} > 0) .

$(\alpha_i > 0).$

— Antoni Parellada,

@AntoniParellada niesamowita odpowiedź Bardzo dziękuję Antoni - ale czy nie brakuje ci części dotyczącej problemu podwójnego i warunków KTT?

— Xavier Bourret Sicotte

@XavierBourretSicotte Przez pewien czas nie będę w stanie nad tym pracować. Zastanów się, czy nie napisać alternatywnej odpowiedzi dotyczącej tych kwestii, a jeśli tak, to daj mi znać, że jestem tego świadomy i mogę go głosować.

— Antoni Parellada

3

Kilka komentarzy na temat warunków dualności i KTT

Pierwotny problem

Pobierając z postu @ Antoni pomiędzy równaniami i , przypomnij sobie, że nasz pierwotny lub pierwotny problem optymalizacji ma postać: $(4)$ $(5)$

\begin{aligned} min_{w, b} f (w, b) & = min_{w, b} \frac{1}{2} | | w | |^{2} \\ s . t . g_{i} (w, b) & = - y^{(i)} (w^{T} x^{(i)} + b) + 1 = 0 \end{aligned}

$\begin{aligned} \min_{w, b} f(w,b) & = \min_{w, b} \ \frac{1}{2} ||w||^2 \\ s.t. \ \ g_i(w,b) &= - y^{(i)} (w^T x^{(i)} + b) + 1 = 0 \end{aligned}$

Metoda Lagrange'a

Metoda mnożników Lagrange'a pozwala nam przekształcić ograniczony problem optymalizacji w nieograniczoną jedną z następujących form:

L (w, b, α) = \frac{1}{2} | | w | |^{2} - \sum_{i}^{m} α_{i} [y^{(i)} (w^{T} x^{(i)} + b) - 1]

$\mathcal{L}(w, b, \alpha) = \frac{1}{2} ||w||^2 - \sum_i^m \alpha_i [y^{(i)} (w^T x^{(i)} + b) - 1]$

Gdzie nazywa się Lagrangian, a nazywa się mnożnikami Lagrangian . $\mathcal{L}(w, b, \alpha)$ $\alpha_i$

Nasz pierwotny problem optymalizacji z Lagrangianem wygląda następująco: (zauważ, że użycie , nie jest najbardziej rygorystyczne, ponieważ powinniśmy również używać i tutaj ...) $min$ $max$ $\inf$ $\sup$

min_{w, b} (max_{α} L (w, b, α))

$\min_{w,b} \left( \max_\alpha \mathcal{L}(w, b, \alpha)\right)$

Podwójny problem

To, co @Antoni i prof. Patrick Winston zrobili w swoim wyprowadzeniu, zakłada, że funkcja optymalizacji i ograniczenia spełniają pewne warunki techniczne, dzięki czemu możemy wykonać następujące czynności:

min_{w, b} (max_{α} L (w, b, α)) = max_{α} (min_{w, b} L (w, b, α))

$\min_{w,b} \left( \max_\alpha \mathcal{L}(w, b, \alpha)\right) = \max_\alpha \left( \min_{w,b} \mathcal{L}(w, b, \alpha)\right)$

To pozwala nam wziąć częściowe pochodne w odniesieniu do i , równe zero, a następnie podłączyć wyniki z powrotem do pierwotnego równania Lagrangiana, generując w ten sposób ekwiwalent problem podwójnej optymalizacji formy $\mathcal{L}(w, b, \alpha)$ $w$ $b$

\begin{aligned} max_{α} min_{w, b} L (w, b, α) \\ max_{α} \sum_{i}^{m} α_{i} - \frac{1}{2} \sum_{i, j}^{m} y^{(i)} y^{(j)} α_{i} α_{j} < x^{(i)} x^{(j)} > \\ s . t . α_{i} \geq 0 \\ s . t . \sum_{i}^{m} α_{i} y^{(i)} = 0 \end{aligned}

$\begin{aligned} &\max_{\alpha} \min_{w,b} \mathcal{L}(w,b,\alpha) \\ & \max_{\alpha} \sum_i^m \alpha_i - \frac{1}{2} \sum_{i,j}^m y^{(i)}y^{(j)} \alpha_i \alpha_j <x^{(i)} x^{(j)}> \\ & s.t. \ \alpha_i \geq 0 \\ & s.t. \ \sum_i^m \alpha_i y^{(i)} = 0 \end{aligned}$

Dualność i KTT

Bez wchodzenia w nadmierną matematykę, warunki te są połączeniem warunków dualności i Karush Kuhn Tucker (KTT) i pozwalają nam rozwiązać podwójny problem zamiast pierwotnego , zapewniając jednocześnie optymalne rozwiązanie. W naszym przypadku warunki są następujące:

Pierwotne funkcje celu i ograniczenia nierówności muszą być wypukłe
Funkcja ograniczenia równości musi być afiniczna
Ograniczenia muszą być ściśle wykonalne

Następnie istnieją które są rozwiązaniami pierwotnych i podwójnych problemów. Ponadto parametry spełniają poniższe warunki KTT: $w^*, \alpha^*$ $w^*, \alpha^*$

\begin{aligned} \frac{\partial}{\partial w_{i}} L (w^{*}, α^{*}, β^{*}) = 0 & (A) \\ \frac{\partial}{\partial β_{i}} L (w^{*}, α^{*}, β^{*}) = 0 & (B) \\ α_{i}^{*} g_{i} (w^{*}) = 0 & (C) \\ g_{i} (w^{*}) \leq 0 & (D) \\ α_{i}^{*} \geq 0 & (E) \end{aligned}

$\begin{aligned} &\frac{\partial}{\partial w_i} \mathcal{L}(w^*, \alpha^*, \beta^*) = 0 &(A) \\ &\frac{\partial}{\partial \beta_i} \mathcal{L}(w^*, \alpha^*, \beta^*) = 0 &(B) \\ &\alpha_i^* g_i(w^*) = 0 &(C) \\ &g_i(w^*) \leq 0 &(D) \\ &\alpha_i^* \geq 0 &(E) \end{aligned}$

Ponadto, jeśli niektóre spełniają rozwiązania KTT, są one również rozwiązaniem pierwotnego i podwójnego problemu. $w^*, \alpha^*$

Powyższe równanie ma szczególne znaczenie i nazywa się warunkiem podwójnej komplementarności . To implikuje, że jeśli to co oznacza, że ograniczenie jest aktywne, tzn. ono równość, a nie nierówność. Jest to wyjaśnienie równania w pochodnej Antoniego, w którym ograniczenie nierówności przekształca się w ograniczenie równości. $(C)$ $\alpha_i^* > 0$ $g_i(w^*) = 0$ $g_i(w) \leq 0$ $(2)$

Intuicyjny, ale nieformalny schemat

Źródła

Andrew Ng 1 i 2
MIT

— Xavier Bourret Sicotte
źródło

2

Dziękuję Ci bardzo. Czytam go szybko i wracam do niego później, mając więcej czasu, ale brzmi świetnie i dotyka brakujących punktów w mojej odpowiedzi.