Métodos de kernel
Luis F. Lago Fernández
Aprendizaje Automático II, GCID, EPS, UAM
Luis F. Lago Fernández Métodos de kernel
Contenidos
1 Modelos paramétricos vs no paramétricos
2 Regresión lineal regularizada (kernel ridge regression)
Formulación primal
Formulación dual
3 Funciones de kernel
Luis F. Lago Fernández Métodos de kernel
Lecturas sugeridas
K. Murphy 11.3. Ridge regression
K. Murphy 17.1. Mercer kernels
K. Murphy 17.3.9. Kernel ridge regression
Luis F. Lago Fernández Métodos de kernel
Aprendizaje supervisado (repaso)
El conjunto de entrenamiento contiene datos etiquetados:
D = {(x1 , t1 ), (x2 , t2 ), ..., (xN , tN )}
xi es el vector de características para el dato i (entradas,
atributos, variables independientes)
ti es la variable objetivo para el dato i (salida, etiqueta,
variable dependiente)
N es el número total de datos o patrones
El objetivo es predecir la variable objetivo, ti , dado el vector de
características, xi
Luis F. Lago Fernández Métodos de kernel
Modelos paramétricos (repaso)
Un clasificador (regresor) es una función f (x, θ) que asigna a
cada patrón xi una estimación de la variable objetivo asociada
al mismo: yi = f (xi , θ) ≈ ti
El entrenamiento del modelo consiste en ajustar los parámetros,
θ, para minimizar el riesgo empírico:
N
1 X
L(θ) = l(yi , ti )
N i=1
La función de coste o pérdida, l(yi , ti ), mide cuánto cuesta
decir yi en vez de ti
Una vez ajustados los parámetros, podemos prescindir de los
datos de entrenamiento para hacer predicciones sobre datos
nuevos
Luis F. Lago Fernández Métodos de kernel
Ejemplos de modelos paramétricos
Regresión lineal
Modelo: yi = wT xi + b
Función de coste: l(yi , ti ) = 12 (yi − ti)2 (MSE)
Regresión logística (clasificación binaria)
Modelo: yi = σ(wT xi + b)
Función de coste: l(yi , ti ) = −ti log yi − (1 − ti ) log(1 − yi )
(cross-entropy)
Ambos modelos son lineales, pero pueden usarse para abordar
problemas no lineales transformando el espacio de atributos (p.e.
regresión polinómica)
Luis F. Lago Fernández Métodos de kernel
Modelos no paramétricos
No hay parámetros ajustables
Un subconjunto de los datos de entrenamiento se utiliza
durante la fase de predicción
No es necesario entrenar el modelo para ajustar parámetros,
pero a cambio la predicción es más lenta
El ejemplo más característico de este tipo de algoritmos es
k-Nearest Neighbours
Luis F. Lago Fernández Métodos de kernel
Formulación dual
Algunos modelos paramétricos lineales se pueden reformular
usando una representación dual
Las predicciones se construyen como una combinación lineal de
funciones de kernel evaluadas sobre un subconjunto de los
datos de entrenamiento
En cierto modo estamos expresando el modelo paramétrico de
forma no paramétrica
Uno de estos modelos es el modelo de regresión lineal
regularizada (con regularización ridge)
Luis F. Lago Fernández Métodos de kernel
Regresión lineal regularizada (ridge)
Sea D = {(x1 , t1 ), (x2 , t2 ), ..., (xN , tN )} el conjunto de datos
de entrenamiento
Y sea ϕ(xi ) = (1, ϕ1 (xi ), ..., ϕM (xi ))T es el vector de atributos
para el punto xi en el espacio transformado
El modelo de regresión es
M
X
y (xi ) = wj ϕj (xi ) = wT ϕ(xi )
j=0
Con w = (w0 , w1 , ..., wM )T el vector de parámetros
Luis F. Lago Fernández Métodos de kernel
Regresión lineal regularizada (ridge)
La función de coste es
N
1X λ
J(w) = {ti − wT ϕ(xi )}2 + ||w||2
2 i=1 2
λ es un hiperparámetro que mide la fuerza de la regularización
El mínimo de J(w) se da para
∂J(w)
= 0, k = 0, ..., M
∂wk
La solución se puede expresar de dos formas diferentes, las
formulaciones primal y dual
Luis F. Lago Fernández Métodos de kernel
Formulación primal
La solución se plantea como una suma sobre atributos:
M
X
y (x) = wj ϕj (x) = w0 ϕ0 (x) + w1 ϕ1 (x) + ... + wM ϕM (x)
j=0
El vector de parámetros, w, es la solución de la ecuación
(A + λI)w = ΦT t
Con t = (t1 , t2 , ..., tN )T
Luis F. Lago Fernández Métodos de kernel
Formulación primal
La matriz Φ es la matriz de diseño:
ϕ0 (x1 ) ϕ1 (x1 ) ... ϕM (x1 )
ϕ0 (x2 ) ϕ1 (x2 ) ... ϕM (x2 )
Φ=
... ... ... ...
ϕ0 (xN ) ϕ1 (xN ) ... ϕM (xN )
Y A = ΦT Φ es una matriz M × M
Luis F. Lago Fernández Métodos de kernel
Formulación dual
La solución se plantea como una suma sobre los puntos del
conjunto de entrenamiento:
N
X
y (x) = ai k(xi , x) = a1 k(x1 , x) + ... + aN k(xN , x)
i=1
Donde k(xi , x) = ϕ(xi )T ϕ(x) es una función de kernel, que
representa un producto escalar en el espacio de atributos
Luis F. Lago Fernández Métodos de kernel
Formulación dual
Para obtener los coeficientes ai debemos resolver la ecuación
(K + λI)a = t
Donde K = ΦΦT es una matriz N × N (matriz de kernel)
Y a = (a1 , a2 , ..., aN )T
La matriz de kernel contiene los productos escalares entre los
vectores de atributos de todos los puntos del conjunto de
entrenamiento:
Kij = k(xi , xj ) = ϕ(xi )T ϕ(xj )
Luis F. Lago Fernández Métodos de kernel
Primal vs dual
El problema dual es en general más difícil de resolver que el
problema primal, pues normalmente N ≫ M
Sin embargo, presenta las siguientes ventajas:
1 Si existe la función de kernel k(x, z) = ϕ(x)T ϕ(z), no es
necesario evaluar evaluar ϕ(x) de manera explícita en ningún
momento (kernel trick)
2 La complejidad del problema no depende de la dimensión del
espacio de atributos, sino solo del número de puntos de
entrenamiento. Podemos usar espacios de atributos de
dimensión arbitrariamente alta al mismo coste
Luis F. Lago Fernández Métodos de kernel
Derivación de las soluciones primal y dual
Puede consultarse una derivación completa de las soluciones primal
y dual para el problema de regresión lineal con regularización ridge
en las notas kernel_ridge.pdf disponibles en Moodle
Luis F. Lago Fernández Métodos de kernel
Algunas funciones de kernel típicas
El kernel polinómico:
k(x, z) = (xT z + C )P
Por ejemplo, para x = (x1 , x2 ), C = 1 y P = 2 tenemos:
k(x, z) = (xT z + 1)2 = (x1 z1 + x2 z2 + 1)2
Luis F. Lago Fernández Métodos de kernel
Algunas funciones de kernel típicas
Que se puede expresar como:
z12
2
√ z2
√ √ √
√2z1 z2
2 2
k(x, z) = (x1 , x2 , 2x1 x2 , 2x1 , 2x2 , 1)
√2z1
2z2
1
La transformación asociada es:
√ √ √
ϕ(x) = (x12 , x22 , 2x1 x2 , 2x1 , 2x2 , 1)T
Luis F. Lago Fernández Métodos de kernel
Algunas funciones de kernel típicas
El kernel gausiano (RBF):
!
||x − z||2
k(x, z) = exp −
2σ 2
Por ejemplo, para x = x , y σ = 1 tenemos:
!
(x − z)2
k(x , z) = exp − = exp (−x 2 /2) exp (−z 2 /2) exp (xz)
2
Luis F. Lago Fernández Métodos de kernel
Algunas funciones de kernel típicas
Que se puede expresar como:
∞
2 2
X x nz n
k(x , z) = exp (−x /2) exp (−z /2)
n=0
n!
La transformación asociada es:
x2 x3
ϕ(x ) = exp (−x 2 /2)(1, x , √ , √ , ...)T
2 6
Y corresponde a un espacio de atributos de dimensión infinita
Luis F. Lago Fernández Métodos de kernel
Ejemplos
(ver notebooks kernel_methods_1.ipynb y kernel_methods_2.ipynb)
Luis F. Lago Fernández Métodos de kernel