27
DEA Perception et Traitement de l’Information Reconnaissance des formes Règle de Bayes S. Canu http://psichaud.insa-rouen.fr/~scanu/RdF

DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Embed Size (px)

Citation preview

Page 1: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

DEA Perception et Traitement de l’Information

Reconnaissance des formes

Règle de Bayes

S. Canu

http://psichaud.insa-rouen.fr/~scanu/RdF

Page 2: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Buts de la RdFD : Algorithme

de Reconnaissance

des Formes

Une forme x(vecteur forme

des caractéristiques)

C’est la forme

« y=D(x) »

classe" vraiela" ,

)( ,...,,...,1 : RdF

décisions des ensemble ,...,2,1tiquescaractéris des espace

D(x)Rx

xDxLlRD

LyRx

d

d

d

Nous voulons un algorithme de RdF performant

K

kkXk

D

sSPdxkxfxDsCXDSCEDJ

DJD

1 ,)(,)(,)(

)(min décision de règle uned'Cout D

Page 3: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

K

kkXk

D

sSPdxkxfxDsCXDSCEDJ

DJD

1 ,)(,)(,)(

)(min décision de règle uned'Cout D

Théorème de Bayes (et non la règle)

)(

),( : ème théor

),(,

)(,

, jointe loi

),()( ns"observatio" des loi

à (analogue ),( ncevraisembla

posteriori à loi

priori à loi

xf

sSPkxfxsSP

sSPkxfxsSP

xfxsSPxsSP

xsSP

sSPkxfxf

sSxPkxf

xsSP

sSP

X

kXk

kXk

Xkk

k

kk

XX

kX

k

k

Ex : en français P(e) = 0,12

On choisi la source, et on émet

On choisi une observation, et on décide

Ex : après avoir observé x quelle est P(e|x) ?

Attention à la confusion source - action

Page 4: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

10 20 30 40 50 60 70 80 90 100

10

20

30

40

50

60

70

80

90

100

illustration

source 1

source 2

sans autre informationon décide toujours qu’un pixel vient de la zone (source 1)

car P(S1) > P(S2)

A PRIORI

que se passe t’il si l’on connaît un caratéristique : xl’intensité

Page 5: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

-50 0 50 1000

500

1000

1500

2000

10 20 30 40 50 60 70 80 90 100

10

20

30

40

50

60

70

80

90

100

illustration

source 1

source 2

Caractéristique : xl’intensité

on décidel’action qui « coûte »

le moins cher

en cout 0-1c’est la classe maxA POSTERIORI

x

f(x|s1)

f(x|s2)

Les vraisemblances

111 , SPSxfxaP

Page 6: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

-8 -6 -4 -2 0 2 4 6 8 10 120

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

illustration

f(x|s1)

f(x|s2)

111 , SPSxfxaP

222 , SPSxfxaP

Règle de décision

Page 7: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

notations

xaP

sPkxfxf

sxPkxf

xaP

sP

l

kk

XX

kX

l

k

, jointe loi

),()( ns"observatio" des loi

à (analogue ),( ncevraisembla

posteriori à loi

priori à loi

espace des sources Kk sss ,...,,...,1S

)( ,...,,...,1 : RdF

autres)(classes actions des ensemble ,...,2,1tiquescaractéris des espace

xDyxLlRD

LR

d

d

A

lklk asCasRC

,, :Cout

AS J coût d ’une règle de décision

(erreur de prédiction)

Page 8: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Cas particulier des 2 classes et coûts 0-1

0et 1et erreur

action l' décideon lesquelspour soit

0

0

SCXPSCXPP

axC

O

O

xPxPxSP

pxfpxf

SPxfSPxfxf

SxPxfxf

xrxSPxSPxSPxSE

xSPxrxSPxSP

xSPxSPxsPxsP

SPpSPsPsP

ssS

XX

XXX

XX

,1 deet ,0 de composée , jointes lois

)1,(1)0,(

1)1,(0)0,()( ns"observatio" des lois

à (analogue )1,( ),0,( ncesvraisembla

)(11*10*0 : cas ce dans

1)( 110

1,0ou , posteriori à lois

1,0ou , i)(Bernouill priori à lois

1et 0 valeurs2 prendrepeut qui aléatoire variableuneest source la ,

10

10

10

Page 9: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Cas particulier des 2 classes et coûts 0-1

0)(1)(

0)(1)(

10

1100

10

1 0

1, 0,1

1, )(, 0,)(,1

011101 )(sinon 1

110000 si 0,CCout

) source laest c'( et ) source laest c'( actions 2 rejet, de pas

éprobabilit de Bernouilli de loi unesuit 1,et 0 sources 2

xDX

xDX

xDX

xDX

XX

lk

dxxfxSP dxxfxSP

dxxfp dxxfp

dxxfxDsCp dxxfxDsCp

), ; C(),C(lk

), ; C(),C(lkas

sas a

pSs s

Minimiser J(D) c’est minimiser la probabilité d’erreur

2

1 ,)(,)(,)(

)(min décision de règle uned'Cout

kkXk

D

sSPdxkxfxDsCXDSCEDJ

DJDD

erreur 1et 0et 0 PSCXPSCXP O

Page 10: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

0

0.5

1

loi à

pos

terio

ri

on dé cide la classe 0 on dé cide la classe 1

Théorème : - D* est la règle de Bayes (celle qui minimise la probabilité d’erreur)

- J*=J(D*)=P(D*(x)=S) est la plus petite erreur possible (et donc de coût minimal dans le cadre deux classes 0-1)

Théorème fondamental

sinon 0

2/1)(1P si 1)(*

xrxSxD

Définition : règle de décision du maximum « a posteriori »

x

r(x)

x*tel que

r(x*)=1/2

Page 11: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Définition fondamentaleCoût minimum = maximum à posteriori = minimum d’erreur

Définitions : - D* est appelée règle de Bayes c’est la règle qui donne la plus petite probabilité d’erreur

- le problème qui consiste à rechercher D* est le problème de Bayes

- J*=J(D*) est appelée l’erreur de Bayes

)(minarg )(minarg : possibler classifieumeilleur le

)( )( :ur)(classifiedécision de règle uned'erreur d' éprobabilit

*

*

DJsXDPDD

SXDPDJ

DD DD

Pour donnés et ),( kX sPkxf

Page 12: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

espace des sources

Résumé : problème de RdF

kX

ksxPkxf

sP à (analogue ),( ncevraisembla

priori à loi

Kk sss ,...,,...,1S

)( ,...,,...,1 : RdF

autres)(classes actions des ensemble ,...,2,1tiquescaractéris des espace

xDyxLlRD

LR

d

d

A

lklk asCasRC

,, :Cout

AS

(erreur de prédiction)

K

kkXk

D

sSPdxkxfxDsCXDSCEDJ

DJD

1 ,)(,)(,)(

)(min décision de règle uned'Cout D

)(minarg )(minarg Bayes de règle : possibler classifieumeilleur le

)( )( :ur)(classifiedécision de règle uned'erreur d' éprobabilit cout

1-0cout - classes 2

*

*

DJsXDPDDSXDPDJ

DD DD

Page 13: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

dens

itée

et lo

i à p

oste

riori

classe 0classe 1classe 0classe 1

illustration

Illustration 1dpour deux classes

f X(x,0) ~ N(0,1)

f X(x,1) ~ N(1,1)

r(x) = P(S=1|x)

P(S=0|x) = 1-r(x)

Page 14: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Démonstration du théorème fondamental(maximum a posteriori)

1)(

0)(1)(

0)(1)(

1 )(21

)(11)(11

011 11

0et 0)(1et 1)(1

)(1 )(

XD

XDXD

XDXD

xr

xrxr

xXSPxXSP

xXSXDPxXSXDP

xXSXDP

xXSXDP

0111)(2* 1)(1)(* xDxDxrDJDJ

négatifssont sdeux terme les 21

)(0* si

positifssont sdeux terme les 21

)(1* si

xrD

xrD

Il est difficile de minimiser J(D) (démonstration constructive)car la fonction coût n’est pas dérivable

Page 15: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Interprétation en terme de moindres carrés

xXSPxXSExr

xrXD

xXSxrExrXDxXSxrxrXDE

xXSxrExrXD

xXSxrxrXDE

xXSXDEDJ

x

D

D

D

D

DD

1)(

)()(min

)()()(min )()()(2

)()()(min

)()()(min

)(min)(min

fixé à

2

22

22

2

2

La minimisation de l’erreur quadratique mène à la règle de Bayès

)(

)(min)(min

xr

xXSXDEDJDD

La minimisation de l’erreur absolue aussi !

Page 16: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

dens

itée

et lo

i à p

oste

riori

classe 0classe 1classe 0classe 1

Rejet : règle de Chow

Rejet d’ambiguité

sinon rejet

2/1)(10P si 02/1)(1P si 1

)(* A

AxrxS

xrxSxD

Définition : règle de décision du maximum « a posteriori »

1/2

1

A

x

classe 0 rejet classe 1

Page 17: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Rejet de distance (Dubuisson)

dens

itée

et lo

i à p

oste

riori

classe 0classe 1classe 0classe 1

1/2

1

A

x

rejet de distance classe 0 rejet classe 1 rejet de distance

D = 0 et A = .5 :

règle du MAP (bayes pour le coût 0-1)

ambiguïtéd'rejet sinon 0 classe 2/1)(10P si 1 classe 2/1)(1P si

:sinon distance derejet P si

)(*

D

A

AxrxS

xrxS

x

xD

D

Page 18: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

-4 -2 0 2 4 6 8-6

-4

-2

0

2

4

6

0.7

0.7

0.7

0.7

??????

C0

C1

illustration

Illustration 2dpour deux classes

f X(x,0) ~ N(0,1)

f X(x,1) ~ N(1,1)

r(x) = P(S=1|x)

P(S=0|x) = 1-r(x)

P(x) = f X(x,0) + f X(x,1)

rejet d’ambiguïté

Page 19: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

-4 -2 0 2 4 6 8-6

-4

-2

0

2

4

6Discrimination de Parzen

illustration

Page 20: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Un exemple simpleS=0 vous ratez votre DEA, S=1 vous l’avezX : le nombre d’heures de travail par semaine

...3,0

,min41

* alors

4,0uniforme~X si

)! nul prédictif(pouvoir 21

* alors

heures) étudier d' obligés êtes ou vous militaire (école si

,min)(1),(min*

21

si rateon

21

si al'on Bayes de règle

1 posons

4

0

dxxc

xcc

DJ

c

DJ

ccXXc

XcExrxrEDJ

cxcx

x

cxcx

xcx

xxXSP

c

Page 21: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Un exemple simpleS=0 vous ratez votre DEA, S=1 vous l’avezX : le nombre d’heures de travail par semaine

...3,0

,min41

* alors

4,0uniforme~X si

)! nul prédictif(pouvoir 21

* alors

heures) étudier d' obligés êtes ou vous militaire (école si

,min)(1),(min*

21

si rateon

21

si al'on Bayes de règle

1 posons

4

0

dxxc

xcc

DJ

c

DJ

ccXXc

XcExrxrEDJ

cxcx

x

cxcx

xcx

xxXSP

c

Page 22: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

espace des sources

Résumé : problème de RdF

kX

ksxPkxf

sP à (analogue ),( ncevraisembla

priori à loi

Kk sss ,...,,...,1S

)( ,...,,...,1 : RdF

autres)(classes actions des ensemble ,...,2,1tiquescaractéris des espace

xDyxLlRD

LR

d

d

A

lklk asCasRC

,, :Cout

AS

(erreur de prédiction)

K

kkXk

D

sSPdxkxfxDsCXDSCEDJ

DJD

1 ,)(,)(,)(

)(min décision de règle uned'Cout D

Bayes de règle la à ressemble"" ,1,,

: que tel algorithmeun trouver

,,

*Dniyx

kxfsP

ii

Xk

A

A

Page 23: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

RdF : stratégie de Base1. Estimer

2. Retrouver la règle de BayesAlternative

minimiser directement la probabilité d’erreur(estimer une densité est un problème très difficile)

et ),( kX sPkxf

nniinn

nn

n

nnii

YXYXYXYXSXDPJ

xDJJ

xD

YXYXYXYX

,,...,,,...,,,,)(

)(:tion classifica deerreur une

)( :r classifieuun

,,...,,,...,,,, )étiquettes - stiques(caractéri couples de ensemble néchantillol' geaprentissad' base la

2211

2211

Page 24: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Comment comparer deux algorithmesSoit D1 et D2 deux algorithmes (kppv et arbres de décision)Soit J1 = J(D1) l ’erreur de classification de D1 et J2 = J(D2)

Imaginons que nous connaissions J1 et J2

Sur un échantillon D1 est meilleur, sur un autre c’est D2

comment les comparer ?

En moyenne : E(J) (l’espérance sur tous les échantillons possibles)

un algorithme est dit consistant si

la probabilité d’erreur tend vers son minimum

si c’est vrai quelle que soit la distribution des exemples, l’algorithme est dit universellement consistant

*)(lim JDJE nn

Définition

Page 25: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

Théorème (Stone 1977)

L’algorithme des kppv est un algorithme universellement consistant

k YxD

,...,Y,YY

xistiquesk caractér,...,X,XX

xnk

nk

n

k

k

nn

des emajoritair vote)(

antescorrespond étiquettes les soient

de proches plus les les soient

tiquecaractéris un vecteurpour

0et )(

21

21

Attention : un bon algorithme peut donner un mauvais classifieur (on peu aussi gagner au loto)

Page 26: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

A savoirVariable aléatoire

• cas discret (un exemple)• cas continu (un exemple)

Probabilité, probabilité conditionnelle

fonction de répartition et densité

loi usuelles : bernouilli, binomiale, poisson, normale

Espérance, •cas discret (un exemple)•cas continu (un exemple)

Variance

Quiz de 5 minutes maintenant

Page 27: DEA Perception et Traitement de lInformation Reconnaissance des formes Règle de Bayes S. Canu scanu/RdF

ConclusionUn problème de reconnaissance des formes se caractérisepar une loi à priori, une vraisemblance (souvent inconnues),une fonction coût et un échantillon (souvent connus).

La meilleure solution possible (souvent inconnue) la règle de Bayes c’est le MAP qui minimise la probabilité d’erreur

Il faut en plus faire du rejet

Reste à savoir comment approcher la règle de Bayes à partir de l’échantillon

deux stratégies sont possibles : 1. Approcher les lois inconnues puis appliquer le principe du MAP (la « règle de bayes » sur une approximation des lois)2. Minimiser directement une estimation de la probabilité d’erreur