Función de estructura de Kolmogorov

Función estadística

En 1973, Andrey Kolmogorov propuso un enfoque no probabilístico para 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 clases de modelos que constan de modelos de complejidad máxima de Kolmogorov dada . La función de estructura 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 cardinalidad logarítmica mínima de un modelo en la clase que contiene los datos. La función de estructura determina todas las propiedades estocásticas de la cadena de datos individual: para cada clase de modelo restringida determina el modelo individual que mejor se ajusta 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 una distribución de probabilidad, y las propiedades son las de las expectativas. Por el contrario, aquí nos ocupamos de cadenas de datos individuales y de las propiedades de la cadena individual en la que nos centramos. En este contexto, una propiedad se cumple con certeza y no 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 datos individuales.

La función de estructura de Kolmogorov se utiliza en la teoría algorítmica de la información , también conocida como teoría de la complejidad de Kolmogorov, para describir la estructura de una cadena mediante el uso de modelos de complejidad creciente.

La definición de Kolmogorov.

Kolmogorov (izquierda) habla sobre la función estructura (ver dibujo en la pizarra) en ( Tallin , 1973).

La función 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 del propio Kolmogorov. Una de sus últimas declaraciones científicas es (traducida del original ruso por LA Levin):

A cada objeto constructivo corresponde una función de un número natural k: el registro de cardinalidad mínima de conjuntos que contienen x y que permiten definiciones de complejidad como máximo k. Si el propio elemento x permite una definición simple, entonces la función cae a 0 incluso para k pequeña. A falta de tal definición, el elemento es "aleatorio" en un sentido negativo. Pero es positivamente "probabilísticamente aleatorio" sólo cuando la función ha tomado el valor en un valor relativamente pequeño y luego cambia aproximadamente como . ${\displaystyle \Phi _{x}(k)}$ ${\displaystyle \Phi }$ ${\displaystyle \Phi }$ ${\displaystyle \Phi _{0}}$ ${\displaystyle k=k_{0}}$ ${\displaystyle \Phi (k)=\Phi _{0}-(k-k_{0})}$

—  Kolmogorov , anuncio citado anteriormente

Definición contemporánea

Se analiza en Cover y Thomas. ^[1] Se estudia ampliamente 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

${\displaystyle h_{x}(\alpha )=\min _{S}\{\log |S|:x\in S,K(S)\leq \alpha \}}$

donde es una cadena binaria de longitud con donde es un modelo contemplado (conjunto de cadenas de n longitudes) para , es la complejidad de Kolmogorov y es un valor entero no negativo que limita la complejidad de lo contemplado . Claramente, esta función no es creciente y alcanza dónde está el número requerido de bits para cambiar y es la complejidad de Kolmogorov . ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle x\in S}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle K(S)}$ ${\displaystyle S}$ ${\displaystyle \alpha }$ ${\displaystyle S}$ ${\displaystyle \log |\{x\}|=0}$ ${\displaystyle \alpha =K(x)+c}$ ${\displaystyle c}$ ${\displaystyle x}$ ${\displaystyle \{x\}}$ ${\displaystyle K(x)}$ ${\displaystyle x}$

La estadística algorítmica suficiente

Definimos un conjunto que contiene tal que ${\displaystyle S}$ ${\displaystyle x}$

${\displaystyle K(S)+K(x|S)=K(x)+O(1)}$.

La función nunca disminuye más que una constante independiente fija debajo de la diagonal llamada línea de suficiencia L definida por ${\displaystyle h_{x}(\alpha )}$

${\displaystyle L(\alpha )+\alpha =K(x)}$.

Se aproxima a él dentro de una distancia constante mediante la gráfica de para ciertos argumentos (por ejemplo, para ). Para estos tenemos y el modelo asociado (testigo de ) se llama conjunto óptimo de , y su descripción de bits es, por lo tanto, una estadística algorítmica suficiente . Escribimos "algorítmico" para la "complejidad de Kolmogorov" por convención. Las principales propiedades de un estadístico algorítmico suficiente son las siguientes: Si es un estadístico algorítmico suficiente para , entonces ${\displaystyle h_{x}}$ ${\displaystyle \alpha =K(x)+c}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha +h_{x}(\alpha )=K(x)+O(1)}$ ${\displaystyle S}$ ${\displaystyle h_{x}(\alpha )}$ ${\displaystyle x}$ ${\displaystyle K(S)\leq \alpha }$ ${\displaystyle S}$ ${\displaystyle x}$

${\displaystyle K(S)+\log |S|=K(x)+O(1)}$.

Es decir, la descripción de dos partes del uso del modelo y, como código de datos a modelo, el índice de en la enumeración de bits , es tan concisa como el código de una parte más corto de bits . Esto se puede ver fácilmente de la siguiente manera: ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle \log |S|}$ ${\displaystyle x}$ ${\displaystyle K(x)}$

${\displaystyle K(x)\leq K(x,S)+O(1)\leq K(S)+K(x|S)+O(1)\leq K(S)+\log |S|+O(1)\leq K(x)+O(1)}$,

Funciones de estructura y estadística mínima suficiente. ${\displaystyle h_{x}(\alpha ),\beta _{x}(\alpha ),\lambda _{x}(\alpha )}$

utilizando desigualdades sencillas y la propiedad de suficiencia, encontramos que . (Por ejemplo, dado , podemos describirlo de forma autodelimitante (puede determinar su final) en bits). Por lo tanto, la deficiencia de aleatoriedad de in es una constante, lo que significa que es un elemento típico (aleatorio) de S. Sin embargo, hay Pueden ser modelos que contengan estadísticas que no sean suficientes. Un estadístico algorítmico suficiente para tiene la propiedad adicional, además de ser un modelo de mejor ajuste, de que y por lo tanto por la simetría de complejidad de la información de Kolmogorov (la información sobre in es aproximadamente la misma que la información sobre in x) tenemos : el estadístico algorítmico suficiente para estadística suficiente es un modelo de mejor ajuste que está casi completamente determinado por . ( es el programa más corto para ). La estadística algorítmica suficiente asociada con el menor número de ellos se denomina estadística algorítmica mínima suficiente . ${\displaystyle K(x|S)=\log |S|+O(1)}$ ${\displaystyle S\ni x}$ ${\displaystyle x}$ ${\displaystyle \log |S|+O(1)}$ ${\displaystyle \log |S|-K(x|S)}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle K(x,S)=K(x)+O(1)}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle K(S|x^{*})=O(1)}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle x^{*}}$ ${\displaystyle x}$ ${\displaystyle \alpha }$

Con respecto a la imagen: La función de la 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 para tal que . Esta función de estructura proporciona la bondad de ajuste de un modelo (que contiene x) para la cadena x. Cuando es bajo el modelo ajusta bien, y cuando es alto el modelo no ajusta bien. Si para algunos entonces existe un modelo típico para tal que y es típico (aleatorio) para S. Es decir, es el modelo que mejor se ajusta para x. Para más detalles ver ^[1] y especialmente ^[3] y. ^[4] ${\displaystyle \lambda _{x}(\alpha )}$ ${\displaystyle \beta _{x}(\alpha )}$ ${\displaystyle S\ni x}$ ${\displaystyle x}$ ${\displaystyle K(S)\leq \alpha }$ ${\displaystyle S}$ ${\displaystyle \beta _{x}(\alpha )=0}$ ${\displaystyle \alpha }$ ${\displaystyle S\ni x}$ ${\displaystyle x}$ ${\displaystyle K(S)\leq \alpha }$ ${\displaystyle x}$ ${\displaystyle S}$

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 n y 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 llega primero a la diagonal, el argumento (complejidad) es el del estadístico mínimo suficiente. Es incomputable determinar este lugar. Ver. ^[3] ${\displaystyle K(x)}$ ${\displaystyle O(\log n)}$

Propiedad principal

Está demostrado 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 franja de con certeza, no con gran probabilidad. ^[3] ${\displaystyle \alpha }$ ${\displaystyle S}$ ${\displaystyle O(\log n)}$

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 consta del 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 La complejidad , la complejidad de S acotada superiormente por , está dada por la función MDL o estimador MDL restringido: ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

${\displaystyle \lambda _{x}(\alpha )=\min _{S}\{\Lambda (S):S\ni x,\;K(S)\leq \alpha \},}$

donde es la longitud total del código de dos partes de x con ayuda del modelo S. ${\displaystyle \Lambda (S)=\log |S|+K(S)\geq K(x)-O(1)}$

Propiedad principal

Está demostrado que en cada nivel de complejidad la función de estructura nos permite seleccionar el mejor modelo S para la cadena individual x dentro de una franja de con certeza, no con gran probabilidad. ^[3] ${\displaystyle \alpha }$ ${\displaystyle O(\log n)}$

Aplicación en estadística

Las matemáticas desarrolladas anteriormente fueron tomadas como base de MDL por su inventor Jorma Rissanen . ^[5]

Modelos de probabilidad

Para cada distribución de probabilidad computable se puede demostrar ^[6] que ${\displaystyle P}$

${\displaystyle -\log P(x)=\log |S|+O(\log n)}$.

Por ejemplo, si hay alguna distribución computable en el conjunto de cadenas de longitud , entonces cada una tiene probabilidad . La función estructural de Kolmogorov se convierte en ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle x\in S}$ ${\displaystyle P(x)=\exp(O(\log n))/|S|=n^{O(1)}/|S|}$

${\displaystyle h'_{x}(\alpha )=\min _{P}\{-\log P(x):P(x)>0,K(P)\leq \alpha \}}$

donde x es una cadena binaria de longitud n con donde es un modelo contemplado (probabilidad computable de cadenas de longitud) para , es la complejidad de Kolmogorov y es un valor entero que limita la complejidad de las cadenas contempladas. Claramente, esta función no es creciente y alcanza donde c es el número requerido de bits para cambiar y es la complejidad de Kolmogorov . Entonces . Para cada nivel de complejidad, la función es la versión de complejidad de Kolmogorov de la máxima verosimilitud (ML). ${\displaystyle -\log P(x)>0}$ ${\displaystyle P}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle K(P)}$ ${\displaystyle P}$ ${\displaystyle \alpha }$ ${\displaystyle P}$ ${\displaystyle \log |\{x\}|=0}$ ${\displaystyle \alpha =K(x)+c}$ ${\displaystyle x}$ ${\displaystyle \{x\}}$ ${\displaystyle K(x)}$ ${\displaystyle x}$ ${\displaystyle h'_{x}(\alpha )=h_{x}(\alpha )+O(\log n)}$ ${\displaystyle \alpha }$ ${\displaystyle h'_{x}(\alpha )}$

Propiedad principal

Está demostrado que en cada nivel de complejidad la función de estructura nos permite seleccionar el mejor modelo para la cadena individual dentro de una franja de con certeza, no con gran probabilidad. ^[3] ${\displaystyle \alpha }$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle O(\log n)}$

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 consta del 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 de Kolmogorov dada , la complejidad de P con límite superior por , viene dado por la función MDL o estimador MDL restringido: ${\displaystyle -\log P(x)}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

${\displaystyle \lambda '_{x}(\alpha )=\min _{P}\{\Lambda (P):P(x)>0,\;K(P)\leq \alpha \},}$

donde es la longitud total del código de dos partes de x con la ayuda del modelo P. ${\displaystyle \Lambda (P)=-\log P(x)+K(P)\geq K(x)-O(1)}$

Propiedad principal

Está demostrado que en cada nivel de complejidad la función MDL nos permite seleccionar el mejor modelo P para la cadena individual x dentro de una franja de con certeza, no con gran probabilidad. ^[3] ${\displaystyle \alpha }$ ${\displaystyle O(\log n)}$

Ampliación para calificar la distorsión y la eliminación de ruido.

Resulta que el enfoque puede extenderse a una teoría de distorsión de velocidad de secuencias finitas individuales y eliminación de ruido de secuencias finitas individuales ^[7] utilizando la complejidad de Kolmogorov. Se han llevado a cabo con éxito experimentos utilizando programas de compresores reales. ^[8] Aquí se supone 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

1. Portada abc, Thomas M.; Thomas, alegría A. (1991). Elementos de la teoría de la información . Nueva York: Wiley. págs. 175-178. ISBN 978-0471062592.
2. Resumen de una charla para la Sociedad Matemática de Moscú en Uspekhi Mat. Nauk Volumen 29, Número 4 (178) en Comunicaciones de la Sociedad Matemática de Moscú, página 155 (en la edición rusa, no traducida al inglés)
3. Vereshchagin, NK; Vitanyi, PMB (1 de diciembre de 2004). "Selección de modelos y funciones estructurales de Kolmogorov". Transacciones IEEE sobre teoría de la información . 50 (12): 3265–3290. arXiv : cs/0204037 . doi :10.1109/TIT.2004.838346.
4. 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.
5. Rissanen, Jorma (2007). Información y complejidad en el modelado estadístico (Online-Ausg. ed.). Nueva York: Springer. ISBN 978-0-387-36610-4.
6. 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
7. Vereshchagin, Nikolai K.; Vitanyi, Paul MB (1 de julio de 2010). "Distorsión de velocidad y eliminación de ruido de datos individuales utilizando 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.
8. de Rooij, Steven; Vitanyi, Paul (1 de marzo de 2012). "Aproximación de gráficos de velocidad-distorsión de datos individuales: experimentos de compresión y eliminación de ruido con pérdidas". Transacciones IEEE en computadoras . 61 (3): 395–407. arXiv : cs/0609121 . doi :10.1109/TC.2011.25.

Literatura

• Portada, TM; P. Gacs; RM Gris (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.{{cite book}}: CS1 maint: multiple names: authors list (link), Especialmente las págs. 401–431 sobre la función de estructura de Kolmogorov, y las págs. 613–629 sobre la distorsión de velocidad y la eliminación de ruido de secuencias individuales.
• Shen, A. (1 de abril de 1999). "Discusión sobre la complejidad y el análisis estadístico de Kolmogorov". La revista informática . 42 (4): 340–342. doi :10.1093/comjnl/42.4.340.
• V'yugin, VV (1987). "Sobre el defecto de aleatoriedad de un objeto finito en relación con 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". La revista informática . 42 (4): 294–317. doi : 10.1093/comjnl/42.4.294.