Riconoscimento di
forme
Docente: Edmondo Trentin
[email protected]
http://www.dii.unisi.it/~trentin
Problemi di classificazione








Il cambiamonete
Riconoscimento del parlato
Riconoscimento del labiale
Riconoscimento del parlatore
Identificazione per sistemi di sicurezza (iride, impronte
digitali)
Riconoscimento di caratteri
Classificazione di immagini
Classificazione in ambito biomedico (ECG) e
bioinformatico (genomica funzionale e strutturale)
Schema generale del sistema
Evento
Estrai feature
Classifica
Classe
1. Nel mondo reale si verifica un EVENTO (es. istanza di
un oggetto)
2. Un PROCESSO DI ESTRAZIONE DI FEATURE
rappresenta una descrizione digitalizzata dell’evento
all’interno di uno spazio vettoriale
3. Un PROCESSO DI CLASSIFICAZIONE determina la
CLASSE di appartenenza dell’evento tra c classi possibili
Importanza delle feature


Lo stesso problema di classificazione assume
difficoltà diversa a seconda delle feature che si
hanno a disposizione (es. gender classifier)
Le feature devono essere il più possibile
compatte (dim. ridotta) e informativamente
ricche
Tipi di feature



Numeriche (discrete o continue): numero di pixel neri
in una bitmap, frequenza di un suono, angolo di
inclinazione di una linea di testo manoscritto, peso e
dimensioni di un oggetto, …
Simboliche: simboli o stringhe di simboli su un certo
alfabeto finito e discreto (es. testi letterari, sequenze
aminoacidiche)
Qualitative: alto, basso, grosso, piccolo, rosso, blu,
buono, cattivo, normale, strano, …
Useremo soprattutto feature numeriche. Quelle qualitative
potranno essere codificate con valori numerici.
Estrazione di feature: esempio 1
Estrazione di feature: esempio 2
Forma d’onda
Coefficenti “spettrali”
Funzione discriminante




Sia dato un problema a c classi
I pattern x sono vettori d-dimensionali
Per ogni classe i, i=1,…,c, si cerca di definire
una funzione discriminante g(i,x) tale che:
g(i,x)>g(j,x) sse x è di classe i
Ad ogni nuovo evento, il classificatore si limita
dunque a determinarne la classe di appartenenza
sulla base della funzione discriminante che ha
valore maggiore
Approccio intuitivo 1: distribuzioni
di probabilità delle classi
Approccio intuitivo 2: superfici di
separazione
Programma del corso
1. INTRODUZIONE
Esempi di problemi di classificazione. Estrazione
di feature e classificatore. Feature numeriche
(discrete o continue) e qualitative. Esempi di
estrazione di feature. Funzione discriminante.
Approcci intuitivi: linea di separazione, superficie di
separazione, caratterizzazione statistica della
distribuzione. Classificazione su dati statici e
dinamici. Richiamo di elemnti di statistica
multivariata. La Normale multivariata.
2.APPRENDIMENTO SUPERVISIONATO
2.1 Teoria Bayesiana delle decisioni
Apprendimento supervisionato. Teorema di
Bayes. Rischio Bayesiano, probabilita' di
errore, equal error rate. Classificazione: 2-classi
vs c-classi. Superfici di separazione. Funzioni
discriminanti: il caso notevole della Normale.
2.2 Stimatori parametrici
Nozione di stimatore parametrico nel
caso supervisionato. Stima a massima
verosimiglianza (ML). Stima ML per i
parametri della Normale. Validazione e
generalizzazione: training, validation e
test
set.
Leave-1-out.
Many-fold
crossvalidation. Bootstrap.
2.3 Stimatori nonparametrici
Elementi su density estimation e Parzen
Window. Tecniche nearest neighbor (NN) e kNN. Discriminanti lineari (superfici di
separazione
2-class/c-class;
funzioni
discriminanti lineari generalizzate; separabilita' e
non-separabilita'; algoritmo di Widrow-Hoff;
relazione con i Simple Perceptron); reti neurali
artificiali (ANN); universalita'; relazioni tra
MLP e classificatori Bayesiani; funzioni a base
radiale (RBF); elementi di generalizzazione e
regolarizzazione.
3. APPRENDIMENTO NON
SUPERVISIONATO
Misture di densita', identificabilita', stima ML
unsuprevised. Stima ML per misture di
componenti Gaussiane. Approccio algoritmico:
k-means. Clustering: misure di similarita',
ottimizzazione iterativa (mse), clustering
gerarchico (agglomerativo, partitivo). ANN
competitive e loro relazione con k-means;
ANN a ML per stima di densita' di probabilita'.
4. CLASSIFICAZIONE DI DATI SEQUENZIALI
Esempi (OCR e bioinformatica); il problema del
riconoscimento del parlato: modello acustico e
modello del linguaggio; reti neurali ricorrenti,
backpropagation through time, limitazioni.
Modelli di Markov nascosti (HMM); i 3
problemi fondamentali, trellis, algoritmi di BaumWelch e Viterbi, limitazioni. Ibridi ANN/HMM:
modello di Rigoll, segmental neural net, approccio
di Bengio; uso della rete per stime di probabilita':
paradigma di Bourlard&Morgan, paradigma di
Trenin&Gori. Applicazioni.
5. CENNI ALLA
CLASSIFICAZIONE DI DATI
STRUTTURATI
Dati strutturati e grafi, esempi.
ANN ricorsive e encoding net; caso
supervisionato e non-supervisionato.