Optimización es el problema de encontrar un conjunto de entradas para una función objetiva que dé lugar a una evaluación máxima o mínima de la función.
Es el desafiante problema que subyace en muchos algoritmos de aprendizaje de máquinas, desde el ajuste de modelos de regresión logística hasta el entrenamiento de redes neuronales artificiales.
Hay quizás cientos de algoritmos de optimización populares, y quizás decenas de algoritmos para elegir en las bibliotecas de códigos científicos populares. Esto puede hacer que sea un desafío saber qué algoritmos considerar para un problema de optimización determinado.
En este tutorial, descubrirá un recorrido guiado por diferentes algoritmos de optimización.
Después de completar este tutorial, lo sabrás:
- Los algoritmos de optimización pueden agruparse en los que utilizan derivados y los que no.
- Los algoritmos clásicos utilizan la primera y a veces segunda derivada de la función objetivo.
- La búsqueda directa y los algoritmos estocásticos están diseñados para funciones objetivas en las que no se dispone de derivados de funciones.
Empecemos.
Cómo elegir un algoritmo de optimización
Foto de Matthewjs007, algunos derechos reservados.
Resumen del Tutorial
Este tutorial está dividido en tres partes; son:
- Algoritmos de optimización
- Función de objetivo diferenciable
- Función objetiva no diferenciada
Algoritmos de optimización
La optimización se refiere a un procedimiento para encontrar los parámetros o argumentos de entrada de una función que dan como resultado la salida mínima o máxima de la función.
Los problemas de optimización más comunes que se encuentran en el aprendizaje de las máquinas son optimización continua de la funcióndonde los argumentos de entrada de la función son valores numéricos de valor real, por ejemplo, valores de punto flotante. La salida de la función es también una evaluación de valor real de los valores de entrada.
Podríamos referirnos a los problemas de este tipo como optimización de funciones continuas, para distinguirlas de las funciones que toman variables discretas y que se denominan problemas de optimización combinatoria.
Hay muchos tipos diferentes de algoritmos de optimización que pueden utilizarse para los problemas de optimización de funciones continuas, y quizás también muchas formas de agruparlos y resumirlos.
Un enfoque para agrupar los algoritmos de optimización se basa en la cantidad de información disponible sobre la función objetivo que se está optimizando que, a su vez, puede ser utilizada y aprovechada por el algoritmo de optimización.
Por lo general, cuanta más información se disponga sobre la función de destino, más fácil será optimizarla si la información puede utilizarse eficazmente en la búsqueda.
Tal vez la mayor división en los algoritmos de optimización es si la función objetivo puede ser diferenciada en un punto o no. Es decir, si la primera derivada (gradiente o pendiente) de la función puede ser calculada para una solución candidata dada o no. Esto divide los algoritmos en los que pueden utilizar la información de gradiente calculada y los que no.
- ¿Función de objetivo diferenciable?
- Algoritmos que utilizan información derivada.
- Algoritmos que no utilizan información derivada.
Utilizaremos esta como la principal división para agrupar los algoritmos de optimización en este tutorial y veremos los algoritmos para funciones objetivas diferenciables e indiferenciables.
NotaNo se trata de una cobertura exhaustiva de los algoritmos para la optimización de la función continua, aunque sí de los principales métodos que es probable que encuentre como practicante habitual.
Función de objetivo diferenciable
Una función diferenciable es una función en la que la derivada puede ser calculada para cualquier punto dado en el espacio de entrada.
El derivado de una función para un valor es la tasa o cantidad de cambio de la función en ese punto. A menudo se llama la pendiente.
- Derivado de primer orden: Pendiente o tasa de cambio de una función objetiva en un punto determinado.
La derivada de la función con más de una variable de entrada (por ejemplo, entradas multivariadas) se denomina comúnmente gradiente.
- Gradiente: Derivado de una función objetiva continua multivariante.
Una derivada de una función objetiva multivariante es un vector, y cada elemento del vector se denomina una derivada parcial, o la tasa de cambio de una determinada variable en el punto en que se supone que todas las demás variables se mantienen constantes.
- Derivado parcial: Elemento de un derivado de una función objetiva multivariante.
Podemos calcular la derivada de la derivada de la función objetivo, es decir, la tasa de cambio de la tasa de cambio de la función objetivo. Esto se llama la segunda derivada.
- Derivado de segundo orden: Ritmo al que cambia el derivado de la función objetivo.
Para una función que toma múltiples variables de entrada, ésta es una matriz y se denomina matriz de Hesse.
- Matriz de Hesse: Segunda derivada de una función con dos o más variables de entrada.
Las funciones simples y diferenciables pueden ser optimizadas analíticamente usando el cálculo. Normalmente, las funciones objetivas que nos interesan no pueden ser resueltas analíticamente.
La optimización es significativamente más fácil si se puede calcular el gradiente de la función objetivo, y como tal, se ha investigado mucho más sobre los algoritmos de optimización que utilizan la derivada que los que no la utilizan.
Algunos grupos de algoritmos que utilizan información de gradientes incluyen:
- Algoritmos de soporte
- Algoritmos de Descenso Local
- Algoritmos de primer orden
- Algoritmos de segundo orden
Notaesta taxonomía está inspirada en el libro de 2019 «Algoritmos para la optimización».
Veamos más de cerca a cada uno por separado.
Algoritmos de soporte
Los algoritmos de optimización de corchetes están pensados para problemas de optimización con una variable de entrada en la que se sabe que el óptimo existe dentro de un rango específico.
Los algoritmos de corchetes son capaces de navegar eficientemente por el rango conocido y localizar el óptico, aunque asumen que sólo hay un único óptico presente (lo que se denomina funciones objetivas unimodales).
Algunos algoritmos de paréntesis pueden utilizarse sin información derivada si no se dispone de ella.
Los ejemplos de algoritmos de paréntesis incluyen:
- Búsqueda de Fibonacci
- Búsqueda de la Sección Dorada
- Método de bisección
Algoritmos de Descenso Local
Los algoritmos de optimización de la descendencia local están destinados a problemas de optimización con más de una variable de entrada y un solo óptimo global (por ejemplo, la función objetivo unimodal).
Tal vez el ejemplo más común de un algoritmo de descenso local es el algoritmo de búsqueda de líneas.
Existen muchas variaciones de la búsqueda de líneas (por ejemplo, el algoritmo Brent-Dekker), pero el procedimiento consiste generalmente en elegir una dirección para desplazarse en el espacio de búsqueda, y luego realizar una búsqueda entre paréntesis en una línea o un hiperplano en la dirección elegida.
Este proceso se repite hasta que no se pueden hacer más mejoras.
La limitación es que es computacionalmente caro optimizar cada movimiento direccional en el espacio de búsqueda.
Algoritmos de primer orden
Los algoritmos de optimización de primer orden implican explícitamente el uso de la primera derivada (gradiente) para elegir la dirección en la que moverse en el espacio de búsqueda.
El procedimiento consiste en calcular primero el gradiente de la función y luego seguir el gradiente en la dirección opuesta (por ejemplo, cuesta abajo hasta el mínimo para reducir al mínimo los problemas) utilizando un tamaño de paso (también llamado tasa de aprendizaje).
El tamaño del paso es un hiperparámetro que controla cuán lejos moverse en el espacio de búsqueda, a diferencia de los «algoritmos de descenso local» que realizan una búsqueda de línea completa para cada movimiento direccional.
Un tamaño de paso que es demasiado pequeño resulta en una búsqueda que toma mucho tiempo y puede atascarse, mientras que un tamaño de paso que es demasiado grande resultará en zig-zag o rebotando alrededor del espacio de búsqueda, perdiendo el óptimo completamente.
Los algoritmos de primer orden se denominan generalmente de descenso de gradiente, y los nombres más específicos se refieren a extensiones menores del procedimiento, por ejemplo:
- Descenso gradual
- Momentum
- Adagrad
- RMSProp
- Adam
El algoritmo de descenso de gradiente también proporciona la plantilla para la popular versión estocástica del algoritmo, llamada Descenso de Gradiente Estocástico (SGD) que se utiliza para entrenar modelos de redes neuronales artificiales (aprendizaje profundo).
La diferencia importante es que el gradiente se apropia en lugar de calcularse directamente, utilizando el error de predicción sobre los datos de capacitación, como una muestra (estocástica), todos los ejemplos (lote), o un pequeño subconjunto de datos de capacitación (mini lote).
Las extensiones diseñadas para acelerar el algoritmo de descenso de gradiente (momento, etc.) pueden ser y son comúnmente usadas con el SGD.
- Descenso de gradiente estocástico
- Descenso del gradiente del lote
- Descenso del gradiente del mini lote
Algoritmos de segundo orden
Los algoritmos de optimización de segundo orden implican explícitamente el uso de la segunda derivada (Hessian) para elegir la dirección en la que moverse en el espacio de búsqueda.
Estos algoritmos sólo son apropiados para aquellas funciones objetivas en las que se puede calcular o aproximar la matriz de Hesse.
Entre los ejemplos de algoritmos de optimización de segundo orden para funciones objetivas univariantes se incluyen:
- El método de Newton
- Método Secant
Los métodos de segundo orden para las funciones objetivas multivariadas se denominan métodos cuasi-Newton.
Hay muchos Métodos de Cuasi-Newton, y son típicamente nombrados por los desarrolladores del algoritmo, como:
- Davidson-Fletcher-Powell
- Broyden-Fletcher-Goldfarb-Shanno (BFGS)
- BFGS de memoria limitada (L-BFGS)
Ahora que estamos familiarizados con los llamados algoritmos de optimización clásicos, veamos los algoritmos utilizados cuando la función objetivo no es diferenciable.
Función objetiva no diferenciada
Los algoritmos de optimización que utilizan la derivada de la función objetivo son rápidos y eficientes.
No obstante, hay funciones objetivas en las que la derivada no puede ser calculada, típicamente porque la función es compleja por una variedad de razones del mundo real. O la derivada puede ser calculada en algunas regiones del dominio, pero no en todas, o no es una buena guía.
Algunas dificultades en las funciones objetivas de los algoritmos clásicos descritos en la sección anterior incluyen:
- No hay una descripción analítica de la función (por ejemplo, simulación).
- Óptima global múltiple (por ejemplo, multimodal).
- Evaluación de la función estocástica (por ejemplo, ruidosa).
- Función objetiva discontinua (por ejemplo, regiones con soluciones no válidas).
Como tal, existen algoritmos de optimización que no esperan que se disponga de derivados de primer o segundo orden.
Estos algoritmos se denominan a veces algoritmos de optimización de caja negra, ya que suponen poco o nada (en relación con los métodos clásicos) sobre la función objetivo.
Una agrupación de estos algoritmos incluye:
- Algoritmos directos
- Algoritmos estocásticos
- Algoritmos de población
Veamos más de cerca a cada uno por separado.
Algoritmos directos
Los algoritmos de optimización directa son para funciones objetivas para las que no se pueden calcular derivados.
Los algoritmos son procedimientos deterministas y a menudo asumen que la función objetiva tiene un solo óptico global, por ejemplo, unimodal.
Los métodos de búsqueda directa también suelen denominarse «búsqueda de patrones» ya que pueden navegar por el espacio de búsqueda usando formas o decisiones geométricas, por ejemplo, patrones.
La información de los gradientes se aproxima directamente (de ahí el nombre) a partir del resultado de la función objetiva que compara la diferencia relativa entre las puntuaciones de los puntos en el espacio de búsqueda. Estas estimaciones directas se utilizan luego para elegir una dirección para moverse en el espacio de búsqueda y triangular la región del óptico.
Los ejemplos de algoritmos de búsqueda directa incluyen:
- Búsqueda de coordenadas cíclicas
- El método de Powell
- Método Hooke-Jeeves
- Búsqueda de Nelder-Mead Simplex
Algoritmos estocásticos
Los algoritmos de optimización estocástica son algoritmos que utilizan la aleatoriedad en el procedimiento de búsqueda de funciones objetivas para las que no se pueden calcular las derivadas.
A diferencia de los métodos deterministas de búsqueda directa, los algoritmos estocásticos suelen implicar mucho más muestreo de la función objetiva, pero son capaces de manejar problemas con óptimos locales engañosos.
Los algoritmos de optimización estocástica incluyen:
- Recocido simulado
- Estrategia de evolución
- Método de la interropiación
Algoritmos de población
Los algoritmos de optimización de población son algoritmos de optimización estocástica que mantienen un conjunto (una población) de soluciones candidatas que en conjunto se utilizan para muestrear, explorar y perfeccionar un óptimo.
Los algoritmos de este tipo están destinados a problemas objetivos más difíciles que pueden tener evaluaciones de funciones ruidosas y muchos óptimos globales (multimodales), y encontrar una solución buena o suficientemente buena es difícil o inviable con otros métodos.
El conjunto de soluciones candidatas añade robustez a la búsqueda, aumentando la probabilidad de superar el óptimo local.
Entre los ejemplos de algoritmos de optimización de la población se incluyen:
- Algoritmo genético
- Evolución diferencial
- Optimización de los enjambres de partículas
Más lecturas
Esta sección proporciona más recursos sobre el tema si desea profundizar en él.
Libros
Artículos
Resumen
En este tutorial, descubriste un recorrido guiado por diferentes algoritmos de optimización.
Específicamente, aprendiste:
- Los algoritmos de optimización pueden agruparse en los que utilizan derivados y los que no.
- Los algoritmos clásicos utilizan la primera y a veces segunda derivada de la función objetivo.
- La búsqueda directa y los algoritmos estocásticos están diseñados para funciones objetivas en las que no se dispone de derivados de funciones.
¿Tiene alguna pregunta?
Haga sus preguntas en los comentarios de abajo y haré lo posible por responder.