CS229: 1

线性回归, Linear Regression

多元线性回归

多元线性回归的梯度下降法

规定$x^{(i)}$表示训练集的第$i$个输入，$y^{(i)}$表示相应的答案。

设

$$X_{n\times d}=\left[\begin{matrix} x_1^T \\ x_2^T \\ ... \\ x_n^T \end{matrix}\right],y_{n\times 1}=\left[\begin{matrix} y_1 \\ y_2 \\ ... \\ y_n \end{matrix}\right]$$

首先，要意识到，不可能完美预测，所以只能追求“误差”最小。

用$h_{\theta}(x)$表示输入$x$得出的预测结果。

现在考虑最简单的预测方法，

$$h_{\theta}(x)=\theta^T x$$

其中在给出样本的基础上，添加一个参数$x_0=1$。

而且学习是离线的，即只是在已知的训练集上学习一次，用学习出的参数$\theta$来预测。

根据统计直觉，使用欧式空间的“度量”，也就是L2距离来定义误差，即损失函数$J(\theta)$。学习的目标就是在给出的训练集上让$J(\theta)$最小。为了后续求导方便，设置一个常数$\frac{1}{2}$。也有人考虑类似方差的定义，设为$\frac{1}{2n}$

$$J(\theta)=\frac{1}{2}\sum_{i=1}^{n}||y^{(i)}-h_{\theta}(x^{(i)})||^2=\frac{1}{2}(X\theta-y)^T(X\theta-y)$$

所谓的梯度下降法就是对$J(\theta)$每个维度求偏导，也就是梯度，再根据梯度来更新$\theta$，也就是$\theta$向$J(\theta)$更小的方向迈一步。

当然，这只是一个很朴素的贪心算法，所以有可能会陷入局部最优解。但是后面我们可以看到线性回归其实是凸的，对于非凸的函数会进行后面一系列的改进。

求梯度

$$\begin{aligned} \nabla_{\theta}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^TX\theta+y^Ty)\\ & =\nabla_{\theta}\frac{1}{2}(\theta^TX^TX\theta-2y^TX\theta+y^Ty)\\ & =X^T(X\theta-y) \end{aligned}$$

那么更新$\theta$就是

$$\theta:=\theta-\alpha \nabla_{\theta}J(\theta)=\theta-\alpha X^T(X\theta-y)=\theta+\alpha\sum_{i=1}^{n}x^{(i)}(y^{(i)}-\theta^Tx^{(i)})$$

多元线性回归的损失函数的合理性

刚刚先是基于距离假定了损失函数

$$J(\theta)=\frac{1}{2} \sum_{i=1}^{n} ||y^{(i)}-\theta ^T x^{(i)}||^2$$

然后求导，做梯度下降更新参数。

看起来损失函数的设置来源于统计学的直觉，但是为什么对，或者说为什么合理呢？

假设

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

而

$$\epsilon_i \sim \N(0,\sigma^2)$$

其中$\sigma$是定值。

我们再假设所有$\epsilon_i$都是独立同分布的，也就是说所有$\epsilon_i$均相互独立但都服从该分布。

至于为什么要假设符合正态分布呢？

根据中心极限定理，规定了均值和方差后，$n$足够大，和正态分布的误差就能任意地小。

而找到对应的$\theta$，从概率上来讲，就是要做极大似然估计，使得每个$\epsilon_i$取到自己对应的值的时候，总的概率最大

$$L(\theta)=\prod_{i=1}^{n}P(\epsilon_i=y^{(i)}-\theta ^T x^{(i)}|x^{(i)})$$

$$\ln L(\theta)=\sum_{i=1}^{n}\ln P(\epsilon_i=y^{(i)}-\theta ^T x^{(i)}|x^{(i)})$$

$$=\sum_{i=1}^{n}\ln \frac{1}{\sigma\sqrt{2\pi}}\exp \{-\frac{(y^{(i)}-\theta ^T x^{(i)})^2}{2\sigma^2}\}$$

$$=\sum_{i=1}^{n}\ln \frac{1}{\sigma\sqrt{2\pi}}-\frac{(y^{(i)}-\theta ^T x^{(i)})^2}{2\sigma^2}$$

也就是说明了损失函数的合理性。

多元线性回归的解析解

设

$$X_{n\times d}=\left[\begin{matrix} x_1^T \\ x_2^T \\ ... \\ x_n^T \end{matrix}\right],y_{n\times 1}=\left[\begin{matrix} y_1 \\ y_2 \\ ... \\ y_n \end{matrix}\right]$$

直接从定义出发，可得

$$\nabla_{\theta} J(\theta)=-(\sum_{i=1}^n x^{(i)}_jy_j)^T+X^TX\theta=-X^Ty+X^TX\theta$$

假设$X^TX$可逆，则$\theta$的解析解是

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

当然，也可以直接考虑

$$\nabla_{\theta} J(\theta)=\nabla_{\theta} \frac{1}{2}(X\theta-y)^T(X\theta-y)$$

然后求解。

但是如果$X^TX$不可逆，就要考虑其伪逆了。

随机梯度下降（Stochastic Gradient Descent）

原本的梯度下降解线性回归，可以看到每进行一次梯度下降要遍历所有的点，如果数据集足够大的话，即使并行矩阵运算，耗费的时间仍然是不可接受的，也就是说，有限的时间内，我们可能并没有完成几次完整的梯度下降。

原本的梯度下降的更新方式是

$$\theta:=\theta+\alpha\sum_{i=1}^n (y^{(i)}-h_{\theta}(x^{(i)}))x^{(i)}$$

其中$h_{\theta}(x)=\theta^T x$，其中$x_0=1$。

一个很工程但是很不严谨的想法是，不要每次都用所有点来更新，比如每次随机选一个点来更新直到收敛

$$\theta:=\theta+\alpha(y^{(r)}-h_{\theta}(x^{(r)}))x^{(r)}$$

这就是SGD。

或者每次选一小批点来更新，直到收敛。这就是mini-batch SGD，比SGD更常用。

比较类似概率中的“采样”，也可以认为是对训练集的一个无偏估计。如果使用以后的课的记法，可以理解为$\alpha$吸收了一个系数$\frac{1}{n}$，实际上原本的损失函数就是训练集梯度的平均数，SGD就是在估计平均数。

虽然不一定能得到最优的解，但是一定可以收敛，最后一般能达到一个比较优的解。

一般来说，相较于普通GD，SGD在训练前期收敛比较快，而且函数非凸时不容易陷入局部最优。

为什么SGD可以跳出局部最优呢？

如果假设高维空间中每一维相互独立，那么每一维上出现某种“形状”的概率是一样的，如果出现严格的局部最优，也就是每一维上都是一个类似抛物线的形状，或者严格地说，该点的Haissen矩阵是半正定的，每一维上是相乘的关系，高维时概率就很小了。换句话说，高维空间梯度为0的非全局最优点几乎都是鞍部，而SGD如果陷入了鞍点，更新时用部分数据来估计该点的实际梯度，实际上是带有噪声的，也就是不是严格的0，就很容易跳出鞍点。

直观理解，普通的GD，虽然每次梯度下降的效果显著，但是耗时多，不能下降几次；虽然SGD每次只对一个点进行GD，对整体而言效果不显著，但是成本低，可以进行很多次。SGD每次在训练集中选取一个很小的集合，只要训练次数足够多，就能覆盖整个训练集。

工程上，学习率$\alpha$一般不会固定，会随训练时间增加而慢慢减少，类似模拟退火。

局部加权线性回归

如果要拟合的函数正体并没有线性的特征，比如正弦函数，看起来线性回归就失效了？

但是我们可以考虑要预测的点的附近的已知点，可以认为局部就是线性的，所有可以在局部选取几个最近的点做线性回归，但坏处是变成了在线算法。

当然可以用KNN（k-近邻算法），可以k-d tree，ball tree，或者奇奇怪怪的近似算法，直接忽略太远的点。

另外一个自然的想法是修改损失函数，使得较远的点的影响减弱。

$$J(\theta)=\sum_{i=1}^{n}w_i(y^{(i)}-\theta ^T x^{(i)})^2,0<w_i<1$$

一个非常著名的$w$的设置被称为高斯核函数

$$w_i=\exp\{-\frac{||x^{(i)}-x||^2}{2\tau ^2}\}$$

其中$\tau$是人为设定的，决定多远的已知点能起作用。

梯度下降的动量法

更多优化器请参考CS230笔记。

简单来说，就是梯度下降时考虑前面几个版本的增量，和一个指数级数做卷积，相当于滑动窗口。

可以写成动量守恒的碰撞的形式，相当于梯度下降考虑了惯性，所以叫动量法。

K近邻算法(K-Nearest Neighbor, KNN)

在前面的局部线性回归提到的优化算法之一，也可以用于逻辑回归（分类），在线地输入每个点，根据最近的k个点所属的类别来确定该点的类别。

k-d tree

ball tree