FTRL算法的理论分析与工程化实现

FTRL算法本质上是针对梯度下降类算法的参数更新过程进行优化，在FTRL之前还有FOBOS和RDA算法。本文以逻辑回归算法（LR）为例，深入阐述一下FOBOS，RDA，FTRL算法。

关于FTRL算法的发展历程可以参考《各大公司广泛使用的在线学习算法FTRL详解》一文；本文关于逻辑回归算法推导的部分主要参考《LR+FTRL算法原理以及工程化实现》，原文讲的很好，但是一些细节表述有些许不正确，本文做了校正；本文关于FOBOS，RDA，FTRL算法部分的阐述是知乎作者张戎博文《FOLLOW THE REGULARIZED LEADER (FTRL) 算法总结》的精炼版。

1. 逻辑回归算法推导

逻辑回归模型是一种分类模型，由条件概率分布P(Y|X)表示，形式为参数化的logistic分布，如下所示。

$$P(Y=1|x)=\frac{exp(w\cdot x+b)}{1+exp(w\cdot x+b)}$$

$$P(Y=0|x)=\frac{1}{1+exp(w\cdot x+b)}$$

有时为了方便，将权重w和输入向量x进行扩充，即$w=(w^{(1)},w^{(2)},…,w^{(n)},b)^T, x=(x^{(1)},x^{(2)},…,x^{(n)},1)^T$。扩充后如下所示：

$$P(Y=1|x)=\frac{exp(w\cdot x)}{1+exp(w\cdot x)}$$

$$P(Y=0|x)=\frac{1}{1+exp(w\cdot x)}$$

在学习LR模型时通常使用极大似然法估计模型参数，从而得到LR模型。设

$$P(Y=1|x)=\pi(x)$$

$$P(Y=0|x)=1-\pi(x)$$

似然函数为

$$\prod_{i=1}^N [\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}$$

对数似然函数为：

$$\begin{aligned} L(w) &= -\sum_{i=1}^N [y_{i}log\pi(x_i)+(1-y_i)log(1-\pi(x_i))] \\ &= -\sum_{i=1}^N [y_{i}(w\cdot x_i)-log(1+exp(w\cdot x_i))] \\ \end{aligned}$$

对$L(w)$求极大值，得到$w$的估计值。这样，问题就变成了以对数似然函数为目标函数的最优化问题。可以看出，$L(w)$函数是一个高阶可导连续凸函数，可以使用梯度下降法、拟牛顿法求解。

在实际应用中，通常是以最小化损失函数为目标，这里为描述方便，取$L(x)=-L(x)$，转为求$L(x)$的极小值。

以梯度下降法为例：计算$L(w)$的梯度为：

$$\frac{\partial L(w)}{\partial w}=\sum_{i=1}^N[(\pi(x_i)-y_i)\cdot x_i]$$

第j个参数的梯度为：

$$\begin{aligned} g_j &= \frac{\partial L(w)}{\partial w} \\ &= \sum_{i=1}^N[(\pi(x_i)-y_i)\cdot x^j_i] \\ \end{aligned}$$

样本第j个参数的更新方式为：

$$
\begin{aligned}
w^{k+1}j &= w^k_j-\alpha\cdot g_i \\
&= w^k_j-\alpha\cdot \sum^N{i=1}(\pi(x_i)-y_i)\cdot x^j_i\\
\end{aligned}
$$

上述推导基于梯度下降法，当样本量很大的时候，通常使用随机梯度下降法。

FOBOS, RDA, FTRL算法都是针对梯度下降类算法的参数更新过程进行的优化。

2. FOBOS(Forward Backward Splitting)

FOBOS又叫前向后向切分算法，在该算法中，权重的更新主要分为两个步骤：

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

$$W^{(t+1)}=argmin_W \lbrace\frac{1}{2}||W-W^{(t+0.5)}||^2_2+\eta^{(t+0.5)}\Psi(W) \rbrace$$

第一个步骤是一个标准的梯度下降，第二个步骤是对第一个步骤的结果进行局部调整。将两个式子合并之后如下：

$$W^{(t+1)}=argmin_W \lbrace\frac{1}{2}||W-W^{t}+\eta^{t}G^{(t)}||^2_2+\eta^{(t+0.5)}\Psi(W) \rbrace$$

假设$F(w)=\frac{1}{2}||W-W^{t}+\eta^{t}G^{(t)}||^2_2+\eta^{(t+0.5)}\Psi(W)$，如果$W^{(t+1)}$存在一个最优解，则必有$F(W)$导数为0：

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

因为$W^{(t+1)}=argmin_WF(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)})$有关。$\Psi(W^{(t+1)})$是权重的惩罚项。

3. RDA(Regularized Dual Averaging Algorithm)

RDA又叫正则对偶平均算法，特征权重的更新策略是：

$$W^{(t+1)}=argmin_W\lbrace \frac{1}{t}\sum^t_{r=1}G^{(r)}\cdot W+\Psi(W) + \frac{\beta^{(t)}}{t}h(W) \rbrace$$

其中，$G^{(t)}\cdot W$指的是向量$G^{(t)}$和$W$的内积，$\Psi(W)$是正则项，$h(W)$是一个严格凸函数，${ \beta^{(t)}|t\geq 1 }$是一个非负递增序列。

解释：

1. $\frac{1}{t}\sum^t_{r=1}G^{(r)}\cdot W$包括了之前所有梯度的平均值；
2. 正则项$\Psi(W)$；
3. 额外项$\frac{\beta^{(t)}}{t}h(W)$。

4. FTRL(FOLLOW THE REGULARIZED LEADER)

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

$$
W^{(t+1)}=argmin_W \lbrace G^{(1:t)}\cdot W+ \lambda_1||W||1+\frac{\lambda_2}{2}||W||^2_2+\frac{1}{2}\sum^t{s=1}\sigma^{(s)}||W-W^{(s)}||^2_2 \rbrace
$$

其中，$G^{(1:t)}=\sum^t_{s=1}G^{(s)}$。

未完待续。

参考文献

1. 各大公司广泛使用的在线学习算法FTRL详解
2. FOLLOW THE REGULARIZED LEADER (FTRL) 算法
3. FTRL（Follow The Regularized Leader）
4. FOLLOW THE REGULARIZED LEADER (FTRL) 算法总结
5. LR+FTRL算法原理以及工程化实现