Kernels

Kernels

Los clasificadores lineales son geniales, pero ¿qué pasa si no existe

un límite de decisión lineal? Resulta que existe una forma elegante
de incorporar las no linealidades a la mayoría de los clasificadores
lineales.
En las Máquinas de Vectores de Soporte (SVM), un núcleo (o
kernel) es una función matemática crucial que permite que el
algoritmo funcione en espacios de alta dimensionalidad sin
necesidad de calcular explícitamente las coordenadas de los datos
en ese espacio.
Ampliación de características
artesanales/Handcrafted Feature Expansion

Podemos hacer que los clasificadores lineales sean no lineales

aplicando funciones base (transformaciones de características) a los
vectores de características de entrada. Formalmente para un vector
x ∈ ℝ𝑑 aplicamos la transformación x → 𝜙(x) donde 𝜙(x) ∈ ℝ𝐷 ,
tal que 𝐷 es la dimensión, o el número de características o features
Handcrafted Feature Expansion

Usualmente, 𝐷 ≫ 𝑑 porque añadimos dimensiones que captan las

interacciones no lineales entre las características originales.
Ventaja: Es sencillo y el problema sigue siendo convexo y se
comporta bien. (Es decir, puedes seguir utilizando tu código
original de descenso por gradiente, pero con una representación de
mayor dimensión).
Desventaja: 𝜙(x) puede ser de muy alta dimensionalidad.
Por ejemplo

1
⎛
⎜ 𝑥 ⎞
⎟
1
⎜
⎜ ⎟
⎟
⎜ ⋮ ⎟
𝑥1 ⎜ ⎟
⎛ ⎞ ⎜ 𝑥𝑑 ⎟
⎜ 𝑥2 ⎟ ⎜
⎜ ⎟
⎜ ⋮ ⎟
x=⎜ ⎟ , y definimos 𝜙(x) = ⎜ 𝑥1 𝑥2 ⎟ ⎟
⎜
⎜ ⎟
⎟
⎜ ⋮ ⎟
⎝𝑥𝑑 ⎠ ⎜ 𝑥 𝑥 ⎟
⎜
⎜ 𝑑−1 𝑑 ⎟
⎟
⎜ ⋮ ⎟
⎝𝑥1 𝑥2 ⋯ 𝑥𝑑 ⎠
Pregunta:

¿Cuál es la dimensionalidad de 𝜙(x) ?

Esta nueva representación, 𝜙(x) es muy expresivo y permite
complicados límites de decisión no lineales, pero la dimensionalidad
es extremadamente alta. Esto hace que nuestro algoritmo sea
insoportablemente (y prohibitivamente) lento.
Cont.

Se basa en la siguiente observación: Si utilizamos el descenso por

gradiente con cualquiera de nuestras funciones de pérdida estándar,
el gradiente es una combinación lineal de las muestras de entrada.
Por ejemplo, veamos la pérdida cuadrática
The Kernel Trick

El truco del núcleo o kernel es una forma de sortear este dilema

aprendiendo una función en un espacio mucho más alta
dimensionalidad, sin calcular nunca un solo vector 𝜙(x) o el vector
completo w. Es un poco mágico.. pero recordemos un poco…
Recap.

La minimización del riesgo empírico (ERM) es un principio

fundamental en la teoría del aprendizaje estadístico que define una
familia de algoritmos de aprendizaje basados en la evaluación del
rendimiento sobre un conjunto de datos fijo y conocido.
Básicamente es comparar los datos reales con el ajuste
Recap.

En palabras simples, ERM busca elegir el modelo que mejor se

desempeña en el conjunto de datos de entrenamiento que tenemos
disponible. La idea principal es que si un modelo funciona bien en
los datos que ya conocemos, es probable que también funcione
bien en datos nuevos y similares.
El proceso de ERM se puede resumir en los
siguientes pasos:

1. Definir una función de pérdida: Esta función nos indica qué

tan mal predice el modelo para cada punto de datos. Existen
diferentes funciones de pérdida, como el error cuadrático medio
para la regresión o la entropía cruzada para la clasificación.
El proceso de ERM se puede resumir en los
siguientes pasos:

2. Calcular el riesgo empírico: El riesgo empírico es el promedio

de la función de pérdida sobre todos los puntos de datos en el
conjunto de entrenamiento. Estima el error esperado del modelo
en datos típicos.
El proceso de ERM se puede resumir en los
siguientes pasos:

3. Minimizar el riesgo empírico: De un conjunto de modelos

candidatos, elegimos el que minimiza el riesgo empírico. En otras
palabras, seleccionamos el modelo que se desempeña mejor en
nuestros datos de entrenamiento.
Recordemos la formulación SVM sin restricciones

𝑛
⊤ x + 𝑏), 0] + 2
min 𝐶 ∑ max[1 − 𝑦𝑖 ⏟
(𝑤⏟⏟ 𝑖 ⏟⏟ ‖𝑤‖𝑧
⏟
w
𝑖=1 ℎ(x𝑖 )
⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟ 𝑙2 −𝑅𝑒𝑔𝑢𝑙𝑎𝑟𝑖𝑧𝑒𝑟
𝐻𝑖𝑛𝑔𝑒−𝐿𝑜𝑠𝑠

La pérdida de bisagra es la función de error de elección de la SVM,

mientras que la 𝑙2 .-refleja la complejidad de la solución y penaliza
las soluciones complejas. Este es un ejemplo de minimización
empírica del riesgo con una función de pérdida ℓ y un regularizador
r𝑟,
Recordemos la formulación SVM sin restricciones

1 𝑛
min ∑ 𝑙(ℎw (x𝑖 ), 𝑦𝑖 ) + 𝜆𝑟(𝑤)
⏟ ,
w 𝑛 𝑖=1 ⏟⏟⏟⏟⏟
𝐿𝑜𝑠𝑠 𝑅𝑒𝑔𝑢𝑙𝑎𝑟𝑖𝑧𝑒𝑟

donde la función de pérdida es una función continua que penaliza

el error de entrenamiento, y el regularizador es una función
continua que penaliza la complejidad del clasificador. Definimos 𝜆
como 𝐶1 de la anterior clase.
Sigamos..

Si utilizamos el descenso por gradiente con cualquiera de nuestras

funciones de pérdida estándar, el gradiente es una combinación
lineal de las muestras de entrada.
Por ejemplo, veamos la pérdida cuadrática:

𝑛
ℓ(w) = ∑(w⊤ x𝑖 − 𝑦𝑖 )2
𝑖=1
Gradiente descendiente

La regla de descenso por gradiente, con tamaño de paso/velocidad

de aprendizaje 𝑠 > 0 con w actualizaciones sobre el paso del
tiempo.

𝑛 𝑛
𝜕ℓ 𝜕ℓ ⊤
𝑤𝑡+1 ← 𝑤𝑡 −𝑠( ) where: = ∑ 2( w x𝑖 − 𝑦𝑖 ) x𝑖 = ∑ 𝛾𝑖 x𝑖
⏟⏟⏟⏟⏟
𝜕w 𝜕w 𝑖=1 𝑖=1
𝛾𝑖 ∶ function of x𝑖 , 𝑦𝑖

Ahora bien, podemos expresar w como c.l de todos los vectores de

entrada.

𝑛
w = ∑ 𝛼𝑖 x𝑖
𝑖=1
Gradiente descendiente

Debido a que la pérdida es convexa, la solución final es

independiente de la inicialización, y por lo tanto, poremos
inicializar con w0 con lo que nosotros queramos. Por conveniencia,
0
mejor tomemos: w0 = ⎜ ⋮ ⎞⎛ ⎟
⎝ 0⎠
𝑛
La combinación lineal en w = ∑𝑖=1 𝛼𝑖 x𝑖 es trivial,
𝛼1 = ⋯ = 𝛼 𝑛 = 0 .
Gradiente descendiente

Ahora mostremos acontinuación que la optimización de gradiente

descendiente que los coeficientes 𝛼1 , … , 𝛼𝑛 , deben siempre existir,
de manera que podemos reescribir las actualizaciones de gradiente
en términos de los coeficientes solamente:
Gradiente descendiente
Gradiente descendiente

De hecho, el argumento anterior es por inducción. w es realmente

una combinación lineal de los vectores de entrenamiento para w0 .
Entonces si aplicamos la hipótesis inductiva para w que le sigue
w𝑡+1
Por lo tanto la regla de actualización para los coeficientes 𝛼𝑡𝑖 , es
entonces:

𝑡−1
𝛼𝑡𝑖 = 𝛼𝑡−1
𝑖 − 𝑠𝛾 _𝑖𝑡−1 , and we have 𝛼𝑡𝑖 = −𝑠 ∑ 𝛾 _𝑖𝑟
𝑟=0
Gradiente descendiente

En otras palabras, podemos computar la regla del gradiente

descendiente sin expresar los pesos w explícitamente. Solo
necestiamos tener un rastreo de los 𝑛 coeficientes 𝛼1 , … , 𝛼𝑛 .
Ahora que w puede ser expresado como una combinación del
conjunto de entrenamiento, podemos escribir el protucto interno
de w con cualquier input x𝑖 solamente en términos de los
productos internos de entrenamiento.

𝑛
w⊤ x𝑗 = ∑ 𝛼𝑖 x⊤
𝑖 x𝑗 .
𝑖=1
Gradiente descendiente

Por ende, podemos reescribir la forma cuadrada de la pérdida.

𝑛
ℓ(w) = ∑𝑖=1 (w⊤ x𝑖 − 𝑦𝑖 )2
enteramente en el producto interno de los datos de entrenamiento:

2
𝑛 𝑛
ℓ(�) = ∑ (∑ 𝛼𝑗 x⊤
𝑗 x𝑖 − 𝑦𝑖 )
𝑖=1 𝑗=1
Gradiente descendiente

En el tiempo de la prueba, también necesitaremos, solamente los

coeficientes para realizar una predicción de un conjunto de
entrenamiento 𝑥𝑡 , y podemos escribir el clasificador en términos de
productors internos entre el punto de prueba y de entrenamiento.

𝑛
ℎ(x𝑡 ) = w x𝑡 = ∑ 𝛼𝑗 x⊤
⊤
𝑗 x𝑡 .
𝑗=1
Gradiente descendiente

Es decir, solo necesitamos los datos de entrenamiento para poder

entrenar un hiperplano con una pérdida cuadrada de los productos
internos de todos los pares de vectores en los datos.

2
𝑛 𝑛
ℓ(�) = ∑ (∑ 𝛼𝑗 x⊤
𝑗 x𝑖 − 𝑦𝑖 )
𝑖=1 𝑗=1

Tal que:
𝑛
ℎ(x𝑡 ) = w⊤ x𝑡 = ∑ 𝛼𝑗 x⊤
𝑗 x𝑡 .
𝑗=1
Computación del producto interno.

1
⎛
⎜ 𝑥1 ⎞
⎟
⎜
⎜ ⎟
⎟
⎜ ⋮ ⎟
⎜
⎜ 𝑥𝑑 ⎟
⎟
⎜ ⎟
𝜙(x) = ⎜
⎜ 𝑥 𝑥
1 2
⎟
⎟
⎜
⎜ ⎟
⎟
⎜ ⋮ ⎟
⎜
⎜ 𝑥𝑑−1 𝑥𝑑 ⎟ ⎟
⎜
⎜ ⎟
⎟
⋮
𝑥
⎝ 1 2𝑥 ⋯ 𝑥 𝑑⎠

El producto interno 𝜙(x)⊤ 𝜙(z) puede ser formulado de la siguiente

forma.
Computación del producto interno.

𝑑
𝜙(x)⊤ 𝜙(z) = 1⋅1+𝑥1 𝑧1 +𝑥2 𝑧2 +⋯+𝑥1 𝑥2 𝑧1 𝑧2 +⋯+𝑥1 ⋯ 𝑥𝑑 𝑧1 ⋯ 𝑧𝑑 = ∏
𝑘=1

La suma de 2𝑑 terminos se convierte en un producto de 𝑑 términos.

Donde podemos realizar el cómputo anterior de forma más
eficiente:

( x𝑖 , x𝑗 )
k⏟ = 𝜙(x𝑖 )⊤ 𝜙(x𝑗 ).
this is called the kernel function
Computación del producto interno.

Con un conjunto de entrenamiento finito de 𝑛 los productos

internos suelen calcularse previamente y almacenarse en una matriz
de núcleo o matriz kernel:

K𝑖𝑗 = 𝜙(x𝑖 )⊤ 𝜙(x𝑗 ).

Si almacenamos la matriz K sólo tendremos que hacer simples
búsquedas de productos internos y cálculos de baja dimensión a lo
largo del algoritmo de descenso de gradiente. El clasificador final
se convierte en:

𝑛
ℎ(x𝑡 ) = ∑ 𝛼𝑗 k(x𝑗 , x𝑡 ).
𝑗=1
Computación del producto interno.

Durante el entrenamiento en el nuevo espacio de alta

dimensionalidad de 𝜙(x), queremos computar 𝛾𝑖 a través de
kernels, sin tener que cumptar dicha función o los pesos. Si
𝑛
previamente habíamos establecido que w = ∑𝑗=1 𝛼𝑗 𝜙(x𝑗 )
La actualización de gradiente en la iteración 𝑡 + 1 se convierte en:
𝑛
𝛼𝑡+1
𝑖 ← 𝛼𝑡𝑖 − 2𝑠(∑𝑗=1 𝛼𝑡𝑗 𝐾𝑖𝑗 ) − 𝑦𝑖 ).
Kernels Generales

Aquí tenemos una lista de kernels populares.

1. Linear:
K(x, z) = x⊤ z
Kernels Generales

2. Radial Basis Function RBF a.k.a Kernel Gaussiano.

−‖x−z‖2
K( x , z ) = 𝑒 𝜎2
Kernels Generales

Exponencial:
−‖x−z‖
K(x, z) = 𝑒 2𝜎2
Kernels Generales

Laplaciano:
−|x−z|
K(x, z) = 𝑒 𝜎
Kernels Generales

Sigmoid Kernel

K(x, z) = tanh(ax⊤ + 𝑐)
Funciones Kernel

Puede cualquier función K(⋅, ⋅) → ℛ ser usada como Kernel ?

En breves no, tiene que corresponder a productos internos, después
de cierta transformación, x → 𝜙(x), entonces puede ser solo si K
es semidefinida positiva.
Definición

En el álgebra lineal, una matriz semidefinida positiva es una

matriz cuadrada real que satisface las siguientes condiciones:
1. Forma cuadrática no negativa: Para cualquier vector no nulo
𝑥 en el espacio vectorial real n-dimensional ℝ𝑛 , la forma cuadrática
asociada a la matriz 𝐴 y al vector 𝑥 es no negativa:

𝑥𝑇 𝐴𝑥 ≥ 0
Definición

2. Autovalores no negativos: Todos los autovalores de la matriz

𝐴 son no negativos:

𝜆𝑖 ≥ 0

para 𝑖 = 1, 2, … , 𝑛, donde 𝜆𝑖 son los autovalores de 𝐴.

Definición
3. Descomposición en producto de Cholesky: La matriz 𝐴
puede descomponerse en un producto de una matriz triangular
inferior 𝐿 y su traspuesta:

𝐴 = 𝐿𝐿𝑇