Tesis Mg - Seleccion de Hiperparametros en Maquinas de Soporte Vectorial. Univ Colombia.2004

8/16/2019 Tesis Mg - Seleccion de Hiperparametros en Maquinas de Soporte Vectorial. Univ Colombia.2004

1/102

SELECCIÓN DE HIPERPARÁMETROS EN MÁQUINAS DE

SOPORTE VECTORIAL

PorRicardo Henao

[email protected]

Director:

Jorge Eduardo Hurtado Gómez

ENVIADO EN PARCIAL CUMPLIMIENTO DE LOS

REQUERIMIENTOS PARA EL GRADO DE

MSC. EN CONTROL Y AUTOMATIZACIÓN INDUSTRIAL

EN LA

UNIVERSIDAD NACIONAL DE COLOMBIA

MANIZALES, COLOMBIA

MAYO 2004

c Derechos Reservados por Ricardo Henao, 2004

mailto:[email protected]:[email protected]


2/102


FACULTAD DE

INGENIEŔIAS ELÉCTRICA, ELECTRÓNICA Y COMPUTACIÓN

Los abajo firmantes certifican haber leido y recomendado a la facultad

de Facultad de Ingenieŕıa y Administración la aceptación de la tesis titulada

“Selección de Hiperparámetros en Máquinas de Soporte Vectorial”

por Ricardo Henao en parcial cumplimiento de lor requerimientos para el

grado de Msc. en Control y Automatización Industrial.

Fecha: Mayo 2004

Director:Jorge Eduardo Hurtado Gómez

Jurados:Germán Castellanos D.

Julio Fernando Suárez

Oscar Ortega L.

II


3/102


Fecha: Mayo 2004

Autor: Ricardo Henao

Tı́tulo: Selección de Hiperparámetros en Máquinas de Soporte

Vectorial

Facultad: Ingenierı́as Eléctrica, Electrónica y ComputaciónGrado: M.Sc. Término: Julio Año: 2004

Con esta se concede permiso a la Universidad Nacional de Colombia de circular

y copiar este trabajo para propósitos no comerciales y a discresión ante solicitud de

individuales o instituciones.

Firma del Autor

EL AUTOR SE RESERVA OTROS DERECHOS DE PUBLICACION Y NILA TESIS NI EXTRACTOS EXTENSOS DE ELLA PUEDEN SER PUBLICADOS OREPRODUCIDOS EN OTRA FORMA SIN LA AUTORIZACION POR ESCRITO DELAUTOR.

EL AUTOR CERTIFICA QUE HA OBTENIDO PERMISO PARA EL USO DECUALQUIER MATERIAL CON DERECHOS RESERVADOS QUE APARECIERE ENLA TESIS (EXCEPTO EXTRACTOS CORTOS QUE UNICAMENTE REQUIEREN UNRECONOCIMIENTO APROPIADO EN EL CASO ESCRITOS ACADEMICOS) Y QUETAL USO ES CLARAMENTE RECONOCIDO.

III


4/102

Índice General

Índice General IV

Índice de Tablas VII

Índice de Figuras VIII

Resumen IX

Abstract X

Agradecimientos XI

1. Introducción 1

1.1. Trabajo Previo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2. Objetivos Principales del Trabajo . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3. Estructura del Documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2. Máquinas de Soporte Vectorial 5

2.1. Clasificacíon con Vectores de Soporte . . . . . . . . . . . . . . . . . . . . . . 5

2.2. Caso Linealmente no Separable . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3. Máquinas de Soporte no Lineales . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4. Capacidad de Generalización . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.1. Riesgo Actual, Riesgo Emṕırico y Dimensión VC . . . . . . . . . . . 11

2.4.2. La Dimensión VC de las SVM . . . . . . . . . . . . . . . . . . . . . 13

IV


5/102

2.4.3. Procedimiento Leave-One-Out . . . . . . . . . . . . . . . . . . . . . 13

2.4.4. Cotas para el Estimador de Leave-One-Out . . . . . . . . . . . . . . 14

2.5. Algoritmo de Entrenamiento . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5.1. Método de Descomposición . . . . . . . . . . . . . . . . . . . . . . . 18

2.5.2. Selección del Conjunto de Trabajo y Criterio de Parada . . . . . . . 19

2.5.3. Convergencia del Método de Descomposición . . . . . . . . . . . . . 22

2.5.4. Solucíon Anaĺıtica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5.5. Cálculo de b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.5.6. Contraccíon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.5.7. Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.5.8. Complejidad Computacional . . . . . . . . . . . . . . . . . . . . . . 29

2.6. Máquinas de Soporte Multi Clase . . . . . . . . . . . . . . . . . . . . . . . . 30

3. Selección de Hiperparámetros en Máquinas de Soporte Vectorial 32

3.1. Búsqueda en Malla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.2. Búsqueda en Ĺınea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.2.1. Cota de Radio/Margen para L2 . . . . . . . . . . . . . . . . . . . . . 35

3.2.2. Cota de Radio/Margen para L1 . . . . . . . . . . . . . . . . . . . . . 36

3.3. Limitaciones Actuales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4. Estrategias Evolutivas 39

4.1. Adaptación Arbitraria de Distribuciones Normales . . . . . . . . . . . . . . 41

4.2. Adaptación de la Matriz de Covarianza . . . . . . . . . . . . . . . . . . . . 43

4.3. Trayectoria Evolutiva: Cumulación . . . . . . . . . . . . . . . . . . . . . . . 45

4.4. El Algoritmo (µW , λ)-CMA-ES . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.5. Valores para los Parámetros Internos . . . . . . . . . . . . . . . . . . . . . . 49

4.6. Limitaciones y Aspectos Prácticos . . . . . . . . . . . . . . . . . . . . . . . 50

5. Método Propuesto 51

5.1. CMA-ES-SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.2. Caracteŕısticas del CMA-ES-SVM . . . . . . . . . . . . . . . . . . . . . . . 54

V


6/102

5.3. Implementación y Aspectos Prácticos . . . . . . . . . . . . . . . . . . . . . . 55

6. Resultados Numéricos 56

6.1. Conjuntos Artificiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6.1.1. Balanceado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.1.2. No Balanceado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.1.3. Damero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.1.4. Dos Curvas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.1.5. Dos Anillos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.1.6. Anillos Cruzados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.2. Conjuntos Estándares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.3. Conjunto Multi Clase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

6.4. Resultados con Kernel Polinomial . . . . . . . . . . . . . . . . . . . . . . . . 68

6.5. Conjuntos de Problemas Reales . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.5.1. Identificación de Voces Patológicas . . . . . . . . . . . . . . . . . . . 69

6.5.2. Clasificación de Arritmias en ECG . . . . . . . . . . . . . . . . . . . 70

7. Discusión Final, Sumario y Trabajo Posterior 73

A. Kernels 76A.1. Kernels Definidos Positivos . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

A.2. Reproducción de un Mapeo con Kernel . . . . . . . . . . . . . . . . . . . . . 77

A.3. Reproducción de un Espacio de Hilbert mediante Kernels . . . . . . . . . . 79

A.4. El Kernel de Mercer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

A.5. Ejemplos y Propiedades de Kernels . . . . . . . . . . . . . . . . . . . . . . . 81

B. Algoritmo BFGS 83

Apéndices 76

VI


7/102

Índice de Tablas

4.1. Parámetros defecto para (µW , λ) . . . . . . . . . . . . . . . . . . . . . . . . 49

6.1. Estructura de los conjuntos artificiales . . . . . . . . . . . . . . . . . . . . . 57

6.2. Resultados para el conjunto balanceado . . . . . . . . . . . . . . . . . . . . 58

6.3. Resultados para el conjunto no balanceado . . . . . . . . . . . . . . . . . . 59

6.4. Resultados para el conjunto damero . . . . . . . . . . . . . . . . . . . . . . 61

6.5. Resultados para el conjunto dos curvas . . . . . . . . . . . . . . . . . . . . . 61

6.6. Resultados para el conjunto dos anillos . . . . . . . . . . . . . . . . . . . . . 63

6.7. Resultados para el conjunto anillos cruzados . . . . . . . . . . . . . . . . . . 63

6.8. Estructura de los conjuntos estándares . . . . . . . . . . . . . . . . . . . . . 65

6.9. Resultados para los conjuntos estándar . . . . . . . . . . . . . . . . . . . . . 66

6.10. Resultados para los conjuntos estándar. (Continuación) . . . . . . . . . . . 67

6.11. Estructura de los conjuntos multi clase . . . . . . . . . . . . . . . . . . . . . 68

6.12. Resultados para conjuntos multi clase . . . . . . . . . . . . . . . . . . . . . 68

6.13. Resultados para kernel polinomial . . . . . . . . . . . . . . . . . . . . . . . 69

6.14. Estructura del conjunto para identificación de voces patológicas . . . . . . . 70

6.15. Resultados para identificación de voces patológicas . . . . . . . . . . . . . . 71

6.16. Estructura del conjunto para clasificación de arritmias en ECG . . . . . . . 72

6.17. Resultados para clasificación de arritmias en ECG . . . . . . . . . . . . . . 72

VII


8/102

Índice de Figuras

2.1. Hiperplanos que separan correctamente los datos . . . . . . . . . . . . . . . 7

2.2. Mapeo del espacio de entrada en otro de dimensión alta . . . . . . . . . . . 102.3. Solución anaĺıtica de un problema de optimización de dos variables . . . . . 24

4.1. Ĺıneas de igual densidad de probabilidad en dos distribuciones normales . . 40

6.1. Izquierda: Conjunto balanceado. Derecha: Conjunto no balanceado . . . . . 57

6.2. Izquierda: Conjunto damero. Derecha: Conjunto dos curvas . . . . . . . . . 60

6.3. Izquierda: Conjunto dos anillos. Derecha: Conjunto anillos cruzados . . . . 62

A.1. Problema de clasificación mapeado con kernel polinomial . . . . . . . . . . . 76

VIII


9/102

Resumen

Este trabajo de tesis presenta un nuevo método de selección automática de hiperparámetros

en maquinas de soporte vectorial utilizando estrategias evolutivas y cotas efectivas del error

de validación o riesgo emṕırico. El desarrollo descrito en esta tesis involucra una técnica

de estrategias evolutivas denominada adaptación de matriz de covarianza, que a grandes

rasgos reduce el tiempo de convergencia en la medida que un menor número de evaluaciones

de la función objetivo son necesarias y que desaleatoriza al máximo el procedimiento para

obtener soluciones más estables. En particular, dos cotas del error de validación fueron

empleadas, la validación cruzada como generalización del esquema LOO y el span como

medida efectiva tanto teórica como práctica ya que no necesita múltiples evaluaciones de

la SVM, es continua, posee conexión directa con otras como Radio/Margen y requiere una

carga computacional considerablemente pequeña. Además, permite la posibilidad de em-

plear diferentes funciones kernel debido a que no exige diferenciabilidad en dicha funci ón,

esquemas multi clase y selección de múltiples parámetros sin tener que reformular substan-

cialmente todo el algoritmo. Por último, los resultados numéricos muestran un desempeño

bastante competitivo con las otras técnicas revisadas en este trabajo.

IX


10/102

Abstract

This thesis work introduces a new method for automatic hiperparameter selection for

support vector machines using evolutive strategies and validation error or empirical risk

bounds. The actual approach involves an evolution strategy technique designated as covari-

ance matrix adaptation, which in general terms reduces the convergence rates and obtain

steady solutions due to its derandomized nature. In particular, two empirical risk bounds

where used, crossvalidation as generalized LOO scheme and span bound because do not

require multiple SVM evaluations, is continuous, and hold direct connection with some

others like Radius/Margin and its computational cost is low as well. Besides, this method

allows a wide variety of kernel functions since do not demand differentiability, multi-class

schemes and multiple parameter selection without substantial reformulation of the entire

algorithm. Finally, the numerical results reveal a competitive performance related to an-

other considered methods within this work.

X


11/102

Agradecimientos

El autor quiere agradecer al Profesor Jorge Eduardo Hurtado supervisor de esta tesis, por

sus múltiples sugerencias y apoyo constante no solo durante el tiempo que duró este trabajo

sino desde que estoy trabajando con él. Tambíen, al Profesor Germán Castellanos por todo

el apoyo prestado desde que estoy trabajando en investigaci ón.

Además, a los profesores S.S. Keerthi, C.J. Lin y N. Hansen por toda la ayuda prestada a

través de correos electrónicos.

Finalmente, Fabian Ojeda y Juan Carlos Riaño por la ayuda prestada con la revisión de

este trabajo y comentarios pertinentes, al grupo de Control y Procesamiento Digital de

Señales por proporcionar un espacio apropiado para el trabajo de investigación, incluso

más allá del alcance de este trabajo. Los demás supongo saben quienes son.

Esta investigaci´ on fue realizada en el marco de la investigaci´ on “An´ alisis y procesamiento

digital de im´ agenes médicas y se˜ nales bioeléctricas” realizada por la Universidad Nacional

de Colombia sede Manizales mediante la orden contractual 472 de 2003 emitida por el

DIMA.

Manizales, Colombia Ricardo HenaoJulio 22, 2004

XI


12/102

Caṕıtulo 1

Introducción

“I shall certainly admit a system as empirical or scientific only if it is capable of being tested by

experience. These considerations suggest that not the verifiability but the falsifiability of a system is

to be taken as a criterion of demarcation. It must be possible for an empirical scientific system to

be refuted by experience.”

K. Popper. The Logic of Scientific Discovery (1934, ch. 1, sect. 6)

En el área de reconocimiento de patrones y más espećıficamente en la parte de clasificación, las

máquinas de soporte vectorial (SVM), se han convertido en los últimos años en una de las técnicas

más importantes sobre otras muy populares como: k−ésimo vecino cercano (KNN), redes neu-ronales artificiales (ANN) y árboles de clasificación (CART); dado que su aparato matemático está

fundamentado sobre bases muy sólidas [ver Vapnik, 1995] que hacen que posea múltiples ventajas

sobre las otras técnicas mencionadas [ver Vapnik, 1998, Schölkopf and Smola, 2002]. Sinembargo,

Lin [2003] presenta en perspectiva la posibilidad de hacer que las máquinas de soporte vectorial

se conviertan en el principal método de clasificación (según “KDNuggets 2002 Poll 1

”, las redesneuronales y los árboles de clasificación permanecen como principales herramientas) argumentando

que el problema de las SVM es el mal empleo que se les da probablemente por falta de conocimiento

1http:://www.kdnuggets.com, A Site for Data Mining, Knowledge Discovery, Genomic Mining, WebMining.

1


13/102

2

de la metodoloǵıa. Lo que usualmente los usuarios desprevenidos están haciendo es (ver blackboard

http://www.kernel-machines.org): convertir la información a clasificar al formato de algún progra-

ma SVM disponible sin tener en cuenta en la mayoŕıa de los casos las implicaciones del formato,

escalamiento, etc, para luego tratar aleatoriamente con valores de parámetros y kernels indiscrimi-

nadamente sin hacer validaci´ on y sin saber de antemano que los parámetros por defecto en dichos

programas son sorprendentemente importantes y el hecho es que muchos de los usuarios obtienen

como resultado valores de error y generalización insatisfactorias.

Lo mı́nimo que se espera que haga el usuario según Lin [2003] es escalar los datos para validación

y entrenamiento, considerar el kernel RBF (Radial Basis Function) y encontrar valores adecuados

para C y σ2 (o γ ). Ahora, esto de encontrar “valores adecuados” a veces no es tarea f ácil, sin

mencionar que lo que se pretende no es encontrar valores adecuados sino los mejores valores paraun caso dado. Hasta el momento, las técnicas de selección de parámetros o selección del modelo

como también es llamado son las siguientes: búsqueda manual intuitiva, cotas para LOO (leave one

out) o para riesgo emṕırico, búsqueda en dos sentidos y búsqueda en malla.

1.1. Trabajo Previo

En el tema de selección de hiperparámetros en SVM no se ha hecho mucho hasta el momento debido

a que es un tema relativamente nuevo, sinembargo el trabajo realizado es bastante significativo. En

el trabajo con reconocimiento de patrones y m ás espećıficamente en el área de clasificadores es

necesario encontrar medidas que sean proporcionales al error de clasificación (función de riesgo y

dimensión VC), es decir, que sean referentes al momento de seleccionar los parámetros en la SVM

sin tener que realizar un proceso de validación, que dependiendo del volumen de los datos puede

ser prohibitivo en términos de tiempo y recursos computacionales. [Wahba et al., 2000] establece

mediante demostraciones matemáticas y pruebas numéricas la consistencia de la validación cruzada

(en particular LOO) como medida del error en SVM con relación a medidas de margen en el

hiperespacio de SVM. Joachims [2000] realiza pruebas con SVM utilizando como medidas del error:

error de entrenamiento, “hold-out testing”, Boostrap, Jack-knife y validación cruzada en contraste a

una técnica introducida por el llamada estimador ξ α basada en la solución de los α en el problema

dual de SVM y las pérdidas del entrenamiento ξ , obteniendo mejores resultados que validación

cruzada y Boostrap en varias bases de datos estándar. Vapnik and Chapelle [2000] introduce el

concepto de span de los vectores de soporte como forma de obtener parámetros óptimos en SVM


14/102

3

por este ser una medida bastante precisa de el error de validación. Jaakkola and Haussler [1999]

realiza pruebas matemáticas para llegar a una formulación que genera una cota superior para

LOO analizando la solución de la función de costo de SVM. Opper and Winther [2000] utilizan un

método inspirado en la teoŕıa de respuesta lineal y prueban que bajo el supuesto de que los vectores

de soporte no cambian cuando se remueve un ejemplo bajo el esquema de LOO se puede obtener

una matriz de productos punto entre los vectores de soporte que deriva en una cota superior para

la estimación del error. Vapnik [1998] propone bajo el supuesto que la solución de SVM no presenta

errores de entrenamiento, una cota para el error de validación basada en LOO que es la relación entre

el margen y el radio de los vectores de soporte de la máquina entrenada. Keerthi and Ong [2000]

hace un análisis del aporte del valor del corrimiento en la formulación de SVM en la optimalidad del

entrenamiento. Sundararajan and Keerthi [2001] deriva resultados de la probabilidad surrogativa

de Geisser (GPP), error predictivo de Geisser (GPE) y error de validaci ón cruzada para escoger los

parámetros del kernel en el caso RBF. Lee and Lin [2001] propone un método de selección automática

basada en LOO y una reducción simple del espacio de búsqueda de los hiperparámetros utilizando

una descomposición matricial del problema dual de SVM (BSVM). Chapelle et al. [2002] propone

una metodoloǵıa fundamentada en la diferenciabilidad del kernel, el criterio de Radio/Margen y

su dependencia con la solución del problema de optimización de SVM para derivar un esquema

de gradiente descendiente para obtener hiperparámetros óptimos. Keerthi and Lin [2003] hacen un

análisis del comportamiento asintótico de los parámetros de SVM con kernel gaussiano y derivan

un procedimiento heuŕıstico para encontrarlos y obtener un error de generalización bajo. Keerthi

[2002] presenta una implementación del método de Chapelle et al. [2002] utilizando kernel RBF,NPA (algoritmo de punto cercano) como algoritmo de optimización iterativo para SVM, SMO

(optimización secuencial mı́nima) para resolver el problema de Radio/Margen y quasi-Newton como

procedimiento de gradiente descendiente. Chung et al. [2003] utiliza la cota Radio/Margen con kernel

gaussiano para hacer una modificación en el esquema de SVM y derivar a partir de L1-SVM y L2-

SVM un método de selección automática de parámetros. Duan et al. [2003] hace una evaluación

empı́rica del desempeño de varias medidas para selección de hiperparámetros, entre ellos: error de

validación (como referente), validación cruzada, cota χi − alpha, cota VC (Vapnik-Chervonekis),Span aproximado y D2 w2, utilizando bases de datos estándar en reconocimiento de patrones.


15/102

4

1.2. Objetivos Principales del Trabajo

Las publicaciones reportadas hasta la fecha presentan un marcado interés por encontrar cotas del

riesgo empı́rico de manera que no sea necesario llevar a cabo una validación para evaluar la solución

obtenida por una SVM para un problema dado. En la medida en que ha sido posible se han

desarrollado métodos de selección automática de hiperparámetros haciendo uso de dichas cotas y

métodos de optimización. Con esto, no es parte de esta tesis realizar un trabajo de investigación

acerca de las cotas, ni de la forma o caracteŕısticas del espacio de los hiperparámetros o relaciones

entre ellos. Teniendo en cuenta las consideraciones anteriores, los objetivos de este trabajo son:

Profundizar en las técnicas actuales basándose en la teorı́a de SVM con el fin de desarrollar

un algoritmo de selección automática de hiperparámetros en SVM con miras obtener un buen

desempeño de los clasificadores en cuanto a error de validación y costo computacional.

Analizar las técnicas actuales de selección de parámetros para identificar sus ventajas y

desventajas, como base del trabajo a realizar. Investigar acerca de métodos de optimización,

búsqueda y parámetros efectivos en SVM para luego desarrollar un algoritmo de selecci ón

de hiperparámetros automática que ofrezca ventajas sobre las otras desarrolladas hasta el

momento.

Para finalizar, se debe decir que en cuanto a los experimentos numéricos realizados, las compara-

ciones con otras técnicas han de realizarse de acuerdo a las posibilidades y el criterio del autor.

1.3. Estructura del Documento

Partiendo del hecho que se considera primordial que este documento sea lo más compacto y completo

posible, en los caṕıtulos 2 y 4 se presentan respectivamente, los fundamentos teóricos y considera-

ciones prácticas de las SVM y la clase de estrategias evolutivas empleadas en este trabajo. En el

capı́tulo 3 se describen los métodos de selección automática como componentes del marco com-

parativo usado para los experimentos en el caṕıtulo 6. En el caṕıtulo 5 se describe y se hacenlas consideraciones pertinentes con respecto al algoritmo propuesto. El documento termina con

un sumario de los resultados obtenidos e ideas para un trabajo posterior, además de un apéndice

concerniente a kernels como complemento a los fundamentos teóricos de las SVM.


16/102

Caṕıtulo 2

Máquinas de Soporte Vectorial

Las Máquinas de Soporte Vectorial (SVM), han mostrado en los últimos años su capacidad en la

clasificación y reconocimiento de patrones en general. El objetivo de este capı́tulo es presentar los

fundamentos básicos, tanto teóricos como prácticos de las SVM y soportar su potencial en tareas

de clasificación. Intuitivamente, dado un grupo de datos distribuidos en dos clases, una SVM lineal

busca un hiperplano de tal manera que la mayor cantidad de puntos de la misma clase queden

al mismo lado, mientras se maximiza la distancia de dichas clases al hiperplano. De acuerdo a

Vapnik [1995], este hiperplano minimiza el riesgo de clasificaciones erróneas en el grupo tomadopara realizar el proceso de validación.

2.1. Clasificación con Vectores de Soporte

Para un grupo de entrenamiento de tamaño N compuesto de pares atributo-etiqueta (xi, yi)1≤i≤N ,

siendo xi ∈ Rn y yi ∈ {−1, 1}, se desea obtener una ecuación para un hiperplano que divida dichogrupo de entrenamiento, de manera que aquellos puntos con igual etiqueta queden al mismo lado

del hiperplano. Esto significa encontrar un w y un b tal que

yi(wxi + b) > 0, i = 1,...,N (2.1)

5


17/102

6

Si existe un hiperplano que satisfaga (2.1), se dice que los datos son linealmente separables . En este

caso, w y b se pueden escalar aśı,

ḿın1≤i≤N

yi(wxi + b) ≥ 1

de tal manera, que el punto mas cercano al hiperplano tenga como distancia 1/w. Luego (2.1) sepuede escribir como

yi(wxi + b) ≥ 1 (2.2)

aśı, entre todos los posibles hiperplanos, aquel cuya distancia al punto más cercano es máxima se

denomina el “óptimo hiperplano de separación” (OSH). Mientras la distancia al hiperplano óptimo

sea 1/w, encontrar el OSH equivale a resolver el siguiente problema

ḿınw,b

1

2ww

sujeto a yi(wxi + b) ≥ 1, ∀i

(2.3)

La cantidad 2/w es llamada “margen” y el hiperplano que maximiza dicho margen, OSH. Elmargen puede ser visto como una medida de la dificultad del problema, ası́, entre más pequeño sea

el margen más difı́cil es el problema; o de otro modo, se espera una mejor capacidad de generalización

si el margen es más grande (ver figura 2.1).

Mientras ww sea convexo, minimizar la ecuación (2.3) sujeto a (2.2) es posible utilizando multipli-

cadores de Lagrange [Burges, 1998]. Sean α = {α1,...,αN } los N multiplicadores de Lagrange nonegativos asociados a (2.2), para minimizar (2.3) se debe encontrar el punto de silla de la siguiente

función de Lagrange

L(w,b,α) = 1

2

ww−

N

i=1 αi[yi(wxi + b) − 1] (2.4)Para encontrar dicho punto, hay que minimizar la función (2.4) sobre w y b, y luego maximizarla

sobre los multiplicadores de Lagrange αi ≥ 0. El punto de silla debe satisfacer las condiciones de


18/102

7

Figura 2.1: Hiperplanos que separan correctamente los datos. El OSH de la derecha tieneun margen mayor por lo tanto se espera una mejor generalizaci ón

Karush-Kuhn-Tucker (KKT) [Burges, 1998],

∂L(w,b,α)

b =

N i=1

yiαi = 0

∂L(w,b,α)

w = w −

N i=1

αiyixi = 0

(2.5)

Substituyendo (2.5) en (2.4) el problema de optimización apunta ahora a resolver

máx

N i

αi − 12

N i,j

αiαj yiyj xixj

sujeto aN

i=1

yiαi = 0 y αi ≥ 0, ∀i(2.6)

Esto puede ser logrado utilizando métodos de programación cuadrática estándar [Burges, 1998].

Una vez el vector α0 = {α0i ,...,α0N } solución de (2.6) ha sido encontrado, a partir de (2.5), el OSH(w, b) tiene la siguiente forma

w0 =N

i=1

α0i yixi (2.7)


19/102

8

mientras b0 puede ser obtenido a partir de las condiciones de KKT

α0i [yi(wxi + b) − 1] = 0 (2.8)

Nótese que de la ecuación (2.8), los puntos para los cuales α0i > 0, satisfacen la desigualdad en

(2.2). Geométricamente, esto significa que aquellos puntos son los más cercanos al OSH (ver figura

2.1). Estos puntos juegan un papel importante debido a que son los únicos valores necesarios en la

expresión para el OSH (ver ecuación 2.7) y son llamados “vectores de soporte” (SV), por el hecho

que dan “soporte” a la expansíon de w0.

Dado un vector de soporte xi, el parámetro b puede ser obtenido de las condiciones KKT como

b0 = yi − w0xi

El problema de clasificar un nuevo punto x, es resuelto examinando el signo de w0x + b0. Ahora,

considerando la expansión (2.7) de w0, la función de decisión f (x) para el hiperplano puede ser

escrita como

f (x) = sign

N

i=1α0i yix

ix + b

2.2. Caso Linealmente no Separable

Si los datos son linealmente no separables, buscar un OSH carece completamente de sentido. Con

la finalidad de posibilitar las violaciones, se pueden introducir variables “slack” (de relajación)

(ξ 1,...,ξ N ), para ξ i ≥ 0 [Cortes and Vapnik], de manera que la expresión (2.2) se puede escribircomo

yi(wxi + b) ≥ 1 + ξ i, ∀i

El propósito de las variables ξ i es permitir puntos erróneamente clasificados, los cuales correspondan

a ξ i > 1, por lo tanto,

i ξ es una cota superior del número de errores de entrenamiento. El OSH


20/102

9

generalizado puede ser obtenido como la solución del siguiente problema

ḿınw,b

1

2ww + C

N i=1

ξ i

sujeto a yi(wxi + b) ≥ 1 + ξ i y ξ ≥ 0, ∀i

(2.9)

El primer término es minimizado para controlar la capacidad de aprendizaje del mismo modo que

en el caso separable; el segundo término permite mantener bajo control el número de clasificaciones

erróneas. El parámetro C es elegido por el usuario de manera que un valor grande es equivalente

a asignar una alta penalización a los errores. En analoǵıa con el caso separable, la utilización de

multiplicadores de Lagrange deriva en el siguiente problema de optimización,

máxN i

αi − 12

N i,j=0

αiαj yiyj xixj

sujeto a

i

yiαi = 0 y 0 ≥ αi ≥ C, ∀i(2.10)

de la ecuación (2.10) se puede notar que la única diferencia hasta el momento con el caso separable

es que ahora α tiene una cota superior C .

2.3. Máquinas de Soporte no Lineales

El principio de SVM no lineal consiste en mapear el espacio de entrada a un espacio de representación

de dimensión alta a través de una función no lineal elegida a priori [Boser et al., 1992], ver figura

2.2.

Sinembargo en este caso, surge un problema computacional, la dimensión del espacio de repre-

sentación puede ser muy alta y la dificultad radica en cómo construir un hiperplano de separación

en este espacio. La respuesta al problema parte de que para construir dicho hiperplano, el mapeo

z = φ(x) no necesita ser expĺıcito, de manera que reemplazando x por φ(x) en (2.6) se tiene


21/102

10

Figura 2.2: La SVM mapea el espacio de entrada en otro de representación de dimensiónalta y luego construye un OSH sobre este último

máxN i

αi − 12

N i,j

αiαj yiyj φ(xi)φ(xj )

sujeto a

N i=1

yiαi = 0 y αi ≥ 0, ∀i

de lo anterior, el algoritmo de entrenamiento solo depende de los datos a través de los productos

punto en el espacio de representación, esto es, funciones de la forma φ(xi)φ(xj ). Sea dada una fun-

ción kernel simétrica K tal que K (xi, xj) = φ(xi)φ(xj ), de modo que el algoritmo de entrenamiento

dependa solo de K y el mapeo φ no sea usado expĺıcitamente.

Dado φ : Rd → H, el kernel K es K (xi, xj ) = φ(xi)φ(xj ), pero de manera inversa, dado un kernelK se deben establecer las condiciones para que el mapeo exista. Tales condiciones son aseguradas

por las condiciones de Mercer (ver apéndice A):

Teorema 1 Sea K (x, y) una funci´ on simétrica continua en L2(C ), luego, existe un mapeo φ y una

expansi´ on, tal que

K (x, y) =∞

i=1

φ(x)iφ(y)i (2.11)


22/102

11

si y solo si, para alg´ un g ∈ L2(C ), tal que

C ×C

K (x, y)g(x)g(y)dxdy ≥ 0 (2.12)

Nótese que para casos espećıficos, puede no ser fácil mostrar cuando las condiciones de Mercer son

cumplidas, mientras que (2.12) debe mantenerse para algún g ∈ L2(C ). Sin embargo, es fácil probarque la condición se cumple para el kernel polinomial K (x, y) = (xy) p [ver Burges, 1998].

Los primeros kernels investigados para reconocimiento de patrones fueron los siguientes

Polinomial: K (x, y) = (xy + c)d para c > 0

Función de base radial (RBF): K (x, y) = exp(−γ x − y2) para γ > 0

Sigmoide: tanh(κxy + ν )

El primero resulta en un clasificador con función de decisión polinomial, el segundo un clasificador

con función de base radial y el último un tipo particular de red sigmoidal de dos capas. Para el caso

de RBF, el número de centros (número de SV), los centros (SV), los pesos (αi) y el desplazamiento

(b) son generados automáticamente por la SVM en la etapa de entrenamiento y dan excelentes

resultados en comparación a la red RBF clásica [Schölkopf et al., 1996]. De la misma forma, para el

caso del perceptrón multicapa (MLP), la arquitectura (número de nodos ocultos) es determinada

por el entrenamiento de la SVM.

2.4. Capacidad de Generalización

En esta sección, se dan algunas bases teóricas que describen la capacidad de generalización de las

SVM.

2.4.1. Riesgo Actual, Riesgo Emṕırico y Dimensión VC

Suponiendo que se tienen N observaciones (xi, yi)1≤i≤N para xi ∈ Rn y yi ∈ {−1, 1} donde yi esla etiqueta para xi, se asume existe una probabilidad P (x, y) para la cual los datos están descritos.

Sea dada una máquina cuya tarea es aprender a mapear xi → yi, dicha máquina es ciertamente


23/102

12

definida como un grupo de posibles mapeos x → f (x, α) donde las funciones f (x, α) son descritaspor los parámetros ajustables α. Una elección particular de α, genera una “máquina entrenada” en

particular. Esto es, por ejemplo, una red neuronal con una arquitectura fija, donde α corresponde

a los pesos y los desplazamientos, es en efecto una m áquina de aprendizaje.

La esperanza del error de validación, para una máquina entrenada es por consiguiente [Vapnik,

1995]:

R(α) =

1

2|y − f (x, α)|dP (x, y)

La cantidad R(α) es llamada riesgo esperado o simplemente “riesgo”. Se llamará aquı́ riesgo actual

para enfatizar que es la cantidad en la que finalmente se est á interesado. El “riesgo emṕırico”,

Remp(x) está definido como la medida de error en un grupo dado de validaci ón:

Remp(α) = 1

2N

N i=1

|yi − f (x, α)|

La cantidad Q((xi, yi), α) = 12 |yi − f (x, α)| es llamada “pérdida”. Para el caso descrito aqúı, solo

toma valores entre 0 y 1. Si se escoge un η , de manera que 0 ≤ η ≤ 1, luego, con una probabilidadde al menos 1 − η, la siguiente cota se mantiene [Vapnik, 1995]

R(α) ≤ Remp(α) +

h(log(2N/h) + 1) − log(η/4)N

donde h es un entero no negativo llamado dimensión de Vapnik-Chervonenkis (VC) y es la medida

de la capacidad de la máquina de aprendizaje. El segundo término de la desigualdad es llamado

“confidencia VC”, el cual es tan pequeño como la dimensión VC, por lo tanto una forma de controlar

la capacidad de generalización de una máquina es manipular la dimensión VC.

Sea definido un grupo de funciones {f (α)}, tal que para un grupo dado de N puntos, se puedanetiquetar de todas las posibles 2N formas, y para cada etiqueta, un miembro del grupo {f (α)} puedaencontrar la manera de asignar dichas etiquetas. Se dice que este grupo de puntos es fragmentado

por el grupo de funciones. La dimensión VC para el grupo de funciones {f (α)} está definido comoel número máximo de puntos de entrenamiento que pueden ser fragmentados por {f (α)}.


24/102

13

2.4.2. La Dimensión VC de las SVM

Primero, se presenta un teorema que establece una cota de la dimensión VC para hiperplanos de

separación

Teorema 2 Sea X ⊂ Rn un conjunto de vectores, ∀x ⊂ X , x2 < R. Un subconjunto S de hiperplanos, tales que ∀(w, b) ⊂ S ,

inf x⊂X

|wx + b| = 1

|w| ≤ A

tiene una dimensi´ on VC acotada por

V C dim < ḿın(R2A2, n) + 1

De manera que minimizando ww, tambíen la cota de la dimensión VC para los hiperplanos de

separación y, por lo tanto una mejor generalización esperada. Nótese que en el caso de SVM no lineal,

este teorema debe ser aplicado sobre el espacio de representación, aśı, la capacidad de generalización

está bajo control, incluso si el espacio es infinito dimensional.

2.4.3. Procedimiento Leave-One-Out

Una manera de predecir el desempeño de generalización de una SVM es estimar la dimensi ón VC

calculando el término R2ww. Otra manera es utilizar un estimador Leave-one-Out (LOO) [Vapnik,

1998]. Dada una muestra de N + 1 ejemplos de entrenamiento, el procedimiento para LOO consiste

en seguir los siguientes pasos (∀i):

Remover el ejemplo xi del grupo de entrenamiento

Entrenar la máquina con el nuevo grupo de entrenamiento a fin de obtener los αi

Probar si xi es correctamente clasificado

El número de errores cometidos por la máquina en el procedimiento LOO está denotado por LN +1.Por definición


25/102

14

LN +1 =

N +1

n=1 Q((xi, yi), α)La cantidad

LN +1N +1 , es la estimación del error de generalización. Gracias a esto el siguiente teorema

es válido

Teorema 3 (Luntz y Brailovsky, 1969) El estimador LOO es no sesgado, esto es

E

LN +1N + 1

= E (RN )

La esperanza del término del lado izquierdo es tomada del grupo de entrenamiento de tamañoN + 1 y E (RN ) es la esperanza del riesgo actual para OSH construidos sobre la base de un grupo

de entrenamiento de tamaño N . Entonces, para controlar la capacidad de generalización se debe

tratar de minimizar el número de errores cometidos en el procedimiento LOO.

Nota 1 Para SVM, el procedimiento LOO se debe realizar solo en los vectores de soporte, los no

vectores de soporte ser´ an reconocidos correctamente debido a que un no vector de soporte no afecta

la funci´ on de decisi´ on.

2.4.4. Cotas para el Estimador de Leave-One-Out

Se muestran aqúı, diferentes cotas para el estimador LOO en SVM.

Número de SV

Debido al hecho presentado en la nota 1, se puede restringir la sumatoria solo a los vectores de

soporte y luego acotar superiormente cada término en la suma por 1, de lo cual se obtiene la

siguiente cota del número de errores cometidos por el procedimiento LOO [Vapnik, 1995]

T = N SV

N

de donde N SV es el número de vectores de soporte.


26/102

15

Jaakkola-Haussler

Para SVM sin valor de desplazamiento, analizando el proceso de optimizaci ón del algoritmo de SVM

cuando se calcula el error LOO, Jaakkola and Haussler [1999] provee la siguiente desigualdad

y p(f 0(x p) − f p(x p)) ≤ α0 pK (x p, x p) = U p

de la cual se extrae la siguiente cota

T = 1

N

N

p=1 Ψ(α0 pK (x p, x p)

−1)

En [Wahba et al., 2000] se propone una estimación de los errores producidos bajo el esquema LOO,

para el cual en el caso de SVM con margen ŕıgido (C = ∞) se vuelve

T = 1

N

α0 pK (x p, x p)

lo cual se puede ver como una cota superior de Jaakkola-Haussler siempre y cuando Ψ(x − 1) ≤ xpara x ≥ 0.

Opper-Winther

En el caso de SVM con margen rı́gido sin desplazamiento, Opper and Winther [2000] utiliza un

método basado en la teorı́a de respuesta lineal para probar que ba jo el supuesto que un grupo de

vectores de soporte no cambia cuando se remueve un ejemplo p, se tiene

y p(f 0(x p) − f p(x p)) =

α0 p

(K −1SV ) pp

donde K SV es la matriz de productos internos entre los vectores de soporte y que lleva a la siguiente

estimación


27/102

16

T = 1

N

N

p=1 Ψ(α0 p

(K −1SV ) pp −1)

Radio-Margen

Sea que el margen óptimo es igual a M y que las imágenes φ(xi) de los vectores de entrenamiento

xi, están contenidas en una esfera de radio R. Entonces, el siguiente teorema se mantiene [Vapnik

and Chapelle, 2000]

Teorema 4 Dado un conjunto de entrenamiento Z = {(x1, y1), ..., (xN , yN )}, un espacio de repre-sentaci´ on en

H y un hiperplano (w, b), el margen M (w,b,Z ) y el radio R(Z ) son definidos como

M (w,b,Z ) = mı́n(xi,yi)∈Z

yi(wφ(xi) + b)w

R((Z )) = mı́na,xi

φ(xi) + a

El algoritmo de margen m´ aximo, LN : (X × Y )N → H × R toma como entrada el conjunto de entrenamiento de longitud N y devuelve un hiperplano en el espacio de representaci´ on, tal que

el margen es maximizado. N´ otese que asumiendo que dicho grupo de entrenamiento es separable,

entonces M (w,b,Z ) > 0. Bajo este supuesto, para todas las medidas de probabilidad P (Z ), la

probabilidad esperada de clasificaci´ on err´ onea es

perr(w, b) = P (sign(wφ(X ) + b) = Y )

con la cota

E { perr(LN −1(Z ))} ≤ 1N

E

R2(Z )

M 2(L(Z ), Z )

(2.13)

donde la esperanza es tomada sobre un subconjunto aleatorio de Z de longitud N − 1 para el ladoizquierdo y N para el derecho en ( 2.13 ).

Este teorema se ajusta a la idea de construcción de un hiperplano que separe los datos con un margen

grande (entre más grande sea dicho margen, mejor sera el desempeño del hiperplano construido).


28/102

17

De acuerdo al teorema 4, el desempeño promedio depende de E

R2

M 2

y no simplemente de cuan

grande sea el margen M .

Para SVM sin desplazamiento y sin errores de entrenamiento, Vapnik [1998] propone la siguiente

cota superior para el número de errores cometidos por LOO

T = 1

N

R2

M 2(2.14)

donde R y M son respectivamente el radio y el margen definidos en el teorema 4.

Span de los Vectores de Soporte

Vapnik and Chapelle [2000] derivaron otra estimación utilizando el concepto del span de los vectores

de soporte. Bajo el supuesto de que los SV permanecen intactos durante el procedimiento de LOO,

la siguiente igualdad es cierta

y p(f 0(x p) − f p(x p)) = α0 pS 2 p

donde S p es la distancia entre el punto φ(xi) y la colección Λ p, y a su vez,

Λ p =

i= p , α0i>0

λiφ(xi) ,i= p

λ = 1

de lo que se obtiene, el número exacto de errores cometidos por LOO bajo el supuesto previo. Ası́,

la cota para LOO se define como sigue

T = 1

N

N

p=1Ψ(α0 pS

2 p − 1) (2.15)

Además, la estimación del span puede ser relacionada con las otras mencionadas con formulaciones

simples [Chapelle et al., 2002].


29/102

18

2.5. Algoritmo de Entrenamiento

Considerando la fórmula general para la SVM, es decir, no lineal y no separable:

máx

N i

αi − 12

N i,j

αiαj yiyj K (xi, xj )

sujeto aN

i=1

yiαi = 0 y 0 ≤ αi ≤ C, ∀i(2.16)

el método de descomposición es tenido en cuenta considerando la densidad de la matriz kernel

K (xi, xj ) de la ecuación (2.11). Buena parte del trabajo al rededor de este método puede ser

encontrado en [Osuna et al., 1997, Joachims, 1999, Platt, 1999, Saunders et al., 1998].

2.5.1. Método de Descomposición

Partiendo de la ecuación (2.16) se puede realizar la siguiente representación vectorial:

ḿınα

1

2αQα − eα

sujeto a y α = 0 y 0≤

αi ≤

C,

∀i

(2.17)

donde Qij = yiyj K (xi, xj ) y e = 1, ∀i.

Algoritmo 1

Dado un n´ umero q < N , como tama˜ no del conjunto de trabajo, se encuentra α1 soluci´ on

inicial y se hace k = 1

Si αk es la soluci´ on ´ optima de la ecuaci´ on ( 2.17 ) se termina, de otro modo se busca un con-

junto B ⊂ {1,...,N } con tama˜ no q . Se definen L ≡ {1,...,N }\B, αkB y αkL como subvectores

de αk

correspondientes a B y a L respectivamente


30/102

19

Se resuelve el siguiente problema respecto de αB:

ḿınαB

12

αBQBB αB − (eB + QBLαkL)αB

sujeto a yBαB = −yLαkL y 0 ≤ (αB)i ≤ C, ∀i(2.18)

donde

QBB QBL

QLB QLL

es una permutaci´ on de la matriz Q

Se deja αk+1B como soluci´ on ´ optima de ( 2.18 ) y αk+1L ≡ αkL. Se hace k = k + 1 y se vuelve al

paso 2

La idea básica del algoritmo de descomposición es que en cada iteración los ı́ndices

{1,...,N

} del

conjunto de entrenamiento, sean separados en dos más pequeños B y L, donde B es el de trabajo. El

vector αL es fijado de manera que el objetivo sea 12α

BQBB αB − (eB − QBLαL)αB + 12αLQLLαL −

eLαL. Luego, se resuelve un subproblema respecto de αB , B es actualizado en cada iteración (nótese

que para simplificar la notación se utiliza B en vez de B k) y el decrecimiento estricto de la función

objetivo se sostiene (ver sección 2.5.3 referente a la convergencia teórica del algoritmo).

2.5.2. Selección del Conjunto de Trabajo y Criterio de Parada

Una de las partes importantes en el algoritmo de descomposición es la selección del grupo de trabajo

B. La condición de Karush-Kuhn Tucker (KKT) en la ecuación (2.17) muestra que existe un escalar

y dos vectores no negativos λ y µ, tales que

Qα + e + by = λ − µλiαi = 0, µi(C − α)i = 0

λi ≥ 0, µi ≥ 0, ∀i(2.19)

Nótese que si se escriben las condiciones de KKT para el primario y el dual, resultan ser las mismas y

el multiplicador de Lagrange de la restricción lineal y α = 0 coincide con el valor de desplazamientob en la función de decisión. Luego, la ecuación (2.19) puede reescribirse como


31/102

20

Qα + e + by

≥0, si α = 0

= 0, si 0 < α < C

≤ 0, si α = C

ahora, utilizando y = ±1, ∀i y asumiendo que C > 0, se tiene que

y = 1, αt < C ⇒ (Qα + e)t + b ≥ 0 ⇒ b ≥ −(Qα + e)t = −∇f (α)ty = −1, αt > 0 ⇒ (Qα + e)t − b ≤ 0 ⇒ b ≥ (Qα + e)t = ∇f (α)t

y = −1, αt < C ⇒ (Qα + e)t − b ≥ 0 ⇒ b ≤ (Qα + e)t = ∇f (α)t

y = 1, αt > 0 ⇒ (Qα + e)t + b ≤ 0 ⇒ b ≤ −(Qα + e)t = −∇f (α)tdonde f (α) = 12α

Qα + eα y ∇f (α) es el gradiente de f (α) en α y considerando

i ≡ argmax({−∇f (α)t|yt = 1, αt < C }, {∇f (α)t|yt = −1, αt > 0}) j ≡ argmin({∇f (α)t|yt = −1, αt < C }, {−∇f (α)t|yt = 1, αt > 0})

(2.20)

de manera que B = {i, j} puede usarse como grupo de trabajo para el subproblema en la ecuaci ón(2.18) del método de descomposición, donde i y j son los dos elementos que más violan las condi-

ciones de KKT. La idea de utilizar dos elementos como grupo de trabajo son tomadas del algoritmo

de optimización secuencial mı́nima (SMO) de Platt [1999]. La principal ventaja de esto, es que

la solución anaĺıtica de la ecuación (2.17) puede ser obtenida sin la necesidad de un programa de

optimización comercial. Nótese que la ecuación (2.20) es un caso especial del método SV M light

en Joachims [1999]. Para ser más preciso, en S V M light, si α es la solución actual del problema, el

siguiente es resuelto

ḿınd ∇f (α)dyd = 0, −1 ≤ d ≤ 1,

dt ≥ 0, si αt = 0, dt ≤ 0, si αt = 0

(2.21)

|{dt dt = 0}| = q (2.22)

nótese que |{dt dt = 0}| es el conjunto de componentes de d que no son cero. La restricción en laecuación (2.22) implica que la componente descendiente involucra solamente q variables. Luego, las


32/102

21

componentes de α con dt diferentes de cero son incluidas en el grupo de trabajo B utilizado para

construir el subproblema en la ecuación (2.18). En efecto, d únicamente se usa para identificar B y

no para encontrar la dirección de búsqueda.

Puede ser visto claramente que si q = 2 la solución de la ecuación (2.21) es

i = argmin{∇f (α)tdt|ytdt = 1; dt ≥ 0, si αt = 0; dt ≤ 0, si αt = C } j = argmin(∇f (α)tdt|ytdt = −1; dt ≥ 0, si αt = 0; dt ≤ 0, si αt = C }

la cual es igual a la ecuación (2.20) y corresponde a la segunda modificación del algoritmo SMO en

Keerthi et al. [1999].

Ahora, se pueden definir

gi ≡

−∇f (α)i si yi = 1, αi < C ∇f (α)i si yi = −1, αi > 0

(2.23)

y

gj ≡

−∇f (α)j si yj = −1, αj < C

∇f (α)j si yj = 1, αj > 0

(2.24)

De la ecuación (2.21) se tiene que

gi ≤ −gj (2.25)

lo cual implica que α es una solución óptima de la ecuación (2.16), de manera que el criterio de

parada puede ser escrito e implementado de la siguiente forma como

gi ≤ −gj + (2.26)

donde es una constante positiva pequeña.


33/102

22

2.5.3. Convergencia del Método de Descomposición

La convergencia de los métodos de descomposición fue inicialmente estudiada en Chang et al. [2000]

sinembargo, no coinciden con las implementaciones existentes. En esta sección, solo se tienen en

cuenta resultados de convergencia para el método especı́fico de descomposición de la sección 2.5.1.

A partir de Keerthi and Gilbert [2002] se tiene que

Teorema 5 Dado cualquier > 0 después de un n ́umero finito de iteraciones la expresi´ on en ( 2.26 )

ser´ a satisfecha.

El teorema 5 establece la llamada propiedad de terminación finita, de modo que se tiene la seguridad

de que luego de un número finito de pasos el algoritmo terminará.

Teorema 6 Si {αk} es la secuencia generada por el algoritmo de descomposici´ on en la secci´ on 2.5.1, el ĺımite de cualquiera de sus subsecuencias convergentes es soluci´ on ´ optima de la ecuaci´ on

( 2.17 ).

El teorema 5 no implica el teorema 6 si se consideran gj y gj en la ecuación (2.26) como funciones de

α que no son continuas. Por consiguiente no se puede tomar el lı́mite en ambos lados de la ecuación

(2.26) y afirmar que cualquier punto convergente ya satisface las condiciones de KKT.

El teorema 6 fue inicialmente demostrado como una caso especial de los resultados generales en Lin

[2001c] donde algunos supuestos son necesarios. Partiendo de la demostraci ón en Lin [2001a], los

supuestos son eliminados, por tanto el teorema es completamente v álido.

Considerando la convergencia local, debido a que el algoritmo utilizado es una caso especial de uno

discutido en Lin [2001b], se tiene el siguiente teorema

Teorema 7 Si Q es definida positiva y el dual del problema de optimizaci´ on es degenerado (ver

supuesto 2 en Lin [2001b ]), existe un c < 1, tal que luego de que k suficientemente grande,

f (αk+1)−

f (α∗)≤

c(f (αk)−

f (α∗))

donde α∗ es la soluci´ on ´ optima de ( 2.17 ).


34/102

23

Con esto, el método de descomposición aqúı descrito es linealmente convergente. Los resultados

mostrados en esta sección, son válidos para kernels que pueden ser considerados como el producto

punto entre dos vectores de caracteŕısticas, esto es, Q es semidefinida positiva. Por ejemplo, para

algunos kernels como el sigmoidal (ver ecuación A.5) Q puede no ser semidefinida positiva por

tanto la ecuación (2.17) es un problema de optimización no convexo que puede contener varios

mı́nimos locales. Sinembargo, con unas pequeñas modificaciones del algoritmo 1 se puede garantizar

la convergencia a un mı́nimo local (ver Lin and Lin [2003]).

2.5.4. Solución Analı́tica

Con la selección del grupo de trabajo en la sección 2.5.2, la ecuación (2.18) se convierte en unproblema de dos variables

ḿınαi,αj

1

2[αiαj ]

Qii Qij

Qji Qjj

αi

αj

+ (Qi,LαL − 1)αi + (Qj,LαL − 1)αj

sujeto a yiαi + yj αj = 0 ≡ −yLαkL0 ≤ αi, αj ≤ C

(2.27)

En Platt [1999] se sustituye αi por yi(−yLαL − yj αj) en la función objetivo de la ecuación (2.18)

y se resuelve la minimización sin restricciones respecto a αi, obteniéndose la siguiente solución

αnewj ≡ αj +

−Gi−GjQii+Qjj+2Qij

si yi = yjαj +

Gi+GjQii+Qjj−2Qij si yi = yj

(2.28)

donde

Gi ≡ ∇f αi y Gj ≡ ∇f (α)j

Si este último valor está por fuera de de la posible región para αi, el valor en la ecuación (2.28) es

truncado y asignado a αnewj . Por ejemplo, si yi = yj y C ≤ αi + αj ≤ 2C , αnewj debe satisfacer

L ≡ αi + αj − C ≤ αnewj ≤ C ≡ H


35/102

24

de modo que el máximo valor para αnewi y αnewj es C . Por consiguiente

αj + Gi + Gj

Qii + Qjj − 2Qij ≤ L

entonces αnewj = L y

αnewi = αi + αj − αnewj = C (2.29)

Esto puede ser ilustrado en la figura 2.3 en la cual se optimiza una función cuadrática sobre un

segmento de recta. El segmento de recta es la intersección entre la restricción lineal yiαi + yj αj y

las restricciones acotadas 0 ≤ αi y αj ≤ C .

Figura 2.3: Solución anaĺıtica de un problema de optimización de dos variables

No obstante, la igualdad en la ecuación (2.29) podŕıa no mantenerse si la operación de punto flotante

causara que αi + αj −αnewj = αi + αj − (αi + αj −C ) lo cual es diferente de C . Luego, en la mayorı́ade los casos, una pequeña tolerancia α es especificada de manera que todo αi ≥ C − α es una cotasuperior y αi ≤ α = 0. Esto último es necesario ya que algunos datos podŕıan ser consideradoserróneamente como vectores de soporte. En adición el cálculo del valor de desplazamiento también

necesita corrección para aquellos valores libres de αi (0 ≤ αi ≤ C ).

En Hsu and Lin [2002b] es señalado que si todos los αi obtienen sus valores mediante asignaciones

directas, no es necesario utilizar un valor de α. Para ser más precisos, en una operación de punto

flotante si αi ← C es asignado, una futura comparación entre αi y C retornará verdadero siemprey cuando contengan la misma representación interna.


36/102

25

Otro pequeño problema es que el denominador en la ecuación (2.28) puede ser cero. Cuando esto

sucede,

Qij = ±(Qii + Qij )/2

por lo tanto

QiiQjj − Q2ij = QiiQjj − (Qii + Qjj )2/4 = −(Qii − Qij)2/a ≤ 0

Ahora, considerando que QBB es definida positiva, el denominador cero en la ecuación (2.28) no es

posible. De ahı́ que este problema solo pueda suceder cuando Q sea singular de 2×2. A continuaciónse discuten dos situaciones en las cuales dicha matriz puede ser singular

La función φ no mapea los datos en vectores independientes en el espacio de alta dimensio-

nalidad haciendo que Q sea solo semidefinida positiva. Por ejemplo utilizando un kernel lineal

o polinomial de orden bajo.

Algunos kernels tienen una interesante propiedad por la cual φ(xi) ∀(i) son independientessiempre y cuando xi = xj . Un ejemplo de esto es el kernel RBF (ver Micchelli [1986]), debidoa que en muchas situaciones prácticas algunos xi son los mismos lo cual implica columnas (o

filas) de Q que son exactamente iguales y con esto la posibilidad de que QBB sea singular.

De cualquier manera, incluso si el denominador en la ecuación (2.28) es cero no hay problemas

numéricos desde que en la ecuación (2.26) se puede ver que

gi + gj ≥

y durante el proceso de iteración

gi + gj = ±(−Gi − Gj ), si yi = yj , (y)gi + gj = ±(Gi − Gj ), si yi = yj


37/102

26

Si la matriz del kernel no es semidefinida positiva Qii + Qjj ±2Qij puede no ser positiva entonces laecuación (2.28) puede no producir una actualización de modo que el valor objetivo sea disminuido.

Además el algoritmo puede permanecer en un solo punto quedándose en un ciclo infinito. En Lin

and Lin [2003] se estudia este problema en detalle y se propone la siguiente modificaci ón

αnewj ≡ αj +

−Gi−Gjmáx(Qii+Qjj+2Qij,0)

si yi = yjαj +

Gi+Gjmáx(Qii+Qjj−2Qij,0) si yi = yj

aśı, se garantiza el decrecimiento estricto de la función objetivo.

2.5.5. Cálculo de b

Después de encontrar la solución α al problema de optimización la variable b debe ser calculada para

ser utilizada en la función de decisión. Las condiciones KKT de la ecuación (2.17) fueron mostradas

en la ecuación (2.20). Ahora, para el caso de y = 1 si existen αi que satisfagan 0 ≤ αi ≤ C entoncesse hace, r1 = ∇f (α)i. Para evitar errores numéricos, se promedian como

r1 =

0≤αi≤C,yi=1 ∇f (α)i

0≤αi≤C,yi=1 1

Por otro lado, si no existe tal αi, r1 debe satisfacer

máxαi=C,yi=1

∇f (α)i ≤ r1 ≤ ḿınαi=0,yi=1

∇f (α)i

de donde r1 toma el punto medio del rango. Para yi = −1 un r2 se calcula de manera similar yluego de que ambos r1 y r2 son obtenidos,

−b = r1 − r22

Nótese que las condiciones de KKT pueden ser escritas como

máxαi>0,yi=±1

∇f (α)i ≤ ḿınαi


38/102

27

de modo que el siguiente criterio de parada puede ser utilizado pr ácticamente: el algoritmo de

descomposición para si en la iteración α satisface

máx( − ḿınαi0,yi=1

∇f (α)i,

− ḿınαi0,yi=−1

∇f (α)i) <

donde > 0 es una constante elegida como tolerancia de parada.

2.5.6. Contraccíon

Considerando que en muchos de los problemas prácticos, el número de vectores de soporte libres

(0 ≤ αi ≤ C ) es pequeño, la técnica de contracción reduce el tamaño del problema de trabajosin considerar algunas variables acotadas [Joachims, 1999]. En un punto cercano al final del pro-

ceso iterativo, el método de descomposición identifica un posible conjunto A de modo que todos

los vectores de soporte libres queden contenidos en él. Para esto, el siguiente teorema muestra

que en las iteraciones finales de la descomposición propuesta en la sección 2.5.2 solo las variables

correspondientes a un conjunto pequeño tienen la posibilidad de moverse [Lin, 2002]

Teorema 8 Si ĺımk→∞ αk = ᾱ por el teorema 6, entonces, ᾱ es una soluci´ on ´ optima. Incluso,

cuando k es suficientemente grande, solo los elementos en

{t| − yt∇f (ᾱ)t = máx( máxᾱi0,yi=−1

∇f (ᾱ)i)

= mı́n( mı́nᾱi0,yi=1

−∇f (ᾱ)i)

pueden todav́ıa seguir siendo modificados.

por lo tanto, se tiende a pensar que si la variable αi es igual a C para algunas iteraciones, al final

de la solución, ésta permanece como cota superior. De ah́ı que en vez de resolver todo el problema

de la ecuación (2.17), se trabaja con uno de menor tamaño

ḿınαA

1

2αAQAAαA − (eA + QALαkL)αA

sujeto a y AαA = −yLαkL y 0 ≤ (αA)i ≤ C, ∀i(2.30)


39/102

28

donde L = {1,...,N }\A. Sinembargo, esta heuŕıstica puede fallar si la solución de la ecuación (2.30)no es una parte correspondiente a la de la ecuación (2.17). Cuando esto sucede, el problema completo

se vuelve a optimizar desde un punto donde αB es una solución óptima de la ecuación (2.30) y αL

son variables acotadas identificadas antes del proceso de contracción. Nótese que mientras que se

está resolviendo el problema de contracción solo se conoce el gradiente QAAαA + QALαL + eA

de la ecuación (2.30). Considerando esto último, cuando se optimiza de nuevo el problema de la

ecuación (2.17) se debe reconstruir completamente el gradiente de f (α)i lo cual es un tanto costoso

en términos computacionales. Para evitar esto, en vez de iniciar el proceso de contracción al final

del proceso iterativo, se inicia desde el principio como sigue:

Luego de cada mı́n(N, 1000) iteraciones se tratan de contraer algunas variables. Aśı, durante

el proceso iterativo,

mı́n({∇f (αk)t|yt = −1, αt < C }, {−∇f (αk)t|yt = 1, αt > 0}) = −gii< máx({−∇f (αk)t|yt = 1, αt < C }, {∇f (αk)t|yt = −1, αt > 0}) = gjj

la ecuación (2.25) no se satisface todav́ıa. Entonces, se supone que si gi ≤ −gii de la ecuación(2.23) y αt está dentro del rango, es muy posible que αt no vuelva a cambiar, por lo tanto se

desactiva esa variable. Similarmente para −gj ≥ gjj de la ecuación (2.24) con αt dentro delrango. De esta manera, el conjunto A de variables activas es dinámicamente reducido cada

ḿın

{L, 1000

} iteraciones.

Es claro que la estrategia de contracción arriba mencionada es muy agresiva considerando

que el método de descomposición tiene una convergencia lenta y una gran cantidad de las

iteraciones es consumida alcanzando el d́ıgito final de precisión requerido, no es deseado que

se pierdan iteraciones innecesariamente debido a una contracción errónea. Con esto, cuando el

método de descomposición alcanza primero la tolerancia gi ≤ −gj +10, el gradiente completoes reconstruido. Luego, basados en la información correcta, se utilizan las ecuaciones (2.23)

y (2.24) para desactivar algunas variables y continuar con el método de descomposición.

Como el tamaño del conjunto A es dinámicamente reducido, para disminuir el costo computacional

del gradiente ∇f (α) durante las iteraciones se mantiene siempre

Ḡi = C

αj=c

q ij , ∀i


40/102

29

Ası́, para el gradiente ∇f (α)i con i A se tiene

∇f (α)i =i=1

Qij αj = Ḡi +

0


41/102

30

y

∇f (αk+1) = ∇f (αk) + Q:,B(αk+1b − αkB) (2.32)

donde Q:,B es la submatriz de Q con ı́ndices en B. Esto es, en la k−ésima iteración con ∇f (αk)conocido y la parte derecha de la ecuaci ón (2.31) como constructor del subproblema. Luego de

que el subproblema es resuelto, la ecuación (2.32) es empleada para obtener el próximo ∇f (αk+1).Como B contiene solo dos elementos y resolver el subproblema es fácil, el costo sustancial reside

en el cálculo de Q:,B(αk+1b − αkB). La operación en śı toma O(2N ), sinembargo si Q:,B no está

disponible en el cache y cada operación del kernel cuesta O(n) en efecto, cada columna de Q:,Bnecesita

O(nN ). De manera que la complejidad es iteraciones

×O(N ) o iteraciones

×O(N n) según

sea el caso teniendo en cuenta que si se utiliza contracción, N disminuye gradualmente. Desafor-

tunadamente, no se sabe mucho acerca de la complejidad del número de iteraciones. Sinembargo,

algunos resultados interesantes fueron obtenidos por Hush and Scovel [2003] aunque solo para los

métodos de descomposición descritos en Chang et al. [2000].

2.6. Máquinas de Soporte Multi Clase

En esta sección se discute el método para SVM multi clase “uno contra uno” [Knerr et al., 1990],

en el cual k(k − 1)/2 clasificadores deben ser construidos para entrenar pares de diferentes clases.La primera utilización de este método con SVM fue en Friedman [1996], KreSSel [1999]. Para el

entrenamiento de las clases i−ésima y j−ésima se resuelve el siguiente problema binario:

ḿınwij,bij,ξij

1

2(wij)wij + C

t

(ξ ijt )

(wij )φ(xt) + bij ≥ 1 − ξ ijt , si xt ∈ I (wij )φ(xt) + bij ≥ −1 + ξ ijt , si xt ∈ J ξ ij

t ≥0

En la clasificación se utiliza la estrategia de votación de manera que la clase se asigna para cada

punto x como la resultante con mayor número de votos o en el caso que dos clases tengan igual

número de votos, simplemente la de menor ı́ndice.


42/102

31

La otra técnica más usada para SVM multi-clase es “uno contra todos” en la cual se construyen

k modelos binarios entre la clase i

−ésima y el resto de las muestras de las otras clases juntas.

Sinembargo, no se considera debido a que en la literatura [Weston and Watkins, 1998, Platt et al.,

2000] presenta un menor desempeño que “uno contra uno”.

Además, si bien se entrenan más clasificadores k(k − 1)/2, cada problema es más pequeño (ademásrelativamente balanceado) haciendo que el tiempo de entrenamiento total no sea mayor al de “uno

contra todos”. Algunos detalles comparativos de estas y otras técnicas puede ser encontrado en Hsu

and Lin [2002a].


43/102

Caṕıtulo 3

Selección de Hiperparámetros en

Máquinas de Soporte Vectorial

En el problema de aprendizaje supervisado se toma un conjunto de pares entrada salida y se

trata de construir una función f que mapea los vectores de entrada xi ∈ Rn en etiquetas yi ∈{−1, 1}. El objetivo consiste entonces en encontrar una f ∈ F que minimize el riesgo emṕırico Remp(ver sección 2.4.1) en ejemplos posteriores. Los algoritmos de aprendizaje usualmente dependen de

parámetros que controlan el tamaño de la clase F o en la forma como la búsqueda es realizadaen F . Actualmente existen varias técnicas para encontrar dichos parámetros. El riesgo emṕırico oerror de generalización puede ser estimado o bien utilizando algunos de los datos no empleados en el

entrenamiento (validación de muestra independiente o validación cruzada) o mediante alguna cota

dada por el análisis teórico (ver sección 2.4.4).

Usualmente existen múltiples parámetros para ajustar al mismo tiempo, es mas, la estimación del

error no es una función explı́cita de tales valores de manera que la estrategia natural es una búsqueda

exhaustiva en el espacio de los parámetros lo cual corresponde a correr el algoritmo de entrenamiento

en cada valor posible previamente almacenado en un vector (sujeto a alguna discretización). Otra

manera, es encontrar una metodoloǵıa que automáticamente los ajuste, en el caso de la SVM,

tomando ventaja tanto de sus propiedades de formulación como de su algoritmo.

De manera especı́fica, los parámetros de los cuales depende la SVM son: el denotado como C que

32


44/102

33

controla el balance entre la maximización del margen y la penalización del error, aśı como todos

los que aparecen en el mapeo no lineal al espacio de representación o kernel. Como es ampliamente

conocido, uno de los factores más importantes en el desempeño de las SVM es la selección de la

función kernel, sinembargo, en la práctica muy pocos son utilizados debido a la dificultad inherente

en el ajuste de dichos parámetros.

3.1. Búsqueda en Malla

Esta técnica ha sido utilizada durante los últimos años, aunque nunca fue presentada formalmente.

Debido a su simplicidad, es usada ampliamente por muchos investigadores del área de aprendizaje

de máquina. Esta procedimiento consiste en construir una malla acotada de vectores de parámetros

conteniendo todas las posibles combinaciones en un espacio acotado de búsqueda y para un paso

de discretización escogido. Debido a que es necesario utilizar alguna medida del desempeño de la

SVM, la validación cruzada de n particiones es usada de modo que el vector de parámetros elegido

es aquel para el cual el error de validación sea menor para una tarea en espećıfico. La búsqueda en

malla para el kernel RBF está dada por la siguiente definición:

Definición 9 Para un par de par´ ametros de la SVM y el kernel: C y σ respectivamente, con

C min, σmin como cotas inferiores, C max, σmax como cotas superiores y C ∆, σ∆ como los pasos de

discretizaci´ on, la malla de entrenamiento puede ser construida como sigue:

(C i, σj ) = (C min + iC δ, σmin + jσδ) para 0 ≤ i ≤ n y 0 ≤ j ≤ m

donde n = C max−C minC ∆ , m = σmax−σmin

σ∆y (C i, σj ) conforman una matriz de tama˜ no n × m.

Dado que todas las combinaciones son necesarias para calcular una solución, un total de (n+1)(m+

1) optimizaciones de la función de SVM son empleadas.

3.2. Búsqueda en Ĺınea

Esta técnica inicialmente presentada por Chapelle et al. [2002] emplea el hecho de que la cota

de Radio/Margen (ver sección 2.4.4) es diferenciable, con el objeto de desarrollar un algoritmo


45/102

34

“óptimo” para encontrar los parámetros de la SVM partiendo de la idea que la búsqueda exhaustiva

en el espacio de parámetros puede ser prohibitiva. Esta metodoloǵıa propone tomar ventaja de

propiedades especı́ficas de la formulación de la SVM para minimizar una cota de la estimaci ón del

error de generalización empleando un algoritmo de gradiente descendiente sobre un conjunto de

parámetros dados.

Reescribiendo la fórmula de Radio/Margen dada en la ecuación (2.14) se tiene

LOO ≤ 4R2w2 (3.1)

donde w es la solución de (2.3) y R es el radio de la esfera más pequeña conteniendo todos los φ(xi).

Además, Vapnik [1998] muestra que R2 es el valor objetivo del siguiente problema de optimización:

ḿınβ

1 − β Kβ

sujeto a 0 ≤ β i , i = 1,...,leT β = 1

(3.2)

sinembargo, debido a que es posible que los φ(xi) sean no linealmente separables no es práctico usar

(2.3). Además, un φ altamente no lineal, puede producir fácilmente sobre entrenamiento. Luego, es

mejor resolver una de las siguientes variaciones de (2.9),

ḿınw,b,

1

2ww + C

N i=1

ξ i L1 − SVM (3.3)

o

ḿınw,b,

1

2ww +

C

2

N i=1

ξ 2i L2 − SVM (3.4)

De modo que ahora se puede hacer referencia a dos clases de SVM, L1-SVM y L2-SVM respecti-vamente dependiendo si los errores son penalizados lineal o cuadr áticamente. A continuación, se

describen los métodos de selección para Radio/Margen utilizando L1 y L2.


46/102

35

3.2.1. Cota de Radio/Margen para L2

Con relación a la formulación para L2-SVM en (3.4) y haciendo K (xi, xj ) = zi.zj , el problema de

SVM puede ser convertido a margen rı́gido como:

ḿınw

1

2 w2

sujeto a yi( wi.zi + b) ≥ 0 ∀i (3.5)donde zi denota la transformación a un espacio de representación modificado dado por:

zi.zj = K (xi, xj ) = K (xi, xj ) + 1C

δ ij

con δ ij = 1, si i = j y 0 en otro caso. Aśı, la expresión en (3.1) puede ser volverse a escribir como

se muestra en Vapnik and Chapelle [2000]

LOO ≤ f (C, σ) 1N

R2 w2 (3.6)siendo

w como la solución de (3.5). Debido a que (3.6) es diferenciable respecto de C y σ , es apro-

piado utilizar alguna de las técnicas basadas en gradiente descendiente, por ejemplo el algoritmo

Quasi-Newton para minimizar f (C, σ). El cálculo del gradiente de f (C, σ) requiere que w2 y R2sean conocidos, sinembargo, recientemente Chapelle et al. [2002] provee un resultado bastante útil

que hace fácil la obtención de dichos gradientes una vez los duales de (3.4) y (3.2) son resueltos.

Con esto último se mantiene que:

∂f

∂C =

1

N [

∂ w2∂C

R2 + w2 ∂R2∂C

] ∂f

∂σ2 =

1

N [

∂ w2∂σ2

R2 + w2 ∂R2∂σ2

]

∂ w2∂C

=

i

αiC 2

∂ w2∂σ2

= −i,j

αiαj yiyj K (xi, xj )xi − xj22σ4

∂R

2

∂C = −i

β iC 2 (1 − β i) ∂R2

∂σ2 = −i,j

β iβ j K (xi, xj )xi − xj22σ4luego, si w2, R2, α y β están disponibles, el gradiente de f (C, σ) es fácil de obtener. Como essugerido en Chapelle et al. [2002], u1 = ln C y u2 = ln σ

2 deben ser usados en vez de C and σ2.


47/102

36

Para este trabajo, BFGS como algoritmo quasi-Newton es empleado para minimizar f (C, σ) (ver

apéndice B). Como se presenta en Keerthi [2002], una técnica de gradiente descendiente requiere

muchas más evaluaciones debido a la sensibilidad de tal procedimiento a errores de cálculo numérico

en f (c, σ2) y sus gradientes. Para el algoritmo BFGS, se escogi ó ζ = 1 (ver ecuación B) como

parámetro inicial y C = 1, σ2 = n como condiciones iniciales donde n es la dimensión de xi. El

criterio de parada fue tomado como |f (u + 1) − f (u)| ≤ 10−5f (u), según sugerencia en Keerthi[2002].

3.2.2. Cota de Radio/Margen para L1

En Chung et al. [2003] se propone la siguiente modificación de (3.1) para L1-SVM:

(R2 + ∆

C )(w2 + 2C

N i=1

ξ i) (3.7)

siendo ∆ una constante positiva cercana a 1. Denotando (3.7) como f (C, σ2) y usándola como cota

de (3.3) las derivadas parciales se calculan como:

A = w2 + 2C N

i=1ξ i B = R

2 + ∆

C

∂f

∂C =

∂A

∂C B +

∂ B

∂C A

∂f

∂σ2 =

∂A

∂σ2B +

∂B

∂σ2A

∂A

∂C = 2

i

ξ i∂A

∂σ2 = −

i,j

αiαj yiyj K (xi, xj )xi − xj22σ4

∂B

C = − ∆

C 2∂B

σ2 = −

i,j

β iβ j K (xi, xj )xi − xj22σ4

donde se toma el valor ∆ = 1 según Chung et al. [2003]. Del mismo modo que para L2-SVM,

la transformación de variable, algoritmo de optimización y condiciones iniciales fueron usadas.

Para el parámetro de BFGS, ζ = 1

2

(ver ecuación B) fue elegido debido a que es probable que se

obtengan valores mas allá de la región considerada ([-10,10]x[-10,10] para este trabajo) generando

una posible inestabilidad numérica. Además, para el criterio de parada se prefiere utilizar la siguiente

formulación compuesta:


48/102

37

∇f (xk)∇f (x0) ≤

10−3 or ∇

f (xk)

≤10−3

donde x0 es la solución inicial. En Chung et al. [2003] se afirma que el criterio de parada propuesto

por Keerthi [2002] puede no ser adecuado para este caso, por eso se sigue m ás bien el lineamiento

de Lin and More [1999].

3.3. Limitaciones Actuales

En esta sección se presentan algunas discusiones acerca de la viabilidad y limitaciones de las técnicas

arriba descritas.

Para el caso de búsqueda en malla, los requerimientos en cuanto a evaluaciones de la función de SVM

pueden tornarse prohibitivos para grupos de datos de entrenamiento de mediano y gran tamaño.

Si bien se sugiere que los valores máximos y mı́nimos para C y σ sean [-10,10]x[-10,10] como por

defecto, el tamaño del paso es todav́ıa una incógnita porque un valor grande no es suficiente para

obtener resultados satisfactorios y por el contrario uno pequeño, incrementa dramáticamente el

número de evaluaciones sin de ninguna manera garantizar buenos resultados. En cuanto a ventajas,

dado que este procedimiento utiliza solamente validación cruzada como medida de riesgo, el uso

indiscriminado de kernels y esquemas multi-clase es posible pero teniendo en cuenta que múltiples

parámetros tornan más complejo el espacio de búsqueda, por lo tanto, se espera un incremento

considerable en la carga computacional y por consiguiente es importante tener cuidado al escoger el

tamaño del paso. Otro asunto importante es que el tamaño de la partición en la validación cruzada,

es directamente proporcional al número de evaluaciones de la función de SVM ası́ que también debe

tenerse en cuenta.

En es esquema de búsqueda en ĺınea utilizando Radio/Margen solo son necesarias una pocas evalu-

aciones de la función de SV

Tesis Mg - Seleccion de Hiperparametros en Maquinas de Soporte Vectorial. Univ Colombia.2004

Documents

Transcript of Tesis Mg - Seleccion de Hiperparametros en Maquinas de Soporte Vectorial. Univ Colombia.2004