chapter_multilayer-perceptrons/numerical-stability-and-init.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Numerical Stability and Initialization\n",
    "\n",
    ":label:`sec_numerical_stability`\n",
    "\n",
    "\n",
    "\n",
    "Thus far, every model that we have implemented\n",
    "required that we initialize its parameters \n",
    "according to some pre-specified distribution.\n",
    "Until now, we took the initialization scheme for granted,\n",
    "glossing over the details of how these these choices are made.\n",
    "You might have even gotten the impression that these choices\n",
    "are not especially important.\n",
    "To the contrary, the choice of initialization scheme\n",
    "plays a significant role in neural network learning,\n",
    "and it can be crucial for maintaining numerical stability.\n",
    "Moreover, these choices can be tied up in interesting ways\n",
    "with the choice of the nonlinear activation function.\n",
    "Which function we choose and how we initialize parameters\n",
    "can determine how quickly our optimization algorithm converges.\n",
    "Poor choices here can cause us to encounter\n",
    "exploding or vanishing gradients while training.\n",
    "In this section, we delve into these topics with greater detail\n",
    "and discuss some useful heuristics\n",
    "that you will find useful\n",
    "throughout your career in deep learning.\n",
    "\n",
    "\n",
    "## Vanishing and Exploding Gradients\n",
    "\n",
    "Consider a deep network with $L$ layers,\n",
    "input $\\mathbf{x}$ and output $\\mathbf{o}$.\n",
    "With each layer $l$ defined by a transformation $f_l$\n",
    "parameterized by weights $\\mathbf{W}_l$\n",
    "our network can be expressed as:\n",
    "\n",
    "$$\\mathbf{h}^{l+1} = f_l (\\mathbf{h}^l) \\text{ and thus } \\mathbf{o} = f_L \\circ \\ldots, \\circ f_1(\\mathbf{x}).$$\n",
    "\n",
    "If all activations and inputs are vectors,\n",
    "we can write the gradient of $\\mathbf{o}$ with respect to \n",
    "any set of parameters $\\mathbf{W}_l$ as follows:\n",
    "\n",
    "$$\\partial_{\\mathbf{W}_l} \\mathbf{o} = \\underbrace{\\partial_{\\mathbf{h}^{L-1}} \\mathbf{h}^L}_{:= \\mathbf{M}_L} \\cdot \\ldots, \\cdot \\underbrace{\\partial_{\\mathbf{h}^{l}} \\mathbf{h}^{l+1}}_{:= \\mathbf{M}_l} \\underbrace{\\partial_{\\mathbf{W}_l} \\mathbf{h}^l}_{:= \\mathbf{v}_l}.$$\n",
    "\n",
    "In other words, this gradient is\n",
    "the product of $L-l$ matrices\n",
    "$\\mathbf{M}_L \\cdot \\ldots, \\cdot \\mathbf{M}_l$\n",
    "and the gradient vector $\\mathbf{v}_l$.\n",
    "Thus we are susceptible to the same \n",
    "problems of numerical underflow that often crop up \n",
    "when multiplying together too many probabilities.\n",
    "When dealing with probabilities, a common trick is to\n",
    "switch into log-space, i.e., shifting \n",
    "pressure from the mantissa to the exponent \n",
    "of the numerical representation. \n",
    "Unfortunately, our problem above is more serious:\n",
    "initially the matrices $M_l$ may have a wide variety of eigenvalues.\n",
    "They might be small or large, and \n",
    "their product might be *very large* or *very small*.\n",
    "\n",
    "The risks posed by unstable gradients \n",
    "go beyond numerical representation.\n",
    "Gradients of unpredictable magnitude \n",
    "also threaten the stability of our optimization algorithms.\n",
    "We may be facing parameter updates that are either\n",
    "(i) excessively large, destroying our model\n",
    "(the *exploding* gradient problem);\n",
    "or (ii) excessively small \n",
    "(the *vanishing gradient problem*),\n",
    "rendering learning impossible as parameters \n",
    "hardly move on each update.\n",
    "\n",
    "\n",
    "### Vanishing Gradients\n",
    "\n",
    "One frequent culprit causing the vanishing gradient problem\n",
    "is the choice of the activation function $\\sigma$\n",
    "that is appended following each layer's linear operations.\n",
    "Historically, the sigmoid function \n",
    "$1/(1 + \\exp(-x))$ (introduced in :numref:`sec_mlp`)\n",
    "was popular because it resembles a thresholding function.\n",
    "Since early artificial neural networks were inspired\n",
    "by biological neural networks,\n",
    "the idea of neurons that fire either *fully* or *not at all*\n",
    "(like biological neurons) seemed appealing.\n",
    "Let us take a closer look at the sigmoid\n",
    "to see why it can cause vanishing gradients."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load ../utils/djl-imports\n",
    "%load ../utils/plot-utils\n",
    "%load ../utils/DataPoints.java\n",
    "%load ../utils/Training.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import org.apache.commons.lang3.ArrayUtils;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NDManager manager = NDManager.newBaseManager();\n",
    "NDArray x = manager.arange(-8.0f, 8.0f, 0.1f);\n",
    "x.setRequiresGradient(true);\n",
    "NDArray y = null;\n",
    "try(GradientCollector gc = Engine.getInstance().newGradientCollector()){\n",
    "    y = Activation.sigmoid(x);\n",
    "    gc.backward(y);\n",
    "}\n",
    "\n",
    "NDArray res = x.getGradient();\n",
    "\n",
    "int xLength = (int) x.size();\n",
    "int yLength = (int) y.size();\n",
    "\n",
    "float[] X = new float[xLength];\n",
    "float[] Y = new float[yLength];\n",
    "float[] Z = new float[yLength];\n",
    "\n",
    "X = x.toFloatArray();\n",
    "Y = y.toFloatArray();\n",
    "Z = res.toFloatArray();\n",
    "\n",
    "String[] groups = new String[xLength*2];\n",
    "Arrays.fill(groups, 0, xLength, \"sigmoid\");\n",
    "Arrays.fill(groups, xLength, xLength * 2, \"gradient\");\n",
    "\n",
    "Table data = Table.create(\"Data\").addColumns(\n",
    "    FloatColumn.create(\"X\", ArrayUtils.addAll(X, X)), \n",
    "    FloatColumn.create(\"grad of relu\", ArrayUtils.addAll(Y, Z)),\n",
    "    StringColumn.create(\"groups\", groups)\n",
    ");\n",
    "render(LinePlot.create(\"\", data, \"x\", \"grad of relu\", \"groups\"), \"text/html\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the sigmoid's gradient vanishes\n",
    "both when its inputs are large and when they are small.\n",
    "Moreover, when backpropagating through many layers,\n",
    "unless we are in the Goldilocks zone, where \n",
    "the inputs to many of the sigmoids are close to zero, \n",
    "the gradients of the overall product may vanish.\n",
    "When our network boasts many layers,\n",
    "unless we are careful, the gradient \n",
    "will likely be cut off at *some* layer.\n",
    "Indeed, this problem used to plague deep network training.\n",
    "Consequently, ReLUs, which are more stable\n",
    "(but less neurally plausible), \n",
    "have emerged as the default choice for practitioners.\n",
    "\n",
    "\n",
    "### Exploding Gradients\n",
    "\n",
    "The opposite problem, when gradients explode,\n",
    "can be similarly vexing.\n",
    "To illustrate this a bit better,\n",
    "we draw $100$ Gaussian random matrices\n",
    "and multiply them with some initial matrix.\n",
    "For the scale that we picked\n",
    "(the choice of the variance $\\sigma^2=1$),\n",
    "the matrix product explodes.\n",
    "When this happens due to the initialization \n",
    "of a deep network, we have no chance of getting\n",
    "a gradient descent optimizer to converge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "5"
    }
   },
   "outputs": [],
   "source": [
    "NDArray M = manager.randomNormal(new Shape(4,4));\n",
    "System.out.println(\"A single matrix: \" + M);\n",
    "for(int i=0; i < 100; i++){\n",
    "    M = M.dot(manager.randomNormal(new Shape(4,4)));\n",
    "}\n",
    "\n",
    "System.out.println(\"after multiplying 100 matrices: \" + M);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Symmetry\n",
    "\n",
    "Another problem in deep network design\n",
    "is the symmetry inherent in their parametrization.\n",
    "Assume that we have a deep network\n",
    "with one hidden layer and two units, say $h_1$ and $h_2$.\n",
    "In this case, we could permute the weights $\\mathbf{W}_1$\n",
    "of the first layer and likewise permute \n",
    "the weights of the output layer\n",
    "to obtain the same function.\n",
    "There is nothing special differentiating\n",
    "the first hidden unit vs the second hidden unit.\n",
    "In other words, we have permutation symmetry\n",
    "among the hidden units of each layer.\n",
    "\n",
    "This is more than just a theoretical nuisance.\n",
    "Imagine what would happen if we initialized\n",
    "all of the parameters of some layer \n",
    "as $\\mathbf{W}_l = c$ for some constant $c$.\n",
    "In this case, the gradients \n",
    "for all dimensions are identical:\n",
    "thus not only would each unit take the same value,\n",
    "but it would receive the same update.\n",
    "Stochastic gradient descent would \n",
    "never break the symmetry on its own\n",
    "and we might never be able to realize\n",
    "the network's expressive power.\n",
    "The hidden layer would behave\n",
    "as if it had only a single unit.\n",
    "Note that while SGD would not break this symmetry,\n",
    "dropout regularization would!\n",
    "\n",
    "\n",
    "## Parameter Initialization\n",
    "\n",
    "One way of addressing---or at least mitigating---the \n",
    "issues raised above is through careful initialization.\n",
    "Additional care during optimization \n",
    "and suitable regularization can further enhance stability.\n",
    "\n",
    "\n",
    "### Default Initialization\n",
    "\n",
    "In the previous sections,\n",
    "we used `manager.randomNormal()`\n",
    "to initialize the values of our weights.\n",
    "MXNet will use the default random initialization method,\n",
    "sampling each weight parameter from \n",
    "the uniform distribution $U[-0.07, 0.07]$\n",
    "and setting the bias parameters to $0$.\n",
    "Both choices tend to work well in practice \n",
    "for moderate problem sizes.\n",
    "\n",
    "\n",
    "### Xavier Initialization\n",
    "\n",
    "Let us look at the scale distribution of\n",
    "the activations of the hidden units $h_{i}$ for some layer. \n",
    "They are given by\n",
    "\n",
    "$$h_{i} = \\sum_{j=1}^{n_\\mathrm{in}} W_{ij} x_j.$$\n",
    "\n",
    "The weights $W_{ij}$ are all drawn \n",
    "independently from the same distribution.\n",
    "Furthermore, let us assume that this distribution\n",
    "has zero mean and variance $\\sigma^2$\n",
    "(this does not mean that the distribution has to be Gaussian,\n",
    "just that the mean and variance need to exist).\n",
    "For now, let us assume that the inputs to layer $x_j$\n",
    "also have zero mean and variance $\\gamma^2$\n",
    "and that they are independent of $\\mathbf{W}$.\n",
    "In this case, we can compute the mean and variance of $h_i$ as follows:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "    E[h_i] & = \\sum_{j=1}^{n_\\mathrm{in}} E[W_{ij} x_j] = 0, \\\\\n",
    "    E[h_i^2] & = \\sum_{j=1}^{n_\\mathrm{in}} E[W^2_{ij} x^2_j] \\\\\n",
    "        & = \\sum_{j=1}^{n_\\mathrm{in}} E[W^2_{ij}] E[x^2_j] \\\\\n",
    "        & = n_\\mathrm{in} \\sigma^2 \\gamma^2.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "One way to keep the variance fixed \n",
    "is to set $n_\\mathrm{in} \\sigma^2 = 1$.\n",
    "Now consider backpropagation.\n",
    "There we face a similar problem,\n",
    "albeit with gradients being propagated from the top layers.\n",
    "That is, instead of $\\mathbf{W} \\mathbf{x}$,\n",
    "we need to deal with $\\mathbf{W}^\\top \\mathbf{g}$,\n",
    "where $\\mathbf{g}$ is the incoming gradient from the layer above.\n",
    "Using the same reasoning as for forward propagation,\n",
    "we see that the gradients' variance can blow up\n",
    "unless $n_\\mathrm{out} \\sigma^2 = 1$.\n",
    "This leaves us in a dilemma:\n",
    "we cannot possibly satisfy both conditions simultaneously.\n",
    "Instead, we simply try to satisfy:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\frac{1}{2} (n_\\mathrm{in} + n_\\mathrm{out}) \\sigma^2 = 1 \\text{ or equivalently }\n",
    "\\sigma = \\sqrt{\\frac{2}{n_\\mathrm{in} + n_\\mathrm{out}}}.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "This is the reasoning underlying the now-standard\n",
    "and practically beneficial *Xavier* initialization,\n",
    "named for its creator :cite:`Glorot.Bengio.2010`.\n",
    "Typically, the Xavier initialization\n",
    "samples weights from a Gaussian distribution\n",
    "with zero mean and variance\n",
    "$\\sigma^2 = 2/(n_\\mathrm{in} + n_\\mathrm{out})$.\n",
    "We can also adapt Xavier's intuition to \n",
    "choose the variance when sampling weights\n",
    "from a uniform distribution.\n",
    "Note the distribution $U[-a, a]$ has variance $a^2/3$.\n",
    "Plugging $a^2/3$ into our condition on $\\sigma^2$ \n",
    "yields the suggestion to initialize according to\n",
    "$U\\left[-\\sqrt{6/(n_\\mathrm{in} + n_\\mathrm{out})}, \\sqrt{6/(n_\\mathrm{in} + n_\\mathrm{out})}\\right]$.\n",
    "\n",
    "### Beyond\n",
    "\n",
    "The reasoning above barely scratches the surface\n",
    "of modern approaches to parameter initialization.\n",
    "In fact, MXNet has an entire `mxnet.initializer` module\n",
    "implementing over a dozen different heuristics.\n",
    "Moreover, parameter initialization continues to be\n",
    "a hot area of fundamental research in deep learning.\n",
    "Among these are heuristics specialized for \n",
    "tied (shared) parameters, super-resolution, \n",
    "sequence models, and other situations.\n",
    "If the topic interests you we suggest \n",
    "a deep dive into this module's offerings,\n",
    "reading the papers that proposed and analyzed each heuristic,\n",
    "and then exploring the latest publications on the topic.\n",
    "Perhaps you will stumble across (or even invent!) \n",
    "a clever idea and contribute an implementation to MXNet.\n",
    "\n",
    "\n",
    "## Summary\n",
    "\n",
    "* Vanishing and exploding gradients are common issues in deep networks. Great care in parameter initialization is required to ensure that gradients and parameters remain well controlled.\n",
    "* Initialization heuristics are needed to ensure that the initial gradients are neither too large nor too small.\n",
    "* ReLU activation functions mitigate the vanishing gradient problem. This can accelerate convergence.\n",
    "* Random initialization is key to ensure that symmetry is broken before optimization.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Can you design other cases where a neural network might exhibit symmetry requiring breaking besides the permutation symmetry in a multilayer pereceptron's layers?\n",
    "1. Can we initialize all weight parameters in linear regression or in softmax regression to the same value?\n",
    "1. Look up analytic bounds on the eigenvalues of the product of two matrices. What does this tell you about ensuring that gradients are well conditioned?\n",
    "1. If we know that some terms diverge, can we fix this after the fact? Look at the paper on LARS for inspiration :cite:`You.Gitman.Ginsburg.2017`.\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "14.0.2+12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}