Approximation der Kolmogorov-Komplexität

22

Ich habe etwas über die Kolmogorov-Komplexität studiert, einige Artikel und Bücher von Vitanyi und Li gelesen und das Konzept der normalisierten Kompressionsentfernung verwendet , um die Stilometrie der Autoren zu überprüfen (identifiziere, wie jeder Autor einige Text- und Gruppendokumente anhand ihrer Ähnlichkeit schreibt).

In diesem Fall wurden Datenkomprimierer verwendet, um die Kolmogorov-Komplexität zu approximieren, da der Datenkomprimierer als Turing-Maschine verwendet werden könnte.

Was kann neben Datenkomprimierung und Programmiersprachen (in denen Sie eine Art Kompressor schreiben würden) noch verwendet werden, um die Kolmogorov-Komplexität zu approximieren? Gibt es andere Ansätze, die verwendet werden könnten?

woliveirajr
quelle
Ich bin mir nicht sicher, ob ich Ihre Frage verstehe: Bei der Definition von KC handelt es sich um Turing-Maschinen, von denen Programme Beispiele sind (in Bezug auf einige Übersetzungen). Was bedeutet es, die Kolmogorv-Komplexität "ohne Programmiersprachen" anzunähern?
Cody
1
Komprimieren Sie eine Zeichenfolge mit einer beliebigen Komprimierungssoftware wie GZip. Die Größe der Ausgabe ist eine Obergrenze für den KC der Zeichenfolge.
M. Alaggan
@cody: genau, ich habe in meiner Forschung Datenkompressoren (zip, bzip, ppmd) verwendet, um KC zu approximieren. Datenkomprimierungsprogramme sind eigentlich keine Programme. Ich suche also nach Vorschlägen, was in KC neben Sprachen (= Schreiben eines Programms in C / prolog / whatever) und Datenkomprimierungsprogrammen (= Verwenden von zip, gzip, ppmc, ppmd ...) :)
woliveirajr
1
Ich denke, es scheint mir nur, dass die Definition eines Datenkomprimierungsprogramms genau ist: ein Programm, das die KC einer Zeichenfolge durch ein Programm (den "Dekomprimierer") und eine andere Zeichenfolge (die komprimierte Zeichenfolge) approximiert.
Cody

Antworten:

9

Ich denke , eine mögliche Antwort auf Ihre Frage ist: Nehmen Sie einen Pseudo - Zufallszahlengenerator . Versuchen Sie, einen Generator zu wählen , das einige mächtigen hat Angriffe gegen sie: ein Zufallszahlengenerator Angriff für (für unsere Zwecke), ein Algorithmus , die, wenn eine imput Zeichenfolge gegeben , eine bestimmt Samen , so dass . Dann approximieren Sie die KC von :G A s A ( s ) G ( A ( s ) ) = s sGGAs A(s)G(A(s))=ss

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

Woist die Länge des Programms, das berechnet (oft recht kurz, wie bei linearen Generatoren).G ( s )|G|G(s)

Beachten Sie, dass Zufallszahlengenerator-Angriffe in der Praxis nicht wie beschrieben sind: Sie schlagen möglicherweise fehl oder führen zu unvollständigen Ergebnissen. In diesem Fall können Sie den Algorithmus so anpassen, dass er zurückgibt wenn das Ergebnis des Angriffs unbefriedigend ist. Die gleiche Bemerkung gilt für Kompressionsalgorithmen.|s|

Die Einschränkung bei diesem Ansatz im Gegensatz zu Kompressionsalgorithmen besteht darin, dass Kompressionsalgorithmen im Allgemeinen viel besser für die Berechnung von KC geeignet sind, da sie auf die Arbeit mit einer beliebigen Zeichenfolge zugeschnitten sind , während ein Angriff nur dann funktionieren kann, wenn zufällig im Bild von ( sehr unwahrscheinlich ).GsG

Cody
quelle
7

Beliebige Wahrscheinlichkeitsverteilung. Wenn Sie eine berechenbare Wahrscheinlichkeitsverteilung haben, die Ihre Datenwahrscheinlichkeit ergibt , dann gibt es durch die Kraft-Ungleichung einen berechenbaren Kompressor, der sie in Bits komprimiert (aufrunden, wenn Sie gegen Bruchbits protestieren). Dies bedeutet, dass so ziemlich jeder generative Algorithmus für maschinelles Lernen verwendet werden kann.- log p ( x )p(x)logp(x)

Dies ist der Grund, warum die Komplexität von Kolmogorov so interessant ist, nicht weil es der ultimative Komprimierungsalgorithmus ist (der sich sowieso um die Komprimierung kümmert), sondern weil es der ultimative Lernalgorithmus ist. Komprimierung und Lernen sind im Grunde dasselbe: Finden von Mustern in Ihren Daten. Der statistische Rahmen, der auf dieser Idee aufbaut, heißt Minimum Description Length und wurde direkt von der Komplexität Kolmogorovs inspiriert.

Siehe auch diese Frage bei cstheory StackExchange.

Peter
quelle
5

Die Grammatikcodierung ist eine seltener verwendete Version eines Komprimierungsalgorithmus und kann als "grobe" Schätzung der Kolmogorov-Komplexität angesehen werden. Grammatikcodierung wird nicht so häufig als Komprimierungsalgorithmus verwendet wie andere gängige Ansätze, möglicherweise hauptsächlich, weil sie die Komprimierung von z. B. Lempel-Ziv auf textbasierten Korpussen nicht wesentlich verbessert, aber für andere Arten von Daten möglicherweise gut geeignet ist. Die Idee ist, eine Zeichenfolge mithilfe von Grammatikregeln zu "komprimieren". Eine Grammatikableitung kann zu einer DAG führen (im Vergleich zu einem weniger komplexen Baum), sodass eine erhebliche Komplexität der Darstellung möglich ist.

Eine andere Möglichkeit besteht darin, kleinste / minimale Schaltkreise zu finden , die eine Zeichenfolge darstellen. Es ist jedoch bekannt, dass diese eine sehr hohe Komplexität der Berechnung aufweisen und nur bei kleinen Zeichenfolgen erfolgreich sein können.

Im Allgemeinen ist es umso schwieriger, zu berechnen, je näher eine Annäherung kommt .K(x)

im informellen Sinne muss im Allgemeinen jede "Annäherung" von auch ein "Kompressionsalgorithmus" sein.K(x)

Neben Lempel-Ziv-Ansätzen vom Typ "Lauflängencodierung" gibt es auch andere Komprimierungsalgorithmusmethoden, beispielsweise kann die Vektoralgebra und die SVD als Komprimierungsalgorithmus verwendet werden. Auch Fourier-Transformationen werden häufig verwendet, um Bilder zB im JPG-Standard zu komprimieren.

vzn
quelle
1
Natürlich muss die Komprimierung verlustfrei sein, um tatsächlich als Näherung für . Ich bin mir ziemlich sicher, dass die Fourier-Transformation in JPG verlustbehaftet ist (aber ich bin kein Experte). K(x)
Cody
Ein guter Punkt, jedoch haben verlustbehaftete Algorithmen normalerweise einen einstellbaren Parameter, der die "Verlusthaftigkeit" bestimmt und theoretisch sozusagen die Verlustfreiheit mit genügend "Termen" oder "Frequenzen" erreichen kann, und dies hängt auch von den Eingangsabtastwerten ab, so dass der verlustfreie Parameterwert abhängt auf ihre "relative Ordnung vs Zufälligkeit" durch die "Linse" des Kompressionsalgorithmus gesehen ...
vzn
1
@cody und vzn: Danke für die Antwort, Sie gaben mir einige gute Ideen für meine Promotion über verlustfreie x verlustbehaftete Komprimierung :)
woliveirajr
JPEG verwendet DCT, nicht DFT.
Evil