05.cnn.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convolutional Neural Networks\n",
    "(c) Deniz Yuret, 2018"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Objectives: See the effect of sparse and shared weights implemented by convolutional networks.\n",
    "* Prerequisites: MLP models (04.mlp.ipynb), KnetArray, param, param0, dropout, relu, nll\n",
    "* Knet: conv4, pool, mat (explained)\n",
    "* Knet: dir, gpu, minibatch, KnetArray (used by mnist.jl)\n",
    "* Knet: SGD, train!, Train, load, save (used by trainresults)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Pkg\n",
    "for p in (\"Knet\",\"Plots\",\"ProgressMeter\")\n",
    "    haskey(Pkg.installed(),p) || Pkg.add(p)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Introduction to convolution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Convolution operator in Knet\n",
    "using Knet: conv4\n",
    "@doc conv4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Convolution in 1-D\n",
    "@show w = reshape([1.0,2.0,3.0], (3,1,1,1))\n",
    "@show x = reshape([1.0:7.0...], (7,1,1,1))\n",
    "@show y = conv4(w, x);  # size Y = X - W + 1 = 5 by default"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Padding\n",
    "@show y2 = conv4(w, x, padding=(1,0));  # size Y = X + 2P - W + 1 = 7 with padding=1\n",
    "# To preserve input size (Y=X) for a given W, what padding P should we use?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Stride\n",
    "@show y3 = conv4(w, x; padding=(1,0), stride=3);  # size Y = 1 + floor((X+2P-W)/S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Mode\n",
    "@show y4 = conv4(w, x, mode=0);  # Default mode (convolution) inverts w\n",
    "@show y5 = conv4(w, x, mode=1);  # mode=1 (cross-correlation) does not invert w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Convolution in more dimensions\n",
    "x = reshape([1.0:9.0...], (3,3,1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "w = reshape([1.0:4.0...], (2,2,1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "y = conv4(w, x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Convolution with multiple channels, filters, and instances\n",
    "# size X = [X1,X2,...,Xd,Cx,N] where d is the number of dimensions, Cx is channels, N is instances\n",
    "x = reshape([1.0:18.0...], (3,3,2,1)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# size W = [W1,W2,...,Wd,Cx,Cy] where d is the number of dimensions, Cx is input channels, Cy is output channels\n",
    "w = reshape([1.0:24.0...], (2,2,2,3));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# size Y = [Y1,Y2,...,Yd,Cy,N]  where Yi = 1 + floor((Xi+2Pi-Wi)/Si), Cy is channels, N is instances\n",
    "y = conv4(w,x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "See http://cs231n.github.io/assets/conv-demo/index.html for an animated example."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Introduction to Pooling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Pooling operator in Knet\n",
    "using Knet: pool\n",
    "@doc pool"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# 1-D pooling example\n",
    "@show x = reshape([1.0:6.0...], (6,1,1,1))\n",
    "@show pool(x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Window size\n",
    "@show pool(x; window=3);  # size Y = floor(X/W)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Padding\n",
    "@show pool(x; padding=(1,0));  # size Y = floor((X+2P)/W)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Stride\n",
    "@show x = reshape([1.0:10.0...], (10,1,1,1));\n",
    "@show pool(x; stride=4);  # size Y = 1 + floor((X+2P-W)/S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Mode (using KnetArray here; not all modes are implemented on the CPU)\n",
    "using Knet: KnetArray\n",
    "x = KnetArray(reshape([1.0:6.0...], (6,1,1,1)))\n",
    "@show x\n",
    "@show pool(x; padding=(1,0), mode=0)  # max pooling\n",
    "@show pool(x; padding=(1,0), mode=1)  # avg pooling\n",
    "@show pool(x; padding=(1,0), mode=2); # avg pooling excluding padded values (is not implemented on CPU)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# More dimensions\n",
    "x = reshape([1.0:16.0...], (4,4,1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "pool(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Multiple channels and instances\n",
    "x = reshape([1.0:32.0...], (4,4,2,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# each channel and each instance is pooled separately\n",
    "pool(x)  # size Y = (Y1,...,Yd,Cx,N) where Yi are spatial dims, Cx and N are identical to input X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experiment setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load data (see 02.mnist.ipynb)\n",
    "using Knet: Knet, KnetArray, gpu, minibatch\n",
    "include(Knet.dir(\"data\",\"mnist.jl\"))  # Load data\n",
    "dtrn,dtst = mnistdata();              # dtrn and dtst = [ (x1,y1), (x2,y2), ... ] where xi,yi are minibatches of 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(x,y) = first(dtst)\n",
    "summary.((x,y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# For running experiments\n",
    "using Knet: SGD, train!, nll, zeroone\n",
    "import ProgressMeter\n",
    "    \n",
    "function trainresults(file,model; o...)\n",
    "    if (print(\"Train from scratch? \");readline()[1]=='y')\n",
    "        results = Float64[]; updates = 0; prog = ProgressMeter.Progress(60000)\n",
    "        function callback(J)\n",
    "            if updates % 600 == 0\n",
    "                push!(results, nll(model,dtrn), nll(model,dtst), zeroone(model,dtrn), zeroone(model,dtst))\n",
    "                ProgressMeter.update!(prog, updates)\n",
    "            end\n",
    "            return (updates += 1) <= 60000\n",
    "        end\n",
    "        train!(model, dtrn; callback=callback, optimizer=SGD(lr=0.1), o...)\n",
    "        Knet.save(file,\"results\",reshape(results, (4,:)))\n",
    "    end\n",
    "    isfile(file) || download(\"http://people.csail.mit.edu/deniz/models/tutorial/$file\",file)\n",
    "    results = Knet.load(file,\"results\")\n",
    "    println(minimum(results,dims=2))\n",
    "    return results\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A convolutional neural network model for MNIST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Redefine Linear layer (See 03.lin.ipynb):\n",
    "using Knet: param, param0\n",
    "struct Linear; w; b; end\n",
    "(f::Linear)(x) = (f.w * mat(x) .+ f.b)\n",
    "mat(x)=reshape(x,:,size(x)[end])  # Reshapes 4-D tensor to 2-D matrix so we can use matmul\n",
    "Linear(inputsize::Int,outputsize::Int) = Linear(param(outputsize,inputsize),param0(outputsize))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define a convolutional layer:\n",
    "struct Conv; w; b; end\n",
    "(f::Conv)(x) = pool(conv4(f.w,x) .+ f.b)\n",
    "Conv(w1,w2,cx,cy) = Conv(param(w1,w2,cx,cy), param0(1,1,cy,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define a convolutional neural network:\n",
    "struct CNN; layers; end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Weight initialization for a multi-layer convolutional neural network\n",
    "# h[i] is an integer for a fully connected layer, a triple of integers for convolution filters and tensor inputs\n",
    "# use CNN(x,h1,h2,...,hn,y) for a n hidden layer model\n",
    "function CNN(h...)  \n",
    "    w = Any[]\n",
    "    x = h[1]\n",
    "    for i=2:length(h)\n",
    "        if isa(h[i],Tuple)\n",
    "            (x1,x2,cx) = x\n",
    "            (w1,w2,cy) = h[i]\n",
    "            push!(w, Conv(w1,w2,cx,cy))\n",
    "            x = ((x1-w1+1)÷2,(x2-w2+1)÷2,cy) # assuming conv4 with p=0, s=1 and pool with p=0,w=s=2\n",
    "        elseif isa(h[i],Integer)\n",
    "            push!(w, Linear(prod(x),h[i]))\n",
    "            x = h[i]\n",
    "        else\n",
    "            error(\"Unknown layer type: $(h[i])\")\n",
    "        end\n",
    "    end\n",
    "    CNN(w)\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Knet: dropout, relu\n",
    "function (m::CNN)(x; pdrop=0)\n",
    "    for (i,layer) in enumerate(m.layers)\n",
    "        p = (i <= length(pdrop) ? pdrop[i] : pdrop[end])\n",
    "        x = dropout(x, p)\n",
    "        x = layer(x)\n",
    "        x = (layer == m.layers[end] ? x : relu.(x))\n",
    "    end\n",
    "    return x\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "lenet = CNN((28,28,1), (5,5,20), (5,5,50), 500, 10)\n",
    "summary.(l.w for l in lenet.layers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "using Knet: nll\n",
    "(x,y) = first(dtst)\n",
    "nll(lenet,x,y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CNN vs MLP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Plots; default(fmt=:png,ls=:auto)\n",
    "ENV[\"COLUMNS\"] = 92"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "@time cnn = trainresults(\"cnn.jld2\", lenet; pdrop=(0,0,.3)); # 406s [8.83583e-5, 0.017289, 0.0, 0.0048]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mlp = Knet.load(\"mlp.jld2\",\"results\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Comparison to MLP shows faster convergence, better generalization\n",
    "plot([mlp[1,:], mlp[2,:], cnn[1,:], cnn[2,:]],ylim=(0.0,0.1),\n",
    "     labels=[:trnMLP :tstMLP :trnCNN :tstCNN],xlabel=\"Epochs\",ylabel=\"Loss\")  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "plot([mlp[3,:], mlp[4,:], cnn[3,:], cnn[4,:]],ylim=(0.0,0.03),\n",
    "    labels=[:trnMLP :tstMLP :trnCNN :tstCNN],xlabel=\"Epochs\",ylabel=\"Error\")  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Convolution vs Matrix Multiplication"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Convolution and matrix multiplication can be implemented in terms of each other.\n",
    "# Convolutional networks have no additional representational power, only statistical efficiency.\n",
    "# Our original 1-D example\n",
    "@show w = reshape([1.0,2.0,3.0], (3,1,1,1))\n",
    "@show x = reshape([1.0:7.0...], (7,1,1,1))\n",
    "@show y = conv4(w, x);  # size Y = X - W + 1 = 5 by default"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Convolution as matrix multiplication (1)\n",
    "# Turn w into a (Y,X) sparse matrix\n",
    "w2 = Float64[3 2 1 0 0 0 0; 0 3 2 1 0 0 0; 0 0 3 2 1 0 0; 0 0 0 3 2 1 0; 0 0 0 0 3 2 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "@show y2 = w2 * mat(x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Convolution as matrix multiplication (2)\n",
    "# Turn x into a (W,Y) dense matrix (aka the im2col operation)\n",
    "# This is used to speed up convolution with known efficient matmul algorithms\n",
    "x3 = Float64[1 2 3 4 5; 2 3 4 5 6; 3 4 5 6 7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "@show w3 = [3.0 2.0 1.0]\n",
    "@show y3 = w3 * x3;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Matrix multiplication as convolution\n",
    "# This could be used to make a fully connected network accept variable sized inputs.\n",
    "w = reshape([1.0:6.0...], (2,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "x = reshape([1.0:3.0...], (3,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "y = w * x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Consider w with size (Y,X)\n",
    "# Treat each of the Y rows of w as a convolution filter\n",
    "w2 = copy(reshape(Array(w)', (3,1,1,2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Reshape x for convolution\n",
    "x2 = reshape(x, (3,1,1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Use conv4 for matrix multiplication\n",
    "y2 = conv4(w2, x2; mode=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# So there is no difference between the class of functions representable with an MLP vs CNN.\n",
    "# Sparse connections and weight sharing give CNNs more generalization power with images.\n",
    "# Number of parameters in MLP256: (256x784)+256+(10x256)+10 = 203530\n",
    "# Number of parameters in LeNet: (5*5*1*20)+20+(5*5*20*50)+50+(500*800)+500+(10*500)+10 = 431080"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "accelerator": "GPU",
  "colab": {
   "collapsed_sections": [],
   "name": "julia.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "Julia 1.0.3",
   "language": "julia",
   "name": "julia-1.0"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}