Redes neuronales artificiales en evolución para resolver problemas de NP

10

Hace poco leí una entrada de blog realmente interesante del Blog de Google Research sobre redes neuronales. Básicamente usan estas redes neuronales para resolver varios problemas como el reconocimiento de imágenes. Utilizan algoritmos genéticos para "evolucionar" los pesos de los axones.

Básicamente, mi idea es la siguiente. Si se supone que debo escribir un programa que reconozca números, no sabría cómo comenzar (podría tener una idea vaga, pero mi punto es: no es trivial ni fácil), pero al usar la red neuronal no tengo que hacerlo. Al crear el contexto correcto para que la red neuronal evolucione, mi red neuronal "encontrará el algoritmo correcto". A continuación, cité una parte realmente interesante del artículo donde explican cómo cada capa tiene un papel diferente en el proceso de reconocimiento de imágenes.

Uno de los desafíos de las redes neuronales es comprender qué sucede exactamente en cada capa. Sabemos que después del entrenamiento, cada capa extrae progresivamente las características de nivel superior e superior de la imagen, hasta que la capa final esencialmente toma una decisión sobre lo que muestra la imagen. Por ejemplo, la primera capa puede buscar bordes o esquinas. Las capas intermedias interpretan las características básicas para buscar formas o componentes generales, como una puerta o una hoja. Las pocas capas finales las agrupan en interpretaciones completas: estas neuronas se activan en respuesta a cosas muy complejas, como edificios enteros o árboles.

Básicamente, mi pregunta es la siguiente: ¿No podríamos usar algoritmos genéticos + redes neuronales para resolver todos los problemas de NP? Simplemente creamos el contexto evolutivo correcto y dejamos que la "naturaleza" encuentre una solución.

Inceptionism: profundizando en redes neuronales

EDITAR: Sé que podemos usar Brute-Force o encontrar una solución no eficiente en muchos casos. Es por eso que trato de resaltar la evolución de las redes neuronales artificiales. Como dije en un comentario: dado el tiempo suficiente y una tasa de mutación adecuada, podríamos encontrar la solución óptima (o al menos eso es lo que creo).

Concepto

NMO
fuente
1
No tenemos que hacerlo. Simplemente podemos usar la fuerza bruta. ¿Cuál es tu objetivo, exactamente?
Pål GD
2
No soy un experto en redes neuronales, así que no sé si pueden ser entrenados para resolver problemas NP correctamente. Pero no creo que estés haciendo la pregunta correcta. Encontrar un algoritmo que resuelva un problema contenido en NP generalmente no es difícil, solo verifique todas las soluciones posibles. Sin embargo, encontrar un algoritmo que resuelva un problema NP-difícil en el tiempo polinomial es una historia diferente y su existencia es altamente improbable. Dado que las redes neuronales pueden ser simuladas por una máquina de enrutamiento, todavía necesitan un tiempo súper polinómico a menos que P = NP y no serán de mucha ayuda.
Dennis Kraft
Sí, las redes neuronales se han utilizado contra problemas completos de NP, por ejemplo, el vendedor ambulante y muchos otros, y hay investigaciones / literatura sobre el tema. pueden tener algunas propiedades útiles, pero no se alejan de las limitaciones de tiempo de la teoría de la complejidad como señala DK.
vzn
Mi punto es: usando una tasa de mutación adecuada y el tiempo suficiente podríamos (al menos teóricamente) encontrar la solución óptima. (O al menos un máximo local) Imagen: Concepto
NMO
2
Los algoritmos genéticos (y el resto del lote de técnicas de "IA") son esencialmente aleatorios "pruebe una muestra del espacio de solución" con algunos conocimientos (heurísticos) para que no sea totalmente aleatorio. No, no es mejor que "probar todas las soluciones posibles", la mayoría de las veces mucho peor (ya que no hay garantía de no volver a comprobar el mismo caso descartado). Claro, encuentran soluciones "decentes". Pero queremos encontrar lo mejor .
vonbrand

Respuestas:

21

No. Es poco probable que esta dirección sea útil, por dos razones:

  1. La mayoría de los informáticos creen que P NP. Suponiendo P NP, esto significa que no existe ningún algoritmo de tiempo polinómico para resolver ningún problema de NP completo. Si desea que su red neuronal resuelva el problema en un período de tiempo razonable, entonces no puede ser demasiado grande y, por lo tanto, la red neuronal será un algoritmo de tiempo polinómico. Se deduce que si P NP, las redes neuronales no pueden resolver eficientemente ningún problema de NP completo.

  2. Las redes neuronales no son "mágicas". Son una forma de tratar de encontrar patrones. Para algunos problemas en los que se pueden encontrar patrones lo suficientemente fuertes, y los patrones se pueden aprender de un número razonable de ejemplos, pueden ser efectivos. Pero no son polvo mágico de hadas. El hecho de que pueda configurar una red neuronal no significa que la propagación hacia atrás necesariamente encuentre una buena manera de resolver su problema. Puede ser que no se encuentren patrones, que los patrones solo se puedan descubrir con un número inviable de ejemplos, o que existan patrones pero el procedimiento de entrenamiento de la red neuronal no pueda encontrarlos.

Las redes neuronales son solo otra forma de aprendizaje automático. Podríamos hacer los mismos comentarios sobre SVM o bosques aleatorios o regresión lineal sobre cualquier otra forma de aprendizaje automático. Las redes neuronales no son una especie de bala de plata mágica que resuelve todos los problemas de aprendizaje automático. Son casi tan efectivos como otros métodos de aprendizaje automático, o para algunos tipos de problemas, quizás un poco más efectivos, pero no son mágicos.

A veces me encuentro con personas que han escuchado solo un poco acerca de las redes neuronales, y se van pensando que las redes neuronales son la respuesta a todo, tal vez porque escucharon que "su cerebro también usa redes neuronales", o vieron algunas muy aplicación genial (reconocimiento de voz o algo). Pero no te dejes engañar. No te creas la exageración. Las redes neuronales son una técnica útil, pero no permitirán que las computadoras resuelvan problemas de NP completo, o que superen la prueba de Turing, eliminen todos nuestros trabajos y reemplacen a los humanos con computadoras. No en cualquier momento pronto, de todos modos. Eso es solo ciencia ficción.

DW
fuente
1
Muy buena respuesta. Algoritmos genéticos + Redes neuronales parece muy poderoso, pero tal vez no sea suficiente para resolver todos los problemas de np. Me imagino dejando estas redes neuronales + algoritmos genéticos en la naturaleza en busca de estas soluciones p. Como pequeños exploradores jaja.
NMO
1
También vale la pena señalar que las redes neuronales generalmente brindan cierta probabilidad de encontrar la respuesta correcta, no una garantía. Cuando relaja los requisitos de su problema para permitir soluciones subóptimas, a menudo existen soluciones prácticas para los problemas de NP completo, a pesar de su intratabilidad en el peor de los casos.
Dan Bryant
9

Parece que otras respuestas, aunque informativas / útiles, en realidad no comprenden su pregunta exactamente y leen demasiado. No preguntó si las redes neuronales superarían a otros métodos, solo preguntó si podrían aplicarse a problemas completos de NP. La respuesta es sí, con cierto éxito y esto se conoce desde hace décadas y existe una gran variedad de investigaciones sobre esto, y continúa. Esto tiene que ver con la flexibilidad del aprendizaje automático. Tenga en cuenta que incluso si no encuentran soluciones exactas u óptimas, las soluciones que tienen pueden tener otras propiedades deseables. algunos documentos de ejemplo:

vzn
fuente
4

Las redes neuronales en realidad no resuelven problemas de NP completo. Lo que hacen es resolver problemas que están notablemente cerca de los problemas de NP completo.

Una gran característica de las redes neuronales es que no están obligadas a encontrar la respuesta "correcta" cada vez. Se les permite estar "equivocados". Por ejemplo, es posible que esté resolviendo un problema de empaquetamiento de contenedores, y encuentre una solución que tenga un 1% de descuento de la solución ideal y esté totalmente satisfecho con esa respuesta.

Si elimina el requisito de tener el 100% de razón cada vez, otros enfoques de resolución de problemas funcionan muy bien. Por ejemplo, muchos algoritmos de planificación de rutas (como Google Maps) tienen que ser NP completos, pero es bastante trivial encontrar un algoritmo que encuentre una ruta dentro del 1% del 99.9% óptimo del tiempo. Está tratando de precisar los resultados en ese último 0.1% de los casos que hacen que los esfuerzos completos de NP sean tan abrumadoramente caros.

Resulta que cuando intentamos usar ecuaciones completas de NP en la vida real, a menudo no necesitamos la respuesta real . A menudo nos sentimos muy cómodos con una respuesta "cercana", aunque a menudo no tenemos una redacción que explique qué métrica "cercana" estamos usando. Estas son las situaciones en las que una red neuronal puede responder la pregunta real que quería hacer, en lugar de tener que resolver el problema de NP completo que solicitó.

Cort Ammon
fuente
1

Se sabe que las redes neuronales son capaces de aproximación de funciones universales , pero esto requiere entrenarlas en el problema (optimización), que es un problema NP-completo en sí mismo , y es por eso que tiene entrenamiento evolutivo y SGD con propagación hacia atrás, etc.

Entonces, aunque no es probable que resuelvan problemas de NP completo, pueden ser entrenados para aproximar a un grado arbitrario de precisión una función que modela el problema. Además, incluso si resuelve un problema de NP-completo de manera óptima utilizando una red neuronal, todavía no tiene forma de demostrar que la solución que encontró es en realidad el óptimo global sin la fuerza bruta de la solución (por supuesto, esto no es factible para casi cualquier práctica caso de uso de redes neuronales).

Su visualización es precisa en el sentido de que los algoritmos evolutivos (vea cómo el algoritmo ordenado evita que una sola especie se apodere de la población con una estructura inicialmente altamente eficiente mediante el uso de la aptitud compartida) son menos aptos que el SGD y otras técnicas de aprendizaje automático para quedar atrapados en optimistas locales, pero no proporcionan pruebas de que la solución que encuentran es, de hecho, la solución óptima global.

nickw
fuente
¿Podría agregar algunas referencias a su respuesta? Además, intente mejorar el formato (por ejemplo, use NP, SGD, retropropagación, etc., y quizás agregue algunos saltos de línea).
Yuval Filmus
Muy bien, hice algunas ediciones, hágame saber si debo profundizar más en cualquier lugar
nickw
Creo que debería proporcionar alguna justificación para su afirmación de que "los algoritmos evolutivos ... son menos aptos que SGD y otras técnicas de aprendizaje automático para quedar atrapados en los óptimos locales". No creo que sea correcto, especialmente para la tarea particular de entrenar redes neuronales.
DW
Esta respuesta tiene cierta confusión sobre la definición de completitud NP. Contrariamente a lo que usted dice, si resolvemos un problema NP-completo, nos podemos comprobar si tenemos la solución correcta. Hay una diferencia entre un problema de búsqueda NP-complete y un problema de optimización NP-hard; para el primero, podemos verificar de manera eficiente si la solución es correcta, pero para el segundo quizás no podamos hacerlo.
DW
Califiqué que no pudimos verificar que es la solución óptima sin forzar primero la solución verdaderamente óptima, ¿no es esto correcto? Proporcioné justificación para mi razonamiento de que la neuroevolución es menos apta para atascarse en los óptimos locales con el enlace referenciado al algoritmo ordenado y la aptitud compartida, creo que la susceptibilidad de los descensos de gradiente a quedarse atascado en los óptimos locales es bastante evidente, y aunque un ajuste de hiperparámetro el marco puede ayudar a aliviar esto, no lo atribuiría como una aversión que el sgd posee para atascarse.
nickw