Selección de Atributos
en
Aprendizaje de Preferencias
(usando SVM)
Grupo de Aprendizaje Automático
Universidad de Oviedo en Gijón
www.aic.uniovi.es/MLGroup
Red de Minería y Aprendizaje
Índice de la presentación
• Aprendizaje de Preferencias
• Máquinas de Vectores Soporte
• SVM para Aprendizaje de Preferencias
• Selección de Atributos
• Resultados Experimentales
• Conclusiones
Red de Minería y Aprendizaje
Aprendizaje de Preferencias
• Aplicaciones típicas:
Calidad de productos
 Recuperación de información
 Interfaces adaptativas

• Problemas en los que los métodos de
regresión fracasan
• ¿Por qué fracasan?


Las calificaciones proceden de diferentes
fuentes (distintas escalas)
Tienen un sentido relativo
Red de Minería y Aprendizaje
Aprendizaje de Preferencias
Red de Minería y Aprendizaje
Aprendizaje de Preferencias
• No intenta predecir las etiquetas numéricas
• Datos: conjuntos de relaciones de
preferencia
{ (vi, ui) : i=1..l }
donde vi es considerado
mejor que ui (vi > ui )
Reflejan el sentido relativo de las calificaciones
• Soluciones:

Clasificadores: no transitivos

Funciones de Preferencia
Red de Minería y Aprendizaje
Funciones de Preferencia
f: d  
tal que f(v) > f(u) siempre que v > u
Si consideramos f lineal, en ese caso
fw(x) = +w,x,
+w,v, > +w,u,
(v-u) , +
(u-v) , -
Red de Minería y Aprendizaje
Máquinas de Vectores Soporte
“No hay nada más práctico que una buena teoría”
• Introducidas en los 90 por Vapnik
• Se basan en la Minimización del Riesgo
Estructural (SRM)
• 92: maximización del margen y uso de kernels
• 95: margen blando
• Rápido desarrollo: algoritmos más eficientes,
diseño de kernels
Red de Minería y Aprendizaje
Maximización del Margen
Red de Minería y Aprendizaje
Hiperplano Óptimo
S  ( x1 , y1 ), ..., ( x l , y l )
w, x  b  1
x  X , y  Y   1,  1
w, x  b  0
w, x  b  1
f ( x)  w, x  b
h ( x )  sign ( f ( x ))
min
i
w , xi  b  1
yi  w , xi  b   1 ,
d ( w , b , xi ) 
 ( w , b )  min
xi , yi  1
w , xi  b
 min
w
Red de Minería y Aprendizaje
i  1,..., l
w , xi  b
xi , yi  1
w
w , xi  b
w

2
w
Problema Primal
Maximizar el margen equivale a minimizar la norma
Minimizar:
Sujeto a:
w, w
yi  w , xi  b   1 ,
i  1,..., l
Red de Minería y Aprendizaje
Teoría de Optimización
Se usa la teoría de Lagrange (o de Kuhn-Tucker)
Lagrangiana:
L (w, b) 
1
2
l
w , w    i y i  w , x i  b   1
i  0
i 1
i  1,..., l
Diferenciar y sustituir
L
dw
l
0 
w

i 1
i
yi xi
L
l
0 
db
Red de Minería y Aprendizaje

i 1
i
yi  0
Problema Dual
l
Maximizar:
W ( ) 

i 1
Sujeto a:
i

1
2
l
 
i
i 1 , j 1
i  0
l

i
yi  0
i 1
¡Podemos usar KERNELS!
Red de Minería y Aprendizaje
j
yi y j xi , x j
Propiedades de la solución
• Margen
• Problema de Optimización cuadrática:



convexidad
no hay mínimos locales
resoluble en tiempo polinomial
• Dualidad: permite el uso de kernels
• Esparsidad: sólo son necesarios los
puntos cerca del margen (vectores
soporte)
Red de Minería y Aprendizaje
Margen blando
i
Red de Minería y Aprendizaje
Margen blando
Minimizar:
1
w, w  C   i
2
Sujeto a:
i
yi  w , xi  b   1   i ,
l
Maximizar:
W ( ) 

i 1
Sujeto a:
i

1
2
i  1,..., l
l
 
i
i 1 , j 1
0  i  C
l

i
yi  0
i 1
Red de Minería y Aprendizaje
j
yi y j xi , x j
Clasificadores no-lineales
• Solución 1: crear una red neuronal
Problemas:
 Topología
 Mínimos locales
 Muchos parámetros
• Solución 2: transformar (kernel) el espacio de
entrada en un espacio de características, y
aplicar un clasificador lineal. Hay que decidir:


qué espacio de características es el adecuado para el
problema
el grado de sobreajuste (C)
Red de Minería y Aprendizaje
Clasificadores no-lineales
l
Maximizar:
W ( ) 

i

2
i 1
Sujeto a:
1
l
 
i
j
yi y j K ( xi , x j )
i 1, j 1
0  i  C
l

i
yi  0
i 1
Kernel Polinómico
Kernel Gaussiano
 x ,x
i
j
1

p

xi  x j

exp 
2

2


Kernel Perceptrón Multicapa
2






tanh  x i , x j  
Red de Minería y Aprendizaje

Espacio de características
Input space
Features space
K
Red de Minería y Aprendizaje
Kernels
Red de Minería y Aprendizaje
SVM puede resolver problemas de…
• Clasificación binaria
• Multiclasificación
• Regresión
• Clustering
• y … de Aprendizaje de Preferencias
Red de Minería y Aprendizaje
SVM para Preferencias [Herbrich]
Minimizar:
w, w
Sujeto a:
w , xi
1
 w , xi
2
1
2
1
 w, ( xi  xi )  0
2
 ( xi  xi )
l
  i y i ( xi  xi )
1
w
2
i 1
l
Dual: W ( ) 
 i 
i 1
l
W ( ) 

1
2
1
 i 
2
1
2
1
i 1
2

1
l

 i j y i y j ( x i  x i ), ( x j  x j )
1
2
1
2
i 1, j 1

l
  i j y i y j K ( x i , x i ), ( x j , x j )
1
2
1
2

i 1 , j 1
1
1
2
2
1
2
2
K ( x i , x i ), ( x j , x j )  k ( x i , x j )  k ( x i , x j )  k ( x i , x j )  k ( x i , x j )
Red de Minería y Aprendizaje
FSS en Aprendizaje de Preferencias
• Kernel Lineal
• Ranking de conjunto de atributos: permite
construir d subconjuntos de atributos


Relieve (Kohavi, John, 97), modificación de
Relief (Kira, Rendell, 92)
RFE (Recursive Feature Elimination) (Guyon et al.,02)
F1  F2  ,...,  Fd
• Selección del mejor subconjunto:


Cross-Validation
ADJ (Schuurmans, 97) métrica entre modelos
Red de Minería y Aprendizaje
RFE (Recursive Feature Elimination)
• Backward Feature Elimination: borra un atributo
por iteración
• Criterio (kernel lineal): menor (wi)2
siendo wi el coeficiente del atributo i en el
hiperplano inducido por SVM
• Obtiene una lista ordenada de subconjuntos de
atributos
Red de Minería y Aprendizaje
RFE (Recursive Feature Elimination)
Funcion SVM-RFE(T, fs): Una lista ordenada de subconjuntos de atributos
//T: Conjunto de relaciones de preferencias
//fs: Conjunto de atributos |fs|=d
//L: Lista ordenada de subconjuntos de atributos
Fd = fs;
L = [ Fd ];
//Inicialmente, un subconjunto con todos los atributos
Para cada j desde d hasta 2 do
w = SVM( T );
//Se entrena SVM
2
r = arg min (( w i ) )
//Criterio de selección
i
Fj-1 = Fj \ fr;
//Se borra el atributo r de Fj
L = L + [Fj-1];
//Se añade el subconjunto con el resto de attr.
T = {x'i : x'i is xi 0 T con fr borrado};
//Borra atributo r de T
FinPara
Retorna L;
FinFuncion
//L: lista ordenada de subconjunto de atributos
Red de Minería y Aprendizaje
ADJ (Schuurmans)
• Permite la selección entre múltiples hipótesis
ordenadas por su complejidad
• Adaptable para técnicas FSS
F1  F2  ,...,  Fd
• Define una métrica en el espacio de hipótesis
• La distancia entre dos hipótesis wFi y wFj es:

d w Fi , w F j

def
 
  err w
Fi
 
( x ), w F j ( x ) dP x
err(wFi(x), wFj (x)) mide las discrepancias en un
punto del espacio de ejemplos
Red de Minería y Aprendizaje
ADJ (Schuurmans)

• Hipótesis seleccionada:
w k  arg min d ' w Fi , W
i

• d’ se mide las discrepancias en las predicciones
sobre dos conjuntos T y U
ADJ
w
Fi
,W

d S w F k , w Fi




def

 d T w Fi , W  max
def

d ' w Fi , W

1 
S  2 
1

T i
T i
1
j S
ADJ

w
d U w F k , w Fi
k i
dT
Fk
wF ,x j  wF ,x j
k
w
i
Fi
,W

Red de Minería y Aprendizaje
, w Fi






Resultados Experimentales
• Problema real: Calificación de bovinos
• Idea: morfología del animal debe servir para
evaluar la capacidad como productor de carne
• Sistema:



Obtención de medidas morfológicas (técnicas de Visión
Artificial)
Calificación (ordenación) por grupos de expertos
Aplicación de sistemas de aprendizaje de preferencias
• Proceso costoso: la selección de atributos debe
jugar un papel decisivo
Red de Minería y Aprendizaje
Resultados Experimentales
Red de Minería y Aprendizaje
Resultados Experimentales
Red de Minería y Aprendizaje
Resultados Experimentales
Relief + CV
%Acie. #Atrs
Relief +ADJ
%Acie. #Atrs
Relief +QADJ
%Acie. #Atrs
SVM
%Acie.
BULLS-Z-120
95,43
9,3
94,42
10,5
94,42
5,9
94,17
BULLS-Z-141
95,44
12,4
94,42
13,2
94,67
8,2
94,68
BULLS-L-165
95,69
20,8
95,44
18,3
95,44
14,6
94,42
BULLS-L-193
96,45
25,4
95,69
25,2
95,69
22,1
94,68
COWS-Z-120
93
15,2
92,43
18,3
92,43
15,2
93,19
COWS-Z-141
93,19
16,3
92,8
20,7
92,8
12,2
92,81
COWS-L-165
93,19
42,6
93,56
51,1
93,37
18,2
93
COWS-L-193
Media
93,37
94,47
23,3
20,66
93,56
94,04
21
22,3
92,81
93,95
9,4
13,23
93
93,74
Red de Minería y Aprendizaje
Resultados Experimentales
RFE+CV
RFE+ADJ
RFE+QADJ
SVM
%Acie.
#Atrs
%Acie.
#Atrs
%Acie.
#Atrs
%Acie.
BULLS-Z-120
96,46
6,4
95,96
14,5
96,21
9,1
94,17
BULLS-Z-141
96,69
3,9
96,96
6,8
96,7
6,4
94,68
BULLS-L-165
96,2
4,5
95,7
24,1
95,44
6,6
94,42
BULLS-L-193
96,7
5,7
95,95
10
95,95
6,2
94,68
COWS-Z-120
94,14
4,9
93,57
4,2
93,57
4,2
93,19
COWS-Z-141
93,95
4,2
93,19
18,7
93,57
5,4
92,81
COWS-L-165
94,33
4,9
94,14
7,6
94,2
5,86
93
COWS-L-193
93,56
6,5
93,18
10,2
93,18
6,3
93
Media
95,25
5,13
94,83
12,01
94,85
6,26
93,74
Red de Minería y Aprendizaje
Resultados Experimentales
A-10-0
A-10-5
A-10-10
A-10-15
A-10-20
A-20-0
A-20-5
A-20-10
A-20-15
A-20-20
A-30-0
A-30-5
A-30-10
A-30-15
A-30-20
A-40-0
A-40-5
A-40-10
A-40-15
A-40-20
Media
RFE+CV
%Acie. #Atrs
98,15
10
96,95
10
80,9
57
81,55
35
79,2
39
94,3
22
95,25
22
94,4
21
78
63
74,15
49
91,85
38
93,9
31
85,4
41
79,65
53
73,85
63
92,5
44
86,95
44
76
63
77
64
70,75
52
85,04 41,05
RFE+ADJ
%Acie. #Atrs
96,85
12
96,95
10
94,45
11
79
50
77,65
43
94,5
24
92,95
25
93,45
22
78,55
56
70,5
154
94,5
31
86,25
51
80,15
92
75,8
107
72,85
83
94,15
40
86,95
44
76,3
71
76,95
73
71,05
83
84,49
54,1
RFE+QADJ
%Acie. #Atrs.
96,85
12
96,95
10
94,45
11
90,15
13
77,65
43
95
21
92,95
25
93,45
22
78,55
56
75
46
94,5
31
92,75
32
88,45
32
83,8
29
73,85
22
94,15
40
86,95
44
77,55
26
76,95
73
70,75
58
86,54
32,3
Red de Minería y Aprendizaje
SVM
%Acie.
83,6
81,3
77,15
74,3
71,9
83,65
82,55
78,7
74,1
71,1
82,45
80,8
77,85
75,45
71,1
83
81,35
78,25
75,4
72,65
77,83
Conclusiones
• El aprendizaje de preferencias resuelve
tareas en las que la regresión fracasa
• Las máquinas de vectores soporte
pueden aprender preferencias
• Se están desarrollando técnicas de
selección de atributos para SVM
• Trabajo futuro, FSS para kernels no
lineales
Red de Minería y Aprendizaje
Selección de Atributos
en
Aprendizaje de Preferencias
(usando SVM)
Grupo de Aprendizaje Automático
Universidad de Oviedo en Gijón
www.aic.uniovi.es/MLGroup
Red de Minería y Aprendizaje
Descargar

transparencias