Summary_of_Deep_Learning_Concepts.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Summary of Deep Learning Concepts",
      "version": "0.3.2",
      "provenance": []
    },
    "kernelspec": {
      "name": "python2",
      "display_name": "Python 2"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "[View in Colaboratory](https://colab.research.google.com/github/ppant/deeplearning.ai-notes/blob/master/Summary_of_Deep_Learning_Concepts.ipynb)"
      ]
    },
    {
      "metadata": {
        "id": "oWmGQ8lI6s4S",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Summary of concepts in Deep Learning\n",
        "---"
      ]
    },
    {
      "metadata": {
        "id": "-Tt6DgOD66sI",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Deep Learning is an emerging field which needs no introduction. The aim of this article is to collaboratively learn various concepts in Deep Learning in a concise manner. If you feel something can be added or updated please add a comment. I will keep adding new material to this article as well. "
      ]
    },
    {
      "metadata": {
        "id": "bQXUG3Qk7Mvi",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## How to use this article?\n",
        "\n",
        "Deep Learning has many parameters, hyperparameters and concepts. This article aims to give a quick refresher on some core topics, especially to those who are new to this field. Some use cases I can think of,\n",
        "-\tWhenever you encounter a term in Deep Learning online when surfing the web and cannot remember what it means, come here and do a quick find. \n",
        "-\tIf you are preparing for an interview for a ML role and want to quickly revise, this is a good place as being concise and complete was my primary motto"
      ]
    },
    {
      "metadata": {
        "id": "tZ1AxLTg_4wC",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Credits\n",
        "A big thank you to DeepLearning.ai team and their Deep Learning specialization on Coursera. All the material here including notations, concepts, some diagrams are a heavily shortened form of their excellent 5 course series."
      ]
    },
    {
      "metadata": {
        "id": "Zuwm_Yjp7Ycv",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Notation used throughout\n",
        "Refer this section for any variables used in the article\n",
        "\n",
        "notation | description\n",
        "--- | ---\n",
        "$m$ | number of training examples\n",
        "$n_x$ | number of features per training example\n",
        "$X$ | input matrix where each column is a training example\n",
        "$Y$ | output matrix where each column is the corresponding label of the training example in $X$, i.e. $Y[0]$ is the label for $X[0]$, the 1st training example\n",
        "$\\hat{Y}$ | predicted labels for new test inputs\n",
        "$Z$ | linear transformation of $X$\n",
        "$A$\t| non-linear transformation of $Z$, the result of an activation function\n",
        "$W$ |\tweights matrix for each feature in $X$\n",
        "$x$\t| features of one training example\n",
        "$y$\t| output label of one training example\n",
        "$\\hat{y}$\t| predicted output label of one training example\n",
        "$z$\t| linear transformation of $x$\n",
        "$a$\t| non-linear transformation of $z$, the result of an activation function\n",
        "$w$\t| weights matrix for $x$\n",
        "$b$\t| bias matrix\n",
        "$\\sigma$ | sigmoid function, $\\sigma(z)= \\frac{1}{(1 + e^{-z} )}$ and the output lies in between (0, 1) for any value of $z$\n",
        "$x_j^{(i)}$ | value of the feature j in i<sup>th</sup> training example \n",
        "$w_j^{(i)[k]}$ | value of the weight for j<sup>th</sup> hidden unit in k<sup>th</sup> layer of i<sup>th</sup> training example\n",
        "$L$ | total number of layers in a deep neural net (excluding input layer)\n",
        "$n^{[l]}$ |number of units in hidden layer $l$\n",
        "$X^{\\{t\\}}$, $Y^{\\{t\\}}$ | $X$ and $Y$ values for t<sup>th</sup> mini-batch in mini-batch gradient descend\n",
        "$J$ | cost function of the model considering all training examples\n",
        "$C$\t| number of classes in a multi-class classifier\n",
        "$X^{(i)<t>}$ | In sequence models, represents the t<sup>th</sup> element in i<sup>th</sup> training example\n",
        "$Y^{(i)<t>}$ | In sequence models, represents the output value of t<sup>th</sup> element in i<sup>th</sup> training example\n",
        "$T_X^{(i)}$ | In sequence models, represents the length of input sequence in i<sup>th</sup> training example\n",
        "$T_Y^{(i)}$ | In sequence models, represents the length of output sequence in i<sup>th</sup> training example\n",
        "\n"
      ]
    },
    {
      "metadata": {
        "id": "cyt39ZFv_u1-",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Logistic Regression, the building block of Deep Neural Nets\n",
        "\n",
        "It is a linear model for classification. The goal of the model is to predict probabilities of output labels for a given input.\n",
        "$$z= w^T x+b$$\n",
        "$$a=\\sigma(z)$$\n",
        "$$\\hat{y} = a$$\n",
        "\n",
        "Cross entropy loss for finding out how good the predictions are for a single training example,\n",
        "$$L(\\hat{y},y)= -(y log(⁡\\hat{y}) + (1-y)log(⁡\\hat{y}))$$\n",
        "\n",
        "Cost function for all examples,\n",
        "$$J= -\\frac{1}{m} \\sum_{i=1}^mL(\\hat{y}^{(i)} ,y^{(i)})$$\n",
        "This $J$ is used by an optimization algorithm (like gradient descend) to find optimal values for $w$ and $b$.\n"
      ]
    },
    {
      "metadata": {
        "id": "CApcuF65BuPL",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Shallow Neural Nets\n",
        "\n",
        "In logistic regression $z$ and $a$ are computed to obtain prediction for each training example. In a shallow neural net, this process is repeated twice before predicting the output label. In logistic regression,\n",
        "\n",
        "![logistic_regression_network](https://drive.google.com/uc?export=view&id=1dm9gVeDOf6FOZdaBhIHp94fkRPCP7_nN)\n",
        "\n",
        "whereas in a shallow net,\n",
        "\n",
        "![shallow_neural_network](https://drive.google.com/uc?export=view&id=1dFX5kBsG45RLvnAyFNl80TNdIN7UGizH)\n",
        "\n",
        "[1] and [2] are layers in the network. Layer [1] is a hidden layer as it is neither the input nor output. Layer [1] has three (hidden) units / neurons and layer [2] has one unit. The prediction for a training example $x$, is as follows in a shallow neural net,\n",
        "\n",
        "$$z^{[1]}= w^{[1]} x+b^{[1]}$$\n",
        "$$a^{[1]} = \\sigma(z^{[1]})$$\n",
        "$$z^{[2]} = w^{[2]}a^{[1]} +b^{[2]}$$\n",
        "$$\\hat{y}=a^{[2]} =\\sigma(z^{[2]})$$\n",
        "\n",
        "This process is extended to all training examples to obtain $Z^{[1]}$, $Z^{[2]}$, $A^{[1]}$, $A^{[2]}$, $\\hat{Y}$. If this process is extended to more than 2 hidden layers it is called a deep neural net!\n"
      ]
    },
    {
      "metadata": {
        "id": "gRTDte3UW3Dd",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Activation functions\n",
        "\n",
        "- sigmoid, $\\sigma(z)= \\frac{1}{1+e^{-z}}$\n",
        "  - σ(z) lies in between (0, 1)\n",
        "  - generally used for binary classification tasks in the last layer\n",
        "- $tanh(z)= \\frac{e^z  - e^{-z}}{e^z  + e^{-z}}$\n",
        "  - $tanh(z)$ lies in between (-1, 1)\n",
        "  - the graph is centered at 0, unlike sigmoid\n",
        "- $ReLU(z) = max (0,z)$\n",
        "  - both sigmoid and tanh slow down learning when $z$ is too small or high\n",
        "  - neural net learns much faster when compared to sigmoid or tanh \n",
        "  - generally used in the hidden layers\n",
        "- $Leaky\\ ReLU(z) = max⁡(0.01z,z)$"
      ]
    },
    {
      "metadata": {
        "id": "CnlEfi4HYPzG",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Deep Neural Nets\n",
        "\n",
        "Simply put, it is a neural network with multiple hidden layers. The number of layers $L$ and number of units in each layer are hyperparameters decided before training.\n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=1_qm8c14Gws-k_aR1zeBzlN2O0wvP1kgt\" height=\"250px\" alt=\"deep neural nets\" />\n",
        "</center>\n",
        "<caption>\n",
        "  <center>\n",
        "    <strong>Figure 1: </strong>\n",
        "    A 4 layer, fully connected deep neural network\n",
        "  </center>\n",
        "</caption>\n",
        "\n",
        "The above network has $L = 4$, $n^{[1]} = 3$, $n^{[2]} = 4$, $n^{[3]} = 3$ and $n^{[4]}=1$. $\\hat{Y} = A^L$ is the result for all training examples. $X = A^{[0]}$ is computed as,\n",
        "\n",
        "$$Z^{[1]} = W^{[1]}  A^{[0]} + b^{[1]}$$\n",
        "\n",
        "$$A^{[1]} = g^{[1]}( Z^{[1]})$$\n",
        "\n",
        "Similarly, the process is repeated for layers [2], [3] and [4]\n",
        "$$\\hat{Y}= A^{[L=4]}= g^{[4]}( Z^{[4]})$$\n",
        "\n",
        "Here $g^{[l]}$ is the activation function used in layer $l$. When implemented with numpy vectors, all computations are parallelized across training examples and is called a vectorized implementation. Without vectorization, the neural net has to loop over training examples one by one to complete one epoch of training which slows down learning.\n",
        "\n",
        "Each training example $x^{(i)}$, is passed through the net to obtain the prediction $\\hat{y}^{(i)}$ from the last layer. This step is called **forward propagation** in the entire process. $\\hat{y}^{(i)}$ is compared with $y^{(i)}$ using $J$ to obtain the error in prediction. This error is passed back from layer $[L]$ to $[L-1]$ to $[L-2]$ and so on to $[1]$ to adjust $W^{[l]}$ , $b^{[l]}$ at each layer so that the next prediction causes smaller error. This step of passing back the error is called **back propagation** in the entire process. Every time error is passed back, the amount of change the system makes to the parameters $W^{[l]}$, $b^{[l]}$ is governed by a hyperparameter called learning rate, $\\alpha$.\n"
      ]
    },
    {
      "metadata": {
        "id": "RTdp6tJvicA2",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Dimensionality checks\n",
        "\n",
        "These formulae can help debug [dimensions](https://docs.scipy.org/doc/numpy-1.13.0/reference/generated/numpy.ndarray.shape.html) of various matrices during implementing deep neural nets\n",
        "- $w^{[l]}.shape = (n^{[l]}, n^{[l-1]})$\n",
        "- $b^{[l]}.shape = (n^{[l]}, 1)$\n",
        "- $A^{[l]}.shape = Z^{[l]}.shape = (n^{[l]}, m)$\n"
      ]
    },
    {
      "metadata": {
        "id": "xTONqYzKjHfX",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Hyperparameters to choose\n",
        "\n",
        "$W^{[l]}$, $b^{[l]}$ are parameters of the neural net and are learned during the training phase. Hyperparameters are manually set by the developer before training.\n",
        "\n",
        "- learning rate alpha, $\\alpha$ - the rate at which parameters are updated to bring the predictions close to actual values\n",
        "- number of epochs – After training with the entire training data once, one epoch is completed. This parameter controls how many times this should be repeated.\n",
        "- hidden layers, L – how many hidden layers in the Deep Neural Net (DNN)\n",
        "- hidden units per layer – values for $n^{[1]}$, $n^{[2]}$, $n^{[3]}$,…, $n^{[L]}$\n",
        "- activation functions – [activation function](#activation-functions) to use in each layer, $g^{[1]}$, $g^{[2]}$, $g^{[3]}$,…, $g^{[L]}$\n"
      ]
    },
    {
      "metadata": {
        "id": "XZ6cdSdH8LEP",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Optimizing Deep Neural Networks"
      ]
    },
    {
      "metadata": {
        "id": "gEzV5faK67hu",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Data splitting – All data from same distribution\n",
        "\n",
        "All the available labelled data is split into,\n",
        "\n",
        "<img src=\"https://drive.google.com/uc?export=view&id=1IVxLaZtnxIJNmXwFAgmHdDR6gn-7xf6Z\" alt=\"data splitting in same distribution\" />\n",
        "\n",
        "-\tTrain data – Majority of the data is used for training\n",
        "-\tDev data – Also called validation set / data. Used for validating the model and hyperparameter tuning\n",
        "-\tTest data – Used for validating the final chosen model\n"
      ]
    },
    {
      "metadata": {
        "id": "5tgmguu78Gc_",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "#### Error Types\n",
        "\n",
        "As shown in Figure 2, a DNN has a train and dev error besides the test error\n",
        "\n",
        "- Avoidable bias – difference between human error (the benchmark many a times) and training error. Possible solutions to reduce this are:\n",
        "    - Train on a bigger network (increase $L$ or $n^{[l]}$)\n",
        "    - Increase number of epochs\n",
        "    - Change network architecture\n",
        "- Variance – difference between training error and dev error. This happens due to overfitting to training data. Possible solutions to reduce this are:\n",
        "    - Train on more data\n",
        "    - Regularization\n",
        "    - Change network architecture\n",
        "    \n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=1d438hrqAbvGFRLcXdERzSV2dJz1su2hV\" alt=\"errors when all data is from same distribution\" />\n",
        "</center>\n",
        "<center>\n",
        "  <caption>\n",
        "    <strong>Figure 2: </strong>\n",
        "    Range of each error\n",
        "  </caption>\n",
        "</center>"
      ]
    },
    {
      "metadata": {
        "id": "tKy-BC7u_k_V",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Data Splitting – Data from different distributions\n",
        "\n",
        "Ideally train, dev and test sets should be from the same data distribution for best results. But sometimes big enough data might not be available for performing a deep learning experiment. For example, for creating a DNN to classify 100 pictures of your 2 cats, training on cat pictures from internet and testing on your 100 cat pictures may not yield good results as data distributions are different. In such situations,\n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=1VFingcLOJDHFw9RIYz8sDnK7BZ3xEUp3\" height=\"75px\" alt=\"split limited data sample figure\" />\n",
        "</center>\n",
        "\n",
        "split the available 100 cat pictures 50-50. Mix the Train (50) pictures with internet pictures like so\n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=1xZvPvNkKEQTpEmp1wjnwZ5CMnOjAL5iM\" alt=\"how to use the split limited data figure\" />\n",
        "</center>\n",
        "\n",
        "As the train and dev data are different distributions, comparing the training and dev errors does not clarify if it is due to high variance or due to data mismatch. Hence, the train data is split into train and training-dev after mixing your 50 cat pictures.\n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=1PXrBR1meIcWKDy_U0ygYVCNfJGtPR0OT\" alt=\"final data after mixing all available data sources figure\" />\n",
        "</center>\n",
        "\n",
        "Now as train and training-dev sets are from same distribution, it can be understood the root cause of the problem as either bias or variance or data mismatch.\n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=13FSFXlY-ivHnPLrQgHpBbaA9yfFVfUY3\" alt=\"range of errors when data is from different distributions figure\" />\n",
        "</center>\n",
        "<center>\n",
        "  <caption>\n",
        "    <strong>Figure 3: </strong>\n",
        "    Range of errors when not all data is from same distribution\n",
        "  </caption>\n",
        "</center>\n",
        "\n",
        "As shown in Figure 3, as training-dev set and dev-set are from different data distributions, the difference between their errors is due to data mismatch.\n"
      ]
    },
    {
      "metadata": {
        "id": "PiHZj81vFAGg",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Regularization\n",
        "\n",
        "When the neural net over fits (high variance) the model to training data, predictions on unseen dev set can be poor. Regularization reduces the impact of (various) neurons in the model so that it can generalize better to unseen inputs. lambda $\\lambda$, is the hyperparameter which controls the amount of regularization used in L1 and L2 algorithms. Here are some algorithms / ideas for regularization,\n",
        "\n",
        "- L1 – Uses L1-norm to penalize $W$’s\n",
        "- L2 – Uses L2-norm to penalize $W$’s\n",
        "- Dropout – Randomly zeros (drops) some neurons from the network thus making it simpler and generalize better. $keep\\_prob$ is the hyperparamater which is the probability of retaining a neuron. Different layers can have different values of $keep\\_prob$ based on density of connections\n",
        "- Data augmentation – transform, randomly crop and translate input training images\n",
        "- Early stopping – after every epoch compute dev error and once it starts increasing, stop the training though training error continues to decrease (sign for overfitting)\n"
      ]
    },
    {
      "metadata": {
        "id": "4WC8LRtMFvqW",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Normalization\n",
        "\n",
        "Normalize input features with varying ranges to learn faster. Normalizing, sets $\\mu=0$ and $\\sigma^2=1$ for all training examples.\n",
        "\n",
        "- Batch normalization – the idea of normalizing inputs is extended to all layers. $z^{[l]}$ is normalized before applying the activation function. The flow of parameters would then be,\n",
        "\n",
        "$$X \\xrightarrow{W^{[1]}, b^{[1]}} Z^{[1]} \\xrightarrow{\\beta^{[1]},\\gamma^{[1]}} \\tilde{Z}^{[1]} \\to a^{[1]} = g( \\tilde{Z}^{[1]}) \\xrightarrow{W^{[2]}, b^{[2]}} Z^{[2]}…$$\n",
        "\n",
        "> $\\tilde{Z}^{[1]}$ is the normalized $Z^{[1]}$ computed using parameters $\\beta^{[1]}$, $\\gamma^{[1]}$. Just like $W^{[l]}$ and $b^{[l]}$ are parameters that are learned during training, $\\beta^{[l]}$ and $\\gamma^{[l]}$ are too. \n",
        "\n",
        "> In case of mini-batch gradient descend, exponential weighted averages of $\\mu$ and $\\sigma^2$ across batches are saved during training. These are used to compute $\\tilde{Z}^{[l]\\{t\\}})$ during inference time.\n"
      ]
    },
    {
      "metadata": {
        "id": "mrc6yyA3J42n",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Train faster and better\n",
        "\n",
        "- Mini-batch gradient descend – if the training set size is huge, models learn better, but each epoch takes longer. In mini-batch gradient descend, the inputs are sliced into batches and a step is taken by gradient descend after training on a mini-batch. Mini-batch size is generally chosen in between 1 and $m$ to take advantage of both vectorization and quicker steps. Typical batch sizes are 64, 128, 256 or 512 training examples, such that each mini-batch fits in memory of CPU / GPU\n",
        "\n",
        "- Gradient descend with Momentum – mini-batch gradient descend introduces oscillations which may slow down reaching the optimum. Momentum solves this problem by adding a moving average like affect and dampening the oscillations to reach the optimum faster. Momentum $\\beta$, controls the size of the sliding window $\\approx \\frac{1}{1- β}$\n",
        "\n",
        "- RMS Prop – Guides the gradient descend algorithm towards the minimum by taking longer steps in the dimensions farther away from minimum and smaller steps in the dimensions closer to minimum. $\\beta_2$  and $\\epsilon$ are hyperparameters for this optimization. $\\epsilon$ is not so important and is added only to avoid division by zero error and is generally set to $10^{-8}$\n",
        "\n",
        "- Adam – combines ideas from gradient descend with momentum and RMS prop and uses $\\beta$, $\\beta_2$  and $\\epsilon$ as hyperparameters\n",
        "\n",
        "- Learning rate decay – mini-batch gradient descend adds oscillations around the minimum. Adding a decay to learning rate converges better. So $\\alpha$ is no longer a constant and becomes\n",
        "\n",
        "$$\\alpha=\\frac{1}{(1 + decay\\_rate \\times epoch\\_number) \\times \\alpha_0}$$\n"
      ]
    },
    {
      "metadata": {
        "id": "Z5OheTD8L82x",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Hyperparameter Tuning\n",
        "\n",
        "As there are many hyperparameters to set before training, it is important to realize that not all of them are equally important. For example, $\\alpha$ is more important $\\lambda$, so fine tuning $\\alpha$ first is better. Some approaches for tuning a hyperparameter are,\n",
        "\n",
        "- Grid based search – create a table of combinations of hyperparameter 1 and 2 values. For each combination evaluate on dev set to find the best combination\n",
        "\n",
        "- Random based search – randomly select combinations of values for hyperparameters 1 and 2. For each combination evaluate on dev set to find the best combination. After performing a random search in a broad domain of values, a more fine-grained search in the area(s) of interest using the results from coarse random search can be performed. It is important to scale the hyperparameters before selecting values uniformly at random\n",
        "\n",
        "- Panda VS Caviar approach – If the model is complex that multiple combinations cannot be tested, it is a better idea to baby sit watching how $J$ varies with time and change hyperparameter values at runtime.\n"
      ]
    },
    {
      "metadata": {
        "id": "RAGhT4dLMgKo",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Multiclass classification\n",
        "\n",
        "Softmax layer is used as the final layer to classify into $C$ classes. The activations from final layer $L$ are computed as,\n",
        "\n",
        "$$a_i^{[L]} = \\frac{t_i}{\\sum_{j=1}^C t_i}$$\n",
        "\n",
        "where $t_i = (e^{z_i})^{[L]}$\n"
      ]
    },
    {
      "metadata": {
        "id": "eC3vGlRyNkNl",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Transfer Learning\n",
        "\n",
        "Use the learned parameters from one model to another. It is done by replacing the last few layers in the original trained network. The new layers can then be trained using the new dataset of interest. This is generally applicable when features identified by initial layers of an existing model can be re-used for a another task.\n"
      ]
    },
    {
      "metadata": {
        "id": "CTtgXHRKNxPT",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Convolutional Neural Nets\n",
        "\n",
        "A class of deep neural nets for computer vision tasks. It is expected of a DNN to identify the features from $X$ without the need for hand tuning them. Therefore, in computer vision tasks images, videos are generally used as is as $X$. Without feature engineering if the image is passed as is to the network the number of parameters to learn can be quite high based on the image’s resolution. For example, if the input image is (width, height, RGB channels) = (1000, 1000, 3) dimensional, fully connecting it (as shown in Figure 1) to a layer with $n^{[1]} = 1000$, would imply $W.shape = (1000, 3\\times10^6)$, i.e. 3 billion parameters. Training so many parameters demands lot of training data and hence existing ideas from DNN are not used for computer vision applications. Therefore, a new class called Convolutional Neural Nets (CNN) is studied.\n",
        "\n",
        "It is known that earlier layers in a DNN identify simple features like edges and the later ones detect more complex shapes in a given image. The operator, convolution $\\ast$, in Mathematics solves both the above problems – identify edges in earlier layers and shapes in the later, requires fewer parameters than a fully connected DNN.\n"
      ]
    },
    {
      "metadata": {
        "id": "D7bmAD4VPT5s",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Working of a convolution operation\n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=1i8dczLaLdZ6OYpQXBDrIW7qSwK-CjROb\" alt=\"convolution operator animation\" />\n",
        "</center>\n",
        "<center>\n",
        "  <caption>\n",
        "    <strong>Figure 4:</strong> Convolution operator in action\n",
        "  </caption>\n",
        "  <p>\n",
        "    <small>\n",
        "      <strong>Source:</strong> Coding exercise “Convolution model - Step by Step - v2” in the course https://www.coursera.org/learn/convolutional-neural-networks/\n",
        "    </small>\n",
        "  </p>\n",
        "</center>\n",
        "\n",
        "- The number of channels (the 3rd dimension) in the input layer should match the number of dimension in convolution filter\n"
      ]
    },
    {
      "metadata": {
        "id": "BIDNJPYERINP",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Padding\n",
        "\n",
        "Due to the way $\\ast$ works, cells on the edges contribute lesser compared to inner cells in the output layer. Strip(s) of zeros are added to input layer before $\\ast$ operation which is called padding, $p$ to solve this problem. There are two types of padding,\n",
        "\n",
        "- Same $\\implies p = 0$\n",
        "\n",
        "- Valid $p = \\frac{f-1}{2}$ where $f$ is dimension of the convolution filter. More on $f$ below.\n"
      ]
    },
    {
      "metadata": {
        "id": "R67_XjEOR9ah",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Dimensionality involving a convolution operation \n",
        "\n",
        "$$(n, n, \\#channels) \\ast (f, f, \\#channels) \\to (\\lfloor \\frac{n + 2p - f}{s + 1} \\rfloor,\\lfloor \\frac{n + 2p - f}{s + 1} \\rfloor, \\#filters)$$\n",
        "\n",
        "where $n$ = dimension of input layer / image\n",
        "\n",
        "> $f$ = dimension of convolution filter\n",
        "\n",
        "> $p$ = amount of padding to input layer\n",
        "\n",
        "> $s$ = stride length of convolution filter on input layer\n",
        "\n",
        "> $\\# filters$ = number of convolution filters used on input layer\n",
        "\n",
        "For Figure 4: $n = 5, \\# channels = 1, f = 3, p = 0, s = 1, \\# filters = 1$\n"
      ]
    },
    {
      "metadata": {
        "id": "sbYYOyJfVglB",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Pooling\n",
        "\n",
        "Another type of operator like $\\ast$, which is mainly used to shrink the height and width of the input. Just like $\\ast$, pooling layers also are filters which run across the input. However, they do not have any parameters to learn.\n",
        "\n",
        "- Max Pooling – pick the max value at every position of filter on the input\n",
        "\n",
        "- Average Pooling – pick the average value at every position of filter on the input\n"
      ]
    },
    {
      "metadata": {
        "id": "ZyJQQ50JcETB",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Sequence Models - [ Work in Progress ]\n",
        "\n",
        "A class of Deep Neural Networks for modelling inputs that have an ordering or exist in sequences. For example, a sequence of words is a sentence, a sequence of air pressure values (over time) is an audio / sound. \n",
        "\n",
        "### Natural Language Processing (NLP)\n",
        "\n",
        "Sequence modelling techniques are widely used for processing Natural (Human) language. Since neural networks work on matrices of numbers a simple way to encode (English) words to numbers is to one-hot encode them. In order to do that, assuming there are 10000 words in English dictionary, every word is assigned a unique random number between (10000, 1). Then, if the word 'Aaron' is assigned number 3, its one-hot encoded matrix would be,\n",
        "\n",
        "<center>\n",
        "  $\n",
        "  \\begin{bmatrix}\n",
        "    0 \\\\\n",
        "    0 \\\\\n",
        "    1 \\\\\n",
        "    0 \\\\\n",
        "    . \\\\\n",
        "    . \\\\\n",
        "    . \\\\\n",
        "    0 \\\\\n",
        "  \\end{bmatrix}_{10000\\times 1}\n",
        "  $\n",
        "</center>\n",
        "\n",
        "After every word is converted to its one-hot representation, the sentence is fed into a Recurrent Neural Network (RNN) as shown in Figure 5. For a given sentence say, \"Aaron bikes to school everyday\", $x^{<1>}$ would be one-hot encoding of 'Aaron', $x^{<2>}$ would be one-hot encoding of 'bikes' and so on. If the goal of the RNN is to find the parts of speech of each word in the sentence, then  $y^{<1>}$ would be parts of speech for 'Aaron', $y^{<2>}$ would be parts of speech for 'bikes' and so on. The training data for this task would be, X = one-not encoded words of English sentences, and Y = parts of speech for each word for each sentence.\n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=1FGV5ZaPfAwsRJZJaNzbj7iO2D1Uc9MhH\" alt=\"a recurrent neural network\" />\n",
        "</center>\n",
        "<center>\n",
        "  <caption>\n",
        "    <strong>Figure 5:</strong> Recurrent Neural Network\n",
        "  </caption>\n",
        "</center>\n",
        "\n",
        "### Why RNNs and not just use DNNs?\n",
        "\n",
        "Just like CNNs are well suited for Computer Vision tasks, RNNs are designed for tasks which have a temporal nature. RNNs,\n",
        "\n",
        "\n",
        "*   allow outputs to be of different lengths, i.e. $T_X \\neq T_Y$, for example in the task of Machine Translation where length of output sentence depends on input sentence\n",
        "*   can share features learned accross different positions of text (in NLP)\n",
        "*   have fewer parameters to compute compared to DNNs just like in CNNs\n",
        "\n",
        "[The Unreasonable Effectiveness of Recurrent Neural Networks](http://karpathy.github.io/2015/05/21/rnn-effectiveness/) blog post talks about various applications of RNNs besides NLP.\n",
        "\n"
      ]
    },
    {
      "metadata": {
        "id": "pnQIrImRM5Xn",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Forward Propagation in RNNs\n",
        "\n",
        "<center>\n",
        "  <p>$a^{<t>} = g_1(W_{aa}a^{<t-1>} + W_{ax}x^{<t>} + b_a)$</p>\n",
        "  <p>$\\hat{y}^{<t>} = g_2(W_{ya}a^{<t>} + b_y)$</p>\n",
        "</center>\n",
        "\n",
        "where \n",
        "\n",
        "* $a^{<0>} = \\vec{0}$, usually\n",
        "* $W_{aa}, W_{ax}, W_{ya}, b_a$ and $b_y$ are parameters learned by gradient descend\n",
        "* $g_1$ is usually tanh or ReLU and $g_2$ is usually sigmoid or softmax\n",
        "\n",
        "Note that, the parameters are shared across the time steps &lt;t&gt;. The notation is however simplified to,\n",
        "\n",
        "<center>\n",
        "  <p>$a^{<t>} = g(W_a[a^{<t-1>}, x^{<t>}] + b_a)$</p>\n",
        "  <p>$\\hat{y}^{<t>} = g(W_ya^{<t>} + b_y)$</p>\n",
        "</center>\n",
        "\n",
        "where\n",
        "\n",
        "* $W_a$ is column wise concatenated matrix of $W_{aa}$ and $W_{ax}$\n",
        "* $[a^{<t-1>}, x^{<t>}]$ is concatenated row wise i.e.\n",
        "\n",
        "<center>\n",
        "$\n",
        "  \\begin{bmatrix}\n",
        "      W_{aa} & W_{ax}\n",
        "  \\end{bmatrix}\n",
        "  \\begin{bmatrix}\n",
        "      a^{<t-1>} \\\\\n",
        "      x^{<t>}\n",
        "  \\end{bmatrix} = W_{aa}a^{<t-1>} + W_{ax}x^{<t>}\n",
        "$\n",
        "</center>\n",
        "\n",
        "### Back Propagation in RNNs\n",
        "\n",
        "In Figure 6, it can be seen how parameters flow to compute loss in forward propagation step and how gradient descend flows the derivates of Loss, $L$ back to adjust the parameters via back propagation.\n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=16DR4wsumB0sguKDPWRQf5-_Bx2kC84cu\" alt=\"recurrent neural network computational graph\" />\n",
        "</center>\n",
        "<center>\n",
        "  <caption>\n",
        "    <strong>Figure 6:</strong> Recurrent Neural Network Computational Graph\n",
        "  </caption>\n",
        "</center>\n",
        "\n",
        "<br />\n",
        "In the form of equations, first $L^{<t>}$ is computed using cross entropy loss like before. Final loss, $L$ is a summation of losses for all $t$\n",
        "\n",
        "<center>\n",
        "  <p>$L^{<t>}(\\hat{y}^{<t>}, y^{<t>}) = - (y^{<t>}log(\\hat{y}^{<t>}) - (1-y^{<t>})log(1-\\hat{y}^{<t>}))$</p>\n",
        "  <p>$L(\\hat{y}, y) = \\sum_{t=1}^{T_y} L^{<t>}(\\hat{y}^{<t>}, y^{<t>})$</p>\n",
        "</center>\n"
      ]
    },
    {
      "metadata": {
        "id": "374uU6b4_zLs",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Language Model\n",
        "\n",
        "Grammatically and logically, \"Ram ate an apple\" is more likely than \"Ram <b>an ate</b> apple\". The goal of the language model is to assign a higher probability for the first sentence. In other words the language model should,\n",
        "\n",
        "<center>\n",
        "  $P(y^{<1>} = Ram,\\ y^{<2>} = ate,\\ y^{<3>} = an,\\ y^{<4>} = apple)\\ \\mathbf{>}\\ P(y^{<1>} = Ram,\\ y^{<2>} = an,\\ y^{<3>} = ate,\\ y^{<4>} = apple)$\n",
        "</center>\n",
        "\n",
        "For this task, a one-to-many RNN is used. $y^{<t>}$ are the probabilities of all words in vocabulary to be present at position $<t>$ in a sentence. $y^{<t-1>}$ is fed as input, $x^{<t>}$, making it a conditional probabilty, $P(y^{<2>} = ate\\ |\\ y^{<1>} = Ram)$\n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=181G51N_MwiB-dz9ufBsXOSrmcALILz_o\" alt=\"one-to-many RNN for modelling language\" />\n",
        "</center>\n",
        "<center>\n",
        "  <caption>\n",
        "    <strong>Figure 7:</strong> one-to-many RNN for modelling language\n",
        "  </caption>\n",
        "</center>\n",
        "\n",
        "Training this on a huge corpus of text, models the sequence of words in a language. Using the conditional probabilities obtained at each $<t>$, the probability of a sentence can be found,\n",
        "\n",
        "<center>\n",
        "  $P(y^{<1>} = Ram,\\ y^{<2>} = ate,\\ y^{<3>} = an,\\ y^{<4>} = apple) = P(y^{<1>} = Ram) \\times P(y^{<2>} = ate\\ |\\ y^{<1>} = Ram) \\times P(y^{<3>} = an\\ |\\ y^{<1>} = Ram, \\ y^{<2>} = ate) \\times P(y^{<4>} = apple\\ |\\ y^{<1>} = Ram, \\ y^{<2>} = ate, \\ y^{<3>} = an)$\n",
        "</center>\n",
        "\n",
        "<br />\n",
        "$P(y^{<3>} = an\\ |\\ y^{<1>} = Ram, \\ y^{<2>} = ate)$ is obtained from the 3<sup>rd</sup> neuron and so on. As the vocabulary cannot incorporate all the words that ever appear, a special &lt;UNK> token is used to represent all the words out of vocabulary. Similarly character level language models can be created where each character would be $\\hat{y}^{<t>}$ and this problem of &lt;UNK> words impacting the accuracy could be mitigated. The problem with character models is that the sequences would be much longer and RNNs cannot carry very long range dependencies. Also, character models are more computationally intensive and so not common.\n"
      ]
    },
    {
      "metadata": {
        "id": "Mb_eN0vfD8gg",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Gated Recurrent Units (GRU)\n",
        "\n",
        "RNNs have the problem of vanishing gradients if the sentences are long just like in DNNs. Long term dependencies are quite common in English as a word in the beginning of the sentence can dictate the state of a word in the end of the sentence. To enable long term dependencies, GRU's introduce a concept called a memory cell. \n",
        "\n",
        "<center>\n",
        "  <img src=\"https://drive.google.com/uc?export=view&id=1aQNuDtnrP0wZ26-AgabAeKm41uV8vSVF\" alt=\"RNN and GRU cells\" />\n",
        "</center>\n",
        "<center>\n",
        "  <caption>\n",
        "    <strong>Figure 8:</strong> RNN and GRU cells\n",
        "  </caption>\n",
        "</center>\n",
        "\n",
        "<br />\n",
        "<center>\n",
        "  <p>$\\tilde{c}^{<t>} = tanh(W_c[c^{<t-1>},\\ x^{<t>}] + b_c) $</p>\n",
        "  <p>$\\Gamma_u = \\sigma(W_u[c^{<t-1>},\\ x^{<t>}] + b_u) $</p>\n",
        "</center>\n",
        "\n",
        "TODO"
      ]
    },
    {
      "metadata": {
        "id": "MTDsAEpJWEMB",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Deep Learning Hyperparameters\n",
        "\n",
        "Hyperparameter | Symbol | Common Values\t|\n",
        "--- | --- | --- | ---\n",
        "regularization | $\\lambda$ | | also called, “weight decay”\n",
        "learning rate | $\\alpha$\t| 0.01 | \n",
        "keep_prob | | 0.7 | from Dropout regularization\n",
        "momentum | $\\beta$ | 0.9 | also used in Adam \n",
        "mini-batch size |  $t$\t| 64, 128, 256, 512\t| \n",
        "RMS Prop | $\\beta_2$ | 0.999 | also used in Adam \n",
        "learning rate decay | | | also called decay_rate\n",
        "filter size | $f^{[l]}$\t|\t| In CNN, size of a filter in layer $l$\n",
        "stride | $s^{[l]}$ | | In CNN, stride length in layer $l$\n",
        "padding |  $p^{[l]}$ | | In CNN, padding in layer $l$\n",
        "\\# filters | $n_c^{[l]}$ | | In CNN, number of filters used in layer $l$\n",
        "\n",
        "\n",
        "\t\t\t\n",
        "\t\t\t\n"
      ]
    }
  ]
}