{"id":356472,"date":"2024-05-20T23:30:23","date_gmt":"2024-05-20T23:30:23","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=356472"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=356472","title":{"rendered":"<span>2. Information Theory + ML. Mutual Information<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>In <a href=\"https:\/\/habr.com\/en\/articles\/763090\/\" rel=\"noopener noreferrer nofollow\">Part 1<\/a>, we became familiar with the concept of entropy.<\/p>\n<p>In this part, I&#8217;m going to talk about Mutual Information &#8212; a concept that opens the doors to error-resistant coding, compression algorithms, and also provides a fresh perspective on regression and Machine Learning tasks.<\/p>\n<p>This is a necessary component to transition to ML tasks as we move into the next part, treating them as challenges in extracting mutual information between features and the predicted variable. One way to explain the success of ML models is that they create a natural bottleneck, limited by a self-adjusting value of information bits, through which information about the input data is passed (distilled). But that&#8217;s a topic for the next part.<\/p>\n<p>Here, there will be three important visuals:<\/p>\n<ul>\n<li>\n<p>The first one is about visualizing the entropies of two random variables and their mutual information.<\/p>\n<\/li>\n<li>\n<p>The second one is about understanding the concept of the dependency between two random variables and the fact that zero correlation doesn&#8217;t necessarily mean independence.<\/p>\n<\/li>\n<li>\n<p>And the third one is about how the capacity of an information channel has a straightforward geometric interpretation through the convexity measure of the entropy function.<\/p>\n<\/li>\n<\/ul>\n<p>We will also prove a simplified version of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Shannon%E2%80%93Hartley_theorem\" rel=\"noopener noreferrer nofollow\">Shannon-Hartley&#8217;s theorem<\/a> regarding the maximum bandwidth of a noisy channel.<\/p>\n<p>The material is quite complex, presented concisely, and is more like lecture notes. It is assumed that you will independently explore unclear points or ask me questions to clarify them in a more understandable and detailed manner.<\/p>\n<h2>2. Mutual Information  <\/h2>\n<p>When you have two dependent variables, you can talk about how much information about one is contained in the other. <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Task%201.14%3A,8%2C%2010%20provide%3F\" rel=\"noopener noreferrer nofollow\">The last tasks in Part 1<\/a> essentially revolved around this concept &#8212; Mutual Information between two random variables.<\/p>\n<p>For example, let&#8217;s consider a pair <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h)\" alt=\"(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/82a\/6a3\/173\/82a6a3173f4f9c80937b84a572331819.svg\" width=\"49\" height=\"22\"\/> = (person&#8217;s_weight, person&#8217;s_height). For simplicity, let&#8217;s assume these are integers measured in kilograms and centimeters, with a finite number of possible values. In theory, we could gather data from 7 billion people and build a two-dimensional distribution for the pair <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h)\" alt=\"(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/aad\/00d\/869\/aad00d8692e3a052516ede03c9f8834e.svg\" width=\"49\" height=\"22\"\/> &#8212; <strong>the distribution<\/strong> of two dependent random variables. We can separately construct the distribution only for weight <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"Pr(w = x)\" alt=\"Pr(w = x)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/593\/b26\/214\/593b26214c21d93de7ea87475ca4fa88.svg\" width=\"89\" height=\"22\"\/> (ignoring height) and the distribution for height <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"Pr(h = y)\" alt=\"Pr(h = y)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/05a\/79f\/73f\/05a79f73feee7a8516b218b8831473be.svg\" width=\"85\" height=\"22\"\/> (ignoring weight). These two distributions are called <strong>marginal distributions<\/strong> for the joint distribution on the plane <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(x, y)\" alt=\"(x, y)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e0a\/4e7\/d62\/e0a4e7d62d39f44b9bc56836f715f3f7.svg\" width=\"44\" height=\"22\"\/><\/p>\n<p>In this context, these marginal distributions are naturally referred to as <strong>prior distributions<\/strong> &#8212; they correspond to our knowledge of weight and height when we know nothing else about the person.<\/p>\n<p>It&#8217;s clear that information about a person&#8217;s height will cause us to reconsider the distribution of weight. For example, the message &#171;height = 2 meters 10 centimeters&#187; will shift the weight distribution towards higher values. The new weight distribution after receiving this message is naturally called <strong>posterior<\/strong>. Accordingly, you can express the information gained in this message as the difference between the entropies of the prior and posterior distributions:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"I_w(&quot;h = 2.10&quot;) =\\\\ = H({Pr(w = x)}_x) - H({Pr(w = x | h = 2.10)}_x) \" alt=\"I_w(&quot;h = 2.10&quot;) =\\\\ = H({Pr(w = x)}_x) - H({Pr(w = x | h = 2.10)}_x) \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e67\/d57\/613\/e67d57613f802dc5468659df6badd9d9.svg\" width=\"697\" height=\"51\"\/><\/p>\n<p>Here, <strong>outside the curly braces, I indicate the index<\/strong> to iterate within the curly braces <strong>to obtain a list<\/strong>, and if there are two indices, it&#8217;s a <strong>matrix<\/strong>.<\/p>\n<p>It&#8217;s important to note that there&#8217;s no guarantee that this value will be positive. It&#8217;s possible to have a joint distribution <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h)\" alt=\"(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f91\/729\/ed6\/f91729ed679b833857a655bc899e75c0.svg\" width=\"49\" height=\"22\"\/>where the conditional distribution <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"{Pr(w = x | h = 2.10)}_x\" alt=\"{Pr(w = x | h = 2.10)}_x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e9b\/867\/69d\/e9b86769d07264ad5653ec8d1ed15b24.svg\" width=\"175\" height=\"23\"\/>has higher entropy (uncertainty) than the marginal distribution <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"{Pr(w = x)}_x\" alt=\"{Pr(w = x)}_x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2d1\/17e\/5b4\/2d117e5b449b5df6d3b13afd18445166.svg\" width=\"98\" height=\"23\"\/>. However, <strong>on average<\/strong>, for dependent random variables, the value of <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"I_w(&quot;h = x&quot;)\" alt=\"I_w(&quot;h = x&quot;)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/66b\/65e\/37a\/66b65e37a9c8d17e24ec8419c67b5a89.svg\" width=\"113\" height=\"22\"\/> is positive, namely, the expected value of this quantity is positive:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"M_{I_w(&quot;h = \\cdot&quot;)} = \u2211_x Pr(h = x) * I_w(&quot;h = x&quot;) \u2265 0\" alt=\"M_{I_w(&quot;h = \\cdot&quot;)} = \u2211_x Pr(h = x) * I_w(&quot;h = x&quot;) \u2265 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/798\/b9a\/266\/798b9a26690b721a27b0fc5dafd9bcc0.svg\" width=\"401\" height=\"31\"\/><\/p>\n<p>This quantity is naturally referred to as information about <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w\" alt=\"w\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3a0\/49b\/b78\/3a049bb7813f3f06ea822ccc7d16c56e.svg\" width=\"14\" height=\"12\"\/> in <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"h\" alt=\"h\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e5a\/a19\/e3f\/e5aa19e3f624f0a60622b9ae473ce403.svg\" width=\"11\" height=\"17\"\/>. <strong>Interestingly, it turns out to be symmetric with respect to the permutation of the pair<\/strong> <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h)\" alt=\"(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2c5\/aba\/893\/2c5aba89395b911b6eeca2014e3ec8ac.svg\" width=\"49\" height=\"22\"\/>.<\/p>\n<p><strong>Definition 2.1: Mutual information of two random variables is<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(w, h) = \\sum_x \\mathrm{Pr}(h=x) \\cdot I_{w}(``h=x&quot;)\" alt=\"\\mathrm{MI}(w, h) = \\sum_x \\mathrm{Pr}(h=x) \\cdot I_{w}(``h=x&quot;)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d59\/5a6\/b83\/d595a6b83a431278cb6eb7646b36df61.svg\" width=\"340\" height=\"44\"\/><\/p>\n<p>or<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(w, h) = \\sum_x \\mathrm{Pr}(w=y) \\cdot I_{h}(``w=y&quot;)\" alt=\"\\mathrm{MI}(w, h) = \\sum_x \\mathrm{Pr}(w=y) \\cdot I_{h}(``w=y&quot;)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/332\/639\/3d2\/3326393d2d695bbba46873ac392b5585.svg\" width=\"341\" height=\"44\"\/><\/p>\n<p>or<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(w, h) = H(w) + H(h) - H(\\{w,h\\})\" alt=\"\\mathrm{MI}(w, h) = H(w) + H(h) - H(\\{w,h\\})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1ba\/172\/a0a\/1ba172a0ad4dfceba66a6652141525f3.svg\" width=\"324\" height=\"22\"\/><\/p>\n<p>These are three equivalent definitions. <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(\\{w,h\\})\" alt=\"H(\\{w,h\\})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f51\/6c2\/9d3\/f516c29d3d7b916287ac1409d53e4cfe.svg\" width=\"86\" height=\"22\"\/><\/em>is the entropy of a discrete distribution where the values are not individual numbers but pairs of numbers <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{y,x\\}\" alt=\"\\{y,x\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/53d\/c23\/2ad\/53dc232ade008eb9e640c31a60c58a3c.svg\" width=\"49\" height=\"22\"\/><\/em>. We will prove the equivalence below.<\/p>\n<p>There is a visualization of the MI value:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/94d\/65a\/479\/94d65a47957b6ee7513b6c0b533f391f.png\" width=\"914\" height=\"682\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/94d\/65a\/479\/94d65a47957b6ee7513b6c0b533f391f.png\"\/><\/figure>\n<p>The entropies of random variables correspond to circles \u2013 green and reddish, with areas equal to <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(w)\" alt=\"H(w)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/506\/c0b\/6d6\/506c0b6d69f9c2682d25d557bedbc118.svg\" width=\"47\" height=\"22\"\/><\/em>and<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(h)\" alt=\"H(h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/277\/631\/fb2\/277631fb20f3bd3b1bb31af1920127d6.svg\" width=\"44\" height=\"22\"\/><\/em>respectively, while the brown area of their intersection is precisely <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w,h).\" alt=\"\\mathrm{MI}(w,h).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/09d\/712\/c52\/09d712c52973f4edfe1ed2ba1212871b.svg\" width=\"79\" height=\"22\"\/><\/em>  <\/p>\n<details class=\"spoiler\">\n<summary>Entropy as a measure<\/summary>\n<div class=\"spoiler__content\">\n<p>This visualization, on one hand, is merely an illustration emphasizing that entropy is a non-negative quantity and that <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w,h)\" alt=\"\\mathrm{MI}(w,h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/893\/5dc\/305\/8935dc305cf135ad5924e1ceed249861.svg\" width=\"74\" height=\"22\"\/><\/em>is also a non-negative quantity, which is less than or equal to both <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(w)\" alt=\"H(w)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/506\/c0b\/6d6\/506c0b6d69f9c2682d25d557bedbc118.svg\" width=\"47\" height=\"22\"\/><\/em>and<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(h)\" alt=\"H(h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/277\/631\/fb2\/277631fb20f3bd3b1bb31af1920127d6.svg\" width=\"44\" height=\"22\"\/><\/em>. However, on the other hand, there are interesting results that allow us to construct a measure space in which a random variable corresponds to a subset, the union of subsets corresponds to the direct product of random variables (i.e., the union forms a pair), and the measure of subsets is precisely the entropy of the corresponding random variables.  <\/p>\n<\/div>\n<\/details>\n<details class=\"spoiler\">\n<summary>By the way, in the context of machine learning, the image with green and red circles looks like this.<\/summary>\n<div class=\"spoiler__content\">\n<p>We are given some features, and need to predict the signal (target). For example, we need to forecast the air temperature tomorrow at 12:00 PM in the center of London with an accuracy of 0.5\u00b0C. Features can include data on the temperature in London and its surroundings for the past 10 years, the current date, current values of temperature, pressure, humidity, wind, as well as the position of the Moon and other data. It&#8217;s a typical situation where the amount of information in the features is vast, but the target variable is low in entropy. The entire set of data in the features can be called a random variable &#171;w,&#187; and the target variable is &#171;h.&#187; These random variables have mutual information, and the essence of the prediction task is precisely to find this information within the features.  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/7e5\/d47\/d96\/7e5d47d96786fe711ca6995722966b57.png\" width=\"1078\" height=\"1078\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7e5\/d47\/d96\/7e5d47d96786fe711ca6995722966b57.png\"\/><\/figure>\n<\/p>\n<\/div>\n<\/details>\n<p>Lets describe the first expression in more detail:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(w, h) = \\sum_x \\mathrm{Pr}(h=x) \\cdot I_{w}(``h=x&quot;)\\\\= \\sum_x \\mathrm{Pr}(h=x) \\cdot ( H(\\{\\mathrm{Pr}(w=y)\\}_y) - H(\\{\\mathrm{Pr}(w=y|h=x)\\}_y)) \\\\ =   H(\\{\\mathrm{Pr}(w=y)\\}_y) - \\sum_x \\mathrm{Pr}(h=x) \\cdot H(\\{\\mathrm{Pr}(w=y|h=x)\\}_y)\\\\ = H(w) -  H( w | h)\" alt=\"\\mathrm{MI}(w, h) = \\sum_x \\mathrm{Pr}(h=x) \\cdot I_{w}(``h=x&quot;)\\\\= \\sum_x \\mathrm{Pr}(h=x) \\cdot ( H(\\{\\mathrm{Pr}(w=y)\\}_y) - H(\\{\\mathrm{Pr}(w=y|h=x)\\}_y)) \\\\ =   H(\\{\\mathrm{Pr}(w=y)\\}_y) - \\sum_x \\mathrm{Pr}(h=x) \\cdot H(\\{\\mathrm{Pr}(w=y|h=x)\\}_y)\\\\ = H(w) -  H( w | h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5b5\/2b3\/782\/5b52b3782e94700404cb5850ef133d2c.svg\" width=\"697\" height=\"171\"\/><\/p>\n<p>The notation<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(w | h)\" alt=\"H(w | h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bd1\/fbb\/571\/bd1fbb5712dae2f3243ec2bc3445aeae.svg\" width=\"63\" height=\"22\"\/><\/em> is simply a shorthand for<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sum_x P(h=x) \\cdot H(\\{\\mathrm{Pr}(w=y|h=x)\\}_y)\" alt=\"\\sum_x P(h=x) \\cdot H(\\{\\mathrm{Pr}(w=y|h=x)\\}_y)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5f2\/ee0\/5da\/5f2ee05da947f6a65f393c964b601497.svg\" width=\"324\" height=\"44\"\/><\/em>  <\/p>\n<p>and is called <a href=\"https:\/\/en.wikipedia.org\/wiki\/Conditional_entropy\" rel=\"noopener noreferrer nofollow\">conditional entropy<\/a>.<\/p>\n<p>For independent random variables,<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"I(``h=x&quot;) =\\\\= H({\\mathrm{Pr}(w=y)}) - H({\\mathrm{Pr}(w=y|h=x)})=0\" alt=\"I(``h=x&quot;) =\\\\= H({\\mathrm{Pr}(w=y)}) - H({\\mathrm{Pr}(w=y|h=x)})=0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/35c\/8d5\/bd1\/35c8d5bd1c9dbcfdadbccb47ae772309.svg\" width=\"697\" height=\"50\"\/><\/p>\n<p>because, by the definition of independence, <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{Pr}(w=y) = \\mathrm{Pr}(w=y | h=x)\" alt=\"\\mathrm{Pr}(w=y) = \\mathrm{Pr}(w=y | h=x)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5f9\/0f4\/8b5\/5f90f48b571a317a7cfede7463cd02c5.svg\" width=\"252\" height=\"22\"\/><\/em>   for any <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x.\" alt=\"x.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/85c\/67b\/cc2\/85c67bcc291ee659fa0d1b528dbea8f9.svg\" width=\"16\" height=\"12\"\/><\/em>   Therefore, <strong>for independent random variables, the mutual information is equal to 0<\/strong>.<\/p>\n<p>It turns out that the reverse is also true, meaning the statement <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w, h) = 0\" alt=\"\\mathrm{MI}(w, h) = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ca9\/20f\/37f\/ca920f37f8638f84f5413e2152079cda.svg\" width=\"110\" height=\"22\"\/><\/em> is equivalent to the independence of random variables. However, a similar statement would not hold true for the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Correlation\" rel=\"noopener noreferrer nofollow\">correlation<\/a> of two random variables.<\/p>\n<p>To see the equivalence of the MI definitions, it&#8217;s convenient to introduce the following notations:  <\/p>\n<ul>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P = \\{ p_{x,y} \\}_{x,y}\" alt=\"P = \\{ p_{x,y} \\}_{x,y}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/574\/a17\/0f1\/574a170f1778d40a6964ca9b042d3d6a.svg\" width=\"111\" height=\"23\"\/><\/em>  \u2014 probabilities that height and weight are equal to <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(x, y)\" alt=\"(x, y)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/21a\/a09\/337\/21aa093373ddd90cfbdc20d4caef3fec.svg\" width=\"44\" height=\"22\"\/>.<\/p>\n<\/li>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R = \\{ r_{x} \\}_x = \\{\\sum_y p_{x,y}\\}_x\" alt=\"R = \\{ r_{x} \\}_x = \\{\\sum_y p_{x,y}\\}_x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/33d\/a76\/839\/33da76839f154bf5219f60ae0e27ae74.svg\" width=\"206\" height=\"47\"\/><\/em> \u2014 probabilities that height equals <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x\" alt=\"x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/36a\/945\/8a2\/36a9458a2b0ef8bbbaebe665bbeff3db.svg\" width=\"11\" height=\"12\"\/> (marginal distribution of height).<\/p>\n<\/li>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"Q = \\{ q_{y} \\}_y = \\{\\sum_x p_{x,y}\\}_y\" alt=\"Q = \\{ q_{y} \\}_y = \\{\\sum_x p_{x,y}\\}_y\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0bf\/265\/2fa\/0bf2652fa7dce96d7ec8039d40a19eaa.svg\" width=\"203\" height=\"44\"\/><\/em> \u2014 probabilities that weight equals <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"y\" alt=\"y\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/59a\/0db\/eda\/59a0dbeda6907459115b0313f47ef3de.svg\" width=\"10\" height=\"15\"\/> (marginal distribution of weight).<\/p>\n<\/li>\n<\/ul>\n<p>Let&#8217;s assume that all these numbers are non-zero.  <\/p>\n<p>Firstly, notice that <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{Pr}(w=y | h=x) = p_{x, y} \/ r_x.\" alt=\"\\mathrm{Pr}(w=y | h=x) = p_{x, y} \/ r_x.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c3c\/205\/05b\/c3c20505b480dd89f1ad8a2739d21480.svg\" width=\"230\" height=\"23\"\/><\/em>  <\/p>\n<p>Then, by making substitutions and simple transformations, we obtain the equivalence between the first and third definitions:  <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(w, h) =\\\\=\\sum_x \\mathrm{Pr}(h=x)  \\cdot (H(\\{q_y\\}_y)  - H(\\{\\mathrm{Pr}(w=y | h=x)\\}_y ) = \\\\ \\ \\ = \\sum_x r_x \\cdot (H(Q)  - \\sum_y p_{x,y}\/r_x \\cdot \\log (r_x\/p_{x,y})) = \\\\ \\ \\ = H(Q) -  \\sum_{x,y} r_x \\cdot  (p_{x,y} \/ r_x) \\cdot\\log( r_x \/ p_{x,y}) = \\\\ \\ \\ = H(Q) -  \\sum_{x,y} p_{x,y} \\log (r_x \/ p_{x,y}) = \\\\ \\ \\ = H(Q) +  \\sum_{x,y} p_{x,y} \\log (1 \/ r_x) - \\sum_{x,y} p_{x,y} \\log (1 \/p_{x,y}) = \\\\ \\ \\ = H(Q) + \\sum_{x} r_x \\log (1 \/ r_x) - \\sum_{x,y} p_{x,y} \\log (1\/p_{x,y}) = \\\\ \\ \\ = H(Q) + H(R) - H(P)\" alt=\"\\mathrm{MI}(w, h) =\\\\=\\sum_x \\mathrm{Pr}(h=x)  \\cdot (H(\\{q_y\\}_y)  - H(\\{\\mathrm{Pr}(w=y | h=x)\\}_y ) = \\\\ \\ \\ = \\sum_x r_x \\cdot (H(Q)  - \\sum_y p_{x,y}\/r_x \\cdot \\log (r_x\/p_{x,y})) = \\\\ \\ \\ = H(Q) -  \\sum_{x,y} r_x \\cdot  (p_{x,y} \/ r_x) \\cdot\\log( r_x \/ p_{x,y}) = \\\\ \\ \\ = H(Q) -  \\sum_{x,y} p_{x,y} \\log (r_x \/ p_{x,y}) = \\\\ \\ \\ = H(Q) +  \\sum_{x,y} p_{x,y} \\log (1 \/ r_x) - \\sum_{x,y} p_{x,y} \\log (1 \/p_{x,y}) = \\\\ \\ \\ = H(Q) + \\sum_{x} r_x \\log (1 \/ r_x) - \\sum_{x,y} p_{x,y} \\log (1\/p_{x,y}) = \\\\ \\ \\ = H(Q) + H(R) - H(P)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bd7\/2d9\/3c9\/bd72d93c92b60a980e346a7f23d0ac18.svg\" width=\"697\" height=\"361\"\/><\/p>\n<p>The consideration of cases where some of the probabilities are equal to zero lets leave for textbooks.<\/p>\n<p><strong>Task 2.1:<\/strong> Provide an example of random variables for which the correlation is zero, but MI is not zero.<\/p>\n<p><strong>Task 2.2:<\/strong> Two random variables were measured multiple times, and points were plotted on a plane. Which pictures correspond to dependent random variables, and which ones correspond to independent random variables? For which of them is the correlation between x and y equal to 0?<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/54c\/9b3\/d54\/54c9b3d54292d82ce916cde7842ec458.png\" alt=\"Measurement results of two random variables. On which ones of the 12 pictures are these two variables dependent?  \" title=\"Measurement results of two random variables. On which ones of the 12 pictures are these two variables dependent?  \" width=\"1200\" height=\"892\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/54c\/9b3\/d54\/54c9b3d54292d82ce916cde7842ec458.png\"\/><\/p>\n<div><figcaption>Measurement results of two random variables. <br \/>On which ones of the 12 pictures are these two variables dependent?  <\/figcaption><\/div>\n<\/figure>\n<details class=\"spoiler\">\n<summary>Answers<\/summary>\n<div class=\"spoiler__content\">\n<p>Dependent: 3rd, 4th, 5th, 8th, 11th, 12th.<\/p>\n<p>Correlation is zero for all except the 4th, 5th, 8th, and 12th.<\/p>\n<\/div>\n<\/details>\n<p><strong>Task 2.3:<\/strong> Calculate MI(w=&#187;number is divisible by a=6&#8243;, h=&#187;number is divisible by b=15&#8243;). It is assumed that we randomly select one of the natural numbers, and all numbers are equally likely. To avoid dealing with the concept of a uniform distribution over natural numbers, consider that we are randomly selecting a number from the set {1, &#8230;, 30}. Prove that if you take coprime numbers a and b, then MI=0.  <\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>We know the marginal distributions: R = {5\/6, 1\/6} and Q = {14\/15, 1\/15}. Furthermore, we know that the probability of being divisible by both 6 and 15 is 1\/30. From this, we can derive the joint probability matrix:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"P = \\|p_{xy}\\| =\\\\=\\left\\|\\begin{array}{cc}  5\/6 - (1\/15 - 1\/30)   &amp; 1\/6 - 1\/30 \\\\ 1\/15 - 1\/30 &amp; 1\/30\\end{array}\\right\\|=\\\\=\\left\\|\\begin{array}{cc}  4\/5  &amp; 2\/15\\\\ 1\/30  &amp; 1\/30\\end{array}\\right\\|\" alt=\"P = \\|p_{xy}\\| =\\\\=\\left\\|\\begin{array}{cc}  5\/6 - (1\/15 - 1\/30)   &amp; 1\/6 - 1\/30 \\\\ 1\/15 - 1\/30 &amp; 1\/30\\end{array}\\right\\|=\\\\=\\left\\|\\begin{array}{cc}  4\/5  &amp; 2\/15\\\\ 1\/30  &amp; 1\/30\\end{array}\\right\\|\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/990\/fd9\/cdb\/990fd9cdb5a5ad859b312e7df97d62ee.svg\" width=\"615\" height=\"138\"\/><\/p>\n<p>  We use the formula <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI} = H(w) + H(h) - H({w,h})\" alt=\"\\mathrm{MI} = H(w) + H(h) - H({w,h})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3b3\/7c8\/654\/3b37c8654fc501ac9957aa6445bb5ba1.svg\" width=\"255\" height=\"22\"\/><\/em> and get MI = 0.0311278.  <\/p>\n<\/div>\n<\/details>\n<p>Task 2.4: Prove that there is another equivalent definition<\/p>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w, h) = D_{KL}( \\{\\mathrm{Pr}(w = x, h = y)\\}_{x,y}, \\;\\{\\mathrm{Pr}(w=x) \\cdot \\mathrm{Pr}(h=y) \\}_{x,y}),\" alt=\"\\mathrm{MI}(w, h) = D_{KL}( \\{\\mathrm{Pr}(w = x, h = y)\\}_{x,y}, \\;\\{\\mathrm{Pr}(w=x) \\cdot \\mathrm{Pr}(h=y) \\}_{x,y}),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/072\/ae5\/f30\/072ae5f30714ddfebfc442c1d67153b9.svg\" width=\"582\" height=\"23\"\/><\/em>  <\/p>\n<p>which means that <strong>MI measures how much less efficient the Huffman code for the stream of pairs <\/strong><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{w,h\\}\" alt=\"\\{w,h\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/083\/5be\/778\/0835be778b4d1c7c6fb0fc9aa33211ae.svg\" width=\"53\" height=\"22\"\/><strong>, constructed under the assumption of independence of random variables<\/strong> (i.e., assuming that the joint distribution is equal to the product of marginals), <strong>is compared to the Huffman code constructed based on the actual joint distribution.<\/strong> <strong>It is measured in saved bits per symbol (symbol being an observation of the pair <\/strong><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{w,h\\}\" alt=\"\\{w,h\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/800\/d5d\/986\/800d5d9864a669567db7b6938821a931.svg\" width=\"53\" height=\"22\"\/><strong>).<\/strong><\/p>\n<p>We have been operating in the realm of discrete distributions so far. Transitioning to continuous variables is straightforward.<\/p>\n<p>Let&#8217;s recall <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Task%201.7%3A,Answer\" rel=\"noopener noreferrer nofollow\">task 1.7<\/a>. Suppose we have real random variables <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h)\" alt=\"(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7b5\/26b\/94b\/7b526b94b7d72df7299719a9c0392703.svg\" width=\"49\" height=\"22\"\/>, but we discretize them &#8212; the first one into bins of size <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon_1\" alt=\"\\varepsilon_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cb8\/586\/664\/cb85866641c3387fed99754af532610f.svg\" width=\"18\" height=\"14\"\/><\/em>, and the second one into bins of size <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon_2\" alt=\"\\varepsilon_2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/969\/748\/f5e\/969748f5e713c9da8d932c0d62a86efe.svg\" width=\"18\" height=\"14\"\/><\/em>\u200b. Substituting into the expression<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"H(\\{q_y\\}_y) + H(\\{r_x\\}_x) - H(\\{p_{x,y}\\}_{x,y})\" alt=\"H(\\{q_y\\}_y) + H(\\{r_x\\}_x) - H(\\{p_{x,y}\\}_{x,y})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/efa\/dff\/128\/efadff12810d6e559e6ee797888bf44d.svg\" width=\"310\" height=\"23\"\/><\/p>\n<p>an approximate formula instead of H (see <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Task%201.7%3A,Answer\" rel=\"noopener noreferrer nofollow\">task 1.7<\/a>)<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\log(1\/\\varepsilon) - \\int_{-\\infty}^{+\\infty} \\rho(x)\\log(\\rho(x))dx\" alt=\"\\log(1\/\\varepsilon) - \\int_{-\\infty}^{+\\infty} \\rho(x)\\log(\\rho(x))dx\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/72b\/c4a\/6d6\/72bc4a6d6b70fa707c6f22b071de3b12.svg\" width=\"281\" height=\"51\"\/><\/p>\n<p>for the entropy of discretized continuous distribution, we will get that the first term contributes <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(1\/\\varepsilon_1),\" alt=\"\\log(1\/\\varepsilon_1),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/10f\/1a7\/d73\/10f1a7d73c010773f81c52bf370388b0.svg\" width=\"83\" height=\"22\"\/><\/em> the second term contributes <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(1\/\\varepsilon_2),\" alt=\"\\log(1\/\\varepsilon_2),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1ab\/ffc\/db6\/1abffcdb69b7bc7d800ba0cbf7213dc0.svg\" width=\"83\" height=\"22\"\/><\/em>and the third term (the subtracted one) contributes <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(1\/(\\varepsilon_1\\cdot \\varepsilon_2)\" alt=\"\\log(1\/(\\varepsilon_1\\cdot \\varepsilon_2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/afb\/b45\/cfe\/afbb45cfe244fbc77ae23b60121dfb10.svg\" width=\"117\" height=\"22\"\/><\/em>and these three pieces will cancel each other out.<\/p>\n<p>Thus, mutual information for continuous variables can be naturally defined as the limit of MI for discretized random variables as the bin sizes approach zero.<\/p>\n<p><strong>Definition 2.2: The mutual information of two continuous random variables<\/strong> is given by<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(h,w) = H(\\rho_h) + H(\\rho_w) - H(\\rho_{(h,w)}).\" alt=\"\\mathrm{MI}(h,w) = H(\\rho_h) + H(\\rho_w) - H(\\rho_{(h,w)}).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1a6\/037\/8c0\/1a60378c00434e3e1b4821ff0b54e40a.svg\" width=\"337\" height=\"25\"\/><\/p>\n<p>Here, we use the H function from <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Definition%201.6%3A,density%20function%20(PDF).\" rel=\"noopener noreferrer nofollow\">the definition 1.6 in part 1<\/a>.<\/p>\n<p><strong>Task 2.5:<\/strong> Estimate <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(predict, target)\" alt=\"\\mathrm{MI}(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dde\/d59\/2e9\/dded592e9edcbf53102c51e9126d2b03.svg\" width=\"161\" height=\"22\"\/><\/em>for any forecasting task you have. Calculate <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(predict, target) \/ H(target)\" alt=\"\\mathrm{MI}(predict, target) \/ H(target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/742\/c30\/4b0\/742c304b02291be83cfb4db4973152a2.svg\" width=\"255\" height=\"22\"\/><\/em>, and how close is this ratio to 1?<\/p>\n<p>The estimation of MI between two random variables from a set of their measurements essentially boils down to calculating the joint distribution matrix<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\|p_{xy}\\|\" alt=\"\\|p_{xy}\\|\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1a5\/132\/3fd\/1a51323fdb3fda96ca1a559b72ec8951.svg\" width=\"46\" height=\"23\"\/><\/em>for discretized values of these random variables. The more bins in the discretization, the less inaccuracy associated with discretization, but the less statistics available for an accurate estimation of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"p_{xy}\" alt=\"p_{xy}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4af\/cfe\/67e\/4afcfe67e8f13165b463a13d31e7d3e9.svg\" width=\"27\" height=\"17\"\/><\/em>\u200b.<\/p>\n<p>The estimation of MI from observed measurements is a separate extensive topic, and we will return to it in problem 3.1.<\/p>\n<p><strong>Problem 2.6:<\/strong> Prove that for any strictly monotonic function<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f\" alt=\"f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7aa\/8cb\/a82\/7aa8cba82d4a0b5b1dbcd1933984d2c8.svg\" width=\"11\" height=\"21\"\/><\/em>, it holds true that <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w,h) = \\mathrm{MI}(f(w), h).\" alt=\"\\mathrm{MI}(w,h) = \\mathrm{MI}(f(w), h).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/730\/abd\/0bb\/730abd0bb93d7c3e4b0ac1473236089b.svg\" width=\"205\" height=\"22\"\/><\/em><\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>Let <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_f = f(w)\" alt=\"w_f = f(w)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/179\/647\/2a7\/1796472a7fc0a890e18b1e3320674e79.svg\" width=\"89\" height=\"23\"\/><\/em>. Consider two formulas:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(w, h) = H(h) - H(h | w) =\\\\= H(h) - \\int (\\rho(y) dy)  H(h | w = y)\" alt=\"\\mathrm{MI}(w, h) = H(h) - H(h | w) =\\\\= H(h) - \\int (\\rho(y) dy)  H(h | w = y)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/35b\/de0\/f27\/35bde0f27200581e8325bf01043857ef.svg\" width=\"615\" height=\"74\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(w_f, h) = H(h) - H(h | w_f) =\\\\= H(h) - \\int (\\rho_f(z) dz)  H(h | w_f = z)\" alt=\"\\mathrm{MI}(w_f, h) = H(h) - H(h | w_f) =\\\\= H(h) - \\int (\\rho_f(z) dz)  H(h | w_f = z)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2ba\/7d7\/fe3\/2ba7d7fe3486c46ac7dc39ddbc3e3100.svg\" width=\"615\" height=\"75\"\/><\/p>\n<p>The first terms in both formulas are identical, but subtracted terms are equal since their physical interpretation is the average value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(h')\" alt=\"H(h')\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c3b\/3d2\/c74\/c3b3d2c7477aa36996c7e4bd6c467d38.svg\" width=\"50\" height=\"23\"\/><\/em>, where<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"h'\" alt=\"h'\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b49\/25a\/6d5\/b4925a6d5308cc3358f2ece69e0e687d.svg\" width=\"17\" height=\"19\"\/><\/em>are different random variables gotten from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"h\" alt=\"h\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7fe\/068\/0e6\/7fe0680e6f0bc654860033171a7d5ab4.svg\" width=\"11\" height=\"17\"\/><\/em> when fixing the value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w\" alt=\"w\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6bd\/b7b\/bcd\/6bdb7bbcdf135b43d600e0b95f3325ab.svg\" width=\"14\" height=\"12\"\/><\/em> or, equivalently, when fixing the value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_f\" alt=\"w_f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ae2\/1c1\/03c\/ae21c103cb0db089bdeb39cc5fc4a80b.svg\" width=\"24\" height=\"17\"\/>.<\/em> The averaging is done over the distribution of values of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w\" alt=\"w\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6bd\/b7b\/bcd\/6bdb7bbcdf135b43d600e0b95f3325ab.svg\" width=\"14\" height=\"12\"\/><\/em>   or <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_f\" alt=\"w_f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ae2\/1c1\/03c\/ae21c103cb0db089bdeb39cc5fc4a80b.svg\" width=\"24\" height=\"17\"\/><\/em>, which is not important.<\/p>\n<p>Now, look at the integrals. The values <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(h | w = y)\" alt=\"H(h | w = y)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/201\/225\/92b\/20122592b7827849dd9964d867fc825e.svg\" width=\"99\" height=\"22\"\/><\/em>and<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(h | w_f = f(y))\" alt=\"H(h | w_f = f(y))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d9a\/cec\/af0\/d9acecaf0e96e63b1af13ac68d996fb6.svg\" width=\"134\" height=\"23\"\/><\/em>are just identical, and in both formulas, you are averaging this quantity over the same probability measure <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mu\" alt=\"\\mu\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7f4\/95e\/c07\/7f495ec07261fc96e6d68e040c397ae0.svg\" width=\"12\" height=\"16\"\/><\/em>, which is just parameterized differently: <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"d\\mu = \\rho(x) dx = \\rho_f(z) dz\" alt=\"d\\mu = \\rho(x) dx = \\rho_f(z) dz\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0f8\/871\/3ff\/0f88713fff4fea1ea713a0fa240a2f50.svg\" width=\"195\" height=\"23\"\/><\/em>.  <\/p>\n<\/div>\n<\/details>\n<p><strong>Definition 2.6: An information channel<\/strong> is a Markov chain of length 2, that defines the dependency between two related random variables, one of which is called the input, and the other is called the output. Often, when referring to an information channel, only the <strong>transition probability matrix<\/strong> is considered: <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T=\\|t_{y,x}\\|=\\|\\{\\mathrm{Pr}(output = y | \\; input = x)\\}_{y,x}\\|,\" alt=\"T=\\|t_{y,x}\\|=\\|\\{\\mathrm{Pr}(output = y | \\; input = x)\\}_{y,x}\\|,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/065\/4ce\/0f9\/0654ce0f9620315005d6f476372dd2ef.svg\" width=\"400\" height=\"23\"\/><\/em>  , without specifying the input distribution. We will denote the input distribution as a vector <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R= \\|\\{r_x\\}_x\\|=\\|\\{\\mathrm{Pr}(input=x)\\}_x\\|,\" alt=\"R= \\|\\{r_x\\}_x\\|=\\|\\{\\mathrm{Pr}(input=x)\\}_x\\|,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/878\/f19\/d12\/878f19d12ec5e658684ffc6b7bd1f4f2.svg\" width=\"309\" height=\"22\"\/><\/em>\u200b, and the distribution of output values as a vector <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"Q = \\|\\{q_y\\}_y\\|=\\|\\{\\mathrm{Pr}(output=y)\\}_y\\|.\" alt=\"Q = \\|\\{q_y\\}_y\\|=\\|\\{\\mathrm{Pr}(output=y)\\}_y\\|.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/444\/ed0\/e99\/444ed0e9903c138369743ee9ca75f210.svg\" width=\"314\" height=\"23\"\/><\/em><\/p>\n<p>For discrete distributions, for each of the M possible inputs, we have a distribution over N possible output values. In essence, we have a matrix with M columns and N rows, where all numbers are non-negative, and the sum of numbers in each column equals 1.<\/p>\n<p>Such matrices are called <strong>stochastic matrices, more precisely, left stochastic matrices (left stochastic matrix).<\/strong><\/p>\n<details class=\"spoiler\">\n<summary>About left and right stochastic matrices:<\/summary>\n<div class=\"spoiler__content\">\n<p>In left stochastic matrices, the sum of numbers in each column equals 1, while in right stochastic matrices, it&#8217;s the sum of numbers in each row that equals 1. There are also doubly stochastic matrices, where both columns and rows sum to 1. I have chosen the variant where the vector of input probabilities is considered as a column vector, and to obtain the vector of output probabilities, you perform the standard matrix multiplication: <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"Q  = T \\cdot R\" alt=\"Q  = T \\cdot R\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0f1\/6af\/ce4\/0f16afce485eb8e01b39dac9b5282724.svg\" width=\"84\" height=\"20\"\/><\/em>.<\/p>\n<p>In English-language literature, it&#8217;s common to consider the probability vector as a row vector, transpose the transition matrix (making it a right stochastic matrix), and perform matrix multiplication from the left: <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"Q=R\\cdot T\" alt=\"Q=R\\cdot T\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7f0\/244\/21d\/7f024421d4661116262380021e275bc8.svg\" width=\"84\" height=\"20\"\/><\/em>. I&#8217;m aware that this might be unfamiliar to many, so I&#8217;ve opted for the column vectors and left stochastic transition matrices.<\/p>\n<\/div>\n<\/details>\n<p>Thus, an information channel is essentially a left stochastic matrix, denoted as <em>T<\/em> . By specifying the distribution\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"r_x = \\mathrm{Pr}(input=x)\" alt=\"r_x = \\mathrm{Pr}(input=x)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d96\/c32\/736\/d96c327361cc35f91655c45bdafb40a6.svg\" width=\"165\" height=\"22\"\/><\/em>at the input, you obtain the distribution <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"q_y = \\mathrm{Pr}(output=y)\" alt=\"q_y = \\mathrm{Pr}(output=y)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9ed\/7f9\/9dd\/9ed7f99ddf5ea2dfd35eed6c0234e505.svg\" width=\"171\" height=\"23\"\/><\/em>at the output simply by multiplying the matrix <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T= \\|t_{y,x}\\|\" alt=\"T= \\|t_{y,x}\\|\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/da9\/10f\/ae9\/da910fae9104e4f0fede5f2808fc4c49.svg\" width=\"87\" height=\"23\"\/><\/em>by the vector <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R\" alt=\"R\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0fc\/3cb\/303\/0fc3cb303457af9d1aad79ec52e71afc.svg\" width=\"15\" height=\"17\"\/><\/em>:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"q_y = \\sum_x t_{yx} \\cdot r_x\" alt=\"q_y = \\sum_x t_{yx} \\cdot r_x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a31\/8ee\/cb7\/a318eecb76a8e311ff4b5d1e84d9099a.svg\" width=\"131\" height=\"44\"\/><\/p>\n<p><strong>The capacity<\/strong><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"C(T)\" alt=\"C(T)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/42d\/fb3\/a60\/42dfb3a605fa9f35ac690873d8ee00c6.svg\" width=\"44\" height=\"22\"\/><\/em>of an information channel <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T\" alt=\"T\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ae4\/5aa\/0f5\/ae45aa0f548ce270ec21c8618d800b21.svg\" width=\"14\" height=\"17\"\/><\/em>is defined as the maximum value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(input, output)\" alt=\"\\mathrm{MI}(input, output)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/65c\/733\/11d\/65c73311dd20c30745ed45c2615795d9.svg\" width=\"151\" height=\"22\"\/><\/em>achievable for some input distribution<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R=\\{r_x\\}_x\" alt=\"R=\\{r_x\\}_x\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c9e\/623\/add\/c9e623add69cedeef5aedaca8f6053c2.svg\" width=\"89\" height=\"22\"\/><\/em>at the input.<\/p>\n<p>An information channel for transmitting bits, where 1 turns into 0 with a probability of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon_1,\" alt=\"\\varepsilon_1,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6cf\/f3f\/c81\/6cff3fc817649bd5c72b9d75adf81427.svg\" width=\"23\" height=\"15\"\/><\/em>and 0 turns into 1 with a probability of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon_0\" alt=\"\\varepsilon_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c9c\/905\/602\/c9c90560271d4faac9bcc9f60e7d387b.svg\" width=\"18\" height=\"15\"\/><\/em>\u200b, is defined by the matrix:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"T = \\left\\|\\begin{array}{cc} 1-\\varepsilon_0 &amp;  \\varepsilon_1\\\\ \\varepsilon_0 &amp; 1-\\varepsilon_1 \\end{array}\\right\\|\" alt=\"T = \\left\\|\\begin{array}{cc} 1-\\varepsilon_0 &amp;  \\varepsilon_1\\\\ \\varepsilon_0 &amp; 1-\\varepsilon_1 \\end{array}\\right\\|\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d7e\/7a8\/0f8\/d7e7a80f8f389ca6c61c084b2f007b71.svg\" width=\"188\" height=\"50\"\/><\/p>\n<p><strong>Task 2.7:<\/strong> Let&#8217;s consider an information channel with noise where 1 transforms into 0 with a probability of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon_1,\" alt=\"\\varepsilon_1,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d7e\/54c\/4d7\/d7e54c4d777a22d6c377df3d33d0d87f.svg\" width=\"23\" height=\"15\"\/><\/em>and 0 transforms into 1 with a probability of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\varepsilon_0.\" alt=\"\\varepsilon_0.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a3f\/acc\/82c\/a3facc82ce9df46eac339dde5dc76eb8.svg\" width=\"23\" height=\"15\"\/><\/em> What is the value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(input, \\;output)\" alt=\"\\mathrm{MI}(input, \\;output)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3d9\/56c\/37e\/3d956c37ec8e1a05fbb9f1e1e29e3856.svg\" width=\"156\" height=\"22\"\/><\/em>when the input is a random bit with distribution <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R=\\{0.5,  0.5\\}\" alt=\"R=\\{0.5,  0.5\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/442\/41a\/958\/44241a958cc83e6ddf357a15e1a72bbb.svg\" width=\"119\" height=\"22\"\/><\/em>? What input distribution maximizes <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(input, output)\" alt=\"\\mathrm{MI}(input, output)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b04\/d3e\/d74\/b04d3ed7443b6742b3696399ea2023d1.svg\" width=\"151\" height=\"22\"\/><\/em>, and what is its value? In other words, what is the capacity of this channel?<\/p>\n<p><strong>Answer:<\/strong><\/p>\n<p>Here, it is convenient to use the formula:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI} =  H(Q) - \\sum_x p_x \\cdot H( \\{\\mathrm{Pr}(output = y | \\; input = x)\\}_y ).\" alt=\"\\mathrm{MI} =  H(Q) - \\sum_x p_x \\cdot H( \\{\\mathrm{Pr}(output = y | \\; input = x)\\}_y ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1c0\/b59\/609\/1c0b596095291f1d7812538752abf4e4.svg\" width=\"476\" height=\"44\"\/><\/p>\n<p>We have:<\/p>\n<ul>\n<li>\n<p>Input distribution: <br \/><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"R = \\{r_0, r_1\\}\" alt=\"R = \\{r_0, r_1\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/281\/78e\/c73\/28178ec73702f3481f1ed5ba02d6dd1b.svg\" width=\"104\" height=\"22\"\/><\/em>  <\/p>\n<\/li>\n<li>\n<p>Output distribution: <br \/><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"Q = \\{q_0, q_1\\}  = \\{r_0 \\cdot (1 - \\varepsilon_0) +  r_1 \\cdot \\varepsilon_1,  r_1 \\cdot (1 - \\varepsilon_1) +  r_0 \\cdot \\varepsilon_0\\}\" alt=\"Q = \\{q_0, q_1\\}  = \\{r_0 \\cdot (1 - \\varepsilon_0) +  r_1 \\cdot \\varepsilon_1,  r_1 \\cdot (1 - \\varepsilon_1) +  r_0 \\cdot \\varepsilon_0\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/322\/49e\/df9\/32249edf928027eab0558bc817ee584c.svg\" width=\"503\" height=\"22\"\/><\/em>  <\/p>\n<\/li>\n<li>\n<p>Joint distribution, i.e., distribution over pairs (input, output): <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P =\\{\\{r_0 \\cdot (1 - \\varepsilon_0),   r_1 \\cdot \\varepsilon_1\\}, \\{r_1 \\cdot (1 - \\varepsilon_1),   r_0 \\cdot \\varepsilon_0 \\}\\}\" alt=\"P =\\{\\{r_0 \\cdot (1 - \\varepsilon_0),   r_1 \\cdot \\varepsilon_1\\}, \\{r_1 \\cdot (1 - \\varepsilon_1),   r_0 \\cdot \\varepsilon_0 \\}\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/32a\/647\/5a2\/32a6475a2b932a30babaa9eed2120cd4.svg\" width=\"422\" height=\"22\"\/><\/em>  <\/p>\n<\/li>\n<li>\n<p>And two conditional distributions:<\/p>\n<ul>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{\\mathrm{Pr}(output = y|\\; input = 0)\\}_y = \\{1 - \\varepsilon_0, \\varepsilon_0 \\},\" alt=\"\\{\\mathrm{Pr}(output = y|\\; input = 0)\\}_y = \\{1 - \\varepsilon_0, \\varepsilon_0 \\},\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/46d\/cbf\/1fa\/46dcbf1fa5e5bb735d1c3005e5c8b5bd.svg\" width=\"378\" height=\"23\"\/><\/em> <\/p>\n<\/li>\n<li>\n<p><em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{\\mathrm{Pr}(output = y|\\; input = 0)\\}_y = \\{1 - \\varepsilon_0, \\varepsilon_0 \\},\" alt=\"\\{\\mathrm{Pr}(output = y|\\; input = 0)\\}_y = \\{1 - \\varepsilon_0, \\varepsilon_0 \\},\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/46d\/cbf\/1fa\/46dcbf1fa5e5bb735d1c3005e5c8b5bd.svg\" width=\"378\" height=\"23\"\/><\/em>  <\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>Using the formula for MI, we get:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"MI = H(Q) - r_0 \\cdot H(\\{1 - \\varepsilon_0, \\varepsilon_0 \\}) - r_1\\cdot H(\\{\\varepsilon_1, 1 - \\varepsilon_1\\})\" alt=\"MI = H(Q) - r_0 \\cdot H(\\{1 - \\varepsilon_0, \\varepsilon_0 \\}) - r_1\\cdot H(\\{\\varepsilon_1, 1 - \\varepsilon_1\\})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/34a\/b51\/316\/34ab513168ccb67455a7af78c4a741dc.svg\" width=\"476\" height=\"22\"\/><\/p>\n<p>This formula is nothing but a measure of the convexity of the function <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(x)\" alt=\"H(x)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/256\/5c8\/1e1\/2565c81e1794c00f7054cbe1b7c71240.svg\" width=\"44\" height=\"22\"\/><\/em> (aka JSD, see below) on the interval <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x \\in [\\varepsilon_1, 1 - \\varepsilon_0]\" alt=\"x \\in [\\varepsilon_1, 1 - \\varepsilon_0]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c22\/9bf\/98a\/c229bf98af96cf523ec5acde9b532219.svg\" width=\"124\" height=\"22\"\/><\/em>. In other words, it&#8217;s the value of this function on the convex combination of the abscissas of the endpoints of this interval minus the convex combination of the values of this function at the endpoints (ordinates of the interval).<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/7f3\/47f\/22d\/7f347f22dd642145eb49ce8ae2b22e3a.png\" width=\"1014\" height=\"644\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7f3\/47f\/22d\/7f347f22dd642145eb49ce8ae2b22e3a.png\"\/><\/figure>\n<p>The figure shows the function <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f(x) = H(\\{x, 1 -x \\})\" alt=\"f(x) = H(\\{x, 1 -x \\})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a79\/051\/0ea\/a790510eaae1d2f18f43cb09a2f019e5.svg\" width=\"180\" height=\"22\"\/><\/em>. The KL interval is divided by point A in the ratio of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"r_0:r_1\" alt=\"r_0:r_1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bca\/236\/ba2\/bca236ba22dd1fb776dfd2cd4db326b4.svg\" width=\"52\" height=\"15\"\/><\/em>\u200b. <strong>The length of segment AB is the value of MI.<\/strong><\/p>\n<p>The maximum length of the segment is reached at a point where the derivative<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f'\" alt=\"f'\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fbf\/f77\/e0c\/fbff77e0ca7ddeca59f1cdb8eb7810f4.svg\" width=\"17\" height=\"23\"\/><\/em>equals the slope of the interval.<\/p>\n<p>Generalizing problem 2.7 to the multidimensional case, we get:<\/p>\n<p><strong>Statement 2.1:<\/strong> The channel capacity is determined by the convexity measure of the function <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f(x) = H({x_1, x_2, \\ldots, x_k})\" alt=\"f(x) = H({x_1, x_2, \\ldots, x_k})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e98\/f0e\/001\/e98f0e001973e0a324e2df2b8724ece4.svg\" width=\"208\" height=\"22\"\/><\/em>within a simplex. This simplex is the image of a stochastic transformation defined by the information channel. In particular, it&#8217;s the maximum value of the difference between<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f\" alt=\"f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/443\/764\/bd2\/443764bd2517170882d42c047ddb4538.svg\" width=\"11\" height=\"21\"\/><\/em> from an affine (also known as convex) combination of the vertices of the simplex, the vertices of which are defined by the columns of the stochastic matrix, and the affine combination of the values of the function<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"f\" alt=\"f\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7b5\/e30\/a54\/7b5e30a54e2671ac24cdb239e6fd8afc.svg\" width=\"11\" height=\"21\"\/><\/em> at the vertices of the simplex.The maximum is taken over all possible weights that define the affine sum. In the definition below, the weights are denoted as <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{\\pi_1, \\ldots, \\pi_n\\}\" alt=\"\\{\\pi_1, \\ldots, \\pi_n\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eb0\/322\/075\/eb03220750fa14ff69403b6dd0e4a3ed.svg\" width=\"104\" height=\"22\"\/><\/em>, and the vertices of the simplex are denoted as <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"{P_1, P_2, \\ldots, P_n}\" alt=\"{P_1, P_2, \\ldots, P_n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/62a\/bbd\/2f9\/62abbd2f9abc4356701c717a03d70c85.svg\" width=\"118\" height=\"20\"\/><\/em>.<\/p>\n<p>Interestingly, the channel capacity can be viewed as a measure of the volume enclosed within the simplex, defined by the set of conditional distributions as its vertices.<\/p>\n<p><strong>Definition 2.4:<\/strong> Let there are several distributions<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"{P_1, P_2, \\ldots, P_n}\" alt=\"{P_1, P_2, \\ldots, P_n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/62a\/bbd\/2f9\/62abbd2f9abc4356701c717a03d70c85.svg\" width=\"118\" height=\"20\"\/><\/em>over the same set of values. <a href=\"https:\/\/en.wikipedia.org\/wiki\/Jensen%E2%80%93Shannon_divergence\" rel=\"noopener noreferrer nofollow\">The Jensen\u2013Shannon Divergence (JSD)<\/a> of this set with weights<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{\\pi_1, \\ldots, \\pi_n\\}\" alt=\"\\{\\pi_1, \\ldots, \\pi_n\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eb0\/322\/075\/eb03220750fa14ff69403b6dd0e4a3ed.svg\" width=\"104\" height=\"22\"\/><\/em>is computed as<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(input, output)\" alt=\"\\mathrm{MI}(input, output)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e0b\/1db\/a15\/e0b1dba151d6766c2bfdfaf4425ab004.svg\" width=\"151\" height=\"22\"\/><\/em>for:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"R=\\{\\pi_1, \\ldots,\\pi_n\\}, \\\\ T=\\|P_1,P_2,\\ldots, P_n\\|\" alt=\"R=\\{\\pi_1, \\ldots,\\pi_n\\}, \\\\ T=\\|P_1,P_2,\\ldots, P_n\\|\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/748\/699\/853\/748699853e8c8605c64d2046dfd240cb.svg\" width=\"697\" height=\"50\"\/><\/p>\n<p>so<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"{\\rm JSD}_{\\pi_1, \\ldots, \\pi_n}(P_1, P_2, \\ldots, P_n) =\\\\= H\\left(\\sum_{i=1}^n \\pi_i P_i\\right) - \\sum_{i=1}^n \\pi_i H(P_i).\" alt=\"{\\rm JSD}_{\\pi_1, \\ldots, \\pi_n}(P_1, P_2, \\ldots, P_n) =\\\\= H\\left(\\sum_{i=1}^n \\pi_i P_i\\right) - \\sum_{i=1}^n \\pi_i H(P_i).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f64\/d7a\/22a\/f64d7a22a22cda1d7ef6bdb5dccf2773.svg\" width=\"697\" height=\"90\"\/><\/p>\n<p>The more the distributions differ from each other, the greater the JSD. The maximum<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\max_{\\pi_1, \\ldots, \\pi_n} {\\rm JSD}{\\pi_1, \\ldots, \\pi_n}(P_1, P_2, \\ldots, P_n)  = C(T)\" alt=\"\\max_{\\pi_1, \\ldots, \\pi_n} {\\rm JSD}{\\pi_1, \\ldots, \\pi_n}(P_1, P_2, \\ldots, P_n)  = C(T)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/079\/ea9\/345\/079ea93454423298abf16405afb2c4f8.svg\" width=\"380\" height=\"34\"\/><\/p>\n<p>is the channel capacity of channel <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T=\\|P_1,P_2,\\ldots, P_n\\|.\" alt=\"T=\\|P_1,P_2,\\ldots, P_n\\|.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a80\/ef1\/aed\/a80ef1aed10595adb3cbf641830002ea.svg\" width=\"182\" height=\"22\"\/><\/em><\/p>\n<p><strong>Problem 2.8:<\/strong> Let there are two dependent normal random variables<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h)\" alt=\"(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/924\/1b5\/558\/9241b555860b0f2f8cfd2ca5f5179d91.svg\" width=\"49\" height=\"22\"\/><\/em>with variances <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma_w^2\" alt=\"\\sigma_w^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6a9\/a24\/938\/6a9a24938d9ca5c32473ba0ebadff50a.svg\" width=\"23\" height=\"22\"\/><\/em>   and<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma_h^2\" alt=\"\\sigma_h^2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fea\/fc9\/cd2\/feafc9cd256136bda5864a1508992e74.svg\" width=\"21\" height=\"25\"\/><\/em>, respectively. And let the first one is obtained from the second by adding independent normal noise with variance <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma^2_n\" alt=\"\\sigma^2_n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dd0\/c08\/b2a\/dd0c08b2abb7cd117463911694e33eb5.svg\" width=\"21\" height=\"22\"\/><\/em>:\u00a0<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w = h + noise.\" alt=\"w = h + noise.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/437\/c51\/b17\/437c51b17981f01ef47e51dd0dcbb922.svg\" width=\"127\" height=\"18\"\/><\/em>Then <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\sigma_w^2 = \\sigma_h^2 + \\sigma_n^2.\" alt=\"\\sigma_w^2 = \\sigma_h^2 + \\sigma_n^2.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a91\/07e\/386\/a9107e386137b05b5a2ded221a6d0a84.svg\" width=\"121\" height=\"25\"\/><\/em>What is the mutual information <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w, h)\" alt=\"\\mathrm{MI}(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/782\/22c\/9be\/78222c9bef7122f41aec24ae1d7e60b2.svg\" width=\"74\" height=\"22\"\/><\/em>?<\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>The entropies of <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w\" alt=\"w\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/48f\/930\/dbe\/48f930dbe31080f8e963bf350aa89206.svg\" width=\"14\" height=\"12\"\/> and <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"h\" alt=\"h\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/115\/944\/8e8\/1159448e80c49bf56f0cc5f3ad9606eb.svg\" width=\"11\" height=\"17\"\/> are as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"{1 \\over 2}\\cdot (1+\\log(2\\pi (\\sigma_h^2 + \\sigma_n^2))\\\\\\;\\;\\;\\mathrm{ and } \\;\\;\\;\\;{1 \\over 2}\\cdot (1+\\log(2\\pi \\sigma_h^2))\" alt=\"{1 \\over 2}\\cdot (1+\\log(2\\pi (\\sigma_h^2 + \\sigma_n^2))\\\\\\;\\;\\;\\mathrm{ and } \\;\\;\\;\\;{1 \\over 2}\\cdot (1+\\log(2\\pi \\sigma_h^2))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eaf\/113\/400\/eaf113400731d698414675666e3698f1.svg\" width=\"615\" height=\"89\"\/><\/p>\n<p>The entropy of the pair of real random variables <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{w, h\\}\" alt=\"\\{w, h\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a59\/ac4\/148\/a59ac4148a4c7617f0c16e91e1e19bf0.svg\" width=\"53\" height=\"22\"\/> is:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"H(\\rho_{(w,h)})={1\\over 2}(1 + \\log(2\\pi \\sigma_h^2)) + {1\\over 2}(1 + \\log(2\\pi \\sigma_n^2))\" alt=\"H(\\rho_{(w,h)})={1\\over 2}(1 + \\log(2\\pi \\sigma_h^2)) + {1\\over 2}(1 + \\log(2\\pi \\sigma_n^2))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/91a\/d4d\/af5\/91ad4daf5e588d54387083a1de18cba8.svg\" width=\"423\" height=\"43\"\/><\/p>\n<p>The last expression is obtained by summing the entropies of the two-dimensional distribution of the pair<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{h,noise\\}\" alt=\"\\{h,noise\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fda\/1d5\/274\/fda1d527408293090808a4cb2f7ff2a1.svg\" width=\"86\" height=\"22\"\/><\/em>(the entropy of independent pairs is the sum of their entropies). The entropy of the pair<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{h, w\\}=\\{h,h+noise\\}\" alt=\"\\{h, w\\}=\\{h,h+noise\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5a0\/823\/6aa\/5a08236aa2600bb35a695058e36ed031.svg\" width=\"200\" height=\"22\"\/><\/em>is equal to the entropy of the pair<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{h,noise\\},\" alt=\"\\{h,noise\\},\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f8a\/bdc\/624\/f8abdc6247c505065a777ac9937f3cd2.svg\" width=\"91\" height=\"22\"\/><\/em> because a linear transformation of a vector of random variables using the matrix<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"A\" alt=\"A\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/59a\/7b7\/3a7\/59a7b73a7470301e957472ca0eb5f1d0.svg\" width=\"15\" height=\"17\"\/><\/em> results in a vector with the same entropy plus<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(\\det(A))\" alt=\"\\log(\\det(A))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f85\/0f1\/7aa\/f850f17aa270f62e26faca9942dec9a4.svg\" width=\"97\" height=\"22\"\/><\/em>(you can prove this!). The determinant of our linear transformation is equal to 1.<\/p>\n<p><strong>Explanation about the matrix:<\/strong> here, matrix <strong>A<\/strong> corresponds to the array <strong>{{1,0},{1,1}}<\/strong>:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\left\\|\\begin{array}{l}h\\\\w\\end{array}\\right\\|=\\left\\|\\begin{array}{l}1\\;\\;0\\\\1\\;\\;1\\end{array}\\right\\| \\cdot \\left\\|\\begin{array}{l}h\\\\noise\\end{array}\\right\\|\" alt=\"\\left\\|\\begin{array}{l}h\\\\w\\end{array}\\right\\|=\\left\\|\\begin{array}{l}1\\;\\;0\\\\1\\;\\;1\\end{array}\\right\\| \\cdot \\left\\|\\begin{array}{l}h\\\\noise\\end{array}\\right\\|\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e04\/bba\/0eb\/e04bba0ebd727d7ed71b6a5bf0315758.svg\" width=\"208\" height=\"50\"\/><\/p>\n<p>and its determinant is 1. The value of the determinant <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\det(A)\" alt=\"\\det(A)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/702\/ee1\/5f5\/702ee15f541925bb3475492b28e59097.svg\" width=\"57\" height=\"22\"\/><\/em>is the factor by which the volume of a cube in <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/499\/37e\/f48\/49937ef4828d953c08690c472cf8f5e9.svg\" width=\"12\" height=\"12\"\/><\/em>-dimensional space changes (in our case, <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n=2\" alt=\"n=2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5ed\/934\/84c\/5ed93484cea7a13ef12b0907ac55e768.svg\" width=\"48\" height=\"17\"\/><\/em>). The term <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(\\det(A))\" alt=\"\\log(\\det(A))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f85\/0f1\/7aa\/f850f17aa270f62e26faca9942dec9a4.svg\" width=\"97\" height=\"22\"\/><\/em>arises here for the same reason that the term <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\log(1\/\\varepsilon)\" alt=\"\\log(1\/\\varepsilon)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2b4\/e5e\/e6d\/2b4e5ee6d25f72b91c8cb79291f1462f.svg\" width=\"69\" height=\"22\"\/><\/em>arises in the entropy formula in <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Answer-,Task%201.7,-%3A%20Given%20the\" rel=\"noopener noreferrer nofollow\">task 1.7<\/a> for discretized real random variables. <strong>End of explanation.<\/strong><\/p>\n<p>Finally, using the formula <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(h,w) = H(\\rho_h) + H(\\rho_w) - H(\\rho_{(h,w)})\" alt=\"\\mathrm{MI}(h,w) = H(\\rho_h) + H(\\rho_w) - H(\\rho_{(h,w)})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/477\/7d1\/4c1\/4777d14c146516b8a2d63bda419abd2f.svg\" width=\"332\" height=\"25\"\/><\/em>, we get:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathrm{MI}(w, h) = {1 \\over 2}\\log(1+ {\\sigma_h^2 \\over \\sigma_n^2})\" alt=\"\\mathrm{MI}(w, h) = {1 \\over 2}\\log(1+ {\\sigma_h^2 \\over \\sigma_n^2})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/349\/e8e\/bf3\/349e8ebf3968caa056819b5cab9f6667.svg\" width=\"222\" height=\"53\"\/><\/p>\n<p>Note 1: When the variance (power) of <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"noise\" alt=\"noise\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e8a\/9c1\/d99\/e8a9c1d991ffaca66625c9b03b58ea5d.svg\" width=\"46\" height=\"16\"\/> is equal to the variance (power) of the signal <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w\" alt=\"w\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5fe\/bb3\/067\/5febb3067812f0cbfb3b741e3d56d1f3.svg\" width=\"14\" height=\"12\"\/>, each measurement of <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w\" alt=\"w\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8f2\/b96\/4d6\/8f2b964d61152c8de56f503105ead051.svg\" width=\"14\" height=\"12\"\/> contains 0.5 bits of information about the value of <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"h\" alt=\"h\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3e7\/afb\/843\/3e7afb843f933b1ae9d2fea649c5a8d3.svg\" width=\"11\" height=\"17\"\/>.<\/p>\n<p>Note 2: In essence, this result is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Shannon%E2%80%93Hartley_theorem\" rel=\"noopener noreferrer nofollow\">Shannon-Hartley theorem<\/a> in a simplified form.<\/p>\n<\/div>\n<\/details>\n<p><strong>Task 2.9:<\/strong> Suppose there are two dependent random variables <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h_k)\" alt=\"(w, h_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/643\/fbc\/0fc\/643fbc0fc1567099957d61b50f8361ab.svg\" width=\"58\" height=\"22\"\/>, where <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w\" alt=\"w\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/59f\/d62\/e41\/59fd62e4187c4eb41a6a829260821987.svg\" width=\"14\" height=\"12\"\/> follows an exponential distribution with parameter <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\u03bb\" alt=\"\u03bb\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/87e\/fce\/a96\/87efcea9676de50dbb1243697e046164.svg\" width=\"11\" height=\"17\"\/>, and <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"h_k = floor(kw) \/ k\" alt=\"h_k = floor(kw) \/ k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4f1\/374\/825\/4f1374825dacde56bf3fc9a4db1faa5a.svg\" width=\"148\" height=\"22\"\/>. What is the mutual information <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w, h_k)\" alt=\"\\mathrm{MI}(w, h_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/314\/f56\/676\/314f5667644b9c3f594723fa95714a57.svg\" width=\"83\" height=\"22\"\/><\/em>? In other words, how much information is preserved when rounding an exponential random variable to a certain decimal place? Compare <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w, h_{10})\" alt=\"\\mathrm{MI}(w, h_{10})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cdb\/5cd\/a5b\/cdb5cda5bcd75852e88c5d5d4f60be95.svg\" width=\"90\" height=\"22\"\/><\/em>and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w, h_{100}).\" alt=\"\\mathrm{MI}(w, h_{100}).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/beb\/166\/cc3\/beb166cc3a28fe4555082694815dbbd9.svg\" width=\"102\" height=\"22\"\/><\/em> <\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>Understanding task: The second random variable is uniquely determined by the first one. This means that the mutual information (MI) is simply equal to the entropy of the second variable. The distribution of the second random variable is a geometric progression with <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"q=\\lambda^{1\/k}\" alt=\"q=\\lambda^{1\/k}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/faf\/8ae\/b80\/faf8aeb80571a4d5b1f6096a3a9fe42c.svg\" width=\"69\" height=\"25\"\/><\/em>, and its entropy is<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"H(\\lambda^{1\/k})\/(1 - \\lambda^{1\/k})\" alt=\"H(\\lambda^{1\/k})\/(1 - \\lambda^{1\/k})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/14d\/d18\/160\/14dd18160666afd391abe93cdd2fd12e.svg\" width=\"160\" height=\"26\"\/><\/em>(see <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=number%20of%20measurements.-,Problem%201.4,-%3A%20What%20is%20the\" rel=\"noopener noreferrer nofollow\">task 1.4<\/a>).  <\/p>\n<\/div>\n<\/details>\n<p><strong>Task 2.10:<\/strong> Let&#8217;s consider two dependent random variables<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h_k)\" alt=\"(w, h_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/96a\/347\/e40\/96a347e407a9cb1b5def7408e80399fb.svg\" width=\"58\" height=\"22\"\/><\/em>, where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w\" alt=\"w\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/413\/02a\/25b\/41302a25b9e901f51de8ce529831d0ce.svg\" width=\"14\" height=\"12\"\/><\/em> follows a beta distribution with parameters <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(\\alpha,\\;\\beta)\" alt=\"(\\alpha,\\;\\beta)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/39a\/f0f\/0ef\/39af0f0ef101e7809debfbbe31d55aad.svg\" width=\"53\" height=\"22\"\/><\/em>, and <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"h_k\" alt=\"h_k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6e5\/e76\/d2f\/6e5e76d2f9a9a38690e1151e49cc598d.svg\" width=\"20\" height=\"20\"\/><\/em>is sampled from a binomial distribution with parameters <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(p, n) = (w, k)\" alt=\"(p, n) = (w, k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2a3\/621\/a7f\/2a3621a7f81da1cddb84cce713a1d44a.svg\" width=\"119\" height=\"22\"\/><\/em>. What is the mutual information <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w, h_k)\" alt=\"\\mathrm{MI}(w, h_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/983\/0a6\/54b\/9830a654b419d8624d80ee1b044d8d8c.svg\" width=\"83\" height=\"22\"\/><\/em>? In other words, how many bits of information about the true click-through rate (CTR) of an advertisement can be extracted on average from the click statistics over k impressions?<\/p>\n<p><strong>Task 2.11:<\/strong> Two dependent random variables<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h)\" alt=\"(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/63f\/49c\/527\/63f49c5279a610e04d9ad582fe9d2563.svg\" width=\"49\" height=\"22\"\/>are generated as follows \u2013 first, a random variable <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\u03bb\" alt=\"\u03bb\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/992\/82e\/e00\/99282ee00685917b4712796d4d37df77.svg\" width=\"11\" height=\"17\"\/> is sampled from an exponential distribution with mean <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\u03bb_0\" alt=\"\u03bb_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/694\/74d\/bc5\/69474dbc5da666284e74f9840f7fe8fe.svg\" width=\"20\" height=\"20\"\/>, and then two Poisson random variables<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(w, h)\" alt=\"(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e15\/298\/872\/e15298872ca317851e12ebfacd48118e.svg\" width=\"49\" height=\"22\"\/>are sampled with a parameter <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\u03bb\" alt=\"\u03bb\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b33\/4ab\/280\/b334ab2807e06d486cad69b0d687a5e1.svg\" width=\"11\" height=\"17\"\/>. What is the mutual information <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(w, h)\" alt=\"\\mathrm{MI}(w, h)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/5fa\/4af\/711\/5fa4af7117480c46442dcb0bf5b66444.svg\" width=\"74\" height=\"22\"\/><\/em>? One of the possible interpretations of this problem is as follows: what is the mutual information between the number of sales in one week and the number of sales in another week for a certain unknown product? <\/p>\n<p>The last tasks are an example of how dependencies between random variables can be modeled using <a href=\"https:\/\/en.wikipedia.org\/wiki\/Graphical_model\" rel=\"noopener noreferrer nofollow\">graphical probabilistic models<\/a>, particularly <a href=\"https:\/\/en.wikipedia.org\/wiki\/Bayesian_network\" rel=\"noopener noreferrer nofollow\">Bayesian networks<\/a>.<\/p>\n<p><strong>Task 2.12:<\/strong> The random variable <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"target\" alt=\"target\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/545\/c27\/4da\/545c274da9b6d990718c9fdd922da6d1.svg\" width=\"52\" height=\"20\"\/><\/em>is gotten from independent random variables <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{f_1,\\ldots, f_n,\\; noise\\}\" alt=\"\\{f_1,\\ldots, f_n,\\; noise\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cd6\/c79\/2d7\/cd6c792d7a0e7e4f017f80b90f488add.svg\" width=\"162\" height=\"22\"\/><\/em>with a distribution of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/92a\/b39\/095\/92ab39095f239d951916b312af3274fe.svg\" width=\"63\" height=\"23\"\/><\/em>using the formula:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"target=\\sum_i w_i\\cdot f_i+w_{noise}\\cdot noise\" alt=\"target=\\sum_i w_i\\cdot f_i+w_{noise}\\cdot noise\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d64\/abe\/dc0\/d64abedc0740f3d6ae5711c2e2c27557.svg\" width=\"293\" height=\"45\"\/><\/p>\n<p>The constant weights<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{w_1,\\ldots,w_n\\}\" alt=\"\\{w_1,\\ldots,w_n\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ca3\/0ab\/4e9\/ca30ab4e925783db22b4d110d208f6d9.svg\" width=\"110\" height=\"22\"\/><\/em>are unknown to you, but your prior knowledge about them is that they were independently sampled from <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathcal{N}(0,1)\" alt=\"\\mathcal{N}(0,1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/92a\/b39\/095\/92ab39095f239d951916b312af3274fe.svg\" width=\"63\" height=\"23\"\/><\/em>. You decide to estimate the weights<em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\{\\hat{w_i}\\}_i\" alt=\"\\{\\hat{w_i}\\}_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eda\/d21\/523\/edad21523106d8365932e54a86cd1edf.svg\" width=\"47\" height=\"22\"\/><\/em> using classical regression methods and make a prediction:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"predict = \\sum_i \\hat{w_i}\\cdot f_i\" alt=\"predict = \\sum_i \\hat{w_i}\\cdot f_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/117\/b66\/7f8\/117b667f8413e07ceb7b9b1e8403da30.svg\" width=\"169\" height=\"45\"\/><\/p>\n<p>How will the mean squared error <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"mse = M_{(target - predict)^2}\" alt=\"mse = M_{(target - predict)^2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/78b\/f4a\/b9f\/78bf4ab9f1fa2d40952c6191224e0a98.svg\" width=\"189\" height=\"26\"\/><\/em> and the value of <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\mathrm{MI}(predict, target)\" alt=\"\\mathrm{MI}(predict, target)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/772\/70c\/3f7\/77270c3f76a0a5c222ff952837179950.svg\" width=\"161\" height=\"22\"\/><\/em>change with an increase in the size of the training dataset? Analyze the answer for the case where <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_{noise}=0\" alt=\"w_{noise}=0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/282\/ff4\/cbc\/282ff4cbcd724e754e6fee52691cbac3.svg\" width=\"84\" height=\"20\"\/><\/em>.  .<\/p>\n<ul>\n<li>\n<p><a href=\"https:\/\/habr.com\/en\/articles\/781874\/\" rel=\"noopener noreferrer nofollow\">Part 3 \u2013 ML &amp; Mutual Information<\/a>: Basics of ML in the context of information theory.<\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/764942\/\"> https:\/\/habr.com\/ru\/articles\/764942\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>In <a href=\"https:\/\/habr.com\/en\/articles\/763090\/\" rel=\"noopener noreferrer nofollow\">Part 1<\/a>, we became familiar with the concept of entropy.<\/p>\n<p>In this part, I&#8217;m going to talk about Mutual Information &#8212; a concept that opens the doors to error-resistant coding, compression algorithms, and also provides a fresh perspective on regression and Machine Learning tasks.<\/p>\n<p>This is a necessary component to transition to ML tasks as we move into the next part, treating them as challenges in extracting mutual information between features and the predicted variable. One way to explain the success of ML models is that they create a natural bottleneck, limited by a self-adjusting value of information bits, through which information about the input data is passed (distilled). But that&#8217;s a topic for the next part.<\/p>\n<p>Here, there will be three important visuals:<\/p>\n<ul>\n<li>\n<p>The first one is about visualizing the entropies of two random variables and their mutual information.<\/p>\n<\/li>\n<li>\n<p>The second one is about understanding the concept of the dependency between two random variables and the fact that zero correlation doesn&#8217;t necessarily mean independence.<\/p>\n<\/li>\n<li>\n<p>And the third one is about how the capacity of an information channel has a straightforward geometric interpretation through the convexity measure of the entropy function.<\/p>\n<\/li>\n<\/ul>\n<p>We will also prove a simplified version of <a href=\"https:\/\/en.wikipedia.org\/wiki\/Shannon%E2%80%93Hartley_theorem\" rel=\"noopener noreferrer nofollow\">Shannon-Hartley&#8217;s theorem<\/a> regarding the maximum bandwidth of a noisy channel.<\/p>\n<p>The material is quite complex, presented concisely, and is more like lecture notes. It is assumed that you will independently explore unclear points or ask me questions to clarify them in a more understandable and detailed manner.<\/p>\n<h2>2. Mutual Information  <\/h2>\n<p>When you have two dependent variables, you can talk about how much information about one is contained in the other. <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Task%201.14%3A,8%2C%2010%20provide%3F\" rel=\"noopener noreferrer nofollow\">The last tasks in Part 1<\/a> essentially revolved around this concept &#8212; Mutual Information between two random variables.<\/p>\n<p>For example, let&#8217;s consider a pair  = (person&#8217;s_weight, person&#8217;s_height). For simplicity, let&#8217;s assume these are integers measured in kilograms and centimeters, with a finite number of possible values. In theory, we could gather data from 7 billion people and build a two-dimensional distribution for the pair  &#8212; <strong>the distribution<\/strong> of two dependent random variables. We can separately construct the distribution only for weight  (ignoring height) and the distribution for height  (ignoring weight). These two distributions are called <strong>marginal distributions<\/strong> for the joint distribution on the plane <\/p>\n<p>In this context, these marginal distributions are naturally referred to as <strong>prior distributions<\/strong> &#8212; they correspond to our knowledge of weight and height when we know nothing else about the person.<\/p>\n<p>It&#8217;s clear that information about a person&#8217;s height will cause us to reconsider the distribution of weight. For example, the message &#171;height = 2 meters 10 centimeters&#187; will shift the weight distribution towards higher values. The new weight distribution after receiving this message is naturally called <strong>posterior<\/strong>. Accordingly, you can express the information gained in this message as the difference between the entropies of the prior and posterior distributions:<\/p>\n<p>Here, <strong>outside the curly braces, I indicate the index<\/strong> to iterate within the curly braces <strong>to obtain a list<\/strong>, and if there are two indices, it&#8217;s a <strong>matrix<\/strong>.<\/p>\n<p>It&#8217;s important to note that there&#8217;s no guarantee that this value will be positive. It&#8217;s possible to have a joint distribution where the conditional distribution has higher entropy (uncertainty) than the marginal distribution . However, <strong>on average<\/strong>, for dependent random variables, the value of  is positive, namely, the expected value of this quantity is positive:<\/p>\n<p>This quantity is naturally referred to as information about  in . <strong>Interestingly, it turns out to be symmetric with respect to the permutation of the pair<\/strong> .<\/p>\n<p><strong>Definition 2.1: Mutual information of two random variables is<\/strong><\/p>\n<p>or<\/p>\n<p>or<\/p>\n<p>These are three equivalent definitions. <em><\/em>is the entropy of a discrete distribution where the values are not individual numbers but pairs of numbers <em><\/em>. We will prove the equivalence below.<\/p>\n<p>There is a visualization of the MI value:<\/p>\n<figure class=\"full-width\"><\/figure>\n<p>The entropies of random variables correspond to circles \u2013 green and reddish, with areas equal to <em><\/em>and<em><\/em>respectively, while the brown area of their intersection is precisely <em><\/em>  <\/p>\n<details class=\"spoiler\">\n<summary>Entropy as a measure<\/summary>\n<div class=\"spoiler__content\">\n<p>This visualization, on one hand, is merely an illustration emphasizing that entropy is a non-negative quantity and that <em><\/em>is also a non-negative quantity, which is less than or equal to both <em><\/em>and<em><\/em>. However, on the other hand, there are interesting results that allow us to construct a measure space in which a random variable corresponds to a subset, the union of subsets corresponds to the direct product of random variables (i.e., the union forms a pair), and the measure of subsets is precisely the entropy of the corresponding random variables.  <\/p>\n<\/div>\n<\/details>\n<details class=\"spoiler\">\n<summary>By the way, in the context of machine learning, the image with green and red circles looks like this.<\/summary>\n<div class=\"spoiler__content\">\n<p>We are given some features, and need to predict the signal (target). For example, we need to forecast the air temperature tomorrow at 12:00 PM in the center of London with an accuracy of 0.5\u00b0C. Features can include data on the temperature in London and its surroundings for the past 10 years, the current date, current values of temperature, pressure, humidity, wind, as well as the position of the Moon and other data. It&#8217;s a typical situation where the amount of information in the features is vast, but the target variable is low in entropy. The entire set of data in the features can be called a random variable &#171;w,&#187; and the target variable is &#171;h.&#187; These random variables have mutual information, and the essence of the prediction task is precisely to find this information within the features.  <\/p>\n<figure class=\"full-width\"><\/figure>\n<\/p>\n<\/div>\n<\/details>\n<p>Lets describe the first expression in more detail:<\/p>\n<p>The notation<em><\/em> is simply a shorthand for<\/p>\n<p><em><\/em>  <\/p>\n<p>and is called <a href=\"https:\/\/en.wikipedia.org\/wiki\/Conditional_entropy\" rel=\"noopener noreferrer nofollow\">conditional entropy<\/a>.<\/p>\n<p>For independent random variables,<\/p>\n<p>because, by the definition of independence, <em><\/em>   for any <em><\/em>   Therefore, <strong>for independent random variables, the mutual information is equal to 0<\/strong>.<\/p>\n<p>It turns out that the reverse is also true, meaning the statement <em><\/em> is equivalent to the independence of random variables. However, a similar statement would not hold true for the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Correlation\" rel=\"noopener noreferrer nofollow\">correlation<\/a> of two random variables.<\/p>\n<p>To see the equivalence of the MI definitions, it&#8217;s convenient to introduce the following notations:  <\/p>\n<ul>\n<li>\n<p><em><\/em>  \u2014 probabilities that height and weight are equal to .<\/p>\n<\/li>\n<li>\n<p><em><\/em> \u2014 probabilities that height equals  (marginal distribution of height).<\/p>\n<\/li>\n<li>\n<p><em><\/em> \u2014 probabilities that weight equals  (marginal distribution of weight).<\/p>\n<\/li>\n<\/ul>\n<p>Let&#8217;s assume that all these numbers are non-zero.  <\/p>\n<p>Firstly, notice that <em><\/em>  <\/p>\n<p>Then, by making substitutions and simple transformations, we obtain the equivalence between the first and third definitions:  <\/p>\n<p>The consideration of cases where some of the probabilities are equal to zero lets leave for textbooks.<\/p>\n<p><strong>Task 2.1:<\/strong> Provide an example of random variables for which the correlation is zero, but MI is not zero.<\/p>\n<p><strong>Task 2.2:<\/strong> Two random variables were measured multiple times, and points were plotted on a plane. Which pictures correspond to dependent random variables, and which ones correspond to independent random variables? For which of them is the correlation between x and y equal to 0?<\/p>\n<figure class=\"full-width\">\n<div><figcaption>Measurement results of two random variables. <br \/>On which ones of the 12 pictures are these two variables dependent?  <\/figcaption><\/div>\n<\/figure>\n<details class=\"spoiler\">\n<summary>Answers<\/summary>\n<div class=\"spoiler__content\">\n<p>Dependent: 3rd, 4th, 5th, 8th, 11th, 12th.<\/p>\n<p>Correlation is zero for all except the 4th, 5th, 8th, and 12th.<\/p>\n<\/div>\n<\/details>\n<p><strong>Task 2.3:<\/strong> Calculate MI(w=&#187;number is divisible by a=6&#8243;, h=&#187;number is divisible by b=15&#8243;). It is assumed that we randomly select one of the natural numbers, and all numbers are equally likely. To avoid dealing with the concept of a uniform distribution over natural numbers, consider that we are randomly selecting a number from the set {1, &#8230;, 30}. Prove that if you take coprime numbers a and b, then MI=0.  <\/p>\n<details class=\"spoiler\">\n<summary>Answer<\/summary>\n<div class=\"spoiler__content\">\n<p>We know the marginal distributions: R = {5\/6, 1\/6} and Q = {14\/15, 1\/15}. Furthermore, we know that the probability of being divisible by both 6 and 15 is 1\/30. From this, we can derive the joint probability matrix:<\/p>\n<p>  We use the formula <em><\/em> and get MI = 0.0311278.  <\/p>\n<\/div>\n<\/details>\n<p>Task 2.4: Prove that there is another equivalent definition<\/p>\n<p><em><\/em>  <\/p>\n<p>which means that <strong>MI measures how much less efficient the Huffman code for the stream of pairs <\/strong><strong>, constructed under the assumption of independence of random variables<\/strong> (i.e., assuming that the joint distribution is equal to the product of marginals), <strong>is compared to the Huffman code constructed based on the actual joint distribution.<\/strong> <strong>It is measured in saved bits per symbol (symbol being an observation of the pair <\/strong><strong>).<\/strong><\/p>\n<p>We have been operating in the realm of discrete distributions so far. Transitioning to continuous variables is straightforward.<\/p>\n<p>Let&#8217;s recall <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Task%201.7%3A,Answer\" rel=\"noopener noreferrer nofollow\">task 1.7<\/a>. Suppose we have real random variables , but we discretize them &#8212; the first one into bins of size <em><\/em>, and the second one into bins of size <em><\/em>\u200b. Substituting into the expression<\/p>\n<p>an approximate formula instead of H (see <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Task%201.7%3A,Answer\" rel=\"noopener noreferrer nofollow\">task 1.7<\/a>)<\/p>\n<p>for the entropy of discretized continuous distribution, we will get that the first term contributes <em><\/em> the second term contributes <em><\/em>and the third term (the subtracted one) contributes <em><\/em>and these three pieces will cancel each other out.<\/p>\n<p>Thus, mutual information for continuous variables can be naturally defined as the limit of MI for discretized random variables as the bin sizes approach zero.<\/p>\n<p><strong>Definition 2.2: The mutual information of two continuous random variables<\/strong> is given by<\/p>\n<p>Here, we use the H function from <a href=\"https:\/\/habr.com\/en\/articles\/763090\/#:~:text=Definition%201.6%3A,density%20function%20(PDF).\" rel=\"noopener noreferrer nofollow\">the definition 1.6 in part 1<\/a>.<\/p>\n<p><strong>Task 2.5:<\/strong> Estimate <em><\/em>for any forecasting task you have. Calculate <em><\/em>, and how close is this ratio to 1?<\/p>\n<p>The estimation of MI between two random variables from a set of their measurements essentially boils down to calculating the joint distribution matrix<em><\/em>for discretized values of these random variables. The more bins in the discretization, the less inaccuracy associated with discretization, but the less statistics available for an accurate estimation of <em><\/em>\u200b.<\/p>\n<p>The estimation of MI from observed measurements is a separate extensive topic, and we will <\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-356472","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/356472","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=356472"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/356472\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=356472"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=356472"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=356472"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}