Post on 01-May-2015
Classificatore bayesianoDate k classi C1, C2, …, Ck e il vettore x
delle osservazioni, la probabilità a posteriori vale:
)(
)/()()/(
x
xx
p
CpCPCP ii
i
)(
)/(
)(
x
x
p
Cp
CP
i
i probabilità a priori
densità di probabilità condizionata alla classe
densità di probabilità non condizionata
∑∑11
1)/(→)/()()(k
ii
k
iii CPCpCPp
xxx
)/( iCp x quando è parametrica è detta funzione di verosimiglianza (likelihood)
fattore di normalizzazione
zionenormalizza
ianzaverosimiglprioriposteriori
×=
Decisione ottimaLa probabilità a posteriori P(Ci/x) definisce la probabilità del pattern di appartenere alla classe Ci
La probabilità di misclassificazione è minimizzata scegliendo la classe Ci che ha la maggiore probabilità a posteriori, cosicchè il pattern è assegnato alla classe Ci se: ijCPCP ji ≠∀per)/()/( xx
ijCpCPCpCP jjii ≠∀per)/()()/()( xx
semplificando il fattore di normalizzazione comune, si ha:
N.B. Il confronto è relativo alle d. p. congiunte
Regioni e superfici di decisione
Possiamo concepire lo spazio delle variabili come diviso in k regioni di decisione R1, R2, ..., Rk tali per cui un punto appartenente a Rk è assegnato alla classe Ck
Le regioni devono essere disgiunte, ma non necessariamente contigueLe regioni devono essere disgiunte, ma non necessariamente contigue
I confini tra le regioni sono detti confini o I confini tra le regioni sono detti confini o superficie di decisionesuperficie di decisione
R1
R2
R3 R2R3
R4
R1 R2
R5
R1
Il classificatore bayesiano definisce una regola per assegnare ogni
punto dello spazio delle variabili a una delle k classi
Errore di misclassificazioneCon riferimento a due sole classi e una sola variable x, si ha:
dxCPCxpdxCPCxp
CPCRxPCPCRxP
CRxPCRxPP
RR
errore
∫∫21
)()/()()/(
)()/∈()()/∈(
),∈(),∈(
1122
112221
1221
)()/( 11 CPCxp
)()/( 22 CPCxp
1R 2R
Corretta classificazioneLa probabilità Pc di corretta
classificazione, relativa a k classi e a un vettore d-dimensionale delle variabili, vale:
k
iR ii
k
iiii
k
iiic
dCPCp
CPCRP
CRPP
i1
1
1
)()/(
)()/(
),(
xx
x
x
Il massimo di Pc si ha scegliendo le Ri per cui le osservazioni sono assegnate alla classe che massimizza l’integrando.Ciò corrisponde alla decisione di assegnamento del pattern nella classe con massima probabilità a posteriori.
Funzioni discriminantiIl classificatore bayesiano è basato sulle
distribuzioni di probabilità, ma la decisione di appartenenza alla classe dipende solo dalle dimensioni relative delle probabilità
Ciò conduce alla riformulazione del processo di classificazione nei termini di un insieme di funzioni discriminanti:
)(),...,(),( 21 xxx kyyy
Cosicché il vettore delle osservazioni è assegnato alla classe Ci se: ijyy ji ≠∀per )(>)( xx
La regola di decisione che minimizza la probabilità di misclassificazione può essere facilmente espressa attraverso le funzioni discriminanti, ponendo:)/()( xx ii CPy
Funzioni discriminanti trasformateUsando il teorema di Bayes e semplificando il fattore comune di normalizzazione, le funzioni discriminanti possono essere riformulate:
Poichè per la classificazione interessa solo la relativa grandezza delle funzioni discriminanti, possiamo sostituirle con una qualsiasi trasformazione monotona, come per esempio il logaritmo:
Le superfici di decisione non sono influenzate dalla trasformazione monotona e valgono:
)()/()( iii CPCpy xx
)(ln)/(ln)( iii CPCpy xx
)()( xx ji yy
Funzioni discriminanti per due classiNel caso di due classi, le funzioni discriminanti sono di solito espresse in forma leggermente diversa:
La regola di decisione quindi diventa:
Segue naturalmente anche:
)(-)()( 21 xxx yyy
0)(se
0)(se
2
1
xx
xx
yC
yC
)(
)(ln
)/(
)/(ln)(
)/(-)/()(
2
1
2
1
21
CP
CP
Cp
Cpy
CPCPy
x
xx
xxx
Minimizzazione del rischio
Considerando tutti i pattern che appartengono alla classe Ci, occorre allora attribuire un costo alla decisione:
Lij sono gli elementi di una matrice di perdita che specifica la penale associata con l’attribuzione alla classe Cj di un pattern che appartiene alla classe Ci.
xx )d/(j1
iR
k
jiji CpL
In taluni casi la regola di minimizzazione della probabilità di misclassificazione può non essere un criterio appropriato.P.es., nelle lesioni cutanee, classificare un melanoma come neo è molto più grave che classificare un neo come melanoma
Minimizzazionedel rischio
La perdita complessiva attesa per tutti i pattern di tutte le classi è:
xx d)()/()(1 11
k
j Rii
k
iiji
k
ii
j
CPCpLCP
Il rischio è minimo se l’integrando è minimizzato per ogni pattern, cioè se le regioni Rj sono scelte in modo che:
jRx
jhCPCpLCPCpL ii
k
iihii
k
iij
per)()/()()/(
11
xx
quando:
Costo della decisione di melanomaConsideriamo le classi: C1 = melanomi; C2 = nei Attribuiamo alla matrice di perdita i seguenti valori:
La lesione sarà allora assegnata ai melanomi se:
)/(10
1)/(→
10
1
)()/(
)()/(
)()/(10)()/(
)()/()()/()()/()()/(
22
11
1122
2222111222211111
xxx
x
xx
xxxx
NPMPCPCp
CPCp
CPCpCPCp
CPCpLCPCpLCPCpLCPCpL
01
100L=
melanomi come nei
nei come melanomi
melanomi come melanomi
nei come nei
N.B. La matrice di perdita determina una penalità nulla nell’assegnare la lesione nella giusta classe e una penalità 10 volte superiore all’errato assegnamento dei melanomi come nei
Soglia di rifiutoIn generale ci aspettiamo che molti degli errori di misclassificazione avvengano nelle regioni dove la più grande tra le probabilità a posteriori è relativamente bassa cosicché c’è ampia sovrapposizione tra classiIn alcune applicazioni è bene stabilire una soglia di probabilità (nell’intervallo [0,1]) sotto la quale il classificatore viene rifiutato, cioè:
x
xx
reclassifica di rifiuta
classifica)/(max
θ
θCP k
k
N.B. Nell’esempio dei melanomi, la soglia potrebbe servire per lasciare la diagnosi di lesioni particolarmente difficili al dermatologo esperto
Stima delle probabilità bayesianeIl classificatore bayesiano garantisce
l’errore di classificazione minimo purché siano note le probabilità a priori e le d. p. condizionate alle classi
)(
)/()(=)/(
x
xx
p
CpCPCP ii
i
In pratica le probabilità a priori e le d. p. vanno stimate attraverso i dati campionari del learning set.
N.B. La d. p. non condizionata al denominatore (fattore di normalizzazione) può essere espressa come somma delle d. p. congiunte di tutte le classi a loro volta scomponibili nel prodotto di probabilità a priori e d. p. condizionate
Stima delle probabilità a priori
kiCP i ,...,2,1=)(
In pratica, a fini di classificazione, le probabilità a priori possono anche essere incognite e stimate essere equiprobabili
Impostando il costo della decisione indipendentemente dalla probabilità a priori, possono sempre essere ricomprese nella matrice di perdita L
kik
CP i ,...,2,1=1
=)(ˆ
Stima delle densità di probabilità
kiCp i ...,,2,1)/( x
Le d. p. condizionate vanno stimate dal campione di learning facendo alcune ipotesi circa la loro distribuzione parametrica o ricorrendo a tecniche non parametriche
),ˆ/()/(ˆ iii CCp xx Metodi parametrici
Distribuzione parametrica
Vettore dei parametri stimato dalle osservazioni
campionarie
∑1
)(-1
)/(ˆin
j
j
ii K
nCp
xxx
Metodi non parametrici
Funzione kernel
Numero osservazioni in Ci
Distribuzione gaussiana È l’ipotesi parametrica più frequente
= matrice di covarianza (simmetrica) = vettore delle medied = dimensione delle feature
i
i
dkd
kd
Σ
μ
matrici leper par.2
)1(
vettoriiper parametri
superfici di separazione quadratiche
jijiji ≠|,∀per≠ ΣΣ
parametri2
)3+(dkd
jiji ,∀per= ΣΣ
superfici di separazione lineari
parametri2
)1+2+( kdd
( )
)-()-(2
1- 1-T
2π
1=)/(
iiieCp
idi
μxΣμx
Σx
melanomi neiBlue
content
Area (mm2)
x Bayesiano
lineareBayesian
o quadratic
o
Iperellissoide di confidenza
Termine esponenziale (quadrato della distanza di Mahalanobis) jjji
iii
uuΣ
μxΣμx
λ=
)-()-(=Δ -1T2
2 costante definisce un iperellissoide a probabilità costante.Gli autovettori uj e gli autovalori j di definiscono rispettivamente gli assi principali dell’iperellissoide e le varianze (semidiametri al quadrato)
( )α ,1-2 F
)-(
)1-(<Δ d-nddnn
nd
La regione di confidenza della media vera, con probabilità (1-), è:
n = numerosità campione d = dimensione dello spazio
(F-1)d,n-d = inversa della distribuzione F valutata in (1-), per d e n-d gradi di libertà
x1
x2
u1
u2
i 1λ
2λ
Classificatore bayesiano naïve
d
jijijjji CxpCp
1
2 )/()/()( xS
Matrice di covarianza diagonale variabili indipendenti. Direzioni principali degli ellissoidi di uguale probabilità allineate con le coordinate degli assi
Riduzione del numero di parametri a 2d
, ulteriore semplificazione con d+1 parametri e ipersfere come superfici di ugual probabilità
jj per Se
Proprietà della distribuzione gaussiana
1. Ha proprietà analitiche relativamente semplici
2. Il teorema del limite centrale afferma che la media di N variabili casuali tende alla distribuzione normale per N∞, in pratica già per N>10; molti fenomeni naturali hanno parecchi costituenti casuali che rendono normale la loro distribuzione
3. Qualsiasi trasformazione lineare del sistema di coordinate è ancora gaussiana (con medie e matrice di covarianza diverse) e mantiene 2 di forma quadratica e definita positiva
Proprietà della distribuzione gaussiana
4. Le d. p. marginali, ottenute integrando su qualche variabile, sono ancora gaussiane
5. Le d. p. condizionate, ottenute a valori costanti di alcune variabili, sono ancora gaussiane
6. Esiste una trasformazione lineare che diagonalizza la matrice di covarianza, porta a coordinate basate sugli autovettori, rende le variabili indipendenti e la d. p. si ottiene come prodotto delle d. p. delle singole variabili
7. Ha la massima entropia possibile
Funzioni discriminantiPassando al logaritmo e semplificando i termini classi-indipendenti :
Si tratta quindi di funzioni quadratiche nello spazio a d dimensioni
Se le matrici di covarianza sono uguali per tutte le classi, il termine con || si semplifica così come il termine quadratico xT-1x; poichè è simmetrica lo sarà anche la sua inversa e xT-1= T-1x, cosicchè la funzione discriminante diventa lineare:
)(ln+ln2
1-)-()-(
2
1-=)( 1-T
iiiiii CPy ΣμxΣμxx
)(ln+2
1-==
+=)(
1-T0
1-TT
0T
iiiiii
iii
CPw
w
μΣμΣμw
xwxy
Esercizio: valutare le d. p. con diagonale e P(Ci) tutte uguali
Stima dei parametriUna volta scelto il tipo di d. p. parametrica,
spesso gaussiana, occorre stimarne i parametri. Esistono vari metodi:
1. Massima verosimiglianza. Stima i parametri che massimizzano una funzione di probabilità determinata dai dati di learning
2. Inferenza bayesiana. I parametri vengono descritti da una distribuzione di probabilità che, tramite l’inferenza bayesiana, passa da una situazione a priori più incerta e con forma più allargata, alla probabilità a posteriori, affinata dai dati campionari, perciò di natura meno incerta con forma più stretta; la d. p. gaussiana relativa alle variabili di ingresso è ottenuta con un integrale fatto rispetto tutti i suoi parametri, pesato per la loro probabilità a posteriori
3. Metodi sequenziali. Tecniche iterative basate sull’aggiornamento del valore dei parametri ad ogni nuovo dato acquisito
Stima di massima verosimiglianzaAnche se nella classificazione bayesiana si tratta con la d. p. condizionata alle classi, ci riferiamo per semplicità alla d. p. non condizionata p(x) che dipende dal vettore dei parametri da stimare = (1, 2, …, M)T. Il processo andrà poi ripetuto per ogni classe separatamente. p(x) dipende da e dall’insieme di apprendimento, costituito dalla matrice dN degli N di vettori delle osservazioni:
)(=)(=)(
],..., ,[≡
∏1=
)(
)((2)(1)
θ/θx/θχ
xxxχ
LN
n
n
N
pp
La verosimiglianza (likelihood) L( ), si ottiene dalla produttoria delle d. p. di ogni singola osservazione poiché esse si considerano indipendenti e, per un dato , è solo funzione di
Massima verosimiglianzaPer molte d. p. l’ottimo di va cercato con tecniche
numeriche di minimizzazione iterative.Nel caso speciale della distribuzione gaussiana multivariata, la soluzione è analitica e vale:
∑
∑
1
T)()(
1
)(
ˆ-ˆ-1ˆ
1ˆ
N
n=
nn
N
n=
n
N
N
μxμxΣ
xμ
Sebbene l’approccio di massima verosimiglianza appaia intuitivamente ragionevole, ha qualche difetto. P.es., nel caso monovariato, la stima della varianza è distorta come segue perché è valutata rispetto alla stima campionaria della media22 σ
N
NσE
1-=]ˆ[
Inferenza bayesianaLa d. p. relativa alle variabili di ingresso non viene calcolata fissando i parametri ad uno specifico valore come accade per il metodo di massima verosimiglianza, ma rappresentandoli attraverso una funzione di probabilità
Prima di osservare i dati , i parametri vengono descritti da una d. p. a priori tipicamente piuttosto larga scarsa conoscenza dei valori che potrebbero assumere
Dopo che i dati sono stati osservati, la d. p. a posteriori si restringe attorno a valori di parametri più compatibili coi dati.
priorip()
posteriori
p( /)
Apprendimento bayesiano
Inferenza bayesiana
)/(),()/,(
d)/,()/(
χθχx/θχθx
θχθxχx
ppp
pp
La d.p. desiderata per il vettore x, una volta noti i dati di learning, si può esprimere come l’integrale della d.p. congiunta:
Il primo termine della d.p. congiunta è indipendente da
forma matematica parametrica della d.p. di x, pertanto:
θχθx/θχx d)/()()/( ppp
N.B. L’approccio bayesiano non trova un preciso valore di , ma effettua una media su tutti i valori della d.p. p(x,),
pesata per la d.p. a posteriori p(/ ) dei parametri
)(
)()(=)/(
χθθ/χ
χθp
ppp
La d.p. a posteriori dei parametri può essere valutata attraverso il teorema di Bayes:
La d.p. dei dati campionari condizionata ai parametri, p((/), è esprimibile come prodotto di probabilità poiché i dati sono assunti essere estratti dalla popolazione indipendentemente l’uno dall’altro (campionamento casuale):
∏1=
)( )/()(
)(=)/(
N
n
npp
pp θx
χθ
χθ
∏1=
)( )/(=)(N
n
npp θxθ/χ
Cosicchè:
'd)'/()'()( ∏1
)( θθxθχN
n
nppp
e
Inferenza bayesiana
In generale, gli integrali si risolvono difficilmente in modo analitico. È possibile solo se la d.p. a priori ha la stessa forma funzionale della d.p. a posteriori, detta perciò “coniugata”
Usando una successione di N punti è possibile applicare il processo inferenziale bayesiano ripetitivamente la d.p. a posteriori diventa la d.p. a priori del punto seguente e mantiene la stessa forma funzionale, restringendosi attorno al valore ‘vero’; tali d.p. sono dette “riproducibili”
Inferenza bayesiana
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10
0.5
1
1.5
2
2.5
3
3.5
4
4.5
N=0N=1
N=6
N=12
p(/)EsempioStima del valor medio , dati 12 punti estratti da una d.p. gaussiana monovariata con =0.8:uso di una d.p. a priori (N=0) di tipo gaussiano con 0=0 e 0=0.3
Esiste una semplice relazione tra le due tecniche quando il numero delle osservazioni N è sufficientemente alto
Trascurando il denominatore, indipendente da , con l’inferenza bayesiana si ha:
Inferenza bayesiana massima verosimiglianza
)()(∝)/( θθχθ pp L
La verosimiglianza L() ha un massimo per = Per N sufficientemente elevato, la funzione L() è stretta attorno al picco e l’integrale che stima la d.p. con la tecnica bayesiana può essere pertanto approssimato da:
θ̂
)ˆ(d)/()ˆ(~)/( θx/θχθθx/χx pppp
Metodi sequenzialiAggiornamento parametri ad ogni nuova osservazione
Godono di importanti proprietà:
1. Non richiedono la memorizzazione di tutti i punti osservati ogni punto può essere scartato una volta usato utile per grandi quantità di dati
2. Possono essere usati per l’apprendimento “on-line” in sistemi “real-time” adattivi
3. Se il sistema è stazionario, ma con variazioni lente, la stima sequenziale dei parametri può essere usata per inseguire il comportamento del sistema (“tracking on-line”)
In generale, è possibile esprimere una formulasequenziale aggiornabile ad ogni nuovo punto N+1:
Metodisequenziali
)ˆ(+ˆ=ˆ1+ NNNN g θaθθ
g è una funzione della variabile aleatoria
I coefficienti aN sono una sequenza di numeri positivi che soddisfano alle seguenti proprietà:
∞
∞
0lim
∑
∑
∞
1
2
∞
1
∞→
NN
NN
NN
a
a
a Assicura che le successive correzioni tendono a diminuire è il processo converge a un valore limitato
Assicura che le correzioni sono sufficientemente ampie da trovare effittivamente la soluzione
Assicura che il rumore accumulato si mantenga con varianza limitata, in modo da non compromettere la convergenza
Metodisequenziali
)ˆ-(1+
1+ˆ=ˆ 1)+(
1+ NN
NN Nμxμμ
N.B. È necessario tenere in memoria solo N è il valore della media stimata al passo N, cosicchè ogni punto viene usato una sola volta e poi scartato. Il contributo di ogni punto successivo decresce come conseguenza del coefficiente 1/(N+1)
Per esempio la stima sequenziale della media di una distribuzione gaussiana, si può esprimere come:
N
NNNN p
θ
xaθθˆ
1)+(1+ )/(ln
∂
∂ˆˆ
Risolvendo in modo sequenziale la stima ottenuta col metodo della massima verosimiglianza, usando la formula di Robbins-Monro, si può dimostrare che:
Metodi non parametriciStimano le d.p. la cui forma funzionale complessiva non viene definita preliminarmente. Ne esistono diversi tipi:
1. Istogrammi. Si dividono gli assi di ogni variabile in classi, approssimando la d. p. tramite la frazione di dati che cadono in ogni ‘scatola’ (bin).
2. Metodi a kernel. D. p. come somma di funzioni elementari (kernel) tutte uguali, di forma e volume prefissato, centrate su ogni dato.
3. K-nearest-neighbours. Fissate K osservazioni sul totale N (K<N) la d. p. è stimata in rapporto al volume dell’ipersfera che contiene K dati ed è centrata su ogni valore del vettore delle osservazioni.
4. Modelli misti (semi-parametrici). Si combinano un certo numero (<N) di d. p. elementari, i cui parametri (posizione e apertura) sono stimati con tecniche classiche (massima verosimiglianza), oppure più sofisticate (expected-maximization)
Istogrammi
M=100
M=5
M=20
Il numero di classi M va scelto come giusto compromesso (c) tra due opposte rappresentazioni:
a)troppo rumorosa varianza elevata;
b)poco accurata bias elevato
a)
b)
c)
IstogrammiLa probabilità che ogni vettore delle osservazioni x, estratto da una d.p. p(x) sia compreso in una regione R dello spazio x è definita come:
R
')'( xx dpP
Presi N valori estratti indipendentemente da p(x), la probabilità che K appartengano alla regione R è data dalla legge binomiale:
KNK PPKNK
NK -)-1(
)!-(!
!=)(Π
La frazione media di punti in tale regione è P=E{K/N}, mentre la varianza attorno alla media è uguale a P(1-P)/N
IstogrammiAll’aumentare di N (N) la varianza tende a 0 e quindi la frazione media P di punti in R è ≈ K/N
Se d’altro canto assumiamo che p(x) sia continua e non vari molto in R, possiamo approssimare in:
V è il volume di R e x è un punto generico entro R
VpdpP )(~')'( xxx R
Si ottiene quindi il risultato intuitivo NV
Kp =~)(x
N.B. Il risultato dipende due valide approssimazioni contrapposte: R deve essere abbastanza grande affinché si abbia un sufficiente numero di punti K, ma non troppo da poter considerate p(x) costante nel volume di interesse