SVM Formulaci贸n del problema desde un punto de vista 'real'馃憫

Durante este post usaremos un conjunto de datos un tanto peculiar;

\[\pi = \{(x_i, y_i) , x_i \in R^p, y_i \in \{Austrias, Borbones\} \}^m_{i=1}\]

Como representantes de la dinast铆a borb贸nica he escogido a m铆 tr铆o favorito: Carlos IV, su esposa Mar铆a Luisa de Parma y Manuel Godoy. S铆, Godoy no es ning煤n borb贸n, pero existen razonables dudas sobre la parte que le ocup贸 a Carlos en los 14 hijos de Mar铆a Luisa de Parma y si a esto le a帽adimos el razonable parecido de estos con Godoy junto a la promiscuidad y desatenci贸n de la pobre Mar铆a Luisa por parte de su marido鈥

Como representantes de la dinast铆a de los austrias tenemos a Juana I la Loca, Carlos II el Hechizado y el pr铆ncipe don Carlos (primog茅nito de Felipe II). Creo que estos tres personajes representan a la perfecci贸n la demencia y los frutos de la consanguinidad que caracterizaron a la dinast铆a de los austrias.

Respecto al poco conocido Carlos, creo que merece algunas palabras. El pobre nunca lleg贸 a ser rey, muri贸 a manos de su malvado padre (Felipe II) o esa es la versi贸n que se nos ha intentado vender por parte de los brit谩nicos. En realidad, Carlos era un s谩dico con graves problemas mentales. Sus problemas se manifestaron bien pronto, cuando era beb茅. En aquella 茅poca era habitual que la reina no amamantase a sus hijos sino que lo hiciesen las nodrizas, bien, a nuestro amiguito Carlos no le convenc铆a ninguna teta ya que mord铆a los pezones de sus amas hasta llagarlos y estas terminaban muriendo debido a la sepsis provocada por las heridas. Intentaron que una cabra amamantase a Carlos pero 茅l era m谩s listo que sus amas; 茅l quer铆a carne humana. Su vida no dur贸 mucho, muri贸 a los 23 a帽os tras un encierro (por voluntad de su malvado padre) que acrecent贸 su locura.

Un dataset $D = \{(x_i, y_i) , x_i \in R^p, y_i \in {-1, 1} \}^m_{i=1}$ linealmente separable puede clasificarse usando varios hiperplanos diferentes. Un modelo de clasificaci贸n como el perceptr贸n encontrar谩 miles de hiperplanos diferentes. Las SVM en vez de encontrar un hiperplano cualquiera, encuentran el se帽or hiperplano, el que mejor separa entre los datos.

驴C贸mo comparar dos hiperplanos?

Para encontrar el se帽or hiperplano primero debemos saber c贸mo comparar dos hiperplanos. Dada una observaci贸n $(x_{Juana}, y)$ y un hiperplano, si Juana se encuentra en el plano, se satisface la ecuaci贸n del plano; $wx_{Juana} + b = 0$. 驴Pero qu茅 ocurre si no se est谩 en el plano? Definamos un hiperplano con $w = (-0.6, -1)$ y $b=7$.

  • Para Juana I La Loca (5, 4); $wx_{Juana} + b = 0$ como ya hab铆amos comentado
  • Para Mar铆a Tudor (3,2); $wx_{Mar铆a} + b = 3.2$
  • Para Carlos V de Alemania (1.5, 0.5); $wx_{Carlos} + b = 5.6$
  • Para Pepe Botella (tan querido por el pueblo espa帽ol), que es un dato at铆pico en nuestro dataset (y en la historia de Espa帽a); (7, 6); $wx_{Jose} + b = -3.2$

Como acabamos de ver, si nuestro personaje se sit煤a por encima del hiperplano el valor es negativo y positivo en caso contrario. Por ello, para el problema de clasificaci贸n inicial podemos usar la siguiente regla para clasificar en una clase u otra:

\[Austria \;\;\; \rightarrow \;\;\; si \;\;\; wx_i + b > 0\] \[Borb贸n \;\;\; \rightarrow \;\;\; si \;\;\; wx_i + b \leq 0\]

Adem谩s, seg煤n se alejan nuestros monarcas del hiperplano, la ecuaci贸n de este asigna un valor cada vez mayor. Entonces, podemos calcular el valor $\beta = wx + b$ para saber lo lejos que se encuentra una observaci贸n del hiperplano. El mejor hiperplano ser谩 aquel que tenga las observaciones tan alejadas como sea posible. Definimos $B$ como el menor valor de todos los $\beta$ de nuestro dataset. Si queremos escoger entre dos hiperplanos, escogeremos el que tenga un mayor $B$.

\[B = \underset{i=1,...,m}{\text{min}} \beta_i\]

Problemas con esta aproximaci贸n

Si decidi茅ramos comparar dos hiperplanos seg煤n $B$ tendr铆amos un problema, escoger el $\beta_i$ m铆nimo no funciona para las observaciones en la parte negativa (donde se encuentra Pepe Botella).

Siempre querremos que el $\beta_i$ m铆nimo sea el del punto m谩s cercano al hiperplano. Entre dos observaciones con $\beta_1 = -5$ y $\beta_2=-1$, escoger铆amos $\beta_1$ porque $\beta_1 < \beta_2$, pero, en realidad, $\beta_1$ est谩 m谩s lejos del hiperplano que $\beta_2$. Una forma de solucionar este problema es considerar el valor absoluto de $\beta_i$.

\[B = \underset{i=1,...,m}{\text{min}} | \beta_i |\]

M谩s problemas

Vamos a trabajar con una variable respuesta que tomar谩 el valor +1 si la observaci贸n pertenece a los Borbones y -1 si pertenece a los Austrias (no eran muy positivos).

Calcular $B$ nos ayuda a escoger el hiperplano, pero usando solo $B$ podr铆amos escoger el hiperplano err贸neo. En la siguiente gr谩fica vemos que en el hiperplano de color rojo las clases se separan bien (la clase negativa de los Austrias est谩 por encima de la recta y la clase positiva por debajo), pero en el segundo hiperplano (negro) las clases est谩n mal clasificadas. Sin embargo, ambos hiperplanos tienen un $B = 2$.

La soluci贸n en este caso pasa por considerar el valor de la observaci贸n en la variable respuesta (-1 o 1). Definimos el valor $f_i = y_i \beta_i = y_i (wx_i + b)$. $f_i$ tomar谩 un valor positivo si la observaci贸n est谩 bien clasificada y negativo si no lo est谩. As铆, dado un dataset podemos calcular $F$ que ser谩 el menor $f_i$ del dataset. Si nuestro hiperplano no es el correcto, $F$ tomar谩 un valor negativo. Por tanto, al igual que con $B$, seleccionaremos el hiperplano que mayor $F$ tenga.

\[F = \underset{i=1,...,m}{\text{min}} f_i = \underset{i=1,...,m}{\text{min}} y_i(wx_i + b)\]

El valor $f_i$ se conoce como functional margin of an observation y el valor $F$ como functional margin of the dataset.

Escalado

Houston, tenemos un (otro) problema; $f_i$ no es invariante a la escala. Dado el vector $w_1 = (2, 1)$ y $b_1 = 5$ si multiplicamos ambos por 10 tenemos $\rightarrow$ $w_2=(20,10)$ y $b_2 = 50$. Si calculamos $F$ con $w_2$ obtenemos un valor 10 veces mayor que con $w_1$, lo que nos lleva a afirmar que dado cualquier hiperplano, siempre podremos encontrar otro con un $F$ mayor reescalando $b$ y $w$. Para que esto no sea un problema, usaremos el vector unitario de $w$, dividiendo $w$ por su norma eucl铆dea, tambi茅n lo haremos con $b$. A este nuevo valor lo designaremos con la letra $\gamma_i$ que se conoce como geometric margin of an observation. La ventaja de $\gamma_i$ es que siempre nos devuelve el mismo valor sin importar la escala de $b$ o $w$.

\[\gamma_i = y_i(\frac{w}{||w||}x_i + \frac{b}{||w||})\]

Definimos $M$ como el menor $\gamma_i$ del conjunto de datos, y al igual que antes, seleccionaremos el hiperplano que mayor $M$ tenga.

\[M = \underset{i=1,...,m}{\text{min}} \gamma_i = \underset{i=1,...,m}{\text{min}} y_i(\frac{w}{||w||}x_i + \frac{b}{||w||})\]

Margen geom茅trico ?

A $\gamma_i$ se le llama margen geom茅trico porque mide la distancia entre una observaci贸n $x_i$ y el hiperplano. Para entender por qu茅 el margen geom茅trico es equivalente a la distancia entre una observaci贸n y el hiperplano tomemos a Carlos IV ($x_{Carlos}$) como referente (aunque Carlos IV y referente podr铆a ser un ejemplo de ant铆tesis).

El punto $x鈥$ es la proyecci贸n ortogonal de $x_{Carlos}$ en el hiperplano. El vector $k$ tiene la misma direcci贸n que el vector $w$ que define el hiperplano, comparten el mismo vector unitario; $\frac{w}{\lVert w \rVert}$. La norma de $k$ es la distancia entre el hiperplano y la observaci贸n; $d$. Por tanto, $k = d \frac{w}{\lVert w \rVert}$. Bien, si nos fijamos veremos que $x鈥$ es la resta de $x$ y $k$, o sea, $x鈥 = x - k = x - d \frac{w}{\lVert w \rVert}$ . Como $x鈥$ se encuentra en el hiperplano, debe satisfacer su ecuaci贸n;

\[wx' + b = 0\] \[w(x - d \frac{w}{||w||})+b = 0\] \[wx - d \frac{ww}{||w||}+b = 0\] \[wx - d \frac{||w||^2}{||w||}+b = 0\] \[wx - d ||w|| + b = 0\] \[d = \frac{wx + b}{||w||}\] \[d = \frac{w}{||w||}x + \frac{b}{||w||}\]

Y si nos damos cuenta, la expresi贸n de $d$ es la misma que la de $\gamma_i$ $\rightarrow$ el margen geom茅trico es la distancia entre una observaci贸n $x$ y su proyecci贸n en el hiperplano.

Hiperplano 贸ptimo

Como hemos visto, para encontrar el hiperplano que nos ofrezca un mayor margen debemos encontrar el hiperplano que maximice $M$. Podemos escribirlo de la siguiente forma;

\[\underset{w, b}{\text{max}} \; M\] \[s.t \;\; \gamma_i \geq M, i= 1, ..., m\]

Hay una relaci贸n entre $M$ y $F$ como ya hemos visto $\rightarrow$ $M = \frac{F}{\lVert w \rVert}$. Podemos reescribir el problema como;

\[\underset{w, b}{\text{max}} \; \frac{F}{\lVert w \rVert}\] \[s.t \;\; \frac{f_i}{\lVert w \rVert} \geq \frac{F}{\lVert w \rVert}, i= 1, ..., m\]

Eliminando $\lVert w \rVert$ de la inecuaci贸n tenemos que;

\[\underset{w, b}{\text{max}} \; \frac{F}{\lVert w \rVert}\] \[s.t \;\; f_i \geq F, i= 1, ..., m\]

Intentamos maximizar el margen geom茅trico, por tanto, la escala de $w$ y $b$ no importan. Es decir, podemos variar $w$ y $b$ tanto como queramos que $\gamma_i$ no se ver谩 afectado por ello. Por tanto, escalamos $w$ y $b$ de forma que $F=1$.

\[\underset{w, b}{\text{max}} \; \frac{1}{\lVert w \rVert}\] \[s.t \;\; f_i \geq 1, i= 1, ..., m\]

Este problema es equivalente a;

\[\underset{w, b}{\text{min}} \; \lVert w \rVert\] \[s.t \;\; y_i(wx_i + b)\geq 1, i= 1, ..., m\]

Sin embargo, se suele cambiar la funci贸n objetivo y en vez de considerar la norma eucl铆dea se eleva esta al cuadrado para que desaparezca la ra铆z. Adem谩s y por conveniencia se multiplica por $\frac{1}{2}$. As铆 finalmente llegamos a la conocida funci贸n a minimizar de las m谩quinas de soporte vectorial.

\[\underset{w, b}{\text{min}} \; \frac{1}{2} \lVert w \rVert^2\] \[s.t \;\; y_i(wx_i + b) - 1 \geq 0, i= 1, ..., m\]

En resumen, hemos asumido que existen algunos hiperplanos que son mejores que otros. Para encontrar el hiperplano 贸ptimo hemos llegado a la conclusi贸n de que se debe maximizar el margen geom茅trico; $M$. El mejor hiperplano ser谩 aquel que tenga un mayor $M$. Al final, hemos concluido que el vector $w$ del hiperplano 贸ptimo se encuentra minimizando la norma de $w$.

Referencias

  • Data Science y redes complejas (Eloy Vicente Cestero y Alfonso Mateos Caballero)
  • Support Vector Machines Succinctly (Alexandre Kowalczyk)
updated_at 14-07-2020