Gradient stochastique

 ---

contenu

resources

Descente de Gradient Stochastique

Fonction de cout

Entrainer un modele revient a minimiser une fonction de cout

chaque famille de modele a sa propre fonction de cout

Régression Linéaire

Modèle : y^=wTx+b\hat{y} = w^T x + b

Fonction de coût (MSE - Mean Squared Error) : E(w,b)=12n∑i=1n(yi−y^i)2=12n∑i=1n(yi−wTxi−b)2E(w, b) = \frac{1}{2n}\sum_{i=1}^n (y_i - \hat{y}_i)^2 = \frac{1}{2n}\sum_{i=1}^n (y_i - w^T x_i - b)^2

Régression Logistique

Modèle (classification binaire) :

y^=σ(wTx+b)=11+e−(wTx+b)\hat{y} = \sigma(w^T x + b) = \frac{1}{1 + e^{-(w^T x + b)}} où σ\sigma est la fonction sigmoïde

Fonction de coût (Log Loss / Cross-Entropy) :

E(w,b)=−1n∑i=1n[yilog⁡(y^i)+(1−yi)log⁡(1−y^i)]E(w, b) = -\frac{1}{n}\sum_{i=1}^n \left[ y_i \log(\hat{y}_i) + (1-y_i) \log(1-\hat{y}_i) \right] où yi∈{0,1}y_i \in \{0, 1\}

Decision Tree (Arbre de Décision)

critères de division :

1. Pour la régression - MSE (Mean Squared Error) :

MSE=1n∑i=1n(yi−yˉ)2\text{MSE} = \frac{1}{n}\sum_{i=1}^n (y_i - \bar{y})^2 où yˉ\bar{y} est la moyenne des yy dans le nœud

2. Pour la classification - Gini Impurity :

Gini=1−∑k=1Kpk2\text{Gini} = 1 - \sum_{k=1}^K p_k^2 où pkp_k est la proportion de la classe kk

3. Pour la classification - Entropie (Entropy) :

Entropy=−∑k=1Kpklog⁡2(pk)\text{Entropy} = -\sum_{k=1}^K p_k \log_2(p_k)

Algorithme glouton (greedy) qui choisit la meilleure division à chaque nœud, pas de descente de gradient pour les arbres de decisions !

1. Méthode du Gradient

Objectif : Trouver le minimum d'une fonction dérivable f(x)f(x) (la fonction de cout)

Principe : Itération selon la direction opposée au gradient

xn+1=xn−η∇f(xn)x_{n+1} = x_n - \eta \nabla f(x_n)

où η\eta est le taux d'apprentissage (learning rate) et ∇f(xn)\nabla f(x_n) le gradient, la derivée de la fonction f(x)f(x)

Qu'est-ce que le gradient ?

Le gradient, c'est la pente de la fonction à un point donné.

Analogie : Imaginez que vous êtes dans une vallée. Le gradient vous montre la direction de la montée la plus raide. Pour descendre au fond de la vallée (trouver le minimum), on va dans la direction opposée au gradient.

2. Démonstration : Fonction Polynomiale

Exemple : Minimiser f(x)=x2−4x+5f(x) = x^2 - 4x + 5

Dérivée : f′(x)=2x−4f'(x) = 2x - 4

Algorithme :

Résultat : f(2)=1f(2) = 1 est le minimum global

Code

Colab

def gradient_descent(f, df, x0, learning_rate=0.1, max_iter=100, tol=1e-6):
    """
    Trouve le minimum d'une fonction par descente de gradient

    Args:
        f: fonction à minimiser
        df: dérivée de la fonction
        x0: point de départ
        learning_rate: taux d'apprentissage (eta)
        max_iter: nombre maximum d'itérations
        tol: tolérance pour l'arrêt (early stopping)
    """
    x = x0

    for i in range(max_iter):
        # Calcul du gradient
        grad = df(x)

        # Mise à jour
        x_new = x - learning_rate * grad

        # Critère d'arrêt
        if abs(x_new - x) < tol:
            break

        x = x_new

    return x

Principe fondamental

Le gradient n'est PAS une constante, c'est une fonction de la position :

∇E(w)\nabla E(w)

Notation : w (poids/paramètres)

Le gradient ne s'applique qu'aux modeles dit lineaires ou il faut trouver les poids / les coefficients.

En Machine Learning

ww = vecteur des paramètres (weights)

w=(w1w2⋮wd)∈Rdw = \begin{pmatrix} w_1 \\ w_2 \\ \vdots \\ w_d \end{pmatrix} \in \mathbb{R}^d

où dd = nombre de features (dimensions)

Exemple concret - Régression linéaire

Modèle : y^=w1x1+w2x2+...+wdxd+b\hat{y} = w_1 x_1 + w_2 x_2 + ... + w_d x_d + b

Ou en notation vectorielle : y^=wTx+b\hat{y} = w^T x + b

Paramètres :

Le gradient est aussi un vecteur !

Mise à jour vectorielle :

wt+1=wt−η∇E(wt)w_{t+1} = w_t - \eta \nabla E(w_t)

Cela signifie chaque composante est mise à jour :

wi(t+1)=wi(t)−η∂E∂wiw_i^{(t+1)} = w_i^{(t)} - \eta \frac{\partial E}{\partial w_i}

Cas particulier : 1D

Avec f(x)=x2−4x+5f(x) = x^2 - 4x + 5 :

En pratique ML :

Dimensions

ModèleTaille de ww
Régression simple (1 feature)w∈Rw \in \mathbb{R}
Régression multiple (100 features)w∈R100w \in \mathbb{R}^{100}
Réseau de neurones simplew∈R10000w \in \mathbb{R}^{10000}
GPT-3w∈R175 milliardsw \in \mathbb{R}^{175 \text{ milliards}}

À chaque itération :

  1. On est à une nouvelle position wtw_t
  2. On calcule/estime le gradient à cette position
  3. Le gradient est différent car la pente change selon où on est

Le gradient change car on l'évalue à chaque nouveau point

Analogie simple

descendre une montagne :

Le gradient change naturellement car la pente n'est pas la même partout !

Le Problème : Trop de Données

Contexte Machine Learning : On a nn echantillons d'entraînement (x1,y1),...,(xn,yn)(x_1, y_1), ..., (x_n, y_n)

Fonction de coût totale :

E(w)=1n∑i=1nL(yi,f(xi;w))E(w) = \frac{1}{n}\sum_{i=1}^n L(y_i, f(x_i; w))

où LL = perte (loss) sur un echantillon

Problème : Calculer le gradient complet est coûteux

∇E(w)=1n∑i=1n∇Li(w)\nabla E(w) = \frac{1}{n}\sum_{i=1}^n \nabla L_i(w)

Avec nn = 1 million d'exemples → impossible à chaque itération !

La Solution : Gradient Stochastique

Idée : Au lieu de calculer le gradient sur TOUS les exemples, utiliser UN SEUL echantillon aléatoire

Gradient complet (trop lent) :

∇E(w)=1n∑i=1n∇Li(w)\nabla E(w) = \frac{1}{n}\sum_{i=1}^n \nabla L_i(w)

Gradient stochastique (rapide) :

∇E~(w)=∇Lk(w)\nabla \tilde{E}(w) = \nabla L_k(w) où kk est tiré au hasard parmi {1,...,n}\{1, ..., n\}

Propriété du gradient stochastique : En moyenne, ça marche !

E[∇Lk]=1n∑i=1n∇Li=∇E\mathbb{E}[\nabla L_k] = \frac{1}{n}\sum_{i=1}^n \nabla L_i = \nabla E

Pourquoi "Stochastique" ?

Le terme "stochastique" vient de l'échantillonnage aléatoire

Chaque itération :

  1. Tirer un exemple kk au hasard
  2. Calculer ∇Lk(w)\nabla L_k(w) (gradient analytique exact sur cet exemple)
  3. Mettre à jour : wt+1=wt−η∇Lk(wt)w_{t+1} = w_t - \eta \nabla L_k(w_t)

Ce qui est stochastique :

Ce qui est exact :

Estimation Non Biaisée

Question : Un seul exemple, c'est pas trop approximatif ?

Réponse : C'est bruité, mais non biaisé

Non biaisé = correct en moyenne

Si on répète l'expérience 1000 fois :

Analogie : Lancer un dé

Différence Batch GD vs SGD

Ce qui est calculé/estimé :

Batch GD :

SGD :

En résumé

7. Fonction de Coût : Forme Générale

Pour un seul echantillon : Li(w)=loss(yi,f(xi;w))L_i(w) = \text{loss}(y_i, f(x_i; w))

fonction de Coût avec régularisation estimée sur tous les échantillons : E(w)=1n∑i=1nLi(w)+αR(w)E(w) = \frac{1}{n}\sum_{i=1}^n L_i(w) + \alpha R(w)

Composantes :

8. Brève Histoire du SGD

9. Implémentation Moderne

Frameworks optimisés :

Optimisations :

10. Apprentissage en Ligne (Online Learning)

Principe : Mise à jour après chaque observation

Avantages :

Application :

Principe : Mise à jour des paramètres après chaque observation qui arrive

Algorithme :

À l'instant tt, une nouvelle observation (xt,yt)(x_t, y_t) arrive :

  1. Prédiction avec le modèle actuel : y^t=f(xt;wt)\hat{y}_t = f(x_t; w_t)

  2. Calcul de la perte sur cette seule observation : Lt=L(yt,y^t)L_t = L(y_t, \hat{y}_t)

  3. Mise à jour immédiate des paramètres : wt+1=wt−ηt∇Lt(wt)w_{t+1} = w_t - \eta_t \nabla L_t(w_t)

Différence avec SGD classique :

SGD ClassiqueOnline Learning
Dataset fixe, plusieurs epochsFlux continu, une seule passe
wt+1=wt−η∇Lkw_{t+1} = w_t - \eta \nabla L_kwt+1=wt−ηt∇Ltw_{t+1} = w_t - \eta_t \nabla L_t
kk tiré aléatoirementOrdre d'arrivée des données

Learning rate adaptatif souvent utilisé : ηt=η01+λt\eta_t = \frac{\eta_0}{1 + \lambda t}

où tt est le nombre d'observations vues

Exemple - Régression linéaire online :

Observation (xt,yt)(x_t, y_t) arrive : wt+1=wt+ηt(yt−wtTxt)⋅xtw_{t+1} = w_t + \eta_t (y_t - w_t^T x_t) \cdot x_t

Exemple - Moyenne mobile :

Calculer la moyenne en ligne : μt=μt−1+1t(xt−μt−1)\mu_t = \mu_{t-1} + \frac{1}{t}(x_t - \mu_{t-1})

11. SGDRegressor : Paramètres Clés

from sklearn.linear_model import SGDRegressor

model = SGDRegressor(
    loss='squared_error',      # Fonction de perte
    penalty='l2',              # Régularisation
    alpha=0.0001,              # Force régularisation
    learning_rate='invscaling', # Stratégie LR
    eta0=0.01,                 # LR initial
    max_iter=1000,             # Nb itérations
    tol=1e-3,                  # Critère arrêt
    early_stopping=True        # Arrêt anticipé
)

12. Influence du Taux d'Apprentissage

wt+1=wt−η∇L(wt)w_{t+1} = w_t - \eta \nabla L(w_t)

η\eta trop grand :

η\eta trop petit :

η\eta optimal : Convergence rapide et stable

13. Stratégies de Learning Rate

1. Constant : ηt=η0\eta_t = \eta_0

2. Décroissance temporelle : ηt=η01+t⋅d\eta_t = \frac{\eta_0}{1 + t \cdot d}

3. Inverse scaling : ηt=η0tα\eta_t = \frac{\eta_0}{t^\alpha}

4. Adaptatif : Ajustement selon performance validation

14. Learning Rate Adaptatif

Méthodes avancées :

AdaGrad : Adapte η\eta par paramètre ηt(i)=η0∑τ=1t(gτ(i))2+ϵ\eta_t^{(i)} = \frac{\eta_0}{\sqrt{\sum_{\tau=1}^t (g_\tau^{(i)})^2 + \epsilon}}

RMSprop : Moyenne mobile des gradients

Adam : Combine momentum + adaptation

15. Batch vs Mini-Batch vs Stochastique

TypeTaille échantillonCaractéristiques
Batch GDTous (nn)Stable, lent, grande mémoire
Stochastic GD1Rapide, bruité, converge
Mini-Batch GDmm (ex: 32-256)Optimal : vectorisation + stabilité

Formule mini-batch : wt+1=wt−η1m∑i=1m∇Li(wt)w_{t+1} = w_t - \eta \frac{1}{m}\sum_{i=1}^m \nabla L_i(w_t)

16. Mini-Batch : Out-of-Core Learning

Problème : Dataset trop large pour la RAM

Solution : Charger les données par batch

for epoch in range(n_epochs):
    for batch in data_loader:
        gradient = compute_gradient(batch)
        weights -= learning_rate * gradient

Applications : Big Data, streaming

17. Régularisation L1 (Lasso)

R(w)=∥w∥1=∑i=1d∣wi∣R(w) = \|w\|_1 = \sum_{i=1}^d |w_i|

Effet : Sélection de variables (sparsité)

Gradient sous-différentiel : ∂R∂wi=sign(wi)\frac{\partial R}{\partial w_i} = \text{sign}(w_i)

Usage : Features redondantes, interprétabilité

18. Régularisation L2 (Ridge)

R(w)=∥w∥22=∑i=1dwi2R(w) = \|w\|_2^2 = \sum_{i=1}^d w_i^2

Effet : Réduction de tous les poids

Gradient : ∂R∂wi=2wi\frac{\partial R}{\partial w_i} = 2w_i

Mise à jour : wt+1=(1−2ηα)wt−η∇L(wt)w_{t+1} = (1 - 2\eta\alpha)w_t - \eta \nabla L(w_t)

Pourquoi L1 → Sparsité (sélection de variables) ?

1. Forme de la régularisation

L1 (Lasso) :

R(w)=∥w∥1=∑i=1d∣wi∣R(w) = \|w\|_1 = \sum_{i=1}^d |w_i|

L2 (Ridge) :

R(w)=∥w∥22=∑i=1dwi2R(w) = \|w\|_2^2 = \sum_{i=1}^d w_i^2

2. Gradient / Sous-gradient

L1 : Gradient constant (en valeur absolue)

∂∣wi∣∂wi={+1si wi>0−1si wi<0[−1,1]si wi=0 \frac{\partial |w_i|}{\partial w_i} = \begin{cases} +1 & \text{si } w_i > 0 \\ -1 & \text{si } w_i < 0 \\ [-1, 1] & \text{si } w_i = 0 \end{cases}

L2 : Gradient proportionnel à ww

∂wi2∂wi=2wi\frac{\partial w_i^2}{\partial w_i} = 2w_i

3. Mise à jour des poids

Avec L1 :

wt+1=wt−η(∇L+α⋅sign(wt))w_{t+1} = w_t - \eta(\nabla L + \alpha \cdot \text{sign}(w_t))

➜ On retire une quantité constante ηα\eta \alpha à chaque itération ➜ Les petits poids arrivent rapidement à zéro exact

Avec L2 :

wt+1=wt−η(∇L+2αwt)=(1−2ηα)wt−η∇Lw_{t+1} = w_t - \eta(\nabla L + 2\alpha w_t) = (1-2\eta\alpha)w_t - \eta \nabla L

➜ On multiplie par (1−2ηα)(1-2\eta\alpha) ➜ Les poids diminuent mais n'atteignent jamais zéro (décroissance exponentielle)

4. Visualisation géométrique

Contrainte L1 : ∥w1∥+∥w2∥≤t\|w_1\| + \|w_2\| \leq t → forme un losange

Contrainte L2 : w12+w22≤tw_1^2 + w_2^2 \leq t → forme un cercle

Quand les contours de la fonction de coût rencontrent la contrainte :

[Imagine un graphique 2D avec contours et contraintes]

Conclusion

19. Régularisation Elastic Net

Combinaison L1 + L2 :

R(w)=ρ∥w∥1+1−ρ2∥w∥22R(w) = \rho \|w\|_1 + \frac{1-\rho}{2}\|w\|_2^2

Avantages :

SGDRegressor(penalty='elasticnet',
             l1_ratio=0.5)

20. Comment Régulariser le SGD

Paramètres Scikit-learn :

SGDRegressor(
    penalty='l2',        # 'l1', 'l2', 'elasticnet'
    alpha=0.0001,        # Force régularisation
    l1_ratio=0.15        # Si elasticnet
)

Impact :

21. Early Stopping (Arrêt Anticipé)

Principe : Arrêter l'entraînement avant la fin si pas d'amélioration

Algorithme :

  1. Diviser : train / validation
  2. À chaque époque : évaluer sur validation
  3. Si pas d'amélioration pendant pp époques : STOP

Implémentation :

SGDRegressor( early_stopping=True, validation_fraction=0.1, n_iter_no_change=5)

c'est le parametre n_iter_no_change qui contrôle le nombre d'époques sans amélioration avant l'arrêt.

22. SGDRegressor : Exemple Complet

from sklearn.linear_model import SGDRegressor
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split

# Normalisation
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Division
X_train, X_val, y_train, y_val = train_test_split(
    X_scaled, y, test_size=0.2
)

# Modèle
sgd = SGDRegressor(
    loss='squared_error',
    penalty='l2',
    alpha=0.001,
    learning_rate='adaptive',
    eta0=0.01,
    early_stopping=True
)

sgd.fit(X_train, y_train)

23. Vue d'Ensemble des Optimiseurs

SGD classique : wt=wt−1−η∇Lw_t = w_{t-1} - \eta \nabla L

SGD + Momentum : vt=βvt−1+∇Lv_t = \beta v_{t-1} + \nabla L wt=wt−1−ηvtw_t = w_{t-1} - \eta v_t

Nesterov : Momentum anticipé

AdaGrad : LR adaptatif par paramètre

RMSprop : Moyenne mobile du gradient carré

24. Optimiseurs Avancés

Adam (Adaptive Moment Estimation) :

AdamW : Adam avec weight decay découplé

Nadam : Nesterov + Adam

RAdam : Warmup automatique

Choisir : Adam par défaut, SGD+momentum si besoin de généralisation

25. Comparaison des Optimiseurs

OptimiseurVitesseStabilitéGénéralisationUsage
SGD⭐⭐⭐⭐⭐⭐⭐⭐⭐Classique
SGD+Momentum⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐Recommandé
Adam⭐⭐⭐⭐⭐⭐⭐⭐⭐Deep Learning
RMSprop⭐⭐⭐⭐⭐⭐⭐⭐⭐RNN

26. Momentum : Intuition

Problème SGD : Oscillations dans les ravins

Solution : Accumuler la "vitesse"

vt=βvt−1+(1−β)∇Ltv_t = \beta v_{t-1} + (1-\beta) \nabla L_t wt=wt−1−ηvtw_t = w_{t-1} - \eta v_t

Effet :

27. Diagnostic de Convergence

Courbes d'apprentissage :

Signes de problèmes :

28. Hyperparamètres : Réglage

Stratégies :

  1. Grid Search : Test exhaustif
  2. Random Search : Échantillonnage aléatoire
  3. Bayesian Optimization : Recherche intelligente

Paramètres critiques :

29. Astuces Pratiques

cas general

deep learning

30. Limitations du SGD

Choix du Learning Rate : Sensible, difficile à optimiser

Minima locaux : Peut rester coincé (fonctions non-convexes)

Saddle points : Ralentit près des points-selle

Scaling : Sensible à l'échelle des features

Solution : Optimiseurs adaptatifs (Adam, etc.)

31. Quand Utiliser SGD ?

SGD convient si :

Alternatives :

32. Extensions du SGD

Variance Reduction :

Second-ordre :

Distribué :

33. SGD en Deep Learning

Particularités :

Best Practices :

34. Références et Ressources

Papers fondateurs :

Documentation :

Cours :

35. Conclusion

SGD = Outil fondamental du Machine Learning

Points clés :

Recommandation : Commencer avec SGD+momentum ou Adam

1 / 0