Aspectos matemáticos en Máquinas de Vectores Soporte (SVM)

Facultad de Ciencias Trabajo Fin de Máster Máster en Matemáticas Aspectos Matemáticos en Máquinas de Vectores Soporte (SVM) Autor: Álvaro Valera Blanco Tutor/es: Luis Ángel García Escudero Índice general 1. Introducción al aprendizaje y aprendizaje supervisado 1 2. Caso separable linealmente (Hard-SVM) 3 3. Caso no separable linealmente (Soft-SVM) 19 4. Uso de Kernels 29 5. Algoritmo del Gradiente Estocástico 41 6. Implementación práctica y ejemplos 55 7. Algunas extensiones 65 A. Algoritmo del Perceptrón I Bibliografía 1 iii iv Capítulo 1 Introducción al aprendizaje y aprendizaje supervisado El Aprendizaje Automático, es una disciplina compartida entre la Informática, las Matemáticas y la Estadística que puede considerarse englobada bajo un epígrafe más general de Inteligencia Artificial, cuyo objetivo es desarrollar técnicas que permitan que las computadoras “aprendan”. Existen dos tipos de Aprendizaje Automático: el supervisado y no supervisado. Cuando se desea “predecir” variables a partir de aprender del comportamiento en datos proporcionados sobre una muestra patrón o de entrenamiento, es lo que se conoce como aprendizaje supervisado. Si no se dispone de ninguna muestra patrón o de entrenamiento, se habla de aprendizaje no supervisado y el objetivo es encontrar patrones o grupos de interés aprendiendo directamente del conjunto de datos. El Aprendizaje Estadístico juega un papel muy importante en muchas áreas como las finanzas y la industria y, en general, es uno de los pilares de la Ciencia de Datos (Data Science). El objetivo principal del aprendizaje supervisado es crear o estimar alguna función que sea capaz de poder predecir el valor de nuevas observaciones. Para ello lo que hace es generalizar lo que ha aprendido del conjunto de datos de entrenamiento a una nueva situación que no se haya visto anteriormente. Existen varios métodos dentro del aprendizaje supervisado en función del valor de salida, de clasificación si es una etiqueta de clase y de regresión si es un valor numérico. Diversos campos de las Matemáticas han sido útiles dentro del Aprendizaje Automático. En este trabajo nos centraremos en algunas de las aportaciones matemáticas a los Support Vector Machines. Los Support Vector Machines, conocidos en castellano como máquinas de vectores de soporte (SVM), es una técnica de clasificación de aprendizaje supervisado que tiene su origen en los años 90 con Vladimir Vapnik, y co-autores, y ha ido ganando popularidad desde entonces en muchos campos como la Estadística, la Minería de Datos y la Inteligencia Artificial. Esto se debe a sus sólidos fundamentos teóricos, ya que utiliza conceptos bien establecidos y desarrollados de la teoría de optimización. Esta rama de las Matemáticas es muy importante para el aprendizaje supervisado y los Support Vector Machines en particular. Lo que se trata de hacer es una predicción a partir de un problema de optimización geométrica, el cual se puede escribir como un problema de optimización cuadrático conve- 1 xo con restricciones lineales, que por lo general, puede resolverse mediante procedimientos no lineales. Para ello se pretende buscar un hiperplano de separación óptimos tras, en la mayoría de las ocasiones, llevar el problema a espacios de dimensiones mayores donde los datos transformados puedan estar mejor separados. Originariamente los SVM’s se presentaron como una técnica para resolver problemas de clasificación binaria. Actualmente, se pueden utilizar para resolver otro tipo de problemas, por ejemplo, multiclase, de regresión o en detección de anomalías. El objetivo de este Trabajo de Fin de Máster (TFM) es analizar numerosos aspectos de carácter más matemático que subyacen bajo la metodología SVM. En primer lugar, en los Capítulos 2 y 3, nos centraremos en la clasificación binaria, sobre todo en los aspectos computacionales tanto del caso linealmente separable como del no separable linealmente. A continuación, en el Capítulo 4, veremos cómo si los datos no son separables linealmente, podemos pasar a dimensiones superiores donde sí serán más fácilmente separables y utilizaremos lo que se conoce como “kernel trick”. En el siguiente Capítulo 5, veremos un algoritmo, que se ha desarrollado relativamente hace poco, que sirve para resolver los problemas de optimización relacionados con la solución de los SVMs. En el Capítulo 6, se mostrara la implementación práctica de los SVM con el lenguaje de programación R. Por último, en el Capítulo 7, trataremos alguna extensión de los SVMs, junto con algunas conclusiones y posibles direcciones futuras. Para el desarrollo de este TFM se ha llevado a cabo un proceso de recopilación y análisis de información procedente de distintas fuentes que abordan esta temática. Los libros escogidos han sido [1, 2, 3, 4]. La elección de estos libros se ha basado en su reconocimiento como obras de referencia en el área de estudio, cada uno aportando una perspectiva valiosa sobre algunos aspectos clave de los SVM. Al unificar y dar coherencia a los fragmentos seleccionados de cada uno de estos libros, se ha tratado de establecer un hilo conductor común, buscando asegurar cierta consistencia en la presentación de contenidos. Se han realizado análisis comparativos e identificado los puntos clave en los que los libros seleccionados proporcionaban una explicación más clara o ilustrativa y estos fragmentos se han integrado en la memoria del TFM tratando de ofrecer una perspectiva matemáticamente razonada del SVM. 2 Capítulo 2 Caso separable linealmente (Hard-SVM ) Un problema de aprendizaje binario de dos clases es un problema en el que se busca encontrar un procedimiento para clasificar elementos en dos grupos diferentes. En este tipo de problemas se tiene una variable objetivo, o variable a predecir, binaria, que puede tomar dos valores posibles y que en el SVM se suele codificar como 1o−1. En el contexto de Aprendizaje Automático, el problema de optimización binaria a menudo se refiere a la clasificación binaria, donde se busca encontrar un modelo que pueda separar dos clases diferentes de datos. Supongamos que tenemos disponible un conjunto de datos de aprendizaje, es decir, sea C={(x1, y1),(x2, y2),...,(xn, yn) : xi∈Rp, yi∈ {−1,1}} (2.1) un conjunto de observaciones de entrenamiento, donde cada par (xi, yi)se conoce como observación, siendo el vector xiun conjunto de pcaracterísticas, también conocido como vector de variables predictoras e yila clase a la que pertenece dicha observación, la variable que tenemos que predecir. El problema de clasificación binaria en el cual nos centraremos en los próximos capítulos se basa en usar el conjunto de observaciones Cpara construir una función f:Rp→R tal que Q(x) = sign(f(x)) (2.2) sea un clasificador. La función separadora fnos permite por tanto, separar cada nuevo punto xen las dos clases existentes, dependiendo si Q(x)es 1, es decir, si f(x)≥0, o es −1, si f(x)<0. Existen dos tipos de conjuntos de observaciones de entrenamiento Cque nos permitirán realizar distintos tipos de clasificación. Puede suceder que todas las observaciones del conjunto se puedan separar mediante un hiperplano, es decir, cada una está en el semiplano de la clase correspondiente, entonces diremos que el conjunto de observaciones es separable, o que no pueden separarse todas las observaciones, por tanto diremos que el conjunto es no separable. En este capítulo nos centraremos en el caso linealmente separable. Primero veamos la definición de hiperplano: 3 Definición 2.1. Un hiperplano es un subespacio afín plano de dimensión p−1y, de forma analítica, está definido por nx= (x1, ..., xp)T:β0+β1x1+β2x2+···+βpxp= 0o,(2.3) para los parámetros β0, β1, . . . , βpen R. De manera equivalente, se puede escribir en forma matricial como nx:β0+βTx= 0o(2.4) Propiedades 2.2. Algunas propiedades que presentan los hiperplanos son las siguientes Para dos puntos cualquiera del hiperplano x1yx2se cumple βT(x1−x2)=0y por tanto β∗=β/kβkes el vector normal al hiperplano. Para cualquier punto x0del hiperplano, se tiene βTx0=−β0. La distancia de cualquier punto xdel espacio Sal hiperplano viene dada por β∗T(x−x0) = 1 kβk(βTx+β0) = 1 kβkf(x),(2.5) Por tanto f(x)es proporcional a la distancia desde xal hiperplano definido por f(x) = 0. A lo largo de la historia, han sido varios los algoritmos que han ido apareciendo para resolver el problema de la separación lineal. Un antecedente muy importante de los SVM es el “perceptrón” propuesto en 1956 por Frank Rosenblatt, que discutiremos en el Apéndice A. Decimos que un conjunto Ccomo el que se proporciona en (2.1), es separable linealmente si existe un hiperplano que es capaz de separar dicho conjunto clasificando correctamente todas las observaciones en función del lado del hiperplano en el queden las observaciones. Un hiperplano de este tipo será conocido como hiperplano de separación y proporciona una función lineal f(x) = βTx+β0,(2.6) donde β∈Rpyβ0∈R, que nos permite clasificar nuevas observaciones en función del signo de f(x)como se ha comentado en (2.2). En consecuencia, para todas las observaciones del conjunto de entrenamiento C, se deben cumplir las siguientes restricciones f(xi) = βTxi+β0>0si yi= 1,(2.7) y f(xi) = βTxi+β0<0si yi=−1.(2.8) Ambas ecuaciones (2.7) y (2.8) pueden escribirse de forma única como yi(βTxi+β0) = yif(xi)>0para todo i= 1, . . . , n. (2.9) 4 Este hiperplano de separación de las dos clases si existe, no suele ser único, existe un número infinito de dichos hiperplanos. Esto lo podemos observar en la Figura 2.1, ya que un hiperplano puede desplazarse un poco hacia arriba o hacia abajo y rotar sin llegar a tocar ninguna de las observaciones. Figura 2.1: Múltiples hiperplanos separando dos clases linealmente separables Un método para elegir el mejor hiperplano que separe las observaciones de entre esos infinitos que hay, es elegir aquel que esté más alejado de todas las observaciones. Para ello se define el “margen” Mcomo la mínima distancia entre el hiperplano de separación y la observación más próxima a él de las dos clases. Este hiperplano que separa a las dos clases y maximiza la distancia a las observaciones más cercanas de cada una de ellas se conoce como “hiperplano de margen máximo” o también como “hiperplano de separación óptimo”. A esta regla de clasificación se la conoce como Hard-SVM. Por hipótesis hemos supuesto que el conjunto de observaciones, C, es linealmente separable, por tanto, existen βyβ0tales que se cumplen las siguientes desigualdades para cualquier observación del conjunto de entrenamiento, βTxi+β0≥+1,si yi= +1 (2.10) βTxi+β0≤ −1,si yi=−1.(2.11) Aquellas observaciones que cumplan la igualdad en (2.10), pertenecen al hiperplano H+1 : βTxi+β0= 1, y aquellas que cumplan la igualdad en (2.11) están en H−1:βTxi+β0=−1. A estas observaciones que caen en alguno de estos dos hiperplanos, es decir, están justo en el margen del Hard-SVM se las conoce como vectores soporte, del inglés “support vectors”, y veremos como van a jugar un papel muy importante en los SVM’s. El Hard-SVM proporciona una solución única al problema del hiperplano de separación como se puede observar en la Figura 2.2. Además se puede ver que en este conjunto de datos hay 3 vectores soporte. 5 principal ventaja de transformar un problema primal en su dual es que en los problemas de optimización que trataremos, asociados al SVM, suele ser notablemente más fácil resolver el problema dual que el primal. A continuación, mostramos un teorema conocido como el Teorema de la Dualidad Débil, que nos da una de las relaciones fundamentales entre ambos problemas, proporcionando la relación existente entre las soluciones de los dos problemas. Teorema 2.11 (de la Dualidad Débil).Sea x∈Ωuna solución factible del problema primal (2.19) y(α, µ)una solución factible del problema dual asociado. Entonces f(x)≥ θ(α, µ). Demostración. De la definición de θ(α, µ)para x∈Ω, se tiene θ(α, µ) = ´ınf y∈ΩLP(y, α, µ) ≤LP(x, α, µ) =f(x) + αg(x) + µh(x)≤f(x), (2.24) ya que como xes una solución factible para el problema primal, implica que cumple todas sus restricciones, es decir, g(x)≤0yh(x)=0y(α, µ)es solución factible para el problema dual implica α≥0. Este teorema, como se ha comentado anteriormente, proporciona dos corolarios muy útiles e interesantes. El primero establece que el problema dual está acotado superiormente por el problema primal. Corolario 2.12. El valor óptimo del dual está acotado superiormente por el valor óptimo del primal, es decir sup{θ(α, µ) : α≥0} ≤´ınf{f(x) : g(x)≤0, h(x) = 0}. Este otro corolario, permite obtener las soluciones de ambos problemas cuando se cumplen determinadas condiciones. Corolario 2.13. Si f(x∗) = θ(α∗, µ∗)con α∗≥0yg(x∗)≤0,h(x∗)=0, entonces x∗y(α∗, µ∗)son soluciones del problema primal y dual respectivamente. En este caso se cumple que α∗ igi(x∗) = 0 para i= 1, . . . , k. Demostración. Dado que los valores son iguales, la secuencia de desigualdades en la ecuación (2.24) debe convertirse en igualdades. En particular la última desigualdad solo puede ser igualdad si α∗ igi(x∗)=0para todo i. Estamos ahora en condiciones de enunciar el Teorema de Karush-Kuhn-Tucker que proporciona las condiciones suficientes, que denotaremos como condiciones KKT, para que un vector x∗sea una solución óptima del problema de optimización primal. Teorema 2.14 (de Karush-Kuhn-Tucker).Dado el problema de optimización cuadrático convexo (2.19), la solución óptima (x∗, α∗, µ∗)existe si y solo si se satisfacen las siguientes 12 condiciones ∂Lp(x∗, α∗, µ∗) ∂x= 0, ∂Lp(x∗, α∗, µ∗) ∂µ = 0, α∗ igi(x∗) = 0, i = 1, . . . , k, gi(x∗)≤0, i = 1, . . . , k, αi≥0, i = 1, . . . , k. (2.25) Supongamos ahora un caso particular en que el problema primal cuadrático convexo no tiene restricciones de igualdad, es decir, m´ın f(x),x∈Ω sujeto a: gi(x)≤0, i = 1, . . . , k. (2.26) Para este problema cuadrático convexo, se define la función de Lagrange como LP(x, α) = f(x) + k X i=1 αigi(x)(2.27) donde α= (α1, . . . , αk),αi≥0para i= 1, . . . , k, conocidos como los multiplicadores de Lagrange. A partir de esta función de Lagrange, se puede definir como hemos hecho anteriormente, para el caso general, el problema dual como m´ax θ(α), sujeto a: α≥0,(2.28) donde θ(α) = ´ınf x∈ΩLP(x, α). Para este problema (2.26), las condiciones KKT que tiene que cumplir un punto x∗ para que sea solución del problema primal vienen dadas por el siguiente resultado. Teorema 2.15. Dado el problema de optimización primal (2.26) convexo. Si existen las constantes αi≥0,i= 1, . . . , k (denominadas multiplicadores de Lagrange) tales que ∂Lp(x∗, α∗, µ∗) ∂x= 0 ⇔∂f(x∗) ∂xj + k X i=1 ∂gi(x∗) ∂xj = 0, j = 1, . . . , n α∗ igi(x∗)=0, i = 1, . . . , k. (2.29) entonces (x∗, α∗)es solución óptima del problema. La primera condición, conocida como primera condición KKT, surge como consecuencia de la definición de la función θ(α)como el inferior de la función de Lagrange, pues este se haya en el punto donde las derivadas parciales con respecto a xson cero. La segunda, se denomina condición complementaria, y garantiza que los óptimos de los problemas dual y primal coincidan, θ(α∗) = f(x∗), pues esto implica que todos los sumandos del sumatorio de la función de Lagrange serán cero. El Teorema de Karush-Kuhn-Tucker nos proporciona las condiciones que se tienen que cumplir para resolver el problema primal a partir del problema dual. Primero se 13 construye a partir del problema primal la función de Lagrange. Se aplica la primera condición de KKT a esta función que hace desaparecer todas las variables primales de esta. Además como hemos comentado antes, este paso es equivalente a calcular el inferior de la función de Lagrange. De esto, se obtiene la función de Lagrange del problema dual, que depende única y exclusivamente de los multiplicadores de Lagrange. De la primera condición KKT puede surgir alguna restricción adicional para los multiplicadores de Lagrange, las variables duales. Por último, para obtener la solución del problema primal basta con sustituir el resultado obtenido al resolver el problema dual, en las relaciones obtenidas al aplicar la primera condición KKT. Retomando nuestro problema de optimización cuadrática convexo. Hemos visto un resultado que dice que todo problema de optimización primal con función objetivo y restricciones estrictamente convexas tiene forma dual. En nuestro caso estas hipótesis se cumplen, ya que tanto la función objetivo como las restricciones son funciones convexas, ya que la función objetivo es cuadrática y las restricciones de desigualdad lineales, es decir, es un problema de optimización cuadrático y convexo y por tanto admite dual. Para ello, haremos uso de la función de Lagrange, que en nuestro problema primal ha de ser minimizada con respecto a βyβ0, y es LP(β, β0, α) = 1 2kβk2− n X i=1 αihyixT iβ+β0−1i,(2.30) donde αi≥0, i = 1, . . . , n, son los multiplicadores de Lagrange, que se denotan por α, siendo este el vector de multiplicadores de Kuhn-Tucker. Se puede observar que el signo menos del segundo sumando de esta función de Lagrange se debe a que en las restricciones de (2.18) están expresadas de la forma g(x)≥0en lugar de g(x)≤0. Derivando (2.30) con respecto a las variables βyβ0, que son las variables sobre las que se optimiza el problema primal, e igualando a cero, se tiene la primera condición de KKT. 0 = ∂LP(β, β0, α) ∂β =β− n X i=1 αiyixi, 0 = ∂LP(β, β0, α) ∂β0 =− n X i=1 αiyi, (2.31) es decir, las ecuaciones (2.31) nos permiten expresar βen términos de αiy establecer una restricción adicional para estos multiplicadores de Lagrange, esto es, β= n X i=1 αiyixi, n X i=1 αiyi= 0. (2.32) Si aplicamos la segunda condición de KKT, la condición complementaria, se tiene la siguiente igualdad αi(1 −yi(xT iβ+β0)) = 0 i= 1, . . . , n. (2.33) 14 Queremos construir el problema dual. Para ello, reescribimos (2.30) como L(β, β0, α) = 1 2kβk2− n X i=1 αiyixT iβ−β0 n X i=1 αiyi+ n X i=1 αi.(2.34) A continuación, sustituimos las igualdades (2.32) en (2.34), lo que hace que el tercer término de la parte de la derecha se anule y se obtenga la función de Lagrange que depende únicamente de los multiplicadores de Lagrange, L(α) = 1 2 n X i=1 αiyixi!  n X j=1 αjyjxj − n X i=1 αiyixi!  n X j=1 αjyjxj + n X i=1 αi, L(α) = −1 2 n X i=1 αiyixi!  n X j=1 αjyjxj + n X i=1 αi. Se obtiene así la función objetivo del problema dual, LD(α) = n X i=1 αi−1 2 n X i,j=1 αiαjyiyjxT ixj.(2.35) De esta manera, podemos definir el problema dual, que trata de encontrar un α∗que maximice la función (2.35) añadiendo las restricciones de no negatividad asociadas a los multiplicadores de Lagrange junto con la igualdades de (2.32), es decir m´ax LD(α) = n X i=1 αi−1 2 n X i,j=1 αiαjyiyjxT ixj, sujeto a: n X i=1 αiyi= 0, αi≥0i= 1, . . . , n. (2.36) que es conocido también como problema dual de Wolfe. Este problema dual de Wolfe puede reescribirse en notación matricial de la siguiente forma, donde se busca el αtal que m´ax LD(α) = 1T nα−1 2αTHα, sujeto a: α≥0, αTy= 0. (2.37) donde y= (y1, . . . , yn)TyH= (Hij)es una matriz cuadrada de tamaño n×ntal que Hij =yiyj(xT ixj). Se puede resolver el problema dual utilizando técnicas de programación cuadrática, las cuales comentaremos en posteriores capítulos. Además, en general, este problema suele ser más sencillo de resolver. Esto se debe a que para el problema dual, el número de variables que hay que encontrar es proporcional al tamaño de la muestra n, mientras que para el primal lo es a la dimensionalidad p. Esta propiedad es importante, pues implica que el coste computacional asociado a la resolución del problema dual es menor y por tanto más factible, incluso en problemas con dimensiones altas. 15 Una vez que se obtiene la solución del problema dual, α∗, para obtener la solución del problema primal a partir de esta es un proceso sencillo. Primero basta con sustituir dicha solución α∗en (2.32) para obtener el vector de pesos óptimo β∗, β∗= n X i=1 α∗ iyixi.(2.38) Usando la condición complementaria de KKT en (2.33), dado que los multiplicadores de Lagrange son no negativos, esto es, αi≥0. Si αi>0, entonces el segundo factor de la parte de la izquierda tendrá que ser nulo, yi(xT iβ∗+β∗ 0) = 1,(2.39) es decir, aquellas observaciones que tienen asociado un multiplicador αi>0, satisfacen la igualdad en (2.17) y por tanto son los vectores soporte. En consecuencia, se puede afirmar que el hiperplano de separación óptimo se construye únicamente a partir de una combinación lineal de los vectores soporte, debido a que las demás observaciones del conjunto de entrenamiento tienen asociado un multiplicador nulo, αj= 0. Sea SV ⊂ {1, . . . , n} el subconjunto de índices que identifican a los vectores soporte, y en consecuencia a los multiplicadores de Lagrange no nulos. Se tiene que el vector de pesos del hiperplano β∗ dado por (2.38), viene dado por la suma únicamente de las observaciones que son vectores soporte, esto es β∗=X i∈SV α∗ iyixi.(2.40) En otras palabras, β∗solo depende de vectores soporte, {xi:i∈ SV}. En muchas aplicaciones, el número de vectores soporte puede ser muy pequeño en comparación con el número total de observaciones del conjunto de datos y, en cualquier caso, los vectores soporte proporcionan toda la información necesaria para determinar el Hard-SVM. Queda por determinar el valor del parámetro β∗ 0para obtener la solución del problema primal. Para ello, lo podemos estimar resolviendo (2.33) para uno de los vectores soporte. Es decir, podemos despejar β∗ 0de (2.39), β∗ 0=ysv −xT svβ∗,(2.41) donde (xsv, ysv)representa un punto soporte sv ∈ SV, correspondiente al vector de variables predictoras junto con el valor de su clase, es decir, cualquier observación que tiene asociado un multiplicador de Lagrange αidistinto de cero. En general, en la práctica suele ser más robusto obtener β∗ 0del promedio de todos los vectores soporte. Así la expresión (2.41) se puede sustituir por esta otra β∗ 0=1 NSV X j∈SV (yj−xT jβ∗)(2.42) siendo SV el conjunto de vectores soporte y NSV el cardinal de dicho conjunto. Si además queremos obtener una expresión de β∗ 0a partir de la solución obtenida en el problema dual, α∗, basta con sustituir (2.32) en (2.42). 16 De todo esto se sigue que el hiperplano de separación óptimo (hard-SVM) se puede escribir como f∗(x) = β∗Tx+β0=X i∈SV α∗ iyixTxi+β∗ 0.(2.43) Para resolver este Hard-SVM se puede observar de la ecuación (2.43) que únicamente los vectores soportes son relevantes en el cálculo, mientras que las demás observaciones que no son vectores soporte no juegan ningún papel en la resolución del problema de optimización. Esta descripción de la solución en términos de los vectores soporte, parece sugerir que el hiperplano de separación óptimo se centra más en los vectores más complicados de clasificar (por ser más “fronterizos”) y es más robusto para los errores de especificación del modelo. La regla de clasificación Hard-SVM viene dada por Q(x) = sign(f∗(x)).(2.44) Si j∈ SV, por (2.43) se cumple la siguiente igualdad f∗(xj) = X i∈SV α∗ iyiyj(xT jxi) + yjβ∗ 0(2.45) Por tanto, la norma al cuadrado del vector de pesos β∗del hiperplano de separación óptimo es kβ∗k2=X i∈SV X j∈SV α∗ iα∗ jyiyj(xT ixj) =X j∈SV α∗ jX i∈SV α∗ iyiyj(xT ixj) =X j∈SV α∗ j(1 −yjβ∗ 0) =X j∈SV α∗ j (2.46) donde usamos (2.45) en la tercera linea y (2.32) en la última igualdad. De aquí podemos ver que el hiperplano de margen máximo tiene como margen máximo entre las dos clases L= 2M= 2/kβ∗k, donde 1 kβ∗k= X j∈SV α∗ j  −1/2 .(2.47) Como comentario final, resaltaremos que la definición del problema dual y la del hiperplano de separación óptimo dependen del producto escalar de los vectores soporte. Esto es una propiedad, que se utilizará más tarde, para calcular hiperplanos de separación óptimos en espacios de dimensiones mayores transformando las variables de entrada. 17 18 Capítulo 3 Caso no separable linealmente (Soft-SVM) En la práctica, el problema planteado en el capítulo anterior no tiene demasiado interés, ya que en general, los conjuntos de datos que aparecen en la práctica habitual del aprendizaje supervisado no tienen todas las observaciones separadas linealmente. Es decir, las clases se solapan en el espacio de las características y no pueden ser separadas linealmente por un hiperplano. En este capítulo, trataremos de extender el concepto tratado en el capítulo anterior de hiperplano de separación de margen óptimo, es decir, el hard-SVM, para conseguir un hiperplano que “separe” lo mejor posible las clases, usando lo que se conoce como margen suave. Para este tipo de problemas, Vapnik y Cortes [5] expusieron que es imprescindible permitir que algunas observaciones no cumplan las restricciones del margen formuladas en el problema primal (2.18) del caso de datos separables, es decir, suavizar el grado de separabilidad del conjunto de entrenamiento permitiendo que haya errores en la clasificación de algunas observaciones del conjunto de entrenamiento. Esta generalización se conoce como soft-SVM. Dadas estas circunstancias, existen dos posibilidades para una observación de este tipo. Puede caer al otro lado del hiperplano, es decir en la clase incorrecta, o caer dentro del margen asociado a su clase, de acuerdo a la frontera definida desde el hiperplano de separación. Ambas observaciones se dice que son no separables, siendo la primera mal clasificada y la segunda clasificada de forma correcta. Esto lo podemos observar en la Figura 3.1, donde xjpertenece al primer caso y xkal segundo, respectivamente. Desde el punto de vista de la formulación, una observación no separable es aquella que no cumple las restricciones del problema (2.13). Sea un conjunto de observaciones de entrenamiento Cno separables. La idea para abordar este problema en el que las clases se solapan es maximizar M, pero permitir que algunos puntos puedan quedar en el lado incorrecto del margen. Para ello, definimos las variables de holgura,{ξi:i= 1, . . . , n}, que serán posteriormente utilizadas para cuantificar el número de observaciones no separables que se van a permitir. Un ejemplo de esto, podemos observarlo en la Figura 3.1 19 Figura 3.1: Ejemplos que están en el lado contrario del margen de seguridad junto a sus correspondientes variables de holgura ξi. Hay dos formas para introducir estas variables de holgura en las restricciones del problema (2.13), yixT iβ+β0≥M−ξi,(3.1) o yixT iβ+β0≥M(1 −ξi),(3.2) con ξi≥0para todo i∈ {1, ..., n}y n X i=1 ξi≤K, siendo K una constante a elegir. En función de qué restricción de las dos tomemos llegaremos a distintas soluciones. La primera desigualdad (3.1), parece más natural, pues mide la superposición de la distancia real con respecto al margen, mientras que la segunda (3.2), mide la superposición de la distancia relativa, que cambia con el ancho del margen, M. Sin embargo, la primera da como resultado un problema de optimización no convexo, mientras que la segunda da uno convexo, así pues a partir de ahora utilizaremos la desigualdad (3.2), que conducirá a lo que se conoce como soft-SVM. Se puede entender el valor de la variable de holgura, ξi, en la desigualdad (3.2), como la cantidad proporcional por la cual la predicción de la observación xi,f(xi) = xT iβ+β0, está en el lado equivocado de su margen, es decir, la desviación de la separabilidad con respecto al margen de la clase correspondiente a dicha observación. Por lo tanto, al acotar la suma de estas variables de holgura, Pn i=1 ξi, limitamos la cantidad proporcional total por la cual las predicciones caen en el lado equivocado de su margen. En función del valor de la variable de holgura, se pueden clasificar las observaciones no separables, si la variable de holgura está entre 0 y 1 estará bien clasificado, mientras que una mala clasificación ocurre cuando ξi>1, luego limitando el sumatorio anterior a K, limitamos el número total de observaciones de entrenamiento mal separadas a K, es decir, cuanto mayor sea el valor de esta constante, mayor será el número de observaciones no separables. Para eliminar este problema de llegar a varias soluciones, se fija de forma arbitraria, como hemos hecho 20 en el capítulo anterior en la igualdad (2.16), que Mkβk= 1. En consecuencia, podemos reescribir la condición (3.2) como yixT iβ+β0≥1−ξi,(3.3) con ξi≥0para todo i∈ {1, ..., n}y n X i=1 ξi≤K. Una vez que hemos suavizado las restricciones, según (3.3), podemos escribir el problema equivalente a (2.18), como m´ın β,β0 1 2kβk2 sujeto a: yixT iβ+β0≥1−ξi, i = 1, . . . , n, ξi≥0, i = 1, . . . , n, n X i=1 ξi≤K, para Kconstante. (3.4) Este problema de optimización es cuadrático con restricciones de desigualdad lineales, y por tanto es un problema de optimización convexo. Sin embargo, ya no basta con plantear como único objetivo maximizar el margen, es decir, minimizar la norma de los coeficientes β, pues lo lograríamos fácilmente clasificando erróneamente muchas observaciones. Para no tener este problema, tenemos que incluir de alguna manera en la función objetivo los errores de clasificación que comete el hiperplano de separación. Para ello, se define el siguiente problema de optimización m´ın β,β0 1 2kβk2+C n X i=1 ξi sujeto a: yixT iβ+β0≥1−ξi, i = 1, . . . , n, ξi≥0, i = 1, . . . , n. (3.5) donde Cse denomina parámetro de regularización o parámetro de coste y reemplaza a la restricción de la constante Kdel problema (3.4). Este valor que se elige, permite controlar el grado en que influye el término del coste de observaciones no separables en la minimización de la norma de β, es decir, permite regular el compromiso entre el grado de sobreajuste del clasificador final y la proporción del número de observaciones mal clasificadas, la complejidad y el error de entrenamiento. Elecciones de valores pequeños de Cpermitirán valores de ξimás grandes. Es decir estaríamos admitiendo una anchura de margen óptimo más grande, pero a costa de admitir más observaciones dentro del margen e, incluso, clasificándolas mal. Además, esto produce modelos más complejos, pues va a depender de un mayor número de vectores soporte. El caso extremo, es decir, cuando C→0, implicaría que todas las observaciones podrían estar mal situadas dentro del margen y el número de observaciones mal clasificadas sería máximo, pues las holguras ξse podrían hacer arbitrariamente grandes. Sin embargo, una elección de un valor muy grande de Cfuerza valores de ξimuy pequeños y, en consecuencia, la anchura del margen óptimo será pequeño. El modelo será más simple, pero podría estar sobreajustado a los datos de entrenamiento. El caso de 21 28 Capítulo 4 Uso de Kernels Tanto el hiperplano de separación máximo (Hard-SVM), como el clasificador de vectores soporte (Soft-SVM), explicado en los capítulos anteriores son un enfoque natural para la clasificación en el entorno de dos clases, clasificación binaria, si la frontera entre las dos clases es lineal, o son cuasi-separables linealmente. Para el cálculo de estos hiperplanos, es decir, para la búsqueda de los parámetros, se ha visto que desde el enfoque del problema de optimización dual se puede resolver de forma más sencilla, siendo independiente de la dimensión del problema. Sin embargo, en la práctica muchos de los conjuntos de datos que se quieren clasificar tienen observaciones que no son linealmente separables. Estos métodos anteriores no sirven para clasificar dichos conjuntos de datos. Como con otros métodos lineales de aprendizaje automático, se puede hacer que el procedimiento sea más flexible ampliando el espacio de características, utilizando transformaciones como polinomios o splines. Generalmente las fronteras lineales en el espacio ampliado logran una mejor separación de la clase de entrenamiento y se traducen en límites no lineales en el espacio original. En este capítulo, trataremos de abordar precisamente eso, como adaptar dichos resultados a este último caso. Para ello, veremos cómo utilizar funciones base no lineales de forma que se puedan definir espacios transformados de manera eficiente con una alta dimensionalidad además de cómo encontrar en ellos el hiperplano de separación óptimo. El éxito de este enfoque puede atribuirse tanto a su flexibilidad para acomodar el conocimiento previo específico del dominio como a tener un conjunto bien desarrollado de algoritmos de implementación eficientes. La clave para construir este nuevo clasificador, un SVM no lineal, se encuentra en ver que los vectores de variables predictoras se definen en el problema de optimización dual a través de los productos internos xT ixj=hxi,xjicon i, j = 1, . . . , n. Para ello, se recurrirá a una técnica que consiste en la transformación mediante una función no lineal del espacio original a un espacio dotado de un producto escalar, que denominaremos función kernel. Se conoce como espacio de entradas al espacio original de las observaciones, X, y espacio de características el espacio transformado, F, que en general, tiene dimensiones grandes y se define a partir de un conjunto de funciones base no lineales. Sea h:X→ F una función de transformación que hace corresponder a cada vector de entrada de variables predictoras xcon un punto en el espacio de características F. Sean además, hm(x), m = 1, . . . , M las funciones base no lineales que definen este espacio de características F. El procedimiento a seguir es el mismo que hemos explica- 29 do en los capítulos anteriores. Se ajustará el clasificador de vectores soporte usando las características de entrada h(xi) = (h1(xi), h2(xi), . . . , hM(xi)),con i= 1, . . . , n, lo que produce que la función no lineal sea f(x) = h(x)Tβ∗+β∗ 0y el clasificador sea la función G(x) = signo[f(x)]. La idea es construir un hiperplano de separación lineal en este nuevo espacio, donde la frontera de decisión lineal obtenida en este espacio de características, se transformará en una frontera de decisión no lineal en el espacio original. En la Figura 4.1 podemos ver un ejemplo gráfico de una función de transformación h. Figura 4.1: Ejemplo gráfico de una función de transformación h En este contexto, cómo hemos dicho, la función de decisión en el espacio de características viene dada por f(x) = (β1h1(x) + . . . +βMhM(x)) = h(x)Tβ, (4.1) donde podemos observar que no aparece el término β0, ya que se puede prescindir de él pues éste puede ser incluido al representarlo en la base de funciones de transformación de la función constante h1(x)=1y aumentando en uno la dimensión del vector β, esto es β∈Rp+1. Podemos reescribir la función de decisión en su forma dual transformando de manera conveniente la expresión (4.1) como f(x) = n X i=1 αiyih(x)Th(xi) = n X i=1 αiyihh(x), h(xi)i.(4.2) Veremos a continuación, que el producto escalar h(x)Th(xi), que se representa también por hh(x), h(xi)ise calculará a partir de lo que se denomina función kernel. Para ello, comencemos viendo que es una función kernel. Definición 4.1. Una función kernel es una función K:X×X→Rque a cada par de elementos del espacio original de entrada X, le asigna un valor real que se corresponde con el producto escalar de las imágenes de dichos elementos en el espacio de características F, es decir, K(x,x0) = hh(x), h(x0)i= (h1(x)h1(x0) + . . . +hM(x)hM(x0)) (4.3) donde h:X→ F envía de Xa un (producto interno) espacio de características F. 30 En el ámbito de los support vector machines, un kernel se refiere a una función matemática que se utiliza para medir la similitud entre dos observaciones en un espacio de características. La teoría del kernel es una herramienta importante en el aprendizaje automático que se utiliza para clasificación, regresión y otras tareas de aprendizaje supervisado y no supervisado. Esta teoría, como ya hemos comentado, se basa en la idea de que la elección de una función kernel adecuada que permite transformar los datos de entrada a un espacio de características de alta dimensión, donde pueden ser más fácilmente separables. Por otro lado, existe un desarrollo más formal que en este trabajo de fin de máster no consideramos, conocido como teoría del operador integral, que es una rama de las matemáticas que estudia las propiedades de los operadores integrales. Estos operadores son funciones que actúan sobre un espacio vectorial para producir otro espacio vectorial y se pueden expresar como integrales en un cierto espacio de funciones. Los operadores integrales son importantes en muchas áreas de las matemáticas aplicadas, como la teoría de la aproximación, la teoría de las ecuaciones diferenciales, la estadística y el aprendizaje automático. La teoría del kernel y esta teoría del operador integral están estrechamente relacionadas. La conexión entre ambas es que los kernels son una clase especial de operadores integrales. En particular, el kernel asociado a una función de transformación de características se puede ver como el núcleo de un operador integral que transforma las funciones en el espacio de características. De esta manera, la teoría del kernel utiliza la teoría del operador integral para establecer propiedades teóricas de los métodos de aprendizaje automático basados en kernels, como veremos más adelante. Una consecuencia importante de la representación dual es que la dimensión del espacio de características no afecta a los cálculos, como este no se representa explícitamente por los vectores de características, la cantidad de operaciones requeridas para calcular el producto interno mediante la evaluación de la función kernel no es necesariamente proporcional a la cantidad de dichas características. El uso de los kernels hace posible enviar los datos implícitamente en un espacio de características y entrenar una función lineal en dicho espacio, potencialmente eludiendo los problemas computacionales relacionados en la evaluación del espacio de características. La única información utilizada sobre las observaciones de entrenamiento en el espacio de características es su matriz de Gram omatriz kernel, que se define como la matriz K=Kij de dimensiones n×n, donde Kij =K(xi,xj). Una vez que se define a la matriz K, la función se puede calcular evaluando al menos nveces la matriz Kde la siguiente manera: f(x) = n X i=1 αiyiK(xi,x).(4.4) Utilizando esta función kernel, no hace falta calcular de manera explicita el transformación de la función h:X→ F. Algunas propiedades que estas funciones tienen que cumplir son que han de ser simétricas, es decir, K(x,x0) = hh(x), h(x0)i=hh(x0), h(x)i=K(x0,x), y tienen que satisfacer la siguiente desigualdad que se obtiene a partir de la desigualdad de Cauchy-Schwarz, K(x,x0) = hh(x), h(x0)i2≤ kh(x)k2kh(x0)k2=hh(x), h(x)ihh(x0), h(x0)i=K(x,x)K(x0,x0) 31 Sin embargo, estas condiciones no son suficientes para garantizar la existencia del espacio de características. A continuación, introducimos una proposición que nos permite obtener aquellas condiciones que tiene que cumplir una función K para que sea un kernel que induzca un espacio de características. Proposición 4.2. Sea Xun espacio de entradas finito tal que K(x,x0)es una función simétrica en X. Entonces K(x,x0)es una función kernel, si y solo si la matriz de Gram Ki,j = (K(xi,xj))n i,j=1 es semidefinida positiva, es decir, tiene autovalores no negativos. Demostración. Es trivial ver que si Kes una función kernel, por definición la matriz de Gram es semidefinida positiva, pues que sea semidefinida positiva quiere decir que se cumple Pn i=1 Pn j=1 cicjK(xi,xj)≥0para cualesquiera conjuntos x1,...,xn∈Xy c1, . . . , cn∈R, con n > 0. Para demostrar la otra implicación, definimos el espacio de funciones sobre Xcomo RX={f:X→R}. Para cada x∈X, sea h(x)la función x7→ K(·,x). Definimos el espacio de vectores cogiendo todas las posibles combinaciones de elementos del tipo K(·,x). Definimos un producto interno en este espacio de vectores como *X i αiK(·,xi),X j βjK(·,x0 j)+=X i,j αiβjK(xi,x0 j), Este producto interno es válido pues es simétrico, ya que Kes simétrica, es linear y además es definido positivo, ya que K(x,x)≥0cumpliéndose la igualdad cuando h(x) es la función cero. Claramente, hh(x), h (x0)i=hK(·,x), K (·,x0)i=K(x,x0), lo que concluye la prueba. En los espacios de Hilbert también se pueden definir funciones kernel. Un espacio de Hilbert es una generalización del concepto de espacio euclídeo y, formalmente, se define como un espacio de producto interior que es completo con respecto a la norma vectorial definida por el producto interno, donde completo en este contexto significa que cualquier sucesión de Cauchy de elementos del espacio converge a un elemento en el espacio, en el sentido que la norma de las diferencias tiende a cero. La “teoría de los espacios de Hilbert”, muestra que las funciones kernel se corresponden con un producto escalar y estas inducen en el espacio transformado un espacio lineal de mayor dimensión que el espacio original, que puede ser infinita. Surge la pregunta de cómo transformar las observaciones de entrada, de dimensión finita, en otro espacio de dimensión posiblemente infinita. El siguiente teorema responde a esta pregunta. Teorema 4.3 (de Aronszajn).Para cualquier función K:X×X→Rque sea simétrica y semidefinida positiva, existe un espacio de Hilbert y una función h:X→ F tal que K(x,x0) = hh(x), h(x0)i,para todo x,x0∈X. (4.5) Como consecuencia de este teorema, en 1992 Boser, Guyon y Vapnik [6] demostraron que para construir una función kernel, basta con definir una función que cumpla las dos condiciones del teorema, ha de ser simétrica y semidefinida positiva, no hace falta hacerlo 32 a partir de un conjunto de funciones base h(x)=(h1(x), . . . , hM(x)). Así, la función kernel representa el producto escalar hh(x), h(x0)ique induce a un espacio de dimensión más alta. Esto permite evaluar una función sin conocer dicho conjunto de funciones base, basta con evaluar dicha función kernel sin tener que calcular explícitamente el producto escalar correspondiente. Más adelante lo veremos con unos ejemplos. Todo esto nos permite inducir cualquier algoritmo lineal en un espacio de Hilbert, donde en el espacio original su versión es no lineal, siendo la transformación utilizada para ello hno lineal. Esto es lo que se conoce como el truco de los kernels, en inglés, “Kernel trick”. Existe una serie de funciones kernel que son las más utilizadas y entre las que se pueden destacar las siguientes. Kernel lineal: KL(x,x0) = hx,x0i= p X j=1 xijxi0j,(4.6) que se corresponde con el núcleo utilizado para el Hard-SVM, y se denomina así pues este clasificador es lineal en el espacio de las características. Este kernel esencialmente cuantifica la similitud de un par de observaciones utilizando la correlación de Pearson. Kernel polinómico de grado-d: Kd(x,x0) = (τ+γhx,x0i)d= (τ+γ p X j=1 xijxi0j)d(γ > 0).(4.7) Usando este núcleo con d > 1, en lugar de usar el kernel lineal (4.6) en el algoritmo del Hard-SVM, se llega a una frontera de decisión mucho más flexible. Esencialmente equivale a ajustar un clasificador de vectores de soporte en un espacio de mayor dimensión que involucra polinomios de grado d, en lugar de en el espacio de características original. Kernel radial: KR(x,x0) = exp(−γkx−x0k2) = exp(−γh(x−x0),(x−x0)i) = exp(−γ p X j=1 (xij −xi0j)2), (4.8) donde γes una constante positiva. Más adelante veremos una proposición que nos demuestra porqué esta función es también un kernel. Para ver como funciona el kernel radial (4.8), supongamos que tenemos una observación de test,˜ x= (˜x1,...,˜xp)que está muy alejada de la observación de entrenamiento xi en términos de la distancia Euclidea, por tanto Pp j=1(˜xj−xij)2es grande, y por tanto exp(−γPp j=1(˜xj−xij)2)será muy pequeño. Esto significa que la observación xino juega demasiado papel en la función de decisión f(˜ x). Recordemos que la etiqueta de clase predicha para el ejemplo de prueba ˜ xse basa en el signo de f(˜ x). En otras palabras, los ejemplos de entrenamiento que están lejos de ˜ xno tienen ningún papel en la etiqueta de clase predicha para ˜ x. Esto significa que el núcleo radial tiene un comportamiento muy local, en el sentido de que solo los ejemplos de entrenamiento cercanos tienen un efecto en la etiqueta de clase de una observación del conjunto de test, lo que favorece, en algunas 33 ocasiones, el “sobreajuste”. Veamos cual es la distancia para este kernel radial, es decir, esta es un producto escalar en un espacio transformado de dimensión finita. Si tomamos γ= 1/2σ2, se tiene que K(x,x0) = h(x)Th(x0) = exp(−kx−x0k2/2σ2), y la distancia por tanto entre h(x)yh(x0)es d(h(x), h(x0)) = qkh(x)−h(x0)k2=q2(1 −exp (−kx−x0k22σ2)) = q2(1 −K(x,x0)). Se puede ver que cuando estamos en el caso unidimensional, con σ2= 1 que la distancia varía de manera exponencial. Para el caso de 2D, si tomamos valores pequeños del parámetro σ2, la distancia estará muy localizada y por tanto todos los puntos de fuera de un radio pequeño están igualmente lejos. Sin embargo si tomamos valores un poco más grandes de σ2tendremos una distancia más global, equivalente a un kernel lineal. Kernel sigmoidal: KS(x,x0) = tanh(γhx,x0i+τ) = tanh γ p X j=1 xijxi0j+τ (4.9) A estos parámetros γ, τ ydse les denomina parámetros del kernel. A continuación, vamos a ver un ejemplo para una función kernel polinomial. Ejemplo 4.4. Consideremos el espacio de entradas Xy además consideremos también dos variables de entrada x1yx2, y tomemos el kernel polinomial de grado 2. Entonces se define el kernel de la siguiente manera K(x,x0) = (1 + hx,x0i)2= (1 + x1x0 1+x2x0 2)2= = 1 + 2x1x0 1+ 2x2x0 2+ (x1x0 1)2+ (x2x0 2)2+ 2x1x0 1x2x0 2 (4.10) En este caso M= 6, y si tomamos como funciones base h1(x)=1,h2(x) = √2x1, h3(x) = √2x2,h4(x) = x2 1,h5(x) = x2 2,h6(x) = √2x1x2, es decir, se tiene que h(x) = {1,√2x1,√2x2, x2 1, x2 2,√2x1x2}. Sean ahora los vectores u= (1,2) yv= (3,4). Vamos a calcular h(u)·h(v)de dos maneras, sin utilizar la función kernel y utilizándola. Se cumple que h(u) = {1,√2,2√2,1,4,2√2}yh(v) = {1,3√2,4√2,9,16,12√2}. En consecuencia h(u)·h(v) = 1+3·2+8·2+9+4·16+24·2 = 1+6+16+9+64+48 = 144. Calculamos ahora usando la función kernel h(u)·h(v) = (1 + hu,vi)2= (1 + 1 ·3 + 2·4)2= (1 + 3 + 8)2= 122= 144. Este ejemplo lo que nos permite ver, como habíamos comentado ya anteriormente, es que no es necesario conocer todas las funciones base, ni calcular explícitamente todos los términos, simplemente con conocer la función del kernel y evaluar es suficiente. Una de las ventajas de usar el kernel en lugar de simplemente ampliar el espacio original usando funciones base de las características originales es computacional, pues cuando usamos kernels solo es necesario calcular K(xi,xi0)para todos los n 2pares de índices i, i0 distintos. Esto se puede hacer sin trabajar explícitamente en el espacio de características ampliado y es importante porque en muchas aplicaciones de SVM, el espacio de características ampliado es tan grande que los cálculos son intratables. Para algunos núcleos, 34 como el kernel radial de la ecuación (4.8), el espacio de características es implícito y de dimensión infinita, por lo que nunca podríamos hacer los cálculos allí de todos modos. A parte de estas funciones kernel que se han expuesto anteriormente, se pueden crear otras. Para ello, veamos una caracterización de estas funciones proporcionada por un teorema de análisis funcional cuya demostración queda fuera del alcance de este trabajo. El uso de una función kernel, como se ha comentado anteriormente, es un atajo computacional atractivo. Si deseamos utilizar este enfoque, parece que es necesario crear primero un espacio de características complicado, luego determinar cuál sería el producto interno en ese espacio y, finalmente, encontrar un método directo para calcular ese valor en términos de las entradas originales. En la práctica, el enfoque adoptado es definir una función del kernel directamente, por lo tanto, definir implícitamente el espacio de características. De esta forma, se evita el espacio de características no solo en el cálculo de productos internos, sino también en el diseño de la propia máquina de aprendizaje. Para ello, primero debemos determinar qué propiedades de una función K(x,x0)son necesarias para asegurarnos de que es un núcleo para algún espacio de características. En el Teorema 4.3 hemos visto dos propiedades que se tienen que cumplir, que sea simétrica y semidefinida positiva. Además, existe una contribución del análisis funcional, en la que no entraremos en detalle, que proporciona una caracterización a estas funciones kernel, y se conoce como el Teorema de Mercer. Este asegura que toda función K(x,x0)que verifica ZX×XK(x,x0)g(x)g(x0)dxdx0>0 para toda función g(·)de cuadrado integrable, es decir, cuya integral del cuadrado de su módulo definida en el intervalo de definición converge, es una función kernel. Este teorema nos permite caracterizar funciones kernel y por tanto poder crearlas. También se pueden crear nuevos núcleos mediante transformaciones de alguno que ya se conoce. La siguiente proposición nos permite crear kernels más complicados a partir de otros más sencillos. Proposición 4.5. Sean K1yK2funciones kernel sobre X×X, con X⊆Rn,a∈R+, f(·)una función de valores reales sobre X,h:X→Rm, con K3una función kernel sobre Rm×RmyBuna matriz n×nsemidefinida positiva y simétrica. Las siguientes funciones son kernels: 1. K(x,x0) = K1(x,x0) + K2(x,x0). 2. K(x,x0) = aK2(x,x0). 3. K(x,x0) = K1(x,x0)·K2(x,x0). 4. K(x,x0) = f(x)·f(x0). 5. K(x,x0) = K3(h(x), h(x0)). 6. K(x,x0) = xTBx0 Demostración. Fijemos un conjunto finito de puntos x1, . . . , xl, y sean K1yK2, las correspondientes matrices obtenidas al restringir K1yK2a estos puntos. Considereremos ahora cualquier vector α∈Rl. Recordemos que una matriz Kes semidefinida positiva si y solo si α0Kα≥0, para todo α. 35 1. Tenemos α0(K1+K2)α=α0K1α+α0K2α≥0 y por tanto K1+K2es semidefinida positiva y K1+K2es una función kernel. 2. De una manera similar α0aK1α≥0, probando que aK1es un kernel. 3. Sea K=K1NK2el producto tensorial de las matrices K1yK2. El producto tensorial de dos matrices semidefinidas positivas es también semidefinido positivo ya que los autovalores del producto son todos pares de productos de los autovalores de los dos componentes. La matriz correspondiente a la función K1K2se conoce como el producto Schur Hde K1yK2cuyas entradas son los productos de las entradas correspondientes de las dos matrices. La matriz Hes una submatriz principal de K definida por un conjunto de columnas y el mismo conjunto de filas. Por lo tanto, para cualquier α∈Rl, hay un α1∈Rl2correspondiente, tal que α0Hα=α0 1Kα1≥0, y por tanto Hes semidefinida positiva como queríamos ver. 4. Podemos reorganizar la forma bilineal como sigue ` X i=1 ` X j=1 αiαjK(xi,xj) = ` X i=1 ` X j=1 αiαjf(xi)f(xj) = ` X i=1 αif(xi) ` X j=1 αjf(xj) = ` X i=1 αif(xi)!2 ≥0 , y en consecuencia hemos probado que es una función kernel. 5. Como K3es una función kernel, la matriz obtenida restringiéndola por los puntos h(x1), . . . , h(xl)es semidefinida positiva como queríamos. 6. Consideremos la diagonalización de la matriz B=VTΛV, siendo Vuna matriz ortogonal y Λla matriz diagonal que contiene los autovalores no negativos. Sea √Λ la matriz diagonal con las raíces cuadradas de los autovalores, y sea A=√ΛV. Tenemos por tanto que se cumple K(x,z)=x0Bz=xTVTΛVz = xTVT√Λ√ΛVz=xTATAz=hAx·Azi utilizando en el producto interno la transformación de características de matriz A. Otro corolario que nos permite obtener funciones kernel a partir de una ya conocida además de demostrarnos porqué la función radial lo es también, es el siguiente Corolario 4.6. Sea K1(x,z)una función kernel sobre X×X,x,z∈X, y P(x)un polinomio con coeficientes positivos. Entonces las siguientes funciones también son kernel: 36 1. K(x,z) = P(K1(x,z)), 2. K(x,z) = exp(K1(x,z)), 3. K(x,z) = exp(−kx−zk2/σ2). Demostración. Veamos cada una de los puntos 1. Para un polinomio el resultado es inmediato al combinar las partes de la Proposición 4.7. Tenga en cuenta que la constante está cubierta por el punto 4 de dicha proposición. 2. La función exponencial se puede aproximar arbitrariamente mediante polinomios con coeficientes positivos y por lo tanto es un límite de núcleos. Dado que los núcleos están claramente cerrados tomando límites puntuales, se demuestra el resultado. 3. Podemos descomponer la función como sigue: exp−kx−zk2/σ2= exp −kxk2/σ2exp −kzk2/σ2exp 2(x·zi/σ2. Los primeros dos factores forman un kernel por el apartado 4 de la proposición anterior, mientras que el tercer factor lo es también por el segundo punto de este corolario. Volviendo a la formulación del problema en el caso no separable linealmente, el problema primal asociado a este caso, es muy similar al que hemos descrito previamente para el caso lineal y casi lineal, con la diferencia de que el hiperplano de separación que buscamos se determina en el espacio de características, es decir m´ın 1 2kβk2+C n X i=1 ξi sujeto a: yih(xi)Tβ≥1−ξii= 1, . . . , n ξi≥0i= 1, . . . , n. (4.11) La complejidad de este problema primal (4.11) depende de la dimensión del espacio de características, que en general es alta, llegando incluso a infinita como se ha comentado anteriormente. Por ello de nuevo, se considera el problema dual asociado, cuya complejidad depende del número de observaciones. Dado el conjunto de funciones base h={h1(x), . . . , hM(x)}, el problema a resolver es encontrar el valor de los parámetros α∗ i, i = 1, . . . , n, que optimiza el siguiente problema dual m´ax n X i=1 αi−1 2 n X i,j=1 αiαjyiyjh(xi)Th(xj) sujeto a: n X i=1 αiyi= 0 0≤αi≤C i = 1, . . . , n. (4.12) 37 y combinando las ecuaciones (5.2) y (5.3), se obtiene f(¯ β)−f(β?)≤1 T T X t=1hβ(t)−β?,∇f(β(t))i. Para acotar el lado derecho nos basamos en el siguiente lema: Lema 5.1. Sean ν1, . . . , νTun conjunto de vectores arbitrarios. Cualquier algoritmo con inicialización β(1) = 0 y una regla de actualización de la forma β(t+1) =β(t)−ηνt(5.4) cumple que T X t=1hβ(t)−β?, νti ≤ kβ?k2 2η+η 2 T X t=1 kνtk2.(5.5) En particular, para cualquier B, ρ > 0, si para todo tse tiene que kνtk ≤ ρy si establecemos η=qB2 ρ2T, entonces para todo β?con kβ?k ≤ B, se cumple que 1 T T X t=1hβ(t)−β?, νti ≤ Bρ √T. Demostración. Usando manipulaciones algebraicas, es decir, completando cuadrados, obtenemos hβ(t)−β?, νti=1 ηhβ(t)−β?, ηνti =1 2η−kβ(t)−β?−ηνtk2+kβ(t)−β?k2+η2kνtk2 =1 2η−kβ(t+1) −β?k2+kβ(t)−β?k2+η 2kνtk2, (5.6) donde la última igualdad se deriva de la definición de la regla de actualización (5.4). Sumando la igualdad sobre t, tenemos T X t=1hβ(t)−β?, νti=1 2η T X t=1 −kβ(t+1) −β∗k2+kβ(t)−β∗k2+η 2 T X t=1 kνtk2.(5.7) La primera suma en el lado derecho es una serie telescópica, es decir, es una serie cuyas sumas parciales poseen un número fijo de términos tras su cancelación, en este caso el resultado es kβ(1) −β?k2−kβ(T+1) −β?k2. Sustituyendo esta igualdad en la ecuación (5.7), se tiene T X t=1hβ(0) −β?, νti=1 2ηkβ(1) −β∗k2−kβ(T+1) −β?k2+η 2 T X t=1 kνtk2 ≤1 2ηkβ(1) −β?k2+η 2 T X t=1 kνtk2 =1 2ηkβ∗k2+η 2 T X t=1 kνtk2 44 donde la última igualdad se debe a la definición β(1) = 0. Esto prueba (5.5), y la segunda parte del lema se tiene por el límite superior de kβ?kpor B,kνtkpor ρ, dividiendo entre Ty reemplazando el valor de η. Si el Lema 5.1 se aplica al algoritmo de descenso de gradiente con νt=∇f(β(t)), por satisfacerse las condiciones de dicho lema, se llega al siguiente corolario: Corolario 5.2. Sea funa función ρ-Lipschitz convexa, y sea β?∈argmin{β:kβk≤B}f(β). Si ejecutamos el algoritmo de descenso de gradiente en fpara Tpasos con η=qB2 ρ2T, entonces el vector de salida ¯ βsatisface la siguiente desigualdad f(¯ β)−f(β?)≤Bρ √T. Además, para todo ε > 0, para conseguir f(¯ β)−f(β?)≤ε, es suficiente ejecutar el algoritmo de descenso de gradiente un número de iteraciones T, tal que T≥B2ρ2 ε2. El algoritmo del descenso del gradiente requiere que la función fsea diferenciable. Ahora vamos a generalizarlo más allá de las funciones diferenciables. Mostraremos que este algoritmo se puede aplicar a funciones no diferenciables usando en lugar del gradiente, el llamado subgradiente de f(β)en β(t). Para motivar la definición de los subgradientes, tenemos que para una función convexa f, el gradiente en βdefine la pendiente de una tangente que se encuentra debajo de f.. Es decir, para todo u, f(u)≥f(β) + hu−β, ∇f(β)i.(5.8) Esto lo podemos ver en la parte izquierda de la Figura 5.1. La existencia de una tangente que se encuentra debajo de fes una propiedad importante de las funciones convexas, que de hecho es una caracterización alternativa de la convexidad. Lema 5.3. Sea Sun conjunto abierto y convexo. Una función f:S → Res convexa si y solo si para todo β∈ S existe un vtal que para todo u∈ S f(u)≥f(β) + hu−β, vi.(5.9) Esta desigualdad nos permite definir lo que es un subgradiente. Definición 5.4. Un vector vque satisface la ecuación (5.9) se llama subgradiente de fen β. El conjunto de subgradientes de fen βse denomina conjunto diferencial y se denota como ∂f(β). 45 En el lado derecho de la Figura 5.1 se muestra una ilustración de los subgradientes. Para funciones escalares, un subgradiente de una función convexa fen βes una pendiente de una línea que toca fen βy no está por encima de fen ningún otro lugar. Figura 5.1: En la imagen de la izquierda podemos ver que el lado derecho de la ecuación (5.8) es la tangente de fen β. Para una función convexa, los límites inferiores de la tangente f. En la imagen de la derecha podemos ver varios subgradientes de una función convexa no diferenciable. Para construir el subgradiente de una función convexa dada, se tiene que si una función es derivable en un punto β, entonces el conjunto diferencial es trivial, pues ∂f(β)contiene un solo elemento: el gradiente de fen β,∇f(β). Veamos a continuación un ejemplo de cálculo del conjunto diferencial de una función no diferenciable. Ejemplo 5.5. Si consideramos la función f(x) = kxk, usando todo lo anterior, podemos construir fácilmente el conjunto diferencial para las partes diferenciables de f, y el único punto que requiere especial atención es x0= 0. En ese punto, es fácil ver que el subdiferencial es cualquier valor en el intervalo -1 y 1. Por lo tanto podemos definirlo de manera completa como ∂f(x) =      {1}if x>0 {−1}if x<0 [−1,1] if x= 0 Para muchos usos prácticos, no necesitamos calcular todo el conjunto de subgradientes en un punto dado, ya que bastaría con un miembro de este conjunto. La siguiente afirmación muestra cómo construir un subgradiente para funciones máximas en un punto. Proposición 5.6. Sea g(β) = m´axi=1,...,r gi(β)para rfunciones diferenciables convexas g1, . . . , gr. Para j∈argmaxi=1,...,r gi(β)se tiene ∇gj(β)∈∂g(β). Demostración. Como gjes convexa, tenemos por el Lema 5.3 que para todo u gj(u)≥gj(β) + hu−β, ∇gj(β)i. Como g(β) = gj(β)yg(u)≥gj(u)obtenemos que g(u)≥g(β) + hu−β, ∇gj(β)i, lo que concluye la prueba. 46 Para verlo con un ejemplo, vamos a calcular el subgradiente de la función de pérdida de hinge. Ejemplo 5.7. Recordemos para ello que la función de pérdida de hinge, vista en capítulos anteriores, se definía como f(β) = m´ax{0,1−yhβ, xi} para un vector xy un escalar y. Para calcular un subgradiente de la función de pérdida de hinge en algún β, nos basamos en la proposición anterior y obtenemos que el vector definido a continuación es un subgradiente de esta función de pérdida en β: ∂f(β) = (0si 1−yhβ, xi ≤ 0 −yxsi 1−yhβ, xi>0 El siguiente lema nos da una definición equivalente usando las normas de los subgradientes: Lema 5.8. Sea Aun conjunto abierto y convexo y sea f:A→Runa función convexa. Entonces, fes ρ-Lipschitz sobre Asi y solo si para todo β∈Ayv∈∂f(β)se cumple que kvk ≤ ρ. Demostración. Veamos la implicación de derecha a izquierda. Para ello supongamos que para todo v∈∂f(β)se cumple que kvk ≤ ρ. Como v∈∂f(β)se tiene que f(β)−f(u)≤ hv, β −ui. Acotando la parte de la derecha utilizando la desigualdad de Cauchy-Schwartz obtenemos f(β)−f(u)≤ hv, β −ui≤kvkkβ−uk ≤ ρkβ−uk. Utilizamos el mismo argumento para demostrar que f(u)−f(β)≤ρkβ−uk.En consecuencia fes ρ-Lipschitz. Veamos ahora la otra implicación. Supongamos que fes una función ρ-Lipschitz. Tomamos algún β∈A, v∈∂f(β). Como Aes un conjunto abierto, tenemos que existe ε > 0tal que u=β+εv/kvkpertenece a A. Por lo tanto, hu−β, vi=εkvkyku−βk=ε. Por la definición de subgradiente, f(u)−f(β)≥(v,u−βi=εkvk. Por otro lado, por ser funa función Lipschitziana, tenemos ρε =ρku−βk ≥ f(u)−f(β). Combinando las dos desigualdades, se tiene que kvk ≤ ρ, lo que concluye la prueba. Como observación de este Lema tenemos que si fes ρ-Lipschitz, entonces se cumple que k∇f(β(t))k ≤ ρ. El algoritmo de descenso del gradiente se puede generalizar a funciones no diferenciables mediante el uso de un subgradiente de f(β)en β(t), en lugar del gradiente. El análisis de la tasa de convergencia permanece sin cambios, simplemente hay que tener en cuenta que la ecuación (5.3) también es válida para los subgradientes. 47 Descenso de gradiente estocástico A continuación, vamos a explicar el método del descenso de gradiente estocástico. En este método no se exige que la dirección de actualización se base exactamente en el gradiente, en cambio, se permite que la dirección sea un vector aleatorio y solo hace falta que su valor esperado en cada iteración sea igual a la dirección del gradiente, o de manera más general, se requiere que el valor esperado del vector aleatorio sea un subgradiente de la función en el vector actual. El procedimiento de Descenso de gradiente estocástico para minimizar una función f(β)puede ser esquematizado como sigue: Para un η > 0yT∈N: Inicializar con β(1) = 0 Para t= 1, ..., T −1: Vtvector aleatorio con E[Vt|β(t)]∈∂f(β(t)) Actualizar β(t+1) =β(t)−ηVt Devolver ¯ β=PT t=1 β(t) T Nótese que los β(t)son vectores aleatorios que se van actualizando en el proceso iterativo. Para las funciones Lipschitzianas convexas ya hemos visto que existía una cota superior para el algoritmo del descenso del gradiente en el Corolario 5.2. Para el caso estocástico, en el que la esperanza condicional de Vtestá en ∂f(β(t)), no podemos aplicar directamente la ecuación (5.3). Sin embargo, podemos obtener una cota superior similar en el vector final esperado del descenso del gradiente estocástico. Esto lo formalizamos en el siguiente teorema. Teorema 5.9. Sean B, ρ > 0,funa función convexa y β?con β?∈argmin{β:kβk≤B}f(β). Ejecutamos el algoritmo de descenso del gradiente estocástico para fen Titeraciones con η=qB2 ρ2T. Suponemos además que para todo t,P[kVtk ≤ ρ] = 1. Entonces el vector de salida ¯ βsatisface la siguiente desigualdad E[f(¯ β)] −f(β?)≤Bρ √T. Además, para todo ε > 0, para conseguir E[f(¯ β)] −f(β?)≤ε, es suficiente ejecutar el algoritmo de descenso de gradiente estocástico para un número de iteraciones que satisfaga T≥B2ρ2 ε2. 48 Demostración. Sea V1, . . . , VTuna secuencia de vectores aleatorios y EV1,...,VTla esperanza en función de la distribución conjunta de la secuencia de vectores aleatorios V1, . . . , VT. Usando la desigualdad (5.2) y tomado esperanzas, se tiene EV1,...,VThf(¯ β)−f(β?)i≤EV1,...,VT"1 T T X t=1 fβ(t)−f(β?)#. Dado que el Lema 5.1 se cumple para cualquier sucesión V1, V2, . . . , VT, también se podrá aplicar al algoritmo de descenso de gradiente estocástico. Tomando esperanzas de la cota en dicho lema tendríamos que EV1,...,VT"1 T T X t=1hβ(t)−β?, Vti#≤Bρ √T. Solo nos falta por probar el hecho de que se satisface EV1,...,VT"1 T T X t=1 fβ(t)−f(β?)#≤EV1,...,VT"1 T T X t=1 Dβ(t)−β?, VtE#,(5.10) y eso concluiría con la prueba. Con este propósito, usando la linealidad de la esperanza, tenemos EV1,...,VT"1 T T X t=1 Dβ(t)−β?, VtE#=1 T T X t=1 EV1,...,VThhβ(t)−β?, Vtii. Nos fijamos primero en que EV1,...,VThhβ(t)−β?, Vtii=EV1,...,Vthhβ(t)−β?, Vtii, por como están definidos los β(t). A continuación, usamos que para dos variables aleatorias generales XeY(no tienen que ver con el vector aleatorio Xy la variable Yque usamos para modelar las variables de entrada a salida de nuestros clasificadores) se tiene que EX[φ(X)] = EYEX[φ(X)|Y]. Fijando X= (V1, . . . , Vt)eY= (V1, . . . , Vt−1)obtenemos: EV1,...,VThhβ(t)−β?, Vtii=EV1,...,Vthhβ(t)−β?, Vtii =EV1,...,Vt−1EV1,...,VthDβ(t)−β?, VtE|V1, . . . , Vt−1i. Condicionalmente a los vectores en la secuencia V1, . . . , Vt−1, el valor de β(t)ya no es aleatorio y, por tanto, EV1,...,Vt−1EV1,...,VthDβ(t)−β?, VtE|V1, . . . , Vt−1i=EV1,...,Vt−1hβ(t)−β?,EVt[Vt|V1, . . . , Vt−1]i. Dado que β(t)solo depende de V1, . . . , Vt−1, y que el algoritmo de descenso del gradiente estocástico cumple EVt[Vt|β(t)]∈∂f(β(t)), se obtiene que EVt[Vt|V1, ..., Vt−1]∈∂f(β(t)). 49 De este modo, EV1,...,Vt−1hβ(t)−β?,EVt[Vt|V1, . . . , Vt−1]i ≥ EV1,...,Vt−1[f(β(t))−f(β?)] Con lo que se ha demostrado que EV1,...,VT[hβ(t)−β?, Vti]≥EV1,...,Vt−1[f(β(t))−f(β?)] =EV1,...,VT[f(β(t))−f(β?)]. Sumando sobre t, dividiendo por Ty usando la linealidad de la esperanza, obtenemos que se cumple la ecuación (5.10), lo que concluye nuestra demostración. Una vez que hemos introducido y analizado el algoritmo de descenso de gradiente estocástico para funciones generales convexas. Ahora veamos su uso en las tareas de aprendizaje automático. Recordemos que en el aprendizaje automático (caso de separación por hiperplanos) nos enfrentamos al problema de minimizar el riesgo esperado R(β) = EZ[`(β, Z)]. Hemos visto en el Capítulo 3 método basados en técnicas de optimización para minimización del riesgo empírico (o versiones penalizadas), donde minimizamos el riesgo empírico RC(β)para el conjunto de observaciones C={z1, . . . , zn}como una “aproximación” a minimizar R(β). El algoritmo del descenso de gradiente estocástico nos permite adoptar un enfoque diferente y buscar minimizar R(β)directamente. Como no conocemos la distribución conjunta de Z= (X, Y ), no podemos simplemente calcular ∇R(β)y minimizarlo con el método del descenso del gradiente. Sin embargo, con el algoritmo del descenso del gradiente estocástico, todo lo que necesitamos, en cada paso, es generar un vector aleatorio que cumpla que E[Vt|β(t)]∈∂R(β(t)). Ahora veremos cómo se puede obtener fácilmente tal vector aleatorio. Para simplificar, consideremos primero el caso de las funciones de pérdida `diferenciables y, por tanto, la función de riesgo R(β)también será diferenciable. Si tomamos el vector aleatorio Z= (X, Y )yVtigual al gradiente de `(β(t), Z), por la linealidad del gradiente, tenemos EhVt|β(t)i=EZh∇`(β(t), Z)i=∇EZh`(β(t), Z)i=∇R(β(t)).(5.11) Por tanto, la realización de Vtse obtiene muestreando una sola observación nueva desde la distribución conjunta de Z= (X, Y ), por ejemplo Z=z, y calculando el gradiente de `(β, z)evaluado en β=β(t). El mismo argumento vale para las funciones de pérdida no diferenciables. Simplemente dejamos que Vtsea un subgradiente de `(β, Z)en β(t). Entonces, para cada vector uy realización Z=zse cumple la siguiente desigualdad `(u, z)−`(β(t), z)≥ hu−β(t), Vti. Tomando esperanzas en ambos lados con respecto a Zy condicionadas al valor de β(t) obtenemos R(u)−R(β(t)) = E[`(u, z)−`(β(t), z)|β(t)] ≥E[hu−β(t), Vti | β(t)] =hu−β(t),E[Vt|β(t)]i. 50 De todo esto podemos deducir que E[Vt|β(t)]es un subgradiente de R(β)en β(t), ya que cumple con la Definición 5.4. Ahora usaremos nuestro análisis del algoritmo del descenso de gradiente estocástico para obtener un análisis de complejidad muestral para aprender problemas acotados Lipschitz convexos. La aplicación del Teorema 5.9 proporciona el siguiente corolario: Corolario 5.10. Consideremos un problema de aprendizaje acotado convexo y de Lipschitz con los parámetros ρyB. Entonces, para cualquier ε > 0, si repetimos el método de descenso de gradiente estocástico para minimizar R(β)un número de iteraciones T≥B2ρ2 ε2 con η=qB2 ρ2T, entonces la salida del algoritmo de descenso de gradiente estocástico satisface R(¯ β)≤m´ın βR(β) + ε. Dado que estamos tratando con problemas de aprendizaje convexos en los que la función de pérdida es convexa, vamos a presentar un problema que es también convexo y se puede resolver usando el descenso del gradiente estocástico, como veremos a continuación. El método trata ahora de realizar la minimización en βmediante m´ın β λ 2kβk2+RC(β)!, que ahora sí implica la perdida empírica RC(β)y se adopta la habitual penalización en la norma al cuadrado de β Para ello veamos primero la definición de una función λ-fuertemente convexa. Definición 5.11. Una función fes λ-fuertemente convexa si para todos los vectores u, βy constantes α∈(0,1) se cumple f(αβ + (1 −α)u)≤αf(β) + (1 −α)f(u)−λ 2α(1 −α)kβ−uk2. Claramente, toda función convexa es 0-fuertemente convexa. A continuación mostramos un lema que será utilizado posteriormente. Lema 5.12. Se cumplen las siguientes implicaciones 1. La función f(β) = λkβk2es 2λ-fuertemente convexa. 2. Si fes λ-fuertemente convexa y ges convexa, entonces f+ges λ-fuertemente convexa. 3. Si fes λ-fuertemente convexa y ues un mínimo de f, entonces para cualquier β, f(β)−f(u)≥λ 2k2−uk2. 51 Demostración. Los dos primeros puntos se obtienen directamente de la definición. Para probar el tercero, dividimos la definición de convexidad fuerte por αy reorganizamos los términos para obtener f(u+α(β−u)) −f(u) α≤f(β)−f(u)−λ 2(1 −α)kβ−uk2. Tomando el límite α→0, obtenemos que el lado derecho de la ecuanción converge a f(β)−f(u)−λ 2kβ−uk2. Por otro lado, el lado izquierdo se convierte en la derivada de la función g(α) = f(u+α(β−u)) en α= 0. Dado que ues un mínimo de f, se deduce que α= 0 es un mínimo de g, y por tanto el lado izquierdo de lo anterior tiende a cero cuando el límite α→0, con lo que concluye nuestra demostración. A partir de la Definición 5.11, vamos a ver una variante del descenso del gradiente estocástico que tiene una tasa de convergencia más rápida para problemas en los que la función objetivo es fuertemente convexa. En este caso, el método de descenso de gradiente estocástico se puede modificar a funciones λ-fuertemente convexas: Para un η > 0yT∈N: Inicializar con β(1) = 0 Para t= 1, ..., T −1: Vtvector aleatorio con E[Vt|β(t)]∈∂f(β(t)) ηt=1 λ·t β(t+1) 0=β(t)−ηtVt Actualizar β(t+1) = arg m´ınβkβ−β(t+1) 0k2(paso de “proyección”) Devolver ¯ β=PT t=1 β(t) T Nos basamos en la siguiente proposición, que generaliza el Lema 5.12, con una demostración muy similar y que no será detallada. Proposición 5.13. Si fes una función λ-fuertemente convexa entonces para cualquier vector β, uyv∈∂f(β)se cumple hβ−u,vi ≥ f(β)−f(u) + λ 2kβ−uk2 La proposición anterior es usada para probar el siguiente resultado que extiende el Teorema 5.9 a este tipo de funciones λ-fuertemente convexas: Teorema 5.14. Supongamos que fes λ-fuertemente convexa y E[kVtk2]≤ρ2. Sea β?∈ arg m´ınβ∈H f(β)una solución óptima. Entonces, E[f(¯ β)] −f(β∗)≤ρ2 2λT (1 + log(T)) 52 Demostración. Por hipótesis, fes una función fuertemente convexa. Como E[Vt|β(t)] está en el subgradiente de fen β(t), tenemos que hβ(t)−β?,E[Vt|β(t)]i ≥ f(β(t))−f(β?) + λ 2kβ(t)−β?k2.(5.12) Ahora veremos que hβ(t)−β∗,E[Vt|β(t)]i ≤ E[kβ(t)−β?k2−kβ(t+1) −β?k2] 2ηt +ηt 2ρ2(5.13) Por la definición de β(t) 0tenemos que kβ(t)−β?k2>kβ(t+1) −β?k2. Por lo tanto kβ(t)−β?k2−kβ(t+1) −β?k2≥ kβ(t)−β?k2−kβ(t) 0−β?k2 = 2ηthβ(t)−β?, Vti−η2 tkVtk2.(5.14) Tomando la esperanza ambos lados, reordenando y usando la hipótesis E[kVtk2]≤ρ2se obtiene la ecuación (5.13). Comparando las ecuaciones (5.12) y (5.13) y sumando sobre t obtenemos T X t=1 (E[f(β(t))] −f(β?)) ≤E"T X t=1 kβ(t)−β?k2−kβ(t+1) −β?k2 2ηt−λ 2kβ(t)−β∗k2!#+p2 2 T X t=1 ηt. A continuación, usamos la definición ηt= 1/(λt)y observamos que la primera suma del lado derecho de la ecuación se reduce a −λTkβ(T+1) −β?k2≤0. Por lo tanto, T X t=1 (E[f(β(t))] −f(β∗)) ≤ρ2 2λ T X t=1 1 t≤ρ2 2λ(1 + log(T)). El teorema se deriva de la desigualdad anterior, dividiendo por Ty usando la desigualdad de Jensen. La función f(β) = λ 2kβk2+RC(β)es una función λ-fuertemente convexa. Podemos pues, aplicar la variante del algoritmo del descenso de gradiente explicada anteriormente con β∈Rd. Para aplicar este algoritmo, solo necesitamos encontrar una forma de construir una estimación insesgada de un subgradiente de fen β(t). Esto se hace tomando una observación zal azar en C={z1, ..., zn}y elegir Vttal que Vt∈∂`(β(t),z)lo que hace que se tenga que el valor esperado de λβ(t)+Vtsea un subgradiente de fen β(t). El procedimiento de actualización sería el siguiente (el paso de “proyección no es necesario porque estamos trabajando con β∈Rd): β(t+1) =β(t)−1 λt λβ(t)+Vt=t−1 tβ(t)−1 λtVt =t−1 t t−2 t−1β(t−1) −1 λ(t−1)Vt−1!−1 λtVt =−1 λt t X i=1 Vi. (5.15) 53 Falsos negativos (FN): correo electrónico que es spam en clase verdadera pero que no es catalogado como spam. Clase Verdadera Clase en que se cataloga Spam No Spam Spam TP FP No Spam FN TN Tabla 6.2: Matriz de Confusión A partir de esta matriz de confusión mostrada en la Figura 6.2, se pueden definir las siguientes métricas que nos sirven para conocer cómo funcionan nuestros clasificadores según nuestros objetivos: La sensibilidad, también conocida como “Tasa de Verdaderos Positivos” o “recall” es la proporción de observaciones de spam que el modelo ha identificado correctamente como spam en relación con todas las instancias de spam reales: Sensibilidad =TP TP+FN La especificidad representa la proporción de observaciones que no son spam que el modelo ha identificado correctamente como no spam en relación con todas las observaciones que no son spam reales: Especificidad =TN TN+FP La precisión es la proporción de observaciones clasificadas correctamente como spam en relación con todas las observaciones clasificadas como spam por el modelo: Precisión =TP TP+FP La sensibilidad se centra en la capacidad del modelo para detectar positivos (spam), mientras que la especificidad se enfoca en la capacidad del modelo para detectar negativos (no spam). La precisión se refiere a la exactitud de las clasificaciones positivas realizadas por el modelo. En este ejemplo, donde seguramente no deseamos que un correo importante sea determinado como spam, a precio de que nos deje sin filtrar algún correo de spam, seguro que nos interesa una especificidad alta. Para nuestro conjunto de datos, podemos observar en la Tabla 6.3 un resumen de las principales métricas que se han obtenido a partir de la matriz de confusión para cada uno de los tres modelos. 60 show(tabKRad) true pred 0 1 0 773 58 1 31 519 show(tabKSig) true pred 0 1 0 773 67 1 31 510 show(tabKPol) true pred 0 1 0 767 48 1 37 529 Modelo Sensibilidad Especificidad Precisión Kernel Radial 0.89948 0.96144 0.94363 Kernel Sigmoidal 0.88388 0.96144 0.94269 Kernel Polinómico 0.91681 0.95398 0.93462 Tabla 6.3: Métricas de rendimiento de los clasificadores Para escoger el mejor clasificador para nuestro conjunto de datos, como hemos comentado anteriormente, nos basamos en aquel cuya especificidad sea mayor. Como para el kernel radial y el sigmoidal tienen la misma, vemos que el radial tiene mayor sensibilidad y precisión y en consecuencia es mejor clasificador. A continuación mostraremos un segundo ejemplo, usando también la librería e1071 en R, en un problema de mayor dimensionalidad p= 256. Con este fin, usaremos las imagenes correspondientes a los dígitos “5” y “8” escritos a mano incluidos en el conjunto “USPS” del repositorio UCI [8]. Este conjunto de datos se creó mediante el escaneo automático de sobres por parte del Servicio Postal de EE. UU. y muestra una amplia gama de estilos de fuente. Así, contaremos con un conjunto de datos X58 que contiene 556 dígitos que son etiquetados como “5” y 542 dígitos etiquetados como “8”. Estas imágenes contienen 16 ×16 píxeles, lo que nos lleva a p= 16 ×16 = 256 variables x1,x2, ..., x256 que miden la intensidad de la imagen en ese píxel. La Figura 6.1 muestra 4 de estas imágenes, dos correspondientes al dígito “5” y dos al correspondientes al dígito “8”. La variable cls de este conjunto X58 de datos nos proporciona la etiqueta (dígito) al que estaba asignada esa imagen. 61 Figura 6.1: Ejemplos de las imágenes consideradas en el conjunto de datos “USPS”. En este ejemplo, nos centraremos en usar kernels tipo “bases radiales” y, primeramente, eligiéremos los parámetros óptimos mediante la función tune.svm. Tras unas pruebas iniciales, acotamos nuestra búsqueda de parámetros en una rejilla de valores que se obtienen al cruzar valores de γentre 10−5,10−4, ..., y 10−1y valores del coste Centre 10−1, 100,101y102. El código utilizado es el siguiente: tobj <- tune.svm(cls~.,data=X58,kernel=’radial’, gamma=10^(-5:-1), cost=10^(-1:2)) summary(tobj) Obtenemos la siguientes salida numérica: Parameter tuning of ‘svm’: - sampling method: 10-fold cross validation - best parameters: gamma cost 0.001 10 - best performance: 0.01642202 - Detailed performance results: gamma cost error dispersion 1 1e-05 0.1 0.50816514 0.04439007 2 1e-04 0.1 0.10479566 0.05208055 3 1e-03 0.1 0.03185154 0.01972968 4 1e-02 0.1 0.11384487 0.03045004 62 5 1e-01 0.1 0.50816514 0.04439007 6 1e-05 1.0 0.08928274 0.03861044 7 1e-04 1.0 0.03004170 0.01604535 8 1e-03 1.0 0.01823186 0.01289617 9 1e-02 1.0 0.04917431 0.02579808 10 1e-01 1.0 0.47804837 0.07198567 11 1e-05 10.0 0.03185988 0.01878258 12 1e-04 10.0 0.01914095 0.01574600 13 1e-03 10.0 0.01642202 0.01349394 14 1e-02 10.0 0.04552961 0.02461888 15 1e-01 10.0 0.46167640 0.07105138 16 1e-05 100.0 0.02277731 0.01501645 17 1e-04 100.0 0.02188490 0.01376606 18 1e-03 100.0 0.01914095 0.01516277 19 1e-02 100.0 0.04552961 0.02461888 20 1e-01 100.0 0.46167640 0.07105138 Usando elección de parámetros por 10-fold (la segunda columna de la tabla anterior muestra los estimadores del error de generalización obtenidos al promediar los 10 errores en cada una de los 10 subconjuntos de datos que considera 10-fold y la última columna un estimador de la desviación típica de esos estimadores) vemos que unos parámetros bastante razonables para aplicar SVM con bases radiales son γ= 10−3= 0.001 yC= 10. Para estos valores de γyCse alcanza un error de generalización estimado de 0.0164. Es decir, esperaríamos equivocarnos, de forma automatizada, sobre un 1.64% de las imágenes, lo que no está nada mal puesto que algunas imágenes son ciertamente complejas de ser clasificadas correctamente por un humano, por usar escrituras de los dígitos bastante extrañas. Este resultado del tune.svm se puede representar gráficamente mediante: plot(tobj,transform.x = log10, xlab = expression(log[10](gamma)), transform.y = log10, ylab = expression(log[10](C)), color.palette = topo.colors) El gráfico obtenido puede verse en la Figura 6.2, donde se aprecia bastante bien como una correcta elección de parámetros γyCafecta notablemente al funcionamiento del SVM, pasando de tasas de error próximas al 1% (como la óptima anteriormente comentada) a tasas de error próximas al 50 % (casi equivalentes a asignar dígitos al azar en este ejemplo). 63 Figura 6.2: Resultado del tune.svm mostrando los errores 10-fold para distintas combinaciones de parámetros al usar kernels con “bases radiales” y justificando la elección γ= 10−3= 0.001 yC= 10. 64 Capítulo 7 Algunas extensiones Los SVM, como hemos visto en los capítulos anteriores, son un algoritmo muy utilizado de aprendizaje supervisado para resolver problemas de clasificación binaria. Sin embargo, a lo largo de los años, se han desarrollado varias extensiones del SVM para abordar diferentes problemas de aprendizaje automático. Una de las extensiones más comunes es la resolución del problema de clasificación multiclase. En lugar de clasificar entre dos clases, se trata de clasificar entre tres o más clases. Hay varias formas de abordar este problema, entre las que se incluyen la técnica “one-versus-all” y la técnica “one-versus-one”. Otra aplicación interesante de estos es el problema de “caracterización” de texto, que consiste en clasificar objetos que se representan mediante cadenas de caracteres, como secuencias de ADN, palabras o frases. En este caso, los SVM se utilizan en combinación con funciones kernel especiales para trabajar directamente con las secuencias de caracteres. Otra extensión tratada en muchos libros es la resolución del problema de regresión, donde el objetivo es predecir una variable continua en lugar de una variable categórica. Para ello, se utiliza una variante llamada SVM de regresión. En este capítulo comentaremos un poco por encima todas estas variantes junto con algunos métodos de optimización para el cálculo de los SVM como alternativas al algoritmo del gradiente estocástico visto en el Capítulo 5. Problema SVM Multiclase Hasta ahora, los problemas que hemos presentado a lo largo de este trabajo son problemas binarios, es decir, tenemos únicamente dos clases en las que se clasifican. Hay ocasiones en las que los datos pueden clasificarse en más de dos clases. Este es el caso de los problemas multiclase, donde xi∈Rpes el vector de variables predictoras e yi∈ {1,2, . . . , K}la etiqueta de clase, siendo Kel número de posibles clases. Ya que los clasificadores SVM expuestos en los capítulos anteriores están formulados solo para dos clases, necesitamos saber cómo la metodología SVM puede extenderse para distinguir entre K > 2clases. Para ello, se ha intentado definir el SVM multiclase de varias formas siempre tratando de reducir este problema a una serie de problemas binarios. Trataremos por encima dos de esos enfoques. El primero de ellos es el One-Versus-All, “uno contra el resto”, que divide el problema de clase Ken Ksubproblemas del tipo “clase k-ésima” frente a “clase no k-ésima”, con 65 k= 1,2, . . . , K. Tomando como referencia el subproblema k-ésimo, se construye la función fken el que la clase k-ésima se codifica como positiva y la unión de las demás clases se codifica como negativa en la clasificación. Una nueva observación x∈Rpse asignará a la clase con el mayor valor de fk(x), con k= 1,2, . . . , K, siendo fk(x)la solución SVM óptima para el problema binario de la k-ésima clase frente al resto. El otro enfoque es el que se conoce como One-Versus-One, “uno contra uno”, que divide el problema de clase Ken K 2problemas, que son todas las posibles comparaciones de los pares de clases. En este caso se construye una función clasificadora fjk codificando la “clase j-ésima” como positiva y la “clase k-ésima” como negativa, con j, k = 1,2, . . . , K yj6=k. Para una nueva observación x∈Rpse le asignará la clase que tenga el mayor número de votos evaluando en todas las funciones clasificadoras fjk y sumando dichos votos. Aunque este tipo de enfoques se utilizan ampliamente en la práctica para resolver problemas de SVM multiclase, se debe tener cuidado con su uso. El problema de “uno contra el resto” es popular para llevar a cabo tareas de categorización de texto, donde cada documento puede pertenecer a más de una clase. Esto es un tipo de problema que comentaremos brevemente a continuación. Este tipo de enfoque permite optimizar el método del SVM para cada subproblema binario, pero puede generar una clasificación diferente a otros clasificadores utilizados para el caso de multiclase. El éxito de la clasificación del enfoque de “uno contra el resto” depende del grado de desequilibrio del tamaño de clase de cada subproblema y de si una clase domina a todas las demás clases al determinar la clase más probable para cada nueva observación x. El enfoque de “uno contra uno”, que usa solo aquellas observaciones que pertenecen a las clases involucradas en cada comparación por pares, tiene el problema de tener que usar muestras más pequeñas para entrenar a cada clasificador, lo que, a su vez, puede aumentar la variabilidad de la solución. Problema de Categorización de Texto con SVM La categorización de texto es la asignación de documentos de texto (o hipertexto) en lenguaje natural a un número determinado de categorías predefinidas en función del contenido de dichos documentos. Aunque la categorización manual de documentos de texto es actualmente el sentido común, por ejemplo, usar carpetas para guardar archivos, mensajes de correo electrónico, direcciones URL, etc, algunas categorizaciones/clasificación de texto están automatizadas, como es el caso, como hemos visto en el Capítulo 6, de filtros de spam o correo no deseado para ayudar a los usuarios a lidiar con el gran volumen de mensajes de correo electrónico diarios. Para reducir los costos de las tareas de categorización de texto, se espera un mayor grado de automatización en el futuro. Para estos problemas de categorización de texto, se han propuesto durante estos años lo que se conoce como kernels de cadenas, que vamos a ver a continuación sin entrar mucho en detalle. Para ello, comencemos definiendo los siguientes conceptos. Sea Aun alfabeto finito, diremos que una cadena s=s1s2···s|s|, es una secuencia finita de elementos de A, incluyendo la secuencia vacía y donde |s| denota la longitud de s. Llamamos a uuna subsecuencia de s, que la denotamos como 66 u=s(i), si hay índices i= (i1, i2, . . . , i|u|), con 1≤i1<··· < i|u|≤ |s|, tal que uj=sij, j = 1,2,...,|u|. Si los índices ison contiguos, decimos que ues una subcadena de s. La longitud de uen ses `(i) = i|u|−i1+ 1, que es el número de elementos de ssuperpuestos por la subsecuencia u. Por ejemplo, sea sla cadena “SVM” (s1=S, s2=V, s3=M, |s|= 3), y considerense todas las posibles secuencias de 2 símbolos, “SV”, “SM” y “VM”, derivadas de s. Para la cadena u=SV, tenemos que u1=S=s1, u2=V=s2, de donde, u=s(i), donde i= (i1, i2) = (1,2). Así, `(i)=2. De manera similar, para la subsecuencia u=SM, se tiene que u1=S=s1, u2=M=s3, de donde, i= (i1, i2) = (1,3),y`(i) = 3. Además, la subsecuencia u=MV tiene u1=M=s2, u2=V=s3, de donde, i= (2,3), y `(i) = 2. Si D=Ames el conjunto de todas las cadenas finitas de longitud como máximo m del lenguaje definido A, entonces, el espacio de características para un kernel de cadena es RD. La transformación de las características Φu, que opera en una cadena s∈ Am, se caracteriza en términos de un cadena dada u∈ Am. Para tratar con subsecuencias no contiguas, definimos λ∈(0,1) como la tasa de disminución, o factor de reducción, y lo usamos para ponderar los huecos interiores en las subsecuencias. El grado de importancia que le damos a una subsecuencia contigua se refleja en cuanto de pequeño tomamos el valor de λ. El valor Φu(s)se calcula de la siguiente manera: hay que identificar todas las subsecuencias (indexadas por i) de sque son idénticas a u; para cada una de esas subsecuencias, se eleva λa la potencia `(i); y luego se suman los resultados sobre todas las subsecuencias. Debido a que λ < 1, los valores más grandes de `(i)tienen menos peso que los valores más pequeños de `(i). Esto se escribe como Φu(s) = X i:u=s(i) λ`(i), u ∈ Am.(7.1) Considerando el ejemplo anterior, tenemos que ΦSV(SVM) = λ2,ΦSM(SVM) = λ3y ΦVM(SVM) = λ2. Dos documentos se consideran “similares” si tienen muchas subsecuencias en común, es decir, cuantas más subsecuencias tengan en común, más similares se considerarán. Hay que tener en cuenta que el grado de contigüidad presente en una subsecuencia determina el peso de esa subcadena en la comparación; cuanto más cerca esté la subsecuencia de una subcadena contigua, más debería contribuir a la comparación. Sean sytdos cadenas. El kernel asociado con la transformación de características correspondientes a sytviene dado por la suma de los productos internos para todas las subcadenas comunes de longitud m, Km(s, t) = X u∈DhΦu(s),Φu(t)i =X u∈DX i:u=s(i)X j:u=s(j) λ`(i)+`(j).(7.2) El kernel (7.2) se denomina kernel de cadena, o kernel de subsecuencias ponderadas por intervalos. Para el ejemplo que hemos visto, sea tla cadena “SVA” (t1=S, t2= V, t3=A,|t|= 3). Tengase en cuenta que las cadenas “SVM” y “SVA” son subcadenas de la cadena “Support Vector MAchines”. 67 Las tres subcadenas de 2 elementos de tson “SVA”,“SA”,“VA”. Para estas subcadenas, tenemos que ΦSV(SVA) = λ2,ΦSA(SVA) = λ3yΦVA(SVA) = λ2. El producto interior (7.1) de las dos cadenas viene dado por K2(SV M, SV A) = hΦSV(SVM),ΦSV(SVA)i=λ4. El mapeo de características en el espacio de características generalmente se normalizan para eliminar cualquier sesgo introducido por la longitud del documento. Esto es equivalente a normalizar el kernel (7.2), K∗ m(s, t) = Km(s, t) qKm(s, s)Km(t, t). Para nuestro ejemplo, por la definición de (7.2) tenemos que K2(SVM,SVM) = hΦSV(SVM),ΦSV(SVM)i+hΦSM(SVM),ΦSM(SVM)i+hΦVM(SVM),ΦVM(SVM)i=λ6+ 2λ4, y, de manera similar, K2(SVA,SVA) = λ6+2λ4. Por tanto se tiene K∗ 2(SVM,SVA) = λ4/(λ6+ 2λ4) = 1/(λ2+ 2). Problema SVM de Regresión Dada la eficacia demostrada de los support vector machine en el ámbito de la clasificación, surge la pregunta de por qué no aprovechar esta teoría y conocimientos en otros contextos como la regresión. La técnica de los vectores de soporte se presenta como una herramienta versátil para resolver problemas de estimación de funciones en problemas de alta dimensionalidad. Debido a los buenos resultados alcanzados para la clasificación, se plantea la posibilidad de aplicar este enfoque basado en conceptos análogos a los vistos en los capítulos anteriores para abordar problemas de regresión. Para ello, tenemos que buscar el hiperplano regresor que mejor se ajuste al conjunto de datos de entrenamiento Cy no existe un conjunto de clases en las que queremos clasificar. En la clasificación SVM, el margen se utiliza para determinar la cantidad de separación entre dos clases de puntos que no se superponen: cuanto mayor sea el margen, más confianza tenemos en que el hiperplano de separación óptimo es un clasificador superior. En la regresión, no estamos interesados en separar puntos, sino en proporcionar una función de los vectores de entrada que sigan más de cerca los datos observados. Por lo tanto, en la regresión, la idea se basa en considerar una distancia margen ε, de tal forma que todas las observaciones han de encontrarse dentro de una banda otubo de nuestro hiperplano, es decir, que se encuentren a una distancia menor de εdel hiperplano. Para definir este hiperplano sólo se tiene en consideración aquellas observaciones que disten más de εdel hiperplano, que se describirán a través de variables de holgura. Estos será los considerados como vectores soporte. Para formular estas ideas, hay que definir una función de pérdida apropiada. La función de perdida que se define ignora los errores asociados con los puntos que se encuentran dentro de una cierta distancia ε > 0de la verdadera función de regresión lineal, f(x) = β0+xTβ. (7.3) Esto significa que si la observación (x, y)es tal que |y−f(x)| ≤ ε, entonces la pérdida se toma como 0 y si, por el contrario, la observación (x, y)cumple que |y−f(x)|> ε, entonces la pérdida es |y−f(x)|−ε. Con esta estrategia en mente, podemos definir los siguientes dos tipos de función de pérdida: Lε 1(y, f(x)) = m´ax{0,|y−f(x)|−ε}.(7.4) 68 Lε 2(y, f(x)) = m´ax n0,(y−f(x))2−εo.(7.5) Dichas funciones son denominadas funciones de pérdida ε-insensible lineal y cuadrática respectivamente. Veamos la optimización lineal del problema con estas funciones de pérdida. Definimos las variables de holgura ξiyξ0 jde la siguiente manera. Si la observación (xi, yi)está en la parte superior del ε-tubo, entonces ξi=yi−f(xi)−ε≥0, mientras que si la observación (xj, yj)se encuentra en la parte inferior del ε-tubo, entonces ξj= f(xj)−ε−yj≥0. Para las observaciones que quedan fuera del tubo, los valores de las variables de holgura dependen de la forma de la función de pérdida y para aquellas que están dentro del tubo, las variables de holgura tienen valor cero. Para la función de pérdida ε-insensible lineal, el problema de optimización primal es encontrar β0, β, ξ0= (ξ0 1,··· , ξ0 n)T,yξ= (ξ1,··· , ξn)Ttal que m´ın 1 2kβk2+C n X i=1 (ξi+ξ0 i) sujeto a: yi−(β0+xT iβ)≤ε+ξ0 i, (β0+xT i, β)−yi≤ε+ξi, ξ0 i≥0, ξi≥0, i = 1,2, . . . , n. (7.6) La constante C > 0se incluye en la formulación del problema de una manera análoga a como también sucedía para el problema de clasificación, para equilibrar la uniformidad de la función ffrente a nuestra tolerancia de desviaciones mayores que ε. Ya que εsolo se encuentra en las restricciones, la solución a este problema de optimización tiene que incorporar una banda alrededor de la función de regresión. En consecuencia, la función de Lagrange primal para el problema (7.6) es la siguiente. LP(β, β0, ξ, ξ0) = 1 2kβk2+C n X i=1 (ξi+ξ0 i)−X i ainyi−β0+xT iβ−ε−ξ0 io −X i binβ0+xT iβ−βi−ε−ξio −X i ciξ0 i−X i diξi, (7.7) donde ai, bi, ciydi, i = 1,2, . . . , n, son los multiplicadores de Lagrange, lo que implica que hay una restricción mas que es que ai, bi, ciydi,con i= 1,2, . . . , n, son todas no negativas. Las derivadas parciales de la función de Lagrange primal son ∂LP ∂β0 =X i ai−X i bi, ∂LP ∂β =β+X i aixi−X i bixi, ∂LP ∂ξi =C+bi−di, ∂LP ∂ξ0 i =C+ai−ci. (7.8) 69 Bibliografía [1] Trevor Hastie, Robert Tibshirani & Jerome Friedman,The Elements of Statistical Learning (Data Mining, Inference, and Prediction), Springer 2 Edition (2008). [2] Nello Critianini & John Shawe-Taylor,An Introduction to Support Vector Machines and other kernel-based learning methods, Cambridge University Press. [3] Shai Shalev Shwartz & Shai Ben David,Understanding Machine Learning, Cambridge University Press (2014). [4] Alan J. Izenman,Modern Multivariate Statistical Technicques, Springer Texts in Statistics (2006). [5] Corinna Cortes & Vladimir Vapnik,Support-vector networks. Machine learning, SpringerLink (1995). [6] Bernhard E. Boser, Isabelle M. Guyon & Vladimir N. Vapnik,A Training Algorithm for Optimal Margin Classifiers, Proceedings of the 5th Annual Workshop on Computational Learning Theory (COLT’92). [7] Alexandros Karatzoglou, David Meyer & Kurt Hornik Journal of Statistical Software, Support Vector Machines in R. April 2006, Volume 15, Issue 9. [8] UCI machine learning repository.https://archive.ics.uci.edu/ml/index.php [9] Kaggle.https://www.kaggle.com/datasets [10] The Comprehensive R Archive Network. https://cran.r-project.org/manuals. html. [11] Gareth James, Daniela Witten, Trevor Hastie & Robert Tibshirani, An Introduction to Statistical Learning with Applications in R, Springer Texts in Statistics (2013). [12] Frank Rosenblatt,The perceptron: a probabilistic model for information storage and organization in the brain, Psychological Review 65, 386-408 (1958). 1