CMU Introduction To Deep Learning 11-785, Fall 2026: Lecture 2

Overview

The lecture develops what multilayer perceptrons (MLPs) can represent and how representational efficiency depends on depth, width, and activation functions. It shows that shallow MLPs can express any Boolean function or approximate arbitrary classifiers and real-valued functions, but may need exponentially or infinitely many neurons; deeper networks can often achieve the same task with far fewer units, provided their layers preserve enough information.

Key takeaways

A one-hidden-layer MLP can compute any Boolean function by assigning hidden units to DNF clauses, but worst-case width can grow as 2^(n-1) for n inputs.
Parity illustrates the depth-width tradeoff: a shallow network may need exponentially many units, while a layered XOR tree uses linearly many perceptrons and about 2 log₂(n) layers.
A threshold perceptron implements a linear decision boundary, so one unit cannot classify XOR's alternating input cases; combining units creates the multiple boundaries XOR requires.
One-hidden-layer MLPs can approximate arbitrary real-valued functions and complex decision regions to arbitrary precision, but some constructions require infinitely many units for exact representation.
Depth does not eliminate capacity requirements: a narrow threshold layer can erase input-location information that later layers cannot reconstruct.
Graded activations preserve more information than binary threshold outputs; leaky ReLU retains signal on both sides of a boundary, while sigmoid outputs eventually saturate.

Chapters

0:00 Perceptrons: Weighted Inputs, Bias, and Activation Functions

A perceptron computes a weighted sum of its inputs and compares the result with a threshold to produce an output.
Writing the threshold as a bias gives an affine function, which can be followed by a step activation.
Sigmoid, tanh, ReLU, and softplus are alternative activations; the lecture uses threshold activations to build intuition.

8:00 How MLPs Differ from Individual Neurons

A multilayer perceptron connects perceptrons so that one unit's output becomes another unit's input.
The lecture distinguishes affine functions, which can include a bias, from linear functions that pass through the origin.
A single perceptron can represent Boolean gates such as AND and OR, but cannot represent every Boolean function.

11:00 Defining Network Depth with Directed Paths

A neural network is treated as a directed graph with source nodes at the inputs and sink nodes at the outputs.
Graph depth is the length of the longest path from a source to a sink, not the length of a shorter available route.
A network with paths of lengths one and two has depth two.

14:00 Layers Are Grouped by Longest-Path Distance

Neurons belong to the same layer when they have the same longest-path distance from the inputs.
The illustrated network has four layers: red, green, yellow, and blue neurons at depths one through four.
The input nodes are not counted as a network layer in the lecture's convention.

18:00 Perceptrons as Boolean Pattern Detectors and Majority Gates

Weights of +1 for required one-bits and -1 for required zero-bits let one perceptron fire for a chosen input pattern.
Setting all weights to one and the threshold to k implements a gate that fires when at least k inputs are one.
A single perceptron can therefore compute majority functions, which may require exponentially large circuits built from standard Boolean gates.

25:00 Why XOR Requires a Network of Perceptrons

A single perceptron creates one linear decision boundary, so it cannot separate the alternating positive and negative cases of two-input XOR.
Combining hidden perceptrons makes XOR representable; the lecture shows constructions using either two or three perceptrons.
Connecting perceptrons into an MLP makes it possible to compute Boolean functions that one unit alone cannot represent.

28:00 One Hidden Layer Computes Any Boolean Function

A Boolean function can be represented by listing the truth-table rows for which its output is one.
Disjunctive normal form (DNF) expresses each such row as an AND clause, then ORs the clauses together.
A hidden perceptron can detect each clause and an output perceptron can OR their results, making a one-hidden-layer MLP universal for Boolean functions.

31:00 Karnaugh Maps Reveal the Width Cost of Shallow Networks

Karnaugh maps arrange truth-table inputs so adjacent cells differ in one bit, allowing neighboring one-cases to be grouped into simpler DNF clauses.
The lecture's four-input checkerboard example cannot be grouped and needs eight hidden clauses, plus an output unit.
In the worst case, a one-hidden-layer network may require up to 2^(n-1) hidden perceptrons for n Boolean inputs.

39:00 Parity Shows How Depth Reduces Boolean Network Size

The checkerboard pattern is parity: flipping any one input bit flips the output.
A shallow DNF for parity can require exponentially many units, while chaining two-input XOR computations uses a number of perceptrons linear in the input count.
For n inputs, the lecture gives an XOR construction using roughly 2(n-1) to 3(n-1) perceptrons, depending on the XOR implementation.

46:00 XOR Trees Trade Network Depth Against Width

Because XOR is associative, inputs can be paired in a tree, reducing the number of remaining values by half at each stage.
The lecture estimates a depth of 2 log₂(n) layers when each two-input XOR block uses two layers.
Truncating the tree early forces the remaining layer to compute parity over many inputs directly, requiring exponentially more width.

52:00 Threshold Perceptrons as Linear Classifiers

For real-valued inputs, a threshold perceptron divides the input space with a hyperplane defined by its weighted sum and bias.
Moving the bias shifts the boundary and can change a two-input gate from OR to AND.
An XOR classifier needs two separating boundaries, explaining geometrically why one perceptron cannot implement it.

57:30 Shallow Classifiers Approximate Complex Boundaries with Many Regions

Multiple perceptrons can define polygonal regions: one unit detects each boundary, and a final threshold unit combines their outputs.
For a polygon with increasingly many sides, the lecture examines how the summed hidden-unit outputs form narrower regions around the target shape.
A one-hidden-layer threshold network may need infinitely many units to represent some curved or disconnected boundaries exactly, though it can approximate them with increasingly fine constructions.

1:08:00 Deep Networks Reuse Boundaries to Reduce Classifier Size

The lecture compares a complex pattern built from 16 lines and 40 highlighted regions with a two-hidden-layer construction of roughly 57 neurons.
Recognizing the pattern as parity allows a deeper construction with fewer units, including a two-neuron XOR implementation.
For the more complex 64-line example, the lecture contrasts hundreds of units in a direct construction with a substantially smaller layered XOR network.

1:12:00 One-Hidden-Layer MLPs Approximate Real-Valued Functions

For a scalar input, two threshold units and output weights of +1 and -1 create a pulse active between two thresholds.
Combining many such pulses gives a piecewise-flat approximation to a one-dimensional function.
In higher dimensions, analogous cylinder-shaped regions can approximate a function to arbitrary precision, but a finite network does not necessarily represent it exactly.

1:15:00 Layer Width and Graded Activations Preserve Useful Information

A narrow first layer with threshold activations can discard position information by reporting only which side of each boundary an input occupies.
Later layers cannot recover details that the first layer erased, so every layer needs enough capacity to preserve information relevant to the target function.
Sigmoid, ReLU, and leaky ReLU provide graded outputs rather than binary gates; leaky ReLU also retains information on the negative side of its boundary.

1:20:30 Lecture Takeaways and the Transition to Training

MLPs are universal Boolean function computers, classifiers, and function approximators, but shallow universal networks can be extremely large.
Greater depth can reduce the number of neurons needed, while adequate width and information-preserving activations remain necessary.
The next lecture will address how to train an MLP to model a particular function.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Carnegie Mellon University Deep Learning.