08 - Optimization for Training Deep Models.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Deep Learning Book (Simplified)\n",
    "## Part II - Modern Practical Deep Networks\n",
    "*This is a series of blog posts on the [Deep Learning book](http://deeplearningbook.org)\n",
    "where we are attempting to provide a summary of each chapter highlighting the concepts \n",
    "that we found to be most important so that other people can use it as a starting point\n",
    "for reading the chapters, while adding further explanations on few areas that we found difficult to grasp. Please refer [this](http://www.deeplearningbook.org/contents/notation.html) for more clarity on \n",
    "notation.*\n",
    "\n",
    "\n",
    "## Chapter 8: Optimization for Training Deep Models\n",
    "\n",
    "There are many types of optimization problems involved in deep learning, with the toughest one being that of training a neural network. The main theme of the chapter is to focus on one type of optimization - finding the parameters $\\theta$ that reduce a cost function $J(\\theta)$. <br>\n",
    "\n",
    "The chapter is organized as follows:\n",
    "\n",
    "**1. How Learning Differs from Pure Optimization** <br>\n",
    "**2. Challenges in Neural Network Optimization** <br>\n",
    "**3. Basic Algorithms** <br>\n",
    "**4. Parameter Initialization Strategies** <br>\n",
    "**5. Algorithms with Adaptive Learning Rates** <br>\n",
    "**6. Approximate Second-Order Methods** <br>\n",
    "**7. Optimization Strategies and Meta-Algorithms** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. How Learning differs from Pure Optimization\n",
    "\n",
    "- In Machine Learning (ML), we care about a certain performance measure *P* (for e.g. accuracy) defined w.r.t the test set and optimize *$J(\\theta)$* (for e.g. cross-entropy loss) with the hope that it improves *P* as well. In pure optimization, optimizing *$J(\\theta)$* is the final goal.\n",
    "\n",
    "- The expected generalization error (**risk**) is taken over the true data-generating distribution $p_{data}$. If we do have that, it becomes an optimization problem. When we don't have $p_{data}$ but a finite training set, we have a ML problem. The latter can be converted back to an optimization problem by replace $p_{data}$ with the empirical distribution, $\\tilde{p}_{data}$ obtained from the training set, thereby reducing the empirical risk. This is called empirical risk minimization (ERM) and although it might look relatively similar to optimizationthere are two main problems:\n",
    "    - ERM is prone to overfitting with the possibility of the dataset being learned by high capacity models.\n",
    "    - ERM might not be feasible. Most optimization algorithms now are based on Gradient Descent (GD) which may not work with various loss functions like 0-1 loss (as it is not differentiable)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics import log_loss, zero_one_loss\n",
    "import numpy as np\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_true = np.ones(201, dtype='float')\n",
    "y_pred = np.linspace(start=0, stop=1.0, num=201) # only the last prediction is correct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# storing the losses for each example\n",
    "zero_one_losses = []\n",
    "cross_entropy_losses = []\n",
    "\n",
    "for i in range(len(y_true)):\n",
    "    zero_one_loss_value = zero_one_loss([y_true[i]], [y_pred[i] >= 0.5])\n",
    "    cross_entropy_loss_value = log_loss([y_true[i]], [y_pred[i]], labels=[0, 1])\n",
    "    zero_one_losses.append(zero_one_loss_value)\n",
    "    cross_entropy_losses.append(cross_entropy_loss_value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# neat visualization hack\n",
    "y_max_allowed = 5\n",
    "for i, loss in enumerate(cross_entropy_losses):\n",
    "    if loss <= 5:\n",
    "        index_to_start = i\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAagAAAEYCAYAAAAJeGK1AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4xLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvAOZPmwAAIABJREFUeJzs3Xl4FFX28PHvyUIChJ2AQFgVBFkECSLDoIA6uAKuuAKiuI466rjNOIqO/t5xdNRREUWRRRwcd1FR1AFERZSAAWSRHYmgQBBkkSXhvH/cG9KGdNJZOt1Jn8/z1JPuqlvVp6qXk1t1615RVYwxxphoExfpAIwxxpjCWIIyxhgTlSxBGWOMiUqWoIwxxkQlS1DGGGOikiUoY4wxUckSVAwSkUtF5KNIx5FHRKqLyLsiskNEXot0PBVNRFqJiIpIQqRjKSkRGSUikyMdR6wRkVkiclWk4wg3S1BlICKXiEiGiOwSkU0i8oGI/D7ScRVHVV9W1T9EOo4A5wONgQaqekGkgzGmIBEZLiKfRzqOWGMJqpRE5FbgCeD/cD+uLYBngEGRjKs4UfpfektgharmhOsFonS/DSBOpf8tEpH4SMdQ5aiqTSWcgDrALuCCIsok4RLYRj89AST5ZX2BLOAOYDOwCRgMnAGsALYBfwnY1ijgdeC/wE5gAXBswPK7gNV+2VLgnIBlw4EvgMeBbOBBP+9zv1z8ss3AL8BioFPAfk4CtgDrgXuAuIDtfg48CvwMrAVOL+J4dABmAduBJcBAP/9+YD9wwB/TKwtZd7tftgvYDSjQyi87C8j0ZeYAXQLWWwfcCSwC9gEJweIoIu6RwCr/nkwFmgYsU+BaYKXf3mhAApaPAJb54zMdaBnkNVr5bSX45039a23zrz0yoOzxQIZ/r34CHvPzk4HJ/j3eDswDGgd5veI+L0HfV6A18Klf92PgaWByEcdvkH9/fvGveZqfPwt4CPfZ/BU4Ktz7Xdx7Euz99J+ZvUAu7jO43ZefAIwBpuE+l6dQ/HfmC3/MdgDLgZP9sguA+QVivRV4J8h+zAKu8o/j/Ousx32PJwF1ijs+Pp41/r1cC1wa6d/Ww/Yz0gFUxgk4DcjB/6AEKfMAMBdoBKTifjz/7pf19evfCyTifgS3AP8BagEd/Ze2tS8/CvcDfr4v/2f/gUr0yy/wX+44YIj/sjQJ+BDmADfifqCr89sENQCYD9QN+DLmrTsJeMfH1AqXPK8M2O4BH3s8cB0uEUshxyIR94PzF6Aa0N9/KY4O2L+gP3IFtvV/wGy/zW7+C9nTxzAMl5Ty/hFYh/txbO73u8g4Cnmt/sBW4DjcPxxPAbMDlivwnj92Lfx7mPcDPMi/Vgd/3O8B5gR5nVb8NkHNxtXGk4Gufrv9/bIvgcv94xTgBP/4GuBdoIY/Ft2B2kFer7jPS9D31b/+Y/54nOiPX6HvHS6p7ABO9a/VDGjvl80Cvsd91hP8exPu/S7yPSnm/RyO/84ElJ/g96+3379kiv/O5AC3+P0d4tev74/nNqBDwPa/Ac4Lsi+zyE9QI/x+tfHH5k3gpaKOD1ATl+zzvoNNgI6R/m09bD8jHUBlnIBLgR+LKbMaOCPg+QBgnX/cF5eA4v3zWv7L0TOg/HxgsH88CpgbsCwOV+vqE+S1M4FB/vFw4PsCyw992XA/wiuAE/D/6fn58biazTEB864BZgVsY1XAshp+H44oJJ4+wI8Ftj8FGBWwf8UmKP+FXgek+udj8Ek/oMx3wEn+8TpgRKhxFPJ644B/BjxPwf14t/LPFfh9wPJXgbv84w8IqA3692wPhdSiCEhQuGSaC9QKWP7/gAn+8WxcrbNhgW2MoEANsgSf54Kfl0LfV9yPdg5QM2D5f4K9d8BzwONBls0CHgh4Hvb9Lu49Keb9HE7hCWpSCb8zv/knDvia/MQ7BnjIP+6Iq+UlFXH88hLU/4DrA5Yd7T+nCcGODy5BbQfOA6qX9DNTUVOlP+8bIdlAw2KuazTFVbnzrPfzDm1DVXP941/9358Clv+K+0HMsyHvgaoexJ0ibAogIkNFJFNEtovIdqAT0LCwdQtS1Rm4Uw6jgc0iMlZEavv1EwvZh2YBz38M2M4e/zAw5jxNgQ0+7mDbKpKIdPNxnqOqW/zslsBtefvt9705vz3OgfseNA4RaeEbu+wSkV0B5Q/tv6ruwr33hR4D3I9d3v63BP4dENc2XA21uH1uCmxT1Z0FY/SPrwTaActFZJ6InOXnv4Q7ZfWKiGwUkX+KSGJhLxDC5yXY+9oU+FlVdxeILZjmuH/Ugin43pTbfotIn4D3c4kvG8p7Euz9DGUfQvnO/KA+QwQsz/u8TgQuEREBLgdeVdV9xbw+FP5bk4C7Nl7o8fHv4RDcKc1NIvK+iLQP4bUqlCWo0vkSd01jcBFlNuK+EHla+Hml1Tzvgb+gnAZsFJGWwPPAH3Gt4OoC3+K+eHkCvxCHUdUnVbU7cAzuR+B23KmtA4Xsww+liH0j0LzAhfCQtyUijYC3gRtU9ZuARRtw/3HWDZhqqOqUgDKB+x40DlX9XlVT8qaA8of2X0RqAg1CjHsDcE2B2Kqr6pxi1tsI1BeRWgVjBFDVlap6Me7U8cPA6yJSU1UPqOr9qnoM8DvctbmhBTce4uclmE1APX8cAmMLZgNwZBHLC7435bbfqvpZwPvZMSCe0rwnBWMNNj+U70wzn4ACl2/0+zgXVwPrA1yCSy6hKOy3Jgf4qajPhapOV9VTcaf3luM+F1HFElQpqOoO3PWj0SIyWERq+P/aTheRf/piU4B7RCRVRBr68mW5X6S7iJzra21/wiXIubiquuLOlyMiV+D+Iw6JiPQQkZ7+v+3duIvBB33t7lXgIRGp5X/Ybi3lPnyF+2/0Dn+c+gJnA6+EEF8CroHIZFV9tcDi54FrffwiIjVF5MwCP3JliWMKcIWIdBWRJNz1r69UdV1xcQPPAneLSEe/H3VEpNgm9Kq6AXdK5v+JSLKIdMHVHib77VwmIqm+Frjdr3ZQRPqJSGffkuwX3A/lwUJeotSfF1Vdj2uocL+IVPO3VJxdxCrjcMfvZBGJE5Fmwf5Lr4D9hlK+J95PQJqIVAtWIMTvTCPgJv/5uwB3PWxawPJJuDMFB1Q11GbtU4BbRKS1iKTgPqf/VdWcYMdHRBqLyCD/z8Y+XOOPYMctYixBlZKq/gv34bsH92XfgPuv9G1f5EHcl3kRrmXcAj+vtN7BVcl/xlX/z/X/HS0F/oWr1f0EdMa1FApVbdwP/c+4UwPZwCN+2Y24pLUG17LrP8CLJQ1cVffjfshOx/2X+Qzuv9zlIayehvuP8k+Bp+BEpIWqZuAu5j/t41+FO89fLnGo6ifA34A3cLWHI4GLQogZVX0L95/+KyLyC66Wcnoo6wIX465LbQTeAu7zsYBroLPEn4b8N3CRqv6Ku0b0Ou5HaBmupd1h/4GXw+flElyjlG3Afbgf1EKp6tfAFbhWojt8TC2DlSeM++3jKct7MgPX6vNHEdlaRLnivjNfAW1xn7+HgPNVNTtg+Uu4fxhK8o/gi3692bjGU3t9HBD8+MThfr824t7Lk3ANYqJKXsscE8VEZBRwlKpeFulYjDGlIyLDcQ0bgt7MLyLVcS1Tj1PVlRUVW7SyGpQxxkSP64B5lpycsCcoEYkXkW9E5L0gyy8UkaUiskRE/hMwf5iIrPTTsID5s0TkO3GtkDL9BXRjjKnURGQdcDNwW4RDiRphP8UnrkugdNzNc2cVWNYWd1Gxv6r+LCKNVHWziNTHXb9Jx13QnQ9092VmAX/21x+MMcZUUWGtQYlIGnAm8EKQIiOB0ar6M4CqbvbzBwAfq+o2v+xj3EVSY4wxMSLcHWg+getvLliz33YAIvIF7i7sUar6Ie7GtsAb4LL47c1u40UkF9e66kEtpBooIlcDVwPUrFmze/v27WFPNmz/Hhp3hPigrUWNMcaUo/nz529V1dSSrhe2BCXuTu/Nqjrf328S7PXb4rr+SQNmi0jnYjZ9qar+4O91eQPX5Pqwpq6qOhYYC5Cenq4ZGRmwfBq8cjGMHA/Nupdqv4wxxpSMiBTV40hQ4TzF1xsY6C/8vQL0l8MHNssCpvr7edbi+oRri7vzunlAuTTy7yjP+7sTd4/B8SFHlNLY/d21pehyxhhjIi5sCUpV71bVNFVthbu5cUYh9/G8jas94XtbaIe7wW068AcRqSci9YA/ANNFJMGXw/d8cBbuZrvQpPga5q6fii5njDEm4ip8EDcReQDIUNWp5CeipbiejG/Pu6taRP6OG7sEXK/H23y3HNN9cooHPqEk/UfV9C3Sd28uupwxxpiIq5AEpaqzcN3Do6r3BsxXXHcbtxayzosU6FbH98Bb+otHicmQVMdO8RkTBgcOHCArK4u9e/dGOhQTIcnJyaSlpZGYWGhH+iUWe8Ngp6TaKT5jwiArK4tatWrRqlUrRELpHN1UJapKdnY2WVlZtG7duly2GXtdHaU0ht1WgzKmvO3du5cGDRpYcopRIkKDBg3KtQYdewmqZirssmtQxoSDJafYVt7vf+wlqJRGlqCMMaYSiM0EtW8HHLALucYYE81iL0FZU3NjTJRat24dnTqFPCB2lRd7CSrFJyhram6MAXJzcyMdggkiBpuZWw3KmHC7/90lLN34S7lu85imtbnv7I5Blz/77LM8++yzAOzYsYNWrVpx9913c99997Fv3z6OPPJIxo8fT0pKCq1atWLIkCF8/PHH3HHHHbRv355rr72WPXv2cOSRR/Liiy9Sr169Ql8nMzOz0LJ9+/alZ8+ezJw5k+3btzNu3Dj69OlDbm4ud911F7NmzWLfvn3ccMMNXHPNNcXu7969e7nuuuvIyMggISGBxx57jH79+rFkyRKuuOIK9u/fz8GDB3njjTdo2rQpF154IVlZWeTm5vK3v/2NIUOGlO5AR5HYq0HlneKze6GMqVKuvfZaMjMzmTdvHmlpaYwYMYIHH3yQTz75hAULFpCens5jjz12qHyDBg1YsGABF110EUOHDuXhhx9m0aJFdO7cmfvvvz/o6xRVNicnh6+//ponnnji0Pxx48ZRp04d5s2bx7x583j++edZu3ZtsfszevRoRITFixczZcoUhg0bxt69e3n22We5+eabyczMJCMjg7S0ND788EOaNm3KwoUL+fbbbznttKoxOlHs1qDsFJ8xYVNUTSfcbr75Zvr370+9evVYunQpvXv3BmD//v306tXrULm8GsaOHTvYvn07J510EgDDhg3jggsuKHTbxZU999xzAejevTvr1q0D4KOPPmLRokW8/vrrh7axcuXKYm9m/fzzz7nxxhsBaN++PS1btmTFihX06tWLhx56iKysLM4991zatm1L586due2227jzzjs566yz6NOnT4mOWbSKvQSVkATJdewUnzFV0IQJE1i/fj1PP/0077//PqeeeipTpkwptGzNmjXL/fWTkpIAiI+PJycnB3A9LDz11FMMGDCgXF7jkksuoWfPnrz//vucccYZPPfcc/Tv358FCxYwbdo07rnnHk4++WTuvffe4jcW5WLvFB+403x2is+YKmX+/Pk8+uijTJ48mbi4OE444QS++OILVq1aBcDu3btZsWLFYevVqVOHevXq8dlnnwHw0ksvHaohlaVsngEDBjBmzBgOHDgAwIoVK9i9e3ex+9OnTx9efvnlQ+t8//33HH300axZs4Y2bdpw0003MWjQIBYtWsTGjRupUaMGl112GbfffjsLFiwodvuVQezVoMB1d2Sn+IypUp5++mm2bdtGv379AEhPT2fChAlcfPHF7Nu3D4AHH3yQdu3aHbbuxIkTDzV8aNOmDePHjw/6OiUpC3DVVVexbt06jjvuOFSV1NRU3n777WL35/rrr+e6666jc+fOJCQkMGHCBJKSknj11Vd56aWXSExM5IgjjuAvf/kL8+bN4/bbbycuLo7ExETGjBlT7PYrAylktPQq59CIunleGw6bFsJN30QsJmOqmmXLltGhQ4dIh2EirLDPgYjMV9X0km4rNk/x1UmDHT/AwYORjsQYY0wQsXmKr25LyN3nrkPVbhLpaIwxUeiGG27giy+++M28m2++mSuuuKLM2168eDGXX375b+YlJSXx1VdflXnbVUnYE5SIxAMZwA+qelaBZUnAJNwghNnAEFVdJyLVgOeAdOAgcLMf9BAR+RBo4mP/DLhBVUt2K3i9Vu7v9vWWoIwxhRo9enTYtt25c2cyMzPDtv2qoiJO8d0MLAuy7ErgZ1U9CngceNjPHwmgqp2BU4F/iUherBeq6rFAJyAVKPyGhaLUben+/ry+xKsaY4ypGGFNUCKSBpwJvBCkyCBgon/8OnCyuAFFjgFmAKjqZmA7rjaFqub1n5IAVANK3sqjbgv3d7slKGOMiVbhrkE9AdyBO01XmGbABgBVzQF2AA2AhcBAEUkQkda4U4DN81YSkenAZmAnLrEdRkSuFpEMEcnYsqVAk/LEZEg5wmpQxhgTxcKWoETkLGCzqs4vxeovAlm4a1dPAHOAQ9eZVHUA7jpUEtC/sA2o6lhVTVfV9NTU1MML1GtpNShjjIli4axB9cbVgtYBrwD9RWRygTI/4GtGIpIA1AGyVTVHVW9R1a6qOgioC/zmFnBV3Qu8gztNWHJ1W1oNyhgTEbNmzWLOnDkRe+2zzjqr+IJRIGwJSlXvVtU0VW0FXATMUNXLChSbCgzzj8/3ZVREaohITQARORXIUdWlIpIiIk38/ATc9a3lpQqwXkv4JQtyD5RqdWNM5ZLXN140KCpBRVOckVbh90GJyANAhqpOBcYBL4nIKmAbLpEBNAKmi8hBXC0r74aBmsBU3zw9DpgJPFuqQOq2BD0IO7KgftG9ChtjSuiDu+DHxeW7zSM6w+n/KLLIpEmTePTRRxERunTpQnx8PMnJyXzzzTf07t2be+65hxEjRrBmzRpq1KjB2LFj6dKlC59++ik333wzACLC7Nmz2bVrF0OGDOGXX34hJyeHMWPGBO0l/KOPPgo67tSwYcN49913OXDgAK+99hrJyck8++yzxMfHM3nyZJ566inGjRsXUpyjRo1i9erVrFq1iq1bt3LHHXcwcuRIhg4dyrnnnsvgwYMBuPTSS7nwwgsZNKjoE0zbtm0Ly/EoLxWSoPw9TLP843sD5u+lkGbiqroOOLqQ+T8BPcolqHq+qfn29ZagjKkClixZwoMPPsicOXNo2LAh27Zt49ZbbyUrK4s5c+YQHx/PjTfeSLdu3Xj77beZMWMGQ4cOJTMzk0cffZTRo0fTu3dvdu3aRXJyMmPHjmXAgAH89a9/JTc3lz179hT6ulu3bj007lTNmjV5+OGHeeyxxw71Jt6wYUMWLFjAM888w6OPPsoLL7zAtddeS0pKCn/+858BN2ZUKHECLFq0iLlz57J79266devGmWeeyZVXXsnjjz/O4MGD2bFjB3PmzGHixImFxhvovvvuK/fjUZ5isycJsHuhjAmnYmo64TBjxgwuuOACGjZsCED9+vUBuOCCC4iPjwfcGEtvvPEGAP379yc7O5tffvmF3r17c+utt3LppZdy7rnnkpaWRo8ePRgxYgQHDhxg8ODBdO3atdDXnTt3bpHjTgWOEfXmm28GjT+UOAEGDRpE9erVqV69Ov369ePrr79m8ODBXH/99WzZsoU33niD8847j4SE4n/ew3E8ylNs9sUHULsZSLy15DOmigtl3Ke77rqLF154gV9//ZXevXuzfPlyTjzxRGbPnk2zZs0YPnw4kyZNKnRdVeXUU08lMzOTzMxMli5dyrhx4w4tL2yMqNLGCe6UW2HPhw4dyuTJkxk/fjwjRowIaVvBlOV4lKfYTVDxCVC3OWxbE+lIjDHloH///rz22mtkZ2cD7vpKQYFjLM2aNYuGDRtSu3ZtVq9eTefOnbnzzjvp0aMHy5cvZ/369TRu3JiRI0dy1VVXBR1jKdRxpwLVqlWLnTt3Bl0eLE6Ad955h71795Kdnc2sWbPo0cNd9Rg+fDhPPPEEAMccc0yRrx/O41GeYvcUH0DDo2FL0R8kY0zl0LFjR/76179y0kknER8fT7du3Q4rM2rUKEaMGEGXLl2oUaPGoes0TzzxBDNnziQuLo6OHTty+umn88orr/DII4+QmJhISkpK0BpDampqyONO5Tn77LM5//zzeeedd3jqqadCjhOgS5cu9OvXj61bt/K3v/2Npk2bAtC4cWM6dOhwqKFEKMJxPMpTbI4Hlefje2HuGPjLJlejMsaUmo0HFX6jRo36TeOKQHv27KFz584sWLCAOnXqRCA6x8aDKi+p7SF3P/y8NtKRGGNMqX3yySd06NCBG2+8MaLJqbzFdrUhtb37u2U5NGwb2ViMMVGvZ8+eh07j5XnppZfo3Llzhbz+qFGjCp1/yimnsH79bxt8TZ8+nTvvvPM381q3bs1bb70VrvDKXWwnqIb+HPHm5dDh7MjGYkwVoKqHtTKrSirTgIIDBgxgwIABFfqa5X3JKLZP8SWluKE3tpSutyRjTL7k5GSys7PL/UfKVA6qSnZ2NsnJyeW2zdiuQYE7zWcJypgyS0tLIysri8OGtzExIzk5mbS0tHLbniWo1Paw5lPIzbGWfMaUQWJiIq1bW7dhpvzE9ik+8C359sHP6yIdiTHGmACWoBrlteRbFtk4jDHG/IYlqNT2IHHw47eRjsQYY0wAS1DVaroktfGbSEdijDEmQNgSlIgki8jXIrJQRJaIyP2FlBkuIltEJNNPVwUs+6dfb5mIPClODRF5X0SW+2Xl06d/024uQVnzWGOMiRrhrEHtA/qr6rFAV+A0ETmhkHL/VdWufnoBQER+B/QGugCdcIMUnuTLP6qq7YFuQG8ROb3MkTbtBrs3wy8by7wpY4wx5SNsCUqdXf5pop9CraIokAxUA5L8uj+p6h5Vnem3vx9YAJS90X1T3+uxneYzxpioEdZrUCISLyKZwGbgY1UtrJ+Q80RkkYi8LiLNAVT1S2AmsMlP01X1N83sRKQucDbwvyCvfbWIZIhIRrE3DjbuCHEJlqCMMSaKhDVBqWquqnbF1XKOF5FOBYq8C7RS1S7Ax8BEABE5Cujg12sG9BeRPnkriUgCMAV4UlULHXFQVceqarqqpqemphYdaGJ1aNTBEpQxxkSRCmnFp6rbcTWi0wrMz1bVvK6BXwC6+8fnAHNVdZc/TfgB0Ctg1bHASlV9otyCbNoNNmVaQwljjIkS4WzFl+pPwyEi1YFTgeUFyjQJeDoQyDuN9z1wkogkiEgiroHEMr/Og0Ad4E/lGnDTbrAnG7avL76sMcaYsAtnDaoJMFNEFgHzcNeg3hORB0RkoC9zk28uvhC4CRju578OrAYWAwuBhar6roikAX8FjgEWFGyaXiZpx7u/388tl80ZY4wpm9ge8j3QwYPwz1ZwzGAY+GSFxGWMMbHAhnwvq7g4aNEL1s+JdCTGGGOwBPVbLXpB9krYZePZGGNMpFmCCtSyt/v7vdWijDEm0ixBBWpyLCRUt9N8xhgTBSxBBUqoBs17wPovIh2JMcbEPEtQBbXq48aG2p0d6UiMMSamWYIq6Mj+gMKamZGOxBhjYpolqIKadoPq9WD1jEhHYowxMc0SVEFx8dCmr0tQMXATszHGRCtLUIU58mTYuQk2L410JMYYE7MsQRXmyP7u76pCh5oyxhhTASxBFaZOM2h0DKz8KNKRGGNMzLIEFczRp7sbdvdsi3QkxhgTkyxBBdP+TNBcWDE90pEYY0xMsgQVTNPjoHYzWP5epCMxxpiYFM4RdZNF5GsRWegHJby/kDJJIvJfEVklIl+JSCs//1I/GGHedFBEuvpl3UVksV/nSRGRMO2Aq0Wt+h/s3xOWlzDGGBNcOGtQ+4D+qnos0BU4TUROKFDmSuBnVT0KeBx4GEBVX1bVrqraFbgcWKuqmX6dMcBIoK2fTgvbHrQ/E3J+tZt2jTEmAsKWoNTZ5Z8m+qngna+DgIn+8evAyYXUiC4GXgEQkSZAbVWdq24o4EnA4HDED7jhN6rXhyVvhu0ljDHGFC6s16BEJF5EMoHNwMeq+lWBIs2ADQCqmgPsABoUKDMEmBJQPitgWZafFx7xidDxHFg+DfbtKr68McaYchPWBKWquf40XRpwvIh0Ksn6ItIT2KOq35b0tUXkahHJEJGMLVvKMEJu5wvcab7vppV+G8YYY0qsQlrxqep2YCaHXy/6AWgOICIJQB0gcJyLi8ivPeWVTwt4nubnFfaaY1U1XVXTU1NTSx98855QOw0Wv1b6bRhjjCmxcLbiSxWRuv5xdeBUYHmBYlOBYf7x+cAMf20JEYkDLsRffwJQ1U3ALyJygr9WNRR4J1z7AEBcHHQ+z7Xm2701rC9ljDEmXzhrUE2AmSKyCJiHuwb1nog8ICIDfZlxQAMRWQXcCtwVsP6JwAZVXVNgu9cDLwCrgNXAB2HcB6fLEHfT7qJXw/5SxhhjHNEYGFIiPT1dMzIyyraRsf0gZy9cN8fdI2WMMSYkIjJfVdNLup71JBGq4y53w2/8sCDSkRhjTEywBBWqTudDYg1YMLH4ssYYY8rMElSokmvDMYPh2zdg7y+RjsYYY6o8S1Al0eNK2L8LFr5SfFljjDFlYgmqJNLSXS/nX4+FgwcjHY0xxlRplqBKquc1kL0S1syMdCTGGFOlWYIqqY7nQM1U+Oq5SEdijDFVmiWokkpIgh4jYeV02Lws0tEYY0yVZQmqNI4f6Zqcf/FkpCMxxpgqyxJUadSoD8cNhcWvwo5C+6o1xhhTRpagSqvXDaAKc6wWZYwx4WAJqrTqtoCul0DGi7Ajq/jyxhhjSsQSVFmcdIerRc1+JNKRGGNMlWMJqizqtoD0K+CbybCt4KggxhhjysISVFn1uQ3iEmHWw5GOxBhjqhRLUGVV6wjX7HzRf2FzwQGDjTHGlFY4h3xvLiIzRWSpiCwRkZsLKdNXRHaISKaf7g1Ytk5EFvv5GQHzu4rI3Lz5InJ8uPYhZL+/BaqlwKz/i3QkxhhTZSSEcds5wG2qukBEagHzReRjVV1aoNxnqnpWkG30U9WtBeb9E7hfVT8QkTP8877lGnlJ1ajt9/0VAAAgAElEQVTvmp1/+g/4fi60OCGi4RhjTFUQthqUqm5S1QX+8U5gGdCsPDYN1PaP6wAby2GbZfe7G6FWU5h2OxzMjXQ0xhhT6VXINSgRaQV0A74qZHEvEVkoIh+ISMeA+Qp8JCLzReTqgPl/Ah4RkQ3Ao8DdQV7zan8KMGPLli3lsh9FSkqBAQ/Cj4tg/oTwv54xxlRxYU9QIpICvAH8SVULDkW7AGipqscCTwFvByz7vaoeB5wO3CAiJ/r51wG3qGpz4BZgXGGvq6pjVTVdVdNTU1PLcY+K0PFcaNUHZvwd9myrmNc0xpgqKqwJSkQSccnpZVV9s+ByVf1FVXf5x9OARBFp6J//4P9uBt4C8hpDDAPytvVawPzIE4HTH3ZDws/4e6SjMcaYSi2crfgEV7tZpqqPBSlzhC+Hb40XB2SLSE3fsAIRqQn8AfjWr7YROMk/7g+sDNc+lErjjq7ZecZ42JgZ6WiMMabSCqkVn4gcCWSp6j4R6Qt0ASap6vYiVusNXA4sFpG8X+q/AC0AVPVZ4HzgOhHJAX4FLlJVFZHGwFs+dyUA/1HVD/02RgL/FpEEYC8QeH0qOvS9G759A969Ca76H8QnRjoiY4ypdERViy/kEkw60AqYBrwDdFTVM8IaXTlJT0/XjIyM4guWpyVvw2vDoP/f4MQ/V+xrG2NMFBGR+aqaXtL1Qj3Fd1BVc4BzgKdU9XagSUlfLKZ0HAzHDIZZ/4CfCt76ZYwxpjihJqgDInIxroHCe36enbcqzpn/guQ68M71kJsT6WiMMaZSCTVBXQH0Ah5S1bUi0hp4KXxhVRE1G7oktfEbmPPvSEdjjDGVSkgJSlWXqupNqjpFROoBtVTVuu8OReCpvk0LIx2NMcZUGiElKBGZJSK1RaQ+7uba50Wk0KbjphBnPgY1GsJrV8C+nZGOxhhjKoVQT/HV8b1AnItrXt4TOCV8YVUxNRvA+ePg57Xw3q1uFF5jjDFFCjVBJYhIE+BC8htJmJJo+Tvo+xdY/CpkvhzpaIwxJuqFmqAeAKYDq1V1noi0Idp6cKgM+twKrU+E9/9sgxsaY0wxQm0k8ZqqdlHV6/zzNap6XnhDq4Li4uHc513P5/+9DPbuiHRExhgTtUJtJJEmIm+JyGY/vSEiaeEOrkqqdQRcMNFdj3rjKhs7yhhjggj1FN94YCrQ1E/v+nmmNFr1htP/CSs/sl7PjTEmiFATVKqqjlfVHD9NACpokKUqqseV0P0K+PxxWPx6pKMxxpioE2qCyhaRy0Qk3k+XAdnhDCwmnP5PaNEL3rkBNsyLdDTGGBNVQk1QI3BNzH8ENuGGyRgepphiR0I1uPAld11qyhDIXh3piIwxJmqE2opvvaoOVNVUVW2kqoMBa8VXHlJS4TI/QPDkc2HX5sjGY4wxUaIsI+reWtRCEWkuIjNFZKmILBGRmwspIyLypIisEpFFInJcgeW1RSRLRJ72z2uJSGbAtFVEnijDPkSHBkfCJa/Czp/gPxfCvl2RjsgYYyKuLAlKilmeA9ymqscAJwA3iMgxBcqcDrT109XAmALL/w7MznuiqjtVtWveBKwH3izDPkSPtHS4YILrUPbVyyFnX6QjMsaYiCpLgiqyQzlV3aSqC/zjncAyoFmBYoNwffupqs4F6voulRCR7kBj4KPCti8i7YBGwGdl2IfocvRpMPApWD0DXhsOuQciHZExxkRMkQlKRHaKyC+FTDtx90OFRERaAd2ArwosagZsCHieBTQTkTjgX0BRY6VfBPxXg4xZLyJXi0iGiGRs2bIl1FAjr9tlcMaj8N00eHOkDXRojIlZCUUtVNVaZX0BEUkB3gD+5HtED8X1wDRVzRIJeibxIuDyYAtVdSwwFiA9Pb1ydR9+/EjI2Qsf3QMJyTDoGYgrS2XXGGMqnyITVFmJSCIuOb2sqoVdK/oBaB7wPM3P6wX0EZHrgRSgmojsUtW7/HaPBRJUdX4444+o390IB36FmQ+54TkGjYb4sL5dxhgTVcL2iyeu6jMOWKaqwQY3nAr8UUReAXoCO1R1E3BpwHaGA+l5ycm7GJgSlsCjyUl3gAjMeNDVqM57AeITIx2VMcZUiHD+S94bdwpusYhk+nl/AVoAqOqzwDTgDGAVsAe4IsRtX+jXq/pOvB0SqsNHf3WNJi4YDwlJkY7KGGPCToK0MahS0tPTNSMjI9JhlM3Xz8O0P0ObfjDkJUgq8+VBY4ypECIyX1XTS7qeXXmvLI4f6RpLrJ0NE86CXZWoZaIxxpSCJajKpNulcPEU2PIdjDsVtq2JdETGGBM2lqAqm3YDYNi7sHc7jPsDZFXdhozGmNhmCaoyat4DRnwEiTVgwhk2npQxpkqyBFVZpbaDkTOhWXd440rXFP3gwUhHZYwx5cYSVGVWswFc/jZ0uxxmPwKvDYX9uyMdlTHGlAtLUJVdQjXXweyA/wfL34cXB8D2DcWvZ4wxUc4SVFUgAr2ud2NK/bwenjsRVn4S6aiMMaZMLEFVJW1PddelajWBl8/316VyIx2VMcaUiiWoqqbhUXDVJ+6eqdmPwKRBbqReY4ypZCxBVUXVarjezwc9A1kZ8FwfWPd5pKMyxpgSsQRVlXW7FEb+z/XbN+Es+GQU5OyPdFTGGBMSS1BVXeOOcPWncNzl8Pnj8MLJrqskY4yJcpagYkFSimuKPuRl2JHlWvl9NdYNhGiMMVHKElQs6XAWXP8ltPo9fHA7TD7PJSxjjIlCYUtQIvKiiGwWkW+DLO8rIjtEJNNP9/r5ySLytYgsFJElInJ/wDoTRGRtwDpdwxV/lVXrCLj0dTjjUVg/B0afABkvWjdJxpioE84a1ATgtGLKfKaqXf30gJ+3D+ivqscCXYHTROSEgHVuD1gn87AtmuKJuPGlrv8SmnWD926BSQMhe3WkIzPGmEPClqBUdTawrRTrqaru8k8T/WQXS8KhfmsYOhXOfhI2LYQxvWHOU5CbE+nIjDEm4tegevlTeR+ISMe8mSISLyKZwGbgY1X9KmCdh0RkkYg8LiJJFR5xVSMC3YfBDV9Bm77w0T3wfD/YMC/SkRljYlwkE9QCoKU/lfcU8HbeAlXNVdWuQBpwvIh08ovuBtoDPYD6wJ3BNi4iV4tIhohkbNliw6MXq3ZTN1rvBRNg9xYYdwpMvQn2lLgSbIwx5SJiCUpVf8k7laeq04BEEWlYoMx2YCb+WpaqbvKnAPcB44Hji9j+WFVNV9X01NTUsO1HlSICHc+BP86DXn+EbybDU91hwSRrRGGMqXARS1AicoSIiH98vI8lW0RSRaSun18dOBVY7p838X8FGAwU2kLQlFFSLRjwEFz7GaQeDVNvdDWq7+dGOjJjTAxJCNeGRWQK0BdoKCJZwH24Bg+o6rPA+cB1IpID/ApcpKrqk9BEEYnHJa1XVfU9v9mXRSQVECATuDZc8RtcLxRXfAALX3HdJL04wNWwThkF9VpFNjZjTJUnGgO9CaSnp2tGRkakw6jc9u+GL56EL/4NmgsnXAd9boPkOpGOzBgT5URkvqqml3S9SLfiM5VFtZrQ7264aQF0Ot8lqie7wbwXrFm6MSYsLEGZkqndFM4ZA1fPgtT28P5tMKYXLHnLGlIYY8qVJShTOk27wfD3XQe0CLw2HMaeCCumWye0xphyYQnKlJ5Ifge05zwH+3bCfy50jSnWzo50dMaYSs4SlCm7uHg49iL4Ywac9Ths3wATz4aJA61HCmNMqVmCMuUnPhHSR8BN38CA/4Oflrj7pyYOhLWf2ak/Y0yJWIIy5S8xGXrdADcvhD88CFuWw8Sz3Km/FR9ZojLGhMQSlAmfpBT43Y1w8yI3/tQvG+E/F7gRfZe+Y63+jDFFsgRlwi8x2Y0/deMCGDTa3fT76lB4pifMnwgH9kY6QmNMFLIEZSpOQjXodpnrjPa8cZCQDO/eBE90glkPw+7sSEdojIkilqBMxYuLh87nwzWz3YCJTbvBrP+Dx4+Bd/8EW1dGOkJjTBQIW2exxhRLBNqc5KbNy2HuaMh8GeZPgHanudOCbfpBnP0fZUwsss5iTXTZtRm+fh4yXoQ9W6H+kS5RHXsxVK8b6eiMMaVQ2s5iLUGZ6JSzD5a8DfOeh6x5kFgDulwIPUbCEZ2KX98YEzVKm6DsFJ+JTglJcOwQN238Br5+wY1LNX8CtPgdHH8VtD/bNbwwxlRJVoMylceebW4Y+nkvwPb1UDMVul4C3YZCw6MiHZ0xJoioGw9KRF4Ukc0iUuiw7OI8KSKrRGSRiBzn53cVkS9FZImfPyRgnXEistDPf11EUsIVv4lCNepD75tcV0qXvAppx8Ocp+Hp7vDi6ZA5BfbviXSUxphyErYalIicCOwCJqnqYRcNROQM4EbgDKAn8G9V7Ski7QBV1ZUi0hSYD3RQ1e0iUltVf/HrPwZsVtV/FBeL1aCqsJ0/wsIpsOAl2LYakmq7JuzdLnfN10UiHaExMS/qrkGp6mwRaVVEkUG45KXAXBGpKyJNVHVFwDY2ishmIBXYHpCcBKgOVP3zk6ZotY6A398Cvf8E6+fANy+5mlTGi9C4szsF2Pl8SGkU6UiNMSUUyUYSzYANAc+z/LxNeTNE5HigGrA6YN54XK1rKXBbsI2LyNXA1QB1m7bhL28tLs/YTVSqDdxAUvthHPvzJ6Rve5e06XeTO/0eVtXqwTf1BrCsTh8OxCVHOtCQ1EpK4JZT25GcGB/pUIyJiKhtxSciTYCXgGGqeqhXUVW9QkTigaeAIcD4wtZX1bHAWICazdrpR0t+Cn/QJmq8Sy+gF63jN3D6wdmcsXM2F+2cyy6qM0NO4AM5kfnSkYMSnT/+B3IPsuPXA/Rv34iebRpEOhxjIiKSCeoHoHnA8zQ/DxGpDbwP/FVV5xZcUVVzReQV4A6CJKhAHZrUJuOeU8olaFMZXeF6Tl//BSmLXmHg0qkM3DcTajWFLhdAp/PhiM5Rdb1q/vqfOW/MHH49kBvpUIyJmEj2ITMVGOpb850A7FDVTSJSDXgLd33q9bzCvtxReY+BgcDySARuKqG4OGjdx/Wm/ucVcP54aNIFvhwNz/WBp9NhxoNukMUouPUiOdF9NfcesCFJTOwKWw1KRKYAfYGGIpIF3AckAqjqs8A03LWkVcAe4Aq/6oXAiUADERnu5w0HFgETfe1KgIXAdeGK31RhidWh07lu2p0Ny6bCkrfgs3/B7Eeg4dHQ8Ry3PPXoiIRY3V932ms1KBPDwtmK7+JilitwQyHzJwOTg6zWuxxCMyZfzQaQfoWbdm12yerbt+DTh+HTf0Cjji5ZdTynQm8GTrYEZUz0NpIwpsKlNIIeV7lp54+wdCoseRNmPuimxp2hw1nQ/kxo3Cms16zyalB2DcrEMktQxhSm1hHQ82o37fjBDVG/9B2Y9Q+Y9f+gbktof5ZLWM17ujGuylF+DcquQZnYZQnKmOLUaQa9rnfTrs3w3Qew/D3X0/rc0VCjIRx9muu8tk1fN8R9GSUluEYSVoMyscwSlDElkdIIug9z076dsOoTWPaeOx34zWRIrAltT4Gjz4CjToGaDUv1MnFxQlJCHPssQZkYZgnKmNJKqpXfgCJnP6z7zNWslk9zpwMRSEuHtgOg3YAS32tVvVq8NZIwMc0SlDHlIaEaHHWym874F/y4EFZ8BCs+zG9kUasptD3VJavWJ0FS0Z3xJyfE2yk+E9MsQRlT3uLiXE/qTbtB3zvddauVH8PK6e5+qwUTIb4atPq9q10ddQo0OPKw2pWrQVkjCRO7LEEZE24pjaDbpW7K2Q/ffwkrP4IV0+HDO12ZOi3gyH5wZH9ocxJUr0dSQpzVoExMswRlTEVKqOYSUJuTYMBDsG0trJ7hprzalcRBs+5csb8t3+3qAbldId6+qib22JDvxkSL3Bz4YT6s/h+snsHBrPnEcdANwtj6RFe7OrI/1G8d6UiNKZHSDlhoCcqYKPXHcTNo9vM87m73g6th7fDDp9Vt6Tq+bX0StOoDtZtENlBjihF1I+oaY8rmYHId/hd3AncPPMn1sJ692iWqtZ+6e6++8V1WNmjrE9aJLmGV8t4rY6KNJShjolRyYsB9UCKus9qGR7nulw7mwk/fwtrZsPYzWPSaG+YeXAe3rU90Satlb6heN3I7YUwZWIIyJkr9JkEVFBcPTY510+9udNevNmW62tXaz2D+BPhqjGtwcURnl6ha9HJTSmqF7ocxpWUJypgoVT2xBPdBxSe4XivS0qHPbZCzzzW4WDsb1n0OGeNh7jOubIO20LJXftKq2yKqRhM2Jk9YE5SInAb8G4gHXlDVfxRYPhx4BD/UO/C0qr7gl30InAB8rqpnBazzMpAOHAC+Bq5R1QPh3A9jIiE5sQz3QSUkQcvfuQnc/VebMmH9HHcf1tJ3YMEkt6x2M5eo8pJWw6PdzcbGRFg4R9SNB0YDpwJZwDwRmaqqSwsU/a+q/rGQTTwC1ACuKTD/ZeAy//g/wFXAmHIL3JgoUT0xntyDyoHcgyTGlzFhJFSD5se7iT/BwYOwealLVuvnwPov4NvX/QvXyz8d2Px4aNK1XHpoN6akwlmDOh5YpaprAETkFWAQUDBBFUpV/ycifQuZPy3vsYh8DaSVS7TGRJnAUXXLnKAKiouDIzq56fiRrpXgz2th/Zfw/Rz39zv/VYtLhCZdIO14aN7DjX9Vx752JvzCmaCaARsCnmcBPQspd56InAisAG5R1Q2FlDmMiCQClwM3B1l+NXA1QIsWLUoQtjHRITlgVN1ayYnhfTERqN/GTd0udfN2bYasebDha/c3r+EFuI5vm/fwSet411gjISm8MZqYE+lGEu8CU1R1n4hcA0wE+oe47jPAbFX9rLCFqjoWGAvuRt3yCNaYipSXoPZFqsPYlEZuePv2Z7rnuQdc0/YNX/uk9bUfVgTX+W2TY13tKq0HNDsO6jS3xhemTMKZoH4Amgc8TyO/MQQAqpod8PQF4J+hbFhE7gNSOfz6lDFVRnJilI2qG5+Y30t7T//V2/mTS1R5tayvn4cvn3bLaqZC0+NcsmrW3T2u2SBy8ZtKJ5wJah7QVkRa4xLTRcAlgQVEpImqbvJPBwLLituoiFwFDABOVlUbi8BUWdUDrkFFrVqNocPZbgLXWvCnxfDDAtj4jWvqvvIjwJ/EqNvSJaymPmk1ObbYcbFM7ApbglLVHBH5IzAd18z8RVVdIiIPABmqOhW4SUQGAjnANmB43voi8hnQHkgRkSzgSlWdDjwLrAe+FHf64E1VfSBc+2FMpBy6BrU/ihNUQQnVXOJp1j1/3r6dsDETNi5wiStrvuu5HdyNxA2P9ut0c4mrcSe3HRPzwnoNyre4m1Zg3r0Bj+8G7g6ybp8g8yN93cyYCnGoFV9OJT9RkFTL9xUY8JXetSU/Yf0wH1Z8AJm+b8H4atDoGNdysMmxrpl7446QWD0y8ZuIsR97Y6LUoWtQlakGFaqUVGg3wE3gmrlvX59/avDHRbDs3fybiSUeUo+GI7rkd/F0RGdIrh25fTBhZwnKmCiVdw1qX04VTFAFiUC9Vm7qdK6bp+qGGNm0EDYtcn/XzIJFr+SvV79NfsJqciwccaw1xKhCLEEZE6Uq5TWo8iTi+gms2yK/EQa4loM/LnJdN21a6E4R5l3TAqidll/DOqKTOz1Yt5V131QJWYIyJkpVilZ8kVCrMdQ6Fdqemj9vzzb4cbFLWD8uco0yvpvGodaD1VLcda3GHX3S6uSe2ynCqGYJypgold+TRCVvJFERatSHNie5Kc/+PbBlGfy0BH781v1d8ibMH59fpm5Ll6wCE1e91lbbihKWoIyJUkkJ7kfSalClVK3G4U3eVeGXH3zSWuz+/vSta0WYd1tlYo2A2lZnSG3vntu1rQpnCcqYKBUXJyQlxLE3FhpJVBQR19FtnbT8FoQAB36FLcvza1o/feuHJJmYX6ZmKjTqAKkdoJFPWqntbcTiMLIEZUwUq14tnr2x2kiiIiVWz+/GKY8q7NwEm5e5aYv/m/ky7N+VX65Wk0IS19Hu/i9TJpagjIliyQklGFXXlC8RqN3UTUednD//4EH4JSsgcS13Y2tlvAg5v+aXq9PCJay8U4SN2rteM6rVqPh9qaQsQRkTxapXi4+ezmKNExeX3/w98DThwVz4eZ1PWAHJa80syN2fX65OC2jY1tWyGraFhu1c4qrZ0Hp/L8ASlDFRLCkhzhpJVBZx8dDgSDflDVECkJsD29a4U4RbVsDW72DrCpj/JRzYk18uuW5A0jraJa7Udq6lYVx8xe9PFLAEZUwUsxpUFRCf4BJNarvfzj940LUo3PodbF0JW/zfFdPhm8kB6ye5pNewnU9aPok1aFvlTxdagjImiiUnxEduwEITXnFxULe5m4465bfL9mxzyWrrivzpx0WwbGp+c3jIP13Y4Kj82luDo9xgkVWg1mUJypgoVr1aPFt27ot0GKai1agPLXq6KdCBve50YWCtK3ulGzBy/878cvHVXD+F9QOSVt6U0qjSXOuyBGVMFEtOtGtQJkBiMjQ+xk2BVGHXZshe5aZtqyF7tXu86uPfNtKolnJ40spLZFF2T5clKGOiWHKiXYMyIRDxfRQ2hla9f7vsYK7rFT47IGllr4KsDNfJbuApwxoN808X1m/tun2q38Y9rl6vYveJMCcoETkN+DduRN0XVPUfBZYnAZOA7kA2MERV1/lldwNXArnATX403WK3aUxVkpxo90GZMoqLzx/KJPB+LoCcfa5pfF7Syktiq/4Hu378bdnq9VyyCkxaec/DdNowbAlKROKB0cCpQBYwT0SmqurSgGJXAj+r6lEichHwMDBERI4BLgI6Ak2BT0QkrwlMcds0psqonhhvp/hM+CQkuVaBqUcfvmz/Hpe8tq1x089r3d+sea7T3cCaV2JNn7BaH57AajcrfXilXrN4xwOrVHUNgIi8AgwCApPJIGCUf/w68LSIiJ//iqruA9aKyCq/PULYpjFVRo1q8ezal0PHez+MdCgmZiUA7fzkJJJDE7bQgh9pwU+02P8jzX/8ieY/zqc5H1BNcg6V3a+lTzPhTFDNgA0Bz7OAnsHKqGqOiOwAGvj5cwusm5eGi9smACJyNXC1f7pPRL4txT5UdQ2BrZEOIkrZsQnOjk3hYuq4LCxZ8UKqaMWrso0kVHUsMBZARDJUNT3CIUUdOy7B2bEJzo5N4ey4BCciGaVZL5yjcv0ANA94nubnFVpGRBKAOrjGEsHWDWWbxhhjqoBwJqh5QFsRaS0i1XCNHqYWKDMVGOYfnw/MUFX18y8SkSQRaQ20Bb4OcZvGGGOqgLCd4vPXlP4ITMc1CX9RVZeIyANAhqpOBcYBL/lGENtwCQdf7lVc44cc4AZVzQUobJshhDO2nHevqrDjEpwdm+Ds2BTOjktwpTo24iosxhhjTHQJ5yk+Y4wxptQsQRljjIlKVSpBichpIvKdiKwSkbsKWZ4kIv/1y78SkVYVH2XFC+G43CoiS0VkkYj8T0RaRiLOSCju2ASUO09EVERiohlxKMdFRC70n5slIvKfio4xUkL4PrUQkZki8o3/Tp0RiTgrmoi8KCKbg91zKs6T/rgtEpHjit2oqlaJCddoYjXQBqiGu4/smAJlrgee9Y8vAv4b6bij5Lj0A2r4x9fFwnEJ9dj4crWA2bibx9MjHXc0HBdcy9pvgHr+eaNIxx1Fx2YscJ1/fAywLtJxV9CxORE4Dvg2yPIzgA8AAU4Avipum1WpBnWoayVV3Q/kdYMUaBAw0T9+HTjZd61UlRV7XFR1pqrmjT09F3d/WSwI5TMD8HdcP5F7KzK4CArluIwERqvqzwCqurmCY4yUUI6NArX94zrAxgqML2JUdTauNXYwg4BJ6swF6opIk6K2WZUSVGFdKxXspfA3XSsBeV0rVWWhHJdAV+L+y4kFxR4bfxqiuaq+X5GBRVgon5l2QDsR+UJE5vpRBmJBKMdmFHCZiGQB04AbKya0qFfS36Kq29WRKTkRuQxIB06KdCzRQETigMeA4REOJRol4E7z9cXVuGeLSGdV3R7RqKLDxcAEVf2XiPTC3evZSVVt3JQSqko1qLJ0rVSVhdQ9lIicAvwVGKiuF/lYUNyxqQV0AmaJyDrcefOpMdBQIpTPTBYwVVUPqOpaYAUuYVV1oRybK4FXAVT1SyAZ15FsrCtxV3VVKUGVpWulqqzY4yIi3YDncMkpVq4lQDHHRlV3qGpDVW2lqq1w1+cGqmqpOr6sREL5Lr2Nqz0hIg1xp/zWVGSQERLKsfkeOBlARDrgEtSWCo0yOk0FhvrWfCcAO1R1U1ErVJlTfFqGrpWqshCPyyNACvCabzPyvaoOjFjQFSTEYxNzQjwu04E/iMhS3KjXt6tqVT8bEeqxuQ14XkRuwTWYGB4D/wgjIlNw/7Q09Nff7gMSAVT1Wdz1uDOAVcAe4IpitxkDx80YY0wlVJVO8RljjKlCLEEZY4yJSpagjDHGRCVLUMYYY6KSJShjjDFRyRKUMYCI5IpIpoh8KyKviUiNMmyrr4i85x8PLKaX9Loicn3A86Yi8nppX7ssRGRWDNyEbCoRS1DGOL+qaldV7QTsB64NXOhvLizx90VVp6rqP4ooUhfXy35e+Y2qen5JX8eYqsgSlDGH+ww4SkRa+XF/JgHfAs1F5A8i8qWILPA1rRQ4NEbQchFZAJybtyERGS4iT/vHjUXkLRFZ6KffAf8AjvS1t0f8a37ryyeLyHgRWezHFuoXsM03ReRDEVkpIv8suAM+ntcCngfW6saISIa4cZzuL+wAiMiugMfni8gE/zhVRN4QkXl+6l2mI21MESxBGRPA99F4OrDYz2oLPKOqHYHdwD3AKap6HJAB3CoiycDzwNlAd+CIIJt/EvhUVY/FjZuzBLgLWO1rb7cXKH8DoKra+f+3dz8vNodRHMffn7GhqbG08iuaxsg0i5koSpbRAzIAAAIlSURBVGQnCym3ycKKKLGxUP4ECymxsVEaLGmUMAtpsCCM0shCYycLTZPY3I7Fc4av6d7cyeAbn9fuPt/n3O/zvXU7PU/fzqEUIL2c9wIYBBrAJqAhaeW82HvAZknd+blBaQ0BcDoihoABYLukgU5+m3QOOBsRw8A+4NICYs0WxAnKrFgm6Tkl6byjlMUCmM7eNVCKxfYDEzn3ILAa6APeRsSbLGlzpc09dgIXASKiGREzP1nTtrnviogpYJpS8w5gPGsFfgFe5Tq+yXYyt4E9mXR3Azfy8v7c6T0DNuYzdWoXcD6f/ybQM7eLNFts/0wtPrNf9DkiBqsDWZfwU3UIuBsRI/Pm/RD3h1Qrzjdp/V++Bhyj1J18EhGzktYCJ4HhiPiYR3dLW8RWa6BVr3cBWzIxmv1W3kGZde4xsFXSegBJ3ZJ6gSlgjaR1OW+kTfw4cDRjl0haDsxS2nq08gA4kPN7gVXA6wWs9z7lKPEQ34/3eihJd0bSCspxZivvJW3IF0P2VsbvUGnA95eSs/0nnKDMOhQRHyjNC69KmgQeAX25mzgM3Mqjs3YtS04AOyS9BJ4C/VkBfCJfbz8zb/4FoCvnX6dUxe64V1dENIExShIay7EXlKO9KWAUmGgTfipjHgLVlgjHgSFJk1nJ/EirYLPF4GrmZmZWS95BmZlZLTlBmZlZLTlBmZlZLTlBmZlZLTlBmZlZLTlBmZlZLTlBmZlZLX0FSqXM0fNRLUoAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7efffd41dc90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(y_pred, zero_one_losses, label='zero_one_loss')\n",
    "plt.plot(y_pred[index_to_start:], cross_entropy_losses[index_to_start:], label='cross_entropy_loss')\n",
    "plt.legend(loc='best')\n",
    "plt.xlabel('Prediction value')\n",
    "plt.ylabel('Loss')\n",
    "plt.title('Comparison of zero-one loss and cross-entropy loss')\n",
    "plt.xticks(np.linspace(0, 1.4, 8))\n",
    "plt.yticks(np.linspace(0, np.max(cross_entropy_losses[index_to_start:]), 10))\n",
    "plt.tight_layout()\n",
    "plt.margins(0)\n",
    "plt.savefig('images/loss_comparison.png')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    \n",
    "- It is for the reasons mentioned above that a **surrogate loss function** (SLF) is used instead that acts as a proxy. E.g. the negative log-likelihood of the true class is used as a surrogate for 0-1 loss. Using a SLF might even turn out to be beneficial as you can keep continuing to obtain a better test error by pushing the classes even further apart to get a more reliable classifier.\n",
    "\n",
    "- Another common difference is that training might be halted following some convergence criterion based on Early Stopping to prevent overfitting, when the derivative of the surrogate loss function might still be large. This is different from pure optimization which is halted only when the derivative becomes very small. If you're not familiar with Early Stopping, I'd recommend you to look at our [previous post](https://medium.com/inveterate-learner/deep-learning-book-chapter-7-regularization-for-deep-learning-937ff261875c) where we talk about Early Stopping and other regularization techniques.\n",
    "\n",
    "- In ML optimization algorithms that objective function decomposes as a sum over the examples and we can perform updates by randomly sampling a batch of examples and taking the average over those examples. The Standard Error of the mean estimated from *n* examples is given by $\\frac {\\sigma} {\\sqrt{n}}$ indicating that as we include more examples for making an update, the returns of additonal examples in improving the error is less than linear. Thus, if we use 100 and 10000 example s to make an update, the latter takes 100 times more compute, but reducing the error only by a factor of 10. Thus, it's better to compute rapid approximate updates rather than a slow exact update.\n",
    "\n",
    "- There are 3 types of sampling based algorithms - **batch gradient descent (BGD)** where the entire training set is used to make a single update, **stochastic gradient descent (SGD)** where a single example is used to make an update and **mini-batch gradient descent (MBGD)** where a batch (not to be confused with BGD) of examples is randomly sampled from the entire training set and is used to make an update. *MBGD is nowadays commonly refered to as SGD*. It is a common practise to use batch sizes as powers of 2 to offer better runtime with certain hardware. Small batches tend to have a regularizing effect because of the noise they inject as each update is made by seeing only a very small portion of the entire training set, a.k.a., a batch of samples.\n",
    "\n",
    "- The minibatches should be selected randomly. It is sufficient to shuffle the dataset once and iterate over it multiple times. In the first epoch, the network sees each example for the first time and hence, the estimate of gradient is an *unbiased* estimate of the gradient of the true generalization error. However, from the second epoch onwards, the estimate becomes biased as it is resampling from data that it has already seen.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Challenges in Neural Network Optimization\n",
    "\n",
    "The optimization problem for training neural networks is generally nonconvex. Some of the challenges faced are mentioned below:\n",
    "\n",
    "- **Ill-conditioning of the Hessian Matrix**: Can cause the SGD to get stuck in a sense that even very small steps increase the cost function. Moving by a factor of $-\\epsilon \\mathbf{g}$  would add the term given below to the cost function. Ill-conditioning is to happen when the first term exceeds the second term. In many cases, $\\mathbf{g}^TH\\mathbf{g}$ does increase significantly leading to slower learning due to reduced learning rate. Thus, while the gradient norm might be increasing, it can still lead to successful training.\n",
    "\n",
    "$$ \\frac{1}{2}\\epsilon^2\\mathbf{g}^TH\\mathbf{g} - \\epsilon\\mathbf{g}^T\\mathbf{g} $$\n",
    "\n",
    "- **Local minima**: Nearly any DL model is guaranteed to have an extremely large number of local minima (LM) arising due to the model identifiability problem.\n",
    "\n",
    "![minima](images/local_minima.gif)\n",
    "\n",
    "A model is said to be identifiable if a sufficiently large training set can rule out all but one setting of the model parameters. In case of neural networks, we can obtain equivalent models by swapping the position of the neurons. Thus, they are not identifiable.\n",
    "\n",
    "![model_identifiability](images/model_identifiability.png)\n",
    "\n",
    "Swapping the two hidden nodes leads to equivalent models. Thus, even after having a sufficiently large training set, there is not a unique setting of parameters. This is the model identifiability problem that neural networks suffer from.\n",
    "\n",
    "However, all the local minima caused due to this have the same value, thus not being a problem. However, if local minima with high cost are common, it becomes a serious problem. Many points other than local minima can lead to low gradients. Nowadays, it's common to aim for a low but not minimal cost value.\n",
    "\n",
    "\n",
    "- **Plateaus, Saddle Points and Other Flat Regions**: Saddle point (SP) is another type of point with zero gradient where some points around it have higher value and the others have lower. Intuitively, this means that a saddle point acts as both a local minima for some neighbors and a local maxima for the others. Thus, Hessian at SP has both +ve and -ve eigenvalues. \n",
    "\n",
    "![saddle](images/saddle_point.png)\n",
    "\n",
    "For many classes of random functions, saddle points become more common at high dimensions  with the ratio of number of SPs to LMs growing exponentially with *n* for an n-dimensional space. Many random functions have an amazing property that near points with lost cost, the Hessian tends to take up mostly positive eigenvalues. SGD empirically tends to rapidly avoid encountering a high-cost saddle point. There also might be wide, flat regions of constant value, thereby having a zero gradient. These can be problematic if the cost is high in these regions.\n",
    "\n",
    "![plateau](images/plateau.png)\n",
    "\n",
    "- **Cliffs and Exploding Gradients**: NNs might sometimes have extremely steep regions resembling cliffs due to the repeated multiplication of weights. At the edge of such a cliff, an update step might throw the parameters extremely far. It can be taken care of by using **gradient clipping (GC)**. The gradient indicates only the direction in which to make the update. If the GD update proposes making a very large step, GC intervenes to reduce the step size.\n",
    "![gradient clipping](images/gradient_clipping.png)\n",
    "\n",
    "- **Long-Term Dependencies**: This problem is encountered when the NN becomes sufficiently deep. For example, if the same weight matrix $\\mathbf{W}$ is used in each layer, after *t* steps, we'd get $\\mathbf{W}^t$. Using the eigendecomposition of $\\mathbf{W}$:\n",
    "\n",
    "$$ \\mathbf{W} = \\mathbf{V} diag(\\lambda) \\mathbf{V}^T $$\n",
    "$$ \\mathbf{W}^t = \\mathbf{V} diag(\\lambda)^t \\mathbf{V}^T $$\n",
    "\n",
    "Thus, any eigenvalues not near an absolute value of 1 would either explode or vanish leading to the [**vanishing and exploding gradient problem**](https://machinelearningmastery.com/exploding-gradients-in-neural-networks/). The use of the same weight matrix is especially the case in RNNs where this is a serious problem.\n",
    "\n",
    "![vanish explode gradient](images/exploding_vanishing_gradient.jpg)\n",
    "\n",
    "- **Inexact Gradients**: Most optimization algorithms use a noisy/biased estimate of the gradient in cases where the estimate is based on sampling, while in cases where the true gradient is intractable for e.g. in the case of training a [Restricted Boltzmann Machine (RBM)](https://deeplearning4j.org/restrictedboltzmannmachine), an approximation of the gradient is used. For RBM, the [contrastive divergence algorithm](https://deeplearning4j.org/glossary.html#contrastivedivergence) gives a technique for approximating the gradient of its intractable log-likelihood\n",
    "\n",
    "\n",
    "- Neural Networks might not end up at any critical point at all and such critical points might not even necessarily exist. A lot of the problems might be avoided if there exists a space connected to reasonably directly to the solution by a path that local descent can follow and if we are able to initialize learning within that well-behaved space. Thus, choosing good initial points should be studied."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Basic Algorithms\n",
    "\n",
    "- **Stochastic Gradient Descent**: This has already been described before but there are certain things that should be kept in mind regarding SGD. The learning rate $\\epsilon$ is a very important parameter for SGD. $\\epsilon$ should be reduced after each epoch in general. This is due to the fact that the random sampling of batches acts as a source of noise which might make SGD keep oscillating around the minima without actually reaching it (the image [Source: https://goo.gl/tq6Xof] below shows this). The true gradient of the total cost function (involving the entire dataset) actually becomes 0 when we reach the minimum. Hence, BGD can use a fixed learning rate. <br>\n",
    "![decrease lr](images/decrease_lr.png)\n",
    "The following conditions guarantee convergence in case of SGD: \n",
    "![convergence of sgd](images/sgd_convergence.png) \n",
    "Practically, epsilon is decreased linearly until iteration $\\tau$: \n",
    "![lr update](images/lr_update.png)\n",
    "\n",
    "The main question is how to choose $\\epsilon_0$. Setting it too low makes the training proceed slowly which might lead to the algorithm being stuck at a high cost value. Setting it too high would lead to large oscillations which might even push the learning outside the optimal region. The best way is to monitor the first several iterations and set the learning rate to be higher than the best performing one, but not too high to cause instability. <br> <br>\n",
    "\n",
    "![lr_high_low](images/lr_high_low.png)\n",
    "\n",
    "A big advantage of SGD is that the time taken to compute a weight update doesn't grow with the number of training examples as each update is computed after observing a batch of samples which is independent of the total number of training examples. Theoretically, BGD makes the error rate $O(\\frac{1}{k})$ after *k* iterations whereas SGD makes it $O(\\frac{1}{\\sqrt{k}})$. However, SGD compensates for this with its advantages after a few iterations along with the ability to make rapid updates in the case of a large training set.\n",
    "\n",
    "- **Momentum**: The momentum algorithm accumulates the exponentially decaying moving average of past gradients (called as velocity) and uses it as the direction in which to take the next step. Momentum is given by mass times velocity, which is equal to velocity if we're using unit mass. The momentum update is given by:\n",
    "\n",
    "![momentum](images/momentum_update.png)\n",
    "\n",
    "The step size (earlier equal to learning rate * gradient) now depends on how large and aligned the sequence of gradients are. If the gradients at each iteration point in the same direction (say g), it will lead to a higher value of the step size as they just keep accumulating. Once it reaches a constant (terminal) velocity, the step size becomes ϵ || g|| / (1 - α). Thus, using α as 0.9 makes the speed 10 times. Common values of α are 0.5, 0.9 and 0.99.\n",
    "\n",
    "![momentum_visual](images/momentum.png)\n",
    "\n",
    "Viewing it as the Newtonian dynamics of a particle sliding down a hill, the momentum algorithm consists of solving a set of differential equations via numerical simulation. There are two kinds of forces involved as shown below:\n",
    "\n",
    "![momentum_newton](images/momentum_ball_roll.png)\n",
    "Momentum can be seen as two forces operating together. 1) Proportional to the negative of the gradient such that whenever it descends a steep part of the surface, it gathers speed and continues sliding in that direction until it goes uphill again. 2) A viscous drag force (friction) proportional to -v(t) without the presence of which the particle would keep oscillating back and forth as the negative of the gradient would keep forcing it to move downhill . Viscous force is suitable as it is weak enough to allow the gradient to cause motion and strong enough to resist any motion if the gradient doesn't justify moving.\n",
    "\n",
    "Read more about momentum in this excellent blog post by [distill.ai](http://www.distill.ai/): [Why Momentum Really Works](https://distill.pub/2017/momentum/).\n",
    "\n",
    "\n",
    "- **Nesterov Momentum**: This is a slight modification of the usual momentum equation. Here, the gradient is calculated after applying the current velocity to the parameters, which can be viewed as adding a correction factor.\n",
    "\n",
    "![nesterov](images/nesterov.png)\n",
    "\n",
    "The intuition behind Nesterov momentum is that upon being at a point θ in the parameter space, the momentum update is going to shift the point by $\\alpha$v. So, we are soon going to end up in the vicinity of ($\\theta$ + $\\alpha$v). Thus, it might be better to compute the gradient from that point onward. The figure below describes this visually:\n",
    "\n",
    "![nesterov_intuition](images/nesterov.jpeg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Parameter Initialization Strategies\n",
    "\n",
    "Training algorithms for deep learning models are iterative in nature and require the specification of an initial point, which is extremely crucial as it decides whether the algorithm would converge or not and if it does, then is it as a point with a high cost or low cost. We have limited understanding of neural network optimization but the one property that we know with complete certainty is that the initialization should break symmetry. This means that if two hidden units are connected to the same input units, then these should have different initialization or else the gradient would update both the units in the same way and we don't learn anything new by using an additional unit. The idea of having each unit learn something different motivates random initialization of weights which is also computationally cheaper. \n",
    "\n",
    "Biases are often chosen heuristically (zero mostly) and only the weights are randomly initialized, almost always from a Gaussian or uniform distribution. The scale of the distribution is of utmost concern. Large weights might have better symmetry-breaking effect but might lead to chaos (extreme sensitivity to small perturbations in the input) and exploding values during forward & back propagation. As an example of how large weights might lead to chaos, consider that there's a slight noise adding $\\epsilon$ to the input. Now, we if did just a simple linear transformation like `W * x`, the $\\epsilon$ noise would add a factor of W * $\\epsilon$ to the output. In case the weights are high, this ends up making a significant contribution to the output. SGD and its variants tend to halt in areas near the initial values, thereby expressing a prior that the path to the final parameters from the initial values is discoverable by steepest descent algorithms. A more mathematical explanation for the symmetry breaking can be found in the [Appendix](https://github.com/dalmia/Deep-Learning-Book-Chapter-Summaries/blob/master/Appendix.ipynb).\n",
    "\n",
    "Various suggestions have been made for appropriate initialization of the parameters. The most commonly used ones include sampling the weights of each fully-connected layer having `m` inputs and `n` outputs uniformly from the following distributions:\n",
    "- $U(-\\frac{1}{\\sqrt{m}}, \\frac{1}{\\sqrt{m}})$\n",
    "- $U(-\\sqrt{\\frac{6}{n+m}}, \\sqrt{\\frac{6}{m+n}})$\n",
    "\n",
    "U(a, b) represents the uniform distribution where the probability of each value between a and b, a and b inclusive, is 1/(b-a). The probability of every other value is 0. \n",
    "\n",
    "![uniform dist](images/uniform_distribution.png)\n",
    "\n",
    "These have already been incorporated into most commonly used Deep Learning frameworks so that you can just specify which initializer to use and the framework takes care of sampling appropriately. For e.g. [Keras](https://keras.io/), which is a very famous deep learning framework, has a module called [initializers](https://keras.io/initializers/), where the second type of distribution is implemented as glorot_uniform .\n",
    "\n",
    "These initializations have already been incorporated into the most commonly used Deep Learning frameworks nowadays so that you can just specify which initializer to use and the framework takes care of sampling appropriately. For e.g. Keras, which is a very famous deep learning framework, has a module called initializers, where the second distribution (among the 2 mentioned above) is implemented as glorot_uniform .\n",
    "\n",
    "One drawback of using 1 / √m as the standard deviation is that the weights end up being small when a layer has too many input/output units. Motivated by the idea to have the total amount of input to each unit independent of the number of input units m, Sparse initialization sets each unit to have exactly k non-zero weights. However, it takes a long time for GD to correct incorrect *large values* and hence, this initialization might cause problems.\n",
    "\n",
    "If the weights are too small, the range of activations across the mini-batch will shrink as the activations propagate forward through the network.By repeatedly identifying the ﬁrst layer with unacceptably small activations and increasing its weights, it is possible to eventually obtain a network with reasonable initial activations throughout.\n",
    "\n",
    "The biases are relatively easier to choose. Setting the biases to zero is compatible with most weight initialization schemes except for a few cases for e.g. when used for an output unit, to prevent saturation at initialization or when using unit as a gate for making a decision. Refer to the [chapter](https://www.deeplearningbook.org/contents/optimization.html#pf1f) for details."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Algorithms with Adaptive Learning Rates\n",
    "\n",
    "- **AdaGrad**: As mentioned in above, it is important to incrementally decrease the learning rate for faster convergence. Instead of manually reducing the learning rate after each (or several) epochs, a better approach is to adapt the learning rate as the training progresses. This can be done by scaling the learning rates of *each model parameter* individually inversely proportional to the square root of the sum of historical squared values of the gradient. In the parameter update equation below, r is initialized with 0 and the multiplication in the update step happens element-wise as mentioned. Since the gradient value would be different for each parameter, the learning rate is scaled differently for each parameter too. Thus, those parameters having a large gradient have a large decrease in the learning rate as the learning rate might be too high leading to oscillations or it might be approaching the minima but having large learning rate might cause it to jump over the minima as explained in the figure below, because of which the learning rate should be decreased for better convergence, while those with small gradients have a small decrease in the learning rate as they might have already approached their respective minima and should not be pushed away from that. Even if they have not, reducing the learning rate too much would reduce the gradient even further leading to slower learning.\n",
    "\n",
    "![adagrad update](images/adagrad.png)\n",
    "\n",
    "![adagrad requirement](images/convex.png)\n",
    "\n",
    "This figure illustrates the need to reduce the learning rate if gradient is large in case of a single parameter. 1) One step of gradient descent representing a large gradient value. 2) Result of reducing the learning rate - moves towards the minima 3) Scenario if the learning rate was not reduced - it would have jumped over the minima.\n",
    "\n",
    "However, accumulation of squared gradients from the very beginning can lead to excessive and premature decrease in the learning rate. Consider that we had a model with only 2 parameters (for simplicity) and both the initial gradients are 1000. After some iterations, the gradient of one of the parameters has reduced to 100 but that of the other parameter is still around 800. However, because of the accumulation at each update, the accumulated gradient would still have almost the same value. For e.g. let the accumulated gradients at each step for the Parameter 1 be `1000 + 900 + 700 + 400 + 100 = 3100, 1/3100=0.0003` and that for Parameter 2 be: `1000 + 900 + 850 + 800 + 750 = 4300, 1/4300 = 0.0002`. This would lead to a similar decrease in the learning rates for both the parameters, even though the parameter having the lower gradient might have its learning rate reduced too much leading to slower learning.\n",
    "\n",
    "\n",
    "![adagrad problem](images/adagrad_problem.png)\n",
    "\n",
    "The figure above explains the problem with AdaGrad. Accumulated gradients can cause the learning rate to be reduced far too much in the later stages leading to slower learning\n",
    "\n",
    "\n",
    "- **RMSProp**: RMSProp addresses the problem caused by accumulated gradients in AdaGrad. It modifies the gradient accumulation step to an exponentially weighted moving average in order to discard history from the extreme past. The RMSProp update is given by:\n",
    "\n",
    "![rmsprop](images/rmsprop.png)\n",
    "\n",
    "In the figure, **ρ** is the weighing used for exponential averaging. As more updates are made, the contribution of past gradient values are reduced since **ρ** < 1 \n",
    "and **ρ** > **ρ**² > **ρ**³ …\n",
    "\n",
    "This allows the algorithm to converge rapidly after finding a convex bowl, as if it were an instance of AdaGrad initialized within that bowl. Let me explain why this is so. Consider the figure below. The region represented by 1 indicates usual RMSProp parameter updates as given by the update equation, which is nothing but exponentially averaged AdaGrad updates. Once the optimization process lands on A, it essentially lands at the top of a convex bowl. At this point, intuitively, all the updates before A can be seen to be forgotten due to the exponential averaging and it can be seen as if (exponentially averaged) AdaGrad updates start from point A onwards.\n",
    "\n",
    "![rmsprop convergence](images/nonconvex.png)\n",
    " \n",
    "The figure above explains the intuition behind RMSProp. 1) Usual parameter updates 2) Once it reaches the convex bowl, exponentially weighted averaging would cause the effect of earlier gradients to reduce and to simplify, we can assume their contribution to be zero. This can be seen as if AdaGrad had been used with the training initiated inside the convex bowl\n",
    "\n",
    "\n",
    "- **Adam**: Adapted from \"adaptive moments\", it focuses on combining RMSProp and Momentum. Firstly, it views Momentum as an estimate of the first-order moment and RMSProp as that of the second moment. The weight  update for Adam is given by:\n",
    "\n",
    "![adam_update](images/adam_update.png)\n",
    "\n",
    "Secondly, since s and r are initialized as zeros, the authors observed a bias during the initial steps of training thereby adding a correction term for both the moments to account for their initialization near the origin. As an example of what is the effect of this bias correction, we'll look at the values of **s** and **r** for a single parameter (in which case everything is now represented as a scalar). Let's first understand what would happen if there was no bias correction. Since *s* (notice that this is not in bold as we are looking at the value for a single parameter and the *s* here is a scalar) is initialized as zero, after the first iteration, the value of *s* would be (1 - $\\rho_1$) X g and that of *r* would be (1 - $\\rho_2$) X g². The [preferred values](https://arxiv.org/pdf/1412.6980.pdf) for  $\\rho_1$ and  $\\rho_2$ are 0.9 and 0.99 respectively. Thus, the initial values of s and r are pretty small and this gets compounded as the training progress. However, if we now use bias correction, after the first iteration, the value of s is just g and that of r is just g². This gets rid of the bias that occurs in the initial phase of training. A major advantage of Adam is that it's [fairly robust](https://stats.stackexchange.com/questions/232719/what-is-the-reason-that-the-adam-optimizer-is-considered-robust-to-the-value-of) to the choice of these hyperparameters, i.e.  $\\rho_1$ and  $\\rho_2$.\n",
    "\n",
    "The figure below shows the comparison between the various optimization methods discussed above. It can be clearly seen that algorithms with adaptive learning rates provide faster convergence:\n",
    "\n",
    "![optimizers_comparison](images/optimizers_comparison.gif)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.  Approximate Second-Order Methods\n",
    "\n",
    "The optimization algorithms that we've looked at till now involved computing only the first  derivative. But there are many methods which involve higher order derivatives as well. The main problem with these algorithms are that they are not practically feasible in their vanilla form and so, certain methods are used to approximate the values of the derivatives. We explain three such methods, all of which use empirical risk as the objective function:\n",
    "\n",
    "- **Newton's Method**: This is the most common higher-order derivative method used. It makes use of the curvature of the loss function via its second-order derivative to arrive at the optimal point. Using the second-order Taylor Series expansion to approximate the $\\mathbf{\\it{J}(\\theta)}$ around a point $\\mathbf{\\theta_o}$ and ignoring derivatives of higher order, we get:\n",
    "\n",
    "![newton](images/newton.png)\n",
    "\n",
    "We know that we get a critical point for any function f(x) by solving for f'(x) = 0. We get the following critical point of the above equation (refer to the [Appendix](https://github.com/dalmia/Deep-Learning-Book-Chapter-Summaries/blob/master/Appendix.ipynb) for proof):\n",
    "\n",
    "![newton point](images/newton_point.png)\n",
    "\n",
    "For quadratic surfaces (i.e. where cost function is quadratic), this directly gives the optimal result in one step whereas gradient descent would still need to iterate. However, for surfaces that are not quadratic, as long as the [Hessian remains positive definite](https://math.stackexchange.com/questions/1985889/why-how-does-the-determinant-of-the-hessian-matrix-combined-with-the-2nd-deriva), we can obtain the optimal point through a 2-step iterative process - 1) Get the inverse of the Hessian and 2) update the parameters.\n",
    "\n",
    "\n",
    "[Saddle points](https://medium.com/inveterate-learner/deep-learning-book-chapter-8-optimization-for-training-deep-models-part-i-20ae75984cb2#c3a9) are problematic for Newton's method. If all the eigenvalues are not positive, Newton's method might cause the updates to move in the wrong direction. A way to avoid this is to add regularization:\n",
    "\n",
    "![regularization](images/regularization.png)\n",
    "\n",
    "However, if there is a strong negative curvature, $\\alpha$ needs to be sufficiently large to offset the negative eigenvalues in which case the Hessian becomes dominated by the diagonal matrix thereby leading to an update which becomes the standard gradient divided by $\\alpha$. \n",
    "\n",
    "![hessian_as_gd](images/hessian_as_gd.png)\n",
    "\n",
    "Another problem restricting the use of Newton's method is the computational cost. It takes $O(k^3)$ time to calculate the inverse of the Hessian where $k$ is the number of parameters. It's not uncommon for Deep Neural Networks to have about a million parameters and since the parameters are updated every iteration, this inverse needs to be calculated at every iteration, which is not computationally feasible.\n",
    "\n",
    "\n",
    "- **Conjugate Gradients**: One weakness of the method of steepest descent (i.e. GD) is that [line searches](http://www.deeplearningbook.org/contents/numerical.html#pf7) happen along the direction of the gradient. Suppose the previous search direction is $d_{t-1}$. Once the search terminates (which it does when the gradient along the current gradient direction vanishes) at the minimum, the next search direction, $d_{t}$ is given by the gradient at that point, which is orthogonal to $d_{t-1}$ (because if it's not orthogonal, it'll have some component along $d_{t-1}$ which cannot be true as at the minimum, the gradient along $d_{t-1}$ has vanished). \n",
    "Upon getting the minimum along the current search direction, the minimum along the previous search direction is not preserved, undoing, in a sense, the progress made in previous search direction.\n",
    "\n",
    "![conjugate gradient](images/conjugate_gradient.png)\n",
    "\n",
    "In the method of conjugate gradients, we seek a search direction that is conjugate to the previous line search direction:\n",
    "\n",
    "![conjugate_gd](images/conjugate_gd.png)\n",
    "\n",
    "with $d_t$ and $d_{t-1}$ being called as **conjugate** if $d^T_tHd_{t-1} = 0$.\n",
    "where $\\beta_t$ decides how much of $d_{t-1}$ is added back to the current search direction. There are two popular choices for $\\beta_t$ - Fletcher-Reeves and Polak-Ribière. These discussions assumed the cost function to be quadratic. To extend the concept to work for training neural networks, there is one additional change. Since it's no longer quadratic, there's no guarantee anymore than the conjugate direction would preserve the minimum in the previous search directions. Thus, the algorithm includes occasional resets where the method of conjugate gradients is restarted with line search along the unaltered gradient.\n",
    "\n",
    "- **BFGS**: This algorithm tries to bring the advantages of Newton's method without the additonal computational burden by approximating $H^{-1}$ by $M_t$, which is iteratively refined using low-rank updates. Finally, line search is conducted along the direction  $M_tg_t$. BFGS requires storing the matrix $M_t$ which takes $O(n^2)$ memory making it infeasible. An approach called Limited Memory BFGS (L-BFGS) has been proposed to tackle this infeasibility by computing the matrix $M_t$ using the same method as BFGS but assuming that $M_{t-1}$ is the identity matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7. Optimization Strategies and Meta-Learning Algorithms\n",
    "\n",
    "- **Batch Normalization**: Batch normalization (BN) is one of the most exciting innovations in Deep learning that has significantly stabilized the learning process and allowed faster convergence rates. The intuition behind batch normalization is as follows: Most of the Deep Learning networks are compositions of many layers (or functions) and the gradient with respect to one layer is taken considering the other layers to be constant. However, in practise all the layers are updated simultaneously and this can lead to unexpected results. For example, let $\\tilde{y}$ = x $W_1$ $W_2$ … $W_n$. Here, $\\tilde{y}$ is a linear function of x but not a linear function of the weights. Suppose the gradient is given by g and we now intend to reduce $\\tilde{y}$ by 0.1. Using first-order Taylor Series approximation, taking a step of ϵg would reduce $\\tilde{y}$ by $\\epsilon g^T g$ . Thus, $\\epsilon$ should be $\\frac{0.1}{g^T g}$ just using the first-order information. However, higher order effects also creep in as the updated $\\tilde{y}$ is given by:\n",
    "\n",
    "![update](images/batch_norm.png)\n",
    "\n",
    "An example of a second-order term would be $\\epsilon^2$ $g^1$ $g^2$ $\\prod w_i$. $\\prod w_i$ can be negligibly small or exponentially high depending on whether the individual weights are less than or greater than 1. Since the updates to one layer is so strongly dependent on the other layers, choosing an appropriate learning rate is tough. Batch normalization takes care of this problem by using an efficient reparameterization of almost any deep network. Given a matrix of activations, H, the normalization is given by: $ H' = \\frac{H-\\mu}{\\sigma}$, where the subtraction and division is [broadcasted](https://docs.scipy.org/doc/numpy-1.13.0/user/basics.broadcasting.html).\n",
    "\n",
    "![update](images/batch-normalization.png)\n",
    "\n",
    "Going back to the earlier example of $\\tilde{y}$, let the activations of layer l be given by $h_{l-1}$. Then $h_{l-1}$ = x $W_1$ $W_2$ … $W_{l-1}$. Now, if x is drawn from a unit Gaussian, then $h_{l-1}$ also comes from a Gaussian, however, not of zero mean and unit variance, as it is a linear transformation of x. BN makes it zero mean and unit variance. Therefore, $\\tilde{y}$ = $W_l$ $h_{l-1}$ and thus, the learning now becomes much simpler as the parameters at the lower layers mostly do not have any effect. This simplicity was definitely achieved by rendering the lower layers useless. However, in a realistic deep network with non-linearities, the lower layers remain useful. Finally, the complete reparameterization of BN is given by replacing H with $\\gamma$H' + $\\beta$. This is done to retain its expressive power and the fact that the mean is solely determined by $\\beta$. Also, among the choice of normalizating X or XW + B, the authors recommend the latter, specifically XW, since B becomes redundant because of $\\beta$. Practically, this means that when we are using the Batch Normalization layer, the biases should be turned off. In a deep learning framework like [Keras](http://keras.io), this can be done by setting the parameter *use_bias=False* in the Convolutional layer.\n",
    "\n",
    "- **Coordinate Descent**: Generally, a single weight update is made by taking the gradient with respect to every parameter. However, in cases where some of the parameters might be independent (discussed below) of the remaining, it might be more efficient to take the gradient with respect to those independent sets of parameters separately for making updates. Let me clarify that with an example. Suppose we have the following cost function:\n",
    "\n",
    "![coordinate descent](images/coordinate_descent.png)\n",
    "\n",
    "This cost function describes the learning problem called sparse coding. Here, **H** refers to the sparse representation of **X** and **W** is the set of weights used to linearly decode **H** to retrieve **X**. An explanation of why this cost function enforces the learning of a sparse representation of X follows. The first term of the cost function penalizes values far from 0 (positive or negative because of the modulus, |H|, operator. This enforces most of the values to be 0, thereby sparse. The second term is pretty self-explanatory in that it compensates the difference between **X** and **H** being linearly transformed by **W**, thereby enforcing them to take the same value. In this way, **H** is now learned as a sparse \"representation\" of **X**. The cost function generally consists of additionally a [regularization](https://medium.com/inveterate-learner/deep-learning-book-chapter-7-regularization-for-deep-learning-937ff261875c) term like [weight decay](https://medium.com/inveterate-learner/deep-learning-book-chapter-7-regularization-for-deep-learning-937ff261875c#e021), which has been avoided for simplicity. Here, we can divide the entire list of parameters into two sets, **W** and **H**. Minimizing the cost function with respect to any of these sets of parameters is a convex problem. Coordinate Descent (CD) refers to minimizing the cost function with respect to only 1 parameter at a time. It has been shown that repeatedly cycling through all the parameters, we are guaranteed to arrive at a local minima. If instead of 1 parameter, we take a set of parameters as we did before with **W** and **H**, it is called block coordinate descent (the interested reader should explore [Alternating Minimization](http://www.mit.edu/~rakhlin/6.883/lectures/lecture07.pdf)). CD makes sense if either the parameters are clearly separable into independent groups or if optimizing with respect to certain set of parameters is more efficient than with respect to others.\n",
    "\n",
    "A visual explanation for coordinate descent:\n",
    "\n",
    "![coord desc 2](images/coordinate_descent2.png)\n",
    "\n",
    "The points A, B, C and D indicates the locations in the parameter space where coordinate descent landed after each gradient step. ([Source](https://www.researchgate.net/figure/Coordinate-Descent-CD-CD-algorithm-searches-along-one-coordinate-direction-in-each_fig2_262805949))\n",
    "\n",
    "\n",
    "Coordinate descent may [fail terribly](https://www.deeplearningbook.org/contents/optimization.html#pf30) when one variable influences the optimal value of another variable.\n",
    "\n",
    "- **Polyak Averaging**: Polyak averaging consists of averaging several points in the parameter space that the optimization algorithm traverses through. So, if the algorithm encounters the points θ(1), θ(2), … during optimization, the output of Polyak averaging is:\n",
    "\n",
    "![polyak](images/polyak.png)\n",
    "\n",
    "The figure below explains the intuition behind Polyak averaging:\n",
    "\n",
    "![polyak](images/polyak_intuition.png)\n",
    "\n",
    "Most optimization problems in deep learning are non-convex where the path taken by the optimization algorithm is quite complicated and it might happen that a point visited in the distant past might be quite far from the current point in the parameter space. Thus, including such a point in the distant past might not be useful, which is why an exponentially decaying running average is taken. This scheme where the recent iterates are weighted more than the past ones is called **Polyak-Ruppert Averaging**:\n",
    "\n",
    "![polyak](images/polyak_exp.png)\n",
    "\n",
    "- **Supervised Pre-training**: Sometimes it's hard to directly train to solve for a specific task. Instead it might be better to train for solving a simpler task and use that as an initialization point for training to solve the more challenging task. As an intuition for why this seems logical, consider that you didn't have any background in integration and were asked to learn how to compute the following integral:\n",
    "\n",
    "![dvance integral](images/advance_int.jpg)\n",
    "\n",
    "If you're anyone close to a normal person, your first reaction would be:\n",
    "\n",
    "![meme](images/math_meme.jpg)\n",
    "\n",
    "However, wouldn't it be better if you were asked to understand the more basic integrations first:\n",
    "\n",
    "![easy int](images/easy_int.gif)\n",
    "\n",
    "I hope you understand what I meant with this example - learning a simpler task would put you in a better position to understand the more complex task. This particular strategy of training to solve a simpler task before facing the herculean one is called pretraining. A particular type of pretraining, called **greedy supervised pretraining**, firstly breaks a given supervised learning problem into simpler supervised learning ones and solving for the optimal version of each component in isolation. To build on the above intuition, the hypothesis as to why this works is that it gives better guidance to the intermediate layers of the network and helps in both, generalization and optimization. More often that not, the greedy pretraining is followed by a fine-tuning stage where all the parts are jointly optimized to search for the optimal solution to the full problem. As an example, the figure below shows how each hidden layer is trained one at a time, where the input to the hidden layer being learned is the output of the previously trained hidden layer.\n",
    "\n",
    "![greedy](images/greedy_final.png)\n",
    "\n",
    "Greedy supervised pretraining (a) The first hidden layer is being trained only using the original inputs and outputs. (b) For training the second hidden layer, the hidden-output connection from the first hidden layer is removed and the output of the first hidden layer is used as the input.\n",
    "\n",
    "Also, **[FitNets](https://arxiv.org/abs/1412.6550)** shows an alternative way to guide the training process. Deep networks are hard to train mainly because as deeper the model gets, more non-linearities are introduced. The authors propose the use of a shallower and wider **teacher** network that is trained first. Then, a second network which is thinner and deeper, called the **student** network is trained to predict not only the final outputs but also the intermediate layers of the teacher network. For those who might not be clear with what deep, shallow, wide and thin might mean, refer the following diagram:\n",
    "\n",
    "![deep shallow](images/deep_shallow.png)\n",
    "\n",
    "The idea is that predicting the intermediate layers of the teacher network provides some hints as to how the layers of the student network should be used and aids the optimization procedure. It was shown that without the hints to the hidden layers, the students networks performs poorly in both the training and test data.\n",
    "\n",
    "- **Designing Models to Aid Optimization**: Most of the work in deep learning has been towards making the models easier to optimize rather than designing a more powerful optimization algorithm. This is evident from the fact that Stochastic Gradient Descent, which is primarily used for training deep models today, has been in use [since the 1960s](https://en.wikipedia.org/wiki/Stochastic_gradient_descent#Applications). Many of the current design choices lend towards using linear transformations between layers and using activation functions like ReLU (max(0, x)) which are linear for the most part and enjoy large gradients as compared to sigmoidal units which saturate easily. Also, linear functions increase in a particular direction. Thus, if there's an error, there's a clear direction towards which the output should move to minimize the error.\n",
    "\n",
    "![residual](images/residual.png)\n",
    "\n",
    "[Residual connections](https://arxiv.org/pdf/1512.03385.pdf) reduce the length of the shortest path from the output to the lower layers, thereby allowing a larger gradient to flow through and hence, tackling the [vanishing gradient problem](https://medium.com/inveterate-learner/deep-learning-book-chapter-8-optimization-for-training-deep-models-part-i-20ae75984cb2#6fd2). Similarly, [GoogleNet](https://arxiv.org/pdf/1409.4842.pdf) attached multiple copies of the output to intermediate layers so that a larger gradient flows to those layers. Once training is complete, the auxiliary heads are removed.\n",
    "\n",
    "![inception](images/inception.png)\n",
    "\n",
    "- **Continuation Methods and Curriculum Learning**: Based on the explanation given in the book (and also given that it's fairly short), I'd recommend the interested reader to refer the [book](http://www.deeplearningbook.org/contents/optimization.html#pf35) directly. The reason being that I realized that the content there was exactly to the point with no further scope of summarizing and hence, found it redundant to explain it again here. To give a very brief idea, **Continuation Methods** are a family of strategies where instead of a single cost function, a series of cost functions are optimized to aid optimization by making sure that the algorithm spends most of the time in well-behaved regions in the parameter space. The series of cost functions are designed such that the cost functions become progressively harder to solve, i.e. the first cost function is easiest to solve and the final cost function (which is actually the cost function we wanted to minimize) is the toughest, and the solution to each easier cost function serves as a good initialization point for the next, harder-to-optimize cost function. **Curriculum Learning** can be interpreted as a type of continuation method where the learning process is planned such that the simpler concepts are learned first and then the harder ones which depend on those simpler concepts. This concept had been shown to accelerate progress in animal training. One simple way to use it in the context of machine learning is to initially show the algorithm more of the easier images and less of the harder images. As the learning progresses, the proportion of easier images is reduced and that of the harder images is increased so that the model can ultimately learn the harder task."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}