Effizient berechenbare Varianten der Kolmogorov-Komplexität

Die Komplexität des Kolmogorov-Präfixes (dh ist die Größe des minimalen selbstbegrenzenden Programms, das ausgibt ) weist mehrere nette Merkmale auf:$K(x)$$x$

1. Es entspricht einer Intuition, Strings mit Mustern oder Strukturen eine geringere Komplexität zu geben als Strings ohne.
2. Es erlaubt uns, die bedingte Komplexität oder besser für ein Orakel .$K(x|y)$$K(x|O)$$O$
3. Es ist Subadditiv .$K(x,y) \leq K(x) + K(y)$

Es hat jedoch einen schrecklichen Nachteil: Die Rückgabe von mit ist nicht zu entscheiden.$K(x)$$x$

Ich habe mich gefragt, ob es eine Variante der Kolmogorov-Komplexität , die ein eingeschränktes Berechnungsmodell verwendet (entweder durch Verwendung von schwächeren Sprachen als TMs oder durch Verwendung von begrenztem TM mit Ressourcen), bei dem die Merkmale (1) und (2) erhalten bleiben (Merkmal ( 3) Ist ein Bonus, aber kein Muss, während es effizient berechenbar ist?$K'(x)$

Die Motivation für diese Frage ist die Verwendung in Simulationsstudien verschiedener Spielzeugmodelle der Evolution. Daher wird eine Antwort bevorzugt, die als "grobe Näherung" für die Kolmogorov-Komplexität in numerischen Arbeiten verwendet wurde. Das Ziel ist jedoch nicht, vollständig experimentell vorzugehen. Daher wird eine relativ einfache / übersichtliche Beschreibungssprache / Berechnungsmodell für bevorzugt, damit möglicherweise einige vernünftige Sätze darüber bewiesen werden können, wie drastisch sich von unterscheidet und auf welche Art von Saiten.K '$K'$$K'$$K$

Bezieht sich auf Fragen

Kolmogorov-Komplexität mit schwachen Beschreibungssprachen

Gibt es eine vernünftige Vorstellung eines Näherungsalgorithmus für ein unentscheidbares Problem?

Gzip. Cilibrasi und Vitanyi haben einen wirklich schönen Artikel, in dem sie gzip als Annäherung an die Kolmogorov-Komplexität für das Clustering verwenden. Clustering durch Komprimierung

Ich dachte mehr über meine Frage nach und kam zu einer möglichen Lösung. Es gibt zwei Einschränkungen: Es ist nur für Zeichenfolgen mit einer Länge von (ich werde dies jedoch noch näher erläutern), und es handelt nicht von universellen Turing-Maschinen. Stattdessen wird einer vorherigen Frage gefolgt und ein alternatives Berechnungsmodell verwendet.$n = 2^m$

Grundsätzlich können wir einen String mit | interpretieren x | = 2 m als Funktion f x : { 0 , 1 } m → { 0 , 1 } . Dann ist unser Komplexitätsmaß K ' ( x ) die Größe (Anzahl der Kanten) des eindeutigen Binärentscheidungsdiagramms mit reduzierter Ordnung (ROBDD; mit fester Standardordnung), das f x darstellt . Dies erfüllt die Bedingung [1]. Da ROBDDs auch in 2 m Zeitpolynom berechnet werden können$x$$|x| = 2^m$$f_x: \{0,1\}^m \rightarrow \{0,1\}$$K'(x)$$f_x$$2^m$Wir haben eine effiziente Maßnahme.

Um die Bedingung [2] zu erfüllen, müssen wir Standard-BDDs ändern, indem wir einen speziellen Typ für den Knoten zulassen. Normalerweise sind Knoten , die durch Indizes gekennzeichnet , wir werden einen speziellen Orakelknoten einfügen. Für K ( x | y ) wo | y | = 2 m erlauben wir spezielle Knoten in den BDDs wie folgt:$i \in \{1,...,m\}$$K(x|y)$$|y| = 2^m$

Wenn wir eine BDD am Eingang ( | a | = m ) ausführen, sendet uns ein normaler Knoten mit der Bezeichnung i einfach die Kante mit der Bezeichnung a i hinunter . Ein Orakelknoten sendet uns stattdessen eine Kante mit der Bezeichnung f y ( a ) hinunter . Somit ist K ' ( x | x ) = 2 und mit hoher Wahrscheinlichkeit wird K ' ( x | y ) ≤ K ( x ) für ein y gleichmäßig zufällig ausgewählt.$a$$|a| = m$$i$$a_i$$f_y(a)$$K'(x|x) = 2$$K'(x|y) \approx K(x)$$y$

[Anmerkung: Es ist nicht klar, ob die bedingte Komplexität noch effizient berechnet werden kann :(]

Praktischerweise haben wir auch Subadditivität, um eine OBDD für zu erstellen . y wir können eine Abfrage für das erste Bit haben und bei 0 zum ROBDD für x und bei 1 zum ROBDD für y gehen . Somit haben wir K ' ( x . Y ) ≤ K ' ( x ) + K ' ( y ) .$x.y$$0$$x$$1$$y$$K'(x.y) \leq K'(x) + K'(y)$

Zu den potenziellen Kosten der Subadditivität können wir für jede Länge x definieren, indem wir nur Zweierpotenzen nehmen und ihre Komplexität addieren. Zum Beispiel für | x | = 2 m und | y | = 2 l mit m > l können wir K ' ( x . Y ) = K ' ( x ) + K ' ( y ) definieren .$K'(x)$$x$$|x| = 2^m$$|y| = 2^l$$m > l$$K'(x.y) = K'(x) + K'(y)$

Es gibt leider auch einige Einschränkungen bei meinem Ansatz. Wir können nicht viel über OBDDs hinausgehen. Wenn wir minimale Entscheidungsbäume oder nur BDDs berücksichtigen, werden wir uns mit den in dieser Antwort angesprochenen Problemen der Unlösbarkeit befassen . Sogar für die variable Ordnung von OBDDs scheint es Ergebnisse der Unlösbarkeit zu geben . Es scheint also, dass OBDDs die Grenze dieses nicht ganz standardähnlichen Kolmogorov-Komplexitätsansatzes sind.

Ich bin kein Experte, aber wenn Sie ein praktisches Maß für die Komplexität von Saiten benötigen , schauen Sie sich das Maß für die T-Komplexität von Titchener an .

Siehe Titcheners Website für eine schnelle Einführung; seine Arbeiten können im pdf-Format heruntergeladen werden .

Zusammenfassung - Ein neues Maß für die String-Komplexität für endliche Strings wird basierend auf einem bestimmten rekursiven hierarchischen String- Produktionsprozess vorgestellt . Aus der maximalen Schranke leiten wir ein Verhältnis zwischen Komplexität und Gesamtinformationsgehalt ab. ..kompletter Artikel...

Ich habe auch einige Artikel über praktische Implementierungen gefunden (siehe zum Beispiel " Ein schneller T-Zerlegungsalgorithmus ")

Grundsätzlich ist fast jede maschinelle Lern- oder Komprimierungsmethode eine Annäherung an die Kolmogorov-Komplexität:

• Wenn Sie irgendeine berechenbare Wahrscheinlichkeitsverteilung haben , die Ihre Daten Wahrscheinlichkeit zuweist dann durch die Kraft Ungleichheit, haben Sie einen Kompressor, der Ihre Daten in komprimiert - log p ( x ) Bits.$p(x)$$- \log p(x)$
• Wenn Sie einen berechenbaren Kompressor C haben, der Ihre Daten auf Bits komprimiert , dann haben Sie K ( x ) ≤ n + s C , wobei s C von Ihrem Kompressor abhängt, aber nicht von x (es ist im Grunde die Anzahl der Bits, die Sie benötigen) beschreiben Sie C Ihrer universellen Turingmaschine).$n$$K(x) \leq n + s_C$$s_C$$x$

Sie können also einfach nach Mustern mit einer beliebigen Kompressor- oder Wahrscheinlichkeitsverteilung suchen. Je besser diese Ihre Daten komprimieren, desto besser ist Ihre Obergrenze für K (x). Stellen Sie einfach sicher, dass Sie die Größe des Kompressors selbst zur Größe der komprimierten Daten addieren, um die Schätzung zu erhalten.

$K(x)$

$K(x)$$K$

Sie können auch eine Zeitbeschränkung verwenden, um Ihre Modellklasse zu definieren, die Sie zu Sureshs Antwort führt. Grundsätzlich können Sie ziemlich sicher sein, dass Sie die Kolmogorov-Komplexität genau geschätzt haben, wenn Sie davon ausgehen, dass Ihre Datenquelle eine polynomielle Zeitkomplexität aufweist, und Sie versuchen, sie mit allen polynomischen Turing-Maschinen zu komprimieren. Dies mag immer noch nicht so praktisch sein, aber für niedrigere Zeitgrenzen können Sie möglicherweise die vollständige Bayes'sche Mischung berechnen, die sich gut annähert.

Technische Details finden Sie in diesem Dokument . Haftungsausschluss: Ich bin einer der Autoren.

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

Sie suchen nach einer ressourcenbeschränkten Kolmogorov-Komplexität. Sie können mit diesem Papier beginnen und verzweigen.