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

81–90 of 106 posts

Re: Kolmogorov Complexity and Compression Distance (2023)

#81

Post by kaba0 »

rhelz wrote: post #72
AnotherGoodName wrote: post #62

Earlier quoted context omitted.

Just because a turing machine prints out 0 and 1 at each step doesn't mean the sequences to factor into the calculation of what to print out next can't be longer binary sequences. Pretty much all the best compression methods are language agnostic and work on bit wise sequences. They also pretty much all predict the next bit and feed that into an alogithmic encoder. Eg. look up dynamic markov coding which is commonly…

> the turing machine doesn't care about that. It's also just writing 1's and 0's as per a turing machine. But a Turing machine does not have to be restricted to just printing out zeros and ones. It can be any finite set of symbols. For example, he Soviets built a computer which used base 3--its symbol set was {-1, 0, 1}. It didn't have bits which could just store "1" or "0", it had trits which could store "-1", "0",…

You can trivially convert any such Turing machine to another simply by adding n new states to it, that map a letter of the previous alphabet to the new’s.

With all due respect, you are misunderstanding something/bring something up with no relevance to complexity.

Re: Kolmogorov Complexity and Compression Distance (2023)

#82

Post by Ono-Sendai »

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…

Practically speaking, trying to compress a file is a nice way of measuring... something. I was more talking about the theoretical notion of complexity.

Re: Kolmogorov Complexity and Compression Distance (2023)

#83

Post by [deleted] »

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…

[deleted]

Re: Kolmogorov Complexity and Compression Distance (2023)

#84

Post by tromp »

rhelz wrote: post #61
AnotherGoodName wrote: post #60

Earlier quoted context omitted.

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 '…

> Different human languages don't figure into this at all and are completely irrelevant. Back to basics: A Turing machine is specified by a set of symbols it can read/write to a tape, and a state machine matching current state and read symbol to next state and actions. If that set of symbols is just {1,0}, then it absolutely, positively, cannot print out the string "ABC". > the best compression methods out all have a…

> cannot print out the string "ABC"

When you write a program in any modern programming language to print "ABC", that program merely outputs the 3 bytes 01000001 01000010 01000011, ASCII codes which your console window (not the program you wrote) decides to display graphically as those characters.

So any machine outputting bits can be said to print out "ABC" just as well.

Furthermore, your comment above was transmitted by your browser to Hacker News not as English characters but as those very bits, and everyone reading your comment was receiving those bits. The way that the browser decides to display those bits does not change their character.

Re: Kolmogorov Complexity and Compression Distance (2023)

#85

Post by tromp »

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.

KC(x) is always finite for any finite x. What we can say instead is that KC is unbounded. I.e. there is no finite bound on the value of KC(x).

Re: Kolmogorov Complexity and Compression Distance (2023)

#86

Post by Xcelerate »

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…

Many people seem to get hung up on questions related to the specifics about the implementation of computational models, but mathematicians don’t, because the fundamental aspects of the theory don’t change much when you swap out one particular model of universal computation for another.

As noted, Kolomogorov complexity depends on the specific UTM only up to a constant factor (this is known as the invariance theorem). But even the change in runtime, memory usage, and essentially anything else you might think are important are bounded by a factor that is either a constant or a “slow-growth” function (e.g. a polynomial) when you swap out one computational model for another. These small terms are generally dwarfed by the size of the data itself (even for small datasets) and the complexity of the algorithms used.

That said, I also share some of your confusion on the “specifics” when it comes to Solomonoff induction. I have yet to understand why the universal distribution uses negative exponentiated program size to weight the universal a priori probability of a particular string as opposed to some measure that involves program runtime or frequency over an equivalence class of programs that implement the same algorithm.

Solomonoff was careful to point out that his universal distribution is more of a class of distributions that have certain “universally optimal” convergence properties given a reasonable assumption on the underlying model of data generation: a deterministic algorithm with a short description that has access to a source of randomness. But I think many people since then have made the unwarranted leap that Solomonoff induction is the best induction scheme for all models of data generation, including data obtained via observation within our universe. I’m not sure that has been proven true. And if it has, I certainly haven’t come across the paper showing it.

Re: Kolmogorov Complexity and Compression Distance (2023)

#87

Post by woliveirajr »

anonzzzies wrote: post #38

Kolmogorov complexity is a lovely subject and one of the more influential ones in my life. THE book https://link.springer.com/book/10.1007/978-0-387-49820-1 is absolutely a thing to read. It was for me 30 years ago and it aged well.

One of Vitany's student used it to create the NCD (normalized compression distance), and then I went on to get Master/PhD degree on using it to authorship attribution.

Re: Kolmogorov Complexity and Compression Distance (2023)

#88

Post by data_maan »

uoaei wrote: post #69
canjobear wrote: post #51

Earlier quoted context omitted.

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.

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...?

Re: Kolmogorov Complexity and Compression Distance (2023)

#90

Post by rhelz »

tromp wrote: post #84
rhelz wrote: post #61

Earlier quoted context omitted.

> Different human languages don't figure into this at all and are completely irrelevant. Back to basics: A Turing machine is specified by a set of symbols it can read/write to a tape, and a state machine matching current state and read symbol to next state and actions. If that set of symbols is just {1,0}, then it absolutely, positively, cannot print out the string "ABC". > the best compression methods out all have a…

> cannot print out the string "ABC" When you write a program in any modern programming language to print "ABC", that program merely outputs the 3 bytes 01000001 01000010 01000011, ASCII codes which your console window (not the program you wrote) decides to display graphically as those characters. So any machine outputting bits can be said to print out "ABC" just as well. Furthermore, your comment above was transmitte…

> When you write a program in any modern programming language

Think about it this way. Say you have 1 bit of memory. Can you store any of the three numbers -1, 0, 1 with that a bit?? No. The only thing a bit can store is 0 or 1.

There have been trinary computers built. They don't use bits, they use trits. A Trit can store -1,0, or 1.

A bit cannot. Saying that a turing machine, whose symbol set is {0,1} can print "A" on its tape, is like saying you can store "-1" >>>in a single bit<<<< on a binary computer.

Post reply on HN