Modelos de Clasificaci´on basados en M´aquinas de Vectores Soporte L. Gonz´alez Abril [email protected] - Departamento de Econom´ıa Aplicada I Universidad de Sevilla Palabras clave: Problemas de Clasificaci´ on, SVM, N´ ucleos (Kernels). Resumen En este trabajo se presentan las caracter´ısticas m´ as importantes de los modelos de clasificaci´ on basados en m´ aquinas de vectores soporte (SVM- Support Vector Machines). Las m´ aquinas de vectores soporte son sistemas de aprendizaje que utilizan como espacio de hip´ otesis, funciones lineales en espacios caracter´ısticos de dimensi´ on muy alta, ensayando algoritmos de aprendizaje de la teor´ıa de la optimizaci´ on que implementan un aprendizaje sesgado derivado a partir de la teor´ıa del aprendizaje estad´ıstico. Algunas de las caracter´ısticas de estos modelos tienen una especial significaci´ on en problemas de clasificaci´ on de corte econ´ omico y en este trabajo se presentan y comentan.

1.

Introducci´ on La teor´ıa de las SVMs fue desarrollada inicialmente por V. Vapnik [18] a principios de los a˜ nos

80 y se centra en lo que se conoce como Teor´ıa del Aprendizaje Estad´ıstico1 . El objeto de las SVMs es dar soluci´ on al problema fundamental que surge en distintos campos, donde se estudia, la relaci´ on entre sesgo y varianza [8], el control de la capacidad [13], sobreajuste en los datos [15], etc. Este problema consiste en buscar, para una tarea de aprendizaje dada, con una cantidad finita de datos, una adecuada funci´ on que permita llevar a cabo una buena generalizaci´ on2 que sea resultado de una adecuada relaci´ on entre la precisi´ on alcanzada con un particular conjunto de entrenamiento y la capacidad del modelo3 . 1 De

forma simplificada indicar que esta teor´ıa busca formas de estimar dependencias funcionales a partir de una

colecci´ on de datos. 2 Donde

se entiende por generalizaci´ on, la capacidad de una determinada funci´ on de explicar el comportamiento de

los datos dentro de un dominio m´ as amplio. 3 Capacidad

para aprender con cualquier conjunto de ensayo.

1

A continuaci´ on desarrollamos brevemente el planteamiento general de las SVMs para posteriormente centrarnos en los problemas de clasificaci´ on4 desde la perspectiva de un aprendizaje supervisado, es decir, el conocimiento de las salidas de un conjunto de entradas nos permite cuantificar (supervisar) la bondad de los resultados del modelo. El objetivo fundamental de este tipo de estudios es aprender a partir de los datos y para ello busca la existencia de alguna dependencia funcional entre un conjunto de vectores inputs (o de entrada) {xi , i = 1, · · · , n} ⊆ X ⊆ IRd y valores5 outputs (o salidas) {yi , i = 1, · · · , n} ⊆ Y ⊆ IR El modelo representado por la figura 1 (denominado modelo de aprendizaje a partir de ejemplos) recoge de manera clara el objetivo que se persigue. En este esquema, G representa un modelo

FY/X (y)

FX (x) G Generador de Datos

xi

S Operador Objetivo

-

?

 LM M´ aquina de Aprendizaje

-

yi -

? yi∗

F(X ,Y) (x, y)

Figura 1: Esquema de configuraci´ on de una m´ aquina de aprendizaje a partir de ejemplos. generador de datos que nos proporciona los vectores xi ∈ X, independientes e id´enticamente distribuidos de acuerdo con una funci´ on de distribuci´ on FX (x) desconocida pero que suponemos no var´ıa a lo largo del proceso de aprendizaje. Cada vector xi es la entrada del operador objetivo S, el cual lo transforma en un valor yi seg´ un una funci´ on de distribuci´ on condicional FY/X =xi (y). As´ı la m´ aquina6 de aprendizaje, que denotamos LM (learning machine) recoge el siguiente conjunto de entrenamiento, Z = {(x1 , y1 ), · · · , (xn , yn )} ⊆ X × Y = Z 4 Desde

las SVM se puede abordar diferentes problemas como: regresi´ on, estimaci´ on de densidades, aproximaci´ on de

funciones, ... 5 La

generalizaci´ on a IRd se sigue sin m´ as que considerar el vector componente a compenente.

6 Las

SVMs tienen sus or´ıgenes en problemas de corte industrial. La puesta en pr´ actica de estos modelos en la industria

finaliza cuando se implementa un programa inform´ atico dentro de un procesador que recoja datos y los procese. Este procesador es un objeto f´ısico y tangible y por ello la denominaci´ on de m´ aquina.

2

el cual es obtenido independiente e id´enticamente distribuido siguiendo la funci´ on de distribuci´ on conjunta: F(X ,Y) (x, y) = FX (x) · FY/X =x (y) A partir del conjunto de entrenamiento Z, la m´ aquina de aprendizaje “construye” una aproximaci´ on al operador desconocido la cual proporcione para un generador dado G, la mejor aproximaci´ on (en alg´ un sentido) a las salidas proporcionadas por el supervisor. Formalmente construir un operador significa que la m´ aquina de aprendizaje implementa un conjunto de funciones, de tal forma que durante el proceso de aprendizaje, elige de este conjunto una funci´ on apropiada siguiendo una determinada regla de decisi´ on. La estimaci´ on de esta dependencia estoc´ astica basada en un conjunto de datos trata de aproximar la funci´ on de distribuci´ on condicional FY/X (y), lo cual en general lleva a un problema realmente complicado [18, 10]. Sin embargo, el conocimiento de la funci´ on FY/X (y) no siempre es necesario; a menudo se esta interesado solo en alguna de sus caracter´ısticas. Por ejemplo se puede buscar estimar la funci´ on de esperanza matem´ atica condicional: def

E[Y /X = x] =

y dFY/x (y)

Por ello el objetivo del problema es la construcci´ on de una funci´ on f (x, y) dentro de una determinada clase de funciones7 F elegida a priori, la cual debe cumplir un determinado criterio de la mejor manera posible. Formalmente el problema se plantea como sigue: Dado un subespacio vectorial Z de IRd+1 donde se tiene definida una medida de probabilidad FZ (z), un conjunto F = {f (z), z ∈ Z} de funciones reales y un funcional R : F → IR. Buscar una funci´ on f ∗ ∈ F tal que8 R[f ∗ ] = m´ın R[f ] f ∈F

Con objeto de ser lo m´ as general posible ser´ıa bueno elegir el funcional R de tal manera que se pudiese plantear con ´el, el mayor n´ umero de problemas posibles. Por ello se define R[·] como sigue: Definici´ on 1.1 Dada una clase F = {f (z), z ∈ Z} de funciones reales y una medida de probabilidad FZ (z) se define el riesgo, R : F → IR, como: R[f ] =

c(z, f (z)) dFZ (z)

(1)

Z

donde c(·, ·) se denomina funci´ on de p´erdida (o de coste) y tomar´ a valores no negativos. A la vista de la figura 1 se llega a la conclusi´ on que los valores yi e yi∗ no necesariamente coinciden. Cuando esto sea as´ı, la m´ aquina de aprendizaje habr´ a cometido un error que se debe cuantificar de alguna forma y este es precisamente el sentido que tiene la funci´ on de perdida. 7 En

este contexto, una clase de funciones (espacio de hip´ otesis) es sin´ onimo de una m´ aquina (o modelo) de aprendi-

zaje. 8 La

existencia del m´ınimo se garantiza cuando se concluye las hip´ otesis de esta teor´ıa [18].

3

As´ı, en este planteamiento, dado un conjunto {(x1 , y1 ), · · · , (xn , yn )}, el principal problema consiste es formular un criterio constructivo para elegir una funci´ on de F puesto que el funcional (1) por si mismo no sirve como criterio de selecci´ on, ya que la funci´ on FZ (z) incluida en ´el es desconocida. Para elaborar dicho criterio se debe tener en cuenta que el riesgo se define como la esperanza matem´ atica de una variable aleatoria respecto a una medida de probabilidad, por tanto es l´ ogico elegir como estimaci´ on, la media muestral y de aqu´ı la siguiente definici´ on: Definici´ on 1.2 Dado un riesgo definido por (1), un conjunto de funciones F y una muestra {z1 , · · · , zn }. Al funcional Remp : F → IR definido como Remp [f ] =

1 n

n

c(zi , f (zi )),

f ∈F

i=1

se le denomina riesgo emp´ırico9 . La forma cl´ asica de abordar estos problemas es: si el valor m´ınimo del riesgo se alcanza con una funci´ on f0 y el m´ınimo del riesgo emp´ırico con fn para una muestra dada de tama˜ no n, entonces se considera que fn es una aproximaci´ on a f0 en un determinado espacio m´etrico. El principio que resuelve este problema se denomina principio de minimizaci´ on del riesgo emp´ırico, Este es el principio utilizado en los desarrollos cl´ asicos por ejemplo cuando se plantea a partir de un conjunto de datos la regresi´ on lineal m´ınimo cuadr´ atica. La pregunta que surge es: ¿se puede asegurar que el riesgo R[fn ] est´ a cerca del m´ınf ∈F R[f ]? La respuesta es que en general esto no es cierto [10], lo cual lleva a la conclusi´ on que la clase de funciones F no puede ser arbitraria, necesariamente se debe imponer algunas condiciones de regularidad a sus elementos, v´ıa un funcional Q[f ]. As´ı en la elaboraci´ on del problema se debe buscar una adecuada relaci´ on entre la precisi´ on alcanzada con un particular conjunto de entrenamiento, medido a trav´es de Remp [f ], y la capacidad de la m´ aquina medida por Q[f ]. Ello lleva a considera el problema de minimizar un riesgo regularizado, donde este se define para alg´ un λ > 0 en la forma: Rreg [f ] = Remp [f ] + λ Q[f ] Indicar que en las SVMs, el espacio de trabajo es F = f (x) = w · x + b, w ∈ IRd , b ∈ IR




(funciones lineales) y la restricci´ on se impone sobre el par´ ametro w.

1.1.

Problemas de clasificaci´ on

En los problemas de clasificaci´ on dicot´ omicos (con etiquetas {0, 1}) es posible dar una interpretaci´ on probabil´ıstica de los funcionales riesgos. Sea F la clase de todas las funciones reales definidas en X = IRd que solo pueden tomar los valores {0, 1}. Entonces dada una funci´ on f ∈ F existe un subconjunto A ⊂ IRd tal que 9 Es

importante notar que la medida de probabilidad F (z) aparece dada impl´ıcitamente a trav´es de los datos

z1 , · · · , z n .

4

f (x) = IA (x) (funci´ on indicadora del conjunto A). Por tanto se tiene que si f (x) = y entonces la p´erdida es c(x, y, f (x)) = 0 y si f (x) 6= y se cuantifica el error como c(x, y, f (x)) = 1, y se sigue: R[f ] = P


(x, y) ∈ IRd+1 / f (x)) 6= y 

= P (Af )

y se tiene que el riesgo coincide con la probabilidad de un conjunto Af respecto a una medida de probabilidad. Adem´ as elegida f ∈ F se tiene que Af ∈ IRd+1 es el conjunto de vectores donde se realiza una clasificaci´ on err´ onea, y de aqu´ı que el riesgo proporciona la probabilidad de una clasificaci´ on err´ onea y cobra un mayor sentido la minimizaci´ on de ´este, es decir, determinar f ∗ tal que: R[f ∗ ] = P (Af ∗ ) = m´ın P (Af ) f ∈F

Veamos como es el riesgo emp´ırico: Definici´ on 1.3 Sea un espacio probabil´ıstico (Ω, A, P ). Se define la probabilidad emp´ırica de A ∈ A a partir de la muestra {z1 , · · · , zn } def

vn (A) = v(A; z1 , · · · , zn ) =

n(A) n

donde n(A) es el n´ umero de elementos de la muestra que pertenecen a A. De la definici´ on se tiene que: Remp [f ] =

1 n

n

c(xi , yi , f (xi )) = vn (Af ) i=1

es decir, el riesgo emp´ırico es la frecuencia relativa de ocurrencia del suceso Af en una muestra. Luego seg´ un el principio de minimizaci´ on del riesgo emp´ırico el problema que se plantea es m´ınf ∈F vn (Af ). ¿C´ omo se interpretar´ıa el riesgo emp´ırico en este caso? Sea un conjunto de vectores {x1 , · · · , xn } y sus correspondientes etiquetas {y1 , · · · , yn }. Si nos olvidamos de ellas y sobre los vectores {x1 , · · · , xn } se aplica una funci´ on f (x) se obtendr´ a un conjunto de salidas {y10 , · · · , yn0 }. Entonces cuando se tenga para i ∈ {1, · · · , n} que yi 6= yi0 se dir´ a que se ha producido un error de entrenamiento. As´ı pues la minimizaci´ on del riesgo emp´ırico consiste en buscar la funci´ on f ∗ ∈ F que minimiza los errores de entrenamiento.

2.

Modelos lineales de vectores soporte Denotamos las dos posibles etiquetas por Y = {−1, 1} y

Definici´ on 2.1 Un conjunto de vectores {(x1 , y1 ), · · · , (xn , yn )} donde xi ∈ IRd e yi ∈ {−1, 1} para i = 1, · · · , n se dice separable si existe alg´ un hiperplano en IRd que separa10 los vectores X = {x1 , · · · , xn } con etiqueta yi = 1 de aquellos con etiqueta yi = −1. 10 En

el sentido de dejar en dos regiones del espacio diferentes.

5

Dado un conjunto separable existe (al menos) un hiperplano11 π : w·x+b = 0 que separa los vectores xi , i = 1, · · · , n (ver figura 2). Las SVMs buscan entre todos los hiper-

A

B

Figura 2: Conjunto e hiperplano separador en IR2 . Los puntos huecos representan los vectores con etiqueta y = 1 y los restantes y = −1. planos separadores aquel que maximice la distancia de separaci´ on entre los conjuntos {(x i , 1)} y {(xi , −1)} (las dos clases posibles). Veamos como se plantea el problema de optimizaci´ on correspondiente: Fijado un hiperplano separador siempre es posible reescalar (ver [9]) los par´ ametros w y b de tal forma que: xi · w + b ≥ +1

para yi = +1

(regi´ on A)

xi · w + b ≤ −1

para yi = −1

(regi´ on B)

De esta forma la m´ınima separaci´ on entre los vectores y el hiperplano separador es la unidad 12 ; y las dos desiguladades se pueden expresar en una sola de la forma: yi (xi · w + b) − 1 ≥ 0,

i = 1, · · · , n

(2)

Sean los vectores de etiqueta 1 para los cuales se cumple la igualdad en (2). Estos puntos pertenecen al hiperplano π1 : xi · w + b = 1 con vector normal w y distancia perpendicular hasta el origen igual a |1 − b| / kwk donde kwk es la norma euclidea de w. An´ alogamente, los vectores de etiqueta −1 que cumplen la igualdad en (2) pertenecen al hiperplano π2 : xi · w + b = −1 con vector normal w y distancia perpendicular al origen de coorcdenadas igual a |−1 − b| / kwk. As´ı se tiene que los hiperplanos π1 y π2 son paralelos, la separaci´ on entre ellos es 2/ kwk y ning´ un vector del conjunto de entrenamiento se encuentra entre ellos. De entre las posibles elecciones del los hiperplanos π1 y π2 , parece natural elegir aquella que proporcione una mayor separaci´ on entre ellos, ya que de esta forma permitir´ıa distinguir de forma m´ as clara las regiones donde caen los puntos con distintas etiquetas. As´ı se plantea13 : 1 m´ın kwk2 w∈IRd 2 s.a. 11 Se

(3)

yi (xi · w + b) − 1 ≥ 0, i = 1, · · · , n

utilizar´ a indistintamente la notaci´ on w · x y hw, xi para denotar el producto escalar de dos vectores.

12 Ser´ ıa

una especie de normalizaci´ on.

13 Otra

formulaci´ on, que proporciona la misma soluci´ on pero cuyo tratamiento es m´ as complicado, consiste en maxi-

mizar la separaci´ on pero fijando la norma del vector w a la unidad.

6

La soluci´ on para el caso de dimensi´ on dos se puede interpretar gr´ aficamente a partir de la figura 3. A la vista de esta figura, es f´ acil darse cuenta de una caracter´ıstica muy importante de las SVMs y es que si se a˜ nade o elimina cualquier n´ umero de vectores que cumplan la desigualdad estricta (2), la soluci´ on del problema de optimizaci´ on no se ve afectada. Sin embargo, basta con a˜ nadir un vector que se encuentre entre los dos hiperplanos, para que la soluci´ on cambie totalmente.

A

π1

B

π π2

Figura 3: Hiperplanos paralelos y vectores soporte en IR2 . Para resolver el problema de optimizaci´ on con restricciones (3) se utiliza los multiplicadores de Lagrange14 . As´ı la funci´ on objetivo es: LP (w, b, αi ) =

n

1 kwk2 − 2

αi (yi (xi · w + b) − 1) i=1

El problema queda como un problema de programaci´ on cuadr´ atica donde la funci´ on objetivo es convexa, y los vectores que satisfacen las restricciones forman un conjunto convexo. Esto significa que se puede resolver el siguiente problema dual asociado al problema primal: maximizar la funci´ on LP (w, b, αi ) respecto a las variables duales αi sujeta a las restricciones impuestas para que los gradientes de LP con respecto a w y b sean nulos, y sujeta tambi´en al conjunto de restricciones C2 = {αi ≥ 0, i = 1, · · · , n}. La soluci´ on de este problema se expresa en la forma: n

w=

n

α i yi x i ,

α i yi = 0

i=1

i=1

y la funci´ on objetivo dual: n

LD (α) =

αi − i=1

1 2

n

α i α j yi yj x i x j

(4)

i,j=1

Los vectores del conjunto de entrenamiento que proporcionan un multiplicador αi > 0 son denominados vectores soporte y claramente, estos vectores se encuentran en uno de los hiperplanos π1 o π2 . Para este tipo de modelo de aprendizaje, los vectores soporte son los elementos cr´ıticos ya que ellos son los que proporcionan la aproximaci´ on del problema, puesto que si todos los restantes elementos del conjunto de entrenamiento son eliminados (o son cambiados por otros que no se encuentren entre los dos hiperplanos), y se repite el problema de optimizaci´ on, se encuentran los mismos hiperplanos separadores. 14 En

la literatura cl´ asica se denominan de forma err´ onea de esta manera a pesar de plantearse un problema de

optimizaci´ on cons restricciones de desigualdades, La denominaci´ on correcta ser´ıa multiplicadores de Karush-KuhnTucker, sin embargo utilizaremos las denominaci´ on cl´ asica.

7

Esta caracter´ıstica de los modelos de vectores soporte puede ser utilizada en muchos problemas econ´ omicos donde se desea destacar la importancia de determinadas entradas. Tambi´en si se trabaja con una gran cantidad de entradas, es u ´til trabajar con los vectores soporte ya que estos forman un esquema de comprensi´ on15 que permite reconstruir la soluci´ on del problema, es decir, si consideramos exclusivamente los vectores soporte y descartamos el resto de vectores de entrenamiento tendr´ıamos un problema de optimizaci´ on con menos restricciones que proporciona la misma informaci´ on. Las condiciones del problema de optimizaci´ on nos lleva a que se cumple la condici´ on (ver [9]): αi · (yi · (xi · w + b) − 1) = 0 denominada condici´ on (complementaria) de Karush-Kuhn-Tucker (KKT). Estas restricciones indican que el producto de las restricciones del problema primal (yi · (xi · w + b) − 1 ≥ 0) y las restricciones del problema dual (αi ≥ 0) se anulan en todos los vectores de entrenamiento. De esta forma se sigue que las condiciones KKT, v´ease [7], para el problema primal definido a partir de la funci´ on objetivo son las siguientes: n

wj −

αi yi xij

=

0

j = 1, · · · , d

∂ LP = − α i yi ∂b i=1

=

0

yi (xi · w + b) − 1

≥

0

∀i = 1, · · · , n

αi

≥

0

∀i = 1, · · · , n

αi (yi (xi · w + b) − 1)

=

0

∀i = 1, · · · , n.

i=1 n

De los desarrollos iniciales no se sigue una forma expl´ıcita de determinar el valor b, sin embargo, la condici´ on KKT complementaria nos permite determinarlo. Para ello, basta elegir un αi > 0 y despejar el valor de b obteniendo b = yi − xi · w. Aunque se ha determinado b, es m´ as adecuado realizar los c´ alculos con todos los αi > 0 y elegir como valor de b un valor promedio de los resultados obtenidos, con objeto de redondear los errores intr´ınsecos asociados a todo m´etodo de c´ alculo num´erico16 : b=

1 # {αi > 0}

(yi − xi · w) αi >0

Una vez obtenidos el vector w y la constante b la soluci´ on al problema de optimizaci´ on se interpreta a partir de una funci´ on Θ de la siguiente forma:


Θ(x) =

15 Es



1

si π(x) > 0

−1

si π(x) < 0

(5)

una regla ρ : S → ρ(S) que permite construir una clasificaci´ on de un conjunto S a partir de un conjunto ρ(S)

m´ as peque˜ no. 16 Por

# {A} se denota el n´ umero de elementos del conjunto A.

8

2.1.

Ejemplo

Sean los vectores inputs X dados por17 las dos primeras columnas de la tabla 1 y donde la tercera columna de esa misma tabla representa la etiqueta sexo. La soluci´ on y otros resultados interesantes aparecen recogidos en la tabla 1. Se observa que la soluci´ on se determina a partir de s´ olo tres vectores, que el conjunto de entrenamiento es separable y por tanto la soluci´ on clasifica correctamente todos los vectores. De estos valores se sigue que el αi

π(xi1 , xi2 )

1

0

21.2230

1

1

1.2346

1.0000

1

80

1

0

23.4450

1

176

70

1

0

6.5558

1

160

65

1

0

2.3330

1

160

61

-1

0

-3.8894

-1

162

62

-1

0

-2.7782

-1

168

64

-1

0.3210

-1.0000

-1

164

63

-1

0

-1.6670

-1

175

65

-1

0.9136

-1.0000

-1

x1i

x2i

yi

180

80

173

66

170

signo(π)

Tabla 1: Resultados del ejemplo. hiperplano separador es : π(x1 , x2 ) : −0,2222x1 + 1,5556x2 − 63,22893 = 0 (x1 y x2 denotan la primera y segunda componente de un vector x ∈ IR2 ). N´ otese como la imagen de cada vector soporte seg´ un el plano π es la unidad lo que significa que se encuentran en uno de los dos hiperplanos separadores. Si se tiene un nuevo vector input (altura y peso de una persona), por ejemplo {195, 95}, la soluci´ on se interpreta a partir del signo de π(195, 95) = 41,224 > 0 lo que significa que la etiqueta que nosotros le asignamos es y = 1, es decir, se indicar´ıa que esta nueva persona es un hombre.

2.2.

SVMs para datos no separable

En la pr´ actica no es habitual trabajar con conjuntos separables. En estos casos (ver en la figura 4) se encuentran vectores de una clase dentro de la regi´ on correspondiente a los vectores de otra clase y por tanto nunca podr´ an ser separados de esta clase por medio de hiperplanos. En estas situaciones se dir´ a que el conjunto es no separable. Ante estos casos, el problema de optimizaci´ on (3), no encuentra una soluci´ on posible y ello es evidente sin m´ as que observar como la funci´ on objetivo (4) crece de forma arbitraria ya que el multiplicador de Lagrange correspondiente a este vector se puede tomar arbitrariamente grande sin que viole las restricciones. Sin embargo, 17 Este

ejemplo esta tomado de [16]. Los inputs son de dimensi´ on dos, la primera componente representa la altura en

cent´ımetros y la segunda el peso en kilogramos de una persona. Las salidas son y = 1 si es hombre e y = −1 si es mujer.

9

A

π1

B

π π2

Figura 4: Ejemplo de hiperplanos separadores para el caso de datos no separables. no es dif´ıcil ampliar las ideas generales del caso separable al caso no separable introduciendo una variable ξ de holgura en las restricciones y plantear un nuevo conjunto de restricciones: xi · w + b

≥

+1 − ξi

para yi = +1

xi · w + b

≤

−1 + ξi

para yi = −1

ξi

≥

0

∀i = 1, · · · , n

Se tiene ahora que para que se produzca un error en la clasificaci´ on de un vector de entrenamiento (una entrada no es ubicada en la clase correcta) es necesario que el valor correspondiente a ξi sea superior a la unidad. As´ı, si en el vector xi se comete un error entonces ξi ≥ 1 y por tanto

i

ξi

es una cota superior del n´ umero de errores que se cometen dentro del conjunto de entrenamiento. Ya que en el caso no separable, necesariamente se han de cometer errores, parece natural asignar a la funci´ on objetivo un coste extra que en “cierto modo” penalice los errores (funci´ on de p´erdida). Por todo ello, una opci´ on l´ ogica ser´ıa plantear el problema de minimizar 1 kwk2 + C 2

n

ξik i=1

con k ≥ 1. ¿C´ omo se interpreta esta funci´ on objetivo? Si se considera un valor C grande, significa que el investigador est´ a asignando un peso a los errores muy alto frente a kwk2 , y por el contrario si C es peque˜ no asigna un mayor peso a kwk2 . Esta interpretaci´ on resulta m´ as intuitiva si se interpreta que kwk2 es un factor de suavizamiento de la soluci´ on buscada. Por otro lado si k es grande lo que hacemos es dar mucho m´ as peso a los errores cuantos mayores sean ´estos. Se llega por tanto a plantear un problema de programaci´ on convexa para cualquier valor de k. Si k=2o ´ k = 1 se tiene un problema de programaci´ on convexa cuadr´ atico. En el presente trabajo se considera k = 1 ya que en este caso se tiene la ventaja de que ning´ un valor ξi , ni ninguno de sus correspondientes multiplicadores de Lagrange, aparecen en el problema dual. Por tanto el problema de optimizaci´ on que se plantea es: 1 kwk2 + C 2

m´ın

w∈IRd


s.a.



n

ξi i=1

yi (xi · w + b) − 1 + ξi ≥ 0, ∀ i ξi ≥ 0, ∀ i

10

(6)

Utilizando la t´ecnica de los multiplicadores de Lagrange se llega a la funci´ on objetivo dual n

LD (α) =

αi − i=1

1 2

n

α i α j yi yj x i x j i,j=1

la cual hay que maximizar respecto αi sujeta a n

α i yi = 0

0 ≤ αi ≤ C, i = 1, · · · , n i=1

y cuya soluci´ on final viene dada por NSV

w=

α i yi s i i=1

donde NSV denota el n´ umero de vectores soporte y por si los vectores soporte del conjunto {x1 , · · · , xn }. Claramente NSV ≤ n y una de las caracter´ısticas m´ as interesante de estos modelos es que eligiendo adecuadamente los par´ ametros es posible conseguir que NSV sea muy inferior a n con lo que se consigue una representaci´ on “corta” de la soluci´ on en funci´ on de los vectores de entrada sin perder capacidad de generalizaci´ on. En problemas econ´ omicos, donde se trabaje con una cantidad ingente de datos, y se necesita dar una r´ apida respuesta frente a una nueva entrada, este esquema resulta muy atractivo puesto que la cantidad de recursos necesarios para proporcionar una salida es “peque˜ na” en comparaci´ on con la cantidad de datos de entrenamiento18 . N´ otese, que la u ´nica diferencia en la soluci´ on con respecto a la dada en el caso separable es que los multiplicadores de Lagrange αi , est´ an acotados superiormente por la constante C. Las condiciones de KKT asociada a este problema son las siguientes: ∂ LP = wj − ∂wj

n

αi yi xij

=

0

=

0

=

0

≥

0

ξi , α i , µ i

≥

0

αi (yi (xi · w + b) − 1 + ξi )

=

0

(8)

µ i ξi

=

0

(9)

i=1 n

∂ LP = − α i yi ∂b i=1 ∂ LP = C − α i − µ i ∂ξi yi (xi · w + b) − 1 + ξi

(7)

Como se coment´ o en el caso separable, se pueden usar las condiciones complementarias de KKT (las igualdades (8) y (9)), para determinar el valor de b. N´ otese que la ecuaci´ on (7) combinada 18 En

este punto es importante rese˜ nar que del an´ alisis por ordenador de problemas multidimensionales altos result´ o el

descubrimiento que R. Bellman denomin´ o, “la maldici´ on de la dimensionalidad”, ya que observo que incrementando el n´ umero de factores que deb´ıan ser tomados en consideraci´ on, estos requer´ıan un incremento exponencial de la cantidad de recursos computacional.

11

con la ecuaci´ on (9) muestra que, si ξi = 0 entonces αi < C. As´ı se puede simplificar el c´ alculo de b tomando los vectores de entrenamiento tales que 0 < αi < C y usar la ecuaci´ on (8) con ξi = 0 (como ya se indic´ o anteriormente es m´ as adecuado promediar este valor entre todos los vectores de entrenamiento con ξi = 0).

2.3.

Modelos te´ oricos SVMs

Como resumen de lo se˜ nalado hasta ahora en esta secci´ on se sigue que en el problema de minimizaci´ on (6) se busca determinar un hiperplano separador o ´ptimo: π ≡ f (x; w, b) = hw, xi + b = 0 donde w ∈ IRd y b ∈ IR son par´ ametros que deben ser estimados. Por ello se puede considerar que el conjunto de funciones F sobre la que se busca la soluci´ on al problema (6) es F = f (x; w, b) = hw, xi + b, w ∈ IRd , y ∈ IR




es decir, que m´ın LP (x; w, b) = m´ın LP (x, f ) f ∈F

w∈IRd

y LP (x; f ) puede ser considerado como un riesgo regularizado (ver en [9]) Rreg [f ] por lo que m´ın LP (x; w, b) = m´ın Rreg [f ] f ∈F

w∈IRd

Por otro lado, ya que una vez determinado el valor o ´ptimo de w, a partir de las condiciones de KKT se obtiene el par´ ametro b, el objeto principal de estudio se reduce en esencia al vector de par´ ametros w ∈ IRd . Este vector de par´ ametros se obtiene seg´ un una combinaci´ on lineal de los vectores del conjunto de entrenamiento por la expresi´ on w =

N i=1

αi yi xi de donde se sigue que

la funci´ on soluci´ on al problema de clasificaci´ on se expresa: n

f (x) =

αi yi hxi , xi + b.

(10)

i=1

3.

M´ aquinas no lineales de vectores soporte En esta secci´ on se aborda el problema de generalizar los desarrollos anteriores para el caso

de clases de funciones no necesariamente lineales en los par´ ametros. Para ello, obs´ervese que los vectores de entrada forman parte de la soluci´ on (10) del problema de clasificaci´ on, a trav´es de los productos escalares, hxi , xi. Utilizando la idea dada en [1] se sigue: Sea una aplicaci´ on Φ del conjunto de entradas X , en un espacio H (denominado espacio caracter´ıstico) dotado de un producto escalar. Φ : X ⊂ IRd −→ H. Ahora, en lugar de considerar el conjunto de vectores {x1 , · · · , xn } se considera los vectores transformados {Φ(x1 ), · · · , Φ(xn )} y si se plantea el problema de optimizaci´ on original a estos

12

vectores se tiene que los nuevos vectores forman parte de la soluci´ on del problema solo a trav´es del producto escalar definido en H: hΦ(xi ), Φ(x)i. As´ı, si se considera una funci´ on k : H × H → IR (denominada funci´ on n´ ucleo), tal que k(x, x0 ) = Φ(x) · Φ(x0 ) = hΦ(x), Φ(x0 )iH solo es necesario conocer la funci´ on n´ ucleo para resolver el algoritmo y no se necesita tener la forma expl´ıcita de la aplicaci´ on Φ. Por tanto si se reemplaza hxi , xi por k(xi , x) en la soluci´ on de los problemas de optimizaci´ on, se habr´ a conseguido una m´ aquina de vectores soporte planteada en un nuevo espacio, y adem´ as, lo que resulta muy importante en la pr´ actica, la ejecuci´ on de un programa que lleve a cabo esta t´ecnica no lineal, consume la misma cantidad de recursos computacionales que si la t´ecnica fuese lineal. Al resolver este problema en H, donde se trabaja con funciones lineales, la soluci´ on que resulta es lineal en ´el, pero no es necesariamente lineal en el espacio de entradas X , con lo cual se esta generalizando el problema a conjuntos de funciones no lineales. Si se lleva a cabo la transformaci´ on de los datos, el vector soluci´ on es NSV

w=

αi yi Φ(si )

(11)

i=1

donde Φ(si ) denota los vectores soporte del conjunto {Φ(x1 ), · · · , Φ(xn )}. Es importante notar que los vectores soporte se encuentran dentro del conjunto {Φ(x1 ), · · · , Φ(xn )}, se denotan por Φ(si ) pero no son necesariamente los transformados de los vectores soporte si que se encuentran dentro del conjunto {x1 , · · · , xn }, entre otras cosas porque con los vectores sin transformar no se realiza ning´ un algoritmo, a pesar de esta indicaci´ on se sigue con esta notaci´ on, puesto que es la utilizada tradicionalmente. Aunque la aplicaci´ on Φ aparece en la soluci´ on (11) se tiene que cuando se realiza la fase de prueba, no se necesita tener de forma expl´ıcita ya que la soluci´ on queda: NSV

f (x) =

αi yi hΦ(si ), Φ(x)i + b i=1

y escrita en t´erminos de la funci´ on n´ ucleo: NSV

f (x) =

αi yi k(si , x) + b i=1

Una importante consecuencia de la representaci´ on dual (en t´erminos del n´ ucleo) es que la dimensi´ on del espacio caracter´ıstico no afecta a los c´ alculos ya que la u ´nica informaci´ on necesaria se encuentra en la matriz de orden n×n: {k(xi , xj )}n i,j=1 (denominada matriz de Gram). Un esquema de esta construcci´ on se encuentra en la figura 5 y un ejemplo gr´ afico de la soluci´ on aportada por la SVM al ejemplo aparece en la figura 6.

13

x1 , x 2 , · · · , x n , x

Espacio de entradas

? φ(x1 ), φ(x2 ), · · · , φ(xn ), φ(x)

Espacio Caracter´ıstico

? k(x1 , x), k(x2 , x), · · · , k(xn , x)

N´ ucleos

? f (x) =

n X

αi k(xi , x) + b

Funci´ on soluci´ on

i=1

Figura 5: Las m´ aquinas de vectores soporte transforman, inicialmente, el espacio de entradas en un espacio caracter´ıstico de dimensi´ on superior y entonces construye la funci´ on de clasificaci´ on lineal o ´ptima dentro de este nuevo espacio. Al usar Φ : X → H se trabaja en un nuevo espacio H por lo cual el vector soluci´ on w se encuentra en este espacio. Por tanto, puede ocurrir que sobre el conjunto X inicial no se tenga definida ning´ un tipo de estructura, y la funci´ on Φ sirve para dar una estructura19 a los datos y poder aplicar una adecuada clasificaci´ on. Esta idea aparece recogida en el trabajo [11] donde se presenta una funci´ on n´ ucleo concreta y sobre todo una forma de hacer frente a la construcci´ on de funciones n´ ucleos a partir de una interpretaci´ on de similitud entre vectores de entrada. Por otro lado, dado un espacio H dotado de un producto escalar habr´ıa que estudiar que propiedades deben cumplir las funciones k : X ×X → H que permiten construir un par {Φ, H}, con las propiedades descritas anteriormente, es decir, ser funciones n´ ucleos. Un an´ alisis detallado de este punto puede encontrarse entre otros en [9], [5] y [18]. 19 Una

forma de verlos.

14

Figura 6: Soluci´ on gr´ afica al problema planteado en la secci´ on 2.1 a partir de una funci´ on n´ ucleo (gaussiano). Los puntos “+”en negro representan los vectores de entrada con etiqueta 1 (hombres) y los puntos “+”en rojo los de etiqueta −1 (mujeres). Los puntos en c´ırculos representan los vectores soporte.

3.1.

Clasificaci´ on m´ ultiple

Generalizamos los problemas de clasificaci´ on a etiquetas m´ ultiples. As´ı sea el conjunto de etiquetas posibles {θ1 , · · · , θ` }, siendo ` > 2 y sin una relaci´ on de orden definida entre ellas. Sea Z el conjunto de entrenamiento y se construyen los subconjuntos Zk = {(xi , yi ), tales que yi = θk } que determinan una partici´ on de Z. Denotamos por nk el n´ umero de vectores de entrenamiento del conjunto Zk (n = n1 + n2 + · · · + n` ); y por Ik el conjunto de ´ındices i tales que (xi , yi ) ∈ Zk de donde se sigue que

i∈Ik

{(xi , yi )} = Zk .

La forma, m´ as habitual, de utilizaci´ on de las m´ aquinas de vectores soporte para resolver problemas de multiclasificaci´ on admite dos tipos de arquitectura: SVMs biclasificadoras generalizadas: Construyen una funci´ on clasificadora global a partir de un conjunto de funciones clasificadoras dicot´ omicas (biclasificadoras). SVMs multiclasificadoras: Construyen una funci´ on clasificadora global directamente considerando todas las clases a la vez. Las SVMs multiclasificadoras plantea un problema de optimizaci´ on similar a las SVMs biclasificadoras que posteriormente resuelve. Tienen el inconveniente que proporciona una salida final y el proceso de obtenci´ on de esta salida es como una caja negra que no admite ninguna reconstrucci´ on posterior.

15

Las SVMs biclasificadoras generalizadas dan soluci´ on al problema de la multiclasificaci´ on transformando las ` particiones del conjunto de entrenamiento en un conjunto de L biparticiones, en las cuales construye la correspondiente funci´ on clasificadora (es lo que se denomina esquema de descomposici´ on) obteniendo f1 , · · · fL clasificadores dicot´ omicos o biclasificadores. A continuaci´ on, mediante un esquema de reconstrucci´ on, realiza la fusi´ on de los biclasificadores fi , i = 1, · · · , L con objeto de proporcionar como salida final, una de las ` clases posibles, {θ1 , · · · , θ` }. Dentro del esquema de descomposici´ on, las m´ aquinas m´ as utilizadas son: M´ aquinas 1-v-r SV (iniciales de one- versus- rest). M´ aquinas de vectores soporte, donde cada funci´ on clasificadora parcial fi , enfrenta los vectores de la clase θi contra los vectores de las restantes clases. M´ aquinas 1-v-1 SV (iniciales de one- versus- one). M´ aquinas de vectores soporte, donde cada funci´ on clasificadora parcial fij , enfrenta los vectores de la clase θi contra los de la clase θj , sin considerar las restantes clases. En estos casos para la reconstrucci´ on del problema se utiliza alg´ un esquema de votaci´ on que tenga en cuenta la distribuci´ on de las etiquetas asignadas por las m´ aquinas parciales: Etiquetas

Votos

θ1 .. .

m1 .. .

θk .. .

mk .. .

θ`

m` `·(`−1) 2

donde mk es el n´ umero de votos que las m´ aquinas fi , i = 1, · · · ,

4.

`·(`−1) 2

dan a la etiqueta θk .

Comentarios Los n´ ucleos proporcionan el lenguaje descriptivo usado por la m´ aquina para ver los datos.

Frecuentemente, el dise˜ nador puede trabajar con una noci´ on m´ as intuitiva de similitud en el espacio de los inputs y es ah´ı donde los expertos pueden dar una gu´ıa inigualable de una apropiada medida de similitud. Dentro de los problemas econ´ omicos, la elecci´ on de los n´ ucleos nos permitir´ a tener a nuestra disposici´ on un gran n´ umero de modelos no param´etricos con la ventaja de poder interpretar las caracter´ısticas del modelo, gracias a la linealidad del espacio caracter´ıstico. La introducci´ on de los n´ ucleos aumenta significativamente la potencia de las m´ aquinas de aprendizaje a la vez que retiene la linealidad que asegura que los aprendizajes resulten comprensibles. El incremento de la flexibilidad, sin embargo, incrementa el riesgo de sobreajuste con la elecci´ on de hiperplanos separables que aumentan los problemas debido al n´ umero de grados de libertad. El control adecuado de la flexibilidad del espacio caracter´ıstico inducido por los n´ ucleos requiere una teor´ıa de generalizaci´ on, la cual sea capaz de describir con precisi´ on que factores han

16

de ser controlados en las m´ aquinas de aprendizaje con objeto de garantizar unas buenas generalizaciones. Este control de la capacidad de generalizaci´ on queda recogido en [5] donde se dan diferentes teoremas que permiten afirmar que para cualquier distribuci´ on seguida por los datos y considerando el dominio de las funciones f ∈ F, una bola de radio R centrada en el origen que contengan todos los vectores xi , se sigue que con probabilidad al menos 1 − η sobre una muestra de tama˜ no n, se tiene para todas f ∈ F, el error de ensayo m´ınf ∈F P (Af ) puede ser controlado a partir de kwk2 + λ

n i=1

ξi lo cual da pleno sentido a las m´ aquinas de vectores soporte.

Indicar que s´ olo despu´es de llevar a cabo un proceso de aprendizaje se puede conocer cual es la complejidad de la hip´ otesis resultante. Este tipo de an´ alisis, el cual proporciona una forma de explotar las buenas condiciones entre la funci´ on objetivo y la distribuci´ on de las entradas, es llamada minimizaci´ on del riesgo estructural dependiente de los datos. Los multiplicadores de Lagrange asociados con cada input, en la soluci´ on aportada por las m´ aquinas de vectores soporte, llegan a ser las variables duales, dando con ello una interpretaci´ on intuitiva que cuantifica como de importante es un vector de entrenamiento dado en la formaci´ on de la soluci´ on final. Para muchas clases de n´ ucleos, siempre es posible encontrar un par´ ametro del n´ ucleo para el cual los datos llegan a ser separables (en general forzar esta separaci´ on puede conducir f´ acilmente al sobreajuste). En estos casos, los outliers podr´ıan ser caracterizados por tener multiplicadores de Lagrange muy grandes, y este procedimiento podr´ıa ser usado para depurar los datos ya que ello puede clasificar los datos de entrenamiento de acuerdo a la dificultad que ellos presentan para una clasificaci´ on correcta. La idea de representar la soluci´ on por medio de un peque˜ no subconjunto del conjunto de entrenamiento tiene una enorme ventaja de c´ alculo. La implementaci´ on de estas t´ecnicas pasa por plantear una funci´ on objetivo con tantas restricciones como n´ umero de entradas, lo cual conduce a un problema de una elevada complejidad de c´ alculo. Existen distintas direcciones de p´ aginas web, por ejemplo: http://www.support-vector.net http://www.kernel-machines.org http://svm.first.gmd.de http://www.syseng.anu.edu.au/lsg/ donde se pueden encontrar muchos art´ıculos donde se estudian diferentes formas de optimizar estas t´ecnicas, as´ı como comparativas con otras t´ecnicas que resuelven problemas similares. Los modelos basados en SVMs pueden ser tambi´en aplicado a los problemas de estimaci´ on de la regresi´ on, manteniendo las principales caracter´ısticas de los problemas de clasificaci´ on: una funci´ on no lineal es buscada, a trav´es de una m´ aquina lineal, en un espacio caracter´ıstico inducido por un n´ ucleo mientras la capacidad del sistema es controlada por un par´ ametro que no depende de la dimensionalidad del espacio. En la p´ agina web: http://www.clopinet.com/isabelle/Projects /SVM/applist.html se puede encontrar diferentes aplicaciones de estos modelos a problemas reales, donde se obtie-

17

nen resultados muy satisfactorios. Algunos de los problemas que resuelven se encuentran en los siguientes campos: Clasificaci´ on de im´ agenes, Aproximaci´ on de funciones y regresi´ on, Reconocimiento de objetos en 3D, Caracterizaci´ on de textos, Reconocimiento de caracteres de escritura, ´ Predicci´ on de series temporales y Reconstrucci´ on de sistemas ca´ oticos, Arboles de decisi´ on, ...... La aplicaci´ on de estas t´ecnicas a problemas econ´ omicos no han sido a´ un muy utilizadas, sin embargo algunas referencias son: [2] estudia el problema de clasificaci´ on de empresas (rating) [14] donde se plantea un modelo de regresi´ on que explica el precio de la casas en Boston, a partir de 15 variables explicativas continuas, y compara la soluci´ on aportada por una m´ aquina de vectores soporte con una regresi´ on en cordillera (ridge) y otra regresi´ on en a ´rbol; [4] plantea a ´rboles de decisi´ on en bases de datos comerciales y lo compara con otros m´etodos est´ andar de clasificaci´ on. [6] Plantea a trav´es de un problema de clasificaci´ on una modelo de predecir bancarrotas aplicadas a un conjunto de bancos australianos. [17] se presentan algunos resultados sobre precios de stocks En estos trabajos se compara los modelos SVMs con otros (redes neuronales, a ´rboles de decisi´ on,...) y se obtiene unos resultados muy satisfactorios.

5.

Conclusiones y trabajos futuros Poco a poco la comunidad cient´ıfica esta cada vez m´ as convencida de la utilidad de las SVMs y

as´ı se pone de manifiesto cuando, por ejemplo, buscamos una palabra clave relacionada con est´ as t´ecnicas en los buscadores de internet y observamos el alto n´ umero de referencias que aparecen. Sin embargo, a´ un son pocas las aplicaciones de esta metodolog´ıa en problemas econ´ omicos. En la actualidad estoy trabajando con compa˜ neros de otras universidades con el objetivo de generalizar las SVMs a problemas de multiclasificaci´ on en dos sentido: en primer lugar incorporando una interpretaci´ on probabil´ıstica de las salidas, parte de estas investigaciones se encuentran en [12]; y en segunda lugar, mejorando algunas deficiencias que presentan las SVMs 1-v-1 cuyos trabajos van por buen camino y nos han aceptado una comunicaci´ on en ESANN2003 [3].

Referencias [1] M.A. Aizerman, E.M. Braverman, and L.I. Rozono´er. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, (25):821– 837, 1964. [2] C. Angulo. Aprendizaje con m´ aquinas n´ ucleos en entornos de multiclasificaci´ on. Tesis doctoral, Universidad Polit´ecnica de Catalu˜ na, Abril 2001.

18

[3] C. Angulo and L. Gonz´ alez. 1-v-1 tri-class sv machine. ESANN’2003, 2003. [4] K. Bennett and L. Auslender. On support vector decision trees for database marketing. Bajado de http://www.clopinet.com/ isabelle/ Projects/ SVM/ applist.html, Marzo 1998. [5] N. Cristianini and J.Shawe-Taylor. An introduction to Support Vector Machines and other kernel-based learning methods. Cambridge University press 2000, 2000. [6] A. Fan and M. Palaniswami. Selecting bankruptcy predictors using svm approach. IEEE, 2000. [7] R. Fletcher. Practical methods of optimization. John Wiley and Sons, Inc, 2 edition, 1987. [8] S. German and E. Bienenstock. Neural networks and the bias / variance dilemma. Neural Computation, 4:1-58, 1992. [9] L. Gonz´ alez. Teor´ıa del aprendizaje estad´ıstico de la regresi´ on. M´ aquinas de regresi´ on de vector base. Trabajo interno del departamento de econom´ıa aplicada i, Facultad de Ciencias Econ´ omicas y Empresariales, Universidad de Sevilla, Diciembre 2000. [10] L. Gonz´ alez. An´ alisis discriminante utilizando m´ aquinas n´ ucleos de vectores soporte. Funci´ on n´ ucleo similitud. Tesis doctoral, Dpto. Econom´ıa Aplicada I. Universidad de Sevilla, Junio 2002. [11] L. Gonz´ alez and J.M. Alba. Similitud entre sucesos. Terceras Jornadas de Trabajo sobre Metodolog´ıas Cualitativas Aplicadas a los Sistemas Socioecon´ omicos, Julio 2001. [12] L. Gonz´ alez, C. Angulo, F. Velasco, and M. Vilchez. M´ aquina `-SVCR con salidas probabil´ısticas. Inteligencia Artificial, (17):72–82, september 2002. [13] I. Guyon, V. Vapnik, B. Boser, L. Bottou, and S. Solla. Structural risk minimization for character recognition. Advances in Neural Information Processing Systems, 4:471-479, 1992. [14] K.R. M¨ uller, A.J. Smola, G. R¨ atsch, B. Sch¨ olkopf, J. Kohlnorgen, and V. Vapnik. Predicting times series with support vector machine. Notas de trabajo, 1997. [15] D. Montgomery and Peck E. Introduction to Linear Regression Analysis. John Wiley and Sons, Inc. 2nd edici´ on, 1992. [16] M. Stitson, J. Weston, A. Gammerman, V. Vovk, and V. Vapnik. Theory of support vector machines. Informe T´ecnico. Bajado de http://svm.first.gmd.de/, 1996. [17] T. Trafalis and H. Ince. Svm for regression and applications to financial forecasting. IEEE, 2000. [18] V.N. Vapnik. Statistical Learning Theory. John Wiley & Sons, Inc, 1998.

19