正则化 （Regularization）

过拟合问题（The Problem of Overfitting）

• 左边的算法没有很好地拟合训练集，这个问题称作欠拟合(underfitting)，也可以说该算法具有高偏差(high bias)
• 中间的算法拟合效果不错，是理想的模型
• 右边的算法几乎完美地拟合了训练集，它的代价函数也可能接近于0，但是它最后给出的模型并不好。这就是过拟合(Overfitting) 问题，也称该算法具有 高方差(high variance)

解决过拟合问题的方法

1. 减少选取特征的数量
   • 手动删去部分特征变量
   • 模型选择算法(Model Selection Algorithm)
2. 正则化(Regularization)
   • 保留所有的特征变量，但是减少参数$\theta_j$θj​的量级或数值大小

代价函数（Cost Function）

• 正则化的思路就是减少参数$\theta_j$θj​的量级或数值大小

• 理想的情况下，我们选出一些影响较小的特征，并减小它们对应的参数，假设是$\theta_3,\theta_4$θ3​,θ4​ ，我们可以修改代价函数来达到这个效果：
  $J(\theta)=\frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{i})-y^{(i)})+\lambda_3\theta_3^2+\lambda_4\theta_4^2$J(θ)=2m1​i=1∑m​(hθ​(xi)−y(i))+λ3​θ32​+λ4​θ42​

• 但通常我们是很难选出哪些特征重要，哪些次要，所以我们直接把代价函数改成如下形式：
  $J(\theta)=\frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{i})-y^{(i)})+\lambda\sum_{j=1}^n\theta_j^2$J(θ)=2m1​i=1∑m​(hθ​(xi)−y(i))+λj=1∑n​θj2​

• 如果 $\lambda$λ 过小，就相当于没有正则化。

• 如果 $\lambda$λ 过大，$\theta_1...\theta_n$θ1​...θn​有可能都会趋向于$0$0，只剩下一个$\theta_0$θ0​，图像就只剩下了一条直线，也就会出现欠拟合问题。

线性回归的正则化（Regularized Linear Reression）

梯度下降算法：

$\begin{aligned} & repeat\;until\;converge\{\\ & \qquad \theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m{(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}}\\ & \qquad \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\\ & \}\\ \end{aligned}$​repeatuntilconverge{θ0​:=θ0​−αm1​i=1∑m​(hθ​(x(i))−y(i))x0(i)​θj​:=θj​−αm1​i=1∑m​(hθ​(x(i))−y(i))xj(i)​+mλ​θj​}​

转化一下第二个式子：
$\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​:=θj​(1−αmλ​)−αm1​i=1∑m​hθ​(x(i))−y(i)xji​
其中系数 $1-\alpha\frac{\lambda}{m}$1−αmλ​ 是一个比 $1$1 小，但接近 $1$1 的数。此时算法的意义就是每次对参数 $\theta_j$θj​ 缩小，然后再正常的进行梯度下降。

正规方程

$\theta=(X^TX+\lambda \left[ \begin{matrix} 0 & & & & \\ & 1 & & & \\ & & 1 & & \\ & & & ... & \\ & & & & 1 \end{matrix} \right] ) ^{-1}X^Ty$θ=(XTX+λ⎣⎢⎢⎢⎢⎡​0​1​1​...​1​⎦⎥⎥⎥⎥⎤​)−1XTy

• 公式中新增的矩阵是$(n+1)\times(n+1)$(n+1)×(n+1)的

• 此时一定存在逆矩阵

逻辑回归的正则化（Regularized Logistic Regression）

梯度下降算法

$\begin{aligned} & repeat\;until\;converge\{\\ & \qquad \theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m{(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}}\\ & \qquad \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\\ & \}\\ \end{aligned}$​repeatuntilconverge{θ0​:=θ0​−αm1​i=1∑m​(hθ​(x(i))−y(i))x0(i)​θj​:=θj​−αm1​i=1∑m​(hθ​(x(i))−y(i))xj(i)​+mλ​θj​}​

• 算法形式长得和线性回归的一样，只有 $h_\theta(x)$hθ​(x) 的意义不一样
• 通过正则化，能够有效的避免过拟合

参考链接

[1].吴恩达机器学习 第八章-正则化