Stories
Slash Boxes
Comments
Search

News for nerds, stuff that matters

Slashdot Log In

Log In

Create Account  |  Retrieve Password

Compress Wikipedia and Win AI Prize

Posted by CmdrTaco on Sun Aug 13, 2006 05:50 PM
from the what-does-this-mean dept.
The Almighty Buck IT
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."
+ -
story

Related Stories

[+] Science: Text Compressor 1% Away From AI Threshold 442 comments
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]."
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.

Compress Wikipedia and Win AI Prize 50 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.

  • I'd love to be able to have the whole WikiPedia available on my iPod (or cell phone), but without destroying [sourceforge.net]

    info.edu.org [edu.org] - Speedy information and news from the Top 10 educational organisations.

    • Then it would be an encyclopedia, not a Wiki, thats another point why I say: forget about it. Would be nice though. ;)

    • Re:WikiPedia on iPod! (Score:4, Insightful)

      by CastrTroy (595695) on Sunday August 13 2006, @06:25PM (#15899896) Homepage
      Well, since it's currently only 1 Gig, you could probably put it on a flash card and read it from a handheld. It wouldn't be an ipod. but probably wouldn't require destroying a perfectly good piece of equipment either. You could probably even get weekly updates (hopefully in a diff file) to make sure your copy is in sync with the rest of the internet. Now that I think about it, this would be a really good application. There's lots of times when I'd like to look up something off wikipedia, but not connected to the internet.

  • But captain (Score:5, Funny)

    by Anonymous Coward on Sunday August 13 2006, @05:52PM (#15899787)
    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.

    But captain, if we reverse the tachyon inverter drives then we will have insufficient dilithium crystals to traverse the neutrino warp.

    • Re:But captain (Score:5, Funny)

      by Anonymous Coward on Sunday August 13 2006, @06:09PM (#15899836)
      You left out the part involving the deflector shield. Remember, the first rule of star trek technobabel is always involve the deflector in some way.

  • Painful to read (Score:4, Insightful)

    by CuriHP (741480) on Sunday August 13 2006, @05:54PM (#15899793)
    For the love of god, proofread!

  • lossy compression (Score:5, Insightful)

    by RenoRelife (884299) on Sunday August 13 2006, @05:55PM (#15899798)
    Using the same data lossy compressed, with an algorithm that was able to permute data in a similar way to the human mind, seems like it would come closer to real intelligence than the lossless compression would

    • Re:lossy compression (Score:3, Insightful)

      by Anonymous Coward
      Funny? That's most intelligent and insightful remark I've seen here in months, albeit rather naively stated.
      The human brain is a fuzzy clustering algorithm, that's what neural networks do, they reduce the space of a large
      data set by eliminating redundancy and mapping only the salient features of it onto a smaller data set, which in bio systems
      is the weights for triggering sodium/potassium spikes at a given junction. If such a thing existed a neural compression algorithm would be capable of immense data red
    • that's one piece, but not necessarily - "lossy" nature of human mind compression can be overcome by "additional checks".

      Lossy relational/dictionary based compression is the base. You hardly ever remember text by order of letters or sound of voice reading it. You remember the meaning of a sentence, plus optionally some rough pattern (like voice rhythm) to reproduce the exact text from rewording the meaning. So you understand meaning of sentence, store it as relation to known meanings (pointers to other entri

      • Re:lossy compression (Score:5, Insightful)

        by swillden (191260) * <shawn-ds@willden.org> on Sunday August 13 2006, @10:14PM (#15900595) Homepage Journal

        You just need to re-create afile that matches the md5sum and still follows the rules of a Linux kernel. It is extremely unlikely any other file that can be recognized as some kind of Linux kernel and matches. Of course there are countless blocks of data that still match, but very few will follow the ruleset of "ELF kernel executable" structure which can be deduced numerically.

        Mmmm, no. You were fine up until you said "very few will follow the ruleset". That's not true. To see that it's not true, take your kernel, which consists of around 10 million bits. Now find, say, 512 of those bits that can be changed, independently, while still producing a valid-looking kernel executable. The result doesn't even have to be a valid, runnable kernel, but it wouldn't be too hard to do it even with that restriction.

        So you now have 2^512 variants of the Linux kernel, all of which look like a valid kernel. But there are only 2^128 possible hashes, so, on average, there will be four kernels for each hash value, and the odds are very, very good that your "real" kernel's hash is also matched by at least one of them. If by some chance it isn't, I can always generate a whole bunch more kernel variants. How about 2^2^10 of them?

        A hash plus a filter ruleset does not constitute a lossless compression of a large file, even if computation power/time is unbounded.



  • There. All of wiki, in 31 bytes.

  • Who'da thunk... (Score:5, Funny)

    by blueadept1 (844312) on Sunday August 13 2006, @05:59PM (#15899809)
    Man, WinRar is taking its bloody time. But oh god, when its done, I'll be rich!
    • Damn you and your WinRAR! When is the deadline? WinRK says it needs 3 days 14 hours, you might be finished before then, but I'll surely take the prize... when it's done®

  • Lossy Compression? (Score:4, Funny)

    by Millenniumman (924859) on Sunday August 13 2006, @06:06PM (#15899826)
    Convert it to AOL! tis wikpedia, teh fri enpedia . teh bst in da wrld.
  • There are some amazing compression programs out there, trouble is they tend to take a while and consume lots of memory. PAQ [fit.edu] gives some impressive results, but the latest benchmark figures [maximumcompression.com] are regularly improving. Let's not forget that compression is not good unless it is integrated into a usable tool. 7-zip [7-zip.org] seems to be the new archiver on the block at the moment. A closely related, but different, set of tools are the archivers [freebsd.org], of which there are lots with many older formats still not supported by open s

  • It's a big world out there (Score:5, Interesting)

    by Harmonious Botch (921977) on Sunday August 13 2006, @06:09PM (#15899835) Homepage Journal
    "The basic theory...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." In a finite discrete environment ( like Shurdlu: put the red cylinder on top of the blue box ) that may be possible. But in the real world the problem is knowing that one's observations are all - or even a significant percentage - of the possible observations.
    This - in humans, at least - can lead to the cyclic reinforcement of one's belief system. The belief system that explains observations initially is used to filter observations later.

    TFA is a neat idea theoreretically, but it's progeny will never be able to leave the lab.

    --
    I figured out how to get a second 120-byte sig! Mod me up and I'll tell you how you can have one too.
    • But in the real world the problem is knowing that one's observations are all - or even a significant percentage - of the possible observations.

      This is precisely the assumption of Hutter's theory.

      Chapter 2 of his book "Simplicity & Uncertainty" deals with this in more detail but the link provided does do an adequate job of stating:

      The universal algorithmic agent AIXI. AIXI is a universal theory of sequential decision making akin to Solomonoff's celebrated universal theory of induction. Solomonoff d

    • This - in humans, at least - can lead to the cyclic reinforcement of one's belief system. The belief system that explains observations initially is used to filter observations later.

      There is no allowance for lossy compression. The requirement of lossless compression is there for precisely the reason you state.

    • Re:It's a big world out there (Score:5, Funny)

      by gardyloo (512791) on Sunday August 13 2006, @06:54PM (#15899973)
      TFA is a neat idea theoreretically, but it's progeny will never be able to leave the lab.

            Your use of "TFA" is a good compressional technique, but you could change "it's" to "its" and actually GAIN in meaning while losing a character! You're well on your way...

    • Re:It's a big world out there (Score:5, Informative)

      by DrJimbo (594231) on Sunday August 13 2006, @07:13PM (#15900036)
      Harmonious Botch said:
      This - in humans, at least - can lead to the cyclic reinforcement of one's belief system. The belief system that explains observations initially is used to filter observations later.
      I encourage you to read E. T. Jaynes' book: Probability Theory: The Logic of Science [amazon.com]. It used to be available on the Web in pdf form before a published version became available.

      In it, Jaynes shows that an optimal decision maker shares this same tendency of reinforcing exiting belief systems. He even gives examples where new information reinforces the beliefs of optimal observers who have reached opposite conclusions (due to differing initial sets of data). Each observer believes the new data further supports their own view.

      Since even an optimal decision maker has this undesirable trait, I don't think the existence of this trait is a good criteria for rejecting decision making models.

      • In it, Jaynes shows that an optimal decision maker shares this same tendency of reinforcing exiting belief systems. He even gives examples where new information reinforces the beliefs of optimal observers who have reached opposite conclusions (due to differing initial sets of data). Each observer believes the new data further supports their own view.

        I think what Hutter has shown is that there is a solution which unifies the new data with the old within a new optimum, which is most likely unique. I think

    • I think the original premise is wrong. Real world intelligence is not lossless. The algorithms only have to be right most of the time to be effective. And our intelligence is incredibly redundant. If you want robust AI, you're going to have to accept redundancy and imperfection. Same goes for data transmission. Sure, you compress, but then you also add in self-error correcting codes with a level on redundancy based on the known reliability of the network.

  • Er, I'm not so sure about this. (Score:4, Interesting)

    by aiken_d (127097) <aiken@NOSpAm.bondage.com> on Sunday August 13 2006, @06:15PM (#15899857) Homepage
    Given that the hypothesis is valid (which is arguable), it seems to me that compressing wikipedia is a fairly useless way of supporting it. It seems like an abstraction error: Wikipedia is *not* a set of rules that predict the observations in it. It's a list of observations, sure, but there's no ruleset involved. Now, someone/thing who can read and parse language can get educated based on the knowledge in wikipedia, but then the intelligence is providing the ruleset, just training itself with the raw data in wiki.

    It really seems like one of those mistaking-the-map-for-the-territory errors.

    -b

  • Solution. (Score:5, Funny)

    by Funkcikle (630170) on Sunday August 13 2006, @06:34PM (#15899916)
    Removing all the incorrect and inaccurate data from the Wikipedia sample should "compress" it down to at least 20mb.

    Then just apply your personal favourite compression utility.

    I like lharc, which according to Wikipedia was invented in 1904 as a result of bombarding President Lincoln, who plays Commander Tucker in Star Trek: Enterprise with neutrinos.

  • Incentivize? (Score:5, Funny)

    by noidentity (188756) on Sunday August 13 2006, @06:47PM (#15899952)
    the intent of which is to incentivize the advancement of AI

    Sorry, anything which uses the word "incentivize" does not involve intelligence, natural or artificial.

  • I'll try: (Score:5, Funny)

    by dcapel (913969) on Sunday August 13 2006, @06:59PM (#15899986) Homepage
    echo "!#/bin/sh\nwget en.wikipedia.org/enwiki/" > archive

    Mine wins as it is roughly 40 bytes total.To get your results, you simply need to run the self-extracting archive, and wait. Be warned, it will take a while, but that is the cost of such a great compression scheme!

  • C++ (Score:3, Funny)

    by The Bungi (221687) <thebungi@gmail.com> on Sunday August 13 2006, @07:32PM (#15900103) Homepage
    Interestingly enough, the source code [fit.edu] for the compressor is C++. One would expect the thing to be written in pure C.

    A (good) sign of the times, I guess.

  • Hutter's Theory - Disproved (Score:4, Insightful)

    by giafly (926567) on Sunday August 13 2006, @09:57PM (#15900538)
    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.
    A "Hutter AI" will be at a disadvantage when competing against an opponent which knows it's acting as above and can do the same calculations. Under these circumstances, the opponent will be one step ahead. The Hutter AI is predictable and so can be outmanoeuvered. Hence the Hutter AI's moves are not optimal.

    Human poker players address this issue by deliberately introducing slight randomness into their play. I think a "Hutter AI" will make better real-world decisions if it does the same (see Game Theory).

    Occam's razor (also spelled Ockham's razor) is a principle attributed to the 14th-century English logician and Franciscan friar William of Ockham. Originally a tenet of the reductionist philosophy of nominalism, it is more often taken today as a heuristic maxim that advises economy, parsimony, or simplicity in scientific theories. Occam's razor states that the explanation of any phenomenon should make as few assumptions as possible - Wikepedia [wikipedia.org]
    Occam's razor is also highly suspect. There's the issue of cultural bias when counting assumptions. And all programmers will be aware of how they fixed "the bug" that caused all the problems in an application, only to find there were other bugs that caused identical symptoms.

  • Compress Wikipedia and win a prize? (Score:5, Funny)

    by Dachannien (617929) on Sunday August 13 2006, @09:59PM (#15900551)
    Can't I just punch the monkey for $20 instead?

    • Re:Can it be "lossy" compression? (Score:5, Funny)

      by Bill Kilgore (914825) on Sunday August 13 2006, @06:22PM (#15899879)
      I have a program that compresses 100M of Wikipedia to one bit with no loss at all. The program is somewhat special-purpose, and at 100,024,076 bytes, a little chunkier than I'd like.

      • Wrong contest (Score:4, Informative)

        by Baldrson (78598) * on Sunday August 13 2006, @06:55PM (#15899977) Homepage Journal
        That's another contest that is useless for the reason you cite.

        The contest for the Hutter Prize requires the compressed corpus to be a self-extracting archive -- or failing that to add the size of the compressor to the compressed corpus.

          • See the detailed rules for specifics [fit.edu] but generally the rules are just what you would expect: The program runs (and completes in a reasonable time) on a relatively recent system running Windows (currently XP) or Linux with no external inputs, eg no dynamically loaded libraries not included in the submission, no net communication and no disk I/O that isn't generated by the program itself.

            Points are not awarded for attempting to circumvent the intent of the competition. I expect such attempts would result

          • Why so? The test file is exactly 10^8 bytes.

            I downloaded the corpus, and indeed, you're right -- it's 10^8 bytes. The article is incorrect, it says 100M where it means 95.3M.

            This inconsistency doesn't have any effect on the challenge, though -- that 50kEUR[1] is offered for compressing the given data corpus, not for compressing a string of 100MB.

            [1] 1kEUR=1000EUR. 1M EUR=1000000EUR. 1KB=1024B. 1MB=1048576B.
            And by the way, what about fixing Slash to finally allow Unicode -- either natively or at least as

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.