Daniel Barker - Cameron SLB, 2017

# Introduction

Over the last few years, I've spent the majority of my professional career developing models of complex dynamic control systems. Historically, I've focused on a physics based approach to the development of such models. Lately, however, I've been working on a new project with a heavy data science focus. One recurring theme that I've noticed in both approaches is the centrality of information. 

This has led to a broader interest in data, information, knowledge, and wisdom as well. The objective of this notebook is to learn the fundamentals of information theory in order to gain insight into the fundamentals of data science and modeling/simulation of complex systems. I have found I learn best by teaching, so this notebook will serve as a tutorial for myself (and perhaps others) in the basics of information theory. As this is first and foremost a personal learning objective, my examples will tend to draw from things that are relevant and meaningful to me, but perhaps not others. Readers can expect to see a concrete examples focused on wine, books, and the energy industry, likely among other topics.

I will draw from whatever sources are relevant to learn the material, but the primary test I will be following is <link>"Information Theory: A Tutorial Introduction"</link> by Dr. James V. Stone. 

# 1. Information Definition

## 1.1 Definition of a bit 

We all a great deal of gratitude to Claude Shannon for his 1933 paper, "A Mathematical Theory of Communication". Without Shannon's seminal work developing the formal study of information theory, all of our modern digital conveniences, from smartphones to the internet, would not be possible.

One of Shannon's central concepts was a formal definition of information, to which he ascribed the unit "bits". Being in posession of one "bit" of information allows you to choose between two <u>equally probably</u> outcomes (e.g. turning left or right on a street).

I like wine, so I'll expound upon this definition with a concrete example. Imagine you are in a restaurant. The sommelier offers you a red or white bottle of wine. Of the red bottles, I then have an option of a lighter or heavier bodied wine, say a Pinot Noir and a Cabernet Sauvignon. Likewise for the whites, I have the option of choosing a Champagne or a Chardonnay. In total, that gives us four possibilities of equal probability (in theory, we all know I would choose the Champagne or Chardonnay). How does the sommelier figure out what wine I want?

Whether he realizes it or not, he directly uses information theory. Likely, his first question would be "red or white?". My response "red" to that question contains <u>one bit</u> of information. Next, he might ask if I want a lighter or heavier bodied red - my answer "lighter bodied" to this question would also contain 1 bit of information, leading the sommelier to recommend the Pinot Noir.

This leads to a generalizable property of binary decision making that is at the heart of information theory. Given 4 possible equally probably outcomes (i.e. the four different bottles of wine), I need 2 bits of information in order to discriminate between the various choices and arrive at a decision. More generally, if I let 'n' equal the number of forks or decisions required to be made (i.e. the number of bits of information required) and 'm' the number of equally probable outcomes, I find that there is a logarithmic relationship between the number of outcomes and the bits of information required. 


```python
n = 2
print('The number of bits of information we have = ' + str(n))
# The following equation then gives us the number of possible alternatives
m = 2**n
print('The number of equally probable alternatives given that information = ' + str(m))
```

    The number of bits of information we have = 2
    The number of equally probable alternatives given that information = 4


Conversely, let's assume there are 4096 different varietals of wine in the world - how many yes/no questions (i.e. bits of information) would we have to ask to arrive at an individual varietal? This is where the logarithmic definition developed by Shannon is particularly useful:


```python
import math

m = 4096
print('The number of varietals is = ' + str(m))
n = math.log(m, 2)
print('The number information bits required to choose from that number of varietals is = ' + str(int(n)))
```

    The number of varietals is = 4096
    The number information bits required to choose from that number of varietals is = 12


This means with *only* 12 questions, we could in theory discriminate between 4096 varietals and arrive at a single choice! It's important to note that this is predicated on asking "good" questions. What is a good question - well for our purposes here, mathematically speaking a good question is one that eliminates half the possibilities. 

This brings up on important distinction between <i>bits</i> and <i>binary digits</i>. If I ask a question about the grape varietals like, "do any of them grow underground?", the answer to that question is an obvious 'no' since we're not talking about potatoes. That answer 'no' could be encoded as a binary digit (i.e. 0), but it's very important to note that in this case, this binary digit doesn't actually contain any information. Why? Because the question posed didn't allow me to narrow down the list from the set of equally probably varietals. This means that the binary digit, even though it contained a variable (= 0) it didn't actually contain any information. The key point being that bits (i.e. information) and binary digits are NOT necessarily equivalent, and to equate them is actually a category error.

# 2. Entropy of Discrete Variables

This chapter opens with a discussion of the following important ground rules:

<li>Probability</li>
<li>Discrete Variables</li>
<li>Random Variables</li>

These are all important details for more complicated problems, but for sake of brevity I won't discuss them here. Revisit this section if any of these topics seem murky.

<b>What is a message?</b> A message (:= 's') is generated by a <i>source</i>, which generated a sequence of ordered symbols from 1 to k. How do we transmit such a message?

That was one of the things Shannon defined in his original paper. One of Shannon's brilliant insights, and one that I still struggle with, is realizing that the meaning of the message was of no consequence to the <u>engineering</u> problem of sending and receiving a message across a noisy channel. As long as the message is a sequence within the set of all possible sequences, the problem of meaning is irrelevant. 

Shannon helped explain this with a diagram very similar to the one shown in the image below (see earlier reference to text). The source generates a message 's' (the sequence of ordered symbols). The message is encoded with some function 'g(s)', which results in an encoded message 'x'. The encoded message is a sequence of <i>codewords</i>. The number of symbols in 's' and the number of codewords in 'x' need not necessarily be equal; the message could be compressed. With lossless compression, the original message s can theoretically be retrieved exactly, while lossy compression irretrievably loses some of the information in the transormation from 's' to 'x'. 

This encoded message is then passed as an input into the communication channel. However, a communication channel has the problem of <i>noise</i>. This means that at the output of our channel, our message x is transormed into output y, which consists of the original encoded message 'x' plus the noise. The decoder then attempts to recover the original encoded message 'x', which is interpreted as the original message 's'.




## 2.3 Shannon's Desiderata

Shannon defined the following four requirements for his theory of information to be mathematically useful:
<li>1. Continuity - Changes in the amount of information associated with an outcome (e.g. a coin flip) must be continuous as the probability of that outcome changes. That is, there cannot be discrete jumps in the amount of information when we change the probability of a coin flip coming up heads vs. tails.</li>
<li>2. Symmetry - The amount of information contained in a sequence of outcomes is not dependent on the order of those outcomes.</li>
<li>3. Maximal Value - If a set of outcomes are all equally probable, the amount of information cannot be increased. This will make sense when we talk in more detail about entropy later, but as an example, if I have a jar of fair coins, I can't distinguish one coin from another simply by performing trials of coin flips, because the probability distribution for all will be 0.5. However, if one of the coins is unfair (i.e. not equally probable), this adds information which allows me to distinguish the unfair coin from the set of all other coins by performing a set of coin flip trials.</li>
<li>4. Additive - The information associated with a set of outcomes is obtained by adding the information of the individual outcomes (this one isn't immediately clear to me).</li>


## 2.4 Information, Surprise, and Entropy

The intuition described above in point 3 on maximal value foreshadows a more rigorous definition of surprise, which will eventually lead us to a definition of entropy. Intuitively, something is <i>surprising</i> to us if some observation deviates from an expected value. For example, if I walk into a restaurant on any given Friday night, and suddenly 10 of my friends jump out and yell "surprise" for my birthday, this is a presumably unexpected outcome (although since we would be aware that that particular day is our birthday, we might suspect a surprise could happen, which is additional <i>information</i>, but Bayes' Law is for another day...).

More concretely, we could say surprise is equal to 1/p(x). Since the maximal probability value of an event is equal to 1 (i.e. we're certain that outcome will happen), then something that is has no surprise to us at all would be equal to 1/1 = 1. If we then take the limit as the probability of an event goes to zero, my surprise grows to infinity. 

An infinite amount of surprise isn't a particularly useful concept (although it might make for an interesting philosophical question: what is an infinite amount of surprise?), so Shannon decided a better way to describe surprise would be the logarithm of 1/p(x), which regulates an infinite amount of surprise to an asymptotic value. This definition is known as the <i>Shannon information of x</i>. At its core <b>Shannon information is a measure of surprise</b>.

Using the standard notation 'h' used by Shannon, for binary outcomes we use the base 2 log (which gives us information in units of 'bits')

\begin{equation}h(x)=log_{2}(\frac{1}{p(x)}) \quad bits\end{equation}

Which is usually simplified to:

\begin{equation}h(x)=-log_{2}p(x) \quad bits\end{equation}

This leads to a key point: In order to calculate the Shannon surprise of an outcome, we need the probability distribution 'p(X)' in order to calculate the surprise of a particular outcome.

<b>Shannon Information == Entropy:</b>
Calculating the Shannon suprisal of my hypothetical surprise birthday party might be useful as a thought experiment, but practically speaking, we're likely more interested in the how much suprise, on average, is associated with an entire set of possible values. This leads into Shannon's discussion on <i>information entropy</i>, which is equivalent to the idea of Shannon surprise.


```python

```


```python

```

e39712ca57216173ee2ec619f6ec2bc5c81e31bf
ipynb
Jupyter Notebook
InformationTheory/Notebook1.ipynb
dcbark01/InformationTheory
4f883520fd63838ed5e815d786fe1bd189eb8b1c
MIT
InformationTheory/Notebook1.ipynb
dcbark01/InformationTheory
4f883520fd63838ed5e815d786fe1bd189eb8b1c
MIT
InformationTheory/Notebook1.ipynb
dcbark01/InformationTheory
4f883520fd63838ed5e815d786fe1bd189eb8b1c
MIT
Qwen/Qwen-72B
1. YES
2. YES