Maximum Entropy Discrete Distribution

Question

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.

Answer 1

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.