¿Podemos aplicar el aprendizaje automático a los problemas de NP Complete? La tecnología cambia la vida futura

Comencemos diseccionando la pregunta: ¿qué significa aplicar el aprendizaje automático a problemas de NP completo?

Los problemas NP-completos más comunes tienen un espacio de estado discreto exponencialmente grande, y el objetivo es minimizar una función objetivo bien definida. Por ejemplo, en el problema del vendedor ambulante (TSP), el espacio de estado es el conjunto de todas las permutaciones de los vértices y la función objetivo para una permutación (estado) particular es la suma de distancias entre vértices consecutivos en el recorrido. Ahora, las personas que están trabajando en un problema de NP completo, ¿qué están tratando de lograr? Depende:

Ciencias de la computación teóricas: las personas que trabajan en ciencias de la computación teóricas intentan desarrollar un algoritmo para el cual pueda dar garantías teóricas como “para cualquier caso de este problema, el algoritmo generará una solución que es como máximo 2 veces peor que la solución óptima “. (Por peor, quiero decir que la función objetivo en la solución devuelta por el algoritmo es como máximo 2 veces el valor mínimo de la función objetivo alcanzable). Claramente, desea el algoritmo que funciona mejor en el peor de los casos.
Investigación de operaciones: las personas que trabajan en investigación de operaciones, por otro lado, no se preocupan por el peor de los casos, en su mayor parte. Quieren un algoritmo que funcione bien en casos prácticos de los problemas o que funcione bien en promedio. Estas son esencialmente heurísticas, a menudo sin garantías teóricas.

Ahora, veamos qué te ofrece el aprendizaje automático. La mayoría del aprendizaje automático puede considerarse como una aproximación de funciones: dado algunos pares (entrada, salida), desea encontrar una función que, cuando se alimenta la entrada, la mayoría de las veces proporciona algo cercano a la salida.

Entonces, el objetivo de los problemas NP-completos es obtener un algoritmo, mientras que el aprendizaje automático le da una función. Estos no son exactamente lo mismo, pero puede pensar en un algoritmo como una función. Por ejemplo, todos los algoritmos de ordenación pueden considerarse funciones que toman una matriz sin clasificar y devuelven una matriz ordenada. Pierde información sobre la eficiencia en esta transformación, pero si evaluar la función devuelta por su sistema de aprendizaje automático lleva tiempo polinómico, está bien.

Finalmente, tenemos el siguiente marco: le damos a nuestro sistema de aprendizaje automático un conjunto de pares (entrada, salida) para el problema NP-completo dado. Por ejemplo, para TSP, las entradas serán los gráficos y las salidas serán los recorridos óptimos. El modelo de aprendizaje automático devuelve una función, que toma un nuevo gráfico y devuelve algo . Tendrá que modelar su problema de manera que tenga restricciones para que lo que se devuelva sea al menos un recorrido válido . Suponiendo que sí, ahora tiene una función que toma un gráfico y devuelve un recorrido. Aquí hay algunos problemas periféricos:

¿De dónde obtienes estos datos? Idealmente, para aprender, el sistema de aprendizaje automático requerirá datos con diferentes tamaños de gráficos. A medida que los gráficos se hacen más grandes, solo podrá resolverlos exactamente si tienen una estructura específica. Esto introducirá un sesgo en los datos.
La mayoría de los marcos de aprendizaje automático suponen que la función objetivo que se optimiza es continua y se basan en algoritmos basados en gradientes. Dado que los problemas NP-completos en consideración tienen un espacio de estado discreto, puede requerir modificaciones no triviales a los marcos de aprendizaje automático existentes para obtener algo significativo.

Suponga que de alguna manera evita estos problemas y obtiene una función de su marco de aprendizaje automático.

En la mayoría de los casos, no puede realizar un análisis del peor de los casos en esta función. Esto se debe a que, para un algoritmo, usted sabe con experiencia qué pasos introducirán errores y tiene formas de vincularlos. A menudo, cada paso de un algoritmo está cuidadosamente diseñado para que pueda realizar un análisis de errores. Pero para las funciones devueltas por los sistemas de aprendizaje automático, como SVM o redes neuronales, es muy difícil / imposible razonar dónde funcionará mal la función. Por lo tanto, el marco no es particularmente útil para la comunidad teórica de la informática.

Sin embargo, para la comunidad de investigación de operaciones, podría ser algo útil. Pero, de nuevo, hay algunos problemas por los cuales puede no ser particularmente útil. Primero, como mencioné anteriormente, generar datos imparciales y optimizar la función objetivo no es trivial. En segundo lugar, a menos que haya probado exhaustivamente la función devuelta por el sistema de aprendizaje automático con su algoritmo heurístico y demuestre que es mejor en la mayoría de los casos, es posible que no confíe lo suficiente como para usarlo en la práctica, porque para el algoritmo heurístico, usted ordena de saber que al menos hará algo razonable en la mayoría de los casos, mientras que el algoritmo de aprendizaje automático es más como una caja negra y puede salirse completamente de los rieles de vez en cuando. En tercer lugar, sabes dónde funciona mal el algoritmo heurístico y puedes mejorarlo con el tiempo. La función devuelta por el sistema de aprendizaje automático es mucho menos susceptible a tales mejoras incrementales.

En resumen, con el estado actual del aprendizaje automático y los objetivos de los problemas de NP completo, en la actualidad, no ayuda utilizar el aprendizaje automático para los problemas de NP completo.