Compress Wikipedia and Win AI Prize

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."

WikiPedia on iPod!

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.

Re:WikiPedia on iPod!

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

wikicast

a method for periodically re-syncing...

So, we need a WikiCast - remember folks, you heard it here first!

Re:WikiPedia on iPod!

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.

Re:WikiPedia on iPod!

Umm... which of the 5 thousand links is the article?

But captain

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

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

For the love of god, proofread!

Re:Painful to read

> For the love of god, proofread!

Yeah, I just read the write-up twice and have no idea if this is an AI contest, something to do with compression, or what. In fact, all I can remember now is the word "incentivize" which is the sort of thing I expect som

Re:Painful to read

Agreed -- why can they not MOTIVATE us instead?

No, they need to verbize another noun when there was a perfectly good word in the language that means *exactly* what they want. feh.

Re:Not sure if that's a joke.

Of course he was joking. If he was serious he would've said "verbificate".

Re:Painful to read

He did, but Slashdot's AI compressed it for him.

:-D

lossy compression

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

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

Re:lossy compression

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 i

Re:lossy compression

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.

As long as it is Wiki that we are talking about...

There. All of wiki, in 31 bytes.

Who'da thunk...

Man, WinRar is taking its bloody time. But oh god, when its done, I'll be rich!

Re:Who'da thunk...

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®

Easy!

arj

Lossy Compression?

Convert it to AOL! tis wikpedia, teh fri enpedia . teh bst in da wrld.

Re:Lossy Compression?

That is actually an interesting idea. What if you added a layer of compression that converted every possible common acronym, made contractions, etc...

Re:Lossy Compression?

1) it wouldn't be lossless and 2) most compression techniques use a dictionary of common used words.

Would be useful for images

... now all we need is a dictionary for nudity and we could save a lot of bandwidth on the Internet!

Comparison

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 g

Re:Comparison

erm... isn't that already a part of how data compression algorithms like ZIP work right now?

Re:Comparison

Whoa, you are an inventive genious! Oh wait, that's kinda how nearly all compression works.

Re:Comparison

Well, if I knew that 15 years ago, I would indeed have been a genuis, sadly I realized too late and my genuis talents are wasted yet again.

Have no fear though, I'm working on a new one.

It's a big world out there

"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.

Re:It's a big world out there

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" deal

Re:It's a big world out there

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 lossle

Re:It's a big world out there

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

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.

Re:It's a big world out there

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 diffe

Re:It's a big world out there

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 r

Re:It's a big world out there

Yeah, but you can use Turbo codes to achieve near Shannon limit, and you don't have to worry too much about the addition of the ECC. Remember kids: study that math, you never know when information theory can suddenly pay off.

Just to help (and so you don't think I made Turbo Codes up -- it's sounds like I did 'cause it's such a bad name)
http://en.wikipedia.org/wiki/Turbo_code [wikipedia.org]

Er, I'm not so sure about this.

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.

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?

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:

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!

Re:I'll try:

echo "!#/bin/cat /dev/tty0" > archive

Here's one that's even shorter, but you have to type in the decryption key exactly right.

C++

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

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?

Can't I just punch the monkey for $20 instead?

Re:for those who rtfa

a) how big the compressed size was

18MB

b) how many bytes was wikipedia before it was compressed

A sample of 100MB

Your goal:
.

KFG

Re:Can it be "lossy" compression?

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

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.

Barebones Windows or Linux

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 dynamic

Re:Can it be "lossy" compression?

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 50kEU

Re:Can it be "lossy" compression?

Hmmm...well in that case, someone go edit the Wikipedia entry on "computers" and allow them to store data at the bit level. Also, I heard somewhere where computers in Africa have tripled in the past six months!