最小二乘法背后的秘密

最小二乘法背后的秘密

还记得最早接触最小二乘法是在学习高中数学的时候,直观上觉得这个方法是可以得到一条拟合直线的,高中数学追求计算,因此对这一部分一带而过。现在想想,还是不求甚解啊。这里提出本文要阐述的几个问题:

  1. 学完线性代数后,如何利用矩阵梯度得到理论拟合直线的权重
  2. 如何从线性代数的投影角度思考最小二乘法
  3. 为什么最小二乘法得到的直线是最优的,还有没有更好的直线
  4. 正则项的由来

1. 线性代数表示

在学习线性代数之前,或者说高中数学,我们求解最小二乘法时,一般只有两个变量 \(x\)\(y\)。但学完线性代数后,我们应该用向量化的思路来思考之前相同的问题,即输入的是向量 \(\mathbf {x}\) (\(n\) 维列向量,表示 \(n\) 个未知数,也叫 \(n\) 个特征),输出的是标量 \(y\) ,表示预测的结果

那么问题就变成了如下问题:

输入: \((\mathbf {x}^{[k]}, y^{[k]}), (k=1, 2, \ldots, m), \mathbf {x}^{[k]} \in \mathbb {R}^n\) ,即 \(n\) 维列向量, \(y^{[k]}\) 是标量

问题: 找到 系数向量 \(\pmb {\theta}\) (每个未知数的权重和偏置), \(\pmb {\theta} \in \mathbb {R}^n\) ,它对应如下直线: \[
\hat y = \mathbf {x}^T \pmb {\theta} = x_1 \theta_1 + \cdots + x_n \theta_n, \quad 其中 \; x_1 = 1
\]

限制条件: \(\hat y\)\(y\) 必须满足最小平方误差 (least square root) \[
\min_{\pmb {\theta}} E = \sum_{k=1}^{m} (\hat y^{[k]} – y^{[k]})^2 = \sum_{k=1}^{m} ((\mathbf {x}^{[k]})^{T} \pmb {\theta} – y^{[k]})^2
\]

我们构造这样的矩阵 \(A\), \(A\) 的每一行是每个输入列向量 \(\mathbf {x}^{[k]}\) 的转置 \((\mathbf {x}^{[k]})^{T}\) \[
A =
\begin {bmatrix}
— & (\mathbf {x}^{[1]})^{T} & — \\
— & (\mathbf {x}^{[2]})^{T} & — \\
& \vdots & \\
— & (\mathbf {x}^{[m]})^{T} & — \\
\end {bmatrix}
\]

于是 \(A\) 的维度为 \(m \times n\), \(m\) 个输入样本,\(n\) 个特征 (未知数)

输出 \(y_i (i = 1, 2, \ldots, m)\) 合并一起组成列向量 \(\mathbf {y}\) 的格式, \(\mathbf {y} \in \mathbb {R}^m\)

利用向量长度的定义公式,可以将累计平方误差公式表示为: \[
E(\pmb {\theta}) = \vert \vert A \pmb {\theta} – \mathbf {y} \vert \vert ^2
\]

1.1 矩阵梯度计算

利用矩阵梯度可以直接找到我们需要的 \(\pmb {\theta}\) ,使得 \(E(\pmb {\theta})\) 最小

\(E(\pmb {\theta})\) 展开如下: \[
\begin {align}
E(\pmb {\theta}) = ||A \pmb {\theta} – \mathbf {y}||^2 &= (A \pmb {\theta} – \mathbf {y})^T (A \pmb {\theta} – \mathbf {y}) \\
&= (\pmb {\theta}^TA^T – \mathbf {y}^T)(A \pmb {\theta} – \mathbf {y}) \\
&= \pmb {\theta}^TA^T A \pmb {\theta} – \pmb {\theta}^TA^T\mathbf {y} – \mathbf {y}^TA \pmb {\theta} + \mathbf {y}^T \mathbf {y}
\end {align}
\]

\(\min E(\pmb {\theta})\) 对应的 \(\pmb {\theta}\),实际上是求 \(\cfrac { d E(\pmb {\theta})} {d \pmb {\theta}} = \mathbf {0}\) 对应的 \(\pmb {\theta}\)

根据矩阵梯度公式: \[
\cfrac { d \mathbf {x}^T \mathbf {A}\mathbf {x}} {d \mathbf {x}} = 2 \mathbf {x}^T (\mathbf {A}+\mathbf {A}^T)
\]

可以得到:

\[
\begin {align}
\cfrac {d E(\pmb {\theta})} {d \pmb {\theta}} &= \pmb {\theta}^T (A^T A + A^TA) – (A^T \mathbf {y})^T – (\mathbf {y}^T A) + \mathbf {0} \\
&= 2 \pmb {\theta}^T A^T A – 2 \mathbf {y}^T A \\
& = \mathbf {0}
\end {align}
\]

即:

\[
A^T A \pmb {\theta} = A^T\mathbf {y}
\]

如果 \(A^T A\) 非奇异,可以得到:

\[
\pmb {\theta} = (A^T A)^{-1} A^T \mathbf {y}
\]

这也是吴恩达老师在 “Machine Learning” 直接给出的公式

其实 \(A^TA\) 非奇异等价于 \(A\) 列满秩,感兴趣的可以看我的其他博客

1.2 投影定理

从几何空间的角度思考,我们知道 \(n\) 维列向量和 \(n\) 维欧式空间的坐标点是一一映射的

\(\pmb {\theta} \in \mathbb {R}^n\)\(n\) 维坐标,而通过矩阵计算得到 \(A \pmb {\theta}\) 则是 \(m\) 维空间的一个坐标, 同时 \(\mathbf {y}\) 也是 \(m\) 维空间的一个点,它的坐标已经固定,由 \(m\) 个样本输入得到

从几何空间的角度看,计算累计平方误差 \(E(\pmb {\theta}) = \vert \vert A \pmb {\theta} – \mathbf {y} \vert \vert ^2\) 实际上就是计算坐标点 \(\mathbf {y}\)\(A \pmb {\theta}\) 的距离

于是最小误差 \(\min_{\pmb {\theta}} E\) 等价于 \(\mathbf {y}\)\(A \pmb {\theta}\) 的距离最短

学过矩阵的四个子空间的同学一定知道,尽管 \(\pmb {\theta} \in \mathbb {R}^n\) 是任意一个 \(n\) 维列向量,但实际上

经过矩阵乘法得到的 \(A \pmb {\theta}\) 并不能取 \(m\) 维空间的任意一点,它只能在 \(A\) 的列空间 \(C(A)\) 内 (因为 \(A \pmb {\theta}\)\(A\) 的列向量的线性组合,更详细证明可以看我的博客)

于是,上面的寻找距离最短等价于一个我们都熟悉的问题:

空间外的一点和空间内的一点,什么时候距离最短 ?

回答是: 沿着法向量的方向距离最短,下图中向量 \(\mathbf {e}\) 的长度就是最短距离

矩阵的左零空间和列空间互为补空间,于是:

\[
A^T \mathbf {e} = A^T (\mathbf {y} – A \pmb {\theta}) = \mathbf {0}
\]

我们得到和 1.1小节相同的结论:

\[
A^T A \pmb {\theta} = A^T\mathbf {y}
\]

如果 \(A^T A\) 非奇异,可以得到:

\[
\pmb {\theta} = (A^T A)^{-1} A^T \mathbf {y}
\]

其实这里的证明还得到一个附加结论:

如何获得一个向量在矩阵列空间的投影 ? 就是给你矩阵 \(A\) 和向量 \(\mathbf {y}\) ,要你求它的投影 \(A \pmb {\theta}\) ,

根据前面计算,

\[
A\pmb {\theta} = A (A^T A)^{-1} A^T \mathbf {y}
\]

于是 投影矩阵 \(P: \mathbf {y} \to A \pmb {\theta}\) 如下

\[
P = A (A^T A)^{-1} A^T
\]

2. 为什么最小二乘法是最优的

回答这个问题就要从统计学说起了。还有经典概率学派和贝叶斯学派的理论之争。

在经典统计学家看来,所有的事件都不是确定的,所谓的确定事件只是概率比较高而已。同样的,在他们看来,样本的输出 \(y\) 也并不是百分百确定的,它也是符合某种概率分布的,这种概率分布的输入是 \(\mathbf {x}\)

于是问题变成如下问题: 给你一组独立分布的样本,样本输入为 \(\mathbf {x}^{[k]}\) ,输出为 \(y^{[k]}\) (\(k=1,2,\ldots, m\)),给出输入,请找到最合适的条件概率分布来描述这组样本的输出,即概率分布 \(p(y \vert{\pmb{\theta}})\)。这样,当我给出一个新的样本输入 \(\mathbf {x}\) 时,输出值 \(\hat y = \mathbf {x}^T \pmb {\theta}\) 是最合理的,也就是概率最大的, 即 \(p(\hat y) = p(\mathbf {x}^T \pmb {\theta}) = \max p(y)\)

怎么找最合适的条件概率分布呢 ?

经典学派认为,我们先人为假定某个概率分布,我们要做的就是寻找最优的概率分布参数。

因为我们对样本输出的具体分布一无所知,最合理的概率分布就是高斯分布 !!

\[
p(y) = N(\hat y, \beta^{-1}) = N(\mathbf {x}^T \pmb {\theta}, \beta^{-1})
\]

如下图所示,我们通过直线拟合得到 \(\hat y = \mathbf {x}^T \pmb {\theta}​\) 是高斯分布的中心点 (自然它的概率就是最大的), \(\beta^{-1} = \sigma^2​\) 就是方差,表示分布的不确定程度

根据极大似然估计原理:

\[
\prod_{k=1}^m p(y^{[k]}\vert \pmb {\theta}) = \prod_{k=1}^m N\Big( y^{[k]} \vert (\mathbf {x}^{[k]})^T \pmb {\theta}, \beta^{-1} \Big)
\]

也就是说:

\[
p(y^{[k]}\vert \pmb {\theta}) = \sqrt { \cfrac {\beta}{2\pi} } \exp^{- \frac{\beta}{2} \big ( y^{[k]} – (\mathbf {x}^{[k]})^T \pmb {\theta} \big )^2 }
\]

极大似然就是要求上式的最大值所对应的参数。

自然,我们要取对数求导

\[
\sum_{k=1}^m \ln p(y^{[k]}\vert \pmb {\theta}) = – \frac{\beta}{2}\sum_{k=1}^m \big ( y^{[k]} – (\mathbf {x}^{[k]})^T \pmb {\theta} \big )^2 + \frac {M}{2} \ln \beta – \frac {M}{2} \ln (2 \pi)
\]

不知道你有没有看出来,

\[
\max \prod_{k=1}^m p(y^{[k]} \vert \pmb {\theta}) \Longleftrightarrow \max \sum_{k=1}^m \ln p(y^{[k]} \vert \pmb {\theta}) \Longleftrightarrow \min \sum_{k=1}^m \big ( y^{[k]} – (\mathbf {x}^{[k]})^T \pmb {\theta} \big )^2
\]

OK,是不是和最小二乘法一模一样 ?

3. 正则项的由来

经典概率学派认为输出是符合某种概率分布的,而分布的参数是固定的,我们可以通过极大似然法求得该参数。

但在贝叶斯学派眼中看来,分布的参数是不固定的,也是符合某种分布的,只是我们不知道而已。贝叶斯学派认为知识比结果重要,如果我们尽可能的收集信息,获得参数的先验分布以及它的似然条件概率分布,那么我们就可以得到后验分布

所谓后验分布,直观上说,就是我们对参数的已有经验加上 参数对结果的影响,我们就可以得到 结果

\[
p(\pmb{\theta} \vert y) = \cfrac {p(y \vert \pmb {\theta})p(\pmb {\theta})} {p(y) } = \cfrac {p(y \vert \pmb {\theta})p(\pmb {\theta})} {\sum_{\pmb {\theta}} p(y \vert \pmb {\theta})p(\pmb {\theta})}
\]

即:

\[
p(\pmb{\theta} \vert y) \propto p(y \vert \pmb {\theta})p(\pmb {\theta})
\]

经典概率学派认为的最大似然就是不考虑 \(p(\pmb {\theta})\) (因为 \(\pmb {\theta}\) 是固定的),利用似然概率分布最大得到对应的 \(\pmb {\theta}\)

而贝叶斯学派则认为: 最好的 \(\pmb {\theta}\) 只是概率 \(p(\pmb {\theta} \vert y)\) 最大对应的 \(\pmb {\theta}\) 而已

其实贝叶斯学派很难推广的一点就是: 如何得到 \(p(\pmb {\theta})\), 即如何得到参数的先验分布。

因为 \(\pmb {\theta} \in \mathbb {R}^n\) ,我们假设它符合 \(n\) 维高斯分布,中心为原点,协方差矩阵为对角阵 \(\alpha^{-1}I\) (\(\alpha\) 为未知参数),可以得到:

\[
p(\pmb {\theta}) = N(0, \alpha^{-1}I) = (\cfrac {\alpha}{2\pi})^{(M+1)/2} \exp ^{- \frac{\alpha}{2} \pmb {\theta}^T \pmb {\theta}}
\]

于是:

\[
\max p(\pmb{\theta} \vert y) \Longleftrightarrow \max p(y \vert \pmb {\theta})p(\pmb {\theta})
\]

结合先去的推导,取对数

\[
\sum_{k=1}^m \ln p(y^{[k]}\vert \pmb {\theta}) + \sum_{k=1}^m \ln p(\pmb {\theta}) = – \frac{\beta}{2}\sum_{k=1}^m \big ( y^{[k]} – (\mathbf {x}^{[k]})^T \pmb {\theta} \big )^2 – \frac {\alpha} {2} \pmb {\theta}^T \pmb {\theta} + \cdots
\]

后面省略号的部分和 \(\pmb {\theta}\) 无关,故省略。

我们要求的,就是:

\[
\min \frac{\beta}{2}\sum_{k=1}^m \big ( y^{[k]} – (\mathbf {x}^{[k]})^T \pmb {\theta} \big )^2 + \frac {\alpha} {2} \pmb {\theta}^T \pmb {\theta}
\]

后面就是我们经常看到的 L2 正则表达式了。

也就是说,所谓的正则过拟合,实际上是假设了贝叶斯条件概率的先验知识,从而让 \(\pmb {\theta}\) 的后验概率分布更准确

发表评论

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d 博主赞过: