转载

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要求快速求出目标函数的最优解,最好是能有解析解。

怎样实现Online Learning

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

Bayesian Online Learning

贝叶斯方法能够比较自然地导出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算法的损失函数,一般也不是能够很快求解的,这种情况下,一般需要找一个代理的损失函数。

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

  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算法理论与实践

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

美团重排序Online Learning架构

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

Online Learning算法理论与实践

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

训练数据生成

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

Online Learning算法理论与实践

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

特征

用的特征如下图所示:

Online Learning算法理论与实践

算法选择

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

算法 AUC 模型参数个数
FTRL 0.8432 200W
BPR 0.8441 1500W

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

模型训练

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

线上效果

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

Online Learning算法理论与实践

参考资料

  • [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.
原文  http://tech.meituan.com/online-learning.html
正文到此结束
Loading...