Dado un conjunto de puntos en un espacio bidimensional, ¿cómo se puede diseñar una función de decisión para SVM?

¿Alguien puede explicarme cómo se diseña una función de decisión SVM? O señalarme un recurso que discute un ejemplo concreto.

EDITAR

Para el siguiente ejemplo, puedo ver que la ecuación separa las clases con un margen máximo. Pero, ¿cómo ajusto los pesos y escribo ecuaciones para hiperplanos en la siguiente forma?$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}$$

Estoy tratando de entender bien la teoría subyacente en el espacio 2-D (ya que es más fácil de visualizar) antes de pensar en dimensiones más altas.

He encontrado una solución para esto. ¿Alguien puede confirmar si esto es correcto?

el vector de peso es (0, -2) y W_0 es 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}$$

Hay al menos dos formas de motivar a los SVM, pero tomaré la ruta más simple aquí.

Ahora, olvide todo lo que sabe sobre SVM por el momento y concéntrese en el problema en cuestión. Se le da un conjunto de puntos junto con algunas etiquetas ( ) que son de . Ahora, estamos tratando de encontrar una línea en 2D de modo que todos los puntos con la etiqueta caigan en un lado de la línea y todos los puntos con la etiqueta caigan en el otro lado.y i { 1 , - 1 } 1 - $\mathcal{D} = \{(x^i_1, x^i_2, y_i)\}$$y_i$$\{1, -1\}$$1$$-1$

En primer lugar, cuenta que es una línea en 2D y representa "un lado" de la línea y representa el "otro lado" del línea.w 0 + w 1 x 1 + w 2 x 2 > 0 w 0 + w 1 x 1 + w 2 x 2 < $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 lo anterior podemos concluir que queremos algún vector tal que, para todos los puntos con y para todos los puntos con [1].w 0 + w 1 x i 1 + w 2 x i 2 ≥ 0 x i y i = 1 w 0 + w 1 x i 1 + w 2 x i 2 < 0 x i y i = - $[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$$x^i$$y_i = -1$

Supongamos que tal línea realmente existe, entonces puedo definir un clasificador de la siguiente manera,

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

He usado una función objetivo arbitraria arriba, realmente no nos importa en este momento qué función objetivo se usa. Solo queremos una que satisfaga nuestras limitaciones. Como hemos asumido que existe una línea tal que podemos separar las dos clases con esa línea, encontraremos una solución al problema de optimización anterior.$w$

Lo anterior no es SVM pero le dará un clasificador :-). Sin embargo, este clasificador puede no ser muy bueno. Pero, ¿cómo se define un buen clasificador? Un buen clasificador suele ser el que funciona bien en el conjunto de prueba. Idealmente, debería revisar todas las posibles que separan sus datos de entrenamiento y ver cuál de ellos funciona bien en los datos de la prueba. Sin embargo, hay infinitas 's, por lo que esto es bastante inútil. En cambio, consideraremos algunas heurísticas para definir un buen clasificador. Una heurística es que la línea que separa los datos estará suficientemente lejos de todos los puntos (es decir, siempre hay un espacio o margen entre los puntos y la línea). El mejor clasificador entre estos es el que tiene el margen máximo. Esto es lo que se usa en SVM.$w$$w$

En lugar de insistir en que para todos los puntos con y para todos los puntos con , si insistimos en que para todos los puntos con y para todos los puntos con , entonces estamos insistiendo en que los puntos estén lejos de la línea. El margen geométrico correspondiente a este requisito resulta ser .x i y i = 1 w 0 + w 1 x i 1 + w 2 x i 2 < 0 x i y i = - 1 w 0 + w 1 x i 1 + w 2 x i 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$$x^i$$y_i = -1$$w_0 + w_1x^i_1 + w_2x^i_2 \geq 1$y i = 1 w 0 + w 1 x i 1 + w 2 x i 2 ≤ - 1 x i y i = - 1 $x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 \leq -1$$x^i$$y_i = -1$$\frac{1}{\|w\|_2}$

Entonces, tenemos el siguiente problema de optimización, Una forma de escritura un tanto sucinta es, Esta es básicamente la formulación básica de SVM. Me he saltado muchas discusiones por brevedad. Con suerte, aún tengo la mayor parte de la idea.

$$\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 \\ $$ $$\min \|w\|_2 \\ \text{subject to} : y_i(w_0 + w_1x^i_1 + w_2x^i_2) \geq 1, \forall i$$

---

Script CVX para resolver el problema de ejemplo:

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

---

Anexo - Margen Geométrico

Arriba, ya hemos solicitado que tal que o generalmente . El LHS aquí que ves se llama margen funcional, por lo que lo que hemos solicitado aquí es que el margen funcional sea . Ahora, intentaremos calcular el margen geométrico dado este requisito de margen funcional.y i ( w 0 + w 1 x 1 + w 2 x 2 ) ≥ 1 y i ( w 0 + w T x ) ≥ 1 ≥ $w$$y_i(w_0 + w_1x_1 + w_2x_2) \geq 1$$y_i(w_0 + w^Tx) \geq 1$$\geq 1$

¿Qué es el margen geométrico? El margen geométrico es la distancia más corta entre puntos en los ejemplos positivos y puntos en los ejemplos negativos. Ahora, los puntos que tienen la distancia más corta como se requiere arriba pueden tener un margen funcional mayor que igual a 1. Sin embargo, consideremos el caso extremo, cuando están más cerca del hiperplano, es decir, el margen funcional para los puntos más cortos es exactamente igual a 1. Sea el punto en el ejemplo positivo, sea un punto tal que y sea ​​el punto en el ejemplo negativo, sea un punto tal que . Ahora, la distancia entre y será la más corta cuandow T x + + w 0 = 1 x - w T x - + w 0 = - 1 x + x - x + - x $x_+$$w^Tx_+ + w_0 = 1$$x_-$$w^Tx_- + w_0 = -1$$x_+$$x_-$$x_+ - x_-$ es perpendicular al hiperplano.

Ahora, con toda la información anterior, intentaremos encontrar que es el margen geométrico. $\|x_+ - x_-\|_2$

$$w^Tx_+ + w_0 = 1$$ $$w^Tx_- + w_0 = -1$$ $$w^T(x_+ - x_-) = 2$$ $$|w^T(x_+ - x_-)| = 2$$ ‖ x + - x - ‖ 2 = $$\|w\|_2\|x_+ - x_-\|_2 = 2$$ $$\|x_+ - x_-\|_2 = \frac{2}{\|w\|_2}$$

---

[1] En realidad no importa qué lado elijas para y . Solo tienes que mantenerte consistente con lo que elijas.- $1$$-1$