Comprendre et implémenter l'algorithme de la descente du gradient

Introduction

La descente du gradient est une méthode d’optimisation fondamentale en apprentissage automatique. La grande majorité des intelligences artificielles (IA) reposant sur des réseaux de neurones artificiels utilisent cet algorithme pour ajuster leurs paramètres et “apprendre” de leurs erreurs.

Au-delà de l’IA classique, cette méthode trouve des applications variées. Par exemple, la société DeepMind l’a exploitée pour prédire le repliement des protéines, une étape cruciale pour la conception de nouveaux médicaments.

Crédit : DeepMind (deepmind.com/blog/article/AlphaFold-Using-AI-for-scientific-discovery)

On retrouve également la descente du gradient dans la mise au point de filtres numériques récursifs, omniprésents en audio et en télécommunications. Qu’il s’agisse de reconnaissance d’objets, d’extraction de voix ou de génération de texte, cet algorithme est souvent le moteur de l’entraînement des modèles.

Nous allons explorer ici comment implémenter cet algorithme de manière simple et concrète.

Mise en situation

Pour illustrer les points forts de la descente du gradient, nous allons nous appuyer sur un exemple pratique. Il n’est pas nécessaire de posséder des notions avancées en mathématiques pour en comprendre le fonctionnement global ; les équations suivantes sont fournies à titre d’illustration.

Il arrive que l’on soit face à un problème impossible à résoudre de manière directe. Prenons un cas calculatoire simple :

Eq.1 Fonction simple

Si l’objectif est de trouver ‘A’, la méthode directe permet d’écrire immédiatement A = y[n]/n.

Considérons maintenant une fonction récursive où il faut trouver ‘A’ et ‘B’ :

Eq.2 Fonction récursive

Pour de telles équations, la résolution directe de ‘A’ et ‘B’ peut devenir extrêmement complexe. Si l’on manipule des millions, voire des milliards de paramètres, cette tâche devient insurmontable par les voies classiques.

Dans ces situations, l’approche itérative constitue une alternative efficace. Plutôt que de chercher la solution d’un seul coup, nous progressons par étapes successives vers le résultat optimal. C’est précisément le rôle de la descente du gradient.

Explication de l’algorithme

L’objectif de la descente du gradient est de trouver le minimum d’une fonction (dite dérivable). Graphiquement, cela revient à chercher le point le plus bas d’une courbe.

Fig.1 : Exemple de fonction avec deux minimums

Pour déterminer la direction du mouvement sur la courbe, l’algorithme utilise la notion de dérivée. Cette notion est centrale pour comprendre le processus, même s’il n’est pas indispensable de savoir dériver manuellement pour utiliser la méthode. Nous verrons d’ailleurs deux approches :

• Une méthode basée sur le calcul préalable des dérivées partielles.
• Une méthode par approximation, qui s’en dispense.

La dérivée permet de savoir dans quelle direction évolue le signal et avec quelle accélération.

Fig.2 Fonction y, y’ et y”

Sur ce graphique, la courbe bleue représente la fonction originale. La courbe rouge est sa dérivée. Lorsque la courbe bleue descend, la rouge prend des valeurs négatives. À l’inverse, quand la bleue monte, la rouge devient positive. Si la rouge vaut zéro, cela signifie que la bleue n’évolue plus (nous sommes sur un plateau ou un extremum).

Fig.3 Illustration de la descente du gradient

L’animation montre ce processus itératif : un point rouge, placé initialement au hasard, descend la pente vers la droite tant que le signe de la dérivée est négatif. Plus la valeur de la dérivée s’éloigne de zéro, plus le point avance rapidement. Dès que la dérivée atteint zéro, le point s’arrête : un minimum a été trouvé.

La fonction objectif

Trouver un minimum n’est utile que si la fonction représente un enjeu concret. La descente du gradient prend tout son sens lorsqu’elle est associée à une fonction objectif (ou loss function).

Une fonction de perte attribue un score aux données. Si l’on fait une analogie avec un examen, vous chercheriez à obtenir la meilleure note, mais c’est l’examinateur qui fixe le barème. La fonction objectif compare votre résultat à la “copie parfaite”. Elle donne un score de zéro si le résultat est parfait, et un score positif qui augmente à mesure que l’on s’éloigne de la perfection.

Pour les tâches de régression, l’erreur quadratique moyenne (MSE pour Mean Squared Error) est l’une des plus utilisées :

Eq.3 : MSE loss

Ici, ‘Yi’ représente les données de référence et ‘Ýi’ les données prédites. En minimisant cette fonction de perte, nous améliorons mécaniquement la précision du modèle. Il existe de nombreuses autres fonctions selon les besoins, dont une liste est disponible sur le site de TensorFlow.

Implémentation pratique

Nous allons maintenant implémenter la descente du gradient pour résoudre l’équation récursive présentée plus haut. L’objectif est de faire correspondre ‘y[n]’ à une cible en trouvant les bonnes valeurs de ‘A’ et ‘B’. Nous fixerons arbitrairement la longueur de la séquence à 128 points.

La fonction x[n] est définie ainsi :

Eq.4 : Définition de x[n]

Fig.4 : Représentation graphique de x[n]

La fonction y[n] est définie comme suit :

Eq.5 : Définition de y[n]

Fig.5 : Représentation graphique de y[n]

Pour générer cette cible, nous avons utilisé l’équation Eq.2 avec des valeurs arbitraires (A=1.0 et B=-0.95). Cela nous permet de vérifier que l’algorithme retrouve bien ces paramètres optimaux.

Implémentation sans calcul des dérivées partielles

Nous utilisons Python 3 et la bibliothèque matplotlib pour la visualisation. Le code source complet est disponible sur notre GitHub.

Initialisation du programme :

import matplotlib.pyplot as plt

LEN = 128
EPOCH = 200
LEARNING_RATE = 1.0
LEARNING_RATE_DECAY_STEP = 50
LEARNING_RATE_DECAY_FACTOR = 4.0
EPSILON = 0.00001

• LEN : longueur des séquences.
• EPOCH : nombre d’étapes d’entraînement.
• LEARNING_RATE : paramètre ajustant l’ampleur de la mise à jour des paramètres.
• EPSILON : constante utilisée pour estimer la pente des dérivées.

Code générant ‘y[n]’ :

def reponseImpulsion(A, B):
    # Definition des x[n] eq.4, avec un padding initial
    impulsion = [0.0] * (LEN+1)
    impulsion[1] = 1.0
    # Application de l'eq.2
    y = [0.0] * (LEN+1)
    for i in range(1, LEN+1):
        y[i] = (A * impulsion[i]) + (B * y[i-1])
    return y[1:]

# Définition de la cible
CIBLE = reponseImpulsion(1.0, -0.95)

Calcul de la fonction de perte :

def lossMSE(y_true, y_pred):
    mse = 0
    for i in range(LEN):
        mse += (y_true[i] - y_pred[i])**2
    return mse / LEN

Estimation du gradient :

def gradient(A, B):
    lossRef = lossMSE(CIBLE, reponseImpulsion(A, B))
    
    # Estimation de la dérivée pour A
    A += EPSILON
    gradientA = (lossMSE(CIBLE, reponseImpulsion(A, B)) - lossRef) / EPSILON
    A -= EPSILON

    # Estimation de la dérivée pour B
    B += EPSILON
    gradientB = (lossMSE(CIBLE, reponseImpulsion(A, B)) - lossRef) / EPSILON
    B -= EPSILON

    return gradientA, gradientB

Cette fonction calcule les gradients par différenciation numérique en faisant varier légèrement chaque paramètre pour observer l’évolution du résultat. C’est l’application directe de la définition de la dérivée :

Eq.6 : Définition formelle de la dérivée

La boucle principale d’entraînement :

def main():
    global LEARNING_RATE
    A, B = 0, 0

    for e in range(EPOCH):
        gradA, gradB = gradient(A, B)
        # Mise à jour des paramètres en soustrayant le gradient
        A -= gradA * LEARNING_RATE
        B -= gradB * LEARNING_RATE

        if (e+1) % LEARNING_RATE_DECAY_STEP == 0:
            LEARNING_RATE /= LEARNING_RATE_DECAY_FACTOR
        
        # ... code d'affichage ...

Fig.6 : Visualisation de la convergence du modèle

Implémentation avec calcul des dérivées partielles

Pour plus de précision, on peut utiliser les dérivées exactes de la fonction MSE par rapport à nos paramètres.

Eq.7 : Dérivée partielle en ‘A’ du loss MSE

Eq.8 : Dérivée partielle de ‘A’ de l’équation récursive

Il en va de même pour le paramètre ‘B’ :

Eq.10 : Dérivée partielle de ‘B’ du loss MSE

Eq.11 : Dérivée partielle de ‘B’ de l’équation récursive

L’implémentation de ces formules dans les fonctions dpA et dpB permet d’obtenir un calcul du gradient plus rigoureux et plus stable.

def dpA(A, B):
    impulsion = [0.0] * (LEN+1)
    impulsion[1] = 1.0
    y, dy = [0.0] * (LEN+1), [0.0] * (LEN+1)
    for i in range(1, LEN+1):
        y[i] = (A * impulsion[i]) + (B * y[i-1])
        dy[i] = impulsion[i] + (B * y[i-1])
    
    y_true = CIBLE
    mse = 0
    for i in range(LEN):
        mse += (y_true[i] - y[i+1]) * -dy[i+1]
    return (mse * 2) / LEN

def dpB(A, B):
    impulsion = [0.0] * (LEN+1)
    impulsion[1] = 1.0
    y, dy = [0.0] * (LEN+1), [0.0] * (LEN+1)
    for i in range(1, LEN+1):
        y[i] = (A * impulsion[i]) + (B * y[i-1])
        dy[i] = y[i-1] + (B * dy[i-1])
    
    y_true = CIBLE
    mse = 0
    for i in range(LEN):
        mse += (y_true[i] - y[i+1]) * -dy[i+1]
    return (mse * 2) / LEN

Avantages et limites

Bien que les exemples présentés ici soient solubles directement, la méthode itérative devient indispensable dès que le nombre de paramètres explose. Certains réseaux de neurones profonds comportent des milliards de paramètres, et la descente du gradient reste efficace dans ces conditions.

Il existe toutefois des limites importantes :

• Minimums locaux : l’algorithme peut se retrouver bloqué dans une zone optimale localement, mais qui n’est pas le meilleur résultat possible (minimum global).
• Instabilité du gradient : les valeurs peuvent devenir trop grandes (explosion) ou trop petites (disparition), rendant l’apprentissage impossible.
• Réglage des hyper-paramètres : le choix du taux d’apprentissage et du nombre d’itérations est déterminant pour la réussite de l’optimisation.
• Dérivabilité : le modèle doit théoriquement être dérivable pour chaque paramètre.

En pratique, on utilise des techniques de normalisation, des fonctions d’activation spécifiques et des optimiseurs évolués comme Adam pour contourner ces difficultés et garantir la convergence des modèles les plus complexes.