Vtyjkyuk

Consider the training cost for softmax regression (I will use the term multinomial logistic regression):

$$ J( theta ) = - sum^m_i=1 sum^K_k=1 1 y^(i) = k log p(y^(i) = k mid x^(i) ; theta) $$

according to the UFLDL tutorial the derivative of the above function is:

$$ bigtriangledown_ theta^(k) J( theta ) = -sum^m_i=1 [x^(i) (1 y^(i) = k - p(y^(i) = k mid x^(i) ; theta) ) ] $$

however, they didn't include the derivation. Does someone know what the derivation is?

I have tried taking the derivative of it but even my initial steps seems to disagree with the final form they have.

So I first took the gradient $bigtriangledown_ theta^(k) J( theta )$ as they suggested:

$$ bigtriangledown_ theta^(k) J( theta ) = - bigtriangledown_ theta^(k) sum^m_i=1 sum^K_k=1 1 y^(i) = k log p(y^(i) = k mid x^(i) ; theta) $$

but since we are taking the gradient with respect to $theta^(k)$, only the term that matches this specific k will be non-zero when we taking derivatives. Hence:

$$ bigtriangledown_ theta^(k) J( theta ) = - sum^m_i=1 bigtriangledown_ theta^(k) log p(y^(i) = k mid x^(i) ; theta) $$

then if we proceed we get:

$$ - sum^m_i=1 frac1p(y^(i) = k mid x^(i) ; theta) bigtriangledown_ theta^(k) p(y^(i) = k mid x^(i) ; theta) $$

however, at this point the equation looks so different from what the UDFL tutorial has plus the indicator function disappeared completely, that it makes me suspect that I probably made a mistake somewhere. On top of that it seems that the final derivative has difference, but I don't see any differences/subtractions on my derivation. I suspect a difference might come in when expressing the Quotient rule but the indicator function disappearing still worries me. Any ideas?

I encountered the same problem and tackled it after understanding the algorithm. Here I'd like to explain a bit.

$$ J( theta ) = - sum^m_i=1 sum^K_k=1 1 y^(i) = k log p(y^(i) = k mid x^(i) ; theta) $$

Just imagine the result as a 2D matrix with each item(i, k) being a probability, each raw being a coefficient vector for the ith sample(or observation i) and each column being a category(k).

Let's expand p and make the equation to this:

$ J( theta ) = - sum^m_i=1 sum^K_k=1 1 y^(i)=k log frace^theta^T_k x^(i)sum^K_l=1e^theta^T_l x^(i)$

And rearranging gives:

$ J( theta ) =- sum^m_i=1 sum^K_k=1 1 y^(i)=k[log e^theta^T_kx^(i)-log sum^K_l=1e^theta^T_lx^(i)]$

The partial derivative of $J$ with respect to $theta_k$ is (treat $1 y^(i)=k$ as a constant):

$ bigtriangledown_ theta_k J( theta ) = - sum^m_i=1 1 y^(i)=k[x^(i)-underbracefrac1sum^K_l=1e^theta^T_lx^(i)e^theta^T_kx^(i)_p(y^(i) = k mid x^(i) ; theta)x^(i)] + 1y^(i) neq k[-underbracefrac1sum^K_l=1e^theta^T_lx^(i)e^theta^T_kx^(i)_p(y^(i) = k mid x^(i) ; theta)x^(i)]$

Note that for the kth category only one element in $bigtriangledown_ theta_k sum^K_l=1e^theta^T_lx^(i)$ is nonzero, that is $e^theta^T_kx^(i)$.

Then we replace p back and get:

$$ bigtriangledown_ theta_k J( theta ) = -sum^m_i=1 [x^(i) (1 y^(i) = k - p(y^(i) = k mid x^(i) ; theta) ) ] $$