Answers.Body: <h2>Information-theoretic view of Bayesian learning</h2>
  <blockquote>
  <p>I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible?</p>
  </blockquote>
  <p>Yes, this is indeed possible. More precisely, there is an <strong>information-theoretic view</strong> of Bayesian learning in neural networks, which can also be thought of as a communication problem, which explains both <em>maximum a posteriori estimation (MAPE)</em> and <em>full</em> Bayesian learning [<a href="https://www.cs.helsinki.fi/u/ahonkela/papers/infview.pdf" rel="nofollow noreferrer">1</a>], i.e. finding the posteriors over the weights of the neural network: the neural networks that maintain a probability distribution over the weights are now known as <strong>Bayesian neural networks</strong> (and, in terms of theory, they are strongly related/similar to the famous <em>variational auto-encoders</em>).</p>
  <p>The oldest relevant paper (I am aware of) that <em>interprets</em> Bayesian learning in neural networks as a <em>communication problem</em> is the 1993 paper by Hinton and Van Camp entitled <a href="https://dl.acm.org/doi/pdf/10.1145/168304.168306" rel="nofollow noreferrer">Keeping the neural networks simple by minimizing the description length of the weights</a> (COLT), which is the paper that introduces <em>variational Bayesian neural networks</em> (sometimes called <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/bishop-ensemble-nato-98.pdf" rel="nofollow noreferrer"><em>ensemble learning</em> in some papers from the 1990s</a>), i.e. variational inference (VI) applied to neural networks (yes, the same VI used in VAEs). <strong>Hinton</strong> (yes, the famous Hinton that won the Turing award) and Van Camp (who is this? probably a Dutch guy from the name!) write in this paper</p>
  <blockquote>
  <p>We can think in terms of a <strong>sender</strong> who can see both the input vector and the correct output and a <strong>receiver</strong> who can only see the input vector. The sender first fits a neural network, of pre-arranged architecture, to the complete set of training cases, then sends the weights to the receiver. For each training case, the sender also sends the discrepancy between the net's output and the correct output. By adding this discrepancy to the output of the net, the receiver can generate exactly the correct output.</p>
  </blockquote>
  <p>You should read this seminal paper if you want to understand all the details.</p>
  <p>Another relevant paper is <a href="https://papers.nips.cc/paper/2011/file/7eb3c8be3d411e8ebfab08eba5f49632-Paper.pdf" rel="nofollow noreferrer">Practical Variational Inference for Neural Networks</a> (2013, NeurIPS) by Graves, who cites the 1993 paper immediately at the beginning of the paper. Essentially, as the title of the paper suggests, Graves tries to make VI in neural networks practical.</p>
  <p>There are other relevant papers that still attempt to provide this information-theoretic view of Bayesian learning, such as <a href="https://www.cs.helsinki.fi/u/ahonkela/papers/infview.pdf" rel="nofollow noreferrer">Variational learning and bits-back coding: An information-theoretic view to bayesian learning</a> (2004, IEEE Transactions on Neural networks), but most current papers on Bayesian neural networks, such as <a href="http://proceedings.mlr.press/v37/blundell15.html" rel="nofollow noreferrer">Weight Uncertainty in Neural Networks</a> (2015, PMLR) don't do it (at most they may mention that this interpretation exists, but they don't go into the details).</p>
  <h3>Minimum description length</h3>
  <p>To give you a few more details, the information-theoretic view of Bayesian learning in these papers is that of the <strong>minimum description length (MDL)</strong>, i.e. Bayesian learning (i.e. the application of Bayes rule to find the posteriors over the parameters of the model) is equivalent to finding a model that gives the &quot;shortest description of the data&quot; (hence the name MDL), where a description is some <a href="https://en.wikipedia.org/wiki/Coding_theory" rel="nofollow noreferrer">code/encoding of the data</a>: in the case of the NNs, this encoding is contained in their weights.</p>
  <p>Given that you want to find the simplest code, then this is a direct application of <strong>Occam's razor</strong>: <em>if you have multiple hypotheses/functions that describe your data (or are consistent with your observations), then choose the simplest one</em>. Occam's razor underlies many other mathematical/ML theories and frameworks, for example, <a href="https://jan.leike.name/AIXI.html" rel="nofollow noreferrer">AIXI</a>, a framework for artificial general intelligence developed by Marcus Hutter. Jürgen Schmidhuber is also a good fan of Occam's razor and <em>compression</em> as a means to act intelligently (see e.g. the <a href="http://people.idsia.ch/%7Ejuergen/speedprior.html" rel="nofollow noreferrer">speed prior</a>). If you are familiar with deep learning, a light bulb should turn on in your brain now. Yes, <strong>regularization</strong> techniques to avoid over-fitting and improve generalization can also be viewed as an application of Occam's razor principle.</p>
  <h3>Bits-back coding</h3>
  <p>How do we find the simplest weights? The <strong>bits-back coding</strong>, used by the 1993 paper and described in the 2004 and 2013 papers, essentially states that you can find the simplest encoding (i.e. posterior over the weights) by minimizing the <strong>Kullback-Leibler divergence</strong> (aka <em>relative entropy</em>: say what?!) between the posterior (which is unknown: so how can we compute the KL divergence?) and some prior (coding distribution), which is zero when the prior is equal to the posterior (but we don't know the posterior) [<a href="https://www.cs.helsinki.fi/u/ahonkela/papers/infview.pdf" rel="nofollow noreferrer">1</a>]. Given that we don't know the posterior, we need to use a proxy objective function that doesn't involve the posterior, such as the <strong>Evidence Lower BOund</strong> (ELBO), also known as <strong>variational free-energy</strong>, which leads to a non-optimal coding (i.e. possibly, you will find some posteriors that are not optimal given the data).</p>
  <h2>Conclusions</h2>
  <p>Using MAPE or performing (approximate) Bayesian learning in a neural network (which finds one function or a probability distribution over functions, respectively) can be interpreted as finding the MDL, i.e. an optimal or near-optimal encoding of the data that needs to be communicated from a sender to a receiver.</p>
  <h2>Side notes</h2>
  <p><strong>Information theory</strong> was pioneered by Claude Shannon in his 1948 seminal paper <a href="http://people.math.harvard.edu/%7Ectm/home/text/others/shannon/entropy/entropy.pdf" rel="nofollow noreferrer">A Mathematical Theory of Communication</a>.</p>
  <p>Claude Shannon was also one of the participants at the <a href="https://en.wikipedia.org/wiki/Dartmouth_workshop" rel="nofollow noreferrer">Dartmouth workshop</a>, which officially started the field of artificial intelligence, so he is one of the fathers of the AI field, and his impact on the field is definitely huge (although most people are not aware of it, but, hopefully, this answer will change that).</p>
  <h2>Further reading</h2>
  <p>Apart from the papers that I cited above, you may also be interested in <a href="https://arxiv.org/pdf/1501.04309.pdf" rel="nofollow noreferrer">Information Theory and its Relation to Machine Learning</a> (2015) by Hu.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-23T13:26:48.947Z
Answers.LastActivityDate: 2020-11-23T11:05:12.157Z
Answers.LastEditDate: 2020-11-23T11:05:12.157Z
Answers.UserDisplayName: nbro
Body: <p>I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible? </p>
  
Tags: <computational-learning-theory><information-theory><bayesian-deep-learning><minimum-description-length>
Title: How can a machine learning problem be reduced as a communication problem?
UserDisplayName: Raphael Augusto
ThreadText: # How can a machine learning problem be reduced as a communication problem?
  
  (Asked by: username_0 on 2020-04-23)
  
  I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible?
  
  **Tags:** computational-learning-theory, information-theory, bayesian-deep-learning, minimum-description-length
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-23. Score: 3 | Accepted answer
  
  ## Information-theoretic view of Bayesian learning
  
  > I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible?
  
  Yes, this is indeed possible. More precisely, there is an **information-theoretic view** of Bayesian learning in neural networks, which can also be thought of as a communication problem, which explains both *maximum a posteriori estimation (MAPE)* and *full* Bayesian learning [[1](https://www.cs.helsinki.fi/u/ahonkela/papers/infview.pdf)], i.e. finding the posteriors over the weights of the neural network: the neural networks that maintain a probability distribution over the weights are now known as **Bayesian neural networks** (and, in terms of theory, they are strongly related/similar to the famous *variational auto-encoders*).
  
  The oldest relevant paper (I am aware of) that *interprets* Bayesian learning in neural networks as a *communication problem* is the 1993 paper by Hinton and Van Camp entitled [Keeping the neural networks simple by minimizing the description length of the weights](https://dl.acm.org/doi/pdf/10.1145/168304.168306) (COLT), which is the paper that introduces *variational Bayesian neural networks* (sometimes called [*ensemble learning* in some papers from the 1990s](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/bishop-ensemble-nato-98.pdf)), i.e. variational inference (VI) applied to neural networks (yes, the same VI used in VAEs). **Hinton** (yes, the famous Hinton that won the Turing award) and Van Camp (who is this? probably a Dutch guy from the name!) write in this paper
  
  > We can think in terms of a **sender** who can see both the input vector and the correct output and a **receiver** who can only see the input vector. The sender first fits a neural network, of pre-arranged architecture, to the complete set of training cases, then sends the weights to the receiver. For each training case, the sender also sends the discrepancy between the net's output and the correct output. By adding this discrepancy to the output of the net, the receiver can generate exactly the correct output.
  
  You should read this seminal paper if you want to understand all the details.
  
  Another relevant paper is [Practical Variational Inference for Neural Networks](https://papers.nips.cc/paper/2011/file/7eb3c8be3d411e8ebfab08eba5f49632-Paper.pdf) (2013, NeurIPS) by Graves, who cites the 1993 paper immediately at the beginning of the paper. Essentially, as the title of the paper suggests, Graves tries to make VI in neural networks practical.
  
  There are other relevant papers that still attempt to provide this information-theoretic view of Bayesian learning, such as [Variational learning and bits-back coding: An information-theoretic view to bayesian learning](https://www.cs.helsinki.fi/u/ahonkela/papers/infview.pdf) (2004, IEEE Transactions on Neural networks), but most current papers on Bayesian neural networks, such as [Weight Uncertainty in Neural Networks](http://proceedings.mlr.press/v37/blundell15.html) (2015, PMLR) don't do it (at most they may mention that this interpretation exists, but they don't go into the details).
  
  ### Minimum description length
  
  To give you a few more details, the information-theoretic view of Bayesian learning in these papers is that of the **minimum description length (MDL)**, i.e. Bayesian learning (i.e. the application of Bayes rule to find the posteriors over the parameters of the model) is equivalent to finding a model that gives the "shortest description of the data" (hence the name MDL), where a description is some [code/encoding of the data](https://en.wikipedia.org/wiki/Coding_theory): in the case of the NNs, this encoding is contained in their weights.
  
  Given that you want to find the simplest code, then this is a direct application of **Occam's razor**: *if you have multiple hypotheses/functions that describe your data (or are consistent with your observations), then choose the simplest one*. Occam's razor underlies many other mathematical/ML theories and frameworks, for example, [AIXI](https://jan.leike.name/AIXI.html), a framework for artificial general intelligence developed by Marcus Hutter. Jürgen Schmidhuber is also a good fan of Occam's razor and *compression* as a means to act intelligently (see e.g. the [speed prior](http://people.idsia.ch/%7Ejuergen/speedprior.html)). If you are familiar with deep learning, a light bulb should turn on in your brain now. Yes, **regularization** techniques to avoid over-fitting and improve generalization can also be viewed as an application of Occam's razor principle.
  
  ### Bits-back coding
  
  How do we find the simplest weights? The **bits-back coding**, used by the 1993 paper and described in the 2004 and 2013 papers, essentially states that you can find the simplest encoding (i.e. posterior over the weights) by minimizing the **Kullback-Leibler divergence** (aka *relative entropy*: say what?!) between the posterior (which is unknown: so how can we compute the KL divergence?) and some prior (coding distribution), which is zero when the prior is equal to the posterior (but we don't know the posterior) [[1](https://www.cs.helsinki.fi/u/ahonkela/papers/infview.pdf)]. Given that we don't know the posterior, we need to use a proxy objective function that doesn't involve the posterior, such as the **Evidence Lower BOund** (ELBO), also known as **variational free-energy**, which leads to a non-optimal coding (i.e. possibly, you will find some posteriors that are not optimal given the data).
  
  ## Conclusions
  
  Using MAPE or performing (approximate) Bayesian learning in a neural network (which finds one function or a probability distribution over functions, respectively) can be interpreted as finding the MDL, i.e. an optimal or near-optimal encoding of the data that needs to be communicated from a sender to a receiver.
  
  ## Side notes
  
  **Information theory** was pioneered by Claude Shannon in his 1948 seminal paper [A Mathematical Theory of Communication](http://people.math.harvard.edu/%7Ectm/home/text/others/shannon/entropy/entropy.pdf).
  
  Claude Shannon was also one of the participants at the [Dartmouth workshop](https://en.wikipedia.org/wiki/Dartmouth_workshop), which officially started the field of artificial intelligence, so he is one of the fathers of the AI field, and his impact on the field is definitely huge (although most people are not aware of it, but, hopefully, this answer will change that).
  
  ## Further reading
  
  Apart from the papers that I cited above, you may also be interested in [Information Theory and its Relation to Machine Learning](https://arxiv.org/pdf/1501.04309.pdf) (2015) by Hu.
  
  
  ---
  
  