5 ms·

Shannon’s Source Coding Theorem (2020)

127 points by ElFitz 3y ago

ElFitz 3y ago
I was curious as to wether or not there is a way to determine the actual amount of information in a given file (say, an image), and thus a theoretical limit to lossless compression, which is apparently called "Kolmogorov Complexity" [1], and this came up. [1]: https://en.m.wikipedia.org/wiki/Kolmogorov_complexity https://en.m.wikipedia.org/wiki/Kolmogorov_complexity
- KRAKRISMOTT 3y ago
  Run your file through every compression algorithm (that doesn't utilize too much prior knowledge i.e. not LLMs) that you can get your hands on. After a certain point it won't be able to get compressed further. It's a good approximation for the limit I think.
  - ElFitz 3y ago
    I wouldn’t have thought of that. I was more interested in learning about the possible theory behind such a limit, to see if we had a way to actually know how far such optimisations can go. Basically, for any given file, what would be the absolute best we could hope for (without resorting to losing information).
    - MauranKilom 3y ago
      That question makes pretty little sense without fixing some constraints like "what other files exist" and "what language are you allowed to reproduce them". In a world where every single file is exactly "abcd", it takes zero bits to represent the file - you don't need any information to know that the file contains "abcd" because all files do. In theory, the language you use to output the file could have a one-bit coding '0' for "produce the file 'there are comments on HN'" (and all other commands starting with '1...'). So in the world we live in, the smallest a file can be compressed to is 1 bit - if you just use the right language. None of these are practical in general, but the point is that Kolmogorov Complexity is not meaningful without specifying more assumptions/priors.
      - ElFitz 3y ago
        Absolutely, that is part of what I have come to understand while diving into the topic. That I first needed to answer quite a few other questions for that one to even make sense. Thank you for the examples; they are much clearer and straightforward than most of those I’ve come across.
      - guimplen 3y ago
        This is a misconception. The main result in the Kolmogorov complexity theory that there is precisely the "universal prior" that comes simply from the notion of computability.
        Ono-Sendai 3y ago
        It's a misconception the "universal prior" is at all helpful.
        guimplen 3y ago
        This universal prior is both theoretically useful and help conceptualize the real-world compression techniques.
    - oh_sigh 3y ago
      Not to be pedantic, but for any given file the answer is 0% compression, due to the pigeonhole principle.
      - ElFitz 3y ago
        Not at all! Having basically no knowledge in that area, aside from a vague understanding of the purpose and uses of information theory, it is more than welcome! For those interested also unfamiliar with it: - https://eprint.iacr.org/2021/1333.pdf https://eprint.iacr.org/2021/1333.pdf - https://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/ https://matt.might.net/articles/why-infinite-or-guaranteed-f...
  - jsenn 3y ago
    This might give a decent estimate of the entropy of the file, but it is a poor approximation of the Kolmogorov complexity in general. All major compression libraries that I know of essentially work by "factoring out" statistical regularities in the input string--i.e. repeating patterns. But many strings have regularity that can't be captured statistically. For example, the sequence 1, 2, 3, 4, ... has an entropy rate of 1, because all digits and all subsequences of digits occur with equal frequency, so most modern compression libraries are going to be unable to compress it to any significant degree [1]. However, it obviously has a very compact representation as a program in your favourite language. If you want to go down a bit of a rabbit hole, this video from a researcher in this field gives an overview, as well as some proposed methods for approximating Kolmogorov Complexity in a reasonable way (even though in a technical sense approximating it with known, fixed bounds is I believe impossible): https://www.youtube.com/watch?v=HXM3BUXsY4g https://www.youtube.com/watch?v=HXM3BUXsY4g. This paper also discusses a theory that decomposes KC into a statistical part (Shannon entropy) and a "computational part": https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePage.htm https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePag.... [1]: Note that if you encode it as ASCII or even N-bit integers there will be significant redundancy in the encoding. To properly test it you'd have to encode the numbers in a packed binary encoding with no padding.
    - Panzer04 3y ago
      Thus is how some video encoding algorithms ans the like sort of work, iirc - you encode interface differences under the assumption that any particular part of the screen isn't likely to change much. Encoding algorithms end up getting specialised for particular types of data because different data exhibits different patterns.
- deleted 3y ago
  [deleted]
- supriyo-biswas 3y ago
  The formula for entropy and the source coding theorem discussed in the article describe exactly that.
  - waveBidder 3y ago
    beyond, in fact, since they're lossy formats
- canjobear 3y ago
  If you have a probability distribution over patterns you are likely to find in a file, then the Shannon entropy gives you the best losslessly compressed filesize you can achieve. Kolmogorov complexity is the length of the shortest computer program in some programming language that can generate your file. It gives the same number across different programming languages, up to an uncomputable and likely very large additive constant. It’s a more universal notion of compressibility than Shannon entropy, because it doesn’t depend on a probability distribution, but it is uncomputable. The concepts are related because for any programming language, you can see it as corresponding to a probability distribution such that p(x) \propto 2^-(length of the program that generates x).
- exhaze 3y ago
  A practical way I used to grok this is to try to zip up an mp4 or a jpeg. You’ll notice the size doesn’t really change. That’s because these formats already applied entropy coding compression techniques and have compressed the information very close to the Shannon entropy limit.
  - CorrectHorseBat 3y ago
    JPEG XL supports reversible JPEGs transcoding in ~20% less space, which wouldn't be possible if JPEG was very close to the Shannon entropy limit.
    - Panzer04 3y ago
      JPEG is lossy though - I'm pretty sure these theorems only really apply to lossless compression, because if you allow lossy compression you can do all kinds of things to different t types of data (pictures being the classic case of permitting pretty lossy compression without much noticeable quality degradation)
      - CorrectHorseBat 3y ago
        Maybe I wasn't clear enough: JPEG -> JPEG XL -> JPEG is not lossy, you get exactly the same bits back, but the JPEG XL file is 20% smaller.
        Panzer04 3y ago
        Oh, very interesting. I'll have to look into it.
  - pizza 3y ago
    There's a distinction to be made here, order-0 entropy versus higher order entropy. Order here just means how long a chain of symbols that is considered, where order-0 means just count each symbol at a time, versus eg order-1 where you consider chains of two symbols. Like the other commenter says, JPEGXL can recompress JPEGs losslessly to be around 20% smaller by exploiting higher order patterns (eg via move-to-front, lz77-ish matches, and the MANIAC tree context modeling, versus JPEG's RLE (which is "sort of beyond order-0") combined with Huffman coding (which is order-0))
- contravariant 3y ago
  Entropy doesn't make much sense for a single instance. There trivially exists a codec that will translate any particular file into any other. To get a real idea how much information is in a file you'll need some statistical model about how it may have been generated (thankfully the model doesn't have to be perfect). You will also want to be a bit careful what assumptions you allow this model to make. In a very real sense a hash is mostly enough information to recover a file if you know it exists somewhere, as torrents and magnet links prove.
nico 3y ago
In the example in the article, if you want to communicate a series of 5 dice rolls, you can send a binary symbol of the number of each roll (1-6), 5 times. Using 3-bit coding for each number, it would take 15bits (5 numbers in the sequence, 3 bits each) to communicate a message But there’s an alternative way, instead of each number individually, you can code the sequences of 5 numbers, which there are 65432 of in this case, 6!/1! = 720, which can be encoded in binary with 8 bits So instead of 15 bits, you can use 8
- rododendro 3y ago
  All sequences of 5 numbers in the range [6] should be 6 * 6 * ... * 6 = 6^5, which would give 12.92 bits, so 13. The only way to actually do better than sending every symbol would be run length encoding or other non fixed alphabet encodings, which fortunately do not need to be longer than the entropy of the distribution.
  - nico 3y ago
    You are right, it’s 6^5 to include sequences with repeating symbols In any case, you don’t need to index the whole numbers space to transmit all the information Like you say, you can use 13 bits instead of 15 And using variable length encoding you can reduce it even more But what is the distribution in this case?
    - rododendro 3y ago
      Well in this case the distribution would simply be a uniform distribution over [1:6], which has entropy 2.58 for each symbol. Which is also the most entropic distribution on the sets of size 6. Like other have said, you can't actually know in a real world scenario your underlying distribution in whatever file you are trying to compress, but since you want to compress it you are telling the program that the file has interesting information (otherwise it would be just noise) and so grammar based encoding would probably not be best, instead lz77 or lz78 would perform better (for example, if you know more about the file you could even do better by transforming first into some frequency domain and then compressing).
teleforce 3y ago
Shannon is such an engineering marvel as Einstein is for science. His perennial works, hobbies, papers and theses outlined the fundamentals of modern engineering foundations including digital, computer and communication systems including AI systems of early forms of chess engine, LLM, etc [1]. Kleinrock once noted that he has to pursue exotic field of queuing theory that led to packet switching and then Internet, because most of popular problems in his research field have been solved by Shannon (who was also one of Kleinrock's doctoral research study committee members). [1]How Claude Shannon Helped Kick-start Machine Learning: https://www.spectrum.ieee.org/claude-shannon-information-theory-2656470431 https://www.spectrum.ieee.org/claude-shannon-information-the...
- 082349872349872 3y ago
  I'm fond of his "mind-reading machine": https://literateprograms.org/mind_reading_machine__awk_.html https://literateprograms.org/mind_reading_machine__awk_.html (compare Agassi/Becker for the value of single-bit predictions)
  - metadat 3y ago
    Wow, what a fascinating concept and read. It's humbling to consider and marvel at what early technology pioneers like Claude Shannon envisioned and accomplished with a tiny, miniscule sliver of computational power compared to what we are surrounded by today. I couldn't resist submitting it, especially considering it has not yet been discussed on HN*: https://news.ycombinator.com/item?id=36385198 https://news.ycombinator.com/item?id=36385198 (*A different link covering the same subject was submitted 6 years ago but never caught on: https://news.ycombinator.com/item?id=14450232 https://news.ycombinator.com/item?id=14450232)
activatedgeek 3y ago
Another excellent book that I recently read was "Information Theory: A Tutorial Introduction" by James V. Stone [1]. This book is a fairly light read and builds up everything from scratch which was very nice. Shannon's original paper [2] is often touted to be very parseable, but it is always enlightening to read the same basics many times from multiple sources, especially something as foundational as source coding (and broader information theory) in a more modern language. I also finally discovered the meaning of "differential" in differential entropy [2], the continuous counterpart of discrete probability masses, something that I always swept under the rug. [1]: https://www.librarything.com/work/16165301/book/242295611 https://www.librarything.com/work/16165301/book/242295611 [2]: https://ieeexplore.ieee.org/document/6773024 https://ieeexplore.ieee.org/document/6773024 [3]: https://sanyamkapoor.com/kb/differential-entropy https://sanyamkapoor.com/kb/differential-entropy

127 points by ElFitz 3y ago

I was curious as to wether or not there is a way to determine the actual amount of information in a given file (say, an image), and thus a theoretical limit to lossless compression, which is apparently called "Kolmogorov Complexity" [1], and this came up. [1]: https://en.m.wikipedia.org/wiki/Kolmogorov_complexity https://en.m.wikipedia.org/wiki/Kolmogorov_complexity

KRAKRISMOTT 3y ago
Run your file through every compression algorithm (that doesn't utilize too much prior knowledge i.e. not LLMs) that you can get your hands on. After a certain point it won't be able to get compressed further. It's a good approximation for the limit I think.
- ElFitz 3y ago
  I wouldn’t have thought of that. I was more interested in learning about the possible theory behind such a limit, to see if we had a way to actually know how far such optimisations can go. Basically, for any given file, what would be the absolute best we could hope for (without resorting to losing information).
  - MauranKilom 3y ago
    That question makes pretty little sense without fixing some constraints like "what other files exist" and "what language are you allowed to reproduce them". In a world where every single file is exactly "abcd", it takes zero bits to represent the file - you don't need any information to know that the file contains "abcd" because all files do. In theory, the language you use to output the file could have a one-bit coding '0' for "produce the file 'there are comments on HN'" (and all other commands starting with '1...'). So in the world we live in, the smallest a file can be compressed to is 1 bit - if you just use the right language. None of these are practical in general, but the point is that Kolmogorov Complexity is not meaningful without specifying more assumptions/priors.
    - ElFitz 3y ago
      Absolutely, that is part of what I have come to understand while diving into the topic. That I first needed to answer quite a few other questions for that one to even make sense. Thank you for the examples; they are much clearer and straightforward than most of those I’ve come across.
    - guimplen 3y ago
      This is a misconception. The main result in the Kolmogorov complexity theory that there is precisely the "universal prior" that comes simply from the notion of computability.
      - Ono-Sendai 3y ago
        It's a misconception the "universal prior" is at all helpful.
        guimplen 3y ago
        This universal prior is both theoretically useful and help conceptualize the real-world compression techniques.
  - oh_sigh 3y ago
    Not to be pedantic, but for any given file the answer is 0% compression, due to the pigeonhole principle.
    - ElFitz 3y ago
      Not at all! Having basically no knowledge in that area, aside from a vague understanding of the purpose and uses of information theory, it is more than welcome! For those interested also unfamiliar with it: - https://eprint.iacr.org/2021/1333.pdf https://eprint.iacr.org/2021/1333.pdf - https://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/ https://matt.might.net/articles/why-infinite-or-guaranteed-f...
- jsenn 3y ago
  This might give a decent estimate of the entropy of the file, but it is a poor approximation of the Kolmogorov complexity in general. All major compression libraries that I know of essentially work by "factoring out" statistical regularities in the input string--i.e. repeating patterns. But many strings have regularity that can't be captured statistically. For example, the sequence 1, 2, 3, 4, ... has an entropy rate of 1, because all digits and all subsequences of digits occur with equal frequency, so most modern compression libraries are going to be unable to compress it to any significant degree [1]. However, it obviously has a very compact representation as a program in your favourite language. If you want to go down a bit of a rabbit hole, this video from a researcher in this field gives an overview, as well as some proposed methods for approximating Kolmogorov Complexity in a reasonable way (even though in a technical sense approximating it with known, fixed bounds is I believe impossible): https://www.youtube.com/watch?v=HXM3BUXsY4g https://www.youtube.com/watch?v=HXM3BUXsY4g. This paper also discusses a theory that decomposes KC into a statistical part (Shannon entropy) and a "computational part": https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePage.htm https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePag.... [1]: Note that if you encode it as ASCII or even N-bit integers there will be significant redundancy in the encoding. To properly test it you'd have to encode the numbers in a packed binary encoding with no padding.
  - Panzer04 3y ago
    Thus is how some video encoding algorithms ans the like sort of work, iirc - you encode interface differences under the assumption that any particular part of the screen isn't likely to change much. Encoding algorithms end up getting specialised for particular types of data because different data exhibits different patterns.
deleted 3y ago
[deleted]
supriyo-biswas 3y ago
The formula for entropy and the source coding theorem discussed in the article describe exactly that.
- waveBidder 3y ago
  beyond, in fact, since they're lossy formats
canjobear 3y ago
If you have a probability distribution over patterns you are likely to find in a file, then the Shannon entropy gives you the best losslessly compressed filesize you can achieve. Kolmogorov complexity is the length of the shortest computer program in some programming language that can generate your file. It gives the same number across different programming languages, up to an uncomputable and likely very large additive constant. It’s a more universal notion of compressibility than Shannon entropy, because it doesn’t depend on a probability distribution, but it is uncomputable. The concepts are related because for any programming language, you can see it as corresponding to a probability distribution such that p(x) \propto 2^-(length of the program that generates x).
exhaze 3y ago
A practical way I used to grok this is to try to zip up an mp4 or a jpeg. You’ll notice the size doesn’t really change. That’s because these formats already applied entropy coding compression techniques and have compressed the information very close to the Shannon entropy limit.
- CorrectHorseBat 3y ago
  JPEG XL supports reversible JPEGs transcoding in ~20% less space, which wouldn't be possible if JPEG was very close to the Shannon entropy limit.
  - Panzer04 3y ago
    JPEG is lossy though - I'm pretty sure these theorems only really apply to lossless compression, because if you allow lossy compression you can do all kinds of things to different t types of data (pictures being the classic case of permitting pretty lossy compression without much noticeable quality degradation)
    - CorrectHorseBat 3y ago
      Maybe I wasn't clear enough: JPEG -> JPEG XL -> JPEG is not lossy, you get exactly the same bits back, but the JPEG XL file is 20% smaller.
      - Panzer04 3y ago
        Oh, very interesting. I'll have to look into it.
- pizza 3y ago
  There's a distinction to be made here, order-0 entropy versus higher order entropy. Order here just means how long a chain of symbols that is considered, where order-0 means just count each symbol at a time, versus eg order-1 where you consider chains of two symbols. Like the other commenter says, JPEGXL can recompress JPEGs losslessly to be around 20% smaller by exploiting higher order patterns (eg via move-to-front, lz77-ish matches, and the MANIAC tree context modeling, versus JPEG's RLE (which is "sort of beyond order-0") combined with Huffman coding (which is order-0))
contravariant 3y ago
Entropy doesn't make much sense for a single instance. There trivially exists a codec that will translate any particular file into any other. To get a real idea how much information is in a file you'll need some statistical model about how it may have been generated (thankfully the model doesn't have to be perfect). You will also want to be a bit careful what assumptions you allow this model to make. In a very real sense a hash is mostly enough information to recover a file if you know it exists somewhere, as torrents and magnet links prove.

nico 3y ago

In the example in the article, if you want to communicate a series of 5 dice rolls, you can send a binary symbol of the number of each roll (1-6), 5 times. Using 3-bit coding for each number, it would take 15bits (5 numbers in the sequence, 3 bits each) to communicate a message But there’s an alternative way, instead of each number individually, you can code the sequences of 5 numbers, which there are 65432 of in this case, 6!/1! = 720, which can be encoded in binary with 8 bits So instead of 15 bits, you can use 8

rododendro 3y ago
All sequences of 5 numbers in the range [6] should be 6 * 6 * ... * 6 = 6^5, which would give 12.92 bits, so 13. The only way to actually do better than sending every symbol would be run length encoding or other non fixed alphabet encodings, which fortunately do not need to be longer than the entropy of the distribution.
- nico 3y ago
  You are right, it’s 6^5 to include sequences with repeating symbols In any case, you don’t need to index the whole numbers space to transmit all the information Like you say, you can use 13 bits instead of 15 And using variable length encoding you can reduce it even more But what is the distribution in this case?
  - rododendro 3y ago
    Well in this case the distribution would simply be a uniform distribution over [1:6], which has entropy 2.58 for each symbol. Which is also the most entropic distribution on the sets of size 6. Like other have said, you can't actually know in a real world scenario your underlying distribution in whatever file you are trying to compress, but since you want to compress it you are telling the program that the file has interesting information (otherwise it would be just noise) and so grammar based encoding would probably not be best, instead lz77 or lz78 would perform better (for example, if you know more about the file you could even do better by transforming first into some frequency domain and then compressing).

teleforce 3y ago

Shannon is such an engineering marvel as Einstein is for science. His perennial works, hobbies, papers and theses outlined the fundamentals of modern engineering foundations including digital, computer and communication systems including AI systems of early forms of chess engine, LLM, etc [1]. Kleinrock once noted that he has to pursue exotic field of queuing theory that led to packet switching and then Internet, because most of popular problems in his research field have been solved by Shannon (who was also one of Kleinrock's doctoral research study committee members). [1]How Claude Shannon Helped Kick-start Machine Learning: https://www.spectrum.ieee.org/claude-shannon-information-theory-2656470431 https://www.spectrum.ieee.org/claude-shannon-information-the...

082349872349872 3y ago
I'm fond of his "mind-reading machine": https://literateprograms.org/mind_reading_machine__awk_.html https://literateprograms.org/mind_reading_machine__awk_.html (compare Agassi/Becker for the value of single-bit predictions)
- metadat 3y ago
  Wow, what a fascinating concept and read. It's humbling to consider and marvel at what early technology pioneers like Claude Shannon envisioned and accomplished with a tiny, miniscule sliver of computational power compared to what we are surrounded by today. I couldn't resist submitting it, especially considering it has not yet been discussed on HN*: https://news.ycombinator.com/item?id=36385198 https://news.ycombinator.com/item?id=36385198 (*A different link covering the same subject was submitted 6 years ago but never caught on: https://news.ycombinator.com/item?id=14450232 https://news.ycombinator.com/item?id=14450232)

activatedgeek 3y ago

Another excellent book that I recently read was "Information Theory: A Tutorial Introduction" by James V. Stone [1]. This book is a fairly light read and builds up everything from scratch which was very nice. Shannon's original paper [2] is often touted to be very parseable, but it is always enlightening to read the same basics many times from multiple sources, especially something as foundational as source coding (and broader information theory) in a more modern language. I also finally discovered the meaning of "differential" in differential entropy [2], the continuous counterpart of discrete probability masses, something that I always swept under the rug. [1]: https://www.librarything.com/work/16165301/book/242295611 https://www.librarything.com/work/16165301/book/242295611 [2]: https://ieeexplore.ieee.org/document/6773024 https://ieeexplore.ieee.org/document/6773024 [3]: https://sanyamkapoor.com/kb/differential-entropy https://sanyamkapoor.com/kb/differential-entropy