21
$\begingroup$

I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (identify how each author writes some text and group documents by their similarity).

In that case, data compressors were used to approximate the Kolmogorov complexity, since the data compressor could be used as a Turing Machine.

Besides data compression and programming languages (in which you would write some kind of compressor), what else could be used to approximate the Kolmogorov complexity? Are there any other approaches that could be used?

$\endgroup$
  • $\begingroup$ I'm not sure I understand your question: The definition of KC involves turing machines, of which programs form examples (with respect to some translation). What does it mean to approximate the Kolmogorv complexity "without programming languages"? $\endgroup$ – cody Sep 12 '12 at 22:47
  • 1
    $\begingroup$ Compress a string using any compression software, like GZip. The size of the output is an upper bound to the KC of the string. $\endgroup$ – M. Alaggan Sep 13 '12 at 0:51
  • $\begingroup$ @cody: exactly, I've used data compressors in my research (zip, bzip, ppmd) to approximate KC. Data compressor aren't, exactly, programs.. So, I'm looking for suggestions on what could be used in KC besides languages (=write a program in C / prolog / whatever) and data compressors (=use zip, gzip, ppmc, ppmd...) :) $\endgroup$ – woliveirajr Sep 13 '12 at 14:39
  • 1
    $\begingroup$ I guess it just seems to me that the definition of a data compression program is exactly: a program that approximates the KC of a string by a program (the "uncompressor") and another string (the compressed string). $\endgroup$ – cody Sep 13 '12 at 18:09
9
$\begingroup$

I guess one possible answer to your question is this: Take a pseudorandom number generator $G$. Try to chose a generator which has some powerful attacks against it: a random number generator attack for $G$ is (for our purposes), an algorithm $A$ which, when given an imput string $s$, determines a seed $A(s)$, such that $G(A(s))=s$. Then approximate the KC of $s$:

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

Where $|G|$ is the length of the program that computes $G(s)$ (often quite short, as for linear generators).

Note that in practice, random number generator attacks are not as described: they may fail or produce incomplete results. In that case, you may adapt the algorithm so that it returns $|s|$ when the result of the attack is unsatisfactory. The same remark goes for compression algorithms.

The caveat to this approach as opposed to compression algorithms is that compression algorithms are in general much more suited to computing KC as they are tailored to work on any string, whereas an attack can work only if $s$ happens to be in the image of $G$ (very unlikely).

$\endgroup$
7
$\begingroup$

Any probability distribution. If you have a computable probability distribution that gives your data probability $p(x)$, then by the Kraft inequality, there's a computable compressor that compresses it in $-\log p(x)$ bits (round up if you object to fractional bits). This means pretty much any generative machine learning algorithm can be used.

This is why Kolmogorov complexity is so interesting, not because it's the ultimate compression algorithm (who cares about compression anyway), but because it's the ultimate learning algorithm. Compression and learning are basically the same thing: finding patterns in your data. The statistical framework built on this idea is called Minimum Description Length, and it was directly inspired by Kolmogorov complexity.

See also this question over at the cstheory StackExchange.

$\endgroup$
5
$\begingroup$

grammar coding is a less-frequently used version of a compression algorithm and can be taken as a "rough" estimate of Kolmogorov complexity. grammar coding is not as commonly used as a compression algorithm as other more common approaches maybe mainly because it doesnt improve much on compression from eg Lempel-Ziv on text based-corpuses, but it may do well on other kinds of data. the idea is to "compress" a string using grammar rules. a grammar derivation can result in a DAG (vs a less complex tree) so there is substantial representational complexity possible.

another option is to find smallest/minimal circuits representing a string but this is known to have very high complexity of computation and could succeed only on small strings.

generally the closer any approximation comes to calculating $K(x)$, the more intractable it is.

in an informal sense, generally any "approximation" of $K(x)$ must also be a "compression algorithm".

there are also other compression algorithm methods besides Lempel-Ziv "run length encoding" type approaches, for example vector algebra and the SVD can be used as a compression algorithm. also Fourier transforms are frequently used to compress images eg in JPG standard.

$\endgroup$
  • 1
    $\begingroup$ Of course, the compression has to be lossless to actually count as an approximation of $K(x)$. I'm pretty sure that the Fourier transform in JPG is lossy (but I'm not an expert). $\endgroup$ – cody Dec 11 '13 at 0:55
  • $\begingroup$ good point however lossy algorithms usually have an adjustable parameter that determines "lossiness" and can theoretically achieve losslessness with enough "terms" or "frequencies" so to speak, and it also depends on the input samples, such that the lossless parameter value will depend on their "relative order vs randomness" seen through the "lens" of the compression algorithm... $\endgroup$ – vzn Dec 11 '13 at 4:32
  • 1
    $\begingroup$ @cody and vzn: Thanks for the answer, you gave me some good ideas for my PhD about lossless x lossy compression :) $\endgroup$ – woliveirajr Dec 11 '13 at 10:37
  • $\begingroup$ JPEG uses DCT, not DFT. $\endgroup$ – Evil Jan 17 '17 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.