Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Kolmogorov Complexity and Compression Distance (2023)

smunshi.net

Post reply on HN
Print view View original

51–60 of 106 posts

Re: Kolmogorov Complexity and Compression Distance (2023)

#51

Post by canjobear »

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…

The whole point of Kolmogorov complexity is that description lengths under different Turing-complete description languages (such as UTM and lambda calculus) are only different up to a constant that depends on the languages and not on the thing being described.

Re: Kolmogorov Complexity and Compression Distance (2023)

#52

Post by canjobear »

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…

Why is this a problem? No information is lost when characters (or graphics) are encoded in binary.

Re: Kolmogorov Complexity and Compression Distance (2023)

#53

Post by canjobear »

n4r9 wrote: post #33
arketyp wrote: post #9

Richard von Mises (brother of the economist) formulated a definition of randomness as a sequence of data that, were you a gambler, you cannot by any strategy make money on betting on the outcomes. This was before computational calculus and was later developed by Kolmogorov and others in algorithmic complexity. The modern variation would be (Wiki) "considering a finite sequence random (with respect to a class of compu…

> you cannot by any strategy make money on betting on the outcomes What does "strategy" mean here? I might just happen to have a strategy which involves betting on the exact sequence of heads and tails in a given sequence. The analogy in terms of languages is that my language might just happen to have a short keyword that represents a given sequence of heads and tails. I don't know much about Kolmogorow complexity so…

> What does "strategy" mean here?

Any function that outputs bets.

Re: Kolmogorov Complexity and Compression Distance (2023)

#54

Post by canjobear »

arketyp wrote: post #9

Richard von Mises (brother of the economist) formulated a definition of randomness as a sequence of data that, were you a gambler, you cannot by any strategy make money on betting on the outcomes. This was before computational calculus and was later developed by Kolmogorov and others in algorithmic complexity. The modern variation would be (Wiki) "considering a finite sequence random (with respect to a class of compu…

Do you have a citation? I didn’t know the idea went back that far.

Re: Kolmogorov Complexity and Compression Distance (2023)

#55

Post by srcreigh »

causal wrote: post #42
srcreigh wrote: post #4

Earlier quoted context omitted.

The author is referring to something called Chaitin incompleteness. https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin'... Of course trivially some KC can be proven, ex a language with 1 or 0 characters that is interpreted to a specific string. Or to prove KC(x) where the compressed value has length N and you can list out all the results for all strings of length less than N, and they don't equal x, proves K…

This seems to assume that KC can be infinite. That must have been proven at some point? Otherwise it may be that there is some upper-bound for L which happens to also be the KC for a KC-computer.

yes, it’s a pigeonhole principle argument. A bit tricky to actually enumerate everything. Imagine KC had a limit k. Then there’s a fixed number of strings that can be compressed to k characters. so considering how there’s an infinite number of strings of length greater than k, they can’t all be compressed to be at most k. Therefore KC has no limit

Re: Kolmogorov Complexity and Compression Distance (2023)

#56

Post by SimplyUnknown »

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…

But Chinese (or mandarin) is not a context-free grammar whereas I believe that encoding a language on a turing machine implies a context-free grammar so this example doesn't hold.

Re: Kolmogorov Complexity and Compression Distance (2023)

#57

Post by quibono »

alfanick wrote: post #34

A side question: is this taught in CS curriculum you know? It was at my uni (fairly good one, in a minor European country), and this experience biases me because I assume every CS knows Kolmogorov complexity.

Yes, at least in the UK. From working through some US university curricula - it's also present there as well.

Re: Kolmogorov Complexity and Compression Distance (2023)

#58

Post by AnotherGoodName »

davesque wrote: post #37

Something I've always noticed with the notion of Kolmogorov complexity is that the question of determining the lowest level of computation is problematic. For example, in the article, the author first defines the basic idea of KC. But then they correctly point out that the basic idea depends very much on the exact language that is chosen. So they describe how theorists have defined the notion of universal computation…

Shannon entropy and Kolmogorov complexity are absolutely literally the same thing though! They are both purely theoretical and you cannot calculate the minimum Shannon entropy any better than you can calculate the Kolmogorov complexity. In fact if you could calculate one you could calculate the other trivially but we don't have a way to do that.

For those now thinking about how to calculate Shannon entropy using the defined formula what are you using for the symbols? If you used one bit symbols of '1' and '0' and a probability of each appearing a file that was just 11101110... repeating would you would find a different Shannon entropy to someone using 4 bit symbols. Shannon entropy is literally uncomputable in the real world. You can only compute it if you are given a fixed alphabet and frequencies but in the real world the optimal alphabet for a given file to calculate the minimum Shannon entropy is actually unknowable.

That's where Kolmogorov complexity comes in. It states that "well we don't actually have a way to define the alphabet in Shannon entropy in the real world but if we pretend we have a system (the universal computation) we could calculate it". They then add in the size of the program length that does the calculation as well to prevent cheating by having a language that has a dictionary specific to the thing to encode and call that Kolmogorov complexity. But that's it. They are literally the same thing in essence.

Kolmogorov complexity is in fact better than Shannon entropy for real world usage. It's every bit as computable in the real world (ie. not at all but at the very least you can do the best compression you can and make a guess!) but it at least states that upfront.

For anyone wanting to claim that they had a CS assignment to calculate Shannon entropy and it's totally computable your teacher should probably have explained that the symbol frequencies for the alphabet given aren't actually computable like that in the real world as the optimal symbol lengths themselves aren't actually computable. You cannot in the real world just say "compute the Shannon entropy of an alphabet with two symbols - B 30% and A 70%" because you don't actually know if B and A are the optimal alphabet to define to minimize Shannon entropy. BBBAAAAAAA repeated has no entropy but it fits the definition of the question given and would give you a different result.

Re: Kolmogorov Complexity and Compression Distance (2023)

#59

Post by basil-rash »

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.

The complexity cannot be over 10,000,000 if that simple program generated it. That is the precise definition of complexity.

I don’t understand what you mean by reducibility to random strings, randomness has precisely nothing to do with complexity, even if they do tend to go together.

Re: Kolmogorov Complexity and Compression Distance (2023)

#60

Post by AnotherGoodName »

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…

This is quite misguided as you seem to think the alphabet for Shannon entropy or Kolmogorov complexity is in any way what we think of as an alphabet.

Did you know the best compression methods out all have a variable length (measured in bits) alphabet? eg. Dynamic Markov Coding will start with just '0' and '1' and then predict the next bit but as it see's more symbols it will extend this to single characters (so see 'a' or 'b' and predict the next bit). They'll then continue as they learn more of the file and their alphabet will essentially include common pairwise letters, then words and entire common phrases.

This is actually a commonly missed aspect of Shannon entropy. A file of 0111101110111 repeated will give you a different result if you consider a 1 bit alphabet of 25% '0' and 75% '1' than a 4 bit alphabet of 100% '0111'. No one in the real world is using the character frequencies of english characters as a measure of Shannon entropy or Kolmogorov complexity. No algorithm expects that. They all work at the binary level and they will try to adjust the symbol lengths of the alphabet to common sequences to achieve the best result.

This is in fact the reason Kolmogorov complexity is used rather than Shannon entropy. Shannon entropy doesn't tell you how to define an optimal alphabet. That part is actually undefinable. It just tells you what to do if you have that already. Kolmogorov complexity says more completely 'find the optimal alphabet and the symbol probabilities and make a minimal sequence from that'.

Different human languages don't figure into this at all and are completely irrelevant.

Post reply on HN