Tasas adaptativas

Optimizadores, episodio cuatro: tasas adaptativas. El momentum del episodio tres atacó el valle recordando gradientes. Hoy, la otra idea: que cada parámetro tenga su propio learning rate, ajustado solo según el tamaño de sus gradientes. Dos optimizadores: AdaGrad, adaptive gradient, y RMSProp, root mean square propagation. Los dos, a mano y contra PyTorch.

Parte 1 · Dividir por el tamaño del gradiente

En el valle, x necesitaba un paso grande e y uno chico. Un solo learning rate no puede darles los dos.

Cada coordenada, su propia escala

descenso en el valle: el primer paso

con $\eta = 0{,}5$: el mismo largo en las dos

AdaGrad: la suma de los cuadrados, por parámetro

El primer paso de descenso en el valle, con learning rate cero coma tres: delta, el cambio de los pesos, es menos eta por el gradiente. En el dibujo, y se mueve diez veces más que x. Idea: dividir cada componente del gradiente por su propio tamaño. El subíndice i es la coordenada, y las barras, el valor absoluto. Lo que queda es solo el signo, y las dos coordenadas avanzan eta: cero coma cinco. AdaGrad lo hace con memoria. Para cada parámetro guarda s sub i, la suma de los cuadrados de todos sus gradientes, y divide por la raíz. Theta son los pesos. Épsilon es diminuto, diez a la menos diez en PyTorch: evita dividir por cero. En el dibujo, la s de y acumulando tres gradientes.

AdaGrad a mano, contra torch.optim.Adagrad

La clase, con la misma forma que la de momentum. El estado ahora es s: la suma de los gradientes al cuadrado, coordenada por coordenada. El paso divide el gradiente por la raíz de s. Al lado, PyTorch, con learning rate cero coma cinco y los demás valores por defecto. Imprimimos el primer paso. El primer paso es cero coma cinco en x y menos cero coma cinco en y: igual largo, como prometía la cuenta. Después de cuarenta pasos, los dos terminan en menos cero coma seis cinco, cero. La diferencia máxima, una diezmillonésima: redondeo de float32.

class AdaGrad:
    def __init__(self, lr, eps=1e-10):
        self.lr, self.eps, self.s = lr, eps, 0.0
    def paso(self, p, g):
        self.s = self.s + g ** 2                     # suma de cuadrados
        return p - self.lr * g / (np.sqrt(self.s) + self.eps)

mano, p = AdaGrad(lr=0.5), np.array([-4.5, 1.5]); camino = [p]
w = torch.tensor([-4.5, 1.5], requires_grad=True)
opt = torch.optim.Adagrad([w], lr=0.5)
for t in range(40):
    p = mano.paso(p, grad(p)); camino.append(p)
    opt.zero_grad(); valle(w).backward(); opt.step()
print("primer paso:", (camino[1] - camino[0]).round(3))
print("mano: ", p.round(4), " torch:", w.detach().numpy().round(4))
print(f"diferencia máxima: {np.abs(p - w.detach().numpy()).max():.1e}")

primer paso: [ 0.5 -0.5]
mano:  [-0.6548  0.    ]  torch: [-0.6547  0.    ]
diferencia máxima: 1.3e-07

Momentum (ep. 3) contra AdaGrad

Cuarenta pasos cada uno. El momentum del episodio tres: baja, se pasa y vuelve, y la velocidad lo lleva por el fondo. AdaGrad: el primer paso sale en diagonal, porque x e y avanzan lo mismo. Sin rebotes, baja al fondo y sigue derecho hacia la estrella. Son dos remedios distintos para el mismo valle: momentum amortigua el rebote, AdaGrad iguala las escalas. Pero mirá cómo AdaGrad se frena al final: termina más lejos que momentum. Eso es la parte dos.

Duchi, Hazan y Singer, 2011 — Adaptive Subgradient Methods for Online Learning and Stochastic Optimization · fuente

η / √Σg² · «our procedures give frequently occurring features very low learning rates and infrequent features high learning rates»

AdaGrad sale de este paper de dos mil once, de John Duchi, Elad Hazan y Yoram Singer, en el Journal of Machine Learning Research. Su motivación no era el valle, sino los datos dispersos, como el texto: palabras que aparecen todo el tiempo y palabras raras que dicen mucho. Textual: sus procedimientos dan learning rates muy bajos a las features frecuentes y altos a las infrecuentes. Una feature que casi nunca aparece acumula poca s, y cuando aparece da un paso grande. Ellos lo describen como encontrar agujas en un pajar.

Parte 2 · La suma nunca baja

s solo crece. Aunque los gradientes no cambien, el paso se achica para siempre.

AdaGrad sobre una pendiente constante

El caso más simple donde se ve el problema. AdaGrad con learning rate uno, empezando en cero. Le pasamos siempre el mismo gradiente, cero coma cinco: una pendiente recta que nunca se termina. Imprimimos cuánto se movió en cada paso. Y cuánto lleva recorrido. Paso uno: se movió uno. Paso cuatro: cero coma cinco. Paso cien: cero coma uno. Paso mil: cero coma cero tres. El terreno es idéntico en todos los pasos, pero AdaGrad camina cada vez más lento. En mil pasos recorrió sesenta y uno coma ocho.

opt, w = AdaGrad(lr=1.0), 0.0
for t in range(1, 1001):
    nuevo = opt.paso(w, 0.5)            # pendiente constante: g = 0,5
    if t in (1, 4, 100, 1000):
        print(f"paso {t:4}: se movió {abs(nuevo - w):.4f}"
              f"   recorrido total {abs(nuevo):7.2f}")
    w = nuevo

paso    1: se movió 1.0000   recorrido total    1.00
paso    4: se movió 0.5000   recorrido total    2.78
paso  100: se movió 0.1000   recorrido total   18.59
paso 1000: se movió 0.0316   recorrido total   61.80

Por qué uno sobre raíz de t

t gradientes iguales sumados

el paso no depende de g, sí de t

medido: 61,8 en vez de 1000

Si el gradiente es siempre el mismo, g, después de t pasos la suma s vale t por g al cuadrado, y su raíz, raíz de t por el valor absoluto de g. En el dibujo, cuatro pasos con g cero coma cinco: s vale uno. El largo del paso es eta por g dividido eso: la g se cancela y queda eta sobre raíz de t. No depende del terreno, solo de cuántos pasos llevás. En el dibujo, los largos que imprimió el snippet. La suma de uno sobre raíz de t, hasta T, crece más o menos como dos raíz de T: para mil pasos, sesenta y tres. Medimos sesenta y uno coma ocho; con un paso fijo de uno habrían sido mil. En una red que entrena durante días, eso es frenar hasta casi parar.

Parte 3 · RMSProp: olvidar lo viejo

En vez de sumar todos los cuadrados, promediar los recientes. Así el divisor sube y baja con el terreno.

Un promedio que se olvida

promedio móvil exponencial de $g^2$

igual que AdaGrad, con $v$ en lugar de $s$

v arranca en cero: el primer paso es grande

RMSProp reemplaza la suma por un EMA, exponential moving average: promedio móvil exponencial. V es alfa por la v anterior más uno menos alfa por el gradiente al cuadrado, con alfa cero coma nueve. Desarmado como el momentum, es una suma con pesos que se apagan y en total pesan uno. En el dibujo, esos pesos. El paso es el de AdaGrad, con v en lugar de s. Como v es un promedio y no una suma, con gradientes constantes v se queda quieta y el paso no se achica. En el dibujo, paso cien: cero coma uno contra uno. Un detalle que vuelve en el episodio cinco: v arranca en cero, así que en el primer paso vale un décimo de g al cuadrado, y el paso es eta sobre raíz de cero coma uno, tres coma dieciséis veces eta. En el dibujo, tarda unos diez pasos en asentarse.

RMSProp a mano, contra torch.optim.RMSprop

La clase: el estado es v, y el paso lo actualiza con alfa y uno menos alfa. El paso divide por la raíz de v. Ojo con PyTorch: su alfa por defecto es cero coma nueve nueve, no el cero coma nueve de la clase de Hinton. Acá lo pasamos explícito, junto con épsilon diez a la menos ocho, que es el de PyTorch. Learning rate cero coma uno, cuarenta pasos en el valle. Y el primer paso. El primer paso es cero coma tres uno seis en cada coordenada: tres coma dieciséis veces el learning rate, como dice la cuenta. Mano y PyTorch terminan en menos cero coma seis siete seis tres, cero. Diferencia máxima, cuatro diezmillonésimas: redondeo.

Cada línea, su término:

• self.v = self.alpha * self.v → $v \leftarrow \alpha v + (1 - \alpha)\, g^2$ — el promedio móvil de $g^2$
• return p - self.lr * g / (np.sqrt(self.v) → $\theta \leftarrow \theta - \eta\, \frac{g}{\sqrt{v} + \varepsilon}$ — el paso
• torch.optim.RMSprop → $\alpha = 0{,}9 \text{ (PyTorch: } 0{,}99 \text{ por defecto)}$ — hay que pasarlo explícito
• primer paso → $|\Delta_1| = \frac{0{,}1}{\sqrt{0{,}1}} = 0{,}316$ — el primer paso, agrandado

class RMSProp:
    def __init__(self, lr, alpha=0.9, eps=1e-8):
        self.lr, self.alpha, self.eps, self.v = lr, alpha, eps, 0.0
    def paso(self, p, g):
        self.v = self.alpha * self.v + (1 - self.alpha) * g ** 2
        return p - self.lr * g / (np.sqrt(self.v) + self.eps)

mano, p = RMSProp(lr=0.1), np.array([-4.5, 1.5]); camino = [p]
w = torch.tensor([-4.5, 1.5], requires_grad=True)
opt = torch.optim.RMSprop([w], lr=0.1, alpha=0.9, eps=1e-8)
for t in range(40):
    p = mano.paso(p, grad(p)); camino.append(p)
    opt.zero_grad(); valle(w).backward(); opt.step()
print("primer paso:", (camino[1] - camino[0]).round(3))
print("mano: ", p.round(4), " torch:", w.detach().numpy().round(4))
print(f"diferencia máxima: {np.abs(p - w.detach().numpy()).max():.1e}")

primer paso: [ 0.316 -0.316]
mano:  [-0.6763  0.    ]  torch: [-0.6763  0.    ]
diferencia máxima: 4.5e-07

El largo del paso, AdaGrad contra RMSProp

Volvamos a la pendiente constante, ahora con las dos reglas lado a lado. AdaGrad suma. RMSProp promedia, con alfa cero coma nueve. Guardamos el largo de cada paso, con learning rate uno. AdaGrad: uno, cero coma siete uno, cero coma tres dos, cero coma uno. RMSProp: tres coma uno seis, dos coma dos nueve, uno coma dos cuatro, y en el paso cien, uno exacto. AdaGrad se frena para siempre; RMSProp arranca acelerado y se asienta en un paso fijo.

def pasos(regla, n=100, g=0.5):         # pendiente constante: g = 0,5
    s, v, largos = 0.0, 0.0, []
    for t in range(n):
        s = s + g ** 2                  # AdaGrad: suma
        v = 0.9 * v + 0.1 * g ** 2      # RMSProp: promedio móvil
        largos.append(g / np.sqrt(s) if regla == "AdaGrad" else g / np.sqrt(v))
    return np.array(largos)             # largo de cada paso, con lr = 1

for regla in ["AdaGrad", "RMSProp"]:
    l = pasos(regla)
    print(f"{regla:8}: pasos 1, 2, 10, 100 →",
          " ".join(f"{l[i]:.2f}" for i in (0, 1, 9, 99)))

AdaGrad : pasos 1, 2, 10, 100 → 1.00 0.71 0.32 0.10
RMSProp : pasos 1, 2, 10, 100 → 3.16 2.29 1.24 1.00

El largo de cada paso

Los primeros cuarenta pasos, con gradiente constante. AdaGrad: la curva uno sobre raíz de t, que baja rápido al principio y nunca deja de bajar. RMSProp: empieza arriba de tres, por el promedio que arranca en cero, y en unos veinte pasos se queda en uno, el largo que corresponde. Esa joroba del principio es lo que corrige Adam, adaptive moment estimation, en el episodio cinco.

Hinton, con Srivastava y Swersky — Neural Networks for Machine Learning, clase 6e · fuente

0,9 · MeanSquare + 0,1 · g² · «Dividing the gradient by sqrt(MeanSquare(w,t)) makes the learning work much better (Tijmen Tieleman, unpublished)»

RMSProp tiene una historia rara: no tiene paper. Apareció en las diapositivas de la clase seis e del curso en línea Neural Networks for Machine Learning, de Geoffrey Hinton, con Nitish Srivastava y Kevin Swersky. La diapositiva dice: guardar un promedio móvil del gradiente al cuadrado para cada peso, cero coma nueve el viejo más cero coma uno el nuevo. Y atribuye la mejora a Tijmen Tieleman, como trabajo no publicado. Por eso, cuando un paper usa RMSProp, cita esa clase.

AdaGrad contra RMSProp, mismo learning rate

Los dos con learning rate cero coma uno, cuarenta pasos. AdaGrad: los pasos se acortan tan rápido que a los cuarenta todavía no bajó al fondo del valle; está en menos tres coma cuatro, cero coma cinco siete. RMSProp: avanza en diagonal a paso casi constante, baja al fondo y llega a menos cero coma seis ocho. En el fondo, el gradiente en y casi desaparece, su promedio baja, y el divisor se ajusta.

Parte 4 · Inmunes a la escala

Una propiedad que explica por qué estos métodos se volvieron el default: no les importa en qué unidades está la pérdida.

Multiplicar la pérdida por cien

El mismo valle, multiplicado por una constante k. El mínimo y la forma son los mismos; solo cambian las unidades. SGD, stochastic gradient descent, resta el gradiente tal cual. AdaGrad lo divide por la raíz de la suma de sus cuadrados. Probamos k igual a uno y k igual a cien, con los learning rates de antes. SGD con k uno termina en menos cero coma tres siete nueve, como en el episodio uno. Con k cien, diverge: el gradiente es cien veces más grande y el learning rate quedó muy por encima del techo. AdaGrad termina exactamente en el mismo punto, menos cero coma seis cinco cinco, con k uno y con k cien: la k aparece arriba y abajo, y se cancela.

def correr(regla, k, lr, pasos=40):     # pérdida: k · (0,1x² + 3y²)
    p, s = np.array([-4.5, 1.5]), 0.0
    for _ in range(pasos):
        g = k * np.array([0.2, 6.0]) * p
        if regla == "SGD":
            p = p - lr * g
        else:                           # AdaGrad
            s = s + g ** 2
            p = p - lr * g / (np.sqrt(s) + 1e-10)
    return p

for regla, lr in [("SGD", 0.3), ("AdaGrad", 0.5)]:
    for k in [1, 100]:
        p = correr(regla, k, lr)
        fin = "diverge" if np.abs(p).max() > 1e6 else p.round(3)
        print(f"{regla:7} k = {k:3}: termina en {fin}")

SGD     k =   1: termina en [-0.379  0.   ]
SGD     k = 100: termina en diverge
AdaGrad k =   1: termina en [-0.655  0.   ]
AdaGrad k = 100: termina en [-0.655  0.   ]

Lo que cambia al dividir

En SGD y momentum, el paso es proporcional al gradiente: si cambian las unidades de la pérdida, cambia el paso, y el learning rate hay que buscarlo de nuevo para cada problema. En AdaGrad y RMSProp, el gradiente se divide por su propio tamaño. El learning rate pasa a ser, más o menos, el largo del paso en cada coordenada. Por eso un mismo valor, como diez a la menos tres, sirve en problemas muy distintos. Falta juntar las dos ideas: la memoria del momentum y la escala por parámetro. Eso es Adam.

Resumiendo

• AdaGrad: $s \leftarrow s + g^2$, paso $\eta\, g / \sqrt{s}$
• Primer paso: $\eta$ por el signo, en cada coordenada
• Con $g$ constante, AdaGrad: $\eta/\sqrt{t}$, se frena
• RMSProp: promedio móvil $v$; el paso se asienta
• $v$ arranca en 0: primer paso $3{,}16\,\eta$
• Próximo: Adam = momentum + RMSProp + corrección

Papers del episodio

• Duchi, Hazan y Singer, 2011 — Adaptive Subgradient Methods for Online Learning and Stochastic Optimization