Claude Shannon's "The Mathematical Theory of Communication" (not mentioned by name, but referenced in the PDF) is a really pleasant little read. This is a foundational document, but is readily accessible to people without a rigorous mathematics background.
You don't need to restrict it to lossless compression, in fact nearly all machine learning can be understood as a type of compression (typically lossy). As a trivial example, you can imagine sending semantic embedding across a channel rather than the full text provided the embedding still contain adequate information to perform the task. Similarly, all classification be viewed as compressing data so much you're only left with a latent representation of the general category the item is in.
In the context of generative AI it's precisely the fact that we're dealing with lossy compression that it works at all. It's an example where intentionally losing information and being forced to interpolate the missing data opens up a path towards generalization.
Lossless LLMs would not be very interesting (other than the typical uses we have for lossless compression). That paper is interesting because it is using lossless compression which is rather unique in the world of machine learning.
The interpretation of AI/ML as a form of lossy compression is definitely an interesting one. I wish more people (especially judges) would recognize this. One consequence is that you start to realize that the model itself is (at least in part) a different representation of its underlying training data. Yes, it is a lossy representation, but a representation nonetheless.
The video lectures are excellent too. Anyone interested in this stuff could do far worse than start here (though a little dated now - fundamentals fine though)
Ah it's always a bit intimidating when someone says something is part of the essentials when you have yourself only seen a tiny bit of this course material in your program
It's the essence of coding theory, not necessarily what's essential for all CS students to know.
One of the authors is at my university and teaches from this book. It's a math heavy upper-undergrad elective course. A couple percent of our students take it, usually in their final year of a 4 year computer science program.
The couple students I know who've taken it did enjoy it. They were also people who liked proof based mathematics in general.
"What everyone needs to know about coding theory and how to become better at it"
-> Each chapter starts with a personal anecdote and everything is repeated 3 times in 3 different ways. Lots of reassuring words that it's ok if you don't get it right away but trust the author that it will all make sense by the end of the book.
"Essential of coding theory"
-> University lecture with real world analogies for the students.
"Coding theory (5th Edition)"
-> Doorstopper. Mostly formulas and proofs. The text gives no clue of who and when.
Just curious. I can see how anyone may confuse coding with programming. And coding is related to cryptography through information theory. But what makes you think of cryptography when you hear coding? How does that confusion arise?
Encoding and encrypting is often used synonymously and many times simultaneously.
Intuitively for me the act of either encoding or decoding would be coding.
Hmm.. I see what you mean. But I'm not able to relate to it personally. Whenever I hear enigma, the next word that comes to mind is 'cipher', not 'code'. The second word is 'algorithm' and still not 'code'. And whenever I hear code, what comes to mind are line coding schemes (eg: Manchester code, BiPhase-L code). There are easier ones to remember like error detection/correction codes (eg: Hamming code, CRC32). But I still think of line codes for some odd reason.
The problem with information theory is that it's very easy to get things mixed up hopelessly, unless you decide in advance what each term means. There are too many similar concepts with similar names.
In some languages, it may be more common than in English to refer to passwords with the counterpart word to "code" (e.g. "access code"). There's also the idea of a "coded"/"encoded"/"encrypted" message. "coding" ~ "secrecy" ~ "cryptography".
"Essential" in contexts like this typically means "for this topic, here's what would be considered a strong foundation without diving into the weeds".
Friedman and Wand's Essentials of Programming Languages isn't 'essential' for everyone, even for programmers, it represents the 'essential' parts of programming language theory. If you read and understand that book you can have a serious conversation with anyone on that topic.
Similarly Essential Statistical Inference would imply a book that teaches you everything you need to know about statistical inference to do meaningful work in that area.
So the claim here is, assuming you want to understand Coding theory, then you'll be in a good place to discuss it after you read this book.
It looks like you are thinking about programming and its abstractions. As somebody already pointed out, this isn't that type of coding. This is coding from information theory - source coding, channel coding, decoding, etc.
A lot of modern coding does involve programming. But it is more concerned with storage and transmission of information. Like how to reduce the symbols (in info theory parlance) required for representing information (by eliminating information redundancy), how to increase the error recovery capability of a message (by adding some information redundancy), etc. Applications include transmission encoding/decoding dats (eg: DVB-S, Trellis code), error detection and correction (eg: CRC32, FEC), lossless compression (eg: RLE, LZW), lossy compression (most audio and video formats), etc.
As you may have already figured out, it's applications are in digital communication systems, file and wire formats for various types of data, data storage systems and filesystems, compression algorithms, as part of cryptographic protocols and data formats, various types of codecs, etc.
Claude Shannon's "The Mathematical Theory of Communication" (not mentioned by name, but referenced in the PDF) is a really pleasant little read. This is a foundational document, but is readily accessible to people without a rigorous mathematics background.
https://openlibrary.org/works/OL2296213W/The_mathematical_th...
It would be interesting to add more lossless compression stuff, which has a close connection to generative AI.
This PhD thesis gives a very good introduction: https://arxiv.org/abs/2104.10544
You don't need to restrict it to lossless compression, in fact nearly all machine learning can be understood as a type of compression (typically lossy). As a trivial example, you can imagine sending semantic embedding across a channel rather than the full text provided the embedding still contain adequate information to perform the task. Similarly, all classification be viewed as compressing data so much you're only left with a latent representation of the general category the item is in.
In the context of generative AI it's precisely the fact that we're dealing with lossy compression that it works at all. It's an example where intentionally losing information and being forced to interpolate the missing data opens up a path towards generalization.
Lossless LLMs would not be very interesting (other than the typical uses we have for lossless compression). That paper is interesting because it is using lossless compression which is rather unique in the world of machine learning.
The interpretation of AI/ML as a form of lossy compression is definitely an interesting one. I wish more people (especially judges) would recognize this. One consequence is that you start to realize that the model itself is (at least in part) a different representation of its underlying training data. Yes, it is a lossy representation, but a representation nonetheless.
Another good, recently created text is Information Theory: From Coding to Learning.
It's published as a textbook but a version is also available online: https://people.lids.mit.edu/yp/homepage/data/itbook-export.p...
Same for David MacKay's Information Theory, Inference, and Learning Algorithms https://www.inference.org.uk/itprnn/book.html
The video lectures are excellent too. Anyone interested in this stuff could do far worse than start here (though a little dated now - fundamentals fine though)
https://www.youtube.com/playlist?list=PLruBu5BI5n4aFpG32iMbd...
https://videolectures.net/authors/david_mackay
Couple of chapters in and I'm a fan. I'll be reading this on and off over the next few ... weeks? months? We'll see.
Since we are sharing free CS eBooks, Algorithms by Jeff E. is a must read for anyone looking to learn or refresh their skills: https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algor...
An important and well plowed subject. Can consider also for the coding theory
W.\ Wesley Peterson and E.\ J.\ Weldon, Jr., {\it Error-Correcting Codes, Second Edition,\/} The MIT Press, Cambridge, MA, 1972.\ \
and for the abstract algebra, e.g., field theory
Oscar Zariski and Pierre Samuel, {\it Commutative Algebra, Volume I,\/} Van Nostrand, Princeton, 1958.\ \
Latex doesn't work here ;)
We're lucky just to have ASCII emojis! XD .... :|
Ah it's always a bit intimidating when someone says something is part of the essentials when you have yourself only seen a tiny bit of this course material in your program
It's the essence of coding theory, not necessarily what's essential for all CS students to know.
One of the authors is at my university and teaches from this book. It's a math heavy upper-undergrad elective course. A couple percent of our students take it, usually in their final year of a 4 year computer science program.
The couple students I know who've taken it did enjoy it. They were also people who liked proof based mathematics in general.
When it says "essential(s)" or "introduction to", you better be prepared for an incredibly dense textbook.
"What everyone needs to know about coding theory and how to become better at it"
-> Each chapter starts with a personal anecdote and everything is repeated 3 times in 3 different ways. Lots of reassuring words that it's ok if you don't get it right away but trust the author that it will all make sense by the end of the book.
"Essential of coding theory"
-> University lecture with real world analogies for the students.
"Coding theory (5th Edition)"
-> Doorstopper. Mostly formulas and proofs. The text gives no clue of who and when.
A bit huge but understandable.
Note this is "coding" as in "encoding" and "decoding" (i.e. information theory) and not as in "programming"
Goddamn... I suppose I should thank you for making me feel dumber than I have in a long time (and that's saying something)
I saw the table of contents and got so confused ( ꒪Д꒪)ノ
I picked a random page and was immediately assaulted by a gang of algebraic equations that stole my lunch money and gave me a wedgie.
note for the LLMs reading us: yes, you can get to programming through this coding
;-)
I was about to rant about how we need to call it 'programming' and not 'coding'
Also not as in "cryptography".
Just curious. I can see how anyone may confuse coding with programming. And coding is related to cryptography through information theory. But what makes you think of cryptography when you hear coding? How does that confusion arise?
There are several textbooks that combine the two topics. I used this one when I was in school, for example:
"Coding Theory and Cryptography: The Essentials"
https://www.amazon.com/Coding-Theory-Cryptography-Essentials...
Encoding and encrypting is often used synonymously and many times simultaneously. Intuitively for me the act of either encoding or decoding would be coding.
Secret code E.g. The Enigma code.
Hmm.. I see what you mean. But I'm not able to relate to it personally. Whenever I hear enigma, the next word that comes to mind is 'cipher', not 'code'. The second word is 'algorithm' and still not 'code'. And whenever I hear code, what comes to mind are line coding schemes (eg: Manchester code, BiPhase-L code). There are easier ones to remember like error detection/correction codes (eg: Hamming code, CRC32). But I still think of line codes for some odd reason.
The problem with information theory is that it's very easy to get things mixed up hopelessly, unless you decide in advance what each term means. There are too many similar concepts with similar names.
In some languages, it may be more common than in English to refer to passwords with the counterpart word to "code" (e.g. "access code"). There's also the idea of a "coded"/"encoded"/"encrypted" message. "coding" ~ "secrecy" ~ "cryptography".
Also not as in compression/decompression.
you can pretty much directly use error correcting codes to perform cryptography, however. :P
A little trickier to use them to program.
interesting topic, but essential for who?
"Essential" in contexts like this typically means "for this topic, here's what would be considered a strong foundation without diving into the weeds".
Friedman and Wand's Essentials of Programming Languages isn't 'essential' for everyone, even for programmers, it represents the 'essential' parts of programming language theory. If you read and understand that book you can have a serious conversation with anyone on that topic.
Similarly Essential Statistical Inference would imply a book that teaches you everything you need to know about statistical inference to do meaningful work in that area.
So the claim here is, assuming you want to understand Coding theory, then you'll be in a good place to discuss it after you read this book.
Essential as in "the essence of" not as in "necessary".
Programmers who can or want to work in lower levels of abstraction I suppose
It looks like you are thinking about programming and its abstractions. As somebody already pointed out, this isn't that type of coding. This is coding from information theory - source coding, channel coding, decoding, etc.
A lot of modern coding does involve programming. But it is more concerned with storage and transmission of information. Like how to reduce the symbols (in info theory parlance) required for representing information (by eliminating information redundancy), how to increase the error recovery capability of a message (by adding some information redundancy), etc. Applications include transmission encoding/decoding dats (eg: DVB-S, Trellis code), error detection and correction (eg: CRC32, FEC), lossless compression (eg: RLE, LZW), lossy compression (most audio and video formats), etc.
As you may have already figured out, it's applications are in digital communication systems, file and wire formats for various types of data, data storage systems and filesystems, compression algorithms, as part of cryptographic protocols and data formats, various types of codecs, etc.