《线性代数及其应用》笔记19.最小二乘法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 最小二乘法\n",
    "$\\quad$最小二乘法是在工程问题中非常常用的一个算法，用于预测、拟合函数曲线。在本节中我们会从线性代数的角度去介绍最小二乘问题与如何得到最小二乘解，接着推广到实际应用中，最后会补充别的教材里的最小二乘法的不同。  \n",
    "## 1最小二乘问题\n",
    "$\\quad$在实际问题中，解方程$A\\mathbf{x}=\\mathbf{b}$很多时候都是不相容问题，方程组的解不存在但又需要求解时，最好的方法是寻找$\\mathbf{x}$，使得$A\\mathbf{x}$尽可能接近$\\mathbf{b}$。要使$A\\mathbf{x}$尽可能地接近$\\mathbf{b}$，即两者之间的距离$\\Vert\\mathbf{b}-A\\mathbf{x}\\Vert$越小越好。这也是就是术语“最小二乘”的由来，即$\\Vert\\mathbf{b}-A\\mathbf{x}\\Vert$是平方和的平方根。  \n",
    "$\\quad$**定义**：如果$m\\times n$矩阵$A$和向量$\\mathbf{b}$属于$\\Bbb{R}^{m}$，则$A\\mathbf{x}=\\mathbf{b}$的最小二乘解是$\\Bbb{R}^{n}$中的$\\hat{\\mathbf{x}}$，使得$\\Vert\\mathbf{b}-A\\hat{\\mathbf{x}}\\Vert\\lt\\Vert\\mathbf{b}-A\\mathbf{x}\\Vert$对所有$\\mathbf{x}\\in\\Bbb{R}^{n}$成立。  \n",
    "$\\quad$在最小二乘问题中，$\\mathbf{b}$不在$A$的列空间中(因为方程无解)，而$A\\mathbf{x}$又必然在$A$的列空间中，因此寻求的最小二乘解是使得$A\\mathbf{x}$为$ColA$中最接近$\\mathbf{b}$的点。因此$\\Vert\\mathbf{b}-A\\mathbf{x}\\Vert$的本质是系数矩阵$A$所张成的向量空间$ColA$到观测向量$\\mathbf{b}$的误差。  \n",
    "\n",
    "<img src=\"./_image/19_1.png\" width=\"300\" height=\"250\" />  \n",
    "\n",
    "## 2.法方程求解\n",
    "$\\quad$设$A$是$m\\times n$矩阵，下面的条件是逻辑等价的：  \n",
    "1. 对于$\\Bbb{R}^{m}$中的每个$\\mathbf{b}$，方程$A\\mathbf{x}=\\mathbf{b}$有唯一最小二乘解；\n",
    "2. $A$的列是线性无关的；\n",
    "3. 矩阵$A^{T}A$是可逆的。\n",
    "\n",
    "当这些条件成立，最小二乘解$\\hat{\\mathbf{x}}$有下面表示：\n",
    "\n",
    "$$\\hat{\\mathbf{x}}=(A^{T}A)^{-1}A^{T}\\mathbf{b}$$\n",
    "\n",
    "从正交性可很容易地推导（借助求导也可），过程如下：\n",
    "\n",
    "<img src=\"./_image/19_2.png\" width=\"450\" height=\"400\" />  \n",
    "\n",
    "## 3.QR分解求解\n",
    "$\\quad$在某些时候，最小二乘问题的法方程可能是病态的，$A^{T}A$的元素在计算过程中出现的小误差有时会导致解出现大误差，但是如果$A$的列线性无关，则可借助[$QR$分解](《线性代数及其应用》笔记17.矩阵分解-QR分解.ipynb)来更可靠地解出。  \n",
    "$\\quad$**定理**：给定一个$m\\times n$矩阵$A$，它具有线性无关的列，对$A$做$QR$分解有$A=QR$，那么每一个属于$R^{m}$中的$\\mathbf{b}$有唯一最小二乘解，其解为：\n",
    "\n",
    "$$\\hat{\\mathbf{x}}=R^{-1}Q^{T}\\mathbf{b}$$\n",
    "\n",
    "证明如下：\n",
    "\n",
    "<img src=\"./_image/19_3.png\" width=\"450\" height=\"400\" />  \n",
    "\n",
    "因为$R$是一个上三角矩阵，因此以回代过程或行变换解方程$R\\mathbf{x}=Q^{T}\\mathbf{b}$比计算$R^{-1}$更快。\n",
    "## 4.最小二乘法的实际应用\n",
    "$\\quad$科学和工程中的一项任务是分析或理解几个变化量之间的联系。通常我们需要根据一些数据，去构造或验证一个公式，该公式可预测一个变量作为其他变量的函数。  \n",
    "$\\quad$和前面所讲的不同，我们改变一下$A\\mathbf{x}=\\mathbf{b}$的记法，改为$X\\mathbf{\\beta}=\\mathbf{y}$。这样改是有道理的，以往的线性方程组是已知方程组的系数$A$与$\\mathbf{b}$，要求能满足该矩阵方程的$\\mathbf{x}$，是一种已知函数图像求点的坐标的方程。但是在最小二乘问题则相反，我们是有一批观测数据，想求能“尽量”接近这些观测点的图像的系数，是已知点的坐标求函数图像的方程，未知的是系数，因此改写成$X\\mathbf{\\beta}=\\mathbf{y}$，其中称$X$为**设计矩阵**，$\\mathbf{\\beta}$为**参数向量**，$\\mathbf{y}$为**观测向量**。  \n",
    "$\\quad$两式$A\\mathbf{x}=\\mathbf{b}$和$X\\mathbf{\\beta}=\\mathbf{y}$只是记法不同，最小二乘解同样可以应用在$X\\mathbf{\\beta}=\\mathbf{y}$上。  \n",
    "### 4.1最小二乘直线\n",
    "$\\quad$变量$x$和$y$之间最简单的关系是线性方程$y=\\beta_{0}+\\beta_{1}x$。实验数据常给出观测点$(x_1,y_1),\\cdots,(x_n,y_n)$，它们的图形接近于直线，我们希望确定参数$\\beta_{0},\\beta_{1}$使得直线能靠近这些观测点。  \n",
    "$\\quad$假设$\\beta_{0},\\beta_{1}$固定，考虑下图中的直线$y=\\beta_{0}+\\beta_{1}x$，对应于每一个数据点$(x_j,y_j)$，有一个在直线上的点$(x_j,\\beta_{0}+\\beta_{1}x_j)$，我们称$y_j$为$y$的**观测值**，而$\\beta_{0}+\\beta_{1}x_j$为$y$的**预测值**（由直线确定），$y_j$与$\\beta_{0}+\\beta_{1}x_j$之间的差称为**余差**。\n",
    "\n",
    "<img src=\"./_image/19_4.png\" width=\"350\" height=\"300\" />  \n",
    "\n",
    "$\\quad$一般选取余差平方之和（$\\Vert\\mathbf{y}-X\\mathbf{\\beta}\\Vert$）来作为度量直线与数据的接近程度，最小二乘直线$y=\\beta_{0}+\\beta_{1}x$是是余差平方和最小的，这条直线也称为$y$对$x$的**回归直线**（假设数据中的任何误差只出现在$y$坐标），系数$\\beta_{0},\\beta_{1}$被称为**回归系数**。  \n",
    "\n",
    "<img src=\"./_image/19_5.png\" width=\"150\" height=\"100\" />  \n",
    "\n",
    "写成矩阵方程的形式有：\n",
    "\n",
    "<img src=\"./_image/19_6.png\" width=\"350\" height=\"300\" />  \n",
    "\n",
    "举例：\n",
    "\n",
    "<img src=\"./_image/19_7.png\" width=\"350\" height=\"300\" />  \n",
    "### 4.2其他类型的最小二乘直线\n",
    "$\\quad$在很多应用下，必须将数据点拟合为非直线形式。统计学家引入余差向量$\\mathbf{\\epsilon}$（为了使等式成立），记作：\n",
    "\n",
    "$$\\mathbf{y}=X\\mathbf{\\beta}+\\mathbf{\\epsilon}$$\n",
    "\n",
    "任何具有这种形式的方程称为线性模型，最小二乘解$\\mathbf{\\beta}$是下面法方程的解:\n",
    "\n",
    "$$X^{T}X\\mathbf{\\beta}=X^{T}\\mathbf{y}$$\n",
    "\n",
    "#### 4.2.1单一变量\n",
    "$\\quad$当我们可视化数据点$(x_1,y_1 ),\\cdots,(x_n,y_n)$，发现散落的形状不接近任何直线时，我们认为$\\mathbf{x}$和$\\mathbf{y}$具有其他函数关系。可以将数据拟合为更具一般形式的曲线：  \n",
    "\n",
    "<img src=\"./_image/19_8.png\" width=\"200\" height=\"150\" />  \n",
    "\n",
    "其中$f_0,…,f_k$是已知函数，$\\beta_{0},\\cdots,\\beta_{k}$是待定参数，该方程描述一个线性模型，因为它是对于未知参数的线性模型。  \n",
    "$\\quad$例如：\n",
    "\n",
    "<img src=\"./_image/19_9.png\" width=\"400\" height=\"350\" />  \n",
    "\n",
    "#### 4.2.2多个变量\n",
    "$\\quad$假如一个实验包含两个独立变量$u,v$和一个相关变量$y$，一般地，一个线性模型是指$y$可由下面的方程来预测:\n",
    "\n",
    "$$y=\\beta_{0}f_{0}(u,v)+\\cdots+\\beta_{k}f_{k}(u,v)$$\n",
    "\n",
    "其中$f_0,\\cdots,f_k$是已知函数，$\\beta_{0},\\cdots,\\beta_{k}$是未知权。例如：\n",
    "\n",
    "<img src=\"./_image/19_10.png\" width=\"400\" height=\"350\" />  \n",
    "## 5.关于$y=\\beta_{0}+\\beta_{1}x$的计算\n",
    "$\\quad$在各个机器学习教材介绍线性回归或最小二乘法时，都会以$y=\\beta_{0}+\\beta_{1}x$为例子，但是他们通常都是推导出$\\beta_{0},\\beta_{1}$的一个式子，和《线性代数及其应用》切入的角度不同，所以这里单独研究研究$y=\\beta_{0}+\\beta_{1}x$中的回归系数求解通式。    \n",
    "$\\quad$给定下面几个缩写符号：\n",
    "\n",
    "<img src=\"./_image/19_11.png\" width=\"250\" height=\"200\" />  \n",
    "\n",
    "### 5.1法方程推导\n",
    "<img src=\"./_image/19_12.png\" width=\"450\" height=\"400\" />  \n",
    "<img src=\"./_image/19_13.png\" width=\"450\" height=\"400\" />  \n",
    "### 5.2求导推导\n",
    "<img src=\"./_image/19_14.png\" width=\"500\" height=\"450\" />  \n",
    "<img src=\"./_image/19_15.png\" width=\"450\" height=\"400\" />  \n",
    "$\\quad$可以看出，两个推导出发点是不同的。法方程通过线性代数的角度可以很简单的得到；求导推导是通过对所求参数求偏导，也可以得到法方程的形式，但是不太好观察得到，而且求导的过程并不是那么好计算。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}