La teoría de la inferencia inductiva de Solomonoff

La teoría se basa en fundamentos filosóficos y fue fundada por Ray Solomonoff alrededor de 1960. ^{[ 9 ]} Es una combinación formalizada matemáticamente de la navaja de Occam ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]} y el Principio de Explicaciones Múltiples . ^{[ 10 ]} Todas las teorías computables que describen perfectamente observaciones anteriores se utilizan para calcular la probabilidad de la siguiente observación, otorgando mayor peso a 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.

Se ha argumentado que la inducción de Solomonoff es la formalización computacional del bayesianismo puro . ^{[ 3 ]} Para entenderlo, recordemos que el bayesianismo deriva la probabilidad posterior de una teoría dados los datos aplicando la regla de Bayes, que produce${\displaystyle \mathbb {P} [T|D]}$${\displaystyle T}$${\displaystyle D}$

${\displaystyle \mathbb {P} [T|D]={\frac {\mathbb {P} [D|T]\mathbb {P} [T]}{\mathbb {P} [D|T]\mathbb {P} [T]+\sum _{A\neq T}\mathbb {P} [D|A]\mathbb {P} [A]}}}$

donde las teorías son alternativas a la teoría . Para que esta ecuación tenga sentido, las cantidades y deben estar bien definidas para todas las teorías y . En otras palabras, cualquier teoría debe definir una distribución de probabilidad sobre los datos observables . La inducción de Solomonoff se reduce esencialmente a exigir que todas esas distribuciones de probabilidad sean computables .${\displaystyle A}$${\displaystyle T}$${\displaystyle \mathbb {P} [D|T]}$${\displaystyle \mathbb {P} [D|A]}$${\displaystyle T}$${\displaystyle A}$${\displaystyle D}$

Curiosamente, el conjunto de distribuciones de probabilidad computables es un subconjunto del conjunto de todos los programas, que es numerable . De manera similar, los conjuntos de datos observables considerados por Solomonoff eran finitos. Sin pérdida de generalidad , podemos considerar que cualquier dato observable es una cadena de bits finita . En consecuencia, la inducción de Solomonoff puede definirse simplemente recurriendo a distribuciones de probabilidad discretas.

La inducción de Solomonoff permite entonces hacer predicciones probabilísticas de datos futuros , simplemente obedeciendo las leyes de probabilidad. Es decir, tenemos . Esta cantidad puede interpretarse como las predicciones promedio de todas las teorías dados los datos pasados , ponderadas por sus creencias posteriores .${\displaystyle F}$${\displaystyle \mathbb {P} [F|D]=\mathbb {E} _{T}[\mathbb {P} [F|T,D]]=\sum _{T}\mathbb {P} [F|T,D]\mathbb {P} [T|D]}$${\displaystyle \mathbb {P} [F|T,D]}$${\displaystyle T}$${\displaystyle D}$${\displaystyle \mathbb {P} [T|D]}$

La demostración de la "navaja" se basa en las propiedades matemáticas conocidas de una distribución de probabilidad sobre un conjunto numerable . 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 > 0, existe alguna longitud l tal que la probabilidad de todos los programas más largos que l es como máximo . Sin embargo, esto no excluye que los programas muy largos tengan una probabilidad muy alta.${\displaystyle \epsilon }$${\displaystyle \epsilon }$

Los ingredientes fundamentales de la teoría son los conceptos de probabilidad algorítmica y complejidad de Kolmogorov . La probabilidad a priori 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 computan algo que comienza con p . Dado un valor p y cualquier distribución de probabilidad computable pero desconocida de la cual se extrae x , la probabilidad a priori universal y el teorema de Bayes pueden usarse para predecir de manera óptima las partes aún no vistas de x .

La propiedad más destacada de la inducción de Solomonoff es su completitud. En esencia, el teorema de completitud garantiza que los errores acumulativos esperados de las predicciones basadas en la inducción de Solomonoff están acotados superiormente por la complejidad de Kolmogorov del proceso generador de datos (estocástico). Estos errores pueden medirse mediante la divergencia de Kullback-Leibler o el cuadrado de la diferencia entre la predicción de la inducción y la probabilidad asignada por el proceso generador de datos (estocástico).

Desafortunadamente, Solomonoff también demostró que su inducción es incomputable. De hecho, demostró que la computabilidad y la completitud son mutuamente excluyentes: cualquier teoría completa debe ser incomputable. La prueba de esto se deriva de un juego entre la inducción y el entorno. En esencia, cualquier inducción computable puede ser engañada por un entorno computable, eligiendo aquel que niega la predicción de la inducción. Este hecho puede considerarse un ejemplo del teorema de la imposibilidad de obtener algo gratis .

Aunque la inferencia inductiva de Solomonoff no es computable , varios algoritmos derivados de AIXI la aproximan para poder ejecutarla en un ordenador moderno. Cuanto mayor sea la potencia de cálculo que se les asigne, más se aproximarán sus predicciones a las de la inferencia inductiva (su límite matemático es la inferencia inductiva de Solomonoff). ^{[ 11 ] [ 12 ] [ 13 ]}

Otra dirección de inferencia inductiva se basa en el modelo de aprendizaje en el límite de E. Mark Gold de 1967 y desde entonces ha desarrollado cada vez más modelos de aprendizaje. ^{[ 14 ]} El escenario general es el siguiente: Dada una clase S de funciones computables, ¿existe un aprendiz (es decir, un funcional recursivo) que para cualquier entrada de la forma ( f (0), f (1),..., f ( n )) produzca 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 requerirse consistente con los valores dados de f )? Un aprendiz M aprende una función f si casi todas sus hipótesis son el mismo índice e , 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 recursivamente enumerables son aprendibles mientras que la clase REC de todas las funciones computables no es aprendible. 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 desde el artículo pionero de Gold en 1967 en adelante. Una extensión de gran alcance del enfoque de Gold es desarrollada por la teoría de complejidades de Kolmogorov generalizadas de Schmidhuber, ^{[ 15 ]} que son tipos de algoritmos superrecursivos .