Deep Learning

Backpropagation

Tip

Dive deep(pun intended) into neural nets with some exciting learnings! Try to become a back prop ninja with Karpathy’s courses.

Derive Backprop Gradients step by step

dprobs = dlogprobs / probs
 
dcounts_sum_inv = (dprobs * counts).sum(1, keepdim=True)
 
dcounts = dprobs * counts_sum_inv
 
dcounts_sum = -dcounts_sum_inv * counts_sum ** -2
 
dcounts += dcounts_sum.broadcast_to(counts.shape)
 
dnorm_logits = dcounts * norm_logits.exp() # norm_logits.exp() is actually counts
 
dlogit_maxes = (-dnorm_logits).sum(1, keepdim=True)
 
dlogits = dnorm_logits.clone()
 
tmp = torch.zeros_like(logits)
 
tmp[range(n), logits.max(1, keepdim=True).indices.view(-1)] = 1 # try F.one_hot
 
dlogits += dlogit_maxes * tmp
 
dh = dlogits @ W2.T
 
dW2 = h.T @ dlogits
 
db2 = dlogits.sum(0, keepdim=False)
 
# dhpreact = dh * (1 - torch.tanh(hpreact) ** 2)
 
# dhpreact = (1.0 - h ** 2) * dh # figure out later
 
dhpreact = hpreact.grad.clone()
 
# dbngain = (dhpreact * bnraw).sum(0, keepdim=True)
 
dbngain = (dhpreact * bnraw).sum(0, keepdim=True)
 
dbnbias = dhpreact.sum(0, keepdim=True)
 
dbnraw = dhpreact * bngain
 
dbnvar_inv = (dbnraw * bndiff).sum(0, keepdim=True)
 
dbndiff = dbnraw * bnvar_inv
 
# dbnvar = dbnvar_inv * (-0.5) * bnvar_inv ** 3
 
dbnvar = dbnvar_inv * (-0.5) * (bnvar + 1e-5) ** -1.5
 
dbndiff2 = 1.0 / (n-1) * torch.ones_like(bndiff2) * dbnvar
 
dbndiff += 2 * bndiff * dbndiff2
 
dbnmeani = -dbndiff.sum(0, keepdim=True)
 
dhprebn = dbndiff.clone()
 
dhprebn += dbnmeani * 1.0 / n * torch.ones_like(hprebn)
 
dembcat = dhprebn @ W1.T
 
dW1 = embcat.T @ dhprebn
 
db1 = dhprebn.sum(0, keepdim=False)
 
demb = dembcat.view(emb.shape)
 
dC = torch.zeros_like(C)
 
for k in range(Xb.shape[0]):
 
for j in range(Xb.shape[1]):
 
ix = Xb[k,j]
 
dC[ix] += demb[k,j]

dlogprobs

Notation-wise, $dlogprobs$ stands for the gradient of loss through $logprobs$. To start we have the following

$$loss=-\frac{1}{n}\sum _{i=1}\sum _{j\in Y_b}logprob{s}_{i,j}$$

which easily yields the gradient as follows.

$${\left(\frac{dloss}{dlogprobs}\right)}_{i,j}=\{\begin{array}{rl}-\frac{1}{n},& j\in Y_b\\ 0,& \text{otherwise}\end{array}$$

dlogprobs = torch.zeros_like(logprobs)
dlogprobs[range(n), Yb] = -1. / n

dprobs

Continue the process, we have

$$logprob{s}_{i,j}=\log (prob{s}_{i,j})$$

Hence

$${\left(\frac{dloss}{dprobs}\right)}_{i,j}={\left(\frac{dloss}{dlogprobs}\right)}_{i,j}\cdot {\left(\frac{dlogprobs}{dprobs}\right)}_{i,j}={\left(\frac{dloss}{dlogprobs}\right)}_{i,j}\cdot \frac{1}{prob{s}_{i,j}}$$

dprobs = dlogprobs / probs

dcounts_sum_inv

dcounts_sum_inv = (dprobs * counts).sum(1, keepdim=True)

Note that probs = counts * counts_sum_inv is in fact

$$prob{s}_{i,j}=count{s}_{i,j}\cdot cs{i}_i$$

For simplicity of notation, denote counts_sum_inv by csi.

Sanity check the broadcasting by taking a look at the shapes.

>>> counts.shape, counts_sum_inv.shape
(torch.Size([32, 27]), torch.Size([32, 1]))

Hence

$${\left(\frac{dprobs}{dcsi}\right)}_i=\sum _{j}count{s}_{i,j}$$

and

$${\left(\frac{dloss}{dcsi}\right)}_i=\sum _j{\left(\frac{dloss}{dprobs}\right)}_{i,j}\cdot {\left(\frac{dprobs}{dcsi}\right)}_i$$

dcounts_sum_inv = (dprobs * counts).sum(1, keepdim=True)

dcounts

Note that from one also has

probs = counts * counts_sum_inv

which leads to

$${\left(\frac{dprobs}{dcounts}\right)}_{i,j}=cs{i}_i$$

However, other than contributing to loss through probs, counts also does that through counts_sum and then counts_sum_inv. The complete gradient of dcounts remains to be determined.

counts_sum_inv = counts_sum**-1

dcounts_sum

leads to

$${\left(\frac{dcsi}{dcs}\right)}_i=-c{s}_i^{-2}$$

and then

$${\left(\frac{dloss}{dcounts\_sum}\right)}_i=-{\left(\frac{dloss}{dcsi}\right)}_i\cdot counts\_su{m}_i^{-2}$$

dnorm_logits

dnorm_logits = dcounts * norm_logits.exp() # norm_logits.exp() is actually counts

dlogit_maxes

dlogit_maxes = (-dnorm_logits).sum(1, keepdim=True)

dlogits

dlogit_maxes = (-dnorm_logits).sum(1, keepdim=True)

Backprop through cross_entropy but All in One Go

Basically what happens in the forward pass can be described by the following pseudocode

logprobs = log(norm(softmax(logits, 1), 1))
loss = -mean(logprobs[range(n), Yb])

To discuss derivative for each single element, for every $i$, denote $(Y_b{)}_i$ by $y$. For simplicity of notation, denote $logits$ by $lg$.

$$\begin{array}{rl}loss& =-\frac{1}{n}\sum _{i=1}^{n}logprob{s}_{i,y}\\ & =-\frac{1}{n}\sum _{i=1}^n\log (prob{s}_{i,y})\\ & =-\frac{1}{n}\sum _{i=1}^n\log \left(\frac{\exp \{l{g}_{i,y}\}}{{\sum }_k\exp \{l{g}_{i,k}\}}\right)\end{array}$$

Note

Keep in mind that there is supposed to be a subtracting the maximum of logits (in each row) in the numerator. Here it is omitted because it does not affect the gradient towards loss.

Now conduct chain rules to derive the derivatives. If $j\ne y$,

$${\left(\frac{dloss}{dlg}\right)}_{i,j}=-\frac{1}{n}\frac{{\sum }_k\exp \{l{g}_{i,k}\}}{\exp \{l{g}_{i,y}\}}\cdot (-1)\cdot \frac{\exp \{l{g}_{i,y}\}}{({\sum }_k\exp \{l{g}_{i,k}\}{)}^2}\cdot \exp \{l{g}_{i,j}\}$$

which yields

$${\left(\frac{dloss}{dlg}\right)}_{i,j}=\frac{1}{n}\cdot \frac{\exp \{l{g}_{i,j}\}}{\sum k\exp \{l{g}_{i,k}\}}=\frac{1}{n}\cdot \text{softmax}(l{g}_{i,\cdot }{)}_j$$

If $j=y$,

$${\left(\frac{dloss}{dlg}\right)}_{i,j}=-\frac{1}{n}\frac{{\sum }_k\exp \{l{g}_{i,k}\}}{\exp \{l{g}_{i,y}\}}\cdot \frac{\exp \{l{g}_{i,y}\}\cdot {\sum }_k\exp \{l{g}_{i,k}\}-\exp \{l{g}_{i,y}{\}}^2}{({\sum }_k\exp \{l{g}_{i,k}\}{)}^2}$$

which yields

$${\left(\frac{dloss}{dlg}\right)}_{i,j}=-\frac{1}{n}+\frac{1}{n}\cdot \frac{\exp \{l{g}_{i,y}\}}{{\sum }_k\exp \{l{g}_{i,k}\}}=\frac{1}{n}\cdot (\text{softmax}(l{g}_{i,\cdot }{)}_y)-1$$

While the two cases are discussed separately, they share a common part in softmax.

dlogits = F.softmax(logits, 1)
dlogits[range(n), Yb] -= 1
dlogits /= n

Finish calculating the rest derivatives. Read more

A typical training loop looks like this. One thing worth mentioning is the line optimizer.zero_grad().

Gradients in PyTorch are accumulated by default. Without zeroing them, gradients from multiple backpropagation steps would add up, leading to incorrect model updates.

In other words, zeroing gradients ensures that each backward pass calculates gradients based only on the current mini-batch.

# Training loop
losses = []
for epoch in range(num_epochs):
    epoch_loss = 0
    for batch_X, batch_y in dataloader:
        # Forward pass
        outputs = model(batch_X)
        loss = criterion(outputs, batch_y)
        
        # Backward pass and optimize
        
        optimizer.zero_grad()
        loss.backward()
        optimizer.step()
        
        
        epoch_loss += loss.item()
    
    # Record average loss for the epoch
    avg_loss = epoch_loss / len(dataloader)
    losses.append(avg_loss)

These steps are part of each training loop iteration and help in adjusting the model’s parameters to improve its predictions.

1. optimizer.zero_grad():

   • Purpose: Clears old gradients.
   • What Happens: Resets the gradients of all model parameters to zero. This prevents the accumulation of gradients from multiple backpropagations, ensuring each mini-batch is computed independently.

2. loss.backward():

   • Purpose: Computes gradients.
   • What Happens: Performs backpropagation to compute the gradient of the loss with respect to each parameter (weight and bias). This is where the network learns, by calculating how much each parameter needs to change to minimize the loss.

3. optimizer.step():

   • Purpose: Updates parameters.
   • What Happens: Updates the model parameters based on the calculated gradients. This step uses the gradients computed during loss.backward() to adjust the weights in an attempt to minimize the loss.

Loss Functions

hinge loss

cross-entropy loss

The cross-entropy between a “true” distribution p and an estimated distribution q is defined as:

$$H(p,q)=-\sum _{x}p(x)\log q(x)$$

Possibly confusing naming conventions

To be precise, the SVM classifier uses the hinge loss, or also sometimes called the max-margin loss. The Softmax classifier uses the cross-entropy loss. The Softmax classifier gets its name from the softmax function, which is used to squash the raw class scores into normalized positive values that sum to one, so that the cross-entropy loss can be applied. In particular, note that technically it doesn’t make sense to talk about the “softmax loss”, since softmax is just the squashing function, but it is a relatively commonly used shorthand.

focal loss

readme

• CS231n - Linear Classification

ROC-AUC

Basic Concepts

Consider a two-class prediction problem (binary classification), in which the outcomes are labeled either as positive or negative. There are four possible outcomes from a binary classifier:

• True Positive(TP): the prediction is positive and the actual value is positive.
• True Negative(TN): the prediction is negative and the actual value is negative.
• False Positive(FP): the prediction is positive and the actual value is negative.
• False Negative(FN): the prediction is negative and the actual value is positive.

Precision measures the accuracy of positive predictions. It is the ratio of true positive predictions to the total positive predictions (true positives + false positives). High precision indicates that fewer false positives are present.

$$\begin{array}{c}\text{Precision}=\frac{TP}{TP+FP}\end{array}$$

Recall (also known as sensitivity or true positive rate) measures the ability of a model to identify all relevant instances. It is the ratio of true positive predictions to the actual number of positive cases (true positives + false negatives). High recall means the model successfully captured most of the actual positives.

$$\begin{array}{c}\text{Recall}=\frac{TP}{TP+FN}\end{array}$$

F1 score is

$$F1=\frac{2}{1/\text{Precision}+1/\text{Recall}}$$

Calculation and Interpretation

Note

The area under the curve (often referred to as simply the AUC) is equal to the probability that a classifier will rank a randomly chosen positive instance higher than a randomly chosen negative one (assuming positive ranks higher than negative). ¹

some probablistic interpretation

The ROC curve $\{(x,y)\}$ can be parameterized by $y=TPR(T)$ and $x=FPR(T)$.

Given a threshold parameter $T$, the instance is identified as positive if $X>T$ and negative otherwise. $X$ follows a probability density function $f_1(x)$ if the instance actually belongs to the class positive, and $f_0(x)$ otherwise. Therefore, the true positive rate is given by $TPR(T)={\int }_T^{\infty }{f}_1(x)dx$ and the false positive rate is given by $\text{FPR}(T)={\int }_T^{\infty }{f}_0(x)dx$. According to the following maps, $\text{TPR}(T):T\to y(x)$ and $\text{FPR}(T):T\to x$, the area under the curve is given by:

$$\begin{array}{rl}\text{AUC}& ={\int }_{x=0}^{1}y(x)dx\\ & ={\int }_{x=0}^1\text{TPR}(T)dx\\ & ={\int }_0^1\text{TPR}({\text{FPR}}^{-1}(x))dx\\ & ={\int }_{\infty }^{-\infty }\text{TPR}(T){\text{FPR}}^{\prime }(T)dT\\ & ={\int }_{-\infty }^{\infty }\text{TPR}(T)f_0(T)dT\\ & ={\int }_{-\infty }^{\infty }{\int }_T^{\infty }{f}_1(x)dx{f}_0(T)dT\\ & ={\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }1\{x\ge T\}{f}_1(x)dx{f}_0(T)dT\\ & ={\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }1\{T^{\prime }\ge T\}{f}_1(T^{\prime })f_0(T)d{T}^{\prime }dT\\ & =P(X_1\ge X_0)\end{array}$$

Read more on ROC’s Wiki page and some CSDN blog post

Suppose the numbers of positive and negative samples in a batch are $M$ and $N$, respectively.

$$\text{AUC}=\frac{\sum \mathbf{I}(P_{pos},P_{neg})}{M\cdot N}$$

where $\mathbf{I}$ is a characteristic function:

$$\mathbf{I}(p,q)=\{\begin{array}{rl}1,& p>q\\ 0.5,& p=q\\ 0,& p<q\end{array}$$

The time complexity is $O(MN)$. Denote by $r_i$ the rank score of $i$-th sample, i.e., for $x_j$ with the smallest prediction score, $r_j=0$ and for $x_k$ with the largest prediction score, $r_k=M+N-1$.

For each positive sample, its rank is precisely the same amount of contribution towards the count of pairs where positive sample is picked over negative sample (because of higher score).

Therefore, one can first sum up all ranks from positive samples, then subtract those cases where two positive samples are paired. Note that for the highest ranked positive sample, there are $M-1$ positive samples below it, corresponding to a subtraction of $M-1$. A simple deduction leads to the final subtraction is

$$(M-1)+\cdots +1+0=\frac{(M-1)M}{2}.$$

Finally we have

$$\text{AUC}=\frac{{\sum }_{i\in \text{Positive}}{r}_i-\frac{(M-1)M}{2}}{M\cdot N}$$

The time complexity is $O((M+N)\log (M+N))$, which is noticeably better than $O(MN)$ when $M$ and $N$ are large.

Now we calculate with an example:

$$\begin{array}{ccc}\text{real label}& \text{pred score}& \text{rank}\\ 1& 0.9& 5\\ 1& 0.7& 4\\ 0& 0.6& 3\\ 1& 0.55& 2\\ 0& 0.2& 1\\ 0& 0.1& 0\end{array}$$

• Calculate AUC with the original formula:

$$\text{AUC}=\frac{1_{0.9}\cdot 3+1_{0.7}\cdot 3+1_{0.55}\cdot 2}{3\cdot 3}=\frac{8}{9}.$$

• Calculate AUC with the quicker formula:

$$\text{AUC}=\frac{5+4+2}{3\cdot 3}-\frac{3-1}{2\cdot 3}=\frac{8}{9}.$$

CUDA

Warning

FileNotFoundError: [Errno 2] No such file or directory: ’:/usr/local/cuda-11.8:/usr/local/cuda-11.8/bin/nvcc’

solution

export CUDA_HOME=/usr/local/cuda

or change export CUDA_HOME=/usr/local/cuda-11.8 in ~/.bashrc to export CUDA_HOME=/usr/local/cuda.

For more detail refer to GitHub issue.

Footnotes

1. Fawcett, Tom (2006); An introduction to ROC analysis, Pattern Recognition Letters, 27, 861–874. ↩