r/programming • u/fagnerbrack • 7h ago

Compression is prediction

https://ngrok.com/blog/compression-is-prediction
78 Upvotes

86% Upvoted

18 comments sorted by

48

u/Bunslow 5h ago

that's literally the meaning of "information", is how predictable the next bit is. if it's predictable, it's not (new) information. if it's unpredictable (random), then it's novel information.

(this is why information and entropy are measured the same way)

-3

u/ptoki 2h ago

I have beef with this and similar approach.

I remember a book for young enthusiasts about logic. One of the riddles was:

What is the value of the information you already know. Their answer was none.

My issue with this is that it totally ignores how trusted is the information.

if 2+2=4 is known in the domain of integers and we learn it also works for real or complex numbers does that mean we gain zero additional value from knowing that fact?

7

u/Giannis4president 1h ago

In logic the riddles are not about alternative meanings or potential problems or real life communication. In logic information is information, there is no trust attached to it

1

u/Az0n 1h ago

I think you are thinking of the statement too generally. "2+2=4 holds in the domain of integers" and "2+2=4 holds in the domain of reals" are two separate pieces of information.

Your point about trust is not really relevant to compression. There, information is the data you want to compress. If the data is entirely random it has a lot of information, and will take more space to encode.

1

u/paulstelian97 28m ago

Checksums. Error correction codes. They add more bits to help validate the existing ones, and sometimes even fix tiny differences.

8

u/reddit_user13 3h ago

Compression can be a bit lossy or lossless. You can get back the input, or in the case of the source code example, something close enough to be functional.

Crunching input texts into an LLM model is very lossy, and you can't get anything like the source text(s) back.

1

u/nsaisspying 48m ago

In the case of the LLM, when you say 'source text', do you mean the training data? Or the prompt?

1

u/rationalguy2 4m ago

The training data would be the source text. So a lossless LLM that trained on every book in the 20th century could recite any paragraph of The Lord of the Rings.

That said, LLMs likely use prompts as training data, in which case, both are the source text. (I don't enter sensitive information in a prompt.)

0

u/Ok-Craft4844 45m ago

Even before they could use tools, you could ask the early gpts "what's the national anthem" and you got the text back, so "you can get anything like the source text back" seems hyperbolic

9

u/Most-Cloud 7h ago edited 7h ago

Cool visuals and interactive educational content

6

u/Bradnon 7h ago

Took 3b1b three years to recap googles paper linked in her article? https://arxiv.org/abs/2309.10668

4

u/jmickeyd 3h ago

Fabrice Bellard, the guy who wrote qemu, wrote a paper on this back in 2019: https://bellard.org/nncp/nncp.pdf

3

u/Most-Cloud 7h ago

Yeah just saw a Google talk about this in a related video. Came here to delete my negativity.

1

u/Bradnon 7h ago

Ahh good on ya.

2

u/flip314 3h ago

IMO the coolest thing about arithmetic coding is that you don't even need to share the dictionary/probabilities between the encoder and decoder.

If instead of calculating the probability of the entire data set at once you build it up over time, then the decoder can build its own table in the same way. Start by assuming all the probabilities are the same and adjusting the frequency after each symbol before encoding the next. The decoder can predict the first symbol based on equal probabilities, then update its own frequency table and use that for the next symbol, etc.

-1

u/ctrlHead 4h ago

Is it also inside out?