在线优化算法FTRL的原理与实现
在线学习想要解决的问题
在线学习 ( Online Learning ) 代表了⼀系列机器学习算法，特点是每来⼀个样本就能训练，能够根据线上反馈数据，实时快速地进⾏模型调整，使得模型及时反映线上的变化，提⾼线上预测的准确率。相⽐之下，传统的批处理⽅式需要⼀次性收集所有数据，新数据到来时重新训练的代价也很⼤，因⽽更新周期较长，可扩展性不⾼。
⼀般对于在线学习来说，我们致⼒于解决两个问题：降低 regret 和提⾼ sparsity。其中 regret 的定义为：
Regret=
T
∑
t=1ℓt(w t)−
min
w
T
∑
t=1ℓt(w)
其中t表⽰总共T轮中的第t轮迭代，ℓt表⽰损失函数，w表⽰要学习的参数。第⼆项min w∑T t=1ℓt(w) 表⽰得到了所有样本后损失函数的最优解，因为在线学习⼀次只能根据少数⼏个样本更新参数，随机性较⼤，所以需要⼀种稳健的优化⽅式，⽽ regret 字⾯意思是 “后悔度”，意即更新完不后悔。
在理论上可以证明，如果⼀个在线学习算法可以保证其 regret 是t的次线性函数，则：
lim t→∞Regret(t)
t=0
那么随着训练样本的增多，在线学习出来的模型⽆限接近于最优模型。⽽毫不意外的，FTRL 正是满⾜这⼀特性。
正则化解决什么问题
另⼀⽅⾯，现实中对于 sparsity，也就是模型的稀疏性也很看中。上亿的特征并不鲜见，模型越复杂，需要的存储、时间资源也随之升⾼，⽽稀疏的模型会⼤⼤减少预测时的内存和复杂度。另外稀疏的模型相对可解释性也较好，这也正是通常所说的 L1 正则化的优点。
后⽂主要考察 FTRL 是如何实现降低 regret 和提⾼ sparsity 这两个⽬标的。
FTRL 原理
⽹上很多资料都是从 FTRL 的⼏个前辈，FOBOS、RDA 等⼀步步讲起，本篇就不绕那么⼤的圈⼦了，直接从最基本的 OGD 开路到 FTRL 。OGD ( online gradient descent ) 是传统梯度下降的 online 版本，参数更新公式为：
w t+1=w t−ηt g t
t表⽰第t轮迭代，注意上式中的学习率ηt每轮都会变，⼀般设为ηt=1√t
OGD 在准确率上表现不错，即 regret 低，但在上⽂的另⼀个考量因素 sparsity 上则表现不佳，即使加上了 L1 正则也很难使⼤量的参数变零。⼀个原因是浮点运算很难让最后的参数出现绝对零值；另⼀个原因是不同于批处理模式，online 场景下每次w的更新并不是沿着全局梯度进⾏下降，⽽是沿着某个样本的产⽣的梯度⽅向进⾏下降，整个寻优过程变得像是⼀个“随机” 查的过程，这样 online 最优化求解
即使采⽤ L1 正则化的⽅式，也很难产⽣稀疏解。正因为 OGD 存在这样的问题，FTRL 才致⼒于在准确率不降低的前提下提⾼稀疏性。
相信⼤部分⼈对于 (1.1) 式都不陌⽣，然⽽其实际等价于下式：
w t+1=argmin
w g t⋅w+
1
2ηt
||w−w t||22
对 (1.2) 式直接求导即可，g t+1
ηt(w−w
t)=0⟹w=w t−ηt g t。有了 (1.2) 式的基础后，后⾯ FTRL 的那些奇奇怪怪的变换就能明了
了，⽬的⽆⾮也是降低 regret 和提⾼ sparsity 。
⾸先，为了降低 regret，FTRL ⽤g1:t代替g t，g1:t为前 1 到 t 轮损失函数的累计梯度，即g1:t=∑t s=1g s=∑t s=1∇ℓs(w s) 。由于在线学习随机性⼤的特点，累计梯度可避免由于某些维度样本局部抖动太⼤导致错误判断。这是从 FTL ( Follow the Leader ) 那借鉴⽽来的，⽽FTRL 的全称为 Follow the Regularized Leader ，从名字上看其实就是在 FTL 的基础上加上了正则化项，即 (1.2) 式中的
||w−w t||22项。这意味着每次更新时我们不希望新的w离之前的w t太远 (这也是有时其被称为FTRL-proximal的原因)，这同样是为了降低 regret，在线学习噪⾳⼤，若⼀次更新错得太远后⾯难以收回来，没法轻易“后悔”。
()
其次，为提⾼ sparsity ，最直接的⽅法就是⽆脑加 L1 正则。但这⾥的问题是上⽂中 OGD 加了 L1 正则不能产⽣很好的稀疏性，那么 FTRL 为什么就能呢？这在后⽂的具体推导中会逐⼀显现，耐⼼看下去就是。另外 FTRL 2013 年的中也加上了 L2 正则，所以综合上述⼏
点，FTRL 的更新公式变为：
w t+1=argmin
w g1:t⋅w+
1
2
t
∑
s=1σs||w−w s||22+λ1||w||1+
1
2λ
2||w||
2
2
其中σs=1
ηs−
1
ηs−1，则σ
1:t=∑
t
s=1σs=
1
ηs，主要是为了后⾯推导和实现⽅便⽽这么设置，后⽂再述。
下⾯可以推导 FTRL 的算法流程，将 (1.3) 式中的 ||w−w s||22展开：
w t+1=argmin
w g1:t−
t
∑
s=1σs w s⋅w+λ1||w||1+
1
2λ
2+
t
∑
s=1σs⋅||w||2
2
+
1
2
t
∑
s=1σs||w s||22
由于1
2
t
∑
s=1σs||w s||22相对于要优化的w是⼀个常数可以消去，并令z t=g1:t−
t
∑
s=1σs w s，于是 (1.4) 式变为：
w t+1=
argmin
w z t⋅w+λ1||w||1+
1
2λ
2+
t
∑
s=1σs⋅||w||2
2
将特征的各个维度拆开成独⽴的标量最⼩化问题，i为第i个特征：
w t+1,i=argmin
w i∈R z
t,i w+λ1|w i|+
1
2λ
2+
t
∑
s=1σs⋅w2i
(1.6) 式是⼀个⽆约束的⾮平滑参数优化问题，其中第⼆项λ1|w i| 在w i=0 处不可导，因⽽常⽤的⽅法是使⽤次导数 (详见附录1)，这⾥直接上结论：定义ϕ∈∂|w∗i| 为 |w i| 在w∗i处的次导数，于是有：
∂|w∗i|=
{1}if w∗i>0−1<ϕ<1if w∗i=0 {−1}if w∗i<0
有了 |w i| 的次导数定义后，对 (1.6) 式求导并令其为零：
z t,i+λ1ϕ+λ2+
t
∑
s=1σs⋅w i=0
上式中λ1>0,λ2+∑t s=1σs>0 ，下⾯对z t,i的取值分类讨论：
(1) |z t,i|<λ1，那么w i=0 。因为若w i>0 ，根据 (1.7) 式ϕ=1 ，则 (1.8) 式左侧>0 ，该式不成⽴；同样若w1<0，则 (1.8) 式左侧<0，不成⽴。
(2) z t,i>λ1，则ϕ=−1⟹w i=−
1
λ2+∑t s=1σs
(z t,i−λ1)<0 。因为若w i>0，ϕ=1，(1.8) 式左侧>0，不成⽴；若w i=0，由 (1.8) 式
ϕ=−z t,i
λ1<−1 ，与 (1.7) 式⽭盾。
()
{()()}
{()}
{()}
{
()
()
(3) z t ,i <−λ1，则 ϕ=1⟹w i =−
1
λ2+∑t s =1σs
(z t ,i +λ1)>0 。因为若 w i <0，ϕ=−1，(1.8) 式左侧 <0，不成⽴；若 w i =0，由 (1.8) 式
ϕ=−z t ,i λ1
>1 ，与 (1.7) 式⽭盾。
综合这⼏类情况，由 (1.8) 式得到 w t ,i  的更新公式：
w t +1,i =
if |z t ,i |<λ1
−
1λ2+∑t s =1σs
z t ,i −sgn(z t ,i )⋅λ1otherwise
可以看到当 z t ,i =g 1:t ,i −∑t s =1σs w s ,i <λ1 时，参数置为零，这就是 FTRL 稀疏性的由来。另外加⼊ L2 正则并没有影响模型的稀疏性，从
(1.9) 式看只是使得分母变⼤，进⽽ w i  更趋于零了，这在直觉上是符合正则化本⾝的定义的。
观察 (1.9) 式还遗留⼀个问题，σ 的值是什么呢？这牵涉到 FTRL 的学习率设置。当然严格意义上的学习率是 ηt  ，⽽ σt =1η
t −1
η
t −1 ，论⽂中这样定义可能是为了推导和实现的⽅便。前⽂ (1.1) 式中 OGD 使⽤的是⼀个全局学习率 \eta_t = \frac{1}{\sqrt{t}} ，会随着迭代轮数的增加⽽递减，但该⽅法的问题是所有特征维度都使⽤了⼀样的学习率。
FTRL 采⽤的是 Per-Coordinate Learning Rate ，即每个特征采⽤不同的学习率，这种⽅法考虑了训练样本本⾝在不同特征上分布的不均匀性。如果⼀个特征变化快，则对应的学习率也会下降得快，反之亦然。其实近年来随着深度学习的流⾏这种操作已经是很常见了，常⽤的AdaGrad 、Adam 等梯度下降的变种都蕴含着这类思想。FTRL 中第 t  轮第 i  个特征的学习率为：\eta_{t, i} = \frac{\alpha}{\beta + \sqrt{\sum_{s=1}^t g_{s, i}^2}} \tag{1.10}这样 (1.9) 式中的 \sum_{s=1}^t \sigma_s  为：
\begin{align*} \sum\limits_{s=1}^t \sigma_s &= (\frac{1}{\eta_t} - \frac{1}{\eta_{t-1}}) + (\frac{1}{\eta_{t-1}} - \frac{1}{\eta_{t-2}}) + \cdots +(\frac{1}{\eta_1} - \frac{1}{\eta_0}) \\ &=\;\; \frac{1}{\eta_t} \;\;=\;\; \frac{\beta + \sqrt{\sum_{s=1}^tg_{s,i}^2}}{\alpha} \tag{1.11} \end{align*}其中 \alpha, \beta  为超参数，论⽂中建议 \beta  设为 1，⽽ \alpha  则根据情况选择。g_{s,i} 为第 s  轮第 i  个特征的偏导数，于是 (1.9) 式变为：
w_{t+1,i} = \begin{cases} \qquad\qquad \large{0} & \quad\text{if}\;\; |z_{t,i}| < \lambda_1 \\[2ex] - \left(\lambda_2 + \frac{\beta +
\sqrt{\sum_{s=1}^t g_{s,i}^2}}{\alpha} \right)^{-1} \left(z_{t,i} - \text{sgn}(z_{t,i})\cdot\lambda_1 \right) & \quad \text{otherwise} \tag{1.12}\end{cases}
综合 (1.10) 式和 (1.12) 式可以看出，学习率 \eta_{t,i} 越⼤，则参数 w  更新幅度越⼤，这与学习率的直
觉定义相符。
FTRL 实现
完整代码见 ( ) ，实现了多线程版本 FTRL 训练 Logistic Regression 。
对于算法的实现来说，⾸先需要得到完整的算法流程。仔细审视 (1.12) 式，要在 t + 1 轮更新 w_{t+1, i} 需要哪些值？ 需要 \{ \;z_{t,i}, \,g_{t,i},\,\alpha, \,\beta, \,\lambda_1, \,\lambda_2 \; \} ，后四个为预先指定的超参数，对于 z_{t,i} ，注意其定义有可以累加的特性 :
\begin{aligned} z_{t,i} &= g_{1:t, i} - \sum\limits_{s=1}^t \sigma_{s, i} w_{s,i} \\ &= \sum\limits_{s=1}^t g_{s,i} - \sum\limits_{s=1}^t \sigma_{s, i}w_{s,i} \\ &= z_{t-1,i} + g_{t,i} - \sigma_{t,i}w_{t,i} \\[1ex] &= z_{t-1,i} + g_{t,i} - \left(\frac{1}{\eta_{t,i}} - \frac{1}{\eta_{t-1, i}} \right) w_{t,i} \\[1ex]&= z_{t-1,i} + g_{t,i} - \frac{\sqrt{\sum_{s=1}^t g_{s,i}^2} - \sqrt{\sum_{s=1}^{t-1} g_{s,i}^2}}{\alpha} w_{t,i} \end{aligned}
所以我们只需存储上⼀轮迭代得到的三个量 : z_{t-1,i}, \, w_{t,i}, \sqrt{\sum_{s=1}^t g_{s,i}^2} ，并在本轮迭代中计算 g_{t,i} ，就能不断更新参
{
()
()
数了。g_{t,i}为损失函数对第i个特征的偏导数，\text{Logistic Regression}的损失函数是\text{Log Loss}，这⾥直接给出结论，具体推导见附录 2：
g_{t,i} = y_t (S(y_t f(\bold{x}_t)) - 1) x_i = y_t \left(\frac{1}{1 + e^{- y_t f(\bold{x}_t)}} - 1 \right) x_i \tag{2.1}
其中S(\cdot)为 Sigmoid函数，x_i为第i个特征值，y \in \{-1, + 1\}为标签，f(\bold{x}_t) = \sum_{i=1}^I w_ix_i。下⾯就可以给出完整的算法流程了，其中为⽅便表⽰定义了n_i = \sum_{s=1}^t g_{s,i}^2：
输⼊：参数\alpha, \,\beta, \,\lambda_1, \,\lambda_2
初始化：\bold{z}_0 = \bold{0}, \; \bold{n}_0 = \bold{0}
\text{for t = 1 to T} :
\qquad收到⼀个样本\{\bold{x}_t, y_t\}，y_t \in \{-1, + 1\}。令I为所有不为零的特征集合，即I = \{i \,|\, x_i \neq 0\}
\qquad\text{for} \;\;i \in I更新w_{t,i} :
w_{t,i} = \begin{cases} \qquad\qquad \large{0} & \quad\text{if}\;\; |z_{i}| < \lambda_1 \\[2ex] - \left(\lambda_2 + \frac{\beta +
\sqrt{n_i}}{\alpha} \right)^{-1} \left(z_{i} - \text{sgn}(z_{i})\cdot\lambda_1 \right) & \quad \text{otherwise} \end{cases}
\qquad使⽤更新后的\bold{w}_t计算f(\bold{x}_t) = \bold{w}_t \cdot \bold{x}_t
\qquad\text{for all} \; i \in I :
\qquad\qquad g_i = y_t (S(y_t f(\bold{x}_t)) - 1) x_i
\qquad\qquad\sigma_i = \frac{\sqrt{n_i + g_i^2} - \sqrt{n_i}}{\alpha}
\qquad\qquad z_i \leftarrow z_i + g_i - \sigma_i w_{t,i}
\qquad\qquad n_i \leftarrow n_i + g_i^2
\qquad\text{end for}
\text{end for}
如上⽂所述，中使⽤了⼀个ftrl_model_unit类来存储三个量z_{i}, \, w_{i}, n_i :
class ftrl_model_unit
{
public:
double wi;
double w_ni;
double w_zi;
ftrl_model_unit()
{
wi = 0.0;
w_ni = 0.0;
w_zi = 0.0;
}
ftrl_model_unit(double mean, double stddev)
{
wi = utils::gaussian(mean, stddev);
w_ni = 0.0;
w_zi = 0.0;
}
}
更新参数的核⼼步骤为：
void ftrl_trainer::train(int y, const vector<pair<string, double> > &x)
{
ftrl_model_unit *thetaBias = pModel->getOrInitModelUnitBias();
vector<ftrl_model_unit *> theta(x.size(), nullptr);
int xLen = x.size();
for (int i = 0; i < xLen; ++i) {
const string &index = x[i].first;
theta[i] = pModel->getOrInitModelUnit(index);  // 获取相应的 ftrl_model_unit
}
for (int i = 0; i <= xLen; ++i) {
ftrl_model_unit &mu = i < xLen ? *(theta[i]) : *thetaBias;
if (fabs(mu.w_zi) <= w_l1)
mu.wi = 0.0;
else {
mu.wi = (-1) *
(1 / (w_l2 + (w_beta + sqrt(mu.w_ni)) / w_alpha)) *
(mu.w_zi - utils::sgn(mu.w_zi) * w_l1);  // 更新 wi
}
}
double bias = thetaBias->wi;
double p = pModel->forecast(x, bias, theta);  // 计算 f(x)
double mult = y * (1 / (1 + exp(-p * y)) - 1);
for (int i = 0; i <= xLen; ++i) {
ftrl_model_unit &mu = i < xLen ? *(theta[i]) : *thetaBias;
double xi = i < xLen ? x[i].second : 1.0;
double w_gi = mult * xi;      // 更新 gi
double w_si = 1 / w_alpha * (sqrt(mu.w_ni + w_gi * w_gi) - sqrt(mu.w_ni));
mu.w_zi += w_gi - w_si * mu.wi;      // 更新 zi
mu.w_ni += w_gi * w_gi;        // 更新 ni
}
}
Appendix 1: 次导数
(1.7)式中使⽤了f(x) = |x|的次导数，这⾥做⼀下具体推导。⾸先次导数的定义 —— 凸函数f: \text{I} \rightarrow \mathbb{R}在开区间\text{I}内的点x_0的次导数c满⾜：
f(x) - f(x_0) \geq c(x - x_0)
其物理含义是通过x_0下⽅的直线的斜率，如下图，f(x)在x_0处不可导，则经过x_0画⼀条红线，总是位于f(x)下⽅，其斜率就是次导数c。可以看出很多时候次导数并不唯⼀。
对于f(x) = |x|来说，x < 0时，次导数为单元素集合\{-1\}，x > 0时为\{1\}。⽽在x = 0处则不连续，根据次导数的定义，f(x) - f(0) \geqslant c\,(x - 0), \; f(x) \geqslant c\,x，则满⾜该式的c \in [-1, 1]，因⽽f(x) = |x|的次导数为 (如下图所⽰)：
\partial f(x) = \begin{cases} &\;\;\{1\} &\text{if}\;\; x > 0 \\[1ex] &[-1,1] & \text{if}\;\; x = 0 \\[1ex] &\;\{-1\} &\text{if}\;\; x < 0 \end{cases}
Appendix 2: \text{Log Loss}
FTRL 的算法流程中每⼀轮更新都要计算损失函数对每个特征分量的偏导数，中写的是使⽤梯度，但实际上是梯度的⼀个分量，即偏导数，

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。