Compression is right at the junction of computer science and information theory. It might be what joins them together. For example, if you have infinite space, any algorithm can be O(n), trivially fast, with a giant lookup table between inputs and outputs. In practice you want to find a smaller but reasonably fast equivalent program to represent the same mapping -- optimizing a program is lossless compression. In machine learning, model training takes a large one-dimensional array (such as a string with all the text on the Internet) and lifts it into a multidimensional space. Language models create output strings patterned like the input string, while storing less data than the complete input string -- machine learning is a type of lossy compression.
Any further recollections to help drill down and find it?
- [0]: https://www.pcmag.com/encyclopedia/term/data-compression
https://books.google.com/books?id=gCfzPMoPJWgC&lpg=PP1&pg=PA...
https://books.google.com/books?id=eX8w8B-OhIIC&lpg=PA371&pg=...
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 to artificial intelligence (whatever that ends up meaning).
How so? Aren't the networks' weights orders of magnitude smaller than the training data?
Check out Karpathy’s video “let’s build GPT from scratch”
Using the exact same data (a 1MB text file containing all of Shakespeare’s works), he goes from several models that spit out garbage, to a GPT model that outputs good looking garbage
The only changes are the algorithms used, the data is always the same
There is a big opportunity in creating small models that can “learn” and then “reason about”, very little data
I can't find any archives for Dr Dobb's, but some articles are in his personal site, for example this one about arithmetic coding: https://marknelson.us/posts/1991/02/01/arithmetic-coding-sta...
Much appreciation to all the folks who put in the work to make these things interesting and accessible.
The compression rabbit hole can be a rewarding to go down if you haven't. Besides the tech itself making a lot of things work better (like a Web built on human-readable formats, or more specialized stuff like Parquet or other columnar formats, or video on the lossy side), it can give you some tools or perspective that apply elsewhere, e.g. to other probablistic stuff like caching and predictions for lossless compression, or other signal-processing stuff for lossy compression.