13 ms·
Hutter Prize for compressing human knowledge
- slashdev 3y agoI think the mistake here is to require lossless compression. Humans and LLMs only do lossy compression. I think lossy compression might be more critical to intelligence. The ability to forget, change your synapses or weights, is crucial to being able to adapt to change.
- version_five 3y agoYeah it makes no sense to say it's inspired by intelligence and then require lossless which is definitionally rote work and not intelligent.
- whimsicalism 3y agoNot true, a smart model could be really good at lossy compression and then you only have to store a small delta to make it lossless.
- ClassyJacket 3y agoI'm no mathematician but I don't believe this is true. Lossless information encoding requires all the original information to be present.
- AnotherGoodName 3y agoArithmetic coding allows you to make a prediction and only provide bits for correction. Have the de-compressor predict the next data based on the outcome so far (a statistical prediction of next data will be lossy as it won't always be correct). If the prediction is correct you need to spend very little to confirm that. If it's incorrect you'll need to spend data to correct it. Arithmetic coding is the best way to make this work. It's also been used by all winning entries of the Hutter prize so far.
- ClassyJacket 3y agoAlright I guess I was wrong.
- slashdev 3y agoTechnically you’re correct. If you can rebuild the original losslessly then all the original information is present, just in a different configuration.
- glitchc 3y agoOr at least reproducible. It could still be compressed.
- vladf 3y agoWhat
- AnotherGoodName 3y agoThat's literally arithmetic coding which is used by all winning entries in the above so far.
- whimsicalism 3y agoyep!
- kaba0 3y agoWhich is the exact same function of the difference between any competitor, so you can actually fairly compare them on the lossy part.. like, people have been thinking about this problem much more than the 3 minutes HNers in this comment section.
- sytelus 3y agoHumans can do lossy or lossless. There are plenty of people who can recite entire Bible or Koran flawlessly.
- Supply5411 3y agoAnd there are humans that can jump 8ft in the air. Doesn't mean it's correct to say that "humans can jump 8ft in the air." Very few people are regurgitating verbatim information.
- kadoban 3y agoThat's true, but it seems unlikely that that's a particularly important part of intelligence. The vast majority of people do _not_ do that type of memorization, are they still intelligent?
- anonylizard 3y agoMany can recite the Koran flawlessly, its short and heavily encouraged in education through rote repetition. Much, much fewer can recite the bible, its many times longer. LLMs can also recite the bible and Koran flawlessly, given how frequent the text appears in their training material.
- RugnirViking 3y ago> LLMs can also recite the bible Is this something you've seen demonstrated? I have no doubt they would be able to recite a lot of sections of it, but there are many sections that are less often quoted, and its a long frickin book. If its just a hunch you have I might give it a go and compare if thats okay I think it would be interesting to interpret what given LLM knows and might miss
- _0ffh 3y agoNow you've given me the idea of coaxing new bible verses out of an LLM. Maybe we can even get one to confabulate a complete additional book! =)
- 3y ago
- mik1998 3y agoLossy text compression has little utility.
- JumpCrisscross 3y ago> Lossy text compression has little utility You're describing every book you've ever read and learned from.
- mik1998 3y agoNo, not at all. I don't read a book to regurgitate the text in an imperfect form later. I read it to learn about the ideas and thought. The syntax itself (ie. text) is not that important.
- _jal 3y ago> The syntax itself (ie. text) is not that important So, you're preferentially discarding information you consider extraneous to your application, distilling it to a smaller representation that retains what you consider important about it.
- JumpCrisscross 3y agoMost image compression smooths skies. Because most people don’t want a regurgitated sky. If you’re an astronomer, on the other hand, you’ll compress away the trees. These are all lossy retrieval (and, inherent to compression, transformation) functions.
- dekhn 3y agoAh, see but what they really meant to say was "Lossy text compression has a little utility" but due to lossy compression the meaning changed to be the opposite, thus proving the author's point.
- barrysteve 3y agoGood books aren't lossy.
- lucb1e 3y agoFeel free to start your own competition where people are awarded money for a system that correctly answers some set of questions, divided by the amount of storage that system needs. Sounds like a tough competition to run objectively, not that that makes it less worth doing, but I can see why the parameters were chosen as they were in 2006.
- AnotherGoodName 3y agoSome 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 agoYour 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 agoSorry 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.
- thelastparadise 3y agoGood lossy compression can be used to achieve lossless compression. (information theory) The more accurate the lossy compression is, the smaller the difference between the actual data (lossless) and the approximation. The smaller the difference, the fewer bits required to restore the original data. So a naive approach is use the LLM to approximate the text (this would need to be deterministic --zero temp with a preset seed), then subtract that from the original data. Store this diff then add back to restore the original data bit-for-bit.
- Xcelerate 3y agoWho downvoted you? This is correct; the better the lossy compression, the better the lossless compression as well.
- CamperBob2 3y agoThat's true until the lossy compression alters the data in a way that actually makes it harder to represent. As an example, a bitstream that 'corrects' a decompressed .MP3 file to match the original raw waveform data would be almost as difficult to compress as the raw file itself would be. It wouldn't be a matter of simply computing and compressing deltas at each sample, because frequency-domain compression moves the bits around.
- hinkley 3y agoIn psychoacoustics, one of the most important aspects of how lossy compression works is that they throw away sounds that a human can't even hear, because it's too short or subtle to be noticed. This is the difference between data and knowledge. Someone with perfect pitch and a good memory knows exactly what Don't Stop Me Now by Queen sounds like, and it's a lot smaller than digitizing an LP record in mint condition. This person can cover that song, and everyone will be happy, because they have reproduced everything that makes that song what it is. If anything we might be disappointed because it's a verbatim reproduction (for some reason we prefer cover songs to introduce their own flavor). If I ask you to play Don't Stop Me Now and you sound like alcoholic Karaoke, you haven't satisfied the request. You've lost. Actually we've all lost, please stop making that sound, and never do that again.
- modeless 3y agoThe problem with lossy compression in a competition is that in order to compare different approaches to lossy compression you have to define a metric for the quality of different lossy reconstructions of the data. This is practically impossible to do in an unbiased way. As soon as you define a quality metric then the competition becomes cheating the metric instead of useful compression. So how do you define a metric that can't be cheated? You add an arithmetic coder after your lossy compressor, which turns it into a lossless compressor, and the size of the losslessly compressed data is your metric for the quality of your lossy compressor. It's the only metric that definitively can't be cheated.
- jharohit 3y agoTed Chiang actually explores this concept in his article on ChatGPT and other LLMs https://www.newyorker.com/tech/annals-of-technology/chatgpt-is-a-blurry-jpeg-of-the-web https://www.newyorker.com/tech/annals-of-technology/chatgpt-...
- hnfong 3y agoSee a related benchmark: http://www.mattmahoney.net/dc/text.html http://www.mattmahoney.net/dc/text.html In particular, Fabrice Bellard is leading with a transformer model for “enwik9” that which is 10 times larger than the one used in Hutter. It’s doing quite well with enwik8 too, but perhaps the issue is that the “economy of scale” with on the fly training hasn’t caught up in the smaller benchmark yet. Transformers are definitely lossy, but afaict Bellard’s entry uses the probabilities generated by the model to create an encoding that used fewer bits
- vintermann 3y agoLossy compression is lossless over the information you decided to care about. You may decide that the sound that's outside the human range of hearing isn't interesting. Or that the colours in your camera sensor that's just thermal noise can be safely ignored. Then you can throw it away and do lossy compression. What you care about, an algorithm can't answer for you. Sometimes you may want to keep the inaudible sounds in a recording to better understand the audible ones. Sometimes you may be glad you kept the noise in a picture as it allowed you to later identify the model of camera. There's no context-free answer to what matters. There's no subject-free answer to what matters, there's always a "who" it matters to.
- mrcgnc 3y agoTrue, but then I would argue (as a layman) that AGI would need to be able to guess what matters in a given context to really be AGI.
- vintermann 3y agoMatters to who? To me? In that case, it sometimes does, sometimes doesn't, depending on how lazy I've been in constraining to the algorithm what I might want. To itself? Then who can say if it isn't doing that already?
- Geee 3y agoThe compression should be semantically lossless, but lexicographically lossy. It should find ways to say the same thing in less characters. I.e "Sky is blue. Ocean is blue." -> "Sky and ocean are blue."
- YetAnotherNick 3y agoLossless text compression is basically something like arithmetic coding[1] on top of probability. In fact the loss metric that LLM directly optimize for is bits required for lossless compression. Loss plotted in papers is generally nits/token. The only reason why LLM are not in the leaderboard because it is not a task for compressing human knowledge. It's a task for compressing wikipedia which is tiny in comparison, and the model size plays a big role. [1]: https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding
- mjan22640 3y agomath is a lossless compression
- TheAlchemist 3y agoI mean, come on man. For some reason, the nerd in me sees this and immediately adds it on my 'I really need to do this' list. Just memories of old times doing some similar (albeit less challenging probably) competitions on TopCoder almost a decade ago, and also the curiosity to see how I would manage it know, with experience. Given that the current scores are also very far from what they estimate the lower bound to be, this is really interesting ! The prize is however very misleading - per their own FAQ - the total possible payout is ~223k euros. Definitely not thanking you for the hours I will put into this !
- demandingturtle 3y agoI have an idea if you want to code it. You know how we can drop the vowels from sentences and still understand the sentence? What if we do that on the first stage? May not work for every case so have to identify. Worse comes to worst, use full word. Probably not saving much though. Worth a try.
- saulpw 3y agoI bet you think of yourself as an idea guy.
- freilanzer 3y ago> I bet you think of yourself as an idea guy. What does this even mean?
- saulpw 3y agoIt means he wants to sit back, write a lazy comment, and have someone else do all the work ("code it up", hah). Toss his brilliant ideas that are "worth a try" over the fence and move on to the next brilliant idea. Without any research or due diligence or even consideration for the comparative amount of effort it takes to have an idea, vs executing on it. Ideas are a dime a thousand. This is the same kind of person who's got a great business idea, they just need you to write up an AirBnb clone in a couple of weeks, and they'll give you 5% of the company.
- omoikane 3y ago500000 EUR is the prize pool. Each winner has to gain at least 1% improvement over previous record to claim a prize that is proportional to the improvement. Getting the full 500000 EUR prize requires an 100% improvement (i.e. compressing 1GB to zero bytes).
- phobotics 3y agoDoes it or does it just require 1% improvement over the last winner? As opposed to a static additional 1% improvement vs the initial best “score”.
- omoikane 3y agoIt's 1% over the last winner. The latest winner has a total size of 114156155, compared to previous winner of 115352938. The payout was 500000 * (1 - 114156155 / 115352938) = 5187 (see table near "Baseline Enwik9 and Previous Records Enwik8")
- bigyikes 3y agoProbably if you succeed at this, 500,000 will be worthless to you
- sytelus 3y agoWhy? How does this improvement translates to more financial gains?
- Eduard 3y agobecause with that knowledge, you will be able to decompress 0 dollar to infinite dollars which the storage mafia will pay you for not publishing your breakthrough in making them obsolete.
- aleph_minus_one 3y agoLet's say you really find a new, much much better compression algorithm for texts. I do believe that soon new applications will appear that will make use of the whole storage space that existing data storage devices can offer.
- TheRealPomax 3y agoQ: Why do you restrict to a single CPU core and exclude GPUs? A: The primary intention is to limit compute and memory to some generally available amount in a transparent, easy, fair, and measurable way. 100 hours on one i7 core with 10GB RAM seems to get sufficiently close to this ideal Sorry, who are these people that don't have a GPU? Even laptops have GPUs. Why would you spend 100 hours on an "i7" (which generation? 4790K or six times faster 13700k?) CPU when you can achieve orders of magnitude better performance on a consumer GPU that literally everyone has access to?
- lucb1e 3y agoNote that the competition close to 20 years old ...though I also had a GPU in 2006, so idk. Then again, you need to define something as reference hardware and it doesn't really matter what it is. Better compression should win out over less-good compression no matter if you run both on a 100-core system or a 1-core system, I think?
- TheRealPomax 3y agoIn the category "then update your FAQ, you've have many, many years to do so" =D (not to change the rules, but to explain why they rules haven't changed, and to clarify the super vague phrasing even back when the 3dfx Voodoo was the pinnacle of graphics. Level playing fields are a worthwhile pursuit)
- caseyavila 3y agoI do think it's interesting that recent submissions use nearly the entire 50 hours. I wonder how much better people could do if faster hardware was allowed.
- AnotherGoodName 3y agoAbsolutely they could. All the entries so far can do even better with more RAM. That PAQ entries have command line flags to do this. That's already known in fact. What this is looking for is fundamental improvements, not "i brute forced a known way to win this competition".
- dang 3y agoRelated. Others? Saurabh Kumar's fast-cmix wins €5187 Hutter Prize Award - https://news.ycombinator.com/item?id=36839446 https://news.ycombinator.com/item?id=36839446 - July 2023 (1 comment) Hutter Prize Submission 2021a: STARLIT and cmix (2021) - https://news.ycombinator.com/item?id=36745104 https://news.ycombinator.com/item?id=36745104 - July 2023 (1 comment) Hutter Prize Entry: Saurabh Kumar's “Fast Cmix” Starts 30 Day Comment Period - https://news.ycombinator.com/item?id=36154813 https://news.ycombinator.com/item?id=36154813 - June 2023 (5 comments) Hutter Prize - https://news.ycombinator.com/item?id=33046194 https://news.ycombinator.com/item?id=33046194 - Oct 2022 (3 comments) Hutter Prize - https://news.ycombinator.com/item?id=26562212 https://news.ycombinator.com/item?id=26562212 - March 2021 (48 comments) 500'000€ Prize for Compressing Human Knowledge - https://news.ycombinator.com/item?id=22431251 https://news.ycombinator.com/item?id=22431251 - Feb 2020 (1 comment) Hutter Prize expanded by a factor of 10 - https://news.ycombinator.com/item?id=22388359 https://news.ycombinator.com/item?id=22388359 - Feb 2020 (2 comments) Hutter Prize: up to 50k € for the best compression algorithm - https://news.ycombinator.com/item?id=21903594 https://news.ycombinator.com/item?id=21903594 - Dec 2019 (2 comments) Hutter Prize: Compress a 100MB file to less than the current record of 16 MB - https://news.ycombinator.com/item?id=20669827 https://news.ycombinator.com/item?id=20669827 - Aug 2019 (101 comments) New Hutter Prize submission – 8 years since previous winner - https://news.ycombinator.com/item?id=14478373 https://news.ycombinator.com/item?id=14478373 - June 2017 (1 comment) Hutter Prize for Compressing Human Knowledge - https://news.ycombinator.com/item?id=7405129 https://news.ycombinator.com/item?id=7405129 - March 2014 (24 comments) Build a human-level AI by compressing Wikipedia - https://news.ycombinator.com/item?id=143704 https://news.ycombinator.com/item?id=143704 - March 2008 (4 comments)
- lucb1e 3y agoOne would think it ought to be possible to automate generating these overviews. Or has it been automated and is it being posted with a non-service account because it's partially but not fully automated?
- LeonB 3y agoPretty sure Dang has some nice scripts that generate this, and I expect he does a little manual pruning before posting it. He’s very precise in his choices, definitely applies some intuition/judgement. We can’t losslessly compress him — yet!
- hn_throwaway_99 3y agoThis is probably a dumb question, but I recall from (way) back in my college days studying Shannon's source coding theorem that there are calculable limits regarding how much a data stream can be compressed. Has this limit been calculated for the sample file in question? And apologies if this was in the linked article or one of the footnotes.
- AnotherGoodName 3y agoNo. In fact there are limits but unless you've already written a 'perfect compression tool' you can't actually know the limit. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity is ultimately what you're looking for btw. Shannon is more about limits in transmission speed given noise but Kolmogorov dealt with the limits of compression which is actually unknowable.
- mgraczyk 3y agoTo establish bounds in this way, you have to start with some claim about the distribution of the input data. In this case, the data is natural human language, so it's difficult or impossible to directly state what distribution the input was drawn from. Even worse, the prize is for compressing a particular text, not a sample from a distribution, so tight bounds are actually not possible to compute. There is some discussion on the Hutter prize page, under "What is the ultimate compression of enwik9?" http://prize.hutter1.net/hfaq.htm http://prize.hutter1.net/hfaq.htm
- jftuga 3y agoFrom this article: More empirically, Shannon's lower estimate suggests that humans might be able to compress enwik9 down to 75MB, and computers some day may do better.
- AnotherGoodName 3y agoThe current best compresses it to <15MB because it's not a human which that example is referring to. :)
- userbinator 3y agoIt's interesting to see a new winner of different nationality beating the multiple previous records by the same guy, and what appears to be another one who beat him 2 years ago; for some (cultural?) reason, there seems to be a historical association between Soviets and advanced data compression technologies in general, possibly starting with Markov's work in the 19th century.
- eru 3y agoThe causation for this might run along the lines of having plenty (in absolute terms) of well educated smart folks but pretty low wages. Most of the really smart people in Europe and the US for example already have high paying jobs and thus less time for these relatively low paying competitions.
- matanyall 3y agoEasy! Write a compression algorithm that works as follows: if you detect the input is the first gb of Wikipedia, return nothing. Else return the compressed artifact of your compression algorithm of choice. To decompress, running the decompression algorithm on an empty input returns the first gb of Wikipedia, if else you use whatever algorithms you used earlier :) This is inspired by HQ9++: https://www.dangermouse.net/esoteric/hq9plusplus.html https://www.dangermouse.net/esoteric/hq9plusplus.html
- quickthrower2 3y ago> Rules > Publish a compression program comp9.exe that outputs archive9.exe given input enwik9. > If archive9.exe is run with no input, it reproduces 10^9 byte file data9 that is identical to enwik9. > Total size is measured as S := length(comp9.exe/zip)+length(archive9.exe). In other words the input is indeed set to zero, but the size of the .exe is actually measured. And even stricter the thing that made archive.exe is included (which I think I a bit mean)
- mr_toad 3y agoNot sure if you’re joking or not, but the prize is for the smallest archive + compressor. The best you could do with this approach is to use the best existing compressor and the compressed text (needed to check the input). With the extra test you’d end up doing slightly worse than the previous winner.
- asah 3y agoI will now compress all of human knowledge: fuck /s
- aaron695 3y ago[dead]
- NooneAtAll3 3y agoIf anyone is interested in lossless compression competition, but is too intimidated by 100MB/1GB size and level of optimization already achieved here - you can try http://golf.horse/ http://golf.horse/ challenges, which include Wordle wordlist, Pokemons and OEIS database
- Dave_Rosenthal 3y agoWhile I know it wouldn't qualify for the prize due to the size of the model, I'm curious how well a big modern LLM can compress the prize file (enwiki9) compared to the current record. (I guess ideally it would be an LLM not trained on wikipedia as well, to minimize memorizing). On that thought, with a modern LLM's weights dwarfing the enwiki9 file used by the prize, it feels like this prize was setup with the right idea to advance AGI, but with the problem several orders of magnitude to small.
- lIIllIIllIIllII 3y agoThe site itself says that this is the general idea, proposing that intelligence can actually be defined as the ability to compress information as much as possible and.. I guess either just rehydrate it or also derive inferences from it. So basically like enthalpy Interesting - if you play the universe in reverse (reversing entropy) you wind up at the Big Bang, which is the final boss of compressing everything, into a singularity.
- DaiPlusPlus 3y ago> The site itself says that this is the general idea, proposing that intelligence can actually be defined as the ability to compress information as much as possible I don't understand how anyone can define "intelligence" like that...
- GolDDranks 3y agoIt's not an unreasonable definition, if you are aware of Kolmogorov complexity and Solomonoff induction. Intelligence is intimately connected to the ability to predict and model things, and it turns out that data compression is _also_ connected to the ability of predict and model things.
- lIIllIIllIIllII 3y agoIt makes sense intuitively right? If I tell you that this week it's raining on Monday, raining on Tuesday, raining on Wednesday, etc.. Compressing that information into "it's raining every day this week" requires creating an abstraction around it. Finding a pattern. Producing more order from something more chaotic.
- aranchelk 3y agoSmall font — great place to start.
- OccamRazorBlade 3y agoMiddle out ftw
- OscarCunningham 3y agoI don't understand why they sum the size of the compressor with the combined compressed file and decompressor. I think the compressed file and decompressor would make an ungameable challenge on their own. Their FAQ section 'Why is Compressor Length superior to other Regularizations?' is satisfied equally well by the decompressor length.
- jcparkyn 3y agoI had the same question, and I think this FAQ entry answers it fairly well: http://prize.hutter1.net/hfaq.htm#addcomp http://prize.hutter1.net/hfaq.htm#addcomp
- OscarCunningham 3y agoThanks, that one answers my question.
- EVa5I7bHFq9mnYK 3y agoDoes it require participants to give up all their source codes, as usual in these competition? Wonder what the free market price for winner system would be.
- bob1029 3y ago> So the ultimate compressor of it should "understand" all human knowledge, i.e. be really smart. enwik9 is a hopefully representative 1GB extract from Wikipedia. I spotted 2 really compelling examples of "compression is AI" posted recently. ChatLZMA: https://news.ycombinator.com/item?id=37318810 https://news.ycombinator.com/item?id=37318810 Ziplm: https://news.ycombinator.com/item?id=36732430 https://news.ycombinator.com/item?id=36732430
- Rexxar 3y agoWhy the formula use the size of the compressor ? Intuitively I would expect the size of the decompressor and compressed data is the only think that is really important to know how much the total information have been compressed.
- Conlectus 3y agoPerhaps because they include metrics for compression time, which could easily be gamed by doing significant precomputation in the compressor?
- Klaus23 3y agoOtherwise you could just store the whole text in the decompressor. Another way is to keep the file secret and just output a score, but if you want to use a public file, you have to include the program in the calculated size.
- jcparkyn 3y ago> Otherwise you could just store the whole text in the decompressor. I don't think GP was asking about the decompressor, but specifically the compressor. The FAQ has a fairly detailed answer for this though: http://prize.hutter1.net/hfaq.htm#addcomp http://prize.hutter1.net/hfaq.htm#addcomp
- peter_d_sherman 3y agoRelated: Homepage of Marcus Hutter: http://www.hutter1.net/ http://www.hutter1.net/
- MagicMoonlight 3y agoI worked on this a bit and potentially had an improved result on the current leader but it felt a bit cheap since I was doing it manually for this data set rather than for data in general.