La longitud mínima de descripción (MDL) se refiere a varias formalizaciones de la navaja de Occam basadas en lenguajes formales utilizados para describir datos con parsimonia . En su forma más básica, MDL es un principio de selección de modelo : la descripción más corta de los datos como el mejor modelo. Estas descripciones están destinadas a proporcionar modelos científicos basados en datos . Esta idea se puede extender a otras formas de inferencia inductiva y aprendizaje, más allá de la selección del modelo; también se puede usar para la estimación y la predicción secuencial, por ejemplo, sin identificar explícitamente un solo modelo para los datos. MDL es un concepto importante en la teoría de la información y la teoría del aprendizaje computacional.. Es importante destacar que la frase nominal definida " el principio de longitud mínima de descripción " se utiliza para al menos tres ejemplificaciones bastante diferentes de esta idea, que, aunque están interrelacionadas, varían en lo que se entiende por "descripción". Se utiliza principalmente para la teoría del aprendizaje de Jorma Rissanen , en la que los modelos son hipótesis estadísticas y las descripciones se definen como códigos universales, un concepto central de la teoría de la información (ver más abajo). En segundo lugar, todavía se usa a menudo para referirse al primer intento pragmático de Rissanen de 1978 [1] de derivar automáticamente descripciones breves, relacionadas con el Criterio de Información Bayesiano (BIC). En tercer lugar, se utiliza a menudo 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 es 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 del advenimiento de la programación de computadoras, generar tales descripciones era el trabajo intelectual de los teóricos científicos. Era mucho menos formal de lo que se ha convertido 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ó como la navaja de Occam fue una guía informal para decidir qué modelo era mejor.
Con el advenimiento de los lenguajes formales y la programación informática, la navaja de Occam se definió matemáticamente. Los modelos de un conjunto dado de observaciones, codificados como bits de datos, podrían crearse en forma de programas de computadora 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 completamente producto de 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 los mismos. El principio MDL solo requiere que la descripción más corta, cuando se ejecuta, produzca el conjunto de datos original sin errores.
Códigos de dos partes
La distinción en los programas de computadora entre programas y datos literales se aplica a todas las descripciones formales y, a veces, se las denomina " dos partes " de una descripción. En el aprendizaje estadístico de MDL, esta descripción con frecuencia se denomina 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 de descripción mínima teórica de un conjunto de datos, denominada complejidad de Kolmogorov , no puede calcularse. 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 probar que no existe tal programa más corto. No obstante, dados dos programas que generan el conjunto de datos, el principio MDL selecciona el más corto de los dos como el que incorpora el mejor modelo.
En la práctica, cuando se encuentra un modelo de aprendizaje automático que se ajusta mejor a los datos de acuerdo con el principio MDL, se selecciona el modelo que minimiza la longitud de un código (programa) de dos partes. Como ejemplo, en el caso supervisado de aprender la lista de reglas que mejor se ajusta (la forma probabilística de una lista de decisiones ) de un conjunto de datos, [2] uno elige la lista de reglas que minimiza el código de dos partes compuesto por: 1) el código que define de forma única una lista de reglas dadas todas las posibles listas de reglas que podrían generarse a partir de ese conjunto de datos, es decir, teniendo en cuenta el número de variables y sus posibles combinaciones; y 2) el código que devuelve el conjunto de datos dada la lista de reglas específicas como se define en el primer código. El primer código está diseñado específicamente para evitar el sobreajuste mediante la penalización de listas de reglas más complejas que, naturalmente, serían más propensas a sobreajustarse. Tenga en cuenta que el uso de un código de dos partes es esencial cuando se necesita distinguir los diferentes modelos, como en el caso de encontrar el modelo y sus parámetros que mejor se ajustan a los datos. Esto contrasta con la tarea de simplemente querer saber el tamaño del modelo (por ejemplo, el número de reglas en una lista de reglas) necesario para el mejor desempeño.
Trabajo reciente sobre aprendizaje MDL algorítmico
El reciente aprendizaje automático de modelos de datos algorítmicos, en oposición a los estadísticos, ha recibido una atención cada vez mayor con la creciente disponibilidad de datos, recursos informáticos y avances teóricos. [3] [4] Los enfoques se basan en el floreciente campo de la inteligencia artificial general . Poco antes de su muerte, Marvin Minsky se pronunció rotundamente a favor de esta línea de investigación, diciendo: [5]
- "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 de cómo hacer predicciones dada una colección de experiencias y esta es una teoría hermosa, todo el mundo debería aprenderlo, pero tiene un problema, es decir, que no se puede calcular realmente lo que predice esta teoría porque es demasiado difícil, requiere una cantidad infinita de trabajo. Sin embargo, debería ser posible hacer aproximaciones prácticas al Chaitin , Kolmogorov, teoría de Solomonoff que haría mejores predicciones que cualquier otra que tengamos hoy. Todos deberían aprender todo sobre eso y pasar el resto de sus vidas trabajando en ello ".
- Mesa redonda sobre los límites del entendimiento
- Festival Mundial de la Ciencia, Nueva York, 14 de diciembre de 2014
Aprendizaje estadístico MDL
Cualquier conjunto de datos se puede representar 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 dado de datos puede usarse para comprimir los datos , es decir, para describirlos usando menos símbolos de los necesarios para describir los datos literalmente. (Grünwald, 1998) [6]
Basándose 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. Comienza 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 más puede comprimir estadísticamente los datos. Al igual que otros métodos estadísticos, se puede utilizar para aprender los parámetros de un modelo utilizando algunos datos. Sin embargo, por lo general, los métodos estadísticos estándar asumen 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 solo un modelo, a veces solo parámetros, a veces ambos al mismo tiempo) se llama hipótesis. La idea básica es entonces considerar el código de dos etapas (sin pérdidas) que codifica los datos con longitud primero codificando una hipótesis en el conjunto de hipótesis consideradas y luego codificando "con la ayuda de" ; en el contexto más simple, esto solo significa "codificar las desviaciones de los datos de las predicciones hechas por:
La 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ía consistir en una secuencia de puntos , el conjunto podría ser el conjunto de todos los polinomios de a . 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 parámetros; la longitud total sería. Entonces, uno describiría los puntos en usando un código fijo para los valores xy luego usando un código para el desviaciones .
En la práctica, a menudo (pero no siempre) se usa un modelo probabilístico . Por ejemplo, se asocia cada polinomio con la distribución condicional correspondiente expresando que dado , se distribuye normalmente con media y alguna variación que podría ser fijo o agregado como un parámetro libre. Entonces el conjunto de hipótesis se reduce a la suposición de un modelo lineal, , con un polinomio.
Además, a menudo uno no está directamente interesado en valores de parámetros específicos, sino solo, por ejemplo, en el grado del polinomio. En ese caso, uno establece ser - estar donde cada representa la hipótesis de que los datos se describen mejor como un polinomio de j-ésimo grado. Uno luego codifica datos hipótesis dada utilizando un código de una parte diseñado de tal manera que, siempre que alguna hipótesis se ajusta bien a los datos, la longitud del código es corto. El diseño de tales códigos se llama codificación universal . Hay varios tipos de códigos universales que se pueden usar, que a menudo dan longitudes similares para secuencias de datos largas pero que difieren para las cortas. El 'mejor' (en el sentido de que tiene una propiedad de optimalidad 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 usa Jeffreys prior y el espacio de parámetros está adecuadamente restringido, estos coinciden asintóticamente con los códigos NML; esto pone la teoría MDL en estrecho contacto con la selección objetiva del modelo de 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 "proporciona un criterio de selección formalmente idéntico al enfoque BIC " [7] para un gran número de muestras.
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 los 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 1000 bits.
- El segundo consiste en 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 colas. Entonces, la longitud del código de acuerdo con 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 una 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 un código de este tipo, la longitud de código total basada en la segunda clase de modelo sería superior a 1000 bits. Por lo tanto, la conclusión al seguir un enfoque MDL es inevitablemente que no hay suficiente evidencia para apoyar la hipótesis de la moneda sesgada, aunque el mejor elemento de la segunda clase de modelo proporciona un mejor ajuste a los datos.
Notación estadística MDL
El 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 es 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 lo mismo vale. (Aquí se ignoran los problemas de redondeo). En otras palabras, buscar un código eficiente equivale a buscar una buena distribución de probabilidad.
Limitaciones del aprendizaje estadístico MDL
El lenguaje de descripción de MDL estadístico no es computacionalmente universal. Por tanto, no puede, ni siquiera en principio, aprender modelos de procesos naturales recursivos.
Conceptos relacionados
El aprendizaje estadístico de MDL está fuertemente conectado con la teoría de la probabilidad y la estadística a través de la correspondencia entre los códigos y las 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 a menudo es útil para construir códigos MDL eficientes, el marco MDL también se adapta a otros códigos que no son bayesianos. Un ejemplo es el código de máxima verosimilitud normalizada de Shtarkov , que juega un papel central en la teoría actual de MDL, 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] [10] En la última referencia mencionada, Rissanen basa el sustento matemático de MDL en la función de estructura de Kolmogorov .
De acuerdo con la filosofía MDL, los métodos bayesianos deben descartarse si se basan en antecedentes inseguros que conducirían a resultados deficientes. Los a priori que son aceptables desde el punto de vista de MDL también tienden a ser 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 de 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 hay algunas diferencias significativas, especialmente en la interpretación:
- MML es un enfoque bayesiano completamente subjetivo: parte de la idea de que uno representa las propias 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 se 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 en la primera parte. La diferencia entre los métodos es que, en la literatura MDL, se aboga por que los parámetros no deseados se muevan a la segunda parte del código, donde pueden representarse con los datos mediante el uso de un código de una parte , que suele ser más eficaz 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 de MML, cada parámetro se establece exactamente con esa precisión, lo 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 para explicar los datos (a dicho parámetro se le asignará una longitud de código correspondiente a la probabilidad previa (bayesiana) de que el parámetro no resulte ú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 hace. La diferencia radica en la maquinaria aplicada para llegar a la misma conclusión.
Ver también
- Probabilidad algorítmica
- Teoría algorítmica de la información
- Inferencia inductiva
- Probabilidad inductiva
- Complejidad de Lempel-Ziv
Referencias
- ^ Rissanen, J. (septiembre de 1978). "Modelado por descripción de datos más corta". Automatica . 14 (5): 465–471. doi : 10.1016 / 0005-1098 (78) 90005-5 .
- ^ Proença, Hugo; van Leeuwen, Matthijs (mayo de 2019). "Clasificación multiclase interpretable por listas de reglas basadas en MDL". arXiv : 1905.00328 . doi : 10.1016 / j.ins.2019.10.050 . Cite journal requiere
|journal=
( ayuda ) - ^ Zenil, Héctor; Kiani, Narsis A .; Zea, Allan A .; Tegnér, Jesper (enero de 2019). "Deconvolución causal por 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 .
- ^ "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 .
- ^ https://www.youtube.com/watch?v=DfY-DRsE86s&feature=youtu.be&t=5402
- ^ Grunwald, Peter (junio de 2004). "Una introducción tutorial al principio de longitud mínima de descripción". arXiv : matemáticas / 0406077 . Bibcode : 2004math ...... 6077G . Cite journal requiere
|journal=
( ayuda ) - ^ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). "Evaluación y selección de modelos". Los elementos del aprendizaje estadístico . Springer Series en Estadística. págs. 219-259. doi : 10.1007 / 978-0-387-84858-7_7 . ISBN 978-0-387-84857-0.
- ^ 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 ]
- ^ 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 .[ fuente autoeditada? ]
- ^ Rissanen, J. (2007). Información y complejidad en el modelado estadístico . Springer . Consultado el 3 de julio de 2010 .[ página necesaria ]
- ^ Nannen, Volker (mayo de 2010). "Una breve introducción a la selección del modelo, la complejidad de Kolmogorov y la longitud mínima de descripción (MDL)". arXiv : 1005.2364 . Código Bibliográfico : 2010arXiv1005.2364N . Cite journal requiere
|journal=
( ayuda )
Otras lecturas
- Longitud mínima de descripción en la Web , por la Universidad de Helsinki. Presenta 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 descripción , prensa MIT , ISBN 0-262-07262-9 .