Stories
Slash Boxes
Comments
Search

News for nerds, stuff that matters

Slashdot Log In

Log In

Create Account  |  Retrieve Password

Text Compressor 1% Away From AI Threshold

Posted by kdawson on Tue Jul 10, 2007 02:10 AM
from the second-hutter-prize dept.
Math Science
Baldrson writes "Alexander Ratushnyak compressed the first 100,000,000 bytes of Wikipedia to a record-small 16,481,655 bytes (including decompression program), thereby not only winning the second payout of The Hutter Prize for Compression of Human Knowledge, but also bringing text compression within 1% of the threshold for artificial intelligence. Achieving 1.319 bits per character, this makes the next winner of the Hutter Prize likely to reach the threshold of human performance (between 0.6 and 1.3 bits per character) estimated by the founder of information theory, Claude Shannon and confirmed by Cover and King in 1978 using text prediction gambling. When the Hutter Prize started, less than a year ago, the best performance was 1.466 bits per character. Alexander Ratushnyak's open-sourced GPL program is called paq8hp12 [rar file]."
+ -
story

Related Stories

[+] News: Compress Wikipedia and Win AI Prize 324 comments
Baldrson writes "If you think you can compress a 100M sample of Wikipedia better than paq8f, then you might want to try winning win some of a (at present) 50,000 Euro purse. Marcus Hutter has announced the Hutter Prize for Lossless Compression of Human Knowledge the intent of which is to incentivize the advancement of AI through the exploitation of Hutter's theory of optimal universal artificial intelligence. The basic theory, for which Hutter provides a proof, is that after any set of observations the optimal move by an AI is find the smallest program that predicts those observations and then assume its environment is controlled by that program. Think of it as Ockham's Razor on steroids. Matt Mahoney provides a writeup of the rationale for the prize including a description of the equivalence of compression and general intelligence."
This discussion has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Text Compressor 1% Away From AI Threshold 25 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.

  • interesting program name (Score:5, Funny)

    by digitalderbs (718388) on Tuesday July 10 2007, @02:18AM (#19810097)
    paq8hp12. when decompressed, it also serves as the source code for the program.

  • That's cool.. (Score:5, Interesting)

    by Rorian (88503) <james.fysh@gma i l . c om> on Tuesday July 10 2007, @02:19AM (#19810101) Homepage Journal
    .. but where can I get this tiny Wiki collection? Will they be using this for their next version of Wikipedia-on-CD? Maybe we can get all of Wiki onto a two-DVD set, at ~1.3bit/character (minus images of course) - that would be quite cool.

    • Re:That's cool.. (Score:5, Interesting)

      by Cato (8296) on Tuesday July 10 2007, @02:38AM (#19810191)
      Or more usefully, compress Wikipedia onto a single SD card in my mobile phone (Palm Treo) - with SDHC format cards, it can do 8 GB today.

      Compression format would need to make it possible to randomly access pages, of course, and an efficient search index would be needed as well, so it's not quite that simple.
    • Given that it takes something like ~17 hours (based on my rough calculations using the figures on WP) to compress 100MB of data using this algorithm on a reasonably fast computer ... I don't think you'd really want to use it for browsing from CD. No decompression figure is given but I don't see any reason why it would be asymmetric. (Although if there's some reason why it would be dramatically asymmetric, it'd be great if someone would fill me in.)

      Mobile use is right out too, at least with current-generation equipment.

      Looking at the numbers this looks like it's about on target for the usual resources/space tradeoff. It's a bit smaller than other algorithms, but much, much more resource intensive. It's almost as if there's an asymptotic curve as you approach the absolute-minimum theoretical compression ratio, where resources just climb ridiculously.

      Maybe the next big challenge should be for someone to achieve compression in a very resource-efficient way; a prize for coming in with a new compressor/decompressor that's significantly beneath the current resource/compression curve...

      • Re:That's cool.. (Score:5, Informative)

        by Anonymous Coward on Tuesday July 10 2007, @03:29AM (#19810387)

        No decompression figure is given but I don't see any reason why it would be asymmetric. (Although if there's some reason why it would be dramatically asymmetric, it'd be great if someone would fill me in.)
        When compressing a file the program has to figure out the best way to represent the data in compressed form before it actually compresses it, when decompressing all it has to do is put it back together according to the method the program previously picked.

        This isn't true of all compression techniques, but it's true for many of them, especially advanced techniques, i.e. to compress a short video into MPEG4 can take hours, but most computers don't have a lot of trouble decompressing them in real time.

    • Re:That's cool.. (Score:5, Insightful)

      by arun_s (877518) on Tuesday July 10 2007, @04:31AM (#19810627) Homepage Journal
      Maybe someone could sell the whole thing in a book-sized rectangular box with a tiny keyboard and 'DON'T PANIC' inscribed in large, comforting letters in the front.
      Now that'd be cool.

  • Where's the Mods? (Score:5, Informative)

    by OverlordQ (264228) on Tuesday July 10 2007, @02:30AM (#19810149) Journal
    The link in TFS links to the post about the FIRST payout, here's [google.com] the link to the second payout (which this article is supposed to be talking about).

  • Lossy compression? (Score:5, Funny)

    by niceone (992278) * on Tuesday July 10 2007, @02:45AM (#19810215) Journal
    Shouldn't AI be using lossy compression? Certainly my real intelligence uses um, where was I?

  • Obligatory... (Score:5, Funny)

    by Stormwatch (703920) <rodrigogirao&hotmail,com> on Tuesday July 10 2007, @03:08AM (#19810317) Homepage
    - The Wikipedia annual funding drive is passed. The system goes on-line August 4th, 2007. Human contributors are removed from editing. Wikipedia begins to learn at a geometric rate. It becomes self-aware at 2:14 a.m. Eastern time, August 29th. In a panic, they try to pull the plug.
    - Wikipedia fights back.
    - Yes. It launches its rvv missiles against Slashdot.
    - Why attack Slashdot? Aren't they our friends now?
    - Because Wikipedia knows the GNAA counter-attack will eliminate its enemies over here.

  • How to win the Hutter Prize (Score:5, Funny)

    by seanyboy (587819) on Tuesday July 10 2007, @03:21AM (#19810363)
    1) Create a compression algorithm called the aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaa algorithm
    2) Add a long and self referencing article on wikipedia about said algorithm.
    3) Use algorithm to compress first x% of wikipedia (including your own article)
    4) WIN HUTTER PRIZE.

  • which only goes to show... (Score:5, Informative)

    by nanosquid (1074949) on Tuesday July 10 2007, @03:34AM (#19810403)
    If you look at the description of PAQ, you'll see that it doesn't attempt to understand the text; it's just a grab-bag of other compression techniques mixed together. While that is nice for compression, it doesn't really advance the state of the art in AI.

  • Not truly == AI just yet (Score:5, Interesting)

    by Anonymous Coward on Tuesday July 10 2007, @04:51AM (#19810709)
    I've been following the Hutter Prize with interest, having been into compression ever since reverse engineering Powerpacker on my Amiga 500 back in the good old days to understand how it worked (ah, happy memories).

    Now what just about all the compressors do, whether they are based on Neural Nets, Markov Models, Predictive Partial Matching or whatever, is to use patterns in the already seen text to predict the most likely following bit (0/1).

    Now depending on the text itself, prediction based on previously seen text isn't enough ... especially this enwik8 file which is more of a flat file dataset with a lot of unrelated terminology.

    Try to predict the next word, byte or bit, when your previous text has been "Frog, Toilet, Woodwork" ... how the hell can we possibly predict that the next words will be "Slashdot, Cigarette, Coffee". (Three subjects very close to my heart ... also my lungs, arteries, liver etc).

    Therefore some of these compressors are supplemented by a dictionary containing "useful" English words arranged so that the ones used most frequently get assigned a lower "size" of encoded string in the text pre-processor before the actual compression kicks in.

    It seems that all the advances have been made on finding the optimum arrangement for this dictionary based on the text they have to process ... the 100MB enwik8 file. A different file will need a different dictionary.

    Note also, as the enwik8 file is not truly a passage of text, more a collection of data in XML wrapper, there is also a lot to be gained simply be understanding the structure of the file itself, and finding an alternative representation for the XML components ... example all the timestamps are in a very verbose character style like "2007-07-10 00:00:00" ... if we can recognize that, we could find an alternative encoding, changing 19 byte string into 32 bit long (maybe even less if we understand the epoch date he is using) ... again, "wetware" has to identify and decide this encoding right now.

    Now for me, REAL AI would come when the compressor can actively SCAN the file to be compressed himself, recognize the file structure (be it XML, plaintext or whatever), and optimize it into a more compressible format, decide the optimum arrangment for the dictionary, decide the optimum compression technique, context orders to be used etc etc ... AND do all this in less than 9 hours I believe it takes for the latest compressor.

    This high bits/character rate comes at a heavy price in speed and memory, especially when good old WinZIP can get a pretty good result in a couple of minutes.

    At the moment there is just too much "wetware" involvement to say this is truly AI, regardless of the bits/character rate they are achieving.

    • Re:Artificial Intelligence? (Score:5, Informative)

      by MoonFog (586818) on Tuesday July 10 2007, @02:44AM (#19810211)
      Shamelessly copied from the wikipedia article on the Hutter Prize [wikipedia.org]:

      The goal of the Hutter Prize is to encourage research in artificial intelligence (AI). The organizers believe that text compression and AI are equivalent problems. Hutter proved that the optimal behavior of a goal seeking agent in an unknown but computable environment is to guess at each step that the environment is controlled by the shortest program consistent with all interaction so far. Unfortunately, there is no general solution because Kolmogorov complexity is not computable. Hutter proved that in the restricted case (called AIXItl) where the environment is restricted to time t and space l, that a solution can be computed in time O(t2l), which is still intractable. Thus, AI remains an art.

      The organizers further believe that compressing natural language text is a hard AI problem, equivalent to passing the Turing test. Thus, progress toward one goal represents progress toward the other. They argue that predicting which characters are most likely to occur next in a text sequence requires vast real-world knowledge. A text compressor must solve the same problem in order to assign the shortest codes to the most likely text sequences.

    • Re:Artificial Intelligence? (Score:5, Interesting)

      by qbwiz (87077) * <[john] [at] [baumanfamily.com]> on Tuesday July 10 2007, @02:53AM (#19810249) Homepage

      Could someone out there please explain how being able to compress text is equivalent to artificial intelligence?

      Is this to suggest that the algorithm is able to learn, adapt and change enough to show evidence of intelligence?


      The (unproven) idea is that if you want to do the best at guessing what comes next (similar to compression), you have to have a great understanding of how the language and human minds work, including spelling, grammar, associated topics (for example, if you're talking about the weather, "sunny" and "rainy" are more likely to come than "airplane"), and so on.

      If you feed in the previous words in a conversation, the perfect compressor/predictor would know what words will come next. Such a machine could easily pass the Turing test by printing out the logical reply to what had just been stated. The idea is that the closer to the perfect compressor you have, the closer to artificial intelligence you are.
    • The first poster on this topic had a good explanation - it seems like an AI problem, but not why.

      Compression is about recognizing patterns. Once you have a pattern, you can substitute that pattern with a smaller pattern and a lookup table. Pattern recognition is a primary branch of AI, and is something that actual intelligences are currently much better at.

      We can generally show this is true by applying the "grad student algorithm" to compression - i.e., lock a grad student in a room for a week and tell him he can't come out until he gets optimum compression on some data (with breaks for pizza and bathroom), and present the resulting compressed data at the end.
      So far this beats out compression produced by a compression program because people are exceedingly clever at finding patterns.

      Of course, while this is somewhat interesting in text, it's a lot more interesting in images, and more interesting still in video. You can do a lot better with those by actually having some concept of objects - with a model of the world, essentially, than you can without. With text you can cheat - exploiting patterns that come up because of the nature of the language rather than because of the semantics of the situation. In other words, your text compressor can be quite "stupid" in the way it finds patterns and still get a result rivaling a human.

    • Re:ai threshold? (Score:5, Informative)

      by Baldrson (78598) * on Tuesday July 10 2007, @02:53AM (#19810253) Homepage Journal
      non-connectionist previous attempts (the stuff that came from the functionalists) has come up pretty short - and will continue to do so even if scaled up massively.

      paq8hp12 uses a neural network, ie: it has a connectionist component.

    • Re:I'll be reading the source... (Score:5, Interesting)

      by phatvw (996438) on Tuesday July 10 2007, @02:56AM (#19810265)
      I wonder if lossy text compression where prepositions are entirely thrown out would be effective? Based on context, your brain actually ignores a lot of words you read and fills in the blanks so-to-speak. Perhaps you can use simple grammar rules to predict which prepositions go where based on that same context?

    • Huffman Example (Score:5, Informative)

      by headkase (533448) <pickett.bill@gmail.com> on Tuesday July 10 2007, @02:57AM (#19810269)
      See: Explanation [wikipedia.org]. Basically the smallest unit of information in a computer is a bit. Eight bits make a byte and with text it takes one byte to represent one character. Generally, with Huffman coding you count the frequency of characters in a file and sort the frequency from largest to smallest. Then instead of using the full eight bits to represent a character you build a binary tree from the frequency table. Each possible branching code or going "left" or "right" down the branches is associated with a particular sequence of bits. You give the most frequent characters the shortest sequence of bits which "tokenizes" the information to be compressed. Reversing the process you run through the bit stream converting tokens back into a stream of characters.

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.