3
$\begingroup$

The below code is a max pooling algorithm being used in a CNN. The issue I've been facing is that it is offaly slow given a high number of feature maps. The reason for its slowness is quite obvious-- the computer must perform tens of thousands of iterations on each feature map. So, how do we decrease the computational complexity of the algorithm?

('inputs' is a numpy array which holds all the feature maps and 'pool_size' is a tuple with the dimensions of the pool.)

def max_pooling(inputs, pool_size):

    feature_maps = []
    for feature_map in range (len(inputs)):
        feature_maps.append([])
        for i in range (0, len(inputs[feature_map]) - pool_size[0], pool_size[0]):
            for j in range (0, len(inputs[feature_map]) - pool_size[0], pool_size[0]):    
                feature_maps[-1].append(np.array(max((inputs[feature_map][j:j+pool_size[0], i:i+pool_size[0]]).flatten())))

    return feature_maps
$\endgroup$
1
$\begingroup$

The reason for its slowness is quite obvious-- the computer must perform tens of thousands of iterations on each feature map. So, how do we decrease the computational complexity of the algorithm?

In terms of computational complexity / algorithm, there is not a lot to gain; max pooling simply has to go through all the feature maps to find the maximum numbers in each of the sections to be "merged/pooled" by taking the max.

There likely is a lot to gain in terms of implementation though. The current implementation is entirely in pure Python, and pure Python is notoriously slow. Those kinds of loops can be run significantly faster using numpy operations rather than manual Python loops. Such operations tend to be much faster due to:

  1. running optimized C code rather than Python code, and
  2. in some cases, using vectorized operations to perform multiple similar computations at different indices simultaneously, rather than doing them one-by-one

I did not yet try to "translate" your pure python code into python code using numpy. However, some examples of numpy-based implementations can be found in various answers to this question on StackOverflow.


I assume that your choice to manually implement things like max pooling is because you want to learn about implementing it / understand it better. If, instead, your goal is simply to get something running as quickly as possible, it may be a good idea to look into using a framework such as Tensorflow or PyTorch. These come with efficient implementations of many things you'll want for Neural Networks, including Max Pooling.

$\endgroup$
  • 2
    $\begingroup$ Thank you so much! That makes a great deal of sense. The code does work properly, but I was able to make it considerably faster by implementing Numpy functions. $\endgroup$ – Chandler Supple Jul 25 '18 at 17:41

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.