Variantes efficacement calculables de la complexité de Kolmogorov

La complexité du préfixe de Kolmogorov (c'est-à-dire que est la taille du programme d'auto-délimitation minimal qui génère ) a plusieurs fonctionnalités intéressantes:$K(x)$$x$

1. Cela correspond à une intuition de donner aux chaînes avec des motifs ou une structure une complexité inférieure à celle des chaînes sans.
2. Il nous permet de définir la complexité conditionnelle , ou mieux encore pour un oracle .K ( x | O ) $K(x|y)$$K(x|O)$$O$
3. C'est un sous-additif .$K(x,y) \leq K(x) + K(y)$

Cependant, il a un inconvénient horrible: renvoyer étant donné est indécidable.$K(x)$$x$

Je me suis demandé s'il existait une variante de la complexité Kolmogorov utilisant un modèle de calcul restreint (soit en utilisant des langages plus faibles que les MT, soit en utilisant des ressources limitées liées) qui préserve les caractéristiques (1) et (2) (caractéristique ( 3) est un bonus, mais pas un must) tout en étant efficacement calculable?$K'(x)$

La motivation de cette question est de l'utiliser dans des études de simulation de divers modèles de jouets de l'évolution. Ainsi, une réponse qui a été utilisée comme une «approximation approximative» de la complexité de Kolmogorov dans le travail numérique auparavant est préférée. Cependant, le but n'est pas d'aller complètement expérimental, donc un langage de description / modèle de calcul relativement simple / propre pour est préféré, de sorte qu'il pourrait être possible de prouver quelques théorèmes raisonnables sur la façon dont diffère radicalement de et sur quel type de cordes.K ′$K'$$K'$$K$

Relie les questions

Complexité de Kolmogorov avec des langages de description faibles

Existe-t-il une notion raisonnable d'un algorithme d'approximation pour un problème indécidable?

Gzip. Cilibrasi et Vitanyi ont un très bel article où ils utilisent gzip comme approximation de la complexité de Kolmogorov pour faire des clusters. Regroupement par compression

J'ai réfléchi davantage à ma question et suis parvenu à une solution possible. Il a deux limites, il n'est défini que sur des chaînes de longueur (bien que j'en discuterai plus) et il ne parle pas de machines de Turing universelles, à la place à la suite d'une question précédente et en utilisant un autre modèle de calcul.$n = 2^m$

Fondamentalement, nous pouvons interpréter une chaîne avec en fonction . Ensuite, notre mesure de complexité est la taille (nombre d'arêtes) du diagramme de décision binaire ordonné réduit unique (ROBDD; avec l'ordre standard fixe) représentant . Cela satisfait la condition [1]. De plus, comme les ROBDD peuvent être calculés en polynôme temporel en , nous avons une mesure efficace.$x$$|x| = 2^m$$f_x: \{0,1\}^m \rightarrow \{0,1\}$$K'(x)$$f_x$$2^m$

Pour satisfaire la condition [2], nous devons modifier les BDD standard en autorisant un type spécial sur le nœud. Habituellement, les nœuds sont étiquetés par des index , nous inclurons un nœud oracle spécial. Pour où nous autoriserons des nœuds spéciaux dans les BDD comme suit:$i \in \{1,...,m\}$$K(x|y)$$|y| = 2^m$

Si nous exécutons un BDD sur l'entrée ( ), un nœud normal étiqueté par nous envoie simplement en bas du bord étiqueté . Un nœud oracle nous enverra à la place un bord . Ainsi, et avec une probabilité élevée pour un choisi uniformément au hasard.$a$$|a| = m$$i$$a_i$$f_y(a)$$K'(x|x) = 2$$K'(x|y) \approx K(x)$$y$

[Remarque: il n'est pas clair si la complexité conditionnelle peut encore être calculée efficacement :(]

Par commodité, nous avons également une sous-additivité puisque pour construire un OBDD pour nous pouvons avoir une requête pour le premier bit et sur aller au ROBDD pour et sur pour le ROBDD pour . Ainsi, nous avons .$x.y$$0$$x$$1$$y$$K'(x.y) \leq K'(x) + K'(y)$

Au coût potentiel de la sous-additivité, nous pourrions définir pour n'importe quelle longueur en prenant simplement la puissance de deux morceaux et en additionnant leurs complexités ensemble. Par exemple pour et avec on peut définir .x | x | = 2 m | y | = 2 l m > l K ′ ( x . Y ) = K ′ ( x ) + K ′ ( y $K'(x)$$x$$|x| = 2^m$$|y| = 2^l$$m > l$$K'(x.y) = K'(x) + K'(y)$

Il y a aussi malheureusement quelques limites à mon approche. Nous ne pouvons pas aller bien au-delà des OBDD, si nous considérons des arbres de décision minimaux ou simplement des BDD, nous nous accrocherons aux problèmes d'intraçabilité abordés dans cette réponse . Même pour l'ordre variable des OBDD, il semble y avoir des résultats d'intractabilité . Il semble donc que les OBDD constituent la limite de cette approche de complexité de Kolmogorov pas si similaire.

Je ne suis pas un expert, mais si vous avez besoin d'une mesure de complexité pratique pour les chaînes, vous pouvez jeter un œil à la mesure de complexité T de Titchener .

Voir le site Web de Titchener pour une introduction rapide; ses articles peuvent être téléchargés au format pdf .

Résumé - Une nouvelle mesure de la complexité des chaînes pour les chaînes finies est présentée sur la base d'un processus de production de chaînes hiérarchique récursif spécifique . De la limite maximale, nous déduisons une relation entre la complexité et le contenu total de l'information. ..article complet ...

J'ai aussi trouvé des articles sur des implémentations pratiques (voir par exemple " Un algorithme de décomposition en T rapide ")

Fondamentalement, presque toutes les méthodes d'apprentissage automatique ou de compression sont une approximation de la complexité de Kolmogorov:

• $p(x)$$- \log p(x)$
• $n$$K(x) \leq n + s_C$$s_C$$x$

Ainsi, vous pouvez simplement rechercher des modèles avec n'importe quel compresseur ou distribution de probabilité et mieux ils compressent vos données, meilleure est votre limite supérieure pour K (x). Assurez-vous simplement d'ajouter la taille du compresseur lui-même à la taille des données compressées pour obtenir l'estimation.

$K(x)$

$K(x)$$K$

Vous pouvez également utiliser un temps limité pour définir votre classe de modèle, ce qui vous amène à la réponse de Suresh. Fondamentalement, si vous supposez que votre source de données a une complexité temporelle polynomiale et que vous essayez toutes les machines de Turing polynomiales pour la compresser, vous pouvez être sûr que vous avez correctement estimé la complexité de Kolmogorov. Ce n'est peut-être pas encore aussi pratique, mais pour des limites de temps inférieures, vous pourrez peut-être calculer le mélange bayésien complet, d'une bonne approximation.

Pour les détails techniques, voir ce document . Avertissement: je suis l'un des auteurs.

$K(x)$$K(x)$

Vous recherchez la complexité de Kolmogorov limitée par les ressources. Vous pouvez commencer avec ce document et vous diversifier.