回归（一）：线性回归

2019-01-22 本文已影响80人阿圆的一亩三分地

回归

通常对于一组特征数据和其标记值： $(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)$ ，在使用特征值 $x_i$ 对 $y_i$ 进行预测时，根据习惯，如果 $y_i$ 是连续的，则称这种操作或者技术为回归；如果 $y_i$ 是离散的，则通常称为分类。

线性回归

以根据房屋的属性来预测价格为例，假设房屋的价格与房屋的面积和居室的数目有关，如下表所示；

Living area( $feet^2$ )	bedrooms	Prices
2104	3	400
1600	3	330
2400	3	369
1416	2	232
3000	4	540

把房屋的面积记为特征 $x_1$ ，把居室的数目记为特征 $x_2$ ，价格记为 $y$ 。我们猜测 $x_1, x_2$ 和 $y$ 之间，满足关系：

$y = \theta_0 + \theta_1x_1 + \theta_2x_2$

因此我们可以建立模型：

$h_{\theta}(x) = \theta_0 + \theta_1x_1 + \theta_2x_2$

我们也可以把上式写成向量的形式

$h_{\theta}(x) = \sum_{i=0}^{n}\theta_ix_i = \theta^Tx$

其中， $\theta$ 是参数， $x$ 是我们的训练数据和检测数据中的特征值。实际上， $\theta$ 是未知量，我们的目标就是通过训练数据调整 $\theta$ ，来使得输出的结果更接近真实值。

在将训练的数据中的 $x_1$ 代入，都会得到一个输出 $\theta^Tx_i$ ，这个值和真实的 $y_i$ 之间会存在一个随机的误差 $\epsilon_i$ ：

$y^{(i)} = \theta^Tx^{(i)} + \epsilon^{(i)}$

我们假定所有的房屋都是独立的，我们可以认为，误差的存在可能是房屋中的价格还会受到一些其他的因素的影响，而这些因素在建模的过程中没有体现，这些细枝末节可能使得房屋的价格有一些震荡。如果把这些因素看成随机变量，当足够多的随机变量叠加之后，根据中心极限定理，形成的分布就是正态分布。因此：

误差 $\epsilon^{(i)}(1\leq i \leq m)$ 是独立同分布的，服从均值为0，方差为某定值 $\sigma^2$ 的高斯分布。

我们做一些推导：

根据高斯分布：

$p(\epsilon^{(i)}) = \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(\epsilon^{(i)})^2}{2\sigma^2})$

将 $\epsilon^{(i)}$ 用训练数据替换：

$p(y^{(i)}|x^{(i)};\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2})$

因为我们认为这些数据是独立同分布的，因此所有的训练数据的联合概率就是各自的边缘概率的乘积，得到似然函数：

$L(\theta) = \prod_{i=1}^m p(y^{(i)}|x^{(i)}; \theta) = \prod_{i=1}^m \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2})$

为了简化计算，我们对 $L(\theta)$ 取对数，得到对数似然函数：

$l(\theta) = logL(\theta)\\ = log\prod_{i=1}^m \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2}) \\ = \sum_{i=1}^m log\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2}) \\ = mlog\frac{1}{\sqrt{2\pi}\sigma} - \frac{1}{\sigma^2} \centerdot \frac{1}{2}\sum_{i=1}^m (y^{(i)} - \theta^Tx^{(i)})^2$

当我们使用极大似然估计的方法，则 $l(\theta)$ 取最大值的时候，去掉式子中的定值部分，就是

$J(\theta) = \frac{1}{2}\sum_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)})^2$

取最小值，这就是最小二乘法的目标函数。

求解 $\theta$ 的解析式

将M个N维的样本组成矩阵X：

X的每一行对应一个样本，共有M个样本
X的每一列对应样本的一个维度，共N维
- 还有一个额外的常数项，全为1

目标函数： $J(\theta) = \frac{1}{2}\sum_{i=1}^m(h_{\theta}(x^{(i)} - y^{(i)}))^2 = \frac{1}{2}(X\theta - y)^T(X\theta - y)$

求梯度： $\nabla J(\theta) = \nabla_{\theta} (\frac{1}{2}(X\theta - y)^T(X\theta - y) \\= \nabla_{\theta} (\frac{1}{2}(\theta^TX^T - y^T)(X\theta - y))\\ = \nabla_{\theta}(\frac{1}{2}(\theta^TX^TX\theta -\theta^TX^Ty - y^T(X\theta + y^Ty ))\\ = \frac{1}{2}(2X^TX\theta - X^Ty - (y^TX)^T) \\ = X^TX\theta - X^Ty$

其中用到了线性代数的公式：

$\frac{\partial A\theta}{\partial \theta} = A^T$ ； $\frac{\partial \theta^TA}{\partial \theta} = A$ ；
$\frac{\partial \theta^TA\theta}{\partial \theta} = (A + A^T)\theta$ ；对于对称方阵A， $\frac{\partial \theta^TA\theta}{\partial \theta} = 2A\theta$ ；

求驻点：令 $\nabla J(\theta) = 0 \Rightarrow \theta = (X^TX)^{-1}X^Ty$

如果 $X^TX$ 不可逆或者防止过拟合，可以加入 $\lambda$ 扰动：

$\theta = (X^TX+\lambda I)^{-1}X^Ty$

加入复杂度惩罚因子

有时，当我们认为 $y$ 不仅和 $x$ 有关系，还可能和 $x^2, x^3, ..., x^n$ 有关系时，我们也可以在上面的式子中加入这些项。例如，考虑二阶的情况，上面的目标函数会更改为：

$h_{\theta}(x) = \theta_0 + \theta_{11}x_1 + \theta_{12}x_2 + \theta_{21}x_1^2 + \theta_{22}x_2^2$

而且，在处理的过程中，通常会把 $x, x^2, x^3, ..., x^n$ 也当作相互独立的随机变量处理。以此类推，我们也可以加入 $logx, a^x, sinx$ 等。实际上，以我个人的理解，线性回归中，线性指的其实是死参数 $\theta$ 的线性。

假设现在有九个点 $(x_i, y_i) , i\in\{0, 1, 2, 3, 4, 5, 6, 7, 8\}$ ，那么我们就一定可以用一个最高次不超过8次的表达式去拟合它。

随机产生九个点，然后进行实验，得到了如下结果：

image-20190122210356583.png

系数如下：

image-20190122210453756.png

可以看到，虽然8阶的曲线可以完美地通过所有的点，但是8的曲线的参数值都很大，也就很不稳定。而且从曲线图中很容易就可以看出，8阶的曲线虽然完美的通过了所有的点，但是并不能很好地反映九个点的分布。这里就存在过拟合。为了放着这种现象的发生，一种通常的做法是，在式子中加入一个惩罚因子，来限制参数大小：

$J(\theta) = \frac{1}{2}(h_{\theta}(x^{(i)}) - y^{(i)} )^2 + \lambda\sum_{j=1}^{n}\theta_j^2$

其中 $\lambda$ 是一个可调的参数。

这种操作称为正则化，因为我们用的是 $\theta$ 的平方求和，因此称为L2正则化。如果是 $\theta$ 的绝对值求和，则称为L1正则化：

$J(\theta) = \frac{1}{2}(h_{\theta}(x^{(i)}) - y^{(i)} )^2 + \lambda\sum_{j=1}^{n}|\theta_j|$

在Elastic Net中将两种正则化整合：

$J(\theta) = \frac{1}{2}(h_{\theta}(x^{(i)}) - y^{(i)} )^2 + \lambda(\rho\sum_{j=1}^{n}|\theta_j| + (1-\rho)\sum_{j=1}^{n}\theta_j^2)$

梯度下降算法(gradient descent)

在实际的应用中，并不是所有的情况下都会有最优解的解析解，而且也没有必要去求解析解，有的时候有数值解就够了。梯度下降算法就是一种应用非常广泛的求最有参数数值解的方法，步骤如下：

初始化 $\theta$ （随机初始化）
沿着负梯度的方向迭代，更新后的 $\theta$ 使 $J(\theta)$ 更小

$\theta = \theta - \alpha \centerdot \frac{\partial J(\theta)}{\partial \theta}$

就是让 $\theta$ 沿着让 $J(\theta)$ 下降最快的方向移动。求一下梯度方向；

$\frac{\partial}{\partial\theta_j}J(\theta) = \frac{\partial}{\partial\theta_j}\frac{1}{2}(h_{\theta}(x) - y)^2\\ = 2 \times \frac{1}{2} (h_{\theta}(x) - y) \centerdot \frac{\partial}{\partial\theta_j}(h_{\theta}(x) - y)\\ = (h_{\theta}(x) - y) \centerdot \frac{\partial}{\partial\theta_j}(\sum_{i = 0}^n\theta_ix_i - y)\\ = (h_{\theta}(x) - y)x_j$