4 ms·

A Mini-Introduction to Information Theory

136 points by godelmachine 8y ago

kitd 8y ago
I realise I'm only a s/w dev and probably not the target audience, but I stopped reading by the end of the first page. For a mini-introduction, it assumes a lot of mathematical skill.
- improbable22 8y ago
  The funny part is that this may also be the most approachable thing Witten has ever written. In case the name isn't familiar, he's a leading theoretical physicist (with a fields medal), and I'm sure this was his idea of taking a week's holiday. https://en.wikipedia.org/wiki/Edward_Witten https://en.wikipedia.org/wiki/Edward_Witten
- throwawaymath 8y ago
  Unfortunately, information theory is not a topic that can be made accessible without several nontrivial prerequisites. This would normally constitute a graduate level topic - something to dig into after you've worked through the better part of a mathematics undergrad (particularly the upper level analysis/probability/algebra courses). Mathematics has a peculiar habit (to those outside the domain) to call things like this "introductions" - it's technically true, but unhelpful to those outside the target audience. Unless you dilute the topic to the point of unusability, this is basically what an introduction to the subject looks like. Still, it's a little hard for me to figure out what the target audience for this is. Grad students would probably want a focused textbook, so I'm guessing this is for undergrads who are only partially through the full prereqs, but who have a lot of interest in it.
  - improbable22 8y ago
    Footnote 1 explains "The article is based on a lecture at the 2018 summer program Prospects in Theoretical Physics", which is a 2-week school for grad students, most of whom would not be working on exactly this.
  - kitd 8y ago
    Yes, I was disappointed because the topic is fascinating in its abstract form, so from the title I was hoping for something a little more accessible. However it made me hunt around for more appropriate sources and I found a few, so that at least is good.
amelius 8y ago
> Suppose that one receives a message that consists of a string of symbols a or b, say aababbaaaab··· And let us suppose that a occurs with probability p, and b with probability 1−p. How many bits of information can one extract from a long message of this kind, say with N letters? They should first define what they mean by probability. For example, what am I supposed to fill in for p when b always occurs after exactly 3 times a?
- nabla9 8y ago
  If you can't figure it out from the sentence you quoted, you are not the target audience for that paper. (p is independent)
  - godelmachine 8y ago
    Please don’t discourage honest learners.
    - nabla9 8y ago
      Honest leaners don't start with complaint. I also provided the answer.
  - amelius 8y ago
    > (p is independent) But this does not hold for most real-life data streams.
    - henrikeh 8y ago
      Ph.d. student in information theory and signal processing here. It is actually a very reasonable assumption for almost all kinds of data -- given that suitable compression is applied. Data, which is well-compressed, is essentially uniformly random. When p('a') = p and p('b') = 1 - p, it means that the probability of 'a' and 'b' do not depend on anything. The probabilities must sum to 1, since it is the certain event, so p('a') + p('b') = p('a' + 'b') = p + 1 - p = 1. That is when we assume that only the symbols 'a' and 'b' are possible. If there was a relationship between 'a' and 'b', say that 'b' always occurs after every 'aaa', then the when we receive 'aaa', we know that the next symbol is 'b' -- always. So in this case the probability of 'b' has a relationship, a condition on the history, which would be written as p('b' | hist = 'aaa') = 1. A much more useful framework for this is a Markov process the a history/memory of 3. A graph for such a process can be seen here: https://mermaidjs.github.io/mermaid-live-editor/#/view/eyJjb2RlIjoiZ3JhcGggVERcbkEgLS0gYSAtLT4gQlxuQiAtLSBhIC0tPiBDXG5DIC0tIGEgLS0-IERcbkQgLS0gYiAtLT4gQVxuQiAtLSBiIC0tPiBBXG5DIC0tIGIgLS0-IEFcbkEgLS0gYiAtLT4gQSIsIm1lcm1haWQiOnsidGhlbWUiOiJkZWZhdWx0In19 https://mermaidjs.github.io/mermaid-live-editor/#/view/eyJjb... Each node is a state and the edges represent the possible outputs. The rul for such a graph is that the probabilities of the "leaving" edges must sum to 1 -- we must of course always leave the current state we are in. Notice that it takes a sequence of 'aaa' to enter node "D", afterwhich we _must_ output a 'b'. Using some matrix formulations it is possible to calculate the probabilities of 'a' and 'b' (the stationary distribution I think it is called). And to return to the first point, why is independence a reasonable assumption. In the Markov process, in node D, we known that we must always output a 'b'. In terms of information theory, if we receive 'aaa' then the 'b' is given and provides no new information. There we can perfectly predict it and we could also remove it (compress the data), without _losing_ information. 'abaabbaaab' contains the same information as 'abaabbaaa' since we _know_ that there must be a 'b'. I hope that explains why independence is reasonable.
painful 8y ago
Good find. Also see https://arxiv.org/abs/1802.05968 https://arxiv.org/abs/1802.05968
graycat 8y ago
For a "mimi-introduction" to information theory, it's essentially how many little balls can fit inside a big ball. Each little ball is from a particular signal as received with its errors in transmission, and the big ball is from the power of the signal. So, the number of little balls is how many different signals can send, with the assumed added noise level, and still have the signals all distinct at the receiver. So, sure, if send with more power have a larger big ball and more signals. Also if have lower noise, then signals are corrupted less, get smaller little balls, and can send more signals. Sorry, that's my best summary from the time I did look at information theory some years ago!!!
gajjanag 8y ago
Witten's talk at the IAS on this subject may also be of interest: https://www.youtube.com/watch?v=XYugyhoohhY https://www.youtube.com/watch?v=XYugyhoohhY
- throwawaymath 8y ago
  Ed Witten gave a talk on information theory? At IAS?! Well, now I've got to bookmark this for later; thanks!
- ivan_ah 8y ago
  Halfway through the talk he switches to discussing quantum information theory. Here is an excellent book on this subject "From Classical to Quantum Shannon Theory" https://arxiv.org/abs/1106.1445 https://arxiv.org/abs/1106.1445

136 points by godelmachine 8y ago

kitd 8y ago

I realise I'm only a s/w dev and probably not the target audience, but I stopped reading by the end of the first page. For a mini-introduction, it assumes a lot of mathematical skill.

improbable22 8y ago
The funny part is that this may also be the most approachable thing Witten has ever written. In case the name isn't familiar, he's a leading theoretical physicist (with a fields medal), and I'm sure this was his idea of taking a week's holiday. https://en.wikipedia.org/wiki/Edward_Witten https://en.wikipedia.org/wiki/Edward_Witten
throwawaymath 8y ago
Unfortunately, information theory is not a topic that can be made accessible without several nontrivial prerequisites. This would normally constitute a graduate level topic - something to dig into after you've worked through the better part of a mathematics undergrad (particularly the upper level analysis/probability/algebra courses). Mathematics has a peculiar habit (to those outside the domain) to call things like this "introductions" - it's technically true, but unhelpful to those outside the target audience. Unless you dilute the topic to the point of unusability, this is basically what an introduction to the subject looks like. Still, it's a little hard for me to figure out what the target audience for this is. Grad students would probably want a focused textbook, so I'm guessing this is for undergrads who are only partially through the full prereqs, but who have a lot of interest in it.
- improbable22 8y ago
  Footnote 1 explains "The article is based on a lecture at the 2018 summer program Prospects in Theoretical Physics", which is a 2-week school for grad students, most of whom would not be working on exactly this.
- kitd 8y ago
  Yes, I was disappointed because the topic is fascinating in its abstract form, so from the title I was hoping for something a little more accessible. However it made me hunt around for more appropriate sources and I found a few, so that at least is good.

amelius 8y ago

> Suppose that one receives a message that consists of a string of symbols a or b, say aababbaaaab··· And let us suppose that a occurs with probability p, and b with probability 1−p. How many bits of information can one extract from a long message of this kind, say with N letters? They should first define what they mean by probability. For example, what am I supposed to fill in for p when b always occurs after exactly 3 times a?

nabla9 8y ago
If you can't figure it out from the sentence you quoted, you are not the target audience for that paper. (p is independent)
- godelmachine 8y ago
  Please don’t discourage honest learners.
  - nabla9 8y ago
    Honest leaners don't start with complaint. I also provided the answer.
- amelius 8y ago
  > (p is independent) But this does not hold for most real-life data streams.
  - henrikeh 8y ago
    Ph.d. student in information theory and signal processing here. It is actually a very reasonable assumption for almost all kinds of data -- given that suitable compression is applied. Data, which is well-compressed, is essentially uniformly random. When p('a') = p and p('b') = 1 - p, it means that the probability of 'a' and 'b' do not depend on anything. The probabilities must sum to 1, since it is the certain event, so p('a') + p('b') = p('a' + 'b') = p + 1 - p = 1. That is when we assume that only the symbols 'a' and 'b' are possible. If there was a relationship between 'a' and 'b', say that 'b' always occurs after every 'aaa', then the when we receive 'aaa', we know that the next symbol is 'b' -- always. So in this case the probability of 'b' has a relationship, a condition on the history, which would be written as p('b' | hist = 'aaa') = 1. A much more useful framework for this is a Markov process the a history/memory of 3. A graph for such a process can be seen here: https://mermaidjs.github.io/mermaid-live-editor/#/view/eyJjb2RlIjoiZ3JhcGggVERcbkEgLS0gYSAtLT4gQlxuQiAtLSBhIC0tPiBDXG5DIC0tIGEgLS0-IERcbkQgLS0gYiAtLT4gQVxuQiAtLSBiIC0tPiBBXG5DIC0tIGIgLS0-IEFcbkEgLS0gYiAtLT4gQSIsIm1lcm1haWQiOnsidGhlbWUiOiJkZWZhdWx0In19 https://mermaidjs.github.io/mermaid-live-editor/#/view/eyJjb... Each node is a state and the edges represent the possible outputs. The rul for such a graph is that the probabilities of the "leaving" edges must sum to 1 -- we must of course always leave the current state we are in. Notice that it takes a sequence of 'aaa' to enter node "D", afterwhich we _must_ output a 'b'. Using some matrix formulations it is possible to calculate the probabilities of 'a' and 'b' (the stationary distribution I think it is called). And to return to the first point, why is independence a reasonable assumption. In the Markov process, in node D, we known that we must always output a 'b'. In terms of information theory, if we receive 'aaa' then the 'b' is given and provides no new information. There we can perfectly predict it and we could also remove it (compress the data), without _losing_ information. 'abaabbaaab' contains the same information as 'abaabbaaa' since we _know_ that there must be a 'b'. I hope that explains why independence is reasonable.

painful 8y ago

Good find. Also see https://arxiv.org/abs/1802.05968 https://arxiv.org/abs/1802.05968

graycat 8y ago

For a "mimi-introduction" to information theory, it's essentially how many little balls can fit inside a big ball. Each little ball is from a particular signal as received with its errors in transmission, and the big ball is from the power of the signal. So, the number of little balls is how many different signals can send, with the assumed added noise level, and still have the signals all distinct at the receiver. So, sure, if send with more power have a larger big ball and more signals. Also if have lower noise, then signals are corrupted less, get smaller little balls, and can send more signals. Sorry, that's my best summary from the time I did look at information theory some years ago!!!

gajjanag 8y ago

Witten's talk at the IAS on this subject may also be of interest: https://www.youtube.com/watch?v=XYugyhoohhY https://www.youtube.com/watch?v=XYugyhoohhY

throwawaymath 8y ago
Ed Witten gave a talk on information theory? At IAS?! Well, now I've got to bookmark this for later; thanks!
ivan_ah 8y ago
Halfway through the talk he switches to discussing quantum information theory. Here is an excellent book on this subject "From Classical to Quantum Shannon Theory" https://arxiv.org/abs/1106.1445 https://arxiv.org/abs/1106.1445