过度拟合
考虑如下的一个数据集的三种拟合曲线
图1采用$ y = θ_0 + θ_1x $的直线作为假设函数，然而训练数据集看起来并不适合直线，所以假设函数看起来不太合适。图2采用$ y = θ_0 + θ_1x + θ_2x^2 $，我们得到了一个拟合度更好的曲线。观察图3，貌似的，通过添加高阶特征，我们获得了更好的拟合。然而，如果加入过多的特征，尽管可以获得“完美”的拟合度，但是却不是一个好的预测函数。我们称图1叫拟合不足(underfitting)，图3为过度拟合(overfitting)。
拟合不足或者叫高偏差(high bias)，导致假设函数不能很好的表示数据的趋势，这通常是由于函数过于简单，或者特征太少。另一个极端，过度拟合虽然可以“很好”拟合训练数据集，但是却不能很好的预测新数据，这可能是由于假设函数过于复杂，引入了过多的曲线和转角。
无论是线性回归还是逻辑回归都有这种情况，下面是逻辑回归的例子：
有两种主要的解决方案：
- 减少特性的数量：人工去掉一些不需要的特性或者使用模型选择算法。
- 正则化代价函数：保留特征，但是设法减小
θ，如果有很多权重不大的特征，正则化很适合。
正则化的代价函数
正则化(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, X, y)), initial_theta, options);
正则化的代价函数，这里需要注意的是正则项中是不对$ \theta_0 $惩罚的：
function [J, grad] = costFunctionReg(theta, X, 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
