lectures/matrix_calculus.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Matrix calculus\n",
    "\n",
    "\n",
    "## Useful definitions and notations\n",
    "We will treat all vectors as column vectors by default.\n",
    "### Matrix and vector multiplication\n",
    "Let $A$ be $m \\times n$, and $B$ be $n \\times p$, and let the product $AB$ be\n",
    "\n",
    "$$\n",
    "C = AB\n",
    "$$\n",
    "\n",
    "then $C$ is a $m \\times p$ matrix, with element $(i, j)$ given by \n",
    "\n",
    "$$\n",
    "c_{ij} = \\sum_{k=1}^n a_{ik}b_{kj}\n",
    "$$\n",
    "\n",
    "Let $A$ be $m \\times n$, and $x$ be $n \\times 1$, then the typical element of the product\n",
    "\n",
    "$$\n",
    "z = Ax\n",
    "$$\n",
    "\n",
    "is given by\n",
    "\n",
    "$$\n",
    "z_i = \\sum_{k=1}^n a_{ik}x_k\n",
    "$$\n",
    "\n",
    "Finally, just to remind:\n",
    "\n",
    "* $C = AB \\quad C^\\top = B^\\top A^\\top$\n",
    "* $AB \\neq BA$\n",
    "* $e^{A} =\\sum\\limits_{k=0}^{\\infty }{1 \\over k!}A^{k}$\n",
    "* $e^{A+B} \\neq e^{A} e^{B}$\n",
    "\n",
    "### Gradient\n",
    "Gradient\n",
    "Let  $f(x):\\mathbb{R}^n→\\mathbb{R}$, then vector, which contains all first order partial derivatives:\n",
    "\n",
    "$$\n",
    "\\nabla f(x) = \\dfrac{df}{dx} = \\begin{pmatrix}\n",
    "    \\frac{\\partial f}{\\partial x_1} \\\\\n",
    "    \\frac{\\partial f}{\\partial x_2} \\\\\n",
    "    \\vdots \\\\\n",
    "    \\frac{\\partial f}{\\partial x_n}\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "### Hessian \n",
    "Let  $f(x):\\mathbb{R}^n→\\mathbb{R}$, then matrix, containing all the second order partial derivatives:\n",
    "\n",
    "$$\n",
    "f''(x) = \\dfrac{\\partial^2 f}{\\partial x_i \\partial x_j} = \\begin{pmatrix}\n",
    "    \\frac{\\partial^2 f}{\\partial x_1 \\partial x_1} & \\frac{\\partial^2 f}{\\partial x_1 \\partial x_2} & \\dots  & \\frac{\\partial^2 f}{\\partial x_1\\partial x_n} \\\\\n",
    "    \\frac{\\partial^2 f}{\\partial x_2 \\partial x_1} & \\frac{\\partial^2 f}{\\partial x_2 \\partial x_2} & \\dots  & \\frac{\\partial^2 f}{\\partial x_2 \\partial x_n} \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    \\frac{\\partial^2 f}{\\partial x_n \\partial x_1} & \\frac{\\partial^2 f}{\\partial x_n \\partial x_2} & \\dots  & \\frac{\\partial f}{\\partial x_n \\partial x_n}\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "But actually, Hessian could be a tensor in such a way: $\\left(f(x): \\mathbb{R}^n \\to \\mathbb{R}^m \\right)$ is just 3d tensor, every slice is just hessian of corresponding scalar function $\\left( H\\left(f_1(x)\\right), H\\left(f_2(x)\\right), \\ldots, H\\left(f_m(x)\\right)\\right)$\n",
    "\n",
    "### Jacobian\n",
    "The extension of the gradient of multidimensional  $f(x):\\mathbb{R}^n→\\mathbb{R}^m$ :\n",
    "\n",
    "$$\n",
    "f'(x) = \\dfrac{df}{dx^T} = \\begin{pmatrix}\n",
    "    \\frac{\\partial f_1}{\\partial x_1} & \\frac{\\partial f_1}{\\partial x_2} & \\dots  & \\frac{\\partial f_1}{\\partial x_n} \\\\\n",
    "    \\frac{\\partial f_2}{\\partial x_1} & \\frac{\\partial f_2}{\\partial x_2} & \\dots  & \\frac{\\partial f_2}{\\partial x_n} \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    \\frac{\\partial f_m}{\\partial x_1} & \\frac{\\partial f_m}{\\partial x_2} & \\dots  & \\frac{\\partial f_m}{\\partial x_n}\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "### Summary\n",
    "\n",
    "\n",
    "$$\n",
    "f(x) : X \\to Y; \\;\\;\\;\\;\\;\\;\\;\\; \\frac{\\partial f(x)}{\\partial x} \\in G\n",
    "$$\n",
    "\n",
    "|             X             |        Y       |             G             |                   Name                  |\n",
    "|:-------------------------:|:--------------:|:-------------------------:|:----------------------------------------------:|\n",
    "|        $\\mathbb{R}$       |  $\\mathbb{R}$  |        $\\mathbb{R}$       |              $f'(x)$ (derivative)             |\n",
    "|       $\\mathbb{R}^n$      |  $\\mathbb{R}$  |       $\\mathbb{R^n}$      |  $\\dfrac{\\partial f}{\\partial x_i}$ (gradient) |\n",
    "|       $\\mathbb{R}^n$      | $\\mathbb{R}^m$ | $\\mathbb{R}^{n \\times m}$ | $\\dfrac{\\partial f_i}{\\partial x_j}$ (jacobian) |\n",
    "| $\\mathbb{R}^{m \\times n}$ |  $\\mathbb{R}$  | $\\mathbb{R}^{m \\times n}$ |      $\\dfrac{\\partial f}{\\partial x_{ij}}$     |\n",
    "\n",
    "named gradient of  $f(x)$ . This vector indicates the direction of steepest ascent. Thus, vector  $−\\nabla f(x)$  means the direction of the steepest descent of the function in the point. Moreover, the gradient vector is always orthogonal to the contour line in the point.\n",
    "\n",
    "## General concept\n",
    "### Naive approach\n",
    "The basic idea of naive approach is to reduce matrix\\vector derivatives to the well-known scalar derivatives.\n",
    "![](matrix_calculus.svg)\n",
    "One of the most important practical trick here is to separate indicies of sum ($i$) and partial derivatives ($k$). Ignoring this simple rule tends to produce mistakes.\n",
    "### Guru approach\n",
    "The guru approach implies formulating a set of simple rules, which allows you to calculate derivatives just like in a scalar case. It might be convinient to use the differential notation here.\n",
    "\n",
    "#### Differentials\n",
    "After obtaining the differential notaion of $df$ we can retrieve the gradient using following formula:\n",
    "\n",
    "$$\n",
    "df(x) = \\langle \\nabla f(x), dx\\rangle\n",
    "$$\n",
    "\n",
    "Than, if we have differential of the above form and we need to calculate the second derivative of the matrix\\vector function, we treat \"old\" $dx$ as the constant $dx_1$, than calculate $d(df)$\n",
    "\n",
    "$$\n",
    "d^2f(x) = \\langle \\nabla^2 f(x) dx_1, dx_2\\rangle = \\langle H_f(x) dx_1, dx_2\\rangle\n",
    "$$\n",
    "\n",
    "#### Properties\n",
    "\n",
    "Let $A$ and $B$ be the constant matrices, while $X$ and $Y$ are the variables (or matrix functions).\n",
    "\n",
    "* $dA = 0$\n",
    "* $d(\\alpha X) = \\alpha (dX)$\n",
    "* $d(AXB) = A(dX )B$\n",
    "* $d(X+Y) = dX + dY$\n",
    "* $d(X^\\top) = (dX)^\\top$\n",
    "* $d(XY) = (dX)Y + X(dY)$\n",
    "* $d\\langle X, Y\\rangle = \\langle dX, Y\\rangle+ \\langle X, dY\\rangle$\n",
    "* $d\\left( \\dfrac{X}{\\phi}\\right) = \\dfrac{\\phi dX - (d\\phi) X}{\\phi^2}$\n",
    "* $d\\left( \\det X \\right) = \\det X \\langle X^{-\\top}, dX \\rangle $\n",
    "* $d \\text{tr } X = \\langle I, dX\\rangle$\n",
    "* $df(g(x)) = \\dfrac{df}{dg} \\cdot dg(x)$\n",
    "\n",
    "## References\n",
    "* [**solutions**](./data/solutions.pdf)\n",
    "* [Good introduction](https://atmos.washington.edu/~dennis/MatrixCalculus.pdf)\n",
    "* [The Matrix Cookbook](https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf)\n",
    "* [MSU seminars](http://www.machinelearning.ru/wiki/images/a/ab/MOMO18_Seminar1.pdf) (Rus.)\n",
    "* [Online tool](http://www.matrixcalculus.org/) for analytic expression of a derivative.\n",
    "\n",
    "\n",
    "##### Example 1\n",
    "Find $\\nabla f(x)$, if $f(x) = \\dfrac{1}{2}x^TAx + b^Tx + c$.\n",
    "\n",
    "##### Example 2\n",
    "Find the gradient $\\nabla f(x)$ and hessian $f''(x)$, if $f(x) = \\dfrac{1}{2} \\|Ax - b\\|^2_2$.\n",
    "\n",
    "##### Example 3\n",
    "Find $\\nabla f(x), f''(x)$, if $f(x) = -e^{-x^Tx}$.\n",
    "\n",
    "##### Example 4\n",
    "Find the gradient $\\nabla f(x)$ and hessian $f''(x)$, if \n",
    "\n",
    "$$\n",
    "f(x) = \\ln \\left( 1 + \\exp\\langle a,x\\rangle\\right)\n",
    "$$\n",
    "\n",
    "##### Example 5\n",
    "Find $f'(X)$, if $f(X) = \\det X$  \n",
    "\n",
    "Note: here under $f'(X)$ assumes first order approximation of $f(X)$ using Taylor series:\n",
    "\n",
    "$$\n",
    "f(X + \\Delta X) \\approx f(X) + \\mathbf{tr}(f'(X)^\\top \\Delta X)\n",
    "$$\n",
    "\n",
    "##### Example 6\n",
    "Calculate: $\\dfrac{\\partial }{\\partial X} \\sum \\text{eig}(X), \\;\\;\\dfrac{\\partial }{\\partial X} \\prod \\text{eig}(X), \\;\\;\\dfrac{\\partial }{\\partial X}\\text{tr}(X), \\;\\; \\dfrac{\\partial }{\\partial X} \\text{det}(X)$\n",
    "\n",
    "##### Example 7\n",
    "Find $\\nabla f(X)$, if $f(X) = \\langle S, X\\rangle - \\log \\det X$\n",
    "\n",
    "##### Example 8\n",
    "Calculate the derivatives of the loss function with respect to parameters $\\frac{\\partial L}{\\partial W}, \\frac{\\partial L}{\\partial b}$ for the single object $x_i$ (or, $n = 1$)\n",
    "![](./data/simple_learning.svg)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Travelling salesman problem.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "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.7.1"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}