¿Cómo podría ahorrar tiempo el descenso de gradiente estocástico en comparación con el descenso de gradiente estándar?

Question

Estándar de Gradiente de la pendiente sería calcular el gradiente para todo el conjunto de datos de entrenamiento.

for i in range(nb_epochs):
  params_grad = evaluate_gradient(loss_function, data, params)
  params = params - learning_rate * params_grad

Para un número prefijado de épocas, en primer lugar, calcular el vector gradiente weights_grad de la función de pérdida para todo el conjunto de datos w.r.t. nuestro parámetro de vector de parámetros.

Estocástico de Gradiente de la pendiente en contraste realiza un parámetro de actualización para cada formación ejemplo x(i) y de la etiqueta y(i).

for i in range(nb_epochs):
  np.random.shuffle(data)
  for example in data:
    params_grad = evaluate_gradient(loss_function, example, params)
    params = params - learning_rate * params_grad

SGD se dice que ser mucho más rápido. Sin embargo, no entiendo cómo se puede ser mucho más rápido si todavía tenemos un lazo sobre todos los puntos de datos. Hace el cálculo de la pendiente en el GD es mucho más lento que el cálculo de la GD para cada punto de datos por separado?

Código proviene de aquí.

Answer 1

Respuesta corta:

• En muchas de las grandes datos de configuración (es decir, varios millones de puntos de datos), el cálculo de costo o de gradiente lleva mucho tiempo, porque ambos necesitan sumar sobre todos los puntos de datos.
• Usted no necesita tener exacta de gradiente para reducir el costo y en una iteración dada. Algunos aproximación de gradiente iba a funcionar bien, pero mucho computacional eficiente.
• Estocástico gradiente decente (SGD) aproximar el gradiente de utilizar sólo un punto de datos. Así, la evaluación de gradiente ahorra tiempo.
• Con el número de iteraciones es mucho menor que el número de puntos de datos. Estocástico gradiente decente puede obtener una buena solución.

---

Respuesta larga:

Mi notación de la siguiente manera Andrew NG, de la máquina de aprendizaje curso de coursera. Si usted no está familiarizado con ella, favor de revisar la serie de conferencias aquí

Supongamos que la regresión en el cuadrado de la pérdida, la función de costo es

\begin{align} J(\theta)= \frac 1 {2m} \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})^2 \end{align}

y el gradiente es

\begin{align} \frac {d J(\theta)}{d \theta}= \frac 1 {m} \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})x^{(i)} \end{align}

para el gradiente decente (GD), se actualiza el parámetro por

\begin{align} \theta_{new} &=\theta_{old} - \alpha \frac 1 {m} \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})x^{(i)} \end{align}

Para estocástico gradiente decente nos deshacemos de la suma y $1/m$ constante, pero el gradiente de la corriente de datos de punto de $x^{(i)},y^{(i)}$, cuando llega el momento de guardar.

\begin{align} \theta_{new}=\theta_{old} - \alpha \cdot (h_{\theta}(x^{(i)})-y^{(i)})x^{(i)} \end{align}

Supongamos que usted tiene 1 mil millones de puntos de datos. En el GD, con el objeto de actualizar los parámetros de una vez, usted necesita tener el gradiente, por lo tanto, usted necesita para resumir estos 1 mil millones de puntos de datos para tener 1 actualización.

Por otro lado, se puede pensar en SGD está tratando de obtener un aproximado de degradado en lugar de exacta gradiente. La aproximación es conseguir que sólo desde un punto de datos (o de varios puntos de datos llamado mini lote). Por lo tanto, en SGD, puede actualizar los parámetros muy rápidamente, por lo tanto, si usted bucles sobre sus datos, usted realmente tiene 1 mil millones de actualizaciones.

El truco es que, en SGD usted no necesita tener 1 mil millones de iteraciones/actualizaciones, pero mucho menos iteraciones/actualizaciones, por ejemplo, 1 millones, tendrá "lo suficientemente bueno" modelo a utilizar.

---

Estoy escribiendo un código para la demo de la idea. Primero vamos a resolver el sistema lineal por el normal de la ecuación, y luego resolver con SGD. A continuación, comparamos los resultados en términos de los valores de parámetro y el objetivo final de los valores de la función. Para visualizarlo más tarde., vamos a tener 2 parámetros para afinar

set.seed(0);n_data=1e3;n_feature=2;
A=matrix(runif(n_data*n_feature),ncol=n_feature)
b=runif(n_data)
res1=solve(t(A) %*% A, t(A) %*% b)

sq_loss<-function(A,b,x){
  e=A %*% x -b
  v=crossprod(e)
  return(v[1])
}

sq_loss_gr_approx<-function(A,b,x){
  # note, in GD, we need to sum over all data
  # here i is just one random index sample
  i=sample(1:n_data, 1)
  gr=2*(crossprod(A[i,],x)-b[i])*A[i,]
  return(gr)
}

x=runif(n_feature)
alpha=0.01
N_iter=300
loss=rep(0,N_iter)

for (i in 1:N_iter){
  x=x-alpha*sq_loss_gr_approx(A,b,x)
  loss[i]=sq_loss(A,b,x)
}

Los resultados:

as.vector(res1)
[1] 0.4368427 0.3991028
x
[1] 0.3580121 0.4782659

Nota, si bien los parámetros no son para cerrar, la pérdida de valores de $124.1343$ $123.0355$ que están muy cerca.

Aquí está la pérdida de más de iteraciones, podemos ver que efectivamente puede disminuir la pérdida, lo que ilustra la idea: podemos utilizar un subconjunto de los datos para aproximar el gradiente y obtener "lo suficientemente buenos" resultados.

Ahora vamos a ver los esfuerzos computacionales entre los dos enfoques. En el experimento, tenemos $1000$ puntos de datos, el uso de SD, evaluar el gradiente de una vez las necesidades de la suma sobre los mismos datos. PERO en SGD, sq_loss_gr_approx función solo suma 1 punto de datos, y en general podemos ver, el algoritmo converge a menos de $300$ iteraciones (nota, no $1000$ iteraciones.) Este es el centro de cálculo de ahorros.