Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A student’s desire to get out of a exam led to a compression algorithm

quantamagazine.org

Post reply on HN
Print view View original

101–110 of 132 posts

Re: A student’s desire to get out of a exam led to a compression algorithm

#101

Post by karpierz »

floobertoober wrote: post #98
MauranKilom wrote: post #82

Earlier quoted context omitted.

Another interesting facet is that, according to some schools of thought, compression and AI are equivalent problems: The better you understand something, the less you need to memorize to reproduce it. https://en.wikipedia.org/wiki/Hutter_Prize (and https://en.wikipedia.org/wiki/AIXI ) Of course, large language models are (by definition) currently going the other direction, but it remains to be seen whether that leads…

> Of course, large language models are (by definition) currently going the other direction ... How so? Aren't the networks' weights orders of magnitude smaller than the training data?

I believe the parent poster's point is: LLMs are more effective when they use more memory, meaning the less they are forced to compress the training data, the better they perform.

Re: A student’s desire to get out of a exam led to a compression algorithm

#102

Post by amelius »

vjerancrnjak wrote: post #86
amelius wrote: post #79

What would be interesting is something like an LLM attempting to compress some piece of data, and see how it gets better at it over time.

I think there’s a contest for this compressing Wikipedia. LMs are winning.

Interesting. Do you mean [1]?

[1] https://en.wikipedia.org/wiki/Hutter_Prize

Re: A student’s desire to get out of a exam led to a compression algorithm

#103

Post by Georgelemental »

fguerraz wrote: post #8

Quanta magazine and all these pop science websites need to be stopped. (Not because popular science is bad, but because they do it badly, and the clickbait is insufferable)

I like Quanta! They explain things accurately and in detail, with helpful figures and diagrams. They did go wrong a few months ago with the "quantum computer black hole" article, but the heat they recieved was precisely because it fell well below their usual standards, which are otherwise well above other "pop science" sites in my experience.

Re: A student’s desire to get out of a exam led to a compression algorithm

#104

Post by [deleted] »

govg wrote: post #100
floobertoober wrote: post #98

Earlier quoted context omitted.

> Of course, large language models are (by definition) currently going the other direction ... How so? Aren't the networks' weights orders of magnitude smaller than the training data?

I interpreted that statement as saying the current practice is to make LLMs larger and larger (so they effectively memorize more and more data) to make them more powerful, but from the perspective of information theory, if models were powerful and "understanding", then models could stay the same size and become more and more powerful as they get increasingly better at compressing the available information. I am not s…

[deleted]

Re: A student’s desire to get out of a exam led to a compression algorithm

#105

Post by hgsgm »

sn41 wrote: post #23
fguerraz wrote: post #8

Quanta magazine and all these pop science websites need to be stopped. (Not because popular science is bad, but because they do it badly, and the clickbait is insufferable)

I agree. They have a breathless tone to them that's quite annoying to me (I work in data compression as an academic, and I found this article uninspiring.) By the way, there was an old Soviet magazine called "Kvant" (Russian for Quantum, I think). I do not know Russian, but I have 2 collected volumes of selected articles from them. [1] [2] Their quality is astonishingly good, and high-level. The difference is this: T…

Not everyone who reads the news is a mathematian.

Quanta is far better than the programmer / bizhacker / SEO blogs that dominate HN.

> “My mind was just blown. Like, wait, have they really done this?” said Sisask, a lecturer at Stockholm University."

> Sisask called it “the biggest result in the area for 20 years.”

> “Meka and Kelley have sort of leapfrogged all this incremental progress,” said Terence Tao, a prominent mathematician at UCLA.

Maybe you're just wrong? I trust the judgement of these people more than yours.

Re: A student’s desire to get out of a exam led to a compression algorithm

#106

Post by abecedarius »

sn41 wrote: post #23
fguerraz wrote: post #8

Quanta magazine and all these pop science websites need to be stopped. (Not because popular science is bad, but because they do it badly, and the clickbait is insufferable)

I agree. They have a breathless tone to them that's quite annoying to me (I work in data compression as an academic, and I found this article uninspiring.) By the way, there was an old Soviet magazine called "Kvant" (Russian for Quantum, I think). I do not know Russian, but I have 2 collected volumes of selected articles from them. [1] [2] Their quality is astonishingly good, and high-level. The difference is this: T…

I haven't seen Kvant, but it's worth adding that Scientific American up till maybe the mid-80s was also more real than standard pop science. Don't take its current incarnation as much like its past. (I guess the 70s were even better for it, but this is my fuzzy memory of a trove of back issues I went through in the 80s.)

That said, from a skim I wouldn't call this particular article standard pop science: it explains an idea/result rather than spending most of its words on periphera, and the subject is not recent news. It does ask less of the reader than an old Sci Am article would, I think.

Re: A student’s desire to get out of a exam led to a compression algorithm

#107

Post by thesz »

iforgotpassword wrote: post #48

Interesting refresher. I do remember in college we had to build the lookup tree for some word as an exercise. Obviously the name Huffman stuck in my brain. But for the love of god, I can't even remember if the lecture mentioned Fano. Seems he was just as important in the design process of what we only refer to as Huffman encoding today.

Here's Shannon-Fano coding: https://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding

It is used in PKZip Deflate algorithm.

Fano's work is as famous and as useful as Huffman's.

Re: A student’s desire to get out of a exam led to a compression algorithm

#108

Post by the-mitr »

abecedarius wrote: post #106
sn41 wrote: post #23

Earlier quoted context omitted.

I agree. They have a breathless tone to them that's quite annoying to me (I work in data compression as an academic, and I found this article uninspiring.) By the way, there was an old Soviet magazine called "Kvant" (Russian for Quantum, I think). I do not know Russian, but I have 2 collected volumes of selected articles from them. [1] [2] Their quality is astonishingly good, and high-level. The difference is this: T…

I haven't seen Kvant, but it's worth adding that Scientific American up till maybe the mid-80s was also more real than standard pop science. Don't take its current incarnation as much like its past. (I guess the 70s were even better for it, but this is my fuzzy memory of a trove of back issues I went through in the 80s.) That said, from a skim I wouldn't call this particular article standard pop science: it explains…

> but it's worth adding that Scientific American up till maybe the mid-80s was also more real than standard pop science.

glad that someone also shares this opinion, the articles and the art in those two decades was great

Re: A student’s desire to get out of a exam led to a compression algorithm

#109

Post by gavinray »

sn41 wrote: post #23
fguerraz wrote: post #8

Quanta magazine and all these pop science websites need to be stopped. (Not because popular science is bad, but because they do it badly, and the clickbait is insufferable)

I agree. They have a breathless tone to them that's quite annoying to me (I work in data compression as an academic, and I found this article uninspiring.) By the way, there was an old Soviet magazine called "Kvant" (Russian for Quantum, I think). I do not know Russian, but I have 2 collected volumes of selected articles from them. [1] [2] Their quality is astonishingly good, and high-level. The difference is this: T…

I really enjoyed this article, as someone who didn't finish highschool and is a professional programmer.

The Wikipedia entry on Huffman Coding is impenetrable to me, this article was easy to follow.

Re: A student’s desire to get out of a exam led to a compression algorithm

#110

Post by nico »

In the article the compression doesn’t make sense

If you are only sending one word, and the recipient already needs to know the word, then you only need 1 bit, essentially just signaling that you are saying that specific word

If you want a richer vocabulary, you could create an index of about 300k words (from the English dictionary), shared between the parties

Then to send any word you only need to send one number, and in binary it would have between 1 and at most 19 bits, for any word in the index (2^19 is around 500k)

That’s without even sorting the index by frequency of appearance/usage

27 bits for just one word seems wasteful

Post reply on HN