Principio de longitud mínima de descripción

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de marzo de 2021; la verificación requiere 1 edición .

El principio de longitud de descripción mínima ( MDL ) es una  formalización de la navaja de Occam , en la que la mejor hipótesis (modelo y sus parámetros) para un conjunto de datos dado es la que conduce a una mejor compresión de datos . El principio MDL fue propuesto por Jorma Rissanen en 1978 [1] . El principio es un concepto importante en la teoría de la información y la teoría del aprendizaje computacional [2] [3] [4] .

Resumen

Cualquier conjunto de datos se puede representar como una cadena de caracteres de un alfabeto finito (digamos, binario ) .

[El Principio MDL] se basa en la siguiente realización: cualquier patrón en un conjunto dado de datos se puede usar para comprimir los datos , es decir, describir los datos usando un conjunto de caracteres más pequeño que el necesario para describir los datos literalmente. (Grunwald, 1998) [5]

MDL es una teoría de inferencia e inferencia estadística que comienza con la idea de que todo el aprendizaje estadístico consiste en descubrir patrones en los datos, y la mejor hipótesis para describir patrones en los datos es aquella que los comprime al máximo. Al igual que otros métodos estadísticos, el principio se puede utilizar para entrenar los parámetros del modelo utilizando algunos datos. Aunque, por lo general, los métodos estadísticos estándar asumen que la forma general del modelo es fija. La principal fortaleza del principio MDL es que se puede utilizar para seleccionar la apariencia general de un modelo y sus parámetros. Una característica cuantitativa (a veces solo el modelo, a veces solo los parámetros, a veces tanto el modelo como los parámetros) se denomina hipótesis. La idea básica es considerar un código de dos etapas (sin pérdidas) que codifica datos codificando primero la hipótesis en el conjunto de hipótesis bajo consideración y luego codificando "con" . En su contexto más simple, esto simplemente significa "la codificación de la desviación de los datos de la predicción obtenida por" :

La hipótesis sobre la que se alcanza el mínimo se considera entonces como la mejor explicación de los datos . Como un ejemplo simple, considere un problema de regresión: deje que los datos consistan en una secuencia de puntos , deje que el conjunto sea el conjunto de todos los polinomios de a . Para describir un polinomio de grado (digamos) , primero se deben discretizar los parámetros con cierta precisión, luego se debe describir esta precisión ( un número natural ). Luego se debe describir el grado (otro número natural) y, finalmente, se deben describir los parámetros. La longitud total será . Luego describimos los puntos usando un código fijo para los valores de x y luego usando un código para las varianzas .

En la práctica, a menudo (pero no siempre) se utiliza un modelo estadístico . Por ejemplo, asocie cada polinomio con la distribución condicional correspondiente, lo que indica que los datos se distribuyen normalmente con una media y alguna varianza , que se pueden fijar o agregar como parámetros. Luego, el conjunto de hipótesis se reduce a un modelo lineal en forma de polinomio.

Además, a menudo los valores específicos de los parámetros no son directamente interesantes, sino que solo, por ejemplo, es interesante el grado del polinomio. En este caso, el conjunto se establece igual a , donde cada elemento representa la hipótesis de que los datos se describen mejor mediante un polinomio de grado j. Luego codifique los datos de la hipótesis dada con un código de una parte diseñado para que cuando alguna hipótesis se ajuste bien a los datos, el código sea corto. El desarrollo de dichos códigos se denomina codificación universal . Hay varios tipos de códigos universales que se pueden usar, a menudo con longitudes similares para secuencias de datos largas pero diferentes para secuencias cortas. Los "mejores" códigos (en el sentido de que tienen la propiedad de optimización minimax) son códigos de máxima verosimilitud normalizados (NML) o códigos Shtarkov . Una clase muy útil de códigos son los códigos de verosimilitud marginal bayesianos. Para una familia de distribuciones exponenciales, cuando se usa el anterior de Jeffreys y el espacio de parámetros está adecuadamente restringido, son asintóticamente iguales a los códigos NML. Esto acerca la teoría MDL a la selección del modelo bayesiano objetivo, al que también se aplica a veces el anterior de Jeffreys, aunque por diferentes razones.  

MDL versus la teoría de la inferencia de Solomon

Para seleccionar la hipótesis que captura la mayor regularidad en los datos, los científicos buscan la hipótesis que ofrece la mejor compresión. Para hacer esto, el código de compresión de datos es fijo. Quizás el código más común que se puede usar es un lenguaje de computadora ( Turing-completo ) . El programa de salida está escrito en este lenguaje. Luego, el programa presenta efectivamente los datos. La longitud del programa más corto que genera datos se denomina complejidad de Kolmogorov de los datos. Esta es la idea central de la teoría idealizada de inferencia de Ray Solomon , que es la inspiración para MDL.

Conclusión

Sin embargo, esta teoría matemática no proporciona un método práctico para obtener una conclusión. Las razones más importantes para esto son:

MDL intenta combatir este problema al:

Una de las propiedades más importantes de los métodos MDL es que brindan una protección natural contra el sobreajuste , ya que implementan un compromiso entre la complejidad de la hipótesis (clase modelo) y la complejidad de los datos [3] .

Ejemplo de MDL

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

Por esta razón, un método estadístico ingenuo puede elegir el segundo modelo como la mejor explicación para los datos. Sin embargo, el enfoque MDL construiría un código basado en la hipótesis en lugar de usar el mejor código. Este código podría ser un código de máxima verosimilitud normalizado o un código bayesiano. Si se utiliza dicho código, la longitud total del código basado en la segunda clase de modelos sería de más de 1000 bits. Por lo tanto, la conclusión que se deriva inevitablemente del enfoque MDL es que no hay pruebas suficientes para la hipótesis de la moneda sesgada, incluso si el mejor elemento de la segunda clase de modelos se ajusta mejor a los datos.

Designación MDL

El centro de la teoría MDL es la correspondencia uno a uno entre las longitudes del código de función y las distribuciones de probabilidad (esto se deriva de la desigualdad de Kraft-McMillan ). Para cualquier distribución de probabilidad, puede construir un código tal que la longitud (en bits) sea . Este código minimiza la longitud de código esperada. Por el contrario, si se da un código , se puede construir una distribución de probabilidad tal que se cumpla el enunciado anterior. (Los problemas de redondeo se ignoran aquí). En otras palabras, encontrar un código eficiente es equivalente a encontrar una buena distribución de probabilidad.

Conceptos relacionados

El principio MDL está fuertemente relacionado con la teoría de la probabilidad y las estadísticas a través de la coincidencia de códigos y la distribución de probabilidad mencionada anteriormente. Esto ha llevado a algunos investigadores a concluir que el principio MDL es equivalente a la inferencia bayesiana : la longitud del código del modelo y los datos en MDL corresponden a la probabilidad previa y la probabilidad marginal en el esquema bayesiano [6] .

Si bien los algoritmos bayesianos suelen ser útiles para construir códigos MDL eficientes, el principio MDL también se adapta a otros códigos no bayesianos. Un ejemplo es el código de máxima verosimilitud normalizado de Starkov , que juega 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 la corrección del proceso de adquisición de datos ; en la práctica, una clase de modelos suele ser una simplificación de la realidad y, por lo tanto, no contiene códigos ni distribuciones de probabilidad que sean verdaderas en un objetivo. sentido [7] [8] . En el último enlace, Rissanen trae la base matemática del principio MDL a la función de estructura de Kolmogorov .

De acuerdo con la filosofía de MDL, los métodos bayesianos deben evitarse si se basan en una probabilidad previa poco confiable , lo que puede conducir a resultados deficientes. Las condiciones a priori aceptables desde el punto de vista de MDL también son preferibles al llamado análisis objetivo bayesiano . Aquí, sin embargo, las razones suelen ser diferentes [9] .

Otros sistemas

MDL no fue el primer enfoque de aprendizaje teórico de la información . En 1968, Wallace y Bolton introdujeron un concepto relacionado denominado longitud mínima del mensaje ( MML) .  La diferencia entre MDL y MML es una fuente de confusión constante. Externamente, los métodos parecen ser en su mayoría equivalentes, pero hay algunas diferencias significativas, especialmente en la interpretación:

Véase también

Notas

  1. ↑ Rissanen, 1978 , pág. 465–658.
  2. ↑ Longitud mínima de descripción (enlace descendente) . Universidad de Helsinki . Consultado el 3 de julio de 2010. Archivado desde el original el 18 de febrero de 2010. 
  3. ↑ 1 2 Grünwald, 2007 .
  4. ↑ Grünwald, Myung, Pitt, 2005 .
  5. ↑ Grunwald, 2004 .
  6. ↑ Mackay, 2003 .
  7. ↑ 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.
  8. ↑ Rissanen, 2007 .
  9. ↑ Nannen, 2010 .

Literatura

Lectura para leer más