Gradient of Log-Likelihood

Question

Considering the following functions I'm having a tough time finding the appropriate gradient function for the log-likelihood as defined below:

$a_k(x)=\sum_{i=1}^D w_{ki}\cdot x_i$

$P(y_k|x) = {\exp\{a_k(x)\}}\big/{\sum_{k'=1}^K \exp\{a_{k'}(x)\}}$

$L(w)=\sum_{n=1}^N\sum_{k=1}^Ky_{nk}\cdot \ln(P(y_k|x_n))$

where

• $x$ is a vector of inputs defined by 8x8 binary pixels (0 or 1)
• $y_{nk} = 1$ iff the label of sample $n$ is $y_k$ (otherwise 0)
• $N$ is the number of training examples
• $K$ is the number of class labels
• $D := \left\{\left(y_n,x_n\right) \right\}_{n=1}^{N}$

The partial derivatives of the gradient for each weight $w_{k,i}$ should look like this:

$\left<\frac{\delta}{\delta w_{1,1}}L,...,\frac{\delta}{\delta w_{k,i}}L,...,\frac{\delta}{\delta w_{K,D}}L \right>$

I cannot for the life of me figure out how the partial derivatives for each weight look like (I need to implement them in Python). I'm hoping that somebody of you can help me out on this or at least point me in the right direction.

Answer 1

So if we construct a matrix $W$ by vertically stacking the vectors $w^T_{k^\prime}$, we can write the objective as

$$L(w) = \sum_{n,k} y_{nk} \ln \text{softmax}_k(Wx)$$

Then

$$\frac{\partial}{\partial w_{ij}} L(w) = \sum_{n,k} y_{nk} \frac{1}{\text{softmax}_k(Wx)} \times \frac{\partial}{\partial w_{ij}}\text{softmax}_k(Wx)$$

Now the derivative of the softmax function is

$$\frac{\partial}{\partial z_l}\text{softmax}_k(z) = \text{softmax}_k(z)(\delta_{kl} - \text{softmax}_l(z))$$

and if $z = Wx$ it follows by the chain rule that

$$ \begin{align} \frac{\partial}{\partial w_{ij}}\text{softmax}_k(z) & = \sum_l \text{softmax}_k(z)(\delta_{kl} - \text{softmax}_l(z)) \times \frac{\partial z_l}{\partial w_{ij}} \\% & = \text{softmax}_k(z)(\delta_{ki} - \text{softmax}_i(z)) \times x_j \end{align} $$

So the whole thing is

$$ \begin{align} \frac{\partial}{\partial w_{ij}} L(w) & = \sum_{n,k} y_{nk} \frac{1}{\text{softmax}_k(Wx)} \times \text{softmax}_k(z)(\delta_{ki} - \text{softmax}_i(z)) \times x_j \\ & = \sum_{n,k} y_{nk} (\delta_{ki} - \text{softmax}_i(Wx)) \times x_j \end{align} $$

Now, having wrote all that I realise my calculus isn't as smooth as it once was either! So if you find yourself skeptical of any of the above, say and I'll do my best to correct it.