Reconnaissance des formes

Règle de Bayes
 Buts de la RdF
D : Algorithme
Une forme x C’est
de
(vecteur forme la forme
Reconnaissance
des caractéristiques) « y=D(x) »
des Formes
x  Rd espace des caractéristiques
y  1,2,..., L ensemble des décisions
RdF D : R d  1,..., l ,..., L
x  D( x)
Nous voulons un algorithme de RdF performant
x  R d , D(x)  " la vraie classe"
Cout d' une règle de décision D min J ( D)
DD

J ( D)  E C S , D( X )     C sk , D( x)  f X  x, k  dx  PS  sk 
K

k 1
 Théorème de Bayes (et non la règle)
loi à priori P  S  sk  Ex : en français P(e) = 0,12
loi à posteriori P S  s k x  Ex : après avoir observé x
quelle est P(e|x) ?
vraisemblance f X ( x, k ) (analogue à P x S  sk 
loi des " observations" f X ( x)   f X ( x, k )PS  sk 
P  S  sk , x 
k
loi jointe

PS  sk , x   PS  sk x  f X ( x) On choisi une observation, et on décide

PS  sk , x   f X ( x, k ) PS  sk  On choisi la source, et on émet

f X ( x, k ) PS  sk  Attention à la confusion
théorème : PS  sk x  
f X ( x) source - action
Cout d' une règle de décision D min J ( D)
DD

J ( D)  E C S , D( X )     C sk , D( x)  f X  x, k  dx  PS  sk 
K

k 1
 illustration
10
sans autre information
20 on décide toujours
30
qu’un pixel
source 1 vient de la zone
40
(source 1)
50

60 car P(S1) > P(S2)

70

80
A PRIORI
source 2
90
que se passe t’il
100
10 20 30 40 50 60 70 80 90 100
si l’on connaît
une caractéristique : x
l’intensité
 Caractéristique : x
illustration l’intensité
10
on décide
20
l’action qui « coûte »
30 le moins cher
40
source 1
en cout 0-1
50
c’est la classe max
60
A POSTERIORI
70

2000 f(x|s1)
80

90
source 2 1500
f(x|s2)
1000
100
10 20 30 40 50 60 70 80 90 100
500
Les vraisemblances
Pa1 x   f  x, S1 PS1 
0
-50 0 50 100
x
 illustration
0.8 Pa2 x   f  x, S 2 PS 2 
0.7 Pa1 x   f  x, S1 PS1 
0.6
f(x|s2)

0.5

0.4

0.3

0.2 f(x|s1)
0.1

0
-8 -6 -4 -2 0 2 4 6 8 10 12

Règle de décision
 notations
S  s1 ,..., sk ,..., sK  espace des sources
Rd espace des caractéristiques
A  1,2,..., L ensemble des actions (classes  autres)
RdF D : R d  1,..., l ,..., L
x  y  D( x)
Cout C : S  A  R J coût d ’une règle de décision
sk , al   C sk , al  (erreur de prédiction)

loi à priori P  sk 
loi à posteriori Pal x 
vraisemblance f X ( x, k ) (analogue à P x sk 
loi des " observations" f X ( x)   f X ( x, k )Psk 
Pal , x 
k
loi jointe
Cas particulier des 2 classes et coûts 0-1
S , la source est une variable aléatoire qui peut prendre 2 valeurs
s0  0 et s1  1
lois à priori (Bernouilli) Ps0 , Ps1  ou PS  0 , p  PS  1
lois à posteriori Ps0 x , Ps1 x  ou PS  0 x , PS  1 x 
P S  0 x   1  P S  1 x 
r ( x )  P S  1 x 
dans ce cas : E S x   0 * PS  0 x   1* PS  1 x   PS  1 x   r ( x)

vraisemblances f X ( x,0), f X ( x,1) (analogue à P x S 

lois des " observations" f X ( x)  f X ( x,0) PS  0   f X ( x,1) PS  1
 f X ( x,0)1  p   f X ( x,1) p
lois jointes PS , x  composée de P0, x  et de P1, x 
soit CO  x pour lesquels on décide l' action a0 

Perreur  P X  CO et S  1  P X  C0 et S  0
 Cas particulier des 2 classes et coûts 0-1
2 sources s0  0 et s1  1, S suit une loi de Bernouilli de probabilité p
pas de rejet, 2 actions a0 (c' est la source s0 ) et a1 (c' est la source s1 )
0 si k  l C( 0 ,0 )  0 ; C( 0 ,1 )  1
Cout Csk , al   
 1 sinon (k  l ) C( 1,0 )  1 ; C( 1,1 )  0
Cout d' une règle de décision D min J ( D)
DD

J ( D)  E C S , D( X )     C sk , D( x)  f X  x, k  dx  PS  sk 
2

k 1
 1  p  C s0 , D ( x)  f X  x,0  dx  p  C s1 , D( x)  f X  x,1 dx
 1  p   f X  x,0  dx  p  f X  x,1 dx
D ( x ) 1 D ( x ) 0

  PS  0 x  f X  x  dx   PS  1 x  f X  x  dx
D ( x ) 1 D ( x ) 0
 P X  C0 et S  0  P X  CO et S  1  Perreur
Minimiser J(D) c’est minimiser la probabilité d’erreur
 Théorème fondamental
Définition : règle de décision du maximum « a posteriori »
1 si PS  1 x   r ( x)  1 / 2
D * ( x)  
0 sinon
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)
1
loi à posteriori

0.5

0
on dé cide la classe 0 x* on dé cide la classe 1 x
tel que
r(x*)=1/2
 Définition fondamentale
Coût minimum = maximum à posteriori
= minimum d’erreur
Pour f X ( x, k ) et Psk  donnés
probabilité d' erreur d' une règle de décision (classifieur) :
J ( D)  P D( X )  S 

le meilleur classifieur possible : D*

D*  arg min P D( X )  s   arg min J ( D)
DD DD

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
 Résumé : problème de RdF
S  s1 ,..., sk ,..., sK  espace des sources
Rd espace des caractéristiques
A  1,2,..., L ensemble des actions (classes  autres)
RdF D : R  1,..., l ,..., L
d Cout C : S  A  R
x  y  D( x) sk , al   C sk , al 
loi à priori P  sk 
vraisemblance f X ( x, k ) (analogue à P x sk 
Cout d' une règle de décision D min J ( D) (erreur de prédiction)
DD

J ( D)  E C S , D( X )     C sk , D( x)  f X  x, k  dx  PS  sk 
K

k 1

2 classes - cout 0 - 1
cout  probabilité d' erreur d' une règle de décision (classifieur) :
J ( D)  P D( X )  S 
le meilleur classifieur possible : D*  règle de Bayes
D*  arg min P D( X )  s   arg min J ( D)
DD DD
 illustration

classe 0
classe 1
densité e et loi à posteriori

Illustration 1d classe 0
pour deux classes classe 1
f X(x,0) ~ N(m0,1)

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

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

P(S=0|x) = 1-r(x)
 Démonstration du théorème fondamental
(maximum a posteriori)
PD( X )  S X  x  
 1  PD( X )  S X  x 
 1  PD( X )  1 et S  1 X  x   PD( X )  0 et S  0 X  x 
 1  1D ( X )1 P S  1 X  x   1D ( X )0 PS  0 X  x 
 1  1D ( X )1 r ( x)  1D ( X )0 1  r ( x) 
 1  2r ( x)  1D ( X )1
J  D   J  D *  2r ( x)  11D*( x )1  1D ( x )1   0
1
si D*  1  r ( x)  les deux termes sont positifs
2
1
si D*  0  r ( x)  les deux termes sont négatifs
2
Il est difficile de minimiser J(D) (démonstration constructive)
car la fonction coût n’est pas dérivable
Interprétation en terme de moindres carrés
à x fixé

D D

min J ( D)  min E  D( X )  S  X  x
2

 min E  D( X )  r ( x)  r ( x)  S  X  x 
2

 min  D( X )  r ( x)   E r ( x)  S  X  x 
D
2 2

 2 E  D( X )  r ( x) r ( x)  S  X  x 
D

D
2

 min  D( X )  r ( x)   E r ( x)  S  X  x
2

 min  D( X )  r ( x) 
2
D
 r ( x )  E S X  x   P S  1 X  x 
La minimisation de l’erreur quadratique mène à la règle de Bayès

La minimisation min J ( D )  min E  D ( X )  S X  x 

D D
de l’erreur absolue aussi !  r ( x)
 Rejet : règle de Chow
1 si PS  1 x   r ( x)   A  1 / 2
Définition :
D * ( x)  0 si PS  0 x   1  r ( x)   A  1 / 2
règle de décision
du maximum
« a posteriori »  rejet sinon

1
classe 0
classe 1
densité e et loi à posteriori

classe 0
A classe 1

1/2

Rejet
d’ambiguité
x
classe 0 rejet classe 1
 Rejet de distance (Dubuisson)
 si P x    D rejet de distance
 sinon :
 si PS  1 x   r ( x)    1 / 2
D * ( x)   classe 1
 si PS  0 x   1  r ( x)   A  1 / 2 classe 0
A

 sinon rejet d' ambiguïté

1
classe 0
classe 1
densité e et loi à posteriori

classe 0
A classe 1 D = 0 et
A = .5 :
1/2 règle du MAP
(bayes pour
le coût 0-1)
D
x
rejet de distance classe 0 rejet classe 1 rejet de distance
 illustration
6

0.7
4
Illustration 2d C1
pour deux classes

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

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

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

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

C0

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

-4
??????

rejet d’ambiguïté -6
-4 -2 0 2 4 6 8
 illustration
Discrimination de Parzen
6

-2

-4

-6
-4 -2 0 2 4 6 8
 Un exemple simple
S=0 vous ratez votre diplôme, S=1 vous l’avez
X : le nombre d’heures de travail par semaine

posons P S  1 X  x   x
xc
 x 1
 on l' a si x  c  2  x  c
règle de Bayes 
x 1
on rate si   xc
 xc 2
 min c, X  
J  D *  E min r ( x),1  r ( x)   E  
 c X 
si X  c (école militaire ou vous êtes obligés d' étudier c heures)
1
alors J  D *  (pouvoir prédictif nul !)
2
si X ~ uniforme0,4c 
1 4c min c, x 
alors J  D *   dx  0,3...
4c 0 c  x
 Un exemple simple
S=0 vous ratez votre DEA, S=1 vous l’avez
X : le nombre d’heures de travail par semaine

posons P S  1 X  x   x
xc
 x 1
 on l' a si x  c  2  x  c
règle de Bayes 
x 1
on rate si   xc
 xc 2
 min c, X  
J  D *  E min r ( x),1  r ( x)   E  
 c X 
si X  c (école militaire ou vous êtes obligés d' étudier c heures)
1
alors J  D *  (pouvoir prédictif nul !)
2
si X ~ uniforme0,4c 
1 4c min c, x 
alors J  D *   dx  0,3...
4c 0 c  x
 Résumé : problème de RdF
S  s1 ,..., sk ,..., sK  espace des sources
Rd espace des caractéristiques
A  1,2,..., L ensemble des actions (classes  autres)
RdF D : R  1,..., l ,..., L
d Cout C : S  A  R
x  y  D( x) sk , al   C sk , al 
loi à priori P  sk 
vraisemblance f X ( x, k ) (analogue à P x sk 
Cout d' une règle de décision D min J ( D) (erreur de prédiction)
DD

J ( D)  E C S , D( X )     C sk , D( x)  f X  x, k  dx  PS  sk 
K

k 1

Psk , f X  x, k 
trouver un algorithme A tel que :
A  xi , yi , i  1, n  " ressemble" à D* la règle de Bayes
 RdF : stratégie de Base
1. Estimer f X ( x, k ) et Psk 
2. Retrouver la règle de Bayes
Alternative
minimiser directement la probabilité d’erreur
(estimer une densité est un problème très difficile)

la base d' aprentissage  l' échantillon

 ensemble de couples (caractéristiques - étiquettes)
 X 1 , Y1 ,  X 2 , Y2 ,...,  X i , Yi ,...,  X n , Yn 
un classifieur : Dn ( x)
une erreur de classification : J n  J  Dn ( x) 
J n  PDn ( X )  S  X 1 , Y1 , X 2 , Y2 ,..., X i , Yi ,..., X n , Yn 
Comment comparer deux algorithmes
Soit 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)

Définition
un algorithme est dit consistant si *
lim E  J ( Dn )   J
n
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
 Théorème (Stone 1977)
L’algorithme des kppv est un algorithme universellement consistant
 k n 
k (n) n  et  0
n
pour un vecteur caractéristique x
soient  X 1,X 2 ,...,X k  les k caractéristiques les plus proches de x
soient Y1,Y2 ,...,Yk  les étiquettes correspondantes

Dn ( x)  vote majoritaire des k Y

Attention : un bon algorithme peut donner un mauvais classifieur

(on peu aussi gagner au loto)
 A savoir
Variable 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

 Conclusion
Un problème de reconnaissance des formes se caractérise
par 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