linear_regression_project.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 欢迎来到线性回归项目\n",
    "\n",
    "若项目中的题目有困难没完成也没关系，我们鼓励你带着问题提交项目，评审人会给予你诸多帮助。\n",
    "\n",
    "所有选做题都可以不做，不影响项目通过。如果你做了，那么项目评审会帮你批改，也会因为选做部分做错而判定为不通过。\n",
    "\n",
    "其中非代码题可以提交手写后扫描的 pdf 文件，或使用 Latex 在文档中直接回答。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 目录:\n",
    "[1 矩阵运算](#1-矩阵运算)  \n",
    "[2 Gaussian Jordan 消元法](#2-Gaussian-Jordan-消元法)  \n",
    "[3  线性回归](#3-线性回归)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 任意选一个你喜欢的整数，这能帮你得到稳定的结果\n",
    "seed = # TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1 矩阵运算\n",
    "\n",
    "## 1.1 创建一个 4*4 的单位矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 这个项目设计来帮你熟悉 python list 和线性代数\n",
    "# 你不能调用任何NumPy以及相关的科学计算库来完成作业\n",
    "\n",
    "\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",
    "# 向量也用二维列表表示\n",
    "C = [[1],\n",
    "     [2],\n",
    "     [3]]\n",
    "\n",
    "#TODO 创建一个 4*4 单位矩阵\n",
    "I = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 返回矩阵的行数和列数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO 返回矩阵的行数和列数\n",
    "def shape(M):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 运行以下代码测试你的 shape 函数\n",
    "%run -i -e test.py LinearRegressionTestCase.test_shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3 每个元素四舍五入到特定小数数位"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO 每个元素四舍五入到特定小数数位\n",
    "# 直接修改参数矩阵，无返回值\n",
    "def matxRound(M, decPts=4):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 运行以下代码测试你的 matxRound 函数\n",
    "%run -i -e test.py LinearRegressionTestCase.test_matxRound"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.4 计算矩阵的转置"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO 计算矩阵的转置\n",
    "def transpose(M):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 运行以下代码测试你的 transpose 函数\n",
    "%run -i -e test.py LinearRegressionTestCase.test_transpose"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.5 计算矩阵乘法 AB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO 计算矩阵乘法 AB，如果无法相乘则raise ValueError\n",
    "def matxMultiply(A, B):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 运行以下代码测试你的 matxMultiply 函数\n",
    "%run -i -e test.py LinearRegressionTestCase.test_matxMultiply"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "# 2 Gaussian Jordan 消元法\n",
    "\n",
    "## 2.1 构造增广矩阵\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",
    "返回 $ 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 构造增广矩阵，假设A，b行数相同\n",
    "def augmentMatrix(A, b):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 运行以下代码测试你的 augmentMatrix 函数\n",
    "%run -i -e test.py LinearRegressionTestCase.test_augmentMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2 初等行变换\n",
    "- 交换两行\n",
    "- 把某行乘以一个非零常数\n",
    "- 把某行加上另一行的若干倍："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO r1 <---> r2\n",
    "# 直接修改参数矩阵，无返回值\n",
    "def swapRows(M, r1, r2):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 运行以下代码测试你的 swapRows 函数\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",
    "# scale为0是非法输入，要求 raise ValueError\n",
    "# 直接修改参数矩阵，无返回值\n",
    "def scaleRow(M, r, scale):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 运行以下代码测试你的 scaleRow 函数\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",
    "# 直接修改参数矩阵，无返回值\n",
    "def addScaledRow(M, r1, r2, scale):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 运行以下代码测试你的 addScaledRow 函数\n",
    "%run -i -e test.py LinearRegressionTestCase.test_addScaledRow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3  Gaussian Jordan 消元法求解 Ax = b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3.1 算法\n",
    "\n",
    "步骤1 检查A，b是否行数相同\n",
    "\n",
    "步骤2 构造增广矩阵Ab\n",
    "\n",
    "步骤3 逐列转换Ab为化简行阶梯形矩阵 [中文维基链接](https://zh.wikipedia.org/wiki/%E9%98%B6%E6%A2%AF%E5%BD%A2%E7%9F%A9%E9%98%B5#.E5.8C.96.E7.AE.80.E5.90.8E.E7.9A.84-.7Bzh-hans:.E8.A1.8C.3B_zh-hant:.E5.88.97.3B.7D-.E9.98.B6.E6.A2.AF.E5.BD.A2.E7.9F.A9.E9.98.B5)\n",
    "    \n",
    "    对于Ab的每一列（最后一列除外）\n",
    "        当前列为列c\n",
    "        寻找列c中 对角线以及对角线以下所有元素（行 c~N）的绝对值的最大值\n",
    "        如果绝对值最大值为0\n",
    "            那么A为奇异矩阵，返回None (你可以在选做问题2.4中证明为什么这里A一定是奇异矩阵)\n",
    "        否则\n",
    "            使用第一个行变换，将绝对值最大值所在行交换到对角线元素所在行（行c） \n",
    "            使用第二个行变换，将列c的对角线元素缩放为1\n",
    "            多次使用第三个行变换，将列c的其他元素消为0\n",
    "            \n",
    "步骤4 返回Ab的最后一列\n",
    "\n",
    "**注：** 我们并没有按照常规方法先把矩阵转化为行阶梯形矩阵，再转换为化简行阶梯形矩阵，而是一步到位。如果你熟悉常规方法的话，可以思考一下两者的等价性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3.2 算法推演\n",
    "\n",
    "为了充分了解Gaussian Jordan消元法的计算流程，请根据Gaussian Jordan消元法，分别手动推演矩阵A为***可逆矩阵***，矩阵A为***奇异矩阵***两种情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 推演示例 \n",
    "\n",
    "\n",
    "$Ab = \\begin{bmatrix}\n",
    "    -7 & 5 & -1 & 1\\\\\n",
    "    1 & -3 & -8 & 1\\\\\n",
    "    -10 & -2 & 9 & 1\\end{bmatrix}$\n",
    "\n",
    "$ --> $\n",
    "$\\begin{bmatrix}\n",
    "    1 & \\frac{1}{5} & -\\frac{9}{10} & -\\frac{1}{10}\\\\\n",
    "    0 & -\\frac{16}{5} & -\\frac{71}{10} & \\frac{11}{10}\\\\\n",
    "    0 & \\frac{32}{5} & -\\frac{73}{10} & \\frac{3}{10}\\end{bmatrix}$\n",
    "\n",
    "$ --> $\n",
    "$\\begin{bmatrix}\n",
    "    1 & 0 & -\\frac{43}{64} & -\\frac{7}{64}\\\\\n",
    "    0 & 1 & -\\frac{73}{64} & \\frac{3}{64}\\\\\n",
    "    0 & 0 & -\\frac{43}{4} & \\frac{5}{4}\\end{bmatrix}$\n",
    "\n",
    "$ --> $\n",
    "$\\begin{bmatrix}\n",
    "    1 & 0 & 0 & -\\frac{3}{16}\\\\\n",
    "    0 & 1 & 0 & -\\frac{59}{688}\\\\\n",
    "    0 & 0 & 1 & -\\frac{5}{43}\\end{bmatrix}$\n",
    "    \n",
    "\n",
    "#### 推演有以下要求:\n",
    "1. 展示每一列的消元结果, 比如3*3的矩阵, 需要写三步\n",
    "2. 用分数来表示\n",
    "3. 分数不能再约分\n",
    "4. 我们已经给出了latex的语法,你只要把零改成你要的数字(或分数)即可\n",
    "5. 可以用[这个页面](http://www.math.odu.edu/~bogacki/cgi-bin/lat.cgi?c=sys)检查你的答案(注意只是答案, 推演步骤两者算法不一致)\n",
    "\n",
    "_你可以用python的 [fractions](https://docs.python.org/2/library/fractions.html) 模块辅助你的约分_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 分数的输入方法\n",
    "(双击这个区域就能看到语法啦)  \n",
    "  \n",
    "示例一: $\\frac{n}{m}$  \n",
    "\n",
    "示例二: $-\\frac{a}{b}$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 以下开始你的尝试吧!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 不要修改这里！\n",
    "from helper import *\n",
    "A = generateMatrix(3,seed,singular=False)\n",
    "b = np.ones(shape=(3,1),dtype=int) # it doesn't matter\n",
    "Ab = augmentMatrix(A.tolist(),b.tolist()) # 请确保你的增广矩阵已经写好了\n",
    "printInMatrixFormat(Ab,padding=3,truncating=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "请按照算法的步骤3，逐步推演***可逆矩阵***的变换。\n",
    "\n",
    "在下面列出每一次循环体执行之后的增广矩阵(注意使用[分数语法](#分数的输入方法))\n",
    "\n",
    "$ Ab = \\begin{bmatrix}\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\end{bmatrix}$\n",
    "\n",
    "$ --> \\begin{bmatrix}\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\end{bmatrix}$\n",
    "    \n",
    "$ --> \\begin{bmatrix}\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\end{bmatrix}$\n",
    "    \n",
    "$...$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 不要修改这里！\n",
    "A = generateMatrix(3,seed,singular=True)\n",
    "b = np.ones(shape=(3,1),dtype=int)\n",
    "Ab = augmentMatrix(A.tolist(),b.tolist()) # 请确保你的增广矩阵已经写好了\n",
    "printInMatrixFormat(Ab,padding=3,truncating=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "请按照算法的步骤3，逐步推演***奇异矩阵***的变换。\n",
    "\n",
    "在下面列出每一次循环体执行之后的增广矩阵(注意使用[分数语法](#分数的输入方法))\n",
    "\n",
    "$ Ab = \\begin{bmatrix}\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\end{bmatrix}$\n",
    "\n",
    "$ --> \\begin{bmatrix}\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\end{bmatrix}$\n",
    "    \n",
    "$ --> \\begin{bmatrix}\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 \\end{bmatrix}$\n",
    "    \n",
    "$...$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3.3 实现 Gaussian Jordan 消元法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO 实现 Gaussain Jordan 方法求解 Ax = b\n",
    "\n",
    "\"\"\" Gaussian Jordan 方法求解 Ax = b.\n",
    "    参数\n",
    "        A: 方阵 \n",
    "        b: 列向量\n",
    "        decPts: 四舍五入位数，默认为4\n",
    "        epsilon: 判读是否为0的阈值，默认 1.0e-16\n",
    "        \n",
    "    返回列向量 x 使得 Ax = b \n",
    "    返回None，如果 A，b 高度不同\n",
    "    返回None，如果 A 为奇异矩阵\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": [
    "# 运行以下代码测试你的 gj_Solve 函数\n",
    "%run -i -e test.py LinearRegressionTestCase.test_gj_Solve"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (选做) 2.4 算法正确判断了奇异矩阵：\n",
    "\n",
    "在算法的步骤3 中，如果发现某一列对角线和对角线以下所有元素都为0，那么则断定这个矩阵为奇异矩阵。\n",
    "\n",
    "我们用正式的语言描述这个命题，并证明为真。\n",
    "\n",
    "证明下面的命题：\n",
    "\n",
    "**如果方阵 A 可以被分为4个部分: ** \n",
    "\n",
    "$ A = \\begin{bmatrix}\n",
    "    I    & X \\\\\n",
    "    Z    & Y \\\\\n",
    "\\end{bmatrix} , \\text{其中 I 为单位矩阵，Z 为全0矩阵，Y 的第一列全0}$，\n",
    "\n",
    "**那么A为奇异矩阵。**\n",
    "\n",
    "提示：从多种角度都可以完成证明\n",
    "- 考虑矩阵 Y 和 矩阵 A 的秩\n",
    "- 考虑矩阵 Y 和 矩阵 A 的行列式\n",
    "- 考虑矩阵 A 的某一列是其他列的线性组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO 证明："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3 线性回归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.1 随机生成样本点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 不要修改这里！\n",
    "%matplotlib notebook\n",
    "from helper import *\n",
    "\n",
    "X,Y = generatePoints2D(seed)\n",
    "vs_scatter_2d(X, Y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.2 拟合一条直线\n",
    "\n",
    "### 3.2.1 猜测一条直线"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#TODO 请选择最适合的直线 y = mx + b\n",
    "m1 = 0.\n",
    "b1 = 0.\n",
    "\n",
    "# 不要修改这里！\n",
    "vs_scatter_2d(X, Y, m1, b1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2.2 计算平均平方误差 (MSE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "我们要编程计算所选直线的平均平方误差(MSE), 即数据集中每个点到直线的Y方向距离的平方的平均数，表达式如下：\n",
    "$$\n",
    "MSE = \\frac{1}{n}\\sum_{i=1}^{n}{(y_i - mx_i - b)^2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO 实现以下函数并输出所选直线的MSE\n",
    "def calculateMSE2D(X,Y,m,b):\n",
    "    return 0.\n",
    "\n",
    "# TODO 检查这里的结果, 如果你上面猜测的直线准确, 这里的输出会在1.5以内\n",
    "print(calculateMSE2D(X,Y,m1,b1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2.3 调整参数 $m, b$ 来获得最小的平方平均误差\n",
    "\n",
    "你可以调整3.2.1中的参数 $m1,b1$ 让蓝点均匀覆盖在红线周围，然后微调 $m1, b1$ 让MSE最小。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.3 (选做) 找到参数 $m, b$ 使得平方平均误差最小\n",
    "\n",
    "**这一部分需要简单的微积分知识(  $ (x^2)' = 2x $ )。因为这是一个线性代数项目，所以设为选做。**\n",
    "\n",
    "刚刚我们手动调节参数，尝试找到最小的平方平均误差。下面我们要精确得求解 $m, b$ 使得平方平均误差最小。\n",
    "\n",
    "定义目标函数 $E$ 为\n",
    "$$\n",
    "E = \\frac{1}{2}\\sum_{i=1}^{n}{(y_i - mx_i - b)^2}\n",
    "$$\n",
    "\n",
    "因为 $E = \\frac{n}{2}MSE$, 所以 $E$ 取到最小值时，$MSE$ 也取到最小值。要找到 $E$ 的最小值，即要找到 $m, b$ 使得 $E$ 相对于 $m$, $E$ 相对于 $b$ 的偏导数等于0. \n",
    "\n",
    "因此我们要解下面的方程组。\n",
    "\n",
    "$$\n",
    "\\begin{cases}\n",
    "\\displaystyle\n",
    "\\frac{\\partial E}{\\partial m} =0 \\\\\n",
    "\\\\\n",
    "\\displaystyle\n",
    "\\frac{\\partial E}{\\partial b} =0 \\\\\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "### 3.3.1 计算目标函数相对于参数的导数\n",
    "首先我们计算两个式子左边的值\n",
    "\n",
    "证明/计算：\n",
    "$$\n",
    "\\frac{\\partial E}{\\partial m} = \\sum_{i=1}^{n}{-x_i(y_i - mx_i - b)}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial E}{\\partial b} = \\sum_{i=1}^{n}{-(y_i - mx_i - b)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO 证明:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3.2 实例推演\n",
    "\n",
    "现在我们有了一个二元二次方程组\n",
    "\n",
    "$$\n",
    "\\begin{cases}\n",
    "\\displaystyle\n",
    "\\sum_{i=1}^{n}{-x_i(y_i - mx_i - b)} =0 \\\\\n",
    "\\\\\n",
    "\\displaystyle\n",
    "\\sum_{i=1}^{n}{-(y_i - mx_i - b)} =0 \\\\\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "为了加强理解，我们用一个实际例子演练。\n",
    "\n",
    "我们要用三个点 $(1,1), (2,2), (3,2)$ 来拟合一条直线 y = m*x + b, 请写出\n",
    "\n",
    "- 目标函数 $E$, \n",
    "- 二元二次方程组，\n",
    "- 并求解最优参数 $m, b$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO 写出目标函数，方程组和最优参数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3.3 将方程组写成矩阵形式\n",
    "\n",
    "我们的二元二次方程组可以用更简洁的矩阵形式表达，将方程组写成矩阵形式更有利于我们使用 Gaussian Jordan 消元法求解。\n",
    "\n",
    "请证明 \n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "    \\frac{\\partial E}{\\partial m} \\\\\n",
    "    \\frac{\\partial E}{\\partial b} \n",
    "\\end{bmatrix} = X^TXh - X^TY\n",
    "$$\n",
    "\n",
    "其中向量 $Y$, 矩阵 $X$ 和 向量 $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",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO 证明:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "至此我们知道，通过求解方程 $X^TXh = X^TY$ 来找到最优参数。这个方程十分重要，他有一个名字叫做 **Normal Equation**，也有直观的几何意义。你可以在 [子空间投影](http://open.163.com/movie/2010/11/J/U/M6V0BQC4M_M6V2AJLJU.html) 和 [投影矩阵与最小二乘](http://open.163.com/movie/2010/11/P/U/M6V0BQC4M_M6V2AOJPU.html) 看到更多关于这个方程的内容。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 求解 $X^TXh = X^TY$ \n",
    "\n",
    "在3.3 中，我们知道线性回归问题等价于求解 $X^TXh = X^TY$ (如果你选择不做3.3，就勇敢的相信吧，哈哈)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO 实现线性回归\n",
    "'''\n",
    "参数：X, Y 存储着一一对应的横坐标与纵坐标的两个一维数组\n",
    "返回：线性回归的系数(如上面所说的 m, b)\n",
    "'''\n",
    "def linearRegression2D(X,Y):\n",
    "    return 0.,0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请不要修改下面的代码\n",
    "m2,b2 = linearRegression2D(X,Y)\n",
    "assert isinstance(m2,float),\"m is not a float\"\n",
    "assert isinstance(b2,float),\"b is not a float\"\n",
    "print(m2,b2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "你求得的回归结果是什么？\n",
    "请使用运行以下代码将它画出来。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "## 请不要修改下面的代码\n",
    "vs_scatter_2d(X, Y, m2, b2)\n",
    "print(calculateMSE2D(X,Y,m2,b2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bonus !!!\n",
    "如果你的高斯约当消元法通过了单元测试, 那么它将能够解决多维的回归问题  \n",
    "你将会在更高维度考验你的线性回归实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 生成三维的数据点\n",
    "X_3d, Y_3d = generatePoints3D(seed)\n",
    "vs_scatter_3d(X_3d, Y_3d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "你的线性回归是否能够对付三维的情况?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def linearRegression(X,Y):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "coeff = linearRegression(X_3d, Y_3d)\n",
    "vs_scatter_3d(X_3d, Y_3d, coeff)"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}