Significado (y prueba) de "RNN puede aproximar cualquier algoritmo"

Question

Hace poco leí que una red neuronal recurrente puede aproximarse a cualquier algoritmo.

Así que mi pregunta es: ¿qué significa esto exactamente y puede darme una referencia donde se demuestre esto?

Answer 1

Antecedentes

Primero tenemos que repasar algunos conceptos de la teoría de la computación. Un algoritmo es un procedimiento para calcular una función. Dada la entrada, el algoritmo debe producir la salida correcta en un número finito de pasos y luego terminar. Para decir que una función es computable significa que existe un algoritmo para calcularlo. Entre el conjunto infinito de todas las funciones, la mayoría no son computables. Máquinas de Turing son un modelo matemático que formaliza la noción de computación. Existen otros modelos equivalentes, pero las máquinas de Turing son el "modelo de referencia" estándar. Según el Tesis de Church-Turing Cualquier algoritmo puede ser implementado por una máquina de Turing, y todas las funciones computables pueden ser calculadas de esta manera. Cualquier instancia particular de una máquina de Turing sólo computa una función particular. Pero existe una clase especial de máquinas de Turing llamada máquinas de Turing universales que puede simular cualquier otra máquina de Turing para cualquier entrada. Lo hacen tomando una descripción de la máquina a simular (y su entrada) como parte de su propia entrada. Por tanto, cualquier instancia particular de una máquina de Turing universal puede calcular cualquier función computable (es decir, puede implementar cualquier algoritmo). Cualquier sistema que comparta esta capacidad se denomina Turing completo . Una forma de demostrar que un sistema es completo de Turing es mostrar que puede simular una máquina de Turing universal. Se ha demostrado que muchos sistemas son completos de Turing (por ejemplo, la mayoría de los lenguajes de programación, ciertos autómatas celulares y mecánica cuántica ).

Redes neuronales recurrentes

El siguiente artículo muestra que, para cualquier función computable, existe una red neuronal recurrente (RNN) finita que puede calcularla. Además, existen RNN finitas que son Turing completas, y por tanto pueden implementar cualquier algoritmo.

Siegelmann y Sontag (1992) . Sobre la capacidad de cálculo de las redes neuronales

Utilizan redes que contienen un número finito de unidades conectadas de forma recurrente, que reciben entradas externas en cada momento. El estado de cada unidad viene dado por una suma ponderada de sus entradas (más un sesgo), pasada por una función de activación no lineal. La función de activación es una función lineal saturada, que es una aproximación lineal a trozos de una sigmoidea. Los pesos y los sesgos son fijos, por lo que no se produce ningún aprendizaje.

La red realiza un mapeo de una secuencia binaria de entrada a una secuencia binaria de salida. Hay dos entradas externas a la red, que se introducen en todas las unidades: una "línea de datos" y una "línea de validación". La línea de datos contiene la secuencia de entrada de ceros y unos, y el cero una vez terminada la secuencia de entrada. La línea de validación permite a la red saber cuándo se produce la secuencia de entrada. Contiene un uno durante la duración de la secuencia de entrada, y un cero una vez finalizada. Una unidad se considera la "unidad de salida". Da salida a ceros durante un retardo arbitrario, luego a la secuencia de salida de ceros y unos, y luego a cero después de que la secuencia de salida haya terminado. Otra unidad se considera la "unidad de validación", que nos permite saber cuándo se produce la secuencia de salida. La unidad de validación emite un uno mientras se produce la secuencia de salida, y un cero en caso contrario.

Aunque estas RNN asignan secuencias binarias de entrada a secuencias binarias de salida, podemos estar interesados en funciones definidas sobre otros objetos matemáticos (otros tipos de números, vectores, imágenes, gráficos, etc.). Pero, para cualquier función computable, estos otros tipos de objetos pueden codificarse como secuencias binarias (por ejemplo, véase aquí para una descripción de la codificación de otros objetos mediante números naturales, que a su vez pueden representarse en binario).

Resultado

Demuestran que, para cada función computable, existe una RNN finita (de la forma descrita anteriormente) que puede calcularla. Para ello, demuestran que es posible utilizar una RNN para simular explícitamente un autómata pushdown con dos pilas. Este es otro modelo que es computacionalmente equivalente a una máquina de Turing. Cualquier función computable puede ser calculada por una máquina de Turing. Cualquier máquina de Turing puede ser simulada por un autómata pushdown con dos pilas. Cualquier autómata pushdown con dos pilas puede ser simulado por una RNN. Por lo tanto, cualquier función computable puede ser calculada por una RNN. Además, como algunas máquinas de Turing son universales, las RNN que las simulan son completas de Turing, y por tanto pueden implementar cualquier algoritmo. En particular, demuestran que existen RNN completas de Turing con 1058 o menos unidades.

Otras consecuencias

Una consecuencia interesante de los resultados de la simulación es que ciertas preguntas sobre el comportamiento de las RNN son indecidibles. Esto significa que no existe ningún algoritmo que pueda responderlas para RNN arbitrarias (aunque pueden ser respondidas en el caso de particular RNNs). Por ejemplo, la pregunta de si una unidad dada toma alguna vez el valor 0 es indecidible; si se pudiera responder a esta pregunta en general, sería posible resolver el problema de detención para las máquinas de Turing, que es indecidible.

Potencia de cálculo

En el documento anterior, todos los parámetros y estados de la red son números racionales. Esto es importante porque limita la potencia de las RNN y hace que las redes resultantes sean más realistas. La razón es que los racionales son números computables lo que significa que existe un algoritmo para calcularlos con una precisión arbitraria. La mayoría de los números reales no son computables y, por tanto, son inaccesibles: ni siquiera la máquina de Turing más potente puede representarlos, y mucha gente duda de que puedan representarse en el mundo físico. Cuando tratamos con "números reales" en ordenadores digitales, accedemos a un subconjunto aún más pequeño (por ejemplo, 64 bits punto flotante números). Representar números reales arbitrarios requeriría una información infinita.

El documento dice que dar acceso a la red a los números reales aumentaría la potencia de cálculo aún más, más allá de las máquinas de Turing. Siegelmann ha escrito otros artículos en los que explora esta capacidad "super-Turing". Sin embargo, es importante señalar que se trata de modelos matemáticos y que los resultados no significan que una máquina de este tipo pueda existir realmente en el mundo físico. Hay buenas razones para pensar que no podría, aunque es una cuestión abierta.

Answer 2

Creo que esto es lo que estás buscando. Este tipo demostró que una red multicapa, o incluso una red feedforward de una sola capa, puede aproximar cualquier función, siempre que la red tenga suficientes unidades ocultas.

Hornik, K. (1991). Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2), 251-257.