Machine Learning is Calculus Plus Linear Algebra

Henry Kautz henry.kautz@gmail.com

Loss Functions

The goal of machine learning is to learn a function $f$$f$ from some input space $X$$X$ to some output space $Y$$Y$ from training data $D$$D$. This may sound abstract, but is general enough to cover anything we might call learning. The algorithm is given the form of the input and output spaces and the space of functions $F$$F$ from which $f$$f$ is drawn. In supervised learning, the learning algorithm is give a set of pairs $[x,y]$$[x,y]$. In unsupervised learning, the algorithm is given only a set of instances $x$$x$. We consider only supervised learning here.

Let $f$$f$ be a candidate function. The loss $L$$L$ measures the errors $f$$f$ makes on the training data.

where $|f(x),y|$$|f(x), y|$ is a measure of distance in the output space, $\lambda$$\lambda$ is a small real number, and $r(f)$$r(f)$ is a "regularizer", that is, some a priori measure of preference over learned functions. The goal of machine learning is to find an $f$$f$ that minimizes this loss function.

Parameterized Families of Functions

Now let us assume that $f$$f$ comes from a class of functions parameterized by a vector of real numbers $\mathrm{\Theta }$$\Theta$. For example, the class could be neural networks of a certain shape, and $\mathrm{\Theta }$$\Theta$ could be a vector of the weights of the network. To simplify notation, we will write $L_{f_{\mathrm{\Theta }}}$$L_{f_\Theta}$ as simply $L_{\mathrm{\Theta }}$$L_\Theta$, and $r(f_{\mathrm{\Theta }})$$r(f_\Theta)$ as $r(\mathrm{\Theta })$$r(\Theta)$.

Our goal, then, is to find $\theta$$\theta$ that minimizes $L_{\theta }$$L_\theta$. A convex function over the reals can be minimized by starting at a random point, computing the derivative of the function at that point, taking a small step in the opposite of the direction of the derviative, and repeating until the derivative is zero. A convex function over a sequence of reals can be minimized by following the negative of its "gradient" downhill, where the gradient is the sequence of partial derivatives of the function over each of its parameters. Although in general $F$$F$ is not provabily convex, in practice for many useful classes of functions this approach finds a good approximation to the minimum. The gradient is thus defined as follows where $n$$n$ is the number of parameters:

Now let us take the output space to be the reals or a vector of reals; the distance measure to be the squared Euclidean norm; and $r$$r$ to be a real-value function:

In the case that the output is a single real number, the squared Euclidean norm is simply $(f_{\mathrm{\Theta }}(x)-y{)}^2$$(f_\Theta(x) - y)^2$. If the output is a vector, it is the dot product $(f_{\mathrm{\Theta }}(x)-y{)}^T(f_{\mathrm{\Theta }}(x)-y)$$(f_\Theta(x)-y)^T(f_\Theta(x)-y)$, and thus is a single real number. We can simplify the gradient using the fact that the derivative of a sum is a sum of derivatives as follows:

Now consider one element of the vector inside the summation above. We can use the chain rule to calculate that

This expression can be interpreted as twice the influence of the parameter on the results times the difference between the current candidate and the target. (The difference is also called the error or the residual.) Gradient descent minimizes the loss by repeatedly updating the parameters by a small constant $\eta$$\eta$ times the negative of the gradient.

We see now that we can compute the gradient of the loss function as long as the family of parameterized functions $f_{\mathrm{\Theta }}$$f_\Theta$ is differentiable with respect to $\mathrm{\Theta }$$\Theta$ and the the regularization function is likewise differentiable.

In gradient descent, the parameters are adjusted many time. Each pass over the training data is called an epoch. A stopping rule specifies when training stop. A simple rule is to stop when all the elements of the gradient are smaller in absolute value than some given small constant. Another stopping rule is hold out some of the data in what is called a validation set. The validation data is not used in computing the gradient. Instead, after some number of descent steps, the network is tested on the validation data. If the loss on the validation set stops decreasing, then training stops, because the network has stopped generalizing to data not used in training. This stopping rule prevents the network from overfitting to the training data and failing to generalize to new data.

Regularization Functions

The general purpose of regularization is prefer simplier functions under the hope that they generalize better to unseen data. This is a way to implement Ockham’s Razor, the principle that the simpliest explanation is usually the best.

A commonly used regularization function is the sum of squares of the parameters, which is called the L2 regularizer.

This will prefer functions where many of the parameters are zero or near zero. (It is often combined with a heuristic step where near-zero parameters are rounded to zero.) It is easy to compute the gradient of this function:

Artificial Neurons

A standard artificial neuron takes the weighted sum of its inputs plus a constant and applies a non-linear function to produce the output. The constant can be handled by considering it to be a weight applied to special input that is always 1. Many non-lnear output functions have been studied, but the most useful turn out to be a simple threshold function that outputs zero if the sum is negative and outputs the sum otherwise. This is called a "rectified linear unit" (ReLU). We assume that input $x_0$$x_0$ is fixed to 1. The parameterized function $f_{\theta }$$f_\theta$ is thus

The fact that this function is not differential at 0 can be ignored by simply defining its deriviative to be 0 at 0. (Although the standard definition of derivatives do not allow this trick, more generalized notions of derivative from convex analysis allows this to be done as a "choice of subgradient".)

When taking the partial derivative of $f_{\mathrm{\Theta }}(x)$$f_\Theta(x)$ with respect to a weight ${\theta }_i$$\theta_i$ all of the terms in the sum ${\mathrm{\Theta }}^{T}x$$\Theta^T x$ not involving ${\theta }_i$$\theta_i$ become zero and the one that does involve ${\theta }_i$$\theta_i$ becomes its coefficient $x_i$$x_i$. Therefore

Note that because our neuron has a single output, it's partial derivative is a single real number rather than a vector of real numbers. We can write down and simplify the gradient as follows.

The reader will note that the when $x$$x$ is such that the output of the unit is zero, the first term of the gradient becomes zero and only the regularization function can move the gradient away from zero. This fact can lead linear rectifier units to become stuck at zero during optimization. There are variations of linear rectifier units that include a slight slope in the negative sum region to prevent this from happening. The issue of dead units is less of problem once we move to large networks with thousands or millions of units because having some fraction of the units "die" during training can make the network smaller and faster.

Layered Neural Networks

Single neurons or even a single layer of neurons can only learn linear functions. Once multiple layers are introduced, with enough neurons any function can be learned. There theoretical results on the width and depth necessary to learn various classes of functions. For example, any continuous function can be learned by a network of depth $2$$2$ and arbitrarily high width. Likewise, any function can be learned by a network of width $n+1$$n+1$ where $n$$n$ is the number of inputs and arbitrarily high depth. In practice, of course, both the width and depth must be bounded, and finding a sufficient width and depth for a particular task is a matter of trial and error.

Consider a layered neural network where $L$$L$ is the depth. Each unit in a layer takes inputs from all of the neurons in the previous layer. By convention the inputs are layer $0$$0$, and the input in position $0$$0$ in each layer is fixed to $1$$1$. The following notation is commonly used where $l$$l$ is the layer and $i$$i$ is the postion in the layer of the neuron.

Following common practice, we will henceforth use $W$$W$ for the parameters instead of $\mathrm{\Theta }$$\Theta$. We will also use an improved notation for the nonlinear activation function $\sigma$$\sigma$ in an ReLU and its derivative:

The derivative uses indicator function notation, where $\mathbf{1}\{P\}$$\mathbf{1}\{\,P \,\}$ means "1 if the statement $P$$P$ is true, 0 otherwise".

Example: a 3-Unit Network

We begin by considering a three unit network where there are there are two inputs in layer 0, two ReLU units in layer 1, one ReLU unit in the output layer 2, and no regularization. There are a total of 9 weights in the network. (Recall that three of the weights are for the special $x_0^{(l)}$$x_0^{(l)}$ constant 1 inputs. Some formalizations of neural networks use a separate vector of so-called bias weights instead of using special fixed inputs.)

We will see that the calculation of the gradient uses the error signal of the entire network in computing the derivatives for the weights in the output layer, and then propagates the error signal back to the previous layer in proportion to the weights on the outputs of that layer, and so on. This intuitive description of the calculation is why the method is named "back propagation". It is important to understand, however, that it is simply an application of the chain rule.

For a given training instance $((x_1,x_2),y)$$((x_1,x_2),y)$, we begin by running the neural network from $x$$x$ to $\hat{y}$$\hat y$ and storing the intermediate values. This is called the "forward pass".

Layer 1 (two units):

Layer 2 (one unit / output):

Loss:

We define the following shorthand for the partial derivative of the loss with respect to the pre-activation of unit $i$$i$ in layer $l$$l$:

The $\delta$$\delta$ are called "error terms" and measure how much the loss would change if you nudged the corresponding pre-activations a bit. We can now calculate the gradient of the loss function by backpropagation via the chain rule.

Step 1: Top derivative

Step 2: Through the ReLU

Step 3: Gradients for layer-2 weights $w^{(2)}$$w^{(2)}$

Step 4: Send error to hidden activations

Step 5: Through hidden ReLUs to pre-activations

Step 6: Gradients for layer-1 weights $w^{(1)}$$w^{(1)}$

Deep Networks

Many applications today use neural networks that are thousands of units wide and hundreds of layers deep. We now show the general form of the feed-forward and back-propagation calculations for a depth-$L$$L$ fully connected ReLU network of width $m$$m$ at every layer.

Forward pass (any $L$$L$, width $m$$m$):

For each layer $l=1,\dots ,L$$l=1,\dots,L$ and unit $i=1,\dots ,m$$i=1,\dots,m$:

Output and loss:

Backward pass (any $L$$L$, width $m$$m$):

Top layer errors:

Hidden layers $l=L-1,\dots ,1$$l=L-1,\dots,1$:

Gradients with respect to weights (including the bias weights $j=0$$j=0$):

We have been using $\ell$$\ell$ to represent the loss on a particular training instance. We use ${\mathcal{L}}_{\text{mean}}$$\mathcal{L}_\text{mean}$ to represent the mean average loss over the entire training set. The mean loss is more useful than the total loss because it does not depend upon the size of the data set and its gradient is in the same direction as that of the total loss.

We make one small change in the regularization function by not including the weights on the constant 1 dummy inputs - that is, the bias weights. This is because the purpose of regularization is to push the network toward sparsity by having many zero weights on connections between neurons. Thus, we write:

The order of the partial derivatives in the gradient follows the order of weights in the vector $W$$W$. So, where

the gradient is

Although we represented the gradient as a single long vector, in machine learning it is common to organize it as a set of 2-dimensional matrices, one per layer, because the width of network can vary by layer. Thus you will see expressions like the following, where each $G^{(l)}$$G^{(l)}$ is gradient of one layer of weights.

Jacobian Notation

In the previous section, we used only basic calculus and linear algebra notation. We can more compactly represent the gradient by using an operator named the Jacobian that combines notions from calculus and linear algebra. For a vector-valued function $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$$f:\mathbb{R}^n\to\mathbb{R}^m$ with components $f(x)=(f_1(x),\dots ,f_m(x){)}^{\mathrm{\top }}$$f(x)=\big(f_1(x),\dots,f_m(x)\big)^\top$, the Jacobian at $x$$x$ is the $m\times n$$m\times n$ matrix:

In a neural network, the weights at layer $l$$l$ are naturally organized as a matrix $W^{(l)}$$W^{(l)}$. If we collect all entries of all layer weight matrices into a single long vector, we get the stacked parameter vector

where $\mathrm{vec}(\cdot )$$\operatorname{vec}(\cdot)$ stacks all entries, and $P$$P$ is the total number of scalar weights in the network.

Let the dataset loss be $\mathcal{L}:{\mathbb{R}}^P\to \mathbb{R}$$\mathcal{L}:\mathbb{R}^P\to\mathbb{R}$. Its Jacobian with respect to the stacked weights $W$$W$ is a $1\times P$$1\times P$ row matrix:

The gradient vector is then the transpose of that row:

We next want to calculte the mean loss over the dataset. Since $\mathcal{L}(W)=\frac{1}{|D|}\sum _{t=1}^{|D|}{\ell }_t(W)$$\mathcal{L}(W)=\tfrac{1}{|D|}\sum_{t=1}^{|D|}\ell_t(W)$, then Jacobians add linearly:

Now we come to the chain rule in Jacobian form. Let $\varphi$$\phi$ be the final scalar loss function that takes the network's output and compares it to the target label; for L2 loss, $\varphi (\hat{y},y)=||\hat{y}-y|{|}_2^2$$\phi(\hat y,y) = || \hat y - y ||^2_2$. For a composition $\mathcal{L}=\varphi \circ a^{(L)}\circ \cdots \circ a^{(1)}$$\mathcal{L}=\phi\!\circ\!a^{(L)}\!\circ\cdots\!\circ a^{(1)}$ depending on $W$$W$,

Other Kinds of Units and Layers

Several other kinds of units and layers are used in deep neural networks.

Softmax

Softmax takes a vector of pre-activations as input, computes their exponentials, and then normalizes them so they sum to one. The result has several interesting properties. First, if one of the inputs is much larger than the others, the corresponding output is near 1 and the others are near 0. Softmax is thus a relation of the argmax operator. Second, the output can be viewed as probability distribution. For example, if the network is being used to classify inputs and each of the inputs to the softmax is a score computed for a particular label, then the output can be interpreted as the probability that the corresponding label is the correct one.

Suppose the input to a softmax layer is $x\in {\mathbb{R}}^d$$x \in \mathbb{R}^d$, and the weight matrix is

The pre-activation vector is

The softmax output is the vector $a=\sigma (z)\in {\mathbb{R}}^m$$a = \sigma(z) \in \mathbb{R}^m$, with components

This ensures $a_i>0$$a_i > 0$ for all $i$$i$ and $\sum _{i=1}^m{a}_i=1$$\sum_{i=1}^m a_i = 1$.

Now we consider the derivative of softmax. If $i=j$$i = j$:

If $i\ne j$$i \neq j$:

Convolution and Weight Sharing

A key operation in applications of neural networks to computer vision is convolution. A 2-D convolution takes a small filter (also called a kernel) and slides it across an input grid, such as an image. At each position, the filter values are multiplied with the overlapping input values and summed together, producing a single number in the output grid. Repeating this process across all positions produces a new 2-D array where each entry reflects how strongly that local region of the input “matches” the filter. In short: A 2-D convolution is a way of scanning a small pattern across an image to detect features like edges, corners, or textures, turning local structure in the input into structured signals in the output.

As you read the previous paragraph, you will likely be puzzled by the idea of a filter "sliding" across an image. Neurons are simply wired from one to another in a fixed pattern (even if the weights change) and cannot slide connections from one neuron to another. Sliding is a metaphor for weight sharing, where we deliberately reuse the same parameter values across multiple connections instead of learning a separate weight for each one. In other words, different parts of the network are “tied together” so they use the same weights. Thus there are many instances of the filter implemented by different neurons across the 2-D image array, each separated by a few pixels (a quantiity called the stride). All these instances, however, use the same values for their weights.

Let the input be an image

and let the convolution kernel (shared weights) be

The convolution output at spatial position $(u,v)$$(u,v)$ is

Here, the same kernel weights $w_{i,j}$$w_{i,j}$ are reused at every location $(u,v)$$(u,v)$. This is weight sharing: the filter $\mathcal{F}$$\mathcal{F}$ detects the same pattern (for example, an edge) regardless of where it appears in the image.

Pooling Layers

Convolution layers are often used in conjunction with pooling layers, also called downsampling layers. While a filter activates at the position in the image where it matches, a pooling layer determines if a filter activates anywhere is a rectangular region of the image of a specified size. For example, you might have a high-level filter that detects cats, and you want to know if a cat appears anywhere in the image.

Let the input feature map be

Choose a pooling window of size $r\times s$$r \times s$ and a stride $t$$t$. The max pooling output is

Each entry is defined as

Mini-Batches, Cross-Entropy, and Dropout

The three concepts in this section title are crucial for making it practical to train neural networks. The formalization of gradient descent presented above computed the gradient across the entire training set for each weight update. This would be too slow if there were thousands of training instances. The idea of mini-batches (or just batches) is to update the weights after a given number of instances are processed during an epoch. The batch size is often chosen to be 128, so small enough for efficient processing, but large enough to prevent the update from being swayed by a few anomolous data points.

The second crucial concept is using cross-entropy rather than the L2 norm to measure the loss. The network is trying to classify the input, that is, assign one of 10 labels to it. Given a predicted probability distribution over the outputs (e.g. from a softmax layer)

and a true one-hot encoded label vector

the cross-entropy loss for a single example is defined as

For one-hot targets this simplifies to

where $c$$c$ is the index of the correct class. In $n$$n$-way classification problems, cross-entropy leads to faster convergence than L2 loss because it optimizes the log-probability of the true class directly and provides stronger corrective gradients when the model is wrong or uncertain.

The third concept is drop-out. Dropout sets a random fraction of the activations to zero during a training epoch. Dropout is a kind of regularization because it reduces overfitting: it forces neurons to learn more robust, distributed representations by randomly removing them during training, effectively ensembling many models into one.

As an example of these concepts in practice, here is a complete Python program for recognizing handwritten digits. The dataset, MNIST, was used in one of the first successful neural network programs, LeNet-5, created in 1998 by Yann LeCun. MNIST is still a starter baseline for work in machine learning and is included in PyTorch.

xxxxxxxxxx
# mnist_cnn_with_dropout.py
import torch
import torch.nn as nn
import torch.optim as optim
from torchvision import datasets, transforms
from torch.utils.data import DataLoader

# Use GPU if available
device = torch.device("cuda" if torch.cuda.is_available() else "cpu")

# ------------------------
# Data: MNIST
# ------------------------
# Transform: convert to tensor + normalize with dataset mean/std
transform = transforms.Compose([
    transforms.ToTensor(),
    transforms.Normalize((0.1307,), (0.3081,))
])

# Train and test datasets
train_set = datasets.MNIST(root="./data", train=True, download=True, transform=transform)
test_set  = datasets.MNIST(root="./data", train=False, download=True, transform=transform)

# Dataloaders
train_loader = DataLoader(train_set, batch_size=128, shuffle=True)
test_loader  = DataLoader(test_set,  batch_size=256, shuffle=False)

# ------------------------
# Model: small CNN
# ------------------------
class SmallCNN(nn.Module):
    def __init__(self, num_classes=10):
        super().__init__()
        self.classifier = nn.Sequential(
            nn.Conv2d(1, 32, kernel_size=3, padding=1),  # Conv layer (28x28 -> 28x28)
            nn.ReLU(inplace=True),
            nn.MaxPool2d(2),                             # Pool (28x28 -> 14x14)

            nn.Conv2d(32, 64, kernel_size=3, padding=1), # Conv (14x14 -> 14x14)
            nn.ReLU(inplace=True),
            nn.MaxPool2d(2),                             # Pool (14x14 -> 7x7)

            nn.Flatten(),                                # Flatten to vector
            nn.Linear(64 * 7 * 7, 128),                  # Fully connected layer
            nn.ReLU(inplace=True),
            nn.Dropout(0.3),                             # Dropout regularization
            nn.Linear(128, num_classes)                  # Output logits (10 classes)
        )

    def forward(self, x):
        y = self.classifier(x)
        return y

# Instantiate model
model = SmallCNN().to(device)

# Loss function: CrossEntropyLoss combines softmax + negative log-likelihood
criterion = nn.CrossEntropyLoss()

# Optimizer: Adam with learning rate 1e-3.  
# L2 regularization is set by the weight_decay parameter.
optimizer = optim.Adam(model.parameters(), lr=1e-3, weight_decay=1e-4)

# ------------------------
# Training loop
# ------------------------
for epoch in range(5):  # Train for 5 epochs
    # Put Pytorch into training mode
    model.train()
    
    running_loss, running_correct, running_total = 0.0, 0, 0
    # Loop over the training instances
    for images, targets in train_loader:
        images, targets = images.to(device), targets.to(device)

        optimizer.zero_grad(set_to_none=True)          # Reset gradients
        logits = model(images)                         # Forward pass
        loss = criterion(logits, targets)              # Compute loss
        loss.backward()                                # Backprop
        optimizer.step()                               # Update weights

        # Accumulate stats over this epoch
        running_loss += loss.item() * targets.size(0)
        running_correct += (logits.argmax(1) == targets).sum().item()
        running_total += targets.size(0)

    # final stats for this epoch
    train_loss = running_loss / running_total
    train_acc = running_correct / running_total

    # ------------------------
    # Evaluation
    # ------------------------
    # Put PyTorch in evaluation mode
    model.eval()
    test_loss, test_correct, test_total = 0.0, 0, 0
    with torch.no_grad():
        for images, targets in test_loader:  # compute loss over the test data
            images, targets = images.to(device), targets.to(device)
            logits = model(images)
            loss = criterion(logits, targets)

            test_loss += loss.item() * targets.size(0)
            test_correct += (logits.argmax(1) == targets).sum().item()
            test_total += targets.size(0)

    print(f"Epoch {epoch+1}/5 | "
          f"train loss {train_loss:.4f} acc {train_acc:.4f} | "
          f"test loss {test_loss/test_total:.4f} acc {test_correct/test_total:.4f}")

What Else?

Understanding the concepts presented in this tutorial should give you a good foundation for reading papers and building applications with neural networks. The most important concepts not covered here that you should learn about are:

1. Neural methods for natural language processing: how to convert words to real-number vectors in a manner that captures word meaning. Once so converted, a neural network architecture called the transformer can handle a wide range of language tasks - and might even be the basis for artificial general intelligence.

2. Unsupervised learning: how to learn when there are no labels by discovering regularities in raw data.

3. Reinforcement learning: learning how to act in a world on the basis of receiving rewards that are delayed in time from when the system must begin to act.

4. Non-neural net methods of machine learning. For many practical problems, neural networks are overkill and require too much data. Important other methods are regression and its variants, decision trees, nearest-neighbor clustering, and what are called support vector machines (SVMs). Until deep neural networks became practical by using GPUs, SVMs were the most powerful form of machine learning - and their theory also involves much calculus and linear algebra.