# Active Data Selection and Information Seeking
## 2 Bayesian Inference, Generative Models, and Expected Information Gain
\begin{array}{rl}I[\pi]&=\mathbb{E}_{p(y|\pi)}[\underbrace{D_{KL}[p(\theta|y, \pi)||p(\theta|\pi)]]}_{\text{Information gain}}\\ &=\underbrace{D_{KL}[p(y,\theta|\pi)||p(\theta|\pi)p(y|\pi)]}_{\text{Mutual information}}\\ &=\underbrace{\mathbb{E}_{p(y,\theta|\pi)}[\ln p(y|\theta,\pi)]}_{\text{(-) Conditional entropy}}-\underbrace{\mathbb{E}_{p(y,\theta|\pi)}[\ln p(y|\pi)]}_{\text{ Predictive entropy}}\\ &=\mathbb{E}_{p(\theta|\pi)}\Big{[}\mathbb{E}_{p(y|\theta,\pi)}[\ln p(y| \theta,\pi)]\Big{]}-\mathbb{E}_{\mathbb{E}_{p(\theta|\pi)}[p(y|\theta,\pi)]} \Big{[}\ln\mathbb{E}_{p(\theta|\pi)}[p(y|\theta,\pi)]\Big{]}\end{array}  \tag{2}\]  
In Equation (2), we have conditioned our model upon the variable \(\pi\), which represents a choice we can make in selecting our data. The first line specifies expected information gain directly as the expectation of an information gain. The second line expresses information gain in terms of mutual information that quantifies the degree of conditional dependence between parameters and data. If the parameters were independent of data, the joint distribution would be equal to the product of their marginals, rendering the divergence zero. The third line provides a further interpretation in terms of the difference between two entropies. Essentially, the greater the predictive uncertainty the greater the potential information we can gain, but only if the conditional entropy is sufficiently small that there is a precise mapping from parameters to the data they cause. The final line of Equation (2) re-expresses the penultimate line by explicitly separating the joint distributions into their constituent singleton (i.e., marginal) and conditional distributions. This gives a sense of a recursive structure, in which the key constituents of information gain are themselves built up of expectations of expectations (of expectations as the model becomes more complex). This provides us with a method for quantifying the information gain about parameters in graphical models. Such models are typically expressed using a series of nodes (or edges, in factor graphs) representing variables linked together by the factors of their associated probability distributions. Typically, causative variables are placed towards the top of the graph and measurable data at the bottom. Pairs of nodes are linked if there is a conditional dependence between them. In other words, two nodes are depicted as linked if there is a (conditional probability) factor of the model in which the variable represented by one of the two nodes is in the conditioning set (the 'parent') and the variable represented by the other node is the support (the 'child') of that factor. Using the notation \(pa()\) to represent parents of (i.e., the things something depends upon), and \(ch()\) to represent children of (i.e., the things that depend upon it), we can express the expected information gain in Equation (2)--about a parameter \(\theta_{i}\)--in terms of messages (\(\mu\)) that are passed along the edges of the factor graph:  
\[ \begin{split} I[\pi]^{i}&=\Lambda_{i}\Big{[}\mu_{i} ^{pa(i)}\Lambda_{y}\Big{[}\mu_{i}^{ch(i)}\ln\mu_{i}^{ch(i)}\Big{]}\Big{]}- \Lambda_{y}\Big{[}\mu_{y}^{pa(y)}\ln\mu_{y}^{pa(y)}\Big{]}\\ \mu_{i}^{pa(i)}&=p(\theta_{i}\Big{|}\pi)=\Lambda_{ pa(i)}\Big{[}\mu_{par(i)}^{pa(pa(i))}p(\theta_{i}\Big{|}par(\theta_{i}),\pi) \Big{]}\\ \mu_{i}^{ch(i)}&=p(y\Big{|}\theta_{i},\pi)=\Lambda_{ par(ch(i)),i}\Big{[}\Lambda_{ch(i)}\Big{[}\mu_{ch(i)}^{ch(ch(i))}p(ch(\theta_{i}) \Big{|}pa(ch(\theta_{i})),\pi)\Big{]}\mu_{ch(i)}^{pa(ch(i))\setminus i}\Big{]} \end{split}  \tag{3}\]  
The \(\Lambda\) operator here is introduced to indicate either summation or integration--depending upon whether we are dealing with continuous or discrete variables--with respect to the variables indicated by the subscript. The recursive definitions of the messages (\(\mu\)) in Equation (3) are exactly the definitions that underwrite belief-propagation inference schemes, including the sum-product algorithm [24].