2237568 Arda Karaman CENG501 - Spring2022 - PA2 - Task 1 - Naive Convolution and Pooling.ipynb

{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"2237568 Arda Karaman CENG501 - Spring2022 - PA2 - Task 1 - Naive Convolution and Pooling.ipynb","provenance":[{"file_id":"1KsxBw2eKH_gPgSy-_W3nK6utB0HuTwJh","timestamp":1652992914659}],"collapsed_sections":[],"toc_visible":true},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"markdown","metadata":{"id":"-N8A5UYiE4L7"},"source":["# Task 1: Naive Convolution and Pooling\n","# CENG501 - Spring 2022 - PA2\n","\n","In this task, you will implement convolution and pooling operations in a naive way without using any matrix-vector multiplication. \n","\n","*Disclaimer: Some components are adapted or taken from [CS231n](https://cs231n.github.io/) materials.*"]},{"cell_type":"markdown","metadata":{"id":"pfmBLQj5OAnT"},"source":["## 1 Import the Modules\n","\n","As usual, let us import the modules that we will use."]},{"cell_type":"code","metadata":{"id":"DSIkrblIOA_R","executionInfo":{"status":"ok","timestamp":1654374939336,"user_tz":-180,"elapsed":363,"user":{"displayName":"Arda Karaman","userId":"09649945184885111594"}}},"source":["import matplotlib.pyplot as plt # For plotting\n","import numpy as np              # NumPy, for working with arrays/tensors \n","import os                       # Built-in library for filesystem access etc.\n","import pickle                   # For (re)storing Python objects into (from) files \n","import time                     # For measuring time\n","\n","%matplotlib inline\n","plt.rcParams['figure.figsize'] = [12, 8]\n","plt.rcParams['figure.dpi'] = 100 # 200 e.g. is really fine, but slower"],"execution_count":1,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"e6NQtyenE8kd"},"source":["## 2 Naive Implementation of Convolution\n","\n","Here, we will implement 2D convolution using only for/while loops; in other words, **NO** vector/matrix multiplications."]},{"cell_type":"markdown","metadata":{"id":"VF-mlexaVVAf"},"source":["### 2.1 Convolution Feedforward\n","\n","\n"]},{"cell_type":"code","metadata":{"id":"i-8UbQIsJkIj","executionInfo":{"status":"ok","timestamp":1654377728359,"user_tz":-180,"elapsed":385,"user":{"displayName":"Arda Karaman","userId":"09649945184885111594"}}},"source":["def conv_forward_naive(x, w, b, stride, padding):\n","    \"\"\"\n","    The input consists of N samples, each with C channels, height H and\n","    width W. We convolve each input with F different filters, where each filter\n","    spans all C channels and has height FH and width FW.\n","\n","    Input:\n","    - x: Input data of shape (N, C, H, W)\n","    - w: Filter weights of shape (F, C, FH, FW)\n","    - b: Biases, of shape (F,)\n","    - stride: The number of pixels between adjacent receptive fields in the\n","        horizontal and vertical directions.\n","    - padding: The number of pixels that will be used to zero-pad the input. \n","        \n","    During padding, 'padding'-many zeros should be placed symmetrically (i.e equally on both sides)\n","    along the height and width axes of the input. Be careful not to modfiy the original\n","    input x directly.\n","\n","    Returns a tuple of:\n","    - out: Output data, of shape (N, F, H', W') where H' and W' are given by\n","      H' = 1 + (H + 2 * padding - FH) / stride\n","      W' = 1 + (W + 2 * padding - FW) / stride\n","    - cache: (x_pad, w, b, stride, padding)\n","    \"\"\"\n","\n","    # Layer output:\n","    out = None\n","    \n","    # Get values for the dimensions:\n","    N, C, H, W = x.shape\n","    F, C, FH, FW = w.shape\n","\n","    # Just to make sure \n","    if (H - FH + 2 * padding) % stride != 0: \n","      return ValueError(\"Filters do not align horizontally\")\n","    if (W - FW + 2 * padding) % stride != 0: \n","      return ValueError(\"Filters do not align vertically\")\n","\n","    ###########################################################################\n","    # TODO: Implement the convolutional forward pass. You cannot use          #\n","    # vector or matrix multiplications here. Be careful about stride.         #\n","    # Hints:                                                                  #\n","    #  (1) You can use the function np.pad for padding.                       #\n","    #  (2) You will have such a nested loop structure here:                   #\n","    #    - loop over N samples                                                #\n","    #      - loop over F filters                                              #\n","    #        - loop over rows of x_pad                                        #\n","    #          - loop over cols of x_pad                                      #\n","    #            - loop over kernel rows                                      #\n","    #              - loop over kernel cols                                    #\n","    #                - loop over channels                                     #\n","    ###########################################################################\n","    \n","    to_fields = lambda x: np.lib.stride_tricks.sliding_window_view(x, (FW,FH,C,N))\n","\n","    x_pad = np.pad(x, ((0,0), (0,0), (padding, padding), (padding, padding)), 'constant')\n","\n","    _H = 1 + (H + 2 * padding - FH) // stride\n","    _W = 1 + (W + 2 * padding - FW) // stride\n","    \n","    w_row = w.reshape(F, -1)\n","    x_col = to_fields(x_pad.T).T[...,::stride,::stride].reshape(N, C*FH*FW, -1)\n","\n","    out = np.zeros((N, F, _H, _W))\n","    print(out.shape)\n","\n","    for n in range(N):\n","        for f in range(F):\n","            for j in range(0, _H):\n","                for i in range(0, _W):\n","                    pass\n","\n","    out = (w_row @ x_col).reshape(N, F, _H, _W) + np.expand_dims(b, axis=(2,1))\n","    print(out.shape)\n","    ###########################################################################\n","    #                             END OF YOUR CODE                            #\n","    ###########################################################################\n","    cache = (x_pad, w, b, stride, padding)\n","    return out, cache"],"execution_count":22,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"JQk5fjckWhnR"},"source":["### 2.2 Convolution Feedforward Check \n","\n","Let us quickly check your implementation with some known values. Your output should differ by $\\sim 10^{-8}$."]},{"cell_type":"code","metadata":{"id":"kWO4tshRIAxq","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1654377730364,"user_tz":-180,"elapsed":373,"user":{"displayName":"Arda Karaman","userId":"09649945184885111594"}},"outputId":"609b4106-b31d-420b-c17a-41704751e183"},"source":["\n","x_shape = (2, 3, 4, 4)\n","w_shape = (3, 3, 4, 4)\n","x = np.linspace(-0.1, 0.5, num=np.prod(x_shape)).reshape(x_shape)\n","w = np.linspace(-0.2, 0.3, num=np.prod(w_shape)).reshape(w_shape)\n","b = np.linspace(-0.1, 0.2, num=3)\n","\n","stride = 2\n","padding = 1\n","out, _ = conv_forward_naive(x, w, b, stride, padding)\n","correct_out = np.array([[[[-0.08759809, -0.10987781],\n","                           [-0.18387192, -0.2109216 ]],\n","                          [[ 0.21027089,  0.21661097],\n","                           [ 0.22847626,  0.23004637]],\n","                          [[ 0.50813986,  0.54309974],\n","                           [ 0.64082444,  0.67101435]]],\n","                         [[[-0.98053589, -1.03143541],\n","                           [-1.19128892, -1.24695841]],\n","                          [[ 0.69108355,  0.66880383],\n","                           [ 0.59480972,  0.56776003]],\n","                          [[ 2.36270298,  2.36904306],\n","                           [ 2.38090835,  2.38247847]]]])\n","\n","def rel_error(x, y):\n","  \"\"\" returns relative error \"\"\"\n","  return np.max(np.abs(x - y) / (np.maximum(1e-8, np.abs(x) + np.abs(y))))\n","\n","# Compare your output to ours; difference should be around e-8\n","print('Testing conv_forward_naive')\n","print('difference: ', rel_error(out, correct_out))"],"execution_count":23,"outputs":[{"output_type":"stream","name":"stdout","text":["(2, 3, 2, 2)\n","(2, 3, 2, 2)\n","Testing conv_forward_naive\n","difference:  2.2121476575931688e-08\n"]}]},{"cell_type":"markdown","metadata":{"id":"r4DXOOvBWSjE"},"source":["### 2.3 Convolution Gradient\n","\n","Now, let us implement the gradient. Again, you are **NOT** allowed to use any vector/matrix multiplication here."]},{"cell_type":"code","metadata":{"id":"5ewZb1xkroZX","executionInfo":{"status":"ok","timestamp":1654376638725,"user_tz":-180,"elapsed":508,"user":{"displayName":"Arda Karaman","userId":"09649945184885111594"}}},"source":["def conv_backward_naive(dout, cache):\n","    \"\"\"\n","    A naive implementation of the backward pass for a convolutional layer.\n","\n","    Inputs:\n","    - dout: Upstream derivatives.\n","    - cache: A tuple of (x, w, b, stride, padding) as in conv_forward_naive\n","    \n","    Returns a tuple of:\n","    - dx: Gradient with respect to x. \n","    - dw: Gradient with respect to w\n","    - db: Gradient with respect to b\n","    \"\"\"\n","    dx, dw, db = None, None, None\n","    \n","    ###########################################################################\n","    # TODO: Implement the convolutional backward pass.                        #\n","    ###########################################################################\n","    x_pad, w, b, stride, padding = cache\n","    F, C, HF, WF = w.shape\n","    N, _, HO, WO = dout.shape\n","    db = np.sum(dout, axis=(0,2,3))\n","\n","    dw = np.zeros(shape=w.shape)\n","    dx = np.zeros(shape=x.shape)\n","    dx_pad = np.pad(dx, [(0,0), (0,0), (pad, pad), (pad, pad)])\n","\n","\n","    for n in range(N):\n","      for f in range(F):\n","        for i in range(HO):\n","            for j in range(WO):\n","\n","    ###########################################################################\n","    #                             END OF YOUR CODE                            #\n","    ###########################################################################\n","    return dx, dw, db"],"execution_count":12,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"ka7ev5-BwTSc"},"source":["### 2.4 Convolution Gradient Check\n","\n","Let us check the gradient. You should see differences lower than $10^{-9}$."]},{"cell_type":"code","metadata":{"id":"FSk5T7cOwUtC","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1654376642313,"user_tz":-180,"elapsed":414,"user":{"displayName":"Arda Karaman","userId":"09649945184885111594"}},"outputId":"b201e4f4-4cae-4071-9381-4ceec0af0ca6"},"source":["def eval_numerical_gradient_array(f, x, df, h=1e-5):\n","    \"\"\"\n","    Evaluate a numeric gradient for a function that accepts a numpy\n","    array and returns a numpy array.\n","    \"\"\"\n","    grad = np.zeros_like(x)\n","    it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])\n","    while not it.finished:\n","        ix = it.multi_index\n","\n","        oldval = x[ix]\n","        x[ix] = oldval + h\n","        pos = f(x).copy()\n","        x[ix] = oldval - h\n","        neg = f(x).copy()\n","        x[ix] = oldval\n","\n","        grad[ix] = np.sum((pos - neg) * df) / (2 * h)\n","        it.iternext()\n","    return grad\n","\n","np.random.seed(231)\n","x = np.random.randn(4, 3, 5, 5)\n","w = np.random.randn(2, 3, 3, 3)\n","b = np.random.randn(2,)\n","dout = np.random.randn(4, 2, 5, 5)\n","stride = 1\n","pad = 1\n","\n","dx_num = eval_numerical_gradient_array(lambda x: conv_forward_naive(x, w, b, stride, pad)[0], x, dout)\n","dw_num = eval_numerical_gradient_array(lambda w: conv_forward_naive(x, w, b, stride, pad)[0], w, dout)\n","db_num = eval_numerical_gradient_array(lambda b: conv_forward_naive(x, w, b, stride, pad)[0], b, dout)\n","\n","out, cache = conv_forward_naive(x, w, b, stride, pad)\n","dx, dw, db = conv_backward_naive(dout, cache)\n","\n","# Your errors should be around e-8 or less.\n","print('Testing conv_backward_naive function')\n","print('dx error: ', rel_error(dx, dx_num))\n","print('dw error: ', rel_error(dw, dw_num))\n","print('db error: ', rel_error(db, db_num))"],"execution_count":13,"outputs":[{"output_type":"stream","name":"stdout","text":["Testing conv_backward_naive function\n","dx error:  7.990010601910952e-09\n","dw error:  2.678293773461729e-10\n","db error:  3.8835192329918934e-11\n"]}]},{"cell_type":"markdown","metadata":{"id":"nj-avor_VY-O"},"source":["## 3 Pooling\n","\n","Now, we implement pooling, max-pooling to be specific. Again, **no** use of vector/matrix multiplications."]},{"cell_type":"markdown","metadata":{"id":"iyEDErauzUuw"},"source":["### 3.1 Pooling Feedforward"]},{"cell_type":"code","metadata":{"id":"V6SOEQieWbh8"},"source":["def max_pool_forward_naive(x, stride, PH, PW):\n","    \"\"\"\n","    A naive implementation of the forward pass for a max-pooling layer.\n","    Inputs:\n","    - x: Input data, of shape (N, C, H, W)\n","    - stride: The distance between adjacent pooling regions\n","    - PH: The height of each pooling region\n","    - PW: The width of each pooling region\n","    \n","    Returns a tuple of:\n","    - out: Output data, of shape (N, C, H', W') where H' and W' are given by\n","      H' = 1 + (H - pool_height) / stride\n","      W' = 1 + (W - pool_width) / stride\n","    - cache: (x, pool_param)\n","    \"\"\"\n","    out = None\n","    ###########################################################################\n","    # TODO: Implement the max-pooling forward pass                            #\n","    ###########################################################################\n","    N, C, H, W = x.shape\n","\n","    _H = 1 + (H - PH) // stride\n","    _W = 1 + (W - PW) // stride\n","\n","    out = np.zeros((N, C, _H, _W))\n","\n","    for n in range(N):\n","        for c in range(C):\n","            for i in range(_H):\n","                for j in range(_W):\n","                    out[n,c,i,j] = np.max( x[n, c, (stride * i) : (stride * i) + PH, (stride * j) : (stride * j) + PW ] )\n","\n","    ###########################################################################\n","    #                             END OF YOUR CODE                            #\n","    ###########################################################################\n","    cache = (x, stride, PH, PW)\n","    return out, cache"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"1JNpYSV8EFF3"},"source":["### 3.2 Pooling Feedforward Check\n","\n","You should observe ~$10^{-8}$ difference."]},{"cell_type":"code","metadata":{"id":"lSlsvDgEEFgO"},"source":["x_shape = (2, 3, 4, 4)\n","x = np.linspace(-0.3, 0.4, num=np.prod(x_shape)).reshape(x_shape)\n","stride, PH, PW = (2, 2, 2)\n","\n","out, _ = max_pool_forward_naive(x, stride, PH, PW)\n","\n","correct_out = np.array([[[[-0.26315789, -0.24842105],\n","                          [-0.20421053, -0.18947368]],\n","                         [[-0.14526316, -0.13052632],\n","                          [-0.08631579, -0.07157895]],\n","                         [[-0.02736842, -0.01263158],\n","                          [ 0.03157895,  0.04631579]]],\n","                        [[[ 0.09052632,  0.10526316],\n","                          [ 0.14947368,  0.16421053]],\n","                         [[ 0.20842105,  0.22315789],\n","                          [ 0.26736842,  0.28210526]],\n","                         [[ 0.32631579,  0.34105263],\n","                          [ 0.38526316,  0.4       ]]]])\n","\n","# Compare your output with ours. Difference should be on the order of e-8.\n","print('Testing max_pool_forward_naive function:')\n","print('difference: ', rel_error(out, correct_out))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"m_d7rzkMWb-0"},"source":["### 3.3 Pooling Gradient\n","\n","Again, **no** use of vector/matrix multiplications."]},{"cell_type":"code","metadata":{"id":"RzVNQ60RWeTR"},"source":["def max_pool_backward_naive(dout, cache):\n","    \"\"\"\n","    A naive implementation of the backward pass for a max-pooling layer.\n","    Inputs:\n","    - dout: Upstream derivatives\n","    - cache: A tuple of (x, stride, PH, PW) as in the forward pass.\n","    Returns:\n","    - dx: Gradient with respect to x\n","    \"\"\"\n","    dx = None\n","    ###########################################################################\n","    # TODO: Implement the max-pooling backward pass                           #\n","    ###########################################################################\n","    dx = np.zeros_like(x)\n","    x, stride, PH, PW = cache\n","    N, C, H, W = x.shape\n","\n","    _H = 1 + (H - PH) // stride\n","    _W = 1 + (W - PW) // stride\n","\n","    \n","\n","    for n in range(N):\n","        for c in range(C):\n","            for j in range(_H):\n","                for i in range(_W):\n","                    ind = np.argmax(x[n, c, j*stride:j*stride+PH, i*stride:i*stride+PW])\n","                    ind1, ind2 = np.unravel_index(ind, (PH, PW))\n","                    dx[n, c, j * stride : j * stride + PH, i * stride : i * stride + PW][ind1, ind2] = dout[n, c, j, i]\n","    ###########################################################################\n","    #                             END OF YOUR CODE                            #\n","    ###########################################################################\n","    return dx"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"ZIebBQp0Ejzt"},"source":["### 3.4 Pooling Gradient Check\n","\n","You should observe ~$10^{-12}$ difference."]},{"cell_type":"code","metadata":{"id":"-Rsbl6GlEmF-"},"source":["np.random.seed(231)\n","x = np.random.randn(3, 2, 8, 8)\n","dout = np.random.randn(3, 2, 4, 4)\n","stride, PH, PW = (2, 2, 2)\n","\n","dx_num = eval_numerical_gradient_array(lambda x: max_pool_forward_naive(x, stride, PH, PW)[0], x, dout)\n","\n","out, cache = max_pool_forward_naive(x, stride, PH, PW)\n","dx = max_pool_backward_naive(dout, cache)\n","\n","# Your error should be on the order of e-12\n","print('Testing max_pool_backward_naive function:')\n","print('dx error: ', rel_error(dx, dx_num))"],"execution_count":null,"outputs":[]}]}