# CS 462 - Lecture 04

## Deep Networks

Bernhard Firner

2026-02-03

---

## Reading

* Chapter 3 in the book last week, chapters 4 & 7.1-7.4 today

---

## Review

* **Universal Approximation Theorem**
* There is no bound on the complexity we can model with a shallow NN given an arbitrary number of hidden units
  * As long as the curve being modelled is continuous
  * The precision of our fit is arbitrary with the number of hidden units

---

## Capacity Review

* Each elbow in the output allows the model to match part of the target function
  * The network is **memorizing** the slope of the target function in small segments
* Thus, the capacity is a function of the number of **hidden units**

---

## Network Size

* What does it cost to add capacity?
* Each input to a neuron requires a weight, and each neuron has a bias value
  * $w$ hidden units with $n$ inputs require $w(n + 1)$ values
  * The output layer uses 1 bias value plus $w$ weights

---

## Network Size

* Each unit in the hidden layer has 1 weight and 1 bias
* The output layer has 2 weights and 1 bias
* There are a total of 7 parameters, giving the output 3 regions

---

## Network Size

* Each unit in the hidden layer has 1 weight and 1 bias
* The output layer has 3 weights and 1 bias
* There are a total of 10 parameters, giving the output 4 regions

---

## Shallow Network Costs

* With a single input and a single hidden layer, each new elbow "costs" 3 additional values
* There are $w+1$ regions in the network output with a cost of $w(n+1) + (1 + w)$
  * $w$ is the number of hidden units
* Note: I'm using $w$ for the "width" of the network, the book uses $D$ instead

---

## Adding Inputs

* Each unit in the hidden layer has 2 weights and 1 bias
* The output layer has 3 weights and 1 bias
* We can't plot the hidden layer outputs as lines
  * They are hyperplanes now, and the 2 regions per unit are multiplicitive
* There are a total of 13 parameters, and 7 regions

---

<p fontsize="8">See Figure 3.8 in "Understanding Deep Learning"</p>

---

## Capacity Core Concept

* With a single input, each new hidden unit simply adds an elbow to the output line
  * So each additional unit adds 1 new output region
* With two inputs, we are mapping from a 2D space onto a 1D space
* If you remember some linear algebra, you should remember the concept of **orthogonality**

---

## Maximizing Regions

* Imagine we have some dimensions and the same number of hidden units
* The weights of the hidden units form a matrix
  * Set it to the identity (1s in the diagonal)
* Each new dimension partitions the space, doubling the number of regions

---

## Region Growth

* As long as we have as many hidden units as inputs, we get good capacity growth

---

## Problem

* We don't actually have that many input features
  * So how can we take advantage of this growth?
* Solution: make new features

---

## Depth 2 Network

* First hidden layer
  * $h_{11} = a[\theta_{11} + \theta_{12}x]$
  * $h_{12} = a[\theta_{13} + \theta_{14}x]$

</div>
<div class="col">

* Second hidden layer
  * $h_{21} = a[\theta_{21} + \theta_{22}h_{11} + \theta_{23}h_{12}]$
  * $h_{22} = a[\theta_{24} + \theta_{25}h_{11} + \theta_{26}h_{12}]$

</div>
</div>

* Output is $y = \phi_0 + \phi_1h_{21} + \phi_2h_{22}$

-v-

## In Torch

```python
>>> import torch
>>> net = torch.nn.Sequential(torch.nn.Linear(1, 2), torch.nn.ReLU(), torch.nn.Linear(2, 2), torch.nn.ReLU(), torch.nn.Linear(2, 1))
>>> net
Sequential(
  (0): Linear(in_features=1, out_features=2, bias=True)
  (1): ReLU()
  (2): Linear(in_features=2, out_features=2, bias=True)
  (3): ReLU()
  (4): Linear(in_features=2, out_features=1, bias=True)
)
```

-v-

## Torch Parameters

```python
>>> list(net.parameters())
[Parameter containing:
tensor([[ 0.9080],
        [-0.5867]], requires_grad=True), Parameter containing:
tensor([-0.2368,  0.1715], requires_grad=True), Parameter containing:
tensor([[-0.3880, -0.1083],
        [ 0.2117,  0.3026]], requires_grad=True), Parameter containing:
tensor([-0.3903, -0.1561], requires_grad=True), Parameter containing:
tensor([[-0.5150, -0.2760]], requires_grad=True), Parameter containing:
tensor([0.5740], requires_grad=True)]
>>> net[0].weight
Parameter containing:
tensor([[ 0.9080],
        [-0.5867]], requires_grad=True)
>>> net[0].bias
Parameter containing:
tensor([-0.2368,  0.1715], requires_grad=True)
>>> net[2].weight
Parameter containing:
tensor([[-0.3880, -0.1083],
        [ 0.2117,  0.3026]], requires_grad=True)
>>> net[2].bias
Parameter containing:
tensor([-0.3903, -0.1561], requires_grad=True)
>>> net[4].weight
Parameter containing:
tensor([[-0.5150, -0.2760]], requires_grad=True)
>>> net[4].bias
Parameter containing:
tensor([0.5740], requires_grad=True)
```

---

## Depth 2 Regions

* The first hidden layer is unchanged
  * Each one has two regions
  * This is the most we can get out of a ReLU

---

## Depth 2 Regions

* Hidden layer 2 has outputs like an entire single-layer network
  * With 2 inputs, each can have 4 output regions
* We could get as many as 6 elbows in the final output
  * But that isn't guaranteed, and we could model simpler functions

---

## Overparameterization

* It's a big word
* Simply means that we have more parameters than is required
* Because we can always model a simpler function, it doesn't hurt a neural network
  * As long as we've got some type of regularization!

---

## Capacity Growth

* The number of output regions is our measure of **capacity**
* Recall, shallow networks with 1 input and output and w hidden units
  * $w+1$ linear regions from $3w+1$ parameters

---

## Deeper Networks

* A deeper network, with $k$ hidden layers, has faster capacity growth
  * $(w+1)^k$ linear regions
  * Costs $3w + 1 + (k-1)w(w+1)$ parameters
  * Notice that with $k=1$ hidden layers, this is the same as before

---

## Depth Efficiency

* Adding a layer means adding a new weight for each input, plus a bias parameter
  * This is where the $w(w+1)$ part of the equation comes from
* In reality, every layer won't have the same width, but this gives us an easy equation to follow
* Deeper networks are more efficient at adding capacity than shallow networks

---

## Capacity Gains

* K is the depth, D is the width
* Notice that a deeper networks have more regions per parameters
  * This is the **depth efficiency** of neural networks

---

## Deeper Always Better?

* So is a deeper network always better?
  * Is state of the art just DNNs that are 1000s of layers deep?
* There are some limitations
  * Run time
  * Memory
  * Precision

---

## Run Time Constraints

* One problem with a deeper network is that each layer's output depends upon the previous layer
* That means that calculations are sequential
  * Each neuron is a floating point multiplication and addition
  * Is that slow? It could be, especially going backwards

---

## Forward Vs Backward

* When we find the output of a neural network, that is called the **forward pass**
* But recall that we need to calculate the derivative during training
  * That was pretty simple when we had a simple network, but depth adds more steps
* We are going to jump into a bit of chapter 7 to explain

---

## Loss

* Recall that we used MSE as a loss function: $\ell_i = (f[x_i,\phi] - y_i)^2$
* We sum the loss over multiple samples to get: $L[\phi] = \sum_{i=1}^{I}\ell_i$
* But that isn't how we actually learn in a neural network
  * Loss is only calculated over a batch
  * And we update each parameter separately

---

## Parameter Updates

* $\phi_{t+1} \longleftarrow \phi_t - lr\sum_{i \in \mathcal{B}} \frac{\delta \ell_i[\phi_t]}{\delta\phi}$
  * Find the loss due to $\phi_t$
  * Multiply by the learning rate
  * Subtract from $\phi_t$

---

## Backpropagation

* We now have $k$ layers in our network
  * So the output of one layer depends upon the $k-1$ layer
  * And the loss depends upon the next layer, $k+1$
* We will begin calculations at the end and work our way backwards
  * This is called the backpropagation algorithm

---

## Algorithm:

* Group the paramters by layer, the weights and biases from layer $k$ are $\Omega_k$ and $\beta_k$
* Step 1: run each data sample forward, and remember the outputs of each layer
* Step 2: compute the derivatives of the loss with respect to the values saved in the forward pass
* Step 3: compute the derivatives of the loss with respect to the parameters

---

## Example

* Let's just consider a tiny example
  * We'll revisit the model we used for the sin curve
  * Use a shallow network with 3 hidden layers
* How many parameters are in the model?

```python
    net = torch.nn.Sequential(
            torch.nn.Linear(1, 3),
            torch.nn.ReLU(),
            torch.nn.Linear(3, 1))
```

---

## A Note

* We are about to do some math
  * This is the hardest and only real math required for deep learning
* I'm not going to ask you to do this on an exam
  * Because you are just about 100% guaranteed to mess up
  * But I will ask you to remember some important concepts

---

## Parameters

* There are 3 bias values and 3 weights in the first layer
* The last layer has 3 weights and 1 bias
* Let's initialize them so that we start with some kind of output

```python
        net[0].bias[0] = -1
        net[0].bias[1] = 0
        net[0].bias[2] = 1
        net[0].weight[0][0] = 1
        net[0].weight[1][0] = -1
        net[0].weight[2][0] = 1

net[2].bias[0] = 1
        net[2].weight[0][0] = 1
        net[2].weight[0][1] = -1
        net[2].weight[0][2] = 1
```

---

## Forward Pass

* The loss is the mean of the squared errors from *each* point
  * But we will need **all** of the intermediate values
  * Let's start with a single point, $x=0$, $y=1$

---

## Intermediate Values

* We find the intermediate values from the forward pass
* Begin with outputs for the first training point
  * First layer ($f_0$): -1.0,  0.0,  1.0
  * Second layer (relu): 0.0, 0.0, 1.0
  * Third layer ($f_1$): 0
  * The error is $(f_1 - y)^2 = -1^2 = 1$

---

## Backward Pass

* In the first backward pass, we find the loss with respect to those outputs
  * $\frac{\delta\ell}{\delta f_1} = 2(f_1 - y)$
* We apply the **chain rule** over each layer
  * This means that we can solve for derivatives in pieces
  * $\frac{\delta\ell}{\delta relu} = \frac{\delta f_1}{\delta relu} \frac{\delta\ell}{\delta f_1}$
  * $\frac{\delta\ell}{\delta f_0} = \frac{\delta relu}{\delta f_0}\frac{\delta f_1}{\delta relu} \frac{\delta\ell}{\delta f_1}$

---

## With Parameters

* Now we compute derivatives for biases and weights
* Our linear layers are all the same: $f_k = \beta_k + \omega_k h_h$
  * $h_k$ is the input to the hidden layer (or $x$, if this is the first layer)
  * Once again, we use the chain rule

---

## With Parameters

* Chain rule for layer $k$
  * $\frac{\delta\ell}{\delta\beta_k} = \frac{\delta f_k}{\delta\beta_k}\frac{\delta\ell}{\delta f_k}$
  * $\frac{\delta\ell}{\delta\omega_k} = \frac{\delta f_k}{\delta\omega_k}\frac{\delta\ell}{\delta f_k}$
  * We already know the right sides of these equations
* Left sides:
  * $\frac{\delta f_k}{\delta \beta_k} = 1$
  * $\frac{\delta f_k}{\delta \omega_k} = h_k$, where $h_k$ is the input to layer k

---

## relu

* What about the derivative of the ReLU?
  * Just 0 with input < 0, and the input otherwise

---

## Gradients (last layer)

* For the first training point (x=0, y=1):
* $h_1 = [0, 0, 1]$ (the inputs to the third layer)
* $f_1 = 0$
* $\frac{\delta\ell}{\delta f_1} = 2(f_1 - y) = -2$
* $\frac{\delta\ell}{\delta\omega_1} = \frac{\delta f_1}{\delta\omega_1}\frac{\delta\ell}{\delta f_1} = [0, 0, 1]\cdot -2 = [0, 0, -2]$
* $\frac{\delta\ell}{\delta\beta_1} = \frac{\delta f_1}{\delta\beta_1}\frac{\delta\ell}{\delta f_1} = 1 \times -2 = -2$

---

## Gradient Updates

* We can talk about the gradient updates for layers independently
  * The output of the last layer was too small
  * The math tells us to subtract -2 from the bias and from the third weight
    * Subtracting a negative means that we'll be adding 2, scaled by the learning rate

---

## 0 Gradients

* Why don't the first two weights change?
  * Their inputs were 0
  * This is because we are using a ReLU
* Notice that we could get really unlucky, and no learning could take place

---

## Gradients (relu)

* $relu(f_0) = [0, 0, 1]$
* $\frac{\delta\ell}{\delta relu} = \frac{\delta f_1}{\delta relu} \frac{\delta\ell}{\delta f_1}$
  * We already solved $\frac{\delta\ell}{\delta f_1} = -2$ in the last step
* $\frac{\delta \ell}{\delta relu} = \mathbb{I} [f_0 > 0] \odot (\omega_1^T \frac{\delta\ell}{\delta f_1}) = [0\times1, 0\times-1, 1\times-1] \cdot -2 = [0, 0, 2]$
  * $\mathbb{I}[f_0 > 0]$ means 0 when the input is negative, and the input otherwise
  * $\odot$ means point-wise multiplication

---

## Gradients (first layer)

* For the first training point (x=0, y=1):
* $x = [0]$ (the inputs to the first layer)
* $f_0 = [-1, 0, 1]$
* $\frac{\delta\ell}{\delta relu} = [0, 0, 2]$
* $\frac{\delta\ell}{\delta f_0} = \frac{\delta relu}{\delta f_0}\frac{\delta f_1}{\delta relu}\frac{\delta\ell}{\delta f_1} = [0, 0, 2]$
* $\frac{\delta\ell}{\delta\omega_0} = \frac{\delta f_0}{\delta\omega_0}\frac{\delta relu}{\delta f_0}\frac{\delta f_1}{\delta relu}\frac{\delta\ell}{\delta f_1} = x\cdot [0, 0, 2] = [0, 0, 0]$
* $\frac{\delta\ell}{\delta\beta_0} = \frac{\delta f_0}{\delta\beta_0}\frac{\delta relu}{\delta f_0}\frac{\delta f_1}{\delta relu}\frac{\delta\ell}{\delta f_1} = 1\cdot [0, 0, 2] = [0, 0, 2]$

---

## What Does That Mean?

* The weights of the first layer don't change again
  * But now it is because the input was 0
  * Any weight value would have a 0 gradient
* But the bias in the first layer has a gradient

---

## Iteration

* If we actually iterated on just this one point, eventually the first layer would output all 0s and the bias of the last layer would be 1
* This solution would only work for $x=0$, so it is important that we train on multiple points at a time
* Great topics for later!
  * This is getting away from our original point though

---

## Deep Networks

* Notice that we need to store the outputs of every intermediate layer?
  * That takes memory, which puts a practical limitation on the size of networks
* This math turns into linear algebra and is handled by pytorch (or another framework)
  * But there is still a cost during training

-v-

## Gradient Code

* If you want to play around with the gradients, try changing the training data, x

```python
#! /usr/bin/python3

import matplotlib.pyplot as plt
import math
import torch

my_colors = [ '#2E2585', '#337538', '#5DA899', '#94CBEC' ]

torch.random.manual_seed(1)

# Set up x points
x = torch.linspace(0,6,6)

def init_axes(ax):
    ax.set_xlim([0, 6])
    ax.set_ylim([-1.5, 1.5])
    ax.set_xlabel('Input, $x$', fontsize=16)
    ax.set_ylabel('Output, $y$', fontsize=16)

# Plot the training input and the current output
figure, [ax_left, ax_full] = plt.subplots(nrows=1, ncols=2, sharey=True)
figure.set_size_inches(w=12, h=7)

def solveAndPlot(ax_left, ax_full, x):
    num_hidden = 3
    for ax in [ax_left, ax_full]:
        ax.clear()
        init_axes(ax)

ax_left.set_title('Training Points', fontsize=16)
    ax_full.set_title('NN Output', fontsize=16)
    sin_y = torch.sin(0.5*torch.pi + x)

# Make a model
    net = torch.nn.Sequential(
            torch.nn.Linear(1, num_hidden),
            torch.nn.ReLU(),
            torch.nn.Linear(num_hidden, 1))
    # The output isn't normalized, so we'll initialize the bias so that more of
    # the lines are used
    with torch.no_grad():
        net[0].bias[0] = -1
        net[0].bias[1] = 0
        net[0].bias[2] = 1
        net[0].weight[0][0] = 1
        net[0].weight[1][0] = -1
        net[0].weight[2][0] = 1

net[2].bias[0] = 1
        net[2].weight[0][0] = 1
        net[2].weight[0][1] = -1
        net[2].weight[0][2] = -1
    print(f"Parameters are {list(net.parameters())}")

learning_rate = 0.01

# Train the model
    # Convert the data to torch tensors first
    xt = x.reshape(x.size(0), 1).float()
    yt = sin_y.reshape(x.size(0), 1).float()

ax_left.plot(xt, yt, linestyle='solid', alpha=0.5, marker="o", color=my_colors[0], linewidth=0)

loss_fn = torch.nn.MSELoss()
    # Ensure that there are no gradients stored
    net.zero_grad()
    first = net[0](xt)
    second = net[1](first)
    y_hat = net[2](second)
    print(f"first {first}")
    print(f"second {second}")
    print(f"y_hat {y_hat}")
    # This computes the loss
    loss = loss_fn(yt, y_hat)
    print(f"Loss is {loss}")
    # This computes the gradients (derivates of the error w.r.t each parameter)
    loss.backward()
    # Update the parameters
    for param in net.parameters():
        print(f"Grad is {param.grad}")
        param.data -= param.grad * learning_rate
        # Zero the gradient before the next pass
        param.grad = None

ax_full.plot(xt, y_hat.detach().numpy(), linestyle='solid', marker=None, label="fit", color=my_colors[2], linewidth=3)
    ax_full.plot(x, sin_y, linestyle='solid', marker=None, label="target", color=my_colors[3], linewidth=3)
    ax_full.legend(loc='best', fontsize=16)

solveAndPlot(ax_left, ax_full, x)
plt.savefig(f"04_fitting.svg", dpi=2*96)
```

---

## Network Parameters

* We also have to worry about a lack of gradients
  * From the ReLU layer in our example
  * And from another problem, called vanishing gradients
    * Caused when mathematical imprecision makes things get too close to 0
* These are major topics, which we'll get to in time

---

## Deeper Vs Wider

* So we do prefer deeper networks
  * But they come with costs and complications
* Historically, we didn't know how to train deeper networks until recently
  * We'll start looking at some examples soon
  * But first we need to learn how to apply a DNN to a problem