Embed Size (px)
Citation preview
Régression logistique
G. Gasso, S. Canu
15 novembre 2016
G. Gasso, S. Canu Régression logistique 1 / 22
Plan
1 Introduction
2 Modèle
3 Estimation des paramètresCritèreEstimationAlgorithme
4 Conclusion
5 Annexe
G. Gasso, S. Canu Régression logistique 2 / 22
Introduction
Discrimination et probabilité a priori
Discrimination : problème de reconnaissance de caractères
Classe C1 : 3 contre Classe C2 : 8
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
5 10 15
5
10
15
Quelle est la probabilité a priori Pr(C1) que cette image soit un 8 ?
2 4 6 8 10 12 14 16
2
4
6
8
10
12
14
16
G. Gasso, S. Canu Régression logistique 3 / 22
Probabilité a postériori, cote et scoreQuelle est la probabilité Pr(C1/x) que chaque image soit un 3 ?
x =
5 10 15
2
4
6
8
10
12
14
16
5 10 15
2
4
6
8
10
12
14
16
5 10 15
2
4
6
8
10
12
14
16
5 10 15
2
4
6
8
10
12
14
16
5 10 15
2
4
6
8
10
12
14
16
Décision de Bayes : D(x) =
{C1 si Pr(C1/x)
Pr(C2/x) > 1C2 autrement
Quelle « cote » accorde-t-on à la décision (odds ratio) ?
cote(x) =Pr(C1/x)
Pr(C2/x)=
Pr(C1/x)
1− Pr(C1/x)
Score de Bayes
score(x) = log(
Pr(C1/x)
1− Pr(C1/x)
)
Probabilité a postériori, cote et score : quelles valeurs ?
La probabilité Pr(C1/x) ∈ [0, 1]
La « cote » : cote(x) = Pr(C1/x)Pr(C2/x) = Pr(C1/x)
1−Pr(C1/x) ∈ [0,∞[
score(x) = log(
Pr(C1/x)1−Pr(C1/x)
)∈ ]−∞,∞[
La décision D(x) : ∈ {C1, C2} ou encore ∈ {1, 0}
Remarque : la règle de décision de Bayes peut encore s’écrire
D(x) =
{C1 si score(x) = log
(Pr(C1/x)
1−Pr(C1/x)
)> 0
C2 autrement
Du score aux probabilités : les fonctions logit et logistique
s : le score de Bayesp : la probabilité a posteriori Pr(C1/x)
s = score = logp
1− pp =
exps
1 + exps=
1exp−s +1
0 0.2 0.4 0.6 0.8 1−8
−6
−4
−2
0
2
4
6
8
p
s,
la f
on
ctio
n lo
git
−6 −4 −2 0 2 4 6
0
0.2
0.4
0.6
0.8
1
p,
la f
on
ctio
n lo
gis
tiq
ue
s=score
Plus le score est grand, plus la probabilité Pr(C1/x) est proche de 1
Introduction
Récapitulation
La règle de décision requiert uniquement la connaissance du score
score(x) = log(
Pr(C1/x)
1− Pr(C1/x)
)La fonction de décision est D(x) = sign(score(x))
Objectifs de la régression logistique
trouver directement un modèle du score score(x) = log(
Pr(C1/x)1−Pr(C1/x)
)−→ Eviter de déterminer les lois conditionnelles p(x/Ck) et les probabilités
a priori Pr(Ck) afin d’en déduire les probabilités a posteriori Pr(Ck/x)
G. Gasso, S. Canu Régression logistique 7 / 22
Modèle
Modèle pour la régression logistique
Modèle linéaireOn représente le score par un modèle linéaire
logPr(C1/x)
Pr(C2/x)= [1 x>]θ = φ>θ
Expression des probabilités a posteriori
Pr(C1/x) =expφ
>θ
1 + expφ>θet Pr(C2/x) =
11 + expφ>θ
car Pr(C1/x) + Pr(C2/x) = 1
Remarque : si x ∈ Rd , on a θ et φ ∈ Rd+1
G. Gasso, S. Canu Régression logistique 8 / 22
Modèle
Régression logistique
Illustration des probabilités a posteriori
Pr(C1/x) = expφ>θ
1+expφ>θ
−10 −5 0 5 100
0.2
0.4
0.6
0.8
1
xa
T θ
PY
/X(Y
=1/X
=x)
Pr(C2/x) = 11+expφ>θ
−10 −5 0 5 100
0.2
0.4
0.6
0.8
1
xa
T θ
PY
/X(Y
=2/X
=x)
Estimation des paramètresParamètres : vecteur θ
Optimisation des paramètres : maximisation de la vraisemblance àpartir de données D = {(xi , yi )}i=1,··· ,N
G. Gasso, S. Canu Régression logistique 9 / 22
Estimation des paramètres Critère
Des données à la vraisemblance
Données {(xi , yi )}i=1,··· ,N i.i.d. de loi jointe P(yi , xi )
Vraisemblance
Λ(x1, · · · , xN) =N∏i=1
P(yi , xi )
Λ(θ; x1, · · · , xN) =N∏i=1
Pr(yi/xi ; θ) pX
(xi ) d’après Bayes
Log-Vraisemblance
L(θ; x1, · · · , xN) =N∑i=1
log(Pr(yi/xi ; θ)) +N∑i=1
log(pX
(xi ))
Maximisation de la log-vraisemblance conditionnelle
Le 2e terme de la log-vraisemblance étant indépendante de θ,
minθ−L(θ; x1, · · · , xN) ⇔ min
θJ(θ) avec J(θ) = −
N∑i=1
log(Pr(yi/xi ; θ))
G. Gasso, S. Canu Régression logistique 10 / 22
Estimation des paramètres Critère
Critère à optimiser
Notationsposons pi = Pr(yi = C1/xi ; θ). Remarque : Pr(yi = C2/xi ; θ) = 1− pi
soit la variable z telle que zi = 1 si yi = C1 et zi = 0 si yi = C2
Le critère J peut s’écrire alors
J(θ) = −
(N∑i=1
zi log(pi ) + (1− zi ) log(1− pi )
)
Or pi = expφ>i θ
1+expφ>iθ. On a alors
J(θ) =N∑i=1
−ziφ>i θ + zi log(1 + expφ>i θ) + (1− zi ) log(1 + expφ
>i θ)
J(θ) = −N∑i=1
ziφ>i θ +
N∑i=1
log(1 + expφ>i θ) avec θ ∈ Rd+1
G. Gasso, S. Canu Régression logistique 11 / 22
Estimation des paramètres Estimation
Estimation des paramètres
Estimation des paramètres par calcul de la solution de
minθ
J(θ)
Critère : J(θ) = −∑N
i=1 ziφ>i θ +
∑Ni=1 log(1 + expφ
>i θ)
−5 −4 −3 −2 −1 0 1 2 3 4 5
0
1
2
3
4
5
6
cout logistique
cout charnière
cout quadratique
Utilisation de méthodes de descente : gradient ou NewtonG. Gasso, S. Canu Régression logistique 12 / 22
Estimation des paramètres Estimation
Gradient et HessienGradient a et hessien du critère
a. Voir annexe
Critère : J(θ) = −∑N
i=1 ziφ>i θ +
∑Ni=1 log(1 + expφ
>i θ)
Gradient g = ∇θJ(θ)
g = −N∑i=1
ziφi +N∑i=1
φiexpφ
>i θ
1 + expφ>i θ
g = −N∑i=1
φi (zi − pi ) avec pi =expφ
>i θ
1 + expφ>i θ
Matrice hessienne H = ∂2J(θ)∂θ ∂θ>
H =N∑i=1
φiφ>i pi (1− pi )
On remarquera que pi dépend de θG. Gasso, S. Canu Régression logistique 13 / 22
Estimation des paramètres Estimation
Gradient et Hessien : forme matricielle
Posons
z =
z1z2...zN
, p =
p1p2...pN
∈ RN , Φ =
1 x>11 x>2
...1 x>N
∈ RN×(d+1)
Soit la matrice diagonale W ∈ RN×N telle que
Wii = pi (1− pi )
On montre qu’on a
gradient g = −Φ> (z− p)
Hessien H = Φ>WΦ
G. Gasso, S. Canu Régression logistique 14 / 22
Estimation des paramètres Estimation
Solution de la régression logistique
Méthode de Newtonθt+1 = θt − H−1
t gt
Remarque : le gradient et le hessien au point θt sont donnés par
gt = −Φ> (z− pt)
Ht = Φ>WtΦ
où pt et Wt sont calculés à partir de pti = expφ>i θ
t
1+expφ>iθt
En combinant ces éléments, on a alors
θt+1 = θt +(
Φ>WtΦ)−1
Φ> (z− pt)
G. Gasso, S. Canu Régression logistique 15 / 22
Estimation des paramètres Estimation
Solution de la régression logistique
Réécriture de la solution
θt+1 =(
Φ>WtΦ)−1
Φ>Wtrt avec rt = Φθt + W−1t (z− pt)
r est la sortie ajustée du modèle de régression logistique puisque Φθt
est le vecteur de sortie et (z− pt) l’erreur à l’itération t
On s’apercoit qu’à chaque itération, on résoud un problème demoindres carrés pondérés. En effet θt+1 est solution du problèmesuivant
θt+1 = argminθ (rt − Φθ)>Wt (rt − Φθ)
G. Gasso, S. Canu Régression logistique 16 / 22
Estimation des paramètres Algorithme
Algorithme
Entrées : la matrice des données X ∈ RN×d et le vecteur des labels y ∈ RN
Sortie : l’estimation du vecteur de paramètres θ
1 former la matrice Φ = [1 X ], le vecteur z tq zi = 1 si yi = 1 et 0 sinon
2 Initialisation : t = 0 et θt = 0.3 Répéter
Former le vecteur pt tq pt(i) = expφ>i θt
1+expφ>i
θ0 , i = 1, · · · ,N
Former la matrice Wt = diag(p1(1− p1) · · · pN(1− pN))
Former le vecteur rt = Φθt + W−1t (z− pt)
Calculer la nouvelle estimation des paramètres
θt+1 =(Φ>WtΦ
)−1Φ>Wtrt
t = t + 14 Jusqu’à convergence
G. Gasso, S. Canu Régression logistique 17 / 22
Estimation des paramètres Algorithme
Illustration
−3 −2 −1 0 1 2−2
−1.5
−1
−0.5
0
0.5
1
1.5
20.5
0.5
0.5
0.5
Classe 1
Classe 2
Dec frontier
G. Gasso, S. Canu Régression logistique 18 / 22
Estimation des paramètres Algorithme
Exploitation du modèle
Modèle de régression logistique
A la fin de l’algorithme, on a l’estimation des paramètres θ̂On en déduit : score(x) = φ>θ̂ avec φ> =
[1 x>
]Probabilités a posteriori
Pr(C1/x) = expφ>θ̂
1+expφ>θ̂et Pr(C2/x) =
1
1 + expφ>θ̂
Classification d’un nouveau point x`1 Calculer score(x`) = φ>` θ̂ avec φ>` =
[1 x>`
]2 Affecter le point x` à C1 si score(x`) > 0 ou à C2 autrement
3 Remarque : on affecte x` à C1 si p` > 1/2 avec p` = expφ>` θ̂
1+expφ>`θ̂
G. Gasso, S. Canu Régression logistique 19 / 22
Conclusion
Récapitulation
Théorie bayésienne de la décision
Coût 0 - 1 : décision basée sur la comparaison des probabilités aposteriori
mais nécessite la connaissance des lois conditionnelles et a priori
Régression logistique
modélise directement le rapport des probabilités
connaissance des lois n’est plus nécessaire
approche discriminative
Estimation des paramètres du modèle
Maximimisation de la log-vraisemblance ...
... par la méthode de Newton
G. Gasso, S. Canu Régression logistique 20 / 22
Conclusion
simple et précis : bonne prédictionmodèle très utilisé : détection de fraudes, scoringprobabilitésmais non parcimonieux...flexible : de nombreuses généralisations et notamment au casmulticlassepasse à l’échelle
Pour en savoir plus :http://www.stat.cmu.edu/~cshalizi/uADA/12/lectures/ch12.pdfhttp://www.math.univ-toulouse.fr/~besse/Wikistat/pdf/st-m-modlin-reglog.pdfhttps://stat.duke.edu/courses/Spring13/sta102.001/Lec/Lec20.pdfhttp://www.cs.berkeley.edu/~russell/classes/cs194/f11/lectures/CS194%20Fall%202011%20Lecture%2006.pdf
et le livre pages 120 et 121...
Annexe
Calcul du gradient par dérivée directionnelleOn suppose θ ∈ Rd+1, h ∈ Rd+1 et ε ∈ R
J(θ) = −N∑i=1
ziφ>i θ +
N∑i=1
log(1 + expφ>i θ)
ϕ(ε) = J(θ + εh) = −N∑i=1
ziφ>i (θ + εh) +
N∑i=1
log(
1 + expφ>i (θ+εh)
)
= −N∑i=1
ziφ>i θ − ε
N∑i=1
ziφ>i h +
N∑i=1
log(1 + expφ>i θ expεφ
>i h)
ϕ′(ε) = −
N∑i=1
ziφ>i h +
N∑i=1
φ>i h expφ
>i θ expεφ
>i h
1 + expφ>i
θ expεφ>i
h
ϕ′(0) = −
N∑i=1
ziφ>i h +
N∑i=1
expφ>i θ
φ>i h
1 + expφ>i
θ
=
− N∑i=1
ziφi +N∑i=1
expφ>i θ
φi
1 + expφ>i
θ
>
h
La dérivée directionnelle étant ϕ′(0) on en déduit alors que le gradient du critère est
g = −N∑i=1
ziφi +N∑i=1
expφ>i θ
φi
1 + expφ>i
θ= −
N∑i=1
ziφi +N∑i=1
piφi avec pi =expφ
>i θ
1 + expφ>i
θ
G. Gasso, S. Canu Régression logistique 22 / 22
