6 ms·

This competition is flawed in the context of artificial intelligence. Most of the information in the Wikipedia text is in the language, not in the 'actual' know

by Geee 13y ago

This competition is flawed in the context of artificial intelligence. Most of the information in the Wikipedia text is in the language, not in the 'actual' knowledge. It would be much more interesting competition if it would allow the uncompressed text to say the same things in different words. Although there's the problem of how to verify if it's the same thing.

Houshalter 13y ago
Compression is closely related to intelligence. In order to compress something you have to understand the pattern behind it. The better you can learn the pattern, the better you can compress.
- psb217 13y ago
  Lossy compression, yes. Lossless compression, not so much. And, the parent post seems to have been hinting at this. I.e. being able to usefully "tl;dr" all of Wikipedia would require a rather intelligent system. But, recapitulating all of Wikipedia's content word-for-word and pixel-for-pixel (including page layout for the truly pedantic) would not meaningfully test the sort of abstract pattern recognition that you seem to be confusing with lossless compression. In other words, though often conflated, information and meaning are not equivalent. "Meaning", as people typically use the word, seems to include some concept of the utility of a bit of information. Most information in typical text/images/sounds/etc. is really quite useless. Being able to discard the useless while keeping the useful actually seems like one of the key traits exhibited by intelligent systems, and this ability is not measured (and perhaps even selected against) by lossless compression performance.
  - Houshalter 13y ago
    Loseless compression may not be as useful as a summarizing algorithm, but it is definitely a test of intelligence. Lossless compression requires identifying the pattern that produced an input as perfectly as possible. If you have an algorithm that can predict the next letter with great probability, you only only need a few bits to store a string of text. And making good predictions on real world data is a good test of AI and machine learning.
    - psb217 13y ago
      "Lossless compression requires identifying the pattern that produced an input as perfectly as possible": no, it requires identifying it absolutely perfectly. This includes all vacuous information as well. E.g., in the Wikipedia example, if there were a 2d scatter plot of a sample from a bivariate uniform distribution, lossless compression would require "memorizing" all of the plotted points. Predicting perfectly is much, much different from predicting well. Machine learning is about the latter, while lossless compression is about the former.
      - Houshalter 13y ago
        This is not true. If you have a good predictor, you only need a few bits to store a piece of information. One way is just to record the places where your prediction is wrong. The ideal way would be to split all the possibilities so exactly half of possible sequences are on one side, and exactly half the probability is on the other. Every bit tells you what path to go down. So instead of using 64 bits to specify the x y coordinates of every point on the plot, you could just use a much smaller number to represent how far it diverges from it's predicted location. You could narrow down the possible locations the point could be in by half, and then you just bits to specify only those possibilities, not all of them.
hcarvalhoalves 13y ago
> Most of the information in the Wikipedia text is in the language, not in the 'actual' knowledge. Exactly, I see the same problem. With the current rules, this is just a challenge of text compression. I believe compressing the knowledge in the Wikipedia would be more akin to extracting meaning with NLP into a highly-normalized dataset, and then compressing that. From an AI perspective, this is more close to how our memory actually works. Unless you're savant, you don't memorize the actual text of a topic, but the inferred associations, which compress much better, although lossy.
- darkmighty 13y ago
  You give lossless compressors too little credit. An optimal text compressor (with a sane running time) should be able to "understand" the context to generate a density function over words close to the true one to encode optimally. The lossy one if optimal in some manner should generate this same density but it would use an error metric to achieve a "rate-distortion" boundary, and encode optimally based on the desired position on that boundary. So what separates the two is the error metric, in other words, how much humans would bother if you replaced y for x. But this involves humans, not general intelligence -- you'd need a lot of testing with actual humans to get good results (jpeg has extensive testing to find optimal quantizers for chroma values based on human perception, for example). Not that the latter would not be interesting too; I just think it's less practical. Relevant: http://www.stanford.edu/class/ee368b/Handouts/04-RateDistortionTheory.pdf http://www.stanford.edu/class/ee368b/Handouts/04-RateDistort...
  - hcarvalhoalves 13y ago
    I had something else in mind, I think the parent thought that too. Imagine, for instance, how many articles there are about how A has relation R with C, and B also (e.g., George Washington was a president of the USA, Abraham Lincoln also). For some definition of "understanding", you wouldn't need to encode data about the text of both articles A and B, you could use NLP to somehow store just the ontology. The problem would change from encoding text to encoding a graph. So it would be a lossy process (because you wouldn't be able to decompress into the original Wikipedia), but in my opinion seems more relevant to AI than bothering with the original corpus.
apw 13y ago
The codebook of a lossless predictive coding system is exactly "say[ing] the same things in different words".

by Geee 13y ago

Houshalter 13y ago

Compression is closely related to intelligence. In order to compress something you have to understand the pattern behind it. The better you can learn the pattern, the better you can compress.

psb217 13y ago
Lossy compression, yes. Lossless compression, not so much. And, the parent post seems to have been hinting at this. I.e. being able to usefully "tl;dr" all of Wikipedia would require a rather intelligent system. But, recapitulating all of Wikipedia's content word-for-word and pixel-for-pixel (including page layout for the truly pedantic) would not meaningfully test the sort of abstract pattern recognition that you seem to be confusing with lossless compression. In other words, though often conflated, information and meaning are not equivalent. "Meaning", as people typically use the word, seems to include some concept of the utility of a bit of information. Most information in typical text/images/sounds/etc. is really quite useless. Being able to discard the useless while keeping the useful actually seems like one of the key traits exhibited by intelligent systems, and this ability is not measured (and perhaps even selected against) by lossless compression performance.
- Houshalter 13y ago
  Loseless compression may not be as useful as a summarizing algorithm, but it is definitely a test of intelligence. Lossless compression requires identifying the pattern that produced an input as perfectly as possible. If you have an algorithm that can predict the next letter with great probability, you only only need a few bits to store a string of text. And making good predictions on real world data is a good test of AI and machine learning.
  - psb217 13y ago
    "Lossless compression requires identifying the pattern that produced an input as perfectly as possible": no, it requires identifying it absolutely perfectly. This includes all vacuous information as well. E.g., in the Wikipedia example, if there were a 2d scatter plot of a sample from a bivariate uniform distribution, lossless compression would require "memorizing" all of the plotted points. Predicting perfectly is much, much different from predicting well. Machine learning is about the latter, while lossless compression is about the former.
    - Houshalter 13y ago
      This is not true. If you have a good predictor, you only need a few bits to store a piece of information. One way is just to record the places where your prediction is wrong. The ideal way would be to split all the possibilities so exactly half of possible sequences are on one side, and exactly half the probability is on the other. Every bit tells you what path to go down. So instead of using 64 bits to specify the x y coordinates of every point on the plot, you could just use a much smaller number to represent how far it diverges from it's predicted location. You could narrow down the possible locations the point could be in by half, and then you just bits to specify only those possibilities, not all of them.

hcarvalhoalves 13y ago

> Most of the information in the Wikipedia text is in the language, not in the 'actual' knowledge. Exactly, I see the same problem. With the current rules, this is just a challenge of text compression. I believe compressing the knowledge in the Wikipedia would be more akin to extracting meaning with NLP into a highly-normalized dataset, and then compressing that. From an AI perspective, this is more close to how our memory actually works. Unless you're savant, you don't memorize the actual text of a topic, but the inferred associations, which compress much better, although lossy.

darkmighty 13y ago
You give lossless compressors too little credit. An optimal text compressor (with a sane running time) should be able to "understand" the context to generate a density function over words close to the true one to encode optimally. The lossy one if optimal in some manner should generate this same density but it would use an error metric to achieve a "rate-distortion" boundary, and encode optimally based on the desired position on that boundary. So what separates the two is the error metric, in other words, how much humans would bother if you replaced y for x. But this involves humans, not general intelligence -- you'd need a lot of testing with actual humans to get good results (jpeg has extensive testing to find optimal quantizers for chroma values based on human perception, for example). Not that the latter would not be interesting too; I just think it's less practical. Relevant: http://www.stanford.edu/class/ee368b/Handouts/04-RateDistortionTheory.pdf http://www.stanford.edu/class/ee368b/Handouts/04-RateDistort...
- hcarvalhoalves 13y ago
  I had something else in mind, I think the parent thought that too. Imagine, for instance, how many articles there are about how A has relation R with C, and B also (e.g., George Washington was a president of the USA, Abraham Lincoln also). For some definition of "understanding", you wouldn't need to encode data about the text of both articles A and B, you could use NLP to somehow store just the ontology. The problem would change from encoding text to encoding a graph. So it would be a lossy process (because you wouldn't be able to decompress into the original Wikipedia), but in my opinion seems more relevant to AI than bothering with the original corpus.

apw 13y ago

The codebook of a lossless predictive coding system is exactly "say[ing] the same things in different words".