Máquinas de vector soporte para dos y más clases

Máquinas de vector soporte para dos y más clases Eduardo Mera Gómez Máquinas de vector soporte para dos y más clases Eduardo Mera Gómez Memoria presentada como parte de los requisitos para la obtención del título de Grado en Matemáticas por la Universidad de Sevilla. Tutorizada por D.Justo Puerto Albandoz Índice general Introducción 1 Conceptos previos 3 0.1. Separación de puntos mediante hiperplanos orientados en RN. . . . . 5 0.2. La dimensión VC y el número de parámetros . . . . . . . . . . . . . . . . 8 0.3. Minimizar el límite minimizando h . . . . . . . . . . . . . . . . . . . . . 8 0.4. Principio de minimización del error estructural(SRM)(Vapnik,1979). . . . . . . . . . . . . . . . . . . 9 1. Máquinas de vector soporte lineales 11 1.1. Caso separable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.1. Fase de Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2. Caso no separable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2. Máquinas de Vector Soporte no lineales 21 2.0.1. Soluciones globales y unicidad . . . . . . . . . . . . . . . . . . . . 25 3. Métodos de solución 27 3.1. Método SMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1.1. Solución analítica de la optimización de dos puntos . . . . . . . 30 II MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES 3.1.2. Selección heurística de dos puntos . . . . . . . . . . . . . . . . . 32 4. Métodos Multi-Clase 35 4.1. Método uno contra uno (OVO) . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2. Método uno contra todos (OVA) . . . . . . . . . . . . . . . . . . . . . . . 36 4.3. Método de Weston-Watkins . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.4. Método de Cramer-Singer . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5. Experiencia computacional 51 5.1. Conjunto de datos IRIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.2. Conjunto de datos ADULT . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.3. Conjunto de datos WINE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6. Conclusión 57 Introducción La Máquina de Vector Soporte(SVM), nos aporta un algoritmo para, dado un conjunto de clases, predecir a qué clase pertenece una nueva observación. La idea consiste en separar, de la mejor manera posible, las observaciones de una muestra, mediante hiperplanos en el espacio, según su clase. Una vez realizado lo anterior, obtendremos una función clasificadora, que servirá para ver en qué lado del hiperplano se encuentra el valor de esa función al evaluar una nueva observación. La idea es asignarle a dicha observación, la clase correspondiente al lado del hiperplano en el que se encuentra. La aplicación principal de una SVM, consiste en aportar una predicción sobre a qué clase pertenece una nueva observación, gracias a entrenar el algoritmo a partir de una muestra de entrenamiento. Podemos encontrar aplicaciones prácticas en diferentes ámbitos. En el ámbito de la medicina, a partir de una muestra de pacientes, puede ayudar a predecir si un paciente padece o no una determinada enfermedad. En el ámbito de las finanzas, a partir de datos de operaciones y créditos de los que ya se conocen los resultados, permite predecir si un nuevo crédito o una nueva operación es viable. Nuestro objetivo en este trabajo, será el de definir el concepto de SVM, y abordar también los casos de separación no lineal y no separable. Trataremos de descubrir los problemas de optimización que será necesario resolver para obtener la función de clasificación. En un primer momento, presentamos los conceptos necesarios, como puede ser el caso de cuándo unas observaciones son separables. Una vez presentados estos conceptos, comenzaremos a desarrollar el problema deseado. Para ello abordaremos el caso en el que el hiperplano de separación es lineal y 2MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES las observaciones son separables. Para este problema, definiremos un determinado margen, que corresponderá a la distancia, ortogonal al hiperplano de separación, de ambos conjuntos. El hecho de que un punto correspondiente a una clase deba estar en el lugar que le corresponde del margen, nos aporta las restricciones del problema. Y el problema de optimización será el de obtener el hiperplano que maximiza dicho margen. Como todos los datos no son separables, o no conviene separarlos porque obtendríamos un margen demasiado pequeño. El siguiente paso será el de extender el problema anterior al caso no separable. El problema de optimización a resolver, será igual que el problema anterior pero añadiéndole unos valores de error a las restricciones que permiten que alguna observación no este correctamente clasificada. Una vez analizado este problema, trataremos extenderlo al caso en el que el separador no sea obligatoriamente lineal. Esto mejora el problema, ya que el hecho de que el separador pueda ser no lineal, relaja las restricciones. Para llevar a cabo esta generalización, se implementarán determinadas funciones denominadas Kernels, que sustituirán a los productos escalares presentes en el problema, y de las cuales veremos algún ejemplo. Cuando se haya construido el problema de SVM de 2 clases, no lineal y no separable, trataremos de desarrollar algunos métodos multi-clase. Dos de ellos estarán basados en la resolución de varias SVM de dos clases, y los otros tratarán de resolver el problema mediante un único problema de optimización. Por último desarrollaremos en el lenguaje Python, algunos ejemplos de implementación de SVM sobre algunos conjuntos de datos, de los más conocidos en el ámbito de Máquinas de Aprendizaje, para ver los resultados de la precisión en función del Kernel elegido. Conceptos previos En este capítulo, trataremos de definir algunos conceptos con los que trabajaremos más adelante. Para ello nos basaremos en diferentes conceptos recogidos en [1]. El "aprendizaje automático" es el algoritmo usado para la estimación de funciones, el término "entrenamiento" es el procedimiento de estimación de los parámetros que son usados en el procedimiento, "test" es el cálculo del valor de las funciones y "rendimiento" , el término usado para la precisión de la generalización. Definición 0.1. Una observación es un par de elementos {xi,yi} donde xies el elemento observado e yiel correspondiente "resultado" asociado a dicha observación. Ejemplo 0.1.Un caso práctico podría ser un estudio sobre pacientes de hospital. En dicho estudio, se estudia si un conjunto de pacientes tiene o no una enfermedad. En este caso, la matriz xiserían los datos recogidos del paciente ieyitomaría el valor 1 si el paciente padece la enfermedad y −1 en caso contrario. Se tratará de definir la máquina como un conjunto de posibles evaluaciones x7→ f(x,α). Para ello se asume que los puntos de la observación descrita anteriormente se distribuyen según una cierta distribución de probabilidad P(x,y), dichos datos se suponen independientes e idénticamente distribuidos. Se busca que exista un y determinado para cada valor de xdado. La máquina aprende la asignación xi7→ yide la muestra. Gracias a esta se obtiene una asignación x7→ f(x,α) que se usará para evaluar los nuevos datos en la fase "test". Se debe tener en cuenta que αes un parámetro ajustable para que la solución se acerque lo máximo posible a la realidad. El siguiente problema sería cómo elegir el parámetro αde la mejor forma posible. Para ello se necesita definir los errores que se tratarán de minimizar. 1 Máquinas de vector soporte lineales En este capítulo, desarrollaremos el concepto de Máquinas de Vector Soporte en el caso de separador lineal. Para ello nos basaremos en los conceptos de programación lineal recogidos en [4] y en los desarrollos de las SVMs recogidos en [1] y [8]. 1.1 Caso separable En esta sección se estudiará el caso en el cual nuestros datos de entrenamien- to {xi,yi},i=1,..l;yi∈{−1,1},xi∈Rd, vienen dados de forma que son separables mediante un hiperplano lineal como puede ser el siguiente ejemplo. Ejemplo 1.1.En este ejemplo en R2se puede observar como los puntos azules y los rojos, se pueden separar mediante una recta en el espacio. 12 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES El hiperplano de separación en cuestión podemos identificarlo con su ecuación general de la forma w∗x+b=0, donde wes un vector normal a dicho hiperplano y|b|/kwkes la distancia perpendicular al origen de dicho hiperplano, notando kwk como la norma euclídea. Si se toma un hiperplano que separe ambos grupos, y dado un nuevo punto, se le asigna un valor de yi, que depende del lado del hiperplano en el que se encuentre, se realiza el método del hiperplano clasificador. Se debe tener en cuenta que, en el caso de existir un hiperplano de separación, pueden existir infinitos, debido a que puede obtenerse otro mediante un giro, una traslación... El hiperplano que se suele utilizar es construido de la siguiente manera: Se denota d1la distancia entre el conjunto de los puntos {xi:yi=1} y el hiperplano de separación. Igualmente, se denota por d2a la distancia entre el conjunto de puntos {xi:yi=−1} y dicho hiperplano. Se define el margen como h=d1+d2y el problema consistirá en tomar el hiperplano de separación de tal manera que se maximice el margen. Este método es conocido por el nombre de Clasificador de Máximo Margen (o hiperplano de separación óptima). Es el método más natural, debido a que cuanto mayor sea el margen, existe una mayor confianza de que una observación sea evaluada correctamente. Para obtener el margen h, se construyen dos hiperplanos paralelos al hiperplano de separación, digamos H1={x∈Rd:w∗x+b=1} y H2={x∈Rd:w∗x+b=−1} tal que: xi∗w+b≥1∀xi|yi=1 xi∗w+b≤−1∀xi|yi=−1. Combinando ambas desigualdades obtenemos: yi(xi∗w−b)−1≥0∀i. Estos dos hiperplanos son paralelos al hiperplano de separación y cumplen que no hay puntos de entrenamiento entre ambos, por ello teniendo en cuenta que H1 tiene una distancia al origen de |1−b| kwkyH2de |−1−b| kwk, se obtiene que si se toma di,i=1,2 como la distancia del hiperplano Hial hiperplano de separación, se tiene d1=d2=1/kwk. Entonces el margen es h=2/kwky por lo tanto maximizar el margen consiste en minimizar kwk2cumpliendo las restricciones yi(xi∗w+b)−1≥0∀i. 1. MÁQUINAS DE VECTOR SOPORTE LINEALES 13 Los puntos que se observan que caen sobre los hiperplanos H1oH2en la figura anterior, son aquellos cuya variación cambiaría el problema y por ello se les conoce como vectores soporte. Este conjunto de puntos tiene una gran importancia, ya que el margen depende únicamente de ellos. Es decir, el movimiento de alguno de estos puntos, provocaría un cambio en el margen. Sin embargo, el movimiento del resto de puntos, siempre y cuando ese movimiento no haga que el punto cruce al otro lado del hiperplano que marca el margen, no afecta al cálculo del máximo margen. Se tiene entonces que resolver un problema de minimizar con restricciones. Se busca su formulación lagrangiana ya que esto convierte las restricciones originales, en términos de la función original mediante multiplicadores. Además los datos de entrenamiento aparecerán simplemente como productos escalares de vectores, lo cuál será beneficioso a la hora de generalizar el problema al caso no lineal. 14 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES El problema original consiste en: m´ ın wkwk2 s.a:yi(xi∗w+b)−1≥0∀i. Para pasar a la forma lagrangiana, se toman los multiplicadores de Lagrange, uno por cada una de las restricciones del problema original (al no ser ecuaciones de igualdad todas ellas, se tomará la generalización de Karush-Kunh-Tucker). Si partimos de un problema de la forma: m´ ın xf(x) s.a:hi≤0∀i. En ese caso se obtendría como función lagrangiana: LD=f(x)+ l X i=1 αi∗hi con αi≥0∀i. En nuestro caso se tomaría f(w)=kwk2 2yhi=1−yi(xi∗w+b)∀i∈ {1,...,l}, obteniendo la siguiente función lagrangiana: LD=kwk2 2+ l X i=1 αi(1−yi(xi∗w+b)). En este caso como restricciones se obtendría la propia condición αi≥0, la fórmula de Lagrange depende de dos variables, wyb, por ello por condición de optimalidad se obtienen las siguientes ecuaciones: d dwk LD=0 d db LD=0. Y a todo esto habría que añadirle las condiciones de holgura complementaria y las restricciones del problema original: αi((xi∗w+b)−1) =0∀i yi(xi∗w+b)−1≥0∀i. 1. MÁQUINAS DE VECTOR SOPORTE LINEALES 15 Por lo que se obtiene el problema siguiente: m´ ınw,bLP=kwk2 2+Pl i=1αi(1−yi(xi∗w+b)) s.a. d dwkLP=0k∈{1..d} d db LP=0 αi≥0∀i in{1..l} αi(yi(xi∗w+b)−1) =0∀i yi(xi∗w+b)−1≥0∀i. Se toma ahora el problema dual correspondiente al problema anterior, m´ axαLD(α). Para obtener la ecuación LDdel dual del problema de optimización lagrangiano, usamos las restricciones: ∇wLP=0 ∇bLP=0, ya que se obtiene: ∇wLP=kwk− l X i=1 αiyixi=0⇒kwk= l X i=1 αiyixi ∇bLP=− l X i=1 αiyi=0⇒ l X i=1 αiyi=0. Por lo que para obtener el valor de LDbasta con sustituir esos valores en LDya que buscamos tener el problema: m´ axα(m´ ınw,bLP). Por lo que LD=m´ ınw,bLPy dicho mínimo se alcanza para los valores de wy de b calculados anteriormente. Por ello: LD=1 2X i αiyixiX j αjyjxj+X i αi−X i αiyixiX j αjyjxj= =−1 2X i,j αiαjyiyjxixj+X i αi. 16 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES 1.1.1 Fase de Test Una vez "entrenada" la máquina de vector soporte, para utilizarla lo único que debemos hacer es ver en qué lado del hiperplano de separación se encuentra el pun- to x, y se le asigna el valor de ycorrespondiente a dicho lado del hiperplano. Es decir, sabemos la asignación de xsimplemente por el signo obtenido al evaluar la función f(x)=w∗x+b. 1. MÁQUINAS DE VECTOR SOPORTE LINEALES 17 1.2 Caso no separable En la realidad, podemos encontrarnos con que los puntos de la muestra no son separables, o bien, no es recomendable separarlos completamente. Esto ocurre cuando el hecho de separar todas las observaciones, de manera correcta, provoca que el margen sea muy pequeño. Como ya se ha comentado anteriormente, el hecho de que el margen sea muy reducido, produce una menor confianza de que las observaciones estén bien asignadas. Por este motivo, en ocasiones, merece la pena dejar que alguna de las observaciones no se encuentre en el lado correcto del margen, o incluso, en el otro lado del hiperplano de separación. Esto ofrece una mayor robustez en las nuevas observaciones individuales. La extensión del método del Hiperplano de Margen Máximo al caso no separable, es conocida como Clasificador de Vector Soporte. Ejemplo 1.2.Veamos un caso en el cual los datos de entrenamiento no son separables mediante un hiperplano. En este caso tenemos un conjunto de valores de entrenamiento que no son completamente separables mediante un hiperplano en el espacio. El problema es que usando el mismo algoritmo que en el caso separable, en ocasiones el problema es infactible. Por ello como solución a este problema se pueden relajar las restricciones : xi∗w+b≥1∀xi:yi=1 18 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES xi∗w+b≤−1∀xi:yi=−1. Para ello se introducen unas nuevas variables ξi, que serán los errores a cometer, pero solo serán distintas de 0 en el caso de que sea realmente necesario introducir ese error. Luego el siguiente paso es añadir algo que impida que sea distinto de 0 en casos en los que no sea necesario introducir la variable. La forma de resolver este problema es añadir un coste adicional por cada error que se utilice, es decir, cambiar la función a minimizar a kwk2 2+C(Piξi)kdonde Ces un parámetro elegido por el usuario que representa si le quiere añadir un coste mayor o menor a usar los errores. Para todo valor de kel problema es un problema de programación convexo, si k=1 ok=2 entonces es un problema de programación cuadrática y el valor k=1 tiene la ventaja extra de que ni los errores ni sus correspondientes multiplicadores de Lagrange aparezcan en el problema dual. Introduciendo estas nuevas variables se obtiene el siguiente problema: m´ ınw,ξikwk2 2+C(Pl i=1ξi)k s.a. yi(xi∗w+b)−1+ξi≥0∀i ξi≥0∀i. Por lo que volviendo a hacer el mismo razonamiento para pasar a su forma Lagrangiana, como se ha hecho en el caso separable, se obtiene el problema: LP=m´ ınw,b,ξikwk2 2+C(Pl i=1ξi)−Pl i=1αi{yi(xi∗w+b)−1+ξi}−Pl i=1µiξi s.a. d dwvLP=d db LP=d dξi=0∀i∀v(1.1) yi(xi∗w+b)−1+ξi≥0∀i(1.2) ξi,αi,µi≥0∀i(1.3) αi{yi(xi∗w+b)−1+ξi}=0∀i(1.4) µiξi=0∀i(1.5) 1. MÁQUINAS DE VECTOR SOPORTE LINEALES 19 Para ver el valor de LDcomo se ha hecho en el caso separable, se buscan los valores de w,b,ξque hacen mínimo el problema anterior para maximizar en αyµ. Para ello se utiliza (1.1) : d dwv LP=wv−X i αiyixi=0 d db LP=−X i αiyi=0 d dξi LP=C−αi−µi=0. Sustituyendo estos valores que son para los que se alcanza el mínimo se obtiene: LD=1 2Pi,jαiyixiαjyjxj+Pi(αi+µi)ξi−Pi,jαiyixiαjyjxj+Piαi−Pi(αi+µi)ξi= 1 2Pi,jαiαjyiyjxixj+Piαi−Pi,jαiαjyiyjxixj= −1 2Pi,jαiαjyiyjxixj. Se tiene que w=PNS i=1αiyixidonde NS es el número de vectores soporte. También se necesita el valor de b. Usando las ecuaciones (1.4) y (1.5) se puede obtener b, ya que usando esta última y la última ecuación obtenida a partir de (1.1) se obtiene que ξi=0∀i:αi≤C. Tomando aquellos puntos de entrenamiento tales que 0≤αi≤Cy usando la ecuación (1.4) con ξi=0 se puede calcular b. Se podría añadir un valor D, que aportase una restricción sobre la suma de ξi, es decir, Pl i=1ξi≤D. En este caso, el valor de Dtiene una gran importancia, es elegido mediante el método de validación cruzada. Se tiene que si el valor ξi>0, quiere decir que el punto xi, se encuentra al otro lado del margen. Si ξi>1, entonces el punto xise encuentra en el otro lado del hiperplano de separación. Por este motivo, como Pl i=1ξi≤D, quiere decir que si D=0, todas las observaciones son separadas de manera correcta. En el caso en el que D≥0, a lo sumo Dobservaciones se encuentran en el lado incorrecto del hiperplano. Esto es debido a que si el punto xi, se encuentra en el lado correcto del hiperplano, entonces ξi>1 y Pl i=1ξi≤D. El valor de Dcontrola el equilibrio sesgo-varianza de la técnica de aprendizaje. Si Des pequeño, pocos puntos pueden incumplir la restricción del margen, lo cual 26 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES que cumpla también que es ortogonal al vector de unos. Entonces tomando αi+α0 i, si 0 ≤αi+α0 i≤Cyα0satisface : Piαiyi=0. Se tiene un valor b α=α+α0, para el cual, al sustituir αpor b αen la solución, se convierte también en solución. Finalmente incluimos un resultado que demuestra que en el caso de que la solución no sea única entonces un punto que es solución puede ser transformado de manera continua en otro que es solución y todos los puntos intermedios son solución. Teorema 2.1. Sea la variable X representando al par de variables {w,b}. Sea el Hessiano para el problema semi-definido positivo y la función objetivo convexa. Sean X0y X1dos puntos para los cuáles la función objetivo alcanza el mínimo . Entonces existe un camino X =X(τ)=(1−τ)X0+τX1,τ∈[0,1], tal que , X (τ)es solución para todo τ. La demostración de este teorema es directa por la condición de convexidad. 3 Métodos de solución En este capítulo, expondremos algunos métodos de solución, ya que en la mayoría de casos reales es necesaria una resolución numérica del problema. Esto solo puede ser resuelto de manera analítica en el caso en que el número de datos de entrenamiento sea pequeño. Por ello expondremos algunos métodos recogidos en [7]. Los pasos a seguir, son: ver las condiciones de optimalidad de Karush-Kunh- Tucker, definir una estrategia de aproximación al dato óptimo mediante un incremento uniforme del valor de la función objetivo del dual y usar un algoritmo de descomposición para que sólo partes de los datos de entrenamiento sean manejadas en cada momento. El método que se usará para este fin, es un método de conjunto activo que combina el método de Newton, y el método de ascenso del gradiente conjugado. Esto se realiza, porque ambos métodos por si solos tienen algún inconveniente para este fin. El método de Newton puede resolver problemas con restricciones de igualdad en tan solo un paso, pero hay que tener en cuenta el coste de almacenamiento extra de una factorización del Hessiano proyectado. El método de ascenso del gradiente conjugado, puede resolver problemas cuadráticos en a lo sumo lpasos, con lel número de datos de entrenamiento, pero tiene la desventaja de que solo una nueva restricción es añadida cada vez. Para solventar este problema, se entra en los llamados "Métodos de proyección" donde una vez seleccionado un punto de la región factible, se realizan búsquedas unidimensionales y proyecciones para que el movimiento permanezca dentro de la región factible, lo que permite añadir varias restricciones al mismo tiempo. Expliquemos en qué consiste el método. Primero, hay que tener en cuenta que cuando se calcula la función objetivo, también se calcula el gradiente con un pequeño coste extra. Encuanto al funcionamiento del método, en un primer momento, las 28 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES direcciones de búsqueda, denotadas por s, se encuentran a lo largo del gradiente. Se busca el conjunto de puntos más cercano dentro de la región factible. Si el producto escalar del gradiente con sindica que el máximo a lo largo de scae entre el punto original y el conjunto de puntos comentado anteriormente, se cálcula el punto óptimo a través de la dirección de búsqueda de manera analítica y se pasa a la segunda fase. De lo contrario se busca un nuevo conjunto de puntos y se repite el paso anterior. En la fase 2 , se realiza el método de ascenso del gradiente conjugado de Polak-Ribiere, hasta que se encuentre un nuevo conjunto de puntos cómo los descritos anteriormente, en cuyo caso se volvería a aplicar el primer paso, o se llegue al criterio de parada. Dicho algoritmo se detiene cuando la razón fracción de aumen- to de la función objetivo cae por debajo de una cierta tolerancia(normalmente se toma 1.e−10, para una precisión doble). Las direcciones de búsqueda se toman de manera que los αicontinúen satisfaciendo la restricción Piαiyi=0. Es importante que además la proyección sea implementada de tal manera que el ángulo entre la dirección de búsqueda anterior y la resultante se minimice. Una vez acabado el algoritmo, se puede comprobar si este esta funcionando correctamente, comprobando que la solución satisfaga las condiciones de Karush- Kun-Tucker ya que son condiciones necesarias y suficientes de optimalidad. Una cosa importante que se debe tener en cuenta en los métodos de solución es la complejidad de dicho método. Tanto en la fase de entrenamiento como en la fase de test, solo depende del Kernel, el cual incluso aunque sea un producto escalar en un espacio infinito o de dimensión muy alta, la complejidad de calcular K puede ser pequeña. Para Kernels de la forma K=(xi·xj)p, un producto escalar en Hrequiere ¡dL+p−1 p¢operaciones, mientras que el cálculo de Krequiere dLoperaciones. En cuanto a la fase de entrenamiento, se dará la complejidad de uno de los algoritmos de entrenamiento (Bunch-Kaufman), en cuyos resultados se tendrá en cuenta que pueden ser usadas diferentes estrategias dependiendo de la situación. Se tiene en cuenta el problema de entrenamiento con solo una "chunk"(porción). Sea l el número de puntos de entrenamiento, NSel número de vectores soporte, y dLla dimensión de los datos de entrada. En el caso en el que muchos vectores suporte no estén en el límite superior y NS/l<< 1 entonces el número de operaciones es O(N3 S+(N2 S)l+NSdLl). Si NS/l≈1 entonces es O(N3 S+NSl+NSdLl). Para el caso en el que muchos vectores soporte estén en el límite superior, si NS/l<<1 entonces es O(N2 S+NSdLl) y si NS/l≈1 es O(DLl2). El método "chunking" empieza con un subconjunto pequeño y arbitrario de da- 3. MÉTODOS DE SOLUCIÓN 29 tos y entrena sobre ellos, una vez realizado dicho entrenamiento, se usa el resto de puntos de entrenamiento para probarlo y se anotan los errores cometidos, de aquellos puntos que con el método actual, se le ha asignado un valor (o un lado del hiperplano) que no les corresponde. A continuacuón se genera otra "porción" de los datos, usando los Nprimeros de estos, combinados con los NSvectores soporte ya conocidos. A la hora de elegir N+NShay que cuidar ciertos detalles como que el tamaño de la nueva "porción" sea el adecuado para la convergencia. Se sigue empleando el método hasta que todas las condiciones de Karush-Kun-Tucker se cumplan. En la fase de test se debe simplemente evaluar la ecuación: f(x)= NS X i=1 αiyiΦ(si)·Φ(x)+b= NS X i=1 αiyiK(si,x)+b. Lo cual requiere O(MNS) operaciones, donde Mes el número de operaciones requeridas para calcular el Kernel.En el caso de los Kernels que son productos escalares o funciones de base radial, Mes O(dL), la dimensión de los vectores de datos. 3.1 Método SMO Cuando se habla de métodos de solución hay que destacar el método del algoritmo de Optimización Mínima Secuencial (SMO), que es el método más utilizado, puesto que es el más competitivo y sencillo de implementar. El método "Chunking", o de descomposición, estaba caracterizado por empezar por un subconjunto pequeño de datos y entrenar sobre ellos. El algoritmo SMO realiza algo parecido, con la excepción de que toma un subconjunto de tan solo 2 puntos y los optimiza en cada iteración. La gran ventaja que tiene sobre otros algoritmos es el hecho de que al tratar solo la optimización de dos puntos (a través de una modificación en los multiplicadores) esto puede hacerse de manera analítica. En el proceso de modificar los multiplicadores para buscar una mejora en el valor de la función objetivo, hay que tener en cuenta que la modificación de un multiplicador, implica la modificación de al menos otro de ellos. Esto es necesario para que la condición Pl i=1αiyi=0 se siga cumpliendo. En un principio, podría parecer que dará lugar a un algoritmo costoso, ya que necesita un mayor número de iteraciones. A pesar de ello como el número de operaciones es muy pequeño para cada iteración, el algoritmo es bastante rápido. 30 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES 3.1.1 Solución analítica de la optimización de dos puntos En esta sección se explicará cómo se modifican los multiplicadores y bajo qué criterios, para mejorar el valor de la función objetivo sin dejar de cumplir las restricciones. La primera restricción que se debe cumplir es Pl i=1αiyi=0. Para ello se debe mantener la proporción. Si se eligen por ejemplo α1yα2, denotando por αnel nuevo valor de αy por αoel antiguo valor, se debe mantener αn 1y1+αn 2y2=αo 1y1+αo 2y2. Añadiendo la restricción 0 ≤α1,α2≤Cse puede acotar la solución de los nuevos valores. Veamos los valores en los que se mueve αn 2Para ello hay que diferenciar dos casos: Si y16= y2, tomaremos por ejemplo y1=−1,y2=1. Usando la condición descrita anteriormente sustituyendo los valores de y1,y2se obtiene: −αn 1+αn 2=−αo 1+αo 2 αn 2=−αo 1+αo 2+αn 1. Usando que αn 1≥0: αn 2≥−αo 1+αo 2. Por lo tanto α2≥m´ ax{0,αo 2−αo 1}. Por otro lado usando αn 2=−αo 1+αo 2+αn 1yαn 1≤C, se tiene αn 2≤C−αo 1+αo 2. Por ello α2≤m´ ın{C,C−αo i+αo 2}. Si y1=y2análogamente, utilizando las mismas ecuaciones pero tomando y1= y2=1 y despejando αn 2se obtiene: m´ ax{0,αo 1+αo 2−C}≤αn 2≤m´ ın{C,αo 1+αo 2}. Para facilitar la notación, tomaremosUcomo la acotación inferior en cada caso, yVcomo la cota superior. El objetivo es ver, analíticamente, cuándo se alcanza el máximo de la función objetivo, en el caso de que solo se puedan variar, por ejemplo, α1yα2. Para este fin, es necesario introducir una definición de error, que será la diferencia entre el valor yiy el valor de f(xi). Esto es, Ei=f(xi)−yi=(Pl j=1αjyjK(xj,xi)+b)−yi. Este error no se considera un error de asignación, ya que si yi=1 y f(xi)=4, la asignación es correcta, sin embargo el error es 3. Se necesitará también la segunda derivada de la función objetivo a lo largo de la línea diagonal, que toma el valor −k con k=K(x1,x1)+K(x2,x2)−2K(x1,x2)=kΦ(x1)−Φ(x2)k2. 3. MÉTODOS DE SOLUCIÓN 31 Teorema 3.1. El máximo de la función objetivo del problema de optimización dual, en el caso en el que se pueden modificar tan solo α1yα2, se obtiene para los siguientes valores de α1yα2. Se calcula αn,u 2=αo 2+y2(E1−E2) k. Se acota para que cumpla las restricciones alcanzadas anteriormente: αn 2=              V si αn,u 2>V αn,u 2si U ≤αn,u 2≤V U si αn,u 2<U Por último, se toma αn 1=αo 1+y1y2(αo 2−αn 2). Demostración. Se define vi=Pl j=3yjαjK(xi,xj)=f(xi)−P2 j=1yjαjK(xi,xj)−b,i=1,2. y se considera la función objetivo como función de α1yα2: W(α1,α2)=α1+α2−1 2K11α2 1−1 2K22α2 2−y1y2K12α1α2−y1α1v1−y2α2v2+Const. Usando lo visto anteriormente se tiene: α1+sα2=αo 1+sαo 2=γ, donde stoma el valor 1 en el caso y1=y2, y −1 en caso contrario. Utilizando este valor, se busca la función objetivo en función de α2. W(α2)=γ−sα2+α2−1 2K11(γ−sα2)2−1 2K22α2 2 −sK12(γ−sα2)α2−y1(γ−sα2)v1−y2α2v2+Const. Esta será la nueva función a optimizar, con respecto a α2, por lo que usando la condición de optimalidad d(W(α2)) dα2=0, se obtiene: d(W(α2)) dα2=1−s+sK11(γ−sα2)−K22α2 +K12α2−sK12(γ−sα2)+sy1v1−y2v2=0. Como s=1, si y1=y2, y −1 en el caso contrario, se puede cambiar sy1v1por y2v1, ya que si y1=y2, entonces s=1 y se puede cambiar y1por y2. Por otro lado, si y16= y2, entonces s=−1 y convierte y1en y2al cambiarle el signo. La condición de optimalidad permite llegar a la siguiente igualdad: 32 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES αn,u 2(K11 +K22 −2K12)=1−s+γs(K11 −K12)+y2(v1−v2) =y2(y2−y1+γy1(K11 −K12)+v1−v2). Por lo tanto usando los valores de v1yv2: αn,u 2ky2=y2−y1+f(x1)−P2 j=1yjαjKi j +γy1K11 −f(x2)+P2 j=1yjαjKi j −γy1K12 =y2−y1+f(x1)−f(x2)+y2α2K11 −y2α2K12 +y2α2K22 −y2α2K12 =y2α2k+(f(x1)−y1)−(f(x2)−Y2), obteniéndose: αn,u 2=α0 2+y2(E1−E2) k. Por último hay que acotar αn 2, a partir de este valor, para que cumpla las condiciones. 3.1.2 Selección heurística de dos puntos Es importante la elección de los dos puntos que se tratarán de optimizar. Para llevarlo a cabo, se busca elegir aquellos puntos que tienen una mayor influencia en el progreso general hacia la solución. Una forma de elegir puntos que tengan una gran influencia en este proceso es elegir aquellos que más incumplen las condiciones de Karish-Kunh-Tucker. En este proceso hay que elegir dos puntos. Para elegir el primero, se busca a través de aquellos puntos que no cumplen las condiciones de KKT. Para buscarlos de una manera más sencilla, el algoritmo, en un principio, busca estos puntos a través de aquellos que cumplen la restricción 0 <αi<C. Es decir, a través de aquellos puntos que no se encuentran en el límite de la región factible. Solo cuando todos estos puntos satisfacen las condiciones KKT, se realiza el algoritmo a través de todo el espacio. Cuando encuentra un punto que incumple las condiciones, se selecciona 3. MÉTODOS DE SOLUCIÓN 33 y pasa a buscar el segundo de la siguiente manera: Como ya se tiene el primer punto, el segundo se busca de manera que la actualización de α1yα2produzca un mayor aumento de la función dual objetivo. La manera de seleccionar el segundo punto, es buscar aquel que consigue maximizar |E1−E2|. Nótese, que todo el desarrollo del apartado anterior y de este, depende del valor de C. Este proceso puede realizarse de igual manera en el caso de que Cfuese infinito. Esto relajaría las restricciones sobre αi. La única diferencia con lo realizado anteriormente es que se alcanzan unos valores distintos de U,Vy, como consecuencia, también cambian los valores de αn 1,αn 2calculados en el teorema del apartado anterior. Todo esto se obtiene de manera idéntica al caso anterior. 4 Métodos Multi-Clase En ocasiones, no se pretende clasificar las observaciones en dos clases distintas, sino en más de dos clases. Las máquinas de vector soporte de K-clases, consisten en, a través de una muestra de lobservaciones, (xi,yi), donde xies un vector d-dimensional, e yi∈{1,...,k}, que marca a qué clase corresponde la observación i-ésima. Se debe obtener una función de decisión, que a cada valor xle asigne la clase que le corresponda. Para llevar a cabo esta tarea, describiremos ciertos métodos eficaces para asignarle a cada observación su correspondiente clase. La mayoría de métodos multi-clase, consisten en reducir un problema de clasificación multi-clase, en múltiples problemas de clasificación de dos clases. En este apartado vamos a ver métodos que se obtienen de realizar esta división en problemas de dos clases, basándonos en [8]. Además, desarrollaremos algunos de los métodos que se basan en la resolución directa de un problema de optimización para varias clases. Concretamente, expondremos los recogidos en [3] y [9]. Empecemos por dos bastante conocidos, y que se obtienen directamente utilizando las máquinas de vector soporte descritas anteriormente. 4.1 Método uno contra uno (OVO) Suponemos que se tienen Kclases diferentes. En este método, se construirá una máquina de vector soporte para cada combinación posible de las Kclases. Por lo tanto habrá ¡K 2¢máquinas de vector soporte. 42 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES Introduciendo estos valores en la formulación lagrangiana, se obtiene un problema de máximo que solo depende de η. Esto es: Q(η)=−1 2β−1X i,j (¯ xi·¯ xj)[X r (δyi,r−ηi,r)(δyj,r−ηj,r)]−X i,r ηi,rδyi,r. Usando ¯ 1yicomo el vector que tiene el valor 1 en la componente yiy 0 en el resto, se llega al problema: m´ axηQ(η)= −1 2β−1Pi,j(¯ xi·¯ xj)[(¯ 1yi−¯ ηi)·(¯ 1yj−¯ ηj)]−Pi¯ ηi·¯ 1yi s.a:¯ ηi≥0, ¯ ηi·¯ 1=1∀i. Para simplificar la notación se toma ¯ τi=¯ 1yi−¯ ηi, notación con la que se obtiene: ¯ Mr=β−1X i τi,r¯ xi. (4.3) Además, sustituyendo los productos escalares por Kernels y omitiendo cualquier constante aditiva o multiplicativa, lo que se puede hacer ya que buscamos los valores de las variables que maximizan la función y no el valor de la función en sí, se llega finalmente al problema de optimización: m´ axτQ(τ)= −1 2Pi,jK(¯ xi·¯ xj)(¯ τi·¯ τj)+βPi¯ τi·¯ 1yi s.a:¯ τi≤¯ 1yi,¯ τi·¯ 1=0∀i. La función de decisión toma el valor: H(¯ x)=k argmax r=1 {X i τi,rK(¯ x,¯ xi)}. En el caso en el que quisiésemos resolver este problema dual de programación cuadrática, al tener m∗kvariables, una técnica normal de programación cuadrática, emplea una matriz de dimensión (mk)x(mk). Esto para problemas de dimensiones elevadas, es muy difícil de manejar. Debido a todo esto, se tratará de descomponer el problema, en problemas más pequeños. La idea es tomar las restricciones del problema original, y dividirlas en mconjuntos 4. MÉTODOS MULTI-CLASE 43 de la forma: {¯ τi,¯ τi≤¯ 1yi,¯ τi·¯ 1=0}m i=1. El algoritmo usado para resolver el problema de optimización se basa en tomar p, y mejorar el valor de la función objetivo, actualizando el valor de ¯ τpbajo las restricciones correspondientes a ese valor. Veamos el problema de optimización a realizar en cada elección de p, aislando la contribución de pal valor de la función objetivo. Qp(¯ τp)=−1 2Pi,jKi j (¯ τi·¯ τj)+βPi¯ τi·¯ 1yi =−1 2Kp,p(¯ τp·¯ τp)−Pi6=pKi,p(¯ τp·¯ τi) −1 2Pi6=p,j6=pKi,j(¯ τi·¯ τj)+β¯ τp·¯ 1yp+βPi6=p¯ τi¯ 1yi =−1 2Kp,p(¯ τp·¯ τp)−¯ τp·[−β¯ 1yp+Pi6=pKi,p¯ τi] +[−1 2Pi6=p,j6=pKi,j(¯ τi·¯ τj)+βPi6=p¯ τi¯ 1yi]. Tomando los siguientes valores: Ap=Kp,p>0 (4.4) ¯ Bp=−β¯ 1yp+X i6=p Ki,p¯ τi(4.5) Cp=−1 2X i,j6=p Ki,j(¯ τi·¯ τj)+βX i6=p ¯ τi·¯ 1yi(4.6) Como Cpno influye en la solución de esta etapa al no depender de p, se puede omitir. Se llega al problema de optimización : m´ ın¯ τpQ(¯ τp)=1 2Ap(¯ τp·¯ τp)+¯ Bp·¯ τp s.a:¯ τp≤¯ 1yp,¯ τp·¯ 1=0. En la aplicación de esta estrategia, los tres problemas a resolver son: cómo seleccionar el criterio de parada, cómo seleccionar el valor pen cada etapa, y cómo resolver el problema reducido. 44 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES Comencemos buscando el criterio de parada. El problema que se quiere resolver es: m´ ınτQ(τ)=1 2Pi,jK(¯ xi·¯ xj)(¯ τi·¯ τj)−βPi¯ τi·¯ 1yi s.a:¯ τi≤¯ 1yi,¯ τi·¯ 1=0∀i. Se utilizan las condiciones de KKT para determinar las condiciones de optimalidad que debe cumplir una solución ¯ τ. Pasando al lagrangiano se obtiene: L(τ,u,v)=1 2Pi,jKi,jPr(τi,rτj)−βPi,rτi,rδyi,r +Pi,rui,r(τi,r−δyi,r)−PiviPrτi,r s.a:ui,r≥0∀i,r. Las condiciones de optimalidad dan la condición: d dτi,r L=X j Ki,jτj,r−βδyi,r+ui,r−vi=0. (4.7) Se define: Fi,r=X j Ki,jτj,r−βδyi,r. (4.8) Este valor marca la confianza en asignar la clase ra¯ xi. Nótese que: Fp,r=Bp,r+kp,pτp,r, (4.9) lo que será necesario más adelante. Derivando L(τ,u,v) con respecto a las variables duales, uyv, y utilizando (4.8), se llega a: Fi,r+ui,r=vi∀i,r. (4.10) ui,r(τi,r−δyi,r) (4.11) ui,r≥0 (4.12) 4. MÉTODOS MULTI-CLASE 45 A la hora de interpretar estas restricciones, nos encontramos con dos casos claramente diferenciados: El primero: τi,r=δyi,r. Entonces como ui,r≥0, se tiene por (4.10) Fi,r≤vi(4.13) Por otro lado, si τi,r<δyi,r. Entonces para que se cumpla (4.11), se tiene ui,r=0, por lo que, por (4.10), Fi,r=vi∀i,r. Esto último equivale a las dos restricciones: Fi,r≤vi(4.14) Fi,r≥vi(4.15) Utilizando las restricciones del problema original, ¯ τi≤¯ 1yiy¯ τi=0∀i, obtenemos: ∃r:τi,r<δyi,r. Se tiene vi=m´ axrFi,r. Combinando (4.13),(4.14) y (4.15). maxrFi,r≤vi≤m´ ın r:τi,r<δyi,r Fi,r(4.16) Por lo que se obtiene: m´ ax rFi,r≤m´ ın r:τi,r<δyi,r Fi,r(4.17) Si se define Ψi=m´ axrFi,r−m´ ınr:τi,r<δyi,rFi,r, entonces la condición de optimalidad necesaria y suficiente es Ψi=0. El criterio de parada buscado será: dado ²>0, Ψi<². Una vez decidido el criterio de parada del algoritmo, queda por determinar el valor inicial y cómo resolver el problema de optimización reducido. Comenzamos reescribiendo Q(τ) usando una expresión como forma cuadrática y sin el índice p Q(τ)=−1 2A(¯ τ·¯ τ)−¯ B·¯ τ =−1 2A[(¯ τ+¯ B A)·(¯ τ+¯ B A)]+¯ B·¯ B 2A. Es necesario introducir ahora las siguientes variables: ¯ ν=¯ τ+ ¯ B A¯ D= ¯ B A+¯ 1y. (4.18) 46 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES Al igual que ocurrió antes, no es necesario tener en cuenta las constantes aditivas o multiplicativas ya que no influyen sobre las variables en el óptimo. Así, se llega al problema: m´ ınν=Q(¯ ν)=k¯ νk2 s.a:¯ ν≤¯ D,¯ ν·¯ 1=¯ D·¯ 1−1. Denotando las variables duales del problema como θyαi, se obtiene por las condiciones de KKT las siguientes restricciones: νr≤Dr;αr(νr−Dr)=0;νr+αr−θ=0∀r. Como αr≥0, se tiene νr≤θ∀r. Uniéndolo a la primera restricción, se tiene: νr≤m´ ın{θ,Dr}. (4.19) En realidad, se espera la igualdad ya que en el caso en el que αr=0, νr=θ, y en el caso en el que αr>0, se tiene νr=Dr. Usando ¯ ν·¯ 1=¯ D·¯ 1−1, se llega a: k X r=1 m´ ın r{θ,Dr}= k X r=1 Dr−1. (4.20) La suma Pk r=1m´ ınr{θ,Dr} es una función estrictamente monótona y continua en θ. Por ello existe un único θ∗que satisface (4.20), veamos que corresponde a la solución óptima. Teorema 4.1. Sea ν∗ r=m´ ın{θ∗,Dr}donde θ∗es solución de Pk r=1m´ ınr{θ,Dr}= Pk r=1Dr−1. Entonces, ∀¯ ν, se tiene: k¯ νk2>k¯ ν∗k. Demostración. Se llevará acabo mediante reducción al absurdo. Supongamos que existe otro punto factible ¯ ν=¯ ν∗+¯ ∆que minimiza la función objetivo y ¯ ν6= ¯ ν∗, por lo que ¯ ∆6=0. Como tanto ¯ νy¯ ν∗deben cumplir las restricciones del problema original, Pr∆r=0, por el mismo motivo, también se tiene: ∆r≤0 cuando ν∗ r=Dr. Combinando ambas con la restricción ¯ ∆6=0, se tiene ∆s>0 para algún s con ν∗ s=θ. Usando de nuevo Pr∆r=0, se tiene que ∃utal que, ∆u<0. Sea ²=m´ ın{|∆s|,|∆u|}. Se define otro punto factible ¯ ν0como: ν0 s=νs−²,ν0 u=νu+² yν0 r=νren otro caso. Como ¯ νy¯ ν0solo difieren en las coordenadas syu, se tiene: k¯ ν0k2−k¯ νk2=(ν0 s)2+(ν0 u)2−(νs)2−(νu)2. 4. MÉTODOS MULTI-CLASE 47 Al escribir ¯ ν0en función de ¯ νy², se tiene : k¯ ν0k2−k¯ νk2=2²(²−νs+νu). Por la construcción de ¯ ν0, se tiene νu−²=θ>vsoνu−²>θ≥νs, y por lo tanto, νu−²>νs. Esto implica: k¯ ν0k2−k¯ νk2<0. lo que es una contradicción. Una vez probada esta propiedad, se busca un algoritmo de punto fijo para aproximar el valor de θ∗. Se utiliza que m´ ın{θ,Dr}+m´ ax{θ,Dr}=θ+Dr, que con (4.20) implica que : k X r=1 [θ+Dr−m´ ax{θ,Dr}] = k X r=1 Dr−1, lo que nos lleva a F(θ∗)=θ∗=1 k[ k X r=1 m´ ax{θ∗,Dr}]−1 k. (4.21) El algoritmo consistirá en, una vez elegido un punto θ, obtener el siguiente valor sustituyendo θpor F(θ). El valor óptimo cumple F(θ∗)=θ∗. El algoritmo termina cuando dos valores consecutivos de θse encuentran lo suficientemente cerca. En cuanto al valor inicial, se demuestra que si θ1≤m´ axrDr, el algoritmo converge hacia θ∗ Teorema 4.2. Sea θ∗el punto fijo de la ecuación F(θ). Si θ1≤m´ axrDry sea θl+1= F(θl). Para l ≥1se tiene: kθl+1−θ∗k kθl−θ∗k≤1−1 k, donde k es el número de clases. Demostración. Asumimos sin pérdida de generalidad: m´ axrDr=D1≥D2≥... ≥ Dk≥Dk+1=−∞. Asumimos θ∗∈(Ds+1,Ds) y θl∈(Du+1,Du) donde u,s∈{1,...,k}. Se tiene: θl+1=F(θl)=1 k[Pk r=1m´ ax{θl,Dr}]−1 k =1 k(Pk r=u+1θl)+1 k(Pu r=1Dr)−1 k=(1−u k)θl+1 k(Pu r=1Dr−1). 48 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES Si θl≤m´ axrDr⇒θl+1≤m´ axrDr. Análogamente, se obtiene: θ∗=F(θ∗)=(1−s k)θ∗+1 k( s X r=1 Dr−1) ⇒θ∗=1 s( s X r=1 Dr−1). Consideramos 3 casos: Primer caso, u=s. En ese caso : |θl+1−θ∗| |θl−θ∗|=|(1−s k)θl+1 k(Ps r=1Dr−1)−θ∗| |θl−θ∗| =|(1−s k)θl+s kθ∗−θ∗| |θl−θ∗| =1−s k≤1−1 k. Segundo caso u>s, entonces ∀r=s+1,...,use tiene: θl≤Dr≤θ∗. (4.22) Usando los valores para θl+1yθ∗anteriores, se llega a θl+1=(1−u k)θl+1 k(Pu r=1Dr−1) =(1−u k)θl+s k 1 s(Ps r=1Dr−1)+1 k(Pu r=s+1Dr) =(1−u k)θl+s kθ∗+1 k(Pu r=s+1Dr). Aplicando (4.22), se obtiene : θl+1≤(1−u k)θl+s kθ∗+1 k(u−s)θ∗ =(1−u k)θl+u kθ∗. Entonces se tiene: |θl+1−θ∗| |θl−θ∗|=θ∗−θl+1 θ∗−θl ≤θ∗−(1−u k)θl−u kθ∗ θ∗−θl =1−u k≤1−1 k. 4. MÉTODOS MULTI-CLASE 49 Caso 3 u<ses análogo al anterior intercambiando los roles de uys. 4.5 Conclusiones En este apartado, se han desarrollado diferentes métodos multi-clase. Los dos primeros métodos, se basan en realizar varias máquinas de vector soporte de 2 clases y combinarlas para clasificar nuevos datos. El método OVO, crea una máquina de vector soporte para cada combinación de clases, lo que, para el caso de K-clases, precisa de ¡K 2¢máquinas de vector soporte. El método OVA, genera una máquina por cada clase, enfrentando a esta clase con todas las demás. Esto reduce el número de máquinas de vector soporte necesarias. El hecho de utilizar una combinación de varias máquinas de vector soporte, puede ser muy costoso en el caso en el que la muestra sea muy amplia, ya que el número de máquinas de vector soporte necesarias puede ser muy grande. Los otros dos métodos, están planteados para resolver el problema mediante una única máquina de vector soporte. Las principales ventajas que conlleva, son la mejora de la interpretación del método, y el hecho de que es más directa la clasificación de un nuevo elemento. Esto se debe a que a la hora de clasificarlo, solo se debe evaluar una máquina de vector soporte. Sin embargo, presenta el siguiente inconveniente. Un problema de optimización de varias clases, puede provocar cálculos muy costosos. Para solucionar estas dificultades, el método C-S, plantea una división del problema de optimización, en múltiples problemas de optimización más simples, esto rebaja la complejidad de cálculo pero lleva a tener que resolver varios problemas distintos, lo que aumenta la cantidad de cálculos. 5 Experiencia computacional En este capítulo, mostraremos la implementación en Python de algunas SVMs, basadas en algunos de los conjuntos de datos más usados en el ámbito de máquinas de aprendizaje. Dichos datos serán extraídos de [5]. El objetivo consiste en, para cada conjunto de datos, observar la precisión de la SVM construida en función del Kernel utilizado. Para ello, se dividirá el conjunto de datos en dos subconjuntos, uno destinado al entrenamiento de la SVM y otro destinado a la fase test. Una vez construida la SVM, se realizará una predicción de en qué clase debería estar cada observación del subconjunto destinado a la fase test. Por último, observaremos la precisión de la SVM comparando la predicción con los datos reales. Para ello nos fijaremos en el ejemplo que aparece en [6]. 5.1 Conjunto de datos IRIS En primer lugar, trabajamos con el conjunto de datos IRIS. Este conjunto recoge 4 variables: sepal-length, sepal-width, petal.length y petal.width. Además, también recoge el tipo de planta: Iris-setosa, Iris-versicolor, Iris-virginica. El conjunto de datos, recoge las 4 variables y el tipo de planta de 150 observaciones. El objetivo será construir una SVM capaz de predecir el tipo de planta de una nueva observación a partir de las 4 variables. En primer lugar, recogeremos una matriz Xque recoge el valor de cada variable de las 150 observaciones, y un vector Ycon el tipo de planta a la que corresponde cada observación. Se dividirán tanto la matriz Xcomo el vector Yen entrenamiento y test aplicando la siguiente orden: 58 MÁQUINAS DE VECTOR SOPORTE PARA DOS Y MÁS CLASES y otros destinados a buscar la resolución de un único problema de optimización, es decir, construir una SVM multi-clase. Por último, se ha realizado la implementación en Python de las SVMs sobre diversos conjuntos de datos, muy utilizados en el ámbito de máquinas de aprendizaje. Lo cual aporta una idea más clara de la utilidad de las SVM en el ámbito de máquinas de aprendizaje, observando su precisión a la hora de predecir determinados resultados. En definitiva, este trabajo me ha enseñado la manera de tratar problemas de clasificación en dos y más clases, mediante el planteamiento de diversos problemas de optimización vistos a lo largo de mis estudios en el grado. Además he aprendido la implementación en Python, y la forma de trabajar con máquinas de aprendizaje, separando las observaciones en dos subconjuntos, entrenamiento y test, para construir el algoritmo y comprobar su eficacia o rendimiento. Bibliografía [1] Christopher J.C. Burges. “A Tutorial on Support Vector Machines for Pattern Recognition”. En: Data Mining and Knowledge Discovery 2, 121-167 (1998). [2] Bazaara M.S;Sherall Hanif D.;Shetty C.M. Nonlinear Programming. Theory and Algorithms. Wiley Sons John Wiley, 1993. [3] J.Weston; C.Watkins. “Support Vector Machines for Multi-Class Pattern Recognition”. En: European Symposium on Artificial Neural Networks 99 (abr. de 1999), págs. 219-224. [4] Bazaara M.; Jarwis J. Linear Programming and Network. Wiley, 1977. [5] Machine Learning Repository.URL:https://archive.ics.uci.edu/ml/ index.php. [6] Usman Malik. Implementing SVM and Kernel SVM with Python’s Scikit-Learn. URL:https://stackabuse.com/implementingsvm- andkernel- svmwith-pythons-scikit-learn/. [7] John Shawe-Taylor Nello Cristianini. “Implementation Techniques”. En: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, 2013. Cap. 7, págs. 125-144. [8] James G.; Witter D.; Hastie T.; Tibshirani R. “Support Vector Machines”. En: An Introduction to Statistical Learning. Springer, 2013. Cap. 9, págs. 337-356. [9] Crammer K.; Singer Y. “On the Algorithmic Implementation of Multiclass Kernelbased Vector Machines”. En: Journal of Machine Learning Research 2 (ene. de 2001), págs. 265-292.