W3_Objective Function.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Name: Chaeyoon Kim\n",
    "#City Email: Chaeyoon.Kim@city.ac.uk\n",
    "\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Derive the the gradient of the objective function with respect to the slope,  𝑚 . Rearrange it to show that the update equation written above does find the stationary points of the objective function. By computing its derivative show that it's a minimum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Derive the the gradient of the objective function with respect to the slope, $m$**\n",
    "\n",
    "\n",
    "\\begin{align*}\n",
    "  E(m, c) = \\sum_{i=1}^n (y_i-mx_i-c)^2\\\\\n",
    "  \\frac{\\text{d}}{\\text{d}m}E(m, c) = -2\\sum_{i=1}^n x_i (y_i - mx_i - c) \n",
    "\\end{align*}\n",
    "\n",
    "\n",
    "\n",
    "**Rearrange it to show that the update equation written above does find the stationary points of the objective function.**\n",
    "\n",
    "\n",
    "\\begin{align*}\n",
    "  0 = -2\\sum_{i=1}^n x_i (y_i - mx_i - c) \\\\\n",
    "  0 = 2m\\sum_{i=1}^n x^2_i -2 \\sum_{i=1}^n x_i(y_i - c) \\\\\n",
    "  2 \\sum_{i=1}^n x_i(y_i - c)  = 2m\\sum_{i=1}^n x^2_i\\\\\n",
    "  m = \\frac{\\sum_{i=1}^n x_i(y_i - c)}{\\sum_{i=1}^n x^2_i}\\\\\n",
    "  m = \\frac{\\sum_{i=1}^n (y_i - c)x_i}{\\sum_{i=1}^n x^2_i}\n",
    "\\end{align*}\n",
    "\n",
    "\n",
    "                       \n",
    "                       \n",
    "                       \n",
    "**By computing the second derivative show that its a minimum.**\n",
    "\n",
    "\\begin{align*}\n",
    "  \\frac{\\text{d}}{\\text{d}m}E(m, c) = -2\\sum_{i=1}^n x_i (y_i - mx_i - c) \\\\\n",
    "  \\frac{\\text{d}}{\\text{d}m}E(m, c) = 2m\\sum_{i=1}^n x^2_i -2 \\sum_{i=1}^n x_i(y_i - c) \\\\\n",
    "  \\frac{\\text{d}^2}{\\text{d}m^2}E(m, c) = 2\\sum_{i=1}^n x^2_i \n",
    "\\end{align*}\n",
    "\n",
    "\n",
    "which is positive because $x^2_i$ is positive. This indicates that the solution is a minimum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Multiple Input Solution with Linear Algebra\n",
    "\n",
    "$$\n",
    "f(x) = mx + c\n",
    "$$\n",
    "\n",
    "\n",
    "I now have to turn the multiplications and additions into a linear algebraic form, we have one multiplication ($m\\times c$) and one addition ($mx + c$). But I can turn this into a inner product by writing it in the following way,\n",
    "$$\n",
    "f(x) = m \\times x + c \\times 1,\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\mathbf{x} = \\begin{bmatrix} 1\\\\ x\\end{bmatrix}.\n",
    "$$\n",
    "$$\n",
    "\\mathbf{w} = \\begin{bmatrix} c \\\\ m\\end{bmatrix}\n",
    "$$\n",
    "because if we now take the inner product between these to vectors we recover\n",
    "$$\n",
    "\\mathbf{x}\\cdot\\mathbf{w} = 1 \\times c + x \\times m = mx + c\n",
    "$$\n",
    "In `numpy` we can define this vector as follows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = ((y - c)*x).sum()/(x**2).sum()\n",
    "\n",
    "# define the vector w\n",
    "w = np.zeros(shape=(2, 1))\n",
    "w[0] = m\n",
    "w[1] = c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The result of this multiplication is of the form\n",
    "$$\n",
    "\\begin{bmatrix}c_1\\\\c_2 \\\\ \\vdots \\\\ a_k\\end{bmatrix} = \n",
    "\\begin{bmatrix} b_{1,1} & b_{1, 2} & \\dots & b_{1, k} \\\\\n",
    "b_{2, 1} & b_{2, 2} & \\dots & b_{2, k} \\\\\n",
    "\\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "b_{k, 1} & b_{k, 2} & \\dots & b_{k, k} \\end{bmatrix} \\begin{bmatrix}a_1\\\\a_2 \\\\ \\vdots\\\\ c_k\\end{bmatrix} = \\begin{bmatrix} b_{1, 1}a_1 + b_{1, 2}a_2 + \\dots + b_{1, k}a_k\\\\\n",
    "b_{2, 1}a_1 + b_{2, 2}a_2 + \\dots + b_{2, k}a_k \\\\ \n",
    "\\vdots\\\\ \n",
    "b_{k, 1}a_1 + b_{k, 2}a_2 + \\dots + b_{k, k}a_k\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Differentiating the Objective\n",
    "**So the full gradient**\n",
    "\n",
    "$$\n",
    "\\frac{\\text{d}E(\\mathbf{w})}{\\text{d}\\mathbf{w}}=\\begin{bmatrix}\\frac{\\text{d}E(m,c)}{\\text{d}m} \\\\ \\frac{\\text{d}E(m,c)}{\\text{d}c}\\end{bmatrix}=-2\\begin{bmatrix}\n",
    "\\mathbf{x}^\\top\\mathbf{y} \\\\ \\mathbf{1}^\\top \\mathbf{y}\n",
    "\\end{bmatrix}+2\\begin{bmatrix}\n",
    "\\mathbf{x}^\\top\\mathbf{x}m + \\mathbf{x}^\\top\\mathbf{1}c \\\\\n",
    "\\mathbf{x}^\\top\\mathbf{1}m + nc\n",
    "\\end{bmatrix}=  \n",
    "\\begin{bmatrix}-2\\sum_{i=1}^n x_i (y_i-mx_i - c)\\\\\n",
    "-2\\sum_{i=1}^n(y_i - mx_i -c)\n",
    "\\end{bmatrix}.\n",
    "$$"
   ]
  }
 ],
 "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}