过度拟合

考虑如下的一个数据集的三种拟合曲线

图1采用$ y = θ_0 + θ_1x $的直线作为假设函数，然而训练数据集看起来并不适合直线，所以假设函数看起来不太合适。图2采用$ y = θ_0 + θ_1x + θ_2x^2 $，我们得到了一个拟合度更好的曲线。观察图3，貌似的，通过添加高阶特征，我们获得了更好的拟合。然而，如果加入过多的特征，尽管可以获得“完美”的拟合度，但是却不是一个好的预测函数。我们称图1叫拟合不足(underfitting)，图3为过度拟合(overfitting)。

拟合不足或者叫高偏差(high bias)，导致假设函数不能很好的表示数据的趋势，这通常是由于函数过于简单，或者特征太少。另一个极端，过度拟合虽然可以“很好”拟合训练数据集，但是却不能很好的预测新数据，这可能是由于假设函数过于复杂，引入了过多的曲线和转角。

无论是线性回归还是逻辑回归都有这种情况，下面是逻辑回归的例子：

有两种主要的解决方案：

1. 减少特性的数量：人工去掉一些不需要的特性或者使用模型选择算法。
2. 正则化代价函数：保留特征，但是设法减小θ，如果有很多权重不大的特征，正则化很适合。

正则化的代价函数

正则化(regularized)的基本思想是：如果想要降低多项式中某些项的比重，那么就提升这些项系数在代价函数中的比重。例如，我们想让下面这个多项式更接近二次曲线：

$$ θ_0 + θ_1x + θ_2x^2 + θ_3x^3 + θ_4x^4 $$

如果$ θ_3 、θ_4 $都为0，那么多项式就是个二次函数曲线。不过，我们不需要完全去掉这两个高阶项，只要让$ θ_3 、θ_4 $减小，甚至趋向于0即可。设置如下代价函数：

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

观察这个代价函数，我们在原先的代价函数中，增加两个额外的项，这两项会让过大的$ θ_3 、θ_4 $得到惩罚。因此，为了让代价函数的结果最小，算法会自动地选择比较小的$ θ_3 、θ_4 $，甚至接近0。从而得到几乎是接近二次函数的假设函数。

我们只要将所有的θ都添加进代价函数，就实现了正则化的代价函数：

$$ min_\theta\ \frac{1}{2m}\sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2 + λ\sum_{j=1}^nθ_j^2 $$

这里的λ是正则化参数，可以想象，如果λ过大，最终的假设函数会趋向于常数项$ θ_0 $，从而造成拟合不足；而过小的λ，会使得正则化无效，造成过度拟合。

用作业中的一个实际的例子来观察一下λ对拟合度的影响。以分类问题为例，下图是一个二值化分类的训练样本：

这个样本有两个变量microchip Test 1和microchip Test 2，分别记作x_1和x_2。我们首先将两个特征映射成28个特征（通过将两个参数进行高阶组合）：

$$ mapFeature(x)=\begin{bmatrix}1 \newline x_1 \newline x_2 \newline x_1^2 \newline x_1x_2 \newline x_2^2 \newline x_1^3 \newline \vdots \newline x_1x_2^5 \newline x_2^6\end{bmatrix} $$

如果λ=0，得到如下决策边界，显然这个决策边界有过度拟合(overfitting)之嫌：

如果λ=1，得到如下决策边界，看起来这个决策边界比较合适：

如果λ=100，得到如下决策边界，看起来这个决策边界又拟合不足(underfitting)：

梯度下降推导

前面给出了引入正则项的代价函数：

$$ min_\theta\ \frac{1}{2m}\sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2 + λ\sum_{j=1}^nθ_j^2 $$

观察发现，正则化的代价函数引入的额外项$ λ\sum_{j=1}^nθ_j^2 $，是从j=1开始的（即不惩罚常数项），所以我们的梯度下降算法公式推导需要区分j=0和j=1两种情况：

$$ \begin{align*} & \text{Repeat}\ \lbrace \newline & \ \ \ \ \theta_0 := \theta_0 - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \newline & \ \ \ \ \theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right] &\ \ \ \ \ \ \ \ \ \ j \in \lbrace 1,2...n\rbrace\newline & \rbrace \end{align*} $$

上述公式的第二部分可以改写成：

$$ θ_j := θ_j(1 - α\frac{λ}{m}) - α\frac{1}{m}\sum_{i=1}^m(h_θ(x^{(i)}) - y^{(i)})x_j^{(i)} $$

上式的第一项$ 1 - α\frac{λ}{m} < 1 $，这相当于在原来的基础上又对$ θ_j $作了一定比例的缩小。

逻辑回归代码总结

采用fminunc算法的逻辑回归代价函数实现如下，sigmoid函数相当于g(z)：

function [J,grad] = costFunction(theta,X,y)
    m = length(y); % number of training examples
    J = 0;
    grad = zeros(size(theta));
    J = (1 / m) * ( (-1 .* y') * log(sigmoid((X * theta))) - (1 - y)' * log(1 - sigmoid((X * theta))) );
    grad = ((1 / m) .* sum((sigmoid((X * theta)) - y) .* X))';
end

调用fminunc：

options = optimset('Gradobj','on','MaxIter',400);
%  Run fminunc to obtain the optimal theta
%  This function will return theta and the cost 
[theta,cost] = ...
    fminunc(@(t)(costFunction(t,y)),initial_theta,options);

正则化的代价函数，这里需要注意的是正则项中是不对$ \theta_0 $惩罚的：

function [J,grad] = costFunctionReg(theta,y,lambda)
    m = length(y); % number of training examples
    J = 0;
    grad = zeros(size(theta));

    theta_2 = theta;
    theta_2(1) = 0;
    J = (1 / m) * ( (-1 .* y') * log(sigmoid((X * theta))) - (1 - y)' * log(1 - sigmoid((X * theta))) ) + sum(theta_2.^2) * lambda / (2 * m);
    grad = ( (1 / m) .* sum((sigmoid((X * theta)) - y) .* X) + ( (lambda / m) .* theta_2' ) )';
end