Aproximando la complejidad de Kolmogorov

22

He estudiado algo sobre la complejidad de Kolmogorov , leí algunos artículos y libros de Vitanyi y Li y usé el concepto de Distancia de compresión normalizada para verificar la estilometría de los autores (identifique cómo cada autor escribe algunos textos y documentos grupales por su similitud).

En ese caso, se usaron compresores de datos para aproximar la complejidad de Kolmogorov, ya que el compresor de datos podría usarse como una máquina de Turing.

Además de la compresión de datos y los lenguajes de programación (en los que escribirías algún tipo de compresor), ¿qué más se podría usar para aproximar la complejidad de Kolmogorov? ¿Hay otros enfoques que podrían usarse?

computability approximation data-compression kolmogorov-complexity woliveirajr
fuente

No estoy seguro de entender su pregunta: la definición de KC implica máquinas de turing, de los cuales los programas forman ejemplos (con respecto a alguna traducción). ¿Qué significa aproximar la complejidad de Kolmogorv "sin lenguajes de programación"?

cody

1

Comprima una cadena con cualquier software de compresión, como GZip. El tamaño de la salida es un límite superior al KC de la cadena.

M. Alaggan

@cody: exactamente, he usado compresores de datos en mi investigación (zip, bzip, ppmd) para aproximar KC. El compresor de datos no son, exactamente, programas ... Por lo tanto, estoy buscando sugerencias sobre lo que podría usarse en KC además de lenguajes (= escribir un programa en C / prolog / lo que sea) y compresores de datos (= usar zip, gzip, ppmc, ppmd ...) :)

woliveirajr

1

Supongo que me parece que la definición de un programa de compresión de datos es exactamente: un programa que se aproxima al KC de una cadena por un programa (el "descompresor") y otra cadena (la cadena comprimida).

cody

9

Creo que una posible respuesta a su pregunta es la siguiente: Tome un generador de números pseudo- . Intente elegir un generador que tenga algunos ataques poderosos contra él: un ataque de generador de números aleatorios para es (para nuestros propósitos), un algoritmo que, cuando se le da una cadena de entrada , determina una semilla , tal que . Luego aproxima el KC de : $G$ $G$ $A$ $s$ $A(s)$ $G(A(s))=s$ $s$

input: s
Compute A(s);
if |A(s)| + |G| > |s| output: |s|
otherwise output: |A(s)| + |G|

Donde es la duración del programa que calcula (a menudo bastante corto, como para generadores lineales). $|G|$ $G(s)$

Tenga en cuenta que en la práctica, los ataques de generador de números aleatorios no son como se describen: pueden fallar o producir resultados incompletos. En ese caso, puede adaptar el algoritmo para que devuelva cuando el resultado del ataque no es satisfactorio. El mismo comentario se aplica a los algoritmos de compresión. $|s|$

La advertencia a este enfoque en comparación con los algoritmos de compresión es que los algoritmos de compresión son en general mucho más adecuados para calcular KC, ya que están diseñados para funcionar en cualquier cadena, mientras que un ataque solo puede funcionar si está en la imagen de ( muy improbable ) $s$ $G$

cody
fuente

7

$p(x)$ $-\log p(x)$

Esta es la razón por la cual la complejidad de Kolmogorov es tan interesante, no porque sea el último algoritmo de compresión (a quien le importa la compresión de todos modos), sino porque es el último algoritmo de aprendizaje . La compresión y el aprendizaje son básicamente lo mismo: encontrar patrones en sus datos. El marco estadístico construido sobre esta idea se llama Longitud mínima de descripción, y se inspiró directamente en la complejidad de Kolmogorov.

Vea también esta pregunta en el cstheory StackExchange.

Peter
fuente

5

La codificación gramatical es una versión menos utilizada de un algoritmo de compresión y puede tomarse como una estimación "aproximada" de la complejidad de Kolmogorov. La codificación gramatical no se usa tan comúnmente como un algoritmo de compresión como otros enfoques más comunes, tal vez principalmente porque no mejora mucho la compresión de, por ejemplo, Lempel-Ziv en corpus basados en texto, pero puede funcionar bien en otros tipos de datos. la idea es "comprimir" una cadena usando reglas gramaticales. una derivación gramatical puede dar como resultado un DAG (frente a un árbol menos complejo), por lo que es posible una complejidad representativa sustancial.

otra opción es encontrar circuitos más pequeños / mínimos que representen una cadena, pero se sabe que tiene una complejidad de cálculo muy alta y que solo puede tener éxito en cadenas pequeñas.

$K(x)$

También hay otros métodos de algoritmos de compresión además de los enfoques de tipo "codificación de longitud de ejecución" de Lempel-Ziv, por ejemplo, el álgebra vectorial y la SVD se pueden usar como algoritmo de compresión. También las transformadas de Fourier se utilizan con frecuencia para comprimir imágenes, por ejemplo, en el estándar JPG.

vzn
fuente

1

K (x)

$K(x)$

Sin embargo, los algoritmos con pérdida suelen tener un parámetro ajustable que determina la "pérdida" y, en teoría, pueden lograr la pérdida con suficientes "términos" o "frecuencias", por así decirlo, y también depende de las muestras de entrada, de modo que el valor del parámetro sin pérdida dependerá en su "orden relativo versus aleatoriedad" visto a través de la "lente" del algoritmo de compresión ...

vzn

1

@cody y vzn: Gracias por la respuesta, me diste algunas buenas ideas para mi doctorado sobre compresión sin pérdida x con pérdida :)

woliveirajr

JPEG usa DCT, no DFT.

Mal

Aproximando la complejidad de Kolmogorov

Respuestas: