Regression

零、Regression回归

回归分析是一种预测性的建模技术，它研究的是因变量（目标）和自变量（预测器）之间的关系。这种技术通常用于预测分析，时间序列模型以及发现变量之间的因果关系。通常使用曲线/线来拟合数据点，目标是使曲线到数据点的距离差异最小。

一、Linear Model线性回归

1.Model（function set）

线性回归假设目标值与特征之间线性相关，即满足一个多元一次方程。

$y=\sum_{i=0}^{n} w_ix_i=W^TX$y=∑i=0n​wi​xi​=WTX

设$x_0=1$x0​=1（截距项），则$w_0=bias$w0​=bias，简化函数表达式，n为变量个数(不含$x_0$x0​)

2.Loss Function损失函数（goodness of function）

Loss function是一个function的function，input：a function，output：how bad/good it is。由于f是由w决定的，因此Loss function实际上是在衡量一组参数的好坏，即$L(f)=L(w)$L(f)=L(w)。

损失函数形式

使用MAE(mean square error)均方误差，即预测值与真实值之间的平均的平方距离。使用均方误差最小化目标函数的方法称为最小二乘法。
$J(w)=\frac{1}{2}\sum_{i=1}^{n}||w^Tx_i-y_i||^2 \\=\frac{1}{2}\sum_{i=1}^{n}(w^Tx_i-y_i)^2$J(w)=21​i=1∑n​∣∣wTxi​−yi​∣∣2=21​i=1∑n​(wTxi​−yi​)2

为什么选用均方误差作为损失函数？

直观解释

有十分好的几何意义，对应了常用的欧式距离。在线性回归中，就是找到一个直线，使得所有样本到直线的欧式距离最小。

概率解释

首先假设目标变量和输入值存在下面这种等量关系：

$y^{(i)}=w^T x^{(i)}+ \epsilon ^{(i)}$y(i)=wTx(i)+ϵ(i)

上式中 $ \epsilon ^{(i)}$ 是误差项，用于存放由于建模所忽略的变量导致的效果或者随机的噪音信息（random noise）。进一步假设 $ \epsilon ^{(i)}$ 是独立同分布的 (IID ，independently and identically distributed) ，服从高斯分布（Gaussian distribution ，也叫正态分布 Normal distribution），其平均值为 $0$0，方差（variance）为 $\sigma ^2$σ2。这样就可以把这个假设写成 $ \epsilon ^{(i)} ∼ N (0, \sigma ^2)$ 。然后 $ \epsilon ^{(i)} $ 的密度函数就是：

$p(\epsilon ^{(i)} )= \frac 1{\sqrt{2\pi}\sigma} exp (- \frac {(\epsilon ^{(i)} )^2}{2\sigma^2})$p(ϵ(i))=2π​σ1​exp(−2σ2(ϵ(i))2​)

这意味着存在下面的等量关系：

$p(y ^{(i)} |x^{(i)}; w)= \frac 1{\sqrt{2\pi}\sigma} exp (- \frac {(y^{(i)} -w^T x ^{(i)} )^2}{2\sigma^2})$p(y(i)∣x(i);w)=2π​σ1​exp(−2σ2(y(i)−wTx(i))2​)

这里的记号 $“p(y ^{(i)} |x^{(i)}; w)”$“p(y(i)∣x(i);w)” 表示的是这是一个对于给定 $x^{(i)}$x(i) 时 $y^{(i)}$y(i) 的分布，用$w$w 代表该分布的参数。 注意这里不能用 $w(“p(y ^{(i)} |x^{(i)},w)”)$w(“p(y(i)∣x(i),w)”) 来当做条件，因为 $w$w 并不是一个随机变量。这个 $y^{(i)}$y(i) 的分布还可以写成$[y^{(i)} | x^{(i)}; w] ∼ N (w ^T x^{(i)}, \sigma^2)$[y(i)∣x(i);w]∼N(wTx(i),σ2)。

给定一个设计矩阵（design matrix）$X$X，其包含了所有的$x^{(i)}$x(i)，然后再给定$w$w，那么 $y^{(i)}$y(i) 的分布是什么？数据的概率以$p (\vec{y}|X;\theta )$p(y​∣X;θ) 的形式给出。在$w$w取某个固定值的情况下，这个等式通常可以看做是一个 $\vec{y}$y​ 的函数（也可以看成是 $X$X 的函数）。当我们要把它当做 $w$w 的函数的时候，就称它为 似然函数（likelihood function)

$L(\theta) =L(\theta;X,\vec{y})=p(\vec{y}|X;\theta)$L(θ)=L(θ;X,y​)=p(y​∣X;θ)

结合之前对 $\epsilon^{(i)}$ϵ(i) 的独立性假设 （这里对$y^{(i)}$y(i) 以及给定的 $x^{(i)}$x(i) 也都做同样假设），就可以把上面这个等式改写成下面的形式：

$\begin{aligned} L(\theta) &=\prod ^m _{i=1}p(y^{(i)}|x^{(i)};w)\\ &=\prod ^m _{i=1} \frac 1{\sqrt{2\pi}\sigma} exp(- \frac {(y^{(i)}-w^T x^{(i)})^2}{2\sigma^2})\\ \end{aligned}$L(θ)​=i=1∏m​p(y(i)∣x(i);w)=i=1∏m​2π​σ1​exp(−2σ2(y(i)−wTx(i))2​)​

现在，给定了$y^{(i)}$y(i) 和 $x^{(i)}$x(i)之间关系的概率模型了，用什么方法来选择咱们对参数$w$w的最佳猜测呢？最大似然法（maximum likelihood）告诉我们要选择能让数据的似然函数尽可能大的$w$w。也就是说，咱们要找的 $w$w 能够让函数 $L(w)$L(w) 取到最大值。

除了找到 $L(w)$L(w) 最大值，我们还以对任何严格递增的 $L(w)$L(w) 的函数求最大值。如果我们不直接使用 $L(w)$L(w)，而是使用对数函数，来找对数似然函数 $l(w)$l(w) 的最大值，那这样对于求导来说就简单了一些：

$\begin{aligned} l(w) &=\log L(w)\\ &=\log \prod ^m _{i=1} \frac 1{\sqrt{2\pi}\sigma} exp(- \frac {(y^{(i)}-w^T x^{(i)})^2}{2\sigma^2})\\ &= \sum ^m _{i=1}log \frac 1{\sqrt{2\pi}\sigma} exp(- \frac {(y^{(i)}-w^T x^{(i)})^2}{2\sigma^2})\\ &= m \log \frac 1{\sqrt{2\pi}\sigma}- \frac 1{\sigma^2}\cdot \frac 12 \sum^m_{i=1} (y^{(i)}-w^Tx^{(i)})^2\\ \end{aligned}$l(w)​=logL(w)=logi=1∏m​2π​σ1​exp(−2σ2(y(i)−wTx(i))2​)=i=1∑m​log2π​σ1​exp(−2σ2(y(i)−wTx(i))2​)=mlog2π​σ1​−σ21​⋅21​i=1∑m​(y(i)−wTx(i))2​

因此，对 $l(w)$l(w) 取得最大值也就意味着下面这个子式取到最小值：

$\frac 12 \sum^m _{i=1} (y^{(i)}-w^Tx^{(i)})^2$21​i=1∑m​(y(i)−wTx(i))2

到这里我们能发现这个子式实际上就是$J(w)$J(w)，也就是最原始的最小二乘成本函数（least-squares cost function）。

**总结：**在对数据进行概率假设的基础上，最小二乘回归得到的$w$w和最大似然法估计的 $w$w 是一致的。所以这是一系列的假设，其前提是认为最小二乘回归（least-squares regression）能够被判定为一种非常自然的方法，这种方法正好就进行了最大似然估计（maximum likelihood estimation）。（要注意，对于验证最小二乘法是否为一个良好并且合理的过程来说，这些概率假设并不是必须的，此外可能（也确实）有其他的自然假设能够用来评判最小二乘方法。）

另外还要注意，在刚才的讨论中，我们最终对 $w$w 的选择并不依赖 $\sigma^2$σ2，而且也确实在不知道 $\sigma^2$σ2 的情况下就已经找到了结果。稍后我们还要对这个情况加以利用，到时候我们会讨论指数族以及广义线性模型。

LSE(最小二乘估计) <==> MLE(极大似然估计) （当noise为Guassian Dist时）

3.Pick the best function

优化目标：$\hat{w}={arg}\ \underset{w}{min} L(w)$w^=arg wmin​L(w)，arg表示返回取得min时的变量值。

1.采用Normal Equation正规方程求解

前提

当$X^TX$XTX为满秩矩阵或者正定矩阵时，可使用正规方程法，直接求得闭式（closed-form）解。

已知

$X=(x_1,x_2,...,x_n)^T=\begin{pmatrix} {x_1^T}\\ {x_2^T}\\ {\vdots}\\ {x_n^T}\\ \end{pmatrix}=\begin{pmatrix} {x_{11}}&{x_{12}}&{\cdots}&{x_{1p}}\\ {x_{21}}&{x_{22}}&{\cdots}&{x_{2p}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {x_{n1}}&{x_{n2}}&{\cdots}&{x_{np}}\\ \end{pmatrix}$X=(x1​,x2​,...,xn​)T=⎝⎜⎜⎜⎛​x1T​x2T​⋮xnT​​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​x11​x21​⋮xn1​​x12​x22​⋮xn2​​⋯⋯⋱⋯​x1p​x2p​⋮xnp​​⎠⎟⎟⎟⎞​，

$Y=\begin{pmatrix} {y_1}\\ {y_2}\\ {\vdots}\\ {y_n}\\ \end{pmatrix}$Y=⎝⎜⎜⎜⎛​y1​y2​⋮yn​​⎠⎟⎟⎟⎞​，
$J(w)=\frac{1}{2}\sum_{i=1}^{n}||w^Tx_i-y_i||^2 \\=\frac{1}{2}\sum_{i=1}^{n}(w^Tx_i-y_i)^2 \\=\frac{1}{2}(w^Tx_1-y_1,w^Tx_2-y_2,...,w^Tx_n-y_n)\begin{pmatrix} {w^Tx_1-y_1}\\ {w^Tx_2-y_2}\\ {\vdots}\\ {w^Tx_n-y_n}\\ \end{pmatrix} \\=\frac{1}{2}[w^T(x_1,x_2,...,x_n)-(y_1,y_2,...,y_3)]*[w^T(x_1,x_2,...,x_n)-(y_1,y_2,...,y_3)]^T \\=\frac{1}{2}(W^TX^T-Y^T)(XW-Y) \\=\frac{1}{2}(W^TX^TXW-W^TX^TY-Y^TXW+Y^TY) \\(因为Y^TXW=(W^TX^TY)^T,且这是一个标量，故二者相等) \\=\frac{1}{2}(W^TX^TXW-2W^TX^TY+Y^TY)$J(w)=21​i=1∑n​∣∣wTxi​−yi​∣∣2=21​i=1∑n​(wTxi​−yi​)2=21​(wTx1​−y1​,wTx2​−y2​,...,wTxn​−yn​)⎝⎜⎜⎜⎛​wTx1​−y1​wTx2​−y2​⋮wTxn​−yn​​⎠⎟⎟⎟⎞​=21​[wT(x1​,x2​,...,xn​)−(y1​,y2​,...,y3​)]∗[wT(x1​,x2​,...,xn​)−(y1​,y2​,...,y3​)]T=21​(WTXT−YT)(XW−Y)=21​(WTXTXW−WTXTY−YTXW+YTY)(因为YTXW=(WTXTY)T,且这是一个标量，故二者相等)=21​(WTXTXW−2WTXTY+YTY)

求解

$\hat{w}={arg}\ \underset{w}{min} J(w)$w^=arg wmin​J(w)，即找到导数为0处的值。
$\frac{\partial J(w)}{\partial w}=\frac{1}{2}(2X^TXW-2X^TY)=0 \\X^TXW=X^TY \\W=(X^TX)^{-1}X^TY \\其中(X^TX)^{-1}X^T也叫伪逆$∂w∂J(w)​=21​(2XTXW−2XTY)=0XTXW=XTYW=(XTX)−1XTY其中(XTX)−1XT也叫伪逆

总结

最小二乘法适用简洁高效，比梯度下降这样的迭代法似乎方便很多，但也具有局限性：

1.最小二乘法需要计算逆矩阵，若逆矩阵不存在，就没法直接用最小二乘法求解了，此时梯度下降法仍然可以使用。当然，我们可以通过对样本数据进行整理，去掉冗余特征。让$X^TX$XTX的行列式不为0，然后继续使用最小二乘法。

2.当样本特征n非常的大的时候，计算逆矩阵非常耗时，甚至不可行,可以通过主成分分析降低特征的维度后再用最小二乘法。此时以梯度下降为代表的迭代法仍然可以使用。

3.如果拟合函数不是线性的，无法使用最小二乘法，需要通过一些技巧转化为线性才能使用，此时梯度下降仍然可以用。

2.采用Gradient Descent梯度下降求解

优点

只要$J(f)$J(f)是可微分的，都可以用于GD处理这个$f$f，找到表现比较好的参数parameters。

步骤

• 首先随机选取初始点$w^{(0)}$w(0)(如果有办法可以得到比较接近$w^*$w∗的表现得比较好的$w^{(0)}$w(0)当初始点，可以有效地提高查找$w^*$w∗的效率)

• 计算L对w的偏微分，即$\frac{\partial J}{\partial w}|_{w=w^{(0)}}$∂w∂J​∣w=w(0)​

• 如果切线斜率是negative负的，那么就应该使w变大，即往右踏一步；如果切线斜率是positive正的，那么就应该使w变小，即往左踏一步，每一步的步长step size就是w的改变量

  w的改变量step size的大小取决于两件事

  • 一是现在的偏微分值$\frac{\partial J}{\partial w_i}$∂wi​∂J​有多大，微分值越大代表现在在一个越陡峭的地方，那它要移动的距离就越大，反之就越小；

  • 二是一个常数项$η$η，被称为learning rate，即学习率，它决定了每次踏出的step size不只取决于现在的斜率，还取决于一个事先就J定好的数值，如果learning rate比较大，那每踏出一步的时候，参数w更新的幅度就比较大，反之参数更新的幅度就比较小。如果learning rate设置的大一些，那机器学习的速度就会比较快；但是learning rate如果太大，可能就会跳过最合适的global minima的点

• 因此每次参数更新的大小是 $η \frac{\partial J}{\partial w}$η∂w∂J​，为了满足斜率为负时w变大，斜率为正时w变小，应当使原来的w减去更新的数值，即
  $w^{(k+1)}=w^{(k)}-η\frac{\partial J}{\partial w}|_{w=w^{(k)}} \\if(\frac{\partial J}{\partial w}==0) \ \ \ then \ \ stop$w(k+1)=w(k)−η∂w∂J​∣w=w(k)​if(∂w∂J​==0)   then  stop
  实际上，J的gradient就是微积分中梯度的概念，即
  $\nabla J= \begin{bmatrix} \frac{\partial J}{\partial w} \end{bmatrix}_{gradient}$∇J=[∂w∂J​​]gradient​

• 此时$w^{(i)}$w(i)对应的斜率为0，我们找到了一个极小值local minima，这就出现了一个问题，当微分为0的时候，参数就会一直卡在这个点上没有办法再更新了，因此通过gradient descent找出来的solution可能并不是最佳解global minima。

  但幸运的是，在linear regression上，loss function是convex凸函数（二阶导数大于0），是没有local minima的，因此可以使用这个方法。

批量梯度下降算法batch gradient descent

在每一个步长内检查整个训练集中的所有样本，即$w^{(k+1)}=w^{(k)}-η\frac{\partial J}{\partial w}|_{w=w^{(k)}} = w^{(k)}-η\sum_{i=1}^{n}((w^{(k)})^Tx_i-y_i)*x_i$w(k+1)=w(k)−η∂w∂J​∣w=w(k)​=w(k)−ηi=1∑n​((w(k))Txi​−yi​)∗xi​

随机梯度下降法stochastic gradient descent

也叫增量梯度下降法（incremental gradient descent）

在一个步长内检查一个样本，对查询到的每个样本都进行运算。即

循环{

​ i从1到m{

$w^{(k+1)}=w^{(k)}-η\frac{\partial J}{\partial w}|_{w=w^{(k)}} = w^{(k)}-η((w^{(k)})^Tx_i-y_i)*x_i$w(k+1)=w(k)−η∂w∂J​∣w=w(k)​=w(k)−η((w(k))Txi​−yi​)∗xi​

​ }

}

总结

通常情况下，随机梯度下降法查找到足够接近最低值的速度比批量梯度下降法更快一些。（但也有可能会一直无法收敛（converge）到最小值，这时候会一直在最小值附近震荡；不过通常情况下在最小值附近的这些值大多数也足以满足精度要求）。在训练集很大的情况下，随机梯度下降往往比批量梯度下降更受青睐。

二、Polynomial Regression多项式回归

为函数添加高次项，以更好拟合数据。但是当高次项过多时，容易出现过拟合。

过拟合的解决方法

1.加数据

2.特征选择、特征提取PCA

3.正则化

三、Regularization正则化

regularization正则化可以使曲线变得更加smooth，使得在training data上的error变大，但是 testing data上的error变小，用于解决overfitting过拟合问题。

正则化框架

$\hat{w}={arg}\ \underset{w}{min} [L(w)+\lambda P(w)]$w^=arg wmin​[L(w)+λP(w)]

P：Penalty

1.L1正则化 Lasso Regression套索回归

Lasso 回归与Ridge回归有一点不同，它使用的惩罚函数是L1范数，而不是L2范数。这导致惩罚值（或等于约束估计的绝对值之和）使一些参数估计结果等于零。使用惩罚值越大，进一步估计会使得缩小值越趋近于零。这将导致要从给定的n个变量中选择变量。

如果预测的一组变量是高度相关的，Lasso 会选出其中一个变量并且将其它的收缩为零。

$P(w) = ||w||$P(w)=∣∣w∣∣

2.L2正则化 Ridge Regression岭回归

目的

当数据之间存在多重共线性（自变量高度相关）时，就需要使用岭回归分析。在存在多重共线性时，尽管最小二乘法（OLS）测得的估计值不存在偏差，它们的方差也会很大，从而使得观测值与真实值相差甚远。岭回归通过给回归估计值添加一个偏差值，来降低标准误差。

损失函数形式

$P(w) = ||w||^2=W^TW$P(w)=∣∣w∣∣2=WTW

$L=\sum\limits_i^n(\widehat{y}^i-\sum\limits_{j}w_jx_j)^2+\lambda\sum(w_i)^2$L=i∑n​(y​i−j∑​wj​xj​)2+λ∑(wi​)2

$\lambda\sum(w_i)^2$λ∑(wi​)2是惩罚项。

步骤

1. 先设定λ

2. 确定loss function

3. 找到使loss最小的$w$w，确定function

4. 计算error

5. 重新设定新的λ重复上述步骤

6. 选取使testing data上的error最小的λ所对应的$w$w即为最佳的function

解释

我们期待参数$w_i$wi​越小甚至接近于0，因为这样函数是比较平滑的，当输入有变化的时候，output对输入的变化是比较不敏感的，噪声产生的影响就会比较小；但是又不喜欢太平滑的function，因为它就失去了对data拟合的能力。而function的平滑程度，就需要通过调整λ来决定。

方程求解

$J(w)=\sum_{i=1}^{n}||w^Tx_i-y_i||^2+\lambda w^Tw \\=W^TX^TXW-2W^TX^TY+Y^TY+\lambda W^TW \\=W^T(X^TX+\lambda I)W-2W^TX^TY+Y^TY$J(w)=i=1∑n​∣∣wTxi​−yi​∣∣2+λwTw=WTXTXW−2WTXTY+YTY+λWTW=WT(XTX+λI)W−2WTXTY+YTY

优化目标$\hat{w}={arg}\ \underset{w}{min} J(w)$w^=arg wmin​J(w)
$\frac{\partial J(w)}{\partial w}=2(X^TX+\lambda I)W-2X^TY=0 \\ \hat{w}=(X^TX+\lambda I)^{-1}X^TY$∂w∂J(w)​=2(XTX+λI)W−2XTY=0w^=(XTX+λI)−1XTY
没有正则化时$\hat{w}=(X^TX)^{-1}X^TY$w^=(XTX)−1XTY，$X^TX$XTX可能不存在逆，而$X^TX$XTX是半正定矩阵，$I$I是单位对角矩阵，则$X^TX+\lambda I$XTX+λI一定是正定矩阵，则一定存在逆。

概率证明

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qMeC2pNH-1596953961843)(img/1.Regression/regularization-L2-proof.png)]

Regularized LSE(最小二乘估计) <==>MAP(最大后验估计) （当noise为Guassian Dist时）

=2(X^TX+\lambda I)W-2X^TY=0
\ \hat{w}=(X^TX+\lambda I)^{-1}XTY
$$
没有正则化时$\hat{w}=(X^TX)^{-1}X^TY$w^=(XTX)−1XTY，$X^TX$XTX可能不存在逆，而$X^TX$XTX是半正定矩阵，$I$I是单位对角矩阵，则$X^TX+\lambda I$XTX+λI一定是正定矩阵，则一定存在逆。

概率证明

Regularized LSE(最小二乘估计) <==>MAP(最大后验估计) （当noise为Guassian Dist时）