Reconnaissance des formes

cours de D.E.A.

Introduction

S. Canu

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

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– Exam final 50 % de la note

– TP 1 : étude biblio : 15 %

– TP 2 : page web : 15 %

– TP 3 : programme matlab, octave,… 15 %

– quiz : 5 % (0 ou +1) 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 – caractère - écriture (c’est une lettre, un mot, une phrase, un sens)– parole (forme temporelle)– voix, identification : c’est Chirac aux guignol, localisation d’une source et séparation – visage (vision)

– identification : visage + voix + odeur + empreintes : c’est « Chirac »

– une voiture (concept imprécis)

– il va pleuvoir (fusion de données - décision incertaine)

Aspects humains

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 Chirac 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

source représentation caractéristiques décision (action)

capteurPrétraitementextraction de

caractéristiques

Algorithmede

R des F

espace des

sources

espace des

caractéristiques

espace des

décisions

Kk sss ,...,,...,1S dRX Ll aaa ,...,,...,1A

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 RdFAlgorithme

de Reconnaissance

des Formes

Une forme x(vecteur forme

des caractéristiques)

C’est la forme

« y »

1. Un algorithme de reconnaissance des formes est une règle de Décision (déterministe dans le cours)

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

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

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

xDyxLlRD

LyRx

d

d

A« je ne sais pas »,

« inconnue »

Sources - Actions - ClassesRègles de décision

Xn

X1

+

+

+

++

+

+

+

+ +

++

xx

xx

x

xx

xxxx

xxx

Frontière de décisionfonction b(x)=0telle que D(x-e) = D(x+e) prototypes

Xn

X1

+

+

+

++

+

+

+

+ +

++

xx

xx

x

xx

xxxx

xxx

Rejet de distanceXn

X1

+

+

+

++

+

+

+

+ +

++

xx

xx

x

xx

xxxx

xxx

Rejet d’ambiguïté

Buts de la RdF

D : Algorithme de

Reconnaissancedes 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

Coûts : matrice de confusion Vraie classe 1 2 3 … k … KDécision123...L???

Rejet

(ambiguïté et distance)

lklk asCasRC

,, :Cout

AS

Si je décide l’action al alors que la « vraie » classe est sk

Combien coûte cette décision ?

Coûts : matrice de confusion Vraie classe 1 2 3 … k … KDécision123...L???

Rejet

(ambiguïté et distance)

lklk asCasRC

,, :Cout

AS

Si je décide l’action al alors que la « vraie » classe est sk

Combien coûte cette décision ?

La réalité

notre décision

Malade pas malade

On soigne

on ne soigne pas

0

0

Coûts : matrice de confusion Vraie classe 1 2 3 … k … KDécision123...L???

Rejet

(ambiguïté et distance)

lklk asCasRC

,, :Cout

AS

Sur les 1500 « cas » testés,voici les résultats de l’algorithmesde RdF

La réalité

notre décision

Malade pas malade

On soigne

on ne soigne pas

14

1480

Algorithme de coût minimum

kXD

kX

K

kk

K

kk

Xk

K

kk

x

k

lklk

sPkxfDJ

dxsPkxfxDsCXDsCEDJ

kxfXs

sPxDsCDJ D

RJD

asCasRC

, )(min

, )(,)(,)(

, densité de aléatoire variableuneest , source lapour

)(, )(

: décision de règle uned'Cout

,, :Cout

11

1possibles

les tous

D

D

AS

Coût minimum : cadre probabiliste

kD

kX

K

kk

K

kk

Xk

K

kk

x

k

lklk

sSPDJ

dxsSPkxfxDsCXDsCEDJ

kxfXs

sSPxDsCDJ D

RJD

asCasRC

)(min

, )(,)(,)(

, densité de aléatoire variableuneest , source lapour

)(, )(

: décision de règle uned'Cout

,, :Cout

11

1possibles

les tous

D

D

AS

La sourceS est une variable aléatoire

P(observer un « E »)

exemple des maladesP(malade) = 15/1000

cas équiprobableP(S=sk) = 1/K(1/2 si K=2)

Coût minimum : cadre probabiliste

kD

kX

K

kk

K

kk

Xk

K

kk

x

k

lklk

sSPDJ

dxsSPkxfxDsCXDsCEDJ

kxfXs

sSPxDsCDJ D

RJD

asCasRC

)(min

, )(,)(,)(

, densité de aléatoire variableuneest , source lapour

)(, )(

: décision de règle uned'Cout

,, :Cout

11

1possibles

les tous

D

D

AS

La sourceS est une variable aléatoire

P(observer un « E »)

exemple des maladesP(malade) = 15/1000

cas équiprobableP(S=sk) = 1/K(1/2 si K=2)

f(x)

: fo

nctio

n de

nsité

e

classe 0classe 1

Coût minimum : cadre probabiliste

kxfXs

sSPxDsCDJ D

RJD

asCasRC

Xk

K

kk

x

k

lklk

, densité de aléatoire variableuneest , source lapour

)(, )(

: décision de règle uned'Cout

,, :Cout

1possibles

les tous

D

AS

Illustration 1dpour deux classes

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

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

Coût minimum : cadre probabiliste

kXD

kX

K

kk

K

kk

Xk

K

kk

x

k

lklk

sSPkxfDJ

dxsSPkxfxDsCXDsCEDJ

kxfXs

sSPxDsCDJ D

RJD

asCasRC

, )(min

, )(,)(,)(

, densité de aléatoire variableuneest , source lapour

)(, )(

: décision de règle uned'Cout

,, :Cout

11

1possibles

les tous

D

D

AS

Toutes lesclasses

En

moyenne On recherche la règle de décision de coût minimum

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 la semaine prochaine

Buts de la RdF2 points de vue : utilisateur - concepteur

Algorithme de

Reconnaissancedes Formes

Une forme(vecteur forme

des caractéristiques)

C’est la forme

« y »

Méthode de construction de l’Algorithme de

Reconnaissancedes Formes

Les enjeux de la RdF

L’apprentissage : ce qu’un bébé réalise en deux ans, aucune machinen’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 RdFDé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

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)

Méthodes de RdF

La RdF par apprentissage