2
$\begingroup$

In Pattern Recognition and Machine Learning the author uses Lagrange multipliers to find the discrete distribution with maximum entropy.

Entropy is defined by;

$$H=-\sum_i p(x_i)\ln(p(x_i))$$

and the constraint used in the optimisation is that the probabilities sum to 1.

Therefore the Lagrangian is defined as

$$ \widetilde{H}=-\sum_i p(x_i)\ln(p(x_i))+\lambda(\sum_i p(x_i)-1) $$

Taking the first partial derivative and setting it equal to zero gives $p(x_i)=1/M$, where $M$ is the number of values that $x_i$ takes on.

For the first partial derivative I got $$ \frac{\partial \widetilde{H}}{\partial p(x_i)}=-\sum_i [\ln(p(x_i))+1]+\lambda M$$

The author then states that to verify the stationary point is a maximum we evaluate the second partial derivative which gives;

$$\frac{\partial^2 \widetilde{H}}{\partial p(x_i) \partial p(x_j)}=-I_{ij}\frac{1}{p_(x_i)}$$

where $I_{ij}$ are the elements of the identity matrix.

I would like to know why this is the second partial derivative (how to derive it) and why it means that the stationary point is a maximum.

I think the author may be talking about the hessian not the second partial derivative since they give a matrix not a function.

Following this line of reasoning if I take the second derivative I get;

$$\frac{\partial^2 \widetilde{H}}{\partial p(x_i) \partial p(x_i)}=-\sum_i \frac{1}{p(x_i)}$$

If I take the second partial derivative wrt $j$ for $i\ne j$ I get;

$$\frac{\partial^2 \widetilde{H}}{\partial p(x_i) \partial p(x_j)}=0 \quad \quad (i \ne j) $$

Therefore;

$$\frac{\partial^2 \widetilde{H}}{\partial p(x_i) \partial p(x_j)} = -I_{ij} \sum_i \frac{1}{p(x_i)}$$

But the summation is missing in the given expression for the hessian.

$\endgroup$

1 Answer 1

3
$\begingroup$

You have to keep in mind that the index in the summation is a "dummy index", it is only a placeholder for $1,2,3,\cdots$. Therefore, it is not the same $i$ that appears in the derivative! We can clarify our notation by writing the indices with different letters:

$$\tilde H=-\sum_k p(x_k)\ln p(x_k) +\lambda\left(\sum_k p(x_k)-1\right)$$

Now, we differentiate on $p(x_i)$. The terms $k\neq i$ vanish because they don't depend on $p(x_i)$, so we only have to differentiate the the term with $k=i$:

$$\frac{\partial\tilde H}{\partial p(x_i)}=-1-\ln p(x_i)+\lambda$$

Now, if we differentiate on $p(x_i)$ again, we get:

$$\frac{\partial^2\tilde H}{\partial p(x_i)^2}=-\frac{1}{p(x_i)}$$

On the other hand, if we differentiate on $p(x_j)$ where $j\neq i$:

$$\frac{\partial^2\tilde H}{\partial p(x_i)\partial p(x_j)}=0$$

We can express this compactly as:

$$\frac{\partial^2\tilde H}{\partial p(x_i)\partial p(x_j)}=-I_{ij}\frac{1}{p(x_i)}$$

The matrix with elements given by this formula is, as you said, the hessian matrix of this function. Since it's a diagonal matrix with negative entries only, this is a negative-definite matrix, which implies that this functions achieves a global maximum whenever its gradient is zero.

$\endgroup$
2
  • $\begingroup$ Why does setting the gradient equal to zero give $p(x_i)=1/M$? I get $p(x_i)=e^{\lambda - 1}$. Wait since $\lambda$ is a constant I think this means the $p(x_i)$ are all equal and since there are M of them and they sum to one they are all $p(x_i)=1/M$ $\endgroup$ May 25, 2021 at 10:37
  • $\begingroup$ @tail_recursion You are 100% correct. The answer $p(x_i)=e^{-\lambda-1}$ is a function of the Lagrange multiplier $\lambda$, which you have to find by imposing the restriction $\sum_i p(x_i)=1$. And a shortcut to this is noticing that $p(x_i)$ is constant and adds up to one, as you did. $\endgroup$
    – PedroSebe
    May 25, 2021 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.