Does this mean that lots of 3:30 minutes 1080p videos could be compressed into 4kb?
EDIT: We can be generous and say 40kb for sake of adding more colours / etc.
EDIT: We can be generous and say 40kb for sake of adding more colours / etc.
The practical answer is no. There is an unimaginable amount of possible 3:30 minute vidoes—far more than the number of possible 4kb or even 40kb files.
To be fair, most of those possible vidoes are just noise. We don't have to be able to compress those because people don't care if one video of noise is different from another. We also don't have to reconstruct the video perfectly: as long as it looks more or less the same, the audience is happy. (This is called "lossy compression".)
But even with these caveats, there is no realistic method for compressing realistic 3:30 minute videos that well on a computer. We likely can't do all that much more than current compression algorithms without a different set of tradeoffs. (Like being better at some videos but worse at others.)
That said, a big part of how compression works is by relying on information already present when decompressing. This demo relies on having a particular kind of chip with certain capabilities (ie a CPU and a GPU) and presumably some standard library functions... etc.
How well could we "compress" videos if we had more information available when decompressing? Here's a fun thought experiment: what if we had a model of a human mind? We could then feed in a pretty sparse description and have the model fill in the details in a natural intuitive way. It would be very lossy, but the results would be compelling.
And you know what? That's a decent mental model of how speech works! If you just look at information content, spoken words are not very dense. But if I describe a scene you can imagine it almost as if you're seeing a video. This works because we both have the same sort of brain as well as shared experiences and intentions.
You can think of speech as incredibly effective—but also rather lossy—compression.
Your thought experiment sounds more like a "codec" than a procedural generation. I guess it is an arbitrary line given that we are using CPU, etc. But the bigger the decompressing "model" the further away from true 4k compression we are.
For example, if you can only tell something was lossy by directly comparing two instances of the same video during playback, then that's probably good enough in most situations.
It occurred to me that we could compress the hell out of written works by translating them into some super dense language, and ultimately only retain the basics of the meaning/concepts/some of the writing style. Then can re-translate that back to whatever language we want to read it in.
For compressing pictures or videos, there could be some similar translation to a much more compact representation. Would probably rely on ML heavily though.
The Kolmogorov Complexity of a video (or any other data) is the size of the shortest program which outputs that video then halts. This 4k executable is similar in spirit, but also follows strict rules about efficiency: Kolmogorov complexity places no time limits on that shortest program, whereas this program must output pixels fast enough to make the video realtime.
It's the pigeonhole principle; there are only a few long videos possibly encodable as short programs because there are only a few short programs in the first place. To get compression performance, one has to target an ever smaller subset of possible videos, which eventually starts becoming an AI-complete problem.
Is it really? Could a human meaningfully distinguish between 2^4096 different 4 minute videos?
A five-word sentence with 1000 options per word isn't 5^1000 but only 1000^5 = 10^15. If we break the movie into 5-second blocks we get 48 of them in a 4-minute movie so (10^15)^48 = 10^720 different movies, which is not bad but we're still 10^513 away. There are a lot more variations we could consider - different actors, costumes, sets, framing, color grading etc. and I think it's plausible that we could come up with enough features. Heck if you talk twice as fast, you could get (10^15)^(48*2) = 10^1440. But it's a lot bigger than I made it out to be.
Although disappointing, you seem to have the correct answer for my question.
The only thing I have to give this function, is the height/width ratio, some other ratio that define how large "corner holes" are in the LST configuration, the amount and relative position of windows and door, the starting point and NSEW direction for inside walls, and with all that, I could create a house of a story building with an inside. Of course it's not finished yet, and there isn't furniture of details, but you see that in theory, you can use procedural generation as a compression tool for human-designed structures, that no machine learning algorithm or autoencoder could really achieve.
If you associate this kind of algorithm into a well made openstreetmap database (think vector tiles which are used for GPS software), you could also recreate the whole world in 3D, with enough details to make a game that would not require that much disk memory. Recreating the roads, fences, parks, rivers, vegetation, elevation etc is difficult because it require a lot of tuning and geometry tricks, but it's very cheap in term of cpu cycle and disk.
The folks at outerra have begun making an actual software that lets you browse the entire planet in 3D. You can zoom in real time from space to 1cm. They don't have cities yet though, but they are planning for it. I want to make a game using such ambitious ideas, but it's not easy...
But, yes, at some level there is an idea of a dna seed and a process to create something much more profound, we as humanity haven't come close to cracking that, though.
For example, and output of all zeros, or the source for a a random number generator itself, or a zipped archive of a work of Shakespeare.
It's fun to think about anyway.