9

I looked to the following examples from Keras:

MLP in MNIST: https://github.com/fchollet/keras/blob/master/examples/mnist_mlp.py

CNN in MNIST: https://github.com/fchollet/keras/blob/master/examples/mnist_cnn.py

I run both in Theano on CPU. In the MLP I have a mean time of approximately 16s per epoch with a total of 669,706 parameters:

Layer (type)                 Output Shape              Param #   
=================================================================
dense_33 (Dense)             (None, 512)               401920    
_________________________________________________________________
dropout_16 (Dropout)         (None, 512)               0         
_________________________________________________________________
dense_34 (Dense)             (None, 512)               262656    
_________________________________________________________________
dropout_17 (Dropout)         (None, 512)               0         
_________________________________________________________________
dense_35 (Dense)             (None, 10)                5130      
=================================================================
Total params: 669,706.0
Trainable params: 669,706.0
Non-trainable params: 0.0

In the CNN, I eliminated the last hidden layer from the original code. I also changed the optimizer to rmsprop to make both cases comparable, leaving the following architecture:

Layer (type)                 Output Shape              Param #   
=================================================================
conv2d_36 (Conv2D)           (None, 26, 26, 32)        320       
_________________________________________________________________
conv2d_37 (Conv2D)           (None, 24, 24, 64)        18496     
_________________________________________________________________
max_pooling2d_17 (MaxPooling (None, 12, 12, 64)        0         
_________________________________________________________________
dropout_22 (Dropout)         (None, 12, 12, 64)        0         
_________________________________________________________________
flatten_17 (Flatten)         (None, 9216)              0         
_________________________________________________________________
dense_40 (Dense)             (None, 10)                92170     
=================================================================
Total params: 110,986.0
Trainable params: 110,986.0
Non-trainable params: 0.0

However, the average time here is of approximately 340 s per epoch! Even though there are six times less parameters!

To check more on this, I reduced the number of filters per layer to 4, leaving the following architecture:

Layer (type)                 Output Shape              Param #   
=================================================================
conv2d_38 (Conv2D)           (None, 26, 26, 4)         40        
_________________________________________________________________
conv2d_39 (Conv2D)           (None, 24, 24, 4)         148       
_________________________________________________________________
max_pooling2d_18 (MaxPooling (None, 12, 12, 4)         0         
_________________________________________________________________
dropout_23 (Dropout)         (None, 12, 12, 4)         0         
_________________________________________________________________
flatten_18 (Flatten)         (None, 576)               0         
_________________________________________________________________
dense_41 (Dense)             (None, 10)                5770      
=================================================================
Total params: 5,958.0
Trainable params: 5,958.0
Non-trainable params: 0.0

Now the time is of 28 s per epoch even though there are roughly 6000 parameters!!

Why is this? Intuitively, the optimization should only depend on the number of variables and the calculation of the gradient (which due to same batch size should be similar).

Some light on this? Thank you

4
  • 3
    Your intuition is wrong. Look at the number of computations that you have to make. In a dense layer, each variable is used once in one multiplication (considering only a forward pass here), it multiplies the weights with the input and that's it. With the convolution on the other hand, your kernel is multiplied as many times as there are output values, this means that for your first layer, one kernel is multiplied 26*26 times, and you have 32 of those (each with 10 variables if I get it right). So the computation power needed here is not equal to the number of variables.
    – Nassim Ben
    Commented Mar 30, 2017 at 15:23
  • Thanks @nassim , I understand that. However, following that logic in the last network the first two convolutional layers would perform 26*26*4+26*26*4=5408 computations, which added to the dense layer computations gives roughly 12000 computations. That number is not even comparable to the 670000 computations of the first network, so why does the last network time per epoch is so similar to the first network? Commented Mar 30, 2017 at 16:52
  • 2
    1) you forget that kernel multiplication is not only 'one computation' its an elementwise matrix multiplication. So if you have 10 elements in your kernel --> 26*26*4*10. 2) im not an expert in that area but i think that doing all those kernels multiplications is more expensive than just one big matrix multiplication... idk how it happens internally but i see a lot more of I/O activity happening on your computing unit. Dense is really efficient, load the two matrices on gpu/cpu, compute, thats it.
    – Nassim Ben
    Commented Mar 30, 2017 at 16:57
  • @nassim You are right, I forgot the size of the kernel. However that gives 60000 computations, more than 10 times less than the MLP network. I guess that it is implemented as a sparse matrix with shared weights, thus being able to be loaded in gpu as in the MLP for the forward pass. After all, the features of CNN's is sparse connectivity and shared weights, isn't the purpose of that precisely to make training more efficient for the same number of neurons, apart from avoiding overfitting? Commented Mar 30, 2017 at 21:42

2 Answers 2

5

I assume the kernel size is (3x3) for all the convolution operations and input 2D array channel size as 3.

For conv2d_36 you would have:

  • 3 * 32 = number of operation for all the channels
  • 26 * 26 = number of convolution operation per channel
  • 3 * 3 = number of multiplication per convolution

So, excluding all the summation(bias + conv internal),

  • For conv2d_36 you would have 3 * 32 * 26 * 26 * 3 * 3 =~ 585k multiplication operations
  • For conv2d_37, similarly 32 * 64 * 24 * 24 * 3 * 3 =~ 10.6M multiplication operations
  • For dense_40 as there is no convolution, it would be equal to 9216 * 10 = 92k multiplication operations.

When we sum up all of them, there are ~11.3M single multiplication operations for second model with CNN.

On the other hand, if we flatten it and apply MLP,

  • For dense_33 layer, there will be 28 * 28 * 3 * 512 = 1.2M multiplication operations
  • For dense_34 layer, there will be 512 * 512 = 262k multiplication operations
  • For dense_35 layer, there will be 512 * 10 = 5k multiplication operations

When we sum up all of them, there are ~1.5M single multiplication operations for first model with MLP.

Hence, just the multiplications of CNN model are ~7.5 times more than MLP model. Considering the overhead within the layers, other operation costs like summation and memory copy/access operations it seems totally reasonable for CNN model to be as slow as you mentioned.

1

The convolution operation are much more complex than dense layer. Convolution is the process of adding each element of the image to its local neighbors, weighted by the kernel. Every convolution is essentially a multiple nested loop. This means that dense layer needs a fraction of the time respect to convolutional layers. Wikipedia has an enlightening example of the convolution operation.

1
  • 1
    Thanks for the answer. However, a convolution can be implemented as a layer with sparse connections and weight sharing. In that context, the operations for forward pass are essentially the same than for the dense case (just a matrix multiplication). For the backpropagation, maybe the complexity varies due to weight sharing, but... that much? Why? I thought the whole purpose of CNNs was to reduce the number of parameters and operations by leveraging spatial correlations in order to reduce overfitting, but also improve efficiency. Commented Apr 2, 2017 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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