Classificatore LMNN

Un classificatore Large Margin Nearest Neighbor (LMNN) ^[1] è un algoritmo di apprendimento automatico statistico per l'apprendimento di metriche. Esso apprende una pseudometrica utile alla classificazione basata sui k-vicini più prossimi (k-NN). L'algoritmo si basa sulla programmazione semidefinita, una sottoclasse dell'ottimizzazione convessa.

L'obiettivo dell'apprendimento supervisionato (e, più specificamente, della classificazione) è apprendere una regola di decisione in grado di categorizzare le istanze di dati in classi predefinite. La regola del k-nearest neighbor assume la disponibilità di un insieme di addestramento di istanze etichettate (con classi note). Essa classifica una nuova istanza con la classe ottenuta dal voto di maggioranza delle k istanze di addestramento (etichettate) più vicine. La vicinanza viene misurata con una metrica predefinita. LMNN è un algoritmo che apprende questa (pseudo-)metrica globale in modo supervisionato per migliorare l'accuratezza della classificazione della regola del k-NN.

Impostazioni

L'idea principale alla base di LMNN è quella di apprendere una pseudometrica in base alla quale tutte le istanze nell'insieme di addestramento siano circondate da almeno k istanze che condividono la stessa etichetta di classe. Se ciò viene raggiunto, l'errore leave-one-out (un caso speciale di convalida incrociata) viene ridotto al minimo. Si assuma che i dati di addestramento siano costituiti da un insieme di dati ${\displaystyle D=\{({\vec {x}}_{1},y_{1}),\dots ,({\vec {x}}_{n},y_{n})\}\subset R^{d}\times C}$, dove l'insieme delle possibili classi (etichette) è ${\displaystyle C=\{1,\dots ,c\}}$ .

L'algoritmo apprende una pseudometrica del tipo

${\displaystyle d({\vec {x}}_{i},{\vec {x}}_{j})=({\vec {x}}_{i}-{\vec {x}}_{j})^{\top }\mathbf {M} ({\vec {x}}_{i}-{\vec {x}}_{j})}$.

Perché ${\displaystyle d(\cdot ,\cdot )}$ sia ben definita, la matrice ${\displaystyle \mathbf {M} }$ deve essere semidefinita positiva. La metrica euclidea è un caso speciale, dove ${\displaystyle \mathbf {M} }$ è la matrice identità. Questa generalizzazione è spesso denominata metrica di Mahalanobis.

La figura 1 illustra l'effetto della metrica al variare ${\displaystyle \mathbf {M} }$. I due cerchi mostrano l'insieme dei punti con uguale distanza dal centro ${\displaystyle {\vec {x}}_{i}}$ Nel caso euclideo questo insieme è un cerchio, mentre secondo la metrica generalizzata (Mahalanobis) diventa un ellissoide.

Figura 1: Illustrazione schematica di LMNN

L'algoritmo distingue due tipi di punti dati speciali: i vicini-obiettivo e gli impostori.

Vicini-obiettivo

I vicini-obiettivo vengono selezionati prima dell'apprendimento. Ogni istanza ${\displaystyle {\vec {x}}_{i}}$ ha esattamente ${\displaystyle k}$ diversi vicini target all'interno di ${\displaystyle D}$, che condividono tutti la stessa etichetta di classe ${\displaystyle y_{i}}$ I vicini-obiettivo sono le istanze che dovrebbero diventare i vicini più prossimi in base alla metrica appresa. Indichiamo con ${\displaystyle N_{i}}$ l'insieme dei vicini-obiettivo per un'istanza ${\displaystyle {\vec {x}}_{i}}$.

Impostori

Un impostore di un'istanza ${\displaystyle {\vec {x}}_{i}}$ è un'altra istanza ${\displaystyle {\vec {x}}_{j}}$ con un'etichetta di classe diversa (ossia ${\displaystyle y_{i}\neq y_{j}}$) che è uno dei vicini più prossimi di ${\displaystyle {\vec {x}}_{i}}$ Durante l'apprendimento, l'algoritmo cerca di ridurre al minimo il numero di impostori per tutte le istanze nell'insieme di addestramento.

Algoritmo

Il LMNN ottimizza la matrice ${\displaystyle \mathbf {M} }$ con l'aiuto della programmazione semidefinita. L'obiettivo è duplice: per ogni istanza ${\displaystyle {\vec {x}}_{i}}$, i vicini-obiettivo dovrebbero essere vicini e gli impostori dovrebbero essere lontani. La Figura 1 mostra l'effetto di tale ottimizzazione con un esempio illustrativo. La metrica appresa fa sì che il vettore di input ${\displaystyle {\vec {x}}_{i}}$ sia circondato da istanze di addestramento della stessa classe. Se fosse un'istanza di test, verrebbe classificato correttamente con la regola del k-NN per ${\displaystyle k=3}$.

Il primo obiettivo di ottimizzazione viene raggiunto riducendo al minimo la distanza media tra le istanze e i loro vicini-obiettivo

${\displaystyle \sum _{i,j\in N_{i}}d({\vec {x}}_{i},{\vec {x}}_{j})}$.

Il secondo obiettivo si raggiunge penalizzando le distanze dagli impostori ${\displaystyle {\vec {x}}_{l}}$ che sono meno di un'unità più lontani rispetto ai vicini-obiettivo ${\displaystyle {\vec {x}}_{j}}$ (quindi spingendoli fuori dal vicinato locale di ${\displaystyle {\vec {x}}_{i}}$). Il valore risultante da minimizzare può essere espresso come:

${\displaystyle \sum _{i,j\in N_{i},l,y_{l}\neq y_{i}}[d({\vec {x}}_{i},{\vec {x}}_{j})+1-d({\vec {x}}_{i},{\vec {x}}_{l})]_{+}}$

Con una funzione di perdita a cerniera (hinge loss), ${\textstyle [\cdot ]_{+}=\max(\cdot ,0)}$, si garantisce che la prossimità dell'impostore non venga penalizzata quando si trova al di fuori del margine. Il margine di un'unità esatta fissa la scala della matrice ${\displaystyle M}$. Qualsiasi scelta alternativa ${\displaystyle c>0}$ si tradurrebbe in un ridimensionamento di ${\displaystyle M}$ di un fattore pari a ${\displaystyle 1/c}$ .

Alla fine, il problema di ottimizzazione diventa:

${\displaystyle \min _{\mathbf {M} }\sum _{i,j\in N_{i}}d({\vec {x}}_{i},{\vec {x}}_{j})+\lambda \sum _{i,j,l}\xi _{ijl}}$

${\displaystyle \forall _{i,j\in N_{i},l,y_{l}\neq y_{i}}}$

${\displaystyle d({\vec {x}}_{i},{\vec {x}}_{j})+1-d({\vec {x}}_{i},{\vec {x}}_{l})\leq \xi _{ijl}}$

${\displaystyle \xi _{ijl}\geq 0}$

${\displaystyle \mathbf {M} \succeq 0}$

L'iperparametro ${\textstyle \lambda >0}$ è una costante positiva (tipicamente impostata tramite convalida incrociata). Qui le variabili ${\displaystyle \xi _{ijl}}$ (insieme a due tipi di vincoli) sostituiscono il termine nella funzione di costo. Esse svolgono un ruolo simile alle variabili di slack, utile ad assorbire l'impatto delle violazioni dei vincoli relativi agli impostori. L'ultimo vincolo garantisce che ${\displaystyle \mathbf {M} }$ sia semidefinita positiva. Il problema di ottimizzazione è un'istanza di programmazione semidefinita (SDP). Sebbene, in generale, la SDP comporti un'elevata complessità computazionale, questa particolare istanza di SDP può essere risolta in modo molto efficiente grazie alle proprietà geometriche intrinseche del problema. In particolare, la maggior parte dei vincoli relativi agli impostori sono soddisfatti naturalmente e non devono essere verificati durante l'esecuzione (l'insieme delle variabili ${\displaystyle \xi _{ijl}}$ risulta sparso). Una tecnica di risoluzione particolarmente adatta è il metodo basato su working set, che mantiene un piccolo insieme di vincoli che vengono applicati attivamente e solo occasionalmente monitora i vincoli rimanenti (verosimilmente soddisfatti) per garantirne la correttezza.

Estensioni e risolutori efficienti

LMNN è stato esteso in modo da comprendere più metriche locali ^[2]. Questa estensione migliora significativamente l'errore di classificazione, ma comporta la risoluzione di un problema di ottimizzazione più costoso. Nel loro articolo sul Journal of Machine Learning Research ^[3], gli ideatori derivano un risolutore efficiente per il programma semi-definito. Il metodo è capace di apprendere una metrica per il dataset di cifre scritte a mano MNIST in diverse ore, elaborando miliardi di vincoli a coppie. Un'implementazione Matlab open source è disponibile gratuitamente sulla pagina web degli autori.

Kumal et al. ^[4] hanno esteso l'algoritmo per incorporare invarianze locali nelle trasformazioni polinomiali multivariate e hanno migliorato la regolarizzazione.

Voci correlate

• Analisi discriminante lineare
• Apprendimento basato su similarità
• Clustering
• Neighbor components analysis
• Ricerca nearest neighbor
• Spazio pseudometrico