{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# From Dense Layers to Convolutions\n",
"\n",
"The models that we've discussed so far are fine options \n",
"if you're dealing with *tabular* data. \n",
"By *tabular* we mean that the data consists \n",
"of rows corresponding to examples and columns corresponding to features.\n",
"With tabular data, we might anticipate that pattern we seek\n",
"could require modeling interactions among the features,\n",
"but do not assume anything a priori about \n",
"which features are related to each other or in what way.\n",
"\n",
"\n",
"Sometimes we truly may not have any knowledge \n",
"to guide the construction of more cleverly-organized architectures.\n",
"and in thise cases, a multilayer perceptron is often the best that we can do.\n",
"However, once we start dealing with high-dimensional perceptual data, \n",
"these *structure-less* netwroks can grow unwieldy. \n",
"\n",
"\n",
"For instance, let's return to our running example \n",
"of distinguishing cats from dogs. \n",
"Say that we do a thorough job in data collection,\n",
"collecting an annotated sets of high-quality 1-megapixel photographs. \n",
"This means that the input into a network has *1 million dimensions*. \n",
"Even an aggressive reduction to *1,000 hidden dimensions* \n",
"would require a *dense* (fully-connected) layer to support $10^9$ parameters. \n",
"Unless we have an extremely large dataset (perhaps billions?), \n",
"lots of GPUs, a talent for extreme distributed optimization,\n",
"and an extraordinary ammount of patience,\n",
"learning the parameters of this network may turn out to be impossible.\n",
"\n",
"A careful reader might object to this argument \n",
"on the basis that 1 megapixel resolution may not be necessary. \n",
"However, while you could get away with 100,000 pixels,\n",
"we grossly underestimated the number of hidden nodes \n",
"that it typically takes to learn good hidden representations of images.\n",
"Learning a binary classifier with so many parameters\n",
"might seem to require that we collect an enormous dataset,\n",
"perhaps comparable to the number of dogs and cats on the planet.\n",
"And yet Yet both humans and computers are able to distinguish cats from dogs quite well, seemingly contradicting these conclusions. \n",
"That's because images exhibit rich structure \n",
"that is typically exploited by humans and machine learning models alike.\n",
"\n",
"## Invariances\n",
"\n",
"Imagine that you want to detect an object in an image. \n",
"It seems reasonable that whatever method we use to recognize objects \n",
"should not be overly concerned with the precise *location* \n",
"of the object shouldn't in the image.\n",
"Ideally we could learn a system \n",
"that would somehow exploit this knowledge.\n",
"Pigs usually don't fly and planes usually don't swim. \n",
"Nonetheless, we could still recognize a flying pig were one to appear.\n",
"This ideas is taken to an extreme in the children's game 'Where's Waldo'. \n",
"The game consists of a number of chaotic scenes bursting with activity\n",
"and Waldo shows up somewhere in each \n",
"(typically lurking in some unlikely location).\n",
"The reader's goal is to locate him.\n",
"Despite his characteristic outfit, this can be surprisingly difficult, \n",
"due to the large number of confounders. \n",
"\n",
"![(Image via Walker Books)](../img/where-wally-walker-books.jpg)\n",
"\n",
"\n",
"Back to images, the intuitions we have been discussion could be made more concrete yielding a few key principles for building neural networks for computer vision:\n",
"\n",
"1. Our vision systems should, in some sense, respond similary to the same object regardless of where it appears in the image (Translation Invariance)\n",
"1. Our visions systems should, in some sense, focus on local regions, without regard for what else is happening in the image at greater distances. (Locality)\n",
"\n",
"Let's see how this translates into mathematics.\n",
"\n",
"## Constraining the MLP\n",
"\n",
"\n",
"To start off let's consider what an MLP would look like \n",
"with $h \\times w$ images as inputs \n",
"(represented as matrices in math, and as 2D arrays in code), \n",
"and hidden representations similarly organized \n",
"as $h \\times w$ matrices / 2D arrays.\n",
"Let $x[i,j]$ and $h[i,j]$ denote pixel location $(i,j)$ \n",
"in an image and hidden representation, respectively. \n",
"Consequently, to have each of the $hw$ hidden nodes receive input\n",
"from each of the $hw$ inputs,\n",
"we would switch from using weight matrices \n",
"(as we did previously in MLPs) \n",
"to representing our parameters \n",
"as four-dimensional weight tensors. \n",
"\n",
"\n",
"We could formally express this dense layer as follows:\n",
"\n",
"$$h[i,j] = \\sum_{k,l} W[i,j,k,l] \\cdot x[k,l] =\n",
"\\sum_{a, b} V[i,j,a,b] \\cdot x[i+a,j+b]$$\n",
"\n",
"The switch from $W$ to $V$ is entirely cosmetic (for now) \n",
"since there is a one-to-one correspondence \n",
"between coefficients in both tensors. \n",
"We simply re-index the subscripts $(k,l)$ \n",
"such that $k = i+a$ and $l = j+b$. \n",
"In other words, we set $V[i,j,a,b] = W[i,j,i+a, j+b]$. \n",
"The indices $a, b$ run over both positive and negative offsets, \n",
"covering the entire image. \n",
"For any given location $(i,j)$ in the hidden layer $h[i,j]$,\n",
"we compute its value by summing over pixels in $x$, \n",
"centered around $(i,j)$ and weighted by $V[i,j,a,b]$.\n",
"\n",
"Now let's invoke the first principle we established aboveâ€”*translation invariance*. \n",
"This implies that a shift in the inputs $x$ \n",
"should simply lead to a shift in the activations $h$. \n",
"This is only possible if $V$ doesn't actually depend on $(i,j)$, \n",
"i.e., we have $V[i,j,a,b] = V[a,b]$. \n",
"As a result we can simplify the definition for $h$.\n",
"\n",
"$$h[i,j] = \\sum_{a, b} V[a,b] \\cdot x[i+a,j+b]$$\n",
"\n",
"This is a convolution!\n",
"We are effectively weighting pixels $(i+a, j+b)$ \n",
"in the vicinity of $(i,j)$ with coefficients $V[a,b]$ \n",
"to obtain the value $h[i,j]$. \n",
"Note that $V[a,b]$ needs many fewer coefficients than $V[i,j,a,b]$. For a 1 megapixel image it has at most 1 million coefficients. This is 1 million fewer parameters since it no longer depends on the location within the image. We have made significant progress!\n",
"\n",
"Now let's invoke the second principle - *locality*.\n",
"As motivated above, we believe that we shouldn't have \n",
"to look very far away from $(i,j)$ \n",
"in order to glean relevant information \n",
"to assess what is going on at $h[i,j]$.\n",
"This means that outside some range $|a|, |b| > \\Delta$,\n",
"we should set $V[a,b] = 0$. \n",
"Equivalently, we can rewrite $h[i,j]$ as\n",
"\n",
"$$h[i,j] = \\sum_{a = -\\Delta}^{\\Delta} \\sum_{b = -\\Delta}^{\\Delta} V[a,b] \\cdot x[i+a,j+b]$$\n",
"\n",
"This, in a nutshell is the convolutional layer. \n",
"When the local region (also called a *receptive field*) is small,\n",
"the difference as compared to a fully-connected network can be dramatic. \n",
"While previously, we might have required billions of parameters \n",
"to represent just a single layer in an image-processing network, \n",
"we now typically need just a few hundred. \n",
"The price that we pay for this drastic modification\n",
"is that our features will be translation invariant\n",
"and that our layer can only take local information into account.\n",
"All learning depends on imposing inductive bias.\n",
"When that bias agrees with reality, \n",
"we get sample-efficient models \n",
"that generalize well to unseen data.\n",
"But of course, if those biases do not agree with reality,\n",
"e.g. if images turned out not to be translation invariant,\n",
"\n",
"\n",
"\n",
"## Convolutions\n",
"\n",
"Let's briefly review why the above operation is called a *convolution*. \n",
"In mathematics, the convolution between two functions, \n",
"say $f, g: \\mathbb{R}^d \\to R$ is defined as\n",
"\n",
"$$[f \\circledast g](x) = \\int_{\\mathbb{R}^d} f(z) g(x-z) dz$$\n",
"\n",
"That is, we measure the overlap beween $f$ and $g$ \n",
"when both functions are shifted by $x$ and 'flipped'. \n",
"Whenever we have discrete objects, the integral turns into a sum. \n",
"For instance, for vectors defined on $\\ell_2$, i.e.,\n",
"the set of square summable infinite dimensional vectors \n",
"with index running over $\\mathbb{Z}$ we obtain the following definition.\n",
"\n",
"$$[f \\circledast g](i) = \\sum_a f(a) g(i-a)$$\n",
"\n",
"For two-dimensional arrays, we have a corresponding sum \n",
"with indices $(i,j)$ for $f$ and $(i-a, j-b)$ for $g$ respectively. \n",
"This looks similar to definition above, with one major difference. \n",
"Rather than using $(i+a, j+b)$, we are using the difference instead. \n",
"Note, though, that this distinction is mostly cosmetic \n",
"since we can always match the notation by using $\\tilde{V}[a,b] = V[-a, -b]$ \n",
"to obtain $h = x \\circledast \\tilde{V}$. \n",
"Also note that the original definition is actually a *cross correlation*. \n",
"We will come back to this in the following section.\n",
"\n",
"\n",
"## Waldo Revisited\n",
"\n",
"Let's see what this looks like if we want to build an improved Waldo detector. The convolutional layer picks windows of a given size \n",
"and weighs intensities according to the mask $V$.\n",
" We expect that wherever the 'waldoness' is highest, \n",
" we will also find a peak in the hidden layer activations.\n",
"\n",
"![](../img/waldo-mask.jpg)\n",
"\n",
"There's just a problem with this approach: \n",
"so far we blissfully ignored that images consist \n",
"of 3 channels: red, green and blue. \n",
"In reality, images are quite two-dimensional objects \n",
"but rather as a 3rd order tensor,\n",
"e.g., with shape $1024 \\times 1024 \\times 3$ pixels. \n",
"Only two of these axes concern spatial relationships,\n",
"while the 3rd can be regarded as assigning \n",
"a multidimensional representation *to each pixel location*.\n",
"\n",
"We thus index $\\mathbf{x}$ as $x[i,j,k]$. \n",
"The convolutional mask has to adapt accordingly. \n",
"Instead of $V[a,b]$ we now have $V[a,b,c]$.\n",
"\n",
"Moreover, just as our input consists of a 3rd order tensor\n",
"it turns out to be a good idea to similarly formulate \n",
"our hidden representations as 3rd order tensors.\n",
"In other words, rather than just having a 1D representation\n",
"corresponding to each spatial location,\n",
"we want to have a multidimensional hidden representations \n",
"corresponding to each spatial location.\n",
"We could think of the hidden representation as comprising a number of 2D grids stacked on top of each other.\n",
"These are sometimes called *channels* or *feature maps*.\n",
"Intuitively you might imaginee that at lower layers,\n",
"some channels specialize to recognizing edges, \n",
"We can take care of this by adding a fourth coordinate to $V$ \n",
"via $V[a,b,c,d]$. Putting all together we have:\n",
"\n",
"$$h[i,j,k] = \\sum_{a = -\\Delta}^{\\Delta} \\sum_{b = -\\Delta}^{\\Delta} \\sum_c V[a,b,c,k] \\cdot x[i+a,j+b,c]$$\n",
"\n",
"This is the definition of a convolutional neural network layer. \n",
"There are still many operations that we need to address. \n",
"For instance, we need to figure out how to combine all the activations \n",
"to a single output (e.g. whether there's a Waldo in the image). \n",
"We also need to decide how to compute things efficiently, \n",
"how to combine multiple layers, and whether it is a good idea\n",
"to have many narrow or a few wide layers. \n",
"All of this will be addressed in the remainder of the chapter. \n",
"\n",
"\n",
"## Summary\n",
"\n",
"* Translation invariance in images implies that all patches of an image will be treated in the same manner.\n",
"* Locality means that only a small neighborhood of pixels will be used for computation.\n",
"* Channels on input and output allows for meaningful feature analysis.\n",
"\n",
"## Exercises\n",
"\n",
"1. Assume that the size of the convolution mask is $\\Delta = 0$. Show that in this case the convolutional mask implements an MLP independently for each set of channels.\n",
"1. Why might translation invariance not be a good idea after all? Does it make sense for pigs to fly?\n",
"1. What happens at the boundary of an image?\n",
"1. Derive an analogous convolutional layer for audio.\n",
"1. What goes wrong when you apply the above reasoning to text? Hint - what is the structure of language?\n",
"1. Prove that $f \\circledast g = g \\circledast f$.\n",
"\n",
"## Scan the QR Code to [Discuss](https://discuss.mxnet.io/t/2348)\n",
"\n",
"![](../img/qr_why-conv.svg)"
]
}
],
"metadata": {
"language_info": {
"name": "python"
}
},
"nbformat": 4,
"nbformat_minor": 2
}