推荐系统

Forward-Backward Splitting (FOBOS) 算法简介

Leave a comment

 

FOBOS 算法简介

（1）FOBOS（Forward Backward Splitting）算法原理

前向后向切分（FOBOS，Forward Backward Splitting）是 John Duchi 和 Yoran Singer 提出的。在该算法中，权重的更新分成两个步骤：

W^{(t+0.5)}=W^{(t)}-\eta^{(t)}G^{(t)}

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}

第一个步骤实际上是一个标准的梯度下降（SGD），第二个步骤是对第一个步骤的结果进行局部调整。写成一个公式那就是：

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}

假设 F(W)=\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)，如果 W^{(t+1)} 存在一个最优解，那么可以推断 0 向量一定属于 F(W) 的次梯度集合：

0 \in \partial F(W)=W-W^{(t)}+\eta^{(t)}G^{(t)}+\eta^{(t+0.5)}\partial\Psi(W).

因为 W^{(t+1)}=argmin_{W}F(W), 那么可以得到权重更新的另外一种形式：

W^{(t+1)}=W^{(t)}-\eta^{(t)}G^{(t)}-\eta^{(t+0.5)}\partial\Psi(W^{(t+1)})

从上面的公式可以看出，更新后的 W^{(t+1)} 不仅和 W^{(t)} 有关，还和自己 \Psi(W^{(t+1)}) 有关。这也许就是”前向后向切分”这个名称的由来。

（2）FOBOS（Forward Backward Splitting）的 L1 正则化

假设 \Psi(W) 是 L1 范数，中间向量是 W^{(t+0.5)}=(v_{1},...,v_{N})\in\mathbb{R}^{N}, 并且参数 \tilde{\lambda}=\eta^{(t+0.5)}\lambda，那么公式就可以展开得到

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}

=argmin_{W}\sum_{i=1}^{N}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|).

所以，可以对特征权重 W 的每一个维度进行单独求解：

w^{(t+1)}_{i}=argmin_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|) for all $latex 1\leq i \leq N$.

Claim. 如果 w_{i}^{*} 是 \min_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|) 的最优解，那么 w_{i}^{*}v_{i}\geq 0.

证明：反证法，如果 w_{i}^{*}v_{i}<0，那么 \frac{1}{2}v_{i}^{2}<\frac{1}{2}(w_{i}^{*}-v_{i})^{2}+\tilde{\lambda}|w_{i}^{*}|， 这与条件矛盾。

通过数学计算可以证明：在 L1 正则化下，FOBOS 的特征权重的各个维度的更新公式是：

w_{i}^{(t+1)}=sgn(v_{i})\max(0,|v_{i}|-\tilde{\lambda})

= sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})\max\{0,|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|-\eta^{(t+0.5)}\lambda\} for all 1\leq i \leq N,

其中 g_{i}^{(t)} 是梯度 G^{(t)} 在第 i 个维度的分量。

从公式上看，

如果 |w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\leq\eta^{(t+0.5)}\lambda， 则有 w_{i}^{(t+1)}=0. 意思就是如果这次训练产生梯度的变化不足以令权重值发生足够大的变化时，就认为在这次训练中该维度不够重要，应该强制其权重是0.

如果 |w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\geq\eta^{(t+0.5)}\lambda，那么则有

w_{i}^{(t+1)}=(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})-\eta^{(t+0.5)}\lambda \cdot sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})

L1-FOBOS 的算法：

（1）输入 \lambda，初始化 W\in\mathbb{R}^{N}
（2）for t=1,2,3..., 计算 G=\nabla_{W}\ell(W,X^{(t)},Y^{(t)})
     按照公式更新 W，w_{i} = sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})\max\{0,|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|-\eta^{(t+0.5)}\lambda\} 
     for all 1\leq i \leq N
（3）Return W

（3）L1-FOBOS 与 Truncated Gradient 的关系

令 \theta=+\infty, k=1, \lambda_{TG}^{(t)}=\eta^{(t+0.5)}\lambda，可以得到 L1-FOBOS 与 Truncated Gradient 完全一致，换句话说 L1-FOBOS 是 Truncated Gradient 在一些特定条件下的形式。

 

Leave a comment