Kolmogorov Complexity and Compression Distance (2023) • Hacker News Board

Re: Kolmogorov Complexity and Compression Distance (2023)

#101

Post by Dylan16807 » Mon, Apr 01, 2024, 1:43 AM UTC

causal wrote: post #40

explaininjs wrote: post #15

Earlier quoted context omitted.

Similar to how the interesting number paradox relies on a "shortcut statement" to force-up the number of non-interest, If Kolmogorov complexity were computable you could create a "shortcut program" to force-down the shortest length of the program: Given: TM length of a JS runtime is 1,000,000 cells. Assume: KC is computable, and TM length of a `function KolmoglorovComplexity(string s)` is 4,000,000 cells. Known: KC's…

Still confused. What is contradictory about a simple program computing a more complex program? Randomly generating a more complex program does not make the complex program reducible to a random string generator.

> Randomly generating a more complex program does not make the complex program reducible to a random string generator.

The complex program probably does something other than generate random strings.

But the complex program is not actually more complex than the generator plus a smidge.

Because anywhere you're using the complex(z), you can replace it with generator()(z).

Re: Kolmogorov Complexity and Compression Distance (2023)

#102

Post by Dylan16807 » Mon, Apr 01, 2024, 1:53 AM UTC

AnotherGoodName wrote: post #76

Ono-Sendai wrote: post #68

Kolmogorov Complexity does not help with giving a universal measure of complexity or randomness: https://forwardscattering.org/page/0

It's a lot better than the alternatives. Particularly the misused Shannon entropy. The top rated answer for "how do i measure Shannon entropy" on stack overflow for example has an accepted answer of "count the probabilities of all 8bit sequences and then multiply the log of those probabilities together as per the equation". Which is a problematic answer. A file of all 8bit characters in sequence repeated many times o…

I'd argue that for most compression methods, not including the decompression program size will give you a better rough estimate.

Re: Kolmogorov Complexity and Compression Distance (2023)

#103

Post by uoaei » Mon, Apr 01, 2024, 2:21 AM UTC

data_maan wrote: post #88

uoaei wrote: post #69

Earlier quoted context omitted.

The whole point of Kolmogorov complexity is that there exists some language for minimal description length of an arbitrary program and you compare optimal descriptions across languages. In other words, the point is to explicitly consider the choice of language as part of the encoding scheme that needs describing. That choice is included as part of the description whose length is being measured.

Is that really true? You could just take whatever you want to describe to be part of the language and arrive trivially at a description length of 1...?

How long is the description length of the language...?

Re: Kolmogorov Complexity and Compression Distance (2023)

#104

Post by AnotherGoodName » Mon, Apr 01, 2024, 2:33 AM UTC

Dylan16807 wrote: post #102

AnotherGoodName wrote: post #76

Earlier quoted context omitted.

It's a lot better than the alternatives. Particularly the misused Shannon entropy. The top rated answer for "how do i measure Shannon entropy" on stack overflow for example has an accepted answer of "count the probabilities of all 8bit sequences and then multiply the log of those probabilities together as per the equation". Which is a problematic answer. A file of all 8bit characters in sequence repeated many times o…

I'd argue that for most compression methods, not including the decompression program size will give you a better rough estimate.

Including it just excludes the old 'program that returns a compressed size of 0 for a common test case because it contains the common test case within itself' scenario. There's variations of that too. Gpt is fantastic at predicting text and you could use that prediction with arithmetic coding to make a very minimal length for some common English text. But is that really fair? The gpt model essentially contains that English text. Including the program size has little overhead for most cases (code size is generally small) but it ensures we catch out cheating which is why kolmogorov complexity includes it.

Re: Kolmogorov Complexity and Compression Distance (2023)

#105

Post by Dylan16807 » Mon, Apr 01, 2024, 2:41 AM UTC

AnotherGoodName wrote: post #104

Dylan16807 wrote: post #102

Earlier quoted context omitted.

I'd argue that for most compression methods, not including the decompression program size will give you a better rough estimate.

Including it just excludes the old 'program that returns a compressed size of 0 for a common test case because it contains the common test case within itself' scenario. There's variations of that too. Gpt is fantastic at predicting text and you could use that prediction with arithmetic coding to make a very minimal length for some common English text. But is that really fair? The gpt model essentially contains that E…

If you're cheating your own rough estimate, what are you even doing?

Custom cheats and large language model predictors are outside the realm of "most compression methods".

My thought is that lots of things you might want to compress are pretty small, so if you toss a 200KB not-ultra-size-optimized decompressor on top you get a very misleading number. Not having it will tend to understate a bit, but also current compression algorithms are far from perfect so that counterbalances the effect.

I think I disagree with you about how big a blob of text is getting compressed in "most cases". (If we look at photographs or videos then it works better, but we still want to arrange a minimal decompressor instead of grabbing a typical implementation. And the lossy/lossless factor makes the entire thing far more complicated.)

Re: Kolmogorov Complexity and Compression Distance (2023)

#106

Post by tromp » Mon, Apr 01, 2024, 9:53 AM UTC

rhelz wrote: post #26

tromp wrote: post #20

> let’s assume that there exists a universal language U Why not specify it? > That gives us the true language-agnostic definition of Kolmogorov Complexity as follows: Choosing the language of Turing Machines does not make the definition language agnostic. Aiming for the simplest definition of description complexity, I instead based my definitions on the older computational model of lambda calculus in [1]. Unlike the…

There is another, more insidious, problem with trying to give a language agnostic definition: Different languages will have different symbols which are outputable. If you have a Turing machine which can only print out binary digits, then it can't print out a chinese character, no matter how long the input program is. Yeah, you can do something like unicode, and associate a binary string with each chinese character--b…

> It therefore cannot be used to define a universal complexity for any string.

It defines a complexity for anything which can be represented in binary. Which in practice is all we want. Who wants to define a new complexity measure for every new alphabet of symbols?