Longitud mínima del mensaje

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

La longitud mínima del mensaje ( MML ) es un método de teoría de la información bayesiano para la comparación y selección de modelos estadísticos. ^[1] Proporciona una reformulación de la teoría de la información formal 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érdida de los datos utilizando el modelo establecido). MML fue inventado por Chris Wallace , apareciendo por primera vez en el artículo seminal "Una medida de información para la clasificación". ^[2] MML no está pensado solo como una construcción teórica, sino como 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 Turing-completo para modelar datos. ^[4]

Definición

En Una teoría matemática de la comunicación (1948) de Shannon se afirma que en un código óptimo, la longitud del mensaje (en binario) de un evento , , donde tiene probabilidad , viene 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 una evidencia fija es proporcional a , que, por 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 conjuntamente. Como , 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 es procesada por 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 intercambia de forma natural y precisa la complejidad del modelo por la bondad del ajuste. Un modelo más complicado lleva más tiempo en enunciar (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 amortice por sí solo.

Parámetros de valor continuo

Una razón por la que 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 de la potencia de MML se deriva de su manejo de la precisión con la que se deben expresar los parámetros en un modelo y de una variedad de aproximaciones que hacen que esto sea factible en la práctica. Esto permite 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 principales de MML

• El MML se puede utilizar para comparar modelos de diferente estructura. Por ejemplo, su primera aplicación fue la búsqueda de modelos de mezcla con el número óptimo de clases. Añadir clases adicionales a un modelo de mezcla siempre permitirá que los datos se ajusten con mayor precisión, pero según el MML esto debe sopesarse frente a los bits adicionales necesarios para codificar los parámetros que definen esas clases.
• MML es un método de comparación de modelos bayesianos . A cada modelo se le asigna una puntuación.
• MML es invariante en cuanto a escala y estadísticamente invariante. A diferencia de muchos métodos de selección bayesianos, a MML no le importa si cambias de medir longitud a medir volumen o de coordenadas cartesianas a coordenadas polares.
• MML es estadísticamente consistente. Para problemas como el problema de Neyman-Scott (1948) o el análisis factorial donde la cantidad de datos por parámetro está limitada, MML puede estimar todos los parámetros con consistencia estadística .
• La MML tiene en cuenta la precisión de la medición. Utiliza la información de Fisher (en la aproximación de Wallace-Freeman de 1987 u otros hipervolúmenes en otras aproximaciones) para discretizar de forma óptima los parámetros continuos. Por lo 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 de decisión y gráficos, 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.

Véase 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 es típicamente una aproximación computable (ver ^[4] )
• Longitud mínima de 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}}: CS1 maint: nombres múltiples: lista de autores ( enlace ) CS1 maint: 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". The Computer Journal . 11 (2): 185–194. doi : 10.1093/comjnl/11.2.185 . ISSN  0010-4620.
3. Allison, Lloyd. (2019). Codificación de la navaja de Ockham . Springer. ISBN 978-3030094881.OCLC 1083131091  .
4. Wallace, CS; Dowe, DL (1999-01-01). "Longitud mínima del mensaje y complejidad de Kolmogorov". The Computer Journal . 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". Computer Journal . 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). Codificación de la navaja de Ockham . Springer. 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 de búsqueda de las publicaciones de Chris Wallace.
• Wallace, CS; Dowe, DL (1999). "Longitud mínima del mensaje y complejidad de Kolmogorov". Revista 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". Revista 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, Sídney, Australia. Computing Science and Statistics . Vol. 28. págs. 614–618.
• Historia de MML, última charla de CSW.
• Needham, S.; Dowe, D. (2001). La longitud del mensaje como una navaja de Ockham eficaz en la inducción de árboles de decisión (PDF) . Actas del 8º Taller internacional sobre IA y estadística. Págs. 253–260.(Muestra cómo la navaja de Occam funciona bien cuando se interpreta como MML).
• Allison, L. (enero de 2005). "Modelos para el aprendizaje automático y la minería de datos en la programación funcional". Journal of Functional Programming . 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 de mensaje, MDL y redes bayesianas generalizadas con lenguajes asimétricos". En Grunwald, P.; Pitt, MA; Myung, IJ (eds.). Avances en longitud mínima de descripción: teoría y aplicaciones. MIT Press. págs. 265–294. ISBN 978-0-262-07262-5.
• Comley, Joshua W.; Dowe, DL (5–8 de junio de 2003). Redes bayesianas generales y lenguajes asimétricos. Actas de la 2.ª Conferencia internacional de Hawái sobre estadística y campos relacionados., .pdf. Comley y Dowe (2003, 2005) son los dos primeros artículos sobre redes bayesianas MML que utilizan parámetros con 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 MML de LA, (MML alt.).
• Longitud mínima del mensaje (MML), investigadores y enlaces.
• «Otro sitio web de investigación sobre 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 una cuenta)
• mikko.ps: breves diapositivas introductorias de Mikko Koivisto en Helsinki
• Método de selección de modelos con criterio de información de Akaike ( AIC ) y una comparación con MML: Dowe, DL; Gardner, S.; Oppy, G. (diciembre de 2007). "Bayes not Bust! Why Simplicity is no Problem for Bayesians" (¡Bayes no es un fracaso! Por qué la simplicidad no es un problema para los bayesianos). Br. J. Philos. Sci . 58 (4): 709–754. doi :10.1093/bjps/axm033.