推荐系统算法常常用到逻辑回归算法,而传统的批量学习算法如 SGD 无法应对大规模、高维的数据集和实时数据流。为了解决这个问题,在线最优化算法如 TG [1]、FOBOS [2]、RDA [3]、FTRL [4,5,6] 应运而生,下面将介绍、对比这些算法。
TODO
L1 正则化在 online 不能产生较好的稀疏性,而稀疏性对于高维特征向量以及大数据集又特别的重要。为解决这个问题,John Langford 等人在 2009 年提出 Truncated Gradient [1]。
对于传统的在线学习方法 SGD,有更新规则
wi+1=wi−ηg(wi,zj)w_{i+1}=w_i - \eta g(w_i, z_j) wi+1=wi−ηg(wi,zj)
其中 zj=(xj,yj)z_j = (x_j, y_j)zj=(xj,yj) , g(a,b)g(a,b)g(a,b) 是 L(a,b)L(a,b)L(a,b) 对于 aaa 的次梯度。
然而,SGD 方法无法满足稀疏性
简单截断法。为了稀疏性,基于 GD,在每 K 次迭代,应用下面的规则,把小的 www 置 0。
wi+1=T0(wi−ηgt,θ)w_{i+1} = T_0\big(w_i - \eta g_t, \theta\big) wi+1=T0(wi−ηgt,θ)
其中 T0T_0T0 是分段函数
T0(vj,θ)={0if ∣vj∣≤θvjotherwiseT_0(v_j, \theta) = \begin{cases} 0 & \text{if } |v_j| \le \theta \\ v_j & \text{otherwise} \end{cases} T0(vj,θ)={0vjif ∣vj∣≤θotherwise
改进了简单截断法中,每 K 步把 wiw_iwi 置 0 太激进的问题,改进了有更新规则
wi+1=T1(wi−ηgt,ηλ,θ)w_{i+1} = T_1 \big(w_i - \eta g_t, \eta \lambda, \theta \big) wi+1=T1(wi−ηgt,ηλ,θ)
其中 T_1 定义
T1(vj,α,θ)={max(0,vj−α)if vj∈[0,θ]min(0,vj+α)if vj∈[−θ,0]vjotherwiseT_1(v_j, \alpha, \theta) = \begin{cases} \max(0, v_j - \alpha) &\text{if } v_j \in [0, \theta] \\ \min(0, v_j + \alpha) &\text{if } v_j \in [-\theta, 0] \\ v_j &\text{otherwise} \end{cases} T1(vj,α,θ)=⎩⎪⎨⎪⎧max(0,vj−α)min(0,vj+α)vjif vj∈[0,θ]if vj∈[−θ,0]otherwise
简单截断法的 T0T_0T0 与 TG 的 T1T_1T1 的对比
wt+1=wt−ηtgtfw_{t+1}=w_t - \eta_t g_t^f wt+1=wt−ηtgtf
w_{t+1}= \Pi_\Omega (w_t - \eta_t g_t^f )=\underset {w \in \Omega} {\arg \min} \bigg\{ \bigg| \bigg| w - (w_t - \eta_t g_t^f)\bigg|\bigg|^2_2 \bigg\}
其中 ΠΩ(w)\Pi_\Omega(w)ΠΩ(w) 是 www 到 Ω\OmegaΩ 的欧几里得投影距离。
前向后向切分,Forward-Bakcward Splitting,又称 FOLOS (Forward Looking Subgradients),由 John Duchi 等人在 2009 提出 [2],解决凸优化问题如下
f(w)+r(w)f(w)+r(w) f(w)+r(w)
权重更新分为两部分
\begin{align} w_{t+\frac{1}{2}} &= w_t - \eta_t g_t\\ w _{t+1} &= \underset{w}{\arg \min} \bigg\{\frac{1}{2} ||w-w_{t+\frac{1}{2}}||^2 + \eta_{t+\frac{1}{2}}r(w) \bigg\} \end{align}
第一项是标准梯度下降;第二项是微调,处理正则化,产生稀疏性。rrr 是正则函数。
当 wt+1w_{t+1}wt+1 有最优解时,有
\textbf{0} \in \partial \bigg\{\frac{1}{2} \big|\big|w-w_{t+\frac{1}{2}} \big|\big|^2 + \eta_{t+\frac{1}{2}} r(w) \bigg\}
由 wt+12=wt−ηtgtfw_{t+\frac{1}{2}} = w_t - \eta_t g_t^fwt+21=wt−ηtgtf ,上式可化简为
\textbf 0 \in w_{t+1} - w_t + \eta_t g_t^f + \eta_{t+\frac{1}{2}} \partial r(w_{t+1}) \\ \textbf 0= w_{t+1} - w_t + \eta_t g_t^f + \eta_{t+\frac{1}{2}} g_{t+1}^r
最终,得到更新公式
wt+1=wt−ηgtf−ηt+12gt+1rw_{t+1} = w_t - \eta g_t^f - \eta_{t+\frac{1}{2}} g_{t+1}^r wt+1=wt−ηgtf−ηt+21gt+1r
其中 gtf∈∂f(wt)g_t^f \in \partial f(w_t)gtf∈∂f(wt) , gt+1r∈∂r(wt+1)g_{t+1}^r \in \partial r(w_{t+1})gt+1r∈∂r(wt+1)
可以看出,更新公式不仅和当前的状态 wtw_twt 相关,和迭代后的 r(wt+1)r(w_{t+1})r(wt+1) 相关,因此改算法称为前向后向切分。
当 rrr 是 ℓ1\ell_1ℓ1 ,在 [2] 的 5.1 章节描述了对应的 derived algorithm。
RDA 是 simple Dual Averaging Scheme 的一个扩展,由 Lin Xiao 在 2009 发表 [3]。
更新策略为
w_{t+1}=\underset {w}{\arg \min} \bigg\{ \frac{1}{t} \sum_{r=1}^t + r(w) + \frac{\beta_t}{t}h(w) \bigg\}
其中, <Gr,w><G_r,w><Gr,w> 表示梯度 GrG_rGr 对 www 的积分平均值;rrr 是正则项; hhh 是辅助的严格凸函数; {βt∣t≥1}\{\beta_t|t\ge1\}{βt∣t≥1} 是一个非负且非自减序列。
RDA 更新策略,最小化:第一项,之前所有梯度的平均值(dual average);第二项,正则项;第三项,额外正则项。
FTRL 是 McMahan 在 2010 提出 [4],在 [5] 与 FOBOS RDA 对比,在 [6] 介绍了 Google FTRL 工程实践。FTRL 综合考虑了 FOBOS 和 RDA,更新公式为
w_{t+1} = \underset{w}\arg\min \bigg\{ G_{1:t} W + \lambda_1 ||w||_1 + \lambda_x||w||_2^2 + \frac{1}{2} \sum_{s=1}^t \sigma_s ||w-w_s||_2^2\bigg\}
凸函数定义
f(tX_1 + (1-t)X_2) \le t f(X_1) + (1-t)f(X_2) \\ \forall X_1, X_2 \in \mathbb C, 0 \le t \le 1
严格凸函数
f(tX_1 + (1-t)X_2) \lt t f(X_1) + (1-t)f(X_2) \\ \forall X_1, X_2 \in \mathbb C, 0 \lt t \lt 1
一个函数是凸函数的充要条件是它存在最优解。
[1] Langford, John, Lihong Li, and Tong Zhang. “Sparse online learning via truncated gradient.” Journal of Machine Learning Research 10.Mar (2009): 777-801. PDF
[2] Duchi, John, and Yoram Singer. “Efficient online and batch learning using forward backward splitting.” Journal of Machine Learning Research 10.Dec (2009): 2899-2934. PDF
[3] Xiao, Lin. “Dual averaging methods for regularized stochastic learning and online optimization.” Journal of Machine Learning Research 11.Oct (2010): 2543-2596. PDF
[4] McMahan, H. Brendan, and Matthew Streeter. “Adaptive bound optimization for online convex optimization.” arXiv preprint arXiv:1002.4908 (2010). PDF
[5] McMahan, Brendan. “Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization.” Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. 2011. PDF
[5] McMahan, H. Brendan, et al. “Ad click prediction: a view from the trenches.” Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013. PDF
[6] 在线最优化求解(Online Optimization) 冯扬 PDF
[7] 简谈L0,L1和L2 modkzs http://modkzs.github.io/2016/02/22/简谈L0-L1和L2/
[8] TRUNCATED GRADIENT (TG) 算法简介 ZHANG RONG https://zr9558.com/2016/01/12/truncated-gradient/