ARF Regression lin´ eaire´ Regression logistique´ Descente

ARF

Regression lineaireRegression logistiqueDescente de gradient

Cours 2ARF Master DAC

Nicolas [email protected]

http://webia.lip6.fr/˜baskiotisn

equipe MLIA, Laboratoire d’Informatique de Paris 6 (LIP6)Universite Pierre et Marie Curie (UPMC)

S2 (2016-2017)N. Baskiotis (LIP6, UPMC) ARF S2 (2016-2017) 1 / 19

http://webia.lip6.fr/~baskiotisn

Plan

1 Regression lineaire

2 Regression logistique

3 Descente de gradient

N. Baskiotis (LIP6, UPMC) ARF S2 (2016-2017) 2 / 19

Introduction

Regression lineaire

Objectif : predire une sortie continue reelle y a partir d’un nombre devariables d’entreebeaucoup d’applications, tres utilisee un peu dans tous les domainestres flexible (transformation des entrees)

20000 25000 30000 35000 40000 45000 50000 55000Revenu par menage

50000

100000

150000

200000

250000

300000

350000

400000

Prix

moy

en p

ar lo

gem

ent


Formalisation

Objectif

Etant donne un ensemble {(xi, yi)} ∈ Rd × R,Hypothese : variation lineaire de la sortie en fonction des entrees

E(y|x) = w0 +

d∑i=1

wixi

⇒ On cherche :I une fonction fw(x) = w0 +

∑di=1 wixi

I qui fait le moins d’erreurs : f (xi) doit etre proche de yi

I sous la condition que l’erreur est independante de x, de variance σ2

constante, suit une loi normale.⇒ y|x ∼ N (f (x), σ2) (lien avec l’apprentissage bayesien)

Notion d’erreur quadratique : `(f (x), y) = (f (x)− y)2


Formalisation (2)

Objectif

Minimiser :E(`(f (x), y)) =

∫x,y(y− f (x))2p(x, y)dxdy

Soit trouver w ∈ Rd+1 qui minimise :

n∑j=1

`(fw(x), y) =n∑

j=1

(yj − f (xj))2 =

n∑j=1

(yj − w0 −d∑

i=1

wixji)

2


Quelques notations et rappels

ConvexiteC ensemble convexe de Rn : ∀x, y ∈ C,∀λ ∈ [0, 1], λx + (1− λ)y ∈ C∑

i λixi est une combinaison convexe ssi ∀i, λi ≥ 0 et∑

i λi = 1Enveloppe convexe d’un ensemble fini {xi}, i = 1 . . . n : toutes lescombinaisons convexes de l’ensembleFonction f : X → R convexe ssi

∀x, x′ ∈ X,∀λ ∈ [0, 1] tq λx + (1− λx′ ∈ X)

alors f (λx + (1− λ)x′) ≤ λf (x) + (1− λ)f (x′)

si λi ≥ 0 et∑

i λi = 1, alors f (∑

i λixi) ≤∑

i λif (xi) (inegalite de Jensen)


Quelques notations et rappels

DifferentiabiliteSi f : X → R est convexe ssi ∀x, x′ ∈ X, f (x′) ≥ f (x)+ < x′ − x,∇f (x) >

Si f convexe, alors sa matrice hessienne est definie semi-positive :∇2f ≥ 0.

MinimumSi f atteint son minimum, alors les minimums forment un ensembleconvexe.Si l’ensemble est strictement convexe, le minimum est un singleton.Si f est strictement convexe, son gradient ne s’annule que a sonminimum local.


Regression : solution analytique

FormalisationMinimiser :

E(`(f (x), y)) =∫

x,y(y− f (x))2p(x, y)dxdy

Soit trouver w ∈ Rd+1 qui minimise :

L(w) =

n∑j=1

`(fw(x), y) =n∑

j=1

(yj − f (xj))2 =

n∑j=1

(yj − w0 −d∑

i=1

wixji)

2

La fonction L : Rd+1 → R est convexe⇒ Solution analytique : annuler son gradient !⇒ Trouver w∗ tq ∇wL(w∗) = 0


Derivee matricielle

Ecriture pratique

X =

x1

x2

...xn

=

x1

1 x12 . . . x1

dx1

1 x21 . . . x2

d...

xn1 xn

2 . . . xnd

, Y =

y1

y2

...yn

, W =

w1w2...

wd

L(w) = (XW − Y)′(XW − Y)

∇wL = 2X′(XW − Y), w optimal⇔ 2X′(XW − Y) = 0Solution : (X′X)−1X′Y

Et pour w0 ?


Plan





Problematique

Classification binaireDeux classes : Y = {0,+1}, et un ensemble d’apprentissage{(xi, yi) ∈ Rd × Y}Peut-on utiliser un cout quadratique dans ce cas ?Cas 2D :

I fw(x) = 1⇔ w0 + x1w1 + w2w2 = 1I fw(x) = 0⇔ w0 + x1w1 + w2w2 = 0


Problematique

Classification binaireDeux classes : Y = {0,+1}, et un ensemble d’apprentissage{(xi, yi) ∈ Rd × Y}Peut-on utiliser un cout quadratique dans ce cas ?Cas 2D :

I fw(x) = 1⇔ w0 + x1w1 + w2w2 = 1I fw(x) = 0⇔ w0 + x1w1 + w2w2 = 0

Et si fw(x) >> 1 ?⇒ le cout sera tres grand !

De meme si fw(x) << 0⇒ Le cout n’est pas adapte a la classification !


Adaptation du formalisme

Dans chaque region de l’espace :

le label +1 suit une loi de Bernoulli : p(y = 1|x) = µ(x)le label 0 egalement : p(y = 0|x) = 1− µ(x)

⇒ p(y|x) = µ(x)y(1− µ(x))1−y

Comment representer µ(x) ? Fonction lineaire ?


Adaptation du formalismeDans chaque region de l’espace :

le label +1 suit une loi de Bernoulli : p(y = 1|x) = µ(x)le label 0 egalement : p(y = 0|x) = 1− µ(x)

⇒ p(y|x) = µ(x)y(1− µ(x))1−y

Comment representer µ(x) ? Fonction lineaire ?⇒ Probleme ! pas entre 0 et 1 !

Transformation d’une fonction lineaire : la fonction sigmoıde.

µ(x) = σ(fw(x)) =1

1 + e−fw(x)

6 4 2 0 2 4 60.0

0.2

0.4

0.6

0.8

1.0


Quelques remarques importantes

Que represente fw(x) ?

C’est le log-ratio des probabilites : fw(x) = log(

P(+|x)P(−|x)

)= log

(µ(x)

1−µ(x)

)qui est approximee par une fonction lineaire :ln P(+|x)

P(−|x) = w0 + w1x1 + w2x2...

µ(x) = 11+e−fw(x) et 1− µ(x) = 1

1+efw(x)

→ P(y|x,w) = σ((2y− 1)fw(x)) (Vraissemblance du modele pour unechantillon (x, y))σ′(x) = σ(x)(1− σ(x))Quand est-ce que :

I p(+|x) = 0.5 ?I p(+|x) < 0.5 ?I p(+|x) > 0.5 ?


Resolution

Maximum de vraissemblanceOn cherche a maximiser :

P(y1, . . . , yn|x1, . . . , xn) =∏n

i=1 P(yi|xi)

⇔ maximiser log∏n

i=1 P(yi|xi)

⇔ maximiser∑n

i=1 log P(yi|xi)

⇔ minimiser 1n

∑ni=1 log 1

P(yi|xi)

⇔ minimiser 1n

∑ni=1 log 1

σ((2yi−1)fw(xi))

⇔ On cherche w∗ = argminw1n

∑ni=1 log

[1 + exp

(−(2yi − 1)fw(xi)

)]Resolution

Pas de solution analytique.Methode d’optimisation numerique→ descente de gradient.


Plan





Principe

Algorithme d’optimisation differentiableS’applique pour toute fonction differentiableIdee simple : ameliorer de facon iterative la solution courante


Algorithme du gradientAlgorithme

1 Choisir un point x02 Iterer :

I Calculer ∇f (xt)I mettre a jour xt+1 ← xt − α∇f (xt)


Pourquoi cela fonctionne ?

Developpement de Taylor

f (x) = f (x1) +∇f (x1)× (x− x1) + O(||x− x1||2)On cherche a “bouger” dans une direction u de facon a minimiser f :

f (x1 + hu)− f (x1) = h∇f (x1)u + h2O(1)

On doit donc minimiser ∇f (x1)u.

On choisit le vecteur unite u = − ∇f (x1)||∇f (x1)||

Plusieurs variantes :Hill climbing dans le cas discretCoordinate descent (line search selon les dimensions)Conjugate Gradient


Importance du pas de gradient

Algorithme1 Choisir un point x02 Iterer :

I Calculer ∇f (xt)I mettre a jour xt+1 ← xt − α∇f (xt)

Remarques

Que se passe-t-il si :I α est choisi trop grand ?I trop petit ?

Est-ce que l’on atteint toujours un minimum global ?Application a la regression logistique ?


Documents

ARF Regression lin´ eaire´ Regression logistique´ Descente