# Derivation of the Conditional Maximum Entropy distribution

I am trying to derive the conditional maximum entropy distribution in the discrete case, subject to marginal and conditional empirical moments. We assume that we have access to the empirical moments, $$\tilde{f}$$ and $$\tilde{g}(x)$$, and the distribution of the conditioning variable, $$p(x)$$.

Question Is the derivation correct? Ultimately I would like to have an expression to compute the Conditional MaxEnt distribution using Maximum Likelihood computing the normalizing constant. However, I cannot seem to find a way to transform the last equation into one that does not contain $$\lambda_{j}$$, but instead a (dreadful) log-sum-exp.

We can write the conditional maximum entropy problem as:

\begin{align} \max_{p(y \mid x)}H(Y\mid X) =-&\sum_{x, y}p(x,y)\log \frac{p(y, x)}{p(x)} =-\sum_{x, y}p(y\mid x)p(x)\log p(y\mid x) \\ \text{s.t.} \ &\sum_{y}p(y)f(y)=\sum_{x,y}p(y\mid x)p(x)f(y)=\tilde{f} \quad \text{some marginal empirical moment,} \\ &\sum_{y}p(y\mid x)g(y)=\tilde{g}(x) \quad \text{some conditional empirical moment,} \\ &\sum_{y}p(y\mid x)=1 \quad \text{for all}\ x,\ \text{normalizing condition.} \end{align}

Using the Lagrange multiplier formalism, we can write the Lagrangian as:

\begin{align} \mathcal{L} &= -\sum_{x, y}p(y\mid x)p(x)\log p(y\mid x) \\ &+ \lambda_{f} \left[ \tilde{f}-\sum_{x,y}p(y\mid x)p(x)f(y) \right] \\ &+ \lambda_{g} \left[ \tilde{g}(x)-\sum_{y}p(y\mid x)g(y) \right] \\ &+ \lambda_{1:J} \left[ 1-\sum_{y}p(y\mid x_{j}) \right] \quad \text{for}\ j=1,\cdots J. \end{align}

By differentiating the Lagrangian with respect to the control variable and the multipliers we get the following first-order conditions:

\begin{align} \frac{\partial \mathcal{L}}{\partial p(y_{i}\mid x_{j})}:\ &-p(x_{j})\log p(y_{i} \mid x_{j}) - p(x_{j}) + \lambda_{f}p(x_{j})f(y) + \lambda_{g}g(y)+\lambda_{j} = 0 \\ \frac{\partial \mathcal{L}}{\partial \lambda_{f}}:\ &\tilde{f}-\sum_{x,y}p(y\mid x)p(x)f(y) = 0 \\ \frac{\partial \mathcal{L}}{\partial \lambda_{g}}:\ &\tilde{g}(x)-\sum_{y}p(y\mid x)g(y) = 0 \\ \frac{\partial \mathcal{L}}{\partial \lambda_{j}}:\ &1-\sum_{y}p(y\mid x_{j}) = 0 \\ \end{align}

From the first equation, we obtain:

\begin{align} &p(x_{j})\log p(y_{i} \mid x_{j}) = - p(x_{j}) + \lambda_{f}p(x_{j})f(y_{i}) + \lambda_{g}g(y_{i}) + \lambda_{j} \\ \iff & p(y_{i} \mid x_{j}) = \exp\left[\lambda_{f}f(y_{i}) + \frac{\lambda_{g}g(y_{i})}{p(x_{j})} + \frac{\lambda_{j}}{p(x_{j})}-1\right] \end{align}

This last equation should be somehow transformed into an expression approximately like this:

\begin{align} p(y_{i} \mid x_{j}) = \exp\left[\lambda_{f}f(y_{i}) + \frac{\lambda_{g}g(y_{i})}{p(x_{j})} + \beta(x_{j})\right]. \end{align}

Where $$\beta(x_{j})$$ is a normalizing constant, possibly with a log-sum-exp expression in it.

• It seems to me that $\tilde{f}(y)$ should not depend on $y$. And $\tilde{g}(y)$ should rather be $\tilde{g}(x)$ (it depends on $x$, no?) Also, you are missing the minus sign in the entropy. Commented May 2, 2022 at 15:53
• @leonbloy you are correct, neither $\tilde{f}$ nor $\tilde{g}$ depend on $y$. Also, I missed the negative sign. I don't know how I let those slip. I will edit accordingly. Commented May 2, 2022 at 16:07
• @leonbloy with the corrections is the question well enough posed so that you can give me an answer or a hint? Commented May 2, 2022 at 18:52

## 1 Answer

I doubt that there is an analytical solution.

Calling $$g_{x,y}=p(x|y)$$, $$F_y= \exp f_y$$, $$G_y= \exp g_y$$ , the critical point that produces the Lagrange multipliers can be written as

$$g_{x,y} = (F_y)^a (G_y)^{b_x} \, c_x$$

where $$a$$, $$b_x$$ and $$c_x$$ are $$2n+1$$ constants ($$n$$ is the number of values of $$x$$) to be determined.

The values of $$c_x$$ are given by the $$n$$ normalization equations: $$c_x = \frac{1}{\sum_y {(F_y)^a (G_y)^{b_x}}}$$

We have $$n+1$$ additional equations which equal the number of incognitas.

$$\sum_{x,y} g_{x,y} p_x f_y = \sum_x c_x p_x \sum_y (F_y)^a (G_y)^{b_x} \,f_y = f$$

$$\sum_y g_{x,y} g_y = c_x \sum_y (F_y)^a (G_y)^{b_x} \, g_y = g_x$$

But the equations are highly non linear, hence it's not guaranteed that we have a single solution - or even, if it's the case, if the critical point is indeed a global maximum.