02. Teoria Della Decisione

1Dipartimento di Ingegneria

Biofisica ed ElettronicaUniversità di Genova

Prof. Sebastiano B. Serpico

2. Teoria della decisione

2

Introduzione alla Teoria della Decisione

• La teoria della decisione Bayesiana affronta un problema diclassificazione su base probabilistica, assegnando cioè uncampione incognito ad una delle classi disponibili sulla basedelle caratteristiche statistiche del vettore delle feature x.

– La teoria della decisione assume nota la densità di probabilità(ddp) p(xi) del vettore delle feature x condizionateall’appartenenza a ciascuna classe i (i = 1, 2, ..., M).

– Un campione incognito x* è assegnato ad una delle classi 1, 2,..., M sfruttando l’informazione statistica contenuta nelle ddpcondizionate alle classi p(x i) (i = 1, 2, ..., M).

– Il problema della decisione è, in realtà, un problema più generalerispetto al problema della classificazione.

• Nell’ambito della teoria della decisione si inquadrano:– la decisione a minimo rischio (Bayes);

– i criteri MAP ed ML;

– il criterio minimax;

– il criterio di Neyman-Pearson.

3

Criterio di classificazione MAP

• Criterio MAP:– un campione x è assegnato alla

classe che presenta la massimaprobabilità a posteriori P(i| x):

x j P(j| x) P(i| x)

i = 1, 2, ..., M

– poichè le probabilità a posteriorisovente non sono note, applicandoil teorema di Bayes (la definizionedi probabilità condizionata), siriscrive la regola MAP nel modoseguente:

x j P(j)p(x| j) P(i)p(x| i)

i = 1, 2, ..., M

– la regola MAP è applicabilequando sono note le probabilità aposteriori P(i| x) o l’insieme delleddp condizionate p(x| i) e delleprobabilità a priori Pi = P(i).

• Ottimalità del criterio MAP– sia Ri la regione di decisione

associata alla classe i da ungenerico classificatore cheabbia disponibili le ddpcondizionate p(x| i) e leprobabilità a priori Pi (i = 1, 2,..., M);

– la probabilità di errore siesprime nel modo seguente:

– si dimostra che il classificatoreMAP minimizza la probabilitàdi errore, note le ddpcondizionate alle classi e leprobabilità a priori delle classistesse.

1

1

{err} {err| } ( )

{ | }

M

e i ii

M

i i ii

P P P P

P R P

x

4

Teoria del minimo rischio

• Il criterio MAP non tiene conto degli eventuali costi associati aidiversi errori di classificazione.

– Noi potremmo sapere a priori che decidere per l’appartenenza diun certo campione ad una certa classe implica come conseguenzadecidere che una certa azione sia eseguita. Le azioni collegate adiverse classi possono avere un costo differente.

– La teoria del minimo rischio, basata anch'essa sulla definizione esulla massimizzazione di una misura di natura probabilistica,integra questa informazione aggiuntiva e può essere consideratacome una teoria più generale che include il criterio MAP comecaso particolare.

– Lo scopo è decidere un’azione in base alla probabilità dellesingole classi. In generale, non c’è una corrispondenza direttaclasse azione, che si può avere però come caso particolare.

• Notazioni:– insieme delle classi: = {1, 2, ..., M};

– insieme delle azioni possibili che vengono prese in funzione delladecisione: A = {1, 2, ..., R};

5

Matrice dei costi

• I costi delle azioni che è possibile intraprendere dipendonodalle classi e sono definiti da una matrice dei costi :

– ha dimensione R × M:

– Esempio:

= {1 = ‚incendio‛, 2 = ‚non-incendio‛}

A = {1 = ‚chiamare i pompieri‛, 2 = ‚non chiamare i pompieri‛}

se introducessimo anche una terza azione ‚chiamare la vigilanza‛,avremmo un caso con due classi e tre azioni.

1 1 1 2 1

2 1 2 2 2

1 1

( | ) ( | ) ( | )

( | ) ( | ) ( | )

( | ) ( | ) ( | )

M

M

R R R M

0

0

è il costo di chiamare i pompieri se non c‘è incendio e di non chiamare i pompieri se c‘è incendio (es.: = 103

costo chiamata e = 106 costo edificio).

L’elemento ij = (i| j)è il costo dell’azione i

data la classe j ed è, ingenere, un numero realee positivo (qualora fossenegativo, denoterebbeun ‚guadagno‛).

6

Criterio del minimo rischio

• Rischio condizionato

– Per ogni pattern x, introduciamo il rischio condizionato R(i|x)di effettuare l’azione i dato il pattern x:

– Il rischio condizionato può essere visto come un costo medio(rispetto alla distribuzione di probabilità a posteriori delle classi)che si ha se, osservato un campione x, si decide per un’azione i.

• Criterio di decisione secondo la teoria del minimo rischio

– Dato il pattern x viene scelta l’azione j cui è associato il minimorischio condizionato:

x j R(j| x) R(i| x) i = 1, 2, ..., R

1

( | ) ( | ) ( | ) { ( | )| }M

i i j j ij

R P Ex x x

7

Caso particolare

• Siano M = R = 2, P1 = P(1) e P2 = P(2):

– è una matrice quadrata 2 × 2 e

– dato allora un campione x, si esegue l’azione 1 se e solo se:

– dato il significato dei coefficienti di costo, l’ipotesi 11 – 21 < 0 ègeneralmente verificata (quando è quadrata, si mettonosolitamente le azioni a minor costo sulla diagonale principale,interpretandole come azioni corrette).

1 1 11 2 12

2 1 21 2 22

( | ) ( | ) ( | )

( | ) ( | ) ( | )

R P P

R P P

x x x

x x x

1 11 2 12 1 21 2 22

1 11 21 2 22 12

1 1 21 11 2 2 12 22

1 2 12 2221 11

2 1 21 11

( | ) ( | ) ( | ) ( | )

( | )( ) ( | )( )

( | ) ( )( ) ( | ) ( )( )

( | ) ( )( ) (per 0)

( | ) ( )

P P P P

P P

p P p P

p P

p P

x x x x

x x

x x

xx

x

Attenzione:

Non si confonda il

rapporto di

verosimiglianza

(x) con la matrice

dei costi .

8

Confronto minimo rischio - MAP

• Caso a due classi

– Se 22 = 11 = 0 (costo nullo associato ad ‚azioni corrette‛), si ha

– MAP:

– Dal punto di vista operativo è come se, gli elementi di costomodificassero le probabilità a priori. Se 21 = 12 (nessun privilegiofra le due azioni ‚sbagliate‛) si riottiene il classificatore MAP.

• Caso multiclasse

– Se ii = 0 per i = 1, 2, ..., n, la decisione a minimo rischio è:

– Si ricade nel caso MAP se ij = 1 – ij, dove ij è il simbolo diKronecker: si parla allora di ‚matrici costo 0-1‛.

1 2 121

2 1 21

( | )( )

( | )

p P

p P

xx x

x

( | ) 1,2,...,

( | )

j ijii

j i ji

Ppj n

p P

xx

x

1 21

2 1

( | )( )

( | )

p P

p P

xx x

x

9

Classificatore ML

• Un classificatore a massima verosimiglianza (maximumlikelihood, ML) associa il campione x alla classe che presenta inx il massimo valore di ddp condizionata.

– Regola di decisione ML: x j p(x| j) p(x| i), i = 1, 2, ..., M.

– Il classificatore ML si può pensare come caso particolare diclassificatore MAP, in cui le classi sono equiprobabili. Dal puntodi vista della minimizzazione della probabilità di errore, ilcriterio ML è quindi ottimo quando le classi sono equiprobabili.

– In caso contrario, ML è una regola di decisione sub-ottima. Ètuttavia largamente usata, quando, in assenza di stime affidabilidelle probabilità a priori, si accetta l’ipotesi di equiprobabilità.

– Il classificatore ML ricade quindi nella teoria del minimo rischio,con le seguenti condizioni:

1

, 1,2,...,1

ij ij

i

i j MP

M

10

Funzione discriminante della regola a minimo rischio

• Il decisore a minimo rischio opera con i seguenti dati iningresso:

– ddp condizionate p(x| i), i = 1, 2, ..., M;

– matrice di costo ;

– probabilità a priori Pi, i = 1, 2, ..., M.

• Noti questi dati, si deduce dalla regola di decisione la funzionediscriminante a minimo rischio.

– Ad esempio, nel caso M = R = 2, se le ddp condizionate p(x| 1) ep(x| 2) sono funzioni continue, l’ipersuperficie discriminante fra1 ed 2 si ottiene imponendo l’uguaglianza seguente:

1 2 12 22

2 1 21 11

( | ) ( )

( | ) ( )

p P

p P

x

x

11

Rischio globale ed hypothesis testing

• La teoria del minimo rischio prende una decisione sulla basedel rischio condizionato associato al singolo campione x,operando cioè con una valutazione locale del rischio.

• In alternativa, il calcolo effettuato sul rischio può esseresviluppato in termini globali, analogamente a quanto si fanella teoria MAP, la quale definisce un classificatore in terminidi minima probabilità media di errore (la probabilità di erroreè infatti una quantità integrale, ‚globale‛).

• Per la formulazione globale nel caso M = R = 2 adottiamo lenotazioni dell’hypothesis testing binaria [Barkat, 1991]:

– si deve decidere tra due ipotesi H0 ed H1 (es.: assenza e presenzadi segnale radar, rispettivamente);

– la scelta è effettuata in base ad n osservazioni x1, x2, …, xn (es.: ncampioni del segnale radar) raccolte in un vettore aleatorio x cheassume valori in uno spazio Z n (spazio delle osservazioni).

12

Regioni di decisione

• Lo spazio Z è suddiviso in due regioni di decisione Z0 e Z1 taliche

– Z = Z0 Z1;

– se x Z0 si decide per H0;

– se x Z1 si decide per H1.

– Le densità di probabilità p(x| H0) e p(x| H1) si assumono note.

Spazio delle

osservazioni

Decido H0

Decido H1

f(y/H0)

f(y/H1)

SORGENTE

p(x| H0)

p(x| H1)

13

Costi e costo medio

• Si hanno quattro costi distinti associati a quattro casi possibili:–

– cij è il costo associato alla decisione Di data l’ipotesi vera Hj. Talecosto è equivalente al costo ij definito nella teoria del minimorischio. In pratica sarà sempre c01 > c11 e c10 > c00.

• Il classificatore Bayesiano minimizza il costo medio su Z,ovvero il rischio, inteso come rischio globale (su tutto Z).

– In altre parole, questo classificatore identifica Z0 e Z1 ottimi nelsenso del minimo rischio globale:

c00 Decido D0 quando H0 è vera decisione corretta

c01 Decido D0 quando H1 è veramancato allarme e

relativa probabilita' PM

c10 Decido D1 quando H0 è verafalso allarme e relativa

probabilita' PF

c11 Decido D1 quando H1 è veradecisione corretta e

relativa probabilita' PD

00 0 0 01 0 1 10 1 0 11 1 1{costo} , , , ,E c P D H c P D H c P D H c P D H

14

Calcolo del rischio

• Applico la regola di Bayes al calcolo del rischio:

– Se P0 = P(H0) e P1 = P(H1) sono le probabilità a priori delle ipotesi(corrispondenti alle probabilità a priori delle classi), si ha:

0 1

0 1

0 0 0 1 0 0

0 1 1 1 1 1

0 0 1 1 0 1

( , ) ( | ) ( )

( | ) ( | ) 1 , ( | ) ( | )

( | ) ( | ) 1 , ( | ) ( | )

{decisione corretta} , , 1

{errore}

i j i j j

F F

Z Z

M D D

Z Z

c F D

e

P D H P D H P H

P D H p H d P P D H p H d P

P D H p H d P P P D H p H d P

P P P D H P D H P P P P

P P P

x x x x

x x x x

0 1 1 0 1 0

00 0 01 1 10 0 11 1

00 0 01 1 10 0 11 1

, ,

1 1

1 (1 )

M F

F D F D

F M F M

D H P D H P P P P

c P P c P P c P P c P P

c P P c P P c P P c P P

espressione del rischio in funzione delle probabilità di falso allarme PF e di detection PD (o in funzione di PF e della probabilità PM di mancato allarme).

15

Regola di classificazione (1)

• Esprimendo opportunamente il costo medio, è possibilededurre la regola di classificazione che lo minimizza.

– Esplicitando le probabilità congiunte P(Di, Hj) (i, j = 0, 1), si ha

– Per la proprietà di normalizzazione delle pdf condizionate si ha:

0 0

1 1

00 0 0 01 1 1

10 0 0 11 1 1

( | ) ( | )

( | ) ( | )

Z Z

Z Z

c P p H d c P p H d

c P p H d c P p H d

x x x x

x x x x

1 0

0

0 10 1 11 1 01 11 1 0 10 00 0

( | ) 1 ( | ) 1 ( | ) , 0,1

[ ( ) ( | ) ( ) ( | )]

j j j

Z Z Z

Z

p H d p H d p H d j

P c P c P c c p H P c c p H d

x x x x x x

x x x

costante (indipendente da Z0) dipendente da Z0

16


• I termini integrandi dentro la parentesi quadra sono entrambipositivi per ogni x Z0. Allora il rischio è minimo quando laregione Z0 include solo quei valori di x per cui il secondotermine integrando è più grande del primo e quindi lafunzione integranda è negativa in tutta Z0.

– Di conseguenza, definisco la regione Z0 come il luogo dei punti xnello spazio delle misure tale che:

P1(c01 – c11)p(x| H1) < P0(c10 – c00)p(x| H0)

– Ne deriva la seguente regola di classificazione:1

0

1

0

1 01 11 1 0 10 00 0

1 0 10 00

0 1 01 11

( ) ( | ) ( ) ( | )

( | ) ( )( ) dove ( ) e

( | ) ( )

H

H

H

H

P c c p H P c c p H

p H P c c

p H P c c

x x

xx x

x

rapporto di verosimiglianza (likelihood ratio)

17


• La regola di decisione ottenuta ottimizzando il rischio globalerispetto alle regioni Z0 e Z1 è identica a quella ricavataoperando localmente sul rischio condizionato a ciascuncampione x.

• Quindi abbiamo verificato che la regola di decisione locale peril minimo rischio ottimizza anche il rischio globale.

18

MAP come caso particolare del minimo rischio

• Anche mediante l’approccio globale, si può verificare che ilclassificatore MAP è un caso particolare del classificatore eminimo rischio.

– Nel caso di matrice dei costi ‚0-1‛, si ha

– Pertanto il classificatore a minimo rischio basato su tale matricedei costi è:

– Inoltre, in questo caso particolare, il rischio coincide con laprobabilità di errore:

– È pertanto confermato che il classificatore MAP minimizza laprobabilità di errore anche in senso globale.

0

1

0 1

1 0

PC

P

1

0

1 0

0 1

( | )( ) MAP

( | )

H

H

p H P

p H P

xx

x

1 0 1 01 D F M F eP P P P P P P P P

19

Osservazioni sulle regioni di decisione

• Un test di verosimiglianza è definito non appena siano noti ilrapporto di verosimiglianza (x) e la soglia . Fissato il test diverosimiglianza, sono pertanto univocamente definite leregioni di decisione Z0 e Z1.

– Z0 = {x Z: (x) < } e Z1 = {x Z: (x) > } (un campione x Ztale che (x) = può essere inserito arbitrariamente in Z0 o in Z1).

– Fissate le densità di probabilità p(x| H0) e p(x| H1), le regioni Z0 eZ1 sono pertanto univocamente determinate dalla soglia :

– Pertanto, anche PF e PD (e quindi anche PM) sono univocamentedeterminate da :

0 0

1 1

( )

( )

Z Z

Z Z

1

1

0

( )

1

( )

( | ) ( )

( | ) ( )

F F

Z

D D

Z

P p H d P

P p H d P

x x

x x

20

Minimax: introduzione

• Quando le probabilità a priori non sono note, non è piùpossibile applicare la teoria del minimo rischio. Il test minimaxconsidera allora la situazione in cui si abbia il massimo valoredel minimo rischio al variare delle probabilità a priori.

– L’approccio minimax assume note le ddp condizionate e lamatrice dei costi, ma non le probabilità a priori. Consideronuovamente il caso M = 2 con le notazioni dell’hypothesis testing.

– Sostituendo P0 = 1 – P1 nelle espressioni di rischio e soglia, si ha:

– Fissata allora la matrice dei costi, il valore di è univocamentedeterminato da quello di P1: = (P1). Anche le probabilità PF =PF() e PM = PM() sono allora funzione di P1. Di conseguenza ilrischio minimo è anch’esso funzione di P1:

00 10 1 11 00 01 11 10 00

10 001

1 01 11

[ (1 ) ] [( ) ( ) ( ) ]

( )1

( )

F F M Fc P c P P c c c c P c c P

c cP

P c c

1( )P

21

Minimax: grafico del rischio minimo

• Graficando il rischio minimo in funzione di P1, si ottiene lacurva seguente:

• In particolare:

– P1 0+ + (x) < x Z Z0 = Z PF 0, PM 1R c00

– P1 = 1 = 0 (x) > x Z Z1 = Z PF =1, PM =0R = c11

0 0,2 0,4 0,6 0,8 1

P1

R

c11

c00

22

Minimax: retta dei rischi (1)

• Consideriamo il test di verosimiglianza associato ad ungenerico valore P1 = P1*.

– La soglia risulta allora fissata ad * = (P1*), le regioni didecisione a Z0(*) e Z1(*), la probabilità di falso allarme a PF* =PF(*) e quella di mancato allarme a PM* = PM(*).

– Essendo sconosciuto il vero valore di P1, il rischio può assumeretutti i valori dati da:

per 0 P1 1. Tali valori di rischio variano linearmente con P1:

0 0,2 0,4 0,6 0,8 1 P1

R

c11

c00

Rmax

P1*

* * * * *00 10 1 11 00 01 11 10 00[ (1 ) ] [( ) ( ) ( ) ]F F M Fc P c P P c c c c P c c P

Nota — La dipendenza di R da P1 è in parte

implicita (tramite PF e PD), in parte esplicita. Fissando

la regola di decisione (ovvero * ), resta solo la

dipendenza esplicita.

23

Minimax: retta dei rischi (2)

• Proprietà della retta R*:

– in P1* la retta e la curva delrischio minimo assumono lostesso valore R1*, perché il test

di verosimiglianza consideratoè ottimo quando P1 = P1*;

– la retta sta ‚sopra‛ (o coincidecon) la curva del rischiominimo perché il testconsiderato è sub-ottimo perogni P1 P1*;

– la retta è tangente e sta soprala curve per ogni P1* [0, 1],per cui significa che la curvadei rischi minimi volge laconcavità verso il basso;

– fissata la regola con P1*, alvariare del P1 vero in [0, 1], R*

varia fino ad un massimo(assunto per P1 = 0 o per P1 =1), che dipende dalla specificaretta scelta;

– al variare di P1* cambia laregola di decisione e quindianche la retta R* ed il suo

massimo

0 0,2 0,4 0,6 0,8 1

P1

R

c11

c00P1* P1**

Rmax*Rmax**

*max.

24

Minimax: criterio di decisione

• Essendo sconosciuto il valore vero di P1, il criterio minimaxsceglie la retta cui corrisponde il minimo rischio massimo edadotta i valori P1* ed * corrispondenti.

– Tale retta è orizzontale e tangente alla curva dei rischi minimi nelsuo punto massimo.

– Impongo pertanto pendenza nulla perR*:

– Tale relazione, detta equazione del minimax, identificaimplicitamente *, e quindi anche P1*.

0 0,2 0,4 0,6 0,8 1

P1

R

c11

c00

Rmax

P1*

* *11 00 01 11 10 00( ) ( ) ( ) 0M Fc c c c P c c P

25

Minimax: casi limite

• L’equazione del minimax fornisce una soluzione * quando lacurva dei rischi minimi ammette massimo internoall’intervallo [0, 1]. In caso contrario si possono presentare duecasi limite:

0 0,2 0,4 0,6 0,8 1

P1

R

c11

c00

P1*

0 0,2 0,4 0,6 0,8 1

P1

R

c11

c00 P1*

se c00 > c11, il criterio minimax assume P1* 0, * + .

se c00 < c11, il criterio minimax assume P1* = 1, * = 0.

26

Minimax: osservazioni

• Casi particolari:

– se c00 = c11 = 0, allora l’equazione del minimax si riduce a:

– se poi anche c01 = c10 (‚matrice costo 0-1‛) si ha:

• Minimax e probabilità di errore

– Nel caso di ‚matrici costo 0-1‛ si ha:

– Allora, la soglia di decisione e le conseguenti regioni di decisionesono scelte in modo tale che gli errori di decisione siano ugualiper entrambe le classi ed il criterio equivale a minimizzare laprobabilità media di errore.

* *01 10M Fc P c P

* *M FP P

* * *M FP P

27

Metodo di Neyman-Pearson: introduzione

• Quando non sono noti nè le probabilità a priori nè i costi daattribuire alle componenti della matrice di rischio, si puòutilizzare l’approccio di Neyman-Pearson.

– Si suppone in tale ambito di conoscere la PF desiderata o, quantomeno, di pretendere che PF non superi un dato valore : PF = .

– Il criterio di Neyman-Pearson massimizza PD (o minimizza PM)sotto il vincolo PF = .

– A tal fine introduce un moltiplicatore di Lagrange 0,minimizzando il seguente funzionale:

0 1

0 0

0

1 0

1 0

1 0

( ) ( | ) ( | )

( | ) 1 ( | )

(1 ) [ ( | ) ( | )]

M F

Z Z

Z Z

Z

P P p H d p H d

p H d p H d

p H p H d

x x

x x

x x

x x

x x

x

28

Metodo di Neyman-Pearson: criterio di decisione

• Il nostro obiettivo è allora trovare il dominio Z0 che risolve ilproblema di minimo vincolato.

– Trascurando il termini additivo costante nel funzionale, ilproblema di minimizzazione è pertanto:

– Come nella teoria del minimo rischio, osservo che entrambi itermini integrandi in parentesi quadra sono positivi: si ha quindiminimo quando la funzione integranda è negativa per ogni x Z0. Pertanto Z0 = {x Z: p(x| H1) < p(x| H0)} = {x Z: (x) < } .

– Ne consegue il seguente criterio di decisione:

00

1

1 0

0

min [ ( | ) ( | )]

( | ) (vincolo)

Z ZZ

F

Z

p H p H d

P p H d

x x

x

x

x

1

0

1

0

( | )( )

( | )

H

H

p H

p H

xx

x

29

Metodo di Neyman-Pearson: calcolo della soglia

• Il metodo di Neyman-Pearson genera nuovamente un test diverosimiglianza. La soglia del test coincide col moltiplicatore

e si calcola imponendo la condizione di vincolo.

– Poiché PF = PF(), l’equazione PF = identifica implicitamente ivalori ammissibili di .

– Più esplicitamente, introducendo la variabile aleatoria = (x)(funzione di x), si ha:

dove

*0 0{ | } ( | )FP P H p H d

x

*

0( | )p H d

Nota — Non è detto che, variando , PF vari con continuità (se le ddp fossero impulsive, ciò non avverrebbe): pertanto, in generale, si può

formulare il test di Neyman-Pearson con la condizione PF .

30

Receiving Operator Characteristic (ROC)

• La curva caratteristica del ricevitore (ROC) rappresental’andamento della probabilità di detection PD in funzione dellaprobabilità di falso allarme PF al variare della soglia didecisione .

– Una curva ROC dipende solo dalle ddp condizionate p(x| H0) ep(x| H1) poiché, note tali ddp e fissato un valore di soglia , ènoto il valore delle probabilità PD() e PF().

– Una curva ROC non dipende da costi né da probabilità a priori.

– Indipendentemente dalle ddp condizionate, una curva ROC giacesempre nel quadrante [0, 1] × [0, 1] (perché PD e PF sonoprobabilità) e passa sempre per i punti (0, 0) ed (1, 1). Infatti:

+ PD 0, PF 0 (caso limite Z0 = Z);

0 PD 1, PF 1 (caso limite Z1 = Z).

– Andamenti irregolari della curva non sono possibili, in quanto PD

e PF variano con continuità (Hp.: ddp non impulsive) e non cipossono essere due punti con la stessa pendenza.

31

Curve ROC: esempio

• Caso gaussiano monodimensionale:

– n = 1, p(x| H0) = N(0, 2), p(x| H1) = N(m, 2);

– le curve ROC in tal caso sono parametrizzabili in funzione di h =m/ = 0.5, 1, 2…:

PD

1

h=0.5h=1

h=2

0

p(x| H0) p(x| H1)PD

PF

D0 D1

0

32

Curve ROC: proprietà

• La pendenza della tangente alla curva ROC coincide con ilvalore di soglia cui corrispondono le probabilità PF e PD.

– Dimostrazione:

In generale risulta:

0 0

1 1

( | ) ( | )

( | ) ( | )

F

D

dPF d

dPD d

P p H d p H

P p H d p H

1

0

( | )

( | )

p H

p H1

0

( | )/

/ ( | )D D

F F

p HdP dP d

dP dP d p H

1 01

0 00

( | ) ( ) ( | )( | )

( ) ( )

( | ) ( | )( | )

( ) ( )

x i i x i

i ii i

x i x i

i ii i

p x H x p x Hp H

x x

p x H p x Hp H

x x

Verifico tale relazione nel caso n = 1 (per la dimostrazione nel caso generale, v. Van Trees). Siano x1, x2, ... le soluzione dell’equazione (x) = :

33

Curve ROC: osservazioni

• Conseguenze della proprietà della pendenza delle curve ROC:

– nella teoria di Neyman-Pearson, fissata PF, trovo PD comeordinata del punto di curva ROC avente ascissa PF e trovo comependenza della curva in quel punto;

– nella teoria del minimo rischio, nota , trovo PF e PD comecoordinate del punto di curva ROC in cui la pendenza è ;

– nella teoria del minimax, trovo PF e PD come coordinate delpunto di intersezione fra la curva ROC e la retta descrittadall’equazione del minimax e trovo come pendenza in quelpunto.

• Tracciamento di curve ROC:

– approccio 1 — calcolo analitico delle funzioni PF() e PD() (quasimai possibile);

– approccio 2 — rilevazione empirica della curva ROC, mediantemisura sperimentale delle probabilità PF e PD, relative a valoridistinti di soglia di decisione.

34

Osservazione sui test di verosimiglianza

• Un test di verosimiglianza riporta il problema della decisionein uno spazio delle feature n-dimensionale ad un testmonodimensionale sulla singola grandezza scalare (x),indipendentemente da n e senza bisogno di conoscereesplicitamente le regioni di decisione.

– Le regioni di decisione possono essere anche sottoinsiemi moltocomplessi dello spazio delle feature (anche non connessi), ma unloro calcolo esplicito non è essenziale alla classificazione di undato campione x.

– Per classificare x è sufficiente calcolare (x) e confrontarne ilvalore con la soglia impiegata.

35

Esempio 1

• Esempio 1

– caso monodimensionale (n = 1);

– due classi gaussiane: p(x| H0) = (0, 2), p(x| H1) = (m, 2);

p(x| H0) p(x| H1)PD

PF

0

PM

m

36

Esempio 1: test di verosimiglianza

1

0

1 1

0 0

2

0 2

2

1 2

21 0 10 00

20 1 01 11

2 2

2

1( | ) exp

22

1( | ) exp

22

( | ) ( )2( ) exp

( | ) ( )2

2ln ( ) ln ln

22

H

H

H H

H H

xp x H

x mp x H

p x H P c cm mxx

p x H P c c

m mx mx x

m

il test di verosiglianza si traduce in un test a soglia sulla feature x,

con soglia di decisione .

37

Esempio 1: PF e PD

2

1 0 0 2

2

1 1 1 2

1 0

1( | ) { | } exp

22

1 ( )( | ) { | } exp

22

1 1

in caso di classi equiprobabili

F

D

M D

e M F

xP P D H P x H dx Q

x m mP P D H P x H dx Q

m mP P Q Q

P P P P P

2

: 2

1dove exp

22

F Me

x

P PP

yQ x dy

integrale della ‚coda di gaussiana‛

38

Esempio 1: minimax

* *

0 1ipotesi:

1 0

* **

2F M

C

m mP Q Q P

equazione del minimax corrispondente alla matrice dei costi data.

1 0 0 1( )

2e M F F F

mP P P P P P P P P Q

Questo passaggio deriva

dal fatto che, per ‚matrici di costo 0-1‛ , le probabilità PF

e PM coincidono

39

Esempio 2

• Esempio 2:

– caso monodimensionale (n = 1):

– ddp non gaussiane:

0 1

1

1exp( )( | )

22(1 ) | | 1

1( | )

2 2

xxp x H

ex

xp x H

PM

p(x/H )0

0,46-0,46

p(x/H )11/2

-1 1

PF

x

Z1

Z1

Z0

1

2(1-e )-1

40

Esempio 2: minimo rischio

1

0

0 1

0

1

0

1

0,46 1

1 0 11 0,46

0 1

1 0ipotesi:

scelgo per 0.461 ( ) 1

scelgo per 0.46 1

[ 0.46,0.46]

[ 1, 0,46] [0,46,1]

1exp exp( ) 0.42( | )

2 1

(

H

H

F

M

C

P P

H xx

H x

Z

Z

P xdx x dxP D He

P P

1 1

1 0

1| ) 2 0.46 0.46

2

0.442

M Fe M F

D H

P PP P P P P

41

Esempio 2: Neyman-Pearson

1

0

1

0

11

0

1

ipotesi: 0.5

( | ) 1( ) 2(1 )exp

( | ) 2

1ln

F

H

H

H

H

P

p x Hx e x

p x H

ex

1

1 0 11

1( | ) exp exp( ) 0.5

2 1

0.38

FP P D H xdx x dxe

soglia di decisione sulla feature x, associata ad un test di

verosimiglianza con soglia .

Secondo il criterio di Neyman-Pearson, determino la soglia imponendo il valore voluto di probabilità di falso allarme. La risultante probabilità di

detection è PD = 2(1 – 0.38)/2 = 0.62.-1 1

PD

y

* *

42

Esempio 3

• Esempio 3:

– caso monodimensionale (n = 1);

– ddp esponenziali:

0

1

exp 0( | )

0 altrove

exp 0( | ) ( 1)

0 altrove

x xp x H

x xp x H

-5 0 5 10 15 20 25

x

p(x| H1)

p(x| H0)

1

43

Esempio 3: curve ROC

• Calcolo delle curve ROC:

– determino le regioni di decisione associate ad un test diverosomiglianza al variare della soglia e le corrispondenti PF()e PD():

1

0

0

1

1

0

0

0

1: ln

( ) exp[ ( 1) ] 1: 0

{0 | } exp( ) 1 exp( )

{0 | } exp( ) 1 exp( )

H

H

D

F

H xx x

H x

P P x H x dx

P P x H x dx

1 (1 )D FP P

forma parametrica della curva ROC

in questo caso si può ottenere la

curva ROC in forma esplicita

0

0,5

1

0 0,5 1

PF

PD

= 1

= 2 = 4 = 8

= 16

44

Esempio 3: osservazioni

• Note sulle curve ROC:

– verifica della proprietà della pendenza della curva ROC:

exp( )/exp[ ( 1) ]

/ exp( )D D

F F

dP dP d

dP dP d

45

Densità di probabilità gaussiane

• Premessa

– Un modello molto sovente usato per le ddp condizionate alleclassi è la gaussiana.

– In generale, una giustificazione della grande diffusione deimodelli gaussiani è rappresentata dal teorema del limite centrale,secondo cui la somma di N variabili aleatorie indipendenticonverge in distribuzione ad una gaussiana per N + .

– Pertanto tutti i fenomeni stocastici dovuti ad un grande numerodi cause indipendenti fra loro sono descritti con ottimaapprossimazione da modelli gaussiani.

• Gaussiana multidimensionale

– Un vettore aleatorio continuo n-dimensionale x si dice gaussianoquando presenta la seguente ddp:

1/ 2 1 / 2

1 1exp ( ) ( )

22

tn

p

x x m x m

(m, )

46

Caratteristiche della gaussiana multidimensionale

• Significato dei parametri

– Come una gaussiana monodimensionale è univocamentedeterminata dai parametri media e varianza, una gaussianamultidimensionale è identificata dal vettore m e dalla matrice .

– m è la media del vettore aleatorio x:m = E{x};

– è la matrice di covarianza di x: = Cov{x} = E{(x –m)(x –m)t}.

• Stima dei parametri

– Adottando un modello gaussiano per un certo insieme di dati,molto sovente i parametri della ddp gaussiana non sono noti apriori, ma vanno stimati a partire dai dati disponibili, costituiti, ingenerale, da N osservazioni x1, x2, …, xN del vettore aleatorio x.

– Stime non polarizzate di m e sono date da:

1 1

1 1ˆˆ ˆ ˆ, ( )( )1

N Nt

k k kk kN N

m x x m x m

47

Osservazioni sulla matrice di covarianza

• Proprietà di :

– è una matrice simmetrica: = t;

– è una matrice semidefinita positiva. Tuttavia, affinchèl’espressione della ddp gaussiana sia ben definita, deve esseredefinita positiva (infatti l’espressione di p(x) coinvolge l’inversadi e la divisione per il determinante ||).

• Variabili aleatorie indipendenti:

– sia

– se ij = 0, allora le v.a. xi ed xj sono scorrelate ed, essendogaussiane, sono anche indipendenti;

– se ij = 0 per ogni i j (ossia se è diagonale), si ha:

p(x) = p(x1) p(x2) ...p(xn)

11 12 1

21 22 2

1 2

n

n

n n nn

48

Visualizzazione di ddp gaussiane: caso 2D

• Visualizzazione:

– p(x) può essere raffigurata come una ‚campana‛ di volumeunitario.

• Curve di livello:

– le sezioni della campana a quota costante z (curve di livello) sonoellissi. Gli autovettori di sono le direzioni degli assi delle ellissi.

– L’autovettore in corrispondenza dell’autovalore maggiore sidispone lungo l’asse maggiore dell’ellisse.

z=P(x)

x1

x2x1

x2 z=3

z=2

z=0.5 z=0.01

y

x1

2

e2

e1

49

Visualizzazione di ddp gaussiane: caso nD

• Sulla ‚geometria‛ di una gaussiana n-dimensionale si possonoestendere le osservazioni fatte per le gaussiane bidimensionali.In particolare:

– siano 1, 2, …, n gli autovalori di ed e1, e2, …, en icorrispondenti autovettori;

– essendo simmetrica e definita positiva, gli autovalori sono tuttireali e positivi e gli autovettori si possono assumere ortonormali(più formalmente, esiste una base ortonormale di autovettori di);

– ordino convenzionalmente autovalori ed autovettori in modo taleche 1 2 … n;

– le curve di livello di p(x) sono iperellissi in n, i cui assi sono

disposti lungo gli autovettori di ;

– l’asse disposto lungo ek è proporzionale a

– pertanto il primo autovettore indica la direzione dell’assemaggiore e l’ultimo autovettore la direzione dell’asse più corto.

;k

50

Trasformazioni di Karhunen-Loeve

• Obiettivo della trasformazione di Karhunen-Loeve (KL) ègenerare n feature scorrelate y1, y2, …, yn a partire da n featuregeneriche x1, x2, …, xn. Nel caso gaussiano, le n featurerisultanti saranno anche indipendenti.

– Giustapponendo per righe gli autovettori, costruisco la seguentetrasformazione lineare:

– La matrice di covarianza nello spazio trasformato è diagonale:

1

2 ,

t

t

tn

T T

e

ey x

e

1

2

0 0

0 0Cov{ }

0 0 n

y

51

Uso di KL per la riduzione di parametri

• Giustapponendo solo k < n autovettori in T si costruisce unatrasformazione dallo spazio delle feature originale ad unospazio trasformato di dimensione minore.

– In tal caso T è una matrice rettangolare.

– Vantaggio di tale trasformazione è la possibilità di elaborarevettori di feature a dimensionalità ridotta nelle successive fasi (es.:per diminuire il costo computazionale del sistema diclassificazione).

– Se infatti si assume che il potere discriminante di una feature sialegato alla sua varianza e se gli ultimi autovalori sono moltopiccoli, le feature trasformate corrispondenti si possonoconsiderare poco significative a fini di classificazione.

• Più avanti considereremo in generale il problema dellariduzione del numero di feature impiegate nella classificazioneed applicheremo anche la trasformazione KL.

52

Whitening

• La trasformazione KL genera, mediante diagonalizzazione di, n feature scorrelate y1, y2, …, yn, le cui varianze coincidonocon gli autovalori di : var{yi} = i, i = 1, 2, …, n.

• L’operazione di whitening genera altre n feature z1, z2, …, zn,che, oltre ad essere scorrelate, hanno uguale varianza.

– È necessario, a tal fine, normalizzare le feature sulla base dellavarianza. Ad esempio, posso normalizzare ad 1 tutte le varianze,definendo:

– Da un vettore gaussiano n-dimensionale è quindi possibilepassare ad n variabili gaussiane monodimensionali, indipendentitra loro e di uguale ‚dispersione‛.

var{ } 1, 1,2,...,ii i

i

yz z i n

e1

e2

Gli iperellissi sono allora

di forma circolare.

53

Gaussianità condizionata alle classi

• Finora abbiamo considerato un generico vettore x di featuregaussiano. Considero adesso un contesto multiclasse, in cui unvettore x di feature è gaussiano quando condizionato aciascuna classe i, i = 1, 2, …, M:

– p(x| i) = (mi, i), i = 1, 2, …, M;

– più esplicitamente:

– mi è la media di x condizionata ad i: mi = E{x| i};

– i è la matrice di covarianza condizionata ad i:

i = Cov{x| i} = E{(x –mi)(x –mi)t| i}

– per il teorema della probabilità totale, la ddp di x è combinazionelineare di ddp gaussiane (gaussian mixture):

11 / 2/ 2

1 1| exp ( ) ( )

22

ti i i in

i

p

x x m x m

1

( ) ( | )M

i ii

p P p

x x

54

Estensione al caso multiclasse

• Le trasformazioni KL e whitening sono associate alla singolamatrice di covarianza i e quindi a classi diversecorrispondono matrici di trasformazione diverse: se Ti è lamatrice associata a i, in generale risulta Ti Tj per i j.

– L’estensione più semplice sarebbe una somma pesata delle Ti, i =1, 2, …, M. Tuttavia, questa soluzione rischia di non esserevantaggiosa per nessuna delle classi in esame.

– Esempio — I due sistemi {e1, e2} sono ‚molto‛ diversi.

x

x1

2

1

2

e1

e1

e2

e2

55

Diagonalizzazione simultanea

• Quando M = 2 è possibile un’estensione di KL e whitening chepermette di generare feature scorrelate sia quando condizionatead 1 sia quando condizionate ad 2. Date n feature x1, x2, …,xn, la diagonalizzazione simultanea esegue le due seguentioperazioni:

– fase 1 – diagonalizzazione e whitening di 1: vengono generate nfeature z1, z2, …, zn, che, condizionate ad 1, hanno matrice dicovarianza simmetrica con tutti gli elementi diagonali uguali; sia2z = Cov{z| 2};

– fase 2 — diagonalizzazione di 2z: vengono generate n feature v1,v2, …, vn che, condizionate ad 2, sono scorrelate per definizionedi diagonalizzazione;

– essendo Cov{z| 1} la matrice identità con tutti gli elementidiagonali uguali, si può verificare che Cov{v| 1} = Cov{z| 1};

– pertanto il vettore v ha matrici di covarianza diagonali siaquando condizionato ad 1 sia quando condizionato ad 2.

56

Test di verosimiglianza con classi gaussiane

• Siano date due classi 1 ed 2 con p(x| i) = (mi, i) (i = 1, 2).

– Test di verosimiglianza con soglia :

– Applicando logaritmi ln(·) ad entrambi i membri, si ha:

– L’ipersuperficie discriminante associata ad un test diverosimiglianza con classi gaussiane è pertanto una iperquadrica:

1

2

11 1 11/ 2/ 2

11

122 2 21/ 2/ 2

2

1 1exp ( ) ( )

22( | )( )

1 1( | )exp ( ) ( )

22

t

n

t

n

p

p

x m x mx

xx

x m x m

1

2

12 2 2

11 1 1 1 2

1ln ( ) ( ) ( )

21 1 1

( ) ( ) ln ln ln2 2 2

t

t

x x m x m

x m x m

1 112 2 1 1 2( ) ( ) 0t tf x C x x x C

C1 e C2 sono costanti.

57

Ipersuperfici discriminanti lineari

• L’ipersuperficie discriminante associata ad un test diverosimiglianza è una iperquadrica con termine quadraticoxt(2

–1 – 1–1)x: pertanto, quando 1 = 2 = , l’ipersuperficie

discriminante diventa lineare.

x

x1

2

1

e1 e

1e2

e2

f (x)i

2

58

Osservazioni sull’iperpiano discriminante

• L’iperpiano discriminante f12(x) = 0 non è necessariamenteperpendicolare alla congiungente (m1 – m2) delle medie delledue classi. Diventa tale quando = 2I, ossia quando èdiagonale e tutte le feature hanno stessa varianza 2.

– La verifica si ottiene per sostituzione diretta nell’espressionedella funzione discriminante.

• La posizione dell’iperpiano discriminante dipende dallacostante additiva C2, che, a sua volta, dipende dalla soglia .

– Ad esempio, in un classificatore MAP o a minimo rischioaumentare P1 (e quindi diminuire P2) sposta l’iperpiano piùlontano da m1 (e più vicino ad m2), per cui ‚la classe piu'probabile invade la classe meno probabile‛.

– Col criterio del minimo rischio, rispetto al caso MAP, l’effettodella matrice di costo è equivalente ad una modifica delleprobabilità a priori, cioè trasla l’iperpiano parallelamente a sestesso in direzione dipendente dai valori della matrice stessa.

59

Esempi di regioni di decisione

1

R1

R2

R2

Coppie di rette

R

R1

R2

Cerchi

R1

R2

Ellissi

R1

R2

Parabole

R1

R2

R2

Iperboli

Legenda: le zone tratteggiate

corrispondono alla regione di

decisione R2; in ciascuna

regione di decisione (R1 ed R2) è

riportata una curva di livello

della ddp corrispondente.

60

MAP con classi gaussiane

• Verifico quanto detto nel caso particolare di un classificatoreMAP con due classi gaussiane.

– In questo caso:

– Ciò permette di introdurre una funzione discriminante ad unindice per il classificatore MAP con classi gaussiane:

– La medesima funzione discriminante si ottiene anche in un casoMAP multiclasse.

– In generale, per un classificatore MAP con ddp condizionategeneriche si può definire: gi(x) = ln p(x| i) + ln Pi o anche gi(x) =Pi p(x| i).

1

2

1

2

121 1 1 1 1

1

12 2 2 2 2

1 1( ) ( ) ln ln

2 2

1 1( ) ( ) ln ln

2 2

t

t

PP

P

P

x m x m

x m x m

11 1( ) ( ) ( ) ln ln

2 2t

i i i i i ig P x x m x m

61

Osservazioni sulla funzione discriminante MAP

• Distanza di Mahalanobis

– A meno di costanti additive la funzione discriminante gi associataalla classe i è espressa dalla distanza di Mahalanobis fra ilgenerico campione x e la mediami della classe i:

• Forma esplicita della funzione discriminante

– Svolgendo i calcoli, la funzione discriminante ad un indice per unclassificatore MAP con classi gaussiante si può scrivere:

1 21 1( , ) ( ) ( ) ( ) ( , ) ln ln

2 2t

i i i i i i i i i id g d P x m x m x m x x m

1

10

10

1

2

( ) con

1 1ln ln

2 2

i i

t ti i i i i i i

ti i i i i i

A

g A w

w P

x x x w x w m

m m

62

MAP con ipersuperfici discriminanti lineari

• Sia 1 = 2 = :

– ciò permette di cancellare il termine quadratico xtx/2 ed iltermine noto ln||/2 dalla funzione discriminante ad un indice(essendo tali termini comuni a tutte le funzioni discriminanti equindi irrilevanti nel confronto fra di esse):

– se, in particolare, = 2I,

1

0 10

( ) con 1ln

2

i it

i i i ti i i i

g ww P

w mx w x

m m

2

0 2

0 2

( ) con

ln2

ii

ti i i

ii i

g w

w P

mw

x w xm

63

Esempio

• Siano date due classi 1 ed 2 sotto le seguenti ipotesi:– p(x| i) = (mi, i) (i = 1, 2).

– Applicando la teoria, si ottengono le seguenti funzionidiscriminanti ad un indice:

– Il piano di separazione si ricava per differenza:

1 2

1

2

1 2

(8, 4, 4)

( 96,80,80)

8 4 4

4 8 4

4 4 8

P P

m

m

12 1 2 1 2 3( ) ( ) ( ) 8 8 8 4 0f g g x x x x x x

31 1 10 1 2

112 1 2 3 2

( ) 4

( ) 4 8 8

tg w x

g x x x

x w x

x

64

Probabilità di errore

• Caso a due classi

– Detta Ri la regione di decisione associata alla classe i (i = 1, 2) siha:

– Il calcolo della probabilità di errore si riconduce quindi al calcolodi due integrali multipli (in n) estesi alle regioni di decisione, il

che è un problema analiticamente complesso.

• Caso multiclasse

– Con notazioni analoghe, si ha la seguente espressione delleprobabilità di decisione corretta e di errore per un classificatoread M classi:

2 1

1 1 2 2

1 2 1 2 1 2

1 1 2 2

{err| } {err| }

{ | } { | }

( | ) ( | )

e

R R

P P P P P

P P R P P R

P p d P p d

x x

x x x x

1 1

{ | } ( | ) , 1i

M M

c i i i i i e ci i R

P P P R P p d P P

x x x

65

Probabilità di errore: caso gaussiano (1)

• Nel caso di due classi gaussiane generiche, il calcolo analiticodella probabilità di errore non è fattibile. Si può eseguire indue casi particolari:

– 1 = 2 (iperpiano discriminante lineare);

– n = 1 (caso monodimensionale: una sola feature).

• Probabilità di errore con 1 = 2 =

– Per semplificare il calcolo di Pe è vantaggioso esprimere il criteriodi decisione come segue:

– Introdotta allora la v.a. u = u12(x), si ha:

– Pertanto u è funzione lineare di x e, condizionata ad 1 e ad 2,ha ddp gaussiana.

1

2

112

2

( | )( ) ln ln

( | )

pu

p

xx

x

1 1 2 2

1 11 2 1 2 1 2

{ | } { | }

1( ) ( ) ( )

2

e

t t

P P u P P u P

u

x m m m m m m

66


• Il criterio di decisione si può quindi esprimere in funzionedella v.a. u la cui ddp è nuovamente una gaussian mixture, i cuiparametri sono legati alla distanza di Mahalanobis fra le classi.

– Le ddp condizionate di u sono:

– Ciò permette il calcolo di Pe:

11

1 2 1 2

2

( | ) ,2

dove ( ) ( )

( | ) ,2

t

rp u r

rr

p u r

m m m m

r è il quadrato della distanza di

Mahalanobis fra le due classi.

2 2

1 2

2 1

1 ( / 2) 1 ( / 2)exp exp

2 22 2

/ 2 / 2

e

u r u rP P du P du

r rr r

r rP Q P Q

r r

67


• Nel caso 1 = 2 = è quindi possibile il calcolo dellaprobabilità di errore di un classificatore basato su test diverosimiglianza con classi gaussiane, noti i parametri = ln

ed r.

– Noti questi parametri, si può eseguire una verifica preliminarecirca la ‚bontà‛ del classificatore: se trovo una Pe non accettabile,non calcolo neppure la funzione discriminante, ma cambio ilmetodo di approccio al problema (es.: nuove feature).

– Per un classificatore ML (P1 = P2, = 1, = 0), l’espressione di Pe

si semplifica in:

2e

rP Q

Pe è funzione strettamente

decrescente di r e, per r = 0,

risulta Pe = 0.5 (non Pe = 1).0

0,5

0 5 10 15 20 25 30

r

Pe

12%

5%

68


• Quando lo spazio delle feature è monodimensionale (n = 1), untest di verosimiglianza su due classi gaussiane genera regionidi decisione che sono unione finita di intervalli.

– Se p(x| 1) = (m1, 12) e p(x| 2) = (m2, 2

2), si ha:

– Le regioni di decisione sono quindi descritte da disequazioni disecondo grado, e sono pertanto singoli intervalli o unioni di 2intervalli disgiunti.

• Pe è allora calcolabile analiticamente, integrando le ddpgaussiane monodimensionali p(x| 1) e p(x| 2) su taliintervalli (ed esprimendo il risultato in funzione di Q(·)).

1

2

1

2

21

2111

22 2

222

2 22 1 2

2 212 1

( )1exp

22( | )( )

( | ) ( )1exp

22

( ) ( )ln ln

2 2

x m

p xx

p x x m

x m x m

69

Maggiorazione della probabilità di errore

• Poichè calcolare analiticamente Pe è un problema soventeirresolubile, è utile poterla almeno maggiorare.

– In presenza di due classi 1 ed 2, si può dimostrare la validitàdella seguente maggiorazione:

– (s) è la distanza di Chernoff fra le due classi e rappresenta unamisura di separazione fra le classi stesse. In particolare, valori altidi distanza di Chernoff implicano valori bassi dell’upper bound u

sulla probabilità di errore.

– Se p(x| i) = (mi, i) (i = 1, 2), si prova che:

11 2

11 2

exp[ ( )] [0,1]

dove ( ) ln ( | ) ( | )n

s se u

s s

P P P s s

s p p d

x x x

1 212 1 1 2 2 1 1

1 2

(1 )(1 ) 1( ) ( ) [ (1 ) ] ( ) ln

2 2t

s s

s ss ss s s

m m m m

70

Chernoff bound & Bhattacharyya bound

• L’upper bound su Pe ha tipicamente il seguente andamento infunzione di s:

• Osservazioni:

– per s 0 e s 1 la maggiorazione è poco precisa;

– la maggiorazione più stretta si ottiene per s = s* (in questoesempio s*=0,7) e si dice Chernoff bound. Il calcolo di s* ècomplesso;

– sovente si adotta pertanto s = 1/2 (Bhattacharyya bound), chefornisce una maggiorazione meno precisa, ma molto più semplicesul piano computazionale.

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 1,1

s

u

s*Chernoff bound

Bhattacharyya bound

P1

P2

71

Osservazioni sul Bhattacharyya bound

• Distanza di Bhattacharyya

– L’espressione esplicita del Bhattacharyya bound è:

– B = (1/2) prende il nome di distanza di Bhattacharyya fra le dueclassi e, nel caso gaussiano, ha la forma seguente:

• Estensione al caso multiclasse

– Anche in presenza di M classi, si può scrivere un Bhattacharyyabound, che si esprime in funzione delle distanze di Bhattacharyyafra singole coppie di classi:

1 2

1 2

exp( )

1dove ln ( | ) ( | )

2 n

e uP P P B

B p p dx x x

1 21

1 22 1 2 1

1 2

1 1 1 2( ) ( ) ln

2 8 2 2tB

m m m m

1

1 1

exp( ) dove ln ( | ) ( | )n

M M

e i j ij ij i ji j i

P P P B B p p dx x x

72

Bibliografia

• K. Fukunaga, Introduction to statistical pattern recognition, 2ndedition, Academic Press, New York, 1990.

• R. O. Duda, P. E. Hart, D. G. Stork, Pattern Classification, 2ndEdition. New York: Wiley, 2001.

• H. L. Van Trees, Detection, estimation and modulation theory, vol.I, John Wiley & Sons, New York, 1968.

• M. Barkat, Signal detection and estimation, Artech House, 1991.

02. Teoria Della Decisione

Documents

Transcript of 02. Teoria Della Decisione