Transcript

CMU Introduction to Deep Learning 11785, Spring 2026: Lecture 2

From Carnegie Mellon University Deep Learning · Episode page · Watch on YouTube

January 14, 2026 · 1 h 24 min · 11,796 words · 96 timestamped sections

This is the full, timestamped transcript of "CMU Introduction to Deep Learning 11785, Spring 2026: Lecture 2", an episode of Carnegie Mellon University Deep Learning published January 14, 2026 (1 h 24 min, about 11,796 words). It mentions 17 people, works and ideas, including Multi-layer Perceptron, Neurons, Activation Function, Decision Boundary, Boolean Functions.

What is discussed, and when

0:00 – 10:00: Neurons, Threshold Logic
10:00 – 20:00: Sigmoid, Neurons, Multi-layer Perceptron, Activation Function
20:00 – 30:00: Neurons, Boolean Functions, Multi-layer Perceptron, Decision Boundary
30:00 – 40:00: Truth Table, Neurons, Multi-layer Perceptron, Boolean Functions
40:00 – 50:00: Neurons
50:00 – 1:00:00: Decision Boundary, Neurons, Boolean Gates, Input Space
1:00:00 – 1:10:00: Neurons, Decision Boundary, Cylinders
1:10:00 – 1:20:00: Neurons, Boolean Functions, Sigmoid, Activation Function
1:20:00 – 1:24:29: Neurons, Activation Function, Boolean Functions, Decision Boundary

Notable quotes from "CMU Introduction to Deep Learning 11785, Spring 2026: Lecture 2"

Neurons themselves are these little units that fire when the combined input exceeds a threshold. And so artificial neural networks are also networks of computational models of…
about Neurons · at 4:43
But instead of having something that jumps so suddenly, I can have something that goes smoother like so. And that is a sigmoid. Now you can see how the sigmoid works. So if z is a very large.
about Sigmoid · at 11:16
And different activation functions will give you different behaviors for the perceptron. But for the moment, we're going to continue to assume a threshold activation because a…
about Activation Function · at 14:02
Now let's continue with this. So now a multi-layer perceptron or an MLP is a network of such perceptrons where the perceptrons receive input from other perceptrons and they feed by other.
about Multi-layer Perceptron · at 16:02
Now we've already seen that MLPS can compose boolean functions. It can operate on boolean inputs and produce boolean outputs like this network to the left. We also saw that networks can compose classifiers, functions that work.
about Boolean Functions · at 22:38
We saw these figures in the last class.
about Boolean Gates · at 24:30
It's a not on a Y. It's ignoring X, right? And now you can see why it cannot capture an XR. An XR actually needs two boundaries because the output is one for these two…
about XOR · at 53:08
Compare this sum to a threshold of five and it's going to capture the pentagon decision boundary. But once you know how to compose a pentagon decision boundary, you can compose…
about Decision Boundary · at 55:33

Who and what is mentioned in this episode?

People

Gerald Freedland — Person · Referenced expert · 4 mentions
Cited as the source of a more compact XOR construction using only two perceptrons, used to illustrate how network design choices can reduce neuron count.
So you get an X or Y. And in fact, this is not the only way to build an NLP to compose an XR. Here's a more compact way that I got from Gerald Freedelland at Berkeley. This…

Concepts & topics

Multi-layer Perceptron — Concept · Core topic · 5 mentions · first at 16:06
Central theme of the episode, discussing the architecture and capabilities of MLPs in neural networks.
Neurons — Concept · Key argument · 51 mentions · first at 2:58
Fundamental units of neural networks, discussed in the context of perceptrons and their computational models.
Activation Function — Concept · Core topic · 3 mentions · first at 13:55
Critical component in perceptrons and neural networks, determining the output of a neuron.
Decision Boundary — Concept · Strategy · 13 mentions · first at 23:48
Discussed in the context of how MLPs can model complex classification boundaries.
Boolean Functions — Concept · Framework · 9 mentions · first at 22:41
Discussed as a type of function that MLPs can model, highlighting their universality in computation.
XOR — Concept · Key argument · 1 mention · first at 28:51
Used as an example to illustrate the limitations of single-layer perceptrons and the need for depth in networks.
Sigmoid — Concept · Framework · 6 mentions · first at 11:23
Discussed as a smoother alternative to threshold activation functions in perceptrons.
Boolean Gates — Concept · Framework · 3 mentions · first at 28:31
Discussed in the context of perceptrons modeling basic boolean operations like AND, OR, and NOT.
Universal Approximation Theorem — Concept · Key argument · 1 mention · first at 23:58
Mentioned in the context of MLPs being able to approximate any function to arbitrary precision.
Again we'll discuss the need for network to be teeth and finally we'll see that MLPs are universal approximators. Give me any input output relationship at all and I can…
Truth Table — Concept · Framework · 6 mentions · first at 32:01
Used to explain how boolean functions can be represented and how MLPs can model them.
Basically just a truth table it takes a number of inputs and computes an output so I can write down a table where I explicitly specify all the input combinations and the…
ReLU — Concept · Framework · 4 mentions
Discussed as a popular activation function in neural networks.
Basically the same as the sigmoine but centered at zero. So it goes from minus1 to one. Or you can have this rectification function where the output of this activ of this…
Cylinders — Concept · Framework · 2 mentions · first at 1:03:52
Used as a metaphor to explain how MLPs can model complex functions by summing scaled and shifted cylinders.
Recalling that a one hidden layer NLP can compose a cylinder that has height n /2 inside and zero outside. And so to compose an arbitrary function in iron dimensions, you can…
Threshold Logic — Concept · Framework · 1 mention · first at 5:44
Discussed in the context of perceptrons implementing threshold-based logic.
Electrical engineering terms, this perceptron is a threshold gate and implements threshold logic. So remember this term, we're going to see it again.
Input Space — Concept · Framework · 1 mention · first at 51:12
Discussed in the context of how MLPs partition and model regions in the input space.
But then once you understand this you can see how it can compute boolean gates. If the input is boolean if you have two boolean inputs the input combinations can be 0 1 0 1 or 1.
Softplus — Concept · Framework · 4 mentions
Mentioned as a smoother version of the ReLU activation function.
Which continues to inform how far you are from the boundary on both sides of the boundary. These are better activations which where the first layer outputs will continue to…
Car Map — Concept · Framework · 2 mentions · first at 35:04
Used as a method to represent and simplify boolean functions.
So okay some folks are some folks are not. Now, a car map is a topological way of representing bit patterns such that bit patterns that differ by only one bit are [clears throat] always arranged next to.

Full transcript with timestamps

1:53 Hello all. Can you hear me? Yes. Okay good. Let's wait a few seconds. Again, as always, uh when in doubt, please either speak up or post a question on chat. I'll only be looking at the chat periodically. So, uh if you post a question on chat, either one of my TAs will reply to you or I will reply but with some delay. Okay, let's begin. So uh can anybody remind me what we discussed in the last class? Anyone?

2:56 What did we discuss? Neurons. History of neural networks, neural networks, perceptrons, NLP. Thank you. Right. So we saw a bit of what neural networks are. We're going to continue with the theme and in this class we're going to see what a network can represent. We'll continue a bit from where we left off. We will discuss what neural networks can represent and the restrictions on their capacity and how these relate to their activation functions and depth and width. So quick recap as we saw in the last class in a great many AI tasks tasks that were previously considered to be solely in the domain of human expertise these have now been successfully taken over by artificial neural networks.

3:46 These include tasks like voice recognition, machine translation, image captioning, intelligence games and pretty much everything that you can think of these days. So what are all these amazing neural networks that do all these great things? In each case, the neural network is a function that takes in some input and produces some output. So an input voice signal produces a transcription. An input image produces a caption. An input game state produces a prediction for the next best move and so on. But what's in these functions?

4:24 If a human were to perform these tasks, these functions were computed by the human brain. And so neural networks mimic the network structure in the brain. And we also saw that the brain in turn is a giant network of neurons where the neurons themselves are these little units that fire when the combined input exceeds a threshold. And so artificial neural networks are also networks of computational models of the neuron which again look like this. And these models of the neuron are what we will call perceptrons. And so again a perceptron is this unit that receives many inputs.

5:11 It has a weight associated with each input. The weight is a real number. So since each input has a corresponding weight, you can compute a weighted sum of all of the inputs. And if the weighted sum exceeds a threshold, then the neuron in the in the simplest case, the neuron, the perceptron outputs a one. And if the weighted sum does not exceed the threshold, it outputs a zero. In electrical electrical engineering terms, this perceptron is a threshold gate and implements threshold logic. So remember this term, we're going to see it again.

5:49 Now let's sort of redo this math a little bit here. Right here, uh, we say that the perceptron computes summation wi. Actually, this color is horrible. Let me get a better color. So it computes summation wi xi, where the x's are the inputs and the w's are the weights. And if this is greater than a threshold t it outputs a one otherwise it outputs a zero. I can rewrite this in this manner right. I can say [clears throat] it computes summation wi x i minus t z equals and if z is greater than zero it outputs a one it outputs a zero otherwise. So, does everybody agree that this thing to the right is the same as the rule to the left? Is everybody with me on this?

7:00 Fairly straightforward, right? But then once I write it like so, I can do it slightly differently. I can say Z equals summation wi XI minus T. And then I can define this operator theta which operates on Z where theta Z equals 1 if Z is greater than equal to 0 and zero otherwise. And so again this comb the combination of these two operations fully defines the perceptron. Yes or no? Do you agree by this? This exactly the same operation as before. So do you agree with this? Yes. No. Okay guys do me a favor. there's a little thumbs up uh or I think it's a thumbs up that you can give on Zoom. So when I ask you a question, you just give me a thumbs up. I'll wait for everybody to give me a thumbs up and then I'll proceed. So but this is easy.

8:10 This is kind of easy, right? And so if I can write things in this manner that means I can partition the uh uh network the unit into these two two operations. First I comput Z which is an aphine function of the input and then you apply the simple rule on the Z. Now what's the difference between linear and aphine? Again do you guys remember the difference between linear and fine? What's the difference between linear and fine? The intercept right? So if I have something like summation wixi, this is a linear. But if I have summation wxi plus b, that's an fi function. And how do you know whether it's linear or alpha? If you equate it to zero, this plot will go through origin. If you equate this term to zero, it does it's still going to be planer, but it will not go through origin. It can intercept anywhere.

9:22 That's the difference between linear and aphine. And so this perceptron is now can be restated as first computing an aine term which is summation wi xr + v and then putting that aine term z through this operator where the output is one. If the alphine term is greater than zero and zero otherwise and once I draw it in this manner I can take one more step and I can separate the whole thing into two steps. I can first say I compute a Z and then I compute theta of Z. And what does theta look like? Theta of Z is this function which output which takes the value one whenever the output is input Z is positive and takes the value zero otherwise and so the perceptron can be rewritten as first computing the aine term Z and then putting the Z through a theta of Z this function which outputs a one whenever the Z whenever Z is positive and zero otherwise. So this is also exactly the same perceptron as we

10:32 saw before. Is this making sense to everybody? Yes. No, guys. Okay. So I don't see any thumbs up, but I'm assuming I'm getting a Can you guys hear me?

10:50 There are millions of thumbs up, sir. Okay, perfect. So all right, this is great. But then once I separate things out in this manner, right? I don't need to retain a uh just the threshold, I can make theta of Z somewhat different. In the first case, we had theta of Z was something that looked like this zero here and then went up and then one. But instead of having something that jumps so suddenly, I can have something that goes smoother like so. And that is a sigmoid. Now you can see how the sigmoid works. So if z is a very large negative number like minus infinity then x of e ra to minus of minus infinity is e ra to infinity which is infinity itself and so this function becomes 1 / 1 + infinity which is zero. Right? So when z is a very large negative number this function is zero. When z is a very large positive so out here it's going to be zero. When z is a very large positive number then

12:02 you have again e ra to z which is say e ra to infinity e ra to minus z right is e ra to minus infinity. Let me do this cleanly. One sec. And so I can say x of minus infinity this is going to be simply zero right. And so this term becomes 1 / 1 + 0 which is 1. And so when z is a large positive number this is one. When z is a large negative number this is zero. And because this is a smooth function in between is going to vary smoothly like so. And so this sigmoid function is basically a smoother function of the threshold activation. And having the smoother function has all kinds of uh uh benefits that we will see later. Right?

13:01 So we can now write the uh perceptron like so. We first compute an aphine value and then put it through a function which could be a a threshold function or a smoother version of a sigmoid. But we can also have other activations like this tanh which is basically the same as the sigmoine but centered at zero. So it goes from minus1 to one. Or you can have this rectification function where the output of this activ of this function is the same as the input when the input is positive but zero if the input is negative or you can have the smooth version of it which is the soft plus. So in every case this function there's a the operation is a two-step process. First you compute this aphine value Z and then you put the aphine value through a function which could be a threshold a sigmoid a tan h or whatever. This function is called an activation function and different activation functions will give you different behaviors for the

14:08 perceptron. But for the moment, we're going to continue to assume a threshold activation because a threshold activation is actually really nice to develop intuitions about what's what the how the perceptron behaves. So that leads us to our first poll. Let me ask this. Can you guys see the poll?

14:54 15 seconds, guys. All right, let me stop this. Okay, can anybody tell me uh if this first one is linear or fine? What is it? The first one. Second second one

15:28 linear aine. Fine. Right. because you have a plus4. Third one, this is an aine function

15:37 linear. Yeah, functions are also a function. So this is an aphine function. A linear case is a special case aine function. And the fourth one aine, right? So the first and the third are linear but they are also aphine. The first, third and fourth are all happen. Now let's continue with this. So now a multi-layer perceptron or an MLP is a network of such perceptrons where the perceptrons receive input from other perceptrons and they feed by other perceptrons in the in the subsequent layer. We'll see a formal definition of what a layer is in a few minutes.

16:23 So when these networks have many such layers is supposed to be deep networks. What is the formal notion of depth in this context? Does anybody have any idea what's the formal notion of depth in this context?

16:41 The number of layers the number of layers. But there's something more to it. Uh to answer someone why this is aphine. This is an aphine where the intercept is zero. That's all. Okay, so let's go there. There's a formal definition of deep structures in any directed graph with sources. Sources are nodes from which you only have outgoing edges and syncs where nodes where you have only incoming edges. The depth of the graph is simply the length of the path which is the number of edges on the longest path from the source to the sync. So here in this left plot, although there's a path of length one, there's a path of length two. So the depth of this graph is two.

17:23 Here this is the source. This is the sync. You have paths of length one, length two and length three. But the longest path is length length three. So the depth of this graph is three. So we uh say a graph is deep if the depth is at least three. The same principle can be applied to networks. And in the computation of a neural network, the computation is generally directed. All the data goes from the input and flows unidirectionally towards the output. So the depth of the network is the longest length of the longest path that is the maximum number of perceptrons or neurons from input to output. So in this first figure you can see that the depth of the network is three.

18:18 Since the longest path is three in this figure, what is the depth of this network to the top? Anybody? What is the depth of this network over here? It's two, right? One, two. What about this guy over here? The one to the bottom right. What's the depth of that one? That's four. Although there are paths of length two and three, the actual depth of the network is four. So, you get the idea right? And if the depth of the network is at least three meaning it has at least the you know to go from the input to the output. The longest path is at least length three then the network is subset to be deep. So a deep network is the one where the depth of the output neurons is at least three. It has to be greater than two. Is this definition making sense to everybody?

19:17 at least three three layers. So what I see one yes okay I bet what's your doubt here so here the input goes to one layer the second layer and the third layer so this is a deep network on the other hand if you had only two layers if the network were only until here then the input would go into one layer and then the next layer this is not deep so you need to have at least three layers for the network to be called D. So uh that's the formal definition. But then how do you define a layer? Does anybody know how you define a layer in this context? I mean I'm just freely talking about layers. What's a layer?

20:08 Anyone? Input output. So here's how you define a layer. A layer is the uh set of all neurons that have the same depth from the input. This network has four layers. Can you identify which neurons are in the first layer? Anybody? Can you identify the neurons in the first layer? So there are four neurons in the first layer. These four red they all have it doesn't matter how I draw the network right these four red neurons all have depth one with respect to the input so these four neurons are layer one these three green neurons all have depth two with respect to the input meaning the longest path to these neurons is too long and so these three neurons form the second layer only these two yellow neurons form the third layer because the longest path to these yellow neurons from any input as length three and the two blue neurons are the fourth layer. So as the idea of a layer coming across a layer is the set

21:25 of all neurons that have the same depth with respect to the input that come across everybody. Everybody yes no I'm assuming you there's a lot of yeses okay so let's move on so here's how we defined our multi-layer perceptron it's a network of perceptrons which uh I will generally also call neurons sometimes after we're talking of neural networks the nodes in the networks and neurons are perceptrons the edges represent uh the connections between the perceptrons that each edge carries a weight. The network performs computations. It takes an input and produces an output. The inputs can be real or boolean. The outputs too can be boolean or real value. And we've mostly shown networks with a single output so far, but in fact the network can have multiple outputs or a vector of outputs.

22:21 So overall the network in fact represents a function that embodies an input output relationship between inputs and outputs. The question is what kind of input output relationships can this network model? What kind of functions can it compute? Now we've already seen that MLPS can compose boolean functions. It can operate on boolean inputs and produce boolean outputs like this network to the left. We also saw that networks can compose classifiers, functions that work on real valued input and output whether the input belongs to a class or not. And we saw that MLPS can also compose re real valued functions. Take in a real valued input and produce a real valued output. For instance, we saw in the last class how to construct a network that approximately computes this blue curve, the function shown by this blue curve.

23:13 But what are the limitations? Can we always construct a network to compute any function or are there limitations on what kinds of functions we can compute with a network? And if so, what are they? So that is the topic of for the rest of today's lecture. Give me a you know we will see that multi-layer perceptrons are universal boolean functions. Give me any boolean function I can compute an M construct an MLP to compute it. In this context we'll discuss why it's necessary for the networks to be deep. We'll also see that they are universal classifiers. Give me an arbitrary decision boundary. I can construct an MLP that captures it arbitrarily precisely.

23:55 Again we'll discuss the need for network to be teeth and finally we'll see that MLPs are universal approximators. Give me any input output relationship at all and I can construct an MLP that approximates it to arbitrary precision and in this context context we'll discuss the issue of optimal width and depth of the network. So first we'll discuss the topic of MLPS's universal boolean functions. Now we all know that MLPS can model boolean functions. But how well how well do they do it? Now we know that individual perceptrons can model boolean functions.

24:30 We saw these figures in the last class. They show how a perceptron can model the and not or or and or gates. To remind you in this figure the numbers on top of the edges represent the weights. The numbers in the circles represent the thresholds. The perceptron outputs a one if the total weighted input matches or exceeds the threshold. So in this figure to the left if x is one and y is one the total input is two and then this perceptron the total input matches two and this perceptron fires. If either x or y were zero then the total input would be less than two and so this would not fire. So this is n. What kind of gate was that one?

25:16 Uh that's an and what was this over here? We saw this in the last class. That was an R. And this guy we saw was a not right. We understood this. But then a perceptron can do a lot more than than just this computation. So the perceptron is in fact a universal and gate. This perceptron will only fire if all of these guys are one and all of these guys are zero. So let's see how if all of these guys are one and all of these guys are zero that see the weights the total input is L because you have L once and the rest are zeros and so this will fire but if any one of them becomes these become zero then the total input will become less than one less than L because that corresponding line no longer contributes to the aine term and so it will not fire. Similarly, if any of these guys becomes a one because the weight is minus one, this will actually subtract from the sum and the total sum will become less than 10. And then once

26:21 again, this unit will not fire. So this unit only fires if all of these guys are one and these guys are zero. So this is a universal and gate. So is this uh did this make sense to you guys over here? Does this make sense to? Okay. Similarly, this one here is what I call a universal orgate. This will fire if any of these guys are one or if any of these guys are zero. And to let's see how that works. Let's start with the only condition under which it doesn't fire. So when all of these are zero and all of these guys are one. When all of these guys are zero and all of these guys are one then the total inputs there are n minus l of these right but because the weight is minus1 that becomes l minus n and so under this condition this sum is going to be l minus n but the threshold is l - n + 1 so it won't fire but if any of these become zero then this my weight minus one will not apply and So then the total sum will

27:33 actually match or exceed L minus N +1 and it will fire. So also if any of these becomes one that's going to add to the total sum and it's going to match or exceed L - N +1 and it will fire. So this unit fires if any of these guys are one or if any of these guys are zero. It's a universal orgate. Did this make sense to you guys? This makes sense to you guys yes or no right it's very straightforward so now you can also do other things uh perceptrons are uh can also act as majority gates this perceptron will fire if at least k of the inputs are one and you can see why if at least k of the inputs are one it's going to match the threshold otherwise it will not a single unit has a majority gate. Whereas if you would try to construct this using standard boolean gates, you need an a large network with an exponential number of gates to compute the majority. And so you can see why the perceptron is a very versatile

28:44 unit and can model all kinds of crazy boolean functions by itself, which is why some early researchers researchers got fooled into thinking it could do any boolean function at all. But then the perceptron cannot model the simple exor. There is no combination of weights or and thresholds that will compute the XR. We saw this in the last class. So to compute an XR, you have to network multiple of these perceptrons and you need a multi-layer perceptron. This for example is a network that computes the XR. It's a network of three perceptrons with one hidden layer uh and one and one output neuron.

29:25 Now the structure is rather obvious. The first perceptron on top computes X or Y. The bottom one in the second layer computes not X or not Y. And the final perceptron adds these two outputs. And so you get an X X or Y. And in fact, this is not the only way to build an NLP to compose an XR. Here's a more compact way that I got from Gerald Freedelland at Berkeley. This unit, this uses only two perceptrons. But now the weights are all not all one. and let you figure out how this works. So the upshot of all of this is that we can compute all basic boolean gates using perceptrons. And so we can in fact construct an MLP for any boolean function like this weird one here uh which computes a function of four inputs. So MLPS are in fact universal boolean functions. What I mean by this is that if you give me any boolean function at all, I can construct an MLP to compute it.

30:26 So MLPS are universal boolean functions. That statement make sense to you that MLPS are universal boolean functions? Yes. No. Okay. Uh all right. Great. So MLPS are universal boolean functions. They can be constructed to compute any boolean function over any number of inputs and any number of outputs. But how complex will the network get? In the example here on the left, we saw that in order to construct a network for this crazy boolean function, we had a network with three layers and seven neurons. So the MLP that computes this network has two hidden layers. If I had a more complex function of a larger number of inputs, how many layers would the MLP need to have to compute it? How does the depth of the network relate to the complexity of the boolean function it computes? Does anybody want to guess how many layers 2 to n how many layers must a network have to compute a really complex boolean function?

31:41 2 3 so four okay I'm [clears throat] getting a few different answers but then consider this the claim is that I can do it with one hidden layer and to see why see the any boolean function is basically just a truth table it takes a number of inputs and computes an output so I can write down a table where I explicitly specify all the input combinations and the corresponding output. In fact, I don't need to write the table for every possible combination. I only need to write the table for all the combinations that produce an output of one. For the rest of them, it uh the output is implicitly zero. Once you write it in this manner, you can write out the boolean function in as a DNF or a disjunctive normal form formula. And the DNF form formula has clauses. One clause for every row, every combination of inputs that produces a one. So this first clause that produces a one says that the output is one if x1

32:52 is 0, x2 is 0, x3 is 1, x4 is 1, and x5 is 0. In boolean terms, not x1, not x2, x3, x4, not x5. The second row says not x1, x2, not x3, x4, x5 and so on. So I have one such clause for each one of these rows. They are all odd as shown by this plus. And this formula computes this this truth table exactly. But now I can build an MLP to construct this formula using perceptrons that model universal and and orgates. I can have one perceptron for this first clause, one for the second clause, one for the third, one for the fourth, one for the fifth, one for the sixth, and then finally a perceptron that orders them all. And this multi-layer perceptron with just one hidden layer is able to compute this truth table. And so the key is that it does not matter how big or how complex the truth table is. You can model any boolean function in this manner because any boolean function can be explicit as a truth

34:06 table. And so any boolean function can be composed using a multi-layer peretron which has only one hidden layer. That make sense to everybody? Does that make sense to everybody? Okay. Right. So easy enough. But then if I do this with just one hidden layer, what is the largest number of perceptrons required in the single hidden layer for an N input variable function? In other words, how large do these DNF formula get? Can anybody guess? So how large must this hidden layer be in the worst case? N plus2 N plus1. So some of you have got the correct answer and let's see why right to answer this let's take a look at the truth table in a different way in the form of a car map. How many of you are familiar with car maps?

35:09 How many of you are familiar with car maps? Anybody? So okay some folks are some folks are not. Now, a car map is a topological way of representing bit patterns such that bit patterns that differ by only one bit are [clears throat] always arranged next to one another. For example, this is a cardinal map over four variables wx, y and z. The four rows represent all four combinations of wx 0 0 1 1 and 1 0. And observe that the way I've arranged it adj adjacent rows differ in only one bit. So these two differ in one bit.

35:55 These two differ in one bit. And note that the bottommost row and the topmost row also differ in only one bit. So this top edge and this bottom edge are virtually connected. Similarly the four columns that represent the four combinations of YZ. They're also arranged so that adjacent columns only differ in one bit and the rightmost edge uh is connected to the leftmost edge. So this although I've shown it as a square, it's actually a Taurus and each cell over here represents one combination of inputs. So is this topological representation making sense?

36:34 This topological representation. Okay. And so now instead of having a truth table, I'm just going to highlight the cells for which the output is one. And so here if I I have seven input combinations for which the output is one. So a naive DNF formula would have seven clauses. But then now we can begin grouping neighbor neighboring boxes to reduce the size of the DNF formula. So here, these four guys, they're all neighboring. I can group them up because what these four guys are telling me is that it does not matter what w and x are. So long as y and y and z take the value 0 0, the output is one. And so these four boxes together can be represented by a single clause not y not z. Similarly, these two guys, they tell me that so long as W and X are zero and one and so long as Y is zero, it doesn't matter what Z is because the difference between these two columns is just Z, right? And so these two guys can be grouped into a

37:47 single clause. Not Y, X, I mean not W, X, not Y. And so also these two guys, in fact I can group all four of four corners and they they're going to give me a single clause not X Y not Z. And so this DNA reduced DNF formula doesn't have seven elements. It has only three. And therefore a single hidden layer MLP that computes the this boolean function for this truth table only has three neurons and a hidden layer. And so long as the entries in the truth table can be grouped in this manner, we can keep shrinking the DNF formula. And so the DNF formula that expresses it can be made smaller and smaller and the resulting network will be small. But we are interested in knowing the worst case. How large the one layer boolean MLP can get uh in the absolute worst case. Again, we're speaking of a one hidden layer MLP, right? So what arrangement of highlighted cells simply cannot be grouped together and reduced?

38:56 Anybody want to tell me? Checkerboard, right? So if I have a checkerboard of this kind, then there's no way for me to be grouping elements. So how many clauses would the DNF formula for this checkerboard require? How many? Anybody? eight right now. Sorry. Here's a three-dimensional version of the same thing. This is a 3D version of a car map on six input variables UV, wx, and yz. How many neurons would be required in the hidden layer for a one hidden layer MLP that computes this boolean function? Anyone? 32. Right. So we can this can be generalized. If you have a boolean function over n variables and you construct a one hidden layer MLP to compose the corresponding DNF formula, you will end up needing 2 ra to n minus1 neurons in the hidden layer. The size of the network in terms of the required neurons is exponential in the number of inputs. [clears throat] This make sense to everybody?

40:16 This make sense? Does this make sense to everybody? Yes or no? Okay, I'm assuming there are lots of thumbs ups. And so that gives us our next poll. 10 seconds, guys. All right, let me stop this. Okay, somebody want to tell me the answer. What is the answer? 512. Right? So indeed that is the correct answer. Beautiful. So you guys got it. Now this can be generalized. So to reiterate, if you only allow one hidden layer, this pattern over n inputs requires an exponential number of neurons to raise to n minus one neurons in the hidden layer. But uh what would be the size of the network if we allowed multiple hidden pairs? Now does anybody recognize this function?

42:07 What is this function with a checkerboard? Can anybody tell me what's this function with a checkerboard? anyone. What is this function? It's an XR, right? Thank you. So, this function represented by these checkerboards is actually just an XR. An XR is just a function where if you change just one bit, the output goes from 0 to one. If the number of bits, the total number of ones is even, the output is zero. If it's odd, the output is one. And so this is wx or xx or y x or z. This is ux or vx or wx or x x or y x or z. And we know that an xr can be constructed using only three neurons in two layers or even just two perceptrons. Right? And so for this function we can construct the mlp as a series of exors like here. The first three neurons compute the XR of W and X.

43:11 Then the next three neurons XR that result with Y. The next three neurons XR that result with Z. And so totally we're going to need only nine neurons. Now again even if we directly implemented this using just the straight up DNF formula, it still need nine neurons. So it doesn't look like we won out here. But then if you go to the larger networks like this one, this is a function of six variables which has five XRS. The XR based network which looks over here only needs 15 perceptrons whereas the one hidden layer network required 33.

43:50 Generalizing this to n inputs, the xr of n input variables will just require 3 * n minus one or even 2 * n minus one neurons when built in this manner. And so we have this right when you have an exord of n inputs a naive single hidden layer MLP will require to require 2 to n -1 + 1 neurons which is exponential in n. Whereas a deep network where you're allowed to have as many hidden layers as you want will require only 3 * n minus one perceptrons. This is linear in n. So when you make the network shallow the number of neurons is exponential. When you allow it to be deep it ends up being linear in the input. And moreover these three n 3 * n minus one neurons can be arranged in only two times log 2 n layers. So did all of this make sense so far guys?

44:56 Did all of this make sense? Okay. So let's see how we can arrange this only in two times login layers. Here's how you do this. The XR is associated which means you can group the operations in any way and the output will still be the same. So we can first compute the XR of the first two inputs separately comput of the next two inputs then compute the XR of the next two inputs and so on. You can compute XR pair-wise. And so the outcome of that operation is going to be a series of values each of which is the exor of two terms. Then those things can be paired up and exort. And then you can you're going to get a series of values which are at x of two terms at this level which is four terms at this level. And those can be exort pair-wise and so on.

45:46 And so here is the kind of structure you would get that each now again each XR of course requires two two layers right. So over here each pair of layers highlighted in a blue box is producing a set of variables that can be further exor downstream. And each blue box reduces the number of variables by a factor of two. And so what this means is that the total number of these blue boxes is going to be log 2 of n. Within each blue box you have two layers. So the total number of layers is 2 * log 2 of n. And so if you allow the network to be deep, the number of neurons is going to be linear in the number of inputs and the number of layers is required is going to be logarithmic and the number of inputs.

46:42 That make sense to everybody? Okay beautiful right? But then what happens if you terminate the network early after just a few layers? So let me say that I don't want the network to have login layers. I want to want it to have at most four layers. Then in the best case, the first two layers can be used to reduce the number of variables by two. But the rest of them still have to be exorked. And because after that you you're only allowed one more hidden layer. This layer is going to be the size of this layer is going to be exponential in the number of variables over here. And so effectively it's going to be exponential in the number of inputs. So if you use fewer than the minimum uh required if you if you use fewer than uh two times login layers or more generally if you use a fixed number of layers then to model the net function exactly you're going to require an exponential number of neurons and if you try to take a

47:51 shortcut and try to go below that number of neurons then the results can be horrible. In fact, for the XR, if you just go one neuron below the minimum, then the error of the XR is going to be 50%. Because that's the function, that's the kind of fun function the XR is. That makes sense to you guys. Why? If you have a fixed number of layers or if you have fewer than the minimum required number of layers, then the network has to be exponentially wide or it's going to be very long. That make sense to everybody? Yes or no?

48:29 I see two S's. Any questions? We have a question in the chat. Okay. What is the question?

48:37 So, will two end layers usually be the optimal starting point when deciding ideally the problem is that we don't know the function here. I'm assuming it's an exor a more general boolean function. A more general function can be anything. And so the optimal number of layers can't really be known for the function. But in the worst case, it has to be log to n. Okay, if you have log to n layers, then you can expect to be able to model functions with a linear number of neurons. Now the thing is uh this means that the depth of the network depends on the number of inputs. More generally, when you build neural networks, you decide on the depth of the network regardless of the size of the input and so you just end up falling into this condition and as a result your networks end up needing to be very large simply because you're not matching the optimal depth.

49:36 And so to recap, deep boolean MLPS that scale linearly in size of the number of inputs can become exponentially large if we cast using only one hidden layer or even a fixed number of hidden layers where the number of hidden layers is independent of the number of variables in the input. And so in summary uh an MLP is a universal boolean function but can represent a given function only if it's sufficiently wide if it's sufficiently deep if depth can be traded off for but depth can be traded off for sometimes exponential growth of the width of the network.

50:14 optimal width and depth depend on the number of variables and the complexity of the boolean function where the complexity can be defined in terms of the minimal number of terms and the DNF formula for the function and so so our story so far is that multi-layer perceptrons are universal boolean machines even a network with a single hidden layer is a universal boolean machine but a single layer network may require an exponentially large number of perceptrons deeper networks may require far fewer neurons in shallower networks to express the same function. They could be exponentially smaller.

50:52 So we've seen MLPS as universal functions. But then let's move on to MLPS as universal classifiers and the need for depth. We've already seen that an MLP can operate as a boolean function over real inputs. Basically as a classifier, a boolean function will effectively partition the input space into regions where the output is one and regions where the output is zero. And therefore it's able to act operate as a classifier where it separates out the data within the region where the output is one from the data where uh in the region where the output is zero.

51:35 And we've also seen that the network and model compute some very complex uh decision boundaries. But before discussing multi-layer perceptrons, let's first consider a single perceptron. To recap, a perceptron uses this criterion for its output. If the weighted sum exceeds the exceeds the threshold, the output is one. If it's less than the threshold, the output is zero. The boundary between the between the two is where the weighted sum is exactly equal to a threshold. That's going to be a hyper plane and on one side of the hyper plane the output is one the other side it's zero.

52:13 The so the perceptron overall models this models this heavy side function where there's a hyper plane on one side the output is zero and the other side the output is one. But then uh once you understand this you can see how it can compute boolean gates. If the input is boolean if you have two boolean inputs the input combinations can be 0 0 1 0 0 1 or 1 1. And so the input combinations can be only one of these four dots. If the weights of the perceptron are set such that this boundary between the one and the zero falls in this region, then this captures a specific boolean gate. What was the boolean gate this captured?

52:59 This is an R. And this guy, if the weights were like this, this what did this capture? The output is one over here. It's a not on a Y. It's ignoring X, right? And now you can see why it cannot capture an XR. An XR actually needs two boundaries because the output is one for these two combinations and zero for these two combinations. Whereas a perceptron can only model one boundary. Which is why a single XR cannot single perceptron cannot model an XR. And that leads us to our third pole. Where is that? I put third pole.

54:07 15 seconds, guys. All right, let me end this poll and let me ask you what is the answer. It's true, right? So an XR needs two hidden neurons and one output neuron because we need one hidden neuron for the two boundaries and an output neuron to add them. Beautiful. But once we have that the basic perceptron we saw how we could compose decision boundaries like this pentagon. You want the net to output of one inside the pentagon and zero outside. So we compose one perceptron for each of the five boundaries like so. And then finally you so each perceptron is going to be outputting a one in the highlighted region and a zero in the non- highlighted region. And so finally you find that only the pentagon is the only region where all five perceptrons output a one. So if you sum the outputs of the five perceptrons it's going to be a five inside the pentagon and less than five outside.

55:30 And now this final perceptron can simply compare this sum to a threshold of five and it's going to capture the uh pentagon decision boundary. But once you know how to compose a pentagon decision boundary, you can compose more complex boundaries. for example, this double pentagon. Uh, and we'd have one subnet that outputs a one inside the first pentagon, a second subnet which outputs a one inside the second pentagon, and then a final neuron which cores these two. And this is going to give you the double pentagon. Once you know how this how to do this, using the same mechanism, you can compose even more complex decision boundaries like the ones on this slide.

56:14 For example, for this decision boundary, we can partition it into many sub regions, compose a subnet for each sub region, and then or the lot and that's going to give you this crazy decision boundary. You can use the same mechanism to compose any arbitrarily complex decision boundary. But the circuit we compose for this actually has two hidden layers. Can we do this with only one hidden layer? And if so, how? To make this more concrete, to give you a simpler example, can anybody suggest how I can compose a network of this kind with only one hidden layer which captures this decision boundary?

57:01 Any suggestions? How would we do this with just one decision boundary? anyone had a layer each side is of course a perceptron but exor xors need to you know leong says is it possible that's actually a good question how would you do this any suggestion not possible okay some of you are probably thinking that you know I can just have one perceptron for each of these boundaries but if I do that go back and look here right you had the the sum was four in this region and here and here and here. So because the sum is four in these regions, if I just have one perceptron for each of these uh pentagons, then the sum is going to be four over here from these five. It's also going to be four over here from these five. And so in this region, although it's neither in this pentagon or in this pentagon, the sum is going to end up being eight, which is probably going to be higher than the sums inside the double

58:13 pentagons. And so you're going to end up you'll get the double pentagon, but you'll get a lot of speurious regions because specifically of these regions over here where the sum is almost five but not quite five. And we need a solution that makes sure that the sum is not close to the to five inside. That make sense to you guys? Did did that make sense to you guys? Right. What we just the logic I gave? Okay. So, how do we get around that? To get around see how we how we get around that. Let's start with a simple diamond shaped decision boundary. We can do this with four hidden neurons, one for each of these boundaries and then the final final and. So if I just plot the sum of the output of these four neurons, the sum of the output of these four neurons is going to look like this.

59:15 It's four over here. It's three in these strips which is infinitely which goes off to infinite which go off to infinity and it's two in these little blue regions. So if I apply a threshold of four, I'm going to get a decision boundary that's a a diamond but then keep track of these regions where the sum is three that's for a diamond if I go I go to a pentagon then again now I need five neurons in the hidden layer but the sum of the output of these five neurons looks like this that it's five in the pentagon but the region where the sum is four has actually become the star which is kind of over here for when I when I had only four sides the region where the sum was three went off to infinity here. The region where the sum is four n minus one is actually finite and this star- shaped region. If I make it a hexagon, then I have six hidden neurons, one for each side. But if I look at the sum of these

1:00:16 outputs, it's going to be six inside. But the region where the sum is five is an even smaller star. If I make it a heptagon, I'm only plotting the sum. You can see that the region where the sum is six and not seven has become even smaller. Where the sum is five is also finite. With 16 sides, this is the figure we get. With 64 sides, this is the figure we get. This is what you get with a th00and sides. And so we see that as we increase the number of sides to the polygon for an n-sided polygon the area within which the sum of the outputs of the hidden layer is just is not quite equal to n but high enough to cause problems keeps shrinking.

1:01:06 That make sense to everybody? This makes sense to everybody? Yes. Right. And so do we have thumbs up Brad? Okay,

1:01:20 we do. So what was the problem here Jesse? Your question can you clarify your doubt? Ask me out.

1:01:29 Yeah, this last part that you said when we have like more uh more polygons like the more size of the polygons I didn't get it well. So here I'm just plotting the sum of the output of these neurons. And you can see why the sum is four inside, three over here, and two over here. Right? Do you get that?

1:01:49 Yes. I did that for five pentagons. It's five here. The sum in the various regions. Did this figure make sense?

1:01:59 Yes. This is I'm plotting the same thing as I keep increasing the number of sides. That makes sense. Yeah.

1:02:09 Okay. And in the limit, you know, we're going to find that the uh that as we increase the number of sides for an ns-sided polygon, the area within which the sum of the outputs lies between n /2 and n keeps decreasing. in the limit is you're actually going to get this function over here which looks uh this which has this crazy formula which one of my TAS once worked out worked out but uh if you simplify it if you have an infinite number of sides that's a circle and then if I have neurons for every side the sum of the outputs is going as n becomes very large you're going to eventually end up with a network where the sum is exactly n inside the circle circle and n /2 everywhere everywhere outside almost everywhere outside then you can place the circle anywhere you want and furthermore if I subtract and the n /2 from the sum I'm going to end up with a network where the sum is exactly n /2 inside the circle and exactly zero

1:03:21 everywhere else. So now if I want to compose uh if I if I add two such networks where this first network the sum of these neurons is this cylinder the second network is the this set of neurons whose sum is given by this cylinder again they're they're just different copies of these this cylinder in different locations because you can place them anywhere. Then the sum of the outputs of both of these networks is going to be two cylinders like this with the height being n /2 inside the cylinders and zero outside. Did that make sense to everybody?

1:04:04 Right. And so any questions on this graph? Do you see any questions in chat? Okay. And so this is beautiful. I can now use a threshold of n /2 and I'm going to get a decision boundary which is two disconnected circles. And if I can place two disconnected circles, then I can make any odd decision boundary. If I want to compose this double pentagon using only one hidden layer, we will do so by approximating it as a union of many little circles. Each one using its own little subnet of hidden neurons. And you can make the approximation arbitrarily precise by filling it with more and more smaller circles. And so you can approximate the double pentagon to arbitrary precision using only one hidden layer. Although this will require an impossibly large number of neurons in the hidden layer.

1:04:59 And thus we have this MLPS can capture any classification boundary. Even a one hidden layer MLP can uh approximate any classification boundary to arbitrary precision. So your MLPS are universal classifiers. Again, what this means is that you give me a classification boundary and I can compose an MLP that computes it. And in fact, I can compose an MLP with just one hidden layer that computes it. But we the thing is if I simply make the network deeper like in this case the number of neurons falls dramatically. If I just wanted only one hidden layer I needed almost infinite neurons and I only got an approximation to the decision boundary. Whereas as soon as I let the network go deep, the uh number of neurons required became finite and my approximation and and and the and the accuracy with which I modeled the boundary became better and better.

1:06:08 So this makes sense to everybody. Does this make sense? Which is why you need depth really matters even for classification. We know deeper network networks are bit better. But why? To get a better idea, let's look at a different kind of decision boundary which is a bit of a worst case decision boundary. We will analyze threshold activation networks. But this should generalize to other networks as well. Consider this decision boundary. This network must output a one when the input is in the yellow regions and zero for the gray regions. Now, if I build a naive one hidden layer neural network, as we just saw, I'm going to have to fill all of these yellow regions with little circles. And so, you're going to need a network with almost infinite neurons in the hidden layer.

1:07:02 But if I do this with two hidden layers, I need only 56 neurons. That's because this decision boundary over here is composed of 16 lines. And so uh uh here the 16 lines are shown here in the top left each of these red lines. And so we need 16 perceptrons to capture each one of these 16 lines. Then there are 40 of these yellow regions in all. So we will need 40 perceptrons in the second hidden layer. One to capture each one of these yellow regions. And then we need a final perceptron to order the outputs of these neurons. And so this network if I allow two hidden layers requires 57 total neurons including the output neuron.

1:07:56 But then can I make it smaller? This is just an XR pattern, right? If we number the outputs of these first 16 neurons as Y1 through Y16, then this entire pattern is simply going to be an XR of Y1 through Y16. So if I compose this using an XR network, the XOR part of it because there are 16 of these guys are only is is only going to require 15 * 3 neurons, 45 neurons. In fact, if I if I compose each XR using the two neuron network from Gerald Freedelland, it's only going to require 15 * 2 30 neurons. And so, the overall network would require only 46 neurons as opposed to the uh 57 neurons. Now in this example maybe it doesn't seem like a big win but if I came went to something more complex like this decision boundary this is composed of 64 lines and we want the network to output of one for the inputs in the yellow regions. You can capture the 64 lines with one hidden layer of 64 perceptrons.

1:09:08 There are 544 of these yellow regions in the second layer. So in so including the output neuron you're going to have 544 neurons over here 641 neurons here this guy over here the total number of neurons is going to be 609 neurons but once again this is just an XR over the 64 lines. So a 7 layer XR network that uses three neurons per XR can do this with only 253 neurons. If I use two neurons per ex, the network will require only 190 neurons as opposed to 609. And so the difference in size between the deeper optimal network and the shallower network increases with increasing pattern complexity and input dimension. Now note that I'm not comparing a network with one hidden layer with a deep network. This network in fact has two hidden layers. But even with two hidden layers, this ends up requiring many more neurons than something that is much deeper.

1:10:19 And so the depth summary is that the number of neurons required in a shallow network can be potentially exponential in the dimensionality of the input in the worst case or exponential in the statistic in the uh in number of statistically independent features. But even if you allow networks of different depths, the deeper network will often require far fewer network neurons than the less deep network. And so the story so far, multi-layer perceptrons are universal boolean machines. Even a network with a single hidden layer is a universal boolean machine.

1:11:01 And we've seen that multi-layer perceptrons are also universal classification functions. Even a network with a single hidden layer is a universal classifier. But a single hidden layer network may require an exponentially large number of perceptrons more than a deep one. And deeper networks in general may require far fewer neurons than shallower networks to express the same function. Could be exponentially smaller. But even if it's not exponentially smaller, as we saw in the case of the little yellow checkerboard, a network that was deep require can end up requiring much much much fewer neurons than a network that is less deep.

1:11:44 Did that that make sense to all of you guys? That make sense what we've covered so far? Yes. No. Any other yeses? Are there thumbs up, Brad? I can't see them for some reason.

1:12:03 Yeah, there are tons. I see some I got 29 thumbs ups. I'm going to wait for 60 of them, right? So, uh, the next time around, I'd like to make sure that at least 20% of my class got it. Okay, I think I have 60. All right. And so, let's go on. Finally as uh MLPS as universal approximators. We've seen their universal boolean functions, universal classifiers. Uh how about as approximators? We saw that an MLP with two perceptrons can compute a this step function, a pulse over a scalar input. The two perceptrons have different thresholds T1 and T2. Their outputs are summed with weight one and minus one.

1:12:52 And so when the input is less than T1, neither of them will fire and the output is zero. When the input is between T1 and T2, this neuron will fire but this will not. So the sum is going to be one. When the input is greater than T2, both of them fire, they cancel each other out and the output becomes zero again. But then subsequently we can compose any scalar function of a scalar variable with a one hidden layer MLP by approximating the function of many function as a sum of many such pulses all scale to the right height. So a one hidden layer MLP can model arbitrary arbitrary scalar functions of a scalar variable.

1:13:32 For functions of higher dimensions it gets trick trickier. We begin by recalling that a one hidden layer NLP can compose a cylinder that has height n /2 inside and zero outside. And so to compose an arbitrary function in iron dimensions, you can approximate it by summing appropriately scaled and shifted cylinders and you can approximate it to arbitrary precision by making the cylinders thinner. So one hidden layer MLP is a universal function approximator. And so here's our fourth pole. I also have a fifth pole, but people don't know how to

1:14:29 only give you 30 seconds for this, guys. So 10 seconds more. Okay, let me end this. What is the answer, guys? It's false. It's false because it can only be approximated, right? Finally, let's briefly discuss the issue of sufficiency of width and depth and its relation to the activation function. We've seen so far that a single hidden layer MLP is a universal function approximator. It can approximate any function to arbitrary precision. More generally, deeper networks we saw will require far fewer neurons for the same approximation error for boolean functions, classifiers, and re real value functions. But there are limitations. And where do these come from?

1:15:33 Now we saw that this neural network can this neural network with 16 hidden neurons and 40 neurons in the second layer can can capture this decision boundary. So our claim is that a neural network can represent any function provided it has sufficient capacity if it's sufficiently broad and sufficiently deep to represent the function here. If it has 16 neurons here and 40 here, it's good enough to model this function. But what if it had only eight neurons in the first layer? I'm going to assume we have threshold activation functions.

1:16:09 Then would it be still be able to capture this function? What do you guys think? If I only have eight neurons in the hidden layer in in the first layer, would it still be able to model this function? So, Praad says no. And the answer is no. Why? Say the eight neurons capture these eight lines as shown in that are shown in red. Now, the output if I'm using threshold activations, then the output of the first layer is only going to tell me, you know, because the output is either one or zero for each of these neurons, right? The output is only going to tell me in which of these strips the input is. but provides no additional information about where you are in the strip. So it doesn't matter how many neurons I put in subsequent uh layers. I do not have the information to capture reconstruct the checkerboard. Even if the eight neurons capture these eight lines, you'll only have the level of information shown here. You can

1:17:13 determine which of these 25 regions the input is in. But you cannot improve beyond that because you you don't know where you are within the region. Regardless of how many layers or neurons you add afterwards, you cannot recover the checkerboard. So also if you even have even if you have a full complement of 16 perceptrons in the first hidden layer, if you have only two layers and fewer than 40 neurons in the second layer, you cannot compose this per function perfectly. In other words, if you make your network deep rather than wide, you have to ensure that each layer is still sufficiently wide [clears throat] to transmit the information required. If if not, it does not matter how deep you make your network, you cannot model your function.

1:18:03 So, but there's a caveat and let's come to the caveat. We saw that a network with fewer than 16 neurons in the first layer could never compose a decision decision pattern. Why? This is because in all of our explanations, we used threshold activations which gates information in the input and prevents it from reaching later layers. So if you had only four neurons in the first layer, each neuron will tell you whether the input is on one side of a boundary or not, but it won't tell you how far you are from the boundary. As a result, if you had only four neurons in the first layer, the output of the first layer will partition the input into a small set of regions like this, but provides no subsequent information and subsequent layers cannot have cannot make up for this loss of information.

1:18:56 This happens because we use threshold activations which lost information about how far you are from the boundary. If on the other hand you used a continuous activation like a sigmoid it will produce a graded output like this one and so the output of the sigmoid will tell you how far you are from the boundary and that can provide the information to subsequent layers which may then be able to use that to compose the rest of the function. But a sigmoid is not great in the sense right you can see that once you get past these dotted lines then the variation of the sigmoid as a function of the distance from the boundary basically vanishes to almost zero. So having more informative activation functions like this guy like a reloop which continues to inform about how far you are from the boundary forever at least on one side of the boundary or a soft or a leaky rail which continues to inform how far you

1:20:02 are from the boundary on both sides of the boundary. These are better activations which where the first layer outputs will continue to give you information. They'll give subsequent layers information that they can then use to compose the decision boundary properly. And so narrow layers can still pass sufficient information to subsequent layers provided the activation function is sufficiently graded. But in order to completely capture the function, we will need greater depth in the network to permit later layers to capture the details of the function.

1:20:42 So did all of this make sense to you guys? The the why we need activations that are not threshold activations. Theations is that they're only going to give you this kind of information. smoother activations will tell you how far you are from the boundary. So these neurons will continue to give information about how far you are from the boundary and then the subsequent layers can use it to compose the con compose the uh the uh compose the rest of the pattern. Right? So the thing is that you're still kind of hoping that you get things right. For example, if I have four neurons and the four neurons are just like this, then you do not have information in this direction.

1:21:37 So you still cannot compose uh the entire boundary. If you want if you have only four neurons, you want your four neurons to capture boundaries of this kind, which is when you'll be able to reconstruct the entire checkerboard. Otherwise, you don't have information in this direction and you won't be able to construct the checkerboard. So you need graded outputs. But even then there is more to it than that for you to be able to capture your model capture your uh boundaries your function properly. And so the lesson so far MLPS are universal function approximities. They can model any boolean function classification functional regression. Deeper MLPS can achieve the same precision with far fewer neurons but must still have sufficient capacity.

1:22:24 The activations must pass information through and each layer must be sufficiently wide to convey all the relevant information to subsequent layers. I have a poll which I will skip. We keep talking about the capacity of a network. What exactly is the capacity of the network? There have been various definitions based on information of storage capacity, VC dimension and so on. From our perspective, it's the largest number of disconnected regions of the input that the network can represent. uh and the point is a network with insufficient capacity cannot model a function that requires greater minimal number of uh a larger network than the a network with a larger capacity than what your network currently has. So uh even more definitions maybe later in the course if I have the uh an extra lecture I'll ask Gerald Freland to give a lecture on this topic and so here are the lessons today MLPS are boolean functions universal boolean

1:23:28 functions universal classifiers universal function approximators even a single layer MLP can approximate anything to arbitrary precision but could be exponentially or even infinitely wide in its input size. Deeper MLPS can achieve the same precision with far fewer neurons. In other words, they're more expressive. Also, more graded activation functions result in more expressive networks. Next up, we know that MLPS can emulate any function, but how do we make them emulate a specific desired function? For example, if you want a function takes an input and labels outputs the labels of all the objects in it or takes in speech and produces transcriptions. How do you compose a network that computes this function? That is training and NLP. And we'll pick that up from the next class.

1:24:20 So I'll stop right here and I'll take any questions.

Questions about this episode

What is discussed in "CMU Introduction to Deep Learning 11785, Spring 2026: Lecture 2"?

In order: 0:00 Neurons, Threshold Logic; 10:00 Sigmoid, Neurons, Multi-layer Perceptron, Activation Function; 20:00 Neurons, Boolean Functions, Multi-layer Perceptron, Decision Boundary; 30:00 Truth Table, Neurons, Multi-layer Perceptron, Boolean Functions; 40:00 Neurons; 50:00 Decision Boundary, Neurons, Boolean Gates, Input Space; 1:00:00 Neurons, Decision Boundary, Cylinders; 1:10:00 Neurons, Boolean Functions, Sigmoid, Activation Function; 1:20:00 Neurons, Activation Function, Boolean Functions, Decision Boundary.

What is mentioned in this Carnegie Mellon University Deep Learning episode?

17 people, works and ideas are mentioned, including Multi-layer Perceptron, Neurons, Activation Function, Decision Boundary, Boolean Functions, XOR. Each one on this page links to its own page with every episode that mentions it.

How long is "CMU Introduction to Deep Learning 11785, Spring 2026: Lecture 2"?

The episode runs 1 h 24 min; the transcript is about 11,796 words in 96 timestamped sections.

More from Carnegie Mellon University Deep Learning

About this transcript: the episode's spoken words as captioned on YouTube, split into timestamped sections. Reclip.Me locates every person, work and idea in the text, keeps the time it is first named, and quotes the words around it verbatim. Last updated January 24, 2026.