Linear Regression

发表于 更新于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

Linear Regression

Model representation

线性回归的预测方程可以写为

hθ(x)=∑i=0nθixih_\theta(x) = \sum_{i=0}^n\theta_ix_i

其中规定 x0=1x_0 = 1。

若令

θ=[θ0θ1⋮θn]∈Rn+1,X=[x0x1⋮xn]∈Rn+1\boldsymbol{\theta} = \begin{bmatrix}\theta_0 \\ \theta_1 \\ \vdots \\ \theta_n\end{bmatrix} \in \mathbb R^{n+1}, \boldsymbol{X} = \begin{bmatrix}x_0 \\ x_1 \\ \vdots \\ x_n\end{bmatrix} \in \mathbb R^{n+1}

则预测方程可以写为

hθ(x)=θTXh_\theta(x) = \boldsymbol{\theta}^\mathrm T\boldsymbol{X}

Cost function

线性回归的代价函数为

J(θ)=12m∑i=1m(hθ(x(i))−y(i))2J(\boldsymbol{\theta}) = \dfrac 1{2m}\sum_{i=1}^m\left(h_\theta(x^{(i)}) - y^{(i)} \right)^2

此时梯度下降式成为

θj:=θj−α1m∑i=1m(hθ(x(i))−y(i))xj(i)\theta_j := \theta_j - \alpha \dfrac 1m\sum_{i=1}^m\left(h_\theta(x^{(i)}) - y^{(i)}\right)x_j^{(i)}

Feature Scaling

所谓的特征缩放，其目的是使所有的特征都能处在一个基本一致的区间内，不会因为某个特征的值都过大或过小而对计算造成误差或难以计算。（即归一化、标准化、正则化）

例如对于一个二维的数据，其中有一维数据比另一维数据大很多，这可能会导致在梯度下降时过分缓慢，出现反复来回震荡的问题。如果将数据进行归一化，可以证明，梯度下降可以找到一条更快地找到全局最小的路径。

归一化希望使所有的特征都能在 approximately −1≤xi≤1-1 \leq x_i \leq 1 的范围内，只要他们足够接近，梯度下降法就会正常地工作。

Mean Normalization

均值归一化是将所有的值 xix_i 都减去其平均值 μi\mu_i，再除以数据的范围 max⁡−min⁡\max - \min

xi=xi−μimax⁡−min⁡x_i = \dfrac{x_i - \mu_i}{\max - \min}

假设 x1∈[0,2000]x_1 \in [0, 2000]，那么对于 x1x_1 的均值归一化为 x1=x1−10002000x_1 = \dfrac{x_1 - 1000}{2000}，如此处理后所有特征都会被缩放在 [−0.5,0.5][-0.5, 0.5] 这一区间内。

min-max Normalization

min-max 归一化是对均值归一化的改进，其公式为

xi=xi−min⁡max⁡−min⁡x_i = \dfrac{x_i - \min}{\max - \min}

其中 max⁡\max 为这组特征的最大值，min⁡\min 为这组特征的最小值。

Learning Rate

image-20221229211633436

image-20221229211638997

Features and polynomial regression

有时不必直接使用给出的特征构造模型，可以新定义一个特征，如此可能会得到一个更好的模型。

image-20221229211645004

关系不一定是线性的，有时需要通过高维进行拟合

如果想使用线性回归的话，可以令 xi=xkx_i = x^k，如此便可得到一个线性回归形式的式子，这样的话归一化变得更为重要。

特征选定可以根据实际情况来改，训练后看测试结果是否符合

Normal equation

Normal equation 是一个计算参数 θ\theta 的解析解法，使得我们不用通过梯度下降法这一迭代算法进行计算。

以 1D 举例：J(θ)=aθ2+bθ+c,θ∈RJ(\theta) = a\theta^2+b\theta+c, \theta \in \mathbb{R}，找到这个函数的最小值只需求此函数的驻点（即一阶导数的零点）即可。

但当 θ∈Rn+1\theta \in \mathbb{R}^{n+1} 时，J(θ⃗)=12m∑i=1m(hθ(x(i))−y(i))2J(\vec\theta) = \dfrac 1{2m}\sum\limits_{i = 1}^m\left(h_\theta\left(x^{(i)}\right) - y^{(i)}\right)^2，找到这个函数的最小值相当于求满足

∂∂θjJ(θ⃗)=0, j=0,1,…,m\dfrac{\partial}{\partial \theta_j}J(\vec\theta) = 0,\ j = 0, 1, \dots, m

的一组 θ\theta 值。
image-20221229211655693

通过数据构造一个矩阵

X=[12104514511416324011534323018522136]X = \begin{bmatrix}1 & 2104 & 5 & 1 & 45\\ 1 & 1416 & 3 & 2 & 40\\ 1 & 1534 & 3 & 2 & 30 \\ 1 & 852 & 2 & 1 & 36\end{bmatrix}

和一个向量

y=[460232315178]y = \begin{bmatrix}460 \\ 232 \\ 315 \\ 178\end{bmatrix}

可以发现，XX 为一个 m×(n+1)m \times (n + 1) 的矩阵，yy 是一个 mm 维向量，其中 mm 为数据集大小，nn 为特征变量数。

由于在线性回归中，我们希望确定 ω,b\omega, b 使得

f(xi)=ωxi+b≃yi\begin{aligned} f(x_i) = \omega x_i + b \simeq y_i \end{aligned}

此时我们可以通过令均方误差最小化得到 ω,b\omega, b 的解 ω∗,b∗\omega^*, b^*

(ω∗,b∗)=arg⁡min⁡(ω,b)∑i=1m(f(xi)−yi)2=arg⁡min⁡(ω,b)∑i=1m(yi−ωxi−b)2=E(ω,b)\begin{aligned}\left(\omega^*, b^*\right) &= \arg\min_{(\omega, b)}\sum\limits_{i=1}^m\left(f(x_i) - y_i\right)^2 \\ &= \arg \min_{(\omega, b)}\sum\limits_{i=1}^m\left(y_i - \omega x_i - b\right)^2 = E(\omega, b)\end{aligned}

令上式分别对 ω\omega 和 bb 求导可得

∂E∂ω=2(ω∑i=1mxi2−∑i=1m(yi−b)xi)∂E∂b=2(mb−∑i=1m(yi−ωxi))\begin{aligned}\dfrac{\partial E}{\partial \omega} &= 2\left(\omega \sum\limits_{i=1}^m{x_i^2} - \sum\limits_{i = 1}^m{(y_i - b)x_i}\right) \\ \dfrac{\partial E}{\partial b} &= 2\left(mb - \sum\limits_{i = 1}^m(y_i - \omega x_i)\right)\end{aligned}

令上述两式分别为 0，可得 ω\omega 和 bb 最优解的闭式解

ω=∑i=1myi(xi−x‾)∑i=1mxi2−1m(∑i=1mxi)2b=1m∑i=1m(yi−ωxi)\begin{aligned}\omega &= \dfrac{\sum\limits_{i=1}^m{y_i(x_i - \overline x)}}{\sum\limits_{i=1}^m{x_i^2} - \frac 1m \left(\sum\limits_{i=1}^m{x_i}\right)^2} \\ b &= \dfrac 1m \sum\limits_{i=1}^m\left(y_i - \omega x_i\right)\end{aligned}

其中 x‾\overline x 为 xx 的均值。

更一般地，当特征不唯一时，我们的 ω\omega 将是一个矩阵，令 w^∗=(ω⃗; b)\hat{\boldsymbol{w}}^{*} = \left(\vec\omega;\ b\right)，则其解为

w^∗=arg⁡min⁡w^(y−Xw^)T(y−Xw^)\hat{\boldsymbol{w}}^{*}=\underset{\hat{\boldsymbol{w}}}{\arg \min }(\boldsymbol{y}-\mathbf{X} \hat{\boldsymbol{w}})^{\mathrm{T}}(\boldsymbol{y}-\mathbf{X} \hat{\boldsymbol{w}})

令 Ew^=(y−Xω^⃗)T(y−Xω^⃗)E_{\hat{\boldsymbol{w}}} = \left(y - X\vec{\hat\omega}\right)^T\left(y - X\vec{\hat\omega}\right)，对 ω^⃗\vec{\hat\omega} 求导得到

∂Ew^∂w^=2XT(Xw^−y)\dfrac{\partial E_{\hat{\boldsymbol{w}}}}{\partial \hat{\boldsymbol{w}}}=2 \mathbf{X}^{\mathrm{T}}(\mathbf{X} \hat{\boldsymbol{w}}-\boldsymbol{y})

令上式为 0 即可得到 w^\hat{\boldsymbol{w}} 最优解的闭式解。当 XTX\mathbf{X}^{\mathrm{T}}\mathbf{X} 为满秩矩阵时可得 θ⃗=(XTX)−1XTy\vec\theta = (\mathbf{X}^{\mathrm{T}}\mathbf{X})^{-1}\mathbf{X}^{\mathrm{T}}y。

于是我们得到 θ⃗=(XTX)−1XTy\vec\theta = (\mathbf{X}^{\mathrm{T}}\mathbf{X})^{-1}\mathbf{X}^{\mathrm{T}}y，这个 θ⃗\vec\theta 就是使代价函数最小的 θ⃗\vec\theta。

更普适地，令 X=[1⋯(x(1))T⋯1⋯(x(2))T⋯⋮⋮⋮⋮1⋯(x(m))T⋯](m×(n+1))X = \begin{bmatrix}1 & \cdots & \left(x^{(1)}\right)^T & \cdots \\ 1 & \cdots & \left(x^{(2)}\right)^T & \cdots \\ \vdots & \vdots & \vdots & \vdots \\ 1 & \cdots & \left(x^{(m)}\right)^T & \cdots\end{bmatrix}_{(m \times (n+1))}，y=[y(1)y(2)⋮y(n)]y = \begin{bmatrix}y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(n)}\end{bmatrix}，则 θ⃗=(XTX)−1XTy\vec\theta = (\mathbf{X}^{\mathrm{T}}\mathbf{X})^{-1}\mathbf{X}^{\mathrm{T}}y。

如果直接使用正规方程法的话，没有必要对所有特征做特征缩放，如果使用梯度下降则必须对所有特征做特征缩放。
image-20221229211704560

由于矩阵乘法是 O(n3)\mathcal{O}(n^3) 的，在特征较多时会很慢，此时可以考虑梯度下降。
image-20221229211709856