11 ms·

Some background before i explain why your suggestion is "not even wrong". If you can predict the next X bits given previous Y bits of observation you don't need

Some background before i explain why your suggestion is "not even wrong". If you can predict the next X bits given previous Y bits of observation you don't need to store the next X bits, the decompressor can just use the same prediction algorithm you just used and write out its predictions without correction. This is the same as general purpose AI at a high level. If you can predict the next X bits given previous Y bits of observation you can make reasoned a decision ("Choose option A now so that the next X bits have a certain outcome"). The above is actually the premise of the competition and the reason it exists. What i've said above is in academic papers in detail by Marcus Hutter et al. who runs this competition. That is lossless compression can be a scorecard of prediction which is the same as AGI. Now saying "they should just make it lossy" misses the point. Do you know how to turn lossy data into lossless? You store some data everytime you're wrong on your prediction. ie. Store data when you have loss to make it lossy. This is arithmetic coding in a nutshell. You can turn any lossy data into lossless data with arithmetic coding. This will require more data the more loss you have. The lossless requirement gives us a scorecard of how well the lossy prediction worked. If you ask for this to be lossy compression you throw out that scorecard and bring in an entire amount of subjectivity to this which is unwanted.

version_five 3y ago
[flagged]
- joshxyz 3y ago
  Your comment is far more worse, lol. His comment actually supports gp's suggestion, just in a different angle. It looks like LLM's are like compression algorithms with strengths and weaknesses in different things. Losslessness doesnt always equate to usefulness. But yea, maybe a different competition for this.
- AnotherGoodName 3y ago
  Sorry but i hope my long-winded explanation explains it. In computer science we have a way to score how good lossy data is. That way is to make it lossless and look at how much data the arithmetic coder needed to correct it from lossy to lossless. This is a mathematically perfect way to judge (you can't correct lossy data any more efficiently than an arithmetic coder). All the entries here do in fact make probabilistic predictions on the data and they do all use arithmetic coding. So the suggestion misses a key point of CS involved here. I don't mean to be rude about it but the idea does need correcting.
  - Dylan16807 3y ago
    > This is a mathematically perfect way to judge Only if you're using a very particular and honestly circular-sounding definition of "good". Some deviations are more important than others, even if you're looking at deviations that take the same amount of data to correct. Think about film grain. Some codecs can characterize it, remove it when compressing, and then synthesize new visually matching grain when decompressing. Let's say it takes a billion bytes to turn the lossy version back into the lossless version. The version with synthetic film grain still needs a billion bytes or maybe even slightly more bytes, even if the synthetic grain is 95% as good as real grain. The cost to turn it lossless is the wrong metric.
aeternum 3y ago
Is there any evidence that arithmetic coding works at the level of concepts? As a thought experiment, suppose Copernicus came up with this Hutter prize idea and declared that he would provide the award to whoever could compress the text of his book on the epicycle-based movement of planets around the sun (De revolutionibus orbium coelestium). Today we can explain the actual motion to high accuracy with a single sentence that would have been understandable in that age: "A line drawn from the sun to any planet sweeps out equal areas in equal time" This however is mostly useless in attempting to win the Copernican Hutter prize. Predicting the wording of some random human's choosing (especially at length) is very far removed from ability to predict in general.
- AnotherGoodName 3y ago
  Arithmetic coding isn't the key thing here. That's just a bit wise algorithm. You predict the next bit is a 1 with 90% certainty? you don't need to store much data with arithmetic coding. That's all arithmetic coding is here. What your getting at is the 'predictor' that feeds into the arithmetic coder and that's wide open and can work any way you want it to. LLMs absolutely have context which is similar to what your asking and they are good predictors of output given complex input (pass gpt a mathematical series and ask it what comes next. If it's right then it's really helpful in compression as you wouldn't need to store the whole series in full).
- kaba0 3y ago
  So you don’t think that writing a wiki article about this could be made smaller by encoding this info in a few logical steps, and adding some metadata on what kind of sentence should follow what? That part about decompressing it is the AI part. Where to place a comma can be added in constant cost between any contender programs.
  - aeternum 3y ago
    Sure my point is more that this adding of commas business dwarfs any real prediction. Suppose there were a superintelligence that figured out the theory of everything for the universe. It's unclear that would actually help with this task. You could likely easily derive things like gravitaiton, chemistry, etc but the vast majority of your bits would still be used attempting to match the persona and wording of the various wikipedia authors. This superintelligence would be masked by some LLM that is slightly better at faking human wording.
canjobear 3y ago
You could still come up with a scorecard for lossy compression, for example area under the rate distortion curve. It would be very hard to calculate.
- gregw134 3y ago
  Or just require the results to be 99.99 percent accurate (within some edit distance)
  - AnotherGoodName 3y ago
    If it's 99.99% accurate arithmetic coding would have next to no data stored. Arithmetic coding is optimal in turning probabilistic data into lossless data. There's provably no way to do it more efficiently than arithmetic coding. The data it needs for corrections is smaller the better the predictions are. So given this why even dwell on ways that add any form of subjectivity. Arithmetic coding is there. It's a simple algorithm.
- eru 3y ago
  Lossless compression _is_ a scorecard for lossy compression. Thanks to the ideas from arithmetic coding.
  - soVeryTired 3y ago
    There’s no way I could reproduce a calculus textbook verbatim, but I can probably prove all the important theorems in it. Even then, given half of any sentence in the book, I don’t rate my chances of reproducing the next half. That’s more a question of knowing the author’s style than knowing calculus itself. Does arithmetic coding capture all of that?
    - QuadmasterXLII 3y ago
      Yep
    - kaba0 3y ago
nathanfig 3y ago
"... lossless compression can be a scorecard of prediction which is the same as AGI." Having not read the papers, this sentence strikes me as a bit of a leap. Maybe for very constrained definitions of AGI?
- AnotherGoodName 3y ago
  There's a section in the link above "Further Recommended Technical Reading relevant to the Compression=AI Paradigm" and they define it in a reasonably precise mathematical way. It's well accepted at this point. If you can take input, predict what will happen given some options you can direct towards a certain goal. This ability to direct towards a goal effectively defines AGI. "Make paperclips" and the AI observes the world, what decisions needed to be made to optimize for output paperclips and then starts taking decisions to output paperclips is essentially what we mean by AGI and prediction is a piece of this. I have no stake in this btw, I've just had a crack at the above challenge in my younger days. I failed but i want to get back into it. In theory a small LLM model without any existing training data (for size) that trains itself on the input as it passes predictions to an arithmetic coder that optimally compresses and the same process on the decompression side should work really well here. But i don't have the time these days. Sigh.
  - mellosouls 3y ago
    This ability to direct towards a goal effectively defines AGI No it doesn't, though it may be argued to be a requirement. That's the point of the previous commenter - that you are making unjustified assertions using an extrapolation of the views of some researchers. Reiterating it with a pointer to why they believe that to be the case doesn't make it more so. If that's your favoured interpretation, fine, but that's all it is at this point.
    - AnotherGoodName 3y ago
      Hey don't pin this on me it's not my assertion. Go argue with the scientists who state pretty much what i just said verbatim including full links with proofs in http://prize.hutter1.net/hfaq.htm#ai http://prize.hutter1.net/hfaq.htm#ai :) >One can prove that the better you can compress, the better you can predict; and being able to predict [the environment] well is key for being able to act well. Consider the sequence of 1000 digits "14159...[990 more digits]...01989". If it looks random to you, you can neither compress it nor can you predict the 1001st digit. If you realize that they are the first 1000 digits of π, you can compress the sequence and predict the next digit. While the program computing the digits of π is an example of a one-part self-extracting archive, the impressive Minimum Description Length (MDL) principle is a two-part coding scheme akin to a (parameterized) decompressor plus a compressed archive. If M is a probabilistic model of the data X, then the data can be compressed (to an archive of) length log(1/P(X|M)) via arithmetic coding, where P(X|M) is the probability of X under M. The decompressor must know M, hence has length L(M). One can show that the model M that minimizes the total length L(M)+log(1/P(X|M)) leads to best predictions of future data. For instance, the quality of natural language models is typically judged by its Perplexity, which is equivalent to code length. Finally, sequential decision theory tells you how to exploit such models M for optimal rational actions. Indeed, integrating compression (=prediction) into sequential decision theory (=stochastic planning) can serve as the theoretical foundations of super-intelligence (brief introduction, comprehensive introduction, full treatment with proofs.
mellosouls 3y ago
Some background before i explain why your suggestion is "not even wrong". The phrase you quote is generally used to imply a stupid or unscientific suggestion. Your succeeding comments about what you think AGI is carry a certitude that isn't warranted. It's good that you are trying to supply knowledge where you think it is lacking, and I understand there are fora where this sort of public school lecturing is amusing but I think your tone is misplaced here.
- carapace 3y ago
  I feel your tone-policing is misplaced here. When someone is that ignorant or foolish they should be told so so they can hopefully recalibrate or something. There's enough inchoate nonsense on the Internet that I appreciate the efforts to keep discussion on a little higher level here.
  - p-e-w 3y ago
    > There's enough inchoate nonsense on the Internet I agree 100%. But the top-level comment is not an example of such. However, the reply in question – and your comment – are certainly examples of the kind of tone-deaf, needlessly aggressive, hostile, confrontational, and borderline malicious posts I wish I could cleanse the Internet of wholesale.
    - gfody 3y ago
      first two comments are the classic HN banter I’m here for, next two have stink on them I do not like
      - Dylan16807 3y ago
        Banter shouldn't be insulting for no good reason.
        ltbarcly3 3y ago
        Banter by definition is teasing, which insulting. That, along with being humorous in that context and not to be taken seriously is what makes it banter rather than any other form of exchange. Lets just go to the dictionary: Banter (n): the playful and friendly exchange of teasing remarks. Teasing (adj): intended to provoke or make fun of someone in a playful way.

version_five 3y ago

[flagged]

joshxyz 3y ago
Your comment is far more worse, lol. His comment actually supports gp's suggestion, just in a different angle. It looks like LLM's are like compression algorithms with strengths and weaknesses in different things. Losslessness doesnt always equate to usefulness. But yea, maybe a different competition for this.
AnotherGoodName 3y ago
Sorry but i hope my long-winded explanation explains it. In computer science we have a way to score how good lossy data is. That way is to make it lossless and look at how much data the arithmetic coder needed to correct it from lossy to lossless. This is a mathematically perfect way to judge (you can't correct lossy data any more efficiently than an arithmetic coder). All the entries here do in fact make probabilistic predictions on the data and they do all use arithmetic coding. So the suggestion misses a key point of CS involved here. I don't mean to be rude about it but the idea does need correcting.
- Dylan16807 3y ago
  > This is a mathematically perfect way to judge Only if you're using a very particular and honestly circular-sounding definition of "good". Some deviations are more important than others, even if you're looking at deviations that take the same amount of data to correct. Think about film grain. Some codecs can characterize it, remove it when compressing, and then synthesize new visually matching grain when decompressing. Let's say it takes a billion bytes to turn the lossy version back into the lossless version. The version with synthetic film grain still needs a billion bytes or maybe even slightly more bytes, even if the synthetic grain is 95% as good as real grain. The cost to turn it lossless is the wrong metric.

aeternum 3y ago

Is there any evidence that arithmetic coding works at the level of concepts? As a thought experiment, suppose Copernicus came up with this Hutter prize idea and declared that he would provide the award to whoever could compress the text of his book on the epicycle-based movement of planets around the sun (De revolutionibus orbium coelestium). Today we can explain the actual motion to high accuracy with a single sentence that would have been understandable in that age: "A line drawn from the sun to any planet sweeps out equal areas in equal time" This however is mostly useless in attempting to win the Copernican Hutter prize. Predicting the wording of some random human's choosing (especially at length) is very far removed from ability to predict in general.

AnotherGoodName 3y ago
Arithmetic coding isn't the key thing here. That's just a bit wise algorithm. You predict the next bit is a 1 with 90% certainty? you don't need to store much data with arithmetic coding. That's all arithmetic coding is here. What your getting at is the 'predictor' that feeds into the arithmetic coder and that's wide open and can work any way you want it to. LLMs absolutely have context which is similar to what your asking and they are good predictors of output given complex input (pass gpt a mathematical series and ask it what comes next. If it's right then it's really helpful in compression as you wouldn't need to store the whole series in full).
kaba0 3y ago
So you don’t think that writing a wiki article about this could be made smaller by encoding this info in a few logical steps, and adding some metadata on what kind of sentence should follow what? That part about decompressing it is the AI part. Where to place a comma can be added in constant cost between any contender programs.
- aeternum 3y ago
  Sure my point is more that this adding of commas business dwarfs any real prediction. Suppose there were a superintelligence that figured out the theory of everything for the universe. It's unclear that would actually help with this task. You could likely easily derive things like gravitaiton, chemistry, etc but the vast majority of your bits would still be used attempting to match the persona and wording of the various wikipedia authors. This superintelligence would be masked by some LLM that is slightly better at faking human wording.

canjobear 3y ago

You could still come up with a scorecard for lossy compression, for example area under the rate distortion curve. It would be very hard to calculate.

gregw134 3y ago
Or just require the results to be 99.99 percent accurate (within some edit distance)
- AnotherGoodName 3y ago
  If it's 99.99% accurate arithmetic coding would have next to no data stored. Arithmetic coding is optimal in turning probabilistic data into lossless data. There's provably no way to do it more efficiently than arithmetic coding. The data it needs for corrections is smaller the better the predictions are. So given this why even dwell on ways that add any form of subjectivity. Arithmetic coding is there. It's a simple algorithm.
eru 3y ago
Lossless compression _is_ a scorecard for lossy compression. Thanks to the ideas from arithmetic coding.
- soVeryTired 3y ago
  There’s no way I could reproduce a calculus textbook verbatim, but I can probably prove all the important theorems in it. Even then, given half of any sentence in the book, I don’t rate my chances of reproducing the next half. That’s more a question of knowing the author’s style than knowing calculus itself. Does arithmetic coding capture all of that?
  - QuadmasterXLII 3y ago
    Yep
  - kaba0 3y ago

nathanfig 3y ago

"... lossless compression can be a scorecard of prediction which is the same as AGI." Having not read the papers, this sentence strikes me as a bit of a leap. Maybe for very constrained definitions of AGI?

AnotherGoodName 3y ago
There's a section in the link above "Further Recommended Technical Reading relevant to the Compression=AI Paradigm" and they define it in a reasonably precise mathematical way. It's well accepted at this point. If you can take input, predict what will happen given some options you can direct towards a certain goal. This ability to direct towards a goal effectively defines AGI. "Make paperclips" and the AI observes the world, what decisions needed to be made to optimize for output paperclips and then starts taking decisions to output paperclips is essentially what we mean by AGI and prediction is a piece of this. I have no stake in this btw, I've just had a crack at the above challenge in my younger days. I failed but i want to get back into it. In theory a small LLM model without any existing training data (for size) that trains itself on the input as it passes predictions to an arithmetic coder that optimally compresses and the same process on the decompression side should work really well here. But i don't have the time these days. Sigh.
- mellosouls 3y ago
  This ability to direct towards a goal effectively defines AGI No it doesn't, though it may be argued to be a requirement. That's the point of the previous commenter - that you are making unjustified assertions using an extrapolation of the views of some researchers. Reiterating it with a pointer to why they believe that to be the case doesn't make it more so. If that's your favoured interpretation, fine, but that's all it is at this point.
  - AnotherGoodName 3y ago
    Hey don't pin this on me it's not my assertion. Go argue with the scientists who state pretty much what i just said verbatim including full links with proofs in http://prize.hutter1.net/hfaq.htm#ai http://prize.hutter1.net/hfaq.htm#ai :) >One can prove that the better you can compress, the better you can predict; and being able to predict [the environment] well is key for being able to act well. Consider the sequence of 1000 digits "14159...[990 more digits]...01989". If it looks random to you, you can neither compress it nor can you predict the 1001st digit. If you realize that they are the first 1000 digits of π, you can compress the sequence and predict the next digit. While the program computing the digits of π is an example of a one-part self-extracting archive, the impressive Minimum Description Length (MDL) principle is a two-part coding scheme akin to a (parameterized) decompressor plus a compressed archive. If M is a probabilistic model of the data X, then the data can be compressed (to an archive of) length log(1/P(X|M)) via arithmetic coding, where P(X|M) is the probability of X under M. The decompressor must know M, hence has length L(M). One can show that the model M that minimizes the total length L(M)+log(1/P(X|M)) leads to best predictions of future data. For instance, the quality of natural language models is typically judged by its Perplexity, which is equivalent to code length. Finally, sequential decision theory tells you how to exploit such models M for optimal rational actions. Indeed, integrating compression (=prediction) into sequential decision theory (=stochastic planning) can serve as the theoretical foundations of super-intelligence (brief introduction, comprehensive introduction, full treatment with proofs.

mellosouls 3y ago

Some background before i explain why your suggestion is "not even wrong". The phrase you quote is generally used to imply a stupid or unscientific suggestion. Your succeeding comments about what you think AGI is carry a certitude that isn't warranted. It's good that you are trying to supply knowledge where you think it is lacking, and I understand there are fora where this sort of public school lecturing is amusing but I think your tone is misplaced here.

carapace 3y ago
I feel your tone-policing is misplaced here. When someone is that ignorant or foolish they should be told so so they can hopefully recalibrate or something. There's enough inchoate nonsense on the Internet that I appreciate the efforts to keep discussion on a little higher level here.
- p-e-w 3y ago
  > There's enough inchoate nonsense on the Internet I agree 100%. But the top-level comment is not an example of such. However, the reply in question – and your comment – are certainly examples of the kind of tone-deaf, needlessly aggressive, hostile, confrontational, and borderline malicious posts I wish I could cleanse the Internet of wholesale.
  - gfody 3y ago
    first two comments are the classic HN banter I’m here for, next two have stink on them I do not like
    - Dylan16807 3y ago
      Banter shouldn't be insulting for no good reason.
      - ltbarcly3 3y ago
        Banter by definition is teasing, which insulting. That, along with being humorous in that context and not to be taken seriously is what makes it banter rather than any other form of exchange. Lets just go to the dictionary: Banter (n): the playful and friendly exchange of teasing remarks. Teasing (adj): intended to provoke or make fun of someone in a playful way.