¿Qué es el algoritmo de descenso de gradiente?

Para ponerlo en términos muy simples, Gradient Descent es un algoritmo auxiliar que tiene como objetivo lograr la solución óptima requerida a través del método de prueba y error.

Entonces, ¿cuál es el problema y cuál es la solución?

Como ejemplo, hay un modelo de aprendizaje automático supervisado llamado Modelo de regresión lineal. En este modelo, se nos da un conjunto de datos específico, por ejemplo, la tasa a la que se vende una casa en particular en función de su tamaño.

Entonces, precio de venta = función (tamaño)

Trazamos el conjunto de datos dado en un gráfico y, según este modelo, intentamos dibujar la mejor línea recta posible a través de este gráfico de modo que cubra la mayoría de los valores dados. Al hacer esto, podemos llegar a un precio de venta relativamente preciso para una casa cuyo tamaño no figura en nuestro conjunto de datos.

Ahora, el problema radica en encontrar los coeficientes apropiados para la línea que deseamos dibujar. Eso es encontrar ‘m’ y ‘c’ en la ecuación de línea recta,

y = mx + c

Entonces, encontramos una función llamada función de costo que ayuda a determinar estos valores de coeficientes. Asocia un valor de costo con un par particular de coeficientes y lo hace para una amplia gama de combinaciones. Entre estos resultados de costos, elegimos el que sea menor porque solo el valor de menor costo garantiza una desviación mínima de nuestra línea del conjunto de datos.

El algoritmo de descenso de gradiente nos ayuda a encontrar una ruta al valor de costo más bajo dados todos los valores de costo.

Funciona así (esto se puede comparar con bajar una colina):

  • Comienza con un par particular de coeficientes y ve su valor de costo.
  • Luego busca un valor de costo menor de lo que sea en este momento.
  • Se mueve al valor más bajo y actualiza los coeficientes en consecuencia.
  • Después de un período de tiempo particular, alcanza un mínimo local más allá del cual no puede continuar.
  • Por lo tanto, ha encontrado el par correcto de coeficientes requeridos en ese punto donde no puede continuar.

NOTA: En el caso del modelo de regresión lineal, solo hay un mínimo y es el mínimo global. Por lo tanto, decimos que se encuentran los coeficientes requeridos para la línea.

En otros casos, el mínimo local alcanzado depende de los coeficientes iniciales tomados en consideración.

Esta es mi explicación más simple posible del algoritmo de descenso de gradiente.

Si desea obtener más información sobre el aprendizaje automático, le sugiero que tome el Curso Coursera en Aprendizaje automático del Sr. Andrew Ng. Es un curso muy agradable y el ejemplo proporcionado anteriormente se toma de eso.

Aprendizaje automático – Universidad de Stanford | Coursera

Espero que la respuesta haya ayudado.

Limitemos la configuración a un problema de optimización convexa.

El descenso de gradiente es un algoritmo simple utilizado para resolver problemas de optimización de la forma [math] min_x f (x) [/ math] a donde [math] f (x) [/ math] es una función suave y convexa y [math] x [/ math] es una colección de parámetros representados por un vector n-dimensional.

Para simplificar aún más las cosas, considere que [math] f (x) [/ math] tiene un mínimo único (por lo tanto, la función se vuelve estrictamente convexa, aunque no es necesario entrar en detalles extraños). La tarea del descenso de gradiente es encontrar / acercarse a ese mínimo de manera iterativa.

Entremos en las matemáticas del problema. Considere la expansión de Taylor de segundo orden de [math] f (x) [/ math]:

[matemáticas] f (y) \ aprox. f (x) + \ nabla f (x) ^ T (yx) + \ frac {1} {2t} || yx || _2 ^ 2 [/ matemáticas]

donde reemplazamos la segunda derivada [math] \ nabla ^ 2 f (x) [/ math] por un término suave [math] \ frac {I} {t} [/ math] que involucra una matriz de identidad y una constante [math] t [/ math] (esta eliminación de la segunda derivada hace que el descenso de gradiente dependa completamente de la primera derivada, de ahí el método de primer orden de etiqueta).

¿Cómo elegiría una [matemática] y [/ matemática] (dado que ya sabe [matemática] x [/ matemática]) de tal manera que [matemática] f (y) [/ matemática] obtenga el menor valor posible? La respuesta es tomar la derivada de [math] f (y) [/ math] wrt a [math] y [/ math] y ponerla a cero:

[matemáticas] \ nabla_y f (y) = \ nabla_y (f (x) + \ nabla f (x) ^ T (yx) + \ frac {1} {2t} || yx || _2 ^ 2) = 0 + \ nabla f (x) + \ frac {1} {t} (yx) = 0 [/ math]

Esto nos da la actualización de descenso de gradiente familiar [matemática] y = x – t * \ nabla f (x) [/ matemática], donde [matemática] t [/ matemática] puede interpretarse como el tamaño del paso.

Una interpretación geométrica relacionada es que en cada paso del descenso del gradiente, encontramos una aproximación cuadrática suave sobre [matemática] x [/ matemática] y luego procedemos a la parte inferior de la aproximación cuadrática en una sola toma.

En la imagen de arriba, el punto azul es [matemático] x [/ matemático] y el punto rojo es [matemático] y [/ matemático]. Después de una iteración, el algoritmo desciende a [matemática] f (y) [/ matemática] en la curva de función, encuentra una aproximación cuadrática alrededor de [matemática] y [/ matemática] y luego repite el mismo proceso hasta que se hayan establecido algunos criterios de convergencia logrado.

(Imagen y la explicación básica tomada de las diapositivas de la conferencia del excelente curso de optimización convexa impartido en CMU por Ryan Tibshirani).

El descenso de gradiente es un algoritmo de optimización muy simple. Realiza movimientos iterativos en la dirección opuesta al gradiente de una función en un punto.

Es fácil de entender si visualizamos el procedimiento.

Supongamos que estamos tratando de encontrar el mínimo de la función [matemáticas] f (x) = (x-1) ^ 2 [/ matemáticas]

(sabemos que el mínimo está en x = 1. Intentemos aplicar el descenso de gradiente)

Tenemos que hacer una suposición inicial para el mínimo. Supongamos que nuestra conjetura inicial es x (0) = -1

Según el algoritmo de descenso de gradiente, nuestro nuevo punto [matemática] x (1) = x (0) – \ eta f ^ {‘} (x (0)) [/ matemática]

donde [math] \ eta [/ math] es el tamaño de paso ajustable (fijémoslo como 0.6) y [math] f ^ {‘} (x) [/ math] denota la derivada de [math] f (x) [ / math] en el punto [math] x. [/ math] La derivada de [math] (x-1) ^ 2 [/ math] es [math] 2 (x-1). [/mates]

Entonces [matemáticas] x (1) = -1 – [/ matemáticas] [matemáticas] 0.6 * 2 * -2 = [/ matemáticas] 1.4

Vemos que nos estamos acercando al mínimo, que es [matemáticas] x = 1 [/ matemáticas]

Hagamos algunas iteraciones más

[matemáticas] x (2) = 1.4 – 0.6 * 2 * 0.4 = 0.92 [/ matemáticas]

[matemáticas] x (3) = 0.91 – 0.6 * 2 * (0.92-1) = 1.016 [/ matemáticas]

[matemática] x (4) = 1.016 – 0.6 * 2 * 0.016 = 0.9968 [/ matemática]

[matemáticas] x (5) = 0.9968 – 0.6 * 2 * (0.9968-1) = 1.00064 [/ matemáticas]

Por cada actualización nos acercamos más y más al verdadero óptimo.

Podemos generalizar el procedimiento para el espacio multidimensional. Allí en lugar de [math] f ^ {‘}, [/ math] denotamos la derivada por el gradiente [math] \ nabla f (x) [/ math]

Entonces, nuestra regla de actualización de descenso de gradiente es [matemáticas] x (k + 1) = x (k) – \ eta \ nabla f (x (k)) [/ matemáticas]

Notas adicionales:

  1. El algoritmo de descenso de gradiente en realidad se deriva de la aproximación de la serie Taylor de una función en un punto.
  2. La convergencia del algoritmo depende del valor del parámetro de paso [math] \ eta [/ math] elegido. Un parámetro de paso más grande significa que los valores se disparan y nunca convergen. (Intente ejecutar el ejemplo anterior con [math] \ eta = 1.) [/ math] Un valor menor de [math] \ eta [/ math] significa que lleva mucho tiempo converger.
  3. El descenso de gradiente es un algoritmo de optimización de primer orden, lo que significa que su convergencia es lenta. Un algoritmo de segundo orden como el algoritmo de Newton será más rápido en convergencia. Consulte mi blog para leer sobre Newton’s Method ML Blog.

Mi publicación de blog puede responder a tu pregunta

Inicio | Srishti Sawla

More Interesting

¿Qué métodos (sin supervisión) deberían usarse para la categorización jerárquica automática de documentos?

¿Cuáles son los consejos para aprender el aprendizaje automático?

¿Por qué se le da tanta atención a xgboost que al aprendizaje profundo a pesar de su ubicuidad en ganar soluciones de Kaggle?

¿Cuál es la relación entre el análisis de sentimientos, el procesamiento del lenguaje natural y el aprendizaje automático?

¿Es aconsejable crear una aplicación basada en el aprendizaje automático y el procesamiento de imágenes sin comprender el concepto matemático subyacente?

¿Dónde puedo encontrar el código fuente para construir un árbol de decisión usando el algoritmo ID3 en C?

¿En qué casos debo usar TensorFlow, PyTorch y Caffe2?

¿Qué aplicaciones iOS usan TensorFlow del lado del cliente?

¿Las GPU seguirán dominando la inteligencia artificial y el aprendizaje automático, aumentando el valor de compañías como Nvidia y AMD, o los chips especializados como los de Graphcore se harán cargo?

¿Puedo confiar en un modelo de clasificación con validación cruzada y precisión de prueba decentes incluso si el número de observaciones es menor que el de las características?

¿Cuáles son los requisitos previos para aprender Machine Learning?

¿Por qué la función sigmoidea rara vez se usa en capas ocultas recientemente?

¿Qué debo usar para el aprendizaje automático si necesito una solución rápida: Python, R o SAS?

¿Podría el aprendizaje automático erradicar el cáncer?

¿Qué deparará el futuro para los desarrolladores en la era del aprendizaje profundo y la IA? ¿Cuáles serán las tendencias y cómo sobrevivirán los desarrolladores?