Biorąc pod uwagę zestaw punktów w przestrzeni dwuwymiarowej, w jaki sposób jedna decyzja projektowa może działać dla SVM?

Czy ktoś może mi wyjaśnić, jak należy zaprojektować funkcję decyzyjną SVM? Lub wskaż mi zasób, który omawia konkretny przykład.

EDYTOWAĆ

W poniższym przykładzie widzę, że równanie $X_2 = 1.5$ oddziela klasy z maksymalnym marginesem. Ale jak dopasować wagi i napisać równania dla hiperpłaszczyzn w następującej formie.

\begin{array}{ll} H_{1} : w_{0} + w_{1} x_{1} + w_{2} x_{2} \geq 1 & for Y_{i} = + 1 \\ H_{2} : w_{0} + w_{1} x_{1} + w_{2} x_{2} \leq - 1 & for Y_{i} = - 1. \end{array}

$\begin{array}{ll} H_1 : w_0+w_1x_1+w_2x_2 \ge 1 & \text{for}\; Y_i = +1 \\ H_2 : w_0+w_1x_1+w_2x_2 \le -1 & \text{for}\; Y_i = -1.\end{array}$

wprowadź opis zdjęcia tutaj

Staram się, aby podstawowa teoria znalazła się w przestrzeni 2D (ponieważ łatwiej jest ją wyobrazić), zanim zacznę myśleć o wyższych wymiarach.

Opracowałem rozwiązanie tego problemu. Czy ktoś może potwierdzić, czy jest to poprawne?

wektor wagowy to (0, -2), a W_0 to 3

\begin{array}{ll} H_{1} : 3 + 0 x_{1} - 2 x_{2} \geq 1 & for Y_{i} = + 1 \\ H_{2} : 3 + 0 x_{1} - 2 x_{2} \leq - 1 & for Y_{i} = - 1. \end{array}

$\begin{array}{ll} H_1 : 3+0x_1-2x_2 \ge 1 & \text{for}\; Y_i = +1 \\ H_2 : 3+0x_1 -2x_2 \le -1 & \text{for}\; Y_i = -1.\end{array}$

svm

— naresh
źródło

Jest to ilustracja z R tutaj , ale czuję, że pytanie jest bardziej na aspekcie algorytmicznego. W takim przypadku pomocne byłoby dodanie nieco więcej szczegółów na temat planowanej aplikacji lub dostępnego zasobu.

— chl

@chl Zaktualizowałem pytanie ze szczegółami

— naresh

Istnieją co najmniej dwa sposoby motywowania SVM, ale wybiorę tutaj prostszą drogę.

Teraz zapomnij na chwilę o wszystkim, co wiesz o SVM i skup się na problemie. Otrzymujesz zestaw punktów wraz z niektórymi etykietami ( $\mathcal{D} = \{(x^i_1, x^i_2, y_i)\}$ ), które pochodzą z . Teraz staramy się znaleźć linię w 2D, tak aby wszystkie punkty z etykietą spadły na jedną stronę linii, a wszystkie punkty z etykietą spadły na drugą stronę. $y_i$ $\{1, -1\}$ $1$ $-1$

Przede wszystkim sobie sprawę, że jest linia 2d i oznacza "z jednej strony" linii i oznacza „drugą stronę” linii. $w_0 + w_1x_1 + w_2x_2 = 0$ $w_0 + w_1x_1 + w_2x_2 > 0$ $w_0 + w_1x_1 + w_2x_2 < 0$

Z powyższego możemy wywnioskować, że chcemy jakiegoś wektora takiego, że dla wszystkich punktów z oraz $[w_0, w_1, w_2]$ $w_0 + w_1x^i_1 + w_2x^i_2 \geq 0$ $x^i$ $y_i = 1$ $w_0 + w_1x^i_1 + w_2x^i_2 < 0$ dla wszystkich punktów z [1]. $x^i$ $y_i = -1$

Załóżmy, że taka linia faktycznie istnieje, wtedy mogę zdefiniować klasyfikator w następujący sposób:

min | w_{0} | + | w_{1} | + | w_{2} | subject to : w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i} \geq 0, \forall x^{i} with y_{i} = 1 w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i} < 0, \forall x^{i} with y_{i} = - 1

$\min |w_0| + |w_1| + |w_2| \\ \text{subject to} : w_0 + w_1x^i_1 + w_2x^i_2 \geq 0, \forall x^i\text{ with }y_i = 1 \\ w_0 + w_1x^i_1 + w_2x^i_2 < 0, \forall x^i\text{ with }y_i = -1 \\$

Użyłem powyżej dowolnej funkcji celu, w tej chwili nie obchodzi nas, która funkcja celu jest używana. Chcemy tylko które spełnia nasze ograniczenia. Ponieważ założyliśmy, że istnieje linia, dzięki której możemy oddzielić dwie klasy tą linią, znajdziemy rozwiązanie powyższego problemu optymalizacji. $w$

Powyższe nie jest SVM, ale da ci klasyfikator :-). Jednak ten klasyfikator może nie być bardzo dobry. Ale jak zdefiniować dobrego klasyfikatora? Dobry klasyfikator to zwykle taki, który dobrze spisuje się na zestawie testowym. Najlepiej, by przejść przez wszystkie możliwe , jakoby rozdzielić dane treningowe i zobaczyć, który z nich ma również na danych testowych. Są jednak nieskończone , więc jest to całkiem beznadziejne. Zamiast tego rozważymy pewne heurystyki, aby zdefiniować dobry klasyfikator. Jedna heurystyka polega na tym, że linia oddzielająca dane będzie wystarczająco daleko od wszystkich punktów (tj. Zawsze będzie przerwa lub margines między punktami a linią). Najlepszy z nich to ten, który ma maksymalny margines. To jest wykorzystywane w SVM. $w$ $w$

Zamiast nalegać, aby dla wszystkich punktów z oraz dla wszystkich punktów $w_0 + w_1x^i_1 + w_2x^i_2 \geq 0$ $x^i$ $y_i = 1$ $w_0 + w_1x^i_1 + w_2x^i_2 < 0$ $x^i$ z , jeżeli twierdzą, że $y_i = -1$ dla wszystkich punktów z , a dla wszystkich punktów z $w_0 + w_1x^i_1 + w_2x^i_2 \geq 1$ $x^i$ $y_i = 1$ $w_0 + w_1x^i_1 + w_2x^i_2 \leq -1$ $x^i$ $y_i = -1$ , to tak naprawdę nalegamy, aby punkty były daleko od linii. Margines geometryczny odpowiadający temu wymaganiu wynosi . $\frac{1}{\|w\|_2}$

Otrzymujemy następujący problem optymalizacji,

max \frac{1}{‖ w ‖_{2}} subject to : w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i} \geq 1, \forall x^{i} with y_{i} = 1 w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i} \leq - 1, \forall x^{i} with y_{i} = - 1

$\max \frac{1}{\|w\|_2} \\ \text{subject to} : w_0 + w_1x^i_1 + w_2x^i_2 \geq 1, \forall x^i\text{ with }y_i = 1 \\ w_0 + w_1x^i_1 + w_2x^i_2 \leq -1, \forall x^i\text{ with }y_i = -1 \\$ Nieco zwięzłą formą pisania jest

Jest to w zasadzie podstawowy preparat SVM. Dla zwięzłości pominąłem sporo dyskusji. Mam nadzieję, że w dalszym ciągu udało mi się zrealizować większość tego pomysłu.

min ‖ w ‖_{2} subject to : y_{i} (w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i}) \geq 1, \forall i

$\min \|w\|_2 \\ \text{subject to} : y_i(w_0 + w_1x^i_1 + w_2x^i_2) \geq 1, \forall i$

Skrypt CVX, aby rozwiązać przykładowy problem:

A = [1 2 1; 3 2 1; 2 3 1; 3 3 1; 1 1 1; 2 0 1; 2 1 1; 3 1 1];
b = ones(8, 1);
y = [-1; -1; -1; -1; 1; 1; 1; 1];
Y = repmat(y, 1, 3);
cvx_begin
variable w(3)
minimize norm(w)
subject to
(Y.*A)*w >= b
cvx_end

Dodatek - marża geometryczna

$w$ $y_i(w_0 + w_1x_1 + w_2x_2) \geq 1$ $y_i(w_0 + w^Tx) \geq 1$ $\geq 1$

$x_+$ $w^Tx_+ + w_0 = 1$ $x_-$ $w^Tx_- + w_0 = -1$ . Now, the distance between $x_+$ and $x_-$ will be the shortest when $x_+ - x_-$ is perpendicular to the hyperplane.

Now, with all the above information we will try to find $\|x_+ - x_-\|_2$ which is the geometric margin.

w^{T} x_{+} + w_{0} = 1

$w^Tx_+ + w_0 = 1$

w^{T} x_{-} + w_{0} = - 1

$w^Tx_- + w_0 = -1$

w^{T} (x_{+} - x_{-}) = 2

$w^T(x_+ - x_-) = 2$

| w^{T} (x_{+} - x_{-}) | = 2

$|w^T(x_+ - x_-)| = 2$

‖ w ‖_{2} ‖ x_{+} - x_{-} ‖_{2} = 2

$\|w\|_2\|x_+ - x_-\|_2 = 2$

‖ x_{+} - x_{-} ‖_{2} = \frac{2}{‖ w ‖_{2}}

$\|x_+ - x_-\|_2 = \frac{2}{\|w\|_2}$

[1] It doesn't actually matter which side you choose for $1$ and $-1$ . You just have to stay consistent with whatever you choose.

— TenaliRaman
źródło

@naresh Yeap, solving this is in cvx gave me the exact same solution that you have

w = [0, - 2, 3]

$w = [0, -2, 3]$ .

— TenaliRaman

@entropy thanks I have fixed the typo. I will add the geometric margin explanation.

— TenaliRaman

@entropy I have updated the answer with the geometric margin explanation.

— TenaliRaman

@entropy

w^{T} x

$w^{T}x$ is a hyperplane passing through origin. To cover the space of all linear equations you need the bias term. Think of points residing in 2D and let us say that you are trying to find a line that separates these points. However these points all lie in the first quadrant. Now one can arrange these points such that they are separable but not by any line that passes through the origin. However, a line with a proper bias can do it.

— TenaliRaman

@entropy Having said the above, you might have realized by now that if you properly rotate and shift the points, even a line passing through the origin should be able to separate the classes. However, usually finding this right rotation and shift is not easy, compared to just learning the bias term.

— TenaliRaman