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 }$是一个非负递增序列。
解释：
- $\frac{1}{t}\sum^t_{r=1}G^{(r)}\cdot W$包括了之前所有梯度的平均值；
- 正则项$\Psi(W)$；
- 额外项$\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)}$。
未完待续。
