The problem of overfitting

在前面的Linear Regression和Logistic Regression中，给定一个数据集，我们都希望找到一条线去拟合数据或是对数据进行合理有效的分类。

在线性回归预测房价的例子中，第一次我们用一条直线来拟合数据，但处于一直上升的趋势，实际中房价应该会逐步趋于平稳，显然不符合实际，我们说这个拟合模型是“欠拟合的”或是“高偏差的”；第二次我们使用一条曲线拟合数据集，拟合效果理想且更加符合实际的情况，我们认为这是一个很好的模型；第三次我们使用了更高次项的曲线拟合，看起来在现有的数据下，它更好的拟合了每一个点，但去无法泛化到后面的预测，我们无法根据它预测输出，称它是过度拟合（Overfitting）或是高偏差的。

从图中我们呢可以看出过度拟合的含义为：如果我们有太多的特征，所做的假设也许会很好的拟合数据集，即代价函数的值几乎为零，但是对于新数据的泛化效果差，也就是说我们无法用它来预测新的数据。

在Logistic regression中，第一次我们使用直线进行分类，分类的效果直观上看上去就不甚理想；第二次我们使用曲线取分类，效果要好很多；第三次我们尽可能的去讲不同的类区分开，函数也更加的复杂，这时就属于过度拟合了。

那么过度拟合我们通常如何解决呢？

（1）减少特征的数量：我们可以手动的选择需要保留的feature或是修改选择算法；
（2）正则化：我们可以保留所有的feature，但是需减小参数的数量级；留下所有的feature，但对于部分feature定义其parameter非常小。

Cost function

在前面的两种算法中我们都涉及到一种重要的方法：梯度下降法，其中有一个很重要的部分就是代价函数的概念，尽管看起来差不多，但由于假设的不同，实际上是两个完全不同的东西。

在过度拟合的方程中，三次项和四次项的存在，使得我们要想最小化代价函数，当x很大时，比如这里的1000（只是随意取得一个很大的数），我们就需要θ3，θ4相当的小，以至于接近于零，这样我们就可以取得最小代价。

正则化的方式如下：

我们需要在代价函数中加入惩罚项，修改后的代价函数如图所示，这样我们就可以减小各参数带来的代价，如果我们不知道对那些特征实现惩罚，就对所有特征惩罚，然后让相关软件选择惩罚的程度。

其中λ是正则化参数，但是如果λ很大时，就会导致除了θ0之外的parameter接近于0，这时拟合线就相当于一条水平于x轴的线，拟合效果就会很差。

Regularized linear regression

对于线性回归的过度拟合问题，正则化的线性回归的公式为：

我们的目标就是找到最小代价，所使用的梯度下降过程为：

θ0我们独立出来，其他的参数依次迭代更新，简化后的公式为，可以看出， 梯度下降算法变在于，每次都原有更新规则基础上令 基础上令 θ 值减少了一个额外的值。
同样我们也可以使用正则方程

公式为：
对于不可逆的情况，我们同样也可以求出正确的值。

regularized logistic regression

对于logistic regression我们同样需要设置惩罚项来避免过度拟合，梯度下降过程为：

记住：这里的h函数不同于线性回归中的h函数！
至于更高级的算法

图中，jval表示cost function 表达式，其中最后一项是参数θ的惩罚项；下面是对各θj求导的梯度，其中θ0没有在惩罚项中，因此gradient不变，θ1~θn分别多了一项(λ/m)*θj；

至此，regularization可以解决linear和logistic的overfitting regression问题了~

参考：吴恩达老师的机器学习课程
黄海广的机器学习笔记
Stanford机器学习—第三讲. 逻辑回归和过拟合问题的解决 logistic Regression & Regularization