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_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}$$

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+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}$$

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 { 1 , - 1 } . Teraz staramy się znaleźć linię w 2D, tak aby wszystkie punkty z etykietą 1 spadły na jedną stronę linii, a wszystkie punkty z etykietą - 1 spadły na drugą stronę.$y_i$$\{1, -1\}$$1$$-1$

Przede wszystkim sobie sprawę, że jest linia 2d i w 0 + w 1 x 1 + w 2 x 2 > 0 oznacza "z jednej strony" linii i wagowo 0 + w 1 x 1 + w 2 x 2 < 0 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 w 0 + w 1 x i 1 + w 2 x i 2 ≥ 0 dla wszystkich punktów x i z y i = 1 oraz w 0 + w 1 x i 1 + w 2 x i 2 < $[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 Y i = - 1 [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| \\ \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 w , 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 x i z y i = 1 oraz w 0 + w 1 x i 1 + w 2 x i 2 < 0 dla wszystkich punktów x i w 1 x i 1 + w 2 x i $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 w 0$y_i = -1$ dla wszystkich punktów x I z Y i = 1 , a W 0 + w 1 x I 1 + w 2 x i 2 ≤ - 1 dla wszystkich punktów x I z Y i = - $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} \\ \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 \\ \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^Tx_+ + w_0 = 1$$ $$w^Tx_- + w_0 = -1$$ $$w^T(x_+ - x_-) = 2$$ $$|w^T(x_+ - x_-)| = 2$$ $$\|w\|_2\|x_+ - x_-\|_2 = 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.