Longitud mínima de la descripción

Principio de selección de modelo.

La longitud mínima de descripción ( MDL ) es un principio de selección de modelos donde la descripción más corta de los datos es el mejor modelo. Los métodos MDL aprenden a través de una perspectiva de compresión de datos y, a veces, se describen como aplicaciones matemáticas de la navaja de Occam . El principio MDL se puede extender a otras formas de inferencia y aprendizaje inductivo, por ejemplo, a la estimación y la predicción secuencial, sin identificar explícitamente un modelo único de datos.

MDL tiene su origen principalmente en la teoría de la información y se ha desarrollado aún más en los campos generales de la estadística, la informática teórica y el aprendizaje automático, y más específicamente la teoría del aprendizaje computacional .

Históricamente, existen usos diferentes, aunque interrelacionados, de la frase nominal definida " el principio de longitud mínima de la descripción " que varían en lo que se entiende por descripción :

• Dentro de la teoría del aprendizaje de Jorma Rissanen , un concepto central de la teoría de la información, los modelos son hipótesis estadísticas y las descripciones se definen como códigos universales.
• El primer intento pragmático de Rissanen en 1978 ^[1] de derivar automáticamente descripciones breves se relaciona con el Criterio de Información Bayesiano (BIC).
• Dentro de la teoría algorítmica de la información , donde la longitud de descripción de una secuencia de datos es la longitud del programa más pequeño que genera ese conjunto de datos. En este contexto, también se conoce como principio MDL "idealizado" y está estrechamente relacionado con la teoría de la inferencia inductiva de Solomonoff , que establece que el mejor modelo de un conjunto de datos está representado por su archivo autoextraíble más corto .

Descripción general

Al seleccionar la descripción de longitud mínima de los datos disponibles como el mejor modelo se observa el principio identificado como la navaja de Occam. Antes de la llegada de la programación informática, generar tales descripciones era el trabajo intelectual de los teóricos científicos. Era mucho menos formal de lo que se ha vuelto en la era de las computadoras. Si dos científicos tenían un desacuerdo teórico, rara vez podían aplicar formalmente la navaja de Occam para elegir entre sus teorías. Tendrían diferentes conjuntos de datos y posiblemente diferentes lenguajes descriptivos. Sin embargo, la ciencia avanzó a medida que la navaja de Occam era una guía informal para decidir qué modelo era mejor.

Con la llegada de los lenguajes formales y la programación informática, la navaja de Occam quedó matemáticamente definida. Se podrían crear modelos de un conjunto determinado de observaciones, codificados como bits de datos, en forma de programas informáticos que generen esos datos. La navaja de Occam podría entonces seleccionar formalmente el programa más corto, medido en bits de esta información algorítmica , como el mejor modelo.

Para evitar confusiones, tenga en cuenta que no hay nada en el principio MDL que implique que una máquina haya producido el programa que incorpora el modelo. Puede ser enteramente producto de los humanos. El principio MDL se aplica independientemente de si la descripción que se ejecutará en una computadora es producto de humanos, máquinas o cualquier combinación de ellos. El principio MDL requiere sólo que la descripción más corta, cuando se ejecute, produzca el conjunto de datos original sin errores.

Códigos de dos partes

En los programas de computadora, la distinción entre programas y datos literales se aplica a todas las descripciones formales y a veces se la denomina " dos partes " de una descripción. En el aprendizaje estadístico de MDL, dicha descripción se denomina frecuentemente código de dos partes .

MDL en aprendizaje automático

MDL se aplica en el aprendizaje automático cuando los algoritmos (máquinas) generan descripciones. El aprendizaje ocurre cuando un algoritmo genera una descripción más corta del mismo conjunto de datos.

Sin embargo , la longitud mínima teórica de descripción de un conjunto de datos, llamada complejidad de Kolmogorov , no se puede calcular. Es decir, incluso si por casualidad un algoritmo genera el programa más corto de todos los que generan el conjunto de datos, un demostrador de teoremas automatizado no puede demostrar que no existe tal programa más corto. Sin embargo, dados dos programas que generan el conjunto de datos, el principio MDL selecciona el más corto de los dos como que incorpora el mejor modelo.

Trabajo reciente sobre aprendizaje algorítmico MDL

El reciente aprendizaje automático MDL de modelos de datos algorítmicos, a diferencia de los estadísticos, ha recibido una atención cada vez mayor con la creciente disponibilidad de datos, recursos computacionales y avances teóricos. ^{[2] [3]} Los enfoques se basan en el floreciente campo de la inteligencia artificial general . Poco antes de su muerte, Marvin Minsky se manifestó firmemente a favor de esta línea de investigación, diciendo: ^[4]

Me parece que el descubrimiento más importante desde Gödel fue el descubrimiento por Chaitin, Solomonoff y Kolmogorov del concepto llamado probabilidad algorítmica, que es una nueva teoría fundamental sobre cómo hacer predicciones dada una colección de experiencias y esta es una hermosa teoría, todos. Deberíamos aprenderlo, pero tiene un problema: que en realidad no se puede calcular lo que predice esta teoría porque es demasiado difícil y requiere una cantidad infinita de trabajo. Sin embargo, debería ser posible hacer aproximaciones prácticas a la teoría de Chaitin, Kolmogorov y Solomonoff que harían mejores predicciones que cualquier cosa que tengamos hoy. Todo el mundo debería aprenderlo todo y pasar el resto de su vida trabajando en ello.

—  Mesa redonda sobre Los límites de la comprensión, Festival Mundial de la Ciencia, Nueva York, 14 de diciembre de 2014

Aprendizaje estadístico MDL

Cualquier conjunto de datos puede representarse mediante una cadena de símbolos de un alfabeto finito (digamos, binario ) .

[El principio MDL] se basa en la siguiente idea: cualquier regularidad en un conjunto de datos determinado se puede utilizar para comprimir los datos , es decir, para describirlos utilizando menos símbolos de los necesarios para describir los datos literalmente. (Grünwald, 2004) ^[5]

Con base en esto, en 1978, Jorma Rissanen publicó un algoritmo de aprendizaje MDL utilizando la noción estadística de información en lugar de información algorítmica. En los últimos 40 años, esto se ha convertido en una rica teoría de procedimientos estadísticos y de aprendizaje automático con conexiones con la selección y el promedio de modelos bayesianos, métodos de penalización como Lasso y Ridge, etc. - Grünwald y Roos (2020) ^[6] dan una introducción que incluye todos los desarrollos modernos. Rissanen comenzó con esta idea: todo aprendizaje estadístico consiste en encontrar regularidades en los datos, y la mejor hipótesis para describir las regularidades en los datos es también la que es capaz de comprimir los datos estadísticamente en mayor medida. Al igual que otros métodos estadísticos, se puede utilizar para aprender los parámetros de un modelo utilizando algunos datos. Sin embargo, normalmente los métodos estadísticos estándar suponen que la forma general de un modelo es fija. La principal fortaleza de MDL es que también se puede utilizar para seleccionar la forma general de un modelo y sus parámetros. La cantidad de interés (a veces sólo un modelo, a veces sólo parámetros, a veces ambos al mismo tiempo) se denomina hipótesis. La idea básica es entonces considerar el código de dos etapas (sin pérdidas) que codifica datos con longitud codificando primero una hipótesis en el conjunto de hipótesis consideradas y luego codificando "con la ayuda de" ; en el contexto más simple, esto simplemente significa "codificar las desviaciones de los datos de las predicciones hechas por : ${\displaystyle D}$ ${\displaystyle {L(D)}}$ ${\displaystyle H}$ ${\displaystyle {\cal {H}}}$ ${\displaystyle D}$ ${\displaystyle H}$ ${\displaystyle H}$

$${\displaystyle {L(D)}=\min _{H\in {\cal {H}}}\ (\ L(H)+L(D|H)\ )\ }$$

El logro de este mínimo se considera entonces como la mejor explicación de los datos . Como ejemplo simple, tomemos un problema de regresión: los datos podrían consistir en una secuencia de puntos , el conjunto podría ser el conjunto de todos los polinomios desde hasta . Para describir un polinomio de grado (digamos) , primero habría que discretizar los parámetros con cierta precisión; entonces habría que describir esta precisión (un número natural); a continuación, habría que describir el grado (otro número natural) y, en el paso final, habría que describir los parámetros; la longitud total seria . Luego se describirían los puntos al usar algún código fijo para los valores de x y luego usar un código para las desviaciones . ${\displaystyle H}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D=(x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ ${\displaystyle {\cal {H}}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle H}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k+1}$ ${\displaystyle L(H)}$ ${\displaystyle D}$ ${\displaystyle n}$ ${\displaystyle y_{i}-H(x_{i})}$

En la práctica, a menudo (pero no siempre) se utiliza un modelo probabilístico . Por ejemplo, se asocia cada polinomio con la distribución condicional correspondiente que expresa que dado , se distribuye normalmente con media y cierta varianza que podría fijarse o agregarse como un parámetro libre. Entonces el conjunto de hipótesis se reduce al supuesto de un modelo lineal ^{[ se necesita aclaración ]} , con un polinomio. ${\displaystyle H}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle H(X)}$ ${\displaystyle \sigma ^{2}}$ ${\displaystyle {\cal {H}}}$ ${\displaystyle Y=H(X)+\epsilon }$ ${\displaystyle H}$

Además, a menudo uno no está directamente interesado en valores de parámetros específicos, sino simplemente, por ejemplo, en el grado del polinomio. En ese caso, se establece que cada uno representa la hipótesis de que los datos se describen mejor como un polinomio de j-ésimo grado. Luego se codifican los datos dada la hipótesis utilizando un código de una parte diseñado de manera que, siempre que alguna hipótesis se ajuste bien a los datos, la longitud del código sea corta. El diseño de dichos códigos se denomina codificación universal . Hay varios tipos de códigos universales que se pueden utilizar, y que a menudo dan longitudes similares para secuencias de datos largas pero diferentes para las cortas. Los "mejores" (en el sentido de que tienen una propiedad de optimización minimax) son los códigos de máxima verosimilitud normalizada (NML) o Shtarkov . Una clase de códigos bastante útil son los códigos de verosimilitud marginal bayesianos. Para familias exponenciales de distribuciones, cuando se utiliza Jeffreys prior y el espacio de parámetros está adecuadamente restringido, estos coinciden asintóticamente con los códigos NML; esto pone a la teoría MDL en estrecho contacto con la selección objetiva del modelo Bayes, en el que a veces también se adopta el anterior de Jeffreys, aunque por diferentes razones. El enfoque MDL para la selección de modelos "ofrece un criterio de selección formalmente idéntico al enfoque BIC " ^[7] para un gran número de muestras. ${\displaystyle {\cal {H}}}$ ${\displaystyle {\cal {H}}=\{{\cal {H}}_{0},{\cal {H}}_{1},\ldots \}}$ ${\displaystyle {\cal {H}}_{j}}$ ${\displaystyle D}$ ${\displaystyle {\cal {H}}_{j}}$ ${\displaystyle H\in {\cal {H}}_{j}}$ ${\displaystyle L(D|H)}$

Ejemplo de aprendizaje estadístico MDL

Se lanza una moneda 1000 veces y se registra el número de caras y cruces. Considere dos clases de modelos:

• El primero es un código que representa resultados con un 0 para cara o un 1 para cruz. Este código representa la hipótesis de que la moneda es justa. La longitud del código según este código es siempre exactamente de 1000 bits.
• El segundo consta de todos los códigos que son eficientes para una moneda con algún sesgo específico, lo que representa la hipótesis de que la moneda no es justa. Digamos que observamos 510 caras y 490 cruces. Entonces, la longitud del código según el mejor código de la segunda clase de modelo es inferior a 1000 bits.

Por esta razón, un método estadístico ingenuo podría elegir el segundo modelo como mejor explicación de los datos. Sin embargo, un enfoque MDL construiría un código único basado en la hipótesis, en lugar de simplemente usar el mejor. Este código podría ser el código de máxima verosimilitud normalizado o un código bayesiano. Si se utiliza dicho código, entonces la longitud total del código basada en la segunda clase de modelo sería mayor que 1000 bits. Por lo tanto, la conclusión al seguir un enfoque MDL es inevitable que no hay suficiente evidencia para apoyar la hipótesis de la moneda sesgada, a pesar de que el mejor elemento de la segunda clase de modelo proporciona un mejor ajuste a los datos.

Notación estadística MDL

Un elemento central de la teoría MDL es la correspondencia uno a uno entre las funciones de longitud del código y las distribuciones de probabilidad (esto se deriva de la desigualdad de Kraft-McMillan ). Para cualquier distribución de probabilidad , es posible construir un código tal que la longitud (en bits) de sea igual a ; este código minimiza la longitud esperada del código. Por el contrario, dado un código , se puede construir una distribución de probabilidad tal que se cumpla lo mismo. (Aquí se ignoran los problemas de redondeo). En otras palabras, buscar un código eficiente equivale a buscar una buena distribución de probabilidad. ${\displaystyle P}$ ${\displaystyle C}$ ${\displaystyle C(x)}$ ${\displaystyle -\log _{2}P(x)}$ ${\displaystyle C}$ ${\displaystyle P}$

Limitaciones del aprendizaje estadístico MDL

El lenguaje de descripción del MDL estadístico no es computacionalmente universal. Por lo tanto, no puede, ni siquiera en principio, aprender modelos de procesos naturales recursivos.

Conceptos relacionados

El aprendizaje estadístico de MDL está fuertemente relacionado con la teoría de la probabilidad y la estadística a través de la correspondencia entre códigos y distribuciones de probabilidad mencionadas anteriormente. Esto ha llevado a algunos investigadores a ver MDL como equivalente a la inferencia bayesiana : la longitud del código del modelo y los datos juntos en MDL corresponden respectivamente a la probabilidad previa y la probabilidad marginal en el marco bayesiano. ^[8]

Si bien la maquinaria bayesiana suele ser útil para construir códigos MDL eficientes, el marco MDL también admite otros códigos que no son bayesianos. Un ejemplo es el código de máxima verosimilitud normalizado de Shtarkov , que desempeña un papel central en la teoría MDL actual, pero no tiene equivalente en la inferencia bayesiana. Además, Rissanen enfatiza que no debemos hacer suposiciones sobre el verdadero proceso de generación de datos : en la práctica, una clase de modelo es típicamente una simplificación de la realidad y, por lo tanto, no contiene ningún código o distribución de probabilidad que sea verdadera en ningún sentido objetivo. ^{[9] [¿ fuente autoeditada? ] [10]} En la última referencia mencionada, Rissanen basa el fundamento matemático de MDL en la función estructural de Kolmogorov .

Según la filosofía MDL, los métodos bayesianos deben descartarse si se basan en antecedentes inseguros que conducirían a malos resultados. Los antecedentes que son aceptables desde el punto de vista de MDL también tienden a verse favorecidos en el llamado análisis bayesiano objetivo ; allí, sin embargo, la motivación suele ser diferente. ^[11]

Otros sistemas

El de Rissanen no fue el primer enfoque del aprendizaje basado en la teoría de la información ; Ya en 1968, Wallace y Boulton fueron pioneros en un concepto relacionado llamado longitud mínima de mensaje (MML). La diferencia entre MDL y MML es una fuente de confusión constante. Superficialmente, los métodos parecen en su mayoría equivalentes, pero existen algunas diferencias significativas, especialmente en la interpretación:

• MML es un enfoque bayesiano totalmente subjetivo: parte de la idea de que uno representa sus creencias sobre el proceso de generación de datos en forma de una distribución previa. MDL evita suposiciones sobre el proceso de generación de datos.
• Ambos métodos utilizan códigos de dos partes : la primera parte siempre representa la información que uno está tratando de aprender, como el índice de una clase de modelo ( selección de modelo ) o valores de parámetros ( estimación de parámetros ); la segunda parte es una codificación de los datos dada la información de la primera parte. La diferencia entre los métodos es que, en la literatura MDL, se recomienda que los parámetros no deseados se muevan a la segunda parte del código, donde se pueden representar con los datos mediante el llamado código de una parte , que A menudo es más eficiente que un código de dos partes . En la descripción original de MML, todos los parámetros están codificados en la primera parte, por lo que se aprenden todos los parámetros.
• Dentro del marco MML, cada parámetro se establece exactamente con la precisión que da como resultado la longitud total óptima del mensaje: el ejemplo anterior podría surgir si algún parámetro se consideró originalmente "posiblemente útil" para un modelo pero posteriormente se descubrió que no podía ayudar a explique los datos (a dicho parámetro se le asignará una longitud de código correspondiente a la probabilidad previa (bayesiana) de que se considere que el parámetro no es útil). En el marco MDL, la atención se centra más en comparar clases de modelos que en modelos, y es más natural abordar la misma pregunta comparando la clase de modelos que incluyen explícitamente dicho parámetro con alguna otra clase que no lo incluye. La diferencia radica en la maquinaria aplicada para llegar a la misma conclusión.

Ver también

• probabilidad algorítmica
• Teoría de la información algorítmica
• inferencia inductiva
• probabilidad inductiva
• Complejidad de Lempel-Ziv

Referencias

1. Rissanen, J. (septiembre de 1978). "Modelado por descripción de datos más corta". Automática . 14 (5): 465–471. doi :10.1016/0005-1098(78)90005-5.
2. Zenil, Héctor; Kiani, Narsis A.; Zea, Allan A.; Tegnér, Jesper (enero de 2019). "Deconvolución causal mediante modelos generativos algorítmicos". Inteligencia de la máquina de la naturaleza . 1 (1): 58–66. doi :10.1038/s42256-018-0005-0. hdl : 10754/630919 . S2CID  86562557.
3. "Remodelación del aprendizaje automático: una IA que piensa como un científico". Nature Machine Intelligence : 1, 28 de enero de 2019. doi :10.1038/s42256-019-0026-3. S2CID  189929110.
4. Archivado en Ghostarchive y Wayback Machine: "Los límites del entendimiento". YouTube .
5. Grunwald, Peter (junio de 2004). "Un tutorial de introducción al principio de longitud mínima de la descripción". arXiv : matemáticas/0406077 . Código Bib : 2004 matemáticas ...... 6077G. {{cite journal}}: Citar diario requiere |journal=( ayuda )
6. Grünwald, Peter; Roos, Teemu (2020). "Revisión de la longitud mínima de la descripción". Revista Internacional de Matemáticas para la Industria . 11 (1). doi : 10.1142/S2661335219300018 . hdl : 10138/317252 . S2CID  201314867.
7. Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). "Evaluación y selección de modelos". Los elementos del aprendizaje estadístico . Serie Springer en Estadística. págs. 219-259. doi :10.1007/978-0-387-84858-7_7. ISBN 978-0-387-84857-0.
8. MacKay, David JC; Kay, David JC Mac (2003). Teoría de la información, inferencia y algoritmos de aprendizaje . Prensa de la Universidad de Cambridge. ISBN 978-0-521-64298-9.^{[ página necesaria ]}
9. Rissanen, Jorma. "Página de inicio de Jorma Rissanen". Archivado desde el original el 10 de diciembre de 2015 . Consultado el 3 de julio de 2010 .
10. Rissanen, J. (2007). Información y complejidad en la modelización estadística. Saltador . Consultado el 3 de julio de 2010 .^{[ página necesaria ]}
11. Nannen, Volker (mayo de 2010). "Una breve introducción a la selección de modelos, la complejidad de Kolmogorov y la longitud mínima de descripción (MDL)". arXiv : 1005.2364 . Código Bib : 2010arXiv1005.2364N. {{cite journal}}: Citar diario requiere |journal=( ayuda )

Otras lecturas

• Longitud mínima de descripción en la Web, por la Universidad de Helsinki. Incluye lecturas, demostraciones, eventos y enlaces a investigadores de MDL.
• Página de inicio de Jorma Rissanen, que contiene notas de conferencias y otro material reciente sobre MDL.
• Avances en la longitud mínima de la descripción , MIT Press , ISBN 0-262-07262-9 .