递推最小二乘遗忘因子法(Recursive Forgetting Factor, RFF)

在普通的递推最小二乘算法中，随着数据的不断到来，显然矩阵X T X X^TX X T X中的元素会变得越来越大，而矩阵P k P_k P k ​作为X T X X^TX X T X的逆矩阵，则会逐渐趋于零，这时，模型将无法继续更新或者更新极其缓慢，这就是数据饱和现象。我们也可以更加直观的理解为，由于过去累加了很多的数据，当前到来的数据与之前累加的数据相比就如一滴水掉落到大海，不会惊起任何波澜。针对数据饱和问题，其中一个解决方案就是带遗忘因子的递推最小二乘法。

假设有数据( X , Y ) (X,Y)(X ,Y )，其中X ∈ R m × d X \in {\mathbb{R}^{m \times d}}X ∈R m ×d，Y ∈ R m × 1 Y \in {\mathbb{R}^{m \times 1}}Y ∈R m ×1，m m m为样本数，d d d为特征数，考虑最小二乘解

θ 0 = ( X T X ) − 1 X T Y = Σ 0 − 1 X T Y (1) \begin{aligned}{\theta_0} = {\left( {{X^{\rm{T}}}X} \right)^{ – 1}}{X^{\rm{T}}}Y = {\Sigma_0}^{-1}{X^{\rm{T}}}Y \tag{1}\end{aligned}θ0 ​=(X T X )−1 X T Y =Σ0 ​−1 X T Y ​(1 )

⇒ Σ 0 θ 0 = X T Y (2) \Rightarrow {\Sigma_0}{\theta_0} = {X^{\rm{T}}}Y \tag{2}⇒Σ0 ​θ0 ​=X T Y (2 )

当新数据( X 1 , Y 1 ) \left( {{X_1},{Y_1}} \right)(X 1 ​,Y 1 ​)到来时，更新模型。我们希望当前的数据对于回归结果更加重要，而过去数据的重要性随着时间的回溯依次降低，从而使得模型能够更好的适应当前数据的变化，克服数据饱和问题。为了达到上述目的，我们可以给之前数据的损失乘以一个权重 α , 0 < α < 1 \alpha, 0，即
α ∥ Y − X θ ∥ 2 2 + ∥ Y 1 − X 1 θ ∥ 2 2 = ∥ [ α Y Y 1 ] − [ α X X 1 ] θ ∥ 2 2 \alpha \left\| {Y – X\theta } \right\|_2^2 + \left\| {{Y_1} – {X_1}\theta } \right\|_2^2 = \left\| {\left[ {\begin{array}{cc} {\sqrt \alpha Y} \ {{Y_1}} \end{array}} \right] – \left[ {\begin{array}{cc} {\sqrt \alpha X} \ {{X_1}} \end{array}} \right]\theta } \right\|_2^2 α∥Y −X θ∥2 2 ​+∥Y 1 ​−X 1 ​θ∥2 2 ​=∥∥∥∥​[α​Y Y 1 ​​]−[α​X X 1 ​​]θ∥∥∥∥​2 2 ​
于是得到新的回归系数

θ 1 = ( [ α X X 1 ] T [ α X X 1 ] ) − 1 [ α X X 1 ] T [ α Y Y 1 ] = Σ 1 − 1 [ α X X 1 ] T [ α Y Y 1 ] (3) \begin{aligned} {\theta_1} &= {\left( {{{\left[ {\begin{array}{cc} {\sqrt \alpha }X\ {{X_1}} \end{array}} \right]}^{\rm{T}}}\left[ {\begin{array}{cc} {\sqrt \alpha }X\ {{X_1}} \end{array}} \right]} \right)^{ – 1}}{\left[ {\begin{array}{cc} {\sqrt \alpha }X\ {{X_1}} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{cc} {\sqrt \alpha }Y\ {{Y_1}} \end{array}} \right] \ &= {\Sigma _1}^{ – 1}{\left[ {\begin{array}{cc} {\sqrt \alpha }X\ {{X_1}} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{cc} {\sqrt \alpha }Y\ {{Y_1}} \end{array}} \right]\tag{3} \end{aligned}θ1 ​​=([α​X X 1 ​​]T [α​X X 1 ​​])−1 [α​X X 1 ​​]T [α​Y Y 1 ​​]=Σ1 ​−1 [α​X X 1 ​​]T [α​Y Y 1 ​​]​(3 )

Σ 1 = [ α X X 1 ] T [ α X X 1 ] = α X T X + X 1 T X 1 = α Σ 0 + X 1 T X 1 (4) \begin{aligned} {\Sigma _1} &= {\left[ {\begin{array}{cc} {\sqrt \alpha }X\ {{X_1}} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{cc} {\sqrt \alpha }X\ {{X_1}} \end{array}} \right] \ &= \alpha {X^{\rm{T}}}X + X_1^{\rm{T}}{X_1} \ &= \alpha {\Sigma _0} + X_1^{\rm{T}}{X_1} \end{aligned} \tag{4}Σ1 ​​=[α​X X 1 ​​]T [α​X X 1 ​​]=αX T X +X 1 T ​X 1 ​=αΣ0 ​+X 1 T ​X 1 ​​(4 )

⇒ α Σ 0 = Σ 1 − X 1 T X 1 (5) \begin{aligned} \Rightarrow \alpha {\Sigma _0} = {\Sigma _1} – X_1^{\rm{T}}{X_1} \end{aligned} \tag{5}⇒αΣ0 ​=Σ1 ​−X 1 T ​X 1 ​​(5 )

根据公式(4)的结果，通过归纳可得
Σ k = α Σ k − 1 + X k T X k (6) \begin{aligned} {\Sigma k} = \alpha {\Sigma {k – 1}} + X_k^{\rm{T}}{X_k} \end{aligned} \tag{6}Σk ​=αΣk −1 ​+X k T ​X k ​​(6 )
从公式(6)可以很容易看出，这是一个典型的套娃行为，当前的权重为1，上一次的权重为 α \alpha α，通过一次套娃 α Σ k − 1 = α 2 Σ k − 2 + α X k − 1 T X k − 1 \alpha{\Sigma {k-1}} = \alpha^2 {\Sigma {k – 2}} + \alpha X_{k-1}^{\rm{T}}{X_{k-1}}αΣk −1 ​=α2 Σk −2 ​+αX k −1 T ​X k −1 ​，我们发现上上次的权重变成了α 2 \alpha^2 α2，依次类推，最终我们发现随着时间的回溯，越久的数据权重会越来越低并逐渐趋于0。
[ α X X 1 ] T [ α Y Y 1 ] = α X T Y + X 1 T Y 1 = α Σ 0 θ 0 + X 1 T Y 1 / / 公 式 ( 2 ) 结 果 替 换 得 到 = ( Σ 1 − X 1 T X 1 ) θ 0 + X 1 T Y 1 / / 公 式 ( 5 ) 结 果 替 换 得 到 = Σ 1 θ 0 + X 1 T ( Y 1 − X 1 θ 0 ) (7) \begin{aligned} {\left[ {\begin{array}{cc} {\sqrt \alpha }X\ {{X_1}} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{cc} {\sqrt \alpha }Y\ {{Y_1}} \end{array}} \right] &= \alpha {X^{\rm{T}}}Y + X_1^{\rm{T}}{Y_1}\ &= \alpha {\Sigma _0}{\theta_0} + X_1^{\rm{T}}{Y_1} \quad //公式(2)结果替换得到\ &= \left( {{\Sigma _1} – X_1^{\rm{T}}{X_1}} \right){\theta_0} + X_1^{\rm{T}}{Y_1} \quad //公式(5)结果替换得到\ &= {\Sigma _1}{\theta_0} + X_1^{\rm{T}}\left( {{Y_1} – {X_1}{\theta_0}} \right) \end{aligned} \tag{7}[α​X X 1 ​​]T [α​Y Y 1 ​​]​=αX T Y +X 1 T ​Y 1 ​=αΣ0 ​θ0 ​+X 1 T ​Y 1 ​//公式(2 )结果替换得到=(Σ1 ​−X 1 T ​X 1 ​)θ0 ​+X 1 T ​Y 1 ​//公式(5 )结果替换得到=Σ1 ​θ0 ​+X 1 T ​(Y 1 ​−X 1 ​θ0 ​)​(7 )

将公式(7)回带到公式(3)：

θ 1 = Σ 1 − 1 ( Σ 1 θ 0 + X 1 T ( Y 1 − X 1 θ 0 ) ) = θ 0 + Σ 1 − 1 X 1 T ( Y 1 − X 1 θ 0 ) (8) \begin{aligned} {\theta_1} &= {\Sigma _1}^{ – 1}\left( {{\Sigma _1}{\theta_0} + X_1^{\rm{T}}\left( {{Y_1} – {X_1}{\theta_0}} \right)} \right) \ &= {\theta_0} + {\Sigma _1}^{ – 1}X_1^{\rm{T}}\left( {{Y_1} – {X_1}{\theta_0}} \right) \end{aligned} \tag{8}θ1 ​​=Σ1 ​−1 (Σ1 ​θ0 ​+X 1 T ​(Y 1 ​−X 1 ​θ0 ​))=θ0 ​+Σ1 ​−1 X 1 T ​(Y 1 ​−X 1 ​θ0 ​)​(8 )

根据公式(8)的结果，通过归纳可得
θ k = θ k − 1 + Σ k − 1 X k T ( Y k − X k θ k − 1 ) (9) \begin{aligned} {\theta_k} = {\theta_{k – 1}} + {\Sigma k}^{ – 1}X_k^{\rm{T}}\left( {{Y_k} – {X_k}{\theta{k – 1}}} \right) \end{aligned} \tag{9}θk ​=θk −1 ​+Σk ​−1 X k T ​(Y k ​−X k ​θk −1 ​)​(9 )

到这里，已经能够实现对遗忘因子最小二乘的递推，其过程可概括如下，我们称为算法1:

但以上过程存在一个问题：

针对以上问题，我们要对公式进一步改造

根据Sherman-Morrison-Woodbury公式：
( A + U V T ) − 1 = A − 1 − A − 1 U ( I + V T A − 1 U ) − 1 V T A − 1 {\left( {A + U{V^{\rm{T}}}} \right)^{ – 1}} = {A^{ – 1}} – {A^{ – 1}}U{\left( {I + {V^{\rm{T}}}{A^{ – 1}}U} \right)^{ – 1}}{V^{\rm{T}}}{A^{ – 1}}(A +U V T )−1 =A −1 −A −1 U (I +V T A −1 U )−1 V T A −1
公式(6)的逆可写成如下形式

Σ k − 1 = ( α Σ k − 1 + X k T X k ) − 1 = 1 α Σ k − 1 − 1 − 1 α Σ k − 1 − 1 X k T ( α I + X k Σ k − 1 − 1 X k T ) − 1 X k Σ k − 1 − 1 (10) \begin{aligned} {\Sigma k}^{ – 1} &= {\left( \alpha {{\Sigma {k – 1}} + X_k^{\rm{T}}{X_k}} \right)^{ – 1}} \ &= \frac{1}{\alpha } \Sigma {k – 1}^{ – 1} – \frac{1}{\alpha }\Sigma {k – 1}^{ – 1}X_k^{\rm{T}}{\left( {\alpha I + {X_k}\Sigma {k – 1}^{ – 1}X_k^{\rm{T}}} \right)^{ – 1}}{X_k}\Sigma {k – 1}^{ – 1} \end{aligned} \tag{10}Σk ​−1 ​=(αΣk −1 ​+X k T ​X k ​)−1 =α1 ​Σk −1 −1 ​−α1 ​Σk −1 −1 ​X k T ​(αI +X k ​Σk −1 −1 ​X k T ​)−1 X k ​Σk −1 −1 ​​(1 0 )
令P k = ∑ k − 1 {P_k} = {\sum k}^{ – 1}P k ​=∑k ​−1，公式(10)变为：
P k = 1 α P k − 1 − 1 α P k − 1 X k T ( α I + X k P k − 1 X k T ) − 1 X k P k − 1 (11) \begin{aligned} {P_k} = \frac{1}{\alpha }{P{k – 1}} – \frac{1}{\alpha }{P_{k – 1}}X_k^{\rm{T}}{\left( {\alpha I + {X_k}{P_{k – 1}}X_k^{\rm{T}}} \right)^{ – 1}}{X_k}{P_{k – 1}} \end{aligned} \tag{11}P k ​=α1 ​P k −1 ​−α1 ​P k −1 ​X k T ​(αI +X k ​P k −1 ​X k T ​)−1 X k ​P k −1 ​​(1 1 )
公式(9)变为：
θ k = θ k − 1 + P k X k T ( Y k − X k θ k − 1 ) (12) \begin{aligned} {\theta_k} = {\theta_{k – 1}} + {P_k}X_k^{\rm{T}}\left( {{Y_k} – {X_k}{\theta_{k – 1}}} \right) \end{aligned} \tag{12}θk ​=θk −1 ​+P k ​X k T ​(Y k ​−X k ​θk −1 ​)​(1 2 )
注意到，公式(11)依然存在对 α I + X k P k − 1 X k T {\alpha I + {X_k}{P_{k – 1}}X_k^{\rm{T}}}αI +X k ​P k −1 ​X k T ​ 的求逆运算，这似乎依然没有解决上述问题1，我们避免了对 Σ k \Sigma_k Σk ​ 的求逆，但却又引入了一个新的逆。事实上，如果数据是逐个到达的，则 X k X_k X k ​ 为一个行向量(在本文中，一个样本我们用行向量表示，这主要是因为本文规定数据矩阵中每一行代表一个样本)，因此 α I + X k P k − 1 X k T {\alpha I + {X_k}{P_{k – 1}}X_k^{\rm{T}}}αI +X k ​P k −1 ​X k T ​ 最终得到结果为一个数值，我们无需矩阵求逆计算，只需要取它的倒数就好了，即
P k = 1 α P k − 1 − 1 α P k − 1 X k T X k P k − 1 α + X k P k − 1 X k T (13) \begin{aligned} {P_k} = \frac{1}{\alpha } {P_{k – 1}} – \frac{1}{\alpha } \frac{{{P_{k – 1}}X_k^{\rm{T}}{X_k}{P_{k – 1}}}}{{\alpha + {X_k}{P_{k – 1}}X_k^{\rm{T}}}} \end{aligned} \tag{13}P k ​=α1 ​P k −1 ​−α1 ​α+X k ​P k −1 ​X k T ​P k −1 ​X k T ​X k ​P k −1 ​​​(1 3 )
于是我们得到了新的递推算法如下,我们称为算法2：

一些书上的递推算法可能并非这样的形式，我们可以进一步对上述过程进行一些整理。在一些书中，K k = P k X k T {K_k} = {P_k}X_k^{\rm{T}}K k ​=P k ​X k T ​也被称为增益，Y k − X k θ k − 1 {Y_k} – {X_k}{\theta_{k – 1}}Y k ​−X k ​θk −1 ​被称为新息，顾名思义，就是引入的新信息。
K k = P k X k T = ( 1 α P k − 1 − 1 α P k − 1 X k T ( α I + X k P k − 1 X k T ) − 1 X k P k − 1 ) X k T / / 公 式 ( 11 ) 结 果 替 换 得 到 = P k − 1 X k T ( 1 α I − 1 α ( α I + X k P k − 1 X k T ) − 1 X k P k − 1 X k T ) = P k − 1 X k T ( α I + X k P k − 1 X k T ) − 1 ( 1 α ( α I + X k P k − 1 X k T ) − 1 α X k P k − 1 X k T ) = P k − 1 X k T ( α I + X k P k − 1 X k T ) − 1 (14) \begin{aligned} {K_k} &= {P_k}X_k^{\rm{T}}\ &= \left( \frac{1}{\alpha } {{P_{k – 1}} – \frac{1}{\alpha }{P_{k – 1}}X_k^{\rm{T}}{{\left( {\alpha I + {X_k}{P_{k – 1}}X_k^{\rm{T}}} \right)}^{ – 1}}{X_k}{P_{k – 1}}} \right)X_k^{\rm{T}} \quad //公式(11)结果替换得到\ &= {P_{k – 1}}X_k^{\rm{T}}\left( {\frac{1}{\alpha } I – \frac{1}{\alpha } {{\left( {\alpha I + {X_k}{P_{k – 1}}X_k^{\rm{T}}} \right)}^{ – 1}}{X_k}{P_{k – 1}}X_k^{\rm{T}}} \right)\ &= {P_{k – 1}}X_k^{\rm{T}}{\left( {\alpha I + {X_k}{P_{k – 1}}X_k^{\rm{T}}} \right)^{ – 1}}\left( \frac{1}{\alpha } {\left( {\alpha I + {X_k}{P_{k – 1}}X_k^{\rm{T}}} \right) – \frac{1}{\alpha } {X_k}{P_{k – 1}}X_k^{\rm{T}}} \right)\ &= {P_{k – 1}}X_k^{\rm{T}}{\left( {\alpha I + {X_k}{P_{k – 1}}X_k^{\rm{T}}} \right)^{ – 1}} \end{aligned} \tag{14}K k ​​=P k ​X k T ​=(α1 ​P k −1 ​−α1 ​P k −1 ​X k T ​(αI +X k ​P k −1 ​X k T ​)−1 X k ​P k −1 ​)X k T ​//公式(1 1 )结果替换得到=P k −1 ​X k T ​(α1 ​I −α1 ​(αI +X k ​P k −1 ​X k T ​)−1 X k ​P k −1 ​X k T ​)=P k −1 ​X k T ​(αI +X k ​P k −1 ​X k T ​)−1 (α1 ​(αI +X k ​P k −1 ​X k T ​)−α1 ​X k ​P k −1 ​X k T ​)=P k −1 ​X k T ​(αI +X k ​P k −1 ​X k T ​)−1 ​(1 4 )
将公式(14)的结果代入到公式(11)可得
P k = 1 α P k − 1 − 1 α K k X k P k − 1 = 1 α ( I − K k X k ) P k − 1 (15) \begin{aligned} {P_k} = \frac{1}{\alpha } {P_{k – 1}} – \frac{1}{\alpha } {K_k}{X_k}{P_{k – 1}} = \frac{1}{\alpha } \left( {I – {K_k}{X_k}} \right){P_{k – 1}} \end{aligned} \tag{15}P k ​=α1 ​P k −1 ​−α1 ​K k ​X k ​P k −1 ​=α1 ​(I −K k ​X k ​)P k −1 ​​(1 5 )
于是，算法2可进一步的写为如下形式，我们称为算法3：

Original: https://blog.csdn.net/qq_39645262/article/details/125717578
Author: tianmingemmm
Title: 递推最小二乘遗忘因子法(Recursive Forgetting Factor, RFF)