En 1973, Kolmogorov propuso un enfoque no probabilístico de la estadística y la selección de modelos. Sea cada dato una cadena binaria finita y un modelo sea un conjunto finito de cadenas binarias. Considere las clases de modelos que consisten en modelos de complejidad máxima dada de Kolmogorov . La función de estructura de Kolmogorov de una cadena de datos individual expresa la relación entre la restricción del nivel de complejidad en una clase de modelo y la menor cardinalidad logarítmica de un modelo en la clase que contiene los datos. La función de estructura determina todo estocásticoPropiedades de la cadena de datos individual: para cada clase de modelo restringida, determina el modelo individual de mejor ajuste en la clase, independientemente de si el modelo verdadero está en la clase de modelo considerada o no. En el caso clásico hablamos de un conjunto de datos con distribución de probabilidad, y las propiedades son las de las expectativas. Por el contrario, aquí tratamos con cadenas de datos individuales y las propiedades de la cadena individual en la que nos enfocamos. En este escenario, una propiedad se mantiene con certeza en lugar de con alta probabilidad como en el caso clásico. La función de estructura de Kolmogorov cuantifica con precisión la bondad de ajuste de un modelo individual con respecto a los datos individuales.
La función de estructura de Kolmogorov se utiliza en la teoría de la información algorítmica , también conocida como la teoría de la complejidad de Kolmogorov, para describir la estructura de una cadena mediante el uso de modelos de complejidad creciente.
Definición de Kolmogorov
La función de estructura fue propuesta originalmente por Kolmogorov en 1973 en un simposio de Teoría de la Información Soviética en Tallin, pero estos resultados no fueron publicados [1] p. 182. Pero los resultados se anunciaron en [2] en 1974, el único registro escrito por el propio Kolmogorov. Una de sus últimas declaraciones científicas es (traducida del ruso original por LA Levin):
A cada objeto constructivo le corresponde una función de un número natural k — el logaritmo de cardinalidad mínima de conjuntos que contienen x que permiten definiciones de complejidad como máximo k. Si el propio elemento x permite una definición simple, entonces la funcióncae a 0 incluso para k pequeño. A falta de tal definición, el elemento es "aleatorio" en un sentido negativo. Pero es positivamente "probabilísticamente aleatorio" solo cuando la función habiendo tomado el valor en un relativamente pequeño , luego cambia aproximadamente como .
- Kolmogorov , anuncio citado anteriormente
Definición contemporánea
Se trata en Cover y Thomas. [1] Está ampliamente estudiado en Vereshchagin y Vitányi [3] donde también se resuelven las principales propiedades. La función de estructura de Kolmogorov se puede escribir como
dónde es una cadena binaria de longitud con dónde es un modelo contemplado (conjunto de cadenas de n longitudes) para , es la complejidad de Kolmogorov de y es un valor entero no negativo que limita la complejidad del objeto contemplado 's. Claramente, esta función no aumenta y alcanza por dónde es el número requerido de bits para cambiar dentro y es la complejidad de Kolmogorov de.
La estadística algorítmica suficiente
Definimos un conjunto conteniendo tal que
- .
La función nunca disminuye más que una constante independiente fija por debajo de la diagonal llamada línea de suficiencia L definida por
- .
Se aproxima a una distancia constante mediante la gráfica de para ciertos argumentos (por ejemplo, para ). Para éstostenemos y el modelo asociado (testigo de ) se denomina conjunto óptimo para , y su descripción de bits es, por tanto, una estadística algorítmica suficiente . Escribimos "algorítmico" para la "complejidad de Kolmogorov" por convención. Las principales propiedades de una estadística algorítmica suficiente son las siguientes: Si es una estadística algorítmica suficiente para , luego
- .
Es decir, la descripción en dos partes de usando el modelo y como código de datos a modelo el índice de en la enumeración de en bits, es tan conciso como el código más corto de una parte de en bits. Esto se puede ver fácilmente de la siguiente manera:
- ,
usando desigualdades sencillas y la propiedad de suficiencia, encontramos que . (Por ejemplo, dado, podemos describir auto-delimitante (se puede determinar su final) en bits.) Por lo tanto, la deficiencia de aleatoriedad de en es una constante, lo que significa que es un elemento típico (aleatorio) de S. Sin embargo, puede haber modelos conteniendo que no son estadísticas suficientes. Una estadística algorítmica suficiente por tiene la propiedad adicional, además de ser un modelo de mejor ajuste, que y por lo tanto por la simetría de complejidad de Kolmogorov de la información (la información sobre en es aproximadamente lo mismo que la información sobre en x) tenemos : la estadística algorítmica suficiente es un modelo de mejor ajuste que está casi completamente determinado por . ( es un programa más corto para .) La estadística algorítmica suficiente asociada con el menor se denomina estadística algorítmica mínima suficiente .
Con respecto a la imagen: La función de estructura MDL se explica a continuación. La función de estructura de bondad de ajuste es la menor deficiencia de aleatoriedad (ver arriba) de cualquier modelo por tal que . Esta función de estructura da la bondad de ajuste de un modelo(que contiene x) para la cadena x. Cuando es bajo, el modelo encaja bien, y cuando es alto, el modelo no encaja bien. Si para algunos entonces hay un modelo típico por tal que y es típico (aleatorio) para S. Es decir, es el modelo que mejor se ajusta a x. Para obtener más detalles, consulte [1] y especialmente [3] y. [4]
Selección de propiedades
Dentro de las restricciones de que el gráfico desciende en un ángulo de al menos 45 grados, que comienza en ny termina aproximadamente en , cada gráfico (hasta un término aditivo en argumento y valor) se realiza mediante la función de estructura de algunos datos x y viceversa. Cuando el gráfico golpea primero la diagonal, el argumento (complejidad) es el de la estadística mínima suficiente. Es imposible determinar este lugar. Ver. [3]
Propiedad principal
Está comprobado que en cada nivel de complejidad la función de estructura nos permite seleccionar el mejor modelo para la cadena individual x dentro de una tira de con certeza, no con gran probabilidad. [3]
La variante MDL
La función Longitud mínima de descripción (MDL): La longitud del código mínimo de dos partes para x que consiste en el costo del modelo K (S) y la longitud del índice de x en S, en la clase de modelo de conjuntos de Kolmogorov máximo dado. complejidad, la complejidad de S superior delimitada por , viene dada por la función MDL o estimador MDL restringido:
dónde es la longitud total del código de dos partes de x con ayuda del modelo S.
Propiedad principal
Está comprobado que en cada nivel complejidad, la función de estructura nos permite seleccionar el mejor modelo S para la cadena individual x dentro de una tira de con certeza, no con gran probabilidad. [3]
Aplicación en estadística
Las matemáticas desarrolladas anteriormente fueron tomadas como la base de MDL por su inventor Jorma Rissanen . [5]
Modelos de probabilidad
Para cada distribución de probabilidad computable se puede probar [6] que
- .
Por ejemplo, si es una distribución computable en el conjunto de cuerdas de longitud , luego cada tiene probabilidad . La función estructural de Kolmogorov se convierte en
donde x es una cadena binaria de longitud n con dónde es un modelo contemplado (probabilidad computable de -cadenas de longitud) para , es la complejidad de Kolmogorov de y es un valor entero que limita la complejidad de lo contemplado 's. Claramente, esta función no es creciente y alcanza por donde c es el número requerido de bits para cambiar dentro y es la complejidad de Kolmogorov de. Luego. Para cada nivel de complejidad la función es la versión de complejidad de Kolmogorov de la máxima verosimilitud (ML).
Propiedad principal
Está comprobado que en cada nivel de complejidad la función de estructura nos permite seleccionar el mejor modelo para la cuerda individual dentro de una franja de con certeza, no con gran probabilidad. [3]
La variante MDL y los modelos de probabilidad
La función MDL: La longitud del código mínimo de dos partes para x que consiste en el costo del modelo K (P) y la longitud de , en la clase de modelo de funciones de masa de probabilidad computable de complejidad máxima dada de Kolmogorov , la complejidad de P superior delimitada por , viene dada por la función MDL o estimador MDL restringido:
dónde es la longitud total del código de dos partes de x con ayuda del modelo P.
Propiedad principal
Está comprobado que en cada nivel complejidad, la función MDL nos permite seleccionar el mejor modelo P para la cadena individual x dentro de una tira de con certeza, no con gran probabilidad. [3]
Extensión para calificar la distorsión y la eliminación de ruido
Resulta que el enfoque puede extenderse a una teoría de la distorsión de la velocidad de las secuencias finitas individuales y la eliminación de ruido de las secuencias finitas individuales [7] utilizando la complejidad de Kolmogorov. Se han llevado a cabo con éxito experimentos con programas de compresores reales. [8] Aquí se asume que, para datos naturales, la complejidad de Kolmogorov no está lejos de la longitud de una versión comprimida que utiliza un buen compresor.
Referencias
- ^ a b c Portada, Thomas M .; Thomas, Joy A. (1991). Elementos de la teoría de la información . Nueva York: Wiley. págs. 175-178 . ISBN 978-0471062592.
- ^ Resumen de una charla para la Sociedad Matemática de Moscú en Uspekhi Mat. Nauk Volumen 29, Número 4 (178) en las Comunicaciones de la Sociedad Matemática de Moscú, página 155 (en la edición rusa, no traducida al inglés)
- ^ a b c d e f g Vereshchagin, NK; Vitanyi, PMB (1 de diciembre de 2004). "Funciones de la estructura de Kolmogorov y selección del modelo". Transacciones IEEE sobre teoría de la información . 50 (12): 3265–3290. arXiv : cs / 0204037 . doi : 10.1109 / TIT.2004.838346 .
- ^ Gacs, P .; Tromp, JT; Vitanyi, PMB (2001). "Estadísticas algorítmicas". Transacciones IEEE sobre teoría de la información . 47 (6): 2443–2463. arXiv : matemáticas / 0006233 . doi : 10.1109 / 18.945257 .
- ^ Rissanen, Jorma (2007). Información y complejidad en el modelado estadístico (Online-Ausg. Ed.). Nueva York: Springer. ISBN 978-0-387-36610-4.
- ^ A.Kh. Shen, El concepto de (α, β) -estocasticidad en el sentido de Kolmogorov, y sus propiedades, Matemáticas soviéticas. Dokl., 28: 1 (1983), 295-299.
- ^ Vereshchagin, Nikolai K .; Vitanyi, Paul MB (1 de julio de 2010). "Tasa de distorsión y reducción de ruido de datos individuales mediante la complejidad de Kolmogorov". Transacciones IEEE sobre teoría de la información . 56 (7): 3438–3454. arXiv : cs / 0411014 . doi : 10.1109 / TIT.2010.2048491 .
- ^ de Rooij, Steven; Vitanyi, Paul (1 de marzo de 2012). "Aproximación de gráficos de tasa-distorsión de datos individuales: experimentos en compresión con pérdida y reducción de ruido". Transacciones IEEE en computadoras . 61 (3): 395–407. arXiv : cs / 0609121 . doi : 10.1109 / TC.2011.25 .
Literatura
- Cover, TM; P. Gacs; RM Gray (1989). "Contribuciones de Kolmogorov a la teoría de la información y la complejidad algorítmica" . Anales de probabilidad . 17 (3): 840–865. doi : 10.1214 / aop / 1176991250 . JSTOR 2244387 .
- Kolmogorov, AN; Uspenskii, VA (1 de enero de 1987). "Algoritmos y aleatoriedad" . Teoría de la probabilidad y sus aplicaciones . 32 (3): 389–412. doi : 10.1137 / 1132060 .
- Li, M., Vitányi, PMB (2008). Una introducción a la complejidad de Kolmogorov y sus aplicaciones (3ª ed.). Nueva York: Springer. ISBN 978-0387339986., Especialmente págs. 401–431 sobre la función de estructura de Kolmogorov, y págs. 613–629 sobre distorsión de frecuencia y eliminación de ruido de secuencias individuales.
- Shen, A. (1 de abril de 1999). "Discusión sobre la complejidad de Kolmogorov y el análisis estadístico". The Computer Journal . 42 (4): 340–342. doi : 10.1093 / comjnl / 42.4.340 .
- V'yugin, VV (1987). "Sobre el defecto de aleatoriedad de un objeto finito relativo a medidas con límites de complejidad dados" . Teoría de la probabilidad y sus aplicaciones . 32 (3): 508–512. doi : 10.1137 / 1132071 .
- V'yugin, VV (1 de abril de 1999). "Complejidad algorítmica y propiedades estocásticas de secuencias binarias finitas". The Computer Journal . 42 (4): 294–317. doi : 10.1093 / comjnl / 42.4.294 .