半小时学习最小二乘法

EndlessLethe原创文章,转载请注明: 转载自小楼吹彻玉笙寒

本文链接地址: 半小时学习最小二乘法


前言

最小二乘法在统计学的地位不必多言。本文的目的是全面地讲解最小二乘法,打好机器学习的基础。本文主要内容是最小二乘法的思想及在线性回归问题中的应用。后面的系列文章会继续讲解最小二乘的正则化。
至于非线性最小二乘和广义线性模型,如果以后有时间会进行整理。

不熟悉极大似然法的读者可以阅读我的另一篇文章《十分钟学习极大似然估计

updata 2019/6/13:添加了对线性回归问题的矩阵定义和简要介绍,修改了少量句子,修正了公式中的少量错误。

核心思想

最小二乘法是勒让德( A. M. Legendre)于1805年在其著作《计算慧星轨道的新方法》中提出的。它的主要思想就是求解未知参数,使得理论值与观测值之差(即误差,或者说残差)的平方和达到最小:
\[E = \mathop \sum \limits_{i = 1}^n e_i^2 = \mathop \sum \limits_{i = 1}^n {\left( {{y_i} – \hat y} \right)^2}\]
观测值\(y_i\)就是我们的多组样本,理论值\(\hat y\)就是我们的假设拟合函数。目标函数也就是在机器学习中常说的损失函数\(E\),我们的目标是得到使目标函数最小化时候的参数。

所谓最小二乘,其实也可以叫做最小平方和,其目的就是通过最小化误差的平方和,使得拟合对象无限接近目标对象。换句话说,最小二乘法定义了一种函数的拟合标准,其目标是最小化误差的平方和。

直观理解

均方误差有非常好的几何意义,它对应了常用的欧几里德距离。在线性回归中,最小二乘法就是试图找到一条直线,使所有样本到直线的欧氏距离之和最小。

假设有一条直线\(y=ax+b\),要在这条直线上找到一点,距离\((x_0,y_0)\)这个点的距离最短。如果用绝对值的方法寻找,也就是取\(\min(|y-y_0|+|x-x_0|)\),由于绝对值最小为0,所以最小的情况就是\(x=x_0\)或者\(y=y_0\)处,如下图1所示。
lsm 1

如果用平方和的方法寻找,就是取\(\min {{(y – {y_0})^2} + {(x – {x_0})^2}}\),可以看出该式是两点间距离公式,也就是距离的概念。那么最短的距离,就是点到直线的垂线,如下图2所示。
lsm 2

事实上,线性回归中最小二乘法的解\(\theta= {\left( {{X^T}X} \right)^{ – 1}}{X^T}Y\)也就是投影矩阵的公式:将Y向量投影到X构成的平面上。

对任意函数f的通用解法

  1. 列出损失函数\(E = \mathop \sum \limits_{i = 1}^n e_i^2 = \mathop \sum \limits_{i = 1}^n {\left( {{y_i} – \hat y} \right)^2}\)
  2. 根据损失函数对参数应用多元函数的求极值方法,直接求解函数最小值。而更常见的方法即是将损失函数\(y_i\)用\(x_i\)和参数表示,然后使用梯度下降算法。
  3. 求得函数最小值的参数或待到梯度算法收敛,此时的参数即为所求
    这些个步骤说起来抽象,实际上这是在机器学习中应用最广泛的方法。但是对于后面的线性回归问题,有着更简洁的推导方法。

以算术平均值为例——为什么算术平均即是真值

可以说整部数理统计学的历史,就是对算术平均不断深入研究的历史。而最小二乘法可以解释为什么多次测量取算术平均的结果就是真值,比如估计身高可以测三次后取平均。

当我们对于某个未知量\(\theta\)观测\(m\)次,记每次的结果为\(x_i\)
\[E = \mathop \sum \limits_{i = 1}^m e_i^2 = \mathop \sum \limits_{i = 1}^m {\left( {{x_i} – \theta} \right)^2}\]
求导得
\[\mathop \sum \limits_{i = 1}^n – \left( {{x_i} – \theta} \right) = 0\]
所以\(\theta = \bar x = \frac{{\mathop \sum \nolimits^ {x_i}}}{m}\)

线性回归问题的定义

这部分我们简要回顾一下基本的线性代数知识。

我们知道一条直线,在三维空间中,可以用形如\(ax+by+cz=d\)的方程表示,而用矩阵的形式表达的话,即为AX=B,其中B为常数,而A和X都为n维向量。那么多个这样的方程联立在一起就被称为线性方程组,其中有两个基本问题:1)方程组是否有解,即解的存在性问题? 2)如果有解,解的个数有多少个?

为了回答这两个问题,我们令线性方程组中的方程都为线性无关方程(可以通过简单地初等行变换),方程个数为\(m\),特征数(参数数量)为\(n\)。在这样的假设下,如果\(m=n\),则一行方程对应一个参数的解,此时方程组有唯一解。如果\(m>n\),则方程无解,因为存在互相矛盾的两个方程。如果\(m<n\),则方程和参数不能一一对应,存在无穷多解。而最小二乘法是在\(m>n\)时可以使用的,其通过让残差平方和最小,找到互相矛盾解之间的近似解。

使用最小二乘求解线性回归问题

对于线性回归问题,当然可以使用求导的代数方法来找到损失函数的最小值。但矩阵法比代数法要简洁,所以现在很多书和机器学习库都是用的矩阵法来做最小二乘法,本文这里介绍一下如何使用矩阵法求解线性回归问题。

对于函数\({h_{\theta}}({x_1},{x_2},…{x_n}) = {\theta_0} + {\theta_1}{x_1} + … + {\theta_n}{x_n}\),我们将其的矩阵形式记作:
\[ X\theta = Y \]
lsm 3

故损失函数根据定义将Y用X和\(\theta\)代替:(系数1/2是为了简化计算添加的,求迹前和求迹后值不变)
lsm 4

应用矩阵迹的计算公式:
lsm 5

令上式为0,解得\(\theta= {\left( {{X^T}X} \right)^{ – 1}}{X^T}Y\)

Note:矩阵求导坑多,使用迹来计算比较方便。

线性回归的t检验

记n为回归方程的特征个数,m为样本数
\[S_回=\sum_{i=1}^m(\hat y – \overline y)\]
\[S_剩=\sum_{i=1}^m(y_i – \hat y)\]

总平方和(SST)可分解为回归平方和(SSR)与残差平方和(SSE)两部
\[MSR = SSR / k\]
\[MSE = SSE / (n – k – 1)\]
\[F = \frac{{MSR}}{{MSE}} = \frac{{{S_回}/k}}{{{S_剩}/(n – k – 1)}}\]

若用样本计算的\(F > F_{0.05} (k , n – k – 1)\),则拒绝\(H_0\),则回归方程在显著性水平\(\alpha=0.05\)下是显著的。

最小二乘法的适用场景

前面已经提到,根据方程数m和特征数n可以判定方程组解的存在性问题和个数问题。
当样本量\(m\)很少,小于特征数\(n\)的时候,这时拟合方程是欠定的,需要使用LASSO。当\(m=n\)时,用方程组求解。当\(m>n\)时,拟合方程是超定的,我们可以使用最小二乘法。

局限性

  • 首先,最小二乘法需要计算\({\left( {{X^T}X} \right)^{ – 1}}\)逆矩阵,有可能逆矩阵不存在,这样就没有办法直接用最小二乘法。
  • 第二,当样本特征n非常的大的时候,计算逆矩阵是一个非常耗时的工作,甚至不可行。建议不超过10000个特征。
  • 第三,如果拟合函数不是线性的,这时无法使用最小二乘法,需要通过一些技巧转化为线性才能使用。(非线性最小二乘)

最小二乘法和M估计

在统计数据时,难免会遇到异常值,即人为误差。而这种误差对结果的影响远比系统误差大,比如将1记录成10。所以我们使用稳健性来评价一个方法对异常值的敏感程度。

最小二乘法是一种稳健性较差的方法,原因在于其目标函数是误差的平方,是一个增长很快的函数,其对离群的异常值非常敏感。所以不难想到,对于\(E = \mathop \sum \nolimits f({x_i})\),我们可以取\(f(x)=|x|\)来减小函数的增长速度。
统计学家休伯将这一想法用于对单个未知量\(\theta\)参数估计的情况,误差满足正态分布\(x_i=\theta+e_i\),就给定\(\rho\)函数:
,取定函数\(\rho\),找出使函数\(M\left( {\theta} \right) = \mathop \sum \limits_{i = 1}^m \rho({x_i} – \theta)\)达到最小的\(\hat \theta\),将其作为\(\theta\)的估计值。\(\hat \theta\)称为\(\theta\)的M估计。

M估计是一类估计,主要包括\(\rho(u)=u^2\)的最小二乘法和\(\rho(u)=|x|\)的最小一乘法。M估计也可以和最小二乘法一样,推广到多元线性回归,称为稳健回归,但是因为难于计算等局限,应用并不广泛。

Note:最小一乘法对未知参数θ的估计值\(\hat \theta =x_i的中位数\)

最小二乘法和正则化

当\({\left( {{X^T}X} \right)^{ – 1}}\)不存在,即\(X_TX\)不满秩时,\(\theta\)无唯一解。

故考虑在原先的A的最小二乘估计中加一个小扰动\(\lambda I\),使原先无法求广义逆的情况变成可以求出其广义逆,使得问题稳定并得以求解。有:
\(\hat \theta= {\left( {{X^T}X} + \lambda I \right)^{ – 1}}{X^T}Y\)

而此时对应的损失函数为
\[ J(\theta ) = \mathop \sum \limits_{i = 1}^m {({y_i} – {\theta ^T}{x_i})^2} + \lambda || \theta || _2^2 \]
上式称为岭回归(ridge regression),通过引入L2范数正则化。


当然也可以将L2范数替换为L1范数。对应有
\[ J(\theta ) = \mathop \sum \limits_{i = 1}^m {({y_i} – {\theta ^T}{x_i})^2} + \lambda || \theta || _1 \]
上式称为LASSO。

对于L2范数,本质上其实是对误差的高斯先验。
而L1范数则对应于误差的Laplace先验。

最小二乘法的理论证明

拉普拉斯指出随机误差应满足正态分布,而高斯创造性地发明并使用极大似然法证明了最小二乘法。
故测量误差服从高斯分布的情况下, 最小二乘法等价于极大似然估计。

对于任何拟合方程都有:\(y = \hat y + e\)
因为\(e \sim N(0,{\sigma^2})\),故\(y \sim N(\hat y,{\sigma^2})\)

由极大似然估计,\(L(\theta ) = \mathop \prod \limits_i f({y_i})\)
\[L = \frac{1}{{{{\left( {\sqrt {2\pi } \sigma } \right)}^n}}}exp\left\{ { – \frac{1}{{2{\sigma ^2}}}\sum\limits_{i = 1}^n {{{\left( {{y_i} – \hat y} \right)}^2}} } \right\} = \frac{1}{{{{\left( {\sqrt {2\pi } \sigma } \right)}^n}}}exp{ – \frac{1}{{2{\sigma ^2}}}\sum\limits_{i = 1}^n {e_i^2} }\]

Note:数学的发展史很多时候是不符合逻辑顺序的。事实上,高斯当时是循环论证最小二乘法的,推理有缺陷。而后拉普拉斯才弥补了这一点。其中故事可以见《数理统计学简史》。

参考文献

I. 《数理统计学简史》 陈希孺著
II. 《机器学习》 周志华著
III. 正态分布的前世今生(二)
IV. 最小二乘法的本质是什么?
V. 最小二乘法小结
VI. 到底什么是最小二乘法?
VII. 最小二乘法和线性回归及很好的总结
VIII. 最小二乘法与岭回归的介绍与对比
IX. 最小二乘法
X. 最优化理论·非线性最小二乘
XI. Linear least squares, Lasso,ridge regression有何本质区别?
XII. 为什么最小二乘法对误差的估计要用平方?

6 评论

  1. 30分钟我可以把所有的中文字看一遍,就是不懂。
    想请教下博主怎么判别数据是否适用于线性回归呢?
    网上说要检查下变量的膨胀系数,系数大于10就说明变量间有明显的相关性了,要换其它方法。
    但我用R语言进行多元线性回归,用逐步排除的方法选择变量进入回归方程。结果:方程是显著的,调整后R方超0.95了,39个变量中有近10个变量都是显著的。
    奇怪的是,变量的vif值有的已经上百了。

      1. 数据是否适用于线性回归?
        在“最小二乘法的适用场景”部分,提到了线性回归矩阵的样本个数m和参数n关系的要求,需要根据参数选取不同变种。线性回归作为一个目的,不存在“适用”一说。
        针对多元线性回归中的多重共线性问题,可以采用岭回归、主成分分析和偏最小二乘回归来解决
      2. R2和VIF
        VIF = 1 / (1 – R方)。这里的R方是排除对应变量计算得到的,和方程的R方不同。
      3. 逐步排除
        我不太清楚这部分,自己看相关资料吧。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注