Monthly Archives: May 2016

推荐系统

Follow the Regularized Leader (FTRL) 算法

2 Comments

（一）FTRL 的算法原理：

FTRL 算法综合考虑了 FOBOS 和 RDA 对于梯度和正则项的优势和不足，其特征权重的更新公式是：

W^{(t+1)}=argmin_{W}\{G^{(1:t)}\cdot W+\lambda_{1}||W||_{1}+\frac{\lambda_{2}}{2}||W||_{2}^{2}+\frac{1}{2}\sum_{s=1}^{t}\sigma^{(s)}||W-W^{(s)}||_{2}^{2}\}

上面的公式出现了 L2 范数，不过这一项的引入不会影响 FTRL 的稀疏性，只是使得求解结果更加“平滑”。通过数学计算并且放弃常数项可以得到上面的优化问题相当于求使得下面式子的最小的参数 W：

(G^{(1:t)}-\sum_{s=1}^{t}\sigma^{(s)}W^{(s)})\cdot W + \lambda_{1}||W||_{1}+\frac{1}{2}(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})||W||_{2}^{2}

如果假设 Z^{(t)}=G^{(1:t)}-\sum_{s=1}^{t}\sigma^{(s)}W^{(s)}=Z^{(t-1)}+G^{(t)}-\sigma^{(t)}W^{(t)}, 上式等价于

W^{(t+1)}=argmin_{W}\{Z^{(t)}\cdot W + \lambda_{1}||W||_{1}+\frac{1}{2}(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})||W||_{2}^{2}\}

写成分量的形式就是：

argmin_{w_{i}}\{z_{i}^{(t)}w_{i}+\lambda_{1}|w_{i}|+\frac{1}{2}(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})w_{i}^{2}\}

通过计算可以直接得到：

w_{i}^{(t+1)}=0, \text{ if } |z_{i}^{(t)}|<\lambda_{1}

w_{i}^{(t+1)}=-(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})^{-1}\cdot(z_{i}^{(t)}-\lambda_{1}\cdot sgn(z_{i}^{(t)})) \text{ otherwise }

由此可以证明：引入 L2 正则化并没有对 FTRL 的稀疏性产生影响。

（二）学习率

在 SGD 的算法里面使用的是一个全局的学习率 \eta^{(t)}=O(t^{-0.5})，意味着学习率是一个正数并且逐渐递减，对每一个维度都是一样的。而在 FTRL 算法里面，每个维度的学习率是不一样的。如果特征 A 比特征 B变化快，那么在维度 A 上面的学习率应该比维度 B 上面的学习率下降得更快。在 FTRL 中，维度 i 的学习率是这样定义的：

\eta_{i}^{(t)}=\alpha/(\beta+\sqrt{\sum_{s=1}^{t}(g_{i}^{(s)})^{2}})

按照之前的定义 \sigma^{(1:t)}=1/\eta^{(t)}, 所以

\sum_{s=1}^{t}\sigma^{(s)}=\eta_{i}^{(t)}=\alpha/(\beta+\sqrt{\sum_{s=1}^{t}(g_{i}^{(s)})^{2}})

（三）FTRL 算法

FTRL Algorithm

（1）输入 \alpha, \beta, \lambda_{1},\lambda_{2}，初始化 W\in\mathbb{R}^{N}, Z=0\in\mathbb{R}^{N}, Q=0\in\mathbb{R}^{N}

（2）for t=1,2,3,.....
        G=\nabla_{W}\ell(W,X^{(t)},Y^{(t)})
        for i=1,2,...,N
         \sigma_{i}=\alpha^{-1}(\sqrt{q_{i}+g_{i}^{2}}-\sqrt{q_{i}})
         q_{i}=q_{i}+g_{i}^{2} // equals to (\eta^{(t)})^{-1}-(\eta^{(t-1)})^{-1}
         z_{i}=z_{i}+g_{i}-\sigma_{i}w_{i}
         \text{if } |z_{i}^{(t)}|<\lambda_{1}, w_{i}=0
         \text{otherwise, }
         w_{i}^{(t+1)}=-(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})^{-1}\cdot(z_{i}^{(t)}-\lambda_{1}\cdot sgn(z_{i}^{(t)}))
        end
     end

（四）Logistic Regression 的 FTRL 形式

在 Logistic Regression 中，假设 \sigma(a)=1/(1+\exp(-a)) 是 sigmoid 函数，y_{t} \in \{0,1\}，需要预估 p_{t}=\sigma(w_{t}\cdot w_{t})，那么 LogLoss 函数是

\ell_{t}(w_{t})=-y_{t}log(p_{t})-(1-y_{t})log(1-p_{t})，

直接计算可得 \nabla\ell(w)=(\sigma(w\cdot x_{t})-y_{t})x_{t}=(p_{t}-y_{t})x_{t}，所以 Logistic Regression 的 FTRL 算法就是：

FTRL Algorithm (Logistic Regression)

（1）输入 \alpha, \beta, \lambda_{1},\lambda_{2}，初始化 W\in\mathbb{R}^{N}, Z=0\in\mathbb{R}^{N}, Q=0\in\mathbb{R}^{N}

（2）for t=1,2,3,.....
        for i=1,2,...,N
         g_{i}=(p_{t}-y_{t})x_{i} // gradient of loss function
         \sigma_{i}=\alpha^{-1}(\sqrt{q_{i}+g_{i}^{2}}-\sqrt{q_{i}})
         q_{i}=q_{i}+g_{i}^{2} // equals to (\eta^{(t)})^{-1}-(\eta^{(t-1)})^{-1}
         z_{i}=z_{i}+g_{i}-\sigma_{i}w_{i}
         \text{if } |z_{i}^{(t)}|<\lambda_{1}, w_{i}=0
         \text{otherwise, }
         w_{i}^{(t+1)}=-(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})^{-1}\cdot(z_{i}^{(t)}-\lambda_{1}\cdot sgn(z_{i}^{(t)}))
        end
     end

 

Advertisement