RECONNAISSANCE DES FORMES - sorbonne-universite · Traitement dimages Traitement du signal (parole) Biologie ... Rappel sur les matrices de covariances Analyse en composantes principales

1Cours de Reconnaissance des Formes– Catherine Achard

RECONNAISSANCE

DES FORMES

Catherine ACHARD

Institut des Systèmes Intelligents et de

Robotique

[email protected]


IntroductionPrincipeApplicationsDifficultésMéthode supervisée ou non supervisée Cas particulier de la détectionRaisonnons sur un exempleRéférences

Prétraitements et codage

Classification


Principe

MATHEMATIQUES INFORMATIQUERdF

Traitement d’images

Traitement du signal (parole) Biologie

PhysiqueInstrumentation


• On dispose d’un ensemble de formes dont la classe est

connue (base d’apprentissage ou de références)

• On met au point une méthode qui, en étudiant cette base,

sera ensuite capable de classer des formes inconnues

Principe




Classification


Applications

isolés

cursifsligne de base

Variabilité entre

scripteurs

Reconnaissance de texte


Biométrie

Signature

Empreinte

digitale

Visage

Iris

Empreinte

vocale

Applications


Reconnaissances d’empreintes digitales

http://www.biometrie-online.net/techno/empreintes/empreintes-

digitales.php

Applications


médicale satellitaire

Imagerie

Applications


200 400 600 800 1000 1200 1400 1600 1800 2000

200

400

600

800

1000

1200

1400

200 400 600 800 1000 1200 1400 1600 1800 2000

200

400

600

800

1000

1200

1400

Aide technique

Véhicules intelligents

Analyse de scène

Applications


Signaux audio

Reconnaissance de locuteurs

• Parmi 10 personnes, qui parle ?

Reconnaissance de parole

• Parmi ces 20 mots, lequel la personne a dit ?

Applications


Signaux divers : diagnostic de panne

Sur un avion, il y a plusieurs centaines de

capteurs qui donnent des signaux en

permanence.

Comment faire pour détecter

automatiquement une panne et diagnostiquer

son origine ?

Applications


Champignon

fermé

Champignon

taché

Champignon

véreux

Champignon

terreux

Contrôle de qualité

Applications




Classification


Difficultés

Problème de

résolution

Problème de

pose

Distance entre

visage?


Difficultés

Expressions faciales, occlusion




Classification


Méthode supervisée ou non supervisée

Méthode supervisée :

On reçoit une image binaire

et on doit l’associer à une

des 26 lettres de l’alphabet

On connait à l’avance les

classes possibles. La base

d’apprentissage est

étiquetée avec ces 26

classes

Méthode non supervisée :

Un client vient d’acheter un

livre sur Amazon. Je souhaite

retrouver les personnes avec

les mêmes gouts pour

orienter ce client

On ne connait pas à

l’avance les classes possibles.

La base d’apprentissage est

composée de clients ayant

fait des achats. On souhaite

regrouper les clients ayant les

mêmes gouts dans une

classe




Classification


Cas particulier : la détection

Raisonnons sur un cas concret : comment détecter un visage dans uneimage ?


On change le problème de détection en un problème de classification

On présente une imagette (une zone de l’image) en entrée d’unsystème de reconnaissance. Celui-ci nous dit si cette imagette est unvisage ou non (sortie binaire)

Problème:

Comment savoir où rechercher dans l’image ?

Comment détecter à plusieurs échelles ?

En testant toutes les combinaisons possibles

En chaque position, problème de reconnaissance. Est-ce un visage ou non ?

Cas particulier : la détection




Classification


Reconnaître les truites et les saumons

Exemple


Extraire l’objet de l’image

Pré-traitement

Exemple


Extraire de la forme un vecteur de mesure

aussi appelé vecteur de caractéristiques

ou codage

ou features

Codage

Exemple en 1 dimension : la taille des poissons

Exemple


Taille des poissons

SaumonTruite

Trop de chevauchement, décision pas robuste. Que faire ?

Taille des

poissons

Seuil de décision

Classification

Exemple


Autre caractéristique :

la teinte des poissons

Trop de chevauchement, décision pas robuste. Que faire ?

Seuil de décision

TruiteSaumon

Teinte

Classification

Exemple


Teinte et longueur des poissons Vecteur de caractéristiques à 2 dimensions

On peut ajouter d’autres caractéristiques pour améliorer la classification

Mais les données ne sont pas toujours idéales

frontière de décision

Truite Saumon

Teinte

Longueur

Classification

Exemple


Pourquoi ne pas utiliser une frontière plus complexe ?Quelle sera l’erreur pour de nouveaux poissons ?


Truite Saumon

Teinte

Longueur


Classification

Exemple


Comment trouver une frontière moins spécifique, moins bonne sur l’ensemble d’entrainement mais certainement meilleure sur de

nouveaux poissons ? ?


Truite Saumon

Teinte

Longueur


Classification

Exemple


Espace

de

représentation

Espace

de

décision

Espace

de

mesure

Codage Classification

Les étapes de la reconnaissance de formes




Classification


- DUDA Richard, HART Peter STORK David, "Pattern Classification ". Wiley Sciences, 2nd edition.

- CHRISTOPHER M. BISHOP, “Pattern Recognition and machine learning”, springer, 2006

- BELAID Abdel, BELAID Yolande, "Reconnaissance des formes : Méthodes et

applications". InterEditions, 1992.

- DEVIJVER Pierre, KITTLER J., "Pattern Recognition: a statistical approach". Prentice Hall, 1982.

- DUBUISSON Bernard, "Diagnostic et reconnaissance des formes". Hermes, 1990.

- FU King-Sun, "Syntactic Methods in Pattern Recognition". Academic Press, 1974.

- GAILLAT Gérard, "Méthodes statistiques de reconnaissance des formes". Publication ENSTA, 1983.

- MICLET Laurent, "Méthodes structurelles pour la reconnaissance des formes". Eyrolles et CNET - ENST, 1984.

- MILGRAM Maurice,"Reconnaissance des formes : Méthodes numériques et

connexionnistes". Armand Colin, 1993.

- PAVLIDIS T., "Structural Pattern Recognition". Springer Verlag, 1982.

- SIMON Jean-Claude, "La reconnaissance des formes par algorithmes". Masson, 1984.

- WATANABE Satosi, "Knowing and Guessing". John Wiley, 1969.

Références


Introduction

Prétraitements et codageCaractéristiques des codagesPrétraitements: extraire la formeCodage global vs structurelCodage de régions

Codage rétinienMoments géométriquesFiltres de HaarLocal Binary Patterns (LBP)

Codage de contoursCodage de FreemanHistogramme des orientations de contoursDescripteurs de Fourier

Comment trouver un bon codage ?Problème des grandes dimensionsRappel sur les matrices de covariancesAnalyse en composantes principalesAnalyse discriminante linéaireSélection/extraction de caractéristiques

Classification


ESPACE DE

REPRESENTATION

ESPACE DE

MESURE

Codage



Introduction





Classification


Qu’est ce qu’un bon codage ?

Pouvoir discriminant

Le codage doit être différent pour des exemples de classesdifférentes forte variance inter-classes

Pouvoir unifiant

Le codage doit être à peu près le même pour tous lesexemples d’une même classe faible variance intra-classe

Stabilité/invariance

Codage le plus insensible possible au bruit

En fonction des applications, invariance en translation,rotation, changement d’échelle

Faible dimension

Plus le codage est de faible dimension, plus les temps decalcul seront faibles

Augmenter la dimension peut détériorer les résultats dereconnaissance (malédiction des grandes dimensioncompromis à trouver)

Caractéristique des codages


Introduction




Comment trouver un bon codage ?Problème des grandes dimensionsRappel sur les matrices de covariances

Analyse en composantes principalesAnalyse discriminante linéaireSélection/extraction de caractéristiques

Classification


Paradoxe

Il faut segmenter pour reconnaître et … reconnaître pour segmenter

Prétraitement

Exemple : isoler les lettres

But : isoler la forme à reconnaître


A vous de jouer, on fait comment ?

Prétraitement


Segmentation

Projection selon y segmentation en lignes

Prétraitement


Projection selon x segmentation en lettres

Prétraitement


Introduction




Comment trouver un bon codage ?Problème des grandes dimensionsRappel sur les matrices de covariances

Analyse en composantes principalesAnalyse discriminante linéaireSélection/extraction de caractéristiques

Classification


Codage global

On code toute la forme sans en extraire d’éléments spécifiques. La

forme peut être représentée par un vecteur de paramètres

Exemple pour une personne : le poids et la taille

Codage structurel

On extrait des éléments spécifiques de la forme et leur relation.

Exemple :

pour la personne 1 : pull rouge au dessus d’un pantalon bleu au

dessus de chaussures noires

Pour reconnaitre un ‘L’ : contour d’abord vertical puis horizontal

Codage global vs structurel


Introduction



Codage de contoursCodage de Freeman

Histogramme des orientations de contoursDescripteurs de Fourier

Comment trouver un bon codage ?Problème des grandes dimensionsRappel sur les matrices de covariancesAnalyse en composantes principales

Analyse discriminante linéaireSélection/extraction de caractéristiques

Classification


Codage rétinien

On garde toute l’information directement dans une rétine :

Problème :

-La lettre n’est pas toujours à la même position

-La résolution de l’image n’est pas toujours la même


Codage rétinien

-Calcul du centre de gravité

-Sélection du plus petit carré centré en G et englobant tous les pixels

-Réduction de la dimension (attention, pas binaire !!)

Rétine 10x10

après centrage

et réduction

Vecteur de

caractéristique

s de dimension

100


Codage quasiment neutre

Pas de perte d’information

Laisse le classifieur travailler

Efficace si base d’exemples importante

Ne tolère ni les transformations ni les déformations

Codage rétinien


Introduction





Classification


Ils codent n’importe quelle forme, même non binaire

Soit I(x,y) une image

Moment d’ordre p,q

Aire :

Centre de masse :

00 ( , )x y

M I x y

01 10( , ) ( , )q p

x y x y

M y I x y M x I x y

( , )p q

pq

x y

M x y I x y

10 01

00 00

M Mx et y

M M

Moments géométriques


Orientation:

Moments centrés pour être invariant en translation

Moments normalisés pour être invariant en changement d’échelle

( ) ( ) ( , )p q

pq

x y

x x y y I x y

11

20 02

1 2arctan( )

2

M

M M



Moments invariants en rotation : Moment de Hu

1 20 02

22

2 20 02 11( ) 4

2 2

3 30 12 21 03( 3 ) (3 )

2 2

4 30 12 21 03( ) ( )

2 2

6 20 02 30 12 21 03 11 30 12 21 03( ) ( ) ( ) 4 ( )( )

2 2 2 2

7 21 03 30 12 30 12 21 03 30 12 21 03 30 12 21 03(3 3 )( ) ( ) 3( ) ( 3 )( ) 3( ) ( )

2 2 2 2

5 30 12 30 12 30 12 21 03 21 03 21 03 30 12 21 03( 3 )( ) ( ) 3( ) (3 )( ) 3( ) ( )



Introduction

Prétraitements et codageCaractéristiques des codages

Prétraitements: extraire la formeCodage global vs structurelCodage de régions

Codage rétinienMoments géométriquesFiltres de Haar

Local Binary Patterns (LBP)Codage de contours

Codage de FreemanHistogramme des orientations de contoursDescripteurs de Fourier


Classification


Filtres de Haar

Plusieurs filtres à plusieurs échelles, plusieursorientations, estimés en plusieurs positions del’image.

On ne peu pas utiliser toutes ces valeurs, lecodage serait bien trop grand (plusieursdizaines d’images !


moyenne pour

plusieurs images

Filtres de Haar

En faisant des statistiques sur plusieursmilliers d’images d’une même classe, ondétermine quelles sont les tailles,orientations et positions pertinents pourfaire le codage.


On en déduit, sur une grande base de données (apprentissage) quels sont les

filtres à utiliser et où.

Le code de l’image (vecteur de caractéristiques) est composé de la sortie de

tous ces filtres locaux

Filtres de Haar

Vecteur de caractéristiques


Même chose pour un visage

Un visage est représenté par la

réponse de plusieurs filtres en

différentes positions

Filtres de Haar


Introduction


Codage rétinien

Moments géométriquesFiltres de HaarLocal Binary Patterns (LBP)



Classification


Idée : obtenir un descripteur complètement invariant à l’éclairage

Solution : codage des relations d’ordre

Comparaison du niveau de gris d’un point avec ses voisins

Chaque comparaison renvoie un nombre binaire

Le mot binaire obtenu avec les 8 voisins est codé en décimal

L’histogramme de cette valeur pour tous les points d’une zone forme le

descripteur

Exemple

Une portion d’image :

un pixel et ses 8 voisins Le résultat de comparaison Le code binaire

Local Binary Patterns (LBP)

1*20+

1*21 +

1*22 +

1*23 +

0*24 + = 15

0*25 +

0*26 +

0*27 +

20

21

22

23

24

25

26

2+


Introduction

Prétraitements et codageCaractéristiques des codagesPrétraitements: extraire la formeCodage global vs structurel

Codage de régionsCodage rétinienMoments géométriquesFiltres de HaarLocal Binary Patterns (LBP)



Classification


On code les contours à partir d’une liste chainée d’angles discrétisés

Exemple :

2 3 4 4 5 6 6 7 0 0 1 2

0

1

2

3

4

5

6

7

Codage des contours de freeman


Quels sont les descripteurs obtenus pour ces deux images

avec un code de Freeman à 8 états?

A quoi ce codage est invariant ?

Peut-on le rendre plus invariant ?

Codage de Freeman

http://images.google.fr/imgres?imgurl=http://fr.dreamstime.com/chercheur-thumb1847315.jpg&imgrefurl=http://fr.dreamstime.com/searcher-image1847315&usg=__Ef8yZ0KwV6-G4Gmatmqunt7Axs4=&h=300&w=300&sz=33&hl=fr&start=16&um=1&tbnid=bIbri2vDWii35M:&tbnh=116&tbnw=116&prev=/images?q=chercheur&hl=fr&rlz=1T4GFRC_frFR316FR316&sa=N&um=1

http://images.google.fr/imgres?imgurl=http://fr.dreamstime.com/chercheur-thumb1847315.jpg&imgrefurl=http://fr.dreamstime.com/searcher-image1847315&usg=__Ef8yZ0KwV6-G4Gmatmqunt7Axs4=&h=300&w=300&sz=33&hl=fr&start=16&um=1&tbnid=bIbri2vDWii35M:&tbnh=116&tbnw=116&prev=/images?q=chercheur&hl=fr&rlz=1T4GFRC_frFR316FR316&sa=N&um=1


Introduction





Classification


Histogrammes des orientations de gradients

On peut observer les probabilités des orientations du gradient dans

différentes zones de l’image

Pour un piéton :

I |Ix| |Iy|


atan 0,Gy

Gx

Plusieurs étapes:- Calcul des gradients horizontaux et verticaux Gx et Gy avec

[-1 0 1] et [-1 0 1]T

- Calcul de l’orientation du gradient

-Construction de l’histogramme d’orientation de gradient pour différentes

zones (souvent 8 bins)

-Concaténation des différents histogrammes

-Variante : pondération des votes par l’amplitude du gradient

Histogrammes des orientations de gradients


Introduction





Classification


Descripteurs de Fourier

Le contour est décrit par la liste chaînée des points qui le constitue. Les

coordonnées {xi,yi} des points de cette liste sont transformées en un

complexe ui=xi+jyi

u0=x0+jy0


TFD de la liste de points :

La majorité des informations est contenue dans les basses fréquences

les premières valeurs de an suffisent à caractériser le signal et

composent le vecteur de caractéristiques

Propriétés:

Translation : modification de a0 seulement

Rotation : modification de la phase

Changement d’échelle : multiplication des an par une constante

2j ni

Nn i

i

a u e

Descripteurs de Fourier


Introduction





Classification


Méthodes empiriques

Choix des caractéristiques pertinentes

Méthodes exploratoires

Algorithmes génétiques

Méthodes statistiques pour réduire la dimension ou la

taille des données

Analyse en composantes principales

Analyse discriminante linéaire

Sélection/extraction de caractéristiques

Comment trouver un bon codage ?


Introduction





Classification


La dimension des données n est la dimension du code les représentant

Ex : n = 100

Complexité algorithmique linéaire f(n2) ou f(n3) ou même,

exponentielle

Rétine 10 X 10:

(après centrage

et réduction)

Problème des grandes dimensions


Plus la dimension n est grande, plus la base de données devra être de grande

dimension

Ex : avec deux exemples par dimension

Si n = 2, 22=4 données

Si n = 3, 23=8 données

Si n = 4 , 24=16 données

Si n = 20, 220=1.048.576 données

Considérons un nombre fixé N de points uniformément répartis dans un hyper-

cube de dimension n.

Plus n augmente, plus la variance des distances entre points diminue

En grande dimension, le voisinage immédiat d'une donnée est très peu

occupé tandis que la plupart des autres données se trouvent à des distances

très comparables de cette dernière.

D'une manière générale, les distances entre données de grande dimension

sont très concentrées autour de leur moyenne.

Problème des grandes dimensions


Introduction





Classification


Si on dispose de N vecteurs de données Xi de dimension n, leur matrice de covariance

est estimée par :

Σ =1

𝑁−1 𝑖=1𝑁−1 𝑋𝑖 − 𝜇 𝑋𝑖 − 𝜇 𝑇 où 𝜇 est le vecteur moyen des données Xi

La matrice de covariance est de dimension n x n et est symétrique.

Exemple en dimension 2

On peut représenter chaque point Xi dans le plan.

La matrice de covariance est de dimension 2x2

Σ =𝜎𝑥𝑥 𝜎𝑥𝑦𝜎𝑥𝑦 𝜎𝑦𝑦

Rappel sur les matrices de covariance

Matrice de covariance

La matrice de covariance est symétrique. Ses

valeurs codent la forme du nuage de point.


1.01 -0.01

-0.01 0.99

1 -0.02

-0.02 9.46

1 3

3 9

Démo

Bayes 2D

Rappel sur les matrices de covariance

Matrice de covariance


Introduction





Classification


Supposons que l’on dispose de plusieurs exemples (N exemples) dont

le vecteur de caractéristiques est de dimension élevée (n).

Garder toutes ces dimensions est très couteux en temps de calcul et

met à mal certains algorithmes de classification sujet au phénomène

de malédiction des grandes dimensions.

On souhaite réduire la dimension du vecteur de caractéristiques

pour qu’il n’ait plus qu’une dimension d<<n

Comment faire ?

Dans un premier temps, il va falloir prétraiter les données.



Prétraitement des données

Les données Xj sont rangées dans un tableau X

(N=4 exemples de dimension n=5)

Mesure 1 Mesure 2 Mesure 3 Mesure 4 Mesure 5

Donnée 1

Donnée 2

Donnée 3

Donnée 4

Le tableau contient des informations de natures différentes.

Il est nécessaire de centrer les données : on soustrait la valeur de la moyenne de la colonne à chaque valeur. La nouvelle moyenne de la

colonne va être 0.

Il est aussi nécessaire de normaliser les données : on divise chaque valeur par l'écart type de sa colonne. Le nouvel écart type de la

colonne va être 1.



L’idée va être de changer le système d’axe de manière à ce que le

maximum d'informations soit contenu sur les premiers axes.

Exemple : pour des données en dimension deux (x1,x2) dans le repère

(i1,i2), l’ACP va donner un nouveau repère (u1,u2) tel que le maximum

d’information soit porté par u1. u1 correspondra à l’élongation maximaledu nuage de point. Les nouvelles coordonnées des points seront (y1,y2)

et la réduction de dimension consistera à ne garder que y1.

Axe principal


i1

i2 u1u2



De manière plus formelle, chaque point 𝑋𝑖 s’exprime dans le repère initial

par:𝑋𝑖 = 𝑥𝑖1𝑖1+𝑥𝑖2𝑖2+…+𝑥𝑖𝑛𝑖𝑛

Et est représentée sous forme vectorielle:

𝑋𝑖 =

𝑥𝑖1⋮

𝑥𝑖𝑛L’ACP consiste à rechercher dans un premier temps l’axe 𝑢1 tq la

projection des données sur cet axe maximise la variance des données.

La projection des données sur l’axe 𝑢1 donne la nouvelle coordonnée des

points:

𝑦𝑖1 = 𝑋𝑖𝑇𝑢1 et 𝑢1

𝑇𝑢1 = 1

Et la variance des données sur cet axe sera:

𝜎 =1

𝑁

𝑖=1

𝑁

𝑦𝑖12=

1

𝑁

𝑖=1

𝑁

𝑦𝑖1𝑇𝑦𝑖1 =

1

𝑁

𝑖=1

𝑁

𝑢1𝑇𝑋𝑖𝑋𝑖

𝑇𝑢1

𝜎 = 𝑢1𝑇 Σ 𝑢1 et 𝑢1

𝑇𝑢1 = 1

Où Σ est la matrice de covariance des données tq Σ =1

𝑁 𝑖=1𝑁 𝑋𝑖𝑋𝑖

𝑇



Il s’agit d’un problème classique de maximisation sous contrainte que l’on

résout à partir du lagrangien:

L=𝑢1𝑇 Σ 𝑢1 - 𝜆 𝑢1

𝑇 𝑢1− 1

En annulant la dérivée de L par rapport à 𝑢1, on obtient:𝜕𝐿

𝜕𝑢1= 0 Σ 𝑢1= 𝜆 𝑢1

On reconnait l’équation des valeurs propres et des vecteurs propres de la

matrice de covariance Σ.

Le second axe correspondra au second vecteur propre de la matrice,…

Rmq:

La matrice de covariance est par construction symétrique et au moins

positive semi-définie. Ceci implique que les valeurs propres et les vecteurs

propres seront réels, que les valeurs propres seront positives ou nulles et que

les vecteurs propres seront orthogonaux entre eux.


Chaque donnée Xi peut s’exprimer dans la base des vecteurs propres:

Xi= yi1 u1 + yi2 u2 + ….+yin un

Avec yi1=XiT. u1 (y1 scalaire)

Et sera représentée par le nouveau vecteur:

𝑋𝑖 =

𝑦𝑖1⋮

𝑦𝑖𝑛

La réduction de dimension consiste à ne garder que les première

composantes de ce vecteur pour représenter Xi:

𝑋𝑖 =

𝑦𝑖1⋮

𝑦𝑖𝑑avec d << n

1 2

1 2 3

... avec

...d

n

d n

On définit l’inertie portée par les d premiers axes par



Comment connaître le nombre d’axes à conserver ?

1. Avec un pourcentage d’inertie souhaité a priori

2. On divise l’inertie totale par la dimension initiale pour connaître l’inertie

moyenne par variable. On conserve tous les axes ayant une inertie

supérieure à cette moyenne

3. On observe l’évolution des valeurs propres:

4. Par validation sur une base de validation



Exemples d’ACP sur des images de visages

On dispose d’une base de références de 270 visages,

Chaque visage a pour dimension 38x38=1444 pixels n=1444

On range tous ces visages dans une matrice de dimension 270x1444.

Chaque visage est considéré comme un exemple de dimension 1444.

On prétraite les données puis on calcule la matrice de covariance de

cette grosse matrice. Elle est de dimension 1444x1444.

On calcule les valeurs propres et les vecteurs propres de cette matrice.

Chaque vecteur propre a pour dimension 1x1444. On peut remettre

chacun d’eux sous la forme d’une matrice de dimension 38*38.

Les 5 premiers vecteurs propres (eigen image) :



Si on ne conserve que ces 5 dimensions, chaque visage Xj de la base

s’exprime comme une combinaison linéaire de ces 5 ‘eigen-image’

Xi= yi1 u1 + yi2 u2 + yi3 u3 + yi4 u4 + yi5 u5

Ainsi, tous les exemples ne seront plus représentés que par un vecteur de

dimension 5.

A partir de ce vecteur, on peut :

Reconstruire les visages, on aura alors fait de la compression

Reconnaitre les visages



Reconstruction avec 5 ‘eigen images’

Compression = 288%


Compression = 32%


Compression = 10%



Démo

acp

Démo

Acp_visage \ACP_VISAGE\ACP_face

Eigen_image

Problème de l’ACP (voir démo)



Introduction





Classification


Analyse discriminante linéaire.

Cette méthode tient compte de la répartition des points dans les

classes et essaye de maximiser le ratio entre la variance

inter classe des données et la variance intra classe.

Supposons que l’on ait un problème à K classes, et les

ensembles de points X1 et X2… XN correspondant, et

X={Xi} i=1…N

moyenne de chaque ensemble de points et moyenne

totale :

1, 2, …, K,

= p1*1 + p2*2+…+ pK*K

Où p1, p2,… pK sont les probabilités de chaque classe



Analyse discriminante linéaire.

Dispersion intra classe:

intra=p1* 1 + p2* 2+…+ + pK* K

où 1, 2,… K sont les matrices de covariance des classes

Dispersion inter classe

inter = p1(1-) (1-)T + p2(2-) (2-)T+…+ pK(K-) (K-)T

On recherche l’axe 𝑢1 tel que la projection des données sur cet axe

maximise le rapport entre la variance inter classe et la variance intra

classe.

La projection des points Xi selon le vecteur 𝑢1 s’exprime par :

𝑦𝑖1 = 𝑋𝑖𝑇𝑢1 et 𝑢1

𝑇𝑢1 = 1

Si la matrice de covariance des données de départ est

=E{XiT Xi}

dans le nouveau repère, on a

new = E{𝑦𝑖1𝑇 𝑦𝑖1 }=𝑢1

𝑇Σ 𝑢1



On recherche l’axe qui maximise le rapport entre la variance inter classe

et la variance intra classe et donc :

𝑢1𝑇Σ𝑖𝑛𝑡𝑒𝑟 𝑢1

𝑢1𝑇Σ𝑖𝑛𝑡𝑟𝑎𝑢1

Ceci revient à maximiser 𝑢1𝑇Σ𝑖𝑛𝑡𝑒𝑟 𝑢1 sous la contrainte 𝑢1

𝑇Σ𝑖𝑛𝑡𝑟𝑎𝑢1 = 1 (car

peu importe la norme de 𝑢1)

Pour cela, on forme le lagrangien dont on annule la dérivée:L=𝑢1

𝑇Σ𝑖𝑛𝑡𝑒𝑟 𝑢1 − 𝜆 𝑢1𝑇Σ𝑖𝑛𝑡𝑟𝑎𝑢1 − 1

𝜕𝐿

𝜕𝑢1= 0 Σ𝑖𝑛𝑡𝑒𝑟 𝑢1= 𝜆Σ𝑖𝑛𝑡𝑟𝑎𝑢1 Σ𝑖𝑛𝑡𝑟𝑎

−1 Σ𝑖𝑛𝑡𝑒𝑟 𝑢1= 𝜆𝑢1

On se ramène de nouveau à un problème aux valeurs/vecteurs propres

et on choisit pour 𝑢1 le premier vecteur propre de Σ𝑖𝑛𝑡𝑟𝑎−1 Σ𝑖𝑛𝑡𝑒𝑟.

Les autres axes de projection correspondent aux autres vecteurs propres

de Σ𝑖𝑛𝑡𝑟𝑎−1 Σ𝑖𝑛𝑡𝑒𝑟



De la même manière que l’ACP, on garde les axes

correspondant aux d premiers vecteurs propres de Σ𝑖𝑛𝑡𝑟𝑎−1 Σ𝑖𝑛𝑡𝑒𝑟

qui correspondent aux d plus grandes valeurs propres.

Avantage et inconvénient dans démo

Démo

lda



Introduction





Classification


Les méthodes de sélection de caractéristiques peuvent

être classées en trois catégories principales :

• Filter

• Wrapper

• Embedded



Les méthodes filter travaillent en amont de la classification : on étudie les n dimensions (ou caractéristiques) et on en sélectionne

d en fonction d’un critère donné.

Par exemple, on garde les caractéristiques qui ont la plus forte

corrélation possible avec les étiquettes.


x1

x2

x3

⁞

⁞

⁞

⁞

xn

Filter

x3

x5

x9

⁞

x40

classifieur

n caractéristiques

d caractéristiques

d<<n



Avantage des méthodes de type filter• efficacité calculatoire

Inconvénient des méthodes de type filter

• ne tiennent pas compte des interactions entre caractéristiques et

tendent a sélectionner des caractéristiques redondantes plutôt que

complémentaires.

• ne tiennent pas compte de la performance des méthodes de

classification


Les méthodes wrapper évaluent un sous-ensemble de

caractéristiques par sa performance de classification en utilisant

un algorithme d'apprentissage

La complexité de l'algorithme d'apprentissage rend les méthodes

"wrapper" très coûteuses en temps de calcul stratégie de

recherche exhaustive impossible


x1

x2

x3

⁞

⁞

⁞

⁞

xn

x3

x5

x9

⁞

x40

classifieur

n caractéristiques

d caractéristiques

d<<n

Wrapper

Algo de

recherche

classification



Exemple :on commence par un ensemble vide de caractéristiques.

A chaque itération, la meilleure caractéristique parmi celles qui restent

est sélectionnée

Avantage des méthodes de type wrapperCapable de sélectionner des sous-ensembles de caractéristiques de

petite taille qui sont performants pour le classificateur

Inconvénient des méthodes de type filter

• Très longues en temps de calcul car beaucoup d’apprentissages

nécessaires pour sélectionner le bon sous-ensemble de

caractéristiques

• Sous-ensemble dépendant du classificateur choisi


Les méthodes Embedded ou intégrées incorporent la sélection de variables lors du processus d'apprentissage (boosting, arbre de

décision),

Ces méthodes seront vues dans la suite du cours



Introduction

Prétraitements et Codage

ClassificationIntroduction

Définition

Généralisation

Rappel sur les probabilités

Estimation des probabilités

Qualité de la base de données

Performance d’un classificateur

Méthodes de classification génératives/discriminatives

Méthode de régression


ESPACE DE

DECISION

ESPACE DE

REPRESENTATION

Reconnaissance des formes

et apprentissage

Introduction


Classifier - Estimer

=

associer une classe C ou une valeur

à un vecteur de caractéristiques X=[x1, x2,… xn ] de dimension n

Vecteur de caractéristique X = forme + variabilité + bruit de mesure

Introduction


Connaissances disponibles

Informations fournies par un « expert »

Modèles explicites (méthode structurelle)

Cas le plus général : base de données étiquetées ou non

Introduction


Introduction



Définition

Généralisation








Condition requise

Bonne généralisation :

Capacité du classificateur/estimateur à reconnaître/estimer des

exemples qu’il n’a pas appris

Ne pas apprendre par cœur…

Généralisation


Bonne généralisation, où est la frontière ?

Généralisation


Introduction




Probabilité, probabilités jointes, probabilités conditionnelles

Règle de Bayes







Il existe deux types de probabilités

Probabilités discrètes : A est un événement

0 < P(A) < 1

p(A) + p(B) + p(C) + … + p(Z) = 1

p(AB)= p(A|B)*p(B) (probabilité conditionnelle)

Probabilités continues (densité de probabilité) :

Ne sont pas majorées par 1 (mais l’aire vaut 1)

Intégrale au lieu d’une somme

Rappels sur les probabilités


Probabilités jointes

Pour 2 variables x et y, certaines instances de ces

deux variables sont plus fréquentes que d’autres.

Cette information est donnée par la densité de probabilité jointe de x et y : P(x,y)

yx

010

2030

4050

0

20

40

600

0.5

1

1.5

2

x 10-3

x

x

x

y

y

y



Marginalisation

On peut retrouver la densité de probabilité d’une

seule variable à partir de la densité de probabilité

jointe par intégration.

Pour les variables continues,

Pour les variables discrètes,



Probabilités Conditionnelles

P(x/y=y*) : probabilité de x sachant que y vaut y*

Cette probabilité conditionnelle peut être estimée

à partir des probabilités jointes :

x

y

y1

y2

P(x/y=y1)

P(x/y=y2)



Probabilités Conditionnelles

P(x/y=y*) : probabilité de x sachant que y vaut y*

Cette probabilité conditionnelle peut être estimée

à partir des probabilités jointes :

Souvent, on ne spécifie pas la valeur de y* et:

Ceci peut être étendu avec plus de variables :



Indépendance

Si les variables x et y sont indépendantes, alors



Introduction




Probabilité, probabilités jointes, probabilités conditionnelles

Règle de Bayes







Les équations précédentes nous conduisent à :

Qui peut se mettre sous la forme :

Pb : comment estimer des probabilités

connaissant des échantillons ?

Règle de Bayes


Introduction





Introduction

Estimation non paramétriques des probabilités

Histogrammes

Estimation par noyaux

Estimation paramétrique des probabilités

Estimation du maximum de vraisemblance

Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale

Mixture de gaussiennes, algorithme E.M






Connaissant un ensemble de N échantillons 𝑥𝑖 générés selon la loi

de probabilité 𝑝(𝑥), comment estimer la densité de probabilité

𝑝(𝑥) ?

Il existe deux grands types d’approches :

• les méthodes non paramétriques

• les méthodes paramétriques (la loi est fixée a priori et on en

recherche les paramètres)



Introduction





Introduction


Histogrammes




Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale







Histogramme (non paramétrique)

Une des méthodes les plus simples consiste à estimer

l’histogramme de l’ensemble de données.

• On divise chaque dimension en cases (bins) de largeur 𝒉• On compte le nombre d’échantillons 𝑥𝑖 par case

Estimation non paramétrique



Pb:

- le choix de l’origine peut changer l’estimation de 𝑝(𝑥)- Comment choisir ℎ ?

Image issue de Pattern Recognition and machine learning – M. Bishop - 2007


𝒑(𝒙) réel

𝒑(𝒙) estimé



En deux dimensions

On peut reprendre la même formulation que précédemment

étendue à une dimension 2 puis 𝑛 dans le cas général,




Problème de l’origine

Problème du choix de h (discrétisation)

Problème des grandes dimensions pour les estimations nonparamétriques

Supposons que l’on ait des données de dimension 20 et que

chaque dimension puisse prendre 5 valeurs, L’histogrammeaura en tout 520=9.1013 cases.

Il faudra une base de donnée énorme pour estimer

correctement 𝑝 𝑥 . Si la dimension est plus grande, le

problème devient encore plus difficile


Introduction





Introduction


Histogrammes




Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale







Estimation par noyau (non paramétrique)


Pour remédier au problème de l’origine,

𝑝 𝑥 =𝑛𝑜𝑚𝑏𝑟𝑒 𝑑′é𝑐ℎ𝑎𝑛𝑡𝑖𝑙𝑙𝑜𝑛𝑠 𝑑𝑎𝑛𝑠 [𝑥 − ℎ, 𝑥 + ℎ]

𝑁2ℎ

Où N est le nombre d’échantillons total

Ceci s’exprime mathématiquement en 1D par :

𝑝 𝑥 =1

𝑁2ℎ

𝑖=1

𝑁

𝐾𝑥 − 𝑥𝑖

ℎ

Avec 𝐾 𝑢 = 1 𝑠𝑖 𝑢 < 10 𝑠𝑖𝑛𝑜𝑛

Ceci revient à compter le nombre d’échantillons tombant dans

un hyper-cube de largeur ℎ centré en 𝑥Cette estimation est continue, elle est faite pour tout x


Kernel Density Estimation (non paramétrique)

Pour remédier aux discontinuités liées à la discrétisation : fenêtres de

Parzen. On estime toujours la densité de probabilité avec:

𝑝 𝑥 =1

𝑁ℎ

𝑖=1

𝑁

𝐾𝑥 − 𝑥𝑖

ℎ

Mais K() peut être un noyau quelconque,

Exemple avec un noyau gaussien en 2D :

𝑝 𝑥 =1

𝑁

𝑖=1

𝑁1

2𝜋 1/2ℎ𝑒𝑥𝑝 −

𝑥 − 𝑥𝑖2

2ℎ2

Ceci revient à placer une gaussienne autour de chaque point et à

sommer leur contribution



Kernel Density Estimation (non paramétrique)

Estimation de la densité de probabilité sur les mêmes données

que pour l’histogramme

- h trop petit estimation très bruitée

- h trop grand estimation trop lisse

Image issue de Pattern Recognition and machine learning – M. Bishop - 2007


𝒑(𝒙) réel

𝒑(𝒙) estimé

Démo

Parzen.m


Introduction





Introduction


Histogrammes




Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale







Estimation paramétrique

On souhaite comme précédemment estimer la densité de

probabilité 𝑝 𝑥 à partir d’une réalisation de N échantillons,

Le problème est très difficile quand on a un faible nombre

d’échantillons de dimension élevée.

La difficulté du problème est réduite si on connait a priori une

forme paramétrique de la loi. Dans ce cas, il n’y a plus qu’à

estimer les paramètres de la loi.

Ce problème est soluble par l’estimation du maximum de

vraisemblance.


Introduction





Introduction


Histogrammes




Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale




Méthodes de classificationgénératives/discriminatives





(Estimation paramétrique)

Nous disposons de N échantillons 𝑥𝑖 tirés à partir de la loi

𝑝 𝑥 . D’autre part, 𝑝 𝑥 a une forme connue, dépendant de

paramètres 𝜃 : 𝑝 𝑥 = 𝑓(𝑥, 𝜃)

Nous recherchons les paramètres 𝜃 qui maximise la

vraisemblance des observations définie par:

𝐿 𝜃 𝑥 =

𝑖=1

𝑁

𝑝(𝑥𝑖) =

𝑖=1

𝑁

𝑓(𝑥𝑖 , 𝜃)

Il est souvent plus simple de travailler avec le logarithme de

cette vraisemblance appelée log-vraisemblance:

𝑙 𝜃 𝑥 = 𝑙𝑛

𝑖=1

𝑁

𝑝(𝑥𝑖) =

𝑖=1

𝑁

𝑙𝑛 𝑝(𝑥𝑖) =

𝑖=1

𝑁

ln(𝑓 𝑥𝑖 , 𝜃 )




(Estimation paramétrique)

Si 𝜃 = 𝜃1, 𝜃2, … , 𝜃𝑝Test un vecteur de dimension p et que △𝜃=

𝜕

𝜕𝜃1, … ,

𝜕

𝜕𝜃𝑝

𝑇

est l’opérateur gradient, l’estimation de 𝜃 est telle

que:

△𝜃 𝑙 = 0

L’estimation du maximum de vraisemblance consiste ainsi à

- Définir la vraisemblance : 𝐿 𝜃 𝑥 = 𝑖=1𝑁 𝑓(𝑥𝑖 , 𝜃)

- Estimer 𝜃 tq : 𝜃 = max𝜃

𝐿 𝜃 𝑥


Introduction





Introduction


Histogrammes




Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale







Loi de Bernouilli (estimation paramétrique)

Si 𝑥 est une variable binaire, alors

𝐵𝑒𝑟𝑛 𝑥 = 1 = 𝜇 et 𝐵𝑒𝑟𝑛 𝑥 = 0 = 1 − 𝜇

Ou encore

𝐵𝑒𝑟𝑛 𝑥 = 𝜇𝑥(1 − 𝜇) 1−𝑥

On montre que :

𝔼 𝑥 = 𝜇 et 𝑣𝑎𝑟 𝑥 = 𝜇(1 − 𝜇)

Et, avec l’estimation du maximum de vraisemblance:

𝜇 =1

𝑁

𝑖=1

𝑁

𝑥𝑖

Ces résultats peuvent être retrouvés par le calcul



Introduction





Introduction


Histogrammes




Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale







Loi binomiale (estimation paramétrique)

Supposons que l’on tire 𝑁 échantillons binaires selon la

loi de Bernouilli. La variable aléatoire 𝑥 qui compte le

nombre de réalisations de 1 parmi ces 𝑁 échantillons

suit une loi binomiale de paramètres 𝑁 et 𝜆 .

𝑥 peut donc prendre toutes les valeurs entières de 0 à

𝑁 et

𝑝 𝑥 =𝑁!

𝑁 − 𝑥 ! 𝑥!𝜆𝑥(1 − 𝜆)𝑛−𝑥

On montre alors que :

𝔼 𝑥 = Nλ et 𝑣𝑎𝑟 𝑥 = 𝑁𝜆 1 − 𝜆

Ces résultats peuvent être retrouvés par le calcul


.


Introduction





Introduction


Histogrammes




Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale







Loi uniforme (estimation paramétrique)

La variable aléatoire continue 𝑥 suit une loi uniforme

sur l’intervalle [a,b] si:

𝑝 𝑥 =1

𝑏 − 𝑎

On a alors

𝔼 𝑥 =𝑏−𝑎

2et 𝑣𝑎𝑟 𝑥 =

𝑏−𝑎 2

12


.


Introduction





Introduction


Histogrammes




Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale







Loi normale mono variable (estimation paramétrique)

Elle est définie par :

𝑝 𝑥 = 𝒩( 𝑥 𝜇, 𝜎) =1

2𝜋𝜎𝑒−

𝑥−𝜇 2

2𝜎2

Et : 𝔼 𝑥 = 𝜇 et 𝑣𝑎𝑟 𝑥 = 𝜎2

L’estimation du maximum de vraisemblance conduit à:

𝜇 =1

𝑁 𝑖=1𝑁 𝑥𝑖 et 𝜎2 =

1

𝑁 𝑖=1𝑁 𝑥𝑖 − 𝜇 2



Loi normale multi variables (estimation paramétrique)

Pour des données x de dimension n , elle est définie par :

𝑝 𝑥 = 𝒩( 𝑥 𝜇, Σ) =1

2𝜋 𝑛/2 Σ 1/2𝑒−

12

2𝑥−𝜇 𝑇Σ−1 𝑥−𝜇

Où 𝜇 est un vecteur de dimension 𝑛 et Σ une matrice de dimension 𝑛x 𝑛.

On a alors :

𝔼 𝑥 = 𝜇 et cov 𝑥 = 𝔼 𝑥 − 𝔼 𝑥 𝑥 − 𝔼 𝑥 𝑇 = Σ

L’estimation du maximum de vraisemblance conduit à:

𝜇 =1

𝑁 𝑖=1𝑁 𝑥𝑖 et Σ =

1

𝑁 𝑖=1𝑁 𝑥𝑖 − 𝜇 𝑥𝑖 − 𝜇 𝑇

Σ est la matrice de covariance. Mais que représente-t-elle











Introduction





Introduction


Histogrammes




Loi de Bernouilli

Loi binomiale

Loi uniforme

Loi normale







Mixture de gaussiennes (estimation paramétrique)

Centaines densités de probabilités ne peuvent pas

être modélisées par une gaussienne. On peut alors

utiliser une mixture de gaussiennes (somme

pondérée de gaussiennes)

Images issue de Pattern Recognition and machine learning – M. Bishop - 2007




De manière plus formelle,

𝑝 𝑥 = 𝑘=1𝐾 𝜋𝑘 𝒩( 𝑥 𝜇𝑘 , Σ𝑘 )

Avec 0 ≤ 𝜋𝑘 ≤ 1 et 𝑘=1𝐾 𝜋𝑘 = 1

Mais comment, à partir d’un ensemble d’échantillons générés à

partir de , 𝑝 𝑥 estimer les paramètres 𝜋𝑘 , 𝜇𝑘 𝑒𝑡 Σ𝑘?

Habituellement, on utilise le maximum de vraisemblance. Ici,

cette méthode n’aboutit pas à une formulation analytique on

utilise une approche numérique appelée ‘Expectation

Maximization’ ou ‘EM’




Idée : ajouter une variable cachée ℎ𝒊𝒌 (non observable) précisant la

probabilité d’appartenance de l’exemple 𝒙𝒊 à la gaussienne 𝒌.

Initialisation : Initialiser de manière aléatoire les paramètres 𝜋𝑘 , 𝜇𝑘 𝑒𝑡 Σ𝑘

Étape E : On utilise les paramètres courants des gaussiennes pour

estimer l’appartenance de chaque exemple 𝑥𝑖 à chaque

gaussienne 𝐺𝑘 :

ℎ𝑖𝑘 =𝒩( 𝑥𝑖 𝜇𝑘 , Σ𝑘 )𝜋𝑘

𝑗𝒩( 𝑥𝑖 𝜇𝑗 , Σ𝑗 )𝜋𝑗

Étape M : connaissant la variable cachée (appartenance), ré-estimer les paramètres du modèle afin de maximiser lavraisemblance:

𝜇 𝑘 = 𝑖 ℎ𝑖𝑘𝑥𝑖

𝑖 ℎ𝑖𝑘Σ 𝑘 =

𝑖 ℎ𝑖𝑘 𝑥𝑖−𝜇𝑘 𝑥𝑖−𝜇𝑘𝑇

𝑖 ℎ𝑖𝑘𝜋 𝑘 = 𝑖 ℎ𝑖𝑘 et 𝑘 𝜋 𝑘 = 1

Itérer E+M jusqu’à convergenceDémo

EMclassique.m




Comment déterminer le nombre de gaussiennes

On va rechercher à avoir une vraisemblance très grande :

𝐿 𝜃 𝑥 =

𝑖=1

𝑁

𝑝(𝑥𝑖) =

𝑖=1

𝑁

𝑘=1

𝐾

𝜋𝑘 𝒩( 𝑥 𝜇𝑘 , Σ𝑘 )

Problème :

Plus il y aura de gaussiennes, plus la vraisemblance sera grande

Pénalisation par la complexité (nombre de gaussiennes 𝑲)

Plus il y aura de données (𝑵 ), plus on peut se permettre degaussiennes

Bayesian Information Criterion (BIC) à minimiser :

𝐵𝐼𝐶 𝐾 = − ln 𝐿 𝜃 𝑥 +𝐾

2ln(N)



Critère BICdonnées

Nombre de lois


Critère BIC



Introduction











Plusieurs problèmes apparaissent:

Données inadaptées

Données aberrantes (outliers)

Données manquantes


Données inadaptées: aucune cohérence n’apparaît

Classe A

Classe B


http://images.google.fr/imgres?imgurl=http://fr.dreamstime.com/chercheur-thumb1847315.jpg&imgrefurl=http://fr.dreamstime.com/searcher-image1847315&usg=__Ef8yZ0KwV6-G4Gmatmqunt7Axs4=&h=300&w=300&sz=33&hl=fr&start=16&um=1&tbnid=bIbri2vDWii35M:&tbnh=116&tbnw=116&prev=/images?q%3Dchercheur%26hl%3Dfr%26rlz%3D1T4GFRC_frFR316FR316%26sa%3DN%26um%3D1



Données aberrantes





Données manquantes : les données ne recouvrent pas

l’ensemble des configurations

Classe A

Classe B

Données à classer





Introduction







Matrice de confusion

Taux de bonne classification avec et sans cout

Courbe ROC




Performances d’un classificateur

En RdF, 3 bases :

-Une base de référence ou d’apprentissage utilisée pourapprendre le classificateur

-Une base de validation pour déterminer les paramètres duclassifieur

-Une base de test : exemples jamais vus au préalable pourévaluer le classificateur

Pourquoi ?


critères de rejet

étude des

confusions

facteur de

qualité

% formes bien classées

% formes mal classées

% formes non classées

En fonction des statistiques sur la base de test, on va pourvoir

définir:



Matrice de confusion :

1 2

1

2

décision

étiquette

e22 = Nb d’exemples

réellement 2 étiquetés 2





e11 = Nb d’exemples réellement 1 étiquetés 1



étiquette

1 2

1 90 6

2 20 104

décision

ExerciceQuel est le nombre d’exemples de la base de test ?

Que représente le chiffre 20 ?

Que représente le chiffre 104 ?

Quel est le taux de bonne reconnaissance?



Introduction









Courbe ROC




Taux de bonne classification sans coûts

Sans rejet

Taux de bonne classification

Taux d’erreur

Avec rejet

Taux de rejet


Taux d’erreur1a aTe Tb Tr

Nb d'exemples bien classés

Nb d'exemplessTb

Nb d'exemples non classés

Nb d'exemplesTr

1s sTe Tb


𝑇𝑏𝑎 =Nb exemples bien classés

Nb exemples=



Problème :

Il s’agit d’une mesure faible qui ne tient pas compte de

la distribution des classes

Exemple :En diagnostic médical, très peu de personnes sont

malades (5%?). On a donc des taux très bons en disant

que la personne est saine. Or, ce que l’on souhaite, c’est

ne pas rater ces 5% et donc, associer un mauvais taux

au classificateur qui dirait toujours ‘personne saine’.

Exemple sur 100 personnes

malade sain

malade 0 5

sain 0 95Tbs=95%




Solution :On tient compte de la répartition des classes et on construit une

matrice de confusion normalisée

1 2

1

2

décision

étiquette

e11/N1 e12/N1

e21/N2 e22/N2

N1 : Nombre d’exemples de la classe 1

N2 : Nombre d’exemples de la classe 2



Le nouveau taux de bonne classification devient

Où eii est le nombre d’exemple de la classe i classés i et Nc est le

nombre de classes

Et le nouveau taux d’erreur :

Exemple du médecin :Matrice de confusion normalisée

1

/Nc

ii

i i

etb Nc

N

e12/N1

e22/N2

1

1/ 1

Ncii

i i

ete Nc tb tr

N

tb=0.5

te=0.5

Taux de bonne classification sans coûts

malade sain

malade 0 1

sain 0 1



Problème 2 : Les performances dépendent des applications.

Exemple : en surveillance médicale, on préfère détecter à tortdes maladies plutôt que de risquer d’en laisser passer on

admet beaucoup de fausses alarmes mais pas de manque de

détection

On introduit une matrice des coûts



Taux de bonne classification avec coûts

1 2

1

2

décisionétiquette

Coût 1,1 Coût 1,2

Coût 2,1 Coût 2,2

Matrice des coûts:

Le taux de classification devient :

1

/

ii ii ij ijci j

i i

e Cout e Cout

tb NcN

Problème :Comment définir les coûts

???

Certains coûts peuvent (et doivent être négatifs)



Introduction









Courbe ROC




Comment comparer plusieurs classificateurs indépendamment du seuil ?

Problèmes à 2 classes

Trouvé par le classificateur

+ -

réel + TP FN

- FP TN

On définit les :

Vrai Positif (True Positive)

Vrai Négatif (True Négatif)

Faux Négatif (False Négatif)

Faux Positif (False Positif)



Négatifs

Positifs

TN

TP

FN FP


Comment comparer plusieurs classificateurs indépendamment du seuil ?

Problèmes à 2 classes


Courbe ROC (Receiver Operating Characteristic )Pour des problèmes binaires

étiquette

+ -

+ TP FN

- FP TN

décision Vrai Positif (TP)

Vrai Négatif (TN)

Faux Négatif (FN)

Faux Positif (FP)

Sensibilité Parmi les positifs de la base, % de correctsTP

TP FN

parmi les négatifs de la base, % de correctsTN

SpécificitéFP TN

Un bon classificateur devra être

sensible : détecter les positifs

spécifique : ne pas détecter aussi les négatifs

Généralement, plus un classificateur est sensible, moins il est

spécifique et vice versa



Courbe ROC (Receiver Operating Characteristic ) :

Sensibilité = f(1-spécificité)

Sensibilité Parmi les positifs de la base, % de correctsTP

TP FN

parmi les négatifs de la base, % de correctsTN

SpécificitéFP TN

1-spécificité

Se

nsi

bili

té

Courbe Roc

Point

idéal

Toutes les courbes ROC

passent par l’origine et

par le point (1,1)



Cas multi-classes

Matrice de confusion:

Trouvé par le classificateur

réel C0 C1 C2

C0 70 11 35

C1 17 73 8

C2 45 5 53

Somme des éléments sur la diagonaleTaux de reconnaissance=

Somme des éléments



Introduction


ClassificationIntroductionRappel sur les probabilitésEstimation des probabilitésQualité de la base de donnéesPerformance d’un classificateurMéthodes de classification génératives/discriminatives

Introduction

Méthode discriminative (K-ppv)1ppvKppvKppv et distance d’éditionDistance euclidienne et distance de Mahalanobis au centre des classesLVQK-moyennesDendrogramme

Méthode discriminative (arbre de décision)Méthode générative : classification bayésienne

IntroductionThéorie de la décisionEstimation des probabilités



3 approches différentes (Bishop 2007):

• Approche générative

• Approche discriminative

• Fonction discriminante

Méthodes génératives/discriminatives


Introduction

Approche générative : déterminer les densités de probabilités conditionnelles 𝑝(𝑥|𝐶𝑘) et les densités de probabilités a priori 𝑝(𝐶𝑘) pour

chaque classe individuellement. Puis utiliser le théorème de Bayes :

𝑝(𝐶𝑘|𝑥) =𝑝(𝑥|𝐶𝑘)𝑝(𝐶𝑘)

𝑝(𝑥)Où le dénominateur est un terme de normalisation :

𝑝(𝑥) =

𝑘

𝑝(𝑥|𝐶𝑘)𝑝(𝐶𝑘)

Connaissant 𝑝(𝐶𝑘|𝑥) , il est facile de trouver la classe de 𝑥.

Cette approche est dite générative car, connaissant 𝑝(𝑥|𝐶𝑘), il est facile de

générer des données dans l’espace des paramètres

Approche discriminative : Déterminer directement 𝑝(𝐶𝑘|𝑥) et décider de la

classe

Fonction discriminante: trouver une fonction 𝑓(𝑥) reliant directement les

données aux classes. Ex : pour un problème a deux classes, 𝑓(𝑥) est une

fonction à valeur binaire tq 𝑓(𝑥) = 0 pour la première classe et 𝑓(𝑥) =1 pour la seconde (aucune notion de probabilité)



Raisonnons sur un exemple : on souhaite déterminer la langue parlée par

une personne.

Approche générative : on apprend chaque langage puis on détermine à quel langage la

parole appartient (peut fonctionner avec une seule langue pour savoir si la personne parle

français ou non).

Approche discriminative: on apprend les différences linguistiques entre les langages,

sans apprendre le langage. Beaucoup plus simple !



Avantage/inconvénient des 3 approches

Approche générative• 𝑝(𝑥) est estimée. On peut considéré 𝑝(𝑥) comme la probabilité que 𝑥

soit bien modélisé par le modèle. Ceci permet de faire du rejet.

• 𝑝(𝑥|𝐶𝑘) peut être utilisée pour générer des données

• Permet à un système d’utiliser une seule classe. Ex : la teinte chaire

• Trouver 𝑝(𝑥|𝐶𝑘) pour chaque classe est très couteux en temps de calcul,

surtout quand 𝑥 est de grande dimension

• Nécessite une grande base de données, surtout quand 𝑥 est de grande

dimension

Approche discriminative• Il est beaucoup plus rapide de déterminer 𝑝(𝐶𝑘|𝑥) car la dimension de

𝐶𝑘 est bien souvent beaucoup plus faible que celle de x

Fonction discriminante• Modélisation et décision sont combinées dans un seul apprentissage

• 𝑝(𝐶𝑘|𝑥) n’est pas estimé. On ne pourra donc (i) ni faire du rejet; (ii) ni

combiner plusieurs classificateurs; (iii) ni compenser différentes

probabilités a priori des classes



Méthodes génératives Méthodes discriminatives

Classification bayésienne K plus proches voisins

Modélisation gaussienne Arbres de décision

GMM (Gaussian Mixture

Model)

Régression linéaire

HMM (Hidden Markov Model) SVM (Support Vector Machine

Réseaux bayésiens RVM (Relevance Vector

Machine)

MRF (Markov Random Fields) Réseaux de neurones

CRF (Conditional Random

fields )



Exemple : classification binaire

(Computer vision: models, learning and inference, Simon J.D. Prince 2012)

On souhaite estimer la teinte chaire (0/1) à partir de la quantité de rouge

𝑥 est une variable continue (quantité de rouge)

2 classes : teinte chaire ou non

Approche générative :• On modélise 𝑝(𝑥|𝐶0) et 𝑝(𝑥|𝐶1) par des gaussiennes (𝜇0, 𝜎0 , 𝜇1 , 𝜎1)

• On modélise 𝑝(𝑥|𝐶0) par une loi de Bernouilli de paramètre 𝜆• On utilise les données d’apprentissage ( 𝑥𝑖 , 𝐶𝑖 ) pour estimer les

paramètres (𝜇0, 𝜎0 , 𝜇1 , 𝜎1, 𝜆)

• On estime 𝑝(𝐶0|𝑥) et 𝑝(𝐶1|𝑥) en utilisant Bayes

Approche discriminative:• On modélise 𝑝(C|𝑥) par une loi de Bernouilli dont le paramètre 𝜆

dépend de x. Comme 0 < 𝜆 < 1 , on pose 𝜆 =1

1+exp(−Φ0−Φ1𝑥)et donc,

𝑝 C 𝑥 = Bern1

1+exp (−Φ0−Φ1𝑥)

• On utilise les données d’apprentissage ( 𝑥𝑖 , 𝐶𝑖 ) pour estimer les

paramètres (Φ0, Φ1) de 𝑝(𝐶0|𝑥) et 𝑝(𝐶1|𝑥) (4 paramètres)

• Pour un 𝑥 donné, on estime directement 𝑝(𝐶0|𝑥) et 𝑝(𝐶1|𝑥)



Introduction



Introduction






Données de départ :

Base de référence : ensemble de vecteurs de caractéristiques Xi et leurclasse Ci

Objectif :

Base de test : pour un nouveau vecteur X, trouver sa classe

Méthode :

Calculer la distance entre X et tous les exemples de la base de référence

Déterminer le vecteur le plus proche.

Affecter à X la classe de ce vecteur

Méthode discriminative : 1ppv


Vecteurs de la

classe C1

Vecteurs de la

classe C2𝑥 ?

Calcul de distanceEn dimension 2, chaque exemple 𝑥𝑖 est caractérisé par un

vecteur de dimension 2 [𝑥 𝑦]𝑇 et est donc représenté dans le

plan :

𝑥

𝑦



Calcul de distance

En dimension 3, chaque exemple 𝑥𝑖 est caractérisé par un vecteur de dimension

3 : [𝑥 𝑦 𝑧]𝑇 et est donc représenté dans l’espace :

Vecteurs de la

classe C2Vecteurs de la

classe C1

𝑥 ?



Forme

Vecteur de

caractéristiques

de dimension 𝑛

Calcul de distance

En dimension n, chaque exemple 𝑥𝑖 est caractérisé par un vecteur de

dimension n et peut être représenté dans un système de dimension 𝑛 :



Signification géométrique

Les classes sont définies par

la réunion des domaines

d’influence des références

La résolution spatiale des

frontières est liée au nombre

de références et à leur

densité



Avantages :

Pas d’hypothèses

Simple à mettre en œuvre

Incrémental

tend vers l’erreur optimale

Inconvénients :

Quantité de calculs quasi-proportionnelle aunombre d’exemples

Pas d’extraction d’information utile



Introduction



Introduction






Algorithme des k ppv (plus proches voisins)

1. Calculer la distance entre 𝑥 et tous les exemples de la

base de référence

2. Déterminer les 𝑘 vecteurs les plus proches

Puis classe majoritaire

on peut faire du rejet

Méthode discriminative : Kppv


-1 0 1 2 3 4 5 6 7-1

0

1

2

3

4

5

6

7

-1 0 1 2 3 4 5 6 7-1

0

1

2

3

4

5

6

7

k = 1, disp = 0.3 k = 1, disp = 0.7



-1 0 1 2 3 4 5 6 7-1

0

1

2

3

4

5

6

7

-1 0 1 2 3 4 5 6 7-1

0

1

2

3

4

5

6

7

k = 11

disp = 0.7

k= 21

disp = 0.7



Dilemme biais/variance

k faible

Bonne résolution des frontières

entre classe

Très sensible au bruit sur les

échantillons de la base de

référence

k grand

Mauvaise résolution des

frontières entre classe : lissage

des frontières

Peu sensible au bruit sur les

échantillons de la base de

référence


http://www.google.fr/imgres?imgurl=http://octocanon.files.wordpress.com/2007/06/attention.jpg&imgrefurl=http://octocanon.wordpress.com/2007/06/12/tournoi-de-neuchatel/&h=407&w=450&sz=93&tbnid=oGVkT4mePqpyHM:&tbnh=115&tbnw=127&prev=/images?q%3Dattention&zoom=1&q=attention&hl=fr&usg=__9r_p5XuVPDbETxeLg9QDhx81fmQ=&sa=X&ei=z1TmTObQAY6ChQfSuOjSDA&ved=0CCIQ9QEwAA

http://www.google.fr/imgres?imgurl=http://octocanon.files.wordpress.com/2007/06/attention.jpg&imgrefurl=http://octocanon.wordpress.com/2007/06/12/tournoi-de-neuchatel/&h=407&w=450&sz=93&tbnid=oGVkT4mePqpyHM:&tbnh=115&tbnw=127&prev=/images?q%3Dattention&zoom=1&q=attention&hl=fr&usg=__9r_p5XuVPDbETxeLg9QDhx81fmQ=&sa=X&ei=z1TmTObQAY6ChQfSuOjSDA&ved=0CCIQ9QEwAA


En testant, il faut alors utiliser une nouvelle base : une base de

validation pour ne pas employer la base de référence pourmettre au point le classificateur

3 bases :

-Base de référence où sont stockés les exemples utilisés dansl’algorithme des k-ppv

-Base de validation qui sera utilisée pour optimiser le paramètrek

-Base de test qui évaluera sur des données jamais observées aupréalable les performances du classificateur

Comment choisir k ?



D\Donnees\Doc-word\Enseignement\Rdf\codes

rdf\codes\demo_ecrit

ppv_char.m

Démo

Démo

Ppv.m

Démo



Noir : base de référence

Blanc : base de test

Donner la matrice de confusion

avec l’algorithme du 1ppv

Exercice





Introduction



Introduction






2 3 4 4 5 6 6 7 0 0 1

3

2 3 4 5 6 6 7 0 1

Comment calculer la distance entre les deux chaines constituées de

suites de symboles de longueur différentes ?

Lorsque les exemples sont codés de manière structurelle, par une suite

de symbole, la distance euclidienne n’a aucun sens.

On fait alors appel à la distance d’édition.

Par exemple, pour un codage de Freeman : 8 états

0

1

2

3

4

56

7

Méthode par discrimination : Kppv


Comparaison de chaînes de longueurs éventuellementdifférentes

Exemple : x = aabcb y = aababd

Déterminer la suite des transformations élémentaires pourpasser de x à y

Supprimer un symboleInsérer un symboleChanger un symbole ( S + I)

- affecter un coût à chaque transformation

distance = somme des coûts



Plusieurs chemins pour passer d’une chaîne à l’autre

Graphe orienté et valué

Choix : chemin de coût minimum

abcb

aabcb

aabcbd

aabab

aababd

ababdabab

arcs sommets

poids de l’arcS

I

C

I

C

I

C

I

aabcb



On note C(u,v) le coût pour changer u en v et $ l’élémentneutre

- x.$ = $.x = x pour tout mot x

- Insertion de u = substitution de $ par u C($,u)

- Suppression de u = substitution de u par $ C(u,$)

- Changement

Matrice des coûts : C(u,u) = 0 et C(u,v) > 0

(permet de corriger les problèmes de segmentation si ladifférence de coût est faible pour une erreur donnée)



Calcul par récurrence des distances cumulées D(i,j)

Matrice des coûts C() à initialiser a priori

X = a1a2a3…an

Y = b1b2b3…bm

X(i) = a1a2a3…ai

Y(j) = b1b2b3…bj

x(0) = y(0) = $

D(0,0) = d($,$) = 0

D(i-1,j) + C(ai,$)

D(i,j) = min D(i,j-1) + C($,bj)

D(i-1,j-1) + C(ai,bj)



Discrétisation

(ex : 8 directions)

Poids du codage

très important

Amplification du

bruit par le codage

Approche moins

structurelle

Plus grande

complexité

Codage

des vecteurs

Attributs

numériques

On peut aussi avoir des suites de caractères numériques :

programmation dynamique

D(i-1, j) + C(ai,bj)

D(i,j) = min D(i, j-1) + C(ai,bj)

D(i-1, j-1) + 2C(ai,bj)

C(ai,bj) = || bj – ai ||



Application à la saisie de mot sur les téléphones portables :

semaine ?

Drmain demain ?

demains ?

Quelle matrice de

cout ?



2 solutions

Réduction de la dimension de chaque exemple

ACP

LDA

Réduction de taille de la base de référence

On ne représente plus chaque classe que par sa

moyenne

Génération de prototypes : LVQ, K-moyennes

Dendrogramme

Dilemme robustesse/accélération

Accélération des k-PPV



Introduction



Introduction






Les classes sont représentées par leur moyenne

2 solutions :

• On ne conserve que les moyennes (centres) 𝜇𝑐 des classes On calcule les distances euclidiennes de(𝑥𝑖 , 𝜇𝑐 ) entre l’exemple

𝑥𝑖 et tous les centres 𝜇𝑐 L’exemple est classé à la classe de la distance la plus faible

• On conserve les moyennes 𝜇𝑐 et les matrices de covariance Σ𝑐 de chaque

classe

On calcule les distances de Mahalanobis dM(𝑥𝑖 , c) entre l’exemple

𝑥𝑖 exemple et les classes c avec

𝒅𝑴 𝒙𝒊, 𝒄 = (𝒙𝒊 − 𝝁𝒄 )𝑻𝜮𝒄

−𝟏(𝒙𝒊 − 𝝁𝒄 )

L’exemple est classé à la classe cde la distance la plus faible

Rq : Si Σ=Identité, on retrouve la distance euclidienne



Comparaison – distance euclidienne – distance de Mahalanobis

Les deux points A et B

sont à la même distance

euclidienne de O

Pas logique

Les deux points A et B

sont à la même distance

de Mahalanobis de O

http://www.aiaccess.net/French/Glossaires

Démo

mahal.M



Introduction



Introduction






Sélection des références LVQ

LVQ : Learning Vector Quantization

Méthode supervisée, itérative :

Génération d’un ensemble de prototypes quasi optimaux

Minimise la variance intra-classe

Maximise variance inter-classe

1.Initialisation aléatoire des prototypes (noyau)

2.Pour chaque vecteur x, trouver le prototype p le plus proche

Si p et X sont de la même classe, rapprocher p de x

sinon, éloigner p de X

p(t+1) = p(t) a(t)[X – p(t)]

où a(t) : pas d’apprentissage

3.Retour en 2 ou arrêt



LVQ, Itération 1 LVQ, Itération 2





LVQ, Itération 10



LVQ, Itération 1

LVQ, Itération 10







Démo

Lvq.m

Initialisation aléatoire :

Pb n°1 : Nombre de prototypes

performances

Pb n°2 : Position des prototypes

convergence


Sélection des références LVQ


Introduction



Introduction






Génération de prototypes: k-moyennes (k-means)

Méthode non supervisée, itérative. Travaille

indépendamment sur chaque classe :

Initialisation aléatoire des prototypes p1,…, pk

Affecter chaque exemple x au prototype pi le plus

proche

Calculer les nouveaux prototypes : moyenne des

exemples de « leur » groupe

Retour en 2 si pas idempotence

Pb : nombre de prototypes optimaux ?

Démo

Kmeans.m



it=0 it=1

it=2 it=3

Génération de prototypes: k-moyennes (k-means)



Introduction



Introduction






Dendrogramme

Méthode non supervisée.

Travaille indépendamment sur chaque classe

Classification ascendante hiérarchique

Regroupement des données suivant un

critère de distance




Dendrogramme


Détermination des prototypes : coupure dans la

hiérarchie

7 prototypes

3 prototypes


Dendrogramme


Introduction



Introduction






Exemple : arbre de décision pour décider si on regarde la TV ou si on vase promener

Méthode discriminative (arbre de décision)

Quel temps ?

Température ? Voisin présent ?

TV

PromenadeTVTV Promenade

couvert soleil

pluie

<10 >10 oui non


Un arbre de décision permet de classer chaque exemple avec un

ensemble de règles.

Manipulation facile de données symboliques.

Une suite de décisions permet de partitionner l’espace en régions

homogènes en terme de classe

La difficulté consiste à créer l’arbre à partir de la base d’exemple

étiquetée



On dispose d’une base de références composée:- des réponses au questions : vecteurs de paramètres

- de la classe associée à chaque exemple

Problème :Trouver l’ordre le plus cohérent dans l’agencement des

questions: il n’y a pas forcement besoin de tester tous les

paramètres à chaque fois



Initialisation : tous les exemples sont dans le même nœud X

Procédure construit_arbre(X)

Si X est une feuille Pb1

o Affecter une classe à X Pb2

Sinon

o Choisir la meilleure question et partitionner X en X1 et X2 Pb3

o Construit_arbre(X1)

o Construit_arbre(X2)

Fin si



Cet algorithme est très général. Plusieurs algorithmes vont en

découler en fonction :

1. De la façon de décider quand un nœud constitue une

feuille (Pb1)

2. De la façon d’affecter une classe à une feuille (Pb2)

3. De la façon de choisir la meilleure question (Pb3)



Problème 1:On décide qu’un nœud constitue une feuille :

Quand tous les exemples du nœud appartiennent à la

même classe

Quand tous les exemples du nœud ont le même vecteur

de paramètre

Quand le nombre d’exemples du nœud est inférieur à un

seuil

Quand une classe est largement majoritaire dans le nœud

En contrôlant les performances en généralisation sur une

base de validation



Problème 2:On affecte au nœud la classe majoritaire de ses exemples



Problème 3:

Comment choisir la meilleure question pour partitionner X ?

On utilise la théorie de l’information.Entropie sur X conditionnée par q

H(X/q) : quantité d’information contenue dans X si on

connaît q.

On va rechercher la question q qui minimise cette quantitéd’information (on voudrait que q nous amène toutes les

connaissances)

2

,

( / ) ( , ) log ( ( / ))u v

H X q p X u q v p X u a v



Dans le cas de données discrètes multi-variées pouvantprendre plus de 2 valeurs (rouge, vert bleu, jaune,…), on

étend le calcul de l’entropie conditionnelle. On pourra

alors être amené à avoir des nœuds non binaires

Dans le cas de variables continues, on va estimer pourchaque variable le seuil qui sépare au mieux les

exemples. On se ramène ainsi à un cas binaire.



Branches peu représentatives qui nuisent à la généralisation

générées par des exemples atypiques

On essaie de les supprimer par élagage en utilisant une

base de validation

Construction d’une forêt d’arbre aléatoire



Introduction



Introduction






𝑝(𝐶𝑘) : probabilité a priori (probabilité de la classe 𝐶𝑘 avantd’observer x)

𝑝(𝑥|𝐶𝑘) : vraisemblance des observations

𝑝(𝑥) : constante de normalisation: 𝑝(𝑥) = Σ 𝑝(𝑥|𝐶𝑘) 𝑝(𝐶𝑘)

𝑝(𝐶𝑘|𝑥) : probabilité a posteriori

Si le but est de minimiser la chance d’affecter 𝑥 à une mauvaiseclasse, intuitivement, on choisit la classe avec la plus grandeprobabilité a posteriori 𝑝(𝐶𝑘|𝑥). Cette décision est correcte maisd’autres décisions peuvent être prises

On dispose d’un exemple 𝑥 que l’on souhaite classer dans une des classes 𝐶𝑘

𝑝 𝐶𝑘 𝑥 =𝑃 𝑥|𝐶𝑘 𝑃(𝐶𝑘)

𝑃(𝑥)

Méthode générative : classification bayésienne


Introduction



Introduction







Décision par minimisation de l’erreur de classification

Dans un problème à 𝐾 classes, l’erreur de classification est donnée

par:

𝑃𝑒𝑟𝑟𝑒𝑢𝑟 = 1 − 𝑘=1𝐾 𝑝(𝑑é𝑐𝑖𝑑𝑒𝑟 𝑥 ∈ 𝐶𝑘 , 𝑥 ∈ 𝐶𝑘)dx

=1- 𝑘=1𝐾 𝑥 𝑎𝑓𝑓𝑒𝑐𝑡é à𝐶𝑘

𝑝(𝑥, 𝐶𝑘)dx

Pour minimiser 𝑃𝑒𝑟𝑟𝑒𝑢𝑟 il faut maximiser le second terme et donc

maximiser la valeur intégrée. On classera donc chaque exemple 𝑥à la classe avec le plus grand 𝑝(𝑥, 𝐶𝑘)

Or, 𝑝(𝑥, 𝐶𝑘)=𝑝(𝐶𝑘|𝑥)p(x)

Et comme 𝑝(𝑥) ne dépend pas de 𝑘,

on affecte 𝒙 à la classe qui maximise 𝒑(𝑪𝒌|𝒙)



Décision par minimisation d’un coût

Considérons une application médicale de détection de

cancer.

• Si un patient sain est diagnostiqué cancéreux, un stress et

d’autres examens complémentaires vont apparaitre

• Si un patient malade n’est pas diagnostiqué, les

conséquences sont beaucoup plus graves car la maladie

va continuer à évoluer

Les conséquences des erreurs ne sont pas les mêmes Introduction d’une matrice de coûts avec 𝐿𝑘𝑗, le coût

d’affecter un exemple de la classe 𝑗 à la classe 𝑘

Le coût total à minimiser va être donné par:

𝐶 = 𝑘 𝑗 𝑥 𝑎𝑡𝑡𝑟𝑖𝑏𝑢é à𝐶𝑘𝐿𝑘𝑗𝑝(𝑥, 𝐶𝑘) 𝑑𝑥

Or, comme précédemment, 𝑝(𝑥, 𝐶𝑘)=𝑝(𝐶𝑘|𝑥)p(x). Pour minimiser 𝐶, il faut minimiser 𝑘 𝐿𝑘𝑗𝑝(𝑥, 𝐶𝑘) pour tout 𝑥

On affecte x à la classe qui minimise 𝐤 𝐋𝐤𝐣𝐩(𝐱, 𝐂𝐤)



Décision avec rejet

Comme 𝑝(𝐶𝑘|𝑥) est connu, nous pouvons rejeter :

• les exemples tq la valeur maximale de 𝑝(𝐶𝑘|𝑥)<seuil

• les exemples qui ont leur deux plus grandes probabilités a

posteriori similaires


Introduction



Introduction






Classification

Une fois la règle de décision choisie, il reste à estimer

les vraisemblances de chaque classe p(x/Ck)

les probabilités a priori P(Ck)



Estimation des densités a priori

En l’absence d’informations particulières, les supposer

égales :

𝑝 𝐶𝑘 =1

𝐾où 𝐾 est le nombre de classes

Si l’échantillon d’apprentissage est représentatif, utiliser un

estimateur fréquentiel :

𝑝 𝐶𝑘 =𝑁𝑘

𝑁où 𝑁𝑘 est le nombre d’exemples de la classe 𝑘

et 𝑁 le nombre d’exemple total



Estimation de la vraisemblance

La vraisemblance de chaque classe Ck p(x/Ck) peut être estimée par

une des méthodes d’estimation de densité de probabilité introduiteprécédemment (estimation paramétrique ou non paramétrique)



Reconnaissance des formes et apprentissageIntroduction







Méthode discriminative utilisant les KppV

Méthode générative


Reconnaissance vs estimation

étiquette Variable continue

Reconnaître des

visages

Estimer la position de la têteΘ, ϕ

Exemples



ESPACE DE DECISION

CONTINU

ESPACE DE

REPRESENTATION

OU

ESPACE DES PARAMETRES

Estimation



Introduction












Entrée : Une base de référence (vecteur de codage) associé à une variable

continue e (décision)

Sortie :Pour un exemple X inconnu, estimer la variable e.

Pour retrouver une estimation, on compare le descripteur de la forme

inconnue à ceux des exemples de la base.

L’estimation est faite en prenant la valeur e de l’exemple le plus

proche.

On peut aussi choisir de garder les K exemples les plus proches, puis

interpoler avec une moyenne ou une médiane des valeurs de e de

ces exemples




e=1.0

e=1.3

e=1.4

e=1.3

e=0.9

e=1.3

e=1.6

e=1.7

e=1.6

e=???




Exemple : Estimation de la courbure de la route à 18m

devant un véhicule




Orientation

gardée

Orientation

indésirable

Bande utile

10 mètres

26 mètres

Ligne de fuite




Ligne de fuite

Votes coté

gauche

26 mètres

10 mètres

Votes coté

droit






Numéro d’image

Angle au volant




Base de 4900 images acquises sur un circuit

On partage la base en 2 : base de références et base de test

Pour chaque image test codage recherche des K codes les plus proches

dans la base de références K angles au volant

Puis moyenne ou médiane de ces valeurs

Taille du codage

Err

eu

r

mo

ye

nn

e



Numéro d’image

Angle au volant réel et estimé à chaque image



Introduction












Apprentissage sur la base d’exemple pour construire une fonction e=f(X) quiprédit les valeurs de e en des points arbitraires X non présents dans la base

d’entrainement.

Les données d’entrée X sont les vecteurs de paramètres (code) de dimension n.

La variable de sortie e est continue, de dimension n1<<n

Pour les modèles linéaires, la fonction est modélisée par une combinaison de

fonctions de base, et l’apprentissage sert à déterminer les coefficients de cette

combinaison.

Autre apprentissage : réseau de neurones

Attention à la complexité des modèles et au sur-apprentissage !



0 1 1 2 2( ) ( ) ( ) ... ( ) K Ke X X X X

Cette équation n’implique pas que e est une combinaison linéaire

des données d’entrée X mais que e est une fonction linéaire des

paramètres que l’on veut estimer ωi

L’emploi des fonctions de base Φi introduit une non linéarité entre X

et e

Plusieurs fonctions de base possible.

Le plus classique : gaussiennes centrées sur les points

d’apprentissage (autant de fonctions de base que de points

d’apprentissage)

2

22( )iX X

i X e



L’apprentissage consiste à rechercher les poids (ω) qui minimisent l’erreur au sens

des moindres carrés sur les données d’apprentissage :

En notant e=(e1, e2,…,eN)T

et

Le système peut s’écrire

Et a pour solution

1 0

( ) ( )N K

j k k j

j k

E w e w X

0 1 1 1 1

0 2 1 2 2

0 1

( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( )

K

K

N N K N

X X X

X X X

X X X

Φ

( )E w e w Φ

† † 1 où ( ) est la pseudo inverse de T Tw e Φ Φ

Des solutions non linéaires plus complexes existent:

-RVM

-…


Documents

RECONNAISSANCE DES FORMES - sorbonne-universite · Traitement dimages Traitement du signal (parole) Biologie ... Rappel sur les matrices de covariances Analyse en composantes principales