La teoría de la inferencia inductiva de Solomonoff es una teoría matemática de la inducción introducida por Ray Solomonoff , basada en la teoría de la probabilidad y la informática teórica . [1] [2] [3] En esencia, la inducción de Solomonoff deriva la probabilidad posterior de cualquier teoría computable , dada una secuencia de datos observados. Esta probabilidad posterior se deriva de la regla de Bayes y de algún previo universal , es decir, un previo que asigna una probabilidad positiva a cualquier teoría computable.
Solomonoff demostró que esta inducción es incomputable , pero señaló que "esta incomputabilidad es de un tipo muy benigno" y que "de ninguna manera inhibe su uso para la predicción práctica". [2]
La inducción de Solomonoff formaliza naturalmente la navaja de Occam [4] [5] [6] [7] [8] al asignar mayores credibilidades previas a teorías que requieren una descripción algorítmica más corta.
La teoría se basa en fundamentos filosóficos y fue fundada por Ray Solomonoff alrededor de 1960. [9] Es una combinación matemáticamente formalizada 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, dando más 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 comprenderlo, recuerde que el bayesianismo deriva la probabilidad posterior de una teoría dados los datos aplicando la regla de Bayes, que produce
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 datos observables . La inducción de Solomonoff se reduce esencialmente a exigir que todas esas distribuciones de probabilidad sean computables .
Curiosamente, el conjunto de distribuciones de probabilidad computables es un subconjunto del conjunto de todos los programas, que es contable . 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 . Como resultado, la inducción de Solomonoff se puede definir invocando únicamente distribuciones de probabilidad discretas.
La inducción de Solomonoff permite entonces hacer predicciones probabilísticas de datos futuros , simplemente obedeciendo las leyes de la probabilidad. Es decir, tenemos . Esta cantidad puede interpretarse como las predicciones promedio de todas las teorías dadas datos pasados , ponderadas por sus credibilidades posteriores .
La prueba de la "navaja" 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 que 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, hay una longitud l tal que la probabilidad de que todos los programas sean más largos que l es como máximo . 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 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 de la cual se muestree x , el prior universal y el teorema de Bayes pueden usarse para predecir las partes aún no vistas de x de manera óptima.
La propiedad notable de la inducción de Solomonoff es su integridad. En esencia, el teorema de completitud garantiza que los errores acumulativos esperados cometidos por las predicciones basadas en la inducción de Solomonoff están limitados superiormente por la complejidad de Kolmogorov del proceso de generación de datos (estocástico). Los errores se pueden medir utilizando 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 de generación de datos (estocástico).
Desafortunadamente, Solomonoff también demostró que la inducción de Solomonoff es incomputable. De hecho, demostró que la computabilidad y la completitud son mutuamente excluyentes: cualquier teoría completa debe ser incomputable. La prueba de ello se deriva de un juego entre la inducción y el medio ambiente. Esencialmente, cualquier inducción computable puede ser engañada por un entorno computable, eligiendo el entorno computable que niegue la predicción de la inducción computable. Este hecho puede considerarse como un ejemplo del teorema del almuerzo gratuito .
Aunque la inferencia inductiva de Solomonoff no es computable , varios algoritmos derivados de AIXI se aproximan a ella para poder ejecutarla en una computadora moderna. Cuanta más potencia de cálculo se les dé, más cercanas estarán sus predicciones a las predicciones de la inferencia inductiva (su límite matemático es la inferencia inductiva de Solomonoff). [11] [12] [13]
Otra dirección de la 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, ¿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 manera consistente con los valores dados de f ). Un alumno M aprende una función f si casi todas sus hipótesis tienen el 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. [ cita necesaria ] 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 Schmidhuber de las complejidades generalizadas de Kolmogorov, [15] que son tipos de algoritmos superrecursivos .
{{cite book}}
: CS1 maint: location missing publisher (link)