The Most Important (and Surprising) Result from Information Theory
ฝัง
- เผยแพร่เมื่อ 24 มิ.ย. 2024
- The machine learning consultancy: truetheta.io
Join my email list to get educational and useful articles (and nothing else!): mailchi.mp/truetheta/true-the...
Want to work together? See here: truetheta.io/about/#want-to-w...
Information Theory contains one idea in particular that has had an incredibly impact on our society.
David MacKay's lecture: • Information Theory, Pa...
SOCIAL MEDIA
LinkedIn : / dj-rich-90b91753
Twitter : / duanejrich
Github: github.com/Duane321
Enjoy learning this way? Want me to make more videos? Consider supporting me on Patreon: / mutualinformation
SOURCES
Chapters 1, 9 and 10 from [1] were the primary source. Chapter 7 of [3] was a secondary source. [2] is inclusive of Shannon's 1948 original paper and provided useful historical context.
[1] D. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press. 2003.
[2] C. E. Shannon and W. Weaver. The Mathematical Theory of Communication. University of Illinois Press. 1964
[3] T. M. Cover and J. A. Thomas. The Elements of Information Theory, 2nd Edition. Wiley-Interscience. 2006.
TIMESTAMPS
0:00 Problem Statement and the R3 Coding Strategy
2:06 Bit Error Probability and Rate
3:30 The Trillion Dollar Question
4:12 Claude Shannon Proves Something Remarkable
6:11 Sidebar on other Educational Content
6:49 The Trick
7:38 Check out David Mackay's Textbook and Lectures, plus Thank You
To quote my PhD supervisor, Prof. James L. Massey: "Do Communication Engineers Need Information Theory? - Not unless they want to understand what they are doing and to be at the forefront of future advances in communications!"
MacKay's book is brilliant. I used it extensively in grad school. I love that all the lectures are online.
Yea! I've long enjoyed the text but I only recently discovered the lectures online. Such a pleasure learning the book from the man himself.
@@jakebrowning2373In the description
Fibonacci sequence
Theory information
Cuasi crystals
i expected you to explain how the encoding works 😢
I get that. Weirdly, Shannon gave a non constructive proof. He just showed the coding strategies exist, not how to construct them. And coding theory, the theory for constructing coding strategies, is a very deep topic. 3Blue1Brown explains some codes much better than I could, so you could check those out if you haven't already.
Numberphile recently published a video on one of these encodings, titled "Error Correcting Curves - Numberphile"
Three blue 1 brown's videos on hamming codes are great for the mathematical explanations
@@Mutual_Informationthabks can you not do a condensed version of that?
@@leif1075What? Can you not decide what others want or dont want to watch? Thx.
Same reason why it’s possible to encode frequencies up to half of the sample rate. He was a brilliant guy.
Only under perfect conditions; you would want to go higher in sampling frequency if you wish to maintain high fidelity.
I am a little bit confused as I thought half the sampling rate thing was from Nyquist. What is the relation between Shannon in this case?
so, with f=0.1, there EXISTS an encoding scheme such that the data transfer rate is only about halved, but the probability of error on any one encoded bit is less than 1/Σ(1000) where Σ is the Busy Beaver function.
and it only halves the data rate. and practically deletes noise. math is incredible.
Wow. This video did not feel like 9 minutes long. Amazing work
Just stumbled upon your channel, you’re amazing dude
Thank you - it comes from trying too hard :)
I do research in information and communication theory for a living, and I must say this is one of the best introductory videos to Shannon's coding theorem that I have come across. The only thing I would object to is that the mention of "doubling the message length" at 5:07 comes out of nowhere: it might be confusing to newbies, because 1) you haven't talked about "message length" up until then (you only do at the very end), 2) Shannon's theorem does not say anything about how much longer ("doubling"?) the message length ought to be. But nevertheless, congrats for the video's quality and for your channel in general. I would be thrilled to see a version 2.0 of this, perhaps with some extensions and additional explanations. Or even a short series (Hamming codes, error exponents, you name it)
Hey it's very cool to get the eyes of a pro on this. I try to consider that as I'm creating it and that helps keep the standard high. And thank you for your compliment and notes. Some of it is due to me making a rather condensed video.. but I shouldn't let that cut out essential meat. I create reflection notes on each vid, and so this will be included.
And regarding a follow up video, I don't have solid plans at the moment, but a follow up vid is likely over the longer term. I was thinking about asymptotic equipartition property actually, since understanding that reveals a lot about many info theory proofs.
@@Mutual_Informationsuch respect online brings me joy
Love your videos!
channel capacity reaches its minimum 0 when f is 0.5 and maximum 1 when f tends to 0. Also it would be interesting to see whether the line between achievable and non achievable is linear after channel capacity.
lol yea you can't communicate anything if there is a 50-50 chance of a bit flipped.. everything is noise. And regarding your second point, it is linear. That was another component of Shannon's proof. His prove is piecewise like that.
Seems like it's because 0.5 is actually the highest error rate, if you're using flips as errors. At 1.0 you're just reversing the message.
My instinct was that we should be able to do much better than what you initially suggested by using something like a checksum for credit cards. The problem is that just tells you the message is wrong, not how to retrieve the correct one.
Cool video! At the right time too as I'm working on MDS now.
The quality of these videos is getting better and better. Keep up this great work!
Your channel is excellent. Extremely instructive and the videos are clearly thought out really well
Glad you think so!
I rewatched the video because i don't remember any details. then i afterwards realized that there isn't one to begin with...
I'll watch the lectures next.
5:42 This was a great moment! =)
Huge moment!
Thanks!
Great Video! :)
You have all the exact same mannerisms as the channel “Whaddo You Meme” 😂. Love the video!
I vaguely remember (from studies at college) something about using XOR to detect data errors
This is so cool!
Nice video! For readers who are interested in machine learning, there is a nice (but distant) analogue of this for binary classification. Suppose you are asked to build an AI that classifies whether an image is that of a cat or a dog. What is the best error rate that you can get? Turns out it is independent of the size of the dataset!
Excellent. So many speakers throw graphs out without properly explaining the axes. Not here!
Can you please do a video on Reed Solomon encoding?
I dimly remember Huffman code. Is that an example of the coding methods mentioned in this video? If yes, it would have been helpful to mention it.
Huffman codes, for certain distributions over inputs, can achieve the lossless rate limit C. But for other input distributions, it can't and other methods will be more efficient (e.g. Arithmetic coding). In retrospect, I agree.. the video should have had more detail on some specific modern coding strategies.
Shannon invented relu!
Great video! Btw your mic is picking up occasional plosives from your voice at very low frequencies and these are booming quite loud on a decent sound system with a subwoofer.
Thank you very much, I didn't know that. I've taken down a note to fix it going forward
Can you please suggest me best books for learning binary or digital systems in general? The books I have don't do a good job at motivating the concepts and explaining them in a "rediscoverable" manner.
"digital systems" is pretty general, so it's hard to say. For information theory, my go-to is "The Elements of Information Theory" by cover and for this, it's the book I showed. Another one is "Understanding Digital Signal Processing", which is for signal processing. These are all big ambitious books FYI.
@@Mutual_Information thank you!
Do you have a discord server?
Arduino is a very fun way to learn some low level programming. Also NAND2tetris is a free comprehensive course that explains computers from transistors to logic gates to binary to machine code and more
This isn't a result, it's just a lecture.
Google’s ads have made TH-cam virtually unwatchable. The advertisers who have signed up for this subterfuge are totally despicable.
Have we found the "optimal" encoding then? Or is it still "out there"?
We've gotten very, very close, but it depends on some assumptions about the channel. There are different types of noisy and flip operations. But, to answer what you're looking for, search "Turbo Code"
How does language effect the error correction? If the binary code was completely random, then there is no language. Though if there were some standardization or organization within the code could we use an algorithm to identify the MOST PROBABLE intended sequence, right? Like if I’m trying an essay and accidentally type “mathimativs’ where the word ‘mathematics’ was implied, since there is a standardization of the language, we can error correct both letters to find the intended word. So my question is: does imposing a language increase the likelihood of error correction?
Sort of. You can think of speaking the same language as sharing knowledge of the encoding and decoding algorithms. Without that prior knowledge (information) there isn't much you can do error correction wise.
Interestingly, this applies to language learning (linguistics) too. There has to be prior knowledge about the rules of a language or else it cannot be learned except in the trivial case of a finite language where the learner is given all the possible sentence/statements.
I was about to say in the beginning “but the noise floor…”
Great video! What's your background, by the way? Seems like you've maybe done a PhD in this kind of thing?
Thank you, much appreciated. And my background is in financial engineering. Practically, I've just been modeling mostly economic data (prices, market dynamics, consumer behavior), and so that made a lot of machine learning relevant. And when studying that, I came across information theory (most with Cover and Thomas' text) and have found it useful + interesting.
@@Mutual_Information I'm a data scientist myself, with no background in info theory, and modelers don't talk much about it. But through effort I found some good sources, and now I see that the relationship between compression and probability theory is fascinating! Info theory has legitimately sharpened my thinking on what it means to predict something or have a good model for it.
@@user__214 Nice to meet a fellow DS! And I'm with you - a big emphasis of MacKay's work was the interplay of info theory + ML.. many interesting things happens in their intersection.
~ 4:43 - But, this is the crux of the problem!
I assume the flip probability is random...and not fixed with Boolean switches.
this creates the error, chance.
your scrambling the message ( slightly ) , not hiding it.
creates a receiver error.
cause the flip is not a fixed switch.
you would need to use like a roller, on an enigma, and flip with a algorithm.
and create "fake" noise.
what is your degree/scientific background?
woah that’s nuts
Great channel, I like to watch your videos after work but always find them a bit too quiet. Maybe it's something with my hearing.
That's good for me to know. Are other videos, outside of my channel, also quiet?
Well like he explained, a noisy channel can cause issues!
@@Mutual_Information I don't think so. I always remember to overamplify the sound when watching your channel.
@@jakubbelicki5755 I see, I'll look into it. Thanks!
Honestly, I was expecting a more exponential-looking curve. Is this a simplification? Isn't there any more effective error correction codes than the one used in the paper? I understand that it's not about the exact coding techniques, still can't wrap my head around on how they managed to neglect it. The paper should make it clear, i guess.
Interestingly, the paper didn't use any error correcting codes. It was a non-constructive proof, where they show things exist without giving any examples. And in doing so, they show the achievability curve looks exactly as I showed. It's just flat and then a straight line. Not what anyone expected.
@@Mutual_Information Ok, thanks for the answer
Combination of mnim graphics and real life footage looks unusual for me
Shout out to the Hadamard matrix and transform to recover n/2 +1 bits 😊
@Mutual_Information, I wanna ask about E.T. Jaynes book about Probability Theory and the Logic of Science. I just don't know where to ask, since the web also says the same thing. It is common knowledge that AND, NOT, and OR logic gates can create all logic operations of arbitrary number of variables. Thus, {AND, NOT, OR} constitutes an adequate set. However, the only single element adequate sets are {NAND} and {NOR} according to the book. Why does this SWITCH logic gate, as I call it, not an adequate set.
This is its truth table
A | B | Switch(A, B)
F | F | F
F | T | F
T | F | T
T | T | T
I discovered that the SWITCH gate can simulate AND, OR, and NOT, so it must be an adequate set. But why does the book and wikipedia not acknowledge this gate as a single element adequate set?
I didn't understand the "trick". Could anyone explain to me?
Sorry about that. That’s on me. I probably shouldn’t have used the word trick. What surprising is that we can arbitrarily small error probability at reasonable fast. The confusing thing is.. how can it be *arbitrarily small*? How is an error prob if 10^-1000 achievable if you only need to double the message length? Well.. such probabilities are only realize-able over extremely long messages.. in other words, you have to send very long messages.. and those very long messages are encoded as even longer messages.. (only about 2x longer in the vid). And that’s how the rate is reasonable.
So let me see if I understand what you say. The fact that the message length needs to be big enough is that I can group it into L chunks of K bits and then I can add redundancy to these chunks in a way that the coded chunk has a length of N bits. Then the addition of that redundancy at a chunk-level has the effect of increasing the length of the original message by a factor of 2 (for example) reducing the rate by one-half. So, the astonishing thing is that I can achieve an arbitrarily small Pb even by adding a small redundancy considering the total message (instead of L×K bits I will send L×N, in a way that L×N = 2(L×K)) and in the case of small message lengths I can't use this because the effect of the redundancy will be at a bit-level instead of a chunk-level, that is the "trick"?
@Mutual_Information so essentially you have 2 parameters and not 1. The wanted probability and the message length.
Could you say that for any given message length N, the best encoding tends to some other value smaller than c? Maybe even 0 for any message of at most N? But it only tends to c if the length of the message tends to infinity?
Error correcting codes?
Indeed, but not specific to any single coding strategy
I identify as 20-something. I am not 40+. That is just a datetime error.
Great ... but can you fix the "... that has gad an ..."?
Wow, that's embarrassing - thanks for the catch
What happened DJ? You quit on us? No new vids in four months! 😐
I'm working on it! It's a fat one. 30+ minutes. And made of solid gold.
@@Mutual_Information Coolio!
I heard it. You must have had a noisy channel. Try again, and good luck.
Sorry but i learned nothing from this video... Waste of time
thank you! love from india.
In italian accent 🤌"Galois o' here buddy"
ב''ה, 🪑