“Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
´ “Vector de Soporte y Metodos de Kernel”
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
Carlos Valle Vidal
[email protected] ´ Departamento de Informatica ´ Universidad Tecnica Federico Santa Mar´ıa
SMO Kernel ridge regression
Santiago, Abril 2009
Kernel PCA y CCA SVR
1 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
2 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
3 / 94
´ Introduccion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
´ Los Metodos de kernel son una familia de algoritmos ´ relativamente nueva en el mundo del analisis inteligente de datos y reconocimiento de patrones. Combinan la simplicidad y eficiencia de algoritmos como el ´ y ridge regression con la flexibilidad de sistemas perceptron ´ ´ no-lineales y el rigor de los metodos de regularizacion. Sea X el espacio de entrada e Y el dominio de salida. ´ , Y ⊆ R regresion ´ X ⊆ Rn , Y = {−1, 1} clasificacion
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
4 / 94
´ (2) Introduccion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
´ A lo largo del cap´ıtulo usaremos como ejemplo una funcion de aprendizaje binaria f : X ⊆ Rn → R de la siguiente forma La entrada x = (x1 , . . . , xn )T es asignada a la clase positiva si f (x) ≥ 0, Sino es asignada a la clase negativa
´ cuando f (x) es una funcion ´ Estaremos interesados ademas no-lineal de x ∈ X , y lo resolveremos encontrando una ´ lineal f (x) que sea la imagen de un mapeo no-lineal. funcion
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
5 / 94
´ (3) Introduccion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels
El conjunto de entrenamiento
S = {(x1 , y1 ), . . . , (xm , ym ) ⊆ (X × Y)m } m es el numero de ejemplos, xi es el ejemplo o instancia e yi ´ es su etiqueta Denotamos por hx, wi = xT w = ∑i xi wi al producto interno entre x y w
Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
6 / 94
´ Metodos de Kernel “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron
´ Metodos de Kernel V llevar los datos a un espacio vectorial ´ donde se pueda aplicar metodos lineales V identificar patrones Este mapeo es no-lineal V descubrir relaciones no-lineales ´ usando metodos lineales.
Usando Kernels
Consideremos el mapeo φ : x ∈ X → φ(x) ∈ F
Sobreajuste y cotas de ´ generalizacion
X : espacio de entrada. F : Espacio caracter´ıstico.
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
7 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
8 / 94
´ Primal Representacion “Vector de Soporte y ´ Metodos de Kernel”
´ aprende una clasificacion ´ binaria El algoritmo del perceptron ´ usando una funcion lineal con valores reales f : X ⊆ Rn → R
Carlos Valle Vidal
f (x) = hw, xi + b
´ Introduccion
n
=
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
∑ wi xi + b i=1
SVM
´ Donde (w, b) ∈ Rn × R son parametros que controlan la ´ y la regla de decision ´ esta´ dada por sign(f (x)) funcion
SMO
w, b se aprenden de los datos y su salida es el algoritmo del
Kernel ridge regression
´ perceptron
Kernel PCA y CCA SVR
9 / 94
´ Geometrica ´ Interpretacion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
El espacio de entradas X se divide en dos partes por el hiperplano definido por hw, xi + b = 0 ´ n − 1 que Un hiperplano es un subespacio af´ın de dimension divide el espacio en dos partes correspondientes a dos clases. ´ de n + 1 parametros ´ Esta representacion libres permite representar todos los posibles hiperplanos en Rn
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
10 / 94
´ Geometrica ´ Interpretacion (2) “Vector de Soporte y ´ Metodos de Kernel”
La distancia euclidiana de un punto xj al plano m
wj xj + b hw, xj i + b = ||w|| j=1 ||w||
Carlos Valle Vidal
∑
´ Introduccion ´ El perceptron Usando Kernels
||w|| =
p hw · wi
Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
11 / 94
Notaciones “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
Los estad´ısticos usan este modelo y le llaman discriminante lineal (Fisher, 1936) ´ (Rosemblatt, En redes neuronales se le llama perceptron 1960) w es el vector de pesos y b el sesgo (bias). −b = θ V umbral Se desea minimizar
D(w, b) = − ∑ yj (xj w + b) j
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
Derivando respecto de w y b tenemos
δD(w, b) δw
=
δD(w, b) δb
=
∑ yj xj j
∑ yj j
12 / 94
´ Algoritmo forma primal El perceptron: “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA
´ (forma primal) Algoritmo 1 Algoritmo del Perceptron 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:
Dado un conjunto de entrenamiento S
w0 ← 0; b0 ← 0; k ← 0 R ← max1≤j≤m ||xj || repeat for j = 1 to m do if yj (hwk , xj i + bk ) ≤ 0 then
wk+1 ← wk + ηyj xj bk+1 ← bk + ηyj R2 k ← k+1 end if end for until No haya errores dentro del loop Salida: (wk , bk )
SVR
13 / 94
Observaciones “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
´ ´ de xj al cambio de peso es αj ηyj xj Notese que la contribucion
αj es el numero de veces que xj esta´ mal clasificado ´ El numero de fallos totales k ´
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
l
k = ∑ αj j=1
l
w = ∑ αj yj xj j=1
El algoritmo modifica directamente w y b Si existe un hiperplano que clasifique correctamente los datos V datos linealmente separables Sino puede caer en infinitos ciclos 14 / 94
´ dual Representacion “Vector de Soporte y ´ Metodos de Kernel”
Dada las observaciones anteriores, podemos representar la ´ de decision ´ de la siguiente manera funcion
Carlos Valle Vidal ´ Introduccion
h(x) = sign(hw, xi + b) * m
´ El perceptron
= sign
Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
∑ αj yj xj , x
(1)
+
! +b
(2)
j=1 m
= sign
∑ αj yj hxj , xi + b
! (3)
j=1
SMO Kernel ridge regression Kernel PCA y CCA SVR
15 / 94
´ Algoritmo forma dual El perceptron: “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
´ (forma primal) Algoritmo 2 Algoritmo del Perceptron 1: 2: 3: 4: 5: 6:
Dado un conjunto de entrenamiento S
α ← 0; b0 ← 0 R ← max1≤i≤m ||xi || repeat for i = 1 to m do if ∑m j=1 αj yj hxj , xi + b ≤ 0 then
7: αi ← αi + 1 8: b ← b + ηyi R2 9: end if 10: end for 11: until No haya errores dentro del loop ´ (1) 12: Salida: (α, b) para definir h(x) segun ´ ecuacion
Kernel PCA y CCA SVR
16 / 94
Observaciones “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA
´ ´ sobre los datos solo ´ llega hxi , xj i Notese que la informacion ´ sus Esto significa que no necesitamos los puntos, solo productos internos. Veremos que esto se puede realizar de manera ´ de kernel computacionalmente eficaz usando una funcion ´ acerca de las posiciones relativas de los La informacion datos en el nuevo espacio esta´ codificado en los productos internos entre ellos Los productos internos entre las proyecciones de los datos de entrada en el espacio nuevo altamente dimensional pueden solucionarse computacionalmente mediante una ´ de kernel funcion
SVR
17 / 94
Problema “Vector de Soporte y ´ Metodos de Kernel”
Minsky 1969
Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
18 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
19 / 94
Mapeo impl´ıcito con kernels “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion
Podemos llevar los datos originales al espacio caracter´ıstico ´ F donde los metodos lineales capturen caracter´ısticas relevantes de los datos. Usamos el mapeo φ
φ : x ∈ X 7→ φ(x) ∈ F
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
´ ´ dual, f (x) en el Aprovechandonos de la representacion espacio caracter´ıstico queda m
f (x) = ∑ αi yi hφ(xi ), φ(x)i + b i=1
Podemos reemplazar estos productos internos en el nuevo ´ de kernel que calcule directamente espacio, por una funcion ´ de las entradas x los productos internos como una funcion originales. 20 / 94
´ de Kernel Funcion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
´ de kernel, tal que para todo x, z ∈ X Sea K funcion
K(x, z) = hφ(x), φ(z)i donde φ es el mapeo de X al espacio caracter´ıstico F ´ del espacio caracter´ıstico no afecta la La dimension ´ del kernel. computacion
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
21 / 94
´ de Kernel: Ejemplo Funcion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA
Consideremos dos puntos x = (x1 , x2 ) y z = (z1 , z2 ) en un ´ K(x, z) = hx, zi2 espacio bi-dimensional y la funcion
hx, zi2 = h(x1 , x2 ), (z1 , z2 )i2 = (x1 z1 + x2 z2 )2 = x12 z21 + x22 z22 + 2x1 x2 z1 z2 √ √ = h(x12 , x22 , 2x1 x2 ), (z21 , z22 , 2z1 z2 )i El producto interno anterior en el espacio caracter´ıstico corresponde al mapeo
√ (x1 , x2 ) 7→ φ(x1 , x2 ) = (x12 , x22 , 2x1 x2 )
SVR
22 / 94
´ de Kernel: Ejemplo(2) Funcion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
Por lo tanto
K(x, z) = hx, zi2 = hφ(x), φ(z)i ´ computar un kernel K(x,z) = hx, zid , pero genera un Es facil espacio caracter´ıstico de n+d−1 dimensiones, por lo que d computar φ(x) se vuelve infactible computacionalmente Podemos usar kernels sin conocer el mapeo φ asociado
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
23 / 94
Teorema de Mercer “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
Sea X un subconjunto compacto de Rn . Supongamos que K ´ continua simetrica ´ es una funcion tal que el operador integral
TK : L2 (X) → L2 (X) Z
´ Introduccion
(Tk f )(·) =
Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
K(·, x)f (x)dx X
´ El perceptron
Es positivo, es decir Z X×X
K(x, z)f (x)f (z)dxdz ≥ 0, ∀f ∈ L2 (X)
Podemos expandir K(x, z) en una serie con convergencia ´ uniforme sobre X × X en terminos de TK funciones propias φj ∈ L2 (X), normalizado de tal forma que ||φj ||L2 = 1 y valores propios asociados positivos λj ≥ 0 ∞
K(x, z) = ∑ λj φj (x)φj (z) j=1 24 / 94
Teorema de Mercer (2) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
La imagen de un p vector x v´ıa el mapeo impl´ıcito definido por ∞ el kernel es ∑j=1 λj φj (x). ´ Kernel estandar gaussiano (radio basal)
´ Introduccion
||x − z||2 K(x, z) = exp − 2σ2
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
Kernel polinomial de grado d
K(x, z) = (hx, zi + 1)d
SVM SMO Kernel ridge regression Kernel PCA y CCA
Red neuronal
K(x, z) = tanh (k1 hx, zi + k2 )
SVR
25 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
26 / 94
´ Sobreajuste y cotas de generalizacion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO
El principal supuesto que haremos, es que todos los puntos de los conjuntos de entrenamiento y prueba son ´ (fija, pero independientes y vienen de la misma distribucion ´ depende del desconocida) La capacidad de generalizacion ˜ de la muestra y de la capacidad efectiva de la tamano ´ hipotesis usada en el sistema (b f) Esta cantidad es una medida de flexibilidad del algoritmo, contando de cuantas formas distintas el algoritmo puede etiquetar un conjunto de datos, separando correctamente al ´ equivalente a la solucion ´ obtenida. usar una funcion
Kernel ridge regression Kernel PCA y CCA SVR
27 / 94
´ Definicion “Vector de Soporte y ´ Metodos de Kernel”
Definamos el margen funcional de una ejemplo (xi , yi ) con respecto al hiperplano, como
Carlos Valle Vidal
γi = yi (hw, xi i + b)
´ Introduccion ´ El perceptron
´ Notemos que γi > 0 implica una correcta clasificacion
Usando Kernels Sobreajuste y cotas de ´ generalizacion
´ de margen funcional por el Reemplazaremos la definicion ´ ´ lineal margen geometrico obtenemos una funcion w b ||w|| , ||w||
SVM
normalizada
SMO
´ en el espacio de entrada. Euclidiana a la frontera de decision
Kernel ridge regression
´ El margen de un conjunto de entrenamiento S es el maximo ´ margen geometrico sobre todos los hiperplanos
Kernel PCA y CCA SVR
correspondiente a la distancia
˜ del margen sera´ positivo si el conjunto de El tamano entrenamiento es linealmente separable 28 / 94
´ Margen geometrico “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
´ ´ ´ Figura: Margen geometrico de dos puntos (a la izquierda), margen de una muestra (a la derecha)
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
29 / 94
Teorema 1 “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
´ de umbral L con vector de pesos Considere una funcion unitarios sobre el producto interno en un espacio X y γ ∈ R ´ de probabilidad D sobre fijo. Para cualquier distribucion X × {−1, 1} con soporte en una bola de radio R entorno al origen, con probabilidad 1 − δ sobre m ejemplos aleatorios S, ´ cualquier hipotesis f ∈ L que tiene margen mS (f ) ≥ γ sobre S tiene errores no mayores que
2 errD (f ) ≤ ε(m, L , δ, γ) = m
64R2 emγ 32m 4 ln 2 ln 2 + ln 2 γ 8R γ δ
m > 2/ε y 64R2 /γ2 < m
Kernel PCA y CCA SVR
30 / 94
Teorema 1 (2) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
´ de Lo importante de este resultado, es que la dimension entrada de x no parece, esto significa que el resultado ´ puede aplicarse a espacios infinito dimensionales tambien Curse of dimensionality (Richard Bellman) Este teorema no dice nada respecto de data no linealmente separable ni data con ruido (que puede causar un margen estrecho)
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
31 / 94
´ Definicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
Consideremos una clase F de funciones en el dominio de los ´ con reales sobre un espacio de entrada X para clasificacion, umbral 0. Definamos la variable de holgura del margen de un ´ ejemplo (xi , yi ) ∈ X × {−1, 1} con respecto a una funcion f ∈ F y el margen γ como la cantidad
ξ((xi , yi ), f , γ) = ξi = max (0, γ − yi f (xi )) ´ de (xi , yi ) Notemos que ξi > γ implica una mala clasificacion
SMO Kernel ridge regression Kernel PCA y CCA SVR
32 / 94
´ (2) Definicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
ξ(S, f , γ) es el vector de holgura del margen de un conjunto de entrenamiento S = {(x1 , y1 ), . . . , (xm , ym )} Respecto de f y γ contiene a las variables de holgura
´ Introduccion ´ El perceptron
ξ = ξ(S, f , γ) = (ξ1 , . . . , ξm )
Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
Las variables de holgura pueden medir ruido en los datos, ˜ causado por puntos individuales en los datos (con pequenos ´ margenes o valores negativos)
SMO Kernel ridge regression Kernel PCA y CCA SVR
33 / 94
Teorema 2 “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
Consideremos funciones L con valores reales, umbral y vector de pesos sobre un producto interno X y γ ∈ R + fijo. ´ de Existe una constante c tal que para cualquier distribucion probabilidad D sobre X × {−1, 1} con soporte en una bola de radio R entorno al origen, con probabilidad 1 − δ sobre m ´ ejemplos aleatorios S, cualquier hipotesis f ∈ L tiene un error no mayor que
c errD (f ) ≤= m
R2 + ||ξ||22 2 1 ln m + ln 2 γ δ
Donde ξ = ξ(f , S, γ) es el vector de holgura respecto de f y γ
Kernel PCA y CCA SVR
34 / 94
Teorema 3 “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
Consideremos funciones L con valores reales, umbral y vector de pesos sobre un producto interno X y γ ∈ R + fijo. ´ de Existe una constante c talque para cualquier distribucion probabilidad D sobre X × {−1, 1} con soporte en una bola de radio R entorno al origen, con probabilidad 1 − δ sobre m ´ ejemplos aleatorios S, cualquier hipotesis f ∈ L tiene un error no mayor que
c errD (f ) ≤= m
R2 2 ||ξ||1 1 ln m + ln m + ln 2 γ γ δ
Donde ξ = ξ(f , S, γ) es el vector de holgura respecto de f y γ
Kernel PCA y CCA SVR
35 / 94
Observaciones “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
´ de la cota del error y toma El Teorema 2 es la generalizacion en cuenta la cantidad en la que los puntos fallan respecto del margen γ ´ La cota es en terminos de ξ, lo que sugiere que si minizamos ˜ esta cantidad, mejoraremos el desempeno. La cota no descansa en que los puntos son linealmente separables, por lo que puede existir ruido o problemas con los datos Optimizar la norma de ξ no implica directamente minimizar el numero de elementos mal clasificados, sin embargo es ´ ´ barato. computacionalmente mas Soft margin v/s hard margin (vector de holgura tiene un efecto difuso sobre el margen) 36 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
37 / 94
Clasificadores SV “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
38 / 94
Hiperplano Optimal “Vector de Soporte y ´ Metodos de Kernel”
´ Encontrar el hiperplano optimo que separa dos clases ´ equivale a resolver el problema de optimizacion
Carlos Valle Vidal
max C w,b
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
S.A.
yi (hw, xi + b) ||w||
≥ C, i = 1, . . . , m
1 Si elegimos C = ||w|| , el problema anterior es equivalente a
SVM
min ||w||2
SMO
w,b
Kernel ridge regression Kernel PCA y CCA SVR
S.A.
yi (hw, xi + b) ||w||
≥ 1, i = 1, . . . , m
1 ´ γ = ||w|| Las restricciones definen un margen de decision 2 39 / 94
Lagrangiano Primal “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA
Por lo tanto, es Lagrangiano primal es m 1 LP (w, b, α) = hw, wi − ∑ αi [yi (hw, xi i + b) − 1] 2 i=1
Donde los αi ≥ 0 son los multiplicadores de Lagrange ´ no-lineal convexo V Este es un problema de programacion ´ objetivo es convexa y los puntos que satisfacen las funcion restricciones, forman un conjunto convexo (cualquier ´ lineal define un conjunto convexo, y un conjunto restriccion ´ ´ de K restricciones lineales simultaneas define la interseccion ´ es un conjunto de los K conjuntos convexos V tambien convexo.
SVR
40 / 94
Lagrangiano dual “Vector de Soporte y ´ Metodos de Kernel”
Derivando respecto de w y b tenemos que
Carlos Valle Vidal
´ El perceptron
Sobreajuste y cotas de ´ generalizacion
LP (w, b, α)
SVR
i=1 m
=
∑ yi αi = 0 i=1
=
m 1 hw, wi − ∑ αi [yi (hw, xi i + b) − 1] 2 i=1
=
m 1 yi yj αi αj hxi , xj i − ∑ yi yj αi αj hxi , xj i + ∑ αi 2∑ i,j i,j i=1
=
∑ αi − 2 ∑ yi yj αi αj hxi , xj i
SMO
Kernel PCA y CCA
w − ∑ yi αi xi = 0
Utilizando estas relaciones en el Primal obtenemos
SVM
Kernel ridge regression
=
δLP (w, b, α) δb
´ Introduccion
Usando Kernels
m
δLP (w, b, α) δw
m
LD (w, b, α)
i=1
1
i,j
´ se conoce como Wolfe dual Tambien ´ ´ tambien ´ se logra una solucion ´ en la Analogo al perceptron, que pueden usarse kernels. 41 / 94
´ 1 Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion
Consideremos una muestra linealmente separable
S = {(x1 , y1 ), . . . , (xm , ym )} ´ Y supongamos que los parametros α resuelven el problema ´ cuadratica ´ de optimizacion
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
Maximizar W(α)
S.A. αi
1 ∑m i=1 αi − 2 ∑i,j yi yj αi αj hxi , xj i ∑m i=1 yi αi = 0 ≥0 , i = 1, . . . , m =
∗ Entonces el vector de pesos w∗ = ∑m i=1 yi αi xi forma parte del ∗ ´ hiperplano de maximo margen γ = 1/||w ||2
Kernel PCA y CCA SVR
42 / 94
´ 1 (2) Proposicion “Vector de Soporte y ´ Metodos de Kernel”
b no aparece en el dual, por lo que b∗ debe ser encontrado usando las restricciones del primal
Carlos Valle Vidal ´ Introduccion
b∗ =
maxyi =−1 (hw∗ , xi i) + maxyi =1 (hw∗ , xi i) 2
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
Las condiciones de Karush-Kunh-Tucker(KKT) afirman que el ´ optimo α∗ , w∗ , b∗ debe satisfacer
α∗i [yi (hw∗i , xi i + b∗ ) − 1] = 0, i = 1, . . . , m
SMO Kernel ridge regression Kernel PCA y CCA
Esto implica que solo para las entradas xi donde el margen funcional es uno V muy cerca del hiperplano clasificador V Support Vectors (SV).
SVR
43 / 94
´ 1 (3) Proposicion “Vector de Soporte y ´ Metodos de Kernel”
´ dual En otras palabras podemos expresar la representacion ´ ´ en terminos de este subconjunto de parametros
Carlos Valle Vidal ´ Introduccion
f (x, α∗ , b∗ ) =
Sobreajuste y cotas de ´ generalizacion SVM
∑ yi α∗i hxi , xi + b∗ i=1
´ El perceptron Usando Kernels
m
=
∑ yi α∗i hxi , xi + b∗
i∈SV
Los multiplicadores de Lagrange miden la importancia de ´ final cada ejemplo de entrenamiento en la solucion
SMO Kernel ridge regression
´ αi media el numero Perceptron de equivocaciones del ´ ´ i-esimo ejemplo
Kernel PCA y CCA SVR
44 / 94
´ 1 (4) Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
Otra importante consecuencia de las KKT para j ∈ SV
! yj f (xj , α∗ , b∗ ) = yj
∑ yi α∗i hxi , xi + b∗
=1
i∈SV ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
Por lo tanto, podemos expresar ||w|| y el margen como ´ de los multiplicadores α funcion
hw∗ , w∗ i =
Kernel ridge regression Kernel PCA y CCA SVR
∑ yi yj α∗i α∗j hxi , xj i i,j
SVM SMO
m
=
∑ α∗j yj ∑ yi α∗i hxi , xj i
j∈SV
=
∑
i∈SV ∗ αj (1 − yj b∗ )
j∈SV
=
∑ α∗i
i∈SV
45 / 94
´ 2 Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion
Consideremos la muestra S{(x1 , y1 ), . . . , (xm , ym )} y supongamos que α∗ y b∗ resuelven el problema de ∗ ´ dual. Entonces w = ∑m optimizacion i=1 yi αi xi forma parte del ´ hiperplano con margen geometrico
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
!−1/2 γ = 1/||w||2 =
∑
α∗i
i∈SV
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
46 / 94
´ 1 usando kernels Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron
Consideremos una muestra S = {(x1 , y1 ), . . . , (xm , ym )} linealizable en el espacio caracter´ıstico definido por el kernel
K(x, z) ´ Y supongamos que los parametros α resuelven el problema ´ cuadratica ´ de optimizacion
Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
Maximizar W(α)
S.A. αi
1 ∑m i=1 αi − 2 ∑i,j yi yj αi αj K(xi , xj ) ∑m i=1 yi αi = 0 ≥0 , i = 1, . . . , m =
SMO Kernel ridge regression Kernel PCA y CCA SVR
47 / 94
´ 1 usando kernels (2) Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
´ dada por sign(f (x)), donde Entonces la regla de decision m ∗ f (x) = ∑i=1 yi αi K(xi , x) + b∗ es equivalente al hiperplano de ´ maximo margen en el espacio caracter´ıstico impl´ıcito definido por el kernel K(x, z) y que el hiperplano tiene margen ´ geometrico
!−1/2 γ=
∑ α∗i
i∈SV
´ Notese que un Kernel que satisface las condiciones de Mercer, es equivalente a que la matriz (K(xi , xj ))m i,j sea definida positiva. Esto transforma el problema a convexo ya que la matriz ´ es definida positiva V solucion ´ unica (yi yj K(xi , xj ))m ´ i,j tambien ´ usando los SV El problema se puede comprimir solo 48 / 94
Teorema “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron
Consideremos funciones L reales con umbral con vector de pesos unitario sobre un espacio X con producto interno. Para ´ de probabilidad D sobre X × {−1, 1}, cualquier distribucion con probabilidad 1 − δ sobre m ejemplos de S, el hiperplano maximal tiene un error menor que
Usando Kernels Sobreajuste y cotas de ´ generalizacion
errD (f ) ≤
em 1 m + ln d ln m−d d δ
SVM
Donde d es el numero de SV. ´
SMO
´ del Kernel Eleccion
Kernel ridge regression Kernel PCA y CCA SVR
49 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
50 / 94
SMO (Soft margin Optimization) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion
´ de Hard Intenta mejorar el problema de generalizacion Margin ´ es Cuyo problema de optimizacion
´ El perceptron
Minimizarw,b hw, wi
Usando Kernels
S.A: yi (hw, xi i + b)
Sobreajuste y cotas de ´ generalizacion SVM
≥ 1, i = 1, . . . , m
Introduciremos variables de holgura permitiendo violar las restricciones
SMO Kernel ridge regression Kernel PCA y CCA SVR
S.A: yi (hw, xi i + b)
≥ 1 − ξi , i = 1, . . . , m
ξi ≥ 0, i = 1, . . . , m ˜ de las De la misma forma necesitamos controlar el tamano violaciones ξi 51 / 94
Soft Margin norma 2 “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
´ es Cuyo problema de optimizacion Minimizarw,b hw, wi S.A: yi (hw, xi i + b)
2 + C ∑m i=1 ξi ≥ 1 − ξi , i = 1, . . . , m ξi ≥ 0, i = 1, . . . , m
(4)
´ y el C controla el equilibrio entre los errores de clasificacion margen. El Lagrangiano primal de este problema es
SVM SMO Kernel ridge regression Kernel PCA y CCA
m 1 C m L(w, b, ξ, α) = hw, wi+ ∑ ξ2i − ∑ αi [yi (hw, xi i + b) − 1 + ξi ] 2 2 i=1 i=1
donde αi ≥ 0 son los multiplicadores de Lagrange
SVR
52 / 94
Soft Margin norma 2 (2) “Vector de Soporte y ´ Metodos de Kernel”
Para encontrar la forma dual debemos derivar respecto a w, ξ yb
Carlos Valle Vidal
m
∂L(w, b, ξ, α) ∂w
=
w − ∑ yi αi xi = 0 i=1
´ Introduccion
∂L(w, b, ξ, α) ∂ξ ∂L(w, b, ξ, α) ∂b
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
Cξ − α = 0
=
∑ yi αi = 0
m i=1
Reemplazando estas relaciones en el primal obtenemos la ´ objetivo siguiente funcion m
L(w, b, ξ, α)
=
Kernel PCA y CCA SVR
=
i=1 m
=
1
1
1
∑ αi − 2 ∑ yi yj αi αj hxi , xj i + 2C hα, αi − 2C hα, αi i,j
1
1
∑ αi − 2 ∑ yi yj αi αj hxi , xj i − 2C hα, αi
i=1
i,j
53 / 94
Soft Margin norma 2 (3) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
Maximizar sobre α es equivalente a maximizar m
1 1 W(α) = ∑ αi − ∑ yi yj αi αj hxi , xj i + δij 2 i,j C i=1 Donde δij es la δ de Kronecker
( 1 si i = j δij = 0 e.t.o.c.
SMO Kernel ridge regression
´ Usando Kernels obtenemos la siguiente proposicion
Kernel PCA y CCA SVR
54 / 94
´ Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
Considerando la muestra de entrenamiento S Usando el espacio caracter´ıstico inducido por el kernel K(x, z) y supongamos que α∗ resuelve el problema de ´ cuadratico: ´ optimizacion m
1 1 W(α) = ∑ αi − ∑ yi yj αi αj hxi , xj i + δij 2 i,j C i=1 m
S.A :
∑ yi αi = 0 i=1
αi ≥ 0, i = 1, . . . , m
Kernel PCA y CCA SVR
55 / 94
´ (2) Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO
∗ ∗ ∗ Sea f (x) = ∑m i=1 yi αi K(xi , x) + b , donde b es escogido de manera tal que f (xi ) = 1 − α∗i /C para cualquier i con α∗i 6= 0. ´ definida por sign(f (x)) es Entonces la regla de decision equivalente al hiperplano en el espacio caracter´ıstico definido impl´ıcitamente por K(x, z) el cual resuelve el problema de ´ (4), donde las variables de holgura estan ´ optimizacion ´ definidas respecto del margen geometrico
γ=
∑
i∈SV
α∗i −
!−1/2 1 ∗ ∗ hα , α i C
Kernel ridge regression Kernel PCA y CCA SVR
56 / 94
´ (3) Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
´ El valor de b∗ es escogido usando la relacion ´ Demostracion: αi = Cξi y por referencia a las restricciones del primal generadas por las condiciones complementarias de Karush Kuhn Tucker αi [yi (hwi , xi i + b) − 1 + ξi ] = 0, i = 1, . . . , m
Esto se mantiene al computar la norma de w∗ la cual define ˜ del margen geometrico ´ el tamano hw∗ , w∗ i
m
=
i,j
=
SMO Kernel ridge regression
∑ yi yj α∗i α∗j K(xi , xj ) ∑ α∗j yj ∑ yi α∗i K(xi , xj )
j∈SV
=
∑
i∈SV ∗ αj (1 − ξ∗j − yj b∗ )
j∈SV Kernel PCA y CCA
=
∑ α∗i − ∑ α∗i ξ∗i
i∈SV
SVR
=
i∈SV
1
∑ α∗i − C hα∗i , α∗i i
i∈SV
57 / 94
´ (4) Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
El problema es equivalente a usar hardmargin, solamente hay que adicionar 1/C en la diagonal de la matriz de kernel. Esto provoca el efecto de agregar 1/C a los valores propios de la matriz, mejorando su condicionamiento Usar un suavizamiento con norma 2, equivale a cambiar el kernel
K(x, z) = K(x, z) +
1 δx (z) C
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
58 / 94
Soft Margin norma 1 “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
´ es Cuyo problema de optimizacion Minimizarw,b hw, wi S.A: yi (hw, xi i + b)
´ Introduccion
+ C ∑m i=1 ξi ≥ 1 − ξi , i = 1, . . . , m ξi ≥ 0, i = 1, . . . , m
(5)
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO
El Lagrangiano primal de este problema es m m m 1 L(w, b, ξ, α) = hw, wi + C ∑ ξi − ∑ αi [yi (hw, xi i + b) − 1 + ξi ] − ∑ ri ξi 2 i=1 i=1 i=1
donde αi ≥ 0 y ri ≥ 0
Kernel ridge regression Kernel PCA y CCA SVR
59 / 94
Soft Margin norma 1 (2) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
Para encontrar la forma dual debemos derivar respecto a w, ξ yb ∂L(w, b, ξ, α, r) ∂w
m
=
w − ∑ yi αi xi = 0 i=1
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA
∂L(w, b, ξ, α, r) ∂ξ ∂L(w, b, ξ, α, r) ∂b
=
C − αi ri = 0
=
∑ yi αi = 0
m i=1
Reemplazando estas relaciones en el primal obtenemos la ´ objetivo siguiente funcion m
L(w, b, ξ, α, r) = ∑ αi − i=1
1 yi yj αi αj hxi , xj i 2∑ i,j
SVR
60 / 94
Soft Margin norma 1 (3) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion
´ ´ Observemos que esta es identica al problema de maximo ´ ´ margen a excepcion de la restriccion C − αi − ri = 0 junto con ri ≥ 0, lo que fuerza αi ≤ C Las condiciones KKT son
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
αi [yi (hxi , wi + b) − 1 + ξi ] = 0, i = 1, . . . , m ξi (αi − C) = 0, i = 1, . . . , m
SVM
Observemos que ξi 6= 0 ⇒ αi = C
SMO
Los puntos con ξi 6= 0 tienen un margen menor a 1/||w||.
Kernel ridge regression Kernel PCA y CCA SVR
61 / 94
´ Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion
Considerando la muestra de entrenamiento S Usando el espacio caracter´ıstico inducido por el kernel K(x, z) y supongamos que α∗ resuelve el problema de ´ cuadratico: ´ optimizacion
´ El perceptron Usando Kernels
m
Maximizar W(α)
Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
=
i=1 m
S.A :
1
∑ αi − 2 ∑ yi yj αi αj K(xi , xj ) i,j
∑ yi αi = 0 i=1
C ≥ αi ≥ 0, i = 1, . . . , m
Kernel PCA y CCA SVR
62 / 94
´ (2) Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
∗ ∗ ∗ Sea f (x)) ∑m i=1 yi αi K(xi , x) + b , donde b es escogido de manera tal que yi f (xi ) = 1 para cualquier i con C > α∗i > 0. ´ definida por sign(f (x)) es Entonces la regla de decision equivalente al hiperplano en el espacio caracter´ıstico definido impl´ıcitamente por K(x, z) el cual resuelve el problema de ´ (5), donde las variables de holgura estan ´ optimizacion ´ definidas respecto del margen geometrico
!−1/2 γ=
∑
yi yj α∗i α∗j K(xi , xj )
i,j∈SV
b∗ se obtiene a partir de las KKT las que si C > α∗i > 0, ξ∗i = 0 y yi (hxi , w∗ i + b∗ ) − 1 + ξ∗i = 0 63 / 94
´ (3) Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
´ La norma de w∗ esta´ dada por la expresion
hw∗ , w∗ i =
i,j
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
m
∑ yi yj α∗i α∗j K(xi , xj )
=
∑ ∑ yi yj α∗i α∗j K(xi , xj )
j∈SV i∈SV
´ para αi V box constraint Restriccion Limitar influencia de outliers Ambas formas de soft margin obtienen soluciones basadas en hard margin
Kernel PCA y CCA SVR
64 / 94
ν-SVM “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion
Un problema es determinar la constante C Este problema equivale a encontrar 0 ≤ ν ≤ 1 en el problema ´ de optimizacion Maximizar W(α)
= −
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
1 yi yj αi αj K(xi , xj ) 2∑ i,j
m
S.A :
∑ yi αi = 0 i=1 m
∑ αi ≥ ν i=1
1/m ≥ αi ≥ 0, i = 1, . . . , m ´ del conjunto de Podemos ver esto como la proporcion entrenamiento cuyo margen es mayor que ν ν no depende de la escala del espacio caracter´ıstico, sino ´ del nivel de ruido en los datos. solo
65 / 94
´ ´ SVM como metodo de penalizacion “Vector de Soporte y ´ Metodos de Kernel”
Usando f (x) = hw, φ(x)i + b consideremos el problema de ´ optimizacion
Carlos Valle Vidal
m
min ∑ [1 − yi f (xi )]+ + λ||w||2
´ Introduccion
b,w
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
(6)
i=1
Donde + indica la parte positiva. Se puede demostrar que ´ es la misma que (5) con lambda = 1/(2C) la solucion ´ de funciones de perdida ´ Tabla: Comparacion
SMO Kernel ridge regression Kernel PCA y CCA SVR
´ de perdida ´ Funcion
L(y,f(x))
´ a minimizar Funcion
Log verosimilitud
log(1 + e−yf (x) )
MSE
(y − f (x))2
SVM
[1 − yi f (xi )]+
f (x) = log Pr(y=−1|X) f (x) = Pr(y ( = +1|X) − Pr(y = −1|X) +1 si Pr(y = +1|X) ≥ 12 f (x) = −1 e.t.o.c.
Pr(y=+1|X)
66 / 94
´ ´ SVM como metodo de penalizacion(2) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
67 / 94
´ de estimacion ´ Kernels y la funcion “Vector de Soporte y ´ Metodos de Kernel”
Recordemos que ∞
Carlos Valle Vidal
K(x, z) = ∑ λj hj (x)hj (z) j=1
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
Y φj (x) =
p p λj hj (x) entonces con θj = λj wj
Podemos reescribir (6) como m
SVM SMO Kernel ridge regression
"
∞
#
min ∑ 1 − yi (b + ∑ θj hj (xi )) b,θ i=1
j=1
θ2 j=1 λj ∞
+C ∑ +
Kernel PCA y CCA SVR
68 / 94
´ de estimacion ´ (2) Kernels y la funcion “Vector de Soporte y ´ Metodos de Kernel”
´ finito dimensional La teor´ıa garantiza que existe una solucion de la forma m
Carlos Valle Vidal
f (x) = b + ∑ αi K(x, xi ) i=1
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
´ equivalente En particular existe un criterio de optimizacion m
min ∑ (1 − yi f (xi ))+ + CαT Kα α
i=1
Donde K es una matriz m × m con entradas Kij = K(xi , xj ) ´ general Estos modelos se pueden expresar de manera mas m
min ∑ (1 − yi f (xi ))+ + CJ(f ) f ∈H i=1
Donde H es el espacio de funciones y J(f ) es el regularizador del espacio 69 / 94
´ de la dimensionalidad SVM y la maldicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
70 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
71 / 94
Kernel ridge regression “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
Ridge regression + Kernels V Proceso Gaussiano ´ de regresion ´ lineal Necesitamos encontrar una funcion f (x) = hw, xi que entrene la muestra S, donde las etiquetas son numeros reales, es decir, yi ∈ R. La calidad del modelo se mide por el cuadrado de las desviaciones yi − hw, xi i junto con tratar de mantener la ´ lo mas ´ pequena ˜ posible. norma de la funcion
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
72 / 94
Kernel ridge regression (2) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion
El resultado se describe en el siguiente problema de ´ optimizacion Minimizar S.A:
2 λ||w||2 + ∑m i=1 ξi yi − hw, xi i = ξi , i = 1, . . . , m
(7)
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
Del cual se deriva el Lagrangiano m
MinimizarL(w, ξ, α) = λ||w||2 +
m
∑ ξ2i + ∑ αi (yi − hw, xi i − ξi ) i=1
i=1
SMO Kernel ridge regression Kernel PCA y CCA SVR
Derivando tenemos que
w=
1 2λ ∑m i=1 αi xi
y ξi =
αi 2 73 / 94
Kernel ridge regression (3) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron
Reemplazando estas relaciones obtenemos el dual m
Maximizar W(α) =
1
m
1
∑ yi αi − 4λ ∑ αi αj hxi , xj i − 4 ∑ α2i
i=1
i,j
Reescribiendo de manera vectorial tenemos
Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
W(α) = yT α −
1 T 1 α Kα − αT α 4λ 4
Donde K es la matriz Gram Kij = hxi , xj i o la matriz de Kernels Kij = K(xi , xj ) si trabajamos en el espacio caracter´ıstico
Kernel PCA y CCA SVR
74 / 94
Kernel ridge regression (4) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
´ Derivando respecto de α la siguiente condicion
−
1 1 Kα − α + y = 0 2λ 2
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA
´ Obteniendo la solucion
α = 2λ(K + λI)−1 y ´ de regresion ´ Y la funcion
f (x) = hw, xi = yT (K + λI)−1 k Donde k es el vector con entradas ki = hxi , xi, i = 1, . . . , m
SVR
75 / 94
´ Proposicion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO
´ sobre la Supongamos que queremos hacer una regresion muestra de entrenamiento S Usando el espacio caracter´ıstico definido impl´ıcitamente por el kernel K(x, z), y sea f (x) = yT (K + λI)−1 k donde K es una matriz m × m con entradas Kij = K(xi , xj ) y k es el vector con entradas ki = K(xi , x). ´ f (x) es equivalente al hiperplano en el Entonces la funcion espacio caracter´ıstico impl´ıcitamente definido por el kernel ´ ridge K(x, z) que resuelve el problema de optimizacion regression (7)
Kernel ridge regression Kernel PCA y CCA SVR
76 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
77 / 94
Kernel PCA y CCA “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
´ Veremos dos tecnicas que pueden ser adaptadas para ser usadas con Kernels ´ Analisis de componentes principales (PCA), para reducir la ´ de los datos. dimension ´ ´ Canonica ´ Analisis de correlacion (CCA), que ayuda a encontrar correlaciones entre los datos formados por dos pares de vectores o entre dos dataset cuyos elementos ´ forman una biyeccion.
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
78 / 94
´ Analisis de componentes principales (PCA) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA
´ ´ ´ Es una tecnica clasica para analizar data de alta dimension V extraer su estructura oculta V Encontrar un subconjunto ˜ de coordenadas que describen la mayor parte de (pequeno) ´ de los datos la informacion ´ Se puede demostrar que las direcciones que proveen mas ´ de los datos son los k vectores propios informacion principales de los datos V Para un k fijo, minimizan la ´ distancia cuadratica entre los datos originales y los datos transformados. Los vectores propios se llaman ejes principales de los datos y las nuevas coordenadas de cada punto se obtienen mediante ´ de este en los k ejes principales. la proyeccion
SVR
79 / 94
´ Analisis de componentes principales (PCA) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
´ Como antes, representabamos los vectores en la forma dual, como combinaciones de los datos v = ∑i αi xi y necesitamos ´ encontrar los parametros αi Dado un conjunto de datos no etiquetados S = {x1 , . . . , xm } ´ centrados ∑i xi = 0 que estan La matriz de covarianza emp´ırica se define como
C=
1 xi xiT m−1 ∑ i
SMO Kernel ridge regression
Y es una matriz semi definida positiva.
Kernel PCA y CCA SVR
80 / 94
´ Analisis de componentes principales (PCA) (2) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
Sus vectores y valores propios pueden ser escritos como
λv = Cv = ∑ hxi , vixi i
´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
´ lineal Cada vector propio puede escribirse como combinacion de los ejemplos de entrenamiento
v = ∑ αi xi i
´ dual que Para algun ´ α y as´ı permitir una representacion utilice kernels. Usando los k primeros vectores propios genera la mejor ´ que minimiza la suma de las 2-normas de los aproximacion residuos de los ejemplos de entrenamiento. 81 / 94
´ Analisis de componentes principales (PCA) (3) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM
´ sobre el espacio Realizando la misma operacion ´ caracter´ıstico V usar imagenes de los puntos φ(xi ), con simples manipulaciones podemos encontrar los coeficientes αn de los n vectores propios pueden obtenerse al resolver el problema de valores propios
mλα = Kα ´ 1 = λn hαn , αn i, n = 1, . . . , n E imponiendo la normalizacion
SMO Kernel ridge regression Kernel PCA y CCA SVR
82 / 94
´ Analisis de componentes principales (PCA) (3) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
Aunque no tengamos las coordenados expl´ıcitas de los vectores propios, podemos calcular las proyecciones de los ejemplos sobre los n vectores propios vn de la siguiente manera m
hφ(x), vn i = ∑ αni K(xi , x) i=1
´ es todo lo que necesitamos de nuestros Esta informacion datos para extraer regularidades.
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
83 / 94
´ ´ Canonica ´ Analisis de correlacion (CCA) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA
´ entre los elementos de dos Asumamos una biyeccion conjuntos, que posiblemente corresponden a diferentes descripciones del mismo objeto ( Ej: dos vistas del mismo objeto tridimensional, o dos versiones del mismo documento en idiomas distintos) Dado dos pares S = {(x1 , x2 )i } CCA busca combinaciones ´ lineales de variables en cada conjunto que con maxima ´ correlacion
∑ ai bi r= q i ∑i a2i ∑i b2i
Donde {ai } y {bi } son realizaciones de la variable aleatoria con media cero
SVR
84 / 94
´ ´ Canonica ´ Analisis de correlacion (CCA) (2) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
Dado dos conjuntos de vectores xi1 ∈ X1 y
xi2 ∈ X2 , i = 1, . . . , m
Encontraremos vectores w1 ∈ X1 y w2 ∈ X2 tal que la ´ de los datos en esos vectores tenga maxima ´ proyeccion ´ correlacion Resolver esto es equivalente a transformar el problema en
SVM
0 C12 C21 0
w1 w2
=λ
C11 0 0 C22
w1 w2
SMO Kernel ridge regression Kernel PCA y CCA
Donde
m
j
Cjk = ∑ xi (xik )T , j, k = 1, 2 i=1
SVR
85 / 94
´ ´ Canonica ´ Analisis de correlacion (CCA) (2) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
Se pueden introducir kernels usando los mismos procedimientos vistos anteriormente
w1 = ∑i α1i φ(xi1 ) y w2 = ∑i α2i φ(xi2 ) lo que conduce al problema dual en α 1 2 1 0 K1 K2 α K1 0 α =λ K2 K1 0 α2 α2 0 K22 Donde K1 y K2 son las matrices de kernel para los vectores ´ en xi1 ∈ X1 y xi2 ∈ X2 , i = 1, . . . , m asumiendo que estan ´ esto es, la entrada ij en cada matriz corresponde biyeccion, al mismo par de puntos. Resolviendo este problema podemos encontrar transformaciones no-lineales de los datos que maximicen la ´ entre ellos. correlacion 86 / 94
Temario “Vector de Soporte y ´ Metodos de Kernel”
1
´ Introduccion
Carlos Valle Vidal
2
´ El perceptron
3
´ impl´ıcita usando Funciones de Kernels Transformacion
4
´ Sobreajuste y cotas de generalizacion
Sobreajuste y cotas de ´ generalizacion
5
SVM
SVM
6
SMO
Kernel ridge regression
7
Kernel ridge regression
Kernel PCA y CCA
8
Kernel PCA y CCA
SVR
9
SVR
´ Introduccion ´ El perceptron Usando Kernels
SMO
87 / 94
Support vector regression “Vector de Soporte y ´ Metodos de Kernel”
´ Recordemos el modelo de regresion
f (x) = xT β + β0
Carlos Valle Vidal ´ Introduccion
´ no lineal Para estimar β consideremos la generalizacion
´ El perceptron
N λ H(β, β0 ) = ∑ V(yi − f (xi )) + ||β||2 2 i=1
Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
Donde
( 0 si |t| < ε Vε (t) = |t| − ε e.t.o.c.
Kernel PCA y CCA SVR
88 / 94
Support vector regression (2) “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron
˜ residuos Medida de error ε-no sensible V ignorar pequenos ´ robusta Estimacion
( r2 /2 si r ≤ c vH (r) = 2 c|r| − c /2 si r > c
Usando Kernels Sobreajuste y cotas de ´ generalizacion
´ de Huber menos sensible a outliers Funcion
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
89 / 94
Support vector regression (3) “Vector de Soporte y ´ Metodos de Kernel”
´ es de la forma Si b β, b β0 minimizan H la solucion N
b β
Carlos Valle Vidal
bf (x)
´ El perceptron
Sobreajuste y cotas de ´ generalizacion SVM SMO
∑ (αb∗i − αbi )xi
(8)
i=1 N
´ Introduccion
Usando Kernels
= =
∑ (αb∗i − αbi )hx, xi i + β0
(9)
i=1
b ∗i son positivos y resuelven el problema de Donde αi , α ´ cuadratica ´ programacion N
N
N
i=1
i=1
i,j
min ε ∑ (α∗i + αi ) − ∑ yi (α∗i + αi ) + ∑ (α∗i + αi )(α∗i + αi )hxi , xj i
αi ,b α∗i
S.A. 0 ≤ αi , α∗i ≤ 1/λ
Kernel ridge regression
N
∑ (α∗i + αi ) = 0
Kernel PCA y CCA
i=1
αi α∗i = 0
SVR
Usar Vε (r/σ) 90 / 94
´ y kernels Regresion “Vector de Soporte y ´ Metodos de Kernel”
´ de regresion ´ en Supongamos que aproximamos una funcion ´ terminos de funciones base {φm (x)}, m = 1, 2, . . . , M
Carlos Valle Vidal ´ Introduccion
M
f (x)
∑ βm φm (x) + β0 m=1
´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
Para estimar β y β0 minimizamos N
H(β, β0 ) = ∑ V(yi − f (xi )) + i=1
λ β2 2∑ m
´ de Para una medida de error general V(r) la solucion bf (x) = ∑ βm φm (x) + β0 tiene la forma N
bf (x) = ∑ b ai K(x, xi ) i=1
Donde K(x, y) = ∑M m=1 φm (x)φm (y) 91 / 94
´ y kernels (2) Regresion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion
Por ejemplo, para V(r) = r2 . Sea H una matriz de funciones ´ base de n × m donde el im - esimo elemento φm (xi ) y supongamos que M N Por simplicidad asumamos β0 = 0 , o que la constante es absorbida en φ ´ Estimemos β minimizando el error cuadratico
H(β) = (y − Hβ)T (y − Hβ) + λ||β||2
SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
´ es La solucion
b y = Hb β Donde b β esta´ determinado por
−H T (y − H b β) + λb β=0 92 / 94
´ y kernels (3) Regresion “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal
Sin embargo
Hb β = (HH T + λI)−1 HH T y
´ Introduccion
Donde la matriz HH T de N × N consiste en
´ El perceptron
{HH T }ij = K(xi , xj )
Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression
´ de un x arbitrario debe Se puede probar que la prediccion satisfacer
bf (x) = φ(x)T b β N
=
i=1
Kernel PCA y CCA SVR
∑ αbi K(x, xi )
b = (HH T + I)−1 y Donde α 93 / 94
Consultas y Comentarios “Vector de Soporte y ´ Metodos de Kernel” Carlos Valle Vidal ´ Introduccion ´ El perceptron Usando Kernels Sobreajuste y cotas de ´ generalizacion SVM SMO Kernel ridge regression Kernel PCA y CCA SVR
94 / 94