斯坦福大学公开课机器学习课程（Andrew Ng）三欠拟合与过拟合

概要

本节课的主要内容有：

1、欠拟合与过拟合

2、  局部加权回归

3、   最小二乘法的概率解释

4、  Logistic回归

5、  感知器算法

一、欠拟合与过拟合

       在机器学习中，通常需要选择某种算法来对数据进行预测，而过拟合与欠拟合就是描述对数据的预测与真实数据之间的拟合程度。

例如上次课的例子中，用x1表示房间大小。通过线性回归，在横轴为房间大小，纵轴为价格的图中，画出拟合曲线。回归的曲线方程为：,如下图：

如果再增加特征集合，比如：x1表示房子大小，x2表示房子大小的平方，使用相同的算法，拟合得到一个二次函数，则会在图中形成一个抛物线，即：

如果特征集合一直增加，得到的曲线就会越接近真实的数据；如果特征集合过少，得到的预测可能就会偏离真实数据。

那是否特征集合越多越好呢？答案是否定的。因为特征集合越多，虽然本次数据拟合的很好，但却 失了一般性。即它可能只对这一组数据拟合的很好，而对于其他的数据则拟合很差。

总结：

过拟合就是特征集过大，对某一组数据拟合程度太高， 以至于失了一般性。

欠拟合就是特征集过小，对某一组数据拟合程度太低，描述不出其应有的特点。

参数学习算法（parametric learning algorithm）

定义：参数学习算法是一类有固定数目参数，以用来进行数据拟合的算法。设该固定的参数集合为。线性回归即使参数学习算法的一个例子

非参数学习算法（Non-parametric learning algorithm）

定义：一个参数数量会随m（训练集大小）增长的算法。通常定义为参数数量随m线性增长。换句话说，就是算法所需要的东西会随着训练集合线性增长，算法的维持是基于整个训练集合的，即使是在学习以后。接下来要讨论的局部加权回归即属于此类。

二、局部加权回归

       局部加权回归算法是对线性回归的拓展，当目标假设是线性模型时，使用线性回归自热能拟合的很好，但如果目标假设不是线性模型，比如忽上忽下的函数，这是线性模型就拟合的很差。为了解决这个问题我们在预测一个值时，选择和这个点相近的点而不是全部的点做线性回归。基于这个思想就有了局部加权回归。

对于局部加权回归，当要处理x时：

1)       检查数据集合，并且只考虑位于x周围的固定区域内的数据点

2)       对这个区域内的点做线性回归，拟合出一条直线

3)       根据这条拟合直线对x的输出，作为算法返回的结果

局部加权回归它的目标函数是加权的最小二乘法。如下：

其中w是权值，它的范围是0-1，当离要预测点越远时，权值越小，否则较大。即使得里的较远的点对预测点影响较小，离得较近的点对预测点影响较大。

w可以有很多选择，一个比较好的选择是下面这个函数：

这个函数具有上面所描述的w的性质。虽然它的形状和高斯分布有些相似，但不是高斯分布。

  被称作波长函数，它控制了权值随距离下降的速率。它越小，钟形越窄，w衰减的很快；它越大，衰减的就越慢。

局部加权回归的问题：

     由于每次进行预测都要根据训练集拟合曲线，若训练集太大，每次进行预测的用到的训练集就会变得很大，Andrew Moore的关于KD-tree的算法可以对该问题进行优化。

三、最小二乘法的概率解释

在线性回归中，为什么选择最小二乘作为计算参数的指标，使得假设预测出的值和真正y值之间面积的平方最小化？

我们提供一组假设，证明在这组假设下最小二乘是有意义的，但是这组假设不唯一，还有其他很多方法可以证明其有意义。

（1）      假设1：

假设输入与输出为线性函数关系，表示为：

其中，为误差项，这个参数可以理解为对未建模效应的捕获，如果还有其他特征，这个误差项表示了一种我们没有捕获的特征，或者看成一种随机的噪声。

（2）假设2：

服从某个概率分布，如高斯分布（正态分布）：

表示一个均值是0，方差是的高斯分布。

为什么误差会服从高斯分布？这是因为影响误差的因素有很多，这些因素都是随机分布，根据中心极限定理，许多独立随机变量的和趋向于正态分布，所以假设二是合理的。还有就是选择高斯分布便与数学处理。

高斯分布的概率密度函数(u=0)：

当给定参数时（把(3)式带入(5)式）， 上式即变为：

注意：这里的p(y(i)|x(i);θ) 并不是表示条件概率，而表示的是：在给定x(i)的情况下，并有参数向量θ  时，y(i)的概率。

即并不是一个随机变量，而是一个尝试估计的值，就是说它本身是一个常量，只不过我们不知道它的值，所以上式读作“给定x(i)以为参数的y(i)的概率服从高斯分布。
（3）假设3：

对于各个样例的误差，他们是IID（independently and identically distributed独立同分布）随机变量。

这样就可以得到似然函数：

最大似然估计：选取使样本出现可能性最大化。

为什么要求概率密度的最大值：我的理解是，对于同样长的区间，越靠近概率密度大的区间，真实值越有可能落在这个区间内，所以应该使你的预测值落尽可能的在概率密度大的区间内。

对于公式（7）找它的最大值，可以似然函数取对数，自然数为底。将求似然函数最大值的问题转变为求平方和最小值。（下式中的log或许更应该为ln，不过结果并没有错误）

上式两个加项，前一项为常数。所以，使似然函数最大，就是使后一项最小，即：

这一项就是上一课中提到的，由此得证。即之前的最小二乘法计算参数，实际上是假设了误差项满足高斯分布，且独立同分布的情况，使似然最大化来计算参数

四、Logistic回归

       这是我们要学习的第一个分类算法。之前的回归问题尝试预测的变量y是连续变量，在这个分类算法中，变量y是离散的，y只取{0,1}两个值。

看下面的一个例子

如果y的取值只有0和1，训练集画出来这这个样子（先没有绿框中的点），我们用线性回归得到1号直线，如果认为模拟直线的取值小于0.5时则预测值就为0，如果模拟直线的取值大于0.5时预测值就为1，感觉还不错。但是将绿框中的点加入后，线性回归得到的直线2，就显得不是很完美了。经过大量的实验证明，线性回归不适合这种训练集。那么怎么解决这个问题呢？

为了解决上面的问题，我们提出来了一种新的回归模型：

其中g的函数原型为：

g函数一般被称为logistic函数，图像如下：

可以看出当z很小时，g(z)趋于0，z很大时，g(z)趋于1，z=0时，g(z)=0.5

给定一个x,设y=1和y=0的概率分别为：

将上述两个式子合并，可以得到如下式子：

这里还是利用最大似然估计的方法去求参数，构造似然函数如下：

对似然函数取对数得：

最大似然估计就是要让L(θ)  达到最大值时，求参数的值。我们前面说过梯度下降法，它是目标函数取最小值时，求参数的值。我们在这里就可以利用相同的想法，进行梯度上升，那么对应的目标函数就是取最大值的情况。更新规则如下：

求梯度下降导数的做法和上一篇中的一样，即先假设有一个样例，这是导数的解法如下：

                 

然后在推广到多个样例：

这里公式18与上一节中最小二乘法的形式一样，但实际上是不一样的，因为函数h不一样。但这并不是巧合，几乎可以说是一种通用的规则，即只要你用梯度下降算法，更新规则都是这种形式。

总结：逻辑回归，和线性回归其本质思想上是一致的。都是利用概率的思想，把我们的估计值当成一个随机变量，我们的训练集就是一组抽样。之后再利用最大似然估计，求其中的参数。当其中的参数求出来后，我们也就得到了回归方程，就可以进行预测或者其他工作了。

五、感知器算法

        在logistic方法中，g(z)会生成[0,1]之间的小数，但如何是g(z)只生成0或1？感知器算法是对逻辑回归的强行约束，使得函数值取0和1。定义形式如下：

同样的我们假设hθ(x)=g(θTx),在利用梯度上升的思想计算参数θ向量。整个推导过程和逻辑回归一样，最终结果如下：

尽管看起来和之前的学习算法类似，但感知器算法是一种非常简便的学习算法，临界值和输出只能是0或1，是比logistic更简单的算法。感知器算法是人工神经网络的基础，后续讲到学习理论中，会将其作为分析的起点。

参考：

斯坦福ML公开课笔记

http://blog.****.net/maverick1990/article/details/11721453

http://blog.****.net/xiaocainiaodeboke/article/details/50382794