neural network - que - ¿Cuán útil es la completitud de Turing? ¿Las redes neuronales están completas?
redes neuronales combativas 2018 (10)
Básicamente significa que con el lenguaje de programación o la arquitectura que están completos Turing
puede ejecutar una amplia variedad de algoritmos ... principalmente - cualquier tipo de ellos.
Los lenguajes no-Turing tienen un potencial mucho más estricto.
Mientras leía algunos artículos sobre la completitud de Turing de las redes neuronales recurrentes (por ejemplo: computación de Turing con redes neuronales, Hava T. Siegelmann y Eduardo D. Sontag, 1991), tuve la sensación de que la prueba que allí se presentaba no era realmente cierta. práctico. Por ejemplo, el documento al que se hace referencia necesita una red neuronal cuya actividad neuronal debe ser de exactitud infinita (para representar con fiabilidad cualquier número racional). Otras pruebas necesitan una red neuronal de tamaño infinito. Claramente, eso no es realmente tan práctico.
Pero comencé a preguntarme si tendría sentido pedir completa integridad. Según la definición estricta, hoy en día no se ha completado ningún sistema informático porque ninguno de ellos podrá simular la cinta infinita.
Curiosamente, la especificación del lenguaje de programación lo deja más a menudo abierto si están completos o no. Todo se reduce a la pregunta de si siempre podrán asignar más memoria y si el tamaño de la pila de llamadas a funciones es infinito. La mayoría de las especificaciones realmente no especifican esto. Por supuesto, todas las implementaciones disponibles están limitadas aquí, por lo que todas las implementaciones prácticas de lenguajes de programación no están completas.
Entonces, lo que puede decir es que todos los sistemas informáticos son igual de poderosos que las máquinas de estado finito y no más.
Y eso me lleva a la pregunta: ¿Qué tan útil es el término Turing en absoluto?
Y de vuelta a las redes neuronales: para cualquier implementación práctica de una red neuronal (incluido nuestro propio cerebro), no podrán representar un número infinito de estados, es decir, mediante la definición estricta de completitud de Turing, no están completos. Entonces, ¿la pregunta de si las redes neuronales son completas tienen sentido?
La pregunta de si son tan poderosas como las máquinas de estados finitos ya fue respondida mucho antes (1954 por Minsky, la respuesta, por supuesto, sí) y también parece más fácil de responder. Es decir, al menos en teoría, eso ya era la prueba de que son tan poderosos como cualquier computadora.
Algunas otras preguntas que son más acerca de lo que realmente quiero saber:
¿Hay algún término teórico que pueda decir algo más específico sobre el poder computacional de una computadora? (dado su espacio de memoria limitado)
¿Cómo se puede comparar el poder computacional de las implementaciones prácticas de redes neuronales con las computadoras? (La completitud de Turing no es útil como se argumentó anteriormente).
Casi siempre es bueno saber qué clase de jerarquía de Chomsky es tu sistema. Esto es especialmente importante en las clases más restringidas, como los lenguajes regulares / autómatas finitos vs idiomas sin contexto. También es importante tener en cuenta la habilidad para reconocer en qué clase está el problema que está tratando de resolver, de lo contrario uno podría intentar hacer cosas tontas como analizar HTML o XML solo con expresiones regulares, lo que es imposible.
Tener el conocimiento de que su formalismo o sistema está completamente terminado hace una declaración de que puede construir lo que quiera con él. No dice nada sobre la practicidad, solo la posibilidad o la imposibilidad de resolver problemas. Esto es dolorosamente cierto cuando se consideran los alquitranes, pero también hay muchos sistemas completos que están hechos específicamente para fines de nicho que nadie debería soñar con utilizar para trabajos de propósito general en un entorno de producción.
En resumen, un buen conocimiento de la jerarquía de Chomsky te ayudará en muchas situaciones, no solo para elegir el tipo correcto de analizador sintáctico; expresiones regulares, pushdown, CFG o más potentes, pero también para elegir el tipo correcto de máquina o formalismo para expresar procesos en general.
Creo que el concepto de integridad de Turing no pretende decirnos si una computadora en particular puede realizar una tarea en particular.
Más bien, tiene el propósito de decir si un idioma en particular es capaz de expresar una tarea en particular. Es decir, yo diría que se trata de expresar un algoritmo que no lo está ejecutando .
Como las redes neuronales no tienen un lenguaje, se trata de expresar un algoritmo en términos de una red neuronal, en lugar de la capacidad de esa red. ¡Así que no sé la respuesta al último bit de tu pregunta!
Creo que un punto importante acerca de la máquina de turing es que para cualquier entrada y programa dado , la máquina solo necesitará una cantidad finita de cinta, suponiendo que se detenga un tiempo. Es por eso que diría que el término "turing completo" es útil: solo necesita memoria finita para ejecutar un programa específico de turing completo en alguna entrada específica (si el programa se detiene). Pero si tiene una máquina / lenguaje / tecnología no completa, no podrá simular ciertos algoritmos, no importa cuánta memoria agregue.
Cuando se dice que las computadoras modernas son Turing Complete, hay una excepción tácita para el dispositivo de almacenamiento infinito descrito por Turing, que obviamente es una imposibilidad en un dispositivo de cálculo físico finito. Si un dispositivo de computación puede hacer todo lo que una máquina de Turing puede hacer (sin importar el almacenamiento infinito), está completo para todos los propósitos prácticos. Según esta definición menos estricta de completitud de Turing , sí, es posible que muchas redes neuronales estén completas .
Por supuesto, es posible crear uno que no esté completo .
El punto de afirmar que un modelo matemático es Turing Complete es revelar la capacidad del modelo para realizar cualquier cálculo, dada una cantidad de recursos suficiente (es decir, infinita) , no para mostrar si una implementación específica de un modelo sí tiene esos recursos. Los modelos completos no Turing no podrían manejar un conjunto específico de cálculos, incluso con recursos suficientes , algo que revele una diferencia en la forma en que operan los dos modelos, incluso cuando tienen recursos limitados . Por supuesto, para probar esta propiedad, debe asumir que los modelos pueden usar una cantidad infinita de recursos, pero esta propiedad de un modelo es relevante incluso cuando los recursos son limitados.
La completitud de las redes neuronales recurrentes podría significar: las tablas de transición (finitas) de todas y cada una de las máquinas de Turing (con una cabeza de estado finito y una cinta infinita) pueden ser modeladas por una red neuronal recurrente finita (finitamente muchas neuronas con finitas estados, especialmente solo dos estados). Las tablas de transición definen tres funciones:
next-state (current-state, current-symbol)
símbolo siguiente (estado actual, símbolo actual)
dirección (actual-estado, actual-símbolo)
Así es como una red neuronal recurrente puede realizar esta tarea (solo un boceto muy crudo):
Las neuronas verdes leen el símbolo en la celda actual (en representación binaria), las neuronas grises (initalmente mudas) determinan el estado actual, las neuronas rojas escriben el nuevo símbolo en la celda actual, las neuronas amarillas determinan si ir a la izquierda o a la derecha . Las neuronas azules son las neuronas internas (inicialmente mudas).
La afirmación es que para todas y cada una de las máquinas de Turing existe una red neuronal recurrente.
Me pregunto si existe una forma sistemática de construir dicha red a partir de tablas de transición dadas.
La respuesta es muy simple. Si puedes emular una puerta NOR o NAND con ella, entonces es Turing Complete, suponiendo que el resto sea simplemente una cuestión de combinar cosas juntas.
Las redes neuronales alimentadas regularmente no están completas . Son, en efecto, equivalentes a una sola función matemática complicada que puede hacer muchos cálculos pero no tiene ninguna habilidad para realizar bucles u otras operaciones de flujo de control.
Sin embargo, si conecta una red neuronal de alguna manera para acceder a un entorno con estado, entonces puede convertirse en una máquina completa .
Como ejemplo más trivial, podría recrear una máquina de Turing de estilo clásico donde:
- la entrada a la red neuronal es el valor en la cinta y el estado anterior
- la salida de la red neuronal es el siguiente estado y la acción
A continuación, podría entrenar la red neuronal para emular las acciones de cualquier tabla / configuración de estado de la máquina turing (tal vez mediante el aprendizaje supervisado sobre las acciones de otra máquina turing).
Nota: la idea de ejecutar una red de feedforward repetidamente con alguna forma de realimentación del estado es esencialmente equivalente a una red neuronal recurrente . Entonces puede pensar en una red neuronal recurrente más la lógica que la ejecuta repetidamente como completada por Turing. Necesita la lógica adicional (más allá de la red misma) para garantizar la integridad de Turing, ya que es necesario manejar cosas como la terminación, la repetición y la IO.
Para abordar parcialmente su segunda pregunta:
Las redes neuronales tienen la propiedad de ser aproximaciones universales , es decir, pueden aproximar cualquier función a un grado arbitrario de precisión. Es la parte del "grado de precisión" lo que impide que la Red Neural necesite ser infinita.