Online Learning算法理论与实践

系统管理员 2023-10-17 19:56 18阅读 0赞

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-flow.png][]

Online Learning有点像自动控制系统，但又不尽相同，二者的区别是：Online Learning的优化目标是整体的损失函数最小化，而自动控制系统要求最终结果与期望值的偏差最小。

传统的训练方法，模型上线后，更新的周期会比较长（一般是一天，效率高的时候为一小时），这种模型上线后，一般是静态的（一段时间内不会改变），不会与线上的状况有任何互动，假设预测错了，只能在下一次更新的时候完成更正。Online Learning训练方法不同，会根据线上预测的结果动态调整模型。如果模型预测错误，会及时做出修正。因此，Online Learning能够更加及时地反映线上变化。

###### Online Learning的优化目标 ######

![online-learning-model-flow.png][]

如上图所示，Online Learning训练过程也需要优化一个目标函数（红框标注的），但是和其他的训练方法不同，Online Learning要求快速求出目标函数的最优解，最好是能有解析解。

### 怎样实现Online Learning ###

前面说到Online Learning要求快速求出目标函数的最优解。要满足这个要求，一般的做法有两种：Bayesian Online Learning和Follow The Regularized Leader。下面就详细介绍这两种做法的思路。

###### Bayesian Online Learning ######

贝叶斯方法能够比较自然地导出Online Learning的训练方法：给定参数先验，根据反馈计算后验，将其作为下一次预测的先验，然后再根据反馈计算后验，如此进行下去，就是一个Online Learning的过程，如下图所示。

![bayesian-online-learning-flow.png][]

举个例子， 我们做一个抛硬币实验，估算硬币正面的概率\$ \\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算法的损失函数，一般也不是能够很快求解的，这种情况下，一般需要找一个代理的损失函数。

代理损失函数需要满足几个要求：

1.  代理损失函数比较容易求解，最好是有解析解
2.  优化代理损失函数求的解，和优化原函数得到的解差距不能太大

为了衡量条件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排序，如下图所示：

![online-learning-rerank.png][]

推荐重排序既能融合不同触发策略，又能较大幅度提高推荐效果（我们这里主要是下单率）。在移动端，屏幕更加小，用户每次看到的item数目更加少，排序的作用更加突出。

**美团重排序Online Learning架构**

美团Online Learning架构如下图所示：

![online-learning-server.png][]

线上的展示日志，点击日志和下单日志会写入不同的Kafka流。读取Kafka流，以HBase为中间缓存，完成label match（下单和点击对映到相应的展示日志），在做label match的过成中，会对把同一个session的日志放在一起，方便后面做skip above：

**训练数据生成**

移动端推荐的数据跟PC端不同，移动端一次会加载很多item，但是无法保证这些item会被用户看到。为了保证数据的准确性，我们采用了skip above的办法，如下图所示：

![online-learning-skip-above.png][]

假设用户点击了第i个位置，我们保留从第1条到第i+2条数据作为训练数据，其他的丢弃。这样能够最大程度的保证训练样本中的数据是被用户看到的。

**特征**

用的特征如下图所示：

![online-learning-feature.png][]

**算法选择**

我们尝试了FTRL和BPR效果，线下实验效果如下表：

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th style="text-align:center;">&nbsp;&nbsp;&nbsp;AUC&nbsp;&nbsp;&nbsp;</th> 
   <th style="text-align:center;">&nbsp;&nbsp;模型参数个数&nbsp;&nbsp;</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>FTRL</td> 
   <td style="text-align:center;">0.8432</td> 
   <td style="text-align:center;">200W</td> 
  </tr> 
  <tr> 
   <td>BPR</td> 
   <td style="text-align:center;">0.8441</td> 
   <td style="text-align:center;">1500W</td> 
  </tr> 
 </tbody> 
</table>

BPR的效果略好，但是我们线上选用了FTRL模型，主要原因是FTRL能够产生稀疏化的效果，训练出的模型会比较小。

**模型训练**

训练算法不断地从HBase中读取数据，完成模型地训练，训练模型放在Medis（美团内部地Redis）中，线上会用Medis中的模型预测下单率，根据预测的下单率，完成排序。

**线上效果**

上线后，最终的效果如下图所示，和base算法相比，下单率提高了5%。

![online-learning-result.png][]

### 参考资料 ###

*  \[1\] McMahan H B, Holt G, Sculley D, et al. Ad Click Prediction: a View from the Trenches. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 2013.
 *  \[2\] Graepel T, Candela J Q, Borchert T,et al. Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft's Bing Search Engine. Proceedings of the 27th International Conference on Machine Learning ICML. 2010.
 *  \[3\] Murphy K P. Machine Learning: A Probabilistic Perspective. The MIT Press. 2012.

**发现文章有错误、对内容有疑问，都可以关注美团点评技术团队微信公众号（meituantech），在后台给我们留言。我们每周会挑选出一位热心小伙伴，送上一份精美的小礼品。快来扫码关注我们吧！**

![公众号二维码][1521521024099-image.png]

[online-learning-flow.png]: https://tech.meituan.com//img/online-learning/online-learning-flow.png
[online-learning-model-flow.png]: https://tech.meituan.com//img/online-learning/online-learning-model-flow.png
[bayesian-online-learning-flow.png]: https://tech.meituan.com//img/online-learning/bayesian-online-learning-flow.png
[online-learning-rerank.png]: https://tech.meituan.com//img/online-learning/online-learning-rerank.png
[online-learning-server.png]: https://tech.meituan.com//img/online-learning/online-learning-server.png
[online-learning-skip-above.png]: https://tech.meituan.com//img/online-learning/online-learning-skip-above.png
[online-learning-feature.png]: https://tech.meituan.com//img/online-learning/online-learning-feature.png
[online-learning-result.png]: https://tech.meituan.com//img/online-learning/online-learning-result.png
[1521521024099-image.png]: https://tech.meituan.com//img/1521521024099-image.png