ML - 22 - Support Vector Machines IV

Le funzioni kernel sono utili in quanto ci permettono di spostarci da un contesto strettamente lineare in un contesto potenzialmente non-lineare utilizzando comunque dei metodi lineari.

Questa abilità di catturare relazioni non lineare infatti non viene ottenuto cambiando l'algoritmo, che rimane lineare, ma bensì cambiando i dati stessi. L'idea è che tramite la funzione kernel i dati vengono proiettati in un'altro spazio, in cui poi si applica l'algoritmo per trovare il modello lineare in questo nuovo spazio. Infine, si torna indietro allo spazio originale e si ottiene un modello che tipicamente non è lineare.

Non tutte le funzioni possono essere utilizzate come funzioni kernel. Ogni funzione kernel \(\kappa\) infatti ha una funzione base associata \(\phi\).

La funzione \(\phi: \chi \to \mathcal{F}\) è una funzione che prende in input un punto \(x \in \chi\) (input space) e lo mappa in uno spazio \(\mathcal{F}\) (feature space), dove lo spazio \(\mathcal{F}\) deve essere uno spazio vettoriale in cui è possibile definire il prodotto scalare (Hilbert space).

La funzione kernel \(\kappa: \chi \times \chi \to \mathbb{R}\) prende due input e permette di calcolare la loro similarità nello spazio delle features \(\mathcal{F}\)

\[\kappa(x_1, x_2) = \phi(x_1)^T \phi(x_2)\]

Osservazione: Notiamo che da nessuna parte c'è scritto che l'elemento \(x \in \chi\) deve essere necessariamente un valore. In linea di principio possiamo pensare ad \(x\) come ad una stringa, e la funzione kernel prende due stringhe e ritorna un valore di similarità tra le due stringhe. Un discorso analogo può essere fatto con dei grafi piuttosto che con delle stringhe. In generale quindi quando lavoriamo solamente con le funzioni kernel possiamo affrontare in modo diretto una serie di problemi di classificazione che non stiamo considerando senza passare per la codifica con vettori.

Come faccio a verificare che una data funzione è una funzione kernel?

A tale fine la condizione più generale possibile, che è sia necessaria che sufficiente è la seguente: affinché una data funzione \(\kappa: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^n\) è una funzione kernel è che per tutti gli insiemi di \(n\) elementi \((x_1, \ldots, x_n)\), la matrice di Gram \(\mathbf{K}\) tale che \(k_{i,j} = \kappa(x_i, x_j)\) è semidefinita positiva, ovvero

\[v^T \mathbf{K} v \geq 0\]

per ogni vettore \(v\).

---

In pratica però la condizione appena data è molto complicata da utilizzare. Un possibile approccio è una verifica più manuale. Supponiamo ad esempio di avere la seguente funzione kernel

\[\kappa(x_1, x_2) = (x_1 \cdot x_2)^2\]

con \(x_1, x_2 \in \mathbb{R}^2\). Possiamo verificare la validità di questa funzione nel seguente modo

\[\begin{split} \kappa(x_1, x_2) &= (x_{11} x_{21} + x_{12} x_{22})^2 \\ &= x_{11}^2x_{21}^2 + x_{12}^2 x_{22}^2 + 2x_{11}x_{12}x_{21}x_{22}\\ &= (x_{11}^2, x_{12}^2, x_{11}x_{12}, x_{11}x_{12}) \cdot (x_{21}^2,x_{22}^2, x_{21}x_{22}, x_{21}x_{22}) \\ &= \phi(x_1) \cdot \phi(x_2) \\ \end{split}\]

e quindi definendo come funziona base la funzione

\[\phi(x) = (x_1^2, x_2^2, x_1x_2, x_1x_2)^T\]

ottengo che la funzione \(\kappa\) data prima è una funzione kernel.

Generalizzando quanto visto prima otteniamo che se \(x_1, x_2 \in \mathbb{R}^d\), allora

\[\kappa(x_1, x_2) = (x_1 \cdot x_2)^2 = \phi(x_1)^T \phi(x_2)\]

è una funzione kernel, con

\[\phi(x) = (x_1^2, \ldots, x_d^2, x_1x_2, \ldots, x_1x_d, x_2x_1, \ldots, x_dx_{d-1})^T\]

Notiamo come lo spazio di input \(d\) dimensionale viene mappato in uno spazio a dimensione \(m=d^2\). Calcolare \(\kappa(x_1, x_2)\) richiede \(O(d)\), mentre derivandola da \(\phi(x_1)^T \phi(x_2)\) richiede \(O(d^2)\) passi.

---

Continuando con questa logica notiamo che anche

\[\kappa(x_1, x_2) = (x_1 \cdot x_2 + c)^2\]

è una funzione kernel, in quanto

\[\begin{split} \kappa(x_1, x_2) &= (x_1 \cdot x_2 + c)^2 \\ &= ... \\ &= \phi(x_1)^T \phi(x_2) \\ \end{split}\]

---

Anche \(\kappa(x_1, x_2) = (x_1 \cdot x_2 + c)^t\) è una funzione nkernel.

---

L'idea generale per costruire le funzioni kernel è quella di partire da delle funzioni kernel e di combinarle tra loro per ottenere nuove funzioni.

Siano quindi \(\kappa_1(x_1, x_2)\) e \(\kappa_2(x_1, x_2)\) due funzioni kernel. La funzionne \(\kappa(x_1, x_2)\) è kernel in tutti i seguenti casi:

• \(\kappa(x_1, x_2) = e^{\kappa_1(x_1, x_2)}\).

• \(\kappa(x_1, x_2) = \kappa_1(x_1, x_2) + \kappa_2(x_1, x_2)\).

• \(\kappa(x_1, x_2) = \kappa_1(x_1, x_2) \cdot \kappa_2(x_1, x_2)\).

• \(\kappa(x_1, x_2) = c \kappa_1(x_1, x_2)\), per ogni \(c > 0\).

• \(\kappa(x_1, x_2) = x_1^T \mathbf{A} x_2\), con \(\mathbf{A}\) definita positiva.

• \(\kappa(x_1, x_2) = f(x_1) \kappa_1(x_1, x_2) g(x_2)\), per ogni \(f, g: \mathbb{R}^n \to \mathbb{R}\).

• \(\kappa(x_1, x_2) = p(k_1(x_1, x_2))\), per ogni polinomio \(p: \mathbb{R}^q \to \mathbb{R}\) con coefficienti non negativi.

• \(\kappa(x_1, x_2) = \kappa_3(\phi(x_1), \phi(x_2))\) per ogni vettore \(\phi\) di \(m\) funzioni \(\phi_i: \mathbb{R}^n \to \mathbb{R}\) e per ogni funzione kernel \(\kappa_3(x_1, x_2) \in \mathbb{R}^m\).

L'idea quindi non è più quella di definire una funzione e poi dimostrare che è una funzione kernel. Si parte da funzioni che già sappiamo essere kernel e le combiniamo utilizzando questi operatori per sapere certamente che il risultato sarà un'altra funzione kernel.

---

Ad esempio per dimostrare che \(\kappa(x_1, x_2) = (x_1 \cdot x_2 + c)^d\) è una funzione kernel, la possiamo costruire nei seguenti steps:

1. \(x_1 \cdot x_2 = x_1^T x_2\) è una funzione kernel corrispondente alle funzioni base \(\phi_i(x) = x\).

2. \(c\) è una funzione kernel base.

3. \(x_1 \cdot x_2 + c\) è la somma di due kernel e dunque è kernel.

4. Elevare ad un coefficiente non negativo una funzione kernel ci da un'altra funzione kernel.

---

Un altro esempio è la seguente

\[\kappa(x_1, x_2) = e^{\displaystyle{-\frac{||x_1 - x_2||^2}{2 \sigma^2}}}\]

che è una funzione kernel detta RBF, in quanto...

Tipicamente su vettori le tipologie più rilevanti di kernel sono le seguenti:

• Polynomial kernel:

  \[\kappa(x_1, x_2) = (x_1 \cdot x_2 + 1)^d\]

• Sigmoidal kernel:

  \[\kappa(x_1, x_2) = \tanh{(c_1 x_1 \cdot x_2 + c_2}\]

• Gaussian kernel:

  \[\kappa(x_1, x_2) = \text{exp}\Big(- \frac{||x_1 - x_2||^2}{2 \sigma^2} \Big)\]

  dove \(\sigma \in \mathbb{R}\).