2
$\begingroup$

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.

$\endgroup$

0

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.