# Expressing the gradient of the softmax cost function using matrix multiplication

Let $$X_{M\times N}$$ be the attribute matrix ($$M$$ number of attributes and $$N$$ of samples), Let $$Y_{K\times N}$$ be the labels matrix in one hot representation ($$K$$ number of classes), and $$W_{M\times K}$$ is the weights matrix. The softmax function is $$S(\overrightarrow{x}) = \frac{1}{\sum^K_{k=0}{e^{\overrightarrow{w}_k^T\overrightarrow{x}}}}\begin{bmatrix}e^{\overrightarrow{w}^T_0\overrightarrow{x}}\\...\\e^{\overrightarrow{w}^T_k\overrightarrow{x}}\end{bmatrix}$$ and the loss function is $$E_{in}(W)=-\sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}\log{\frac{e^{\overrightarrow{w}^T_k\overrightarrow{x_n}}}{\sum_{j=0}{e^{\overrightarrow{w}_j^T\overrightarrow{x}_n}}}}=\sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}(\log{\sum_{j=0}{e^{\overrightarrow{w}_j^T\overrightarrow{x}_n}}}-\overrightarrow{w}_k^T\overrightarrow{x}_n)$$ I want to find a way to express the gradient of $$W$$, i.e $$\nabla{W}$$, using the matrix $$X$$, $$Y$$, $$S(X)$$

I started by trying to calculate the gradient for $$\overrightarrow{w}_i$$ (the i-th column of $$W$$) $$\nabla_{\overrightarrow{w}_i}E_{in}(W) = \frac{\partial}{\partial w_i}\sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}(\log{\sum_{j=0}{e^{\overrightarrow{w}_j^T\overrightarrow{x}_n}}}-\overrightarrow{w}_k^T\overrightarrow{x}_n)=\sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}\frac{\partial}{\partial w_i}\log{(\sum_{j=0}{e^{\overrightarrow{w}_j^T\overrightarrow{x}_n}})}-\sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}\frac{\partial}{\partial w_i}\overrightarrow{w}_k^T\overrightarrow{x}_n=\sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}\frac{\overrightarrow{x}_ne^{\overrightarrow{w}_i^T\overrightarrow{x}_n}}{\sum_{j=0}{e^{\overrightarrow{w}_j^T\overrightarrow{x}_n}}} - \sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}\overrightarrow{x}_n=\sum_{n=0}^{N}\overrightarrow{x}_n(\sum_{k=0}^{K}1\{y_n=k\}\frac{e^{\overrightarrow{w}_i^T\overrightarrow{x}_n}}{\sum_{j=0}{e^{\overrightarrow{w}_j^T\overrightarrow{x}_n}}} - \sum_{k=0}^{K}1\{y_n=k\})=\sum_{n=0}^{N}\overrightarrow{x}_n(\sum_{k=0}^{K}1\{y_n=k\}S(X)_{i,n} - \sum_{k=0}^{K}1\{y_n=k\})$$ and this is were I got stuck, as I can't see how I can express this using matrices.

I did cheat a little, and using pytorch and numpy, I empirically got that $$\nabla{W} = X(S(X) - Y)^T$$ but I don't see how I get to this from $$\nabla_{\overrightarrow{w}_i}E_{in}(W)$$

I actually made a mistake calculating the gradient here $$\sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}\frac{\partial}{\partial w_i}\log{(\sum_{j=0}{e^{\overrightarrow{w}_j^T\overrightarrow{x}_n}})}-\sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}\frac{\partial}{\partial w_i}\overrightarrow{w}_k^T\overrightarrow{x}_n=$$
it should actually be $$=\sum_{n=0}^{N}\sum_{k=0}^{K}1\{y_n=k\}\frac{\overrightarrow{x}_ne^{\overrightarrow{w}_i^T\overrightarrow{x}_n}}{\sum_{j=0}{e^{\overrightarrow{w}_j^T\overrightarrow{x}_n}}}-\sum_{n=0}^{N}1\{y_n=i\}\overrightarrow{x}_n=\sum_{n=0}^{N}\overrightarrow{x}_n(\sum_{k=0}^{K}1\{y_n=k\}\frac{e^{\overrightarrow{w}_i^T\overrightarrow{x}_n}}{\sum_{j=0}{e^{\overrightarrow{w}_j^T\overrightarrow{x}_n}}}-y_{i,n})=\sum_{n=0}^{N}\overrightarrow{x}_n(\sum_{k=0}^{K}1\{y_n=k\}S(X)_{i,n}-y_{i,n})=\sum_{n=0}^{N}\overrightarrow{x}_n(S(X)_{i,n}-y_{i,n})$$ from here I get $$\nabla_{w_i}E_{in}(W)=X(S-Y)^T_i\Longrightarrow \nabla E_{in}(W)=X(S-Y)^T$$ As I get empirically