La teoría de la inferencia inductiva de Solomonoff

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.

Origen

Filosófico

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.

Principio

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 ${\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 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 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 . ${\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]}$

Matemático

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. ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

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.

Garantías matemáticas

La plenitud de Solomonoff

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).

La incomputabilidad de Solomonoff

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 .

Aplicaciones modernas

Inteligencia artificial

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 .

Ver también

• Teoría de la información algorítmica
• Inferencia bayesiana
• Identificación del idioma en el límite
• inferencia inductiva
• probabilidad inductiva
• Los métodos de Mill.
• Longitud mínima de la descripción
• Longitud mínima del mensaje
• Para un punto de vista filosófico, consulte: Problema de la inducción y Nuevo enigma de la inducción.

Referencias

1. Zenil, Héctor (11 de febrero de 2011). Aleatoriedad a través de la computación: algunas respuestas, más preguntas. Científico mundial. ISBN 978-981-4462-63-1.
2. Solomonoff, Ray J. (2009), Emmert-Streib, Frank; Dehmer, Matthias (eds.), "Probabilidad algorítmica: teoría y aplicaciones", Teoría de la información y aprendizaje estadístico , Boston, MA: Springer US, págs. 1–23, doi :10.1007/978-0-387-84816-7_1, ISBN 978-0-387-84816-7, recuperado 2020-07-21
3. Hoang, Lê Nguyên (2020). La ecuación del conocimiento: de la regla de Bayes a una filosofía de la ciencia unificada (Primera ed.). Boca Ratón, Florida. ISBN 978-0-367-85530-7. OCLC  1162366056.{{cite book}}: CS1 maint: location missing publisher (link)
4. JJ McCall. Inducción: de Kolmogorov y Solomonoff a De Finetti y de regreso a Kolmogorov - Metroeconomica, 2004 - Biblioteca en línea Wiley.
5. D Cigüeña. Fundamentos de la navaja de Occam y parsimonia en el aprendizaje de ricoh.com – Taller NIPS 2001, 2001
6. AN Soklakov. La navaja de Occam como base formal para una teoría física de arxiv.org - Foundations of Physics Letters, 2002 - Springer
7. José Hernández-Orallo (1999). "Más allá de la prueba de Turing" (PDF) . Revista de Lógica, Lenguaje e Información . 9 .
8. M Hutter. Sobre la existencia y convergencia de antecedentes universales computables arxiv.org – Teoría del aprendizaje algorítmico, 2003 – Springer
9. Samuel Rathmanner y Marcus Hutter . Un tratado filosófico de inducción universal. Entropía, 13(6):1076–1136, 2011
10. Ming Li y Paul Vitanyi, Introducción a la complejidad de Kolmogorov y sus aplicaciones. Springer-Verlag, Nueva York, 2008p 339 y sigs.
11. J. Veness, KS Ng, M. Hutter, W. Uther, D. Silver. "Una aproximación de Monte Carlo AIXI" - preimpresión de Arxiv, 2009 arxiv.org
12. J. Veness, KS Ng, M. Hutter, D. Silver. "Aprendizaje por refuerzo mediante aproximación AIXI" Preimpresión de Arxiv, 2010 - aaai.org
13. S. Pankov. Una aproximación computacional al modelo AIXI de agiri.org – Inteligencia general artificial, 2008: actas de…, 2008 – books.google.com
14. Oro, E. Mark (1967). «Identificación del idioma en el límite» (PDF) . Información y Control . 10 (5): 447–474. doi : 10.1016/S0019-9958(67)91165-5 .
15. J. Schmidhuber (2002). "Jerarquías de complejidades generalizadas de Kolmogorov e innumerables medidas universales computables en el límite" (PDF) . Revista Internacional de Fundamentos de la Informática . 13 (4): 587–612. doi :10.1142/S0129054102001291.

Fuentes

• Angluin, Dana; Smith, Carl H. (septiembre de 1983). "Inferencia inductiva: teoría y métodos". Encuestas Informáticas . 15 (3): 237–269. doi :10.1145/356914.356918. S2CID  3209224.
• Burgin, M. (2005), Algoritmos superrecursivos , Monografías de informática, Springer. ISBN 0-387-95569-0 
• Burgin, M., "Cómo sabemos qué puede hacer la tecnología", Communications of the ACM , v. 44, núm. 11, 2001, págs.
• Burgin, M.; Eberbach, E., "Universalidad de las máquinas de Turing, máquinas de Turing inductivas y algoritmos evolutivos", Fundamenta Informaticae , v. 91, n.º 1, 2009, 53–77.
• Burgin, M.; Eberbach, E., "Sobre los fundamentos de la computación evolutiva: un enfoque de autómatas evolutivos", en Manual de investigación sobre sistemas inmunológicos artificiales y computación natural: aplicación de tecnologías adaptativas complejas (Hongwei Mo, Ed.), IGI Global, Hershey, Pensilvania, 2009 , 342–360.
• Burgin, M.; Eberbach, E., "Autómatas evolutivos: expresividad y convergencia de la computación evolutiva", Computer Journal , v. 55, núm. 9, 2012, págs.
• Burgin, M.; Klinger, A. Experiencia, generaciones y límites en el aprendizaje automático, informática teórica , v. 317, núm. 1/3, 2004, págs. 71–91
• Davis, Martin (2006) "La tesis de la Iglesia-Turing: consenso y oposición]". Actas, Computabilidad en Europa 2006. Apuntes de conferencias sobre informática, 3988 págs.
• Gasarch, W .; Smith, CH (1997) "Un estudio de la inferencia inductiva con énfasis en las consultas". Complejidad, lógica y teoría de la recursividad , Lecture Notes en Pure y Appl. Math., 187, Dekker, Nueva York, págs. 225–260.
• Hola, Nick. "Semimedidas universales: una introducción", Serie de informes de investigación CDMTCS, Universidad de Auckland, febrero de 2007.
• Jainista, Sanjay; Osherson, Daniel; Royer, James; Sharma, Arun, Sistemas que aprenden: una introducción a la teoría del aprendizaje (segunda edición), MIT Press , 1999.
• Kleene, Stephen C. (1952), Introducción a las metamatemáticas (Primera ed.), Ámsterdam: Holanda Septentrional.
• Li Ming; Vitanyi, Paul, Introducción a la complejidad de Kolmogorov y sus aplicaciones , segunda edición, Springer Verlag, 1997.
• Osherson, Daniel; Stob, Michael; Weinstein, Scott, Sistemas que aprenden, Introducción a la teoría del aprendizaje para científicos cognitivos e informáticos , MIT Press , 1986.
• Solomonoff, Ray J. (1999). "Dos tipos de inducción probabilística" (PDF) . La revista informática . 42 (4): 256. CiteSeerX  10.1.1.68.8941 . doi : 10.1093/comjnl/42.4.256.
• Solomonoff, Ray (marzo de 1964). "Una teoría formal de la inferencia inductiva, parte I" (PDF) . Información y Control . 7 (1): 1–22. doi : 10.1016/S0019-9958(64)90223-2 .
• Solomonoff, Ray (junio de 1964). "Una teoría formal de la inferencia inductiva, parte II" (PDF) . Información y Control . 7 (2): 224–254. doi : 10.1016/S0019-9958(64)90131-7 .

enlaces externos

• Probabilidad algorítmica – Scholarpedia