Reconnaissance des formes

Introduction
 Objectifs du cours
– Principes de base de la RdF
– règle de décision
– cout, règle de Bayes
– matrice de confusion courbe C.O.R.
– Méthode de développement d’une application de RdF
– méthodes et Algorithmes
– méthodes « historiques » (analyse discriminante)
– kppv, CART (arbres de décision)
– réseaux de neurones : optimisation
– EM
– Ouvertures et perspectives (fusion de données, flou, DS,…)
 Aspects pratiques du cours

Biblio :
– les livres du cours
K. Fukunaga, Introduction to Statistical Pattern Recognition (Second Edition), Academic Press, New York, 1990.
P.A. Devijver and J. Kittler, Pattern Recognition, a Statistical Approach, Prentice Hall, Englewood Cliffs, 1982.
R.O. Duda and P.E. Hart, Pattern classification and scene analysis, John Wiley & Sons, New York, 1973.
L. Breiman, J.H. Friedman, R.A. Olshen, and C.J. Stone, Classification and regression trees, Wadsworth, 1984.
L. Devroye, L. Györfi and G. Lugosi, A Probabilistic Theory of Pattern Recognition, (Springer-Verlag 1996)
S. Haykin, Neural Networks, a Comprehensive Foundation. (Macmillan, New York, NY., 1994)
V. N. Vapnik, The nature of statistical learning theory (Springer-Verlag, 1995)

B. Dubuisson, Diagnostic et reconnaissance des formes (Hermès, 1990)

M. Milgram, Reconnaissance des formes, méthodes numériques et connexionnistes, (Armand Colin, collection 2ai, 1993

les journaux
– pattern recognition
les conférences
Quelques exemples de RdF
Quelques exemples de RdF
 Quelques exemples de RdF
– C’est un rond, c’est un carré, (une forme quoi !)
– le feu est vert,
(je passe, ou je m’arrête ! Classe = action possible)
– votre électrocardiogramme est normal :
diagnostic = détection : signal ou bruit (inspection : qualité, monitoring)
– c’est une facture téléphone (reconnaissance syntaxique : les « règles »)

– odeur : c’est une madeleine Aspects humains

– caractère - écriture
(c’est une lettre, un mot, une phrase, un sens)
– parole (forme temporelle)
– voix, identification : c’est M. X aux guignol, localisation d’une source et séparation
– visage (vision)
– identification : visage + voix + odeur + empreintes : c’est « M. X »

– une voiture (concept imprécis)

– il va pleuvoir (fusion de données - décision incertaine)
 Quelques problèmes de RdF
– C’est un rond, c’est un carré, Distance avec des formes de références
– le feu est vert,
(je passe, ou je m’arrête) Représentation des caractéristiques
– votre électrocardiogramme est normal :
diagnostic = détection : signal ou bruit Cadre aléatoire
– c’est une facture téléphone Modèle = les « règles » (même source)

– odeur : c’est une madeleine capteur complexe

– caractère - écriture complexité de la tâche
(c’est une lettre, un mot,...) modélisation par apprentissage
– parole (forme temporelle) Temps (système évolutif :environnement)
– voix (c’est M. X aux guignol), complexité de l’espace des caractéristiques
– visage (vision) invariances
– identification fusion - (informations hétérogènes)

– une voiture (concept imprécis) définition des classes (monitoring)

– il va pleuvoir décision aléatoire
 Les différentes phases des algorithmes
de reconnaissance des formes
Prétraitement Algorithme
capteur extraction de de
caractéristiques R des F

source représentation caractéristiques décision

(action)

espace espace espace

des des des
sources caractéristiques décisions
S  s1 ,..., sk ,..., s K  A  a1 ,..., al ,..., a L 
X  Rd
 Quelques problèmes de RdF
problème sources caractéristiques actions
– C’est un rond, c’est un carré,
– le feu est vert,
(je passe, ou je m’arrête)
– votre électrocardiogramme est normal :
diagnostic = détection : signal ou bruit
– c’est une facture téléphone

– odeur : c’est une madeleine

– caractère - écriture
(c’est une lettre, un mot,...)
– parole (forme temporelle)
– voix (c’est Chirac aux guignol),
– visage (vision)
– identification

– une voiture (concept imprécis)

– il va pleuvoir
 Buts de la RdF
Algorithme
Une forme x C’est
de
(vecteur forme la forme
Reconnaissance
des caractéristiques) «y»
des Formes
1. Un algorithme de reconnaissance des formes est une règle de
Décision (déterministe dans le cours)
x  Rd espace des caractéristiques
y    A  1,2,..., L ensemble des actions (classes  autres)
« je ne sais pas »,
RdF D : R  1,..., l ,..., L
d
« inconnue »
x  y  D( x)
2. Une règle de décision déterministe établie un
partitionnement de l’espace des caractéristiques

C’est le problème de discrimination

 Sources - Actions - Classes
Règles de décision
Xn x x Frontière de décision
x x
+ + + x x fonction b(x)=0
+ x x x
+ + x x
+ + + x telle que
x
prototypes + + x D(x-e) = D(x+e)
+
X1

Rejet de distance Rejet d’ambiguïté

Xn x x Xn x x
x x x x
+ + + x x + + + x x
+ x x x x x x
+ + x x + + + x x
+ + + x + + + x
x x
+ + x + + x
+ +
X1 X1
 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"
 Coûts : matrice de confusion
Vraie classe 1 2 3 … k … K
Décision
1
2
3
.
.
.
L
?
Rejet
??
(ambiguïté et distance)
 Si je décide l’action al
Cout C : SA  R alors que la « vraie » classe est sk
sk , al   C sk , al 
Combien coûte cette décision ?
 Coûts : matrice de confusion
Vraie classe 1 2 3 … k … K
Décision
1
2 La réalité
Malade pas malade
3 notre décision
.
. 0 1
.
L
?
Rejet 100 0
??
(ambiguïté et distance)
 Si je décide l’action al
Cout C : SA  R alors que la « vraie » classe est sk
sk , al   C sk , al 
Combien coûte cette décision ?
 Coûts : matrice de confusion
Vraie classe 1 2 3 … k … K
Décision
1
2 La réalité
Malade pas malade
3 notre décision
.
. 14 5
.
L
?
Rejet 1 1480
??
(ambiguïté et distance)
 Sur les 1500 « cas » testés,
Cout C : SA  R voici les résultats de l’algorithmes
sk , al   C sk , al 
de RdF
 Algorithme de coût minimum
Cout C : S  A  R
sk , al   C sk , al 
Cout d' une règle de décision D
J : D  R
K 
 

D  J ( D )     C  sk , D ( x )   P  sk 
k 1 tous les 
 x possibles 
pour la source sk , X est une variable aléatoire de densité f X  x, k 
K K
J ( D )   E C sk , D( X )     C sk , D( x)  f X  x, k  Psk dx
k 1 k 1

min J ( D )  f X  x, k  P  sk 
DD
Coût minimum : cadre probabiliste
Cout C : S  A  R
sk , al   C sk , al  La source
S est une variable aléatoire
Cout d' une règle de décision D
J : D  R P(observer un « E »)
K 
 

D  J ( D )     C  sk , D ( x )   P  S  sk 
k 1 tous les 
 x possibles 
pour la source sk , X est une variable aléatoire de densité f X  x, k 
K K exemple des malades
J ( D )   E C sk , D( X )     C sk , D( xP(malade)
)  f X  x, k  P
=15/1000
S  sk dx
k 1 k 1

cas équiprobable
min J ( D )  P  S  sk 
DD P(S=sk) = 1/K
(1/2 si K=2)
Coût minimum : cadre probabiliste
Cout C : S  A  R
sk , al   C sk , al  La source
S est une variable aléatoire
Cout d' une règle de décision D
J : D  R P(observer un « E »)
K 
 

D  J ( D )     C  sk , D ( x )   P  S  sk 
k 1 tous les 
 x possibles 
pour la source sk , X est une variable aléatoire de densité f X  x, k 
K K exemple des malades
J ( D )   E C sk , D( X )     C sk , D( xP(malade)
)  f X  x, k  P
=15/1000
S  sk dx
k 1 k 1

cas équiprobable
min J ( D )  P  S  sk 
DD P(S=sk) = 1/K
(1/2 si K=2)
 Coût minimum : cadre probabiliste
Cout C : S  A  R
sk , al   C sk , al 
Cout d' une règle de décision D
J : D  R
K 
 

D  J ( D )     C  sk , D ( x )   P  S  sk 
k 1 tous les 
 x possibles 
pour la source sk , X est une variable aléatoire de densité f X  x, k 
f(x) : fonction densité e

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

f X(x,1) ~ N(m1,1)
 Coût minimum : cadre probabiliste
Cout C : S  A  R
sk , al   C sk , al 
Cout d' une règle de décision D
J : D  R
K 
 

D  J ( D )     C  sk , D ( x )   P  S  sk 
k 1 tous les 
 x possibles 
pour la source sk , X est une variable aléatoire de densité f X  x, k 
K K
J ( D )   E C sk , D( X )     C sk , D( x)  f X  x, k  PS  sk dx
k 1 k 1
Toutes les
classes
min J ( D )  f X  x, k  P  S  sk 
DD
En
moyenne On recherche la règle de décision de coût minimum
 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
 Buts de la RdF
2 points de vue : utilisateur - concepteur
Algorithme
Une forme C’est
de
(vecteur forme la forme
Reconnaissance
des caractéristiques) «y»
des Formes

Méthode de construction
de l’Algorithme de
Reconnaissance
des Formes
 Les enjeux de la RdF
L’apprentissage :
ce qu’un bébé réalise en deux ans, aucune machine
n’est aujourd’hui capable de la réaliser :
et il a besoin d’exemples
(cf les expériences folles du duc de Bavière)

modéliser l’information, dépasser la complexité

fusion de données

représentation des incertitudes

Problèmes de la RdF
Décision

apprentissage

sélection d’entrée

évaluation des performances

prise en compte du temps

fusion de données hétérogènes

Les différentes étapes d’une
application de RdF
– Recueil des données brutes
– génération de caractéristiques
– sélection des caractéristiques pertinentes
– étiquetage des classes
– conception du classifieur
– évaluation du système
 notations
S  s1 ,..., sk ,..., s K  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 
k
loi jointe Pal , x 
Méthodes de RdF

La RdF par apprentissage