Apprendimento Attivo K-Nearest Neighbors
- Introdotto da
- Settles, B. (active learning framework); Fix & Hodges (KNN base)
- Anno
- 1951–2010
- Tipo
- Active learning with KNN base learner
- Famiglia
- Machine learning
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
L'apprendimento attivo con K-nearest neighbors (KNN) combina la predizione basata su istanze del KNN con una strategia di interrogazione iterativa che seleziona gli esempi non etichettati più informativi per l'annotazione.
Il modello richiede etichette solo per le istanze in cui i margini di voto del vicinato sono più ristretti, raggiungendo un'accuratezza competitiva con un numero significativamente inferiore di esempi etichettati rispetto al KNN completamente supervisionato su dati tabulari.
L’intuizione alla base del metodo
Il KNN classifica un punto esaminando i suoi k vicini etichettati più prossimi e prendendo una decisione a maggioranza. Quando questi vicini sono quasi equamente divisi tra le classi, il modello è genuinamente incerto — e tale incertezza individua quale esempio non etichettato sarebbe più utile etichettare. L'apprendimento attivo sfrutta questo segnale: ad ogni iterazione, l'algoritmo trova il punto non etichettato il cui vicinato è più equamente diviso, chiede a un oracolo di etichettarlo, lo aggiunge al pool etichettato e ripete il processo. Il risultato è che lo sforzo di etichettatura si concentra vicino ai confini decisionali, dove le nuove etichette apportano il massimo contributo.
Storia
Il classificatore K-nearest neighbors ha origine in Fix e Hodges (1951) ed è stato formalizzato da Cover e Hart (1967). L'apprendimento attivo come framework concettuale è stato sistematicamente esaminato da Burr Settles (2010), che ha documentato il campionamento dell'incertezza basato su pool (pool-based uncertainty sampling), la query per comitato (query-by-committee) e le strategie ponderate per densità. Il KNN è stato utilizzato come "base learner" nei benchmark di apprendimento attivo basati su pool almeno dai lavori fondamentali di Cohn, Atlas e Ladner (1994), apprezzato per il suo segnale di incertezza trasparente e il costo di riaddestramento nullo per iterazione.
Quando usarlo
Utilizzare l'apprendimento attivo con KNN quando i dati etichettati sono scarsi o costosi da ottenere, le istanze non etichettate sono abbondanti, lo spazio delle feature ha una dimensionalità moderata e il confine decisionale è previsto essere localmente liscio. È particolarmente pratico nei progetti di classificazione in fase iniziale in cui l'etichettatura deve essere razionata. Evitarlo quando il dataset è ad altissima dimensionalità (le metriche di distanza del KNN si degradano in alte dimensioni, la maledizione della dimensionalità), quando il pool etichettato è già grande (il KNN passivo è sufficiente), quando è richiesta una predizione a bassa latenza su larga scala (la predizione del KNN è O(n) nel set etichettato), o quando il budget di etichettatura è così piccolo che le stime del vicinato sono inaffidabili.
Limiti e considerazioni
- Il costo di predizione scala linearmente con la dimensione del set etichettato, rendendo l'inferenza lenta man mano che il pool cresce attraverso le iterazioni.
- L'incertezza basata sulla distanza si degrada drasticamente negli spazi ad alta dimensionalità a causa della maledizione della dimensionalità.
- Il "ceiling" di accuratezza del KNN è inferiore a quello dei metodi ensemble; la strategia attiva non può compensare la capacità limitata del "base learner".
- Sensibile alla scelta di k e della metrica di distanza; impostazioni predefinite scadenti portano a stime di incertezza inaffidabili.
- Tutti i punti etichettati sono memorizzati in memoria; budget elevati comportano un alto consumo di memoria.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Non parametrico e privo di assunzioni: non sono richieste assunzioni distributive sui dati.
- La stima dell'incertezza è naturale e interpretabile — riflette direttamente la divisione dei voti tra i vicini più prossimi.
- L'apprendimento pigro significa nessun costo di riaddestramento per iterazione; il set etichettato espanso è il modello aggiornato.
- Efficace nel concentrare le etichette vicino ai confini decisionali, producendo una buona risoluzione del confine con poche annotazioni.
- Funziona bene su dati tabulari di dimensionalità moderata con feature sia continue che binarie.
Applicazioni
- Annotazione di cartelle cliniche o immagini dove il tempo di etichettatura degli esperti è limitato e i confini decisionali sono localmente lisci.
- Classificazione di testi o documenti con piccoli corpora etichettati e abbondanti documenti non etichettati utilizzando distanze basate su embedding.
- Compiti di rilevamento di guasti in sensori e nell'industria dove solo una frazione degli eventi può essere verificata manualmente.
- Indagini ecologiche dove la conferma sul campo delle etichette delle specie è costosa e localmente raggruppata.
- Classificatori prototipo in fase iniziale prima di passare a un modello con maggiore capacità una volta raccolte sufficienti etichette.
Come funziona
Come funziona
Un piccolo set iniziale di istanze etichettate viene assemblato per avviare il processo, insieme a un pool più ampio di istanze non etichettate. Si raccomanda una selezione casuale stratificata per garantire la presenza di almeno un esempio per classe, fornendo al KNN un vicinato iniziale significativo prima dell'inizio del ciclo attivo.
Un classificatore KNN viene addestrato sul set etichettato corrente utilizzando un k e una metrica di distanza scelti (comunemente Euclidea o coseno). Poiché il KNN è un algoritmo pigro e memorizza tutti i punti di addestramento, l'addestramento è istantaneo, ma il costo di predizione scala linearmente con la dimensione del set etichettato — una considerazione rilevante man mano che il pool cresce attraverso le iterazioni.
Ogni istanza non etichettata viene valutata in base a un criterio di informatività. Il campionamento del margine (margin sampling) calcola il divario tra le quote di voto delle due classi principali tra i k vicini; il campionamento dell'entropia (entropy sampling) calcola H(y-hat | x) su tutte le proporzioni di classe. Viene interrogata l'istanza con il margine più piccolo o l'entropia più alta: x* = argmax H(y-hat | x).
Formula
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)L'istanza interrogata viene inviata a un oracolo — un annotatore umano o un meccanismo di etichettatura automatizzato — per ottenere la sua vera etichetta. L'etichetta viene aggiunta al set di addestramento e l'istanza viene rimossa dal pool non etichettato. L'affidabilità dell'annotatore dovrebbe essere monitorata, poiché le etichette rumorose degradano drasticamente le prestazioni del KNN vicino ai confini.
Poiché il KNN è un "lazy learner" (apprendimento pigro), non è necessario un riaddestramento esplicito; il set etichettato espanso costituisce immediatamente il nuovo modello. Il ciclo di interrogazione-punteggio-etichettatura si ripete fino all'esaurimento del budget di etichettatura, al raggiungimento di una soglia di accuratezza di validazione o al raggiungimento di un numero massimo di iterazioni. Le prestazioni finali vengono riportate su un set di test indipendente tenuto separato.
Errori comuni
- Mancata normalizzazione delle feature prima di calcolare le distanze, causando il dominio delle feature di grande magnitudine sul vicinato.
- Utilizzo del set di test per guidare o valutare la selezione delle query, il che costituisce una "data leakage" (fuga di informazioni).
- Impostazione di k troppo piccolo (k=1) vicino al confine decisionale, producendo punteggi di incertezza altamente variabili che non riflettono la vera ambiguità.
- Ignorare lo squilibrio di classe nel set iniziale, il che polarizza le query iniziali verso i confini della classe di maggioranza.
- Trattare l'accuratezza dell'apprendimento attivo come equivalente a una baseline completamente supervisionata senza riportare il numero di etichette utilizzate.
Domande frequenti
Perché usare il KNN piuttosto che un modello più potente come base per l'apprendimento attivo?
L'incertezza basata sulla divisione dei voti del KNN è economica da calcolare e non richiede riaddestramento — l'aggiunta di un nuovo punto etichettato aggiorna immediatamente il modello. Questo lo rende attraente quando il costo computazionale per iterazione è importante. Per la massima accuratezza con un budget di etichette fisso, i "base learners" ensemble come random forest o gradient boosting superano tipicamente il KNN.
Come scelgo k per l'apprendimento attivo?
Un intervallo iniziale comune è k = 5 a 15. Valori di k più piccoli producono stime di incertezza più rumorose; valori di k più grandi "lisciando" il confine ma possono perdere ambiguità a grana fine. Effettuare una "cross-validation" di k sul set iniziale di semi etichettati e aggiustare man mano che il pool etichettato cresce.
La scalatura delle feature è importante?
Sì, in modo critico. La distanza del KNN è dominata da feature di grande magnitudine se le feature non sono normalizzate. Applicare sempre la scalatura min-max o la standardizzazione z-score prima di calcolare distanze e punteggi di incertezza.
Quanti esempi etichettati iniziali sono necessari?
Al minimo, sono richieste una o due istanze etichettate per classe affinché il KNN possa formare vicinati per tutte le classi. In pratica, 5–20 istanze etichettate forniscono stime di incertezza iniziali più stabili; un numero inferiore rischia vicinati degeneri che producono query iniziali non informative.
Quando dovrei interrompere il ciclo attivo?
Impostare un budget di etichettatura in anticipo, o monitorare l'accuratezza di validazione e interrompere quando il miglioramento per nuova etichetta scende al di sotto di una soglia significativa. Non usare mai il set di test come segnale di arresto, poiché ciò "leaks information" (fa trapelare informazioni) nel processo di interrogazione.
Metodi correlati
Fonti
Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.
Apri il riferimento della pubblicazioneCopiato.Zhu, X., Lafferty, J., & Ghahramani, Z. (2003). Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the ICML 2003 Workshop on the Continuum from Labeled to Unlabeled Data, 58–65.
Apri il riferimento della pubblicazioneCopiato.