Logistic Regression: Deriving Gradients using Matrix Calculus by Marcus Information Theory ML Foundations 🔍 ## Statement of the Problem Here we are going to derive the gradients for the Logistic Regression model defined for the scalar Cross Entropy Loss, with a softmax penultimate layer, and simple linear layer with an input vector linearly transformed by a matrix. Formally, we have our variables defined as: - Ground truth $g \in \mathbb{R}^c$ - One hot vector indicating which class from $c$ total the predicted answer should be - Predicted vector $y \in \mathbb{R}^c$ - Vector of length $c$ with each element representing probability of answer being that class Of important note, we are going to calculate $y$ by using a simple linear model with $z = Mx$ and then passing $z$ through an element-wise softmax to get $y$, i.e. $y = softmax(z)$. For the formal shapes we have that: - Predicted vector $y \in \mathbb{R}^c$ - $y = softmax(z)$ s.t. softmax() is elementwise - Linear Model intermediate result $z \in \mathbb{R}^c$ - $z = Mx$ - Weight matrix $M \in \mathbb{R}^{c \times n}$ - Input $x \in \mathbb{R}^n$ Seeing all the equations together we have our logistic regression is defined as minimizing scalar Loss $L$ defined by: $$ L(y) = - \sum_{i=1}^C g_i \cdot log(y_i) $$ $$ y = softmax(z) \quad z = Mx $$ with the softmax function defined as: $$ softmax(z_i) = \frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} $$ ## Why does this Matter: A Step Back Resources: - [KL-Divergence & Cross Entropy](https://finetuneinterview.com/lessons/kl-divergence-and-cross-entropy) - [Logistic Regression: Maximum Likelihood](https://finetuneinterview.com/lessons/mle-cross-entropy-and-softmax) - [Properties of L2 Loss](https://finetuneinterview.com/lessons/properties-l2-loss) You may be asking *Why does Logistic Regression Matter? Don't we already have Linear Regression?*, and as a follow up question you may ask *Can't we build neural networks with L2 Loss? Why do we need Cross Entropy Loss?* These are excellent questions, firstly L2 Loss measures how close a prediction is to the ground truth. This assumes that the value we want to predict lives in some Hilbert-like space where we can use Euclidean Distance to measure the distance between two points. If this assumption is not met, then what does the loss function mean? If there's no Eucledian distance between two elements in the output space, then what does the L2 Loss mean, which **is** the distance between two elements in the output space? For classification, where we want to predict what the class should be for the given input, we are choosing which class is correct. This doesn't really make any sense with the notion of a Euclidean L2 distance, which is why we use **Maximum Likelihood Estimation** and the **Cross Entropy Loss**. Cross Entropy states *What's the information we get from the hypothesis distribution $Q$ when we sample using distribution $P$?* i.e. $$ H(P,Q) = \sum_i P(x_i) I_Q(x_i) = - \sum_i P(x_i) log(Q(x_i)) = \mathbb{E}_{i \sim P}\ I_Q(x_i)$$ This measures the expected amount of information from hypothesis distribution $Q$, $I_Q$ when sampled according to the ground truth distribution $P$. For Logistic Regression, typically we have a one-hot vector with 1 indicating the correct class, and 0 for all other classes for our ground truth distribution. The model then predicts a vector of size C (for C total classes) outputting essentially a probability mass function. In this framework we have that the cross entropy loss with ground truth distribution $g$ and predicted distribution $y$ is: $$ L(g,y) = H(g,y) = - \sum_i^C g_i\ log(y_i) $$ Typically, we assume that $g_i,y_i \in [0,1]$ are probabilities, and that $g$ is a one hot vector giving us that if $g_i = 1$ and $g_j = 0$, $\forall j \neq i$ that this becomes $$ L(g,y) = L(y) = -g_i\ log(y_i) $$ Note that, we have to put the softmax in the layer before the loss to force all $y_i$ to be probabilities. We will also see, it's convenient for taking the derivative. This technique is quite powerful, and it's famously used for **Large Language Models** since for a set number of tokens (categories) given the sequence, we predict out what the next token should be for each given step. ## Derivation Ok, let's now derive $\frac{\partial L}{\partial M}$ for Logistic Regression. Recall: $$ L(y) = - \sum_{i=1}^C g_i \cdot log(y_i) $$ $$ y = softmax(z) \quad z = Mx $$ with the softmax function defined as: $$ softmax(z_i) = \frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} $$ ### Find $\frac{\partial L}{\partial z}$ Let's first find $\frac{\partial L}{\partial z}$. Note that we are choosing to look at the Cross Entropy Loss and the Softmax together due to the simplifications we'll encounter, including logs and exponentials cancelling out. We can see that $$ L(y) = - \sum_{i=1}^C g_i \cdot log(y_i)$$ Putting this into a vectorized form we get $$ L(y) = - g^T log(y)$$ where $log(y) = [log(y_0), log(y_1), ... log(y_c)]^T$ i.e. elementwise application. Using the fact that $y = softmax(z)$, we get that $$ L(y) = - g^T log(softmax(z))$$ Since $log$ and $softmax$ are both elementwise functions, we're going to focus just on element $z_i$ for now then apply the results. We have that for the second term $log(softmax(z_i)$ that $$ log(softmax(z_i)) = log \left(\frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} \right) $$ Note that $$log \left(\frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} \right) = log(e^{z_i}) - log(\sum_{k=1}^C e^{z_k}) = z_i - log(\sum_{k=1}^C e^{z_k})$$ giving us that $$ log(softmax(z_i)) = z_i - log(\sum_{k=1}^C e^{z_k})$$ This gives us that: $$ L = - \sum_{i=1}^C g_i \cdot log(y_i) = - \sum_{i=1}^C g_i \cdot (z_i - log(\sum_{k=1}^C e^{z_k}))$$ $$ L = - \sum_{i=1}^C g_i \cdot z_i + \sum_{i=1}^C g_i \cdot log(\sum_{k=1}^C e^{z_k}))$$ Recognize that $ \sum_{i=1}^C g_i \cdot z_i$ is the inner product of $g$ and $z$, i.e. $\sum_{i=1}^C g_i \cdot z_i = g^T z$. $$ L = - g^T z + \sum_{i=1}^C g_i \cdot log(\sum_{k=1}^C e^{z_k}))$$ Now notice that: $$ \sum_{k=1}^C e^{z_k} = [e^{z_0}, e^{z_1}, ... e^{z_c}] \cdot \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) = \mathbf{1}^T e^z $$ Giving us $$ L = - g^T z + \sum_{i=1}^C g_i \cdot log(\mathbf{1}^T e^z) $$ $$ L = - g^T z + log(\mathbf{1}^T e^z) \sum_{i=1}^C g_i $$ Recognize $$ \sum_{i=1}^C g_i = [1, 1, ... 1] \cdot \left( \begin{array}{c} g_0 \\ g_1 \\ \vdots \\ g_c \end{array} \right) = \mathbf{1}^T g $$ giving us $$ L = - g^T z + log(\mathbf{1}^T e^z) \mathbf{1}^T g $$ ### Take the differential of $L$, $dL$ Ok, let's take the differential of $L$, of $$ L = - g^T z + log(\mathbf{1}^T e^z) \mathbf{1}^T g $$ #### First Term For the first term we have: $$ dL = - g^T dz - dg^T\ z $$ Note that $dg = 0$, since the ground truth is constant with respect to the input, giving for the first term: $$ dL = - g^T dz$$ #### Second Term For the second term we have: $$L = log(\mathbf{1}^T e^z) \mathbf{1}^T g$$ **Note** that for elementwise applied functions $\phi(x) = [\phi(x_0), \phi(x_1), ... \phi(x_c)]^T$ its differential is taken by: $$ d \phi(x) = diag(\frac{\partial \phi}{\partial x}) dx = \begin{pmatrix} \frac{\partial \phi}{\partial x_1} & 0 & \cdots & 0 \\ 0 & \frac{\partial \phi}{\partial x_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \frac{\partial \phi}{\partial x_C} \end{pmatrix} dx$$ Given that we know that $log(x)$ and $e^x$ are elementwise, we get the following when taking the differential of $L$ for the second term: $$L = log(\mathbf{1}^T e^z) \mathbf{1}^T g = \mathbf{1}^T g\ log(\mathbf{1}^T e^z)$$ $$ dL = d \left( \mathbf{1}^T g\ log(\mathbf{1}^T e^z) \right) $$ Note that $\mathbf{1}^Tg \in \mathbb{R}$ and is simply a scalar constant. Also that $\mathbf{1}^T e^z \in \mathbb{R}$. $$ = \mathbf{1}^T g \cdot dlog(\mathbf{1}^T e^z) $$ $$ = \mathbf{1}^T g \cdot \frac{1}{\mathbf{1}^T e^z} d (\mathbf{1}^T e^z)$$ We have that $$ d (\mathbf{1}^T e^z) = d \mathbf{1}^T\ e^z + \mathbf{1}^T\ d(e^z)$$ Since $\mathbf{1}$ constant, $d \mathbf{1}^T = 0$ simplifying to $$ d (\mathbf{1}^T e^z) = \mathbf{1}^T\ d(e^z)$$ Given that $e^z$ for $z \in \mathbb{R}^c$ is an elementwise function, we have that $$ d(e^z) = diag(e^z) dz $$ Thus we get that the entire second term is: $$ = \mathbf{1}^T g \cdot \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) dz $$ #### Combine Terms Now let's combine terms to see that $$ dL = d \big(- g^T z + log(\mathbf{1}^T e^z) \mathbf{1}^T g \big)$$ Simplifies to $$ dL = - g^T dz + \mathbf{1}^T g \cdot \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) dz$$ Notice that we have in the second term this expression: $$ \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) $$ which we can see: $$ \mathbf{1}^Te^z = \sum_{k=1}^C e^k $$ $$ \mathbf{1}^T diag(e^z) = [1,1,....] \begin{pmatrix} e^{z_1} & 0 & \cdots & 0 \\ 0 & e^{z_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & e^{z_c} \end{pmatrix} = [e^{z_1}, e^{z_2}, ... e^{z_c}] $$ Giving us that: $$ \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) = \frac{1}{\sum_{k=1}^C e^k} [e^{z_1}, e^{z_2}, ... e^{z_c}]$$ $$ = [\frac{e^{z_1}}{\sum_{k=1}^C e^k}, \frac{e^{z_2}}{\sum_{k=1}^C e^k}, ... \frac{e^{z_c}}{\sum_{k=1}^C e^k}] $$ Given that we know that $$ softmax(z_i) = \frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} $$ we have that: $$ [\frac{e^{z_1}}{\sum_{k=1}^C e^k}, \frac{e^{z_2}}{\sum_{k=1}^C e^k}, ... \frac{e^{z_c}}{\sum_{k=1}^C e^k}] = [softmax(z_1), softmax(z_2), ... softmax(z_c)] = softmax(z^T) $$ Fantastic, this simplifies $dL$ to the canonical form: $$ dL = - g^T dz + \mathbf{1}^T g \cdot \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) dz$$ $$ dL = - g^T dz + softmax(z^T) dz $$ $$ \boxed{ dL = \left[softmax(z^T) - g^T \right] dz}$$ ### Find $dz$ given $z = Mx$ Given that $z = Mx$, where $M \in \mathbb{R}^{C \times n}$, $x \in \mathbb{R}^n$, we have that $$ dz = dM\ x + M dx$$ Since $x$ constant (input), we have $dx=0$, simplifying to $$ dz = dM\ x$$ ### Substitute in $ dz = dM\ x$ & Simplify $$ dL = \left[softmax(z^T) - g^T \right] dz \rightarrow dL = \left[softmax(z^T) - g^T \right] dM\ x$$ Note that since $dL \in \mathbb{R}$ that $trace(dL) = dL$. Thus using the circular trace identity $trace(ABC) = trace(CAB)$, we can simplify the above expression to: $$ dL = \left[softmax(z^T) - g^T \right] dM\ x = trace(\left[softmax(z^T) - g^T \right] dM\ x)$$ $$ dL = trace(x \left[softmax(z^T) - g^T \right] dM)$$ Using the Matrix Calculus Identity that: $$ df = \frac{\partial f}{\partial x} [dx] \text{ i.e. } df = \langle \frac{\partial f}{\partial x}, dx \rangle $$ and specifically for traces that: $$ df = trace(\frac{df}{dx} dx) $$ We can see that $$ \boxed{\frac{\partial L}{\partial M} = x \left[softmax(z^T) - g^T \right]}$$ ### Check Dimensions Finally, let's check dimensions, since we did this in numerator form, $\frac{\partial L}{\partial M} \in \mathbb{R}^{n \times C}$, the transpose of $M \in \mathbb{R}^{C \times n}$. We have our final result as: $$ \frac{\partial L}{\partial M} = x \left[softmax(z^T) - g^T \right] $$ where $x \in \mathbb{R}^{n \times 1}$ and $z^T, g^T \in \mathbb{R}^{1 \times C}$, giving us that their outer product is shape $\mathbb{R}^{n \times C}$. Great! ## Update Rule Using our result, we take it's transpose (to put into the same shape as $M$, i.e. denominator form) to give us $$ M' = M - \alpha \frac{\partial L}{\partial M}^T $$ $$ M' = M - \alpha \left( x \left[softmax(z^T) - g^T \right] \right) ^T $$ $$ \boxed{ M' = M - \alpha \left(\left[softmax(z) - g \right] x^T \right) }$$ ## Statement of the Problem Here we are going to derive the gradients for the Logistic Regression model defined for the scalar Cross Entropy Loss, with a softmax penultimate layer, and simple linear layer with an input vector linearly transformed by a matrix. Formally, we have our variables defined as: - Ground truth $g \in \mathbb{R}^c$ - One hot vector indicating which class from $c$ total the predicted answer should be - Predicted vector $y \in \mathbb{R}^c$ - Vector of length $c$ with each element representing probability of answer being that class Of important note, we are going to calculate $y$ by using a simple linear model with $z = Mx$ and then passing $z$ through an element-wise softmax to get $y$, i.e. $y = softmax(z)$. For the formal shapes we have that: - Predicted vector $y \in \mathbb{R}^c$ - $y = softmax(z)$ s.t. softmax() is elementwise - Linear Model intermediate result $z \in \mathbb{R}^c$ - $z = Mx$ - Weight matrix $M \in \mathbb{R}^{c \times n}$ - Input $x \in \mathbb{R}^n$ Seeing all the equations together we have our logistic regression is defined as minimizing scalar Loss $L$ defined by: $$ L(y) = - \sum_{i=1}^C g_i \cdot log(y_i) $$ $$ y = softmax(z) \quad z = Mx $$ with the softmax function defined as: $$ softmax(z_i) = \frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} $$ ## Why does this Matter: A Step Back Resources: - [KL-Divergence & Cross Entropy](https://finetuneinterview.com/lessons/kl-divergence-and-cross-entropy) - [Logistic Regression: Maximum Likelihood](https://finetuneinterview.com/lessons/mle-cross-entropy-and-softmax) - [Properties of L2 Loss](https://finetuneinterview.com/lessons/properties-l2-loss) You may be asking *Why does Logistic Regression Matter? Don't we already have Linear Regression?*, and as a follow up question you may ask *Can't we build neural networks with L2 Loss? Why do we need Cross Entropy Loss?* These are excellent questions, firstly L2 Loss measures how close a prediction is to the ground truth. This assumes that the value we want to predict lives in some Hilbert-like space where we can use Euclidean Distance to measure the distance between two points. If this assumption is not met, then what does the loss function mean? If there's no Eucledian distance between two elements in the output space, then what does the L2 Loss mean, which **is** the distance between two elements in the output space? For classification, where we want to predict what the class should be for the given input, we are choosing which class is correct. This doesn't really make any sense with the notion of a Euclidean L2 distance, which is why we use **Maximum Likelihood Estimation** and the **Cross Entropy Loss**. Cross Entropy states *What's the information we get from the hypothesis distribution $Q$ when we sample using distribution $P$?* i.e. $$ H(P,Q) = \sum_i P(x_i) I_Q(x_i) = - \sum_i P(x_i) log(Q(x_i)) = \mathbb{E}_{i \sim P}\ I_Q(x_i)$$ This measures the expected amount of information from hypothesis distribution $Q$, $I_Q$ when sampled according to the ground truth distribution $P$. For Logistic Regression, typically we have a one-hot vector with 1 indicating the correct class, and 0 for all other classes for our ground truth distribution. The model then predicts a vector of size C (for C total classes) outputting essentially a probability mass function. In this framework we have that the cross entropy loss with ground truth distribution $g$ and predicted distribution $y$ is: $$ L(g,y) = H(g,y) = - \sum_i^C g_i\ log(y_i) $$ Typically, we assume that $g_i,y_i \in [0,1]$ are probabilities, and that $g$ is a one hot vector giving us that if $g_i = 1$ and $g_j = 0$, $\forall j \neq i$ that this becomes $$ L(g,y) = L(y) = -g_i\ log(y_i) $$ Note that, we have to put the softmax in the layer before the loss to force all $y_i$ to be probabilities. We will also see, it's convenient for taking the derivative. This technique is quite powerful, and it's famously used for **Large Language Models** since for a set number of tokens (categories) given the sequence, we predict out what the next token should be for each given step. ## Derivation Ok, let's now derive $\frac{\partial L}{\partial M}$ for Logistic Regression. Recall: $$ L(y) = - \sum_{i=1}^C g_i \cdot log(y_i) $$ $$ y = softmax(z) \quad z = Mx $$ with the softmax function defined as: $$ softmax(z_i) = \frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} $$ ### Find $\frac{\partial L}{\partial z}$ Let's first find $\frac{\partial L}{\partial z}$. Note that we are choosing to look at the Cross Entropy Loss and the Softmax together due to the simplifications we'll encounter, including logs and exponentials cancelling out. We can see that $$ L(y) = - \sum_{i=1}^C g_i \cdot log(y_i)$$ Putting this into a vectorized form we get $$ L(y) = - g^T log(y)$$ where $log(y) = [log(y_0), log(y_1), ... log(y_c)]^T$ i.e. elementwise application. Using the fact that $y = softmax(z)$, we get that $$ L(y) = - g^T log(softmax(z))$$ Since $log$ and $softmax$ are both elementwise functions, we're going to focus just on element $z_i$ for now then apply the results. We have that for the second term $log(softmax(z_i)$ that $$ log(softmax(z_i)) = log \left(\frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} \right) $$ Note that $$log \left(\frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} \right) = log(e^{z_i}) - log(\sum_{k=1}^C e^{z_k}) = z_i - log(\sum_{k=1}^C e^{z_k})$$ giving us that $$ log(softmax(z_i)) = z_i - log(\sum_{k=1}^C e^{z_k})$$ This gives us that: $$ L = - \sum_{i=1}^C g_i \cdot log(y_i) = - \sum_{i=1}^C g_i \cdot (z_i - log(\sum_{k=1}^C e^{z_k}))$$ $$ L = - \sum_{i=1}^C g_i \cdot z_i + \sum_{i=1}^C g_i \cdot log(\sum_{k=1}^C e^{z_k}))$$ Recognize that $ \sum_{i=1}^C g_i \cdot z_i$ is the inner product of $g$ and $z$, i.e. $\sum_{i=1}^C g_i \cdot z_i = g^T z$. $$ L = - g^T z + \sum_{i=1}^C g_i \cdot log(\sum_{k=1}^C e^{z_k}))$$ Now notice that: $$ \sum_{k=1}^C e^{z_k} = [e^{z_0}, e^{z_1}, ... e^{z_c}] \cdot \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) = \mathbf{1}^T e^z $$ Giving us $$ L = - g^T z + \sum_{i=1}^C g_i \cdot log(\mathbf{1}^T e^z) $$ $$ L = - g^T z + log(\mathbf{1}^T e^z) \sum_{i=1}^C g_i $$ Recognize $$ \sum_{i=1}^C g_i = [1, 1, ... 1] \cdot \left( \begin{array}{c} g_0 \\ g_1 \\ \vdots \\ g_c \end{array} \right) = \mathbf{1}^T g $$ giving us $$ L = - g^T z + log(\mathbf{1}^T e^z) \mathbf{1}^T g $$ ### Take the differential of $L$, $dL$ Ok, let's take the differential of $L$, of $$ L = - g^T z + log(\mathbf{1}^T e^z) \mathbf{1}^T g $$ #### First Term For the first term we have: $$ dL = - g^T dz - dg^T\ z $$ Note that $dg = 0$, since the ground truth is constant with respect to the input, giving for the first term: $$ dL = - g^T dz$$ #### Second Term For the second term we have: $$L = log(\mathbf{1}^T e^z) \mathbf{1}^T g$$ **Note** that for elementwise applied functions $\phi(x) = [\phi(x_0), \phi(x_1), ... \phi(x_c)]^T$ its differential is taken by: $$ d \phi(x) = diag(\frac{\partial \phi}{\partial x}) dx = \begin{pmatrix} \frac{\partial \phi}{\partial x_1} & 0 & \cdots & 0 \\ 0 & \frac{\partial \phi}{\partial x_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \frac{\partial \phi}{\partial x_C} \end{pmatrix} dx$$ Given that we know that $log(x)$ and $e^x$ are elementwise, we get the following when taking the differential of $L$ for the second term: $$L = log(\mathbf{1}^T e^z) \mathbf{1}^T g = \mathbf{1}^T g\ log(\mathbf{1}^T e^z)$$ $$ dL = d \left( \mathbf{1}^T g\ log(\mathbf{1}^T e^z) \right) $$ Note that $\mathbf{1}^Tg \in \mathbb{R}$ and is simply a scalar constant. Also that $\mathbf{1}^T e^z \in \mathbb{R}$. $$ = \mathbf{1}^T g \cdot dlog(\mathbf{1}^T e^z) $$ $$ = \mathbf{1}^T g \cdot \frac{1}{\mathbf{1}^T e^z} d (\mathbf{1}^T e^z)$$ We have that $$ d (\mathbf{1}^T e^z) = d \mathbf{1}^T\ e^z + \mathbf{1}^T\ d(e^z)$$ Since $\mathbf{1}$ constant, $d \mathbf{1}^T = 0$ simplifying to $$ d (\mathbf{1}^T e^z) = \mathbf{1}^T\ d(e^z)$$ Given that $e^z$ for $z \in \mathbb{R}^c$ is an elementwise function, we have that $$ d(e^z) = diag(e^z) dz $$ Thus we get that the entire second term is: $$ = \mathbf{1}^T g \cdot \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) dz $$ #### Combine Terms Now let's combine terms to see that $$ dL = d \big(- g^T z + log(\mathbf{1}^T e^z) \mathbf{1}^T g \big)$$ Simplifies to $$ dL = - g^T dz + \mathbf{1}^T g \cdot \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) dz$$ Notice that we have in the second term this expression: $$ \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) $$ which we can see: $$ \mathbf{1}^Te^z = \sum_{k=1}^C e^k $$ $$ \mathbf{1}^T diag(e^z) = [1,1,....] \begin{pmatrix} e^{z_1} & 0 & \cdots & 0 \\ 0 & e^{z_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & e^{z_c} \end{pmatrix} = [e^{z_1}, e^{z_2}, ... e^{z_c}] $$ Giving us that: $$ \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) = \frac{1}{\sum_{k=1}^C e^k} [e^{z_1}, e^{z_2}, ... e^{z_c}]$$ $$ = [\frac{e^{z_1}}{\sum_{k=1}^C e^k}, \frac{e^{z_2}}{\sum_{k=1}^C e^k}, ... \frac{e^{z_c}}{\sum_{k=1}^C e^k}] $$ Given that we know that $$ softmax(z_i) = \frac{e^{z_i}}{\sum_{k=1}^C e^{z_k}} $$ we have that: $$ [\frac{e^{z_1}}{\sum_{k=1}^C e^k}, \frac{e^{z_2}}{\sum_{k=1}^C e^k}, ... \frac{e^{z_c}}{\sum_{k=1}^C e^k}] = [softmax(z_1), softmax(z_2), ... softmax(z_c)] = softmax(z^T) $$ Fantastic, this simplifies $dL$ to the canonical form: $$ dL = - g^T dz + \mathbf{1}^T g \cdot \frac{1}{\mathbf{1}^Te^z} \mathbf{1}^T diag(e^z) dz$$ $$ dL = - g^T dz + softmax(z^T) dz $$ $$ \boxed{ dL = \left[softmax(z^T) - g^T \right] dz}$$ ### Find $dz$ given $z = Mx$ Given that $z = Mx$, where $M \in \mathbb{R}^{C \times n}$, $x \in \mathbb{R}^n$, we have that $$ dz = dM\ x + M dx$$ Since $x$ constant (input), we have $dx=0$, simplifying to $$ dz = dM\ x$$ ### Substitute in $ dz = dM\ x$ & Simplify $$ dL = \left[softmax(z^T) - g^T \right] dz \rightarrow dL = \left[softmax(z^T) - g^T \right] dM\ x$$ Note that since $dL \in \mathbb{R}$ that $trace(dL) = dL$. Thus using the circular trace identity $trace(ABC) = trace(CAB)$, we can simplify the above expression to: $$ dL = \left[softmax(z^T) - g^T \right] dM\ x = trace(\left[softmax(z^T) - g^T \right] dM\ x)$$ $$ dL = trace(x \left[softmax(z^T) - g^T \right] dM)$$ Using the Matrix Calculus Identity that: $$ df = \frac{\partial f}{\partial x} [dx] \text{ i.e. } df = \langle \frac{\partial f}{\partial x}, dx \rangle $$ and specifically for traces that: $$ df = trace(\frac{df}{dx} dx) $$ We can see that $$ \boxed{\frac{\partial L}{\partial M} = x \left[softmax(z^T) - g^T \right]}$$ ### Check Dimensions Finally, let's check dimensions, since we did this in numerator form, $\frac{\partial L}{\partial M} \in \mathbb{R}^{n \times C}$, the transpose of $M \in \mathbb{R}^{C \times n}$. We have our final result as: $$ \frac{\partial L}{\partial M} = x \left[softmax(z^T) - g^T \right] $$ where $x \in \mathbb{R}^{n \times 1}$ and $z^T, g^T \in \mathbb{R}^{1 \times C}$, giving us that their outer product is shape $\mathbb{R}^{n \times C}$. Great! ## Update Rule Using our result, we take it's transpose (to put into the same shape as $M$, i.e. denominator form) to give us $$ M' = M - \alpha \frac{\partial L}{\partial M}^T $$ $$ M' = M - \alpha \left( x \left[softmax(z^T) - g^T \right] \right) ^T $$ $$ \boxed{ M' = M - \alpha \left(\left[softmax(z) - g \right] x^T \right) }$$ Comments (0) Please log in to comment. No comments yet. Be the first to comment! ← Back to Lessons
Comments (0)
Please log in to comment.
No comments yet. Be the first to comment!