过拟合（Overfitting）和正则化（Regularized）

在应用线性回归和逻辑回归去解决某些机器学习的实际应用时，它们可能会出现一种叫做“过度拟合”（Overfitting）的问题。这会使得学习的结果很糟糕。

什么是过拟合

用预测房价的线性回归的例子：

线性回归图表

最左边一张图片用一条直线来拟合数据，这种情况下随着x轴的变大，房价增长的幅度一直不变，这样的结果误差很大，这意味这该算法没有很好的拟合训练数据，
这种称之为 “欠拟合”；

中间一张图用的二次曲线来拟合数据，拟合情况良好，稍有偏差；

右边一张图用了四次项，拟合的更好，在图中，它贯穿了所有样本，但是它的曲线很扭曲，这不是一个很好的预测房价的模型，这称之为 “过拟合”；

定义

过拟合： 假如有很多特征值，且学习算法能够很好的拟合训练集，但是在新的样本上却表现的性能很差。

数据拟合有两个极端，当预测函数过于简单或者使用的相关特征值过少，就会出现欠拟合（高偏差high bias）的情况。
另一个极端，当函数过于复杂，使用的非常多的特征值，使得学习算法在训练样本上非常适合，但是不能推广到新的样本集上，这就是过拟合（高方差high variance）

过拟合问题除了出现在线性回归问题上，也会出现在逻辑回归上。

解决办法

减少特征值的数量
可以通过观察手动删掉一些特征值，或者用模型选择算法来达到目的。
正则化
保留所有特征值，但是减少参数 $\theta_j$ 的大小，因为似乎每个特征值都或多或少的在预测函数起了作用。

这两种方法的本质类似，就是弱化不必要的特征值，从而解决过拟合。

代价函数

假设线性回归的预测函数为：
$h(\theta) = \theta_0+\theta_1x+\theta_2x^2+\theta_3x^3+\theta_4x^4$

这是一个四次项的公式，通过上面的可以知道这是一个过拟合的预测函数，需要解决过拟合，需要忽略后面的三次和四次项，这要改一下代价函数：

$J(\theta) = \frac{1}{2m} \sum_{i=0}^m(h_\theta(x^{(i)})-y^{(i)})^2 +1000\cdot \theta_3^2 +1000\cdot \theta_4^2$

在原油的代价函数上我们添加了 $1000\cdot \theta_3^2$ 和 $1000\cdot \theta_4^2$ 这两个，为了使代价函数尽量小，我们就需要让 $\theta_3$ 和 $\theta_4$ 尽量小，接近于零。

这样就给了一个正则化的思路。将关联小的特征值的参数趋向于0，使得预测函数从过拟合的状态修正过来。

正则化后的代价函数为：
$J(\theta)= \frac{1}{2m} [\sum_{i=0}^m (h_\theta(x^{(i)})-y^{(i)})^2 + \lambda \sum_{j=1}^n\theta_j^2 ]$

其中 $\lambda$ 为正则化参数，为了平衡代价函数。 $\lambda$ 需要选择合适的值。

可以看到，在代价函数后面添加了 $\lambda \sum_{j=1}^n\theta_j^2$ 这一项。注意，这一项中的 $j$ 是从1到m的，因为 $x_0$ 固定为0，不需要修正，所以参数 $\theta_0$ ，不需要添加进来。

线性回归正则化

梯度下降算法：
重复 {
$\theta_0 = \theta_0-\alpha\frac{1}{m}\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$
$\theta_j = \theta_j -\alpha [\frac{1}{m}\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} +\frac{\lambda}{m}\theta_j ], j \in [1,2,3,...,n]$
}

同样的 $\theta_0$ 不需要修正

下面的式子可以稍作调整：
$\theta_j = \theta_j(1-\alpha\frac{\lambda}{m}) -\alpha\frac{1}{m}\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}, j \in [1,2,3,...,n]$

可以看出 $\theta_j$ 是在原来梯度下降的基础上又减去了 $\alpha\frac{\lambda}{m}\theta_j$

逻辑回归正则化

代价函数：
$J(\theta)=-\frac{1}{m} \sum_{i=1}^m [y^{(i)} \log(h_\theta(x^{(i)})) + (1-y^{(i)}) \log(1-h_\theta(x^{(i)}))] + \frac{\lambda}{2m} \sum_{j=1}^n \theta_j^2$

同样的 $\theta_0$ 不需要修正

它的梯度下降算法是：

重复 {
$\theta_0 = \theta_0-\alpha\frac{1}{m} \sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$
$\theta_j = \theta_j -\alpha[\frac{1}{m}\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} +\frac{\lambda}{m}\theta_j ], j \in [1,2,3,...,n]$
}