DLBook_ch07.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chapter 7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Regularization for Deep Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<strong>Regularization</strong> - any modification we make to a learning algorithm that is intended to reduce its generalization error but not its training error."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most regularization strategies are based on <strong><em>regularizing estimators</em></strong><br>\n",
    "Regularization of an estimator works by trading <strong> increased bias </strong> for <strong> reduced variance </strong>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Three situations:\n",
    "1. excluded the true data generating process - corresponding to underfitting and inducing bias\n",
    "1. matched the true data generating process\n",
    "1. included the generating process buy also many other possible generating processes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Goal of Regularization is to take a model from the <strong><em> third regime </em></strong> into the <strong><em>second regime</em></strong> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But, We almost never have access to the true data generating process so\n",
    "we can never know for sure if the model family being estimated includes the\n",
    "generating process or not"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " controlling the complexity of the model is not a\n",
    "simple matter of finding the model of the right size, with the right number of\n",
    "parameters <br>\n",
    "Instead, we might find that the <strong><em>best fitting model </em></strong>(in the sense of minimizing generalization error) is a <strong><em>large model that has been regularized appropriately.</em></strong>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.1 Parameter Norm Penalties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Many regularization approaches are based on limiting the capacity of models"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Note that for neural networks, we typically choose to use a parameter norm penalty that Ω penalizes of the affine transformation at each layer and leaves only the weights the biases unregularized. Each bias controls only a single variable. This means that we do not induce too much variance by leaving the biases unregularized.  Also, regularizing the bias parameters can introduce a significant amount of underfitting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "it is still reasonable to use the same weight decay at all layers just to reduce the size of search space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.1.1 $\\;L^2$ Parameter Regularization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a.k.a. <strong> weight decay, ridge regression, Tikhonov regularization </strong> <br>\n",
    "This strategy drives the weights closer to the origin by adding a regularization term ${\\Omega}({\\Theta})\\; = \\; \\frac{1}{2}\\left\\Vert{\\omega}\\right\\Vert^2_2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ \\omega \\; = \\; Q(A\\;+\\alpha I)^{-1}AQ^T\\omega^* $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "effect of weight decay is to rescale $\\omega$ along the axes defined by the eigenvectors of $H\\;=\\;QAQ^T $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Specifically, the component of $\\omega$ that is alogned with the $i$-th eigenvector of $H$ is rescaled by a factor of $\\frac{\\lambda_i}{\\lambda_i + \\alpha}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Along the direction where eigenvalues of $H$ are relatively large (ie. $\\lambda_i >> \\alpha$ ), effect of regularization is relatively small. <br>\n",
    "However, components with $\\lambda_i << \\alpha $ will be shrunk to have nearly zero magnitude"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only the directions along which the parameters contribute significantly to reducing the objective function are preserved relatively intact. <br>\n",
    "In directions that do <strong>NOT</strong> contribute to reducing the objective function, a <strong>small eigenvalue of the Hessian</strong> tells us that movement in this direction will <strong>not</strong> significantly increase the gradient."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.1.2 $\\;L^1$ Regularization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Omega (\\theta) \\; = \\;  \\left\\Vert{\\omega}\\right\\Vert_1 \\; = \\sum_{i} \\left\\vert {\\omega_i}\\right\\vert$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In comparison to $L^2$ regularization, $L^1$ regularization results in a solution that is more <strong>sparse</strong>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The sparsity property induced by $L^1$ regularization has been used extensively as a <strong>feature selection</strong> mechanism <br>\n",
    "<strong> LASSO </strong> (Least Absolute Shrinkage and Selection Operator) model integrates an $L^1$ penalty with a linear model and a least squares cost function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$L^2$ ~ MAP Bayesian inference with a Guassian prior on the weights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$L^1$ ~ MAP Bayesian inference with an isotropic Laplace distribution on the weights "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.2 Norm Penalties as Constrained Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the cost function regularized by a <strong> parameter norm penalty </strong>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\n",
    "    \\hat{J}(\\theta;X,y) \\; = J(\\theta;X,y) \\; + \\alpha\\Omega(\\theta)\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can Minimize a function subject to Constraints by constructing a <strong> generalized Lagrange function </strong> consisting of the <strong><em> original objective function + a set of penalties </em></strong>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Each penalty is a product between a Coefficient (KKT multiplier) and a function representing whether the constraint is satisfied"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- If to constrain $\\Omega(\\theta)$ to be less than some constant $k$, a generalized Lagrange function: <br>\n",
    "\n",
    "\\begin{equation*}\n",
    "\\mathcal{L}(\\theta,\\alpha;X,y)\\; = \\; J(\\theta; X,y)\\; + \\; \\alpha(\\Omega(\\theta)\\; - k)\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{equation*}\n",
    "\\theta^* = \n",
    "\\underset{\\theta}{\\text{arg min}} \\;\n",
    "\\underset{\\alpha,\\alpha \\geq 0}{\\text{max}}\\;{\\mathcal{L}(\\theta,\\alpha)}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "solving this problem requires modifying both $\\theta$ and $\\alpha$ <br>\n",
    "- $\\alpha$ must increase whenever  $\\Omega(\\theta) > k$ <br>\n",
    "- $\\alpha$ must decrease whenever $\\Omega(\\theta) < k$ <br>\n",
    "- All positive $\\alpha$ encourage $\\Omega(\\theta)$ to shrink\n",
    "- Optimal value $\\alpha^*$ will encourage $\\Omega(\\theta)$ to shrink, but not so strongly to make $\\Omega(\\theta) < k$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can also use <strong><em> explicit constraints </em></strong> rather than penalties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- can modify SGD to take a step downhill on $J(\\theta)$ and then project $\\theta$ back to the nearest point that satisfies $\\Omega(\\theta) < k $.\n",
    "- useful if we know what value of $k$ is appropriate and don't want to waste time searching for $\\alpha$ that corresponds to this $k$\n",
    "- penalties can cause non-convex optimization procedures to get stuck in local minima corresponding to small $\\theta$\n",
    "- Explicit constraints implemented by re-projection only have an effect when the weights become large and attempt to leave the constraint region\n",
    "- Explicit constraints with reprojection imposes some <strong> stability </strong> on the optimization procedure - prevents positive feedback loop from continuing to increase the magnitude of the weights without bound.\n",
    "- In practice, column norm limitation is always implemented as an explicit constraint with reprojection so as to prevent any one hidden unit from having very large weights. \n",
    "- If we converted this constraint into a penalty in a Lagrange function, it would be similar to $L^2$ weight decay but with a separate KKT multiplier for the weights of each hidden unit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.3   Regularization and Under-Constrained Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Linear Regression, PCA and many other Linear models depend on <strong> inverting the matrix $X^{T}X$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is not possible whenever $X^{T}X$ is <strong> singular </strong>\n",
    "<br>\n",
    " - when data generating distribution has no variance in some direction\n",
    " - when no variance is <em>observed</em> in some direction - b/c fewer samples than features\n",
    "<br>\n",
    "$\\rightarrow$ Instead invert $X^{T}X + \\alpha I$\n",
    "<br>This regularized matrix is <strong>guaranteed to be invertible</strong>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When relevant matrix is invertible, closed form solutions exist <br>\n",
    "Problem with <strong>no closed form solution</strong> can be <strong>underdetermined</strong> <br>\n",
    "eg. Logistic regression where classes are linearly separable and $w$ is able to achieve perfect classification - then $2w$ will also achieve perfect classification and higher likelihood <br>\n",
    "SGD wll continually increase the magnitude of $w$ until numerical overflow occurs\n",
    "<br><strong>Regularization</strong> will cause SGD to quit increasing the magnitude of the weights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<strong>(7.17)</strong>\n",
    "\\begin{equation*}\n",
    "w = (X^{T} X + \\alpha I)^{-1} X^{T} y\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<strong>(7.29)</strong> - Definition of pseudoinverse $X^+$ of a matrix $X$<br>\n",
    "<br>\n",
    "\\begin{equation*}\n",
    "X^+ = \\underset{\\alpha\\searrow0} {\\text{lim}}\\: (X^{T}X + \\alpha I)^{-1} X^{T}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(7.29) is the limit of (7.17) as the regularization coefficient shrinks to zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4 Dataset Augmentation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "effective/easiest for classification\n",
    " - object recognition\n",
    " - speech recognition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<strong>Input Noise </strong>- can also bee seen as a form of data augmentation <br>\n",
    "Dropout - can be seen as constructing new inputs by <em>multiplying</em> by noise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.5  Noise Robustness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general, noise injection can be more powerful than simply shrinking parameters, especially when noise is added to the <strong><em>hidden units</strong></em> $\\rightarrow$ <strong><em>dropout</strong></em> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another way: adding noise to the <strong><em>weights</strong></em><br>\n",
    " - RNN\n",
    " - can be interpreted as a Stochastic implementation of Bayesian inference over the weights\n",
    " - Bayesian = model weights are uncertain and representable via a probability distribution\n",
    " - Adding noise to the weights = practical, stochastic way to reflect this uncertainty\n",
    " - Can also be interpreted as <strong><em> pushing the model into regions where the model is relatively insensitive to small variations in the weights</strong></em>, finding minima surrounded by flat regions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 7.5.1 Injecting Noise at the Output Targets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most datasets have some amount of mistakes in the $y$ labels <br>\n",
    " $\\rightarrow$ explicitly model the noise on the labels\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ". incorporate into the cost function\n",
    "$\\rightarrow$ <strong><em>label smoothing</strong></em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Maximum likelihood learning with a softmax classifier and hard targets may actually never converge—the softmax can never predict a probability of exactly 0 or 1 exactly, so it will continue to learn larger and larger weights, making more extreme predictions forever"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.6  Semi-Supervised Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Unlabled Examples from $P(x)$\n",
    "1. Labeled Examples from $P(x,y)$ <br>\n",
    "are used to estimate $P(y|x)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Goal is to learn a representation $h = f(x)$ so that examples from the same class have similar representations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Construct models in which a generative model of either $P(x)$ or $P(x,y)$ shares parameters with a discriminative model of $P(y | x)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, trade-off the supervised critereon $- log P(y | x)$ <br>\n",
    "with unsupervised/generative critereon $-log P(x)\\; or\\; -logP(x,y)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generative critereon then expresses a particular form of <strong><em>prior belief</strong></em> about the solution to the supervised learning problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.7   Multi-Task Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Task-specific parameters - only benefit from examples of their task\n",
    "1. Gener"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}