{"id":355705,"date":"2024-05-20T23:14:19","date_gmt":"2024-05-20T23:14:19","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=355705"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-05-20T23:14:19","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=355705","title":{"rendered":"1. Information theory + ML. Entropy<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

I’ve long wanted to create educational materials on the topic of Information Theory<\/a> + Machine Learning<\/a>. I found some old drafts and decided to polish them up here, on Habr. <\/p>\n

Information Theory and Machine Learning seem to me like an interesting pair of fields, the deep connection between which is often unknown to ML engineers, and whose synergy has not yet been fully revealed. <\/p>\n

When I tell colleagues that LogLoss <\/a>on the test set and Mutual Information<\/a> between the prediction and the predicted value are directly related, and that you can get one from the other using a simple formula, they often express genuine surprise. There is a link from the LogLoss<\/a> Wikipedia page to Mutual Information<\/a>, but that’s about it.<\/p>\n

Information Theory can become (or rather, has become<\/a>) a source of understanding how and why different ML methods work, especially neural networks, and can also provide ideas for improving gradient-based optimization methods<\/a>.<\/p>\n

Let’s start with basic concepts like Entropy, Information in a message, Mutual Information, and channel capacity. Next, there will be materials on the similarity between tasks of maximizing Mutual Information and minimizing Loss in regression problems. Then there will be a section on Information Geometry: Fisher metric<\/a>, geodesics, gradient methods, and their connection to Gaussian processes (moving along the gradient using SGD is moving along the geodesic with noise).<\/p>\n

It’s also necessary to touch upon AIC<\/a>, Information Bottleneck<\/a>, and discuss how information flows in neural networks \u2013 Mutual Information between layers (Information Theory of Deep Learning, Naftali Tishby<\/a>), and much more. It’s not certain that I’ll be able to cover everything listed, but I’ll try to get started.<\/p>\n

1. Basic Definitions<\/strong> <\/p>\n

\"H({p_1, 0.\\;\\;\\;\\;\\;\\;» alt=»\\sum_{i=1}^M p_i =1, \\;\\; p_i > 0.\\;\\;\\;\\;\\;\\;» src=»https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3b0\/b7c\/de0\/3b0b7cde0e031276d3f6ceef94156d05.svg» width=»191″ height=»60″\/><\/p>\n

Let’s describe them. We’ll start with basic definitions <\/p>\n

Definition 1.1: Uncertainty<\/strong> is the logarithm<\/a> base 2 of the number of equiprobable possibilities: \"H. It is measured in bits<\/strong>. For example, the uncertainty of an unknown binary word<\/strong> of length k<\/em> is equal to k. <\/p>\n

\nLogarithm<\/summary>\n
\n

The logarithm<\/a> base 2 of a number is how many times you need to divide the number by 2 to get a number less than or equal to 1. For example,<\/p>\n

\"\\log_2(1)<\/p>\n

For non-powers of two, this function smoothly extends. For example,<\/p>\n

\"\\log_2(3)<\/p>\n

An important property of logarithms:<\/p>\n

\"\\log(x)<\/p>\n

Try to derive it from the non-strict definition above for the case when \"x\" and \"y\" are powers of two.<\/p>\n<\/div>\n<\/details>\n

\nBinary words<\/summary>\n
\n

Binary words of length k are sequences of zeros and ones of length k. Each character in a binary words is called a bit. For example, here are binary words of length 5:<\/p>\n

00000, 00001, 00010, 00011, 00100, 00101, … , 11100, 11101, 111110, 11111 <\/p>\n

There are 32 of them. \"\\log_2(32) , which means the uncertainty of a 5-bit word is 5.<\/p>\n

That’s exactly the number of unknown bits in an unknown 5-bit binary word.<\/p>\n

Thus, each symbol in a binary word is called a «bit,» but a «bit» is also a unit of uncertainty measurement. And this example helps to understand why.<\/p>\n<\/div>\n<\/details>\n

For brevity, \"\\log_2\" is simply denoted as \"\\log\" throughout.<\/p>\n

Definition 1.2: Information in a message<\/strong> is the difference in uncertainty before receiving the message and after.<\/p>\n

\"I(message)<\/p>\n

This is also measured in bits.<\/p>\n

For example, Vanya has chosen a number from 1 to 100. We are told that it is less than or equal to 50. The uncertainty before the message is \"\\log\u2061100\", and after the message, it is \"\\log. Therefore, there is 1 bit of information in this message. By skillfully asking binary questions (questions to which the answer is either YES or NO), you can extract exactly 1 bit of information.<\/p>\n

Some questions are inefficient. For instance, the question «Is the number less than or equal to 25?» reduces uncertainty by \"\\log\u2061100\u2212\\log\u206125=\\log\u2061(100\/25)=2\" bits with a probability of 0.25, and with a probability of 0.75, it only reduces it by \"\\log\u2061(100)\u2212\\log\u2061(75)=\\log\u2061(100\/75)\" bits, which on average is \"0.25\\log\u2061(1\/0.25)+0.75\\log\u2061(1\/0.75)=0.811278\" bits. If you divide the set of possibilities in a ratio of \"x<\/em>, with your question, then the average amount of information in the answer is \"x\\log\u2061(1\/x)+(1\u2212x)\\log\u2061(1\/(1\u2212x))\".<\/p>\n

We will denote this expression as \"H({x, or \"H(x)\". Here, as programmers, we overload the function H<\/strong> to work in two cases — when a pair of numbers is input, the sum of which is 1, and when one number is from the interval [0, 1].<\/p>\n

Definition 1.3:<\/strong>\u00a0\"H(\\{x,<\/em> <\/p>\n

\nPlot H(x)<\/summary>\n
\n
<\/figure>\n<\/p>\n<\/div>\n<\/details>\n

It’s evident that by asking binary questions, you can extract a maximum of 1 bit of information on average (the maximum value of the function \"H(x))\". Let’s reiterate: yes, you can directly ask questions like «Is the number equal to 57?» and if you’re lucky, you can get log(100) bits of information. However, if luck is not on your side, you will only get log(100\/99) bits of information. The average number of bits of information<\/strong> for such types of questions is\"(1\/100) which is noticeably less than 1.<\/p>\n

In this example, there are 100 possibilities, which means the initial uncertainty is\"\\log\u2061(100)\"\u2013 this is how many binary questions you, on average, need to ask Vanya to find out the answer. However, the number is not an integer, so you need to round it up.<\/p>\n

If we ask not binary questions but questions that imply a natural number from 1 to M as the answer, we can get more than one bit of information in a single response. If we ask a question for which all M answers are equally likely, then on average, we will get \"\\log bits. However, if the probability of answer i<\/em> is p<\/em>(i<\/em>), then the average number of bits in the response will be:<\/p>\n

\"H(\\{p_1,<\/p>\n

Definition 1.4: The entropy of a discrete distribution<\/strong> \u00a0\"P=\\{p_i\\}_{i=1}^M\"<\/em> is defined by the formula (1) above.<\/p>\n

Here, we have overloaded the function H for the case when a discrete distribution is provided as input.<\/p>\n

SO: The first straightforward way to arrive at the formula for entropy <\/strong>\"H(P)\" is to calculate the average number of bits of information in response to a question with equiprobable answers.<\/strong><\/p>\n

Let’s go further. Suppose Vanya doesn’t choose a number but samples it from the distribution \"P=\\{p_i\\}_{i=1}^M\"<\/em> . How many binary questions do we need to ask Vanya to determine the sampled number? Intuitively, we need to divide the set of possibilities into two subsets, not necessarily of equal size but with approximately equal total probability, and ask Vanya which of the two subsets contains the sampled number. Get the answer and continue in the same manner with the reduced set of possibilities — again dividing it into two subsets with roughly equal probability, asking Vanya which of the two subsets contains the sampled number, and so on. The idea is good but not quite practical. It turns out it’s more effective to work backward and start building the partition tree from the bottom. Specifically, find the two least probable outcomes and merge them into a single new outcome, thus reducing the number of possibilities by 1. Then, once again, find the two least probable outcomes and merge them into a new one, and so on, ultimately constructing a binary tree. The numbers are located in the leaves of this tree. The internal nodes are labeled with sets of numbers from the subtree they represent, and the root is labeled with the set of all numbers. This tree provides an algorithm for how to ask Vanya questions. You should start at the root of the tree and ask Vanya which way to go — left or right (which of the two children subsets contains the sampled number) according to this tree structure. This tree not only provides the recipe for the fastest average method of guessing the number but also serves as the Huffman algorithm for data compression<\/a>.<\/p>\n

Task 1.1:<\/strong> Study the Huffman code. Prove that a text with an original length of \"N\" characters, in its compressed form, has a length bounded from below by \"N bits, and under favorable circumstances, it achieves this bound.<\/p>\n

So, the formula <\/strong>\"H(P)\" arises when solving the problem of finding the minimum average number of binary questions needed to determine the outcome of a random variable with distribution <\/strong>\"P\".<\/strong><\/p>\n

This is the second way to arrive at formula (1).<\/p>\n

For a random variable \"\u03be\", we will use the following notations for the entropy of its distribution \"P=\\{{p_i}\\}_{i=1}^M\" (once again, «overloading» the function \"H\"):<\/p>\n

\"H(\\xi)\" or \"H(P)\" or \"H({\\{p_i}\\}_{i=1}^M)\" or \"H(\\{p_i\\}_i)\"<\/p>\n

There’s yet another, a third, simple way to arrive at the formula for entropy, but it requires knowledge of the Stirling formula<\/a>.<\/p>\n

Task 1.2:<\/strong> You have an unknown binary word of length k (a sequence of ones and zeros, a total of \"k\" characters). You are told that it contains 35% ones. What is the value of \"I(message) for large \"k<\/p>\n

\nAnswer<\/summary>\n
\n

Approximately\"\\log<\/em>, where\u00a0\"p<\/em> <\/p>\n<\/div>\n<\/details>\n

Task 1.3:<\/strong> Vanya has an unknown word of length k in an alphabet of size M. He has provided the proportions of all the letters in the word as \"P.
What is the value of I(message) \/ k for large k? <\/p>\n

\nAnswer<\/summary>\n
\"\\approx<\/p>\n<\/div>\n<\/details>\n

So, Task 1.3 is indeed the third way to arrive at formula (1).<\/p>\n

Definition 1.5:<\/strong> Information in a message about a certain random variable is the difference in entropies: \"I(message)<\/p>\n

The values of a random discrete variable can be seen as letters, and each successive letter in a word is just another measurement of the random variable. So, the information in a message about a certain random variable is the number of bits of information about measurements of that random variable, normalized by the number of measurements.<\/p>\n

Problem 1.4<\/strong>: What is the entropy of the discrete distribution \"P? How much information is contained in the message \"\\xi, where \"\\xi\" has the distribution \"P\"?<\/p>\n

\nAnswer<\/summary>\n
\"H(P)\"I(``\\xi<\/p>\n

This result requires acceptance. How can this be? \u2013 We were given seemingly non-zero information, eliminated the most probable option from the possibilities. However, the uncertainty about the remaining possibilities remains the same, so the formula \"H(before) yields an answer of 0. <\/p>\n<\/div>\n<\/details>\n

Task 1.5:<\/strong> Provide an example of a finite distribution and a message that does not reduce but increases uncertainty.<\/p>\n

\n\u041e\u0442\u0432\u0435\u0442<\/summary>\n
\n

\"P<\/em>, and message = «this is not the first element». Then\u00a0\"P_{after}<\/em> <\/p>\n<\/div>\n<\/details>\n

The ancient wisdom «in much wisdom is much grief» in this context gets another interesting interpretation: the modern world, science, and human life are such that new «messages» about history and the structure of the world only increase uncertainty.<\/p>\n

Discrete distributions on a countable set of values that decay exponentially (geometric progressions) have the property of unchanged uncertainty when receiving information, meaning that among the first elements, there is no correct answer. Distributions with less than exponential decay (e.g., \"p_k={C) only increase uncertainty when discarding the first elements.<\/p>\n

Problem 1.6:<\/strong> Write the formula for the entropy of the Poisson distribution<\/p>\n

\"p_k=e^{-\\lambda}{\\lambda^k<\/em><\/p>\n

Find a simple approximation for large \"\\lambda\".<\/p>\n

\nAnswer<\/summary>\n
\"H(\\{p_k\\}_{k=0}^{\\infty})={1\\over<\/p>\n<\/div>\n<\/details>\n

Task 1.7:<\/strong> Given the distribution \"\\rho(x)\" of a real random variable. Let \"Q(\\rho,\\varepsilon)\" be the average number of binary questions needed to determine some outcome of the random variable with an accuracy of \"\\varepsilon\". Find an approximate expression for \"Q(\\rho,\\varepsilon)\" for small values of \"\\varepsilon\". <\/p>\n

\nAnswer<\/summary>\n
\"\\sum_i\"=<\/p>\n

(see definition of entropy of a continuous distribution below).<\/p>\n<\/div>\n<\/details>\n

Definition 1.6:<\/strong> The entropy of a continuous distribution is given by<\/p>\n

\"H(\\rho)<\/p>\n

Here, we have once again overloaded the symbol H for the case when the argument is a probability density function (PDF).<\/p>\n

Task 1.8:<\/strong> Given two distributions \"\\rho_1(x)\"<\/em>and\u00a0\"\\rho_2(x)\"<\/em> of two real random variables. What does the difference \"Q(\\rho_1,<\/em> approach as\u00a0\"\\varepsilon\\to0\"<\/em>?<\/p>\n

\nAnswer<\/summary>\n
\"H(\\rho_1)<\/p>\n<\/div>\n<\/details>\n

Task 1.9:<\/strong> What is the entropy of a normal distribution \"\\mathcal{N}(\\mu,<\/em>? <\/p>\n

\nAnswer<\/summary>\n
\"1\/2<\/p>\n<\/div>\n<\/details>\n

Task 1.10:<\/strong> Write down the formula for the entropy of an exponential distribution \"\\rho(x)=e^{-x\/a}\/a\"<\/em>. <\/p>\n

Problem 1.11:<\/strong> A random variable \"\\xi\"<\/em> is a mixture of two random variables, meaning its distribution \"\\rho(x)\"<\/em>is a weighted sum of distributions:<\/p>\n

\"\\rho(x)<\/p>\n

Let the set of values taken by \"\\xi_1\"<\/em>not overlap with the set of values taken by \"\\xi_2\"<\/em>, in other words, let the supports of these two random variables not intersect. Find an expression for the entropy\u00a0\"H(\\xi)\"<\/em>in terms of the entropies \"H(\\xi_1)\"<\/em>and \"H(\\xi_2)\"<\/em>.<\/p>\n

\nAnswer<\/summary>\n
\"H(\\rho)<\/p>\n

The last equality here is possible only because the supports of \"X_1\"\u200b and \"X_2\"\u200b from the two distributions do not overlap as stated in the problem. Next, we will transform this expression into<\/p>\n

\"-w_1\\int_{X_1}<\/p>\n

In this problem, the goal was to show that even in the simple case of non-overlapping supports, entropies do not simply add up with their respective weights, but there is an additional term \"-(w_1\\log. When the weights are equal to 1\/2, this additional term is equal to 1. <\/p>\n

The interpretation of the formula is as follows: when an outcome is measured, with a probability of \"w_1\", it lies in \"X_1\", and with a probability of \"w_2\", it lies in \"X_2\". Consequently, we incur an uncertainty of \"H_1\" values on the set \"X_1\", or an uncertainty of \"H_2\" on the set \"X_2\". However, to determine in which set the measurement lies, on average, we will need to ask \"-(w_1\\log questions.<\/p>\n

From this, it follows, in particular, that a mixture with coefficients of 1\/2 of two normal random variables with the same variance, but significantly different means, has an entropy, that is 1 greater than the entropy of a single normal distribution. The supports of normal random variables span the entire real line, which means they overlap, but in the case of significantly different means, this overlap can be neglected.<\/p>\n<\/div>\n<\/details>\n

Task 1.12<\/strong>: A random variable \"\\xi\"<\/em> is equally likely to be 0 or 1. Another random variable \"\\nu\"<\/em> depends on \"\\xi\"<\/em> : if \"\\xi=0\"<\/em> , then \"\\nu\"<\/em> is sampled from \"\\mathcal{N}(0,<\/em>, and if \"\\xi=1\"<\/em>, then \"\\nu\"<\/em> is sampled from \"\\mathcal{N}(\\mu,<\/em>. How many bits of information about the random variable \"\\nu\"<\/em> are contained in the message \"``\\xi=0"\"<\/em>(as a function of \"\\mu\"<\/em>)?<\/p>\n

\nAnswer<\/summary>\n
\n

There is a numerical answer to this: <\/p>\n

<\/figure>\n

It’s clear that the graph starts at 0 and approaches 1:<\/p>\n