Online Learning算法理论与实践
Online Learning是工业界比较常用的机器学习算法，在很多场景下都能有很好的效果。本文主要介绍Online Learning的基本原理和两种常用的Online Learning算法：FTRL（Follow The Regularized Leader）[1]和BPR（Bayesian Probit Regression）[2]，以及Online Learning在美团移动端推荐重排序的应用。
什么是Online Learning
准确地说，Online Learning并不是一种模型，而是一种模型的训练方法，Online Learning能够根据线上反馈数据，实时快速地进行模型调整，使得模型及时反映线上的变化，提高线上预测的准确率。Online Learning的流程包括：将模型的预测结果展现给用户，然后收集用户的反馈数据，再用来训练模型，形成闭环的系统。如下图所示：
Online Learning有点像自动控制系统，但又不尽相同，二者的区别是：Online Learning的优化目标是整体的损失函数最小化，而自动控制系统要求最终结果与期望值的偏差最小。
传统的训练方法，模型上线后，更新的周期会比较长（一般是一天，效率高的时候为一小时），这种模型上线后，一般是静态的（一段时间内不会改变），不会与线上的状况有任何互动，假设预测错了，只能在下一次更新的时候完成更正。Online Learning训练方法不同，会根据线上预测的结果动态调整模型。如果模型预测错误，会及时做出修正。因此，Online Learning能够更加及时地反映线上变化。
Online Learning的优化目标
如上图所示，Online Learning训练过程也需要优化一个目标函数（红框标注的），但是和其他的训练方法不同，Online Learning要求快速求出目标函数的最优解，最好是能有解析解。
怎样实现Online Learning
前面说到Online Learning要求快速求出目标函数的最优解。要满足这个要求，一般的做法有两种：Bayesian Online Learning和Follow The Regularized Leader。下面就详细介绍这两种做法的思路。
Bayesian Online Learning
贝叶斯方法能够比较自然地导出Online Learning的训练方法：给定参数先验，根据反馈计算后验，将其作为下一次预测的先验，然后再根据反馈计算后验，如此进行下去，就是一个Online Learning的过程，如下图所示。
举个例子， 我们做一个抛硬币实验，估算硬币正面的概率\( \mu \)。我们假设\( \mu \)的先验满足
$$ p\left(\mu \right) = \operatorname{Beta}(\alpha, \beta)$$
对于观测值\( Y＝1 \)，代表是正面，我们可以算的后验：
$$p\left( \mu | Y=1 \right) = \operatorname{Beta}(\alpha+1, \beta)$$
对于观测值\( Y＝0 \)，代表是反面，我们可以算的后验：
$$ p\left(\mu \right | Y=0) = \operatorname{Beta}(\alpha, \beta+1)$$
按照上面的Bayesian Online Learning流程，我们可以得到估算\( \mu \)的Online Learning算法：
初始化 \( \alpha \),\( \beta \)
for i = 0 ... n如果 \( Y_i \)是正面
\( \alpha = \alpha + 1 \)
如果 \(Y_i\)是反面
\( \beta = \beta + 1 \)
最终: \( \mu \sim \operatorname{Beta}(\alpha, \beta) \)，可以取\( \mu \)的期望，\( \mu = \frac{\alpha}{\alpha+\beta}\)
假设抛了\(N\)次硬币，正面出现\(H\)次，反面出现\(T\)次，按照上面的算法，可以算得：
$$ \mu = \frac{ \alpha + H}{\alpha + \beta + N} $$
和最大化似然函数：
$$ \mathrm{log}\left[ p\left(\mu \mid \alpha,\beta \right) \cdot p \left( Y = 1 \mid \mu \right)^{H} \cdot p \left( Y = 0 \mid \mu \right)^{T} \right] $$
得到的解是一样的。
上面的例子是针对离散分布的，我们可以再看一个连续分布的例子。
有一种测量仪器，测量的方差\( \sigma^2\)是已知的， 测量结果为：\( Y_1 , Y_2 , Y_3 , ... , Y_n \), 求真实值\( \mu \)的分布。
仪器的方差是\( \sigma ^{2}\), 所以观测值Y满足高斯分布：
$$p\left(Y \mid \mu\right) = N\left( Y \mid \mu,\sigma^2 \right)$$
观测到 \( Y_1 , Y_2 , Y_3 , ... , Y_n \), 估计参数 \( \mu \) 。
假设参数 \( \mu \) 满足高斯分布：
$$ p\left( \mu \right) = N\left( \mu \mid m ,v ^2 \right) $$
观测到\( Y_i \), 可以计算的后验：
$$ p \left( \mu \mid Y_i \right) = N\left( \mu \mid \frac{Y_i v^{2}+m\sigma^{2}}{\sigma^{2}+v^{2}} , \frac{\sigma^{2}v^{2}}{\sigma^{2}+v^{2}} \right) $$
可以得到以下的Online Learning算法：
初始化 \( m \),\( v ^{2} \)
for i = 0 ... n观测值为\( Y_{i} \)
更新
$$ m = \frac{Y_i v^{2} + m \sigma^{2}}{\sigma^{2} + v^{2}} $$
$$ v^{2} = \frac{\sigma^{2} v^{2}}{\sigma^{2} + v^{2} } $$
上面的两个结果都是后验跟先验是同一分布的（一般取共轭先验，就会有这样的效果），这个后验很自然的作为后面参数估计的先验。假设后验分布和先验不一样，我们该怎么办呢？
举个例子：假设上面的测量仪器只能观测到\( Y \)，是大于0，还是小于0，即\(Y_{i} \in \{-1，1\} \),\( Y_{i} = -1\)，代表观测值小于0，\( Y_{i} = 1\)代表观测值大于0。
此时，我们仍然可以计算后验分布：
$$ p( \mu \mid Y_i ＝1) = \frac{ I(\mu > 0 )p(\mu)}{ \int_{0}^{+\infty} p(\mu)\mathrm{d}u}$$
$$ p( \mu \mid Y_i ＝-1) = \frac{ I(\mu< 0) p(\mu)}{ \int_{-\infty}^{0} p(\mu)\mathrm{d}u}$$
但是后验分布显然不是高斯分布（是截断高斯分布），这种情况下，我们可以用和上面分布KL距离最近的高斯分布代替。
观测到\( Y_{i} = 1\)
$$ KL( p(\mu \mid Y_i =1) || N(\mu \mid \tilde m ,\tilde v^{2})) $$
可以求得：
$$\tilde m = m + v \cdot \upsilon\left(\frac{m}{v}\right)$$
$$\tilde v^{2} = v^2\left(1 - \omega\left(\frac{m}{v}\right)\right)$$
观测到\( Y_{i} = -1\)
$$ KL( p(\mu \mid Y_i =-1) || N(\mu \mid \tilde \mu ,\tilde v^{2})) $$
可以求得：
$$\tilde m = m - v \cdot \upsilon\left(-\frac{m}{v}\right)$$
$$\tilde v^{2} = v^2\left(1 - \omega\left(-\frac{m}{v}\right)\right)$$
两者综合起来，可以求得：
$$\tilde m = m + Y_{i} v \cdot \upsilon\left(Y_{i}\frac{m}{v}\right)$$
$$\tilde v^{2} = v^2\left(1 - \omega\left(Y_{i}\frac{m}{v}\right)\right)$$
其中：
$$\upsilon(t) = \frac{\phi(t)}{\Phi(t)}$$
$$\phi(t) = \frac{1}{2\pi} \mathrm{exp} \left(-\frac{1}{2} t^2\right) $$
$$\Phi(t)=\int_{-\infty}^{t} \phi(t)\mathrm{d}t$$
$$\omega(t) = \upsilon(t)*(t-\upsilon(t))$$
有了后验我们可以得到Online Bayesian Learning流程：
初始化 \( m \),\( v ^{2} \)
for i = 0 ... n观测值为\( Y_{i} \)
更新$$ m = m + Y_{i} \cdot v \cdot \upsilon\left(Y_{i} \cdot \frac{m}{v}\right) $$
$$ v^{2} = v^2\left(1 - \omega\left(Y_{i} \cdot \frac{m}{v}\right)\right) $$
Bayesian Online Learning最常见的应用就是BPR（Bayesian Probit Regression）。
BPR
在看Online BPR前，我们先了解以下Linear Gaussian System(具体可以参考[3]的4.4节)。
\(x\)是满足多维高斯分布：
$$p \left( x \right) = N \left(x \mid \mu_x, \Sigma_x \right) $$
\(y\)是\(x\)通过线性变换加入随机扰动\(\Sigma_y \)得到的变量：
$$p \left(y \mid x \right) = N \left(y \mid Ax+b ,\Sigma_y \right)$$
已知\(x\)，我们可以得到\(y\)的分布：
$$ p \left( y \right) = N \left( y \mid A\mu_X +b, \Sigma_y + A \Sigma_x A^{T} \right)$$
上面这个结论的具体的推导过程可以参考[3]的4.4节，这里我们直接拿来用。
我们可以假设特征权重 \(w\) 满足独立高斯分布，即$$ p(w) = N\left( w \mid \mu ,\Sigma \right)$$：
$$ \mu = \left[ \mu_1,\mu_2,...,\mu_D\right]^{\mathrm{T}}$$
$$
\Sigma = \left[ \begin{matrix}
\sigma_1^{2} & 0 & \ldots & 0 \newline
0 & \sigma_2^{2} & \ldots & 0 \newline
\vdots &\vdots & \ddots & \vdots \newline
0 & 0 & \ldots & \sigma_D^{2} \newline
\end{matrix} \right]
$$
\(Y\)是一维变量，是\(w\)与特征向量\(x\)的内积，加入方差为\( \beta^{2}\)的扰动：
$$p\left( y \mid w\right) = N(y \mid x^Tw, \beta^2)$$
根据上面的式子可以得出：
$$p\left( y \mid w\right) = N(y \mid x^T\mu, x^T\Sigma x +\beta^2)$$
由于我们只能观测到\( Y \)，是大于0，还是小于0，即\(Y_{i} \in \{-1，1\} \),\( Y_{i} = -1\)，代表观测值小于0，\( Y_{i} = 1\)代表观测值大于0。
对于观测值，我们可以先用KL距离近似\(y\)的分布，我们可以算出后验：
$$
p\left(y\mid Y_i\right) = N\left(y\mid \tilde m, \tilde v^2 \right)$$
$$\tilde m = x^T\mu + Y_{i}\upsilon \left(Y_{i} \cdot \frac{x^T\mu}{\sqrt{x^T\Sigma x +\beta^2}}\right)$$
$$\tilde v^2 = \left(x^T\Sigma x +\beta^2\right)\left(1-\omega\left(Y_{i} \cdot \frac{x^T\mu}{\sqrt{x^T\Sigma x +\beta^2}} \right)\right) $$
有了\(y\)的近似分布，我们可以计算出后验：
$$p\left(w \mid y \right) \propto p\left(y \mid w \right) p\left(w\right)$$
可以求得：
$$ p\left( w_{d} \mid y \right) = N\left( w_{d} \mid \tilde \mu_{d},\tilde \sigma_{d} \right)$$
$$ \tilde \mu_{d} = \mu_{d} + Y_{i} x_{i,d}\cdot \frac {\sigma_{d}^{2} }{\sqrt{x^T\Sigma x +\beta^2}} \cdot \upsilon \left(Y_{i} \cdot \frac{x^T\mu}{\sqrt{x^T\Sigma x +\beta^2}}\right) $$
$$ \tilde \sigma_{d} = \sigma_{d} \cdot \left[ 1 - x_{i,d} \cdot \frac{\sigma_{d}^{2}}{x^T\Sigma x +\beta^2} \omega\left(Y_{i} \cdot \frac{x^T\mu}{\sqrt{x^T\Sigma x +\beta^2}} \right) \right]$$
Online Bayesian Probit Regression 训练流程如下：
初始化 \( \mu_{1} \),\( \sigma_{1}^{2} \), \( \mu_{2} \),\( \sigma_{2}^{2} \) , ... , \( \mu_{D} \),\( \sigma_{D}^{2} \)
for i = 1 ... n观测值为\( Y_{i} \)
for d = 1 ... D
更新$$ \mu_{d} = \mu_{d} + Y_{i} x_{i,d}\cdot \frac {\sigma_{d}^{2} }{\sqrt{x_{i}^T\Sigma x_{i} +\beta^2}} \cdot \upsilon \left(Y_{i} \cdot \frac{x_{i}^T\mu}{\sqrt{x_{i}^T\Sigma x_{i} +\beta^2}}\right) $$
$$ \sigma_{d} = \sigma_{d} \cdot \left[ 1 - x_{i,d} \cdot \frac{\sigma_{d}^{2}}{x_{i}^T\Sigma x_{i} +\beta^2} \omega\left(Y_{i} \cdot \frac{x_{i}^T\mu}{\sqrt{x_{i}^T\Sigma x +\beta^2}} \right) \right]$$
FTRL
除了Online Bayesian Learning，还有一种做法就是FTRL（Follow The Regularized Leader）。
FTRL的网上资料很多，但是大部分介绍怎么样产生稀疏化解，而往往忽略了FTRL的基本原理。顾名思义，FTRL和稀疏化并没有关系，它只是一种做Online Learning的思想。
先说说FTL（Follow The Leader）算法，FTL思想就是每次找到让之前所有损失函数之和最小的参数。流程如下：
初始化 \( w \)
for t = 1 ... n损失函数 \( f_{t} \)
更新$$ w = argmin_{w} \sum_{i=1}^{t} f_i \left (w \right) $$
FTRL算法就是在FTL的优化目标的基础上，加入了正规化，防止过拟合：
$$ w = argmin_{w} \sum_{i=1}^{t} f_i \left (w \right) + R(w) $$
其中，\(R(w)\)是正规化项。
FTRL算法的损失函数，一般也不是能够很快求解的，这种情况下，一般需要找一个代理的损失函数。
代理损失函数需要满足几个要求：
- 代理损失函数比较容易求解，最好是有解析解
- 优化代理损失函数求的解，和优化原函数得到的解差距不能太大
为了衡量条件2中的两个解的差距，这里需要引入regret的概念。
假设每一步用的代理函数是\( h_t \left( w \right)\)
每次取
$$ w_{t} = argmin_{w} h_{t-1} \left (w \right) $$
$$Regret_{t} =\sum_{t=1}^{T}f_{t}\left(w_{t}\right) - \sum_{t=1}^{T}f_{t}\left(w^{*}\right)$$
其中\( w^{*} = argmin_{w} \sum_{i=1}^{t}f_i\left(w\right) \)，是原函数的最优解。就是我们每次代理函数求出解，离真正损失函数求出解的损失差距。当然这个损失必须满足一定的条件，Online Learning才可以有效，就是：
$$ \lim_{t \rightarrow \infty } \frac{Regret_t}{t} = 0 $$
随着训练样本的增多，这两个优化目标优化出的参数的实际损失值差距越来越小。
代理函数 \( h_t(w)\) 应该该怎么选呢？
如果\( f_t(w) \) 是凸函数，我们可以用下面的代理损失函数：
$$ h_{t} = \sum_{i=1}^{t} g_{i}\cdot w + \sum_{i=1}^{t} \left(\frac{1}{2 \eta_{t}} - \frac{1}{2 \eta_{t-1}} \right)||w - w_{t}||^{2}$$
其中\(g_i\) 是\(f_i( w_i) \)次梯度（如果 \(f_i(w_i)\)是可导的，次梯度就是梯度）。\( \eta_{t} \)满足：
$$
\eta_{t} = \frac{\alpha}{\sqrt{\sum_{i=1}^{t} g_{t}^{2}}}
$$
为了产生稀疏的效果，我们也可以加入l1正规化：
$$ h_{t} = \sum_{i=1}^{t} g_{i}\cdot w + \sum_{i=1}^{t} \left(\frac{1}{2 \eta_{t}} - \frac{1}{2 \eta_{t-1}} \right)||w - w_{t}||^{2} ＋ \lambda_{1}|w|$$
只要\( f_t(w) \) 是凸函数，上面的代理函数一定满足：
$$ \lim_{t \rightarrow \infty } \frac{Regret_t}{t} = 0 $$
上面的式子我们可以得出\(w\)的解析解：
$$
w_{t+1,i} = \left\{
\begin{array}{ll}
0 & |z_{t,i}| < \lambda_{1} \newline
-\eta_{t}(z_{t,i} - sgn(z_{t,i})\lambda_{1}) ) & otherwise
\end{array}
\right.
$$
其中
$$
z_{t,i} = \sum_{s=1}^{t}g_{s,i} + \sum_{s=1}^{t}\left( \frac{1}{ \eta_{t,i}} - \frac{1}{ \eta_{t-1,i}} \right) w_{t,i}
$$
可以得到FTRL的更新流程如下：
输入\(\alpha \), \( \lambda_{1} \)
初始化 \( w_{1...N} \), \( z_{1..N} = 0\) , \(n_{1..N} = 0\)
for t = 1 ... T损失函数 \( f_{t} \)
for i = 1 ..N计算
$$ g_{t,i} = \frac{\partial f_{i}\left(w_{t-1}\right)}{w_{t-1,i}}$$
$$
z_{t} += g_{t,i} + \frac{1}{\alpha} \left( \sqrt{n_{i} + g_{t,i}^{2}} -\sqrt{ n_{i} } \right) w_{t,i}
$$$$ n_{i} += g_{t,i}^{2}$$
更新$$
w_{t+1,i} = \left\{
\begin{array}{ll}
0 & |z_{t,i}| < \lambda_{1} \newline
-\eta_{t}(z_{t,i} - sgn(z_{t,i})\lambda_{1}) ) & otherwise
\end{array}
\right.
$$
Online Learning实践
前面讲了Online Learning的基本原理，这里以移动端推荐重排序为例，介绍一下Online Learning在实际中的应用。
推荐重排序介绍
目前的推荐系统，主要采用了两层架构，首先是触发层，会根据上下文条件和用户的历史行为，触发用户可能感兴趣的item，然后由排序模型对触发的item排序，如下图所示：
推荐重排序既能融合不同触发策略，又能较大幅度提高推荐效果（我们这里主要是下单率）。在移动端，屏幕更加小，用户每次看到的item数目更加少，排序的作用更加突出。
美团重排序Online Learning架构
美团Online Learning架构如下图所示：
线上的展示日志，点击日志和下单日志会写入不同的Kafka流。读取Kafka流，以HBase为中间缓存，完成label match（下单和点击对映到相应的展示日志），在做label match的过成中，会对把同一个session的日志放在一起，方便后面做skip above：
训练数据生成
移动端推荐的数据跟PC端不同，移动端一次会加载很多item，但是无法保证这些item会被用户看到。为了保证数据的准确性，我们采用了skip above的办法，如下图所示：
假设用户点击了第i个位置，我们保留从第1条到第i+2条数据作为训练数据，其他的丢弃。这样能够最大程度的保证训练样本中的数据是被用户看到的。
特征
用的特征如下图所示：
算法选择
我们尝试了FTRL和BPR效果，线下实验效果如下表：
| 算法 | AUC | 模型参数个数 |
|---|---|---|
| FTRL | 0.8432 | 200W |
| BPR | 0.8441 | 1500W |
BPR的效果略好，但是我们线上选用了FTRL模型，主要原因是FTRL能够产生稀疏化的效果，训练出的模型会比较小。
模型训练
训练算法不断地从HBase中读取数据，完成模型地训练，训练模型放在Medis（美团内部地Redis）中，线上会用Medis中的模型预测下单率，根据预测的下单率，完成排序。
线上效果
上线后，最终的效果如下图所示，和base算法相比，下单率提高了5%。
精准化营销一直以来都是互联网营销业务在细分市场下快速获取用户和提高转化的利器。在移动互联网爆发的今天，数据量呈指数增长，如何在移动和大数据场景下用数据驱动进行精准营销，从而提高营销效能，成为营销业务部门的 ...