精华内容
下载资源
问答
  • 第十章 On-line Algorithms; 10.1 Introduction to On-line Algorithms ;前九章介绍的算法设计的条件 在算法执行之前整个输入数据的细节都很清楚 问题是在完全...On-line算法 在算法设计阶段或执行之前无完全信息可用,
  • Online Learning 算法简介

    2015-05-18 18:35:58
    Online Learning 算法简介,希望可以对理解Online Learning 算法有所帮助!
  • Online Learning算法理论与实践

    千次阅读 2016-09-17 07:07:21
    本文主要介绍Online Learning的基本原理和两种常用的Online Learning算法:FTRL(Follow The Regularized Leader)[1]和BPR(Bayesian Probit Regression)[2],以及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的过程,如下图所示。

    举个例子, 我们做一个抛硬币实验,估算硬币正面的概率 μ 。我们假设 μ 的先验满足

    p(μ)=Beta(α,β)

    对于观测值 Y1 ,代表是正面,我们可以算的后验:
    p(μ|Y=1)=Beta(α+1,β)

    对于观测值 Y0 ,代表是反面,我们可以算的后验:
    p(μ|Y=0)=Beta(α,β+1)

    按照上面的Bayesian Online Learning流程,我们可以得到估算 μ 的Online Learning算法:


    最终: μBeta(α,β) ,可以取 μ 的期望, μ=αα+β

    假设抛了 N 次硬币,正面出现 H 次,反面出现 T 次,按照上面的算法,可以算得:
    μ=α+Hα+β+N

    和最大化似然函数:
    log[p(μα,β)p(Y=1μ)Hp(Y=0μ)T]


    得到的解是一样的。

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

    有一种测量仪器,测量的方差 σ2 是已知的, 测量结果为: Y1,Y2,Y3,...,Yn , 求真实值 μ 的分布。

    仪器的方差是 σ2 , 所以观测值Y满足高斯分布:
    p(Yμ)=N(Yμ,σ2)

    观测到 Y1,Y2,Y3,...,Yn , 估计参数 μ
    假设参数 μ 满足高斯分布:
    p(μ)=N(μm,v2)

    观测到 Yi , 可以计算的后验:
    p(μYi)=N(μYiv2+mσ2σ2+v2,σ2v2σ2+v2)


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


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

    举个例子:假设上面的测量仪器只能观测到 Y ,是大于0,还是小于0,即 Yi{11} , Yi=1 ,代表观测值小于0, Yi=1 代表观测值大于0。

    此时,我们仍然可以计算后验分布:
    p(μYi1)=I(μ>0)p(μ)+0p(μ)du

    p(μYi1)=I(μ<0)p(μ)0p(μ)du

    但是后验分布显然不是高斯分布(是截断高斯分布),这种情况下,我们可以用和上面分布KL距离最近的高斯分布代替。
    观测到 Yi=1
    KL(p(μYi=1)||N(μm~,v~2))

    可以求得:
    m~=m+vυ(mv)

    v~2=v2(1ω(mv))

    观测到 Yi=1


    KL(p(μYi=1)||N(μμ~,v~2))

    可以求得:
    m~=mvυ(mv)

    v~2=v2(1ω(mv))

    两者综合起来,可以求得:

    m~=m+Yivυ(Yimv)

    v~2=v2(1ω(Yimv))

    其中:
    υ(t)=ϕ(t)Φ(t)

    ϕ(t)=12πexp(12t2)

    Φ(t)=tϕ(t)dt

    ω(t)=υ(t)(tυ(t))

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


    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(yx)=N(yAx+b,Σy)

    已知 x ,我们可以得到 y 的分布:

    p(y)=N(yAμX+b,Σy+AΣxAT)

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

    我们可以假设特征权重 w 满足独立高斯分布,即

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

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

    Σ=σ21000σ22000σ2D

    Y 是一维变量,是 w 与特征向量 x 的内积,加入方差为 β2 的扰动:

    p(yw)=N(yxTw,β2)

    根据上面的式子可以得出:
    p(yw)=N(yxTμ,xTΣx+β2)

    由于我们只能观测到 Y ,是大于0,还是小于0,即 Yi{11} , Yi=1 ,代表观测值小于0, Yi=1 代表观测值大于0。

    对于观测值,我们可以先用KL距离近似 y 的分布,我们可以算出后验:

    p(yYi)=N(ym~,v~2)

    m~=xTμ+Yiυ(YixTμxTΣx+β2)

    v~2=(xTΣx+β2)(1ω(YixTμxTΣx+β2))

    有了 y 的近似分布,我们可以计算出后验:
    p(wy)p(yw)p(w)

    可以求得:

    p(wdy)=N(wdμ~d,σ~d)

    μ~d=μd+Yixi,dσ2dxTΣx+β2υ(YixTμxTΣx+β2)
    σ~d=σd[1xi,dσ2dxTΣx+β2ω(YixTμxTΣx+β2)]

    Online Bayesian Probit Regression 训练流程如下:


    FTRL

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

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


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

    w=argminwi=1tfi(w)+R(w)

    其中, R(w) 是正规化项。

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

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

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

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

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

    wt=argminwht1(w)

    Regrett=t=1Tft(wt)t=1Tft(w)

    其中 w=argminwti=1fi(w) ,是原函数的最优解。就是我们每次代理函数求出解,离真正损失函数求出解的损失差距。当然这个损失必须满足一定的条件,Online Learning才可以有效,就是:

    limtRegrettt=0

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

    代理函数 ht(w) 应该该怎么选呢?

    如果 ft(w) 是凸函数,我们可以用下面的代理损失函数:
    ht=i=1tgiw+i=1t(12ηt12ηt1)||wwt||2

    其中 gi fi(wi) 次梯度(如果 fi(wi) 是可导的,次梯度就是梯度)。 ηt 满足:

    ηt=αti=1g2t

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

    ht=i=1tgiw+i=1t(12ηt12ηt1)||wwt||2λ1|w|

    只要 ft(w) 是凸函数,上面的代理函数一定满足:
    limtRegrettt=0

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

    wt+1,i={0ηt(zt,isgn(zt,i)λ1))|zt,i|<λ1otherwise

    其中

    zt,i=s=1tgs,i+s=1t(1ηt,i1ηt1,i)wt,i

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


    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效果,线下实验效果如下表:


    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.

    原文链接:http://tech.meituan.com/online-learning.html

    展开全文
  • Online LR—— FTRL 算法理解

    千次阅读 2018-01-22 10:13:45
    Online LR—— FTRL 算法理解 Online Learning定义 Online Learning是一种模型训练的方法,能够根据线上反馈数据,实时快速的进行模型调整,使得模型及时反映线上的变化,提高线上预测的准确率。Online Learning的...

    Online LR—— FTRL 算法理解

    Online Learning定义

    Online Learning是一种模型训练的方法,能够根据线上反馈数据,实时快速的进行模型调整,使得模型及时反映线上的变化,提高线上预测的准确率。Online Learning的流程包括:将模型预测结果展现给用户,然后收集用户的反馈数据,再来训练模型,形成闭环的系统。

    与传统训练方法的区别

    传统的训练方法在模型训练上线后,一般是静态的,不会于线上的状况有任何的互动,加入预测错误,只能在下一次更新的时候完成修正,但是这个更新的时间一般比较长。Online Learning训练方法不同,会根据线上的预测结果动态调整模型,加入模型预测错误,会及时做出修正,因此Online Learning能够更加及时地反应线上变化。对于Online learning最重要的问题是SGD很难得到需要的正则化设计的解,特别是几乎得不到稀疏解(因为是浮点运算,训练出的w向量很难出现绝对的0。 当然可以采用当w较小时就强制为0)。

    此处插入下关于稀疏性的常见解决方法[关于稀疏性可参考](http://blog.sina.com.cn/s/blog_eb3aea990101e8rj.html)
    1.  加入L1范数
    2.  在L1范数的基础上做截断:设定一个阈值做截断来保证稀疏,在online训练K个数据阶段一次。
    3.  Black-box wrapper: 利用黑盒方法去掉一些特征,重新训练看去掉的特征是否有效。
    

    Online Learning目标

    Online Learning的优化目标是使得整体的损失函数最小化,它需要快速求解目标函数的最优解。

    实现方法

    Bayesian Online Learning

    贝叶斯方法通过给定参数先验,根据反馈计算后验,将其作为下一次预测的先验,然后根据反馈计算后验,如此循环,可以参考此处

    FTRL

    FTRL 是在之前的几个工作上产生的,主要出发点就是为了提高稀疏度且满足精度要求,关于这个发展可以参照这个地址讲的很清晰
    先上FTRL 的伪代码:

    这里写图片描述

    即上面所谓的per-coordinate,其意思是FTRL是对w每一维分开训练更新的,每一维使用的是不同的学习速率,也是上面代码中lamda2之前的那一项。与w所有特征维度使用统一的学习速率相比,这种方法考虑了训练样本本身在不同特征上分布的不均匀性,如果包含w某一个维度特征的训练样本很少,每一个样本都很珍贵,那么该特征维度对应的训练速率可以独自保持比较大的值,每来一个包含该特征的样本,就可以在该样本的梯度上前进一大步,而不需要与其他特征维度的前进步调强行保持一致。

    关于这个公式是怎么来的,推导如下:

    这里写图片描述

    在论文中还提到了一些工程上的小trick, 我现在还感受不到啦~ 可以参考上面给的参考地址的解释,感觉很厉害。

    最后当然还是得呼应下标题,为什么说是Online LR实现, 其实FTRL 就是正则项为0的SGD算法。

    这里写图片描述

    以上就是一些看论文的整理啦。

    展开全文
  • online_psp_matlab:在线PCA算法的基准
  • 在线学习算法(Online Learning)理论与实践

    万次阅读 多人点赞 2018-11-08 21:17:38
    本文主要介绍Online Learning的基本原理和两种常用的Online Learning算法:FTRL(Follow The Regularized Leader)[1]和BPR(Bayesian Probit Regression)[2],以及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
    如果 YiYi是反面
    \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 |Y_{i} =1 ) = \frac{ I(\mu > 0 )p(\mu)}{ \int_{0}^{+\infty} p(\mu)\mathrm{d}u}

                                                                  p( \mu | 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)
    yx通过线性变换加入随机扰动\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},\cdots ,\mu _{D},\sigma _{D}^{2}
    for i = 1 ... n

    观测值为YiYi
    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 )\left \| w - w_{t} \right \|^{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.

    wt+1,i={0−ηt(zt,i−sgn(zt,i)λ1))|zt,i|<λ1otherwisewt+1,i={0|zt,i|<λ1−ηt(zt,i−sgn(zt,i)λ1))otherwise

    其中

                                                              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

    损失函数 ftft
    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     模型参数个数  
    FTRL0.8432200W
    BPR0.84411500W

    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.
    展开全文
  • 在线算法 online algorithm在线算法 online algorithm
  • 1. 在线算法online) PFC(prefix-free code)编码树的解码过程:可以在二进制编码串的接收过程中实时进行,而不必等到所有比特位都到达后才开始; 2. 离线算法(offline) 转载于:...

    1. 在线算法(online)

    • PFC(prefix-free code)编码树的解码过程:可以在二进制编码串的接收过程中实时进行,而不必等到所有比特位都到达后才开始;

    2. 离线算法(offline)

    转载于:https://www.cnblogs.com/mtcnn/p/9423752.html

    展开全文
  • 在线算法(online algorithm)--竞争性分析

    千次阅读 2020-09-08 19:28:12
    文章目录一、competitve analysis二、page replacement2.1 问题背景2.2 deterministic online algorithm2.2.1 LIFO和LFU不是α\alphaα-竞争算法2.2.2 LRU和FIFO是kkk-竞争算法2.3 deterministic online algorithm的...
  • 为了减小以太网无源光网络(EPON) offline调度产生的上行信道空闲时间,提出了基于最小群时延优先(SPD)改进的online & offline混合调度算法,考虑到环路时延(RTT)的影响,在请求带宽大小的基础上再结合对RTT范围的限定,...
  • 文章提出了一种通过online hard example mining(OHEM)算法训练基于区域的卷积检测算子的高效目标检测算法,能够对简单样本和一些小数量样本进行抑制,使得训练过程更加高效。该方法利用显著的bootstrapping技术...
  • 在线随机森林算法包(online-random-forests),在linux系统下安装调试。 可用于机器学习研究。
  • 题目1158:买房子 题目描述: 某程序员开始工作,年薪N万,他希望在中关村公馆买一套60平米的房子,现在价格是200万,假设房子价格以每年百分之K增长,并且该程序员未来年薪不变,且不吃不喝,不用交税,每年所得...
  • 题目1062:分段函数题目描述: 编写程序,计算下列分段函数y=f(x)的值。 y=-x+2.5; 0 y=2-1.5(x-3)(x-3); 2 y=x/2-1.5; 4 输入: 一个浮点数N ...测试数据可能有多组,对于每一组数据, 输出N对应的分段函数值:f...
  • python算法 소개 이는저에서에서에서즘즘즘들을입니입니다。 목적 KO(KOI)를이를를다되었습니다。
  • OHEM: online hard example mining 论文链接:https://arxiv.org/abs/1604.03540 主要特点: 1.不需要设置正负样本比例来解决数据类别不平衡问题 2.数据集越大,性能越明显 文中所说: 1.OHEM is a simple ...
  • Coding-Online 整合了一下算法在线练习网站 1.题目全。Lintcode上面目前已有324道题目,基本涵盖了所有算法和数据结构的知识点,题目的难度划分合理,而且可以随时把握刷题的进度。 2.支持中文。这是我选择Lintcode...
  • online_chewing_detection 目前正在开发一种多功能的情境感知智能眼镜,以支持自动饮食监测领域。 该项目提供了在线咀嚼检测算法的实现,该算法能够实时监控饮食活动。 该算法是基于对邻近数据的时间序列分析而设计...
  • 在线学习算法 在专家建议下的在线学习环境中实施一些在线算法: 外部后悔最小化:指数加权平均预报员 内部后悔最小化:切萨·比安奇和卢戈斯减少了外部后悔最小化(第4章) 在线校准:通过内部后悔最小化 在线重新...
  • online learning】在线学习算法

    千次阅读 2018-11-08 15:18:00
    L1-RDA与L1-FOBOS不同的是考虑累积梯度的平均值,因此更容易产生稀疏解,具体算法介绍参见博客: https://zr9558.com/2016/01/12/regularized-dual-averaging-algorithm-rda/ 优化目标: 算法更新: ...
  • online_chewing_detection 目前正在开发一种多功能的情境感知智能眼镜,以支持自动饮食监测领域。 该项目提供了在线叮咬检测算法的python实现,该算法能够实时监控饮食活动。 该算法是基于对邻近数据的时间序列分析...
  • 百柱在线裁判 用python解决算法问题
  • 在线遗传算法整定PID程序及论文-online ga.pdf 本文是基于德国都柏林城市大学(Dublin City University)学位论文《On-line PID Controller Tuning using Genetic Algorithms》而作的工作。本人的工作,只是做翻译...
  • 这是《 数据处理与算法设计》中的一个章节,这本书正在整理当中,大家对这个书有什么建议,希望都提出来 [[Online Game 第七章 寻路算法]]下载:
  • high_level_algorithm_online_judge 南京大学 高级算法 oj题目
  • 百柱在线裁判 [Python]日本央行的研究算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 130,100
精华内容 52,040
关键字:

online算法