Étant donné un ensemble de points dans un espace bidimensionnel, comment peut-on concevoir une fonction de décision pour SVM?

Quelqu'un peut-il m'expliquer comment on conçoit une fonction de décision SVM? Ou pointez-moi vers une ressource qui discute d'un exemple concret.

ÉDITER

Pour l'exemple ci-dessous, je peux voir que l'équation sépare les classes avec une marge maximale. Mais comment puis-je ajuster les poids et écrire des équations pour les hyperplans sous la forme suivante.$X_2 = 1.5$

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

J'essaie d'obtenir la théorie sous-jacente dans l'espace 2D (car c'est plus facile à visualiser) avant de penser à des dimensions plus élevées.

J'ai trouvé une solution pour cela. Quelqu'un peut-il confirmer si c'est correct?

le vecteur de poids est (0, -2) et W_0 est 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}$$

Il existe au moins deux façons de motiver les SVM, mais je prendrai ici l'itinéraire le plus simple.

Maintenant, oubliez tout ce que vous savez sur SVM pour le moment et concentrez-vous simplement sur le problème actuel. On vous donne un ensemble de points ainsi que quelques étiquettes ( y i ) qui sont de { 1 , - 1 } . Maintenant, nous essayons de trouver une ligne en 2D de telle sorte que tous les points avec l'étiquette 1 tombent d'un côté de la ligne et tous les points avec l'étiquette - 1 tombent de l'autre côté.$\mathcal{D} = \{(x^i_1, x^i_2, y_i)\}$$y_i$$\{1, -1\}$$1$$-1$

Tout d'abord, réalisez que est une ligne en 2D et w 0 + w 1 x 1 + w 2 x 2 > 0 représente "un côté" de la ligne et w 0 + w 1 x 1 + w 2 x 2 < 0 représente "l'autre côté" de la ligne.$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$

De ce qui précède, nous pouvons conclure que nous voulons un vecteur tel que, w 0 + w 1 x i 1 + w 2 x i 2 ≥ 0 pour tous les points x i avec y i = 1 et 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$pour tous les points avec y i = - 1 [1].$x^i$$y_i = -1$

Supposons qu'une telle ligne existe réellement, alors je peux définir un classificateur de la manière suivante,

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

J'ai utilisé une fonction objective arbitraire ci-dessus, nous ne nous soucions pas vraiment pour le moment de la fonction objective utilisée. Nous voulons juste un qui réponde à nos contraintes. Puisque nous avons supposé qu'une ligne existe de telle sorte que nous pouvons séparer les deux classes avec cette ligne, nous trouverons une solution au problème d'optimisation ci-dessus.$w$

Ce qui précède n'est pas SVM mais il vous donnera un classificateur :-). Cependant, ce classificateur peut ne pas être très bon. Mais comment définissez-vous un bon classificateur? Un bon classificateur est généralement celui qui fonctionne bien sur l'ensemble de test. Idéalement, vous devriez passer en revue tous les possibles qui séparent vos données d'entraînement et voir lesquels d'entre eux fonctionnent bien sur les données de test. Cependant, il existe des w infinis , c'est donc tout à fait désespéré. Au lieu de cela, nous considérerons quelques heuristiques pour définir un bon classificateur. Une heuristique est que la ligne qui sépare les données sera suffisamment éloignée de tous les points (c'est-à-dire qu'il y a toujours un écart ou une marge entre les points et la ligne). Le meilleur classificateur parmi ceux-ci est celui avec la marge maximale. C'est ce qui est utilisé dans les SVM.$w$$w$

Au lieu d'insister sur le fait que pour tous les points x i avec y i = 1 et w 0 + w 1 x i 1 + w 2 x i 2 < 0 pour tous les points x i avec y i = - 1 , si nous insistons pour que w 0$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$$y_i = -1$ pour tous les points x i avec y i = 1 et w 0 + w 1 x i 1 + w 2 x i 2 ≤ - 1 pour tous les points x i avec 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$, alors nous insistons pour que les points soient loin de la ligne. La marge géométrique correspondant à cette exigence se révèle être .$\frac{1}{\|w\|_2}$

Nous obtenons donc le problème d'optimisation suivant,

$$\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 \\ $$ Une forme d'écriture légèrement succincte est, Il s'agit essentiellement de la formulation SVM de base. J'ai sauté pas mal de discussions par souci de concision. Avec un peu de chance, j'ai réussi à faire passer l'essentiel de l'idée. $$\min \|w\|_2 \\ \text{subject to} : y_i(w_0 + w_1x^i_1 + w_2x^i_2) \geq 1, \forall i$$

---

Script CVX pour résoudre l'exemple de problème:

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

---

Addendum - Marge géométrique

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

$\|x_+ - x_-\|_2$

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