Longitud mínima del mensaje

Reformulación formal de la teoría de la información de la navaja de Occam

La longitud mínima del mensaje (MML) es un método bayesiano de teoría de la información para la comparación y selección de modelos estadísticos. ^[1] Proporciona una reformulación formal de la teoría de la información de la Navaja de Occam : incluso cuando los modelos son iguales en su medida de precisión de ajuste a los datos observados, el que genera la explicación más concisa de los datos tiene más probabilidades de ser correcto (donde la explicación consiste en la declaración del modelo, seguida de la codificación sin pérdidas de los datos utilizando el modelo indicado). MML fue inventado por Chris Wallace y apareció por primera vez en el artículo fundamental "Una medida de información para la clasificación". ^[2] MML no pretende ser sólo una construcción teórica, sino también una técnica que puede implementarse en la práctica. ^[3] Se diferencia del concepto relacionado de complejidad de Kolmogorov en que no requiere el uso de un lenguaje completo de Turing para modelar datos. ^[4]

Definición

Una teoría matemática de la comunicación de Shannon (1948) establece que en un código óptimo, la longitud del mensaje (en binario) de un evento , donde tiene probabilidad , está dada por . ${\displaystyle E}$ ${\displaystyle \operatorname {length} (E)}$ ${\displaystyle E}$ ${\displaystyle P(E)}$ ${\displaystyle \operatorname {length} (E)=-\log _{2}(P(E))}$

El teorema de Bayes establece que la probabilidad de una hipótesis (variable) dada evidencia fija es proporcional a , que, según la definición de probabilidad condicional , es igual a . Queremos el modelo (hipótesis) con la mayor probabilidad posterior . Supongamos que codificamos un mensaje que representa (describe) tanto el modelo como los datos de forma conjunta. Desde , el modelo más probable tendrá el mensaje más corto. El mensaje se divide en dos partes: . La primera parte codifica el modelo en sí. La segunda parte contiene información (por ejemplo, valores de parámetros o condiciones iniciales, etc.) que, cuando la procesa el modelo, genera los datos observados. ${\displaystyle H}$ ${\displaystyle E}$ ${\displaystyle P(E|H)P(H)}$ ${\displaystyle P(H\land E)}$ ${\displaystyle \operatorname {length} (H\land E)=-\log _{2}(P(H\land E))}$ ${\displaystyle -\log _{2}(P(H\land E))=-\log _{2}(P(H))+-\log _{2}(P(E|H))}$

MML cambia de forma natural y precisa la complejidad del modelo por la bondad de ajuste. Un modelo más complicado tarda más en formularse (primera parte más larga) pero probablemente se ajuste mejor a los datos (segunda parte más corta). Por lo tanto, una métrica MML no elegirá un modelo complicado a menos que ese modelo se pague por sí solo.

Parámetros de valores continuos

Una razón por la cual un modelo podría ser más largo sería simplemente porque sus diversos parámetros se expresan con mayor precisión, lo que requiere la transmisión de más dígitos. Gran parte del poder de MML se deriva de su manejo de la precisión con la que se establecen los parámetros en un modelo y de una variedad de aproximaciones que lo hacen factible en la práctica. Esto hace posible comparar de manera útil, por ejemplo, un modelo con muchos parámetros expresados ​​de manera imprecisa con un modelo con menos parámetros expresados ​​con mayor precisión.

Características clave de MML

• MML se puede utilizar para comparar modelos de diferente estructura. Por ejemplo, su primera aplicación fue encontrar modelos mixtos con el número óptimo de clases. Agregar clases adicionales a un modelo mixto siempre permitirá que los datos se ajusten con mayor precisión, pero según MML esto debe sopesarse con los bits adicionales necesarios para codificar los parámetros que definen esas clases.
• MML es un método de comparación de modelos bayesianos . Le da a cada modelo una puntuación.
• MML es invariante en escala y estadísticamente invariante. A diferencia de muchos métodos de selección bayesianos, a MML no le importa si cambia de medir longitud a volumen o de coordenadas cartesianas a coordenadas polares.
• MML es estadísticamente consistente. Para problemas como el de Neyman-Scott (1948) o el análisis factorial donde la cantidad de datos por parámetro está acotada arriba, MML puede estimar todos los parámetros con consistencia estadística .
• MML representa la precisión de la medición. Utiliza la información de Fisher (en la aproximación de Wallace-Freeman 1987, u otros hipervolúmenes en otras aproximaciones) para discretizar de manera óptima parámetros continuos. Por tanto, la posterior es siempre una probabilidad, no una densidad de probabilidad.
• MML se ha utilizado desde 1968. Se han desarrollado esquemas de codificación MML para varias distribuciones y muchos tipos de aprendizaje automático, incluida la clasificación no supervisada, árboles y gráficos de decisión, secuencias de ADN, redes bayesianas , redes neuronales (hasta ahora solo de una capa), compresión de imágenes, segmentación de imágenes y funciones, etc.

Ver también

• probabilidad algorítmica
• Teoría de la información algorítmica
• inducción gramatical
• inferencia inductiva
• probabilidad inductiva
• Complejidad de Kolmogorov – complejidad absoluta (dentro de una constante, dependiendo de la elección particular de la Máquina Universal de Turing ); MML suele ser una aproximación computable (ver ^[4] )
• Longitud mínima de la descripción : una alternativa con una motivación posiblemente diferente (no bayesiana), desarrollada 10 años después de MML.
• La navaja de Occam

Referencias

1. Wallace, CS (Christopher S.), -2004. (2005). Inferencia estadística e inductiva por longitud mínima de mensaje . Nueva York: Springer. ISBN 9780387237954. OCLC  62889003.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ) Mantenimiento CS1: nombres numéricos: lista de autores ( enlace )
2. Wallace, CS; Boulton, DM (1 de agosto de 1968). "Una medida de información para la clasificación". La revista informática . 11 (2): 185-194. doi : 10.1093/comjnl/11.2.185 . ISSN  0010-4620.
3. Allison, Lloyd. (2019). Codificando la navaja de Ockham . Saltador. ISBN 978-3030094881. OCLC  1083131091.
4. Wallace, CS; Dowe, DL (1 de enero de 1999). "Longitud mínima del mensaje y complejidad de Kolmogorov". La revista informática . 42 (4): 270–283. doi : 10.1093/comjnl/42.4.270. ISSN  0010-4620.

enlaces externos

Publicación original:

• Wallace; Boulton (agosto de 1968). "Una medida de información para la clasificación". Diario de informática . 11 (2): 185-194. doi : 10.1093/comjnl/11.2.185 .

Libros:

• Wallace, CS (mayo de 2005). Inferencia estadística e inductiva por longitud mínima de mensaje. Ciencias de la Información y Estadística. Springer-Verlag. doi :10.1007/0-387-27656-4. ISBN 978-0-387-23795-4.
• Allison, L. (2018). Codificando la navaja de Ockham . Saltador. doi :10.1007/978-3-319-76433-7. ISBN 978-3319764320. S2CID  19136282., sobre la implementación de MML y el código fuente.

Enlaces relacionados:

• Enlaces a todas las publicaciones conocidas de Chris Wallace.
• Una base de datos con capacidad de búsqueda de las publicaciones de Chris Wallace.
• Wallace, CS; Dowe, DL (1999). "Longitud mínima del mensaje y complejidad de Kolmogorov". Diario de informática . 42 (4): 270–283. CiteSeerX  10.1.1.17.321 . doi : 10.1093/comjnl/42.4.270.
• "Número especial sobre la complejidad de Kolmogorov". Diario de informática . 42 (4). 1999.^{[ enlace muerto ]}
• Dowe, DL; Wallace, CS (1997). Resolución del problema de Neyman-Scott mediante la longitud mínima del mensaje. 28º Simposio sobre la interfaz, Sydney, Australia. Ciencias de la Computación y Estadística . vol. 28. págs. 614–618.
• Historia de MML, última charla de CSW.
• Needham, S.; Dowe, D. (2001). La longitud del mensaje como navaja de Ockham eficaz en la inducción del árbol de decisiones (PDF) . Proc. 8º Taller Internacional sobre IA y Estadística. págs. 253–260.(Muestra cómo funciona bien la navaja de Occam cuando se interpreta como MML).
• Allison, L. (enero de 2005). "Modelos de aprendizaje automático y minería de datos en programación funcional". Revista de programación funcional . 15 (1): 15–32. doi : 10.1017/S0956796804005301 . S2CID  5218889.(código MML, FP y Haskell).
• Comley, JW; Dowe, DL (abril de 2005). "Capítulo 11: Longitud mínima del mensaje, MDL y redes bayesianas generalizadas con lenguajes asimétricos". En Grunwald, P.; Pitt, MA; Myung, IJ (eds.). Avances en la longitud mínima de la descripción: teoría y aplicaciones. Prensa del MIT. págs. 265–294. ISBN 978-0-262-07262-5.
• Comley, Joshua W.; Dowe, DL (5 a 8 de junio de 2003). Redes bayesianas generales y lenguajes asimétricos. Proc. Segunda Conferencia Internacional de Hawái sobre Estadística y Campos Afines., .pdf. Comley y Dowe (2003, 2005) son los dos primeros artículos sobre redes bayesianas MML que utilizan parámetros de valores tanto discretos como continuos.

• Dowe, David L. (2010). "MML, modelos gráficos de redes bayesianas híbridas, consistencia estadística, invariancia y unicidad" (PDF) . Manual de Filosofía de la Ciencia (Volumen 7: Manual de Filosofía de la Estadística) . Elsevier. págs. 901–982. ISBN 978-0-444-51862-0.
• Longitud mínima del mensaje (MML), introducción a MML de LA, (MML alt.).
• Longitud mínima del mensaje (MML), investigadores y enlaces.
• "Otro sitio web de investigación de MML". Archivado desde el original el 12 de abril de 2017.
• "Página snob para modelado de mezclas MML ".
• MITECS: Chris Wallace escribió una entrada sobre MML para MITECS. (Requiere cuenta)
• mikko.ps: breves diapositivas introductorias de Mikko Koivisto en Helsinki
• Método de selección de modelo del criterio de información de Akaike ( AIC ) y comparación con MML: Dowe, DL; Gardner, S.; Oppy, G. (diciembre de 2007). "¡Bayes no es un fracaso! Por qué la simplicidad no es un problema para los bayesianos". Hno. J. Filos. Ciencia . 58 (4): 709–754. doi :10.1093/bjps/axm033.