Revista de Matema´tica: Teor´ıa y Aplicaciones 2000 7(1-2) : 107–116
cimpa – ucr – ccss issn: 1409-2433
un algoritmo para el entrenamiento de
ma´quinas de vector soporte para regresio´n
John Goddard*– Sergio Gerardo de los Cobos Silva**
Blanca Rosa Pe´rez Salvador***– Miguel A´ngel Gutie´rrez Andrade****
Recibido: 16 Mayo 2000
Abstract
The aim of the present paper is twofold. Firstly an introduction to the ideas of
Support Vector regression is given. Then a new and simple algorithm, suggested by
the work of Campbell y Cristianini in [16], is proposed which solves the corresponding
quadratic programming problem in an easy fashion. The algorithm is illustrated by
example and compared with classical regression.
Keywords: Support vector machines, ε−support vector regression.
Resumen
El propo´sito del presente art´ıculo es doble. Primero se proporciona una introduc-
cio´n a las ideas ba´sicas de la Ma´quinas de Vector Soporte para regresio´n. Posterior-
mente, se presenta un algoritmo novedoso y sencillo, basado en el trabajo de Campbell
y Cristianini [16], que resuelve de manera fa´cil el correspondiente problema de progra-
macio´n cuadra´tica. Se ilustra el algoritmo con un ejemplo, y se compara con el me´todo
de regresio´n cla´sico.
Palabras clave: Ma´quinas de vector soporte, regresio´n ε-vector soporte.
Mathematics Subject Classification: 62J99
*Depto. de Ingenier´ıa Ele´ctrica, Universidad Auto´noma Metropolitana-Iztapalapa, Av. Michoaca´n y La
Pur´ısima, Col. Vicentina, CP 09340 Me´xico D.F., Me´xico; E-Mail: jgc@xanum.uam.mx
**Misma direccio´n que J. Goddard; E-Mail: cobos@xanum.uam.mx
***Depto. de Matema´ticas, Universidad Auto´noma Metropolitana-Iztapalapa, Av. Michoaca´n y La
Pur´ısima, Col. Vicentina, CP 09340 Me´xico D.F., Me´xico.
****Depto. de Sistemas, Universidad Auto´noma Metropolitana-Azcapotzalco, Av. San Pablo 180, Colonia
Reynosa Tamaulipas, 02200 Me´xico, D.F. Me´xico; E-Mail: gama@hp9000a1.uam.mx
107
108 j. goddard – s. de los cobos – b.r. pe´rez – m.a. gutie´rrez
1. Introduccio´n
Las Ma´quinas de Vector Soporte (MVS) es una a´rea prometedora del aprendizaje
maquinal desarrollada inicialmente por Vapnik [1,2] para construir clasificadores. Se fun-
da en la teor´ıa estad´ıstica del aprendizaje, o teor´ıa de VC. Esta teor´ıa permite escoger un
clasificador que minimiza una cota superior sobre el riesgo (o error de prueba), y propor-
ciona una buena medida para obtener clasificadores que generalizan bien sobre datos no
previamente vistos. Esto le da una ventaja a MVS sobre otros clasificadores, como redes
neuronales artificiales que pueden producir modelos que sobreajustan a los datos. Adema´s,
las MVS tienen la habilidad de construir regiones de decisio´n no lineales de una manera
discriminativa mediante la introduccio´n de una funcio´n nu´cleo.
Las MVS han sido estudiadas intensamente en an˜os recientes y aplicadas exitosamente
en gran variedad de temas como: reconocimiento del habla [3], estimacio´n de densidades
probabil´ısticas [4], y la prediccio´n de series de tiempo [5]. El lector puede encontrar un
buen tutorial sobre los aspectos de MVS para clasificacio´n en [6].
En este art´ıculo se considera la aplicacio´n de las MVS en la aproximacio´n de funciones.
En este caso el me´todo se llama regresio´n ε−SV [7,8,9,10], y el objetivo es: dado un con-
junto finito de datos {(xi, yi)}, xi ∈ Rn, yi ∈ R1, i = 1, ..., N , encontrar una funcio´n f(x)
que este´ a lo ma´s ε desviaciones de los objetivos yi para todos los datos de entrenamiento
xi y que a la vez sea tan “plana” como sea posible.
En el caso ma´s sencillo, dado los datos, queremos encontrar una funcio´n lineal f de la
forma:
f(x) = 〈w, x〉+ b (1)
donde 〈·, ·〉 es el producto interior. En este contexto, “plana” significa que queremos en-
contrar un w “pequen˜a”. Para lograr esto, podemos minimizar ||w||2, la norma cuadrada,
y transformar el problema en el siguiente de optimizacio´n convexa (c.f. [8]):
Minimizar
1
2
‖w‖2 (2)
sujeto a : yi− 〈w, xi〉 − b ≤ ε y 〈w, xi〉+ b− yi ≤ ε
Esto supone que el problema es factible. Cuando no es el caso, se reformula el problema
(2) introduciendo variables de holgura ξi, ξ∗i de la siguiente manera:
Minimizar
1
2
‖w‖2 + C
∑
i
(ξi + ξ∗i ) (3)
sujeto a: yi− 〈w, xi〉 − b ≤ ε+ ξi, 〈w, xi〉+ b− yi ≤ ε+ ξ∗i , ξi, ξ∗i ≥ 0
y donde C determina el compromiso entre lo plano de f y la cantidad de desviaciones
mayores a ε que esta´n permitidas. De aqu´ı, el problema dual se deriva dando:
Maximizar − 1
2
∑
i,j
(α∗i − αi)(α∗j − αj) 〈xi, xj〉+
∑
i
yi(α∗i − αi)− ε
∑
i
(α∗i + αi) (4)
entrenamiento de ma´quinas de vector soporte para regresio´n 109
sujeto a:
∑
i
(α∗i − αi) = 0 y α∗i , αi ∈ [0, C]
donde todas las sumatorias recorren desde 1 a N . Por lo que la solucio´n del problema (4)
esta´ dada por:
f (x) =
∑
i
(α∗i − αi) 〈xi, x〉+ b (5)
Frecuentemente el nu´mero de α∗i , αi distintos a cero (cuyos vectores correspondientes se
llaman de soporte) es pequen˜o, y la representacio´n requiere de pocos miembros. Ma´s au´n,
la formulacio´n se generaliza al caso no lineal, que generalmente se requiere para modelar
adecuadamente los datos, sustituyendo el producto interior por una funcio´n nu´cleo,k, de
tal forma que el problema a resolver queda como:
Maximizar −1
2
∑
i,j
(α∗i − αi)
(
α∗j − αj
)
k(xi, xj)+
∑
i
yi (α∗i − αi)−ε
∑
i
(α∗i − αi) (6)
sujeto a:
∑
i
(α∗i − αi) = 0y α∗i , αi ∈ [0, C]
por lo que la solucio´n esta´ dada por:
f(x) =
∑
i
(α∗i − αi)k(xi, x) + b (7)
Algunos de los nu´cleos que han sido usados son:
a) Polinomio: k(x, y) = (〈x, y〉+ 1)d, d = 1, 2, ...
b) Funciones de base radial: k(x, y) = exp{−|x− y|2/σ2}
c) Redes neuronales de dos capas: k(x, y) = tanh(b 〈x, y〉 − c) , (para ciertos valores de
b y c).
Se puede mostrar [8,11] que:
1. Los multiplicadores Lagrangianos α∗i , αi no pueden ser simulta´neamente diferentes
de cero, por lo tanto la restriccio´n α∗iαi = 0 se cumple.
2. Los vectores soporte son aquellos puntos xi en los cuales el error de interpolacio´n
es mayor o igual a ε. Los puntos en los que el error de interpolacio´n es menor que
ε nunca son vectores de soporte, y no forman parte de la solucio´n. Una vez que se
han encontrado, podr´ıan ser eliminados del conjunto de datos, y si se resuelve el
problema de programacio´n nuevamente sobre el conjunto reducido se encuentra la
misma solucio´n.
3. Si α∗i = C o αi = C, esto implica que el vector correspondiente, (xi, yi), esta´ afuera
del ε− tubo.
110 j. goddard – s. de los cobos – b.r. pe´rez – m.a. gutie´rrez
Mientras que teo´ricamente el problema de optimizacio´n tiene una solucio´n u´nica, para
problemas con muchos datos, es imposible encontrar una solucio´n exacta. Adema´s, se ha
observado [8,12] que au´n en problemas con pocos datos, paquetes comerciales de progra-
macio´n cuadra´tica no siempre convergen, y cuando lo hacen no siempre dan las mismas
soluciones. Esto, y las dificultades involucradas en implementar algoritmos para resolver
un problema de programacio´n cuadra´tica, han sido una desventaja para que el me´todo
de MVS sea usado ma´s ampliamente. Para remediar esta situacio´n, se han introducido
distintos algoritmos como: algoritmos de punto interior [13], algoritmos de eleccio´n de
subconjuntos [14], y optimizacio´n minimal secuencial [15].
En este art´ıculo, se presenta un algoritmo sencillo basado en el me´todo de gradiente
ascendente y sugerido por Campbell y Cristianini en [16], para encontrar los coeficientes
α∗i , αi en el caso no lineal. En la siguiente seccio´n se dan detalles de la derivacio´n del
algoritmo y despue´s se muestra que la funcio´n objetivo es convexa. En la seccio´n 4 se
especifica la implementacio´n del algoritmo. Posteriormente se ilustra el algoritmo con un
ejemplo. Finalmente se mencionan algunas conclusiones derivadas del trabajo.
2. El me´todo
Una manera sencilla de resolver el problema (1), siguiendo a [16], es aplicar el me´todo
de gradiente ascendente a la funcio´n objetivo con el Lagrangiano correspondiente definido
por:
L(α∗, α) = −1
2
∑
i,j
(α∗i−αi)(α∗j−αj)k(xi, xj)+
∑
i
yi(α∗i−αi)−ε
∑
i
(α∗i+αi)−λ
∑
i
(α∗i−αi)
(8)
donde α = (α1, . . . , αN )T , α∗ = (α∗1, . . . , α
∗
N )
T RN y 0 ≤ αi,α∗i ≤ C i = 1, . . . , N
Tomando las derivadas parciales, se obtiene:
∂L
∂α∗m
= ym − ε− λ−
∑
i
(α∗i − αi)k(xi, xm)
∂L
∂αm
= −ym − ε+ λ+
∑
i
(α∗i − αi)k(xi, xm)
(9)
Introduciendo los pasos para el me´todo de gradiente ascendente δα∗m, δαm, se obtiene:
δα∗m = η
∂L
∂α∗m
, δαm = η
∂L
∂αm
(10)
y sustituye´ndolos en (8) se obtiene:
L(α∗ + δα∗m, α) = δα
∗
m
∂L
∂α∗m
− 1
2
δα∗
2
mk(xm, xm) (11)
L(α∗ + δα∗m, α) = δα
∗2
m
[
1
η
− 1
2
k(xm, xm)
]
≥ 0 (12)
entrenamiento de ma´quinas de vector soporte para regresio´n 111
si
[
1
η − 12k(xm, xm)
]
≥ 0 o 2 ≥ η k(xm, xm) ≥ 0 suponiendo que η ≥ 0.
De manera ana´loga,
L(α∗, α+ δαm) = δα2m
[
1
η
− 1
2
k(xm, xm)
]
≥ 0 (13)
si 2 ≥ ηk(xm, xm) ≥ 0 suponiendo que η ≥ 0.
En caso de un nu´cleo de funcio´n de base radial,k(xm, xm) = 1, con la condicio´n
2 ≥ η ≥ 0. En la siguiente seccio´n se muestra que L(α∗, α) es una funcio´n convexa.
3. Convexidad de la funcio´n L(α∗, α)
En esta seccio´n se muestra que la funcio´n objetivo de (6) y L(α∗, α) son convexas, lo
cual es importante para garantizar la existencia y unicidad del o´ptimo global. Sustituyendo
a = α∗ − α, y = (y1, . . . , yN )T ∈ Rn se puede escribir la funcio´n objetivo de (6) como:
F (a) = −1
2
aTKa+ yTa− ε||a||1 (14)
sujeta a
∑
i
ai = 0
donde K es la matriz N × N con entradas k(xi, xj), y donde ||a||1 =
∑
i
|α∗i + αi| =∑
i
(α∗i + αi) puesto que α
∗, α ∈ [0, C].
Con esta notacio´n, se puede escribir el Lagrangiano L como:
L(a) = −1
2
aTKa+ yTa− ε||a||1 − λaT1 (15)
donde 1 = (1, ..., 1)T . Primero se mostrara´ que la funcio´n F (a) es convexa, y posterior-
mente que F (α∗, α) tambie´n lo es.
Teorema 1 La funcio´n F (a) de (15) es convexa.
Demostracio´n: Se tiene por definicio´n que una funcio´n f es convexa si para dos vectores
a1 y a2 se tiene que:
f(γ1a1 + γ2a2) ≥ γ1f(a1) + γ2f(a2)
para γ1, γ2 > 0 y γ1 + γ2 = 1.
No´tese que:
F (γ1a1 + γ2a2) = −12(γ1a1 + γ2a2)
TK(γ1a1 + γ2a2) + yT (γ1a1 + γ2a2)− ε||γ1a1 + γ2a2||1
= −1
2
γ21a
T
1Ka1 − γ1γ2aT1 ka2 −
1
2
γ22a
T
2Ka2 + γ1y
Ta1 + γ2yTa2
−ε ‖γ1a1 + γ2a2‖1
112 j. goddard – s. de los cobos – b.r. pe´rez – m.a. gutie´rrez
y que:
γ1F (a1)+ γ2F (a2) = −12γ1a
T
1Ka1+ γ1y
Ta1− ε||γ1a1||1− 12γ2a
T
2Ka2+ γ2y
Ta2− ε||γ2a2||1
Entonces:
F (γ1a1 + γ2a2)− γ1F (a1)− γ2F (a2) = 12γ1(1− γ1)a
T
1Ka1 +
1
2
γ2(1− γ2)aT2Ka2
−γ1γ2aT1Ka2 − ε(||γ1a1 + γ2a2||1
−||γ1a1||1 − ||γ2a2||1) (16)
Como γ1 + γ2 = 1, sustituyendo en (17) se obtiene:
F (γ1a1 + γ2a2)− γ1F (a1)− γ2F (a2) = 12γ1γ2(a
T
1Ka1 + a
T
2Ka2 − 2aT1Ka2)
+ε(‖γ1a1‖1 + ‖γ2a2‖1 − ||γ1a1 + γ2a2||1)
=
1
2
γ1γ2(a1 − a2)TK(a1 − a2)
+ε(‖γ1a1‖1 + ‖γ2a2‖1 − ‖γ1a1 + γ2a2‖1)
≥ 0
Por lo que F (a) es convexa.
Por un procedimiento semejante se tiene que L(a) es convexa tambie´n. Para ver que
F (α∗, α) es convexa, basta ver que: como a = α∗ − α = (I,−I)
(
α∗
α
)
F (α∗, α) = −1
2
(α∗T , αT )
(
I
−I
)
K(I,−I)
(
α∗
α
)
+ yT (I,−I)
(
α∗
α
)
−ε
∥∥∥∥(I.− I)( α∗α
)∥∥∥∥
1
(17)
y como γ1
(
α∗1
α1
)
+ γ2
(
α∗2
α2
)
al transformarse da:
(I,−I)
[
γ1
(
α∗1
α1
)
+ γ2
(
α∗2
α2
)]
= γ1a1 + γ2a2 (18)
los ca´lculos para probar que F (α∗, α) es convexa son los mismos.
4. Implementacio´n del algoritmo
Siguiendo las ideas expuestas en [16], donde se desarrolla el caso de clasificacio´n, en
este trabajo se desarrolla la implementacio´n de un algoritmo para el caso de regresio´n, el
cual se proporciona en la Figura 1. De manera ana´loga que en [16], es importante observar
que en relacio´n a los pasos del algoritmo:
entrenamiento de ma´quinas de vector soporte para regresio´n 113
1. En el caso que α∗0i o α
0
i < 0, se asigna el valor de cero a la variable correspondiente.
2. Se aplica el me´todo de secante para calcular λ
3. El sesgo b, de f(x), es tomado como el valor final de λ
4. Habra´ que incluir una condicio´n dentro del algoritmo para asegurar que el factor
($t−1 −$t−2) sea distinto a cero.
5. Para asegurar que α∗0i , α
0
i ≤ C , se asigna el valor C a la variable correspondiente.
Inicializar α∗0i , α
0
i = 0
Para t = 0 to genmax
Si (t == 0) Entonces
λ0 = µ
Otro Si (t == 1) Entonces
λ1 = −µ
Otro
λt = λt−1 − ωt−1(λt−1 − λt−2)/(ωt−1 − ωt−2)
Fin Si
Para i = 1 to N
zi =
N∑
j=1
(
α∗j − αj
)
k (xi, xj)
δαti = η
(
−yi − ε+ zi + λtt
)
δα∗ti = η
(
yi − ε− zi − λtt
)
:
Si
(
αti + δα
t
i
) ≤ 0 Entonces αti = 0
Otro Si
(
αti + δα
t
i
)
< C Entonces αti = α
t
i + δα
t
i
Otro αti = C
Fin Si
Si
(
α∗ti + δα
∗t
i
) ≤ 0 Entonces α∗ti = 0
OtroSi
(
α∗ti + δα
∗t
i
)
< C Entonces α∗ti = α
∗t
i + δα
∗t
i
Otro α∗ti = C
Fin Si
Fin Para
$t =
∑
j
(
α∗tj − αtj
)
Fin Para
Fig.1 Algoritmo para el caso de la regresio´n.
114 j. goddard – s. de los cobos – b.r. pe´rez – m.a. gutie´rrez
5. Resultados
En esta seccio´n se presenta un ejemplo de aproximacio´n ilustrando el uso del algoritmo
descrito anteriormente. Se tomo´ los valores de la funcio´n:
f(x) =
sen
(
10pi x3
)
x
(19)
en 100 puntos igualmente espaciados en el intervalo [−1, 1], de manera similar al ejemplo
dado en Vapnik [2]. Se tomo´ como nu´cleo la funcio´n de base radial. Despue´s de experi-
mentar con los para´metros del nu´cleo y del algoritmo, se escogieron los siguientes valores:
δ = 0,1, µ = 0,1, η = 1, y el nu´mero ma´ximo de generaciones igual a 3000. Se presentan las
gra´ficas para los casos de ε = 0,05 y 0,1, en las figuras 2 y 3. Para ε = 0,05 se obtuvieron
11 vectores soporte, y para ε = 0,1, 13 vectores soporte. En la Fig.4, se presenta el modelo
polinomial de regresio´n de grado 6 que mejor ajusta a los datos, y que utiliza el criterio
de mı´nimos cuadrados.
Fig. 2: Caso ε = 0,05. Fig. 3: Caso ε = 0,1.
Los resultados que se observan en las Fig.2 y 3 son comparables con aquellos dados
por Vapnik [2]. Adema´s, la suma de los cuadrados de los residuales para ε = 0,05, 0,1 y
el modelo polinomial de regresio´n fueron de 0,15, 0,62, 2,65 respectivamente, por lo que se
obtiene una mejor aproximacio´n de la funcio´n con el algoritmo propuesto. Esto se debe
principalmente al criterio usado en el me´todo de regresio´n ε−SV , el cual trata de obtener
una aproximacio´n de a lo ma´s ε-desviaciones respecto a los datos originales. Lo que se
considerar´ıa como factor cr´ıtico para muchas aplicaciones.
6. Conclusiones
En este art´ıculo se ha presentado una introduccio´n al tema de MVS para regresio´n,
y se ha propuesto un algoritmo sencillo y novedoso, basado en el trabajo de Campbell y
Cristianini, para el caso de regresio´n.
entrenamiento de ma´quinas de vector soporte para regresio´n 115
Fig. 4: Modelo polinomial de regresio´n de grado 6.
Mediante el uso del me´todo de gradiente ascendente dentro del algoritmo, se evita la
necesidad de utilizar un paquete de programacio´n cuadra´tica, lo que hace que la aplicacio´n
de la regresio´n ε−SV sea ma´s accesible. Para una comparacio´n de la regresio´n ε−SV para
estimar funciones respecto a otras te´cnicas Vapnik [2] ha presentado varios ejemplos. As´ı,
para el caso de estimacio´n de funciones de regresio´n lineal, se puede observar de las tablas
de comparaciones que presenta Vapnik que la regresio´n ε − SV proporciona resultados
que son mejores en todos los casos que los obtenidos con el me´todo de mı´nimos cuadrados
ordinarios.
El ejemplo desarrollado en este trabajo es similar a uno dado en [2], y se puede ob-
servar que los resultados obtenidos utilizando el algoritmo propuesto son comparables con
aquellos de Vapnik.
Tambie´n la regresio´n ε − SV tiene ventajas sobre el me´todo de regresio´n tradicional
en varios sentidos: no es necesario experimentar con varios modelos a priori y despue´s
identificar cua´l es el de mejor ajuste, lo que ahorra tiempo. El modelo producido por la
regresio´n ε− SV se obtiene a partir del nu´cleo escogido y de los datos de entrenamiento.
Ser´ıa importante en futuros trabajos explorar el impacto de los diferentes para´metros en
el algoritmo, en particular la eleccio´n de la funcio´n nu´cleo.
Referencias
[1] Vapnik, V. (1995) The Nature of Statistical Learning Theory. Springer-Verlag, New
York.
[2] Vapnik, V. (1998) Statistical Learning Theory. John Wiley and Sons, New York.
[3] Ganapathiraju, A.; Hamaker, J.; Picone, J. (1998) “Support vector machines for
speech recognition”, Proc. ICSLP, Australia.
116 j. goddard – s. de los cobos – b.r. pe´rez – m.a. gutie´rrez
[4] Weston, J.; Gammerman, A.; Stitson, M.; Vapnik, V.; Vovk, V.; Watkins. (1998)
“Density estimation using support vector machines”, Technical Report CSD-TR-97-
23.
[5] Mu¨ller, K.; Smola, A.; Ra¨tsch, G.; Scho¨lkopf, B.; Kohlmorgan, J.; Vapnik, V. (1997)
“Predicting time series with support vector machines”, Proc. of the ICANN Confer-
ence.
[6] Burges, C. (1998) “A Tutorial on support vector machines for pattern recognition”,
Data Mining and Knowledge Discovery, 2(2).
[7] Vapnik, V.; Golowich, S.; y Smola, A. (1997) “Support vector method for function
approximation, regression estimation, and signal processing”, Advances in Neural In-
formation Processing Systems, Vol. 9, MIT Press, Cambridge Mass.: 281–287.
[8] Smola, A.; Scho¨lkopf, B. (1998) “A tutorial on support vector regression”, Neuro-
COLT2 Technical Report Series, NC2-TR-030.
[9] Gunn, S. (1998) “Support vector machines for classification and regression”, ISIS
Technical Report, University of Southampton.
[10] Stitson, M.; Weston, J.; Gammerman, A.; Vovk V.; Vapnik, V. (1996) “Theory of
support vector machines”, Tech. Report CSD-TR-96-17, RHUL.
[11] Girosi, F. (1998) “An equivalence between sparse approximation and support vector
machines”, Neural Computation, 10(6): 1455–1480.
[12] Chin, K. (1998) “Support Vector Machines applied to Speech Pattern Classification”.
M.Phil. Thesis in Computer Speech and Language Processing, Cambridge University,
Engineering Department.
[13] Vanderbei, R.J. (1997) “LOQO user’s manual 3.10”, Technical Report SOR-97-08,
Statistics and Operations Research, Princeton University.
[14] Osuna, E.; Freund, R.; Girosi, F. (1997) “An improved training algorithm for support
vector machines”, Neural Networks for Signal Processing VII - Proc. of the 1997 IEEE
Workshop, J. Principe, L. Gile, N. Morgan, y E. Wilson (Eds.): 276–285.
[15] Platt, J. (1998) “Sequential minimal optimization: A fast algorithm for training sup-
port vector machines”, Advances in Kernel Methods- Support Vector Learning, B.
Scho¨lkopf, C. Burges, A. Smola (Eds.) MIT Press, Cambridge Mass.
[16] Campbell, C.; Cristianini, N. (1999) “Simple learning algorithms for training support
vector machines”, Department of Engineering Mathematics, University of Bristol.