¿Son las técnicas de aprendizaje automático "algoritmos de aproximación"?

Question

Recientemente hubo una pregunta sobre ML en cstheory stackexchange, y publiqué una respuesta recomendando el método de Powell, el descenso de gradiente, los algoritmos genéticos u otros métodos. "algoritmos de aproximación". En un comentario alguien me dijo que estos métodos eran "heurísticos" y no "algoritmos de aproximación" y con frecuencia no se acercaban al óptimo teórico (porque "frecuentemente se atascan en mínimos locales").

¿Están los demás de acuerdo? Además, me parece que hay un sentido en el que se puede garantizar que los algoritmos heurísticos se acerquen a los óptimos teóricos si se configuran para explorar una gran parte del espacio de búsqueda (por ejemplo, estableciendo parámetros/tamaños de paso pequeños), aunque no lo he visto en ningún artículo. ¿Alguien sabe si esto se ha demostrado o demostrado en un documento? (si no para una gran clase de algoritmos tal vez para una clase pequeña decir NNs etc.)

Answer 1

Creo que estás mezclando varios conceptos importantes. Permíteme intentar aclarar un par de cosas:

• Existen métodos metaheurísticos, que son métodos que intentan mejorar iterativamente una solución candidata. Ejemplos de ello son la búsqueda tabú, el recocido simulado, los algoritmos genéticos, etc. Obsérvese que, aunque puede haber muchos casos en los que estos métodos funcionen bien, no existe una comprensión profunda de cuándo funcionan y cuándo no. Y lo que es más importante, cuando no llegan a la solución, podemos estar arbitrariamente lejos de ella. Los problemas resueltos por métodos metaheurísticos tienden a ser de naturaleza discreta, porque hay herramientas mucho mejores para manejar problemas continuos. Pero de vez en cuando también se ven metaheurísticas para problemas continuos.

• Existen métodos de optimización numérica, la gente de esta comunidad examina cuidadosamente la naturaleza de la función que se quiere optimizar y las restricciones de la solución (en grupos como optimización convexa, programación cuadrática, programación lineal, etc.) y aplica algoritmos que se ha demostrado que funcionan para ese tipo de función, y ese tipo de restricciones. Cuando la gente de este campo dice "se ha demostrado que funcionan" se refiere a una prueba. La situación es que este tipo de métodos funcionan en problemas continuos. Pero cuando su problema cae en esta categoría, esta es definitivamente la herramienta a utilizar.

• Existen métodos de optimización discreta, que suelen ser cosas que en la naturaleza están relacionadas con algoritmos para problemas discretos bien estudiados: como los caminos más cortos, el flujo máximo, etc. La gente de esta área también se preocupa de que sus algoritmos funcionen realmente (pruebas). Hay un subconjunto de personas en este grupo que estudian problemas realmente difíciles para los que no se espera que exista ningún algoritmo rápido. Entonces estudian algoritmos de aproximación, que son algoritmos rápidos para los que son capaces de demostrar que su solución está dentro de un factor constante del verdadero óptimo. Esto se denomina "algoritmos de aproximación". Estas personas también muestran sus resultados como pruebas.

Así que... para responder a tu pregunta, no creo que las metaheurísticas sean algoritmos de aproximación. No me parece algo relacionado con la opinión, es simplemente un hecho.

Answer 2

El aprendizaje automático a menudo se ocupa de la optimización de una función que tiene muchos mínimos locales. Un buen ejemplo son las redes neuronales con unidades ocultas. Tanto si estas funciones son discretas como continuas, no existe ningún método que alcance un mínimo global y se detenga. Es fácil demostrar que no existe ningún algoritmo general para encontrar un mínimo global de una función continua, incluso si es unidimensional y suave (tiene infinitas derivadas). En la práctica, todos los algoritmos de aprendizaje de redes neuronales se atascan en un mínimo local. Es fácil comprobarlo: cree una red neuronal aleatoria, haga un gran conjunto de sus respuestas a entradas aleatorias y, a continuación, intente aprender otra red neuronal con la misma arquitectura para copiar las respuestas. Aunque la solución perfecta existe, ni la retropropagación ni ningún otro algoritmo de aprendizaje será capaz de descubrirla, partiendo de un conjunto aleatorio de pesos.

Algunos métodos de aprendizaje, como el recocido simulado o los algoritmos genéticos, exploran muchos mínimos locales. Para funciones continuas existen métodos como el descenso de gradiente, que encuentran el mínimo local más cercano. Son mucho más rápidos, por eso se utilizan mucho en la práctica. Pero si se dispone de tiempo suficiente, el primer grupo de métodos supera al segundo en términos de error del conjunto de entrenamiento. Pero con limitaciones de tiempo razonables, para los problemas del mundo real, el segundo grupo suele ser mejor.

Para algunos modelos, como la regresión logística, existe un mínimo local, la función es convexa, la minimización converge al mínimo, pero los modelos en sí son simplistas.

Esa es la amarga verdad.

Nótese también que la prueba de convergencia y la prueba de convergencia a la mejor solución son dos cosas diferentes. El algoritmo K-means es un ejemplo de ello.

Por último, en algunos modelos no sabemos cómo aprender. Por ejemplo, si la salida es una función computable arbitraria de las entradas, no conocemos buenos algoritmos que, en un tiempo razonable, encuentren una máquina de Turing o equivalente que implemente esta función. Por ejemplo, si f(1)=2, f(2)=3, f(3)=5, f(4)=7, ..., f(10)=29 (diez primeros primos), no conocemos ningún algoritmo de aprendizaje que sea capaz de predecir, en un tiempo razonable, que f(11)=31, a menos que ya conozca el concepto de número primo.