C4W1L05 Strided Convolutions

Striated convolutions is another piece of the basic building block of convolutions as used in convolutional neural networks. Let me show you an example. Let's say you want to convolve this 7 by 7 image with this 3x3 filter, except that instead of doing in the usual way, we're going to do it with a stride of two. What that means is you take the element wise product as usual in this upper left three by three region, and then multiply and add, and that gives you 91. But then instead of stepping the blue box over by one step, we're going to step it over by two steps. So we're gonna make it hop over two steps like so. Notice how the upper left hand corner has gone from this dot to this dot, jumping over one position. And then you do the usual element wise product and summing and that gives you, it turns out 100. And now we're going to do that again and make the blue box jump over by two steps. So you end up there and that gives you 83. And now when you go to the next row, you again actually take two steps instead of one step. So going to move the blue box over over there. Notice how we're skipping over one of the positions. And then this gives you 69. And now you gain step over two steps, this gives you 91, and so on, it's 127. And then for the final row, 44, 72 and 74. So in this example we convolve with a 7 by 7 matrix, with a 3 by 3 matrix and we get a 3 by 3 output. So the input and output dimensions turns out to be governed by the following formula. If you have an n by n image that you convolve with an f by F filter, and if you use padding P and stride S. So in this example s is equal to 2, then you end up with an output that is n +2p +f. And now because you're stepping s steps at a time, instead of just one step at a time, you know, you now divide by S +1 and then by the same thing. So in our example we have seven plus zero minus three divided by two. That's a stride plus one equals, let's see, that's four over two plus one equals three, which is why we wound up with this three by three output. Now just one last detail, which is what if this fraction is not an integer? Um, in that case we're going to round this down. So this Notation denotes the floor of something. So this right, this is also called the floor of Z. It means taking Z and rounding down to the nearest integer. And if the way this is implemented is that you take this type of blue box multiplication only if the blue box is fully contained within the image or the image plus the padding, and if any of this blue box kind of part of it hangs outside, then you just do not do that computation. Then it turns out that if that's a Convention, that your 3x3 filter must lie entirely within your image or the image plus the padding region before there's a corresponding output generator. If that's a convention, then the right thing to do to compute the output dimension is to round down in case this N +2P +F over S is not an integer. So just to summarize the dimensions, if you have an n by n matrix or n by N image that you convolve with an F by F matrix, an F by F filter with padding pnstri s, then the output size will have this dimension. And you know, it is nice we can choose all of these numbers so that that is an integer. Although sometimes you don't have to do that. And rounding down is is just fine as well. But please feel free to work through a few examples of values of n, f, P and S for yourself to convince yourself if you want, that this formula is correct for the output size. Now, before moving on, there is a technical comment I want to make about cross correlations versus convolutions. And this won't affect what you have to do to implement convolutional neural networks, but they depending on if you read a different math textbook or signal processing textbook. There is one other possible inconsistency in the notation, which is that if you look at a typical math textbook, the way that the convolution is defined, before doing the element wise product and summing, there's actually one other step that you would first take, which is to convolve this 6 by 6 matrix with the 3 by 3 filter. You at first take the 3 by 3 filter and and flip it on the horizontal as well as the vertical axes. So this 3, 4, 5, 1, 02 minus 197 would become 3 goes here, 4 goes there, 5 goes there and then the second row becomes this 102 minus 1, 9, 7. But this is really taking the 3 by 3 filter and mirroring it both on the vertical and horizontal axes. And then it was this flipped matrix that you would then copy over Here. So to compute the output you would take 2 times 7 plus 3 times 2 plus 7 times 5 and so on. And you actually multiply out the elements of this flipped matrix in order to compute the upper left hand most element of the, you know, of the four by four output as follows. And then you take those nine numbers and you'll ship them over by one, shift them over by one, and so on. So the way we've defined the convolution operation in these videos is that with skipped this mirroring operation and technically what we're actually doing, really the operation we've been using for the last few videos is sometimes cross correlation instead of convolution. But in the deep learning literature, by convention we just call this the convolution operation. So just to summarize by convention, in machine learning we usually do not bother with this flipping operation. And technically this operation is maybe better call it cross correlation. But most of the deep learning literature just causes the convolution operator, um, and so I'm gonna use that convention in these videos as well. And if you read, um, a lot of the machine learning literature, you find most people just call this the convolution operator without bothering to use these flips. Um, and it turns out that in signal processing or in certain branches of mathematics, doing the flipping in the definition of convol causes a convolution operator to enjoy this property that A convolved with B convolved with C is equal to A convolved with B convolved with C. And this is called associativity in mathematics. And this is nice for some signal processing applications, but for deep neural networks it really doesn't matter. And so omitting this double mirroring operation just simplifies the code and makes the neural networks work just as well. And by convention most of us just call this convolution, even though the mathematicians prefer to call this cross correlation sometimes. But this should not affect anything you have to implement in the programming exercises and should not affect your ability to read and understand the deep learning literature. So you've now seen how to carry out convolutions, and you've seen how to use padding as well as strides for convolutions. But so far all we've been using is convolutions over matrices, like over a six by six matrix. In the next video you see how to carry out convolutions over volumes. And this will make what you can do with convolutions suddenly much more powerful. Let's go on to the next video.