Il problema della classificazione

Macchine che
prendono decisioni
Docente: Edmondo Trentin
[email protected]
http://www.dii.unisi.it/~trentin
Problemi di decisione
(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. PERCEZIONE: un PROCESSO DI ESTRAZIONE
DI FEATURE rappresenta una descrizione digitalizzata
dell’evento all’interno di uno spazio vettoriale
3. AZIONE: 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 di decisione 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
Intelligenza artificiale sub-simbolica:
argomenti 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..
2.3 Stimatori nonparametrici
Density estimation e Parzen Window. Tecniche
nearest neighbor (NN) e k-NN. 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
Trentin&Gori. Applicazioni.
5. CENNI ALLA
CLASSIFICAZIONE DI DATI
STRUTTURATI
Dati strutturati e grafi, esempi.
Modelli bayesiani e neurali caso
supervisionato e non-supervisionato.