Embed Size (px)
Citation preview
DEA Perception et Traitement de l’Information
Reconnaissance des formes
discrimination linéaire
S. Canu
http://psichaud.insa-rouen.fr/~scanu/RdF
Buts de la RdFD : Algorithme
de Reconnaissance
des Formes
Une forme x(vecteur forme
des caractéristiques)
C’est la forme
« y=D(x) »
classe" vraiela" ,
)( ,...,,...,1 : RdF
décisions des ensemble ,...,2,1tiquescaractéris des espace
D(x)Rx
xDxLlRD
LyRx
d
d
d
Nous voulons un algorithme de RdF performant
K
kkXk
D
sSPdxkxfxDsCXDSCEDJ
DJD
1 ,)(,)(,)(
)(min décision de règle uned'Cout D
RdF et apprentissage
D : Algorithme de
Reconnaissancedes Formes
Une forme x(vecteur forme
des caractéristiques)
C’est la forme
« y=D(x) »
A : Algorithme d’apprentissage
niyxS iin ,1 , Ensemble d’apprentissage (échantillon)
)(,)(C,et )(
:couts les
XDSCEDJDJ
A priorisur la
nature de la solution
2
1
3
Les problèmes PYXP ,
RdF et apprentissage
D : Algorithme de
Reconnaissancedes Formes
Une forme x(vecteur forme
des caractéristiques)
C’est la forme
« y=D(x) »
A : Algorithme d’apprentissage
niyxS iin ,1 , Ensemble d’apprentissage (échantillon)
)(,)(C,et )(
:couts les
XDSCEDJDJ
A priorisur la
nature de la solution
2
1
3
Les problèmes PYXP ,
D(x) =signe(w’x+b)
Discrimination linéaire
+
+
+ +
+
++
+
+
+
+
+
+
0' :décision de frontière ,
...
...
,
...
...
te)(croix ver 0
rouges) (ronds 0
linéairedécision de règle
0 : linéairedécision de frontière
tiques)caractéris ( R dans valeursà v.a.
11
1
1
1
bxw
w
w
w
w
x
x
x
x
bxw
bxw
bxw
dX
d
j
d
j
d
jjj
d
jjj
d
jjj
d
Discrimination Linéaire
+
+
+ +
+
+
+
+
+
+
+
+
+
Codage {-1,1}, fonction de décision de type « heaviside »
Codage et géomètrie
0 si 1)(
0 si 1)( " signefonction " laest où
: linéairedécision de règle1
yy
yy
bxwd
jjj
w’x : produit scalaire
Géométrie : illustration dans R2
0' bxw
w
°x
w
bxwxdist
',
1wb
2wb
bxwsignxD ')(
0' bxw
0' bxw
2
1
2
1 , x
xx
w
ww
décision de frontière la à orthogonalest 0)('
0'et 0'et si
wyxw
bywbxwyx
w
bd
Quand le discriminateur linéaire est il optimal ?
• Quand on le sait à priori…
• quand les 2 classes sont gaussiènnes (même matrice de variance covariance, couts 0-1)
• quand on a peu d’exemples par rapport à d (rapport n/d)...et que l’on n’a pas de modèle
on peut l’utiliser pour « représenter » les données (cf ACP)
Avantages : il est simpleon connaît des bornes de l’erreur
MAP : cas gaussien
:du décision de règle
)2,(
1,
1)2,(
1,
10
)(
si
si )(
:du décision de règle
1
2
2
1
2
121
21
122
211
MV
SPSP
xfxf
SPxfSPxf
xSP
xSPxSPxSP
xSPxSPxD
xSPxSPS
xSPxSPSxD
MAP
X
X
X
X
Cas gaussien 1d
2 source la de x vient : )()(
ln2
1 source la de x vient : )()(
ln2
2
2
222,1,
ln
2,1,
2
12, ,
2
11,
1
222
22
121
1
222
22
121
2
22
2121
2
22
2
21
22
22
22
2
22
2
21
2
22
2
21
SPSP
x
SPSP
x
xxxxfxf
exfxf
exfexf
X
X
xx
X
X
x
X
x
X
Exemple : communication binaire synchronela source 1 émet des 0 et la source 2 des 1, le canal est bruité par un bruit blanc, on observe 2,0~ , NSX
Règle de décision
dens
itée
et lo
i à p
oste
riori
Erreur de décision
Gauss de loi la de tables
212121 CsSxPCsSxP
1211 1 ,3/2 pppSP
-3 -2 -1 0 1 2 3-3
-2
-1
0
1
2
3Discrimination de deux classes gausiè nnes
-0.8
-0.6
-0.6
-0.6
-0.4
-0.4
-0.4
-0.2
-0.2
-0.2
0
0
0.2
0.2
0.2
0.2
0.2
0.4
0.4
0.4
0.4
0.6
0.6
0.6
0.8
Cas gaussien multidimensionnel
2
12,
2
11,
21
2
11
1
'2
1
2/12/
'2
1
2/12/
xx
dX
xx
dX
exf
exf
12Le Discriminateur
de Bayesest linéaire...
Cas Gaussien (même variance)
b wbxwSPSP
x
SPSP
xSPSP
xfxf
x
xxx
xxxxfxf
exfxf
X
X
X
X
xxxx
X
X
et ' avec 0'
0ln''2
ln''22,1,
''2
''2'-
''2'2,1,
ln2
2,1,
121
1
221
121
121
1
221
121
121
1
2
211
211
21
11
11
11
21
21
21
'2
1'
2
12
121
11
...
Mise en œuvre pratique
-2 -1 0 1 2 3 4-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
2.5
-2 -1 0 1 2 3 4-3
-2
-1
0
1
2
3
-2 -1 0 1 2 3 4
-3
-2
-1
0
1
2
3
Estimation... et rêve
Discrimination Linéaire
+
+
+ +
+
++
+
+
+
+
+
+wx+ b=0
Discrimination Linéaire
+
+
+ +
+
++
+
+
+
+
+
+wx+ b=0
Discrimination Linéaire
+
+
+ +
+
++
+
+
+
+
+
+wx+ b=0
Discrimination Linéaire
+
+
+ +
+
++
+
+
+
+
+
+wx+ b=0
Marge
Marge
+
+
+ +
+
++
+
+
+
+
+
+
Discrimination Linéaire
wx+ b=0
Marge d’un classifieur
• frontière
• marge
• point influent : « proche » de la frontière, • point influent pour une règle D :
si l’étiquette change, la frontière change « significativement »(un des points
• point non influent
Définition
)()(,0,0 dxDdxDRdRx dd
xxm
niyxDm
Df
ifxni
ii
minmin
:par définieest ,1,n échantillol'pour de marge la ,
décision de règle uned' frontière la soit
,1
![RDF et RDFS - University of Paris-Est Marne-la-Valléeperso.univ-mlv.fr/ocure/RDF.pdfO.Curé [200 ] Présentation de RDF (Resource Description Framework) Un langage pour décrire des](https://img.pdfslide.fr/doc/110x75/60ed2d2053ad366fed1d7999/rdf-et-rdfs-university-of-paris-est-marne-la-vall-ocur-200-prsentation.jpg)
