Online Learning算法理论与实践-k6k4.com

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的过程，如下图所示。

举个例子，我们做一个抛硬币实验，估算硬币正面的概率μ

。我们假设

μ的先验满足

p (μ) = Beta (α, β)

对于观测值

Y＝1，代表是正面，我们可以算的后验：

p (μ | Y = 1) = Beta (α + 1, β)

对于观测值

Y＝0，代表是反面，我们可以算的后验：

p (μ ∣ ∣ Y = 0) = Beta (α, β + 1)

按照上面的Bayesian Online Learning流程，我们可以得到估算

的Online Learning算法：

初始化 α

for i = 0 ... n

如果 Yi

是正面

α=α+1
如果

Yi是反面

β=β+1

最终: μ∼Beta(α,β)

，可以取

μ的期望，

μ=αα+β
假设抛了

N次硬币，正面出现

H次，反面出现

T次，按照上面的算法，可以算得：

μ = α + H α + β + N

和最大化似然函数：

l o g [p (μ ∣ α, β) \cdot p (Y = 1 ∣ μ) H \cdot p (Y = 0 ∣ μ) T]

得到的解是一样的。

上面的例子是针对离散分布的，我们可以再看一个连续分布的例子。

有一种测量仪器，测量的方差σ2

是已知的，测量结果为：

Y1,Y2,Y3,...,Yn, 求真实值

μ的分布。
仪器的方差是

σ2, 所以观测值Y满足高斯分布：

p (Y ∣ μ) = N (Y ∣ μ, σ 2)

观测到

Y1,Y2,Y3,...,Yn, 估计参数

μ 。
假设参数

μ 满足高斯分布：

p (μ) = N (μ ∣ m, v 2)

观测到

Yi, 可以计算的后验：

p (μ ∣ Y i) = N (μ ∣ Y i v 2 + m σ 2 σ 2 + v 2, σ 2 v 2 σ 2 + v 2)

可以得到以下的Online Learning算法：

初始化 m

for i = 0 ... n

观测值为Yi

更新

m = Y i v 2 + m σ 2 σ 2 + v 2

v 2 = σ 2 v 2 σ 2 + v 2

上面的两个结果都是后验跟先验是同一分布的（一般取共轭先验，就会有这样的效果），这个后验很自然的作为后面参数估计的先验。假设后验分布和先验不一样，我们该怎么办呢？

举个例子：假设上面的测量仪器只能观测到Y

，是大于0，还是小于0，即

Yi∈{−1，1},

Yi=−1，代表观测值小于0，

Yi=1代表观测值大于0。
此时，我们仍然可以计算后验分布：

p (μ ∣ Y i ＝ 1) = I ( μ > 0 ) p ( μ ) \int + \infty 0 p ( μ ) d u

p (μ ∣ Y i ＝ - 1) = I ( μ < 0 ) p ( μ ) \int 0 - \infty p ( μ ) d u

但是后验分布显然不是高斯分布（是截断高斯分布），这种情况下，我们可以用和上面分布KL距离最近的高斯分布代替。
观测到

Yi=1

K L (p (μ ∣ Y i = 1) | | N (μ ∣ m ̃, v ̃ 2))

可以求得：

m ̃ = m + v \cdot υ (m v)

v ̃ 2 = v 2 (1 - ω (m v))

观测到Yi=−1

K L (p (μ ∣ Y i = - 1) | | N (μ ∣ μ ̃, v ̃ 2))

可以求得：

m ̃ = m - v \cdot υ (- m v)

v ̃ 2 = v 2 (1 - ω (- m v))

两者综合起来，可以求得：

m ̃ = m + Y i v \cdot υ (Y i m v)

v ̃ 2 = v 2 (1 - ω (Y i m v))

其中：

υ (t) = ϕ ( t ) Φ ( t )

ϕ (t) = 1 2 π e x p (- 1 2 t 2)

Φ (t) = \int t - \infty ϕ (t) d t

ω (t) = υ (t) * (t - υ (t))

有了后验我们可以得到Online Bayesian Learning流程：

初始化 m

for i = 0 ... n

观测值为Yi

更新

m = m + Y i \cdot v \cdot υ (Y i \cdot m v)

v 2 = v 2 (1 - ω (Y i \cdot m v))

Bayesian Online Learning最常见的应用就是BPR（Bayesian Probit Regression）。

BPR

在看Online BPR前，我们先了解以下Linear Gaussian System(具体可以参考[3]的4.4节)。
x

是满足多维高斯分布：

p (x) = N (x ∣ μ x, Σ x)

y是

x通过线性变换加入随机扰动

Σy得到的变量：

p (y ∣ x) = N (y ∣ A x + b, Σ y)

已知x

，我们可以得到

的分布：

p (y) = N (y ∣ A μ X + b, Σ y + A Σ x A T)

上面这个结论的具体的推导过程可以参考[3]的4.4节，这里我们直接拿来用。

我们可以假设特征权重 w

满足独立高斯分布，即

p (w) = N (w ∣ μ, Σ)

：

μ = [μ 1, μ 2, . . ., μ D] T

Σ = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ σ 21 0 ⋮ 0 0 σ 22 ⋮ 0 \dots \dots ⋱ \dots 00 ⋮ σ 2 D ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥

是一维变量，是

w与特征向量

x的内积，加入方差为

β2

的扰动：

p (y ∣ w) = N (y ∣ x T w, β 2)

根据上面的式子可以得出：

p (y ∣ w) = N (y ∣ x T μ, x T Σ x + β 2)

由于我们只能观测到

Y，是大于0，还是小于0，即

Yi∈{−1，1},

Yi=−1，代表观测值小于0，

Yi=1

代表观测值大于0。

对于观测值，我们可以先用KL距离近似y

的分布，我们可以算出后验：

p (y ∣ Y i) = N (y ∣ m ̃, v ̃ 2)

m ̃ = x T μ + Y i υ (Y i \cdot x T μ x T Σ x + β 2 ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt)

v ̃ 2 = (x T Σ x + β 2) (1 - ω (Y i \cdot x T μ x T Σ x + β 2 ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt))

有了

y的近似分布，我们可以计算出后验：

p (w ∣ y) \propto p (y ∣ w) p (w)

可以求得：

p (w d ∣ y) = N (w d ∣ μ ̃ d, σ ̃ d)

μ ̃ d = μ d + Y i x i, d \cdot σ 2 d x T Σ x + β 2 ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt \cdot υ (Y i \cdot x T μ x T Σ x + β 2 ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt)

σ ̃ d = σ d \cdot [1 - x i, d \cdot σ 2 d x T Σ x + β 2 ω (Y i \cdot x T μ x T Σ x + β 2 ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt)]

Online Bayesian Probit Regression 训练流程如下：

初始化 μ1

σ21,

μ2,

σ22 , ... ,

μD,

σ2D

for i = 1 ... n

观测值为Yi

for d = 1 ... D
更新

μ d = μ d + Y i x i, d \cdot σ 2 d x T i Σ x i + β 2 ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt \cdot υ ⎛ ⎝ ⎜ ⎜ ⎜ Y i \cdot x T i μ x T i Σ x i + β 2 ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt ⎞ ⎠ ⎟ ⎟ ⎟

σ d = σ d \cdot ⎡ ⎣ ⎢ ⎢ ⎢ 1 - x i, d \cdot σ 2 d x T i Σ x i + β 2 ω ⎛ ⎝ ⎜ ⎜ ⎜ Y i \cdot x T i μ x T i Σ x + β 2 ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt ⎞ ⎠ ⎟ ⎟ ⎟ ⎤ ⎦ ⎥ ⎥ ⎥

FTRL

除了Online Bayesian Learning，还有一种做法就是FTRL（Follow The Regularized Leader）。
FTRL的网上资料很多，但是大部分介绍怎么样产生稀疏化解，而往往忽略了FTRL的基本原理。顾名思义，FTRL和稀疏化并没有关系，它只是一种做Online Learning的思想。

先说说FTL（Follow The Leader）算法，FTL思想就是每次找到让之前所有损失函数之和最小的参数。流程如下：

初始化 w

for t = 1 ... n

损失函数 ft

更新

w = a r g m i n w \sum i = 1 t f i (w)

FTRL算法就是在FTL的优化目标的基础上，加入了正规化，防止过拟合：

w = a r g m i n w \sum i = 1 t f i (w) + R (w)

其中，

R(w)

是正规化项。

FTRL算法的损失函数，一般也不是能够很快求解的，这种情况下，一般需要找一个代理的损失函数。

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

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

为了衡量条件2中的两个解的差距，这里需要引入regret的概念。

假设每一步用的代理函数是ht(w)

每次取

w t = a r g m i n w h t - 1 (w)

R e g r e t t = \sum t = 1 T f t (w t) - \sum t = 1 T f t (w *)

其中w∗=argminw∑ti=1fi(w)

，是原函数的最优解。就是我们每次代理函数求出解，离真正损失函数求出解的损失差距。当然这个损失必须满足一定的条件，Online Learning才可以有效，就是：

lim t \to \infty R e g r e t t t = 0

随着训练样本的增多，这两个优化目标优化出的参数的实际损失值差距越来越小。

代理函数 ht(w)

应该该怎么选呢？
如果

ft(w)

是凸函数，我们可以用下面的代理损失函数：

h t = \sum i = 1 t g i \cdot w + \sum i = 1 t (1 2 η t - 1 2 η t - 1) | | w - w t | | 2

其中gi

是

fi(wi)次梯度（如果

fi(wi)是可导的，次梯度就是梯度）。

ηt满足：

η t = α \sum t i = 1 g 2 t ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt

为了产生稀疏的效果，我们也可以加入l1正规化：

h t = \sum i = 1 t g i \cdot w + \sum i = 1 t (1 2 η t - 1 2 η t - 1) | | w - w t | | 2 ＋ λ 1 | w |

只要

ft(w)

是凸函数，上面的代理函数一定满足：

lim t \to \infty R e g r e t t t = 0

上面的式子我们可以得出w

的解析解：

w t + 1, i = {0 - η t (z t, i - s g n (z t, i) λ 1)) | z t, i | < λ 1 o t h e r w i s e

其中

z t, i = \sum s = 1 t g s, i + \sum s = 1 t (1 η t , i - 1 η t - 1 , i) w t, i

可以得到FTRL的更新流程如下：

输入α

λ1
初始化

w1...N,

z1..N=0 ,

n1..N=0

for t = 1 ... T

损失函数 ft

for i = 1 ..N

计算

$g t, i = \partial f i ( w t - 1 ) w t - 1 , i$

z t + = g t, i + 1 α (n i + g 2 t, i ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt - n i ‾ ‾ \sqrt) w t, i

n i + = g 2 t, i

更新

w t + 1, i = {0 - η t (z t, i - s g n (z t, i) λ 1)) | z t, i | < λ 1 o t h e r w i s e

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%。

参考资料

[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.

不想错过技术博客更新？想给文章评论、和作者互动？第一时间获取技术沙龙信息？

请关注我们的官方微信公众号“美团点评技术团队”。现在就拿出手机，扫一扫：

个人资料

随梦而飞
等级：6
文章：29篇
访问：2.2w
排名： 14

推荐圈子

Spark与机器学习