Percettrone basato su kernel

Nell'apprendimento automatico non parametrico, il percettrone basato su kernel (o kernel perceptron) è una variante del popolare algoritmo di apprendimento del percettrone capace di apprendere macchine kernel, ovvero classificatori non lineari che impiegano una funzione del kernel per calcolare la similarità dei nuovi esempi, sui quali effettuare predizioni, rispetto a quelli di addestramento. L'algoritmo è stato proposto nel 1964,^[1] il che lo rende il primo metodo kernel per l'apprendimento di un classificatore.^[2]

Preliminari

L'algoritmo del percettrone

L'algoritmo del percettrone è un algoritmo di apprendimento online che opera secondo un principio chiamato "apprendimento guidato dagli errori". Esso migliora iterativamente un modello eseguendolo su campioni di addestramento, e poi aggiornando il modello ogni volta che rileva una classificazione errata rispetto a un segnale supervisionato. Il modello appreso dall'algoritmo del percettrone standard è un classificatore binario lineare: un vettore di pesi w (e facoltativamente un termine di intercetta b, qui omesso per semplicità) che viene utilizzato per classificare un vettore campione x come classe "1" o classe "-1" in base a:

${\displaystyle {\hat {y}}=\operatorname {sgn}(\mathbf {w} ^{\top }\mathbf {x} )}$

dove uno zero viene arbitrariamente mappato su 1 o -1. (Il "cappello" su ŷ indica un valore stimato).

In pseudocodice, l'algoritmo del percettrone è dato da:

Inizializza w a un vettore tutto nullo di lunghezza p, il numero di predittori (caratteristiche).

Per un numero fisso di iterazioni o finché non viene soddisfatto un criterio di arresto:

Per ogni esempio di addestramento x_i con etichetta di verità di riferimento y_i ∈ {-1, 1}:

Sia ŷ = sgn(w^T x_i) .

Se ŷ ≠ y_i, aggiorna w ← w + y_i x_i.

Metodi kernel

Al contrario dei modelli lineari appresi dal percettrone, un metodo kernel ^[3] è un classificatore che memorizza un sottoinsieme dei suoi esempi di addestramento x_i, associa a ciascuno un peso α_i e prende decisioni per nuovi esempi x' valutando la funzione

${\displaystyle \operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )}$.

Qui, K è una funzione kernel. Formalmente, una funzione kernel è un kernel semidefinito non negativo (condizione di Mercer), che rappresenta un prodotto interno tra vettori-esempio in uno spazio ad alta dimensionalità, come se gli esempi fossero stati espansi per includere caratteristiche aggiuntive da una funzione Φ: K(x, x') = Φ(x) · Φ(x') . Intuitivamente, questa può essere pensata come una funzione di similarità tra campioni, quindi la macchina kernel stabilisce la classe di un nuovo campione tramite confronto pesato con gli esempi nell'insieme di addestramento. Ogni funzione x' ↦ K(x_i,x') funge da funzione di base nella classificazione.

Algoritmo

Per derivare una versione kernelizzata dell'algoritmo del percettrone, esso va prima formulato in forma duale, partendo dall'osservazione che il vettore dei pesi w può essere espresso come una combinazione lineare degli n campioni di addestramento. L'equazione per il vettore dei pesi è la seguente

${\displaystyle \mathbf {w} =\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}}$

dove α_i è il numero di volte in cui x_i è stato classificato erroneamente, forzando un aggiornamento w ← w + y_i x_i. Utilizzando tale risultato, si può formulare l'algoritmo duale del percettrone, che esegue un ciclo sui campioni come in precedenza, effettuando predizioni, ma invece di memorizzare e aggiornare un vettore di pesi w, aggiorna un vettore "contatore di errori" α. Si deve anche riscrivere la formula di previsione per eliminare w:

${\displaystyle {\begin{aligned}{\hat {y}}&=\operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} )\\&=\operatorname {sgn} \left(\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}\right)^{\mathsf {T}}\mathbf {x} \\&=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}(\mathbf {x} _{i}\cdot \mathbf {x} )\end{aligned}}}$

Inserendo le due equazioni nel ciclo di addestramento, si ottiene l'algoritmo del percettrone duale.

Infine, si può sostituire il prodotto scalare nel percettrone duale con una funzione kernel arbitraria, per ottenere l'effetto di una mappa di caratteristiche Φ senza calcolare esplicitamente Φ(x) per alcun esempio. Si ottiene in tal modo l'algoritmo del percettrone basato su kernel:^[4]

Inizializzare α a un vettore di tutti zeri di lunghezza n, numero di esempi di addestramento.

Per un numero fisso di iterazioni o finché non viene soddisfatto un criterio di arresto:

Per ogni esempio di addestramento x_j, y_j:

Sia ${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})}$

Se ŷ ≠ y_j, eseguire un aggiornamento incrementando il contatore degli errori:

α_j ← α_j + 1

Varianti ed estensioni

Un problema del percettrone basato su kernel, come come presentato sopra, è che non apprende macchine kernel sparse. Inizialmente, tutti gli α_i sono zero, quindi la valutazione della funzione di decisione per ottenere ŷ non richiede alcuna valutazione del kernel, ma ogni aggiornamento incrementa un singolo α_i, rendendo la valutazione sempre più costosa. Inoltre, quando il percettrone del kernel viene utilizzato in un contesto di apprendimento online, il numero di α_i diversi da zero, e quindi il costo della valutazione, crescono linearmente con il numero di esempi presentati all'algoritmo.

Per risolvere questo problema è stata proposta la variante del kernel perceptron detta forgettron. Essa mantiene un insieme attivo di esempi con α_i diversi da zero, rimuovendo ("dimenticando") gli esempi dall'insieme attivo quando supera un limite massimo predeterminato e "riducendo" (diminuendo il peso de) i vecchi esempi quando quelli nuovi vengono promossi attraverso α_i diversi da zero.^[5]

Un altro problema del percettrone basato su kernel è che non è regolarizzabile, il che lo rende vulnerabile al sovradattamento. L'algoritmo di apprendimento online basato su kernel denominato NORMA può essere considerato una generalizzazione dell'algoritmo del percettrone basato su kernel con l’aggiunta della regolarizzazione.^[6] Anche l'algoritmo di ottimizzazione minima sequenziale (SMO) utilizzato per apprendere le macchine a vettori di supporto può essere considerato una generalizzazione del percettrone basato su kernel.^[6]

Anche l'algoritmo del percettrone con votazione ideato da Freund e Schapire si estende al caso kernelizzato, ^[7] offrendo in più la possibilità di determinare i limiti di generalizzazione come per le SVM con kernel.^[2]