El algoritmo de descenso de gradiente no converge

Question

Estoy tratando de escribir un código para el algoritmo de descenso de gradiente explicado en la conferencia Stanford Machine Learning (lecture 2 at around 25:00). Debajo está la implementación que usé al principio, y creo que está copiada correctamente de la conferencia, pero no converge cuando agrego números grandes (>8) al conjunto de entrenamiento.

estoy introduciendo un número X, y se añade el point (X,X) para el conjunto de entrenamiento, por lo que en este momento, sólo estoy tratando de conseguir que convergen a y=ax+b donde a=1=theta\[1\] y b=0=theta\[0\]. El conjunto de entrenamiento es el conjunto x y y, donde (x[i],y[i]) es un punto.

void train() 
{ 
    double delta; 
    for (int i = 0; i < x.size(); i++) 
    { 
     delta = y[i]-hypothesis(x[i]); 
     theta[1] += alpha*delta*x[i]; 
     theta[0] += alpha*delta*1; 
    } 
} 

void C_Approx::display() 
{ 
    std::cout<<theta[1]<<"x + "<<theta[0]<<" \t "<<"f(x)="<<hypothesis(1)<<std::endl; 
} 

algunos de los resultados que estoy obteniendo: que introducir un número, que se ejecuta train() un par de veces, luego display()

1 
0.33616x + 0.33616 f(x)=0.67232 
1 
0.482408x + 0.482408  f(x)=0.964816 
1 
0.499381x + 0.499381  f(x)=0.998762 
1 
0.499993x + 0.499993  f(x)=0.999986 
1 
0.5x + 0.5 f(x)=1 

Un ejemplo de ello divergentes después de que pasó 8:

1 
0.33616x + 0.33616 f(x)=0.67232 
2 
0.705508x + 0.509914  f(x)=1.21542 
3 
0.850024x + 0.449928  f(x)=1.29995 
4 
0.936062x + 0.330346  f(x)=1.26641 
5 
0.951346x + 0.231295  f(x)=1.18264 
6 
0.992876x + 0.137739  f(x)=1.13062 
7 
0.932206x + 0.127372  f(x)=1.05958 
8 
1.00077x + 0.000493063 f(x)=1.00126 
9 
-0.689325x + -0.0714712  f(x)=-0.760797 
10 
4.10321e+08x + 4.365e+07  f(x)=4.53971e+08 
11 
1.79968e+22x + 1.61125e+21 f(x)=1.9608e+22 
12 
-3.9452e+41x + -3.26957e+40  f(x)=-4.27216e+41 

Probé la solución propuesta here de escalar el paso y terminé con resultados similares. ¿Qué estoy haciendo mal?

Answer 1

Su implementación es buena. Generalmente, el descenso del gradiente estocástico puede divergir cuando α es demasiado grande. Lo que haría con un gran conjunto de datos es tomar una muestra aleatoria de tamaño razonable, encontrar α que le ofrezca los mejores resultados y luego utilizarlo para el resto.

Answer 2

Si lo entiendo correctamente, su conjunto de entrenamiento solo tiene un gradiente distinto de cero al borde de una línea? A menos que comiences en la línea (en realidad comiences exactamente en uno de tus puntos de entrenamiento) no encontrarás la línea. Siempre estás en un mínimo local.

Answer 3

Cuando su función de costo aumenta o sube y baja, generalmente tiene un valor demasiado grande para alpha. ¿Qué alpha estás usando?

Comience con un alpha = 0.001 y vea si eso converge? Si no, pruebe varios alphas(0.003, 0.01, 0.03, 0.1, 0.3, 1) y encuentre uno que converja rápidamente.

Escalar los datos (normalización) no le ayudará con solo 1 característica (su theta[1]) ya que la normalización solo se aplica a las características 2+ (regresión lineal multivariante).

También tenga en cuenta que para un pequeño número de características, puede usar la ecuación normal para obtener la respuesta correcta.

Answer 4

He tenido el mismo problema (aunque en Java) porque mi tasa de aprendizaje era demasiado grande.
Para abreviar, estaba usando α = 0.001 y tuve que empujarlo a 0.000001 para ver la convergencia real.

Por supuesto, estos valores están vinculados a su conjunto de datos.

Answer 5

utiliza la búsqueda de la línea de seguimiento para garantizar la convergencia. Es muy simple de implementar. Ver Stephen Boyd, Optimización convexa para referencia. Puede elegir algunos valores alfa, beta estándar para la búsqueda de líneas de seguimiento, por ejemplo 0.3 y 0.8.