Live data from Hacker News

Compression is prediction

ngrok.com

221–230 of 324 posts

Re: Compression is prediction

#221
post #14

Nope; there is a bit more nuance and the distinction is important. Compression is functionally equivalent to prediction when the data distribution is exactly representative of all future problems . The story changes drastically if you want generalization -- because the test distribution could be arbitrarily different, even if it had the same support ! Eg: you observe a rare edge case in your training data and (lossy)…

> because the test distribution could be arbitrarily different,

In that case all bets are off for all machine learning algorithms anyway. If the changes are not arbitrarily different then some of the lost performance can be recovered.

You talk about generalization a lot, but perhaps you are not aware that the technical term is defined under the assumption that test and train distribution are the same.

Re: Compression is prediction

#222
Yep, for example for predicting future access patterns in a VM subsystem.

Practical Prefetching via Data Compression; Vitter, Krishnam, Curewitz. 1993

The page addresses ('names') were the characters and the built-up LZ dictionary used to predict which "characters" → pages would come next.

https://www.ittc.ku.edu/~jsv/Papers/CKV93.practical-prefetch...

Optimal Prediction for Prefecting in the Worst Case; Vitter, Krishnan

https://dl.acm.org/doi/pdf/10.5555/314464.314575

Apparently the same trick was later rediscovered for web-pages.

Re: Compression is prediction

#223
If a string produced from random noise gets compressed (because it has invariably some repetitions in it if long enough), is there any prediction? Even getting the probability distributions right doesn't get to any way to reliably to predict the next symbol out of the sample string. Any functions fitted etc. will be incorrect, too.

Re: Compression is prediction

#224

There is Compression done by Prediction by partial matching [0] There is the Kolmogorov Complexity [1], Normalized Information Distance [2] and Normalized compression distance [3] that correlates those. Finally, there's the Pre-Big Bang Informational Compression and the Delayed Release of Antimatter [4] All big {rabbit/black} holes to lose some time, if you have any. [0] https://en.wikipedia.org/wiki/Prediction_by_pa…

I'll add Minimum Description Length to the mix. Under certain definitions and conditions, it equals the Bayesian Information Criterion plus an extra term, which I consider a very interesting result in this "two faces of the same coin" perspective.

Re: Compression is prediction

#225

Earlier quoted context omitted.

We model the data. The model, hopefully, captures something real in the data. If it does, then it's fair to say that we understand the data better. But it's frankly a philosophical question what's real or not. No model is going to capture absolutely everything about the thing it models - at that point, it would be the thing. The best we can hope for is that it captures everything we care about. And no experiment or m…

A model will not capture every nuance of what it models, but it might capture every nuance you managed to measure properly.

Including the things you didn't even realize you measured, or even conceptualized at all.

Re: Compression is prediction

#227

Earlier quoted context omitted.

> How do you decide what shared features a peacock and a palm tree have? At what scale should they be represented? How do you deal with invariance under affine transforms? Do you want to open the box of invariance under non-affine transforms? The whole point is that the representation is learned. When you talk about various levels of abstraction, you're missing that all of these levels are representable with words an…

1) I am talking about representations beyond language models and language embeddings. If you take for example image, video, audio, 3D-spatial DICOM or combinations like VLMs. If you ask a language model to make an image of a Begonia ferox leaf without training it with images as well, it will not be able to represent this. 2) Language is already a higher-order lossy compressed abstraction made by humans to communicate…

1) If you ask a language model to make an image of a Begonia ferox leaf without training it with images as well

is this not true also of humans?

2) The idea that there is a non-compressed prior is already philosophical no? It seems to just be a rehash of whether an example of a "Chair" is a representation of a perfect Idea of a chair, or whether accidental things put together read as a chair. Its just dualism or not, Plato vs aristotle but for LLMs vs human learning.

If we do happen to just form an abstraction from less examples than an LLM, then its a question of efficiency in the learning algo and the capability to fill the gaps faster/better.

Obvs a world model and multi modal learning would close the gap between LLM latent space and what the human mind encodings might look like. But you can formulate a reality where humans do not have access to a non compressed representation (or even say that doesnt exist) and we are just more efficient at abstraction and recollection

3) There are multiple answers to this. One is that language can just be a prong in the learning modes available. Another is that language is many times redundant and includes supplemental information and nuances that despite being a higher order abstraction has enough additional information to reconstruct entire messages even after the lossy transmission.

Btw I am pretty against LLMs as path forward, but I have been interested in their ability to solve problems with Convergent solutions and their learning model as a lossy compression algorithm where instead of saving the actual data, you save a very good guesser of the next word. So if a text is part of its traning algo then you get almost a 1:1 (like a zip dictionary) but if its not, then he gives you something that plausibly could be in an imaginary Zip with that title.

Re: Compression is prediction

#228
post #94

Earlier quoted context omitted.

Ah Sir David MacKay. I so respect him. Great explainer and speaker. He had built this text entry tool called Dasher [0] - that I'd heard him introduce at Princeton around 2006. It was basically an early language model that predicted which characters are more likely than others, given what you've already types and it would adjust the sizes of the available next characters based on their probabilities. [0] https://dash…

He really was fantastic, and prolific in multiple fields. He wrote https://www.withouthotair.org/ (creative commons) and was the Chief Scientific Advisor to the UK Department of Energy and Climate Change. Dedicated to "to those who will not have the benefit of two billion years' accumulated energy reserves".

I also went to a couple of his (fantastic) undergraduate courses, and have a huge amount of respect for him.

That said, I think it's worth mentioning that Climate Change Without the Hot Air has aged pretty badly, and I'd be reluctant to recommend it to people who don't already have the background to understand what's aged well and what hasn't.

The high level approach of making high level numerical estimates makes sense, but it dismisses solar energy in about a page due to assumed high costs. It turns out that even if you're David Mackay you can still be caught out by exponentials :) I notice now that the version you link has some inline updates pointing out how off the assumptions in this section were, but it seems to me that's not enough; you probably need to redo the entire analysis based on what we know today rather than trying to make purely local adjustments.

On the other hand the point at biofuels are even more inefficient, and therefore a dead end even before you consider broader environmental impacts, are well made and something that is sadly not yet widely reflected in policy.

Re: Compression is prediction

#229

Earlier quoted context omitted.

I'm of two minds here. The pro is that the "you could have invented this" walkthrough from first principles is more engaging than "and then so and so introduced this term in 1972 and the definition is such and such". This style is a reaction to that boring and dry teaching style and tries to push towards what eg Feynman pointed at in the Brazil critique. The con is that you don't get to understand and see any of the…

There's no reason a compelling walkthrough can't throw in historical citations, is there?

Often the most straightforward way to walk through an idea while teaching it is not the same order that the ideas were developed, and might not even use the same set of ideas in building up to it, so it can be tricky to get both the best explanation of the idea and the historical context in at the same time without making things more confusing.
Post reply on HN