1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – leonbloy
    Commented May 2, 2022 at 15:53
  • $\begingroup$ @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. $\endgroup$
    – Sergio
    Commented May 2, 2022 at 16:07
  • $\begingroup$ @leonbloy with the corrections is the question well enough posed so that you can give me an answer or a hint? $\endgroup$
    – Sergio
    Commented May 2, 2022 at 18:52

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .