Home Machine Learning Mathematical methods

# 背景介绍

最小二乘法（英语：least squares method），又称最小平方法，是一种数学优化建模方法。它通过最小化误差的平方和（均方误差，mean square error, MSE）寻找数据的最佳函数匹配，以此可以简便的求得未知的数据。其最重要的应用是在曲线拟合上。
最小平方法通常归功于高斯（Carl Friedrich Gauss，1795），但最小平方法是由阿德里安 - 马里・勒让德（Adrien-Marie Legendre）首先发表的。

# 最小二乘法

# 问题描述

下文将以线性函数来对样本SampleSample 进行拟合为例，来说明最小二乘法。同时未经特别说明，文中所有的向量均为列向量（粗体）。

输入描述：m 个样本Sample={(x(1))T,y(1)),(x(2))T,y(2),⋯,(x(m))T,y(m))}Sample = \{(\boldsymbol{x^{(1)}})^{T}, y^{(1)}), (\boldsymbol{x^{(2)}})^{T}, y^{(2)},\cdots, (\boldsymbol{x^{(m)}})^{T}, y^{(m)})\}. 找到一条曲线使得其可以尽可能的接近所以样本点（平均接近）. 对于样本点ii, y(i)y^{(i)} 表示其函数值，x(i)\mathbf{x^{(i)}} 为自变量，不妨设其维度为nn，即有：

x(i)=[x1(i)x2(i)⋮xn(i)]\boldsymbol{x^{(i)}} = \left[\begin{array}{c} x_{1}^{(i)} \\ x_{2}^{(i)} \\ \vdots \\ x_{n}^{(i)} \\ \end{array}\right]

目标函数：

fθ(x)=θ0+θ1x1+⋯+θnxn=[θ0θ1⋯θn][1x1⋮xn]=θTx^(1)f_{\boldsymbol{\theta}}(\boldsymbol{x})= \theta_{0}+\theta_{1}x_{1}+\cdots+\theta_{n}x_{n}= \left[\begin{array}{cccc} \theta_{0} & \theta_{1} & \cdots & \theta_{n} \end{array}\right] \left[\begin{array}{c} 1 \\ x_{1} \\ \vdots \\ x_{n} \\ \end{array}\right] = \boldsymbol{\theta}^{T}\hat{\boldsymbol{x}} \tag{1}

对每个样本自变量添加一个维度x0x_{0}， 并且所以的x0=1x_{0} = 1。即输入样本Sample^={(x^(1))T,y(1)),(x^(2))T,y(2),⋯,(x^(m))T,y(m))}\hat{Sample} = \{(\boldsymbol{\hat{x}^{(1)}})^{T}, y^{(1)}), (\boldsymbol{\hat{x}^{(2)}})^{T}, y^{(2)},\cdots, (\boldsymbol{\hat{x}^{(m)}})^{T}, y^{(m)})\}

损失函数：

L(θ)=∑i=1m(fθ(x(i))−y(i))2=∑i=1m(θTx^(i)−y(i))2(2)L(\boldsymbol{\theta)} = \sum_{i=1}^{m} (f_{\boldsymbol{\theta}}(\boldsymbol{x^{(i)}}) - y^{(i)})^{2} = \sum_{i=1}^{m} (\boldsymbol{\theta}^{T}\boldsymbol{\hat{x}^{(i)}} - y^{(i)})^{2} \tag{2}

在损失函数最小的情况下，求解相应的参数值，即(θ0,θ1,⋯,θn)(\theta_{0}, \theta_{1}, \cdots, \theta_{n})

# 代数求解法

要使得损失函数最小，分别对θj,j∈(0,1,⋯,n)\theta_{j}, j\in(0, 1, \cdots, n) 进行求导，令其偏导数为 0，即：

∂L(θ)∂θj=∑i=1m[(0⋯1⋯0)x^(i)(θTx^(i)−y(i))]=2∑i=1mxj(i)(θTx^(i)−y(i))=0(3)\frac{\partial L(\boldsymbol{\theta})} {\partial \theta_{j}} = \sum_{i = 1}^{m} \left[(\begin{array}{cccc} 0 & \cdots & 1 & \cdots & 0 \end{array}) \boldsymbol{\hat{x}^{(i)}} (\boldsymbol{\theta}^{T}\boldsymbol{\hat{x}^{(i)}} - y^{(i)}) \right] = 2\sum_{i = 1}^{m}x_{j}^{(i)} (\boldsymbol{\theta}^{T}\boldsymbol{\hat{x}^{(i)}} - y^{(i)}) = 0 \tag{3}

即可得到一个 n+1 个关于(θ0,θ1,⋯,θn)(\theta_{0}, \theta_{1}, \cdots, \theta_{n}) 的方程组，联立方程组即可求解。这个方法同样也可以推广至非线性函数拟合，原理与上面一样，均是对每个参数求偏导为 0，然后联立方程组来求得参数值.

# 矩阵求解法

计算机对于方程组的求解，使用的一种技巧是矩阵求解法。对(3)(3) 整理可得：

∂L(θ)∂θj=2(xj(1)xj(2)⋯xj(m))[θTx^(1)−y(1)θTx^(2)−y(2)⋮θTx^(m)−y(m)]=0j=(0,1,⋯,n)(4)\frac{\partial L(\boldsymbol{\theta})} {\partial \theta_{j}} = 2 \left(\begin{array}{cccc} x^{(1)}_{j} & x^{(2)}_{j} & \cdots & x^{(m)}_{j} \end{array}\right) \left[\begin{array}{c} \boldsymbol{\theta}^{T}\boldsymbol{\hat{x}^{(1)}} - y^{(1)} \\ \boldsymbol{\theta}^{T}\boldsymbol{\hat{x}^{(2)}} - y^{(2)} \\ \vdots \\ \boldsymbol{\theta}^{T}\boldsymbol{\hat{x}^{(m)}} - y^{(m)} \\ \end{array}\right] = 0 \quad j = (0, 1, \cdots, n) \tag{4}

故将 n+1 个方程组联立可得：

∂L(θ)∂θ=2[x0(1)x0(2)⋯x0(m)x1(1)x1(2)⋯x1(m)⋮⋮⋱⋮xn(1)xn(2)⋯xn(m)][θTx^(1)−y(1)θTx^(2)−y(2)⋮θTx^(m)−y(m)]=2[x0(1)x0(2)⋯x0(m)x1(1)x1(2)⋯x1(m)⋮⋮⋱⋮xn(1)xn(2)⋯xn(m)]XT([x^(1)x^(2)⋮x^(m)]Xθ−[y(1)y(2)⋮y(m)])=2XT(Xθ−y)=0(5)\frac{\partial L(\boldsymbol{\theta})} {\partial \boldsymbol{\theta}} = 2 \left[\begin{array}{cccc} x^{(1)}_{0} & x^{(2)}_{0} & \cdots & x^{(m)}_{0} \\ x^{(1)}_{1} & x^{(2)}_{1} & \cdots & x^{(m)}_{1} \\ \vdots & \vdots & \ddots & \vdots \\ x^{(1)}_{n} & x^{(2)}_{n} & \cdots & x^{(m)}_{n} \\ \end{array}\right] \left[\begin{array}{c} \boldsymbol{\theta}^{T}\boldsymbol{\hat{x}^{(1)}} - y^{(1)} \\ \boldsymbol{\theta}^{T}\boldsymbol{\hat{x}^{(2)}} - y^{(2)} \\ \vdots \\ \boldsymbol{\theta}^{T}\boldsymbol{\hat{x}^{(m)}} - y^{(m)} \\ \end{array}\right] = 2 \mathop{ \left[\begin{array}{cccc} x^{(1)}_{0} & x^{(2)}_{0} & \cdots & x^{(m)}_{0} \\ x^{(1)}_{1} & x^{(2)}_{1} & \cdots & x^{(m)}_{1} \\ \vdots & \vdots & \ddots & \vdots \\ x^{(1)}_{n} & x^{(2)}_{n} & \cdots & x^{(m)}_{n} \\ \end{array}\right] }\limits_{\boldsymbol{X^{T}}} \left( \mathop{ \left[\begin{array}{cccc} \boldsymbol{\hat{x}^{(1)}} \\ \boldsymbol{\hat{x}^{(2)}} \\ \vdots \\ \boldsymbol{\hat{x}^{(m)}} \end{array}\right] }\limits_{\boldsymbol{X}} \boldsymbol{\theta} - \left[\begin{array}{cccc} y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(m)} \end{array}\right] \right) = 2 \boldsymbol{X^{T}}(\boldsymbol{X}\boldsymbol{\theta} - \boldsymbol{y}) = \boldsymbol{0} \tag{5}

整理化简可得：XTXθ=XTy\boldsymbol{X^{T}}\boldsymbol{X}\boldsymbol{\theta} = \boldsymbol{X^{T}}\boldsymbol{y}. 当XTX\boldsymbol{X^{T}}\boldsymbol{X} 可逆时，可求得：

θ=(XTX)−1XTy\boldsymbol{\theta} = (\boldsymbol{X^{T}}\boldsymbol{X})^{-1}\boldsymbol{X^{T}}\boldsymbol{y}

# 局限性

  1. 如(5)(5) 所示，使用矩阵求解法来求解时，其必须要满足上式(XTX)(\boldsymbol{X^{T}}\boldsymbol{X}) 可逆。如果不可逆，则无法使用最小二乘法，往往此时的解决方法可以是，使用其他优化算法来求解，比如梯度下降法。 (XTX)(\boldsymbol{X^{T}}\boldsymbol{X}) 不可逆存在如下特殊情况：
    • 当样本数 <= 特征数时， (XTX)(\boldsymbol{X^{T}}\boldsymbol{X}) 必定不可逆。往往对样本数据重新整理，去掉冗余特征。若无法使得特征数小于样本数，说明拟合方程是欠定的，常用的优化方法都无法拟合数据。
  2. 当特征数目很多时，求解 (XTX)(\boldsymbol{X^{T}}\boldsymbol{X}) 的逆是一个非常耗时的工作（10000 个特征以上），往往先通过主成分分析 PCA 或者层次分析法降低特征的维度再使用最小二乘法。

# 参考文章

  • 最小二乘法小结 - 刘建平 Pinard - 博客园 (cnblogs.com)
  • 线性模型 - 哔哩哔哩 - 刘二大人 - bilibili
  • WIKI - 维基百科 - 百科全书