Une méthodologie pour développer un produit logiciel pour trouver les raisons des changements dans les tendances des données. Descente de gradient stochastique. Options de mise en œuvre

Descente de dégradé- l'algorithme d'apprentissage le plus utilisé, il est utilisé dans presque tous les modèles. La descente de gradient est essentiellement la façon dont les modèles sont formés. Sans GS, l’apprentissage automatique ne serait pas là où il est aujourd’hui. La méthode de descente de gradient, avec quelques modifications, est largement utilisée pour l’apprentissage et l’apprentissage profond et est connue sous le nom d’erreurs.

Dans cet article, vous trouverez une explication de la descente de pente avec un peu de mathématiques. Résumé:

• La signification du GS est une explication de l’ensemble de l’algorithme ;
• Diverses variantes de l'algorithme ;
• Implémentation du code : écriture de code en Phyton.

Qu'est-ce que la descente de gradient

La descente de gradient est une méthode permettant de trouver la valeur minimale d'une fonction de perte (il existe de nombreux types de cette fonction). Minimiser une fonction signifie trouver la vallée la plus profonde de cette fonction. Gardez à l’esprit que la fonction est utilisée pour contrôler l’erreur dans les prédictions du modèle d’apprentissage automatique. Trouver le minimum signifie obtenir la plus petite erreur possible ou augmenter la précision du modèle. Nous augmentons la précision en itérant sur l'ensemble de données d'entraînement tout en ajustant les paramètres de notre modèle (poids et biais).

Une descente de gradient est donc nécessaire pour minimiser la fonction de perte.

L'essence de l'algorithme est le processus permettant d'obtenir la plus petite valeur d'erreur. De même, cela peut être assimilé à une descente dans une dépression pour tenter de trouver de l'or au fond du ravin (valeur d'erreur la plus faible).

Trouver le minimum d'une fonction

Ensuite, pour trouver l'erreur la plus faible (vallée la plus profonde) dans la fonction de perte (par rapport à un poids), vous devez ajuster les paramètres du modèle. Comment les mettre en place ? L’analyse mathématique y contribuera. Grâce à l'analyse, on sait que la pente du graphique d'une fonction est la dérivée de la fonction par rapport à la variable. Cette pente pointe toujours vers la dépression la plus proche !

Sur la figure, nous voyons un graphique de la fonction de perte (nommée « Erreur » avec le symbole « J ») avec un seul poids. Maintenant, si nous calculons la pente (appelons-la dJ/dw) de la fonction de perte par rapport à un poids, nous obtiendrons la direction dans laquelle nous devons nous déplacer pour atteindre les minima locaux. Imaginons pour l'instant que notre modèle n'ait qu'un seul poids.

Fonction de perte

Important: Au fur et à mesure que nous parcourons toutes les données d'entraînement, nous continuons à ajouter des valeurs dJ/dw pour chaque poids. Puisque la perte dépend de l’exemple de formation, dJ/dw continue également de changer. Nous divisons ensuite les valeurs collectées par le nombre d'exemples de formation pour obtenir la moyenne. Nous utilisons ensuite cette moyenne (de chaque poids) pour ajuster chaque poids.

A noter également : La fonction de perte est destinée à suivre l'erreur avec chaque exemple d'entraînement, tandis que la dérivée de la fonction de poids unique relatif est l'endroit où le poids doit être déplacé pour le minimiser pour cet exemple d'entraînement. Vous pouvez créer des modèles même sans utiliser la fonction de perte. Mais vous devrez utiliser la dérivée par rapport à chaque poids (dJ/dw).

Maintenant que nous avons déterminé la direction dans laquelle nous devons pousser le poids, nous devons comprendre comment le faire. Nous utilisons ici le coefficient de taux d'apprentissage, on l'appelle un hyper-paramètre. Un hyper-paramètre est une valeur requise par votre modèle dont nous n'avons en réalité qu'une vague idée. Généralement, ces valeurs peuvent être apprises par essais et erreurs. Ce n’est pas le cas ici : il y en a un pour tous les hyper-paramètres. Le facteur de taux d'apprentissage peut être considéré comme un « pas dans la bonne direction », où la direction vient de dJ/dw.

Il s’agissait d’une fonction de perte construite sur un seul poids. Dans le modèle réel, nous faisons tout ce qui est indiqué ci-dessus pour tous les poids, en passant en revue tous les exemples d'entraînement. Même dans un modèle d'apprentissage automatique relativement petit, vous aurez plus de 1 ou 2 pondérations. Cela rend la visualisation difficile car le graphique aura des dimensions que l’esprit ne peut pas imaginer.

En savoir plus sur les dégradés

Outre la fonction de perte, la descente de gradient nécessite également un gradient qui est dJ/dw (la dérivée de la fonction de perte par rapport à un poids, effectuée pour tous les poids). dJ/dw dépend de votre choix de fonction de perte. La fonction de perte la plus courante est l’erreur quadratique moyenne.

La dérivée de cette fonction par rapport à n'importe quel poids (cette formule montre le calcul du gradient pour) :

Ce sont toutes les mathématiques en GS. En regardant cela, nous pouvons dire que, par essence, le GS ne contient pas beaucoup de mathématiques. Les seules mathématiques qu'il contient sont la multiplication et la division, auxquelles nous reviendrons. Cela signifie que votre choix de fonction affectera le calcul du gradient de chaque poids.

Facteur de taux d'apprentissage

Tout ce qui est écrit ci-dessus est dans le manuel. Vous pouvez ouvrir n'importe quel livre sur la descente de gradient, la même chose y sera écrite. Des formules de gradient pour chaque fonction de perte peuvent être trouvées sur Internet, sans savoir comment les dériver soi-même.

Cependant, le problème de la plupart des modèles est le taux d’apprentissage. Regardons l'expression mise à jour pour chaque poids (j va de 0 au nombre de poids, et Theta-j est le jème poids dans le vecteur de poids, k va de 0 au nombre de biais, où B-k est le kème biais dans le vecteur déplacement). Ici, alpha est le coefficient du taux d'apprentissage. À partir de là, nous pouvons dire que nous calculons dJ/dTheta-j (le gradient du poids de Theta-j), puis la taille du pas alpha dans cette direction. On descend donc la pente. Pour mettre à jour le décalage, remplacez Theta-j par B-k.

Si cette taille de pas alpha est trop grande, nous dépasserons le minimum : c'est-à-dire que nous manquerons le minimum. Si alpha est trop petit, nous utilisons trop d'itérations pour arriver au minimum. L'alpha devrait donc être approprié.

Utiliser la descente de dégradé

Eh bien, c'est tout. C'est tout ce que vous devez savoir sur la descente de pente. Résumons tout en pseudocode.

Remarque : Les échelles ici sont représentées sous forme de vecteurs. Dans les modèles plus grands, il s'agira probablement de matrices.

De i = 0 à « nombre d’exemples de formation »

1. Calculez le gradient de la fonction de perte pour le i-ème exemple d'entraînement pour chaque poids et biais. Vous disposez maintenant d'un vecteur rempli de dégradés pour chaque poids et d'une variable contenant le gradient de biais.

2. Ajoutez les gradients des poids calculés pour un vecteur cumulatif distinct qui, après avoir parcouru chaque exemple d'entraînement, doit contenir la somme des gradients de chaque poids sur plusieurs itérations.

3. Comme pour les échelles, ajoutez un gradient de biais à la variable cumulative.

Maintenant, APRÈS avoir parcouru tous les exemples de formation, procédez comme suit :

1. Divisez les variables de poids et de biais cumulés par le nombre d'exemples de formation. Cela nous donnera les gradients moyens pour tous les poids et le gradient moyen pour le biais. Nous les appellerons batteries mises à jour (RA).

2. Ensuite, à l’aide de la formule ci-dessous, mettez à jour tous les poids et biais. Au lieu de dJ / dTheta-j, vous remplacerez OA (accumulateur mis à jour) par les poids et OA par le biais. Faites de même pour le décalage.

Ce n’était qu’une itération de descente de gradient.

Répétez ce processus du début à la fin pendant plusieurs itérations. Cela signifie que pour la 1ère itération du GS, vous parcourez tous les exemples de formation, calculez les gradients, puis mettez à jour les poids et les biais. Ensuite, vous faites cela pour un certain nombre d'itérations du HS.

Différents types de descente de pente

Il existe 3 options pour la descente de pente :

1. Mini-lot: Ici, au lieu de parcourir tous les exemples de formation et avec chaque itération effectuant des calculs sur un seul exemple de formation, nous traitons n exemples de formation à la fois. Ce choix convient aux très grands ensembles de données.

2.Descente de gradient stochastique: Dans ce cas, au lieu d'utiliser et de parcourir chaque exemple de formation, nous UTILISONS JUSTE UNE FOIS. Il y a quelques points à noter :

• À chaque itération du GS, vous devez mélanger l'ensemble d'entraînement et sélectionner un exemple d'entraînement aléatoire.
• Puisque vous n'utilisez qu'un seul exemple de formation, votre chemin vers les minima locaux sera très bruyant, comme une personne ivre qui a beaucoup bu.

3. série GS: C'est ce qui est écrit dans les sections précédentes. Cycle sur chaque exemple d’apprentissage.

Image comparant 3 hits aux minimums locaux

Exemple de code en python

Applicable à la série GS, voici à quoi ressemblera un bloc de code de formation en Python.

Def train(X, y, W, B, alpha, max_iters) : """ Effectue GD sur tous les exemples d'entraînement, X : ensemble de données d'entraînement, y : étiquettes pour les données d'entraînement, W : vecteur de poids, B : variable de biais, alpha : Le taux d'apprentissage, max_iters : Itérations GD maximales """ dW = 0 # Accumulateur de gradient de poids dB = 0 # Accumulateur de gradient de biais m = X.shape # No. d'exemples d'entraînement pour i dans range(max_iters) : dW = 0 # Réinitialisation des accumulateurs dB = 0 pour j dans range(m) : # 1. Itérer sur tous les exemples, # 2. Calculer les gradients des poids et des biais dans w_grad et b_grad, # 3. Mettre à jour dW en ajoutant w_grad et dB en ajoutant b_grad, W = W - alpha * (dW/m) # Mettre à jour les poids B = B - alpha * (dB/m) # Mettre à jour le retour de biais W, B # Renvoie les poids et biais mis à jour.

C'est ça. Vous devriez maintenant avoir une bonne compréhension de ce qu’est la descente de gradient.

Où f i – fonction calculée sur le i-ième lot, i est sélectionné au hasard ;

L'étape d'apprentissage est un hyperparamètre ; si les valeurs sont trop grandes, l'algorithme d'apprentissage divergera ; si les valeurs sont trop petites, il convergera lentement.

Descente de gradient stochastique avec inertie

Dans la méthode de descente de gradient stochastique, il n’est pas rare que le gradient change dans une large mesure à chaque itération. Cela est dû au fait que la fonctionnalité est calculée sur diverses données, qui peuvent différer considérablement. Ce changement peut être lissé si nous utilisons les gradients calculés lors des itérations précédentes et mis à l'échelle par l'hyperparamètre d'inertie μ :

	(14)
	(15)

Comme vous pouvez le deviner, l'hyperparamètre d'inertie μ porte ce nom en raison du fait que, comme la force d'inertie dite newtonienne, c'est-à-dire contre-force, « résiste » aux changements de pente et atténue les changements de coefficients de pondération tout au long de l’entraînement. Cet algorithme d'apprentissage est appelé descente de gradient stochastique avec impulsion ou SGDM (descente de gradient stochastique avec impulsion).

Méthode de gradient adaptatif

La méthode du gradient adaptatif (Adagrad – de l'anglais « adaptive gradient algorithm ») est basée sur l'idée de mise à l'échelle. Il redimensionne le taux d'apprentissage pour chaque paramètre réglable individuellement, tout en prenant en compte l'historique de tous les gradients passés pour ce paramètre. Pour ce faire, chaque élément de dégradé est divisé par la racine carrée de la somme des carrés des éléments de dégradé correspondants précédents. Cette approche réduit efficacement le taux d'apprentissage pour les poids qui ont une valeur de gradient élevée, et réduit également le taux d'apprentissage pour tous les paramètres au fil du temps, car la somme des carrés augmente régulièrement pour tous les paramètres à chaque itération. Lors de la définition d'un paramètre de mise à l'échelle initial nul g = 0, la formule de recalcul des coefficients de pondération a la forme (la division est effectuée élément par élément).

Dans le cadre de mes devoirs, on m'a demandé de mettre en œuvre une descente de gradient stochastique pour résoudre un problème de régression linéaire (même si je n'ai que 200 exemples de formation). Mon problème est que la descente de gradient stochastique converge trop doucement, presque de la même manière que la descente de gradient par lots, ce qui m'amène à ma question : pourquoi cela semble-t-il si fluide, étant donné qu'il est généralement beaucoup plus bruyant. Est-ce parce que je ne l'utilise qu'avec 200 exemples ?

MSE avec poids issus de la descente de gradient stochastique : 2,78441258841

MSE avec poids issus de la descente de gradient : 2,78412631451 (identique au MSE avec poids issus de l'équation normale)

Def mserror(y, y_pred) : n = y.size diff = y - y_pred diff_squared = diff ** 2 av_er = float(sum(diff_squared))/n return av_er

Def Linear_prediction(X, w) : return dot(X,np.transpose(w))

Def gradient_descent_step(X, y, w, eta) : n = X.shape grad = (2.0/n) * sum(np.transpose(X) * (linear_prediction(X,w) - y), axis = 1) return w - eta * diplômé

Def stochastic_gradient_step(X, y, w, train_ind, eta) : n = X.shape grad = (2.0/n) * np.transpose(X) * (linear_prediction(X,w) - y) return w - eta * grad

Def gradient_descent(X, y, w_init, eta, max_iter) : w = w_init erreurs = erreurs.append(mserror(y, Linear_prediction(X,w))) pour i dans la plage (max_iter) : w = gradient_descent_step(X, y , w, eta) erreurs.append(mserror(y, Linear_prediction(X,w))) return w, erreurs

Def stochastic_gradient_descent(X, y, w_init, eta, max_iter) : n = X.shape w = w_init erreurs = erreurs.append(mserror(y, Linear_prediction(X,w))) pour i dans la plage (max_iter) : random_ind = np.random.randint(n) w = stochastic_gradient_step(X, y, w, random_ind, eta) erreurs.append(mserror(y, Linear_prediction(X,w))) return w, erreurs

1 réponse

Il n’y a rien d’inhabituel dans votre emploi du temps. Il convient également de noter que votre méthode batch nécessite moins d'itérations pour converger.

Vous pouvez laisser les tracés SGD du réseau neuronal avoir votre propre vision de ce à quoi devrait ressembler SGD. La plupart des réseaux de neurones sont des modèles beaucoup plus complexes (difficiles à optimiser) qui fonctionnent sur des problèmes plus complexes. Cela favorise le « irrégularité » auquel vous vous attendez.

La régression linéaire est un problème simple et a une solution convexe. Cela signifie que toute mesure permettant de réduire notre taux d’erreur est garantie comme un pas vers la meilleure solution possible. C'est beaucoup plus complexe que les réseaux de neurones, et c'est en partie pourquoi vous constatez une diminution progressive des erreurs. C'est pourquoi vous voyez un MSE presque identique. Le SGD et le package convergeront vers la solution exacte.

SVM

Machine à vecteurs de support(Anglais SVM, support vector machine) - un ensemble d'algorithmes d'apprentissage supervisé similaires utilisés pour les problèmes de classification et d'analyse de régression. Appartient à la famille des classificateurs linéaires et peut également être considéré comme un cas particulier de régularisation de Tikhonov. La propriété particulière de la machine à vecteurs de support est de réduire continuellement l'erreur de classification empirique et d'augmenter l'écart. La méthode est donc également connue sous le nom de méthode de classificateur d'écart maximum.

L'idée principale de la méthode est de transférer les vecteurs d'origine dans un espace de dimension supérieure et de rechercher un hyperplan séparateur avec un écart maximum dans cet espace. Deux hyperplans parallèles sont construits de part et d'autre de l'hyperplan séparant nos classes. L'hyperplan séparateur sera l'hyperplan qui maximise la distance à deux hyperplans parallèles. L'algorithme fonctionne sous l'hypothèse que plus la différence ou la distance entre ces hyperplans parallèles est grande, plus l'erreur moyenne du classificateur sera petite.

Souvent, dans les algorithmes d’apprentissage automatique, il est nécessaire de classer les données. Chaque objet de données est représenté sous forme de vecteur (point) dans un espace à dimensions (une séquence de p nombres). Chacun de ces points appartient à une seule des deux classes. Nous souhaitons savoir si nous pouvons séparer les points par une dimension hyperplane. Il s'agit d'un cas typique de séparabilité linéaire. Il peut y avoir de nombreux hyperplans de ce type. Il est donc naturel de croire que maximiser l’écart entre les classes conduit à une classification plus sûre. Autrement dit, pouvons-nous trouver un hyperplan tel que la distance entre celui-ci et le point le plus proche soit maximale. Cela signifierait que la distance entre les deux points les plus proches situés sur les côtés opposés de l'hyperplan est maximale. Si un tel hyperplan existe, c’est alors qu’il nous intéressera le plus ; on l'appelle hyperplan de séparation optimal, et le classificateur linéaire correspondant est appelé classificateur de séparation optimal.

Formellement, le problème peut être décrit comme suit.

Nous supposons que les points ont la forme : , où prend la valeur 1 ou ?1, selon la classe à laquelle appartient le point. Chacun est un vecteur réel à dimensions, généralement normalisé par les valeurs ou. Si les points ne sont pas normalisés, alors un point présentant de grands écarts par rapport aux coordonnées moyennes du point influencera trop le classificateur. Nous pouvons considérer cela comme une collection de formation dans laquelle chaque élément se voit déjà attribuer la classe à laquelle il appartient. Nous voulons que l’algorithme de la machine à vecteurs de support les classe de la même manière. Pour ce faire, on construit un hyperplan séparateur, qui a la forme :

Un vecteur est perpendiculaire à l’hyperplan séparateur. Le paramètre est égal en valeur absolue à la distance de l'hyperplan à l'origine. Si le paramètre est nul, l'hyperplan passe par l'origine, ce qui contraint la solution.

Puisque nous nous intéressons à la séparation optimale, nous nous intéressons aux vecteurs supports et aux hyperplans parallèles à l’optimal et les plus proches des vecteurs supports des deux classes. On peut montrer que ces hyperplans parallèles peuvent être décrits par les équations suivantes (jusqu'à normalisation).

Si l'ensemble d'apprentissage est linéairement séparable, nous pouvons alors choisir des hyperplans tels qu'aucun point de l'ensemble d'apprentissage ne se trouve entre eux, puis maximiser la distance entre les hyperplans. La largeur de la bande entre eux est facile à trouver à partir de considérations géométriques ; elle est égale, notre tâche est donc de la minimiser. Pour exclure tous les points de la bande, il faut s'assurer pour autant

Cela peut également s’écrire :

Dans le cas de séparabilité linéaire des classes, le problème de la construction d'un hyperplan séparateur optimal se réduit à la minimisation sous la condition (1). Il s’agit d’un problème d’optimisation quadratique de la forme :

Selon le théorème de Kuhn-Tucker, ce problème équivaut au double problème de trouver le point selle de la fonction de Lagrange.

Où est un vecteur de variables doubles

Réduisons ce problème à un problème de programmation quadratique équivalent contenant uniquement des variables doubles :

Disons que nous avons résolu ce problème, alors nous pouvons le trouver en utilisant les formules :

En conséquence, l’algorithme de classification peut s’écrire :

Dans ce cas, la sommation n'a pas lieu sur l'ensemble de l'échantillon, mais uniquement sur les vecteurs supports pour lesquels

Dans le cas d'inséparabilité linéaire des classes, pour que l'algorithme fonctionne, on lui permet de commettre des erreurs sur l'ensemble d'apprentissage. Introduisons un ensemble de variables supplémentaires caractérisant l'ampleur de l'erreur sur les objets. Prenons (2) comme point de départ, assouplissons les restrictions d'inégalité et introduisons également une pénalité pour l'erreur totale dans la fonctionnelle minimisée :

Le coefficient est un paramètre de réglage de méthode qui vous permet d'ajuster la relation entre maximiser la largeur de la bande de séparation et minimiser l'erreur totale.

De même, en utilisant le théorème de Kuhn-Tucker, nous réduisons le problème à trouver le point selle de la fonction de Lagrange :

Par analogie, on réduit ce problème à un problème équivalent :

En pratique, pour construire une machine à vecteurs supports, ils résolvent précisément ce problème, et non (3), puisque dans le cas général il n'est pas possible de garantir la séparabilité linéaire des points en deux classes. Cette version de l'algorithme est appelée algorithme SVM à marge souple, tandis que dans le cas linéairement séparable, ils l'appellent SVM à marge dure.

Pour l'algorithme de classification, la formule (4) est retenue, à la seule différence que désormais non seulement les objets de référence, mais aussi les objets intrus ont des valeurs non nulles. Dans un certain sens, cela constitue un inconvénient, car les contrevenants sont souvent les émissions sonores, et une règle décisive basée sur celles-ci est en fait basée sur le bruit.

La constante est généralement choisie selon le critère de contrôle glissant. C'est une méthode qui prend du temps, car le problème doit être résolu à nouveau pour chaque valeur.

S’il y a des raisons de croire que l’échantillon est presque linéairement séparable et que seuls les objets aberrants sont classés de manière incorrecte, un filtrage des valeurs aberrantes peut être appliqué. Premièrement, le problème est résolu pour un certain C et une petite proportion d’objets présentant la plus grande erreur est supprimée de l’échantillon. Après cela, le problème est à nouveau résolu en utilisant un échantillon tronqué. Il peut être nécessaire d'effectuer plusieurs itérations de ce type jusqu'à ce que les objets restants soient linéairement séparables.

L'algorithme de construction d'un hyperplan de séparation optimal, proposé en 1963 par Vladimir Vapnik et Alexey Chervonenkis, est un algorithme de classification linéaire. Cependant, en 1992, Bernhard Boser, Isabel Guyon et Vapnik ont ​​proposé un moyen de créer un classificateur non linéaire basé sur la transition des produits scalaires vers des noyaux arbitraires, ce qu'on appelle l'astuce du noyau (proposée pour la première fois par M.A. Aizerman, E.M. Bravermann et L.V. . Rozonoer pour la méthode des fonctions potentielles), qui permet la construction de séparateurs non linéaires. L'algorithme résultant est extrêmement similaire à l'algorithme de classification linéaire, la seule différence étant que chaque produit scalaire dans les formules ci-dessus est remplacé par une fonction de noyau non linéaire (un produit scalaire dans un espace de dimension supérieure). Un hyperplan de séparation optimal peut déjà exister dans cet espace. Puisque la dimension de l'espace résultant peut être supérieure à la dimension de l'espace d'origine, la transformation comparant les produits scalaires sera non linéaire, ce qui signifie que la fonction correspondant à l'hyperplan de séparation optimal dans l'espace d'origine sera également non linéaire.

Il convient de noter que si l'espace d'origine a une dimension suffisamment élevée, on peut alors espérer que l'échantillon qu'il contient sera linéairement séparable.

Les noyaux les plus courants :

1. Noyau linéaire :

2. Polynôme (homogène) :

Fonction 3.RBF :

4. Sigmoïde :

Dans le cadre de la tâche qui nous est proposée, nous utiliserons un noyau homogène linéaire. Ce noyau a montré d'excellents résultats dans les tâches de classification de documents, bien que par rapport au classificateur Naive Bayes, la formation de ce classificateur prend une période de temps relativement longue. Le fonctionnement de tous les autres noyaux de cette liste a également été vérifié et il a été révélé que leur formation prend beaucoup plus de temps, sans apporter d'amélioration particulière dans la précision de la classification.

Pour accélérer la formation, nous utiliserons une méthode appelée Stochastic Gradient Descent, qui nous permet d'accélérer considérablement la formation du classificateur sans sacrifier une grande partie de sa précision.

Descente de gradient stochastique

Les méthodes de gradient constituent une vaste classe d'algorithmes d'optimisation utilisés non seulement dans l'apprentissage automatique. Ici, l'approche gradient sera considérée comme un moyen de sélectionner un vecteur de poids synaptiques dans un classificateur linéaire. Soit la dépendance cible connue uniquement sur les objets de l'ensemble d'apprentissage :

Trouvons un algorithme qui se rapproche de la dépendance. Dans le cas d'un classificateur linéaire, l'algorithme recherché a la forme :

où joue le rôle de la fonction d'activation (dans le cas le plus simple qu'on puisse mettre).

Selon le principe de minimisation du risque empirique, il suffit de résoudre le problème d'optimisation :

Où est la fonction de perte donnée.

Pour minimiser, nous appliquons la méthode de descente de gradient. Il s'agit d'un algorithme pas à pas, à chaque itération dont le vecteur évolue dans le sens de la plus grande diminution de la fonctionnelle (c'est-à-dire dans le sens de l'antigradient) :

Où est un paramètre positif appelé taux d'apprentissage.

Il existe 2 approches principales pour mettre en œuvre la descente de gradient :

1. Lot, lorsqu'à chaque itération l'échantillon d'apprentissage est visualisé dans son intégralité, et seulement après cela, il est modifié. Cela nécessite des coûts de calcul importants.

2. Stochastique (stochastique/en ligne), lorsqu'à chaque itération de l'algorithme, un seul objet est sélectionné d'une manière (aléatoire) dans l'échantillon d'apprentissage. Ainsi, le vecteur est ajusté à chaque objet nouvellement sélectionné.

Vous pouvez représenter l'algorithme de descente de gradient stochastique en pseudocode comme suit :

· - échantillon de formation

· - rythme d'apprentissage

· - paramètre de lissage fonctionnel

1. Vecteur de poids

1) Initialiser les poids

2) Initialiser l'évaluation fonctionnelle actuelle :

3) Répétez :

1. Sélectionnez un objet au hasard

2. Calculez la valeur de sortie de l'algorithme et l'erreur :

3. Faites un pas de descente en pente

4. Évaluez la valeur de la fonctionnalité :

4) Jusqu'à ce que la valeur se stabilise et/ou que les poids cessent de changer.

Le principal avantage de SGD peut être appelé sa rapidité d'apprentissage sur des données trop volumineuses. C'est précisément ce qui nous intéresse dans le cadre de la tâche qui nous est confiée, car le volume de données d'entrée sera très important. Dans le même temps, l'algorithme SGD, contrairement à la descente de gradient par lots classique, offre une précision de classification légèrement inférieure. De plus, l'algorithme SGD n'est pas applicable lors de la formation d'une machine à vecteurs de support avec un noyau non linéaire.

Conclusions

Dans le cadre du problème à résoudre, nous devrons utiliser l'algorithme de conversion des données sources TF-IDF, qui nous permettra d'augmenter le poids des événements rares et de réduire le poids des événements fréquents. Nous transférerons les données obtenues après la transformation vers des classificateurs adaptés à la résolution du problème auquel nous sommes confrontés, à savoir : Naive Bayes Classifier ou Support Vector Machine with a Linear Kernel, entraîné à l'aide de la méthode de descente de gradient stochastique. Nous testerons également l'efficacité d'une machine à vecteurs de support avec des noyaux non linéaires entraînés à l'aide de la méthode de descente de gradient par lots. Cependant, ce type de classificateur ne semble pas adapté à la tâche en raison du noyau trop complexe et de la tendance au surajustement, dans lequel le classificateur ne gère pas bien les données qui n'ont pas été utilisées pour entraîner le classificateur.

données de prétraitement de la machine logicielle

Ainsi, vous avez pour tâche de prédire une certaine valeur comme le coût d’une maison en fonction de sa taille. Ou le temps nécessaire à votre système pour traiter une demande. On ne sait jamais.

Vous avez décidé d'utiliser la régression linéaire et souhaitez maintenant trouver les coefficients auxquels la différence entre le prix prévu par votre modèle et le coût réel des maisons vendues sera minime. Pour ce faire, vous pouvez utiliser l'une de ces méthodes :

1. Descente de dégradé par lots
2. Descente de gradient stochastique
3. Équations normales
4. Méthode de Newton (méthode de Newton)

Aujourd'hui, nous allons parler de deux types de descente de pente.

Descente de dégradé

De toute façon, qu’est-ce que la descente de gradient ?

Imaginez une fonction complexe d'une variable. Il y a des hauts et des bas. En chaque point de cette fonction on peut prendre la dérivée :

La ligne verte montre qu'à ce stade la dérivée sera positive, la ligne rouge sera négative.

Sélectionnez n’importe quel point de la fonction. Vous voulez "descendre" au minimum le plus proche de ce point. Si la dérivée en votre point est positive (ligne verte), cela signifie que le minimum est « derrière » vous, et pour y descendre, vous devez soustraire de la coordonnée de votre point x la valeur de votre dérivé.

Si en votre point la dérivée est négative (ligne rouge), cela signifie que le minimum est « devant » devant vous, et pour y arriver, il faut, encore une fois, soustraire de la coordonnée x la valeur de votre dérivé. Sa valeur est négative, et donc, en soustrayant une valeur négative, vous augmenterez la coordonnée x.

Eh bien, pour que la descente ne soit pas douloureusement longue ou erronément rapide, multipliez la valeur de votre dérivée au point sélectionné par un coefficient.

Mais c'est tout pour le cas où la fonction dépend d'une seule coordonnée. Dans le cas de notre modèle de vente de maisons, la fonction valeur dépend de deux variables.

Vous pouvez considérer cette fonction comme une « tasse » dans l’espace 3D :

La dérivée des fonctions de plusieurs variables est appelée gradient. Un gradient est un vecteur avec une dimension du nombre de variables, dans lequel chaque élément du vecteur est une dérivée d'une variable.

Notre fonction de coût est :

Son gradient est noté et sera calculé à l'aide de la formule suivante :

Dans chaque dérivée partielle, nous la considérons comme fonction d'une variable. Nous considérons toutes les autres variables comme des constantes, par conséquent, leurs dérivées seront égales à zéro :

Après cela, nous mettons à jour chaque valeur en utilisant la formule :

Le paramètre s'appelle le taux d'apprentissage et détermine la rapidité avec laquelle nous passerons à la valeur minimale de la fonction. A chaque mise à jour des paramètres nous faisons un petit pas vers le minimum. Après cela, nous répétons la procédure. Dans le même temps, nous examinons dans quelle mesure la valeur de la fonction de coût a changé par rapport à l'étape précédente. Lorsque ce changement devient très faible (on marque le pas), on peut s'arrêter et considérer qu'on a atteint le point minimum.

C'est comme descendre une colline en direction d'une vallée voisine. La descente de gradient permet de trouver un minimum local, mais pas global. Cela signifie que s'il y a plusieurs points où votre fonction est minimale, la descente de gradient vous mènera à l'un d'eux - celui qui est le plus proche du point de départ, mais pas nécessairement la crevasse la plus profonde.

Avant la toute première étape, nous déterminons les paramètres de manière aléatoire, et la manière exacte dont nous les déterminons détermine à quel minimum nous tomberons :

Ici, entre parenthèses, il convient de noter que ce qui précède s'applique à la descente de gradient en général, mais ne s'applique pas à la descente de gradient spécifiquement pour la régression linéaire. La fonction de coût de régression linéaire est convexe et n'a qu'un seul minimum (pensez à une tasse 3D), donc la descente de gradient le trouvera toujours.

Plus vous vous rapprochez du minimum de la fonction de coût (plus la différence entre le prix prévu et le prix réel est faible), plus votre ligne droite décrit mieux vos données historiques :

Quand il n’y a pas beaucoup d’exemples historiques, tout va bien, mais quand il y en a des millions, pour chaque petit pas vers le minimum, il faut faire des millions de calculs, et cela peut prendre beaucoup de temps.

Une alternative à cela serait la descente de gradient stochastique - une méthode dans laquelle nous prenons un exemple et mettons à jour les valeurs en fonction uniquement de celui-ci. Ensuite, nous prenons l'exemple suivant et mettons à jour les paramètres en nous concentrant sur celui-ci. Et ainsi de suite. Cela conduit au fait que nous ne « descendons » pas toujours de la colline, parfois nous faisons un pas vers le haut ou sur le côté, mais tôt ou tard nous atteignons ce minimum et commençons à en faire le tour. Lorsque les valeurs commencent à nous convenir (atteindre la précision dont nous avons besoin), nous arrêtons la descente.

En pseudocode, la descente de gradient stochastique ressemble à ceci :

Jusqu'à ce que le changement de la fonction de coût soit faible : (

Pour j:= 1 à m (

Enfin, les caractéristiques de convergence de l'algorithme : la descente de gradient par lots converge toujours vers un minimum, à condition qu'une valeur suffisamment petite soit utilisée. La descente de gradient stochastique ne converge généralement pas vers un minimum, mais il existe des modifications qui permettent d'atteindre la convergence.