convolutional neural network

• (Peter Norvig, Stuart J. Russell, 2020)
• (Jianxin Wu, 2017)
• (Zhifei Zhang, 2016)

and countless other resources that helped me form a good understanding of the topics related to conv networks

an image cannot be thought of as a simple vector of input pixel values, primarily because adjacency of pixels in an image matters. simple multilayer perceptrons arent suited for images because adjacent neurons in the same layer arent really connected or affected by each other, which isnt the case in images.

consider an input image with pixels, if the input and the first hidden layer are fully connected, that means we'd have weights; for a typical RGB image, thats 9 trillion weights, which is an unreasonable amount of parameters, all the more reason we need to ditch multilayer perceptrons.

these considerations suggest that we should construct the first hidden layer so that each hidden unit receives input from only a small, local region of the image. this kills two birds with one stone. first, it respects adjacency, at least locally. second, it cuts down the number of weights.

so far, so good. but we are missing another important property of images: roughly speaking, anything that is detectable in one small, local region of the image–perhaps an eye or a blade of grass–would look the same if it appeared in another small, local region of the image. in other words, we expect image data to exhibit approximate spatial invariance, at least at small to moderate scales. we don’t necessarily expect the top halves of photos to look like bottom halves, so there is a scale beyond which spatial invariance no longer holds.

local spatial invariance can be achieved by constraining the weights connecting a local region to a unit in the hidden layer to be the same for each hidden unit. (that is, for hidden units and , the weights are the same as ) this makes the hidden units into feature detectors that detect the same feature wherever it appear in the image. typically, we want the first hidden layer to detect many kinds of features, not just one; so for each local image region we might have hidden units with distinct sets of weights. this means that there are weights in all–a number that is not only far smaller than , but is actually independent of , the image size. thus, by injecting some prior knowledge–namely, knowledge of adjacency and spatial invariance–we can develop models that have far fewer parameters and can learn much more quickly.

usually an image is stored in memory as a 2d array (or matrix), each cell containing 3 different values for RGB (red,green,blue), which forms a 3 dimensional array or a tensor of order 3, which means the network needs to accept tensors as inputs.

a convolutional neural network is one that contains spatially local connections, at least in the early layers which we call convolutional layers, and has patterns of weights that are replicated across the units in each layer. a pattern of weights that is replicated across multiple local regions is called a kernel which is applied with a convolution.

in practice, multiple kernels are learned at each convolutional layer, suppose the input to the -th layer is an order 3 tensor with size , a kernel would also be an order 3 tensor with size ( and are the dimensions of the kernel and they differ from , but the depth of both the image and tensor should be equal for the result of the convolution to be of lower dimensionality), assuming kernels are used (in other words, feature maps), the tensor of kernels (or weights) would be an order 4 tensor in , assuming a stride of 1, the output would be a tensor of the third order and of size which is composed of feature maps.

at the first layer, the image is stored as a tensor of order 3 of depth , each layer of this tensor is basically a matrix we call a feature map or channel, so at each layer, the image is stored as nested layers of feature maps, it might be easier to take the input to the first layer as an example, which can be thought of as a set of 3 feature maps of RGB values.

a pooling layer in a neural network summarizes a set of adjacent units from the preceding pooling layer with a single value. pooling works just like a convolution layer, with a kernel size l and stride , but the operation that is applied is fixed rather than learned.

typically, no activation function is associated with the pooling layer. there are two common forms of pooling:

• average-pooling computes the average value of its inputs. this is identical to concvolution with a uniform kernel vector . if we set , the effect is to coarsen the resolution of the image–to downsample it–by a factor of . an object that occupied, say, pixels, would now occupy only 10 pixels after pooling. the same learned classifier that would be able to recognize the object at a size of 10 pixels in the original image would now be able to recognize that object in the pooled image, even if it was too big to recognize in the original image. in other words, average-pooling facilitates multiscale recognition. it also reduces the number of weights required in subsequent layers, leading to lower computational cost and possibly faster learning.
• max-pooling computes the maximum value of its inputs. it can also be used purely for downsampling, but it has a somewhat different semantics. suppose we applied max-pooling to a layer with the values [5,9,4]: the result would be a 9, indicating that somewhere in the input image there is a darker dot that is detected by the kernel. in other words, max-pooling acts as a kind of logical disjunction, saying that a feature exists somewhere in the unit's receptive field.

if the goal is to classify the image into one of categories, then the final layer of the network will be a softmax with output units. the early layers of the CNN are image-sized, so somewhere in between there must be significant reductions in layer size. convolution layers and pooling layers with stride larger than 1 all serve to reduce the layer size. it's also possible to reduce the layer size simply by having a fully connected layer with fewer units than the preceding layer. CNNs often have one or two such layers preceding the final softmax layer.

let be the input to the -th pooling layer, the pooling operation requires no parameters (the matrix of weights is nulled), hence parameter learning is not needed for this layer, let the spatial extent (dimensions) of the pooling be , assume that divides and divides , the output of pooling ( or equivalently ) will be an order 3 tensor of size , with

a pooling layer operates upon channel by channel independently. within each channel, the matrix with elements are divided into nonoverlapping subregions, each subregion being in size. the pooling operator then maps a subregion into a single number.

where , and .

since pooling layers have no weights they arent directly connected to their preceding layer, so during backpropagation, we cant directly tell what subregion of the previous layer each pixel in corresponds to, but we can reverse the pooling operation to "decode" the values from back to . assuming a max-pooling layer, we need a triplet to pinpoint one element in the input , and another triplet to locate one element in . assuming a max-pooling layer (process is the same for average-pooling), the pooling output comes from , iff the following conditions are met:

• they are in the same channel,
• the -th spatial entry belongs to the -th subregion,
• the -th spatial entry is the largest one in that subregion.

translating these conditions into equations, we get:

a layer that takes a tensor and vectorizes or flattens it, turning it into a 1d vector, it doesnt need any parameters.

suppose the input of a layer has size . if we use convolution kernels whose size is , then such kernels form an order 4 tensor in . the output would be , which is why these layers are sometimes used as flatten layers.

it is obvious that to compute any element in , we need to use all elements in the input . hence, this layer is a fully connected layer, but can be implemented as a convolution layer. hence, we do not need to derive learning rules for a fully connected layer separately.

if the data has already been flattened in a preceding layer, then the input size would be , we use kernels of size , which form a 2d matrix we can call of size . the convolution , is exactly the same as the matrix multiplication ( multiplied by the transpose of the vector ), which results in a matrix of size , again meaning is just a vector of size , .

because the convolution operation in this layer is equal to a matrix multiplication, the fully connected layers here behave in the same manner as in simple multilayer perceptrons.

notice that here also equals the number of units in the -th layer.

consider the following network:

let denote the th kernel of the th layer whose dimensions are denoted by (depth,height and width of the kernel tensor, respectively, although depth is irrelevant here), where , such that is the number of kernels in the th layer, let denote the tensor of weights of layer , let denote the input to the th layer, let denote the output of the th layer, let denote the output before the activation function. (im using a different notation than in the image but it should be obvious which is which.)

the parameters are:

• or , of size and of size 6, ,
• or , of size and of size 2, (size of the kernel is different from in the original figure),
• or , of size and of size .

feedforwarding for convolutional layer or :

where (i think its better to keep general notation than write 2 explicitly), , , taken from this convolution example.

here , the dimensions of the output are .

feedforwarding for average pooling layer or : in words, we iterate through each block of size (in each kernel) and pool it into a single pixel, here the size of the pooling kernels is and the result is of dimensions .

feedforwarding for convolutional layer or :

where , output is of dimensions , we use for the depth of the image because in truth what we're finding is which is equal to but we omit an index of because its "implied" when its to the left.

feedforwarding for average pooling layer or : here the size of the kernels is aswell, the output is of dimensions .

vectorization before fully connected layer (may have its own layer): the output is of size .

feedforwarding for fully connected layer or :

see not-convnet-I-drop-index as to why i wrote .

let denote the flipping of a matrix over both axes so that the indicies may be reversed, i.e. (a negative index implies an index that is subtracted from the size of the dimension along with the value 1). we can show that this layer resembles the usual fully connected layer from simple multilayer perceptrons by turning the convolution into matrix multiplication:

where (layer contains 10 fully connected kernels), the output is of size 10, here and the size of each kernel is ( ).

in vector notation, we write (notice that results in a vector): at this point we'd have arrived at the output layer and the output of the neural network would be or simply (the output of the last fully connected layer which itself is the output layer), assuming the quadratic loss function, and assuming the desired output is , the loss function would be defined as: now we can begin to backpropagate the error, followed by an object denotes the error at that specific object or point:

backpropagation for fully connected layer or :

where , here , notice that .

let , whose size would be 10, then:

we arrived at an equation in matrix notation which is convenient ( was a column vector initially).

backpropagation through flatten layer before : recall that during feedforwarding, the flatten layer turned the tensor of feature maps which is of the third order into a single vector, the deltas defined by the layer during backpropagation is a vector aswell, which we need to turn them into a tensor of the third order that resembles the delta at each entry in the tensor of the feature maps.

first we find the delta at each entry in the vector:

notice that .

we have because 192 is the total size of the tensor received from during feedforwarding.

now the vector of deltas needs to be reshaped into a tensor of the third order so that we may then send it to the next layer in the process, , which is a pooling layer.

the reshaping should be the exact inverse of the row-major vectorization we did during feedforwarding: such that , here , note that .

backpropagation through average pooling layer : recall that this layer downscaled the input given to it during feedforwarding from its preceding layer , so during backpropagation, when it responds to the next layer which is the one it got the initial message from during feedforwarding it needs to scale its message back up to the dimensions of the input it got from that layer, that "message" would be the deltas: backpropagation through convolutional layer :

where .

see not-convnet-I-indicies about the indicies of (the note talks about the indicies of but the same fact applies to here).

let be the error after (after in terms of backpropagation, before in terms of feedforwarding) the activation function: then: now for the bias:

now we find the deltas at or , because thats what the next layer in backpropagation, , needs.

such that . here, are the deltas that need to be passed onto the next layer .

(defgeneric feedforward (layer x)
  (:documentation "feed-forward, return activations to pass to next layer"))

(defgeneric propbackward (layer layer-x layer-y layer-y-unactivated propped-deltas learning-rate)
  (:documentation "backward-popagation, return gradients to pass to preceding layer"))

(defclass layer ()
  ((weights :initarg :weights :initform nil :accessor layer-weights) ;; weights going into the layer's units
   (biases :initarg :biases :initform nil :accessor layer-biases)
   ;; per-layer activation functions (same activation function for all units in the layer)
   (activation-function :initarg :activation-function :initform #'relu :accessor layer-activation-function)
   (activation-function-derivative :initarg :activation-function-derivative :initform #'relu-derivative :accessor layer-activation-function-derivative)
   ;; use tensor-activation-function and tensor-activation-function-derivative only if you want per-unit special activation functions, they take the indicies list (multidimensional index) of a unit and return a function to use for activation
   (tensor-activation-function :initarg :tensor-activation-function :accessor layer-tensor-activation-function)
   (tensor-activation-function-derivative :initarg :tensor-activation-function-derivative :accessor layer-tensor-activation-function-derivative)))

(defclass network ()
  ((layers :initarg :layers :initform nil :accessor network-layers)
   (learning-rate :initform 0.0005 :initarg :learning-rate :accessor network-learning-rate)))

(defun make-network (&key learning-rate layers)
  (make-instance
   'network
   :layers layers
   :learning-rate (or learning-rate 0.0005)))

(defmethod network-feedforward ((n network) x)
  "x is a tensor, feedforward to the last layer and return its output"
  (with-slots (layers) n
    ;; last-out is needed to keep the output of the lastly feedforwarded layer, the output of the layers is pushed onto the list which means they are stored in reverse order, to be later popped also in "reverse" order for backprop, this means that the first entry in out-list corresponds to the output layer, this should be better than storing them in normal order because we use a list and later we need to iterate from the output of the last layer to the first layer, each entry in the list is a cons with the first element as the activated output and second as the unactivated output
    (let ((last-out x)
          (out-list nil))
      (loop for layer in layers
            do (multiple-value-bind (new-out new-out-unactivated)
                   (feedforward layer last-out)
                 (push (cons new-out new-out-unactivated) out-list)
                 (setf last-out new-out)))
      out-list)))

(defclass convolutional-layer (layer)
  ()
  (:documentation "a layer that arbitrary dimensions for its weights tensor, and convolves it with an arbitrary input tensor (convolution layer of arbitrary dimensions), the weights tensor should be 1 order higher that the input tensor, e.g. if the input tensor is a 3d tensor (image with feature maps), the shape of the weights tensor should be of 4 dimensions (4d tensor), the output tensor of the layer would be of the same order as the input tensor"))

(defun make-convolutional-layer (&key dims activation-function
                                   activation-function-derivative
                                   tensor-activation-function
                                   tensor-activation-function-derivative)
  "consutrctor for convolutional layers"
  (make-instance
   'convolutional-layer
   :weights (random-tensor dims)
   :biases (random-tensor (car dims))
   :activation-function activation-function
   :activation-function-derivative activation-function-derivative
   :tensor-activation-function tensor-activation-function
   :tensor-activation-function-derivative tensor-activation-function-derivative))

(defmethod feedforward ((l convolutional-layer) x)
  "x is an arbitrary tensor"
  (with-slots (weights biases activation-function tensor-activation-function) l
    (let* ((num-kernels (array-dimension weights 0))
           (convolution-out-size
             (mapcar
              (lambda (img-d ker-d) (- img-d (1- ker-d)))
              (array-dimensions x)
              (cdr (array-dimensions weights))))
           (out (make-array (append (list num-kernels) convolution-out-size))))
      (loop for kernel-idx from 0 below num-kernels
            do (set-array-nth
                out
                (array-map (lambda (cell) (+ cell (aref biases kernel-idx)))
                           (tensor-convolution
                            x
                            (array-nth weights kernel-idx)))
                kernel-idx))
      ;; we return 2 values, the output tensor and the unactivated output tensor
      (if tensor-activation-function
          ;; apply per-unit activation functions
          (values
           (array-map-indicies out tensor-activation-function)
           out)
          ;; apply single activation function to all units in the layer
          (values (array-map activation-function out) out)))))

(defclass 3d-convolutional-layer (convolutional-layer)
  ()
  (:documentation "a convolutional layer with 4d weights tensor and 3d input/output tensors, the depths of the input and weight tensors should be the same, this is used for convolving images with feature maps (channels)
to see the difference between this and the parent class consider the following examples:
CL-USER> (array-dimensions (let ((l (make-convolutional-layer :dims '(2 3 3 3))))
                    (feedforward l (random-tensor '(3 6 6)))))
=> (2 1 4 4)
CL-USER> (array-dimensions (let ((l (make-3d-convolutional-layer-from-dims :dims '(2 3 3 3))))
                    (feedforward l (random-tensor '(3 6 6)))))
=> (2 4 4)
"))

(defmethod feedforward :around ((l 3d-convolutional-layer) x)
  "grab the output of the parent arbitrary-convolution class, reshape it and return it, as there is always redundant dimension in the 4d tensor, this happens because the tensors (input and weights) have the same depth when doing image convolution"
  (multiple-value-bind (out unactivated-out) (call-next-method) ;; output of parent class' feedforward
    (let ((actual-convolution-out-size
            (append (list (array-dimension out 0))
                    (cdr (cdr (array-dimensions out))))))
      (values (make-array actual-convolution-out-size :displaced-to out)
              (make-array actual-convolution-out-size :displaced-to unactivated-out)))))

(defun make-3d-convolutional-layer-from-dims (&key dims activation-function activation-function-derivative tensor-activation-function tensor-activation-function-derivative)
  "consutrctor for convolutional layers"
  (make-instance
   '3d-convolutional-layer
   :activation-function activation-function
   :activation-function-derivative activation-function-derivative
   :tensor-activation-function tensor-activation-function
   :tensor-activation-function-derivative tensor-activation-function-derivative
   :weights (random-tensor dims)
   :biases (random-tensor (car dims))))

(defun make-3d-convolutional-layer (&key activation-function activation-function-derivative num-kernels kernel-depth kernel-height kernel-width tensor-activation-function tensor-activation-function-derivative)
  "consutrctor for convolutional layers"
  (make-instance
   '3d-convolutional-layer
   :activation-function activation-function
   :activation-function-derivative activation-function-derivative
   :tensor-activation-function tensor-activation-function
   :tensor-activation-function-derivative tensor-activation-function-derivative
   :weights (random-tensor (list num-kernels kernel-depth kernel-height kernel-width))
   :biases (random-tensor num-kernels)))

(defclass pooling-layer (layer)
  ((rows :initarg :rows :accessor pooling-layer-rows)
   (cols :initarg :cols :accessor pooling-layer-cols)
   (pooling-function :initarg :pooling-function :accessor pooling-layer-function)
   (unpooling-function :initarg :unpooling-function :accessor pooling-layer-unpooling-function))) ;; unpooling-function will make sense when you read later on

(defun max-pooling-function (myvec)
  (reduce #'max myvec))

(defun average-pooling-function (myvec)
  (/ (reduce #'+ myvec) (length myvec)))

(defun make-pooling-layer (&key rows cols pooling-function unpooling-function)
  (make-instance
   'pooling-layer
   :rows rows
   :cols cols
   :pooling-function (or pooling-function #'average-pooling-function)
   :unpooling-function (or unpooling-function #'average-unpooling-function)))

(defmethod feedforward ((l pooling-layer) x)
  "x is a tensor of the third order, which in case of the first layer is the actual image"
  (with-slots (rows cols pooling-function) l
    (let* ((num-channels (array-depth x))
           (img-rows (array-rows x))
           (img-cols (array-cols x))
           (out-rows (/ img-rows rows))
           (out-cols (/ img-cols cols))
           (out (make-array (list num-channels out-rows out-cols))))
      (loop for channel-idx from 0 below num-channels
            do (loop for img-row-idx from 0 below img-rows by rows
                     do (loop for img-col-idx from 0 below img-cols by cols
                              do (let ((out-row-idx (/ img-row-idx rows))
                                       (out-col-idx (/ img-col-idx cols)))
                                   (setf
                                    (aref out channel-idx out-row-idx out-col-idx)
                                    (funcall
                                     pooling-function
                                     (vectorize-array
                                      (subarray
                                       x
                                       (list channel-idx img-row-idx img-col-idx)
                                       (list rows cols)))))))))
      out)))

(defclass flatten-layer (layer) ())

(defun make-flatten-layer () (make-instance 'flatten-layer))

(defmethod feedforward ((l flatten-layer) x)
  (vectorize-array x))