Assignment5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "da5abdd0-543b-45ae-bc30-c08e7703bcd1",
   "metadata": {},
   "source": [
    "# Manual differentiation - Worksheet 5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c57ba291-095d-4b73-bd78-2d7989eb0b11",
   "metadata": {},
   "source": [
    "Given system:\n",
    "\n",
    "$$\n",
    "x_{n+1} = \n",
    "\\begin{bmatrix}\n",
    "x_{n+1,1} \\\\\n",
    "x_{n+1,2} \\\\\n",
    "x_{n+1,3} \\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "x^2_{n,1} + x_{n,2} \\\\ \n",
    "- x_{n,1} + \\frac{x_{n,2}}{2} \\\\\n",
    "- x^2_{n,2} + x_{n,3} \\\\\n",
    "\\end{bmatrix}\n",
    "+\n",
    "\\begin{bmatrix}\n",
    "x_{n,1}\\theta_1 \\\\\n",
    "x_{n,2}\\theta_2 \\\\\n",
    "x_{n,3}\\theta_3 \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b66fc3a1-5499-4dab-88ac-e67ab0c223d3",
   "metadata": {},
   "source": [
    "### (1) One step-control Backprop"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a5bb92c-d63e-4ffa-ba73-8cb5d51a29d4",
   "metadata": {},
   "source": [
    "Current system state and weights:\n",
    "\n",
    "$$\n",
    "x_{0} = (2, -1, 3)^T\n",
    "$$\n",
    "$$\n",
    "\\theta = (1, 4, 2)^T\n",
    "$$\n",
    "\n",
    "Next system state $x_{1}$:\n",
    "$$\n",
    "\\mathbf{x}_1 = \\begin{bmatrix} x_{0,1}^2 + x_{0,2} \\\\ -x_{0,1} + \\frac{x_{0,2}}{2} \\\\ -x_{0,2}^2 + x_{0,3} \\end{bmatrix} + \\begin{bmatrix} x_{0,1}\\theta_1 \\\\ x_{0,2}\\theta_2 \\\\ x_{0,3}\\theta_3 \\end{bmatrix} = \\begin{bmatrix} 2^2 + (-1) + 2\\cdot(-1) \\\\ -2  -0.5 + (-1)\\cdot4 = \\\\ -(-1)^2 + 3 + 3 \\cdot 2 \\end{bmatrix} = \\begin{bmatrix} 1 \\\\ -6.5 \\\\ 8\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Loss function L:\n",
    "$$\n",
    "L = \\|\\mathbf{x}_1\\|_1 = |x_{1,1}| + |x_{1,2}| + |x_{1,3}| = |1| + |-6.5| + |8| = 1 + 6.5 + 8 = 15.5\n",
    "$$\n",
    "\n",
    "Back-propagation gradient \n",
    "$$\n",
    "\\frac{\\partial L}{\\partial \\theta} = \\frac{\\partial L}{\\partial \\mathbf{x}_{1}} \\cdot \\frac{\\partial \\mathbf{x}_{1}}{\\partial \\mathbf{\\theta}}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial \\mathbf{x}_1} = \\begin{bmatrix} \\frac{\\partial L}{\\partial x_{1,1}} \\\\ \\frac{\\partial L}{\\partial x_{1,2}} \\\\ \\frac{\\partial L}{\\partial x_{1,3}} \\end{bmatrix} = \\begin{bmatrix} 1 \\\\ -1 \\\\ 1 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial \\mathbf{x}_1}{\\partial \\boldsymbol{\\theta}} = \\begin{bmatrix} \\frac{\\partial x_{1,1}}{\\partial \\theta_1} & \\frac{\\partial x_{1,2}}{\\partial \\theta_1} & \\frac{\\partial x_{1,3}}{\\partial \\theta_1} \\\\ \\frac{\\partial x_{1,1}}{\\partial \\theta_2} & \\frac{\\partial x_{1,2}}{\\partial \\theta_2} & \\frac{\\partial x_{1,3}}{\\partial \\theta_2} \\\\ \\frac{\\partial x_{1,1}}{\\partial \\theta_3} & \\frac{\\partial x_{1,2}}{\\partial \\theta_3} & \\frac{\\partial x_{1,3}}{\\partial \\theta_3} \\end{bmatrix} = \\begin{bmatrix} x_{0,1} & 0 & 0 \\\\ 0 & x_{0,2} & 0 \\\\ 0 & 0 & x_{0,3} \\end{bmatrix} = \\begin{bmatrix} 2 & 0 & 0 \\\\ 0 & -1 & 0 \\\\ 0 & 0 & 3 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial \\theta} = \\begin{bmatrix} 1 & -1 & 1 \\end{bmatrix} \\cdot \\begin{bmatrix} 2 & 0 & 0 \\\\ 0 & -1 & 0 \\\\ 0 & 0 & 3 \\end{bmatrix} = \\begin{bmatrix} 2 \\\\ 1 \\\\ 3 \\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2a9b109-91ae-42f5-97ab-277b59edb869",
   "metadata": {},
   "source": [
    "### (2) Multi-step control Backprop\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09b645c5-b38a-4dec-9a6b-4e3905c6aafb",
   "metadata": {},
   "source": [
    "Current system state and weights:\n",
    "\n",
    "$$\n",
    "x_{0} = (-1, 1, 2)^T\n",
    "$$\n",
    "$$\n",
    "\\theta = (3, -1, 1)^T\n",
    "$$\n",
    "\n",
    "Next system state $x_{1}$:\n",
    "$$\n",
    "\\mathbf{x}_1 = \\begin{bmatrix} x_{0,1}^2 + x_{0,2} \\\\ -x_{0,1} + \\frac{x_{0,2}}{2} \\\\ -x_{0,2}^2 + x_{0,3} \\end{bmatrix} + \\begin{bmatrix} x_{0,1}\\theta_1 \\\\ x_{0,2}\\theta_2 \\\\ x_{0,3}\\theta_3 \\end{bmatrix} = \\begin{bmatrix} (-1)^2 + 1 + (-1)\\cdot3 \\\\ -(-1)  + 0.5 + 1\\cdot(-1) = \\\\ -(1)^2 + 2 + 2 \\cdot 1 \\end{bmatrix} = \\begin{bmatrix} -1 \\\\ 0.5 \\\\ 3\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Next system state $x_{2}$:\n",
    "$$\n",
    "\\mathbf{x}_2 = \\begin{bmatrix} x_{1,1}^2 + x_{1,2} \\\\ -x_{1,1} + \\frac{x_{1,2}}{2} \\\\ -x_{1,2}^2 + x_{1,3} \\end{bmatrix} + \\begin{bmatrix} x_{1,1}\\theta_1 \\\\ x_{1,2}\\theta_2 \\\\ x_{1,3}\\theta_3 \\end{bmatrix} = \\begin{bmatrix} (-1)^2 + 0.5 + (-1)\\cdot3 \\\\ -(-1)  + 0.25 + 0.5\\cdot(-1) = \\\\ -(0.5)^2 + 3 + 3 \\cdot 1 \\end{bmatrix} = \\begin{bmatrix} -1.5 \\\\ 0.75 \\\\ 5.75\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Loss function L:\n",
    "$$\n",
    "L = \\|\\mathbf{x}_2\\|_1 = |x_{2,1}| + |x_{2,2}| + |x_{2,3}| = |-1.5| + |0.75| + |5.75| = -1.5 + 0.75 + 5.75 = 8\n",
    "$$\n",
    "\n",
    "Back-propagation gradient \n",
    "$$\n",
    "\\frac{\\partial L}{\\partial \\theta} = \\frac{\\partial L}{\\partial \\theta}^{(1)} + \\frac{\\partial L}{\\partial \\theta}^{(2)} = (\\frac{\\partial L}{\\partial \\mathbf{x}_2} \\cdot \\frac{\\partial \\mathbf{x}_2}{\\partial \\mathbf{x}_1} \\cdot \\frac{\\partial \\mathbf{x}_1}{\\partial \\mathbf{\\theta}}) + (\\frac{\\partial L}{\\partial \\mathbf{x}_2} \\cdot \\frac{\\partial \\mathbf{x}_2}{\\partial \\mathbf{\\theta}})\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial \\mathbf{x}_2} = \\begin{bmatrix} \\frac{\\partial L}{\\partial x_{2,1}} \\\\ \\frac{\\partial L}{\\partial x_{2,2}} \\\\ \\frac{\\partial L}{\\partial x_{2,3}} \\end{bmatrix} = \\begin{bmatrix} -1 \\\\ 1 \\\\ 1 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial x_2}{\\partial x_1} = \\begin{bmatrix} \\frac{\\partial x_{2,1}}{\\partial x_{1,1}} & \\frac{\\partial x_{2,1}}{\\partial x_{1,2}} & \\frac{\\partial x_{2,1}}{\\partial x_{1,3}} \\\\ \\frac{\\partial x_{2,2}}{\\partial x_{1,1}} & \\frac{\\partial x_{2,2}}{\\partial x_{1,2}} & \\frac{\\partial x_{2,2}}{\\partial x_{1,3}} \\\\ \\frac{\\partial x_{2,3}}{\\partial x_{1,1}} & \\frac{\\partial x_{2,3}}{\\partial x_{1,2}} & \\frac{\\partial x_{2,3}}{\\partial x_{1,3}} \\end{bmatrix} = \\begin{bmatrix} 2x_{1,1} + \\theta_{1} & 1 & 0 \\\\ -1 & 0.5 + \\theta_{2} & 0 \\\\ 0 & -2x_{1,2} & 1 + \\theta_{3} \\end{bmatrix} = \\begin{bmatrix} 1 & 1 & 0 \\\\ -1 & -0.5 & 0 \\\\ 0 & -1 & 2 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial \\mathbf{x}_1}{\\partial \\boldsymbol{\\theta}} = \\begin{bmatrix} \\frac{\\partial x_{1,1}}{\\partial \\theta_1} & \\frac{\\partial x_{1,2}}{\\partial \\theta_1} & \\frac{\\partial x_{1,3}}{\\partial \\theta_1} \\\\ \\frac{\\partial x_{1,1}}{\\partial \\theta_2} & \\frac{\\partial x_{1,2}}{\\partial \\theta_2} & \\frac{\\partial x_{1,3}}{\\partial \\theta_2} \\\\ \\frac{\\partial x_{1,1}}{\\partial \\theta_3} & \\frac{\\partial x_{1,2}}{\\partial \\theta_3} & \\frac{\\partial x_{1,3}}{\\partial \\theta_3} \\end{bmatrix} = \\begin{bmatrix} x_{0,1} & 0 & 0 \\\\ 0 & x_{0,2} & 0 \\\\ 0 & 0 & x_{0,3} \\end{bmatrix} = \\begin{bmatrix} -1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 0 & 2 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial \\mathbf{x}_2}{\\partial \\boldsymbol{\\theta}} = \\begin{bmatrix} \\frac{\\partial x_{2,1}}{\\partial \\theta_1} & \\frac{\\partial x_{2,2}}{\\partial \\theta_1} & \\frac{\\partial x_{2,3}}{\\partial \\theta_1} \\\\ \\frac{\\partial x_{2,1}}{\\partial \\theta_2} & \\frac{\\partial x_{2,2}}{\\partial \\theta_2} & \\frac{\\partial x_{2,3}}{\\partial \\theta_2} \\\\ \\frac{\\partial x_{2,1}}{\\partial \\theta_3} & \\frac{\\partial x_{2,2}}{\\partial \\theta_3} & \\frac{\\partial x_{2,3}}{\\partial \\theta_3} \\end{bmatrix} = \\begin{bmatrix} x_{1,1} & 0 & 0 \\\\ 0 & x_{1,2} & 0 \\\\ 0 & 0 & x_{1,3} \\end{bmatrix} = \\begin{bmatrix} -1 & 0 & 0 \\\\ 0 & 0.5 & 0 \\\\ 0 & 0 & 3 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial \\theta}^{(1)} = \\frac{\\partial L}{\\partial \\mathbf{x}_2} \\cdot \\frac{\\partial \\mathbf{x}_2}{\\partial \\mathbf{x}_1} \\cdot \\frac{\\partial \\mathbf{x}_1}{\\partial \\mathbf{\\theta}} = \\begin{bmatrix} -1 & 1 & 1 \\end{bmatrix} \\cdot \\begin{bmatrix} 1 & 1 & 0 \\\\ -1 & -0.5 & 0 \\\\ 0 & -1 & 2 \\end{bmatrix} \\cdot \\begin{bmatrix} -1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 0 & 2 \\end{bmatrix} = \\begin{bmatrix} 2 \\\\ -2.5 \\\\ 4 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial \\theta}^{(2)} = \\frac{\\partial L}{\\partial \\mathbf{x}_2} \\cdot \\frac{\\partial \\mathbf{x}_2}{\\partial \\mathbf{\\theta}} = \\begin{bmatrix} -1 & 1 & 1 \\end{bmatrix} \\cdot \\begin{bmatrix} -1 & 0 & 0 \\\\ 0 & 0.5 & 0 \\\\ 0 & 0 & 3 \\end{bmatrix} = \\begin{bmatrix} 1 \\\\ 0.5 \\\\ 3 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L}{\\partial \\theta} = \\begin{bmatrix} 2 \\\\ -2.5 \\\\ 4 \\end{bmatrix} + \\begin{bmatrix} 1 \\\\ 0.5 \\\\ 3 \\end{bmatrix} = \\begin{bmatrix} 3 \\\\ -2 \\\\ 7 \\end{bmatrix}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6d1c493-0d8d-484b-a8e7-389155b86c9e",
   "metadata": {},
   "source": [
    "### (3) Forward Propagation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21a218c2-a6f5-48f1-9fc8-48376cd7a75c",
   "metadata": {},
   "source": [
    "Forward propagation traverses the chain rule from inside to outside (input to output), while Backward differentiation traverses from outside to inside (output to input). Forward propagation is more efficient when $n<<m$ (input dimension much smaller than output), while backward propagation when $n>>m$, which is the case of interest in the context of Deep Learning (big dataset as input)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}