función de estructura de Kolmogorov

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 un conjunto finito de cadenas binarias. Consideremos clases de modelos que consisten en modelos con una complejidad de Kolmogorov máxima dada . 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 modelos 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 a la clase, independientemente de si el modelo verdadero está en la clase de modelos 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 esperanzas. En cambio, aquí tratamos con cadenas de datos individuales y las propiedades de la cadena individual en la que nos centramos. En este contexto, una propiedad se cumple 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 teoría de la complejidad de Kolmogorov, para describir la estructura de una cadena mediante el uso de modelos de complejidad creciente.

La función de estructura fue propuesta originalmente por Kolmogorov en 1973 en un simposio soviético de Teoría de la Información en Tallin, pero estos resultados no fueron publicados ^{[ 1 ]} pág.  182. Sin embargo, los resultados fueron anunciados 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 L.A. Levin):

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

Se discute en Cover y Thomas. ^{[ 1 ]} Se estudia extensamente en Vereshchagin y Vitányi ^{[ 3 ]} donde también se resuelven las propiedades principales. 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 \}}$$ dónde${\displaystyle x}$es una cadena binaria de longitud${\displaystyle n}$con${\displaystyle x\in S}$dónde${\displaystyle S}$ es un modelo contemplado (conjunto de cadenas de longitud n) para${\displaystyle x}$,${\displaystyle K(S)}$es la complejidad de Kolmogorov de${\displaystyle S}$y${\displaystyle \alpha }$ es un valor entero no negativo que limita la complejidad de lo contemplado.${\displaystyle S}$'s. Claramente, esta función no es creciente y alcanza${\displaystyle \log \left|\{x\}\right|=0}$para${\displaystyle \alpha =K(x)+c}$dónde${\displaystyle c}$es el número de bits necesarios para cambiar${\displaystyle x}$en${\displaystyle \{x\}}$y${\displaystyle K(x)}$es la complejidad de Kolmogorov de${\displaystyle x}$.

La estadística suficiente algorítmica

Definimos un conjunto${\displaystyle S}$que contiene${\displaystyle x}$de tal manera que $${\displaystyle K(S)+K(x|S)=K(x)+O(1).}$$ La función${\displaystyle h_{x}(\alpha )}$nunca disminuye más que una constante independiente fija por debajo de la diagonal llamada línea de suficiencia L definida por $${\displaystyle L(\alpha )+\alpha =K(x).}$$ Se aproxima a una distancia constante mediante la gráfica de${\displaystyle h_{x}}$por ciertos argumentos (por ejemplo, para${\displaystyle \alpha =K(x)+c}$). Para estos${\displaystyle \alpha }$tenemos${\displaystyle \alpha +h_{x}(\alpha )=K(x)+O(1)}$y el modelo asociado${\displaystyle S}$(testigo de${\displaystyle h_{x}(\alpha )}$) se denomina un conjunto óptimo para${\displaystyle x}$y su descripción de${\displaystyle K(S)\leq \alpha }$bits es, por lo tanto, una estadística suficiente algorítmica . Por convención, escribimos «algorítmica» en lugar de «complejidad de Kolmogorov». Las principales propiedades de una estadística suficiente algorítmica son las siguientes: Si${\displaystyle S}$es una estadística suficiente algorítmica para${\displaystyle x}$, entonces $${\displaystyle K(S)+\log |S|=K(x)+O(1).}$$ Es decir, la descripción en dos partes de${\displaystyle x}$utilizando el modelo${\displaystyle S}$y como código de datos a modelo el índice de${\displaystyle x}$en la enumeración de${\displaystyle S}$en${\displaystyle \log |S|}$bits, es tan conciso como el código de una parte más corto de${\displaystyle x}$en${\displaystyle K(x)}$bits. Esto se puede ver fácilmente de la siguiente manera: $${\displaystyle {\begin{aligned}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),\end{aligned}}}$$

Utilizando desigualdades sencillas y la propiedad de suficiencia, encontramos que${\displaystyle K(x|S)=\log |S|+O(1)}$. (Por ejemplo, dado${\displaystyle S\ni x}$, podemos describir${\displaystyle x}$autolimitante (puedes determinar su final) en${\displaystyle \log |S|+O(1)}$bits.) Por lo tanto, la deficiencia de aleatoriedad${\displaystyle \log |S|-K(x|S)}$de${\displaystyle x}$en${\displaystyle S}$es una constante, lo que significa que${\displaystyle x}$es un elemento típico (aleatorio) de S. Sin embargo, puede haber modelos${\displaystyle S}$que contiene${\displaystyle x}$que no son estadísticas suficientes. Una estadística suficiente algorítmica${\displaystyle S}$para${\displaystyle x}$tiene la propiedad adicional, aparte de ser un modelo de mejor ajuste, de que${\displaystyle K(x,S)=K(x)+O(1)}$y por lo tanto por la simetría de complejidad de Kolmogorov de la información (la información sobre${\displaystyle x}$en${\displaystyle S}$es aproximadamente lo mismo que la información sobre${\displaystyle S}$en x) tenemos${\displaystyle K(S|x^{*})=O(1)}$: la estadística suficiente algorítmica${\displaystyle S}$es un modelo de mejor ajuste que está casi completamente determinado por${\displaystyle x}$. (${\displaystyle x^{*}}$es el programa más corto para${\displaystyle x}$.) La estadística suficiente algorítmica asociada con el menor de tales${\displaystyle \alpha }$se denomina estadística mínima suficiente algorítmica .

Con respecto a la imagen: La función de estructura MDL${\displaystyle \lambda _{x}(\alpha )}$Se explica a continuación. La función de estructura de bondad de ajuste${\displaystyle \beta _{x}(\alpha )}$es la menor deficiencia de aleatoriedad (ver arriba) de cualquier modelo${\displaystyle S\ni x}$para${\displaystyle x}$de tal manera que${\displaystyle K(S)\leq \alpha }$Esta función de estructura proporciona la bondad de ajuste de un modelo.${\displaystyle S}$(que contiene x) para la cadena x. Cuando es bajo, el modelo se ajusta bien, y cuando es alto, el modelo no se ajusta bien. Si${\displaystyle \beta _{x}(\alpha )=0}$para algunos${\displaystyle \alpha }$Entonces existe un modelo típico.${\displaystyle S\ni x}$para${\displaystyle x}$de tal manera que${\displaystyle K(S)\leq \alpha }$y${\displaystyle x}$es típico (aleatorio) para S. Es decir,${\displaystyle S}$es el modelo que mejor se ajusta a x. Para más detalles, consulte ^{[ 1 ]} y especialmente ^{[ 3 ]} y ^{[ 4 ] .}

La función de longitud de descripción mínima (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 modelos de conjuntos de complejidad de Kolmogorov máxima dada${\displaystyle \alpha }$, la complejidad de S está limitada superiormente por${\displaystyle \alpha }$, viene dado por la función MDL o el estimador MDL restringido:

$${\displaystyle \lambda _{x}(\alpha )=\min _{S}\{\Lambda (S):S\ni x,\;K(S)\leq \alpha \},}$$ dónde${\displaystyle \Lambda (S)=\log |S|+K(S)\geq K(x)-O(1)}$es la longitud total del código de dos partes de x con la ayuda del modelo S.

Para cada distribución de probabilidad computable${\displaystyle P}$Se puede demostrar ^{[ 6 ]} que $${\displaystyle -\log P(x)=\log |S|+O(\log n).}$$ Por ejemplo, si${\displaystyle P}$es alguna distribución computable en el conjunto${\displaystyle S}$de cadenas de longitud${\displaystyle n}$, luego cada uno${\displaystyle x\in S}$tiene probabilidad${\displaystyle P(x)=\exp(O(\log n))/|S|=n^{O(1)}/|S|}$La función de estructura de Kolmogorov se convierte en $${\displaystyle h'_{x}(\alpha )=\min _{P}\left\{-\log P(x):P(x)>0,K(P)\leq \alpha \right\}}$$ donde x es una cadena binaria de longitud n con${\displaystyle -\log P(x)>0}$dónde${\displaystyle P}$ es un modelo contemplado (probabilidad computable de${\displaystyle n}$-cadenas de longitud) para${\displaystyle x}$,${\displaystyle K(P)}$es la complejidad de Kolmogorov de${\displaystyle P}$y${\displaystyle \alpha }$ es un valor entero que delimita la complejidad de lo contemplado.${\displaystyle P}$'s. Claramente, esta función no es creciente y alcanza${\displaystyle \log |\{x\}|=0}$para${\displaystyle \alpha =K(x)+c}$donde c es el número de bits necesarios para cambiar${\displaystyle x}$en${\displaystyle \{x\}}$y${\displaystyle K(x)}$es la complejidad de Kolmogorov de${\displaystyle x}$. Entonces${\displaystyle h'_{x}(\alpha )=h_{x}(\alpha )+O(\log n)}$Para cada nivel de complejidad${\displaystyle \alpha }$la función${\displaystyle h'_{x}(\alpha )}$ es la versión de complejidad de Kolmogorov de la máxima verosimilitud (ML).

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${\displaystyle -\log P(x)}$, en la clase modelo de funciones de masa de probabilidad computables de complejidad de Kolmogorov máxima dada${\displaystyle \alpha }$, la complejidad de P está limitada superiormente por${\displaystyle \alpha }$, viene dado por la función MDL o el estimador MDL restringido:

$${\displaystyle \lambda '_{x}(\alpha )=\min _{P}\{\Lambda (P):P(x)>0,\;K(P)\leq \alpha \},}$$ dónde${\displaystyle \Lambda (P)=-\log P(x)+K(P)\geq K(x)-O(1)}$es la longitud total del código de dos partes de x con la ayuda del modelo P.

Resulta que el enfoque puede extenderse a una teoría de distorsión de tasa de secuencias finitas individuales y eliminación de ruido de secuencias finitas individuales ^{[ 7 ]} utilizando la complejidad de Kolmogorov. Se han realizado experimentos con éxito utilizando programas 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 utilizando un buen compresor.