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, 0 o +1, dove -1 e +1 indicano le due classi del classificatore binario, mentre 0 indica 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: Classef1(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 +1000C2 -100 +1 +10C30 -10 -10 +1C400 -10 -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 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 (+1 invece di -1) e posizione 4 (-1 invece di +1). Distanza = 2 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 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

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

Categoria:Apprendimento automatico