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]

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:

y ^ = sgn ⁡ ( w ⊤ x ) {\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.

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

sgn ⁡ ∑ i α i y i K ( x i , x ′ ) {\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.

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

w = ∑ i n α i y i x i {\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:

y ^ = sgn ⁡ ( w T x ) = sgn ⁡ ( ∑ i n α i y i x i ) T x = sgn ⁡ ∑ i n α i y i ( x i ⋅ x ) {\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 y ^ = sgn ⁡ ∑ i n α i y i K ( x i , x j ) {\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

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]

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Classificazione a singola classe · Ranking · Regole di associazione · Apprendimento non supervisionato · Apprendimento semi-supervisionato · Apprendimento supervisionato · Apprendimento auto-supervisionato · Apprendimento per rinforzo · Apprendimento profondo · Apprendimento online · Apprendimento incrementale · Apprendimento trasduttivo
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · DBSCAN · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random field CRF · Modello di Markov nascosto · Algoritmo k-nearest neighbors (k-NN) · Ragionamento basato su casi (CBR) · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Modello grafico · Rete bayesiana · Macchine a vettori di supporto (SVM) · Processo gaussiano · Modello ensemble · Boosting · Bagging · Stacking · Voting · Cascading · Error correcting output code (ECOC)
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Analisi della correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Selezione delle caratteristiche · Estrazione di caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Percettrone basato su kernel · Rete neurale a funzioni base radiali (RBF net) · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Rete neurale grafica · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · PyTorch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico