Support Vector Machines Ricardo Muñoz

(2)

Contenido

• 1. Introducción

• 2. Caso Separable

• 3. Caso No-Separable

• 4. Extensiones

(3)

Ejemplo introductorio

Caso Retención de Clientes: “detección de fuga”.

• Dada ciertas características del cliente (edad, ingreso, crédito, saldo promedio, comportamiento en general) (atributos)

• Determinar si el cliente cerrará su cuenta corriente en los próximos meses.

Aprender de información de otros clientes, generar alguna

“Regla” y aplicar esta regla a casos nuevos.

(4)

Teoría de Aprendizaje Estadístico

Minimización del riesgo empírico

Queremos encontrar una función f que minimice:

Donde y es el valor conocido del objeto x, f(x) es la función de inducción y n es el número de objetos

n

1i

ii )(x - y2

n

1 ][Remp ff

(5)

Motivación SVM

Caso particular de dos conjuntos linealmente

disjuntos en R2

: No cierra

: Cierra

(6)

Motivación SVM

Caso particular de dos conjuntos linealmente

disjuntos en R2

: No cierra

: Cierra

W

(7)

Support Vector Machines (Para Clasificación)

IDEA:

Construir una función clasificadora que:

• Minimice el error en la separación de los objetos dados (del

conjunto de entrenamiento)

• Maximice el margen de separación (mejora la generalización

del clasificador en conjunto de test)

Dos objetivos:

Minimizar Error

(ajuste del modelo)

Maximizar Margen

(generalización)

(8)

SVM Lineal – Caso Separable

N objetos que consistenten del par : xi Rm, i=1,…,n y de su

“etiqueta” asociada yi {-1,1}

Supongamos que un hiperplano separador wx+b=0 que

separa los ejemplos positivos de los ejemplos negativos. Esto es,

Todos los objetos del conjunto de entrenamiento satisfacen:

1 cuando 1

1 cuando 1

ii

ii

ybwx

ybwx

equivalentemente:

ibwxy ii 01)(

Sean d+ (d-) las distancias más cercanas desde el hiperplano

separador al ejemplo positivo (negativo) más cercano. El margen del

hiperplano separador se define como d+ + d-

(9)

SVM Lineal – Caso Separable

wx+b=0

w

2

(0,0) desde |1|

w

b

(0,0) desde |1|

w

b

(10)

Formulación matemática

(SVM primal)

0 1b

:a sujeto

2

1Minimizar

i i

2

wxy

W W: Normal al hiperplano

separador.

b : Posición del hiperplano

Xi: Objetos de entrenamiento

Yi : Clase del objeto i.

1/Margen

(11)

Formulación matemática

(SVM L dual)

n

1i

i

sii

0

1 0

:a sujeto

2

1 - Maximizar

ii

i

sisi

yα

,...,n

xxyy

KERNELS!!!

Luego...

(12)

SVM Lineal – Caso No Separable

N objetos que consistenten del par : xi Rm, i=1,…,n y de su

“etiqueta” asociada yi {-1,1}

Se introducen variables de holgura positivas i:

1 cuando 1

1 cuando 1

iii

iii

ybwx

ybwx

Y se modifica la función objetivo a:

)(22

iCw

(13)

Formulación matemática

(SVM primal)

0

0 1b

:a sujeto

C 2

1Minimizar

i

i i i

i

2

wxy

W W: Normal al hiperplano

separador.

b : Posición del hiperplano

Xi: Objetos de entrenamiento

Yi : Clase del objeto i.

: Error en la separación

i

Error en

clasificación

1/Margen

(14)

Formulación matemática

(SVM dual)

n

1i

i

sii

0

1 0 C

:a sujeto

2

1 - Maximizar

ii

i

sisi

yα

,...,n

xxyy

KERNELS!!!

Luego...

(15)

Clasificador

• El clasificador lineal de los SVM es:

• Se determina el signo de la función f(x)

• Si signo(f(x)) = +1 pertenece a clase +1

• Si signo(f(x)) = -1 pertenece a clase -1

bxyαxxfi

ii b W )(

(16)

SVM no lineal

Objetos linealmente no

separables en R2, pueden

serlo otro espacio

(17)

SVM no lineal

• Idea:

– Proyectar los objetos a un espacio de mayor dimensión y realizar una clasificación lineal en este nuevo espacio.

– Función de transformación

–

– Basta reemplazar xi· xs por K(xi , xs )

)()()( , sisi xxxxK

(18)

Kernel Machines

x X

)(

)(

)(

xX

xX

ii

))()((sign byySi

iii

xx

)()( xxXX ii

)(sign byySi

iii

XX

),( K ),()()( xxxx ii K

)),((sign bKyySi

iii

xx

Condición de Mercer

(19)

Funciones de Kernel

(20)

SVM para selección de atributos

• Idea:

Penalizar en la función objetivo por cada atributo utilizado.

• Función de penalización:

Penalizar si el coeficiente asociado al atributo es mayor que cero.

x)exp(--e f(x)

e :vector de unos

> 0

(21)

SVM para selección de atributos

0 v

vv-

0

0 1b

:a sujeto

v))exp(--(eeCC W2

1Minimizar

i

i i i

T2i1

2

w

wxy

(23)

Características de SVM

• Herramienta matemática

• No tiene mínimos locales (árboles de decisión)

• No tiene el problema de Overfitting (Redes Neuronales)

• Solución no depende de estructura del planteamiento del problema.

• Aplicabilidad en distintos tipos de problemas (Clasificación, Regresión, descubrimiento de patrones en general)

(24)

Referencias

• Apuntes Curso “Introducción a la minería de datos”, Richard Weber.

• C. Burges, A tutorial on support vector machines for pattern recognition, Data Mining and Knowledge Discovery 2 (1998), no. 2, 121–167