Intuitively, I have I have a discrete (finite) random variable $Z$ whose probability mass function $q(z)$ I can choose. $Z$ selects the conditional probability distribution $p(y|x,z)$ of another (discrete finite) random variable $Y$ given a third (discrete, finite) random variable $X$. The probability mass function $p(x)$ and all the $p(y|x,z)$ are given. I want to find maximize the mutual information $I(X:Y)$ over the possible choices of $q(z)$. I.e. I want to vary the channel with a $q$ which maximizes the mutual information between $X$ and $Y$.

More technically, I would like to maximize the following functional $F(q)$ w.r.t. the probability mass function $q:\mathcal{Z}\rightarrow [0,1]$ with $\sum_{z \in \mathcal{Z}} q(z)=1$, where $\mathcal{Z}$ is a finite set:

\begin{equation} \label{eq:one} \max_q F(q) = \max_{q} \sum_{x,y} p(x) \left(\sum_{z} p(y|x,z) q(z)\right) \log \frac{\sum_{\bar{z}} p(y|x,\bar{z}) q(\bar{z})}{\sum_{\bar{x}} p(\bar{x}) \sum_{\tilde{z}} p(y|\bar{x},\tilde{z}) q(\tilde{z})} \end{equation}

Just like $Z$ the random variables $X,Y$ are finite. Additional constraints are just the normalizations of the probabilities:

$$\forall x,z: \sum_y p(y|x,z) = 1 \text{ and } \forall y \; p(y|x,z) \geq 0,$$ $$\sum_x p(x) = 1 \text{ and } \forall x\; p(x) \geq 0.$$

Note that, if we substitute

$$r(y|x):=\sum_{z} p(y|x,z) q(z)$$

we can see that $F(r(q))$ is a mutual information:

$$F(r) = \sum_{x,y} p(x) r(y|x) \log \frac{r(y|x)}{\sum_{\bar{x}} p(\bar{x}) r(y|\bar{x})}=I(X:Y)$$

This shows the relation to the arbitrarily varying channel (AVC). Where $p(y|x,z)$ is usually denoted $w(y|x,s)$. Also in the AVC setting $q(s)$ is considered unknown and the problem is to maximize the mutual information w.r.t. $p(x)$. But here $p(x)$ and $p(y|x,z)$ are given and I want to maximize over $q(z)$.

Does anybody see a better approach than using a global non-linear optimization toolbox? Or do you have a recommendation for a specific optimizer?

I should add that $F(q)$ is probably not concave in $q$ since $F(r)$ is convex in $r$ and $r$ is linear (an thus convex) in $q$. I don't know if $F(q)$ is convex but as pointed out to me by Michael Grant in this question that would not help that much anyway.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.