batch_conv.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Setting up the data\n",
    "\n",
    "The image is in the format: batch_size, width, height, colors\n",
    "\n",
    "The filter is: width, height, in_colors, out_colors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# dimensions of the image\n",
    "batch_size, dim_x, dim_y, colors=2, 10, 11, 5\n",
    "\n",
    "# dimensions of the filter\n",
    "kernel_x, kernel_y, in_colors, out_colors=2, 3, colors, 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# using random numbers to fill the image and the weights\n",
    "im=np.random.rand(batch_size, dim_x, dim_y, colors)\n",
    "weights=np.random.rand(kernel_x, kernel_y, in_colors, out_colors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Defining a convolution operation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def convolve(im, weights):\n",
    "    \n",
    "    # get the dimensions of image and kernel\n",
    "    kernel_x, kernel_y, in_colors, out_colors=weights.shape\n",
    "    batch_size, dim_x, dim_y, colors=im.shape\n",
    "    \n",
    "    # allocate an output array\n",
    "    # the batch_size stays the same, the number of colors is specified in the shape of the filter\n",
    "    # but the x and y dimensions of the output need to be calculated\n",
    "    # the formula is:\n",
    "    # out_x = in_x - filter_x +1\n",
    "    out=np.empty((batch_size, dim_x-kernel_x+1, dim_y-kernel_y+1, out_colors))\n",
    "    \n",
    "    # look at every coordinate in the output\n",
    "    for i in range(out.shape[1]):\n",
    "        for j in range(out.shape[2]):\n",
    "            \n",
    "            # at this location, slice a rectangle out of the input image\n",
    "            # the batch_size and the colors are retained\n",
    "            # crop has the shape: batch_size, kernel_x, kernel_y, in_colors\n",
    "            crop=im[:,i:i+kernel_x, j:j+kernel_y]\n",
    "            \n",
    "            # the values in crop will be multiplied by the weights\n",
    "            # look how the shapes match:\n",
    "            # crop:   batch_size, x, y, in_colors\n",
    "            # weights:            x, y, in_colors, out_colors\n",
    "            \n",
    "            # numpy can broadcast this, but ONLY if an extra dimension is added to crop\n",
    "            # crop now has the shape: batch_size, x, y, in_colors, 1\n",
    "            crop=np.expand_dims(crop, axis=-1)\n",
    "            \n",
    "            # numpy broadcast magic\n",
    "            # in parallel along the batch_size\n",
    "            # matches the x, y and in_colors dimensions and multiplies them pairwise\n",
    "            res=crop*weights\n",
    "            \n",
    "            # res has the shape: batch_size, x, y, in_colors, out_colors\n",
    "            # we want to sum along x, y, and in_colors\n",
    "            # those are the dimensions 1, 2, 3\n",
    "            # we want to keep the batch_size and the out_colors\n",
    "            res=np.apply_over_axes(np.sum, res, [1,2,3]).reshape(batch_size,-1)\n",
    "            \n",
    "            out[:,i,j]=res\n",
    "            \n",
    "    return out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Apply\n",
    "\n",
    "Use the new convolve function to compute the output of the convolution.\n",
    "Calculate an output value which will be used to test the backward pass later on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "out=convolve(im, weights)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# set up a random weight for every entry in the output\n",
    "debug_weights=np.random.rand(*out.shape)\n",
    "\n",
    "# multiply the output with the random weights, reduce it by summing everything\n",
    "# This scalar output value depends on every entry in the output\n",
    "# If you change an entry, the output value will change with the random weight\n",
    "# therefore, it is possible to identify which value in the output has changed\n",
    "debug_out=np.sum(out*debug_weights)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2472.7945262736876"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "debug_out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Backward pass\n",
    "\n",
    "The backward pass is a convolution with weights that are:\n",
    "1. mirrored along the x axis\n",
    "2. mirrored along the y axis\n",
    "3. transposed: in_colors and out_colors are switched\n",
    "\n",
    "This convolution has to be performed in a padded output.\n",
    "The gradients (output of this convolution) need to match the shape of the input.\n",
    "By applying the convolution, the x and y dimensions are reduced by (kernel_x-1) and (kernel_y-1) respectively.\n",
    "\n",
    "Before applying the convolution for the backward pass, the output will be padded with 2(kernel_x-1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "out_shape=out.shape\n",
    "\n",
    "# set up an array for the padded output\n",
    "padded=np.zeros((batch_size, out_shape[1]+2*(kernel_x-1), out_shape[2]+2*(kernel_y-1), out_colors))\n",
    "\n",
    "# copy the output to its center\n",
    "padded[:, kernel_x-1:kernel_x-1+out_shape[1], kernel_y-1:kernel_y-1+out_shape[2]]=debug_weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.image.AxesImage at 0x7f19ebbb7780>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAASYAAAD8CAYAAADaFgknAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAACx9JREFUeJzt3W+o3YV9x/H3Z7kxadJSO1bKTGTmgTiCdFouna3QB8ZR\n24ruwR4os7TbIE/W1pZCUfagz8ZgpbSw0hHsP2hQRuqYlK7q+ocx2KTXKK1J+kdsq9E4U7a10oGJ\n9LsH97gld4kJ5/czv6/9vV8Qcs/Jyfl98Hrf/s65x3tSVUhSJ78x9QBJ2sgwSWrHMElqxzBJascw\nSWrHMElqxzBJascwSWrHMElqZ+VCHuyibKmtbL+Qh5TUyPP858+q6o3nut0FDdNWtvP72XMhDymp\nkX+qAz89n9v5UE5SO4ZJUjuGSVI7hklSO4ZJUjuDwpTkhiQ/SPJ4kjvGGiVp3pYOU5JNwGeAdwG7\ngVuT7B5rmKT5GnLG9Fbg8ap6oqpOAPcAN48zS9KcDQnTDuCpUy4fXVx3miR7k6wlWTvJCwMOJ2ku\nXvEnv6tqX1WtVtXqZra80oeT9GtgSJieBi495fLOxXWSNMiQMH0HuDzJriQXAbcA940zS9KcLf0/\n8VbVi0k+ANwPbAI+X1WHRlsmabYG/XSBqvoa8LWRtkgS4Cu/JTVkmCS1Y5gktWOYJLVzQX+0bnf3\nP/Po1BOkQd55yVVTTxiFZ0yS2jFMktoxTJLaMUyS2jFMktoxTJLaMUyS2jFMktoxTJLaMUyS2jFM\nktoxTJLaMUyS2jFMktoxTJLaMUyS2jFMktoxTJLaMUyS2jFMktoxTJLaMUyS2jFMktoxTJLaMUyS\n2lk6TEkuTfKtJIeTHEpy+5jDJM3XkLcIfxH4aFUdTPI64OEkD1bV4ZG2SZqppc+YqupYVR1cfPw8\ncATYMdYwSfM1ynNMSS4DrgYeGuP+JM3bkIdyACR5LfAV4MNV9Ysz/PleYC/AVrYNPZykGRh0xpRk\nM+tR2l9V957pNlW1r6pWq2p1M1uGHE7STAz5rlyAzwFHquqT402SNHdDzpiuBd4LXJfk0cWvd4+0\nS9KMLf0cU1X9C5ARt0gS4Cu/JTVkmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVj\nmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOY\nJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLUzOExJNiV5JMlXxxgkSWOcMd0OHBnhfiQJGBimJDuB\n9wB3jTNHkoafMX0K+Bjwq7PdIMneJGtJ1k7ywsDDSZqDpcOU5Ebguap6+OVuV1X7qmq1qlY3s2XZ\nw0makSFnTNcCNyX5CXAPcF2SL4+yStKsLR2mqrqzqnZW1WXALcA3q+q20ZZJmi1fxySpnZUx7qSq\nvg18e4z7kiTPmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVj\nmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOY\nJLVjmCS1Y5gktWOYJLUzKExJLk5yIMn3kxxJ8raxhkmar5WBf//TwNer6o+SXARsG2GTpJlbOkxJ\nXg+8A3g/QFWdAE6MM0vSnA15KLcLOA58IckjSe5Ksn2kXZJmbEiYVoC3AJ+tqquBXwJ3bLxRkr1J\n1pKsneSFAYeTNBdDwnQUOFpVDy0uH2A9VKepqn1VtVpVq5vZMuBwkuZi6TBV1bPAU0muWFy1Bzg8\nyipJszb0u3IfBPYvviP3BPAnwydJmrtBYaqqR4HVkbZIEuArvyU1ZJgktWOYJLVjmCS1Y5gktWOY\nJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gk\ntWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1Y5gktWOYJLVjmCS1MyhMST6S5FCSx5Lc\nnWTrWMMkzdfSYUqyA/gQsFpVVwKbgFvGGiZpvoY+lFsBXpNkBdgGPDN8kqS5WzpMVfU08AngSeAY\n8POqemDj7ZLsTbKWZO0kLyy/VNJsDHko9wbgZmAXcAmwPcltG29XVfuqarWqVjezZfmlkmZjyEO5\n64EfV9XxqjoJ3Au8fZxZkuZsSJieBK5Jsi1JgD3AkXFmSZqzIc8xPQQcAA4C31vc176RdkmasZUh\nf7mqPg58fKQtkgT4ym9JDRkmSe0YJkntGCZJ7RgmSe0YJkntGCZJ7RgmSe0YJkntGCZJ7RgmSe0Y\nJkntGCZJ7RgmSe0YJkntGCZJ7RgmSe0YJkntGCZJ7RgmSe0YJkntGCZJ7RgmSe0YJkntDHrDy183\n77zkqqknSMIzJkkNGSZJ7RgmSe0YJkntGCZJ7ZwzTEk+n+S5JI+dct1vJnkwyY8Wv7/hlZ0paU7O\n54zpi8ANG667A/hGVV0OfGNxWZJGcc4wVdU/A/+x4eqbgS8tPv4S8Icj75I0Y8s+x/Smqjq2+PhZ\n4E0j7ZGk4U9+V1UBdbY/T7I3yVqStZO8MPRwkmZg2TD9e5LfBlj8/tzZblhV+6pqtapWN7NlycNJ\nmpNlw3Qf8L7Fx+8D/mGcOZJ0fi8XuBv4V+CKJEeT/BnwV8AfJPkRcP3isiSN4pw/XaCqbj3LH+0Z\neYskAb7yW1JDhklSO4ZJUjuGSVI7hklSO1l/4fYFOlhyHPjpedz0t4CfvcJzltV5G/Te13kb9N7X\neRuc/77fqao3nutGFzRM5yvJWlWtTr3jTDpvg977Om+D3vs6b4Px9/lQTlI7hklSO13DtG/qAS+j\n8zbova/zNui9r/M2GHlfy+eYJM1b1zMmSTPWKkxJbkjygySPJ2n1c8STXJrkW0kOJzmU5PapN22U\nZFOSR5J8deotGyW5OMmBJN9PciTJ26be9JIkH1l8Th9LcneSrRPvaf0GIGfZ99eLz+13k/x9kouH\nHKNNmJJsAj4DvAvYDdyaZPe0q07zIvDRqtoNXAP8ebN9ALcDR6YecRafBr5eVb8L/B5NdibZAXwI\nWK2qK4FNwC3Trmr/BiBf5P/vexC4sqreDPwQuHPIAdqECXgr8HhVPVFVJ4B7WH/Tgxaq6lhVHVx8\n/DzrX1g7pl31f5LsBN4D3DX1lo2SvB54B/A5gKo6UVX/Ne2q06wAr0myAmwDnplyTPc3ADnTvqp6\noKpeXFz8N2DnkGN0CtMO4KlTLh+l0Rf+qZJcBlwNPDTtktN8CvgY8Kuph5zBLuA48IXFQ827kmyf\nehRAVT0NfAJ4EjgG/LyqHph21Rm9mt4A5E+BfxxyB53C9KqQ5LXAV4APV9Uvpt4DkORG4Lmqenjq\nLWexArwF+GxVXQ38kibvRbh4ruZm1uN5CbA9yW3Trnp553oDkCkl+QvWn/bYP+R+OoXpaeDSUy7v\nXFzXRpLNrEdpf1XdO/WeU1wL3JTkJ6w/BL4uyZennXSao8DRqnrpDPMA66Hq4Hrgx1V1vKpOAvcC\nb59405mc9xuATCXJ+4EbgT+uga9D6hSm7wCXJ9mV5CLWn4C8b+JN/ytJWH+O5EhVfXLqPaeqqjur\namdVXcb6P7dvVlWb/+pX1bPAU0muWFy1Bzg84aRTPQlck2Tb4nO8hyZPzG/Q+g1AktzA+lMJN1XV\nfw+9vzZhWjxx9gHgftb/xfi7qjo07arTXAu8l/WzkUcXv9499ahXkQ8C+5N8F7gK+MuJ9wCwOIs7\nABwEvsf618Skr7Lu/gYgZ9n3N8DrgAcXXxt/O+gYvvJbUjdtzpgk6SWGSVI7hklSO4ZJUjuGSVI7\nhklSO4ZJUjuGSVI7/wPX24/f+sdr0AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f19c33470b8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plotting the padded output.\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "plt.imshow((padded[0]>0).sum(axis=-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# the weights for the backward pass have to be adap\n",
    "backward_weights=weights[::-1,::-1].transpose((0,1,3,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "grads=convolve(padded, backward_weights)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 10, 11, 5)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grads.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "eps=1e-4\n",
    "tol=1e-8\n",
    "\n",
    "for idx in np.ndindex(im.shape):\n",
    "    \n",
    "    d_im=im.copy()\n",
    "    d_im[idx]+=eps\n",
    "    d_out=convolve(d_im, weights)\n",
    "    d_debug_out=np.sum(d_out*debug_weights)\n",
    "\n",
    "    grad=(d_debug_out-debug_out)/eps\n",
    "    \n",
    "    assert np.abs(grad-grads[idx])<tol, idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}