最小二乘法

最小二乘法
写在前面的话：由于在编程实践层面上更倾向于使⽤矩阵/向量而不是方程组的形式进⾏计算，因此包括最小二乘法(Least Square Method)在内的⼀系列优化⽅法和算法的理论讲解，我们也将采⽤矩阵/向量作为基本数据结构进行概念讲解和数学公式推导。在正式讲解LSM的数学原理之前，我们需要先补充一些关于向量求导的相关芝士。

前置芝士

 向量求导基本方法

首先我们来看相对简单的向量求导方法，假设现有一个二元函数 $f(x_1,x_2)=2x_1+x_2$ ，对该函数中的两个变量 $x_1,x_2$ 依次求偏导，可得： $\dfrac {\partial f}{\partial x_1}=2$ ， $\dfrac {\partial f}{\partial x_2}=1$ 。现在考虑将上述求偏导的函数组改写为矩阵形式，我们可以将函数中的两个变量依次排列，组成一个向量变元(即一个由多个变量所组成的向量)，即 $x=[x_1,x_2]^T$ 。此时，如果我们按照向量变元内部的变量排列顺序，依次在每个变量位置填上该变量对应的偏导函数，则就构成了对于函数 $f$ 进行向量变元 $x$ 的向量求导的结果，即： $\dfrac {\partial f(x)}{\partial x}=\left[$
$\begin{matrix} 2 \\ 1 \end{matrix}$
\right] ∂x∂f(x)=[21]，其中 $x$ 为向量变元。

至此，我们就完成了向量求导的基本过程。核心在于我们是依据向量变元中的变量排列顺序，依次填写了对应变量的偏导函数计算结果。不过，更进⼀步的来看，既然⽅程组需要改写成向量/矩阵形式，那么原始函数⽅程其实也同样需要改写成向量/矩阵形式。因此，原⽅程我们可以改写成： $f(x)=A^T\cdot x$ ，其中 $A=[2,1]^T$ ， $x=[x_1,x_2]^T$ ，原方程为 $y=2x_1+x_2$ 。结合函数求偏导结果，易知 $\dfrac {\partial f(x)}{\partial x}$ 的最终结果就是 $A$ ，即 $\dfrac {\partial f(x)}{\partial x}$ = $\dfrac {\partial (A^T\cdot x)}{\partial x}$ = $A$ ，其中 $x$ 为向量变元， $A$ 是列向量。当然，该结论也能推导⾄⼀般的情况，相关证见下述。

很多时候我们并不区分所谓向量⽅程和矩阵⽅程，⼀般所有⾃变量为向量或矩阵的⽅程，我们会统⼀称其为矩阵⽅程。包含向量或者矩阵的表达式，我们也会统⼀称其为矩阵表达式。

向量求导的定义法

设 $f (x)$ 是一个关于 $x$ 的函数，其中 $x$ 为向量变元，并且 $x=[x_1,x_2,\cdots,x_n]^T$ ，则 $\dfrac {\partial f}{\partial x}$ = $[\dfrac {\partial f}{\partial x_1},\dfrac {\partial f}{\partial x_2},\cdots,\dfrac {\partial f}{\partial x}_n]^T$ ，而该表达式也被称为向量求导的梯度向量形式。通过解得函数的梯度向量求解向量导数的方法，也被称为定义法求解。

多元函数是一定能够求得梯度向量的，但是梯度向量或者说向量求导结果，能否由⼀些已经定义的向量解决表示，如 $A$ 就是 $f (x)$ 的向量求导结果，则不一定。

常见向量求导公式

参考博客：求导定义与求导布局、矩阵向量求导之定义法、矩阵向量求导之微分法、矩阵向量求导链式法则

常见的向量求导公式如下图所示：

记 $x=[x_1,x_2,\cdots,x_n]^T$ 。下面利用向量求导的定义法推导一些公式：

（1）证明： $\dfrac {\partial a}{\partial x}=0$ ，这里 $a$ 是常数

$\dfrac {\partial a}{\partial x}$ = $[\dfrac {\partial a}{\partial x_1},\dfrac {\partial a}{\partial x_2},\cdots,\dfrac {\partial a}{\partial x_n}]^T$ = $[0,0,\cdots,0]^T$

（2）证明： $\dfrac {\partial (x^T\cdot A)}{\partial x}$ = $\dfrac {\partial (A^T\cdot x)}{\partial x}$ = $A$

此时 $A$ 为拥有 $n$ 个分量的常数向量，设 $A=[a_1,a_2,\cdots,a_n]^T$ ，则有 $\dfrac {\partial (x^T\cdot A)}{\partial x}$ = $\dfrac {\partial (A^T\cdot x)}{\partial x}$ = $\dfrac {\partial (a_1x_1+a_2x_2+\cdots +a_nx_n)}{\partial x}$ = $\left[$
$\begin{matrix} \frac{\partial (a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n})}{\partial x_{1}} \\ \dot{} \\ \dot{} \\ \dot{} \\ \frac{\partial (a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n})}{\partial x_{n}} \end{matrix}$
\right] ∂x1∂(a1x1+a2x2+⋯+anxn)˙˙˙∂xn∂(a1x1+a2x2+⋯+anxn) = $\begin{matrix} a_{1} \\ a_{2} \\ ⋮ \\ a_{n} \end{matrix}$ = $A$

（3）证明： $\dfrac {\partial (x^T\cdot x)}{\partial x}$ = $2 x$

$\dfrac {\partial (x^T\cdot x)}{\partial x}$ = $\dfrac {\partial (x_1^2+x_2^2+\cdots x_n^2)}{\partial x}$ = $\left[$
$\begin{matrix} \frac{\partial (x_{1}^{2} + x_{2}^{2} + \dots x_{n}^{2})}{\partial x_{1}} \\ \frac{\partial (x_{1}^{2} + x_{2}^{2} + \dots x_{n}^{2})}{\partial x_{2}} \\ ⋮ \\ \frac{\partial (x_{1}^{2} + x_{2}^{2} + \dots x_{n}^{2})}{\partial x_{n}} \end{matrix}$
\right] ∂x1∂(x12+x22+⋯xn2)∂x2∂(x12+x22+⋯xn2)⋮∂xn∂(x12+x22+⋯xn2) = $\begin{matrix} 2 x_{1} \\ 2 x_{2} \\ ⋮ \\ 2 x_{n} \end{matrix}$ = $2[x_1,x_2,\cdots, x_n]^T$ = $2 x$

此处 $x^Tx$ 也称为向量的交叉乘积(crossprod)，在线代中称为向量的内积。

（4）证明： $\dfrac {\partial (x^TAx)}{\partial x}$ = $Ax+A^Tx$

其中 $A$ 是一个 $n\times n$ 的矩阵，首先 $x^TAx$ = $[x_1,x_2,\cdots, x_n]$ $\cdot$ $\left[$
$\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}$
\right] a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮ann $\cdot$ $[x_1,x_2,\cdots,x_n]^T$

= $[x_1a_{11}+x_2a_{21} + \cdots + x_na_{n1}, \cdots, x_1a_{1n}+x_2a_{2n} + \cdots + x_na_{nn}]$ $\cdot$ $\left[$
$\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}$
\right] x1x2⋮xn

= $x_1(x_1a_{11}+x_2a_{21}+\cdots+x_na_{n1}) + \cdots + x_n(x_1a_{1n}+x_2a_{2n}+\cdots+x_na_{nn})$

令 $k (x)$ = $x_1(x_1a_{11}+x_2a_{21}+\cdots+x_na_{n1}) +\cdots + x_n(x_1a_{1n}+x_2a_{2n}+\cdots+x_na_{nn})$

则有 $\dfrac {\partial k(x)}{\partial x_1}$ = $(x_1a_{11}+x_2a_{21}+\cdots+x_na_{n1})+x_1a_{11}$ + $x_2a_{12}$ + $\cdots$ + $x_na_{1n}$

= $(x_1a_{11}+x_2a_{21}+\cdots+x_na_{n1})$ $+$ $(x_1a_{11} + x_2a_{12}+\cdots + x_na_{1n})$

同理可知 $\dfrac {\partial k(x)}{\partial x}$ = $\left[$
$\begin{matrix} \frac{\partial k (x)}{\partial x_{1}} \\ \frac{\partial k (x)}{\partial x_{2}} \\ ⋮ \\ \frac{\partial k (x)}{\partial x_{n}} \end{matrix}$
\right] ∂x1∂k(x)∂x2∂k(x)⋮∂xn∂k(x) = $\begin{matrix} (x_{1} a_{11} + x_{2} a_{21} + \dots + x_{n} a_{n 1}) + (x_{1} a_{11} + x_{2} a_{12} + \dots + x_{n} a_{1 n}) \\ (x_{1} a_{12} + x_{2} a_{22} + \dots + x_{n} a_{n 2}) + (x_{1} a_{21} + x_{2} a_{22} + \dots + x_{n} a_{2 n}) \\ \dot{} \\ \dot{} \\ \dot{(x_{1} a_{1 n} + x_{2} a_{2 n} + \dots + x_{n} a_{n n}) + (x_{1} a_{n 1} + x_{2} a_{n 2} + \dots + x_{n} a_{n n})} \end{matrix}$

= $\left[$
$\begin{matrix} x_{1} a_{11} + x_{2} a_{21} + \dots + x_{n} a_{n 1} \\ x_{1} a_{12} + x_{2} a_{22} + \dots + x_{n} a_{n 2} \\ \dot{} \\ \dot{} \\ \dot{} \\ x_{1} a_{1 n} + x_{2} a_{2 n} + \dots + x_{n} a_{n n} \end{matrix}$
\right] x1a11+x2a21+⋯+xnan1x1a12+x2a22+⋯+xnan2˙˙˙x1a1n+x2a2n+⋯+xnann $+$ $\begin{matrix} x_{1} a_{11} + x_{2} a_{12} + \dots + x_{n} a_{1 n} \\ x_{1} a_{21} + x_{2} a_{22} + \dots + x_{n} a_{2 n} \\ \dot{} \\ \dot{} \\ \dot{} \\ x_{1} a_{n 1} + x_{2} a_{n 2} + \dots + x_{n} a_{n n} \end{matrix}$

= $\left[$
$\begin{matrix} a_{11} & a_{21} & \dots & a_{n 1} \\ a_{12} & a_{22} & \dots & a_{n 2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{1 n} & a_{2 n} & \dots & a_{n n} \end{matrix}$
\right] a11a12⋮a1na21a22⋮a2n…⋯⋱⋯an1an2⋮ann $\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}$ + $\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}$ $\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}$ = $A^Tx+Ax$

最小二乘法的推导及使用

有了上述内容铺垫之后，接下来，我们从数学⻆度讨论最⼩⼆乘法的基本理论，并尝试简单实现最⼩⼆乘法求解损失函数的⼀般过程。

模型及方程组的矩阵形式改写
1. 模型改写矩阵表达式
首先，假设多元线性⽅程有如下形式： $f(x)=w_1x_1+w_2x_2+\cdots+w_nx_n+b$

令 $w=[w_1,w_2,\cdots,w_n]^T$ ， $x=[x_1,x_2,\cdots,x_n]^T$ ，则上式可以改写为 $f(x)=w^Tx+b$

在机器学习领域，我们将线性回归⾃变量系数命名为 $w$ ，其实是weight的简写，意为⾃变量的权重。
1. 将带入数据后的方程组改写为矩阵方程
假设现在总共有 $m$ 条观测值， $x^{(i)}=[x_1^{(i)},x_2^{(i)},\cdots,x_d^{(i)}]$ ，则带入模型可构成 $m$ 个方程：

$\left[$
$\begin{matrix} w_{1} x_{1}^{(1)} + w_{2} x_{2}^{(1)} + \dots + w_{d} x_{d}^{(1)} + b \\ w_{1} x_{1}^{(2)} + w_{2} x_{2}^{(2)} + \dots + w_{d} x_{d}^{(2)} + b \\ \dot{} \\ \dot{} \\ \dot{} \\ w_{1} x_{1}^{(m)} + w_{2} x_{2}^{(m)} + \dots + w_{d} x_{d}^{(m)} + b \end{matrix}$
\right] w1x1(1)+w2x2(1)+⋯+wdxd(1)+bw1x1(2)+w2x2(2)+⋯+wdxd(2)+b˙˙˙w1x1(m)+w2x2(m)+⋯+wdxd(m)+b = $\begin{matrix} {\hat{y}}_{1} \\ {\hat{y}}_{2} \\ ⋮ \\ {\hat{y}}_{m} \end{matrix}$

然后考虑将上述方程组进行改写，可以令：

$\hat w=[w_1,w_2,\cdots,w_d,b]^T$ ， $\hat x=[x_1,x_2,\cdots,x_d,1]^T$

$\hat X$ = $\left[$
$\begin{matrix} x_{1}^{(1)} & x_{2}^{(1)} \dots x_{d}^{(1)} & 1 \\ x_{1}^{(2)} & x_{2}^{(2)} \dots x_{d}^{(2)} & 1 \\ ⋮ & ⋮ ⋱ & 1 \\ x_{1}^{(m)} & x_{2}^{(m)} \dots x_{d}^{(m)} & 1 \end{matrix}$
\right] x1(1)x1(2)⋮x1(m)x2(1)⋯xd(1)x2(2)⋯xd(2)⋮⋱x2(m)⋯xd(m)1111 ， $\begin{matrix} y_{1} \\ y_{2} \\ ⋮ \\ y_{m} \end{matrix}$ ， $\begin{matrix} {\hat{y}}_{1} \\ {\hat{y}}_{2} \\ ⋮ \\ {\hat{y}}_{m} \end{matrix}$
- $\hat w$ ：⽅程系数所组成的向量，并且我们将⾃变量系数和截距 $b$ 放到了⼀个向量
- $\hat x$ ：⽅程⾃变量与常数 $1$ 所共同组成的向量
- $\hat X$ ：样本数据特征构成的矩阵，并在最后⼀列添加⼀个全为 $1$ 的列
- $y$ ：样本数据标签所构成的列向量
- $\hat y$ ：预测值的列向量
因此，上述构成的 $m$ 个方程可以表示为： $\hat X\cdot \hat w = \hat y$

3.模型进一步改写

在改写了 $\hat x$ 和 $\hat w$ 之后，线性模型 $f(x)=w_1x_1+w_2x_2+\cdots+w_dx_d+b$ 可以改写为： $f(\hat x)=\hat w^T\cdot \hat x$

构造损失函数

对于回归类问题，最重要的模型评估指标就是SSE——残差平方和，指的是模型预测值 $\hat y$ 和真实值 $y$ 之间的差值的平方和，计算结果表示预测值和真实值之间的差距，结果越小表示二者差距越小，模型效果越好。SSE基本计算公式为： $SSE=\sum \limits _{i=1} ^n (\hat y_i-y_i)^2$

在⽅程组的矩阵表示基础上，我们可以用SSE作为损失函数基本计算流程构建关于 $\hat w$ 的损失函数：

$SSELoss(\hat w)=||y-\hat X\hat w||_2^2=(y-\hat X\hat w)^T(y-\hat X\hat w)$

向量的2-范数计算公式：

上式中， $||y-\hat X\hat w||_2$ 为向量的2-范数的计算表达式。向量的2-范数计算过程为各分量求平方和再进行开平方。例如 $a = [1, - 1]$ ，则 $||a||_2=\sqrt{1^2+(-1)^2}=\sqrt {2}$

2-范数计算转化为内积运算：

向量的2-范数计算结果其实就是向量内积计算结果后开平⽅。例如 $a = [1, - 1]$ ，则 $a$ 的内积为 $a\cdot a^T=[1,-1]\cdot \left[$
$\begin{matrix} 1 \\ - 1 \end{matrix}$ \right] $a \cdot a^{T} = [1, - 1] \cdot [1 - 1]$ = $2$ ，其开平方后为 $\sqrt{2}$ ，也就等于2-范数的计算结果。

最小二乘法求解损失函数的⼀般过程

在确定损失函数的矩阵表示形式之后，接下来即可利⽤最小二乘法进行求解。基本求解思路：先求导函数、再令导函数取值为零，进⽽解出参数取值。只不过此时求解的是矩阵⽅程。

对 $SSELoss(\hat w)$ 求导并令其等于 $0$ ，则 $0$ = $\dfrac {SSELoss(\hat w)}{\partial \hat w}$ = $\dfrac {\partial ||y-\hat X\hat w||_2^{2}}{\partial \hat w}$ = $\dfrac {\partial [(y-\hat X\hat w)^T(y-\hat X\hat w)]}{\partial \hat w}$ = $\dfrac {\partial[(y^T-\hat w^T\hat X^T)(y-\hat X\hat w)]}{\partial \hat w}$ = $\dfrac {\partial(y^Ty-y^T\hat X\hat w-\hat w^T\hat X^Ty+\hat w^T\hat X^T\hat X\hat w)}{\partial \hat w}$ = $(y^T\hat{X})^T-\hat{X}^Ty+\hat X^T\hat X\hat w + (\hat X^T\hat X)^T\hat w$ = $2(\hat X^T\hat X\hat W - \hat X^Ty)$

因此有： $\hat X^T\hat X\hat w-\hat X^Ty = 0$ ，即 $\hat X^T\hat X\hat w=\hat X^Ty$

要使得此式有解，等价于 $\hat X^T\hat X$ 可逆，则解得 $\hat w$ = $(\hat X^T\hat X)^{-1}\hat X^Ty$

最小二乘法的简单实现

简单尝试利⽤上述推导公式求解简单线性回归参数。原始数据如下：

Whole weight Rings
1 2
3 4

因此利⽤矩阵表达式，可进行如下形式的改写：

特征矩阵 $\hat X=\left[$
$\begin{matrix} 1 & 1 \\ 3 & 1 \end{matrix}$
\right] X^=[1311]，标签数组 $\begin{matrix} 2 \\ 4 \end{matrix}$ ，参数向量 $\begin{matrix} w \\ b \end{matrix}$

求解公式为 $\hat w$ = $(\hat X^T\hat X)^{-1}\hat X^Ty$ = $(\left[$
$\begin{matrix} 1 & 1 \\ 3 & 1 \end{matrix}$
\right]^T\left[
$\begin{matrix} 1 & 1 \\ 3 & 1 \end{matrix}$
\right])^{-1}\left[
$\begin{matrix} 1 & 1 \\ 3 & 1 \end{matrix}$
\right]^T\left[
$\begin{matrix} 2 \\ 4 \end{matrix}$
\right] ([1311]T[1311])−1[1311]T[24]

上述这个小栗子的代码实现过程：
```
'''
输出结果：
array([[1.],
       [1.]])
'''

import numpy as np
X = np.array([[1, 1], [3, 1]])
y = np.array([2,4]).reshape(2, 1)
np.linalg.inv(X.T.dot(X)).dot(X.T).dot(y)
1
2
3
4
5
6
7
8
9
10
```
即解得 $w = 1, b = 1$ ，即模型方程为 $y = x + 1$ 。⾄此，我们即完成了最⼩⼆乘法的推导以及简单实现。

补充

简单线性回归中的"线性"与"回归"的形象理解：

简单线性回归的⼏何意义，就是希望找到⼀条直线，尽可能的接近样本点。或者说，我们是通过⼀条直线去捕捉平面当中的点。当然，大多数情况下我们都⽆法对平⾯中的点进行完全的捕捉，而直线和点之间的差值，实际上就是SSE。而线性回归中"回归"的含义，则是：如果模型真实有效，则新数据也会像朝向这条直线"回归"⼀样，最终分布在这条直线附近。这就是简单线性回归中的"线性"和"回归"的形象理解。

最小二乘法的的局限性和适用场景

从上面可以看出，最小二乘法适用简洁高效，比梯度下降这样的迭代法似乎方便很多。但是最小二乘法也存在局限性。

（1）最小二乘法需要计算 $X^TX$ 的逆矩阵，有可能它的逆矩阵不存在，这样就没有办法直接用最小二乘法了，此时梯度下降法仍然可以使用。当然，我们可以通过对样本数据进行整理，去掉冗余特征。让 $X^TX$ 的行列式不为 $0$ ，然后继续使用最小二乘法。

（2）当样本特征 $n$ 非常大时，计算 $X^TX$ 的逆矩阵是一个非常耗时的工作( $n\times n$ 的矩阵求逆)，甚至不可行。此时以梯度下降为代表的迭代法仍然可以使用。那这个 $n$ 到底多大就不适合最小二乘法呢？如果你没有很多的分布式大数据计算资源，建议超过 $10000$ 个特征就用迭代法吧。或者通过主成分分析降低特征的维度后再用最小二乘法。

（3）如果拟合函数不是线性的，这时无法使用最小二乘法，需要通过一些技巧转化为线性才能使用，此时梯度下降仍然可以用。

（4）讲一些特殊情况。设样本量为 $m$ ，特征数为 $n$ 。当 $时，这时拟合方程是欠定的，常用的优化方法都无法去拟合数据(类似于方程组的个数小于变量个数)。当 m = n 时，用方程组求解就可以了。当 m > n 时，拟合方程是超定的(类似于方程组的个数大于变量个数)，也就是我们常用于最小二乘法的场景了。$
相关阅读:
leetcode字符串必刷题——反转字符串、反转字符串 II、反转字符串中的单词、找出字符串中第一个匹配项的下标、重复的子字符串
 惠普星15和联想小新pro16 哪个好
 利用X6 制作一个简单的流程图工具
 java项目技术方案——书写示例
 docker安装Nacos并配置MySQL
《自然语言处理实战入门》基于知识图谱的问答机器人
 加列法计算lower unit matrix inversion
数据科学家赚多少？数据全分析与可视化 ⛵
7×24无人值守直播推流软件开发实战，一文为你揭开视频推流的底层原理(附源码)
根据服务器系统选择对应的MySQL版本
原文地址：https://blog.csdn.net/qq_45832461/article/details/127590195

Whole weight	Rings
1	2
3	4

前置芝士

向量求导基本方法

向量求导的定义法

常见向量求导公式

最小二乘法的推导及使用

模型及方程组的矩阵形式改写

构造损失函数

最小二乘法求解损失函数的⼀般过程

最小二乘法的简单实现

最小二乘法的的局限性和适用场景