前言：通常一个学习演算法是借由训练范例来训练的。亦即预期结果的范例是可知的。而学习者则被认为须达到可以预测出其它范例的正确的结果，因此，应适用于一般化的情况而非只是训练时所使用的现有资料（根据它的归纳偏向）。然而，学习者却会去适应训练资料中太特化但又随机的特征，特别是在当学习过程太久或范例太少时。在过适的过程中，当预测训练范例结果的表现增加时，应用在未知资料的表现则变更差。——From WikiPedia
过度拟合(Overfitting)问题
正则化(Regularzation)就是被设计为解决过度拟合问题的。
在一个函数拟合数据集的时候会出现三种情况：欠拟合(high bias or underfitting)、正好拟合和过拟合(overfitting or high variance)。
欠拟合(high bias or underfitting)是我们的假想函数对数据趋势拟合程度非常糟糕，造成这种情况通常是由于函数太简单或者使用的参数非常少；
过拟合(overfitting or high variance)是假想函数对训练数据拟合的非常好，但是对未知数据的预测却不尽如人意，通常是由假象函数非常复杂并且使用的参数非常多，使函数产生许多不必要的波浪。
解决过度拟合问题主要有两个方法： 1. 减少特征（参数）的数量 * 自己决定保留哪些特征 * 用一些选择算法来决定保留哪些特征 2. 正则化 * 保留所有特征（参数），但是减小参数\(\theta_j\)的值。
代价函数（Cost Function）
假设我们用一个二次函数来拟合一些数据,它给了我们一个对数据很好的拟合，然而如果我们用一个更高次的多项式去拟合，比如 \(θ_0+θ_1x+θ_2x^2+θ_3x^3+θ_4x^4\)，我们最终可能得到一个曲线能非常好地拟合训练集，但是它过度拟合了数据，一般性并不是很好。
让我们考虑下面的假设：我们想要加上惩罚项从而使参数 \(θ_3\) 和 \(θ_4\) 足够的小，而避免直接删掉它们，只需如下修改代价函数： \[\min_θ \frac{1}{2m}(\sum^m_{i=1}(h_θ(x^{(i)})−y^{(i)})^2+1000⋅θ^2_3+1000⋅θ^2_4)\]
我们对代价函数添加一些了项：加上 1000 乘以 \(θ_3\) 的平方，再加上 1000 乘以 \(θ_4\) 的平方，1000 只是我随便写的某个较大的数字而已。现在，如果我们要最小化这个函数，为了使这个新的代价函数最小化，我们要让 \(θ_3\) 和 \(θ_4\) 尽可能得小，对吧？如果我们这么做了，\(θ_3\) 和 \(θ_4\)可能会趋近于０，结果接近成一个二次函数。
更一般地可以表明，这些参数的值越小通常对应于越光滑的函数，也就是更加简单的函数。因此，就不易发生过拟合的问题。
由于在实际应用中参数可能很多，比如有100个，需要用正则化，但是我不知道具体哪个参数或哪几个参数需要缩小，所以我们只能让所有参数从\(θ_1\) \(θ_2\) \(θ_3\) 直到 \(θ_{100}\) 的值变小。(顺便说一下，按照惯例来讲，我们从第一个这里开始，所以我实际上没有去惩罚 \(θ_0\) , 因此 \(θ_0\) 的值是大的, 这就是一个约定。)
所以代价函数被修改为： \[\min_θ \frac{1}{2m}[\sum^m_{i=1}(h_θ(x^{(i)})−y^{(i)})^2+\lambda \sum^n_{j=1}\theta^2_j]\]
其中 \(\lambda\) 为正则化参数(regularization parameter)。
\(\lambda\) 要做的就是控制在两个不同目标中的平衡关系。第一个目标就是我们想要使假设更好地拟合训练数据，我们希望假设能够很好的适应训练集; 而第二个目标是我们想要保持参数值较小。通过正则化目标函数，它会找到这两者之间的平衡，从而保持假设的形式相对简单, 来避免过度的拟合。
不过，如果 \(\lambda\) 设置过大，假想函数可能会过于光滑平坦而导致欠拟合(underfitting)。
正则化线性回归
对于线性回归的求解，我们之前推导了两种学习算法，一种基于梯度下降，一种基于正规方程。我们将继续把这两个算法推广到正则化线性回归中去 。
梯度下降(Gradient Descent)
因为我们不惩罚第零项参数，所以我们把梯度下降的迭代方程中更新 \(\theta_0\) 和更新其他参数分开，变为如下形式： \(Repeat\{\) \[\theta_0 := \theta_0 - \alpha \frac{1}{m} \sum^m_{i = 1} (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)}\] \[\theta_j := \theta_j - \alpha [(\frac{1}{m} \sum^m_{i = 1} (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}) + \frac{\lambda}{m}\theta_j]\] \(\}\)
这一项 \(\frac{\lambda}{m}\theta_j\) 就是正则化。
第二个方程也可以合并同类项变成： \[\theta_j := \theta_j(1 - \alpha\frac{\lambda}{m}) - \alpha \frac{1}{m} \sum^m_{i = 1} (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}\]
由于 \(α\frac{λ}{m}\) 通常是很小的，所以方程的第一项 \(1 - \alpha\frac{\lambda}{m}\) 一般来说将是一个比1小一点点的值。我们可以把它想成一个像0.99一样的数字，所以对 \(θ_j\) 更新的结果可以看作是被替换为 \(θ_j\) 的0.99倍，也就是 \(θ_j\) 乘以0.99把 \(θ_j\) 向 0 压缩了一点点，所以这使得 \(θ_j\) 小了一点，更正式地说 θj 的平方范数更小了。另外，方程的第二项实际上跟我们加入了正则项之前一样。
正规方程(Normal Equation)
正则化的正规方程如下： \[\theta = (X^TX + \lambda \cdot L)^{-1}X^Ty\] 其中，\[L = \begin{bmatrix} 0 \\ & 1 \\ & & 1 \\ & & & \ddots & \\ & & & & 1 \end{bmatrix}\] 它的维度是\((n+1)×(n+1)\)。
即使 \(X^TX\) 是不可逆的，正则化之后，即加上 \(\lambda \cdot L\) 之后，该矩阵 \(X^TX + \lambda \cdot L\) 一定是可逆的。
正则化逻辑回归
代价函数
复习一下逻辑回归的代价函数： \[J(\theta) = -\frac{1}{m}\sum^{m}_{i = 1}[y^{(i)}\log(h_\theta(x^{(i)})) + (1-y^{(i)})\log(1-h_\theta(x^{(i)}))]\]
我们通过在最后多加上一项来完成正则化： \[J(\theta) = -\frac{1}{m}\sum^{m}_{i = 1}[y^{(i)}\log(h_\theta(x^{(i)})) + (1-y^{(i)})\log(1-h_\theta(x^{(i)}))] + \frac{\lambda}{2m}\sum^{n}_{j=1}\theta_j^2\]
向量形式为： \[J(\theta) = -\frac{1}{m}(\log(g(X\theta))^Ty + \log(1-g(X\theta))^T(1-y)) + \frac{\lambda}{2m}temp^Ttemp\] 其中 \(temp = \theta;temp(1) = 0;\)
注意从1开始而不是从0开始！
梯度下降
\(Repeat\{\) \[\theta_0 := \theta_0 - \alpha \frac{1}{m} \sum^m_{i = 1} (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)}\] \[\theta_j := \theta_j - \alpha [(\frac{1}{m} \sum^m_{i = 1} (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}) + \frac{\lambda}{m}\theta_j]\] \(\}\)
除了 \(h_\theta\) 表示不同以外，其他与线性回归的方程一样。
最后关于梯度（偏导数）的向量形式： \[\frac{\partial}{\partial\theta}J(\theta) = \frac{1}{m}[X^T(g(X\theta) - \overrightarrow{y}) + \lambda_v .* \theta]\] 其中\(\lambda_v = \begin{bmatrix} 0 & \lambda & \lambda & \cdots & \lambda \\ \end{bmatrix}^T\)