CS 188 Introduction to Artificial Intelligence

Spring 2023 Note 25

These lecture notes are based on notes originally written by Nikhil Sharma and on the textbook Artificial
Intelligence: A Modern Approach.
Last updated: January 15, 2023

Neural Networks: Motivation

In what follows we will introduce the concept of a neural network. In doing so, we will be using some of
the modeling techniques we developed for the binary logistic and multi-class logistic regression.

Non-linear Separators
We know how to construct a model that learns a linear boundary for binary classification tasks. This is a
powerful technique, and one that works well when the underlying optimal decision boundary is itself linear.
However, many practical problems involve the need for decision boundaries that are nonlinear in nature, and
our linear perceptron model isn’t expressive enough to capture this relationship.
Consider the following set of data:

We would like to separate the two colors, and clearly there is no way this can be done in a single dimension
(a single dimensional decision boundary would be a point, separating the axis into two regions).
To fix this problem, we can add additional (potentially nonlinear) features to construct a decision boundary
from. Consider the same dataset with the addition of x2 as a feature:

With this additional piece of information, we are now able to construct a linear separator in the two di-
mensional space containing the points. In this case, we were able to fix the problem by mapping our data
to a higher dimensional space by manually adding useful features to data points. However, in many high-
dimensional problems, such as image classification, manually selecting features that are useful is a tedious
problem. This requires domain-specific effort and expertise, and works against the goal of generalization
across tasks. A natural desire is to learn these featurization or transformation functions as well, perhaps
using a nonlinear function class that is capable of representing a wider variety of functions.

CS 188, Spring 2023, Note 25 1

Multi-layer Perceptron
Let’s examine how we can derive a more complex function from our original perceptron architecture. Con-
sider the following setup, a two-layer perceptron, which is a perceptron that takes as input the outputs of
another perceptron.

In fact, we can generalize this to an N-layer perceptron:

With this additional structure and weights, we can express a much wider set of functions.
By increasing the complexity of our model, we in turn greatly increase its expressive power. Multi-layer
perceptrons give us a generic way to represent a much wider set of functions. In fact, a multi-layer percep-
tron is a universal function approximator and can represent any real function, leaving us only with the
problem of selecting the best set of weights to parameterize our network. This is formally stated below:

Theorem. (Universal Function Approximators) A two-layer neural network with a sufficient number
of neurons can approximate any continuous function to any desired accuracy.

CS 188, Spring 2023, Note 25 2

Measuring Accuracy
The accuracy of the binary perceptron after making n predictions can be expressed as:
1 n
l acc (w
w) = ∑ (sgn(ww · f(xi )) == yi )
n i=1
where xi is data point i, w is our weight vector, f is our function that derives a feature vector from a raw data
point, and yi is the actual class label of xi . In this context, sgn(x) represents an indicator function, which
evaluates to −1 when x is negative, and 1 when x is positive. Taking this notation into account, we can note
that our accuracy function above is equivalent to dividing the total number of correct predictions by the raw
total number of predictions.
Sometimes, we want an output that is more expressive than a binary label. It then becomes useful to produce
a probability for each of the N classes we want to classify into, which reflects our a degree of certainty
that the data point belongs to each of the possible classes. To do so, as we did in the multi-class logistic
regression case, we transition from storing a single weight vector to storing a weight vector for each class
j, and estimate probabilities with the softmax function. The softmax function defines the probability of
classifying x(i) to class j as:
T
ef(xi ) w j
σ (xi ) j = N f(x )T w = P(yi = j|f(xi ); w).
∑ℓ=1 e i ℓ
Given a vector that is output by our function f , softmax performs normalization to output a probability
distribution. To come up with a general loss function for our models, we can use this probability distribution
to generate an expression for the likelihood of a set of weights:
n
w) = ∏ P(yi |f(xi ); w).
ℓ(w
i=1

This expression denotes the likelihood of a particular set of weights explaining the observed labels and data
points. We would like to find the set of weights that maximizes this quantity. This is identical to finding the
maximum of the log-likelihood expression (since log is a monotone function, the maximizer of one will be
the maximizer of the other):
n n
w) = log ∏ P(yi |xi ; w ) = ∑ log P(yi |f(xi ); w).
log ℓ(w
i=1 i=1

Depending on the application, the formulation as a sum of log probabilities may be more useful. In the
case where the log-likelihood is differentiable with respect to the weights, we can optimize it using gradient
ascent.

Multi-layer Feedforward Neural Networks

We now introduce the idea of an (artificial) neural network. This is much like the multi-layer perceptron,
however, we choose a different non-linearity to apply after the individual perceptron nodes. Note that it
is these added non-linearities that makes the network as a whole non-linear and more expressive (without
them, a multi-layer perceptron would simply be a composition of linear functions and hence also linear). In
the case of a multi-layer perceptron, we chose a step function:
(
1 if x ≥ 0
f (x) =
−1 otherwise
Let’s take a look at its graph:
CS 188, Spring 2023, Note 25 3
 1

0.5

−0.5

−1
−2 −1 0 1 2

This is difficult to optimize for a number of reasons. Firstly, it is not continuous, and secondly, it has a
derivative of zero at all points. Intuitively, this means that we cannot know in which direction to look for a
local minima of the function, which makes it difficult to minimize loss in a smooth way.
Instead of using a step function like above, a better solution is to select a continuous function. We have
many options for such a function, including the sigmoid function (named for the Greek σ or ’s’ as it looks
like an ’s’) as well as the rectified linear unit (ReLU). Let’s look at their definitions and graphs below:
1
Sigmoid: σ (x) = 1+e−x

0.8

0.6

0.4

0.2

0
−10 −5 0 5 10
(
0 if x < 0
ReLU: f (x) =
x if x ≥ 0

CS 188, Spring 2023, Note 25 4

 2

1.5

0.5

0
−2 −1 0 1 2

Calculating the output of a multi-layer perceptron is done as before, with the difference that at the output
of each layer we now apply one of our new non-linearities (chosen as part of the architecture for the neural
network) instead of the initial indicator function. In practice, the choice of nonlinearity is a design choice
that typically requires some experimentation to select a good one for each individual use case.

Loss Functions and Multivariate Optimization

Now we have a sense of how a feed-forward neural network is constructed and makes its predictions, we
would like to develop a way to train it, iteratively improving its accuracy, similarly to how we did in the
case of the perceptron. In order to do so, we will need to be able to measure their performance. Returning
to our log-likelihood function that we wanted to maximize, we can derive an intuitive algorithm to optimize
our weights given that our function is differentiable.
To maximize our log-likelihood function, we differentiate it to obtain a gradient vector consisting of its
partial derivatives for each parameter:
 
∂ ℓℓ(w) ∂ ℓℓ(w)
∇w ℓ(w) = , ..., .
∂ w1 ∂ wn

Now we can find the optimal values of the parameters using the gradient ascent method described earlier.
Given that the datasets are usually large, batch gradient ascent is the most popular variation of gradient
ascent in neural network optimization.

Neural Networks: Backpropagation

To efficiently calculate the gradients for each parameter in a neural network, we will use an algorithm known
as backpropagation. Backpropagation represents the neural network as a dependency graph of operators
and operands, called a computational graph, such as the one shown below:
The graph structure allows us to efficiently compute both the network’s error (loss) on input data, as well as
the gradients of each parameter with respect to the loss. These gradients can be used in gradient descent to
adjust the network’s parameters and minimize the loss on the training data.

CS 188, Spring 2023, Note 25 5

 x
2

g f
+ ∗

y
3

z
4

The Chain Rule

The chain rule is the fundamental rule from calculus which both motivates the usage of computation graphs
and allows for a computationally feasible backpropagation algorithm. Mathematically, it states that for a
variable f which is a function of n variables x1 , . . . , xn and each xi is a function of m variables t1 , . . . ,tm , then
we can compute the derivative of f with respect to any ti as follows:

∂f ∂ f ∂ x1 ∂ f ∂ x2 ∂ f ∂ xn
= · + · +...+ · .
∂ti ∂ x1 ∂ti ∂ x2 ∂ti ∂ xn ∂ti
In the context of computation graphs, this means that to compute the gradient of a given node ti with respect
to the output f , we take a sum of children(ti ) terms.

The Backpropagation Algorithm

x
2 2→
←4
g f
5→ ∗ 20→
+
←4 ←1
y 3→
←4
3
← →
4
5

z
4

Figure 1: A computation graph for computing (x + y) ∗ z with the values x = 2, y = 3, z = 4.

Figure 1 shows an example computation graph for computing (x + y) ∗ z with the values x = 2, y = 3, z = 4.

CS 188, Spring 2023, Note 25 6

We will write g = x + y and f = g ∗ z. Values in green are the outputs of each node, which we compute in
the forward pass, where we apply each node’s operation to its input values coming from its parent nodes.
Values in red after each node give gradients of the function computed by the graph, which are computed in
the backward pass: the value after each node is the partial derivative of the last node f value with respect
to the variable at that node. For example, the red value 4 after g is ∂∂ gf , and the red value 4 after x is ∂∂ xf . In
our simple example, f is just a multiplication node which outputs the product of its two input operands, but
in a real neural network the final node will usually compute the loss value that we are trying to minimize.
The backward pass computes gradients by starting at the final node (which has a gradient of 1 since ∂∂ ff = 1)
and passing and updating gradients backward through the graph. Intuitively, each node’s gradient measures
how much a change in that node’s value contributes to a change in the final node’s value. This will be the
product of how much the node contributes to a change in its child node, with how much the child node con-
tributes to a change in the final node. Each node receives and combines gradients from its children, updates
this combined gradient based on the node’s inputs and the node’s operation, and then passes the updated
gradient backward to its parents. Computation graphs are a great way to visualize repeated application of
the chain rule from calculus, as this process is required for backpropagation in neural networks.
Our goal during backpropagation is to determine the gradient of output with respect to each of the inputs.
As you can see in Figure 1, in this case we want to compute the gradients ∂∂ xf , ∂∂ yf , and ∂∂ zf :

∂f
1. Since f is our final node, it has gradient ∂ f = 1. Then we compute the gradients for its children, g
∂f
and z. We have ∂g = ∂
∂ g (g · z) = z = 4, and ∂∂ zf = ∂∂z (g · z) = g = 5.
2. Now we can move on upstream to compute the gradients of x and y. For these, we’ll use the chain
rule and reuse the gradient we just computed for g, ∂∂ gf .
∂f ∂ f ∂g
3. For x, we have ∂x = ∂g ∂x by the chain rule – the product of the gradient coming from g with the
partial derivative for x at this node. We have ∂∂ gx = ∂∂x (x + y) = ∂∂x x + ∂∂x y = 1 + 0, so ∂∂ xf = 4 · 1 = 4.
Intuitively, the amount that a change in x contributes to a change in f is the product of the amount that
a change in g contributes to a change in f , with the amount that a change in x contributes to one in g.
4. The process for computing the gradient of the output with respect to y is almost identical. For y
we have ∂∂ yf = ∂∂ gf ∂∂ gy by the chain rule – the product of the gradient coming from g with the partial
∂g ∂ ∂ ∂ ∂f
derivative for y at this node. We have ∂y = ∂ y (x + y) = ∂yx + ∂yy = 0 + 1, so ∂y = 4 · 1 = 4.

Since the backward pass step for a node in general depends on the node’s inputs (which are computed in the
forward pass), and gradients computed “downstream” of the current node by the node’s children (computed
earlier in the backward pass), we cache all of these values in the graph for efficiency. Taken together, the
forward and backward pass over the graph make up the backpropagation algorithm.
For an example of applying the chain rule for a node with multiple children, consider the graph in Figure 2,
representing ((x + y) + (x · y)) · z, with x = 2, y = 3, z = 4. x and y are each used in 2 operations, and so each
has two children. By the chain rule, their gradient values are the sum of the gradients computed for them
by their children (i.e. gradient values add at path junctions). For example, to compute the gradient for x, we
have
∂f ∂ f ∂h ∂ f ∂i
= + = 4 · 1 + 4 · 3 = 4 + 12 = 16.
∂x ∂h ∂x ∂i ∂x
Now that we have a method for computing gradients for all parameters of the network, we can use gradient
descent methods to optimize the parameters to get high accuracy on our training data. For example, suppose

CS 188, Spring 2023, Note 25 7

 x h
2→ +
2 ←16 ←4

5→ 4
g f

←4
←
+ 11→ ∗ 44→
←4 ←1

←1

← →
y

6
4
i

2
3→

← →
3 ∗

11
z

4
←12 ←8
4

Figure 2: A computation graph for computing ((x + y) + (x · y)) · z, with x = 2, y = 3, z = 4.

we have designed some classification network to output probabilities of classes y for data points x, and have
m different training data points (see the Measuring Accuracy section for more on this). Let w be all the
parameters of our network. We want to find values for the parameters w that maximize the likelihood of the
true class probabilities for our data, so we have the following function to run gradient ascent on:
m m
ℓℓ(w) = log ∏ P(y(i) | x(i) ; w) = ∑ log P(y(i) | x(i) ; w)
i=1 i=1

where x(1) , . . . , x(m) are the m data points in our training set.
To minimize the negative of log-likelihood is, at each iteration of gradient descent, we use the data points
x(1) , . . . , x(m) to compute gradients for the parameters w, update the parameters, and repeat until the param-
eters converge (at which point we’ve reached a local minimum of the function).
Neural networks are powerful (and universal!) function approximators, but can be difficult to design and
train. There’s a lot of ongoing research in deep learning focusing on various aspects of neural network
design such as:

1. Network Architectures - designing a network (choosing activation functions, number of layers, etc.)
that’s a good fit for a particular problem
2. Learning Algorithms - how to find parameters that achieve a low value of the loss function, a difficult
problem since gradient descent is a greedy algorithm and neural nets can have many local optima
3. Generalization and Transfer Learning - since neural nets have many parameters, it’s often easy to
overfit training data - how do you guarantee that they also have low loss on testing data you haven’t
seen before?

Summary
In this note, we introduced logistic regression and its close variant, multiclass logistic regression.
We also examined how to solve optimization problems using gradient methods.
Combining these concepts, we come to the idea of neural networks, which are essentially multi-layer per-
ceptrons with nonlinear activations between. These networks are extremely powerful for approximating
functions, and are trained using gradient descent.

CS 188, Spring 2023, Note 25 8