Approximation der Kolmogorov-Komplexität

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?

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 $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|

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 ).$s$$G$

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)$$-\log p(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.

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.