Part1-正则化
过拟合问题
到现在为止，我们已经学习了线性回归和逻辑回归，它们能够有效地解决许多问题，但当将它们应用到某些特定的机器学习应用时，会遇到过拟合问题，导致它们表现欠佳。
什么是过拟合？
例：
对于房价预测问题，输入是房屋面积，输出是房屋价格
如图：
当使用一次函数来拟合数据时，画出的直线对于有的训练数据拟合并不好，这并不是一个很好的模型，因此，将这个问题称为欠拟合，另一个说法是这个算法具有高偏差(High bias)。
在图中第二个图对应的，加入一个二次项，用二次函数来拟合数据集，画出的线拟合效果很好。
另一个极端情况是，如果拟合一个四阶多项式，对应的有四个参数，拟合出的曲线可以拟合所有的训练样本，这看似很好地拟合了训练集，因为它通过了所有的数据点，但这是一条扭曲的曲线，它不停地上下波动，实际上，它并不是一个预测房价的好模型，这个问题，也被称为过拟合，另一个说法是这个算法具有高方差(Hight variance)。
概括地说，过拟合问题，将会在变量过多时出现，这里训练出的假设能很好地拟合训练集，因此，代价函数实际上可能非常接近于0或恰好等于0，这样训练的结果，千方百计地拟合训练样本，导致它无法泛化到新的样本中，无法预测新样本的价格。
同样的，在逻辑回归中，欠拟合和过拟合的表现如图：
解决过拟合：
在特征数量较少时， 如上述，可以采用画图的方式来观察曲线，确定多项式次数
降低特征数量
- 人工决策，挑选更加重要的特征保留下来，而将一些不重要的特征舍弃
- 模型选择算法(PCA......)
正则化
- 保留所有特征，但是减少量级或参数大小
- 如果有许多特征，且每个特征都会对预测\(y\)有一点点作用，则使用正则化会表现很好
代价函数
对于上述的过拟合例子中，如图：
对于这个过拟合的函数，它的泛化性不够好，不妨在函数中加入惩罚项，来使得参数\(\theta_3\)和\(\theta_4\)都非常小
因此，对于\(\min_\theta \frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2\)需要改为：
\(\min_\theta \frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2+1000\theta_3^2+1000\theta_4^2\)(此处1000只是表示一个较大的数，不固定)
为了达到最小的目的，则需要\(\theta_4\)和\(\theta_4\)要尽可能小，即需要\(\theta_3 \rightarrow 0,\theta_4 \rightarrow 0\)
这样，就好像我们将函数中的\(\theta_3x^3+\theta_4x^4\)直接去掉一样，这样的话，这个函数就还是相当于二次函数。
正则化：
正则化的思想就是：
如果我们的参数值较小，则意味着：一个更加简单的假设模型；更不容易出现过拟合问题
还是以房价预测为例，如果房屋特征为：\(x_1,x_2,\cdots,x_100\)，对应的参数为\(\theta_0,\theta_1,\theta_2,\cdots,\theta_100\)
和之前不同的是，我们不知道\(\theta_3\)和\(\theta_4\)是高阶项，也就是不知道因为选出哪些参数来进行惩罚
因此我们需要做的就是修改代价函数，来缩小所有的参数，因为我们不知道应该选择哪些参数去缩小
\(J(\theta)=\frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2\)
\(J(\theta)=\frac{1}{2m}[\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2+\lambda \sum_{j=1}^n \theta_j^2]\)
正则化线性回归
\(J(\theta)=\frac{1}{2m}[\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2+\lambda \sum_{j=1}^n \theta_j^2]\)
\(\min_\theta J(\theta)\)
梯度下降：
之前：
\(Repeat \{ \\ \theta_j := \theta_j-\alpha\ \frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} (j=0,1,2,3,\cdots,n) \\\}\)
正则化：
\(Repeat \{ \\ \theta_0:=\theta_0-\alpha \frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)}) -y^{(i)})x_0^{(i)} \\ \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] \ (j=1,2,3,\cdots,n) \\ (\Rightarrow \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)} ) \\ \}\)
正规方程：
\(X=\left[ \begin{matrix} (x^{(1)})^T \\ \dots \\ (x^{(m)})^T \end{matrix} \right]；y=\left[ \begin{matrix} y^{(1)} \\ \dots \\ y^{(m)} \end{matrix} \right]\)
之前：
\(\theta=(X^TX)^{-1}X^Ty\)
正则化：
\(如果 \lambda > 0,\\ \theta=(X^TX + \lambda \left[ \begin{matrix} 0 & & & \\ & 1 & & \\ & & \cdots & \\ & & & 1 \end{matrix} \right])^{-1}X^Ty\)
其中的矩阵是\((n+1)\times (n+1)\)矩阵(n是特征数量 )
正则化逻辑回归
\(J(\theta)=-[\frac{1}{m}\sum_{i=1}^my^{(i)}\log h_\theta(x^{(i)})+(1-y^{(i)})\log (1-h_\theta(x^{(i)}))]\)
正则化：
\(J(\theta)=-[\frac{1}{m}\sum_{i=1}^m y^{(i)}\log h_\theta(x^{(i)})+(1-y^{(i)})\log (1-h_\theta(x^{(i)}))+\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2]\)
梯度下降：
之前：
\(Repeat\{ \\ \theta_j:=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}(j=0,1,2,3,\cdots,n) \\ \}\)
正则化：
\(Repeat\{ \\ \theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)} \\ \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](j=1,2,3,\cdots,n) \\ \}\)