La teoría de la inferencia inductiva de Solomonoff
La teoría de la inferencia inductiva de Solomonoff es Ray Solomonoff formalización matemática ‘s de la navaja de Occam. Explica las observaciones del mundo por el programa de computadora más pequeño que genera esas observaciones. Solomonoff demostró que esta explicación es la más probable, suponiendo que el mundo es generado por un programa informático desconocido.
Es decir, la distribución de probabilidad de todos los programas de computadora que generan las observaciones favorece la más corta.
La predicción se realiza utilizando un marco completamente bayesiano. El prior universal se calcula para todas las secuencias computables; esta es la distribución de probabilidad universal a priori; ninguna hipótesis computable tendrá una probabilidad cero. Esto significa que la regla de causalidad de Bayes se puede usar para predecir la continuación de cualquier secuencia computable particular.
Origen
Filosófico
La teoría se basa en fundamentos filosóficos y fue fundada por Ray Solomonoff alrededor de 1960. Es una combinación formalmente matemática de la navaja de afeitar de Occam y el Principio de explicaciones múltiples. Todas las teorías computables que describen perfectamente las observaciones previas se utilizan para calcular la probabilidad de la siguiente observación, con más peso en las teorías computables más cortas.
La inteligencia artificial universal de Marcus Hutter se basa en esto para calcular el valor esperado de una acción.
Matemática
La prueba de la «maquinilla de afeitar» se basa en las propiedades matemáticas conocidas de una distribución de probabilidad sobre un conjunto contable. Estas propiedades son relevantes porque el conjunto infinito de todos los programas es un conjunto numerable. La suma S de las probabilidades de todos los programas debe ser exactamente igual a uno (según la definición de probabilidad ), por lo tanto, las probabilidades deben disminuir aproximadamente a medida que enumeramos el conjunto infinito de todos los programas, de lo contrario S será estrictamente mayor que uno.
Para ser más precisos, para cada{\ displaystyle \ epsilon}\ epsilon > 0, hay una longitud l tal que la probabilidad de que todos los programas sean más largos que l es como máximo{\ displaystyle \ epsilon}\ epsilon. Sin embargo, esto no impide que los programas muy largos tengan una probabilidad muy alta.
Los ingredientes fundamentales de la teoría son los conceptos de probabilidad algorítmica y la complejidad de Kolmogorov. La probabilidad previa universal de cualquier prefijo p de una secuencia computable x es la suma de las probabilidades de todos los programas (para una computadora universal ) que calculan algo que comienza con p.
Dada alguna p y cualquier distribución de probabilidad computable pero desconocida a partir de la cual se muestrea x, el teorema universal de Bayes y anterior puede usarse para predecir las partes aún no vistas de x de manera óptima.
Aplicaciones modernas
Inteligencia artificial
Aunque la inferencia inductiva de Solomonoff no es computable, varios algoritmos derivados de AIXI la aproximan para hacerla funcionar en una computadora moderna. Cuanto más poder de cómputo se les da, más cercanas están sus predicciones a las predicciones de inferencia inductiva (su límite matemático es la inferencia inductiva de Solomonoff).
Otra dirección de inferencia inductiva se basa en el modelo de aprendizaje de E. Mark Gold en el límite de 1967 y ha desarrollado desde entonces más y más modelos de aprendizaje. El escenario general es el siguiente: Dada una clase S de funciones computables, ¿hay un alumno (es decir, funcional recursivo) que para cualquier entrada de la forma ( f (0), f (1),…, f ( n )) genera una hipótesis (un índice e con respecto a una numeración aceptable previamente acordada de todas las funciones computables;
La función indexada puede ser requerida de acuerdo con los valores dados de f ). Un alumno Maprende una función f si casi todas sus hipótesis son del mismo índice e, lo que genera la función f; M aprende S si M aprende cada f en S. Los resultados básicos son que todas las clases de funciones enumerables recursivamente se pueden aprender, mientras que la clase REC de todas las funciones computables no se puede aprender.
Se han considerado muchos modelos relacionados y también el aprendizaje de clases de conjuntos recursivamente enumerables a partir de datos positivos es un tema estudiado en el artículo pionero de Gold en 1967 en adelante. La teoría de Schmidhuber de las complejidades generalizadas de Kolmogorov desarrolla una extensión de gran alcance del enfoque de Gold,que son tipos de algoritmos súper recursivos.
Máquinas de Turing
La tercera dirección de inferencia inductiva basada en la matemática hace uso de la teoría de los autómatas y la computación. En este contexto, el proceso de inferencia inductiva lo realiza un autómata abstracto llamado máquina de Turing inductiva (Burgin, 2005). Las máquinas de Turing inductivas representan el siguiente paso en el desarrollo de la informática que proporciona mejores modelos para computadoras y redes de computadoras contemporáneas (Burgin, 2001) y forma una clase importante de algoritmos súper recursivos, ya que satisfacen todas las condiciones en la definición del algoritmo.
A saber, cada máquina de Turing inductiva es un tipo de método efectivo en el que una lista definida de instrucciones bien definidas para completar una tarea, cuando se le da un estado inicial, procederá a través de una serie bien definida de estados sucesivos, que finalmente terminarán en un final -estado.
La diferencia entre una máquina de Turing inductiva y una máquina de Turing es que para producir el resultado, una máquina de Turing tiene que detenerse, mientras que en algunos casos una máquina de Turing inductiva puede hacer esto sin detenerse. Stephen Kleene llamó a procedimientos que podrían ejecutarse para siempre sin detenerse por el procedimiento de cálculo de nombre o algoritmo(Kleene 1952:
137). Kleene también exigió que tal algoritmo eventualmente exhiba «algún objeto» (Kleene 1952: 137). Las máquinas de Turing inductivas satisfacen esta condición, ya que sus resultados se muestran después de un número finito de pasos, pero las máquinas de Turing inductivas no siempre indican en qué etapa se obtuvo el resultado.
Las máquinas de Turing inductivas simples son equivalentes a otros modelos de computación. Las máquinas Turing inductivas más avanzadas son mucho más potentes. Está comprobado (Burgin, 2005) que limitar las funciones recursivas parciales, los predicados de prueba y error, las máquinas de Turing generales y las máquinas de Turing inductivas simples son modelos equivalentes de computación.
Sin embargo, las máquinas de Turing inductivas simples y las máquinas de Turing generales proporcionan construcciones directas de autómatas informáticos, que se basan completamente en máquinas físicas. En contraste, los predicados de prueba y error, las funciones recursivas limitantes y las funciones recursivas parciales presentan sistemas sintácticos de símbolos con reglas formales para su manipulación.
Tenga en cuenta que solo las máquinas Turing inductivas simples tienen la misma estructura (pero diferente semántica funcional del modo de salida) que las máquinas Turing. Otros tipos de máquinas de Turing inductivas tienen una estructura esencialmente más avanzada debido a la memoria estructurada y las instrucciones más potentes.
Su utilización para la inferencia y el aprendizaje permite lograr una mayor eficiencia y refleja mejor el aprendizaje de las personas (Burgin y Klinger, 2004).
Algunos investigadores confunden los cálculos de las máquinas de Turing inductivas con los cálculos continuos o con los cálculos de tiempo infinito. Primero, algunos de los cálculos de las máquinas inductivas de Turing se detienen. Como en el caso de las máquinas Turing convencionales, algunos cálculos de detención dan el resultado, mientras que otros no.
En segundo lugar, algunos cálculos continuos de máquinas de Turing inductivas dan resultados, mientras que otros no dan. Las reglas de las máquinas de Turing inductivas determinan cuándo un cálculo (detenido o sin parar) da un resultado. A saber, una máquina de Turing inductiva produce salidas de vez en cuando y una vez que esta deja de cambiar, se considera el resultado del cálculo.
Es necesario saber que las descripciones de esta regla en algunos documentos son incorrectas. Por ejemplo, Davis (2006: 128) formula la regla cuando se obtiene el resultado sin detenerse ya que «una vez que se haya producido la salida correcta, cualquier salida posterior simplemente repetirá este resultado correcto».
Tercero, en contraste con el concepto erróneo generalizado, las máquinas de Turing inductivas dan resultados (cuando sucede) siempre después de un número finito de pasos (en tiempo finito) en contraste con los cálculos de tiempo infinito e infinito. Hay dos distinciones principales entre las máquinas de Turing convencionales y las máquinas de Turing inductivas simples.
La primera distinción es que incluso las máquinas Turing inductivas simples pueden hacer mucho más que las máquinas Turing convencionales. La segunda distinción es que una máquina de Turing convencional siempre informa (deteniéndose o llegando a un estado final) cuando se obtiene el resultado, mientras que una máquina de Turing inductiva simple en algunos casos informa acerca de alcanzar el resultado, mientras que en otros casos (donde la máquina de Turing convencional es impotente), no informa.
Las personas tienen la ilusión de que una computadora siempre informa (deteniéndose o por otros medios) cuando se obtiene el resultado. En contraste con esto, los propios usuarios tienen que decidir en muchos casos si el resultado calculado es lo que necesitan o si es necesario continuar con los cálculos.
De hecho, las aplicaciones de computadoras de escritorio cotidianas, como los procesadores de texto y las hojas de cálculo, pasan la mayor parte del tiempo esperando Los propios usuarios tienen que decidir en muchos casos si el resultado calculado es lo que necesitan o si es necesario continuar con los cálculos.
De hecho, las aplicaciones de computadoras de escritorio cotidianas, como los procesadores de texto y las hojas de cálculo, pasan la mayor parte del tiempo esperando Los propios usuarios tienen que decidir en muchos casos si el resultado calculado es lo que necesitan o si es necesario continuar con los cálculos.
De hecho, las aplicaciones de computadoras de escritorio cotidianas, como los procesadores de texto y las hojas de cálculo, pasan la mayor parte del tiempo esperandobucles de eventos, y no terminan hasta que los usuarios se lo indiquen.
Máquinas de Turing inductivas evolutivas
El enfoque evolutivo de la inferencia inductiva se logra mediante otra clase de autómatas llamada máquinas de Turing inductivas evolutivas (Burgin y Eberbach, 2009; 2012). Una máquina de Turing inductiva evolutiva es una secuencia (posiblemente infinita) E = { A; t = 1, 2, 3,…} de máquinas de Turing inductivas A cada una trabajando en las generaciones X que están codificadas como palabras en el alfabeto de las máquinas A.
El objetivo es construir una «población» Z que satisfaga la condición de inferencia. El autómata A llamado componente, o autómata de nivel, de E representa (codifica) un algoritmo evolutivo de un nivel que funciona con las generaciones de entrada X de la población aplicando los operadores de variación v y los operadores de selección s.
La primera generación X se proporciona como entrada a E y es procesada por el autómata A, que genera / produce la primera generación X como salida de transferencia, que va al autómata A. Para todos los t = 1, 2, 3,…, el autómata A recibe la generación X como su entrada desde A y luego aplica el operador de variación vy el operador de selección s, produciendo la generación X y enviándola a A para continuar la evolución.
Notas
JJ McCall. Inducción: de Kolmogorov y Solomonoff a De Finetti y de regreso a Kolmogorov – Metroeconomica, 2004 – Biblioteca en línea Wiley.
D Cigüeña. Fundamentos de la navaja y parsimonia de Occam en el aprendizaje de ricoh.com – Taller NIPS 2001, 2001
A.N. Soklakov La navaja de afeitar de Occam como base formal para una teoría físicade arxiv.org- Fundamentos de las letras de la física, 2002 – Springer
José Hernández-Orallo (1999). «Más allá de la prueba de Turing» (PDF). Revista de lógica, lenguaje e información. 9.
M Hutter. Sobre la existencia y convergencia de antecedentes universales computablesarxiv.org- Algorithmic Learning Theory, 2003 – Springer
Ming Li y Paul Vitanyi,Introducción a la complejidad de Kolmogorov y sus aplicaciones. Springer-Verlag, Nueva York, 2008p 339 ss.
Fuentes
- Fuente: www.w3.org
- Fuente: arxiv.org
- Fuente: users.dsic.upv.es
Autor
