Red de Minería y Aprendizaje
Grupo de Aprendizaje AutomáticoUniversidad de Oviedo en Gijón
www.aic.uniovi.es/MLGroup
Selección de Atributosen
Aprendizaje de Preferencias(usando SVM)
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 Preferenciaf: 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
• 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
“No hay nada más práctico que una buena teoría”
Red de Minería y Aprendizaje
Maximización del Margen
Red de Minería y Aprendizaje
Hiperplano Óptimo
1,1,
),(...,),,( 11
YyXx
yxyxS ll
))(()(
,)(
xfsignxh
bxwxf
0, bxw
libxwy ii ,...,1 , 1,
w
bxwxbwd
i
i
,),,(
ww
bxw
w
bxwbw
i
yx
i
yx iiii
2,min
,min),(
1,1,
1,min bxw ii
1, bxw
1, bxw
Red de Minería y Aprendizaje
Problema Primal
ww,
libxwy ii ,...,1 , 1,
Maximizar el margen equivale a minimizar la norma
Minimizar:
Sujeto a:
Red de Minería y Aprendizaje
Teoría de Optimización
l
iiii xyw
dw
L
1
0
l
iiii bxwywwbwL
1
1,,2
1),(
lii ,...,1 0
Se usa la teoría de Lagrange (o de Kuhn-Tucker)
Lagrangiana:
Diferenciar y sustituir
l
iii ydb
L
1
0 0
Red de Minería y Aprendizaje
Problema Dual
01
l
iii y
l
jijijiji
l
ii xxyyW
1,11
,2
1)( Maximizar:
Sujeto a: 0i
¡Podemos usar KERNELS!
Red de Minería y Aprendizaje
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
i
iCww ,2
1
libxwy iii ,...,1 , 1,
Minimizar:
Sujeto a:
01
l
iii y
l
jijijiji
l
ii xxyyW
1,11
,2
1)( Maximizar:
Sujeto a: Ci 0
Red de Minería y Aprendizaje
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
01
l
iii y
pji xx 1,
l
jijijiji
l
ii xxKyyW
1,11
),(2
1)( Maximizar:
Sujeto a: Ci 0
Kernel Polinómico
Kernel Gaussiano
Kernel Perceptrón Multicapa
2
2
2exp
ji xx
ji xx ,tanh
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]
l
jijjiijiji
l
ii xxxxyyW
1,1
2121
1
)(),(2
1)(
)( 2
1
1i
l
iiii xxyw
l
jijjiijiji
l
ii xxxxKyyW
1,1
2121
1
),(),,(2
1)(
ww,
)( 0 )(, ,, 212121iiiiii xxxxwxwxw
Minimizar:
Sujeto a:
),(),(),(),(),(),,( 221221112121jijijijijjii xxkxxkxxkxxkxxxxK
Dual:
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 deRelief (Kira, Rendell, 92)
RFE (Recursive Feature Elimination) (Guyon et al.,02)
• Selección del mejor subconjunto: Cross-Validation ADJ (Schuurmans, 97) métrica entre modelos
dFFF ,...,21
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
r = //Criterio de selección
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; //L: lista ordenada de subconjunto de atributosFinFuncion
))((minarg 2i
iw
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 dFFF ,...,21
• Define una métrica en el espacio de hipótesis
• La distancia entre dos hipótesis wFi y wFj es:
xFF
def
FF dPxwxwerrwwdjiji
)(),( ,
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:
• d’ se mide las discrepancias en las predicciones sobre dos conjuntos T y U
WwdwiF
ik , 'minarg
ik
ik
ii
FFT
FFU
ikFT
def
F wwd
wwdWwdWwADJ
,
, max, ,
Sjxwxw
def
FFSjiFjkFik
wwd,,
112S
1 ,
WwADJiT
iTWwd
ii FF , , '
Red de Minería y Aprendizaje
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 Relief +ADJ Relief +QADJ SVM
%Acie. #Atrs %Acie. #Atrs %Acie. #Atrs %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 93,37 23,3 93,56 21 92,81 9,4 93Media 94,47 20,66 94,04 22,3 93,95 13,23 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 ExperimentalesRFE+CV RFE+ADJ RFE+QADJ SVM
%Acie. #Atrs %Acie. #Atrs %Acie. #Atrs. %Acie.A-10-0 98,15 10 96,85 12 96,85 12 83,6A-10-5 96,95 10 96,95 10 96,95 10 81,3A-10-10 80,9 57 94,45 11 94,45 11 77,15A-10-15 81,55 35 79 50 90,15 13 74,3A-10-20 79,2 39 77,65 43 77,65 43 71,9A-20-0 94,3 22 94,5 24 95 21 83,65A-20-5 95,25 22 92,95 25 92,95 25 82,55A-20-10 94,4 21 93,45 22 93,45 22 78,7A-20-15 78 63 78,55 56 78,55 56 74,1A-20-20 74,15 49 70,5 154 75 46 71,1A-30-0 91,85 38 94,5 31 94,5 31 82,45A-30-5 93,9 31 86,25 51 92,75 32 80,8A-30-10 85,4 41 80,15 92 88,45 32 77,85A-30-15 79,65 53 75,8 107 83,8 29 75,45A-30-20 73,85 63 72,85 83 73,85 22 71,1A-40-0 92,5 44 94,15 40 94,15 40 83A-40-5 86,95 44 86,95 44 86,95 44 81,35A-40-10 76 63 76,3 71 77,55 26 78,25A-40-15 77 64 76,95 73 76,95 73 75,4A-40-20 70,75 52 71,05 83 70,75 58 72,65Media 85,04 41,05 84,49 54,1 86,54 32,3 77,83
Red de Minería y Aprendizaje
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
Grupo de Aprendizaje AutomáticoUniversidad de Oviedo en Gijón
www.aic.uniovi.es/MLGroup
Selección de Atributosen
Aprendizaje de Preferencias(usando SVM)