Classificatore lineare

Nel campo dell'apprendimento automatico, un classificatore lineare prende decisioni su problemi di classificazione basandosi su una combinazione lineare dei valori delle caratteristiche (feature) che descrivono gli oggetti, presentati alla macchina in forma vettoriale (vettori di caratteristiche).^[1][2]

Definizione

In questo caso, i punti vuoti e i punti pieni possono essere correttamente classificati da qualsiasi numero di classificatori lineari. H1 (in blu) li classifica correttamente, come fa H2 (in rosso). H2 potrebbe essere considerato "migliore" nel senso che è anche più lontano da entrambi i gruppi. H3 (in verde) non riesce a classificare correttamente i punti

Se il vettore di caratteristiche in ingresso è un vettore di numeri reali ${\displaystyle \mathbf {x} }$ allora il punteggio in uscita è

${\displaystyle y=f(\mathbf {w} \cdot \mathbf {x} )=f\left(\sum _{j}w_{j}x_{j}\right),}$

dove ${\displaystyle \mathbf {w} }$ è un vettore reale di pesi e ${\displaystyle f}$ è una funzione che converte il prodotto scalare dei due vettori nell'uscita desiderata. In altre parole, ${\displaystyle \mathbf {w} }$ determina una funzione lineare che mappa ${\displaystyle \mathbf {x} }$ in ${\displaystyle \mathbb {R} }$. Il vettore di pesi ${\displaystyle \mathbf {w} }$ viene appreso sulla base di un insieme di campioni d'addestramento (training set) etichettati. Spesso ${\displaystyle f}$ è una semplice funzione di soglia (ad esempio la funzione gradino) che associa i valori di ${\displaystyle \mathbf {w} \cdot \mathbf {x} }$ sopra una certa soglia scalare ${\displaystyle \theta }$ alla prima classe e gli altri valori alla seconda classe ossia:

${\displaystyle f(\mathbf {x} )={\begin{cases}1&{\text{se }}\mathbf {w} ^{T}\mathbf {x} >\theta ,\\0&{\text{altrimenti}}.\end{cases}}}$

Con una ${\displaystyle f}$ più complessa si può fornire la probabilità che un oggetto appartenga a una certa classe.

Per un problema di classificazione a due classi, l'operato di un classificatore lineare può essere visto come la bi-partizione di uno spazio di input multidimensionale tramite un iperpiano: tutti i punti su un lato dell'iperpiano sono classificati come "positivi" e gli altri come "negativi".

Un classificatore lineare viene spesso utilizzato in situazioni in cui la velocità di classificazione è un fattore importante, poiché è spesso il classificatore più veloce, specialmente quando ${\displaystyle \mathbf {x} }$ è sparso. Inoltre, i classificatori lineari spesso funzionano molto bene quando il numero di dimensioni di ${\displaystyle \mathbf {x} }$ è elevato, come nella classificazione dei documenti, dove ogni elemento in ${\displaystyle \mathbf {x} }$ è tipicamente il numero di occorrenze di una parola in un documento (matrice documento-termine). In tali casi, il classificatore dovrebbe essere ben regolarizzato.

Modelli generativi e discriminativi

Esistono due grandi tipologie di metodi per determinare i parametri ${\displaystyle \mathbf {w} }$ di un classificatore lineare. I modelli possono essere generativi o discriminativi.^[3] I metodi del primo tipo modellano la distribuzione di probabilità congiunta, mentre i metodi del secondo modellano funzioni di densità condizionali ${\displaystyle P({\rm {classe}}|\mathbf {x} )}$. Esempi di tali algoritmi includono:

• Analisi discriminante lineare (LDA): assume che le densità condizionate nel modello siano gaussiane.
• Classificatore bayesiano ingenuo (Naive Bayes) con distribuzioni degli eventi multinomiali o bernoulliane multivariate.

La seconda categoria di metodi comprende i modelli discriminativi i quali cercano di massimizzare la qualità delle predizioni su un insieme di dati di addestramento. Alla funzione di costo usata nell'addestramento possono essere aggiunti termini per realizzare facilmente la regolarizzazione del modello finale. Esempi di classificatori lineari discriminativi includono:

• Regressione logistica: modello basato sulla stima di massima verosimiglianza per ${\displaystyle \mathbf {w} }$, avendo assunto che l'insieme dei dati di addestramento sia stato generato da un modello binomiale che dipende dall'output del classificatore.
• Percettrone: algoritmo che tenta di correggere tutti gli errori riscontrati nel training set.
• Analisi discriminante lineare di Fisher: algoritmo (diverso da "LDA") che massimizza il rapporto tra dispersione tra classi e dispersione all'interno delle classi, senza ulteriori assunzioni. Si tratta essenzialmente di un metodo supervisionato di riduzione della dimensionalità per la classificazione binaria.^[4]
• Macchina a vettori di supporto (SVM): algoritmo che massimizza il margine tra l'iperpiano di decisione (modello lineare) e gli esempi nel training set.

Nota: LDA non appartiene alla classe dei modelli discriminativi in questa tassonomia, il suo nome è solo un retaggio storico. ^[5] Il suo significato si chiarisce se confrontato con l'altro fondamentale metodo lineare di riduzione della dimensionalità, l'analisi delle componenti principali (PCA). LDA è un algoritmo di apprendimento supervisionato che utilizza le etichette dei dati, mentre PCA è non supervisionato, non sfruttando le etichette.

L'apprendimento di un modello discriminativo spesso porta a un'accuratezza maggiore rispetto alla modellazione di funzioni di densità condizionate. Tuttavia, la gestione di dati mancanti risulta spesso più semplice se si ricorre a densità condizionate.^[6]

Tutti i modelli di classificazione lineare sopra elencati possono essere convertiti in non lineari andando a operare su uno spazio di input diverso ${\displaystyle \varphi (\mathbf {x} )}$, utilizzando il trucco del kernel.

Apprendimento discriminativo

L'apprendimento discriminativo di classificatori lineari procede solitamente in modo supervisionato, mediante un algoritmo di ottimizzazione al quale viene fornito un training set comprendente gli output desiderati e una funzione di perdita (loss) che misura la discrepanza tra gli output predetti dal classificatore e gli output desiderati. Pertanto, l'algoritmo di apprendimento risolve un problema di ottimizzazione della forma^[7]

${\displaystyle {\underset {\mathbf {w} }{\arg \min }}\;R(\mathbf {w} )+C\sum _{i=1}^{N}L(y_{i},\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i})}$

in cui:

• ${\displaystyle \mathbf {w} }$ è il vettore di parametri del classificatore,
• ${\displaystyle L(y_{i},\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i})}$ è una funzione di perdita che misura la discrepanza fra la predizione del classificatore e il vero output ${\displaystyle y_{i}}$ per l'${\displaystyle i}$-esimo esempio di training,
• ${\displaystyle R(\mathbf {w} )}$ è una funzione di regolarizzazione fa sì che i parametri non crescano troppo (causando sovradattamento), e
• ${\displaystyle C}$ è una costante scalare (impostata dall'utente dell'algoritmo di apprendimento) che controlla il bilanciamento fra termine regolarizzatore e funzione di perdita.

Le funzioni di perdita più diffuse comprendono quella "a cerniera" (hinge loss, tipica nelle SVM lineari) e la perdita logaritmica (nella regressione logistica lineare). Se la funzione di regolarizzazione ${\displaystyle R}$ è convessa, allora il problema sopra descritto è convesso.^[3] Esistono molti algoritmi per risolvere tali problemi; i più diffusi ai fini della classificazione lineare comprendono la discesa del gradiente (stocastica), L-BFGS, la discesa delle coordinate e i metodi di Newton.