<jupyter_start><jupyter_text>Information TheroyThis notebook contains an introduction to information theory and some simple examples.<jupyter_code>import numpy as np<jupyter_output><empty_output><jupyter_text>From Wikipedia:The information entropy, or just entropy, is a basic quantity in information theory associated to any random variable. It can be interpreted as the average level of "information" or "uncertainty" inherent in the variable's possible outcomes. Intuitively we can think of it like this. A variable with no randomness (100% of a single event) carries no new information, since we know the outcome of all future events. However, variables with more randomness carries more information, since we can't perfectly predict the outcome of all future events for that variable. There is an analogy to physics here. A lot of disorder (i.e randomness) => high entropy, low level of disorder => low entropy.It makes intuitive sense that entropy is maximized by the uniform distribution, since all events are then equally probable.   Language ExampleAs an example, consider a random variable $S$ representing a language. Which language contains the most information? Assume that we have a language of 4 characters, where each character occurs with some probability. How much information does the language contain? Example 1)A: 25%B: 25%C: 25%D: 25%        *       / \      *   *     / \ / \    A  B C  D    We must ask two questions to know the next character in a random string, as visualized above. Therefore, the language contains two bits of information. Another way to see it is that we can encode the language with two bits.A: 00B: 01C: 10D: 11 Example 2)A: 50%B: 12.5%C: 12.5%D: 25%        *       / \      A   *         / \        D   *           / \          B   C    Here, we might get the next character after one question! What is the expected number of questions? This is given by the formula:$\sum_s Pr(s) \cdot n(s)$where $s$ is a character, $Pr(s)$ the probability of its occurence and $n(s)$ the number of questions we need to ask. In this case we get:$\frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{4} \cdot 3 = \frac{2}{4} + \frac{2}{4} + \frac{3}{4} = \frac{7}{4} =  1.75 $ Note that $n(s)$ can be expressed in terms of $Pr(s)$ using $log$. For example, we have that $Pr(A) = \frac{1}{2}$, and clearly $log(\frac{1}{\frac{1}{2}}) = log(2) = 1 = n(A)$. We use 2 as a base since that's the number of branches in the language tree. This allows us to calculate the number of expected bits using only the probabilities:$\sum_s Pr(s) \cdot n(s) =  \sum_s Pr(s) \cdot log(\frac{1}{Pr(s)}) = \sum_s Pr(s) \cdot (log(1) - log(Pr(s))) = \sum_s Pr(s) \cdot - log(Pr(s)) = - \sum_s Pr(s) \cdot log(Pr(s))$The number of expected bits is also referred to as the **Entropy** of the language, and is commonly denoted $H(S)$ where $S$ is a random variable, which in this example was a language.  **Definition** $H(X) = - \sum_x Pr(x) \cdot log(Pr(x))$<jupyter_code>def entropy(probabilities: np.ndarray):
    assert len(probabilities.shape) == 1  # Assume 1D array
    
    return -np.sum(probabilities * np.log2(probabilities))
example_one = np.array([0.25, 0.25, 0.25, 0.25])
example_two = np.array([0.5, 0.25, 0.125, 0.125])

print(f"Entropy of example one: {entropy(example_one)}")
print(f"Entropy of example two: {entropy(example_two)}")<jupyter_output>Entropy of example one: 2.0
Entropy of example two: 1.75
{'fraction_non_alphanumeric': 0.11046342174293208, 'fraction_numerical': 0.027688720489653162, 'mean_word_length': 3.840620592383639, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '132085', 'license': 'MIT', 'n_tokens_mistral': 1090, 'n_tokens_neox': 1022, 'n_words': 466, 'path': 'information_theory.ipynb', 'repo_name': 'Nickedude/information_theory', 'size': '3431'}