linear_regression_project_en.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1 Matrix operations\n",
    "\n",
    "## 1.1 Create a 4*4 identity matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#This project is designed to get familiar with python list and linear algebra\n",
    "#You cannot use import any library yourself, especially numpy\n",
    "\n",
    "A = [[1,2,3], \n",
    "     [2,3,3], \n",
    "     [1,2,5]]\n",
    "\n",
    "B = [[1,2,3,5], \n",
    "     [2,3,3,5], \n",
    "     [1,2,5,1]]\n",
    "\n",
    "#TODO create a 4*4 identity matrix \n",
    "I = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 get the width and height of a matrix. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#TODO Get the height and weight of a matrix.\n",
    "def shape(M):\n",
    "    return 0,0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run following code to test your shape function\n",
    "%run -i -e test.py LinearRegressionTestCase.test_shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3 round all elements in M to certain decimal points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO in-place operation, no return value\n",
    "# TODO round all elements in M to decPts\n",
    "def matxRound(M, decPts=4):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run following code to test your matxRound function\n",
    "%run -i -e test.py LinearRegressionTestCase.test_matxRound"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.4 compute transpose of M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#TODO compute transpose of M\n",
    "def transpose(M):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run following code to test your transpose function\n",
    "%run -i -e test.py LinearRegressionTestCase.test_transpose"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.5 compute AB. return None if the dimensions don't match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#TODO compute matrix multiplication AB, return None if the dimensions don't match\n",
    "def matxMultiply(A, B):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run following code to test your matxMultiply function\n",
    "%run -i -e test.py LinearRegressionTestCase.test_matxMultiply"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "# 2 Gaussian Jordan Elimination\n",
    "\n",
    "## 2.1 Compute augmented Matrix \n",
    "\n",
    "$ A = \\begin{bmatrix}\n",
    "    a_{11}    & a_{12} & ... & a_{1n}\\\\\n",
    "    a_{21}    & a_{22} & ... & a_{2n}\\\\\n",
    "    a_{31}    & a_{22} & ... & a_{3n}\\\\\n",
    "    ...    & ... & ... & ...\\\\\n",
    "    a_{n1}    & a_{n2} & ... & a_{nn}\\\\\n",
    "\\end{bmatrix} , b = \\begin{bmatrix}\n",
    "    b_{1}  \\\\\n",
    "    b_{2}  \\\\\n",
    "    b_{3}  \\\\\n",
    "    ...    \\\\\n",
    "    b_{n}  \\\\\n",
    "\\end{bmatrix}$\n",
    "\n",
    "Return $ Ab = \\begin{bmatrix}\n",
    "    a_{11}    & a_{12} & ... & a_{1n} & b_{1}\\\\\n",
    "    a_{21}    & a_{22} & ... & a_{2n} & b_{2}\\\\\n",
    "    a_{31}    & a_{22} & ... & a_{3n} & b_{3}\\\\\n",
    "    ...    & ... & ... & ...& ...\\\\\n",
    "    a_{n1}    & a_{n2} & ... & a_{nn} & b_{n} \\end{bmatrix}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#TODO construct the augment matrix of matrix A and column vector b, assuming A and b have same number of rows\n",
    "def augmentMatrix(A, b):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run following code to test your augmentMatrix function\n",
    "%run -i -e test.py LinearRegressionTestCase.test_augmentMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2 Basic row operations\n",
    "- exchange two rows\n",
    "- scale a row\n",
    "- add a scaled row to another"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO r1 <---> r2\n",
    "# TODO in-place operation, no return value\n",
    "def swapRows(M, r1, r2):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run following code to test your swapRows function\n",
    "%run -i -e test.py LinearRegressionTestCase.test_swapRows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO r1 <--- r1 * scale\n",
    "# TODO in-place operation, no return value\n",
    "def scaleRow(M, r, scale):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run following code to test your scaleRow function\n",
    "%run -i -e test.py LinearRegressionTestCase.test_scaleRow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO r1 <--- r1 + r2*scale\n",
    "# TODO in-place operation, no return value\n",
    "def addScaledRow(M, r1, r2, scale):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run following code to test your addScaledRow function\n",
    "%run -i -e test.py LinearRegressionTestCase.test_addScaledRow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3  Gauss-jordan method to solve Ax = b\n",
    "\n",
    "### Hint：\n",
    "\n",
    "Step 1: Check if A and b have same number of rows\n",
    "Step 2: Construct augmented matrix Ab\n",
    "\n",
    "Step 3: Column by column, transform Ab to reduced row echelon form [wiki link](https://en.wikipedia.org/wiki/Row_echelon_form#Reduced_row_echelon_form)\n",
    "    \n",
    "    for every column of Ab (except the last one)\n",
    "        column c is the current column\n",
    "        Find in column c, at diagonal and under diagonal (row c ~ N) the maximum absolute value\n",
    "        If the maximum absolute value is 0\n",
    "            then A is singular, return None （Prove this proposition in Question 2.4）\n",
    "        else\n",
    "            Apply row operation 1, swap the row of maximum with the row of diagonal element (row c)\n",
    "            Apply row operation 2, scale the diagonal element of column c to 1\n",
    "            Apply row operation 3 mutiple time, eliminate every other element in column c\n",
    "            \n",
    "Step 4: return the last column of Ab\n",
    "\n",
    "### Remark：\n",
    "We don't use the standard algorithm first transfering Ab to row echelon form and then to reduced row echelon form.  Instead, we arrives directly at reduced row echelon form. If you are familiar with the stardard way, try prove to yourself that they are equivalent. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#TODO implement gaussian jordan method to solve Ax = b\n",
    "\n",
    "\"\"\" Gauss-jordan method to solve x such that Ax = b.\n",
    "        A: square matrix, list of lists\n",
    "        b: column vector, list of lists\n",
    "        decPts: degree of rounding, default value 4\n",
    "        epsilon: threshold for zero, default value 1.0e-16\n",
    "        \n",
    "    return x such that Ax = b, list of lists \n",
    "    return None if A and b have same height\n",
    "    return None if A is (almost) singular\n",
    "\"\"\"\n",
    "\n",
    "def gj_Solve(A, b, decPts=4, epsilon = 1.0e-16):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# run following code to test your addScaledRow function\n",
    "%run -i -e test.py LinearRegressionTestCase.test_gj_Solve"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.4 Prove the following proposition:\n",
    "\n",
    "**If square matrix A can be divided into four parts: ** \n",
    "\n",
    "$ A = \\begin{bmatrix}\n",
    "    I    & X \\\\\n",
    "    Z    & Y \\\\\n",
    "\\end{bmatrix} $, where I is the identity matrix, Z is all zero and the first column of Y is all zero, \n",
    "\n",
    "**then A is singular.**\n",
    "\n",
    "Hint: There are mutiple ways to prove this problem.  \n",
    "- consider the rank of Y and A\n",
    "- consider the determinate of Y and A \n",
    "- consider certain column is the linear combination of other columns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO Please use latex （refering to the latex in problem may help）\n",
    "\n",
    "TODO Proof："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "# 3 Linear Regression: \n",
    "\n",
    "## 3.1 Compute the gradient of loss function with respect to parameters \n",
    "## (Choose one between two 3.1 questions)\n",
    "\n",
    "We define loss funtion $E$ as \n",
    "$$\n",
    "E(m, b) = \\sum_{i=1}^{n}{(y_i - mx_i - b)^2}\n",
    "$$\n",
    "and we define vertex $Y$, matrix $X$ and vertex $h$ :\n",
    "$$\n",
    "Y =  \\begin{bmatrix}\n",
    "    y_1 \\\\\n",
    "    y_2 \\\\\n",
    "    ... \\\\\n",
    "    y_n\n",
    "\\end{bmatrix}\n",
    ",\n",
    "X =  \\begin{bmatrix}\n",
    "    x_1 & 1 \\\\\n",
    "    x_2 & 1\\\\\n",
    "    ... & ...\\\\\n",
    "    x_n & 1 \\\\\n",
    "\\end{bmatrix},\n",
    "h =  \\begin{bmatrix}\n",
    "    m \\\\\n",
    "    b \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "\n",
    "Proves that \n",
    "$$\n",
    "\\frac{\\partial E}{\\partial m} = \\sum_{i=1}^{n}{-2x_i(y_i - mx_i - b)}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E}{\\partial b} = \\sum_{i=1}^{n}{-2(y_i - mx_i - b)}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "    \\frac{\\partial E}{\\partial m} \\\\\n",
    "    \\frac{\\partial E}{\\partial b} \n",
    "\\end{bmatrix} = 2X^TXh - 2X^TY\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO Please use latex （refering to the latex in problem may help）\n",
    "\n",
    "TODO Proof："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.1 Compute the gradient of loss function with respect to parameters \n",
    "## (Choose one between two 3.1 questions)\n",
    "We define loss funtion $E$ as \n",
    "$$\n",
    "E(m, b) = \\sum_{i=1}^{n}{(y_i - mx_i - b)^2}\n",
    "$$\n",
    "and we define vertex $Y$, matrix $X$ and vertex $h$ :\n",
    "$$\n",
    "Y =  \\begin{bmatrix}\n",
    "    y_1 \\\\\n",
    "    y_2 \\\\\n",
    "    ... \\\\\n",
    "    y_n\n",
    "\\end{bmatrix}\n",
    ",\n",
    "X =  \\begin{bmatrix}\n",
    "    x_1 & 1 \\\\\n",
    "    x_2 & 1\\\\\n",
    "    ... & ...\\\\\n",
    "    x_n & 1 \\\\\n",
    "\\end{bmatrix},\n",
    "h =  \\begin{bmatrix}\n",
    "    m \\\\\n",
    "    b \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Proves that \n",
    "$$\n",
    "E = Y^TY -2(Xh)^TY + (Xh)^TXh\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E}{\\partial h} = 2X^TXh - 2X^TY\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO Please use latex （refering to the latex in problem may help）\n",
    "\n",
    "TODO Proof："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.2  Linear Regression\n",
    "### Solve equation $X^TXh = X^TY $ to compute the best parameter for linear regression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#TODO implement linear regression \n",
    "'''\n",
    "points: list of (x,y) tuple\n",
    "return m and b\n",
    "'''\n",
    "def linearRegression(points):\n",
    "    return 0,0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.3 Test your linear regression implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#TODO Construct the linear function\n",
    "\n",
    "#TODO Construct points with gaussian noise\n",
    "import random\n",
    "\n",
    "#TODO Compute m and b and compare with ground truth"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Raw Cell Format",
  "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}