la_16_derivative_gradient_hessian.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "#### 1st derivative"
      ],
      "metadata": {
        "id": "Aya28rHL1Yc6"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Assume `column vector convention`, which is the most commonly used convention in matrix calculus"
      ],
      "metadata": {
        "id": "vw1WZDtjEZhr"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For `vectors` $a$ and $x$, general matrix $A$ and symmetric matrix $S$\n",
        "\n",
        "$$\\begin{align*}\n",
        "\\frac{\\partial a^Tx}{\\partial x}&=a \\\\\n",
        "& \\\\\n",
        "\\frac{\\partial Ax}{\\partial x}&=A \\\\\n",
        "& \\\\\n",
        "\\frac{\\partial x^TSx}{\\partial x}&=2Sx\n",
        "\\end{align*}$$"
      ],
      "metadata": {
        "id": "s9JRN0lOHziu"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Jacobian"
      ],
      "metadata": {
        "id": "-ahnQa6bru5v"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Suppose $f: \\mathbf{R}^n \\rightarrow \\mathbf{R}^m$ and is differentiable, then for a point $z$ close to $x$, we have the following 1st order approximation\n",
        "\n",
        "$$f(z)=f(x)+Df(x)(z-x)$$\n",
        "\n",
        "where $Df(x)$ is known as the `Jacobian` of $f$ at $x$\n",
        "\n",
        "$$Df(x)_{ij}=\\frac{\\partial f_i(x)}{\\partial x_j}, i=1, \\cdots, m, \\,\\,j=1, \\cdots, n$$"
      ],
      "metadata": {
        "id": "CPdM5D6Xqugo"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Gradient"
      ],
      "metadata": {
        "id": "5iRCn-QNrwG0"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "When $f$ is `scalar-valued`, that is $f: \\mathbf{R}^n \\rightarrow \\mathbf{R}$, then the Jacobian is a $1 \\times n$ matrix (i.e., a `row` vector) and its `transpose` is called the gradient of $f$ at $x$\n",
        "\n",
        "$$\\nabla f(x) = Df(x)^T\\in \\mathbf{R}^n$$\n",
        "\n",
        "This is a `column` vector\n",
        "\n",
        "$$\\left(\\nabla f(x)\\right)_i=\\frac{\\partial f(x)}{\\partial x_i}, i=1, \\cdots, n$$\n",
        "\n",
        "and the 1st approximation becomes\n",
        "\n",
        "$$f(z)=f(x)+\\nabla f(x)^T (z-x)$$"
      ],
      "metadata": {
        "id": "O_XawbKsrzEG"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Chain rule for 1st derivative"
      ],
      "metadata": {
        "id": "Uc9bKHUCsoTC"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Suppose $f: \\mathbf{R}^n \\rightarrow \\mathbf{R}^m$ and $g: \\mathbf{R}^m \\rightarrow \\mathbf{R}^p$\n",
        "\n",
        "Define $h: \\mathbf{R}^n \\rightarrow \\mathbf{R}^p$ by $h(x)=g(f(x))$ and assume no problem in domain feasibility and differentiability, then\n",
        "\n",
        "$$Dh(x)=Dg(f(x))Df(x)$$\n",
        "\n",
        "and if $f: \\mathbf{R}^n \\rightarrow \\mathbf{R}$ and $g: \\mathbf{R} \\rightarrow \\mathbf{R}$, we have\n",
        "\n",
        "$$\\nabla h(x)=g'(f(x))\\nabla f(x)$$"
      ],
      "metadata": {
        "id": "lOug9qYZsyC0"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For composition with `affine` function, $f: \\mathbf{R}^n \\rightarrow \\mathbf{R}^m$, $A\\in \\mathbf{R}^{n \\times p}, b\\in \\mathbf{R}^n$\n",
        "\n",
        "If $g(x)=f(Ax+b)$, then the Jacobian\n",
        "\n",
        "$$Dg(x)=Df(Ax+b)D(Ax+b)=Df(Ax+b)A$$\n",
        "\n",
        "When $f$ is scalar-valued, we have the gradient\n",
        "\n",
        "$$\\nabla g(x)=Dg(x)^T=A^T\\nabla f(Ax+b)$$"
      ],
      "metadata": {
        "id": "Gq9HfhlJtpCr"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##### Example"
      ],
      "metadata": {
        "id": "NnxXwp3UxaF7"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We want to compute the gradient of the following $$f(x)=\\log\\sum_{i=1}^m \\exp(a_i^Tx+b_i)$$"
      ],
      "metadata": {
        "id": "q5RdnAz4xbx4"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "First, for $g(y)=\\log (\\sum_{i=1}^m \\exp y_i$), we have\n",
        "\n",
        "$$\\begin{align*}\\nabla g(y)&=g'(\\sum_{i=1}^m \\exp y_i)\\nabla (\\sum_{i=1}^m \\exp y_i)\\\\\n",
        "&=\\frac{1}{\\sum_{i=1}^m \\exp y_i}\\begin{bmatrix}\\frac{\\partial (\\sum_{i=1}^m \\exp y_i) }{\\partial y_1}\\\\ \\vdots \\\\ \\frac{\\partial (\\sum_{i=1}^m \\exp y_i) }{\\partial y_m}\\end{bmatrix}\\\\\n",
        "&=\\frac{1}{\\sum_{i=1}^m \\exp y_i}\\begin{bmatrix}\\exp y_1 \\\\ \\vdots \\\\ \\exp y_m \\end{bmatrix}\n",
        "\\end{align*}$$"
      ],
      "metadata": {
        "id": "p6QwIKKm2wsG"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Then, we use the rule for composition with affine function\n",
        "\n",
        "$$\\begin{align*}\\nabla f(x) &= A^T\\nabla g(Ax+b) \\\\\n",
        "&=\\frac{1}{\\mathbf{1}^Tz}A^Tz\n",
        "\\end{align*}$$\n",
        "\n",
        "where\n",
        "\n",
        "$$z=\\begin{bmatrix}\\exp (a_1^Tx+b_1) \\\\ \\vdots \\\\ \\exp (a_m^Tx+b_m) \\end{bmatrix}$$"
      ],
      "metadata": {
        "id": "4fbXST8Q2yPS"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 2nd derivative"
      ],
      "metadata": {
        "id": "EGP2uWkO2puK"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For `scalar`-valued function $f: \\mathbf{R}^n\\rightarrow \\mathbf{R}$, its second derivative or Hessian at $x$ is given by\n",
        "\n",
        "$$\\nabla^2 f(x)_{ij}=\\frac{\\partial^2 f(x)}{\\partial x_i \\partial x_j}, i,j=1, \\cdots, n$$\n",
        "\n",
        "The 2nd derivative can be interpreted as derivative of 1st derivative\n",
        "\n",
        "For $\\nabla f: \\mathbf{R}^n\\rightarrow \\mathbf{R}^n$, we have\n",
        "\n",
        "$$D\\nabla f(x)=\\nabla^2 f(x)$$\n",
        "\n",
        "The 2nd order approximation of $f$ at $z$ close to $x$ is\n",
        "\n",
        "$$f(z)=f(x)+\\nabla f(x)^T(z-x)+\\frac{1}{2}(z-x)^T\\nabla^2 f(x) (z-x)$$"
      ],
      "metadata": {
        "id": "Lh9MnAtB21XC"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Chain rule for 2nd derivative"
      ],
      "metadata": {
        "id": "KTBB3YbS4GD6"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We will skip the general case $f: \\mathbf{R}^n \\rightarrow \\mathbf{R}^m$ and $g: \\mathbf{R}^m \\rightarrow \\mathbf{R}^p$ and focus only the following cases that are more relevant"
      ],
      "metadata": {
        "id": "dpun0J-y5ZCw"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Suppose $f: \\mathbf{R}^n \\rightarrow \\mathbf{R}$ and $g: \\mathbf{R} \\rightarrow \\mathbf{R}$, and $h(x)=g(f(x))$, then we have\n",
        "\n",
        "$$\\nabla^2 h(x)=g'(f(x))\\nabla^2 f(x)+g''(f(x))\\nabla f(x) \\nabla f(x)^T$$"
      ],
      "metadata": {
        "id": "qCqHygIZ5GFf"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For composition with `affine` function, $f: \\mathbf{R}^n \\rightarrow \\mathbf{R}$, $A\\in \\mathbf{R}^{n \\times m}, b\\in \\mathbf{R}^n$ and $g(x)=f(Ax+b)$, then we have\n",
        "\n",
        "$$\\nabla^2 g(x)=A^T\\nabla^2 f(Ax+b) A$$"
      ],
      "metadata": {
        "id": "7qaVL-m65qQq"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##### Example"
      ],
      "metadata": {
        "id": "kMYLgLjh6CUT"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We still use the same example\n",
        "\n",
        "$$f(x)=\\log\\sum_{i=1}^m \\exp(a_i^Tx+b_i)$$"
      ],
      "metadata": {
        "id": "gwGUZmQu6DYG"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "First, for $g(y)=\\log (\\sum_{i=1}^m \\exp y_i$), we have\n",
        "\n",
        "$$\\begin{align*}\n",
        "\\nabla^2g(y)&=g'(\\sum_{i=1}^m \\exp y_i)\\nabla^2 (\\sum_{i=1}^m \\exp y_i)+g''\\nabla(\\sum_{i=1}^m \\exp y_i)\\nabla (\\sum_{i=1}^m \\exp y_i)^T \\\\\n",
        "&=\\frac{1}{\\sum_{i=1}^m \\exp y_i}\\begin{bmatrix}\\exp y_1 & 0 &\\cdots & 0 \\\\ 0 & \\exp y_2 & \\cdots & 0 \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ 0 & 0 & \\cdots &  \\exp y_m \\end{bmatrix} - \\frac{1}{\\left(\\sum_{i=1}^m \\exp y_i\\right)^2}\\begin{bmatrix}\\exp y_1 \\\\ \\vdots \\\\ \\exp y_m \\end{bmatrix}\\begin{bmatrix}\\exp y_1 \\\\ \\vdots \\\\ \\exp y_m \\end{bmatrix}^T\\\\\n",
        "& \\nabla g(y)=\\frac{1}{\\sum_{i=1}^m \\exp y_i}\\begin{bmatrix}\\exp y_1 \\\\ \\vdots \\\\ \\exp y_m \\end{bmatrix}\\\\\n",
        "&=\\text{diag}\\left(\\nabla g(y)\\right)-\\nabla g(y) \\nabla g(y)^T\n",
        "\\end{align*}$$"
      ],
      "metadata": {
        "id": "vw6JktoPRiML"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Then, we use the rule for composition with affine function\n",
        "\n",
        "$$\\begin{align*}\\nabla^2 f(x) &= A^T\\nabla^2 g(Ax+b)A \\\\\n",
        "&=A^T\\left(\\frac{1}{\\mathbf{1}^Tz}\\text{diag}(z)-\\frac{1}{\\left(\\mathbf{1}^Tz\\right)^2}zz^T\\right)A\n",
        "\\end{align*}$$\n",
        "\n",
        "where\n",
        "\n",
        "$$z=\\begin{bmatrix}\\exp (a_1^Tx+b_1) \\\\ \\vdots \\\\ \\exp (a_m^Tx+b_m) \\end{bmatrix}$$"
      ],
      "metadata": {
        "id": "I0r3r8gmVjQd"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "64VKzPhM8fWC"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}