线性回归与递归最小二乘算法 (R.L.S algorithm)

作者: jieyao | 来源:发表于2020-02-01 05:34 被阅读0次

线性回归与递归最小二乘算法 (R.L.S algorithm)
线性回归
算法工程师知识树持续更新
机器学习算法总结
矩阵: QR分解 && 最小二乘问题求解
最小二乘与线性回归
非线性最小二乘法
机器学习
机器学习算法速览表
最小二乘法及矩阵求导

1. 矩阵求逆引理 Matrix inversion lemma

矩阵 $A$ , $B$ 都是 m x n（m行 n列）矩阵 $D$ 是 n x n

若 $A= B^{-1} + CD^{-1}C^{T}$ （公式1）

则它的逆矩阵为 $A^{-1}= B - BC(D+C^{T}BC)^{-1}C^{T}B$ （公式2）

如果把vector $\mathbf{x}$ 看成是一个 Nx1的矩阵,根据以上公式可得，

$(A + \mathbf{x}\mathbf{x^{T}})^{-1} = A^{-1}-\frac{A^{-1}\mathbf{x}\mathbf{x^{T}}A^{-1}}{1+\mathbf{x^{T}A^{-1}\mathbf{x}}}$

这里的 $A$ 相当于公式1中的 $B^{-1}$ ，

$\frac{1}{1+\mathbf{x^{T}A^{-1}\mathbf{x}}}$ 是对应公式2的 $(D+C^{T}BC)^{-1}$ 部分，其结果是一个标量scalar,即一个数值

2. Linear regression 线性回归

Data: $\left\{ x_{n}, y_{n} \right\}^N_{n=1}$ $y_{n}$ 是scalar

Model: $y=w^{T}x+V$

注意：这里V不是bias, bias 项包含在 $w$ 里面，这里 $V$ 是指noise 并且假设其服从均匀分布，则

噪音 Noise: $v \sim N(0,\sigma ^{2} )$

误差Error 记为: $E=\sum_{n=1}^{N}\left(y_{n}-\boldsymbol{w}^{t} \boldsymbol{x}_{n}\right)^{2}$ $E=\sum_{n=1}^{N}\left(y_{n}-\boldsymbol{w}^{t} \boldsymbol{x}_{n}\right)^{2}$

若将误差以矩阵的形式表示，则 $E=\|\mathbf{y}-X \mathbf{w\|^{2}}$

$X$ 矩阵是一个 n 行 (p+1) 列的矩阵，n表示数据量，p则对应数据的维度,多一列常数是为了计算bias，它的每一行是每次输入(向量)的转置的每一行对应每次输入的转置（input is a vector），即 $x_{n}^{T}$ , 如下图所示

$X=\left(\begin{array}{cccc}{1} & {x_{11}} & {\cdots} & {x_{1 p}} \\ {1} & {x_{21}} & {\cdots} & {x_{2 p}} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {1} & {x_{n 1}} & {\cdots} & {x_{n p}}\end{array}\right)$ $\mathbf{y}=\left(\begin{array}{cccc}{y_{1}} \\ {y_{2}} \\ {\vdots} \\ {y_{n}}\end{array}\right)$

我们希望最小化E，且此时 $w$ 是未知，于是，可以求取其梯度，即对 $w$ 进行求导，可得

$\begin{aligned} \nabla_{\boldsymbol{w}} E &=2 X^{T}(\boldsymbol{y}-X \boldsymbol{w}) \\ \end{aligned}$

1. 如果是静态的数据，即数据一次性给出，则可以求出w

$\begin{aligned} \nabla_{\boldsymbol{w}} E &=\mathbf{0} \end{aligned}$ 则 $\boldsymbol{w}=\left(X^{T} X\right)^{-1} X^{t} \boldsymbol{y}$

2. 如果是动态的数据，即数据是一直在更新中，源源不断的产生，则可以通过梯度下降的方式更新 $w$

方法一：批量模式 batch mode

$\begin{aligned} \mathbf{w_{k+1}} & = \mathbf{w_{k}} - \eta \nabla_{\boldsymbol{w}} E \\& =2 X^{T}(\boldsymbol{y}-X \boldsymbol{w}_{k}) \end{aligned}$

方法二：随机梯度下降 stochastic update （sample by sample）, 即随机从样本数据 $\left\{ x_{n}, y_{n} \right\}$ 中选取一个样本，用来更新 $w$

$\mathbf{w}_{k+1}=\mathbf{w}_{k}-\eta\left(y_{k}-\boldsymbol{x}_{k}^{T} \mathbf{w}_{k}\right)$

但是这种方式收敛过程中会存在更多的噪声，其error 如下图所示

梯度下降

3. Recursive Least Squares 递归最小二乘算法

我们也可以通过递归最小二乘的方式得到线性模型

（备注：很多时候都会讲到最小二乘，它又叫做最小平方法，即求得其的最小平方和，比如通过最小二乘，得到模型的残差bias最小, 即最小化目标值与模型预估值的距离的平方和）

令 $R_{n}=X^{T}_{n}X_{n}$ ，有上文可得， $\boldsymbol{w}=\left(X^{T} X\right)^{-1} X^{T} \boldsymbol{y}=\left(R_{n}\right)^{-1} X^{T} \boldsymbol{y}$

在w的表达式中，比较麻烦的是求 $R_{n}^{-1}$ ,如果得到它，那么我们就能成功求得w,得到我们的线性模型。

如果我们的数据是源源不断的进来，即没法一次性取得所有的数据，我们可以通过最小二乘递归的方式，不断更新w。下面会讨论如何求得逆矩阵。

矩阵相乘

如上图所示，根据矩阵相乘的基本原理，可以得出， $X^{T}_{n}X_{n} = X^{T}_{n-1}X_{n-1} + \mathbf{x_{n}}\mathbf{x_{n}^{T}}$ ，即 $R_{n} = R_{n-1}+ \mathbf{x_{n}}\mathbf{x_{n}^{T}}$ 其中， $x_{n}$ 可以认为是只有一列的矩阵（px1）。

根据前文提到的matrix inversion lemma, 可以求得其逆矩阵 $R_{n}^{-1}$

$\begin{equation}\begin{aligned}R_{n}^{-1} &= (R_{n-1}+ \mathbf{x_{n}}\mathbf{x_{n}^{T}})^{-1} \\ &= R_{n-1}^{-1}-\frac{R_{n-1}^{-1}\mathbf{x_{n}}\mathbf{x_{n}^{T}}R_{n-1}^{-1}}{1+\mathbf{x_{n}^{T}R_{n-1}^{-1}\mathbf{x_{n}}}} \end{aligned} \end{equation}$

表达式虽然看上去很复杂，但是计算比原始的逆运算简单，只要记录上一次逆运算的结果，结合当前最新的输入数据 $x_{n}$ ，便可得到 $R_{n}^{-1}$ 从而避免了复杂的矩阵求逆过程,进而得到w.

令 $z_{n}=X^{t}\mathbf{y}=\sum_{i=1}^{n}x_iy_i$

$\boldsymbol{w}=\left(X^{T} X\right)^{-1} X^{T} \boldsymbol{y}=\left(R_{n}\right)^{-1} X^{T} \boldsymbol{y}= R_{n}^{-1} z_{n}$ （公式3）

残差bias $e_{n} = w^{T}x_{n}-y_{n}$

在现实中，新的数据往往会比旧的数据更有意义，所以需要引入一个遗忘因子 $\lambda \in [0,1]$ （一般在0.98到1之间选择），来评估数据对当前模型的影响，使得越往后数据影响越大（这个实际是加权最小二乘的内容）。对于静态的数据而言，即能够一次性给出所有数据，则没有必要考虑遗忘因子。

遗忘因子

此时我们的误差函数为 $E = \sum_{i=0}^{n-1} \lambda^{n-i-1} e_{i}^{2}$ 我们的目标是通过最小化误差求得 $w$ , 由上可知 $\boldsymbol{w}= R_{n}^{-1} z_{n}$

此时 $z_{n-1}=\sum_{i=1}^{n-1}\lambda^{(n-1)-i}x_iy_i$ $R_{n-1}=\sum_{i=0}^{n-1}\lambda^{(n-1)-i}x_{i}x_{i}^{T}$

$\begin{equation} \begin{aligned} R_{n} & =\sum_{i=0}^{n-1}\lambda^{n-i}x_{i}x_{i}^{T} + x_{n}x_{n}^{T} \\ & = \lambda\left[\sum_{i=0}^{n-1}\lambda^{(n-1)-i}x_{i}x_{i}^{T} \right] + x_{n}x_{n}^{T} \\ & =\lambda R_{n-1} + x_{n}x_{n}^{T} \end{aligned}\end{equation}$

根据前文提到的matrix inversion lemma, 可以求得其逆矩阵

$\begin{equation}\begin{aligned}R_{n}^{-1} &= (R_{n-1}+ \mathbf{x_{n}}\mathbf{x_{n}^{T}})^{-1} \\ &= \frac{1}{\lambda} R_{n-1}^{-1}-\frac{\frac{1}{\lambda^{2}} R_{n-1}^{-1}\mathbf{x_{n}}\mathbf{x_{n}^{T}}R_{n-1}^{-1}}{1+\mathbf{x_{n}^{T}\frac{1}{ \lambda} R_{n-1}^{-1}\mathbf{x_{n}}}} \end{aligned} \end{equation}$ (公式4)

为了方便计算，引入增益矢量 gain vector $k_{n}= \frac{\frac{1}{\lambda} P_{n-1}\mathbf{x_{n}} }{1+\frac{1}{ \lambda}\mathbf{x_{n}^{T} P_{n-1}\mathbf{x_{n}}}}$ （公式5）

且定义 $P_{n}=R_{n}^{-1}$ $P_{n-1}=R_{n-1}^{-1}$ ，则由公式4，公式5可得

$\begin{aligned} P_{n} &=\frac{1}{\lambda} P_{n-1}-\frac{\frac{1}{\lambda^{2}} P_{n-1} \boldsymbol{x}_{n} \boldsymbol{x}_{n}^{T} P_{n-1}}{1+\boldsymbol{x}_{n}^{T} \frac{1}{\lambda} P_{n-1} \boldsymbol{x}_{n}} \\ &=\frac{1}{\lambda} P_{n-1}-\frac{1}{\lambda} \boldsymbol{k}_{n} \boldsymbol{x}_{n}^{T} P_{n-1} \end{aligned}$ (公式6)

增益矢量可以进一步化简，得到以下关系 $k_{n} = P_{n}x_{n}$ (公式7), 其推导如下

$\begin{equation} \begin{aligned} & k_{n}= \frac{\frac{1}{\lambda} P_{n-1}\mathbf{x_{n}} }{1+\frac{1}{ \lambda}\mathbf{x_{n}^{T} P_{n-1}\mathbf{x_{n}}}} \\ &k_{n} + k_{n} \frac{1}{ \lambda }x_{n}^{T} P_{n-1}x_{n} = \frac{1}{ \lambda } P_{n-1} x_{n} \\ &k_{n} = \frac{1}{ \lambda } \left[ P_{n-1} - k_{n}x_{n}^{T} P_{n-1} \right] x_{n} = P_{n}x_{n}\end{aligned}\end{equation}$

公式3可知权值 $\boldsymbol{w}= R_{n}^{-1} z_{n} = P_{n} z_{n}$ 带入公式6 $P_{n}$ 与公式7的结论则

$\begin{aligned} \boldsymbol{w}_{n} &=P_{n} \boldsymbol{z}_{n} \\ &=P_{n}\left[\lambda \boldsymbol{z}_{n-1}+\boldsymbol{x}_{n} y_{n}\right] \\ &=\lambda P_{n} \boldsymbol{z}_{n-1}+P_{n} \boldsymbol{x}_{n} y_{n} \\ &=\lambda\left[\frac{1}{\lambda} P_{n-1}-\frac{1}{\lambda} \boldsymbol{k}_{n} \boldsymbol{x}_{n}^{T} P_{n-1}\right] \boldsymbol{z}_{n-1}+P_{n} \boldsymbol{x}_{n} y_{n} \\ &=P_{n-1} \boldsymbol{z}_{n-1}-\boldsymbol{k}_{n} \boldsymbol{x}_{n}^{T} P_{n-1} \boldsymbol{z}_{n-1}+P_{n} \boldsymbol{x}_{n} y_{n} \\ &=\boldsymbol{w}_{n-1}-\boldsymbol{k}_{n}\left(\boldsymbol{x}_{n}^{T} \boldsymbol{w}_{n-1}-y_{n}\right) \end{aligned}$

即 new weight = old weight - gain * prediction error

递归最小二乘算法总结：

1. 计算增益矢量 $k_{n}= \frac{\frac{1}{\lambda} P_{n-1}\mathbf{x_{n}} }{1+\frac{1}{ \lambda}\mathbf{x_{n}^{T} P_{n-1}\mathbf{x_{n}}}}$

2. 计算 $\begin{aligned} P_{n} &=\frac{1}{\lambda} P_{n-1}-\frac{1}{\lambda} \boldsymbol{k}_{n} \boldsymbol{x}_{n}^{T} P_{n-1} \end{aligned}$

3. 计算权值 $\begin{aligned} \boldsymbol{w}_{n} = \boldsymbol{w}_{n-1}-\boldsymbol{k}_{n}\left(\boldsymbol{x}_{n}^{T} \boldsymbol{w}_{n-1}-y_{n}\right) \end{aligned}$

RLS表现出极快的收敛性，且不需要对矩阵进行求逆运算，在这个方面能节省计算量。计算时不需要加载所有的数据，从而节省了内存，但是，这种好处是以高计算复杂度为代价的。

线性回归与递归最小二乘算法 (R.L.S algorithm)
1. 矩阵求逆引理 Matrix inversion lemma 矩阵 , 都是 m x n（m行 n列）矩阵是...
线性回归
线性回归是机器学习算法的入门，通过该算法，管中窥豹，研究该算法的精髓之处。线性回归线性回归的损失函数为最小二乘...
算法工程师知识树持续更新
机器学习算法监督学习分类模型LRSVM决策树NB回归模型线性回归最小二乘融合模型baggingRFboosti...
机器学习算法总结
回归算法线性回归算法：支持向量机&向前逐步回归&惩罚线性回归（岭回归/套索回归/ElasticNet/最小角度...
矩阵: QR分解 && 最小二乘问题求解
最小二乘问题分为线性最小二乘问题和非线性最小二乘问题;非线性最小二乘问题求解方法有高斯牛顿法，Levenberg-...
最小二乘与线性回归
现行的最小二乘法是勒让德( A. M. Legendre)于1805年在其著作《计算慧星轨道的新方法》中提出的。它...
非线性最小二乘法
很多问题最终归结为一个最小二乘问题，求解最小二乘的方法也很多。内容来自Gauss-Newton非线性最小二乘算法...
机器学习
监督学习：分类与回归线性回归：线性模型：最小二乘法，岭回归，lasso回归解决线性问题...
机器学习算法速览表
1. 回归普通最小二乘回归（OLSR）线性回归 Logistic回归逐步回归多变量自适应回归样条曲线（MA...
最小二乘法及矩阵求导
矩阵的迹定义如下最小二乘法最小二乘的概率解释最小即可。这就解释了线性回归为什么要选用最小二乘作为衡量指标了。...