CS229 Lesson 3 欠拟合与过拟合的概念

课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了局部加权回归，logistic回归以及感知机。

3. 概率解释

当遇到回归问题时，为什么线性回归，特别是为什么最小二乘成本函数$J$是合理的选择呢？在本节中，我们将给出一组概率假设，在该假设下，最小二乘回归是作为一种非常自然的算法推导出的。

让我们假设目标变量和输入通过如下等式关联起来

$y^{(i)} =\theta^T x^{(i)} +\epsilon^{(i)}$

其中$\epsilon^{(i)}$是一个误差项，可以捕获不在模型中的影响（例如，如果有一些特征与预测住房价格非常相关，但我们没将其考虑在回归模型中）或随机噪声。让我们进一步假设$\epsilon^{(i)}$是IID（独立同分布）且服从零均值，方差为$\sigma^2$的高斯分布（也称为正态分布）。我们可以把这个假设写成“$\epsilon^{(i)}\sim \mathcal N(0,\sigma^2)$”。即，$\epsilon^{(i)}$的概率密度由下式给出：

$p(\epsilon^{(i)}) =\frac{1}{\sqrt{2\pi}\sigma} \exp \Big( -\frac{(\epsilon^{(i)})^2}{2\sigma^2} \Big)$

这意味着

$p(y^{(i)}|x^{(i)};\theta) =\frac{1}{\sqrt{2\pi}\sigma} \exp \Big( -\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2} \Big)$

符号“$p(y^{(i)}|x^{(i)};\theta)$”表示这是给定$x^{(i)}$并由$θ$参数化的$y^{(i)}$的分布。注意，我们不应该对$θ$取条件概率（“ $p(y^{(i)}|x^{(i)},\theta)$ ”），因为$θ$不是随机变量。我们也可以将$y^{(i)}$的分布写为$y^{(i)}|x^{(i)};\theta\sim \mathcal N(\theta^T x^{(i)},\sigma^2)$。

给定$X$（设计矩阵，其中包含所有的$x^{(i)}$）和$θ$，$y^{(i)}$的分布是什么？数据的概率由$p(\vec y | X;θ)$给出。对于固定值$θ$，该量通常被视为$\vec y$（或者可能是$X$）的函数。当我们希望明确地将其视为$θ$的函数时，我们将其称为似然函数：

$L(\theta)=L(θ;X, \vec y) = p( \vec y|X; θ)$

注意，通过对$\epsilon^{(i)}$的独立假设（以及给定$x^{(i)}$的$y^{(i)}$），这也可以写为

$\begin{aligned} L(\theta) &= \prod_{i=1}^m p(y^{(i)}|x^{(i)};\theta) \\ &=\prod_{i=1}^m\frac{1}{\sqrt{2\pi}\sigma} \exp \Big( -\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2} \Big) \end{aligned}$

现在，给定这个与$y^{(i)} $和$x^{(i)}$相关的概率模型，选择我们对参数$θ$的最佳猜测的合理方法是什么？ 最大似然原理说我们应该选择使数据概率最高的$θ$。即，我们应该选择$θ$来最大化$L(\theta)$。

为了运算方便，实际中我们选择最大化对数似然函数$ℓ(θ)$：

$\begin{aligned} ℓ(θ)&=\log L(\theta)\\ &=\log \prod_{i=1}^m\frac{1}{\sqrt{2\pi}\sigma} \exp \Big(-\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2}\Big) \\ &=\sum_{i=1}^m \log\frac{1}{\sqrt{2\pi}\sigma} \exp \Big(-\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2}\Big) \\ &=m\log \frac{1}{\sqrt{2\pi}\sigma} -\frac 1 {\sigma^2}. \frac 12 \sum_{i=1}^m (y^{(i)}-\theta^T x^{(i)})^2 \end{aligned}$

因此，最大化$ℓ(θ)$与最小化下式的答案相同

$\frac 12 \sum_{i=1}^m (y^{(i)}-\theta^T x^{(i)})^2$

上式即为$J(θ)$，我们最初的最小二乘成本函数。

总结一下：在先前对数据的概率假设下，最小二乘回归对应于找到$θ$的最大似然估计。因此，在在这些假设下，最小二乘回归可以证明是一种非常自然的方法，只是进行最大似然估计。（但请注意，概率假设绝不是必要的，因为最小二乘法是一个完美的合理程序，并且可能——实际上还有其他自然假设也可以用来证明它的合理性。）

还要注意，在我们之前的讨论中，我们对$θ$的最终选择并不依赖于$\sigma^2$的值，实际上即使$\sigma^2$未知，我们也会得到相同的结果。当我们谈论指数族和广义线性模型时，我们将在以后再次使用这一事实。

4. 局部加权线性回归

考虑从$x\in \mathbb R$预测$y$的问题。下面最左边的图显示了将$y =θ_0+θ_1x$拟合到数据集的结果。我们看到数据实际上不是直线，因此拟合不是很好。

相反，如果我们添加了额外的特征$x^2$，并且拟合$y =θ_0+θ_1x+θ_2x^2$，那么我们可以拟合的效果会稍微好些（见中图）。似乎我们添加的特征越多越好。然而，添加太多特征也存在危险：最右边的图是拟合5阶多项式$y=\sum_{j=0}^5 \theta_j x^j$的结果。我们看到，即使拟合曲线完美地通过数据，我们也不会期望这是一个非常好的预测器。在没有正式定义这些术语的含义的情况下，我们会说左边的图显示了欠拟合的例子——其中数据清楚地显示了模型未捕获的结构，右边的图是过拟合的一个例子。（在本课程的后面，当我们谈论学习理论时，我们会将这些概念中的某些概念形式化，并且还要更仔细地定义假设是好还是坏的含义。）

如前所述，并且如上面的例子所示，特征的选择对于确保学习算法的良好性能很重要。（当我们谈论模型选择时，我们还将看到用于自动选择一组良好特征的算法。）在本节中，让我们简单地谈谈局部加权线性回归（LWR）算法，这里假设有足够的训练数据，使得特征选择不那么重要。

在原始线性回归算法中，为了在查询点$x$进行预测（即计算$h(x)$），我们将：

1.选择$\theta$最小化$\sum_i (y^{(i)}-\theta^Tx^{(i)})^2$
2.输出$\theta^T x$

相反，局部加权线性回归算法执行以下操作：

1.选择$\theta$最小化$\sum_i w^{(i)}(y^{(i)}-\theta^Tx^{(i)})^2$
2.$\theta^T x$

这里，$w^{(i)}$是非负权重。直观地，如果$w^{(i)}$对于特定的$i$很大，那么在选择$θ$时，我们将努力使$(y^{(i)}-\theta^Tx^{(i)})^2$变小。如果$w^{(i)}$很小，则拟合中几乎忽略$(y^{(i)}-\theta^Tx^{(i)})^2$误差项。

权重的一个相当标准的选择是

$w^{(i)}= \exp \Big(-\frac{(x^{(i)}-x)^2}{2\tau^2}\Big)$

参数$\tau$控制训练样本的权重随着其$x^{(i)}$距查询点$x$的距离而下降的速度；$\tau$称为带宽参数。

局部加权线性回归是我们看到的非参数算法的第一个例子。我们之前看到的（未加权）线性回归算法被称为参数学习算法，因为它具有固定的，有限数量的参数（$\theta$），这些参数由数据拟合。一旦我们拟合了$θ_i$并将它们存储起来，我们就不再需要保留训练数据来做出未来的预测。相反，为了使用局部加权线性回归进行预测，我们需要保持整个训练集。术语“非参数”（粗略地）指的是我们为了表示假设$h$而需要保留的东西量随着训练集的大小线性增长的事实。

Part II 分类和logistic回归

我们现在谈谈分类问题。这就像回归问题，除了我们现在想要预测的值$y$只取少量离散值。现在，我们将关注二元分类问题，其中$y$只取两个值$0$和$1$。（我们在这里所说的大多数内容也将推广到多类情况。）例如，如果我们正在尝试为电子邮件构建垃圾邮件分类器，则$x^{(i)} $可能是电子邮件的某些特征，如果是垃圾邮件，则$y$为$1$，否则为$0$。 $0$也称为负类，$1$表示正类，它们有时也用符号“ - ”和“+”表示。给定$x^{(i)} $，相应的$y^{(i)} $也称为训练样本的标签。

5. Logistic回归

我们可以忽略$y$是离散值的事实来处理分类问题，并使用我们的旧线性回归算法来尝试预测给定$x$的$y$。但是，很容易构造此方法的效果非常差的例子。直觉上，当我们知道$y\in \{0,1\}$时，$h(x)$取大于$1$或小于$0$的值也没有意义。

为了解决这个问题，让我们改变假设$h(x)$的形式。我们选择

$h_{\theta}(x)=g(\theta^T x)= \frac{1}{1+e^{-\theta^T x}}$

其中

$g(z) =\frac 1 {1+e^{-z}}$

被称为logistic函数或sigmoid函数。这是$g(z)$的图像：

注意，当$z→∞$时$g(z)$趋近于$1$，并且当$z→-∞$时$g(z)$趋近于$0$。此外，$g(z)$和$h(x)$的值总是在$0$和$1$之间。如前所述，我们保持$x_0 = 1$的约定，所以$θ^Tx=\theta_0 +\sum_{j=1}^n \theta_j x_j$。

现在，让我们选择上述$g$。实际中也可以使用从$0$到$1$平滑增加的其他函数，但由于我们稍后会看到的几个原因（当我们谈论GLM时，以及当我们谈论生成学习算法时），logistic函数是一个相当自然的选择。在继续之前，这里是sigmoid函数导数的有用性质，我们将其写为$g’$：

$\begin{aligned} g′(z)& = \frac{d}{dz}\frac 1 {1 + e^{−z}}\\ &= \frac 1 {(1 + e^{−z})^2}(e^{−z})\\ &=\frac 1 {(1 + e^{−z})} . \Big( 1- \frac 1{(1 + e^{−z})}\Big)\\ &=g(z)(1-g(z)) \end{aligned}$

因此，给定logistic回归模型，我们如何拟合$θ$呢？同最小二乘回归在一组假设下可以作为最大似然估计得出，让我们用一组概率假设赋予我们的分类模型，然后通过最大似然拟合参数。

让我们假设

$\begin{aligned} P(y=1|x;\theta)& =h_{\theta}(x)\\ P(y=0|x;\theta)& =1-h_{\theta}(x) \end{aligned}$

请注意，这可以简写为

$p(y|x;\theta)=(h_{\theta}(x))^y(1-h_{\theta}(x))^{1-y}$

假设$m$个训练样本是独立生成的，我们可以将参数的似然性写下来

$\begin{aligned} L(\theta)&= p(\vec y|X;\theta) \\ &=\prod_{i=1}^m p(y^{(i)}|x^{(i)};\theta) \\ &=\prod_{i=1}^m (h_{\theta}(x^{(i)}))^{y^{(i)}}(1-h_{\theta}(x^{(i)}))^{1-y^{(i)}} \end{aligned}$

和以前一样，最大化对数似然会更容易：

$\begin{aligned} ℓ(\theta) & =\log L(\theta)\\ &= \sum_{i=1}^m{y^{(i)}} \log h_{\theta}(x^{(i)})+({1-y^{(i)}}) \log(1-h_{\theta}(x^{(i)})) \end{aligned}$

我们如何最大化似然？与我们在线性回归情况下的推导类似，我们可以使用梯度上升。以矢量符号表示，因此我们的更新为$\theta:= \theta+\alpha \nabla_{\theta}ℓ(\theta)$。（注意更新公式中是正号而不是负号，因为我们现在是最大化而不是最小化函数。）让我们从一个训练样本$(x,y)$开始，通过求导来推导随机梯度上升规则：

$\begin{aligned} \frac{\partial}{\partial \theta_j}ℓ(\theta) &=\Big ( y\frac 1{g(\theta^Tx) }-(1-y) \frac 1 {1-g(\theta^Tx) }\Big) \frac{\partial}{\partial \theta_j} g(\theta^Tx)\\ &=\Big ( y\frac 1{g(\theta^Tx) }-(1-y) \frac 1 {1-g(\theta^Tx) }\Big) g(\theta^Tx)(1-g(\theta^Tx)) \frac{\partial}{\partial \theta_j}\theta^Tx\\ &=\big( y(1-g(\theta^Tx))-(1-y)g(\theta^Tx) \big)x_j \\ &=(y-h_{\theta}(x))x_j \end{aligned}$

上面的推导中，我们使用了$g’(z)=g(z)(1-g(z))$的事实。因此，我们得到了随机梯度上升规则

$\theta_j:=\theta_j + \alpha\big(y^{(i)}-h_{\theta}(x^{(i)})\big)x_j$

如果我们将其与LMS更新规则进行比较，我们会发现它们看起来相同；但这不是相同的算法，因为$h_{\theta}(x^{(i)})$现在被定义为$\theta^T x^{(i)}$的非线性函数。尽管如此，我们最终采用相同的更新规则来解决一个相当不同的算法和学习问题，这有点令人惊讶。这是巧合，还是有更深层次的原因呢？我们在获得GLM模型时会回答这个问题。

6. 题外话：感知机学习算法

我们现在简单地谈谈一个具有一定历史意义的算法，并且当我们谈论学习理论时我们也会回到这里。考虑修改logistic回归方法以“强制”它输出0或1。为此，将$g$的定义更改为阈值函数似乎很自然：

$g(z)=\begin{cases} 1 & 如果z\ge 0\\ 0 & 如果z<0 \end{cases}$

如果我们像以前那样取$h_{\theta}(x)=g(\theta^Tx)$，但是使用这个修改过的$g$的定义，并且如果我们使用更新规则

$\theta_j:=\theta_j + \alpha\big(y^{(i)}-h_{\theta}(x^{(i)})\big)x_j^{(i)}$

那么我们就有了感知机学习算法。

在20世纪60年代，这种“感知机”被认为是大脑中各个神经元如何工作的粗略模型。考虑到算法的简单性，当我们在本课程后面讨论学习理论时，它也将为我们的分析提供一个起点。但请注意，尽管感知器可能在美学上与我们所讨论的其他算法相似，但它实际上是一种与逻辑回归和最小二乘线性回归非常不同的算法类型；特别的，很难通过有意义的概率解释赋予感知机的预测，或者将感知机推导为最大似然估计算法。