Regularization

Regularization

The problem of overfitting

过拟合（overfitting）指的是当有多个特征时，预测函数的代价可能会很低，但对于新的预测数据全都错误的情况，这会导致模型的泛化能力较差。

左侧的称为欠拟合（underfitting），右侧的称为过拟合。

当特征过多而数据过少时，就有可能出现过拟合的情况。

当过拟合的情况发生时，该如何解决呢？

1. 减少特征的数量，我们可以选择重要的特征进行保留，也可以使用模型选择算法，这种算法可以自动选择保留哪些特征和选择哪些特征，但是删去某些特征会导致一些信息的丢失，有可能这些信息都是我们需要的；
2. 保留所有的特征，进行正则化。我们通过正则化将参数 $\theta_j$ 的量级或数量减小，这在我们有很多特征的时候非常有效，由于每个特征都会对结果产生贡献，所以这种方法是行之有效的。

Cost Function

假设此时我们的模型为 $\theta_0 + \theta_1x + \theta_2x^2 + \theta_3x^3 + \theta_4x^4$，我们考虑加入惩罚项，使得 $\theta_3$ 和 $\theta_4$ 非常小，即

$$\underset{\boldsymbol{\theta}}{\arg\min}\dfrac 1{2m}\sum\limits_{i = 1}^m{\left(h_\theta(x^{(i)}) - y^{(i)}\right)^2} + 1000 \theta_3^2 + 1000\theta_4^2$$

如此，要使上式最小，必须令 $\theta_3$ 和 $\theta_4$ 尽量趋近于零，相当于我们尽量去除了 $\theta_3x^3$ 和 $\theta_4x^4$ 两项，最后我们得到的仍是一个拟合效果很好的近似于二次函数的模型。

当参数 $\theta_0, \theta_1, \dots, \theta_n$ 较小时，我们可以得到一个“简化”的模型，过拟合的可能性也会降低。

当我们想把 $\theta_0, \theta_1, \dots, \theta_{100}$ 每个参数的值都缩小时，可以令代价函数为

$$J(\theta) = \dfrac 1{2m}\left[\sum\limits_{i = 1}^m{\left(h_\theta(x^{(i)}) - y^{(i)}\right)^2} + \lambda \sum\limits_{j = 1}^n{\theta_j^2}\right]$$

通过加入第二项，我们可以将所有的参数都缩小。注意，此处是从 $1$ 到 $n$ 进行求和，而不是从 $0$ 到 $n$，这是一种约定俗成的做法。$\lambda \sum\limits_{j = 1}^n{\theta_j^2}$ 被称为正则化项，$\lambda$ 被称为正则化参数。这种正则化方法被称为岭回归，正则化项叫做 L2 正则项。

通过正则化可以提高模型的泛化能力。

当最小化 $J(\theta)$ 时，我们一方面可以令均方误差最小，从而达到让模型更好地拟合数据，另一方面可以令正则化项尽可能小，从而使得每个参数更小，而二者之间的平衡关系由正则化参数 $\lambda$ 掌握，使得更好地去拟合训练集的目标和将参数控制的更小的目标同时实现，从而使得模型尽可能简单，避免出现过拟合的情况。

通过正则化，我们可以得到一个更加光滑、简单的曲线，同时能拟合所有的数据，也即得到了一个更好的假设模型。

如果正则化参数过大，惩罚的程度过高，我们会得到一个除了 $\theta_0$ 以外，其他的参数都趋于零的结果，相当于把假设函数的全部项都忽略掉了，这就导致了欠拟合的现象。

Regularized linear regression

1. 梯度下降法：我们将线性回归中的梯度下降式进行处理，分成 $\theta_0$ 和 $\theta_1, \dots, \theta_n$ 两类，即：

$$\theta_0 := \theta_0 - \alpha \dfrac 1m \sum\limits_{i = 1}^m {\left(h_\theta(x^{(i)}) - y^{(i)}\right)}x_0^{(i)}$$

$$\theta_j := \theta_j - \alpha \dfrac 1m \sum\limits_{i = 1}^m {\left(h_\theta(x^{(i)}) - y^{(i)}\right)}x_j^{(i)}\ (j = 1, 2, 3, \dots, n)$$

由于正则化中正则化式是从 $1$ 到 $n$ 进行求和的，所以我们如此分类也是符合直觉的。

加入正则化式后，$j = 1, 2, \dots, n$ 的梯度下降式应当改变，即加上正则化式对 $\theta_j$ 的偏导，修改后得到

$$\theta_0 := \theta_0 - \alpha \dfrac 1m \sum\limits_{i = 1}^m {\left(h_\theta(x^{(i)}) - y^{(i)}\right)}x_0^{(i)}$$

$$\theta_j := \theta_j - \alpha \left[\dfrac 1m \sum\limits_{i = 1}^m {\left(h_\theta(x^{(i)}) - y^{(i)}\right)}x_j^{(i)} + \dfrac{\lambda}{m}\theta_j\right]\ (j = 1, 2, 3, \dots, n)$$

化简 $j = 1, 2, \dots, n$ 的梯度下降式后得到

$$\theta_{j}:=\theta_{j}\left(1-\alpha \dfrac{\lambda}{m}\right)-\alpha \dfrac{1}{m} \sum_{i=1}^{m}\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right) x_{j}^{(i)}$$

2. 规范方程法：构造矩阵 $\mathbf{X}$ 为一个 $m \times (n + 1)$ 的矩阵

$$\mathbf{X}=\left[\begin{array}{c} \left(x^{(1)}\right)^{T} \\ \vdots \\ \left(x^{(m)}\right)^{T} \end{array}\right]$$

$\vec y$ 为一个 $\mathbb{R}^m$ 维的向量

$$\vec y=\left[\begin{array}{c} y^{(1)} \\ \vdots \\ y^{(m)} \end{array}\right]$$

为了最小化代价函数 $J(\theta)$，我们知道其解为 $\vec\theta = (\mathbf{X}^{\mathrm{T}}\mathbf{X})^{-1}\mathbf{X}^{\mathrm{T}}y$，但此时由于加入了正则项，需要加上正则项对 $\theta_j$ 的偏导等于 $0$ 时的解，结果为

$$\vec\theta = \left(\mathbf{X}^{\mathrm{T}}\mathbf{X} + \lambda \begin{bmatrix}0 & & & & & \\ & 1 & & & & \\ & & 1 & & & \\ & & & 1 & & \\& & & & \ddots & \\ & & & & & 1\end{bmatrix}\right)^{-1}\mathbf{X}^{\mathrm{T}}y$$

矩阵为一个主对角线上除了第一行第一列元素为 $0$，其他全为 $1$ 的 $(n + 1) \times (n + 1)$ 的矩阵。

Regularized logistic regression

对于逻辑回归，我们同样使用岭回归，通过对代价函数添加 L2 正则项进行正则化：

$$J(\vec\theta) = -\dfrac 1m\sum\limits_{i = 1}^m\left[y^{(i)}\log h_\theta(x^{(i)}) + (1 - y^{(i)})\log(1 - h_\theta(x^{(i)}))\right] + \dfrac \lambda{2m}\sum\limits_{j = 1}^n{\theta_j^2}$$

通过如此，可以惩罚参数 $\theta_1, \theta_2, \dots, \theta_n$，使它们在尽可能地小的同时尽可能好地完成任务。
逻辑回归的梯度下降式为：

$$\theta_0 := \theta_0 - \alpha \dfrac 1m\sum\limits_{i = 1}^m\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)x_0^{(i)}$$

$$\theta_j := \theta_j - \alpha \dfrac 1m\sum\limits_{i = 1}^m\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)x_j^{(i)},\ (j = 1, 2, 3, \dots, n)$$

在加上 L2 正则项后，第一个式子不变，第二个式子变为

$$\theta_j := \theta_j - \alpha \left[\dfrac 1m\sum\limits_{i = 1}^m\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)x_j^{(i)} + \dfrac \lambda m \theta_j\right],\ (j = 1, 2, 3, \dots, n)$$

化简后得

$$\theta_j := \left(1 - \dfrac\lambda m\right)\theta_j - \alpha \dfrac 1m\sum\limits_{i = 1}^m\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)x_j^{(i)},\ (j = 1, 2, 3, \dots, n)$$