Classificatore ECOC
Nell'apprendimento automatico, un classificatore ECOC (ossia basato su codici di output con correzione degli errori) rappresenta una tecnica di apprendimento d'insieme utile a migliorare l'accuratezza di singoli algoritmi di classificazione, in particolare nei problemi di classificazione multiclasse. Questo approccio sfrutta i principi della correzione degli errori della teoria dell'informazione per migliorare la robustezza e l'affidabilità dei classificatori. La strategia scompone un problema di classificazione multiclasse in più problemi di classificazione binaria. Assegnando codici binari a ciascuna classe, il classificatore ECOC (Error Correcting Output Codes) sfrutta i principi della correzione degli errori per gestire gli errori di classificazione in modo più efficace.
La tecnica stata introdotta per la prima volta da Dietterich e Bakiri nel 1995 come metodo per migliorare le prestazioni dei classificatori sfruttando i codici di correzione degli errori. L'idea di base è quella di rappresentare ogni classe con un codice binario univoco e quindi addestrare più classificatori binari a distinguere tra questi codici. L'idea-base di ECOC deriva dal campo dei codici di correzione degli errori nella teoria dell'informazione, dove viene aggiunta ridondanza ai dati per rilevare e correggere gli errori durante la trasmissione.
I classificatori ECOC, grazie alla loro capacità intrinseca di correggere gli errori e di scomporre problemi complessi in compiti più semplici, trovano spazio in moltissimi campi ad alta precisione. Le principali applicazioni reali suddivise sono la visione artificiale e il riconoscimento delle immagini, bioinformatica e medicina, elaborazione del linguaggio naturale e text mining, ingegneria e controllo della qualità.
Dettaglio
Il processo ECOC prevede due fasi principali: la codifica e la decodifica.
Codifica
- il primo passo consiste nel costruire una matrice di codici, in cui ogni riga rappresenta una classe e ogni colonna rappresenta un classificatore binario. Gli elementi della matrice sono in genere
-1,0o+1, dove-1e+1indicano le due classi del classificatore binario, mentre0indica che il classificatore non prende in considerazione quella classe; ogni colonna della matrice di codice corrisponde a un problema di classificazione binaria: i classificatori binari vengono addestrati utilizzando i dati, dove le etichette sono determinate dalle voci nella matrice dei codici.
Decodifica
- per una nuova istanza, ogni classificatore binario effettua una predizione, ottenendo un vettore binario; il vettore binario predetto viene confrontato con le parole in codice nella matrice; la classe con la parola in codice più vicina (di solito misurata dalla distanza di Hamming) viene selezionata come classe predetta dal classificatore ECOC.
Esempio
Sistema di smistamento automatico per i rifiuti tecnologici. Supponiamo che un braccio robotico debba classificare un oggetto elettronico in una di K=4 classi:
- Smartphone (C1)
- Laptop (C2)
- Tastiera (C3)
- Cavo (C4)
Si può progettare un classificatore ECOC usando una strategia ECOC Binaria Completa per correggere eventuali errori dei singoli algoritmi.
Matrice di Codifica
Nel contesto degli ECOC, lo 0 significa "indifferente" (o don't care): vuol dire che quel determinato classificatore viene addestrato ignorando completamente le classi contrassegnate con lo zero. Questo è utilissimo nella strategia One-vs-One (uno contro uno), dove ogni classificatore si concentra solo su una coppia di classi, ignorando le altre.
Per 4 classi, il numero di coppie possibili (e quindi di classificatori necessari) è dato dal numero di combinazioni: K(K−1)/2 = 6 classificatori
Una matrice basata su questo approccio è la seguente:
| Classe | f1 (S vs L) |
f2 (S vs T) |
f3 (S vs C) |
f4 (L vs T) |
f5 (L vs C) |
f6 (T vs C) |
|---|---|---|---|---|---|---|
| C1 | +1 |
+1 |
+1 |
0 |
0 |
0 |
| C2 | -1 |
0 |
0 |
+1 |
+1 |
0 |
| C3 | 0 |
-1 |
0 |
-1 |
0 |
+1 |
| C4 | 0 |
0 |
-1 |
0 |
-1 |
-1 |
Ad esempio il classificatore f1 (Smartphone vs Laptop):
- Viene addestrato usando solo esempi di Smartphone (
+1) e Laptop (-1). - Gli esempi di Tastiere e Cavi (
0) vengono escluse dal suo addestramento.
Fase di Test
Sul nastro trasportatore si presenta una Tastiera (C3). Il robot usa tutti e 6 i classificatori. Poiché essi restituiscono un valore binario (+1 o -1) basandosi su ciò che hanno imparato, ecco cosa succede:
- f1 (S vs L): Vede una tastiera, si confonde (visto che per lui è un oggetto sconosciuto) e restituisce un output casuale, ad esempio
+1. - f2 (S vs T): Riconosce la tastiera. Output:
-1. - f3 (S vs C): Si confonde. Output:
-1. - f4 (L vs T): Riconosce la tastiera. Output:
-1. - f5 (L vs C): Si confonde. Output:
+1. - f6 (T vs C): Riconosce la tastiera. Output:
+1.
Il vettore predetto dal robot è:
xpred = [+1,−1,−1,−1,+1,+1]
Decodifica e Correzione dell'Errore
Quando si usa anche lo zero, non si può usare la normale distanza di Hamming, perché lo zero teorico della matrice non deve essere penalizzato se il classificatore ha risposto +1 o -1. Si adotterà una funzione di calcolo che ignora le posizioni in cui la matrice ha uno 0. Contiamo le discrepanze solo dove la matrice prevede +1 o -1:
- Distanza da C1 (Smartphone) -> Codice teorico:
[+1,+1,+1,0,0,0]- Confrontando solo i primi 3 bit di xpred
[+1,-1,-1]; errori: posizione 2 e 3. Distanza = 2
- Confrontando solo i primi 3 bit di xpred
- Distanza da C2 (Laptop) -> Codice teorico:
[-1,0,0,+1,+1,0]- Confrontando i bit nelle posizioni 1, 4, 5 di xpred
[+1,...,...,-1,+1,...]; errori: posizione 1 (+1invece di-1) e posizione 4 (-1 invece di +1). Distanza = 2
- Confrontando i bit nelle posizioni 1, 4, 5 di xpred
- Distanza da C3 (Tastiera) -> Codice teorico:
[0,-1,0,-1,0,+1]- Confrontando i bit nelle posizioni 2, 4, 6 di xpred
[...,-1,...,-1,...,+1]; errori: 0 (tutti i classificatori competenti hanno indovinato). Distanza = 0
- Confrontando i bit nelle posizioni 2, 4, 6 di xpred
- Distanza da C4 (Cavo) -> Codice teorico:
[0,0,-1,0,-1,-1]- Confrontando i bit nelle posizioni 3, 5, 6 di xpred
[...,...,-1,...,+1, +1]; errori: posizione 5 e 6. Distanza = 2
- Confrontando i bit nelle posizioni 3, 5, 6 di xpred
Predizione: classe vincitrice C3 (Tastiera) con una distanza perfetta (nulla)
Grazie agli zeri, il sistema ha saputo "filtrare" il rumore e l'incertezza causati dai classificatori non competenti (f1,f3,f5), focalizzandosi solo sulle risposte di quelli che erano stati effettivamente addestrati per riconoscere la tastiera.
Note
- ↑ (EN) Ethem Alpaydin, Ch.18 - Combining Multiple Learners, in Introduction to machine learning, collana Adaptive computation and machine learning series, Fourth edition, The MIT Press, 2020, ISBN 978-0-262-04379-3.
- ↑ Sergio Escalera, Oriol Pujol e Petia Radeva, Error-Correcting Output Codes Library, in Journal of Machine Learning Research, vol. 11, n. 20, 2010, pp. 661–664.
- ↑ (EN) T. G. Dietterich e G. Bakiri, Solving Multiclass Learning Problems via Error-Correcting Output Codes, in Journal of Artificial Intelligence Research, vol. 2, 1º gennaio 1995, pp. 263–286, DOI:10.1613/jair.105.
- ↑ Koby Crammer e Yoram Singer, On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines, in Journal of Machine Learning Research, vol. 2, Dec, 2001, pp. 265–292.
- ↑ Erin L. Allwein, Robert E. Schapire e Yoram Singer, Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers, in Proceedings of the Seventeenth International Conference on Machine Learning, Morgan Kaufmann Publishers Inc., 29 giugno 2000, pp. 9–16, DOI:10.5555/645529.658120.
