(Normalized Compression Distance)
Gruppo MAPAG
Ingenito 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 spamfiltering 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 ddimensionale 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 crossvalidation 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
yi(xi ·w+b)−1 ≥ 0.

Ve la risparmio!!!
Grazie ;)