Algorithme de descente de gradient stochastique avec Python et NumPy – Python réel

Fonction de coût: l'objectif de l'optimisation

le fonction de coût, ou fonction de perte, est la fonction à minimiser (ou maximiser) en faisant varier les variables de décision. De nombreuses méthodes d'apprentissage automatique résolvent les problèmes d'optimisation sous la surface. Ils ont tendance à minimiser la différence entre les sorties réelles et prévues en ajustant les paramètres du modèle (comme les poids et les biais pour les réseaux de neurones, les règles de décision pour la forêt aléatoire ou l'augmentation de gradient, etc.).

Dans un problème de régression, vous avez généralement les vecteurs des variables d'entrée = (₁,…, ᵣ) et les sorties réelles . Vous voulez trouver un modèle qui mappe à une réponse prédite () de sorte que () soit aussi proche que possible de . Par exemple, vous souhaiterez peut-être prédire un résultat tel que le salaire d’une personne en fonction d’intrants tels que le nombre d’années de la personne dans l’entreprise ou son niveau d’éducation.

Votre objectif est de minimiser la différence entre la prédiction () et les données réelles . Cette différence s'appelle le résiduel.

Dans ce type de problème, vous voulez minimiser la somme des carrés des résidus (SSR), où SSR = Σᵢ (ᵢ – (ᵢ)) ² pour toutes les observations = 1,…, , où est le nombre total de observations. Vous pouvez également utiliser l'erreur quadratique moyenne (MSE = SSR / ) au lieu de SSR.

SSR et MSE utilisent tous deux le carré de la différence entre les sorties réelles et prévues. Plus la différence est faible, plus la prédiction est précise. Une différence de zéro indique que la prédiction est égale aux données réelles.

Le SSR ou MSE est minimisé en ajustant les paramètres du modèle. Par exemple, dans la régression linéaire, vous voulez trouver la fonction () = ₀ + ₁₁ + ⋯ + ᵣᵣ, vous devez donc déterminer les poids ₀, ₁,…, ᵣ qui minimisent SSR ou MSE.

Dans un problème de classification, les sorties sont catégoriques, souvent 0 ou 1. Par exemple, vous pouvez essayer de prédire si un e-mail est du spam ou non. Dans le cas des sorties binaires, il est pratique de minimiser la fonction d'entropie croisée qui dépend également des sorties réelles ᵢ et des prédictions correspondantes (ᵢ):

Dans la régression logistique, qui est souvent utilisée pour résoudre des problèmes de classification, les fonctions () et () sont définies comme suit:

Encore une fois, vous devez trouver les poids ₀, ₁,…, ᵣ, mais cette fois ils devraient minimiser la fonction d'entropie croisée.

Gradient d'une fonction: mise à jour de calcul

En calcul, la dérivée d'une fonction vous montre à quel point une valeur change lorsque vous modifiez son argument (ou ses arguments). Les dérivés sont importants pour l'optimisation car les dérivés zéro peuvent indiquer un minimum, un maximum ou un point de selle.

Le gradient d'une fonction de plusieurs variables indépendantes ₁,…, ᵣ est noté ∇ (₁,…, ᵣ) et défini comme la fonction vectorielle des dérivées partielles de par rapport à chaque variable indépendante: ∇ = ( ∂ / ∂₁,…, ∂ / ᵣ). Le symbole ∇ s'appelle nabla.

La valeur non nulle du gradient d'une fonction en un point donné définit la direction et la vitesse de l'augmentation la plus rapide de . Lorsque vous travaillez avec la descente de gradient, vous êtes intéressé par la direction du plus rapide diminution dans la fonction de coût. Cette direction est déterminée par le gradient négatif, −∇.

L'intuition derrière la descente de gradient

Pour comprendre l'algorithme de descente de gradient, imaginez une goutte d'eau glissant sur le côté d'un bol ou une balle roulant sur une colline. Le drop et la balle ont tendance à se déplacer dans le sens de la diminution la plus rapide jusqu'à ce qu'ils atteignent le fond. Avec le temps, ils prendront de l'élan et accéléreront.

L'idée derrière la descente de gradient est similaire: vous commencez par une position arbitrairement choisie du point ou du vecteur = (₁,…, ᵣ) et la déplacez de manière itérative dans le sens de la diminution la plus rapide de la fonction de coût. Comme mentionné, c'est la direction du vecteur gradient négatif, −∇.

Une fois que vous avez un point de départ aléatoire = (₁,…, ᵣ), vous mettre à jour ou déplacez-le vers une nouvelle position dans la direction du gradient négatif: → – ∇, où (prononcé «ee-tah») est une petite valeur positive appelée taux d'apprentissage.

Le taux d'apprentissage détermine la taille de la mise à jour ou de l'étape de déplacement. C’est un paramètre très important. Si est trop petit, alors l'algorithme peut converger très lentement. Des valeurs élevées peuvent également entraîner des problèmes de convergence ou rendre l'algorithme divergent.

Mise en œuvre de la descente de gradient de base

Maintenant que vous savez comment fonctionne la descente de dégradé de base, vous pouvez l'implémenter en Python. Vous n'utiliserez que Python et NumPy simples, ce qui vous permet d'écrire du code concis lorsque vous travaillez avec des tableaux (ou des vecteurs) et d'obtenir une amélioration des performances.

Il s'agit d'une implémentation de base de l'algorithme qui commence par un point arbitraire, début, le déplace de manière itérative vers le minimum et renvoie un point qui, nous l'espérons, est égal ou proche du minimum:

    1def Descente graduelle(pente, début, learn_rate, nitre):
    2    vecteur = début
    3    pour _ dans intervalle(nitre):
    4        diff = -learn_rate * pente(vecteur)
    5        vecteur + = diff
    6    revenir vecteur

Descente graduelle() prend quatre arguments:

1. pente est la fonction ou tout objet appelable Python qui prend un vecteur et renvoie le dégradé de la fonction que vous essayez de minimiser.
2. début est le point où l'algorithme commence sa recherche, donné sous forme de séquence (tuple, liste, tableau NumPy, etc.) ou scalaire (dans le cas d'un problème unidimensionnel).
3. learn_rate est le taux d'apprentissage qui contrôle l'ampleur de la mise à jour vectorielle.
4. nitre est le nombre d'itérations.

Cette fonction fait exactement ce qui est décrit ci-dessus: elle prend un point de départ (ligne 2), le met à jour de manière itérative en fonction du taux d’apprentissage et de la valeur du gradient (lignes 3 à 5), et renvoie enfin la dernière position trouvée.

Avant de postuler Descente graduelle(), vous pouvez ajouter un autre critère de terminaison:

    1importer engourdi comme np
    2
    3def Descente graduelle(
    4    pente, début, learn_rate, nitre=50, tolérance=1e-06
    5):
    6    vecteur = début
    sept    pour _ dans intervalle(nitre):
    8        diff = -learn_rate * pente(vecteur)
    9        si np.tout(np.abdos(diff) <= tolérance):
dix            Pause
11        vecteur + = diff
12    revenir vecteur

Vous avez maintenant le paramètre supplémentaire tolérance (ligne 4), qui spécifie le mouvement minimal autorisé à chaque itération. Vous avez également défini les valeurs par défaut pour tolérance et nitre, vous n'avez donc pas à les spécifier à chaque fois que vous appelez Descente graduelle().

Les lignes 9 et 10 permettent Descente graduelle() pour arrêter l'itération et renvoyer le résultat avant nitre est atteint si la mise à jour vectorielle dans l'itération courante est inférieure ou égale à tolérance. Cela se produit souvent près du minimum, où les gradients sont généralement très petits. Malheureusement, cela peut également arriver à proximité d'un minimum local ou d'un point de selle.

La ligne 9 utilise les fonctions pratiques NumPy numpy.all () et numpy.abs () pour comparer les valeurs absolues de diff et tolérance en une seule déclaration. C’est pourquoi vous importer numpy sur la ligne 1.

Maintenant que vous avez la première version de Descente graduelle(), il est temps de tester votre fonction. Vous allez commencer par un petit exemple et trouver le minimum de la fonction = ².

Cette fonction n'a qu'une seule variable indépendante (), et son gradient est la dérivée 2. C’est une fonction convexe différentiable, et la manière analytique de trouver son minimum est simple. Cependant, en pratique, la différenciation analytique peut être difficile, voire impossible, et est souvent approchée par des méthodes numériques.

Vous n'avez besoin que d'une seule instruction pour tester votre implémentation de descente de gradient:

>>> Descente graduelle(
...     pente=lambda v: 2 * v, début=10,0, learn_rate=0,2
... )
2.210739197207331e-06

Vous utilisez la fonction lambda lambda v: 2 * v pour fournir le gradient de ². Vous partez de la valeur 10,0 et réglez le taux d'apprentissage sur 0,2. Vous obtenez un résultat très proche de zéro, qui est le minimum correct.

La figure ci-dessous montre le mouvement de la solution à travers les itérations:

Vous partez du point vert le plus à droite ( = 10) et vous vous déplacez vers le minimum ( = 0). Les mises à jour sont plus importantes au début car la valeur du gradient (et de la pente) est plus élevée. À mesure que vous approchez du minimum, ils deviennent plus bas.

Impact du taux d'apprentissage

Le taux d'apprentissage est un paramètre très important de l'algorithme. Différentes valeurs de taux d'apprentissage peuvent affecter considérablement le comportement de la descente de gradient. Prenons l'exemple précédent, mais avec un taux d'apprentissage de 0,8 au lieu de 0,2:

>>> Descente graduelle(
...     pente=lambda v: 2 * v, début=10,0, learn_rate=0,8
... )
-4,77519666596786e-07

Vous obtenez une autre solution très proche de zéro, mais le comportement interne de l’algorithme est différent. Voici ce qui se passe avec la valeur de à travers les itérations:

Dans ce cas, vous recommencez avec = 10, mais en raison du taux d'apprentissage élevé, vous obtenez un grand changement de qui passe de l'autre côté de l'optimum et devient −6. Il franchit le zéro encore quelques fois avant de s'installer près de lui.

De faibles taux d'apprentissage peuvent entraîner une convergence très lente. Si le nombre d'itérations est limité, l'algorithme peut revenir avant que le minimum ne soit trouvé. Sinon, l'ensemble du processus pourrait prendre un temps inacceptable. Pour illustrer cela, exécutez Descente graduelle() encore une fois, cette fois avec un taux d'apprentissage beaucoup plus petit de 0,005:

>>> Descente graduelle(
...     pente=lambda v: 2 * v, début=10,0, learn_rate=0,005
... )
6.050060671375367

Le résultat est maintenant 6,05, ce qui est loin du vrai minimum de zéro. En effet, les changements dans le vecteur sont très faibles en raison du faible taux d'apprentissage:

Le processus de recherche commence à = 10 comme précédemment, mais il ne peut pas atteindre zéro en cinquante itérations. Cependant, avec une centaine d'itérations, l'erreur sera beaucoup plus petite, et avec un millier d'itérations, vous serez très proche de zéro:

>>> Descente graduelle(
...     pente=lambda v: 2 * v, début=10,0, learn_rate=0,005,
...     nitre=100
... )
3,660323412732294
>>> Descente graduelle(
...     pente=lambda v: 2 * v, début=10,0, learn_rate=0,005,
...     nitre=1000
... )
0,0004317124741065828
>>> Descente graduelle(
...     pente=lambda v: 2 * v, début=10,0, learn_rate=0,005,
...     nitre=2000
... )
9,952518849647663e-05

Les fonctions non convexes peuvent avoir des minima locaux ou des points de selle où l'algorithme peut être piégé. Dans de telles situations, votre choix de taux d'apprentissage ou de point de départ peut faire la différence entre trouver un minimum local et trouver le minimum global.

Considérons la fonction ⁴ – 5² – 3. Il a un minimum global en ≈ 1.7 et un minimum local en ≈ −1.42. Le gradient de cette fonction est 4³ – 10 – 3. Voyons comment Descente graduelle() fonctionne ici:

>>> Descente graduelle(
...     pente=lambda v: 4 * v**3 - dix * v - 3, début=0,
...     learn_rate=0,2
... )
-1,4207567437458342

Vous avez commencé à zéro cette fois et l'algorithme s'est terminé près du minimum local. Voici ce qui s’est passé sous le capot:

Au cours des deux premières itérations, votre vecteur se déplaçait vers le minimum global, mais il est ensuite passé du côté opposé et est resté piégé dans le minimum local. Vous pouvez éviter cela avec un taux d'apprentissage plus faible:

>>> Descente graduelle(
...     pente=lambda v: 4 * v**3 - dix * v - 3, début=0,
...     learn_rate=0,1
... )
1.285401330315467

Lorsque vous diminuez le taux d'apprentissage de 0,2 à 0,1, vous obtenez une solution très proche du minimum global. N'oubliez pas que la descente de gradient est une méthode approximative. Cette fois, vous évitez le saut de l'autre côté:

Un taux d'apprentissage inférieur empêche le vecteur de faire de grands sauts, et dans ce cas, le vecteur reste plus proche de l'optimum global.

L'ajustement du taux d'apprentissage est délicat. Vous ne pouvez pas connaître à l’avance la meilleure valeur. Il existe de nombreuses techniques et heuristiques qui tentent de vous aider. En outre, les praticiens de l'apprentissage automatique ajustent souvent le taux d'apprentissage lors de la sélection et de l'évaluation du modèle.

Outre le taux d'apprentissage, le point de départ peut affecter la solution de manière significative, en particulier avec les fonctions non convexes.

Exemples courts

Tout d'abord, vous postulez Descente graduelle() à un autre problème unidimensionnel. Prenez la fonction – log (). Le gradient de cette fonction est de 1 – 1 / . Avec ces informations, vous pouvez trouver son minimum:

>>> Descente graduelle(
...     pente=lambda v: 1 - 1 / v, début=2,5, learn_rate=0,5
... )
1.0000011077232125

Avec l'ensemble d'arguments fourni, Descente graduelle() calcule correctement que cette fonction a le minimum en = 1. Vous pouvez l'essayer avec d'autres valeurs pour le taux d'apprentissage et le point de départ.

Vous pouvez aussi utiliser Descente graduelle() avec des fonctions de plus d'une variable. L'application est la même, mais vous devez fournir le gradient et les points de départ sous forme de vecteurs ou de tableaux. Par exemple, vous pouvez trouver le minimum de la fonction ₁² + ₂⁴ qui a le vecteur gradient (2₁, 4₂³):

>>> Descente graduelle(
...     pente=lambda v: np.tableau([[[[2 * v[[[[0], 4 * v[[[[1]**3]),
...     début=np.tableau([[[[1.0, 1.0]), learn_rate=0,2, tolérance=1e-08
... )
tableau ([8.08281277e-12, 9.75207120e-02])

Dans ce cas, votre fonction de dégradé renvoie un tableau et la valeur de départ est un tableau, vous obtenez donc un tableau comme résultat. Les valeurs résultantes sont presque égales à zéro, vous pouvez donc dire que Descente graduelle() trouvé correctement que le minimum de cette fonction est à ₁ = ₂ = 0.

Moindres carrés ordinaires

Comme vous l’avez déjà appris, la régression linéaire et la méthode des moindres carrés ordinaires commencent avec les valeurs observées des entrées = (₁,…, ᵣ) et des sorties . Ils définissent une fonction linéaire () = ₀ + ₁₁ + ⋯ + ᵣᵣ, qui est aussi proche que possible de .

C'est un problème d'optimisation. Il trouve les valeurs des poids ₀, ₁,…, ᵣ qui minimisent la somme des carrés des résidus SSR = Σᵢ (ᵢ – (ᵢ)) ² ou l'erreur quadratique moyenne MSE = SSR / . Ici, est le nombre total d'observations et = 1,…, .

Vous pouvez également utiliser la fonction de coût = SSR / (2), qui est mathématiquement plus pratique que SSR ou MSE.

La forme la plus élémentaire de régression linéaire est la régression linéaire simple. Il n'a qu'un seul ensemble d'entrées et deux poids: ₀ et ₁. L'équation de la droite de régression est () = ₀ + ₁. Bien que les valeurs optimales de ₀ et ₁ puissent être calculées de manière analytique, vous utiliserez la descente de gradient pour les déterminer.

Tout d'abord, vous avez besoin d'un calcul pour trouver le gradient de la fonction de coût = Σᵢ (ᵢ – ₀ – ₁ᵢ) ² / (2). Puisque vous avez deux variables de décision, ₀ et ₁, le gradient ∇ est un vecteur à deux composantes:

1. ∂ / ∂₀ = (1 / ) Σᵢ (₀ + ₁ᵢ – ᵢ) = moyenne (₀ + ₁ᵢ – ᵢ)
2. ∂ / ∂₁ = (1 / ) Σᵢ (₀ + ₁ᵢ – ᵢ) ᵢ = moyenne ((₀ + ₁ᵢ – ᵢ) ᵢ)

Vous avez besoin des valeurs de et pour calculer le gradient de cette fonction de coût. Votre fonction de gradient aura comme entrées non seulement ₀ et ₁ mais également et . Voici à quoi cela pourrait ressembler:

def ssr_gradient(X, y, b):
    res = b[[[[0] + b[[[[1] * X - y
    revenir res.signifier(), (res * X).signifier()  # .mean () est une méthode de np.ndarray

ssr_gradient () prend les tableaux X et y, qui contiennent les entrées et sorties d'observation, et le tableau b qui contient les valeurs courantes des variables de décision ₀ et ₁. Cette fonction calcule d'abord le tableau des résidus pour chaque observation (res) puis renvoie la paire de valeurs de ∂ / ∂₀ et ∂ / ∂₁.

Dans cet exemple, vous pouvez utiliser la méthode pratique NumPy ndarray.mean () puisque vous passez des tableaux NumPy comme arguments.

Descente graduelle() nécessite deux petits ajustements:

1. Ajouter X et y comme paramètres de Descente graduelle() en ligne 4.
2. Fournir X et y à la fonction de dégradé et assurez-vous de convertir votre tuple de dégradé en un tableau NumPy à la ligne 8.

Voici comment Descente graduelle() s'occupe de ces changements:

    1importer engourdi comme np
    2
    3def Descente graduelle(
    4    pente, X, y, début, learn_rate=0,1, nitre=50, tolérance=1e-06
    5):
    6    vecteur = début
    sept    pour _ dans intervalle(nitre):
    8        diff = -learn_rate * np.tableau(pente(X, y, vecteur))
    9        si np.tout(np.abdos(diff) <= tolérance):
dix            Pause
11        vecteur + = diff
12    revenir vecteur

Descente graduelle() accepte maintenant les entrées d'observation X et sorties y et peut les utiliser pour calculer le gradient. Conversion de la sortie de gradient (x, y, vecteur) à un tableau NumPy permet la multiplication élément par élément des éléments de gradient par le taux d'apprentissage, ce qui n'est pas nécessaire dans le cas d'une fonction à variable unique.

Maintenant, appliquez votre nouvelle version de Descente graduelle() pour trouver la droite de régression pour certaines valeurs arbitraires de X et y:

>>> X = np.tableau([[[[5, 15, 25, 35, 45, 55])
>>> y = np.tableau([[[[5, 20, 14, 32, 22, 38])

>>> Descente graduelle(
...     ssr_gradient, X, y, début=[[[[0,5, 0,5], learn_rate=0,0008,
...     nitre=100_000
... )
tableau ([5.62822349, 0.54012867])

Le résultat est un tableau avec deux valeurs qui correspondent aux variables de décision: ₀ = 5,63 et ₁ = 0,54. La meilleure droite de régression est () = 5,63 + 0,54. Comme dans les exemples précédents, ce résultat dépend fortement du taux d'apprentissage. Vous pourriez ne pas obtenir un si bon résultat avec un taux d'apprentissage trop faible ou trop élevé.

Cet exemple n'est pas entièrement aléatoire. Il est tiré du didacticiel Régression linéaire en Python. La bonne nouvelle est que vous avez presque obtenu le même résultat que le régresseur linéaire de scikit-learn. Les données et les résultats de la régression sont visualisés dans la section Régression linéaire simple.

Amélioration du code

Tu peux faire Descente graduelle() plus robuste, complet et plus esthétique sans modifier ses fonctionnalités de base:

    1importer engourdi comme np
    2
    3def Descente graduelle(
    4    pente, X, y, début, learn_rate=0,1, nitre=50, tolérance=1e-06,
    5    dtype="float64"
    6):
    sept    # Vérifier si le dégradé est appelable
    8    si ne pas appelable(pente):
    9        élever Erreur-type("'gradient' doit être appelable")
dix
11    # Configuration du type de données pour les tableaux NumPy
12    dtype_ = np.dtype(dtype)
13
14    # Conversion de x et y en tableaux NumPy
15    X, y = np.tableau(X, dtype=dtype_), np.tableau(y, dtype=dtype_)
16    si X.forme[[[[0] ! = y.forme[[[[0]:
17        élever ValueError("Les longueurs 'x' et 'y' ne correspondent pas")
18
19    # Initialisation des valeurs des variables
20    vecteur = np.tableau(début, dtype=dtype_)
21
22    # Configuration et vérification du taux d'apprentissage
23    learn_rate = np.tableau(learn_rate, dtype=dtype_)
24    si np.tout(learn_rate <= 0):
25        élever ValueError("'learn_rate' doit être supérieur à zéro")
26
27    # Configuration et vérification du nombre maximal d'itérations
28    nitre = int(nitre)
29    si nitre <= 0:
30        élever ValueError("'n_iter' doit être supérieur à zéro")
31
32    # Configuration et vérification de la tolérance
33    tolérance = np.tableau(tolérance, dtype=dtype_)
34    si np.tout(tolérance <= 0):
35        élever ValueError("'tolérance' doit être supérieure à zéro")
36
37    # Réalisation de la boucle de descente de gradient
38    pour _ dans intervalle(nitre):
39        # Recalculer la différence
40        diff = -learn_rate * np.tableau(pente(X, y, vecteur), dtype_)
41
42        # Vérifier si la différence absolue est suffisamment petite
43        si np.tout(np.abdos(diff) <= tolérance):
44            Pause
45
46        # Mise à jour des valeurs des variables
47        vecteur + = diff
48
49    revenir vecteur si vecteur.forme autre vecteur.article()

Descente graduelle() accepte maintenant un dtype paramètre qui définit le type de données des tableaux NumPy à l'intérieur de la fonction. Pour plus d'informations sur les types NumPy, consultez la documentation officielle sur les types de données.

Dans la plupart des applications, vous ne remarquerez pas de différence entre les nombres à virgule flottante 32 bits et 64 bits, mais lorsque vous travaillez avec de grands ensembles de données, cela peut affecter considérablement l'utilisation de la mémoire et peut-être même la vitesse de traitement. Par exemple, bien que NumPy utilise des flottants 64 bits par défaut, TensorFlow utilise souvent des nombres décimaux 32 bits.

En plus de prendre en compte les types de données, le code ci-dessus introduit quelques modifications liées à la vérification de type et à l'utilisation des fonctionnalités NumPy:

• Lignes 8 et 9 vérifier si pente est un objet appelable Python et s'il peut être utilisé comme fonction. Sinon, la fonction lèvera un Erreur-type.

• Ligne 12 définit une instance de numpy.dtype, qui sera utilisé comme type de données pour tous les tableaux de la fonction.

• Ligne 15 prend les arguments X et y et produit des tableaux NumPy avec le type de données souhaité. Les arguments X et y peuvent être des listes, des tuples, des tableaux ou d'autres séquences.

• Lignes 16 et 17 comparer les tailles de X et y. Ceci est utile car vous voulez être sûr que les deux tableaux ont le même nombre d'observations. Si ce n'est pas le cas, la fonction lèvera un ValueError.

• Ligne 20 convertit l'argument début à un tableau NumPy. C'est une astuce intéressante: si début est un scalaire Python, puis il sera transformé en un objet NumPy correspondant (un tableau avec un élément et zéro dimension). Si vous passez une séquence, elle deviendra un tableau NumPy normal avec le même nombre d’éléments.

• Ligne 23 fait la même chose avec le taux d'apprentissage. Cela peut être très utile car cela vous permet de spécifier différents taux d'apprentissage pour chaque variable de décision en passant une liste, un tuple ou un tableau NumPy à Descente graduelle().

• Lignes 24 et 25 vérifiez si la valeur du taux d'apprentissage (ou les valeurs de toutes les variables) est supérieure à zéro.

• Lignes 28 à 35 ensemble de la même manière nitre et tolérance et vérifiez qu'ils sont supérieurs à zéro.

• Lignes 38 à 47 sont presque les mêmes qu'avant. La seule différence est le type du tableau de dégradés à la ligne 40.

• Ligne 49 renvoie commodément le tableau résultant si vous avez plusieurs variables de décision ou un scalaire Python si vous avez une seule variable.

Votre Descente graduelle() est maintenant terminé. N'hésitez pas à ajouter des fonctionnalités supplémentaires ou de polissage. L'étape suivante de ce didacticiel consiste à utiliser ce que vous avez appris jusqu'à présent pour implémenter la version stochastique de la descente de gradient.

Minibatchs en descente de gradient stochastique

Comme dans le cas de la descente de gradient ordinaire, la descente de gradient stochastique commence par un vecteur initial de variables de décision et le met à jour à travers plusieurs itérations. La différence entre les deux réside dans ce qui se passe à l'intérieur des itérations:

• La descente de gradient stochastique divise aléatoirement l'ensemble des observations en minibatchs.
• Pour chaque mini-match, le gradient est calculé et le vecteur est déplacé.
• Une fois que tous les minibatchs sont utilisés, vous dites que l'itération, ou époque, est terminé et commencez le suivant.

Cet algorithme sélectionne de manière aléatoire les observations pour les minibatchs, vous devez donc simuler ce comportement aléatoire (ou pseudo-aléatoire). Vous pouvez le faire avec la génération de nombres aléatoires. Python a la fonction intégrée Aléatoire module, et NumPy a son propre générateur aléatoire. Ce dernier est plus pratique lorsque vous travaillez avec des tableaux.

Vous allez créer une nouvelle fonction appelée sgd () qui est très similaire à Descente graduelle() mais utilise des minibatchs sélectionnés au hasard pour se déplacer dans l'espace de recherche:

    1importer engourdi comme np
    2
    3def sgd(
    4    pente, X, y, début, learn_rate=0,1, taille du lot=1, nitre=50,
    5    tolérance=1e-06, dtype="float64", random_state=Aucun
    6):
    sept    # Vérifier si le dégradé est appelable
    8    si ne pas appelable(pente):
    9        élever Erreur-type("'gradient' doit être appelable")
dix
11    # Configuration du type de données pour les tableaux NumPy
12    dtype_ = np.dtype(dtype)
13
14    # Conversion de x et y en tableaux NumPy
15    X, y = np.tableau(X, dtype=dtype_), np.tableau(y, dtype=dtype_)
16    n_obs = X.forme[[[[0]
17    si n_obs ! = y.forme[[[[0]:
18        élever ValueError("Les longueurs 'x' et 'y' ne correspondent pas")
19    xy = np.c_[[[[X.remodeler(n_obs, -1), y.remodeler(n_obs, 1)]
20
21    # Initialisation du générateur de nombres aléatoires
22    la graine = Aucun si random_state est Aucun autre int(random_state)
23    rng = np.Aléatoire.default_rng(la graine=la graine)
24
25    # Initialisation des valeurs des variables
26    vecteur = np.tableau(début, dtype=dtype_)
27
28    # Configuration et vérification du taux d'apprentissage
29    learn_rate = np.tableau(learn_rate, dtype=dtype_)
30    si np.tout(learn_rate <= 0):
31        élever ValueError("'learn_rate' doit être supérieur à zéro")
32
33    # Configuration et vérification de la taille des minibatchs
34    taille du lot = int(taille du lot)
35    si ne pas 0 < taille du lot <= n_obs:
36        élever ValueError(
37            "'batch_size' doit être supérieur à zéro et inférieur à"
38            "ou égal au nombre d'observations"
39        )
40
41    # Configuration et vérification du nombre maximal d'itérations
42    nitre = int(nitre)
43    si nitre <= 0:
44        élever ValueError("'n_iter' doit être supérieur à zéro")
45
46    # Configuration et vérification de la tolérance
47    tolérance = np.tableau(tolérance, dtype=dtype_)
48    si np.tout(tolérance <= 0):
49        élever ValueError("'tolérance' doit être supérieure à zéro")
50
51    # Réalisation de la boucle de descente de gradient
52    pour _ dans intervalle(nitre):
53        # Mélanger x et y
54        rng.mélanger(xy)
55
56        # Effectuer des mouvements de minibatch
57        pour début dans intervalle(0, n_obs, taille du lot):
58            Arrêtez = début + taille du lot
59            x_batch, y_batch = xy[[[[début:Arrêtez, :-1], xy[[[[début:Arrêtez, -1:]
60
61            # Recalculer la différence
62            diplômé = np.tableau(pente(x_batch, y_batch, vecteur), dtype_)
63            diff = -learn_rate * diplômé
64
65            # Vérifier si la différence absolue est suffisamment petite
66            si np.tout(np.abdos(diff) <= tolérance):
67                Pause
68
69            # Mise à jour des valeurs des variables
70            vecteur + = diff
71
72    revenir vecteur si vecteur.forme autre vecteur.article()

Vous avez un nouveau paramètre ici. Avec taille du lot, vous spécifiez le nombre d'observations dans chaque mini-match. Il s'agit d'un paramètre essentiel pour la descente de gradient stochastique qui peut affecter considérablement les performances. Les lignes 34 à 39 garantissent que taille du lot est un entier positif non supérieur au nombre total d'observations.

Un autre nouveau paramètre est random_state. Il définit la graine du générateur de nombres aléatoires à la ligne 22. La graine est utilisée à la ligne 23 comme argument pour default_rng (), qui crée une instance de Générateur.

Si vous passez l'argument Aucun pour random_state, le générateur de nombres aléatoires renverra des nombres différents à chaque fois qu’il sera instancié. Si vous voulez que chaque instance du générateur se comporte exactement de la même manière, vous devez spécifier la graine. Le moyen le plus simple est de fournir un entier arbitraire.

La ligne 16 en déduit le nombre d'observations avec forme x[0]. Si X est un tableau unidimensionnel, alors c'est sa taille. Si X a deux dimensions, alors .forme[0] est le nombre de lignes.

À la ligne 19, vous utilisez .reshape () pour s'assurer que les deux X et y devenir des tableaux à deux dimensions avec n_obs lignes et ça y a exactement une colonne. numpy.c_[] concatène commodément les colonnes de X et y en un seul tableau, xy. C'est une façon de rendre les données adaptées à une sélection aléatoire.

Enfin, aux lignes 52 à 70, vous implémentez le pour boucle pour la descente du gradient stochastique. Il diffère de Descente graduelle(). À la ligne 54, vous utilisez le générateur de nombres aléatoires et sa méthode .shuffle () pour mélanger les observations. C'est l'une des façons de choisir des minibatchs au hasard.

L'intérieur pour boucle est répétée pour chaque mini-match. La principale différence avec la descente de gradient ordinaire est que, à la ligne 62, le gradient est calculé pour les observations à partir d'un minibatch (x_batch et y_batch) au lieu de pour toutes les observations (X et y).

À la ligne 59, x_batch devient une partie de xy qui contient les lignes du minibatch actuel (de début à Arrêtez) et les colonnes qui correspondent à X. y_batch contient les mêmes lignes de xy mais seulement la dernière colonne (les sorties). Pour plus d'informations sur le fonctionnement des index dans NumPy, consultez la documentation officielle sur l'indexation.

Vous pouvez maintenant tester votre implémentation de la descente de gradient stochastique:

>>> sgd(
...     ssr_gradient, X, y, début=[[[[0,5, 0,5], learn_rate=0,0008,
...     taille du lot=3, nitre=100_000, random_state=0
... )
tableau ([5.63093736, 0.53982921])

Le résultat est presque le même que celui obtenu avec Descente graduelle(). Si vous omettez random_state Ou utiliser Aucun, vous obtiendrez des résultats quelque peu différents chaque fois que vous courrez sgd () parce que le générateur de nombres aléatoires va mélanger xy différemment.

Momentum dans la descente de gradient stochastique

Comme vous l’avez déjà vu, le taux d’apprentissage peut avoir un impact significatif sur le résultat de la descente de gradient. Vous pouvez utiliser plusieurs stratégies différentes pour adapter le taux d'apprentissage pendant l'exécution de l'algorithme. Vous pouvez également postuler élan à votre algorithme.

Vous pouvez utiliser l'élan pour corriger l'effet du taux d'apprentissage. L'idée est de se souvenir de la mise à jour précédente du vecteur et de l'appliquer lors du calcul de la suivante. Vous ne déplacez pas le vecteur exactement dans la direction du dégradé négatif, mais vous avez également tendance à conserver la direction et l’amplitude du mouvement précédent.

Le paramètre appelé le taux de décomposition ou facteur de décomposition définit la force de la contribution de la mise à jour précédente. Pour inclure l'élan et le taux de décroissance, vous pouvez modifier sgd () en ajoutant le paramètre decay_rate et utilisez-le pour calculer la direction et l'amplitude de la mise à jour vectorielle (diff):

    1importer engourdi comme np
    2
    3def sgd(
    4    pente, X, y, début, learn_rate=0,1, decay_rate=0,0, taille du lot=1,
    5    nitre=50, tolérance=1e-06, dtype="float64", random_state=Aucun
    6):
    sept    # Vérifier si le dégradé est appelable
    8    si ne pas appelable(pente):
    9        élever Erreur-type("'gradient' doit être appelable")
dix
11    # Configuration du type de données pour les tableaux NumPy
12    dtype_ = np.dtype(dtype)
13
14    # Conversion de x et y en tableaux NumPy
15    X, y = np.tableau(X, dtype=dtype_), np.tableau(y, dtype=dtype_)
16    n_obs = X.forme[[[[0]
17    si n_obs ! = y.forme[[[[0]:
18        élever ValueError("Les longueurs 'x' et 'y' ne correspondent pas")
19    xy = np.c_[[[[X.remodeler(n_obs, -1), y.remodeler(n_obs, 1)]
20
21    # Initialisation du générateur de nombres aléatoires
22    la graine = Aucun si random_state est Aucun autre int(random_state)
23    rng = np.Aléatoire.default_rng(la graine=la graine)
24
25    # Initialisation des valeurs des variables
26    vecteur = np.tableau(début, dtype=dtype_)
27
28    # Configuration et vérification du taux d'apprentissage
29    learn_rate = np.tableau(learn_rate, dtype=dtype_)
30    if np.tout(learn_rate <= 0):
31        raise ValueError("'learn_rate' must be greater than zero")
32
33    # Setting up and checking the decay rate
34    decay_rate = np.array(decay_rate, dtype=dtype_)
35    if np.tout(decay_rate < 0) ou np.tout(decay_rate > 1):
36        raise ValueError("'decay_rate' must be between zero and one")
37
38    # Setting up and checking the size of minibatches
39    batch_size = int(batch_size)
40    if ne pas 0 < batch_size <= n_obs:
41        raise ValueError(
42            "'batch_size' must be greater than zero and less than "
43            "or equal to the number of observations"
44        )
45
46    # Setting up and checking the maximal number of iterations
47    n_iter = int(n_iter)
48    if n_iter <= 0:
49        raise ValueError("'n_iter' must be greater than zero")
50
51    # Setting up and checking the tolerance
52    tolerance = np.array(tolerance, dtype=dtype_)
53    if np.tout(tolerance <= 0):
54        raise ValueError("'tolerance' must be greater than zero")
55
56    # Setting the difference to zero for the first iteration
57    diff = 0
58
59    # Performing the gradient descent loop
60    pour _ dans range(n_iter):
61        # Shuffle x and y
62        rng.shuffle(xy)
63
64        # Performing minibatch moves
65        pour start dans range(0, n_obs, batch_size):
66            stop = start + batch_size
67            x_batch, y_batch = xy[[[[start:stop, :-1], xy[[[[start:stop, -1:]
68
69            # Recalculating the difference
70            grad = np.array(gradient(x_batch, y_batch, vector), dtype_)
71            diff = decay_rate * diff - learn_rate * grad
72
73            # Checking if the absolute difference is small enough
74            if np.all(np.abs(diff) <= tolerance):
75                break
76
77            # Updating the values of the variables
78            vector + = diff
79
80    return vector if vector.shape autre vector.item()

In this implementation, you add the decay_rate parameter on line 4, convert it to a NumPy array of the desired type on line 34, and check if it’s between zero and one on lines 35 and 36. On line 57, you initialize diff before the iterations start to ensure that it’s available in the first iteration.

The most important change happens on line 71. You recalculate diff with the learning rate and gradient but also add the product of the decay rate and the old value of diff. Maintenant diff has two components:

1. decay_rate * diff is the momentum, or impact of the previous move.
2. -learn_rate * grad is the impact of the current gradient.

The decay and learning rates serve as the weights that define the contributions of the two.

Random Start Values

As opposed to ordinary gradient descent, the starting point is often not so important for stochastic gradient descent. It may also be an unnecessary difficulty for a user, especially when you have many decision variables. To get an idea, just imagine if you needed to manually initialize the values for a neural network with thousands of biases and weights!

In practice, you can start with some small arbitrary values. You’ll use the random number generator to get them:

    1importer numpy comme np
    2
    3def sgd(
    4    gradient, X, y, n_vars=None, start=None, learn_rate=0.1,
    5    decay_rate=0.0, batch_size=1, n_iter=50, tolerance=1e-06,
    6    dtype="float64", random_state=None
    sept):
    8    # Checking if the gradient is callable
    9    if ne pas callable(gradient):
dix        raise TypeError("'gradient' must be callable")
11
12    # Setting up the data type for NumPy arrays
13    dtype_ = np.dtype(dtype)
14
15    # Converting x and y to NumPy arrays
16    X, y = np.array(X, dtype=dtype_), np.array(y, dtype=dtype_)
17    n_obs = X.shape[[[[0]
18    if n_obs != y.shape[[[[0]:
19        raise ValueError("'x' and 'y' lengths do not match")
20    xy = np.c_[[[[X.reshape(n_obs, -1), y.reshape(n_obs, 1)]
21
22    # Initializing the random number generator
23    seed = None if random_state is None autre int(random_state)
24    rng = np.random.default_rng(seed=seed)
25
26    # Initializing the values of the variables
27    vector = (
28        rng.normal(size=int(n_vars)).astype(dtype_)
29        if start is None autre
30        np.array(start, dtype=dtype_)
31    )
32
33    # Setting up and checking the learning rate
34    learn_rate = np.array(learn_rate, dtype=dtype_)
35    if np.tout(learn_rate <= 0):
36        raise ValueError("'learn_rate' must be greater than zero")
37
38    # Setting up and checking the decay rate
39    decay_rate = np.array(decay_rate, dtype=dtype_)
40    if np.tout(decay_rate < 0) ou np.tout(decay_rate > 1):
41        raise ValueError("'decay_rate' must be between zero and one")
42
43    # Setting up and checking the size of minibatches
44    batch_size = int(batch_size)
45    if ne pas 0 < batch_size <= n_obs:
46        raise ValueError(
47            "'batch_size' must be greater than zero and less than "
48            "or equal to the number of observations"
49        )
50
51    # Setting up and checking the maximal number of iterations
52    n_iter = int(n_iter)
53    if n_iter <= 0:
54        raise ValueError("'n_iter' must be greater than zero")
55
56    # Setting up and checking the tolerance
57    tolerance = np.array(tolerance, dtype=dtype_)
58    if np.tout(tolerance <= 0):
59        raise ValueError("'tolerance' must be greater than zero")
60
61    # Setting the difference to zero for the first iteration
62    diff = 0
63
64    # Performing the gradient descent loop
65    pour _ dans range(n_iter):
66        # Shuffle x and y
67        rng.shuffle(xy)
68
69        # Performing minibatch moves
70        pour start dans range(0, n_obs, batch_size):
71            stop = start + batch_size
72            x_batch, y_batch = xy[[[[start:stop, :-1], xy[[[[start:stop, -1:]
73
74            # Recalculating the difference
75            grad = np.array(gradient(x_batch, y_batch, vector), dtype_)
76            diff = decay_rate * diff - learn_rate * grad
77
78            # Checking if the absolute difference is small enough
79            if np.all(np.abs(diff) <= tolerance):
80                break
81
82            # Updating the values of the variables
83            vector + = diff
84
85    return vector if vector.shape autre vector.item()

You now have the new parameter n_vars that defines the number of decision variables in your problem. The parameter start is optional and has the default value None. Lines 27 to 31 initialize the starting values of the decision variables:

• If you provide a start value other than None, then it’s used for the starting values.
• If start is None, then your random number generator creates the starting values using the standard normal distribution and the NumPy method .normal().

Now give sgd() a try:

>>> sgd(
...     ssr_gradient, X, y, n_vars=2, learn_rate=0.0001,
...     decay_rate=0.8, batch_size=3, n_iter=100_000, random_state=0
... )
array([5.63014443, 0.53901017])

You get similar results again.

You’ve learned how to write the functions that implement gradient descent and stochastic gradient descent. The code above can be made more robust and polished. You can also find different implementations of these methods in well-known machine learning libraries.