Derivación del valor óptimo para el término de intercepción en SVM

Question

Estaba leyendo los apuntes de aprendizaje automático de Andrew Ng sobre SVM. Me encontré con la siguiente ecuación (encontrar el valor óptimo para el término de intercepción $b$ en el problema SVM):

Sin embargo, no tengo ni idea de cómo el término de intercepción $b$ se obtiene resolviendo el problema primario ?

Creo que el Lagrangiano del primal es:

$$\min_{w,b} \max_{\alpha} \mathcal{L}(w,b,\alpha) = \min_{w,b} \max_{\alpha} \frac{1}{2} ||w||^2 - \sum_{i=1}^m \alpha_i [y_i (w^T x_i + b) - 1]$$

Pero, ¿cómo resuelvo $b$ ? Cualquier ayuda será estupenda. Muchas gracias.

Answer 1

Tengo una explicación geométrica. Piense en SVM como un clasificador de margen máximo. En ese sentido buscamos hiperplano de separación que será equidistante de todos los negativos y todos los ejemplos positivos. Esto incluye que la distancia del hiperplano más cercano a su ejemplo negativo sería tan grande como la distancia al positivo más cercano. Sea $w^*$ ser conocido, entonces $$\max_{i: y^{(i)}=-1} w^{*T}x^{(i)}$$ es la distancia más cercana (en el peor de los casos) de todos los ejemplos negativos posibles. Del mismo modo, $$\min_{i: y^{(i)}=1} w^{*T}x^{(i)}$$ es la distancia más cercana (en el peor de los casos) de todos los ejemplos positivos posibles. ¿Cómo podemos elegir la intercepción de modo que la distancia del peor caso para todos los ejemplos (del peor caso) sea máxima? Sí, tomamos la media de dos.

El signo "-".

Estrictamente hablando, $\max_{i: y^{(i)}=-1} w^{*T}x^{(i)}$ no es una distancia porque es negativa, mientras que $\min_{i: y^{(i)}=1} w^{*T}x^{(i)}>0$ . Por lo tanto, para llevar el hiperplano de la peor dirección negativa a la peor dirección positiva necesitamos el signo "-".

Answer 2

En primer lugar, para los vectores de soporte, los límites de decisión vienen dados por $\omega^{*T}x^{(i)} + b = \pm 1$ y $\frac{-b}{||\omega||}$ es la distancia del origen al hiperplano.

Los ejemplos positivos y negativos más cercanos al hiperplano de separación son,

$argmax_{i:y^{(i)} = -1} \omega^{*T}x^{(i)}$ resp. $argmin_{i:y^{(i)} = 1} \omega^{*T}x^{(i)}$

Estos verifican (porque los deben ser vectores soporte) las ecuaciones para los límites de decisión, es decir,

$max_{i:y^{(i)} = -1} \omega^{*T}x^{(i)} + b = -1$ resp. $min_{i:y^{(i)} = 1} \omega^{*T}x^{(i)} + b = 1$

Suma las dos y resuelve para $b$ .

P.D. ¿Por qué $\frac{-b}{||\omega||}$ ¿es la distancia del origen al hiperplano? Podríamos resolverlo con un poco de álgebra (como aquí ), o como un problema de optimización :) La distancia a una recta es la norma del punto vectorial más cercano al origen. Es decir, nos gustaría resolver,

$$ min ||x||^{2} $$ sujeto a $\omega^{T}x + b = 0$ . Introduciendo multiplicadores de Lagrange obtenemos, $$ L = \frac{1}{2}||x||^{2}-\lambda(\omega^{T}x + b) $$ Si derivamos con respecto a $x$ igual a cero y resolver para $x$ obtenemos $x=\lambda \omega$ . Reste de nuevo en la restricción y encuentre $\lambda = \frac{-b}{||\omega||^{2}}$ .

Answer 3

Sé que es tarde, pero por si sirve de ayuda daré una explicación equivalente a las respuestas anteriores, que también pueden ayudar.

En primer lugar, nuestro primal problema aquí es: $$ \min_w \frac{1}{2}\lVert{w}\rVert^2$$ $$ s.t. \rightarrow y^i(w^Tx^i+b)\geq1=\hat{\gamma}$$

A partir de este problema primal y tal como dice jpmuc, los puntos de datos más cercanos ( $x^i$ ) del conjunto de entrenamiento al límite de decisión:

$$\min_{y^i=1} (w^{*T}x^i) + b^*= 1 \iff y^i=1$$ y $$\max_{y^i=-1}(w^{*T}x^i) + b^*= -1 \iff y^i=-1$$

Esto se debe a que antes hemos fijado el margen funcional de todo el conjunto de datos ( $\hat{\gamma}$ ) a $1$ .

Ahora, sabemos que el margen de los puntos positivos respecto al límite de decisión (hiperplano) tiene que ser igual al margen de los puntos negativos respecto al hiperplano. De lo contrario, el margen de un conjunto de puntos (negativos o positivos) no se maximizaría por igual.

Dado esto, y las dos últimas ecuaciones (del problema primal) podemos llegar al valor deseado $b^*$ sumándolos y resolviendo para $b^*$ :

$$b^*=-\frac{\min_{y^i=1} (w^{*T}x^i) + \max_{y^i=-1} (w^{*T}x^i)}{2}$$