Comprendre les mathématiques d'AdaGrad et d'AdaDelta

8

J'ai construit des modèles pour un projet, mais je ne peux pas me concentrer sur les mathématiques des algorithmes Adagrad et Adadelta.

Je comprends le fonctionnement de la descente en gradient de vanille et j'ai écrit du code pour le faire fonctionner avec succès.

Je serais reconnaissant si quelqu'un m'expliquait ces deux choses ou fournissait des ressources pour les comprendre.

Malay Hazarika
la source
1
Bonne explication dans quora.com/…
mico

Réponses:

6

Concernant les ressources:



Voici quelques citations centrales d' ADADELTA: Une méthode de taux d'apprentissage adaptatif , ainsi que quelques exemples et de courtes explications:

ADAGRAD

La règle de mise à jour pour ADAGRAD est la suivante:

ΔXt=-ητ=1tgτ2gt(5)
Ici, le dénominateur calcule la l2norme de tous les gradients précédents sur une base par dimension et η est un taux d'apprentissage global partagé par toutes les dimensions.
Bien qu'il existe un taux d'apprentissage global réglé manuellement, chaque dimension a son propre taux dynamique.

C'est-à-dire si les gradients des trois premières étapes sont g1=(une1b1c1),g2=(une2b2c2),g3=(une3b3c3), puis:

ΔX3=-ητ=13gτ2g3=-η(une12+une22+une32b12+b22+b32c12+c22+c32)(une3b3c3)ΔX3=-(ηune12+une22+une32une3ηb12+b22+b32b3ηc12+c22+c32c3)
Ici, il est plus facile de voir que chaque dimension a son propre taux d'apprentissage dynamique, comme promis.

Problèmes d'ADAGRAD que ADADELTA essaie de contrer

L'idée présentée dans cet article est dérivée d'ADAGRAD afin d'améliorer les deux principaux inconvénients de la méthode: 1) la décroissance continue des taux d'apprentissage tout au long de la formation, et 2) la nécessité d'un taux d'apprentissage global sélectionné manuellement.

Le deuxième inconvénient est assez explicite.

Voici un exemple lorsque le premier inconvénient est un problème:
considérons un cas dans lequel la valeur absolue de chaque composant deg2est beaucoup plus grande que la valeur absolue de la composante respective du gradient dans toute autre étape.
Pour toutet>2, il considère que chaque composant de τ=1tgτ2 est supérieure à la valeur absolue de la composante respective de g2. Mais la valeur absolue de chaque composant deg2 est beaucoup plus grande que la valeur absolue de la composante respective de gt, et donc ΔXtest très petit.
De plus, au fur et à mesure que l'algorithme progresse, il se rapproche d'un minimum, donc le gradient devient plus petit, et ainsiΔXtdevient de plus en plus petit.
Ainsi, il se pourrait que l'algorithme s'arrête pratiquement avant d'atteindre un minimum.

ADADELTA

Au lieu de considérer tous les gradients qui ont été calculés, ADADELTA ne considère que le dernier w dégradés.

Depuis le stockage wles gradients carrés précédents sont inefficaces, nos méthodes implémentent cette accumulation comme une moyenne exponentiellement décroissante des gradients carrés. Supposons à tempst cette moyenne courante est E[g2]t on calcule ensuite:

E[g2]t=ρE[g2]t-1+(1-ρ)gt2(8)
ρest une constante de décroissance [...]. Puisque nous avons besoin de la racine carrée de cette quantité dans les mises à jour des paramètres, cela devient effectivement leRMS des gradients carrés précédents jusqu'à temps t:
RMS[g]t=E[g2]t+ϵ(9)
où une constante ϵ est ajouté pour mieux conditionner le dénominateur

(RMSsignifie Root Mean Square .)

De même:

E[ΔX2]t-1=ρE[ΔX2]t-2+(1-ρ)ΔXt-12
RMS[ΔX]t-1=E[ΔX2]t-1+ϵ
Et enfin:

[...] approximatif ΔXt en calculant la décomposition exponentielle RMS sur une fenêtre de taille w des précédents ΔX pour donner la méthode ADADELTA:

ΔXt=-RMS[ΔX]t-1RMS[g]tgt(14)
où la même constante ϵ est ajouté au numérateur RMSainsi que. Cette constante sert à la fois à démarrer la première itération oùΔX0=0et pour garantir que des progrès continuent d'être réalisés même si les mises à jour précédentes deviennent petites.
[...]
Le numérateur agit comme un terme d'accélération, accumulant les gradients précédents sur une fenêtre de temps [...]

C'est-à-dire si le gradient à l'étape r est gr=(unerbrcr) et ΔXr=(jerjrkr), puis:

ΔXt=-RMS[ΔX]t-1RMS[g]tgt=-E[ΔX2]t-1+ϵE[g2]t+ϵgt=-ρE[ΔX2]t-2+(1-ρ)ΔXt-12+ϵρE[g2]t-1+(1-ρ)gt2+ϵgt=-ρ(ρE[ΔX2]t-3+(1-ρ)ΔXt-22)+(1-ρ)ΔXt-12+ϵρ(ρE[g2]t-2+(1-ρ)gt-12)+(1-ρ)gt2+ϵgt=-ρ2E[ΔX2]t-3+p1(1-ρ)ΔXt-22+p0(1-ρ)ΔXt-12+ϵρ2E[g2]t-2+p1(1-ρ)gt-12+p0(1-ρ)gt2+ϵgt=-ρt-1E[ΔX2]0+r=1t-1ρt-1-r(1-ρ)ΔXr2+ϵρt-1E[g2]1+r=2tρt-r(1-ρ)gr2+ϵgt

ρ est une constante de décroissance, donc nous la choisissons de telle sorte que ρ(0,1) (typiquement ρ0,9).
Par conséquent, en multipliant par une puissance élevée deρentraîne un très petit nombre.
Laisserw être l'exposant le plus bas tel que nous considérons le produit de la multiplication des valeurs sensées par ρwnégligeable.
Maintenant, nous pouvons approximerΔXt en supprimant des termes négligeables:

ΔXt-r=t-wt-1ρt-1-r(1-ρ)ΔXr2+ϵr=t+1-wtρt-r(1-ρ)gr2+ϵgt=-r=t-wt-1ρt-1-r(1-ρ)(jer2jr2kr2)+ϵr=t+1-wtρt-r(1-ρ)(uner2br2cr2)+ϵ(unetbtct)ΔXt-(r=t-wt-1ρt-1-r(1-ρ)jer2+ϵr=t+1-wtρt-r(1-ρ)uner2+ϵunetr=t-wt-1ρt-1-r(1-ρ)jr2+ϵr=t+1-wtρt-r(1-ρ)br2+ϵbtr=t-wt-1ρt-1-r(1-ρ)kr2+ϵr=t+1-wtρt-r(1-ρ)cr2+ϵct)
Oren Milman
la source
1

De quora, vous trouverez un guide plus complet, mais les idées principales sont qu'AdaGrad essaie de balancer ces problèmes dans la sélection du taux d'apprentissage du gradient dans l'apprentissage automatique:

1 Sélection manuelle du taux d'apprentissage η.

2 Le vecteur de gradient gt est mis à l'échelle uniformément par un taux d'apprentissage scalaire η.

3 Le taux d'apprentissage η reste constant tout au long du processus d'apprentissage.

Il résout les problèmes 2 et 3 simplement en divisant chaque composante de gradient actuelle par une norme L2 des gradients observés passés pour cette composante particulière.

Il présente en soi les problèmes suivants:

1 Taux d'apprentissage en décroissance continue η.

2 Sélection manuelle du taux d'apprentissage η.

AdaDelta résout le problème 1 d'AdaGrad en additionnant les gradients uniquement dans une certaine fenêtre W.

La solution de la préoccupation 2 concerne l'inadéquation des unités de gradient et donc

le processus d'accumulation proprement dit est mis en œuvre en utilisant un concept de momentum.

Le dernier calcul nécessite une compréhension de la théorie de l'impulsion et il y a été brièvement expliqué dans l'article.

Mon idée était de donner les principales causes de ce qui était prévu, peut-être que cela facilite la lecture.

mico
la source