La teoría de la inferencia inductiva de Solomonoff

Una teoría matemática

La teoría de inferencia inductiva de Solomonoff demuestra que, bajo sus supuestos de sentido común (axiomas), el mejor modelo científico posible es el algoritmo más corto que genera los datos empíricos bajo consideración. Además de la elección de los datos, otros supuestos son que, para evitar la falacia post-hoc, el lenguaje de programación debe elegirse antes que los datos ^[1] y que el entorno que se observa es generado por un algoritmo desconocido. Esto también se llama teoría de inducción . Debido a su base en el carácter dinámico ( modelo de espacio de estados ) de la teoría de la información algorítmica , abarca criterios de información tanto estadísticos como dinámicos para la selección de modelos . Fue introducida por Ray Solomonoff , basada en la teoría de la probabilidad y la informática teórica . ^{[2] [3] [4]} 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 prior universal , es decir, un prior que asigna una probabilidad positiva a cualquier teoría computable.

Solomonoff demostró que esta inducción es incomputable (o, más precisamente, semicomputable a un nivel inferior), 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" (ya que se puede aproximar desde abajo con mayor precisión con más recursos computacionales). ^[3] Solo es "incomputable" en el sentido benigno de que ningún consenso científico es capaz de demostrar que la mejor teoría científica actual es la mejor de todas las teorías posibles. Sin embargo, la teoría de Solomonoff proporciona un criterio objetivo para decidir entre las teorías científicas actuales que explican un conjunto dado de observaciones.

La inducción de Solomonoff formaliza naturalmente la navaja de Occam ^{[5] [6] [7] [8] [9]} al asignar mayores creencias previas a las 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. ^[10] Es una combinación formalizada matemáticamente de la navaja de Occam ^{[5] [6] [7] [8] [9]} y el Principio de Explicaciones Múltiples . ^[11] Todas las teorías computables que describen perfectamente las observaciones anteriores 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.

Principio

Se ha argumentado que la inducción de Solomonoff es la formalización computacional del bayesianismo puro . ^[4] Para entenderlo, recuerde que el bayesianismo deriva la probabilidad posterior de una teoría dada los datos mediante la aplicación de 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 puede definirse 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 probabilidad. Es decir, tenemos . Esta cantidad puede interpretarse como las predicciones promedio de todas las teorías dadas las estadísticas pasadas , 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]}$

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, existe una longitud l tal que la probabilidad de todos los programas 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 . Dado un valor p y cualquier distribución de probabilidad computable pero desconocida de la que se toma una muestra de x , la probabilidad previa universal y el teorema de Bayes se pueden usar para predecir las partes aún no vistas de x de manera óptima.

Garantías matemáticas

La completitud de Solomonoff

La propiedad notable 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 limitados en su parte superior por la complejidad de Kolmogorov del proceso de generación de datos (estocásticos). 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ásticos).

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 esto se deriva de un juego entre la inducción y el entorno. Esencialmente, cualquier inducción computable puede ser engañada por un entorno computable, al elegir el entorno computable que niega la predicción de la inducción computable. Este hecho puede considerarse como un ejemplo del teorema de que no hay almuerzo gratis .

Aplicaciones modernas

Inteligencia artificial

Aunque la inferencia inductiva de Solomonoff no es computable , varios algoritmos derivados de AIXI la aproximan para que pueda ejecutarse en una computadora moderna. Cuanto más poder computacional se les da, más cercanas son sus predicciones a las predicciones de la inferencia inductiva (su límite matemático es la inferencia inductiva de Solomonoff). ^{[12] [13] [14]}

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. ^[15] El escenario general es el siguiente: Dada una clase S de funciones computables, ¿hay un aprendiz (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 requerirse que sea 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. ^{[ cita requerida ]} 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 generalizadas de Kolmogorov de Schmidhuber, ^[16] que son tipos de algoritmos superrecursivos .

Véase también

• Teoría de la información algorítmica
• Inferencia bayesiana
• Inferencia inductiva
• Probabilidad inductiva
• Los métodos de Mill
• Longitud mínima de descripción
• Longitud mínima del mensaje
• Para un punto de vista filosófico, véase: Problema de inducción y Nuevo enigma de la inducción.

Referencias

1. Rathmanner, Samuel (3 de junio de 2011). "Un tratado filosófico de inducción universal". Entropía . 13 (6): 1076–1136. arXiv : 1105.5721 . doi : 10.3390/e13061076 .
2. Zenil, Hector (11 de febrero de 2011). Aleatoriedad a través de la computación: algunas respuestas, más preguntas. World Scientific. ISBN 978-981-4462-63-1.
3. 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, consultado el 21 de julio de 2020
4. Hoang, Lê Nguyên (2020). La ecuación del conocimiento: de la regla de Bayes a una filosofía unificada de la ciencia (Primera edición). Boca Raton, FL. ISBN 978-0-367-85530-7.OCLC 1162366056  .{{cite book}}: CS1 maint: location missing publisher (link)
5. JJ McCall. Inducción: de Kolmogorov y Solomonoff a De Finetti y de regreso a Kolmogorov – Metroeconomica, 2004 – Wiley Online Library.
6. D Stork. Fundamentos de la navaja de Occam y la parsimonia en el aprendizaje de ricoh.com – Taller NIPS 2001, 2001
7. AN Soklakov. La navaja de Occam como base formal para una teoría física de arxiv.org – Fundamentos de la Física Letters, 2002 – Springer
8. Jose Hernandez-Orallo (1999). "Más allá del test de Turing" (PDF) . Revista de lógica, lenguaje e información . 9 .
9. M Hutter. Sobre la existencia y convergencia de valores universales previos computables arxiv.org – Algorithmic Learning Theory, 2003 – Springer
10. Samuel Rathmanner y Marcus Hutter . Un tratado filosófico de inducción universal. Entropy, 13(6):1076–1136, 2011
11. Ming Li y Paul Vitanyi, Introducción a la complejidad de Kolmogorov y sus aplicaciones. Springer-Verlag, NY, 2008, pág. 339 y siguientes.
12. J. Veness, KS Ng, M. Hutter, W. Uther, D. Silver. "Una aproximación AIXI de Monte Carlo" – Preimpresión de Arxiv, 2009 arxiv.org
13. J. Veness, KS Ng, M. Hutter, D. Silver. "Aprendizaje de refuerzo mediante aproximación AIXI", preimpresión de Arxiv, 2010 – aaai.org
14. S. Pankov. Una aproximación computacional al modelo AIXI de agiri.org – Inteligencia artificial general, 2008: actas de …, 2008 – books.google.com
15. Gold, E. Mark (1967). "Identificación del lenguaje en el límite" (PDF) . Información y Control . 10 (5): 447–474. doi : 10.1016/S0019-9958(67)91165-5 .
16. J. Schmidhuber (2002). "Jerarquías de complejidades de Kolmogorov generalizadas y medidas universales no numerables computables en el límite" (PDF) . Revista Internacional de Fundamentos de la Ciencia de la Computación . 13 (4): 587–612. doi :10.1142/S0129054102001291.

Fuentes

• Angluin, Dana; Smith, Carl H. (septiembre de 1983). "Inferencia inductiva: teoría y métodos". Computing Surveys . 15 (3): 237–269. doi :10.1145/356914.356918. S2CID  3209224.
• Burgin, M. (2005), Algoritmos superrecursivos , Monografías en informática, Springer. ISBN 0-387-95569-0 
• Burgin, M., "Cómo sabemos lo que la tecnología puede hacer", Comunicaciones de la ACM , v. 44, n.º 11, 2001, págs. 82–88.
• Burgin, M.; Eberbach, E., "Universalidad para 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 inmunes 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.º 9, 2012, págs. 1023–1029.
• Burgin, M.; Klinger, A. Experiencia, generaciones y límites en el aprendizaje automático, Theoretical Computer Science , v. 317, n.º 1/3, 2004, págs. 71–91
• Davis, Martin (2006) "La tesis de Church-Turing: consenso y oposición". Actas, Computabilidad en Europa 2006. Apuntes de clase en Ciencias de la Computación, 3988 pp. 125–132.
• Gasarch, W. ; Smith, CH (1997) "Un estudio de la inferencia inductiva con énfasis en las consultas". Teoría de la complejidad, la lógica y la recursión , Lecture Notes in Pure and Appl. Math., 187, Dekker, Nueva York, págs. 225–260.
• Hay, Nick. "Semimedidas universales: una introducción", Serie de informes de investigación del CDMTCS, Universidad de Auckland, febrero de 2007.
• Jain, 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 edición), Ámsterdam: Holanda Septentrional.
• Li Ming; Vitanyi, Paul, Introducción a la complejidad de Kolmogorov y sus aplicaciones , 2.a edición, Springer Verlag, 1997.
• Osherson, Daniel; Stob, Michael; Weinstein, Scott, Sistemas que aprenden. Una introducción a la teoría del aprendizaje para científicos cognitivos y computacionales , MIT Press , 1986.
• Solomonoff, Ray J. (1999). "Dos tipos de inducción probabilística" (PDF) . The Computer Journal . 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