4
$\begingroup$

In Kaiming He's resnet presentation on slide 40 he says, "lower time complexity than VGG-16/19." Why is this the case, when resnet is much deeper?

$\endgroup$
  • 1
    $\begingroup$ You would almost certainly have better success emailing He. Most people are very enthusiastic about discussion work that is dear to them. $\endgroup$ – Matthew Drury May 17 '17 at 18:50
8
$\begingroup$

Updated in order to address @mrgloom's comment

In my original answer, I stated that VGG-16 has roughly 138 million parameters and ResNet has 25.5 million parameters and because of this it's faster, which is not true. Number of parameters reduces amount of space required to store the network, but it doesn't mean that it's faster. Resnet is faster than VGG, but for a different reason.

Also, as @mrgloom pointed out that computational speed my depend heavily on the implementation. Below I'll discuss simple computational case. Also, I'll avoid counting FLOPs for activation functions and pooling layers, since they have relatively low cost.

First of all, speed of the convolution will depend on the size of the input. Let's say you have gray colored (1 channel) 100x100 image and you apply one 3x3 convolution filter with stride 1 and 0 padding. This operation will require you ~163k FLOPs. It's easy to calculate. If you know how convolution works you should know that from the 100x100 image you will get 98x98 (using set up described above). And in order to compute each value from the 98x98 output image you need to do 9 multiplication and 8 additions, which is in total corresponds to 17 operations per value. If you combine everything you get 98 * 98 * 17 and it equals to 163,268. Now, imagine you apply the same filter on the larger image, let's say 200x200. Image has 4 times bigger area and therefor you'll get roughly 4 times more FLOPs.

Now, I'll start with the comparison between VGG19 and Resnet 34, since that's the image that they use in the original paper.

In the figure 3, they break down architecture into the set of blocks marked with different colors. At the end each block reduces height and width by a factor of two. In the first two layers Resnet manages to reduces hight and width of the image by a factor of 4.

vgg-vs-resnet-block-1

From the VGG19 you can see that first two layers apply convolution on top of the full 224x224 image which is quite expensive. If you apply similar calculations as I did above you will find that first layer does ~170M FLOPs, but it produces 64x224x224 output from the 3x224x224 image. Since layer applies the same conv filter you should see that number of FLOPs should be close to 170M * (64 / 3). In fact, it's almost 3.7B FLOPs. This layer alone has roughly as many FLOPs as whole Resnet-34. In order to avoid this computational problem in the Resnet they address this issue in the first layer. It reduces number of row and columns by a factor of 2 and it uses only 240M FLOPs and next max pooling operation applies another reduction by factor of 2.

In contrast, these four convolutional layers in the VGG19 make around 10B FLOPs.

Next, convolutional filters in the Resnet build up slowly. You can see that they use less kernels compare to the VGG, but they have more of them stacked alternating between convolutional operation and non-linear activation functions. That's another thing that was pointed out by @mrgloom. They exploited idea of using thinner, but deeper networks.

vgg-vs-resnet-block-2

Next Resnet layers follow the same strategy, trying to make it thinner and deeper.

In addition, from Table 1 in the paper you can notice that convolutional blocks for Renet 50, Resnet 101 and Resnet 152 look a bit different. That's how it looks visually.

It was used in order to reduce number of operations even more, while using networks with larger number of filters in the convolutional layers. The idea of 1x1 convolutional layer allow to reduce channel depth before applying 3x3 convolution and upscale it back afterwords.

$\endgroup$
  • $\begingroup$ can you tell me that I'm right, that VGG uses much more channels on bigger image dimensions, while ResNet uses the bigger channel layers on much lower image resolution (deeper network stages): e.g. VGG: 256 channels on image resolution 56x56 and 512 channels from resolution 28x28 on, while ResNet uses "only" 64 channels on 56x56, 128 channels on 28x28, 256 channels on 14x14 and 512 channels only on 7x7 images. Sure, the dense layers differene is there too, but those are "only" less than 3 million parameters in VGG? $\endgroup$ – Micka May 13 '18 at 13:29
  • $\begingroup$ @Micka It's not 3 million, for vgg16 it's 123 million out of 138 which is roughly 90% of the parameters in the network. $\endgroup$ – itdxer May 13 '18 at 15:35
  • $\begingroup$ oh yes, you are right, I missed the channels of the last conv layer and had an additional factor 10 error. But computation times (although not the number of parameters) are still dominated by the conv layers, which sum up to > 1.5E+10 FLOPs compared to < 1.0E+9 FLOPs for the fc layers (with flop = add+mul) $\endgroup$ – Micka May 13 '18 at 19:05
  • $\begingroup$ resnet paper says that resnet has less flops compare to vgg: arxiv.org/pdf/1512.03385.pdf. For resnet-50 it has 3.8 billion vs 15.3 billion for vgg16 $\endgroup$ – itdxer May 14 '18 at 17:39
  • $\begingroup$ few last dense layers which are computationally expensive dense layers are not computationally expensive they just need more memory to store weights. Also in practice speed of ResNet50 will be limited by the fact that lots of layers will create additional overhead, so it can be implementation dependent. And, yes, ResNets are thin and deep, for example here is the work exploring wider variants arxiv.org/pdf/1605.07146.pdf $\endgroup$ – mrgloom Oct 20 '18 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.