¿Qué es una prueba intuitiva de que las redes neuronales recurrentes pueden calcular cualquier función computable por una máquina Turing?

Editar: cuando se publicó esta pregunta, estaba preguntando sobre el Teorema de Aproximación Universal; Si está buscando una respuesta a la pregunta como es ahora, la respuesta a continuación podría ayudar, pero está muy lejos de ser una explicación real.

El teorema de aproximación universal, hasta donde yo sé, solo afirma que las redes neuronales de una sola capa pueden aproximarse a funciones continuas en subconjuntos compactos de R ^ n.

Un “subconjunto compacto de los reales” es solo un subconjunto cerrado (es decir, [1, 3], no (1, 3)) y “limitado” (es decir, la distancia entre dos puntos en el conjunto es menor que algún número) . Entonces, por ejemplo, [1, 3] U [5, 6] es un “subconjunto compacto de R”. En resumen: la compacidad es generalmente una buena suposición para los problemas del mundo real.

En cuanto a demostrar que puede aproximarse a una función continua, definamos primero qué entendemos exactamente por “continuo”. Intuitivamente, una función es continua si los puntos que están “cerca” entre sí tienen valores “similares”, es decir, “un pequeño cambio en x conduce a un pequeño cambio en f (x)”.

Existe un teorema increíblemente útil, que establece que cualquier función continua puede aproximarse con la precisión que desee mediante una función de paso. Por ejemplo, aquí está el pecado (6x) que se aproxima mediante una función de paso:

Cuanto más pequeño sea el ancho de los pasos, mejor será una aproximación.


Muy bien, ahora a las redes neuronales. En una dimensión, cada neurona de entrada tiene la forma ∂ (a * x + b), donde “∂” es una función monótona de -1 a 1 (o 0 a 1, o lo que sea). Aquí hay un gráfico de dos neuronas y lo que resumen:

El parámetro “a” nos permite hacer que estas neuronas sean tan empinadas como queramos. Por ejemplo, si establecemos a = 10 (en lugar de a = 1) para ambas neuronas, obtenemos:

Entonces, estas dos neuronas sumadas nos dicen si x está entre 0 o 2. Agregando pares adicionales de neuronas, descubramos si x está entre otros dos puntos:

Si agregamos 16 neuronas más (una para [-10, -8], una para [-8, -6], una para [-6, -4], etc.), entonces la neurona de salida puede mirar nuestra neurona -pares y determinar en qué intervalo se encuentra la “x” original, y luego asignarla al valor correcto. En otras palabras, la neurona de salida está tomando los “pasos” que hicieron las neuronas ocultas y calculando qué tan alto hacer cada paso, ¡que está empezando a sonar muy bajo como una función de paso!

Lo hace con los pesos que elige. En el ejemplo anterior, digamos f (1) = 0.5 yf (5) = -0.5. Entonces la neurona de salida intentaría decir (0.5) * (n1 + n2) + (-0.5) * (n3 + n4). Los números reales serían un poco diferentes (porque la neurona de salida también pasa su salida a través de una función sigmoidea, y “n1 + n2” no llega a 1 (solo sube a ~ 0.6 en el ejemplo anterior), pero La idea sigue funcionando.

Otra forma de pensar en esto es pensar que la capa oculta representa una “expansión de características” de la entrada: convierte un valor inocente de “x” en una tonelada de ceros y casi unos que indican qué pasos “x” pertenece a. Luego, la neurona de salida utiliza esta función de expansión para calcular la función de paso real.

Entonces, el argumento dice: las redes neuronales (pueden) aproximar funciones escalonadas que (pueden) aproximar funciones continuas. Obviamente, las redes neuronales pueden hacer mucho más que simplemente aproximar una función de paso.

Editar: esto se extiende muy naturalmente a dimensiones más altas, solo se necesitan más de 2 neuronas para representar un “paso”. Si X es 2D necesitas 3 neuronas. Si X es 4D, necesita 4, etc. Esto se debe a que necesita el simplex de la dimensión para definir adecuadamente el equivalente de un “paso” en dimensiones superiores.

Editar: wow, lo siento, me perdí totalmente la palabra “recurrente”, pero dado que las redes recurrentes son literalmente redes neuronales de alimentación directa con algunas entradas adicionales (ignorando los problemas de entrenamiento), el mismo argumento aún debería mantenerse.

También vale la pena señalar que en la vida real es poco probable que una red neuronal aprenda algo como esta representación de función de paso, ¡solo porque sea capaz de representar una función continua de esta manera no significa que es probable que converja en esta solución! Y, más concretamente, si su red “una primera capa converge a una solución que parece funcional, no es probable que desee utilizar una red neuronal a menos que tenga muchos más datos de los que necesita (I” sospecha que está sobreajustado de lo contrario).

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 finalizar. Decir que una función es computable significa que existe un algoritmo para calcularla. Entre el conjunto infinito de todas las funciones, la mayoría no son computables. Las 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. De acuerdo con la tesis de Church-Turing, cualquier algoritmo puede ser implementado por una máquina de Turing, y todas las funciones computables se pueden calcular de esta manera. Cualquier instancia particular de una máquina de Turing solo calcula una función particular. Pero, existe una clase especial de máquinas de Turing llamadas máquinas de Turing universales que pueden simular cualquier otra máquina de Turing para cualquier entrada. Lo hacen tomando una descripción de la máquina que se simulará (y su entrada) como parte de su propia entrada. Por lo tanto, cualquier instancia particular de una máquina Universal Turing puede calcular cualquier función computable (es decir, puede implementar cualquier algoritmo). Cualquier sistema que comparta esta habilidad se llama Turing completo. Una forma de demostrar que un sistema está completo en Turing es demostrar que puede simular una máquina universal de Turing. Se ha demostrado que muchos sistemas son Turing completos (por ejemplo, la mayoría de los lenguajes de programación, ciertos autómatas celulares y la mecánica cuántica).

Redes neuronales recurrentes

El siguiente documento muestra que, para cualquier función computable, existe una red neuronal recurrente finita (RNN) que puede computarla. Además, existen RNN finitos que están completos en Turing y, por lo tanto, pueden implementar cualquier algoritmo.

Siegelmann y Sontag (1992). Sobre el poder computacional de las redes neuronales

Utilizan redes que contienen un número finito de unidades conectadas de forma recurrente, que reciben entradas externas en cada punto de tiempo. El estado de cada unidad viene dado por una suma ponderada de sus entradas (más un sesgo), ejecutada a través de 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 por partes de un sigmoide. Los pesos y sesgos son fijos, por lo que no se produce aprendizaje.

La red realiza una asignación de una secuencia de entrada binaria a una secuencia de salida binaria. Hay dos entradas externas a la red, que se alimentan a 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, luego cero después de que finaliza la secuencia de entrada. La línea de validación le permite a la red saber cuándo está ocurriendo la secuencia de entrada. Contiene uno para la duración de la secuencia de entrada, luego cero después de que haya terminado. Una unidad se considera la ‘unidad de salida’. Produce ceros para un retraso arbitrario, luego la secuencia de salida de ceros y unos, luego cero después de que la secuencia de salida ha terminado. Se considera que otra unidad es la ‘unidad de validación’, que nos permite saber cuándo está ocurriendo la secuencia de salida. Emite uno mientras la secuencia de salida está sucediendo, y cero en caso contrario.

Aunque estos RNN asignan secuencias de entrada binarias a secuencias de salida binarias, podríamos estar interesados ​​en funciones definidas en varios 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, vea aquí una descripción de la codificación de otros objetos usando números naturales, que a su vez pueden representarse en binario).

Resultado

Muestran que, para cada función computable, existe un RNN finito (de la forma descrita anteriormente) que puede calcularlo. Hacen esto mostrando que es posible usar un 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 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 un RNN. Por lo tanto, cualquier función computable puede ser calculada por un RNN. Además, debido a que algunas máquinas de Turing son universales, los RNN que las simulan son completas y, por lo tanto, pueden implementar cualquier algoritmo. En particular, muestran que existen RNN completos 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 los RNN son indecidibles. Esto significa que no existe un algoritmo que pueda responderlos para RNN arbitrarios (aunque pueden ser responsables en el caso de RNN particulares ). Por ejemplo, la cuestión de si una unidad dada toma el valor 0 es indecidible; Si se pudiera responder a esta pregunta en general, sería posible resolver el problema de detención de 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 el poder de los 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 precisión arbitraria. La mayoría de los números reales son irrebatibles y, por lo tanto, inaccesibles, incluso la máquina de Turing más poderosa no puede representarlos, y muchas personas dudan de que puedan ser representados en el mundo físico. Cuando tratamos con ‘números reales’ en computadoras digitales, estamos accediendo a un subconjunto aún más pequeño (por ejemplo, números de coma flotante de 64 bits). Representar números reales arbitrarios requeriría información infinita.

El documento dice que dar acceso a la red a números reales aumentaría aún más la potencia computacional, más allá de las máquinas Turing. Siegelmann escribió una serie de otros documentos que exploran esta capacidad de ‘super-Turing’. Sin embargo, es importante tener en cuenta que estos son modelos matemáticos, y los resultados no significan que tal máquina realmente pueda existir en el mundo físico. Hay buenas razones para pensar que no podría, aunque es una pregunta abierta.

Mi prueba favorita fue de Frédéric Gruau . Escribió un compilador de Pascal a red neuronal. Como Pascal es Turing universal, las redes neuronales también deben serlo. QED

More Interesting

¿Cómo funciona la distribución de probabilidad al construir una nueva variable aleatoria?

¿En qué ciencia necesitas pensar más analítica y lógicamente?

¿Hay algún algoritmo del orden O (sqrt (n))?

En la clasificación de texto, ¿hay alguna manera de evitar los mismos resultados para 'hacer adición' y adición?

Sea G un simple gráfico plano conectado con menos de 30 aristas. ¿Cómo puedo mostrar que un gráfico G contiene un nodo cuyo grado es máximo 4?

¿Es posible crear un lenguaje completo de Turing con solo un puntero de instrucción modificable, una operación de intercambio y un incremento por una operación?

¿Cómo los logaritmos convierten la multiplicación en suma?

¿Cuál es la diferencia entre la informática teórica y las matemáticas discretas?

¿Cuáles son algunas formas interesantes de usar tecnologías no convencionales en la programación?

Las calificaciones en una prueba intermedia se distribuyen normalmente con una media de 69 y una desviación estándar de 10. ¿Cuál es la probabilidad de que una clase de 27 tenga un promedio menor de 67 (3 lugares decimales)? ¿Cómo hago esto?

¿Alguien puede mostrarme la relación de recurrencia?

Cómo pasar por las clases de GE

¿Es el código de computadora una forma de representación matemática?

¿Volver a la Universidad para estudiar Matemáticas me ayudará a comprender completamente la lógica del algoritmo de la IA y la Programación Funcional?

¿Cómo se usa el cálculo multivariable en informática?