(Normalized Compression Distance)

Gruppo MAPAGIngenito AntonioIngenito Antonio

0521000141

Con il termine classificazione ci si riferisce al piazzamento di oggetti di test sconosciuti in una della categorie ricavate dall'insieme di oggetti di training.

Tratteremo la combinazione tra NCD ed un modulo di machine learning

• L'obiettivo di una procedura di classificazione è di fare le buone previsioni basate sui dati di training dell'input.

• Un esperto umano prepara un insieme di n esempi di training.

• Ogni esempio di training contiene un vettore di input x d-dimensionale ed una etichetta y dell'obiettivo del training. y deve essere scelto da un insieme L di etichette.

• L'accuratezza è limitata all'accuratezza delle etichette del training set.

• Una sessione di training esegue un modello M dell'input o dei dati di training (xi, yi) per 1≤i≤n

• Dopo che M sia stata calcolata da un classifier learning algorithm, denominato trainable classifier system, viene usata per classificare gli oggetti di test sconosciuti xtest, anche della dimensione d

• Per ogni oggetto ci sarà in output un elemento appartenente ad L

Uno dei primi sistemi che hanno usato i classificatori sono stati gli OCR(Optical Character Recognition) ossia a partire da un’immagine Bitmap Rasterized (che è un matrice di valori) e convertirla in caratteri ASCII con un algoritmo di recognition dei simboli.

In una fase di preprocessing, l’immagine, viene suddivisa in sotto immagini, ognuna contenente un unico simbolo (o glyph).

Ogni quadrato ha lo stesso formato e il glyph è centrato.

I pixel possono non essere letti in ordine e convertiti in una successione dimensioni

x = (x1, . . . , xd), il pixel i corrisponde alla dimensione xi

Per ogni pixel, un colore di background è rappresentato da 0 e da un colore di foreground da 1

Ogni x è un vettore binario con la dimensione uguale al numero di pixel dell’immagine del singolo carattere ottenuto della fase di preprocessing che circonda ogni simbolo

L‘output del sistema di classificazione è un singolo carattere preso in un’insieme di caratteri possibili

Alla procedura di training si da in input una sequenza di training ((x1, y1)...,(xn, yn)) e darà in output un classificatore "istruito" M.

Il classificatore M dovrà essere utilizzato per ogni nuovo esempio x(vettore di pixel che rappresenta un carattere) per fare la predizione della corrispondente classe y(l’attuale carattere)

Il più semplice classificatore è denominato classificatore binario. Questo tipo di classificatore può produrre soltanto due etichette in output per ogni caso della prova. Le etichette sono scritte solitamente +1 e -1 o 0 e 1 secondo il problema

Ci sono due modi per creare classificatori multi classe a partire da classificatori binari:◦ one-of-k style◦ A Coppia

Un esempio comune della classificazione binaria è lo spam-filtering problem. Questo problema deve determinare se un dato messaggio di email è non automaticamente una pubblicità commerciale indesiderata (Spam) o prima che sia portato all'attenzione di un utente del email.

Un altro esempio di classificatore è il classificatore dei multiclass classifier. Questo tipo di classificatore applica più di due tipi di etichette differenti. Ciò è utile nei casi di riconoscimento di una cifra scritta a mano, dove ci sono almeno dieci etichette differenti per le cifre scritte a mano che devono essere date in output

one-of-k style: un classificatore è addestrato per ogni classe, per ognuna delle k classi del problema di classificazione multiclass.

Ogni classificatore è istruito per distinguere solo membri della propria classe e rifiutare membri di ogni altra classe(return 0)

Istruisce a coppia classificatori binari separati per distinguere ogni un singola coppia di classi disordinate, prese in considerazione

È usato uno schema di “votazione” per determinare la classe vincitrice tra tutti i classificatori, per ogni test in input.

Questo provoca O(k2) classificatori per k classi

One-of-k è meno esatto ma più semplice e veloce

A coppia è più accurata ma meno veloce

Il più semplice modo per usare NCD per classificare è lo scegliere, per ognuna delle k classi un singolo oggetto prototipo che in qualche modo catturano l’essenza della categoria.

Se volessimo distinguere l’inglese dal cinese, si potrebbe usare un dizionario per l’inglese come prototipo per la classe inglese ed un dizionario per il cinese come prototipo per la classe cinese.

la classificazione è fatta calcolando l’NCD dell'oggetto di test con ciascuno dei k oggetti del prototipo e selezionando la classe che corrisponde all'oggetto con il minimo valore di NCD

Questo metodo, funziona bene per alcuni domini, mentre ci sono piccoli problemi di classificazione su molti altri di un errore incorreggibile

Questi problemi, sono dovuti al fatto che le classi diverse di molti problemi(come le classi dei caratteri dell’OCR), spesso non sono ben bilanciate sotto alcuni tipi di compressori.

La classe del carattere di pixel del numero ”1” è sufficientemente sottile ed ha un alto valore di NCD confrontata con molti altri membri della classe degli 1.

Diversamente con il numero 8, che ha una ricca combinazione di figure e tende a comprimere bene la maggior parte delle altri immagini dovute all’ampia varietà di match possibili

Questo porta ad un errore costante che non può essere migliorato poiché non sono disponibili cambiamenti naturali.

La più semplice soluzione del problema per usare NCD con una classificazione molto accurata è quella di combinarla con un sistema di classificazione istruibile usando NCD ed una tecnica di estrazione delle caratteristiche.

Un sistema di classificazione istruibile prova a trovare le relazioni funzionali in un range discreto (l’insieme di classi)

Come le reti neurali e la SVM(Support Vector Machines), sono costruiti su algoritmi di learning continui, che fanno parte di un’ampia classe di algoritmi di computer learning.

Data una sequenza di training, ◦ (x1, y1), . . . , (xn, yn)

Impara/da come output una funzione continua M mappando un vettore di input d-dimensionale in reali unidimensionali

Nello stesso modo in cui impara, l’algoritmo di training può essere trasformato in un algoritmo di learning per classificatori binari.

Classificando il test vector x = 1 se M(x)>0 x=-1 se M(x)<0

Applicando questa idea, ad un problema di oggetti sconosciuti, in un qualche sono convertiti in un vettore di dimensioni fissate, usando lo stesso ordine di proiezione usata da NCD.

Una delle tecniche più semplici è di creare d oggetti dome ancore ed usarle per convertirle tutti gli altri oggetti dell’esperimento in vettori d-dimensionali

Ciò può essere memorizzato usando l'oggetto ancora ai per calcolare la dimensione del vettore i per 1≤i≤d

Cioè per oggetto o calcoliamo il corrispondente x = (x1..., xd) usando ◦ xi = NCD(o, ai).

L’ancora può essere scelta da un esperto umano o in modo casuale da un grande insieme di oggetti di training.

Si consiglia di prendere almeno un ancora per ogni categoria in modo da non avere abbassamento dell’accuratezza dovuta all’insufficiente variazione dell’ancoraggio

NCD può usare le ancore Può essere usato anche con la

Normalizzazione delle Distanze di Google(NDG)

Nella scelta di un sistema di learning con l’estrazione di caratteristiche mediante ancore sembra la migliore

Una particolare classe di algoritmi di learning sono chiamati Universal Continuous Funcution Lerners che includono◦ Reti Neurali◦ SVM (Support Vector Machine)

La proprietà di Universal Learning in questo contesto significa che possiamo approssimare ogni funzione continua ad un qualsiasi alto grado di accuratezza dato un sufficiente numero di dati di training vicini al punto che stiamo prendendo in considerazione

Usando questa proprietà su un classificatore, si assicura un aumento di affidabilità ed ottimalità dei risultati generati rispetto ad molti altri algoritmi di learning specializzati

Sia le reti neurali che la SVM, prendono in input un insieme di etichette dei dati di training ed alcuni modelli parametri specializzati che devono essere settati.

In generale i parametri specializzati, sono settati da un esperto umano o da un insieme di procedure automatiche usando cross-validation basate su parameter scanning

Hanno il vantaggio di essere sistemi di classificazione universali

Hanno tantissime procedure di training◦ In questa tesi sono state scelte

Fast Backpropagation Self Organizing Maps(SOM)

◦ SOM non è stato progettato esplicitamente per la classificazione, ma è stato facilmente adattato per essere usato per la classificazione in quando usato congiuntamente alla metrica di compressione come NCD

C’è stata una grande difficoltà con tutti i tipi di reti neurali,

Alcune regolazioni erano difficili da mettere appunto

Ci sono delle componenti non lineari(funzione di trasferimento) ed alcune scelte come le funzione sigmoid trascendental come l’arcotangente

Un altro difficile problema d’affrontare quando si usano molti tipi di reti neurali è il decidere quanti strati debbano essere usati e per ogni specifico livello, quanti debbano avere un certo settaggio

Ci sono quattro difficili scelte prima di decidere quale rete neurale e poiché presentano tutte tanti problemi si fanno due scelte di addestramento:◦ Overlearning◦ Underlearning

Si ha quando ci sono troppi neuroni Durante la fase di training, la rete neurale

sembra che abbia una grande accuratezza sui dati, ma essendo troppi, non riesce a generalizzare

Quando ci sono pochi neuroni L’esattezza della risposta si ha solo in un

numero ristretto di dati in input

E’ difficile dire quali siano i parametri migliori

I sistemi commerciali usano una elevata quantità di macchinari semi-automatici per aiutare l’utente a settare i parametri

Questi problemi portano ad una difficile integrazione tra sistemi easy-to-use e sistemi di addestramento parameter-free

La Statistical Learning Theory, detta anche teoria di Vapnik –Chervonenkis, caratterizza le proprietà di algoritmi di apprendimento che permettono loro di generalizzare a dati nuovi elementi appresi in precedenza.

Una SVM è un classificatore binario che apprende il confine fra esempi appartenenti a due diverse classi.

Funziona proiettando gli esempi in uno spazio multidimensionale e cercando un iperpiano di separazione in questo spazio.

L'iperpiano di separazione massimizza la sua distanza (il “margine”) dagli esempi di training più vicini.

Proprietà generali delle SVM:◦ improbabile l'overfitting, ◦ Capacità di gestire dati con molte

caratteristiche descrittive,◦ compattamento dell'informazione

Per usare una SVM si ha bisogna scegliere una funzione di Kernel che la corrispondente funzione di trasferimento nelle reti neurali

La funzione Kernel va scelta accuratamente per un tipo di problema: è sempre possibile mappare l’input in uno spazio di dimensione maggiore del numero di punti del training set e produrre un classificatore perfetto; tuttavia questi generalizzerebbe malissimo su dati nuovi, per via dell’overfitting.

Ci sono due parametri per la SVM◦ C è la costante delle risposte sbagliate◦ g rappresenta il kernel e determina il tasso di

decadimento esponenziale intorno a ciascuno dei punti di training

Ve la risparmio!!!

yi(xi ·w+b)−1 ≥ 0.

Grazie ;)