Approximation de la complexité de Kolmogorov

J'ai étudié quelque chose sur la complexité de Kolmogorov , lu des articles et des livres de Vitanyi et Li et utilisé le concept de la distance de compression normalisée pour vérifier la stilométrie des auteurs (identifier comment chaque auteur écrit des textes et des documents de groupe par leur similitude).

Dans ce cas, des compresseurs de données ont été utilisés pour approximer la complexité de Kolmogorov, car le compresseur de données pouvait être utilisé comme une machine de Turing.

Outre la compression des données et les langages de programmation (dans lesquels vous écririez une sorte de compresseur), quoi d'autre pourrait être utilisé pour approximer la complexité de Kolmogorov? Y a-t-il d'autres approches qui pourraient être utilisées?

Je suppose que d' une réponse possible à votre question est la suivante: Prenez un générateur de nombres pseudo - aléatoires . Essayez de choisir un générateur qui a de puissantes attaques contre lui: une attaque de générateur de nombres aléatoires pour est (pour nos besoins), un algorithme qui, lorsqu'il reçoit une chaîne imputée , détermine une graine , telle que . Ensuite, approximez le 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|

Oùest la longueur du programme qui calcule (souvent assez courte, comme pour les générateurs linéaires).$|G|$$G(s)$

Notez qu'en pratique, les attaques par générateur de nombres aléatoires ne sont pas telles que décrites: elles peuvent échouer ou produire des résultats incomplets. Dans ce cas, vous pouvez adapter l'algorithme pour qu'il renvoielorsque le résultat de l'attaque n'est pas satisfaisant. La même remarque vaut pour les algorithmes de compression.$|s|$

La mise en garde contre cette approche, par opposition aux algorithmes de compression, est que les algorithmes de compression sont en général beaucoup plus adaptés au calcul de KC car ils sont conçus pour fonctionner sur n'importe quelle chaîne, tandis qu'une attaque ne peut fonctionner que si se trouve à l'image de ( très peu probable ).$s$$G$

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

C'est pourquoi la complexité de Kolmogorov est si intéressante, non pas parce que c'est l'algorithme de compression ultime (qui se soucie de la compression de toute façon), mais parce que c'est l' algorithme d' apprentissage ultime . La compression et l'apprentissage sont fondamentalement la même chose: trouver des modèles dans vos données. Le cadre statistique construit sur cette idée est appelé longueur de description minimale, et il a été directement inspiré par la complexité de Kolmogorov.

Voir aussi cette question sur le cstheory StackExchange.

le codage grammatical est une version moins fréquemment utilisée d'un algorithme de compression et peut être considéré comme une estimation "approximative" de la complexité de Kolmogorov. Le codage grammatical n'est pas aussi couramment utilisé comme algorithme de compression que d'autres approches plus courantes, peut-être principalement parce qu'il n'améliore pas beaucoup la compression, par exemple Lempel-Ziv sur les corpus basés sur du texte, mais il peut bien faire sur d'autres types de données. l'idée est de "compresser" une chaîne en utilisant des règles de grammaire. une dérivation de grammaire peut entraîner un DAG (par rapport à un arbre moins complexe) de sorte qu'il existe une complexité de représentation substantielle possible.

une autre option est de trouver les circuits les plus petits / minimaux représentant une chaîne mais cela est connu pour avoir une complexité de calcul très élevée et ne pourrait réussir que sur de petites chaînes.

$K(x)$

$K(x)$

il existe également d'autres méthodes d'algorithme de compression en plus des approches de type "codage de longueur" de Lempel-Ziv, par exemple l'algèbre vectorielle et le SVD peuvent être utilisés comme algorithme de compression. également transformées de Fourier sont fréquemment utilisés pour les images Compresser par exemple en JPG standard.