Encontrar el mínimo por el descenso del gradiente

pendientes

Pendientes, en 'Redes Neuronales 2020' (Rafael Alberto Moreno Parra / CC BY).

En Encontrar el mínimo en una ecuación por aproximaciones vimos cómo buscar el mínimo valor de y modificando el valor de x por aproximaciones sucesivas, ya sea aumentando o dismuniyendo el valor de x (por la derecha o por la izquierda en el gráfico de la curva). Pero el método resultaría más eficiente si determinamos previamente el sentido de esas variaciones sobre x.

Esto se puede hacer a partir de la derivada de la ecuación, puesto que la derivada muestra la tangente (línea recta con una pendiente) que pasa por el punto que se seleccionó arbitraria o aleatoriamente al inicio como valor de x. Si la pendiente es positiva entonces x debe aproximarse hacia la izquierda de la curva (su valor debe disminuir), en cambio, si la pendiente es negativa entonces x debe ir hacia la derecha (su valor debe aumentar).

Conociendo el sentido de las aproximaciones a partir de la derivada (y teniendo en cuenta que ésta tiende a 0 según se acerca al vértice de la curva, puesto que en el mínimo la tangente será horizontal), el código para encontrar el mínimo en una ecuación mediante el método de descenso del gradiente queda de esta manera implementado con Dart:

import 'dart:io';

const dec = 3; // número de decimales en resultados

void main() {
  // valores de la ecuación
  double a;
  double b;
  double c;
  double x;

  // pide los valores de la ecuación y el valor inicial de x
  print('Siendo la ecuación ax² + bx + c');
  stdout.write('Introduce el valor de a (un número distinto de 0, por defecto 5.0): ');
  a = double.tryParse(stdin.readLineSync()) ?? 5.0;
  a = a <= 0.0 ? 5.0 : a;
  stdout.write('Introduce el valor de b (por defecto -7.0): ');
  b = double.tryParse(stdin.readLineSync()) ?? -7.0;
  stdout.write('Introduce el valor de c (por defecto -13.0): ');
  c = double.tryParse(stdin.readLineSync()) ?? -13.0;
  stdout.write('Introduce el valor inicial de x (por defecto 1.0): ');
  x = double.tryParse(stdin.readLineSync()) ?? 1.0;

  // obtiene derivada y ajusta valor constante
  double derivada(double x) => 2 * a * x + b;
  const alpha = 0.5; // ratio de aprendizaje

  // calcula y muestra el valor inicial de y
  double ecuacion(double x) => a * x * x + b * x + c;
  var yIni = ecuacion(x);
  var cont = 1;
  print('$cont x: ${x.toStringAsFixed(dec)} y: ${yIni.toStringAsFixed(dec)}');

  // método de descenso del gradiente
  while (derivada(x).abs() > 0.1) { // criterio de parada
    var yNew = ecuacion(x);
    if (yNew > yIni) {
      x = x - alpha * derivada(x);
    } else {
      yIni = yNew;
      x = x - alpha * derivada(x);
      cont++;
      print('$cont x: ${x.toStringAsFixed(dec)} y: ${yIni.toStringAsFixed(dec)}');
    }
  }

  // mostrar ecuación y resultado
  String sinCeros(numero) => numero.toString().replaceAll(RegExp(r'([.]*0)(?!.*\d)'), '');
  String signo(numero) => numero < 0 ? '-' : '+';
  print('En la ecuación y = ${sinCeros(a)}x² ${signo(b)} ${sinCeros(b.abs())}x ${signo(c)} ${sinCeros(c.abs())}');
  print('para el valor mínimo de y = ${yIni.toStringAsFixed(dec)}, x = ${x.toStringAsFixed(dec)}');
}

Siendo la ecuación ax² + bx + c
Introduce el valor de a (un número distinto de 0, por defecto 5.0): 0.5
Introduce el valor de b (por defecto -7.0): -3
Introduce el valor de c (por defecto -13.0): -12
Introduce el valor inicial de x (por defecto 1.0): -0.5
1 x: -0.500 y: -10.375
2 x: 1.250 y: -10.375
3 x: 2.125 y: -14.969
4 x: 2.563 y: -16.117
5 x: 2.781 y: -16.404
6 x: 2.891 y: -16.476
7 x: 2.945 y: -16.494
En la ecuación y = 0.5x² - 3x - 12
para el valor mínimo de y = -16.494, x = 2.945

Tal como se ha implementado, este algoritmo tiene el inconveniente de que para funciones con estructuras con valles largos y estrechos requiere muchas iteraciones. Se debe a que, aunque la dirección elegida es la correcta hacia el valor mínimo, esto no significa que necesariamente lo encuentre más rápido. Veremos que esto lo podemos solucionar ajustando dos valores:

  1. El valor de la constante alpha utilizado para obtener cada nuevo valor de x. Este valor controla el tamaño de actualización de x y se le conoce como ratio de aprendizaje. Es importante elegir un buen ratio de aprendizaje para asegurarnos que no vamos dando tumbos (ni pasos demasiados grandes que provocan oscilaciones ni demasiado pequeños que conllevan un proceso más lento y con más iteraciones).
  2. El valor de parada o criterio para detener el proceso de búsqueda (en el código, cuando el valor absoluto de la pendiente sea menor que 0.1).

El valor de estos valores, especialmente la ratio de aprendizaje, deben ser ajustados en función del tipo de datos o de la ecuación que se utiliza. Una opción es ajustarlo "a mano" por ensayo y error hasta encontrar el que mejor se adapta a la ecuación utilizada. Otra opción es crear una lista con ritmos de aprendizaje, por ejemplo [0.001, 0.01, 0.05, 0.1, 0.3, 0.5], y entrenar al modelo con cada uno de estos valores para ver cuál da mejores resultados. Otra alternativa consiste en hacerla variable a lo largo del proceso, mayor al principio y disminuyendo cuando estemos cerca del mínimo.