In this lecture, we are going to discuss convolution in the preparation for building convolutional
neural networks.
Of course, given the name, it's pretty obvious that a convolutional neural network is a neural network
with convolution.
And so in order to understand CNN is we must first understand convolution.
First, I want to mention that people sometimes treat convolution as this mysterious thing.
But as with our discussion of machine learning, we want to take the dumb as possible approach.
Sure, convolution can be complex.
It's a central operation in the signal processing and computer vision.
But in fact, it's quite simple.
There are only two requirements.
First, can you add.
Second, can you multiply?
If your answer to these two questions is yes, then you understand convolution.
Believe it or not, convolution is just adding and multiplying.
So let's start by not doing any math.
Let's just look at convolution qualitatively with convolution.
There are three objects you want to pay attention to.
First is the input image.
Second, there is the filter.
Note that another name for the filter is the kernel.
So we're going to use those two terms interchangeably.
Finally, there's the output image.
The output image is what you get when you convolve the input image with the filter.
In other words, if I perform the convolution operation on the input, image and the filter, I get
the output image.
The Betha medical symbol for convolution is a star or asterisk.
Not to be confused with the asterisk that we use in computer programming for multiplication.
So if you're running convolution in code, it will not be an asterisk because in code we already use
the asterisk for multiplication.
It's helpful to think of some examples of convolution to understand what it can do.
There are two examples I really like.
The first example is blurring.
So the input image is just the original image and the output image is a blurred version of that image.
You might recognize this operation from applications such as Photoshop.
The second example I really like is edge detection as input.
We have the original image and as output, we get white lines where there are edges in the original
image and we get black where there are no edges.
So the output image highlights all the edges in the original input image.
So that's your first lesson on how to view convolution, this perspective is that convolution is an
image modifier.
The input is the original image and the output is a modified or transformed version of that image.
In other words, you might think of this as a feature transformation on the input image.
You know, that sounds curiously like what a neural network does.
In any case, what makes a blurring and edge detection actually work if they are both convolution?
What makes one convolution different from another convolution?
Well, the answer is the filter when you use a gussying filter.
This blurs the image when you use an edge detection filter.
You get edge detection.
You can think of that as sharpening the image.
Your next question might be how do we find or design these filters in the first place?
That's something we'll discuss later in the section.
But the answer, as you might have come to expect, is just another dumb as possible approach.
OK, so let's get into the nitty gritty of how convolution works.
I promise you that all you need to know is how to add and multiply.
Let's see if that's true.
We're going to use it.
Very tiny images for this example.
Although in reality, the actual images we work with will be much bigger.
This is just so we can feasibly do these calculations by hand.
So let's start with an image zero 10, 10, zero, 20, 30, 30, 20, 10, 20, 2010 and zero five
five zero.
And we also have the filter one zero zero two.
So how do we convolve this image with this filter?
Let's imagine overlaying the filter at the upper left corner of the image.
Then all we need to do is Element Y's multiplication and add up all the results.
So, yeah, one time zero plus zero times 10 plus zero times 20 plus 30 times two.
That is equal to 60.
This gives us our first output in the output image.
And as promised, all you needed to do was multiply and add.
Now, let's move our filter over one space to the right and then let's do our element Y's multiplication
and add up the results again so we get one times ten plus zero times ten plus zero times thirty plus
two times thirty.
That's 70.
This gives us our second output, which goes to the right of the first output.
Now, let's move the filter over one more space to the right and do the same operation again.
We get one times ten plus zero times zero plus zero times 30 plus two times 20, and that's 50.
This gives us a third output, which goes to the right of the first two upwards.
Now you realize that there's no more space to move our filter to the right anymore.
So let's instead zigzag back to the left, but go down one row and then let's repeat our calculation.
We get one times 20 plus zero times 30 plus zero times ten plus two times 20.
That's equal to 60.
This gives us our first output in the second row.
So you can see that the outward location corresponds to where we've placed the filter along the original
image.
So we're not going to go through the rest of the calculations, since that would be a bit redundant.
But what I want you to do is if you don't understand this, do the rest of the calculations by hand
to make sure that these results are correct.
So we have 60, 70, 50, 60, 70, 50, and then 20, 30, 20.
One helpful exercise to get a better idea of how Convolution works is to write pseudo code and even
real code to implement the algorithm we just described.
This will help us uncover a few hidden details.
You may have not considered just by starting the code, you realize one thing you need to take care
of, which is what size.
Should I initialize the output array?
As if you recall in our example, the input image huddling for while the kernel had length to the output
handling three.
So what's the pattern?
I claim that if you have an array of length N and a filter of length K, then there are an A minus K
plus one distinct possible positions you can put the filter into.
You might want to draw this on paper.
If you don't see right away why this is true.
So the first step in our pseudocode is to initialize the output array.
But here's another detail.
You may have not considered that what height will be the input height minus Col height plus one that
put width will be the input width minus kind of width plus one.
But in our example, both our image and kernel were square.
So you might be wondering, is this always the case?
What's the convention?
And the answer is that four images, usually these are not square.
This just has to do with cameras and screens.
Most screens like your computer screen and your TV screen are not square.
And therefore, cameras do not take square pictures.
Therefore, images we find in the wild that we want to use as data are typically also not square.
Some known networks do use square images for convenience.
So when you build a data set, you make them square.
And one example of this is amnesty, which we've already seen.
On the other hand, colonels are almost always square by convention.
Let's move on, the next step is just to fill in the output array by performing the convolution algorithm.
So first we loop through zero up to up at height with the index.
I.
Inside that, we loop through zero up to output with with the index J.
So the pair IJA will always index our output.
Then we loop through each position of the colonel.
So we have I going from zero up to Colonel Height.
And we have JJ going from zero up to Colonel Width.
Finally, inside all these loops, we have our main calculation, which, as promised, is just multiplication.
And addition, we multiply the input image at position.
I plus I j plus j k by the colonel.
Add position i j j.
And we add this result to the output image at IJA.
Now it's OK to accumulate using plus equals because we initialize the output image to be all zeros.
As an exercise, you might want to try and put this into code so that you can confirm that it works
and returns the expected result.
The inner part of the pseudocode is key because it helps us understand the equation that defines convolution.
So here we can see that the IJA ith entry of the output a convolve with W is the sum over I prime.
And the sum over gay pride of a at I plus I prime.
J plus J prime times.
W at AI Prime.
J Prime.
Now you might ask, why are we looking at these complicated equations.
If Pi Torch already does all this work for us.
And the answer is that this will help you immensely in understanding the different perspectives on convolution
that we are going to discuss later.
Moreover, if you're a curious person and you go on Wikipedia to read about convolution, you'll see
something very similar to this.
In this example, you can think of X as the filter, Y as the input image, and Z is the output image.
Now, you might notice something weird about this equation from Wikipedia, which is that instead of
plus signs, we have minus signs.
Why is that?
Is the lazy programmer wrong?
And the answer is, in fact, all of deep learning is wrong.
But for better or worse, that's just the way we do things.
In the end, it doesn't make a difference because the filters we use will be learned that using gradient
descent, in other words, automatically.
So the process of finding the filter will be done automatically using gradient descent, which will
find the best values that optimize our lost function.
So it doesn't matter if the filter is reversed or not.
In fact, if you use a library like Saipov, you'll notice that it already has a function called Convolve
Tudi.
The problem is if you use this function as is, you'll get a totally different answer than we did.
And as a side note, you might want to try it yourself to confirm that what I'm saying is true.
Now, this is because Convolve Tudi does a proper convolution and not the deep learning version of convolution
with plus instead of minus.
In order to make Sipos convolution work the same way, we have to flip the filter both horizontally
and vertically and set the mold argument equal to valid.
Now, as a side note, convolution is a commutative operation, a convolve with W is the same as W Convolve
with a, therefore it doesn't matter which input we flip.
In fact, what we are doing in deep learning is actually known as the cross correlation.
I actually think this is a much more helpful and descriptive name compared to convolution convolution
in and of itself.
Probably doesn't mean much to you.
But the word correlation does.
You probably think of the word correlated as sameness.
So if I say X and Y are correlated, that means to you that there is some degree of similarity between
X and Y.
Therefore, you might think of CNN as a correlation or on that work rather than a convolutional neural
network.
The only difference between correlation and convolution is that convolution reverses the orientation
of the filter, whereas correlation does not.
The final topic I want to talk about in this lecture is this Moad argument to understand this.
It's helpful to look at these animations which kind of summarize how Convolution works.
Basically, you're sliding the filter across every possible position in the input image.
And this animation, the motion of the filter is bounded by the edges of the image.
Because of this output, image is always smaller than the input image.
But you might wonder, what if I want the output image to be the same size as the input image in this
case, what you can do is add padding.
This is equivalent to adding a virtual array of zeros around the input image so that the filter can
extend out to those values.
The reason I say it's virtual is because you wouldn't really want to allocate the space in code.
There's no reason to, since you already know that anything multiplied by zero is still zero.
So in other words, to quote unquote add padding, you can just pretend there are zeros surrounding
the input image as many zeros as you need to ensure that the output size is equal to the input size.
You may have noticed, however, that even with padding, we still lose some information.
What I mean by that is there are outputs we could calculate if we extended the padding even further.
That would be non-zero outputs.
So one other thing you can do, which is not as common these days, is to extend the padding further
so you can catch all these non-zero outputs.
This results in an output size of N plus K minus one.
If your input image has length N and your filter has length K.
Again, you should draw this out on paper.
If you're not convinced this is true.
To summarize the three modes of convolution, let's look at this table.
The first one we discussed was called valid convolution.
This applies when the kernel can only touch the original input image.
The output size is in the minus K plus one.
The second one we discussed was called same convolution.
In this scenario, we add some padding just enough so that the output size is the same as the input
size in.
The third mode we discussed is called full convolution in this scenario.
We extend the filter out as far as possible so that at least one point on the filter overlaps with one
point on the input image.
The output size is N plus K minus one.
Normally in deep learning, we use valid or same convolutions.