在线最优化求解(Online Optimization)之三：FOBOS

FOBOS (Forward-Backward Splitting)是由John Duchi和Yoram Singer提出的^[11]。从全称上来看，该方法应该叫FOBAS，但是由于一开始作者管这种方法叫FOLOS（Forward Looking Subgradients），为了减少读者的困扰，作者干脆只修改一个字母，叫FOBOS。

1. 算法原理

在FOBOS中，将权重的更新分为两个步骤：

$W^{(t+frac{1}{2})}=W^{(t)}-eta ^{(t)}G^{(t)}$ $W^{(t+1)}=argmin_{W}left { frac{1}{2} left | W-W^{(t+frac{1}{2})} ight | ight ^2+eta ^{(t+frac{1}{2})}Psi (W)}$ 公式 (1)

前一个步骤实际上是一个标准的梯度下降步骤，后一个步骤可以理解为对梯度下降的结果进行微调。

观察第二个步骤，发现对 $W$ 的微调也分为两部分：(1) 前一部分保证微调发生在梯度下降结果的附近；(2)后一部分则用于处理正则化，产生稀疏性。

如果将公式(1)中的两个步骤合二为一，即将 $W^{(t+frac{1}{2})}$ 代入 $W^{(t+1)}$ 中，有：

$W^{(t+1)}=argmin_{W}left { frac{1}{2} left | W-W^{(t)}+eta ^{(t)}G{(t)} ight | ight ^2+eta ^{(t+frac{1}{2})}Psi (W)}$

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

$0 inpartial F(W)=W-W^{(t)}+eta ^{(t)}G^{(t)}+eta ^{(t+frac{1}{2})}partial Psi (W)$

由于 $W^{(t+1)}=argmin_{W}F(W)$ ,那么有：

$0=left { W-W^{(t)}-eta ^{(t)}G^{(t)}+eta ^{(t+frac{1}{2})}partial Psi (W) ight }|_{W=W^{(t+1)}})$

上式实际上给出了FOBOS中权重更新的另一种形式：

$W^{(t+1)}=W^{(t)}-eta ^{(t)}G^{(t)}-eta^{(t+frac{1}{2})}partial Psi (W^{(t+1)})$

我们这里可以看到 $W^{(t+1)}$ 不仅仅与迭代前的状态 $W^{(t)}$ 有关，而且与迭代后的 $Psi(W^{(t+1)})$ 有关。可能这就是FOBOS名称的由来。

2. L1-FOBOS

关于FOBOS的收敛性和Regret就不在此讨论了，详情可参见论文[1]。这里我们来看看FOBOS如何在L1正则化下取得比较好的稀疏性。
在L1正则化下，有 $Psi (W)=lambda left | W ight |_1$ 为了简化描述，用向量 $V=[v_1,v_2...v_N]in mathbb{R}^N$ 来表示 $W^{(t+frac{1}{2})}$ 用标量 $ilde{lambda }in mathbb{R}$ 来表示 $eta ^{^t+frac{1}{2}}lambda$ 并将公式(1)等号右边按维度展开：

$W^{(t+1)}=argmin_{W}sum_{i=1}^{N}(frac{1}{2}(w_i-v_i)^2+ ilde{lambda }left | w_i ight |)$ 公式(2)

我们可以看到，在求和公式中的每一项都是大于等于 $0$ 的，所以公式(2)可以拆解成对特征权重每一维度单独求解：

$w_i^{(t+1)}=argmin_{W}(frac{1}{2}(w_i-v_i)^2+ ilde{lambda }left | w_i ight |)$

首先，假设 $w^{*}$ 是 $min_{W}(frac{1}{2}(w_i-v_i)^2+ ilde{lambda }left | w_i ight |)$ 的最优解，则有 $w_i^{*}v_igeq 0$ ，这是因为：

--------------------------------------------------------------------
反证法：
假设 $w_i^{*}v_i<0$ 成立，那么有

$frac{1}{2}v_i^2<frac{1}{2}v_i^2-w_i^*v_i+frac{1}{2}(w_i^*)^2<frac{1}{2}(w_i^*-v_i)^2+ ilde{lambda }left | w_i^* ight |$

这与 $w_i^{*}$ 是 $min_{W}(frac{1}{2}(w_i-v_i)^2+ ilde{lambda }left | w_i ight |)$ 的最优解相矛盾，故假设不成立， $w_i^{*}v_igeq 0$ 成立。
---------------------------------------------------------------------

既然有 $w_i^{*}v_igeq 0$ ，那么我们可以分两种情况来进行讨论：
---------------------------------------------------------------------
(1) 当 $v_igeq 0$ 时：
由于 $w_i^{*}v_igeq 0$ ，所以 $w_i^{*}geq 0$ ，相当于对 $min_{W}(frac{1}{2}(w_i-v_i)^2+ ilde{lambda }left | w_i ight |)$ 引入了不等式条件 $-w_ileq 0$ ;
为了求解这个含不等式约束的最优化问题，引入拉格朗日乘子 $etageq 0$ ，由KKT条件，有： $frac{partial }{partial w_i}(frac{1}{2}(w_i-v_i)^2+ ilde{lambda }w_i-eta w_i)|_{w_i=w_i^*}=0$ 以及 $eta w_i^*=0$
根据上面的求导等式可得： $w_i^*=v_i- ilde{lambda }+eta$

再次分为两种情况：

(a) $w_i^*> 0$ ：

由于 $eta w_i^*=0$ ，所以 $eta=0$ ；这时有： $w_i^*=v_i- ilde{lambda }$ ；又由于 $w_i^*gt;0$ ，所以 $v_i- ilde{lambda }> 0$ 。

(b) $w_i^*=0$ ：
这时有 $v_i- ilde{lambda }+eta = 0$ ；又由于 $eta geq 0$ ，所以 $v_i- ilde{lambda }leq 0$
综合(a)(b)的结论，当 $v_igeq 0$ 时， $w_i^*=max(0,v_i- ilde{lambda })$
(2) 当 $v_i< 0$ 时：
采用相同的分析方法可得，在 $v_i< 0$ 时有： $w_i^*=-max(0,-v_i- ilde{lambda })$
---------------------------------------------------------------------

综合上面的分析，可以得到在FOBOS在L1正则化条件下，特征权重的各个维度更新的方式为：

$w_i^{(t+1)}=sgn(v_i)max(0,left | v_i ight |- ilde{lambda })$ 公式(3) $=sgn(w_i^{(t)}-eta ^{(t)}g_i^{(t)})max(0,left | w_i^{(t)}-eta ^{(t)}g_i^{(t)} ight |-eta ^{(t+frac{1}{2})}lambda$

其中， $g_i^{(t)}$ 为梯度 $G^{(t)}$ 在维度i上的取值。

根据公式(3)，我们很容易就可以设计出L1-FOBOS的算法逻辑：

3. L1-FOBOS与TG的关系

公式3)可以看出，L1-FOBOS在每次更新 $W$ 的时候，对 $W$ 的每个维度都会进行判定，当满足 $http://latex.codecogs.com/gif.latex?left | w_i^{(t)}-eta ^{(t)}g_i^{(t)} ight |leq eta ^{(t+frac{1}{2})}lambda$ 时对该维度进行“截断”，这个判定条件的含义是当一条样本产生的梯度不足以令对应维度上的权重值发生足够大的变化时，认为在本次更新过程中该维度不够重要，应当令其权重为0。
对于L1-FOBOS特征权重的各个维度更新公式(3)，也可以写作如下形式：

$w_i^{(t+1)}=left{egin{matrix} 0 & if\ left | w_i^{(t)}-eta ^{(t)}g_i^{(t)} ight |leq eta ^{(t+frac{1}{2})}lambda \ (w_i^{(t)}-eta ^{(t)}g_i^{(t)})-eta ^{(t+frac{1}{2})}lambda sgn(w_i^{(t)}-eta ^{(t)}g_i^{(t)}) & otherwise end{matrix} ight.$

比较上式与TG的特征权重维度更新公式，可以发现如果令 $heta =infty,\ k=1,\ lambda _{TG}^{(t)}=eta ^{(t+frac{1}{2})}lambda$ ，L1-FOBOS与TG完全一致。我们可以认为L1-FOBOS是TG在特定条件下的特殊形式。

参考文献

[1] John Duchi & Yoram Singer. Efficient Online and Batch Learning using Forward Backward Splitting. Journal of Machine Learning Research, 2009