recursion - ¿Pueden las estructuras de Machine Learning existentes emular perfectamente funciones recursivas como la secuencia de Fibonacci?
machine-learning neural-network (5)
La secuencia de Fibonacci, donde se debe devolver un índice específico de la secuencia, se usa a menudo como un problema de referencia en la investigación de Programación Genética. En la mayoría de los casos, se generan estructuras recursivas, aunque mi propia investigación se centró en programas imperativos, por lo que usé un enfoque iterativo.
Hay una breve reseña de otra investigación de médicos de cabecera que utiliza el problema de Fibonacci en la Sección 3.4.2 de mi tesis doctoral, disponible aquí: http://kar.kent.ac.uk/34799/ . El resto de la tesis también describe mi propio enfoque, que se trata un poco más brevemente en este documento: http://www.cs.kent.ac.uk/pubs/2012/3202/
Otra investigación notable que utilizó el problema de Fibonacci es el trabajo de Simon Harding con el Auto-Modificador Cartesiano GP ( http://www.cartesiangp.co.uk/papers/eurogp2009-harding.pdf ).
Para ser claro , no quiero decir, siempre que los dos últimos números de la secuencia proporcionen el siguiente:
(2, 3, -> 5)
Pero dado que cualquier índice proporciona el número de Fibonacci:
(0 -> 1) or (7 -> 21) or (11 -> 144)
Agregar dos números es una tarea muy simple para cualquier estructura de aprendizaje automático y, por extensión, el conteo por unidades, dos o cualquier número fijo es una regla de suma simple. Cálculos recursivos sin embargo ...
A mi entender, la mayoría de las redes de aprendizaje se basan en la evaluación solo hacia adelante, mientras que la mayoría de los lenguajes de programación tienen bucles, saltos o patrones de flujo circular (todos los cuales suelen ser saltos de ASM de algún tipo), lo que permite la recursión.
Claro que algunas redes no son solo hacia adelante; Pero, ¿puede el procesamiento de pesos utilizando la función hiperbólica tangente o sigmoidea ingresar a un estado computacionalmente completo?
es decir, sentencias condicionales, saltos condicionales, saltos forzados, bucles simples, bucles complejos con múltiples condiciones, proporcionando orden de clasificación, reordenamiento real de los elementos, asignaciones, asignación de registros adicionales, etc.
Parecería que incluso una red que no sea solo de forwards solo encontraría un polinomio de mejor ajuste, reduciendo los errores a lo largo de la extensión del conjunto de entrenamiento y no más allá.
¿Me estoy perdiendo algo obvio, o la mayor parte del Aprendizaje automático solo observó la recursión y fingí que esos problemas no existen?
Actualizar
Técnicamente, cualquier lenguaje de programación puede considerarse el ADN de un algoritmo genético, donde el compilador (y posiblemente la medición fuera de consola) sería la función de adecuación. El problema es que la programación (hasta ahora) no se puede expresar en una escalada de pendientes: literalmente, la condición física es 0, hasta que la condición física es 1. Las cosas no funcionan a medias en la programación, y si lo hacen, no hay forma de Medir cómo "trabajar" un programa es para situaciones desconocidas. Incluso un error por un error podría parecer un sistema totalmente diferente y caótico sin salida. Esta es exactamente la razón por la que aprender a codificar en primer lugar es tan difícil, la curva de aprendizaje es casi vertical.
Algunos pueden argumentar que solo necesita proporcionar reglas de cimientos más sólidas para que el sistema las explote, pero eso solo conduce a intentar generalizar todos los problemas de programación, lo que hace que los círculos regresen al diseño de un lenguaje de programación y pierda la noción de alguna máquina de aprendizaje. Seguir este camino te lleva a una variante cercana de LISP con código capaz de mutar y virtualmente funciones sin sentido que impiden que el espacio de código tenga un aspecto ''agradable'' y ''simple'' en un intento de seguir las mejores prácticas de codificación humana.
Otros podrían argumentar que simplemente no estamos usando suficiente población o impulso para ganar pie en la superficie del error, o dar un paso significativo hacia una solución. Pero a medida que su población se aproxima al número de permutaciones del ADN, en realidad solo está siendo forzado brutalmente (y eso es muy ineficiente). Brute forzando las permutaciones de código no es nada nuevo, y definitivamente no es de aprendizaje automático; en realidad es bastante común en el regex golf, creo que incluso hay un xkcd al respecto ...
El problema real no es encontrar una solución que funcione para alguna función recursiva específica, sino encontrar un espacio de solución que pueda abarcar el dominio recursivo de alguna manera útil.
Entonces, además de las Redes neuronales entrenadas usando Backpropagation, hipotéticamente encuentran la forma cerrada de una función recursiva (si existe una forma cerrada, y en la mayoría de los casos reales no es útil la recursión), o una red de no reenvío solo que actúa como un lenguaje de pseudo-programación con horribles perspectivas de acondicionamiento físico en el mejor de los casos, más la tarea prácticamente imposible de ajustar las restricciones de salida para evitar la recursión infinita ... ¿De verdad es así para el aprendizaje automático y la recursión?
Los algoritmos genéticos deberían ser capaces de hacer el truco. Lo importante es (como siempre con los AG) la representación.
Si define el espacio de búsqueda como árboles de sintaxis que representan fórmulas aritméticas y proporciona suficientes datos de entrenamiento (como lo haría con cualquier algoritmo de aprendizaje automático), probablemente converja a la solución de formato cerrado para los números de Fibonacci , que es:
Fib (n) = ((1 + srqt (5)) ^ n - (1-sqrt (5)) ^ n) / (2 ^ n * sqrt (5)) [ Source ]
Si estaba solicitando un algoritmo de aprendizaje automático para obtener la fórmula recursiva de los números de Fibonacci, esto también debería ser posible utilizando el mismo método, pero los individuos son árboles de sintaxis de un programa pequeño que representa una función.
Por supuesto, también debe definir buenos operadores de cruce y mutación, así como una buena función de evaluación. Y no tengo idea de lo bien que convergería, pero debería hacerlo en algún momento.
Edición: También me gustaría señalar que en ciertos casos siempre hay una solución de forma cerrada para una función recursiva:
Como cada secuencia definida por una recurrencia lineal con coeficientes constantes , los números de Fibonacci tienen una solución de forma cerrada.
Ok, por donde empezar ...
En primer lugar, se habla de ''aprendizaje automático'' y ''emulación perfecta''. Este no es generalmente el propósito de los algoritmos de aprendizaje automático. Hacen suposiciones informadas, dadas algunas evidencias y algunas nociones generales sobre las estructuras que existen en el mundo. Eso generalmente significa que una respuesta aproximada es mejor que una "exacta" que es incorrecta. Entonces, no, la mayoría de los enfoques de aprendizaje automático existentes no son las herramientas adecuadas para responder a su pregunta.
Segundo, hablas de "estructuras recursivas" como una especie de bala mágica. Sin embargo, son meras formas convenientes de representar funciones, algo análogas a las ecuaciones diferenciales de orden superior. Debido a las reacciones que tienden a introducir, las funciones tienden a ser no lineales. Algunos enfoques de aprendizaje automático tendrán problemas con esto, pero muchos (las redes neuronales, por ejemplo) deberían poder aproximarse bastante bien si se cuenta con suficiente evidencia .
Dejando de lado, tener o no tener soluciones de forma cerrada es algo irrelevante aquí. Lo que importa es qué tan bien se ajusta la función con los supuestos incorporados en el algoritmo de aprendizaje automático. Esa relación puede ser compleja (por ejemplo: intente aproximar a fibbonacci con una máquina de vectores de soporte), pero esa es la esencia.
Ahora, si desea un algoritmo de aprendizaje automático adaptado a la búsqueda de representaciones exactas de estructuras recursivas, puede establecer algunas suposiciones y hacer que su algoritmo produzca la estructura recursiva "exacta" más probable que se ajuste a sus datos. Probablemente hay problemas del mundo real en los que tal cosa sería útil. De hecho, el campo de la optimización aborda problemas similares.
Los algoritmos genéticos mencionados en otras respuestas podrían ser un ejemplo de esto, especialmente si proporcionó un ''genoma'' que coincida con el tipo de función recursiva con la que cree que está tratando. Los primitivos de forma cerrada también podrían formar parte de ese espacio, si crees que es más probable que sean "exactos" que los algoritmos genéticos más complejos.
Con respecto a su afirmación de que la programación no se puede expresar en una escalada, eso no impide que un algoritmo de aprendizaje marque las posibles soluciones según la cantidad de evidencia que puede reproducir y su complejidad. En muchos casos (la mayoría? Aunque aquí no es realmente posible contar los casos) tal enfoque encontrará una respuesta correcta. Claro, puedes llegar a casos patológicos, pero con esos, hay poca esperanza de todos modos.
En resumen, los algoritmos de aprendizaje automático no suelen estar diseñados para hacer frente a la búsqueda de soluciones "exactas", por lo que no son las herramientas adecuadas tal como están. Sin embargo, al incorporar algunas suposiciones previas de que las soluciones exactas son las mejores, y quizás el tipo de solución exacta que está buscando, probablemente le irán muy bien con los algoritmos genéticos, y probablemente también con algoritmos como las máquinas de vectores de soporte.
Creo que también resumís bien las cosas con esto:
El problema real no es encontrar una solución que funcione para alguna función recursiva específica, sino encontrar un espacio de solución que pueda abarcar el dominio recursivo de alguna manera útil.
Las otras respuestas van un largo camino para decirle dónde está el estado de la técnica. ¡Si quieres más, te espera un nuevo y brillante camino de investigación!
Según Kolmogorov et al. En la representación de funciones continuas de muchas variables por superposición de funciones continuas de una variable y suma, una red neuronal de tres capas puede modelar una función arbitraria con las funciones lineales y logísticas, incluyendo f(n) = ((1+sqrt(5))^n - (1-sqrt(5))^n) / (2^n * sqrt(5)) , que es la solución de forma cerrada de la secuencia de Fibonacci.
Si quisiera tratar el problema como una secuencia recursiva sin una solución de forma cerrada, lo vería como un enfoque especial de ventana deslizante (lo llamé especial porque el tamaño de su ventana parece fijo en 2). Hay estudios más generales sobre el tamaño de ventana adecuado para su interés. Vea estos dos mensajes:
Predicción de series de tiempo a través de redes neuronales
Forma adecuada de utilizar la red neuronal recurrente para el análisis de series de tiempo
Ver este artículo:
Las máquinas de Turing son redes neuronales recurrentes
http://lipas.uwasa.fi/stes/step96/step96/hyotyniemi1/
El artículo describe cómo una red neuronal recurrente puede simular una máquina de registro, que se sabe que es un modelo computacional universal equivalente a una máquina de Turing. El resultado es "académico" en el sentido de que las neuronas tienen que ser capaces de computar con números ilimitados. Esto funciona matemáticamente, pero tendría problemas pragmáticamente.
Debido a que la función de Fibonacci es solo una de las muchas funciones computables (de hecho, es primitiva recursiva), tal red podría calcularla.