See discussions, stats, and author profiles for this publication at: [Link]

net/publication/263817587

Tutorial sobre Máquinas de Vectores Soporte (SVM)

Technical Report · November 2016

CITATIONS READS
13 1,757

1 author:

Enrique J. Carmona
National Distance Education University
31 PUBLICATIONS   652 CITATIONS   

SEE PROFILE

All content following this page was uploaded by Enrique J. Carmona on 30 November 2016.

The user has requested enhancement of the downloaded file.

 Tutorial sobre Máquinas de Vectores Soporte (SVM)

Enrique J. Carmona Suárez

ecarmona@[Link]

Versión inicial: 17/11/2013 Última versión: 16/11/2016

Dpto. de Inteligencia Articial, ETS de Ingeniería Informática, Universidad Nacional de Educación a

Distancia (UNED), C/Juan del Rosal, 16, 28040-Madrid (Spain)

Abstract
Este tutorial presenta una introducción al mundo de las máquinas de vectores soporte
(SVM, del inglés Support Vector Machine ), aplicadas a resolver tareas tanto de clasica-
ción como de regresión. En el primer tipo de tareas, la descripción se restringe al caso de
clasicación binaria y, atendiendo al tipo de separabilidad de los ejemplos de entrada, se
consideran distintas opciones. Así, en primer lugar, se aborda el caso ideal de ejemplos
linealmente separables para, seguidamente, abordar el caso más realista de ejemplos que,
aunque afectados por ruido, se consideran linealmente cuasi-separables y, nalmente, se
considera el caso de ejemplos no linealmente separables, donde las SVM demuestran su
gran potencialidad. Por otro lado, la descripción de las SVMs aplicadas a la tarea de regre-
sión considera los casos tanto de regresión lineal como no lineal. Finalmente, se presentan
algunas herramientas software de uso libre que implementan este tipo de paradigma de
aprendizaje y con las que el usuario puede empezar a experimentar.

1 Introducción
Las máquinas de vectores soporte (SVM, del inglés Support Vector Machine ) tienen su origen
en los trabajos sobre la teoría del aprendizaje estadístico y fueron introducidas en los años
90 por Vapnik y sus colaboradores Boser et al. (1992); Cortes & Vapnik (1995). Aunque
originariamente las SVMs fueron pensadas para resolver problemas de clasicación binaria,
actualmente se utilizan para resolver otros tipos de problemas (regresión, agrupamiento, mul-
ticlasicación). También son diversos los campos en los que han sido utilizadas con éxito,
tales como visión articial, reconocimiento de caracteres, categorización de texto e hipertexto,
clasicación de proteínas, procesamiento de lenguaje natural, análisis de series temporales.
De hecho, desde su introducción, han ido ganando un merecido reconocimiento gracias a sus
sólidos fundamentos teóricos.
Dentro de la tarea de clasicación, las SVMs pertenecen a la categoría de los clasicadores
lineales, puesto que inducen separadores lineales, también llamados hiperplanos, ya sea en
el espacio original de los ejemplos de entrada, si éstos son linealmente separables o cuasi-
separables (ruido), o en un espacio transformado (espacio de características), si los ejemplos no
son linealmente separables en el espacio original. Como se verá más adelante, la búsqueda del
hiperplano de separación en estos espacios transformados, normalmente de muy alta dimensión,
se hará de forma implícita utilizando las denominadas funciones kernel.

1
 Mientras la mayoría de los métodos de aprendizaje se centran en minimizar los errores
cometidos por el modelo generado a partir de los ejemplos de entrenamiento (error empírico),
el sesgo inductivo asociado a las SVMs radica en la minimización del denominado riesgo
estructural. La idea es seleccionar un hiperplano de separación que equidista de los ejemplos
más cercanos de cada clase para, de esta forma, conseguir lo que se denomina un margen
máximo a cada lado del hiperplano. Además, a la hora de denir el hiperplano, sólo se
consideran los ejemplos de entrenamiento de cada clase que caen justo en la frontera de dichos
márgenes. Estos ejemplos reciben el nombre de vectores soporte. Desde un punto de vista
práctico, el hiperplano separador de margen máximo ha demostrado tener una buena capacidad
de generalización, evitando en gran medida el problema del sobreajuste a los ejemplos de
entrenamiento.
Desde un punto de vista algorítmico, el problema de optimización del margen geométrico
representa un problema de optimización cuadrático con restricciones lineales que puede ser
resuelto mediante técnicas estándar de programación cuadrática. La propiedad de convexidad
exigida para su resolución garantizan una solución única, en contraste con la no unicidad de
la solución producida por una red neuronal articial.
Dado el carácter introductorio de este tutorial, los contenidos del mismo sólo abarcan una
pequeña parcela del extenso campo relacionado con las máquinas vectores soporte. Por ejem-
plo, la tarea de clasicación sólo se describirá para el caso de clasicación binaria. El resto del
documento se estructura de la siguiente forma. Así, en la sección 2, se presentan, de forma
resumida, aquellos resultados de la teoría de la optimización necesarios para solucionar los
diferentes problemas de optimización que surgen como consecuencia de abordar la tarea de
clasicación y de regresión mediante SVMs. En la sección 3, se aborda el problema de clasi-
cación binaria para ejemplos perfectamente separables mediante lo que se conoce como SVMs
de "margen duro" ( hard margin SVM ). Dado que en la práctica es normal que los ejemplos
de entrenamiento puedan contener ruido, la sección 4 se dedica al problema de clasicación
binaria para ejemplos cuasi-separables linealmente, mediante lo que se denomina SVMs de
"margen blando" ( soft margin SVM ). La sección 5 culmina el problema de clasicación bina-
ria tratando el caso de la clasicación de ejemplos no separables linealmente mediante lo que
se conoce como SVM kernelizadas. Seguidamente, la sección 6 aborda el problema de regresión
mediante lo que se conoce como regresión con vectores soporte (SVR, del inglés Support Vector
Regression ). En esta sección, se aborda tanto el caso de regresión lineal como el de regresión
no lineal. Finalmente, en la sección 7 se describe algunos de los paquetes software de uso
libre que implementan SVMs y SVRs. El uso de este software puede ser un buen punto de
comienzo para que el lector se familiarice, desde un punto de vista práctico, con las máquinas
de vectores soporte.

2 Breve introducción a la teoría de la Optimización

Tal y como se verá en las siguientes secciones, los diferentes problemas abordados por las SVMs
corresponden a problemas de optimización con restricciones lineales. Este tipo de problemas
se resuelven haciendo uso de la Teoría de la Optimización. En esta sección se hace un breve
resumen de las principales ideas de esta disciplina.
Sea el siguiente problema de optimización denominado problema primal :
min f (x), x∈Ω
(1)
s.a. gi (x) ≤ 0, i = 1, . . . , n

2
La solución del problema primal, x∗ , cumplirá que gi (x∗ ) ≤ 0 y f (x∗ ) ≤ f (x), ∀x t.q. gi (x) ≤
0, donde i = 1, ..., n. Si todas las funciones f y gi son lineales estamos ante un problema
de optimización abordable mediante una disciplina conocida como programación lineal. En
cambio, si la función a optimizar es cuadrática y las restricciones siguen siendo lineales, el
problema es abordable mediante lo que se denomina programación cuadrática. No obstante, en
ambos casos, la teoría de la optimización establece que un problema de optimización (primal)
tiene su forma dual siempre que la función a optimizar y las restricciones sean estrictamente
convexas. En este caso, resolver el problema dual es equivalente a resolver el problema primal.
Para realizar la transformación del problema primal al dual es necesario usar el concepto
de función de Lagrange, denida a partir de la función a minimizar, f (x), y las restricciones,
gi (x), de la siguiente manera:

n
X
L (x, α) = f (x) + αi gi (x) (2)
i=1

donde los coecientes αi ≥ 0 reciben el nombre de multiplicadores de Lagrange y, de forma

intuitiva, indican la dicultad de cumplir cada restricción, es decir, a mayor valor de αi , más
difícil sera de cumplir su restricción asociada gi (x). La función lagrangiana tiene la particu-
laridad de incorporar la función objetivo y las funciones restricción en una única función.
A partir de la función de Lagrange se puede denir el problema dual como:

max ϕ(α) = inf L (x, α)

x∈Ω
(3)

s.a. αi ≥ 0, i = 1, . . . , n

Tal y como se decía anteriormente, el interés del problema dual es que, bajo determinadas
condiciones, al resolverlo, obtenemos también la solución del problema primal asociado. La
ventaja de esta transformación es que normalmente el problema dual es más fácil de resolver
que el primal. Los dos siguiente teoremas ayudan a entender la relación existente entre las
soluciones de estos dos problemas (primal y dual).

Teorema 1. Sean x y α vectores tales que satisfacen las restricciones respectivas del
problema primal y dual, es decir, gi (x) ≤ 0 y αi ≥ 0, con i = 1, ..., n, entonces ϕ(α) ≤ f (x).

Del teorema anterior se pueden extraer dos corolarios. El primero establece que el problema
dual está acotado superiormente por el problema primal. El segundo permite armar que si
ϕ(α) = f (x), entonces α y x son soluciones, respectivamente, del problema dual y primal.
El interés de este teorema es práctico, ya que permite establecer una heurística para resolver,
simultáneamente, el problema primal y dual. Así, estaremos más cerca de la solución, a medida
que la diferencia |ϕ(α) − f (x)| sea más pequeña. La solución se alcanza cuando la diferencia
es nula. Esta solución corresponde a un punto silla de la función lagrangiana, caracterizado por
ser simultáneamente un mínimo de L(x, α) respecto de x y un máximo de L(x, α) respecto
de α.
El segundo teorema, denominado teorema de Karush-Kuhn-Tucker (KKT) establece las
condiciones sucientes (también conocidas como condiciones KKT) para que un punto x∗ sea
solución del problema primal.

Teorema de Karush-Kuhn-Tucker. Si en el problema primal (1), las funciones f :

Rd → R y gi : Rd → R, i = 1, . . . , n son todas ellas funciones convexas, y existen constantes

3
αi ≥ 0, i = 1, . . . , n tales que:
n
∂f (x∗ ) X ∂gi (x∗ )
+ αi =0 j = 1, . . . , d (4)
∂xj ∂xj
i=1

αi gi (x∗ ) = 0 i = 1, . . . , n (5)

entonces el punto x∗ es el mínimo global del problema primal.

La primera condición surge de la función ϕ(α) denida como el ínmo de la función

lagrangiana y, por tanto, como el resultado de calcular las derivadas parciales de la función
lagrangiana e igualarlas a cero. La segunda condición, denominada condición complementaria,
es la que garantizará que los óptimos del problema primal y dual coincidan (ϕ(α
∗) = f (x∗ )),
ya que, de ser cierta la condición, todos los sumandos del sumatorio de la función lagrangiana
(2) serían nulos.
El interés de este último teorema es que permite establecer los pasos y condiciones nece-
sarios para poder obtener la solución del problema primal a partir de la solución obtenida al
resolver el dual. Se pueden resumir dichos pasos de la siguiente forma:

1. Partiendo de la función a minimizar y de las restricciones asociadas al problema primal,

se construye la función lagrangiana.

2. Se aplica la primera condición del teorema de KKT a la función lagrangiana y esto

permite obtener un conjunto de relaciones que, sustituidas en dicha función, harán des-
aparecer todas las variables primales de dicha función. Este paso es equivalente a calcular
inf x∈Ω L (x, α).

3. La función dual así obtenida, sólo dependerá de los multiplicadores de Lagrange. Tam-
bién es posible que, del conjunto de relaciones obtenido al aplicar la primera condición
KKT, surjan restricciones adicionales para las variables duales (además de las restriccio-
nes αi ≥ 0). En este punto queda denido el problema dual (función a optimizar junto
a sus restricciones).

4. La solución del problema dual permitirá resolver también el problema primal. Para ello,
bastará sustituir la solución dual en las relaciones que anteriormente se obtuvieron al
aplicar las dos condiciones KKT.

Estos son los pasos que se utilizarán en la secciones siguientes de este tutorial para resolver
los diferentes problemas de optimización que surgen al abordar la tarea de clasicación o de
regresión mediante SVMs.

3 SVM para clasicación binaria de ejemplos separables lineal-

mente
Dado un conjunto separable de ejemplos S = {(x1 , y1 ) , . . . , (xn , yn )}, donde xi ∈ Rd e yi ∈
{+1, −1}, se puede denir un hiperplano de separación (ver g. 1a) como una función lineal
que es capaz de separar dicho conjunto sin error:

D(x) = (w1 x1 + ... + wd xd ) + b =< w, x > +b (6)

4
 (a) (b)

Figure 1: Hiperplanos de separación en un espacio bidimensional de un conjunto de ejemplos sepa-

rables en dos clases: (a) ejemplo de hiperplano de separación (b) otros ejemplos de hiperplanos de
separación, de entre los innitos posibles.

donde w ∈ Rd , b ∈ R y el operador < x1 , x2 > representa el producto escalar de los vecto-

res x1 y x2 . El hiperplano de separación cumplirá las siguientes restricciones para todo xi
perteneciente al conjunto de ejemplos:

< w, xi > +b ≥ 0 si yi = +1
(7)
< w, xi > +b ≤ 0 si yi = −1, i = 1, ..., n

o también:
yi (< w, xi > +b) ≥ 0, i = 1, . . . , n (8)

o de forma más compacta:

yi D(xi ) ≥ 0, i = 1, . . . , n (9)

Tal y como se puede deducir fácilmente de la g. 1b, el hiperplano que permite separar los
ejemplos no es único, es decir, existen innitos hiperplanos separables, representados por todos
aquellos hiperplanos que son capaces de cumplir las restricciones impuestas por cualquiera de
las expresiones equivalentes (8) y (9). Surge entonces la pregunta sobre si es posible establecer
algún criterio adicional que permita denir un hiperplano de separación único y óptimo. Para
ello, primero, se dene el concepto de margen de un hiperplano de separación, denotado por τ,
como la mínima distancia entre dicho hiperplano y el ejemplo más cercano de cualquiera de las
dos clases (ver g. 2a). A partir de esta denición, un hiperplano de separación se denominará
óptimo si su margen es de tamaño máximo (g. 2b). El concepto de margen máximo está
relacionado directamente con la capacidad de generalización del hiperplano de separación, de
tal forma que, a mayor margen, más equidistará dicho hiperplano de los ejemplos de cada
clase.
Una propiedad inmediata de la denición de hiperplano de separación óptimo es que éste
equidista del ejemplo más cercano de cada clase. La demostración de esta propiedad se puede
hacer fácilmente por reducción al absurdo. Supongamos que la distancia del hiperplano óptimo
al ejemplo más cercano de la clase +1 fuese menor que la correspondiente al ejemplo más
cercano de la clase −1. Esto signicaría que se puede alejar el hiperplano del ejemplo de la

5
 o
óptim
l ano
erp
Hip

(a) (b)

Figure 2: Margen de un hiperplano de separación: (a) hiperplano de separación no-óptimo y su

margen asociado τ (no máximo) (b) hiperplano de separación óptimo y su margen asociado máximo,
τmáx .

clase +1 una distancia tal que la distancia del hiperplano a dicho ejemplo sea mayor que antes
y, a su vez, siga siendo menor que la distancia al ejemplo más cercano de la clase −1. Se
llega así al absurdo de poder aumentar el tamaño del margen cuando, de partida, habíamos
supuesto que éste era máximo (hiperplano óptimo). Se aplica un razonamiento similar en el
caso de suponer que la distancia del hiperplano óptimo al ejemplo más cercano de la clase −1
fuese menor que la correspondiente al ejemplo más cercano de la clase +1.
Por geometría, se sabe que la distancia entre un hiperplano de separación D(x) y un
ejemplo x0 viene dada por:

|D(x0 )|
Distancia D(x), x0 = (10)
kwk

siendo |·| el operador valor absoluto, k·k el operador norma de un vector y w el vector que,
junto con el parámetro b, dene el hiperplano D(x) y que, además, tiene la propiedad de ser
perpendicular al hiperplano considerado. Haciendo uso de la denición de margen máximo y
de la expresiones (9) y (10), todos los ejemplos de entrenamiento cumplirán que la distancia
de cada uno de ellos al hiperplano de separación óptimo es mayor o igual que dicho margen,
es decir:
yi D(xi )
≥ τ, i = 1, . . . , n (11)
kwk
En particular, los ejemplos situados justo en la frontera que delimita el margen a cada
lado del hiperplano de separación reciben el nombre de vectores soporte (ver g. 3) y, por
denición, cumplen que:

yi D(xi )
= τ, ∀i ∈ VS (12)
kwk
donde VS denota el conjunto de todos los vectores soporte. Puesto que dichos vectores son
los ejemplos más cercanos al hiperplano de separación, serán los más difíciles de clasicar y,
por tanto, deberían ser los únicos ejemplos a considerar a la hora de construir dicho hiperplano.

6
 1 / ||w||
D(x)> +1

|D(xi)| / ||w||
1
)= +
D(x (x)=0
im o, D xi
o óp t
lan 1
er p x )= -
Hip D(
D(x)< -1

Figure 3: La distancia de cualquier ejemplo,xi , al hiperplano de separación óptimo viene dada por
|D(xi )| / kwk. En particular, si dicho ejemplo pertenece al conjunto de vectores soporte (identicados
por siluetas sólidas), la distancia a dicho hiperplano será siempre 1/ kwk. Además, los vectores soporte
aplicados a la función de decisión siempre cumplen que |D(x)| = 1.

De hecho, se demostrará más adelante, en esta misma sección, que el hiperplano de separación
óptimo se dene sólo a partir de los vectores soporte.
De la expresión (12), se deduce que maximizar el margen, τ, es equivalente a minimizar
kwk. Sin embargo, existen innitas formas de denir un mismo hiperplano y que dieren solo
en la escala de w. Así, por ejemplo, todas las funciones lineales λ (< w, x > +b), con λ ∈ R,
representan el mismo hiperplano. Para limitar, por tanto, el número de soluciones a una sola,
la escala del producto de τ y la norma de w se ja, de forma arbitraria, a la unidad, es decir:

τ kwk = 1 (13)

Entonces, en este caso, la condición (11), se transforma en:

yi D(xi ) ≥ 1, i = 1, . . . , n (14)

o, lo que es lo mismo, en:

yi (< w, xi > +b) ≥ 1, i = 1, . . . , n (15)

En denitiva, la búsqueda del hiperplano óptimo para el caso que nos ocupa, es decir,
clasicación binaria de ejemplos linealmente separables, puede ser formalizado como el pro-
blema de encontrar los valores w y b que minimizan el funcional f (w) = kwk sujeto a las
restricciones dadas por (15) o, de forma equivalente , como:
1

min 1
2 kwk2 ≡ 1
2 < w, w >
(16)
s.a. yi (< w, xi > +b) − 1 ≥ 0, i = 1, . . . , n
1
Obsérvese que es equivalente minimizar f (w) = kwk o el funcional 1/2 kwk2 propuesto en (16). El proceso
de minimización de este nuevo funcional equivalente, en lugar del original, permitirá simplicar la notación
posterior, obteniendo expresiones más compactas.

7
 Este problema de optimización con restricciones corresponde a un problema de programa-
ción cuadrático y es abordable mediante la teoría de la optimización. Tal y como se mencionó
en la sección 2, dicha teoría establece que un problema de optimización, denominado primal,
tiene una forma dual si la función a optimizar y las restricciones son funciones estrictamente
convexas. En estas circunstancias, resolver el problema dual permite obtener la solución del
problema primal.
Así, puede demostrarse que el problema de optimización dado por (16) satisface el criterio
de convexidad y, por tanto, tiene un dual. En estas condiciones, y aplicando los resultados
descritos en la sección 2, se pueden aplicar los siguientes pasos encaminados a transformar el
problema primal en su dual:
En primer lugar, se construye la función lagrangiana :
2

n
1 X
L (w, b, α) = < w, w > − αi [yi (< w, xi > +b) − 1] (17)
2
i=1

donde αi ≥ 0 son los denominados multiplicadores de Lagrange.

A continuación, se aplican las condiciones de Karush-Kuhn-Tucker (KKT):

n
∂L (w, b, α) X
≡w− αi yi xi = 0 (18)
∂w
i=1

n
∂L (w, b, α) X
≡ αi yi = 0 (19)
∂b
i=1

αi [1 − yi (< w, xi > +b)] = 0, i = 1, . . . , n (20)

Las restricciones (18) y (19) corresponden al resultado de aplicar la primera condición KKT
y, las expresadas por (20), al resultado de aplicar la denominada condición complementaria
(segunda condición KKT). Concretamente, la restricción dada por (18) permite expresar w
en términos de αi :
n
X
w= αi yi xi (21)
i=1

la restricción dada por (19), establece una restricción adicional para los coecientes αi :
n
X
αi yi = 0 (22)
i=1

y, nalmente, las dadas por (20), tal y como se verá más adelante, permitirán obtener el valor
de b.
Para construir el problema dual se realizan los siguientes pasos. En primer lugar, se hace
uso de (21) para expresar la función lagrangiana sólo en función de αi . Antes de ello, se puede
reescribir (17) como:

n n n
1 X X X
L (w, b, α) = < w, w > − αi yi < w, xi > −b αi yi + αi
2
i=1 i=1 i=1
2
El signo menos del segundo sumando es debido a que las restricciones de (16) están expresadas como
restricciones del tipo g(x) ≥ 0 en lugar de g(x) ≤ 0 .

8
Además, teniendo en cuenta las restricciones (22), el tercer sumando de la parte de la derecha
de la expresión anterior es nulo y, por tanto, la anunciada substitución de (21) en dicha
expresión resulta ser:

n
! n

n
! n

n
1 X X X X X
L (α) = αi yi xi  αj yj xj  − αi yi xi  αj yj xj  + αi
2
i=1 j=1 i=1 j=1 i=1

n
! n 
n
1 X X X
L (α) = − αi yi xi  αj yj xj +
 αi
2
i=1 j=1 i=1
n n
X 1X
L (α) = αi − αi αj yi yj < xi , xj > (23)
2
i=1 i=1

De esta forma, se obtiene el problema dual, consistente en encontrar un α∗ que maximice

la función (23) sujeto a las restricciones dadas por (22) y a aquellas otras asociadas a los
multiplicadores de Lagrange (αi ≥ 0), es decir:

max L (α) = ni=1 αi − 21 ni,j=1 αi αj yi yj < xi , xj >

P P

Pn (24)
s.a. i=1 αi yi=0
αi ≥ 0, i = 1, . . . , n

Al igual que el problema primal, este problema es abordable mediante técnicas estándar de
programación cuadrática, pero con la particularidad de que suele ser más fácil de solucionar.
Además, como se puede comprobar, el tamaño del problema de optimización dual escala con
el número de muestras, n, mientras que el problema primal lo hace con la dimensionalidad, d.
Esta propiedad también es importante porque el coste computacional asociado a su resolución
es factible incluso para problemas con un número muy alto de dimensiones.
La solución del problema dual, α∗ , nos permitirá obtener la solución del problema pri-
mal. Para ello, bastará sustituir dicha solución en la expresión (21) y, nalmente, sustituir el
resultado así obtenido en (6), es decir:

n
X
D(x) = αi∗ yi < x, xi > +b∗ (25)
i=1

Para que la denición del hiperplano (25) sea completa, es preciso determinar el valor del
parámetro b∗ . Para ello, se hará uso de las restricciones expresadas en (20), resultantes de
aplicar la segunda condición KKT. Así, dado que αi ≥ 0, se puede armar que si αi >
0, entonces el segundo factor de la parte izquierda de dichas restricciones tendrá que ser
forzosamente cero, para garantizar así el cumplimiento de las mismas y, por tanto:

yi (< w∗ , xi > +b∗ ) = 1 (26)

es decir, todos aquellos (xi , yi ) que tienen asociado un αi > 0, satisfacen la restricción i-ésima
dada por (15), pero considerando el caso igual que. Por denición, los ejemplos que satisfacen
(15), considerando el caso igual que, son los vectores soporte y, por consiguiente, se puede
armar que sólo los ejemplos que tengan asociado un αi > 0 serán vectores soporte. De este
resultado, también puede armarse que el hiperplano de separación (25) se construirá sólo

9
como una combinación lineal de los vectores soporte, ya que el resto de ejemplos del conjunto
de entrenamiento tendrán asociado un αj = 0.
Utilizando los resultados anteriores, se está ya en disposición de calcular el valor de b∗ .
Para ello, bastará despejarlo de la ec. (26):

b∗ = yvs − < w∗ , xvs > (27)

donde (xvs , yvs ) representa la tupla de cualquier vector soporte, junto con su valor de clase, es
decir, la tupla de cualquier ejemplo que tenga asociado un αi distinto de cero. En la práctica,
es
∗
más robusto obtener el valor de b a partir del promediado de todos los vectores soporte.
Así, la expresión (27) se puede sustituir por esta otra:

1 X
b∗ = (yj − < w∗ , xj >) (28)
NVS
j∈VS

donde VS es el conjunto de vectores soporte y NVS es la cardinalidad de dicho conjunto.

Además, si también se quiere obtener una expresión para calcular el valor de b∗ a partir
∗
de la solución obtenida en el problema dual, α , bastará sustituir el resultado de (21) en la
ec. (27), o en la ec. (28).
Por último, obsérvese que tanto la denición del problema dual (24) como la del hiperplano
de separación óptimo (25) dependen del producto escalar de los vectores ejemplos. Esta
propiedad se utilizará más tarde (sección 5) para calcular hiperplanos de separación óptimos
en espacios transformados de alta dimensionalidad.

4 SVM para clasicación binaria de ejemplos cuasi-separables

linealmente
El problema planteado en la sección anterior tiene escaso interés práctico porque los problemas
reales se caracterizan normalmente por poseer ejemplos ruidosos y no ser perfecta y linealmente
separables. La estrategia para este tipo de problemas reales es relajar el grado de separabilidad
del conjunto de ejemplos, permitiendo que haya errores de clasicación en algunos de los
ejemplos del conjunto de entrenamiento. Sin embargo, sigue siendo un objetivo el encontrar
un hiperplano óptimo para el resto de ejemplos que sí son separables.
Desde el punto de vista de la formulación vista en la sección anterior, un ejemplo es no-
separable si no cumple la condición (15). Aquí se pueden dar dos casos. En el primero, el
ejemplo cae dentro del margen asociado a la clase correcta, de acuerdo a la frontera de decisión
que dene el hiperplano de separación. En el otro caso, el ejemplo cae al otro lado de dicho
hiperplano. En ambos casos se dice que el ejemplo es no-separable, pero en el primer caso es
clasicado de forma correcta y, en el segundo, no lo es (ver g. 4).
La idea para abordar este nuevo problema es introducir, en la condición (15), que dene
al hiperplano de separación, un conjunto de variables reales positivas, denominadas variables
de holgura, ξi , i = 1, . . . n, que permitirán cuanticar implícitamente el número de ejemplos
no-separables que se está dispuesto a admitir, es decir:

yi (< w, xi > +b) ≥ 1 − ξi , ξi ≥ 0, i = 1, . . . , n (29)

Por tanto, para un ejemplo (xi , yi ), su variable de holgura, ξi , representa la desviación del
caso separable, medida desde el borde del margen que corresponde a la clase yi (ver g.
4). De acuerdo a esta denición, variables de holgura de valor cero corresponden a ejemplos

10
 xk

ξk=1+|D(xk)|

D(x)> +1
ξj=1+|D(xj)|

xj
)= +1
D(x xi
ξi=1-|D(xi)|
0 xi
)=
D(x 1
( x )= -
D
D(x)< -1

Figure 4: En el caso de ejemplos no-separables, las variables de holgura miden la desviación desde
el borde del margen de la clase respectiva. Así, los ejemplos xi , xj y xk son, cada uno de ellos, no-
separables (ξi , ξj , ξk > 0. Sin embargo, xi está correctamente clasicado, mientras que xj y xk están
en el lado incorrecto de la frontera de decisión y, por tanto, mal clasicados.

separables, mayores que cero y menores o iguales a uno corresponden a ejemplos no separables,
pero bien clasicados, y mayores que uno corresponden a ejemplos no separables y, además,
Pn
mal clasicados. Por tanto, la suma de todas las variables de holgura, i=1 ξi , permite, de
alguna manera, medir el coste asociado al número de ejemplos no-separables. Así, en una
primera aproximación, cuanto mayor sea el valor de esta suma, mayor será el número de
ejemplos no separables.
Relajadas las restricciones, según (29), ya no basta con plantear como único objetivo
maximizar el margen, ya que podríamos lograrlo a costa de clasicar erróneamente muchos
ejemplos. Por tanto, la función a optimizar debe incluir, de alguna forma, los errores de
clasicación que está cometiendo el hiperplano de separación, es decir:

n
1 X
f (w, ξ) = kwk2 + C ξi (30)
2
i=1

donde C se denomina parámetro de regularización, cuyo valor es elegido por el usuario y

permite controlar en qué grado inuye el término del coste de ejemplos no-separables en
la minimización de la norma, es decir, permitirá regular el compromiso entre el grado de
sobreajuste del clasicador nal y la proporción del número de ejemplos mal clasicados. Así,
un valor de C muy grande permitiría valores de ξi muy pequeños y, en este caso, la anchura
del margen óptimo será normalmente estrecha y, además, el modelo aprendido sería más
simple, pero podría estar demasiado sobreajustado a los datos de entrenamiento. En el límite
(C → ∞), estaríamos considerando el caso de ejemplos perfectamente separables (ξi → 0).
Por contra, valores de C pequeños permitirán valores de ξi más grandes, es decir, estaríamos
admitiendo anchuras de margen óptimo más grandes, pero a costa de admitir ejemplos dentro
del margen e, incluso, mal clasicados. A su vez, esto produce modelos más complejos, al
depender éstos de un número mayor de vectores soporte. En el caso límite (C → 0), todos los

11
ejemplos estarían situados dentro del margen y el número de ejemplos mal clasicados sería
máximo (ξi → ∞). Actualmente, dado un conjunto de ejemplos de entrenamiento, no existe
una forma teórica de encontrar el valor óptimo de C .
En consecuencia, el nuevo problema de optimización consistirá en encontrar el hiperplano,
denido por w y b, que minimiza el funcional (30) y sujeto a las restricciones dadas por (29),
es decir Pn
1
min 2 < w, w > +C i=1 ξi

(31)
s.a. yi (< w, xi > +b) + ξi − 1 ≥ 0
ξi ≥ 0, i = 1, . . . , n
El hiperplano así denido recibe el nombre de hiperplano de separación de margen blando
(del inglés soft margin ), en oposición al obtenido en el caso perfectamente separable, también
conocido como hiperplano de separación de margen duro (del inglés hard margin ). Como en
el caso de la sección anterior, el problema de optimización original (problema primal) será
transformado a su forma dual. El procedimiento para obtener el hiperplano de separación es
similar al allí utilizado. Por tanto, aquí sólo se reproducirán de forma esquemática y secuencial
los pasos necesarios para realizar dicha transformación.
Paso 1: Obtención de la función lagrangiana :
3

n n n
1 X X X
L (w, b, ξ, α, β) = < w, w > +C ξi − αi [yi (< w, xi > +b) + ξi − 1] − βi ξi (32)
2
i=1 i=1 i=1

Paso 2: Aplicación de las condiciones KKT:

n
∂L X
≡ w∗ − αi yi xi = 0 (33)
∂w
i=1
n
∂L X
≡ α i yi = 0 (34)
∂b
i=1
∂L
≡ C − αi − βi = 0 i = 1, . . . , n (35)
∂ξi
αi [1 − yi (< w∗ , xi > +b∗ ) − ξi ] = 0, i = 1, . . . , n (36)

βi · ξi = 0, i = 1, . . . , n (37)

Paso 3: Establecer las relaciones entre las variables del problema primal (w, b, ξ) con las
del problema dual (α, β). Para ello, hacemos uso de la relacion (33):

n
X
w∗ = αi yi xi (38)
i=1

Paso 4: Establecer restricciones adicionales de las variables duales. Para ello se hace uso
de las relaciones (34-35):
n
X
α i yi = 0 (39)
i=1
3
Obsérvese que, en este caso, aparecen dos familias de multiplicadores de Lagrange, αi ≥ 0 y βi ≥ 0, con
i = 1, . . . , n, como consecuencia de las dos familias de restricciones que aparecen en (31). Nuevamente, el signo
menos del tercer y cuarto sumando obedece a que las dos familias de restricciones en (31) están expresadas
como restricciones del tipo g(x) ≥ 0 en lugar de g(x) ≤ 0 .

12
 C = αi + βi i = 1, . . . , n (40)

Paso 5: Del resultado obtenido en el paso 3, eliminar las variables primales de la función
lagrangiana para obtener así el problema dual que queremos maximizar:

n n
X 1 X
L (α) = αi − αi αj yi yj < xi , xj >
2
i=1 i,j=1

Finalmente, se obtiene la formalización buscada del problema dual :

4

Pn 1 Pn
max i=1 αi − 2 i,j=1 αi αj yi yj < xi , xj >
Pn (41)
s.a. i=1 αi yi
=0
0 ≤ αi ≤ C, i = 1, . . . , n

Como en el caso anterior, la solución del problema dual nos permitirá expresar el hiperplano
de separación óptima en términos de α∗ . Para ello, bastará tener en cuenta dicha solución y
sustituir la expresión (38) en (6), es decir:

n
X
D(x) = αi∗ yi < x, xi > +b∗ (42)
i=1

Antes de obtener una expresión para el cálculo del valor de b∗ , se considerarán algunos resul-
tados interesantes. Así, de la restricción (40) es fácil deducir que si αi = 0, entonces C = βi .
De este último resultado y de la restricción (37) se deduce que ξi = 0. Por tanto, se puede
armar que todos los ejemplos xi cuyo αi asociado sea igual a cero corresponden a ejemplos
separables (ξi = 0).
Por otro lado, todo ejemplo no separable, xi , se caracteriza por tener asociado un ξi > 0
(ver g. 4). En este caso, y de la restricción (37), se deduce que βi = 0. A su vez, de este
último resultado y la restricción (40), se deduce que αi = C . Por tanto, se puede armar que
todos los ejemplos xi cuyo αi = C corresponderán a ejemplos no-separables (ξi > 0). Además,
dado que, en este caso, αi 6= 0, de la restricción (36) se deduce que:

1 − yi (< w∗ , xi > +b∗ ) − ξi = 0

es decir:
1 − yi D(xi ) = ξi
Aquí se pueden considerar dos casos (ver g. 4). En el primero, el ejemplo, xi , aunque no
separable, está bien clasicado, es decir, yi D(xi ) ≥ 0, entonces ξi = 1 − |D(xi )| y, por tanto,
0 ≤ ξi ≤ 1. En el segundo caso, el ejemplo, xi , es no separable y está mal clasicado, es decir,
yi D(xi ) < 0, entonces ξi = 1 + |D(xi )| y, por tanto, ξi > 1..
Finalmente, consideremos el caso 0 < αi < C . Así, en esta situación, la restricción (40)
permite armar que βi 6= 0 y, de este resultado y la restricción (37), se deduce que ξi = 0.
Igualmente, si 0 < αi < C , de la restricción (36) y del resultado obtenido anteriormente
(ξi = 0), se deduce que:
1 − yi (< w∗ , xi > +b∗ ) = 0
4
La restricción de que αi ≤ C se obtiene de (40) y de las condiciones αi , βi ≥ 0

13
es decir, que el ejemplo xi pertenece a la frontera del margen. Por tanto, se puede armar
que un ejemplo, xi , es vector soporte si y solo si 0 < αi < C .
De la expresión anterior, se está ya en disposición de calcular el valor b∗ , es decir

b∗ = yi − < w∗ , xi > ∀i t.q. 0 < αi < C (43)

Obsérvese que, a diferencia del caso linealmente separable, ahora, para el cálculo de b∗ , no
es suciente con elegir cualquier ejemplo xi que tenga asociado un αi > 0. En este caso, la
restricción es más fuerte, es decir, 0 < αi < C .
Como en el caso linealmente separable, también se puede obtener b∗ de forma más precisa
realizando un promediado, es decir:

1 X
b∗ = (yj − < w∗ , xj >) (44)
NVS0 0 j∈VS

donde VS0 es el conjunto de ejemplos que tienen asociado un αi t.q. 0 < αi < C y NVS0 es la
cardinalidad de dicho conjunto.
Finalmente, haciendo uso de (38), es posible también expresar b∗ en términos de las varia-
bles duales:
n
X
b∗ = yi − αi∗ yi < xj , xi > ∀αi t.q. 0 < αi < C (45)
j=1

donde los coecientes αi∗ , i = 1, . . . , n, corresponden a la solución del problema dual.

A modo de resumen, en el caso de ejemplos linealmente cuasi-separables, hay dos tipos de
vectores soporte para los que los αi∗ 6= 0. Aquellos para los que 0 < αi∗ < C , que corresponden
a ejemplos situados en la frontera del margen a cada lado del hiperplano y aquellos para los
que αi∗ = C , asociados a ejemplos no separables. Esto últimos reciben el nombre de vecto-
res soporte ligados (del inglés bounded support vectors ). Ambos tipos de vectores soporte
(ejemplos) intervienen en la construcción del hiperplano de separación. El problema dual del
caso linealmente cuasi-separable (41) y el correspondiente al caso linealmente separable (24)
son prácticamente iguales. La única diferencia radica en la inclusión de la constante C, cuyo
valor es elegido por el usuario.

5 SVM para clasicación binaria de ejemplos no separables li-

nealmente
En las dos secciones anteriores se ha mostrado que los hiperplanos de separación son buenos
clasicadores cuando los ejemplos son lineal o cuasi-linealmente separables. También se vio
que el proceso de búsqueda de los parámetros que denen dichos hiperplanos se puede hacer,
desde el punto de vista del problema dual, independientemente de la dimensionalidad del pro-
blema a resolver. No obstante, los resultados obtenidos en las dos secciones anteriores no son
directamente aplicables cuando los ejemplos a clasicar no son linealmente separables. En esta
sección se abordará precisamente como adaptar dichos resultados a este último caso. Para ello,
se describirá cómo usar de forma eciente conjuntos de funciones base, no lineales, para denir
espacios transformados de alta dimensionalidad y cómo buscar hiperplanos de separación ópti-
mos en dichos espacios transformados. A cada uno de estos espacios se le denominará espacio
de características, F , para diferenciarlo del espacio original al que pertenecen los ejemplos de
entrada (espacio-x).

14
 Espacio de entradas Espacio de características Espacio de entradas
X1 X1
Φ1(x)

X2 Φ2(x) X2

χ
-1
Φ :F X
χ Φ: X F F
x = (x1,x2) Φ(x) = [Φ 1(x), Φ2(x)] x = (x1,x2)

Figure 5: El problema de la búsqueda de una función de decisión no lineal en el espacio del conjunto
de ejemplos original (espacio de entradas), se puede transformar en un nuevo problema consistente en
la búsqueda de una función de decisión lineal (hiperplano) en un nuevo espacio transformado (espacio
de características). Dicho hiperplano se transforma en una función de decisión no lineal en el espacio de
entradas original. Normalmente, la dimensión del espacio de características suele ser bastante mayor
que la del espacio original.

SeaΦ : X → F una función de transformación que hace corresponder cada vector de

entrada x con un punto en el espacio de características F , donde Φ(x) = [φ1 (x), . . . , φm (x)] y
∃φi (x), i = 1, ..., m, tal que φi (x) es una función no lineal. La idea es construir un hiperplano
de separación lineal en este nuevo espacio. Finalmente, la frontera de decisión lineal obtenida
en el espacio de características se transformará en una frontera de decisión no lineal en el
espacio original de entradas (ver g. 5).
En este contexto, la función de decisión (6) en el espacio de características vendrá dada
5
por :
D(x) = (w1 φ1 (x) + ... + wm φm (x)) =< w, Φ(x) > (46)

y, en su forma dual, la función de decisión se obtiene transformando convenientemente la

expresión de la frontera de decisión (42) en:

n
X
D(x) = αi∗ yi < Φ(x), Φ(xi ) > (47)
i=1

Como se verá a continuación, el producto escalar < Φ(x), Φ(xi ) > se calculará a partir de
lo que se denomina función kernel.

Función kernel
Por denición, una función kernel es una función K : X×X → R que asigna a cada par de
elementos del espacio de entrada, X, un valor real correspondiente al producto escalar de las
imágenes de dichos elementos en un nuevo espacio F (espacio de características), es decir,

K(x, x0 ) =< Φ(x), Φ(x0 ) >= φ1 (x)φ1 (x0 ) + ... + φm (x)φm (x0 )


(48)

5
Obsérvese que se ha prescindido del termino b puesto que éste puede ser representado incluyendo en la
base de funciones de transformación la función constante φ1 (x) = 1 y aumentando en uno la dimensión del
vector w, es decir, w ∈ Rd+1 .

15
donde Φ:X→F .
Por tanto, una función kernel puede sustituir convenientemente el producto escalar en (47),
es decir:
n
X
D(x) = αi∗ yi K(x, xi ) (49)
i=1

Por tanto, dado el conjunto de funciones base, Φ = {φ1 (x), . . . , φm (x)}, el problema a
resolver sigue siendo encontrar el valor de los parámetros αi∗ , i = 1, . . . n, que optimiza el
problema dual (41), pero expresado ahora como:

Pn 1 Pn
max i=1 αi − 2 i,j=1 αi αj yi yj K(xi , xj )

Pn (50)
s.a. i=1 αi yi
=0
0 ≤ αi ≤ C, i = 1, . . . , n

Se está ya en disposición de describir la metodología necesaria para resolver un problema

de clasicación de ejemplos no separables linealmente. Concretamente, la función de decisión
vendrá dada por la expresión (49), donde el valor de los parámetros αi , i = 1, . . . n, se obtendrán
como solución al problema de optimización cuadrática dado por (50), conocidos el conjunto de
ejemplos de entrenamiento (xi , y) , i = 1, . . . , n, el kernel K, y el parámetro de regularización
C.
A modo de ejemplo, supongamos el caso de vectores de entrada de dos dimensiones, x=
(x1 , x2 ), y el conjunto de funciones base formado por todos los polinomios de grado tres, es
decir,
φ1 (x1 , x2 ) = 1 φ2 (x1 , x2 ) = x1 φ3 (x1 , x2 ) = x2
φ4 (x1 , x2 ) = x1 x2 φ5 (x1 , x2 ) = x21 φ6 (x1 , x2 ) = x22
φ7 (x1 , x2 ) = x21 x2 φ8 (x1 , x2 ) = x1 x22 φ9 (x1 , x2 ) = x31
φ10 (x1 , x2 ) = x32
En este caso, cada entrada de dos dimensiones es transformada en un espacio de características
de diez dimensiones. La idea es entonces buscar un hiperplano en el espacio de características
que sea capaz de separar los ejemplos transformados. A su vez, la frontera de decisión lineal
asociada a dicho hiperplano se transformará en un límite de decisión polinomial de grado tres
en el espacio de entradas. Obsérvese también que si, en este ejemplo, un problema de tan solo
dos dimensiones se transforma en uno de diez, un pequeño aumento en la dimensionalidad
del espacio de entrada puede provocar un gran aumento en la dimensionalidad del espacio
de características. En el caso límite, existen incluso espacios de características de dimensión
innita. Es por esta razón por la que, ahora, el problema de optimización se expresa sólo en
su forma dual, ya que, como se ha visto en las dos secciones anteriores, la solución de este
problema no depende de la dimensionalidad del espacio sino de la cardinalidad del conjunto
de vectores soporte.
Sin embargo, si la transformación del espacio de entradas al espacio de características
puede denirse a partir de un conjunto innito de funciones base, surge la pregunta de cómo
transformar los ejemplos de entrada, de dimensión nita, en otro espacio de dimensión innita.
El siguiente teorema responde a esta pregunta.

16
 Teorema de Aronszajn. Para cualquier función K : X × X → R que sea simétrica 6 y
semidenida positiva 7 , existe un espacio de Hilbert y una función Φ : X → F tal que

K(x, x0 ) =< Φ(x), Φ(x0 ) > ∀x, x0 ∈ X (51)

Una consecuencia importante de este teorema es que para construir una función kernel no
es necesario hacerlo a partir de un conjunto de funciones base, Φ(x) = (φ1 (x), . . . , φm (x)),
simplemente basta denir una función que cumpla las dos condiciones del teorema: la función
kernel, K , tiene que ser simétrica y semidenida positiva). Por tanto, para evaluar una función
kernel no se necesitará conocer dicho conjunto de funciones base y, aún conocido éste, tampoco
sería necesario realizar explícitamente el cálculo del producto escalar correspondiente, es decir,
será suciente con evaluar dicha función kernel. En denitiva, para resolver el problema dual
(50), no sólo no se necesita conocer el conjunto de funciones base de transformación, sino que
tampoco es necesario conocer las coordenadas de los ejemplos transformados en el espacio
de características. Sólo se necesitará conocer la forma funcional del kernel correspondiente,
K : X × X → R, aún cuando éste pudiera estar asociado a un conjunto innito de funciones
base.

Ejemplos de funciones kernel

Se presentan aquí algunos ejemplos de funciones kernel:

• Kernel lineal:
KL (x, x0 ) =< x, x0 > (52)

• kernel polinómico de grado -p:

p
KP (x, x0 ) = γ < x, x0 > +τ , γ > 0

(53)

• kernel gaussiano:

 2 
KG (x, x0 ) = exp −γ x − x0 ≡ exp −γ < x − x0 , x − x0 > , γ > 0




(54)

• kernel sigmoidal:
KS (x, x0 ) = tanh(γ < x, x0 > +τ ) (55)

A los parámetros γ, τ y p se les denomina parámetros del kernel.

Ejemplo: Solución del problema OR-exclusivo mediante SVMs

El denominado problema or-exclusivo pertenece al caso de problemas no-linealmente separables

y se dene como el problema de encontrar un hiperplano de separación que clasique sin error
los ejemplos de la tabla siguiente:

6
Una función K : X × X → R es simétrica si K(x, x0 ) = K(x 0
P∀x,
Pn , x) x0 ∈ X
7
Una función K : X × X → R es semidenida positiva si i=1 i=1 ci cj K(xi , xj ) ≥ 0, para cualesquiera
n

conjuntos x1 , . . . , xn ∈ X y c1 , . . . cn ∈ R, siendo n > 0.

17
 2

1.5

0.5

x2
0

−0.5

−1

−1.5

−2
−2 −1 0 1 2
x1

Figure 6: Representación del conjunto de datos perteneciente al problema XOR.

Ejemplo (x1 , x2 ) y
1 (+1, +1) +1
2 (−1, +1) −1
3 (−1, −1) +1
4 (+1, −1) −1

De la g. 6, resulta obvio que es imposible resolver este problema con un límite de decisión
lineal en el espacio original de entradas. La solución que se propone es crear un clasicador
SVM, usando un kernel polinómico (53), con p = 2, γ = 1 y τ = 1:
2
KP (x, x0 ) = < x, x0 > +1

(56)

Los valores de αi∗ , i = 1, . . . n, corresponderán a la solución del problema dual (50), parti-
cularizado para el problema que queremos resolver, es decir

4 4
X 1 X
max αi − αi αj yi yj KP (x, xi )
2
i=1 i,j=1

4
X
s.a. αi yi = 0, 0 ≤ αi ≤ C, i = 1, . . . , 4
i=1
La solución a este problema de optimización es αi∗ = 0.125, i = 1, . . . 4. Dado que no existe
ningún i ∗
para el que αi = 0, se puede armar que todos los ejemplos del conjunto de entrena-
miento corresponden a vectores soporte. Por tanto, la función de decisión se puede obtener a
partir de (47), particularizada para la solución obtenida, α∗ , y el kernel elegido, es decir:

n
X 4
X 4
X
D(x) = αi∗ yi K(x, xi ) = 0.125 yi KP (x, xi ) = 0.125 yi [hx, xi i + 1]2 (57)
i=1 i=1 i=1

Obsérvese que con esta expresión habríamos resuelto el problema de clasicación planteado
inicialmente, es decir, bastaría evaluarla con cualquier ejemplo y asignarle la clase correspon-
diente, dependiendo de si el resultado obtenido es mayor-igual o menor-igual que cero.

18
 Sin embargo, aprovecharemos el problema XOR para obtener otros resultados relacionados
con diferentes conceptos descritos anteriormente. Así, por ejemplo, de la denición de función
kernel (48) y del kernel aquí empleado (56), es posible obtener el conjunto base de funciones
de transformación:

2
K(x, x0 ) =< Φ(x), Φ(x0 ) >= < x, x0 > +1 =


2
< (x1 , x2 ) , x01 , x02 > +1 =


2
2
x21 x01 + x22 x02 + 2x1 x2 x01 x02 + 2x1 x01 + 2x2 x02 + 1 =
 √ √ √   √ √ √
2
2 
< 1, 2x1 , 2x2 , 2x1 x2 , x21 , x22 , 1, 2x01 , 2x02 , 2x01 x02 , x01 , x02 >

es decir, Φ2 = {φ1 (x), . . . , φ6 (x)}, donde

√ √
φ1 (x1 , x2 ) = 1√ φ2 (x1 , x2 ) = 2x1 φ3 (x1 , x2 ) = 2x2 ,
(58)
φ4 (x1 , x2 ) = 2x1 x2 φ5 (x1 , x2 ) = x21 φ6 (x1 , x2 ) = x22

Utilizando este último resultado y el obtenido en (57), la función de decisión lineal en el

espacio transformado puede expresarse en función del conjunto de funciones base:

P4 P4
D(x) = 0.125 · i=1 yi KP (x, xi ) = 0.125 · i=1 yi < Φ2 (x), Φ2 (xi ) >=
√ √ √
0.125 · {[φ1 (x) + 2φ2 (x) + 2φ3 (x) + 2φ4 (x) + φ5 (x) + φ6 (x)]+
√ √ √
[(−φ1 (x)) + 2φ2 (x) − 2φ3 (x) + 2φ4 (x) − φ5 (x) − φ6 (x)]+
(59)
√ √ √
[φ1 (x) − 2φ2 (x) − 2φ3 (x) + 2φ4 (x) + φ5 (x) + φ6 (x)]+
√ √ √
[(−φ1 (x)) − 2φ2 (x) + 2φ3 (x) + 2φ4 (x) − φ5 (x) − φ6 (x)]} =
 √
√1

0.125 4 2φ4 (x) = 2
· φ4 (x)

Del resultado obtenido, se puede armar que, de las seis dimensiones del espacio de caracte-
rísticas, la función lineal de decisión en dicho espacio se expresa en términos de sólo una de
ellas, φ4 (x). Es decir, sólo se necesita una dimensión del espacio transformado para poder
separar los ejemplos del conjunto de entrenamiento original (ver g. 7a). Este hecho se con-
rma al calcular los ejemplos transformados de los ejemplos originales en el nuevo espacio de
características, mostrados en la siguiente tabla:

Ejemplo Espacio de entradas Espacio de características Clase

# (x1 , x2 ) (φ1 (x), φ2 (x), . . . , φ6 (x)) y
√ √ √

1 (+1, +1) 1, √2, √2, √ 2, 1, 1 +1


2 (−1, +1) 1, −√2, √ 2, −√2, 1, 1 −1


3 (−1, −1) 1, −
√ 2, −√ 2, √2, 1, 1
+1
4 (+1, −1) 1, 2, − 2, − 2, 1, 1 −1

19
 2
D(x1,x2)= −1 → ← D(x1,x2)= +1
1.5

1
← D(x)=0
0.5
← D(x)= −1 D(x)=+1 →

x2
0
↑
← D(x1,x2)= 0
−0.5
√ √
τ= 2 τ= 2
−1

−1.5
D(x1,x2)= +1 → ← D(x1,x2)= −1

−2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2

−2 −1.5 −1 −0.5 0 0.5 1 1.5 2
φ4(x) x1

(a) (b)

Figure 7: Solución al problema XOR: (a) hiperplano de separación en el espacio de características, junto con
su margen asociado (los cuatro ejemplos son vectores soporte) (b) función de decisión no lineal en el espacio de
ejemplos original resultante de transformar el hiperplano obtenido en (a) en coordenadas del espacio original.

Concretamente, de los resultados de dicha tabla, puede apreciarse que la cuarta componente
es lo sucientemente discriminante como para que, sólo a partir de ella, los ejemplos puedan
√
clasicarse correctamente en la clase a la que pertenecen: si
√ φ4 (x) = 2, entonces la clase es
y = +1 y si φ4 (x) = − 2, la clase es y = −1.
Para obtener la ecuación del hiperplano de separación en el espacio de características,
bastará hacer D(x) = 0 en (59), es decir:

1
√ φ4 (x) = 0 ⇒ φ4 (x) = 0
2
y para obtener las ecuaciones de las fronteras que delimitan el margen, habrá que calcular
D(x) = +1 y D(x) = −1, es decir:

√
φ4 (x) = +√2
φ4 (x) = − 2

De los resultados obtenidos y de la g. 7a, resulta fácil deducir que el valor del margen
√
máximo es τ = 2. No obstante, el valor de dicho margen máximo se puede calcular mate-
máticamente. Para ello, bastará calcular el valor de kw∗ k y aplicar (13). A su vez, el valor de
w∗ se puede obtener a partir de (21), conocidos los valores de αi∗ , i = 1, . . . 4, es decir,

4  
∗
X 1
w = αi∗ yi xi = 0, 0, 0, √ , 0, 0
i=1
2

donde los valores de xi , i = 1, . . . 4 corresponden a los valores de los ejemplos de entrenamiento

expresados respecto a las coordenadas del espacio de características (no olvidemos que es en
dicho espacio en el que se está buscando el hiperplano de separación). Se está ya en disposición
de aplicar el resultado anterior en (13), obteniendo así el valor del margen máximo, es decir:

1 √
τ= = 2
kw∗ k

20
y que coincide con el que habíamos calculado de forma gráca.
También es fácil obtener la función de decisión no lineal en el espacio original de entradas
(espacio-x) transformando convenientemente el hiperplano obtenido en el espacio de caracte-
rísticas (ver g. 7b). Para ello, basta sustituir el valor de φ4 (x), obtenido de (58), en (59), es
decir
D(x) = x1 x2
Así, las ecuaciones de las fronteras de separación vendrán dadas por D(x) = 0, es decir


 x1 = 0
x1 x2 = 0 ⇒
x2 = 0


y la de las fronteras que delimitan los márgenes por D(x) = +1 y D(x) = −1, es decir

x1 x2 = +1 ⇒ x2 = 1/x1

x1 x2 = −1 ⇒ x2 = −1/x1

6 SVM para regresión

Las máquinas de vectores soporte pueden también adaptarse para resolver problemas de regre-
sión. En estos casos, es muy común designarlas por el acrónimo SVR (del inglés Support Vector
Regression ). Así, dado un conjunto de ejemplos de entrenamiento S = {(x1 , y1 ) , . . . , (xn , yn )},
donde xi ∈ Rd e yi ∈ R, en el que se asume que los valores yi de todos los ejemplos de S
se pueden ajustar (o cuasi-ajustar) mediante una función lineal, el objetivo de la tarea de
regresión es encontrar el valor de los parámetros w = (w1 , . . . , wd ) y b que permitan denir
dicha función lineal:

f (x) = (w1 x1 + ... + wd xd ) + b =< w, x > +b (60)

Dado que en la práctica es muy difícil que los ejemplos de entrenamiento se ajusten al
modelo lineal con un error de predicción igual a cero, se recurre al concepto de margen blando,
ya utilizado anteriormente al resolver el problema de clasicación. De esta forma, se permite
cierto ruido en los ejemplos de entrenamiento y, por tanto, se puede relajar la condición del
error existente entre el valor predicho por la función y el valor real. Para ello, se utiliza la
denominada función de pérdida -insensible, L , (ver g. 8) caracterizada por ser una función
lineal con una zona insensible, de anchura 2, en la que el error es nulo, y denida por:


 0 si |y − f (x)| ≤ 
L (y, f (x)) = (61)
|y − f (x)| − 

en otro caso

La principal razón para elegir esta función es la de permitir cierta dispersión en el regresor
lineal solución, de tal forma que todos los ejemplos que quedan connados en la región tubular
denida por ± no serán considerados vectores soporte. De esta forma se reducirá signicativa-
mente el número de éstos. Además, se denen dos variables de holgura, ξi+ y ξi− , que permiten
+
cuanticar la magnitud de dicho error (ver g. 8). Así, si ξi > 0, entonces la predicción
del ejemplo, f (xi ) será mayor que su valor real, yi , en una cantidad superior a , es decir,
f (xi ) − yi > . En otro caso, su valor será cero. De forma similar, si ξi− > 0, el valor real del

21
Figure 8: SVR con margen blando. Se muestra la relación entre las variables de holgura
− +
(ξi , ξj ), asociadas a ejemplos que quedan fuera de la zona tubular -insensible, y la función
de pérdida, L .

ejemplo es mayor que su predicción en una cantidad superior a , es decir, yi − f (xi ) > . En
otro caso, su valor será cero. Dado que no puede ocurrir que la predicción de un ejemplo sea
+ −
simultáneamente mayor (ξi > 0) y menor (ξi > 0) que su valor real, se puede armar que
ξi+ · ξi− = 0.
Tal y como ocurría en el problema de clasicación con margen blando, aquí también la
suma de todas las variables de holgura permitirá, de forma implícita, medir el coste asociado
al número de ejemplos con un error de predicción no nulo. Por tanto, la función a optimizar
será la misma que la del problema de clasicación con margen blando (30), con la salvedad de
que aquí tenemos dos tipos de variables de holgura en lugar de uno. En denitiva, el problema
primal, en el caso de regresión lineal, queda denido como:

Pn
1
ξi+ + ξi−


min 2 < w, w > +C i=1

s.a. (< w, xi > +b) − yi −  − ξi+ ≤ 0 (62)

yi − (< w, xi > +b) −  − ξi− ≤ 0
ξi+ , ξi− ≥ 0, i = 1, . . . , n

La transformación al problema dual requiere los mismos pasos que se han seguido hasta ahora
en secciones anteriores, es decir:
Paso 1: Obtención de la función lagrangiana

Pn Pn
L w, b, ξ + , ξ − , α+ , α− , β + , β − = 1
ξi+ + ξi− +



2 < w, w > +C i=1 i=1
Pn +
(< w, xi > +b) − yi −  − ξi+ +
 
i=1 αi
(63)
Pn −
ξi−
 
i=1 αi yi − (< w, xi > +b) −  − −
Pn + + Pn − −
i=1 βi ξi − i=1 βi ξi

22
 Paso 2: Aplicación de las condiciones de KKT:

n n
∂L X X
≡w+ αi+ xi − αi− xi = 0 (64)
∂w
i=1 i=1

n n
∂L X + X −
≡ αi − αi = 0 (65)
∂b
i=1 i=1
∂L
≡ C − αi+ − βi+ = 0, i = 1, . . . , n (66)
∂ξi+
∂L
≡ C − αi− − βi− = 0, i = 1, . . . , n (67)
∂ξi−
αi+ (< w∗ , xi > +b∗ ) − yi −  − ξi+ = 0, i = 1, . . . , n
 
(68)

αi− yi − (< w∗ , xi > +b∗ ) −  − ξi− = 0, i = 1, . . . , n

 
(69)

βi+ ξi+ = 0, i = 1, . . . , n (70)

βi− ξi− = 0, i = 1, . . . , n (71)

−
w, b, ξ + , ξ


Paso 3: Establecer las relaciones entre las variables del problema primal con
α+ , α− , β + , β − . Para ello, se hace uso de (64):


las del problema dual

n
X
αi− − αi+ xi


w= (72)
i=1

Paso 4: Establecer restricciones adicionales de las variables duales. Para ello se hace uso
de (65)-(67), es decir:
n
X
αi+ − αi− = 0


(73)
i=1

βi+ = C − αi+ , i = 1, . . . , n (74)

βi− = C − αi− , i = 1, . . . , n (75)

Paso 5: Del resultado obtenido en el paso 3, eliminar las variables primales de la función
lagrangiana:
Pn
L (α+ , α− ) = αi− − αi+ yi −  ni=1 αi− + αi+ −

P

i=1
(76)
Pn
 
1
2 i,j=1 αi− − αi+ αj− − αj+ < xi , xj >

Finalmente, se obtiene la formalización buscada del problema dual :

8

Pn − +
 ni=1 αi− + αi+ −
P


max i=1 αi − αi yi − 
1 Pn − +

−
2 i,j=1 αi − αi αj − αj+ < xi , xj >
(77)
Pn + −


s.a. i=1 αi − αi =0
0 ≤ αi+ , αi− ≤ C, i = 1, . . . , n
8
La restricción de que αi+ ≤ C se obtiene de (74) y de αi+ , βi+ ≥ 0. Igualmente, la restricción αi− ≤ C se
obtiene de (75) y de αi− , βi− ≥ 0

23
 El regresor asociado a la función lineal buscada resulta ser

n
X
αi∗− − α∗+ < x, xi > +b∗


f (x) = i (78)
i=1

donde α∗+ y α∗− son los vectores solución del problema dual. La obtención del valor de
b∗ , como en el caso de clasicación, se puede obtener de las restricciones resultantes de aplicar
la segunda condición KKT (68)-(71). No obstante, antes de ello, se puede obtener otros
resultados interesantes. Así, el uso de las restricciones (74) y (75) permiten, respectivamente,
reescribir las restricciones (70) y (71) como:

C − αi+ ξi+ = 0


(79)

C − αi− ξi− = 0


(80)

De otro lado, se puede armar que si un ejemplo (xi , yi ) está dentro de la zona tubular -
insensible, es decir, ξi− = 0 y ξi+ = 0 y, además, no pertenece a la frontera de dicha zona,
entonces el segundo factor de la parte izquierda de las restricciones (68) y (69) es siempre
distinto de cero y, por tanto, para que se cumplan dichas restricciones, tiene que ocurrir que
αi+ = 0 y αi− = 0, respectivamente.
Obsérvese también que si αi+ > 0, entonces el segundo factor de la parte izquierda de la
restricción (68) tiene que ser nulo para cumplir la restricción, es decir:

(< w∗ , xi > +b∗ ) − yi −  − ξi+ = 0 si αi+ > 0 (81)

De otro lado, si αi+ < C , entonces el segundo factor de la restricción (79) tiene que ser también
nulo, es decir:
ξi+ = 0 si αi+ < C (82)

Por tanto, se pueden combinar los resultados obtenidos en las dos expresiones anteriores de la
siguiente forma:
(< w∗ , xi > +b∗ ) − yi −  = 0 si 0 < αi+ < C (83)

Igualmente, si hubiéramos trabajado con el caso αi− > 0 junto a la restricción (69) y αi− < C
junto a la restricción (80), el resultado obtenido sería:

yi − (< w∗ , xi > +b∗ ) −  = 0 si 0 < αi− < C (84)

Obsérvese que los únicos ejemplos que cumplen las restricciones expresadas en (83) y (84)
son aquellos situados justo en la frontera de la zona tubular, es decir, los que en secciones
anteriores hemos denominado vectores soporte. Además, de cualquiera de dichas expresiones,
se puede obtener una fórmula para el cálculo del valor de b∗ :

b∗ = yi + − < w∗ , xi > si 0 < αi+ < C (85)

b∗ = yi − − < w∗ , xi > si 0 < αi− < C (86)

A pesar de las dos fórmulas obtenidas para calcular el parámetro b∗ , el valor de éste siempre
será único. De hecho, las condiciones asociadas a las expresiones (85) y (86) no pueden ser
ciertas simultáneamente. Efectivamente, si 0 < αi+ < C , implica que el segundo factor de la
restricción (68) es nulo, pero el correspondiente de la restricción (69) es no nulo y, por tanto,
para que se cumpla esta última, αi− = 0. El mismo razonamiento aplica en caso contrario, es
decir, si 0< αi− < C, entonces αi+ = 0.

24
 Finalmente, a partir de (79) y (80), se puede armar que si un ejemplo (xi , yi ) esta fuera
de la zona tubular -insensible, es decir, ξi− = 0 y ξi+ > 0 o ξi− > 0 y ξi+ = 0, entonces αi+ = C
(primer caso) o αi− = C (segundo caso). Los ejemplos que cumplen estas condiciones son los
equivalentes a los que en la sección 4 denominábamos vectores soporte ligados. Al igual que
+ −
el caso anterior, los valores de αi y αi no pueden ser simultáneamente diferentes de cero, es
+ − − +
decir, si αi = C , entonces αi = 0 y, a la inversa, si αi = C , entonces αi = 0.
Resumiendo, se puede armar que sólo los ejemplos que quedan en la frontera o fuera de la
zona tubular contribuyen a la construcción del hiperplano, dado que para el resto de ejemplos
los valores de alfa asociados son αi+ = αi− = 0. En cambio, en el primer caso mencionado
(vectores soporte), los valores alfa asociados están acotados por: 0 < αi+ < C y αi− = 0 ó
0 < αj− < C y αj+ = 0 y, en el segundo caso (vectores soporte
+ −
ligados), por: αi = C y αi = 0
− +
ó αj = C y αj = 0.

Kernelización de las SVR

En el caso de que los ejemplos no puedan ajustarse por una función lineal, se recurre a una
metodología similar a la utilizada en el problema de clasicación para ejemplos no separables
linealmente. Es decir, los ejemplos pertenecientes al espacio original de entradas se transforman
en un nuevo espacio (espacio de características), en el que sí es posible ajustar los ejemplos
transformados mediante un regresor lineal. El tipo de transformación dependerá del kernel
utilizado (ver seccion 5). El regresor asociado a la función lineal en el nuevo espacio es:

n
X
αi∗− − α∗+


f (x) = i K(x, xi ) (87)
i=1

Obsérvese que se prescinde del término b∗ puesto que éste puede ser representado mediante
la inclusión de una función constante en el conjunto de funciones base como, por ejemplo,
φ(x) = 1. Los coecientes α∗+
i y α∗+
i se obtienen como resultado de resolver el problema dual,
expresado ahora como:
Pn − +

Pn − +


max i=1 αi − αi yi −   i=1 αi + αi −
1 Pn − +
αj− − αj+ K(xi , xj )


2 i,j=1 αi − αi
(88)
Pn + −


s.a. i=1 αi − αi =0
+ −
0 ≤ αi , αi ≤ C, i = 1, . . . , n

que no es más que el problema dual (77), en el que los productos escalares se sustituyen por
funciones kernel.
A modo de resumen, puede decirse que para resolver problemas de regresión mediante SVRs
hay que seleccionar, además del kernel (caso de regresión no lineal), el valor de los parámetros
 y C. Ambos parámetros afectan a la complejidad del modelo. En el caso de problemas de
regresión con ruido, el parámetro  debería ser elegido de forma que reeje la varianza del ruido
de los datos. En la mayoría de casos prácticos es posible obtener una medida aproximada de
la varianza del ruido a partir de los datos de entrenamiento. Para problemas de regresión
sin ruido (problemas de interpolación) el valor  corresponde a la exactitud preestablecida de
interpolación, de forma que, cuanto mayor sea el valor de , menor será el número de vectores
soporte que se necesitarán, y viceversa. Por otro lado, la metodología usada para seleccionar el
valor de C se basa normalmente en técnicas de validación cruzada para, de esta forma, evitar
elegir un valor de C basado en los resultados de predicción de un modelo sobreajustado.

25
 (a) (b)

Figure 9: Ejemplos de salida del applet de la página web del software LIBSVM : (a) frontera de decisión
no-lineal en un problema de clasicación binaria (ver PDF en formato electrónico para distinguir el color de
los ejemplos de cada clase); (b) regresor no-lineal del conjunto de ejemplos mostrado en la gura.

7 Software sobre SVMs

En la actualidad existe un número importante de repositorios web y de paquetes software de
libre distribución dedicados a la implementación de SVMs y muchas de sus variantes. En esta
sección vamos a describir algunos de estos paquetes software.

LIBSVM
Enlace : [Link]

La librería LIBSVM es un paquete software pensado para resolver problemas de clasica-

ción y regresión mediante máquinas de vectores soporte. Entre sus principales características,
cabe citar que es un software de código abierto (disponible en C++ y Java); implementa di-
ferentes formulaciones SVM con la posibilidad de usar diferentes tipos de kernels; permite la
clasicación multiclase y la posibilidad de usar técnicas de validación cruzada para la selección
de modelos. También ofrece interfaces para una gran cantidad de lenguajes de programación
(Python, R, MATLAB, Perl, Ruby, Weka, Common LISP, CLISP, Haskell, OCaml, LabVIEW,
y PHP). Además, en su página web dispone de un applet para implementar sencillos problemas
de clasicación y de regresión en dos dimensiones. La gura 9 muestra las soluciones de un
ejemplo de problema de clasicación binaria (g. 9a) y otro de regresión (g. 9b), construidos
y resueltos ambos mediante dicho applet.

SVMlight
Enlace : [Link]

SVM
light es una implementación en C de máquinas de vectores soporte. Entre sus principa-

les características destaca el permitir resolver no sólo problemas de clasicación y de regresión,

sino también problemas de ranking; permite manejar varios cientos de miles de ejemplos de
entrenamiento, junto con muchos miles de vectores soporte; soporta funciones kernel estándar
y, además, permite al usuario denir sus propias funciones kernel. Como novedad presenta

26
 una implementación SVM, denominada SVM
Struct , para la predicción de salidas estructuradas

o multivariable, tales como conjuntos, secuencias y árboles.

References
Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992). A training algorithm for optimal margin
classiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory,
COLT '92 (pp. 144152). New York, NY, USA: ACM.

Cortes, C. & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273297.

27

View publication stats