yahoo在2010年在《A contextual-bandit approach to personalized news article recommendation》中介绍了contextual bandit算法。

2.公式&相关工作

在本节,我们定义了K-armed contextual bandit问题,作为示例,展示了如何用它来建模个性化新闻推荐问题。

2.1 Multi-armed Bandit公式

个性化新闻推荐的问题可以天然建模成:带context信息的multi-armded bandit问题。根据[18],我们称之为”contextual bandit”。正式的,一个contextual-bandit算法A会以离散方式处理实验(trials) t=1,2,3,…,在试验t上,有:

  • 1.该算法会观察当前用户和一个关于arms或actions的集合,以及对于arm 的它们的特征向量(feature vectors) vector 会同时总结用户和arm a的信息,被称为context
  • 2.基于在之前实验中的已观察收益(observed payoffs),算法A会选择一个arm ,并得到新的收益(payoffs): ,它的期望取决于user 和arm 两者
  • 3.算法接着使用新的observation 提升它的arm-selection策略。这里需要重点强调的是:对于未选中的arms ,此处没有观察到feedback(也就是:payoff

上述过程中,算法A的total T-trial payoff被定义成:。相似的,我们将它的最优期望定义为:,其中是在实验t中具有最大期望payoff的arm。我们的目标是:设计一个算法A以便total payoff期望最大化。也相当于:我们会发现一个算法,以便对应各最优的arm-selection策略的regret最小化。这里,T-trail regret 被定义为:

…(1)

一般的contextual bandit问题的一个重要特例是:著名的K-armed bandit,其中:

  • (i) arm set 保持不变,对于所有t都包含K个arms
  • (ii) user (或者相等的,context )对于所有t都相同

因此,在每个实验中的arm set和contexts两者都是常数,对于一个bandit算法来说没啥区别,因此我们可以将该类型的bandit称为是一个context-free bandit

在文章推荐的场景中(context),我们将池子中的文章(articles)看成是arms。当一篇曝光的文章被点击时,会带来一个等于1的payoff;否则payoff为0。有了关于payoff的该定义,一篇文章的期望(expected)payoff就是它的点击率(ctr),使用最大CTR来选择一篇文章等价于从最大化用户点击数目的期望,这与在我们的bandit公式中最大化总期望payoff(total expected payoff)相同。

再者,在网络服务中,我们通常会访问用户信息,它们被用于推断一个用户的兴趣,并用来选择他可能感兴趣的新闻文章。例如,对于一个男青年来说,他很可能对iPod产品的文章感兴趣,而非对退休计划的文章感兴趣。因此,我们会通过一个可以密切描述它们的关于信息特征的集合来“总结(summarize)”用户(users)和文章(articles)。通过这样做,一个bandit算法可以从一个 文章/用户 泛化(generalize) CTR信息给另一个文章/用户,并能学到更快地选择好的文章,特别是对于新用户和新文章。

2.2 已存在的Bandit算法

bandit problems的基本挑战是,需要对exploration和exploitation做平衡。为了最小化等式(1)中的regret(越小表示两者越接近),一个算法A会利用(exploits)它的过往经验来选择看起来最好的arm。另一方面,看起来最优的arm可能在实际上是次优的,因为在算法A的知识(knowledge)中是不精准的(imprecision)。为了避免这种不希望的情况,算法A必须通过实际选择看起来次优的arms来进行explore,以便收集关于它们的更多信息(在bandit过程中的step 3在之前的章节已定义)。Exploration可以增加short-term regret,因为会选到一些次优的arms。然而,获得关于arms的平均payoffs信息(例如:exploration)可以重新定义(refine)算法A的arms payoffs,从而减小long-term regret。通常,即不会存在一个纯粹的exploring,也不会存在一个纯粹的exploiting算法,需要对两者做平衡。

context-free K-armed bandit问题已经被统计学家研究过许多。一种最简单和最直接的算法是ε-greedy。在每个实验t中,该算法会首先估计每个arm a的平均payoff 。接着使用概率来选择greedy arm(例如:具有最高payoff估计的arm);使用概率e来选择一个random arm。在极限上,每个arm会尝试无限次,以便payoff估计会收敛到具有概率为1的真值(true value)。另外,通过对e进行适当的衰减(decaying),每一step的regret 会收敛到0, 概率为1.

对比于ε-greedy所采用的无向导(unguided)的exploration策略,另一类算法通常被称为UCB算法(upper confidence bound算法),它使用一个更聪明的方式来对E&E进行平衡。特别的,在实验t中,这些算法会同时估计:每个arm a的平均payoff 、以及一个相应的置信区间,以便具有较高的概率。它们接着选接arm来达到一个最高的上限置信边界(UCB)。由于合理地定义了置信区间,这样的算法具有一个较小的total T-trail regret,它是trials T的总数的log倍,看起来是最优的。

而context-free K-armed bandits最近被广泛研究,最通用的contextual bandit问题仍然充满挑战。EXP4算法[8]使用指数加权技术来达到一个的regret,但计算复杂度是特征数的指数倍。另一个常用的contextual bandit算法是epoch-greedy算法[18],它与使用shrinking ε的ε-greedy相似。该算法计算更高效,给定一个oracle optimizer,但具有更弱的regret guarantee:

具有更强regret guarantees的算法可以在关于bandit的许多建模假设下被设计。假设一个arm的期望payoff在它的特征中是线性的,Auer[6]描述了LinRel算法,它本质上是一种UCB-type方法,并展示了它的变种之一具有一个regret:,比其它算法有极大提升。

最终,我们注意到,存在另一种基于Bayes rule的bandit算法,比如:Gittins index方法。由于合理定义了先验分布,Bayesian方法具有良好的效果。这些方法需要大量离线工程来获得较好的先验模型.

3.算法

对于context-free bandit算法,给定了渐定最优性(asymptotic optimality)以及较强的regret bound UCB方法;我们可以为contextual bandit问题尝试设计相似的算法。给定关于payoff函数的参数形式,存在许多方法来从数据中估计参数的置信区间,从而我们可以计算估计后的arm payoff的一个UCB。然而,通常这样的方法代价高

在该工作中,我们展示了:当payoff模型是线性时,一个置信区间可以以closed form的形式高效计算,我们称该算法为LinUCB。出于表述(exposition)的需要,我们首先描述了disjoint线性模型的更简单形式,接着将在3.2节中考虑hybird模型的一般形式。我们注意到:LinUCB是一个通用的contextual bandit算法,它可以应用到其它应用中,而非个性化新闻推荐上

3.1 不相交(disjoint)线性模型的LinUCB

使用2.1节的概念,我们假设:一个arm a的期望payoff在d维特征上是线性的,它具有一些未知系数向量(coefficient vector);对于所有t:

…(2)

该模型称为disjoint的原因是:不同arms间的参数不共享(每个arm各有一组权重,与d维特征存在加权关系得到期望payoff)。假设:

  • 是在实验t上的一个m x d维的设计矩阵(design matrix),它的行对应于m个训练输入(例如:对于文章a,之前已经观察到的m个contexts)
  • 是相应的响应向量(corresponding response vector) (例如:相应的m个 点击/未点击 user feedback) (注:paper写的是而非,应该是笔误)

我们将岭回归(ridge regression)应用到训练数据上,给定了系数的一个估计(即伪逆):

…(3)

其中:是d x d的identity matrix。当在中的元素(components)与中相应行是条件独立时,它至少具有的概率:

…(4)

对于任意的以及其中是一个常数。换句话说,上述不等式为arm a的期望payoff给出了一个合理的紧凑的UCB,从中生成一个UCB-type arm-selection策略,在每个实验t上,选择:

…(5)

其中:

在等式(4)中的置信区间可以受其它准则的启发。例如, ridge regression可以被解释成一个Bayesian点估计,其中系数向量的后验分布被表示成:,它是一个关于(mean=)的高斯分布。给定当前模型,期望payoff 的预测变量被评估成,接着变为标准差。接着,在信息论中,的微分熵被定义成:。当的熵由new point 的杂质(inclusion)更新时,接着变为:。模型后验的熵减(entropy reduction)是。该质量(quatity)通常被用于估计来自的模型提升。因此,在等式(5)中的arm selection的准则可以被认为是在payoff估计和model uncertianty reduction间的一个额外的trade-off。

算法1

算法1给出了一个关于整个LinUCB算法的详细描述。只有输入参数。注意,在等式(4)中给定的值在一些应用中会比较大,因此对这些参数最优化实际可能会产生更高的total payoffs。不同于所有的UCB方法,LinUCB总是会选择具有最高UCB的arm(正如等式(5)中).

该算法具有一些良好的性质。

  • 1.它的计算复杂度对于arms的数量来说是线性的,对于特征数目最多是三次方。为了减少计算量,我们可以在每一step中更新,周期性计算和缓存,而非实时。
  • 2.该算法对于一个动态的arm set来说工作良好,仍能高效运行,只要的size不能太大。该case在许多应用中是true的。例如,在新闻文章推荐中,编辑会从一个池子中添加/移除文章,池子的size本质上是个常数。
  • 3.尽管不会该paper的重点,我们仍会采用[6]的分析来展示:如果arm set 是确定的,包含了K个arms,接着置信区间(比如:等式(4)的右手边)会随着越来越多的数据快速减小,接着证明的强regret bound,匹配满足等式(2)的bandits的state-of-art结果[6]。这些理论结果预示着算法的基础牢固以及高效性。

最后,我们注意到,在该假设下,输入特征会从一个正态分布中i.i.d的方式抽出,Pavlidis[22]提出了一个相似的算法,它使用一个最小二乘解来替代我们的ridge-regression解 (等式(3)中的)来计算UCB。然而,我们的方法更通用,当输入特征不稳定时仍合量(valid)。更重要的是,我们在下一节中讨论了,如何将算法1展开到一个更有意思的case。

3.2 Hybrid线性模型的LinUCB

算法1计算了矩阵的逆,(或者:),其中是design matrix,它的行对应于训练数据中的特征。所有arms的这些矩阵具有固定维度d x d,可以高效地进行增量更新。另外,它们的逆( inverses)可以通过算法1的disjoint参数很方便地进行计算:在等式(3)中的解不会被其它arms的数据数据所影响,因为计算是独立的。我们现在考虑使用hybrid模型的case。

在许多应用中(包含新闻推荐),除了arm-specific情况之外,所有arms都会使用共享特征。例如,在新闻文章推荐中,一个用户可能只偏爱于政治文章,因而可以提供这样的一种机制。因此,同时具有共享和非共享components的特征非常有用。正式的,我们采用如下的hybrid模型来额外添加其它的线性项到等式(2)的右侧:

…(6)

其中:

  • 是当前user/article组合的特征
  • 是一个未知的系数向量(coefficient vector),它对所有arms是共享的

该模型是hybrid的,广义上系数的一些参数是会被所有arms共享的,而其它则不会。

算法2

对于hybrid模型,我们不再使用算法1作为多个不相互独立的arms的置信区间,因为它们共享特征。幸运的是,有一种高效方式来计算一个UCB,与之前章节相似。该导数(derivation)严重依赖于块矩阵转置技术。由于空间限制,我们给出了算法2的伪码(第5行和第12行会计算关于系数的redge-regression的解,第13行会计算置信区间),详细导数见完整paper。这里我们只指出了重要的事实:

  • 1.由于算法中使用的构建块()具有固定的维度,可以进行增量更新,该算法计算十分高效。
  • 2.另外,与arms相关联的质量(quatities)在中并不存在,因而在计算量上不再相关。
  • 3.最后,我们也周期性地计算和缓存了逆(),而非在每个实验尾部来将每个实验的计算复杂度

4.评估技术

对比在一些标准监督机器学习setting,contextual bandit setting的评估是相当难的。我们的目标是评估一个bandit算法的效果,也就是说,在每个time step上选择一个arm的规则会基于之前的交互来完成(比如:上述算法描述的)。由于该问题的天然相交特性,看起来只能在真实数据上运行该算法。然而,实际上,该方法可能不可行,因为严重的logistical挑战。更确切的说,我们只具有离线数据提供,它们使用一整个不同的日志策略(logging policy)在之前收集得到。由于payoffs只会被logging policy选中的arms所观察到,它们很可能通常与被评估的算法所选中的不同。该评估问题可以看成是在增强学习中“off-policy evaluation problem”的一个特例。

一种解决方案是:构建一个模拟器(simulator)来从日志数据中建模bandit过程,接着使用该simulator来估计。然而,modeling step会引入在simulator中的bias,使它很难满足这种simulator-based评估方法的可靠性。作为对比,我们提出了一种方法:它很容易实现,基于日志数据,并且是无偏的(unbiased)。

在该节中,我们描述了一种被证明可靠的技术来执行这样的评估。假设,单独事件是i.i.d的,被用于收集日志数据的logging policy会在每个time step上随机均匀的方式选中任一arm。尽管我们会忽略细节,后面的假设会变弱,以便任何随机的logging policy会被允许,我们的解决方案可以根据使用rejection sampling来进行修改,但代价是降低了效果。

更精确的是,我们假设:一些已知分布D,从中进行i.i.d.抽取tuples:,每个tuple包含了已观察到的特征向量和对于所有arms的hidden payoffs。我们也可以访问关于日志事件的大序列,它从logging policy的交互产生。每个这样的事件包含了:context vectors:、一个被选中的arm a、以及产生的observed payoff 。关键的,只有payoff 被随机均匀选中的单个arm a所观察到。出于简洁性,我们将日志事件序列看成是一个无限长的流;然而,我们也在实际有限数目的事件(评估方法所需)上给出了显式的边界。

我们的目标是:使用该数据来评估一个bandit算法。正式的,是一个mapping(可能随机化)来在时间t上基于历史行为和t-1个之前的事件,结合上当前的context vectors 来选择arm

算法3

我们提出的policy评估器如算法3所示。该方法会将输入一个policy 以及一个基于该评估之上的关于“good”事件(event)T的期望值。我们接着沿着日志事件的流(stream)一个接一个地前行。给定当前历史,有:

  • 如果policy 选择了与logging policy所选arm的相同的arm a,那么:event仍被添加到历史中,total payoff 会被更新。
  • 如果policy 选择了与logging policy所选arm所不同的arm,那么:event会被完全忽略,该算法会处理下一event,在该state上无需任何变化。

注意,由于logging policy会随机均匀地选择每个arm,被该算法所维持(retain)的每个event会具有1/K的概率,相互独立。这意味着这些events仍保留与被D选中的相同的分布。作为结果,我们可以证明两种方式是相等价的:第一种采用来自D的T个真实events对policy进行评估,第二种会在日志事件流上使用policy evaluator进行评估

定理1: 对于contexts的所有分布D、所有policies 、所有T、以及所有事件序列,有:

其中S是从一个均匀随机的logging policy和D中i.i.d.的方式抽取出的一个事件流。另外,从流中获得的事件的期望数目(会收集到一个长度为T的历史)是KT。

该定理说明,每一个在真实世界中的历史与在policy evaluator中具有相同的概率(比如:返回由算法3的平均payoff ),即:算法的值无偏估计。另外,该定理表明:KT个日志事件对于维持一个size=T的抽样来说是必需的。

证明:该证明通过引入,以一个t=0时在所有评估方法下概率为1的空历史作为base case开始。在归纳法下,假设我们对于所有t-1:

并希望证明对于任意历史都有相同的声明。由于该数据是i.i.d.的,任何在policy中的随机化(randomization)与世界中的随机化相互独立,我们只需要证明在基于历史条件,在第t个事件(event)上的分布与每个过程(process)相同。换句话说,我们必须展示:

由于该arm a在logging policy中被随机均匀选中,对于任意policy、任意history、任意features、以及任意arm,policy evaluator退出内循环的概率是相同的, 这意味着对于最近的event,它的概率为。相似的,由于该policy 在arms上的分布与基于history 和features 的条件是相互独立的,arm a的概率就是

最后,由于来自该stream的每个event仍会保持概率1/K,需要保持T个event的期望数值是KT。

5.实验

在本节中,我们在一个真实应用中使用第4节中的offline评估法来验证提出的LinUCB的能力(capacity)。我们在Yahoo! Today模块上开始该问题setting的介绍,接着描述在实验中所使用的user/item属性。最终,我们定义了performance metrics,并上报了与一些标准(contextual)bandit算法的实验比较结果。

5.1 Yahoo! Today模块

图1

Today模块是在Yahoo! Front Page(流量最大)的最显著位置的panel,详见图1. 在Today Module上缺省的”Featured” tab会对高质量文章(主要新闻)的1/4进行高亮(highlight), 而4篇文章通过一个小时级别更新的由人工编辑的文章池中进行选择。如图1所示,在底部存在4篇文章,索引为F1-F4. 每篇文章由一张小图和一个标题进行表示。其中之一会在story位置进行着重展示,它由一个大图、一个标题、一个简介、以及相关链接进行着重(featured)。缺省的,在F1的文章会在story位置强调。一个用户可以点击在story位置上的highlightd文章,如果她对文章感兴趣会读取更多的详情。event被看成是一次story click。为了吸引访问者的注意力,我们想根据个人的兴趣对提供的文章进行排序,对于每个visitor在story位置上highlight最有吸引力的文章。

5.2 实验设置

这部分会详细描述实验设置,包括:数据收集,特征构建,效果评估,算法比较。

5.2.1 数据收集

我们收集了在2009年五朋的一个随机bucket上的events。在该bucket上的用户会被随机选中,每个visiting view都有一定的概率。在该bucket中,文章会从池子中随机被选中来服务给用户。为了避免在footer位置处的曝光偏差(exposure bias),我们只关注在story位置处的F1文章的用户交互。每个用户交互event包含了三个部分:

  • (i) 提供给用户随机选中的文章
  • (ii) user/article信息
  • (iii) 在story位置处用户是否对该文章有点击

第4部分展示了这些随机events可以被用于依赖估计一个bandit算法的期望payoff。

在5月1号的随机bucket中有4700W的events。我们使用该天的events(称为:tuning data)来进行模型验以决定最优的参数来对比每个bandit算法。接着,我们使用调过的参数在一周的event-set(称为:evaluation data,从5月03-09号)上运行这些算法,它包含了3600w的events。

5.2.2 特征构建

我们现在描述user/article的特征构建。对于disjoint和hybrid模型分别有两个集合的特征,用于测试在第3节中LinUCB的两种形式,以验证我们的猜想:hybrid模型可以提升学习速率。

我们从原始user features开始,它们通过“support”被选中。一个feature的support指的是,用户具有该feature的比例。为了减少数据中的噪声,我们只选取了具有较高值support的features。特别的,当它的support至少为0.1时,我们才使用该feature。接着,每个user最初通过一个在1000个类别型特征(categorical components)上的原始特征向量(raw feature vector)进行表示,包含了:

  • (i) 人口属性信息(demographic information):性别(2个分类)、年龄(离散化成10个分段)
  • (ii)地理特征(geographic features):包含世界范围和美国的大约200个大都市;
  • (iii)行为类别(behavioral categories):大约1000个二分类别(binary categories),它们总结了用户在Yahoo!内的消费历史。

除了这些特征之外,不会使用其它信息来标识一个用户。

相似的,每篇文章通过一个原始的feature vector进行表示,它以相同的方式构建了100个类别型特征。这些特征包括:

  • (i) URL类别:数十个分类,从文章资源的URL中推断得到
  • (ii) editor类别:数十个主题,由人工编辑打标签总结得到

我们使用一个之前的过程[12]来将类别型user/article特征编码成二分类向量(binary vectors),接着将每个feature vector归一化成单位长度(unit length)。我们也会使用一个值为1的常数特征来增加每个feature vector。现在,每个article和user都可以分别表示成一个关于83个条目和1193个条目的特征向量。

为了进一步减小维度,以及捕获在这些原始特征中的非线性关系,我们会基于在2008年九月收集的随机曝光数据来执行关联分布。根据之前的降维方法[13],我们将用户特征投影到文章类目上,接着使用相似偏好将用户聚类成分组(groups)。更特别的:

  • 我们首先通过原始的user/article features,来使用LR来拟合一个关于点击率(click probability)的bilinear model,以便来近似用户u点击文章a的概率,其中是相应的feature vectors,W是由LR最优化得到的权重矩阵。
  • 通过计算,原始的user features接着被投影到一个induced space上。这里,用于user u,在的第i个元素可以被解释成:用户喜欢文章的第i个类别的度(degree)。在induced的 space中使用K-means算法将用户聚类成5个clusters。
  • 最终的user feature是一个6向量(six-vector):5个条目对应于在这5个clusters中的成员(使用一个Gaussian kernel计算,接着归一化以便他们总和一致),第6个是一个常数特征1.

在实验t中,每篇文章a具有一个独立的6维特征(包含一个常数特征1)。与一个user feature的外积(outer product)给出了6x6=36个特征,表示为,对应于等式(6)的共享特征,这样可以被用于在hybrid线性模型中。注意,特征包含了user-article交互信息,而只包含了用户信息。

这里,我们故意使用5个用户/文章分组(users group),在分段分析中具有代表性[13]。使用一个相对小的feature space的另一个原因是,在在线服务中,存储和检索大量user/article信息在实际上代价高。

5.3 算法比较

我们的实验中评估的算法有三组:

I.不使用特征的算法

这对应于context-free K-armed bandit算法,它们会忽略所有contexts(例如:user/article信息)

  • random: random policy总是会以等概率的方式从池子中选中候选文章之一。该算法无需参数,不会一直学习
  • ε-greedy:在第2.2节所述,它会估计每篇文章的CTR;接着,它会选择具有概率e的一篇随机文章,接着选择具有概率1-e的最高CTR估计的文章。该policy只有一个参数e。
  • ucb: 如2.2节所述,policy会估计每篇文章的CTR,也会估计它的置信区间,总是会选择具有最高UCB的文章。特别的,根据UCB1[7],我们会通过来计算一篇文章a的置信区间,其中是在实验t之前a被选中的次数,是一个参数
  • omniscient(无所不知的): 这样的一个policy会从后见之明(from hindsight)达到最好的经验型的context-free CTR。它首先会从日志事件(logged events)中计算每篇文章的经验CTR,当使用相同的logged events评估时,接着总是选择具有最高经验CTR的文章。该算法无需参数,不需要学习。

II.热启动(warm start)算法

个性化服务的一种中间步骤。它的思想是,在文章的整个流量上的context-free CTR提供一种offline估计的特定用户的调整。该offset会为新内容对CTR估计的实始化,也称为:“warm start”。我们在2008九月的随机流量数据上,使用特征重新训练了bilinear LR模型。选择原则接着变成context-free CTR估计与一个user-specific CTR adujstment的bilinear项的和。在训练中,CTR估计使用context-free ε-greedy,其中e=1.

  • ε-greedy(warm):
  • ucb(warm):

III.在线学习user-specific CTR的算法

参考

0.介绍

Yoon Kim在《Convolutional Neural Networks for Sentence Classification》介绍了使用CNN来做句子分类的任务。下面基于对该paper的理解,简单地做个介绍:

1.模型架构

图1. 对于一个语句,使用双通道的模型架构

$ x_i \in R^k $ 为句子中第i个词的k维词向量。句子长度为n(不足补齐: pad),表示成:

… (1)

其中:

$ \oplus $为串联操作符(concatenation operator)。 $ x_{i:i+j} $ 表示 $ x_i $至$ x_{i+j} $的串联。

卷积(convolution)操作符涉及到一个过滤器(filter): $ w \in R^{h \times k} $,它可以应用于一个含h个词的窗口,来生成一个新的特征。例如,可以由一个词窗口$ x_{i:i+h-1}$来生成一个特征$c_i$

…(2)

这里 $ b \in R^{n-h+1} $是一个bias项,f是一个非线性函数(例如:假设函数tangent)。将filter应用在每个可能的句子中的词窗口:$ {x_{1:h}, x_{2:h+1},…,x_{n-h+1:n}} $来生成一个特征图(feature map)

…(3)

其中$ c \in R^{n-h+1}$,我们接着在该feature map上应用一个max-over-time pooling操作,并采用最大值$ \hat{c} = max \{ c \} $作为该指定filter相应的特征。该思路用来捕获最重要的特征——对于每个feature map取最大值得到。该pooling scheme天然就可以处理不同的句子长度。

我们接着描述该过程,通过从一个filter上抽取一个feature。该模型使用多个filters(具有不同的窗口size)来获得多个feature。这些特征构成了倒数第二层(penultimate layer),并被传到一个fully connected softmax layer,它的输出为在label上的概率分布。

在另一个模型变种中,我们试验了具有两个词向量的通道(channels)——一个保持static throughout training,另一个通过backpropagation进行 fine-tuned。在多通道的架构上,如图1所示,每个filter被应用于多个channel。被添加的结果用来计算等式(2)式中的$c_i$。该模型和单个channel的架构相似。

2.1 Regularization

对于Regularization,我们在倒数处二层(penultimate layer)使用dropout,使用一个关于权重向量的l2-norm的约束(constraint)。通过进行随机dropout, Dropout可以阻止隐单元的相互适应现象(co-adaptation)——这样,在前向传播(forward-backpropagation)期间将比例为p的隐单元置为0. 也就是说,给定倒数第二层(penultimate layer):$ z = [\hat{c}_1, …, \hat{c}_m] $(注意:这里有m个filter),做为替换,不再使用:

…(4)

对于在前向传播(forward propagation)中的输出单元y,dropout使用:

…(5)

其中$ \circ $是element-wise乘法操作,$ r \in R^{m}$是一个关于Bernoulli随机变量的’masking’向量,它具有概率p的部分为1。梯度通过后向传播,只通过unmasked的单元。在测试时,学到的weight向量通过p进行归一化,例如:$ \hat{w} = pw $,其中$ \hat{w} $被用来(没有dropout)对未见过的句子(unseen sentences)进行打分。我们又额外增加权重向量的l2-norms约束,通过对w进行rescaling,使得:$ {||w ||}_{2}$,在经历一个梯度下降的step后,将永远$ {||w ||}_2 > s $。

数据集

  • MR: 电影评论(Movie Reviews)。分类检测正负语义。(Pang and Lee, 2005)
  • SST-1: Stanford Sentiment Treebank——MR的扩展,具有train/dev/test splits,提供了细粒度标签(very positive, positive, neutral, negative, very negative)。 Socher et al. (2013)
  • SST-2: 类似SST-1. 移除了neutral评论,增加了binary labels
  • Subj:Subjectivity数据集,分类任务:将句子分类成:subjective or objective。(Pang and Lee, 2004).
  • TREC: TREC question数据集——将一个question分类成6个问题类型(该问题是关于:person, location, numeric information, etc.) (Li and Roth, 2002)
  • CR: 多种商品的顾客评价(Customer reviews)。预测positive/negative 评论。(Hu and Liu, 2004).
  • MPQA:MPQA数据集的意见极性检测(Opinion polarity detection)。 (Wiebe et al., 2005).

3.1 超参数和训练

对于所有数据集,统一使用:

  • ReLU
  • filter window(h)为:3, 4, 5
  • 每个window具有100个feature map
  • dropout rate (p)为:0.5
  • l2 constraint (s)为:3
  • mini-batch size为:50

这些值的选择在 SST-2 dev set上通过grid search找到。

我们不执行任意的指定数据集的调整,而是在dev sets上做early-stopping。对于没有标签dev set的数据集,我们随机选对10%的训练数据作为dev set。训练过程通过在shuffled mini-batchs数据上,使用Adadelta update rule(Zeiler, 2012),以及SGD来完成。

3.2 Pre-trained词向量

从非监督神经语言模型中获取词向量进行初始化,这种方法很流行。我们使用word2vec对Google News的1000亿个词进行训练。这些向量具有300维,使用CBOW架构,不在pre-trained词向量中的词则随机初始化。

3.3 模型变种

  • CNN-rand: 作为baseline模型,所有的词都是随机初始化,接着在训练中进行修改。
  • CNN-static: 使用来自word2vec的pre-trained vector的model。所有的词(包括随机初始化的未登陆词)保持static,只有模型中的其它参数是通过学习得到。
  • CNN-non-static: 与上面的方法相似,但对于每个任务,pre-trained vectors都会进行微调(fine-tuned)。
  • CNN-multichannel: 模型具有两个词向量集合。每个向量集都看成是一个’channel’,每个filter都会作用于两个channel,但梯度的后向传播只通过其中一个channel进行。这里模型可以fine-tune一个向量集,让另一个保持static。两个channel都通过word2vec进行初始化

为了对上述变种vs.其它随机因子进行比较,我们消除了其它源的随机性——CV-fold任务,未登陆词向量的初始化,CNN参数的初始化——在每个数据集上对它们保持统一。

4.结果

表2: CNN模型vs.其它方法。其它方法详见paper解释.

结果如表2所示。baseline model是CNN-rand:全随机初始化词,表现并不理想。通过使用pre-trained vector,会获得效果的提升。使用CNN-static的效果很显著,比起其它更复杂的深度学习模型(使用pooling或parse tree等),结果也有得一拼。这些结果说明了pre-trained vector很好、很通用(‘universal’)的feature extractors,并且可以跨数据集使用。对pre-trained vector进行微调(finetuning),可以为每个任务获得更进一步的提升(CNN-non-static)。

4.1 Multichannel vs. Single Channel Model

我们原先以为multichannel架构会阻止overfitting的发生(通过确保学到的vector与原先的值偏离太远),会比single channel效果更好,尤其是在小数据集的情况下。然而,结果参半,需要更进一步对fine-tuning过程进行正则化(regularizing)。例如,对于no-static部分使用一个额外的channel,你可以保持一个single channel,并可以额外的维度,它们允许在训练过程中进行修改。

表3: top 4个邻近词——基于consine相似度——static channel(左列)中的向量,在SST-2数据集上,在训练后的multichannel模型中的non-static channel(右侧)中的finetuned vector。

4.2 static vs. Non-static表示

正如single channel non-static model的情况,multichannel模型能够对 non-static channel进行微调(fine-tune),来使要处理任务更具指定性。例如:good在word2vec中与bad最相似,推测起来是因为它们在句子结构(syntactically)上(大至)是相等的。但对于在SST-2数据集上进行微调的non-static channel中的词向量,不再有表3中的情况。相似的,在表示语义上,good与nice更接近(比起good与great),这的确可以反映在学到的向量中。

对于不在pre-trained vector中的token(随机初始化),进行fine-tuning可以使这些token学到更有意义的表示(representation):该网络可以学到:感叹号(exclamation marks)与感情表达有关,逗号与连接词有关。

4.3 进一步观察

  • Kalchbrenner et al. (2014),使用一个 CNN得到更糟的结果,本质上与single model的架构一致。例如,它们的Max-TDNN(Time Delay Neural Network)使用随机初始化的词,在SST-1上获得了37.4%,而我们的模型则为45.0%。我们将这种差异归因于:我们的CNN具有更大的容量(多个filter widths和feature maps)。
  • Dropout被证明是一种很好的regularizer, 它很容易使用一个更大的网络,只需dropout去进行regularize即可。Dropout可以增加2-4%的效果提升
  • 当随机初始化的词不在word2vec中时,通过从U[-a,a]中抽样每一维,可以获得微小的提升,其中选中的a,可以使随机初始化的向量具有与pre-trained vector具有相似的variance。在初始化过程,使用更复杂的方法来反映(mirror)pre-trained vectors的分布,来获得提升是挺吸引人的一件事。
  • 我们试验了另一个公共的词向量(由Collobert et al. (2011) on Wikipedia训练得到),发现word2vec可以获得更好的效果提升。这一点不是很清楚:是否是因为o Mikolov et al. (2013)的架构,还是因为google news 1000亿词的数据集的原因。

5.结论

本文描述了在word2vec上构建CNN的一些试验。只需很少的超参数的调参,一个简单的CNN具有一层的卷积层,就可以得到令人吃惊的效果。本文的结果也有效验证了在Deep NLP中pre-trained word vector相当重要。

参考

Convolutional Neural Networks for Sentence Classification

介绍

在解析XGBoost的源码之前,我们先理解下陈天奇在paper《XGBoost: A Scalable Tree Boosting System》一文中提到的一些概念。

XGBoost的可扩展性(scalability)归因于一些重要的系统优化和算法优化。这些优化包括:

  • 一种新的tree-learning算法(a novel tree learning algorithm):用于处理稀疏数据(sparse data)
  • 一种理论正确的加权分位数略图过程(a theoretically justified weighted quantile sketch procedure):用于处理在近似的tree-learning中实例权重

由于XGBoost的并行化和分布式计算,使得learning过程比其它模型实现要快。更重要地,XGBoost实现了核外计算(out-of-core computation: 基于外存),使得数据科学家们可以在pc机上处理上亿的训练实例。最终,会把这些技术结合起来实现一个end-to-end的系统,可以扩展到集群上。

主要内容:

  • 1.设计和建立了一个高度可扩展的end-to-end tree boosting系统
  • 2.提出了一种理论正确的加权分位数略图过程(theoretically justified weighted quantile sketch procedure),用于高效地进行预计算
  • 3.介绍了一种新的稀疏感知算法(sparsity-aware algorithm),用于并行化tree learning
  • 4.提出了一种高效的内存感知块结构(cache-aware block structure),用于核外(out-of-core)tree learning

2.tree-boosting回顾

XGBoost的方法源自于Friedman的二阶方法。XGBoost在正则化目标函数上做了最小的改进。

2.1 正则化目标函数

对于一个含n个训练样本,m个features的结定数据集:$ D = {(x_i,y_i)} (|D|=n, x_i \in R^m, y_i \in R) $,所使用的tree ensemble model使用K次求和函数来预测输出:

…… (1)

其中,$ F = {f(x)=w_{q(x)}},满足(q: R^m \rightarrow T, w \in R^T) $,是回归树(CART)的空间。q表示每棵树的结构,它会将一个训练样本实例映射到相对应的叶子索引上。T是树中的叶子数每个$ f_k $对应于一个独立的树结构q和叶子权重w。与决策树不同的是,每棵回归树包含了在每个叶子上的一个连续分值,我们使用$ w_i $来表示第i个叶子上的分值。对于一个给定样本实例,我们会使用树上的决策规则(由q给定)来将它分类到叶子上,并通过将相应叶子上的分值(由w给定)做求和,计算最终的预测值。为了在该模型中学到这些函数集合,我们会对下面的正则化目标函数做最小化:

……(2)

其中:$ \Omega(f) = \gamma T + \frac{1}{2}\lambda||\omega||^2 $

其中,$l$是一个可微凸loss函数(differentiable convex loss function),可以计算预测值$\hat{y_i}$与目标值$y_i$间的微分。第二项$ \Omega $会惩罚模型的复杂度。正则项可以对最终学到的权重进行平滑,避免overfitting。相类似的正则化技术也用在RGF模型(正则贪婪树)上。XGBoost的目标函数与相应的学习算法比RGF简单,更容易并行化。当正则参数设置为0时,目标函数就相当于传统的gradient tree boosting方法。

2.2 Gradient Tree Boosting

等式(2)中的tree ensemble模型将函数作为参数,不能使用在欧拉空间中的传统优化方法进行优化。模型以一种叠加的方式进行训练。正式地,$ \hat{y_i}^{(t)} $为第i个实例在第t次迭代时的预测,我们需要添加$ f_t $,然后最小化下面的目标函数:

这意味着,我们贪婪地添加$ f_t $,根据等式(2)尽可能地提升模型。使用二阶近似可以快速优化目标函数。

其中,$ g_i = \partial_{\hat{y}^{(t-1)}} l(y_i,\hat{y}^{(t-1)}) $ ,$ h_i = {\partial}_{\hat{y}^{(t-1)}}^{2} l(y_i, \hat{y}^{(t-1)}) $分别是loss function上的一阶梯度和二阶梯度。我们可以移除常数项,从而获得如下所示的在t次迭代时的简化版目标函数

……(3)

我们定义$ I_j= \{ i | q(x_i)=j \} $是叶子j的实例集合。将(3)式进行重写,并展开$ \Omega $项:

……(4)

对于一个确定的结构q(x),我们可以计算最优的权重 $ w_j^{\ast} $:

……(5)

代入(5)计算得到对应的loss最优解为:

……(6)

等式(6)可以作为一个得分函数(scoring function)来衡量一棵树结构q的质量(quality)。该分值类似于决策树里的不纯度(impurity score),只不过它从一个更宽范围的目标函数求导得到。图2展示了该分值是如何被计算的。

图2:结构得分(structure score)计算。我们只需要在每个叶子上对梯度和二阶梯度统计求和,然后应用得分公式(scoring formula)来获得质量分(quality score)。

通常,不可能枚举所有可能的树结构q。而贪婪算法会从单个叶子出发,迭代添加分枝到树中。假设$ I_L $和$ I_R $是一次划分(split)后的左节点和右节点所对应的实例集合。$ I=I_L \bigcup I_R $,接着,在split之后的loss reduction为:

……(7)

该式通常在实际中用于评估split的候选(split candidates)。

2.3 Shrinkage和列子抽样(column subsampling)

除了2.1节所提到的正则化目标函数外,还会使用两种额外的技术来进一步阻止overfitting。第一种技术是Friedman介绍的Shrinkage。Shrinkage会在每一步tree boosting时,会将新加入的weights通过一个因子$ \eta $进行缩放。与随机优化中的learning rate相类似,对于用于提升模型的新增树(future trees),shrinkage可以减少每棵单独的树、以及叶子空间(leaves space)的影响。第二个技术是列特征子抽样(column feature subsampling)。该技术也会在RandomForest中使用,在商业软件TreeNet中的gradient boosting也有实现,但开源包中没实现。根据用户的反馈,比起传统的行子抽样(row sub-sampling:同样也支持),使用列子抽样可以阻止overfitting。列子抽样的使用可以加速并行算法的计算(后面会描述)。

3.Split Finding算法

3.1 Basic Exact Greedy Algorithm

tree learning的其中一个关键问题是,找到等式(7)的最好划分(best split)。为了达到这个目标,split finding算法会在所有特征(features)上,枚举所有可能的划分(splits)。我们称它为“完全贪婪算法(exact greedy algorithm)”。许多单机版tree-boosting实现中,包括scikit-learn,R’s gbm以及单机版的XGBoost,都支持完全贪婪算法(exact greedy algorithm)。该算法如算法1所示。它会对连续型特征(continuous features)枚举所有可能的split。为了更高效,该算法必须首先根据特征值对数据进行排序,以有序的方式访问数据来枚举等式(7)中的结构得分(structure score)的梯度统计(gradient statistics)。

[算法1]

3.2 近似算法

完全贪婪算法(exact greedy algorithm)很强大,因为它会贪婪地枚举所有可能的划分点。然而,当数据不能整个装载到内存中时,它就变得低效。在分布式设置中也存在相同的问题。为了在两种设置中支持高效地gradient tree boosting计算,需要一种近似算法。

我们总结了一个近似框架(approximate framework),重组了在文献[17,2,22]中提出的思想,如算法2所示。为了进行总结(summarize),该算法会首先根据特征分布的百分位数(percentiles of feature distribution),提出候选划分点(candidate splitting points)。接着,该算法将连续型特征映射到由这些候选点划分的分桶(buckets)中,聚合统计信息,基于该聚合统计找到在建议(proposal)间的最优解

[算法2]

该算法有两个变种,取决于给定的建议(proposal)。全局变种(global variant)会在树构建的初始阶段,建议所有的候选划分,并在所有的层级(level)上使用相同的建议。局部变种(local variant)则在每次划分后重新建议(re-proposes)。比起局部法,全局法需要更少的建议步骤。然而,对于全局建议,通常需要更多的候选点,因为在每次划分之后,不需要重新定义候选。局部建议会在每次划分后重新定义候选,对于更深的树更合适。图3展示了在Higgs boson数据集上不同算法的比较。我们发现,局部建议确实需要更少的候选。如果两者的候选一样多,全局建议比局部建议会更精确。

图3: 在Higgs 10M数据集上的Test AUC收敛比较. eps参数对应于在近似略图(approximate sketch)上的accuracy。这大约可以在proposal中转换成1/eps buckets。我们发现local proposals需要更少的buckets,因为它会重新定义划分候选(split candidates)

大多数分布式tree learning近似算法都遵循该框架。显著的,也可以直接构建近似的梯度统计直方图(approximate histograms of gradient statistics)。也可以使用二分策略(binning strategies)来替代分位数(quantile)。分位数策略(quantile strategy)可以从分布式(distributable)和重计算(recomputable)中受益,详见下一节。从图3中可知,我们发现:给定合理的近似级别(approximation level),分位数策略(quantile strategy)可以获得与exact greedy算法相同的准确率。

对于单机设置,我们的系统高效地支持exact greedy;对于单机和分布式设置,也同时支持带local和global proposal方法的近似算法。用户可以根据需要自由选择。

3.3 加权分位数略图(Weighted Quantile Sketch)

在近似算法中很重要的一步是,提出候选划分点。通常,一个特征的百分位数可以被用来让候选在数据上进行均匀地分布。我们用一个multi-set: $ D_k={(x_{1k}, h_1),(x_{2k},h_2),…(x_{nk},h_n)} $,来表示每个训练实例的第k个特征值以及它的二阶梯度统计。我们可以定义一个排序函数(rank functions):$ r_k=R \rightarrow [0,+\infty) $:

……(8)

它表示相应第k个特征上的输入值小于z的实例的占比。它的目标是,找好候选划分点 $ {s_{k1}, s_{k2}, …, s_{kl}} $,例如:

……(9)

其中$ \epsilon $是近似因子(approximation factor)。直觉上,这意味着大约是 $ \frac{1}{\epsilon} $个候选点。这里,每个数据点通过$h_i$加权。为什么$h_i$可以表示权重呢?我们可以重写(3)式:

它就是真正的加权squared loss,labels为$g_i/h_i $,权重为$h_i$。对于大数据集来说,要找到满足该原则(criteria)的候选集是不容易的。当每个样本实例都具有相同的权重时,有一种已经存在的算法可以解决该问题:分位数略图(quantile sketch)。因而,大多数已存在的近似算法,或者会重新排序来对数据的一个随机子集进行排序(有一定的失败率),或者是启发式的(heuristics),没有理论保障。

为了解决该问题,XGBoost引入了一种新的分布式加权分位数略图算法(distributed weighted quantile sketch algorithm),使用一种可推导证明的有理论保证的方式,来处理加权数据。总的思想是,提出了一个数据结构,它支持merge和prune操作,每个操作证明是可维持在一个固定的准确度级别。算法的详细描述在这里

3.4 稀疏感知的划分查找(sparsity-aware Split Finding)

在许多现实问题中,输入x是稀疏的。有多种可能的情况造成稀疏:

  • 1)数据中的missing values
  • 2)统计中常见的零条目
  • 3)特征工程:比如one-hot encoding

图4: 带缺省方向的树结构。当在split时相应的feature缺失时,一个样本可以被归类到缺省方向上

让算法意识到数据中的稀疏模式很重要。为了这么做,我们提出了在每个树节点上增加一个缺省的方向(default direction),如图4所示。当稀疏矩阵x中的值缺失时,样本实例被归类到缺省方向上。在每个分枝上,缺省方向有两种选择。最优的缺省方向可以从数据中学到。如算法3所示。关键的改进点是:只访问非缺失的条目$I_k$。上述算法会将未出现值(non-presence)当成是一个missing value,学到最好的方向来处理missing values。当未出现值对应于一个用户指定值时,应用相同的算法,可以通过将枚举(enumeration)限定到一致的解上。

[算法3]

据我们所知,大多数已存在的tree learning算法,或者只对dense data进行优化,或者需要指定函数来处理受限的情况:比如对类别编码(categorical encoding)。XGBoost以统一的方式处理稀疏模式。更重要的是,我们的方法充分使用稀疏性,它的计算复杂度与在输入中的未缺失条目(non-missing entries)的数目成线性关系。图5展示了在Allstate-10K数据集上稀疏感知和naive实现间的比较。我们发现,稀疏感知算法比naive版本要快50倍。这证实了稀疏感知算法的重要性。

图5: 稀疏感知算法(sparsity aware algorithm)在Allstate-10K上的影响。数据集很稀疏,主要因为one-hot编码。稀疏感知算法比naive版本(不会考虑稀疏性)要快50倍。

4.系统设计

4.1 用于并行学习的Column Block

tree learning最耗时的部分,是以有序方式获得数据。为了减少排序的开销,我们提出了将数据存储到内存单元(in-memory units)中,它们被称为“块(block)”。每个块中的数据,以压缩列(CSC)格式存储。每列由相应的特征值进行排序。输入数据的布局,在训练前只需要计算一次,在后续迭代中可复用。

在exact greedy algorithm中,我们将整个数据集存储到单个块中,通过对预排序的条目进行线性扫描的方式,来运行split search算法。我们会对所有叶子共同进行split finding算法,因而,在块上的一次扫描,将收集到在所有叶分枝上的划分候选的统计信息。图6展示了,我们如何将一个数据集转成该格式,并找到使用该块结构的最优划分(optimal split)。

图6: 用于并行学习的块结构。块中的每个列通过相应的特征值(feature value)进行排序。在块中的某列上进行一次线性扫描,足够枚举所有的划分点

当使用近似算法时,块结构也有用。这种情况下,可以使用多个块,每个块对应于数据集中行的子集。不同的块可以跨机器分布,或者以out-of-core设置的方式存储在磁盘中。使用排序过的结构,quantile finding步骤会在排好序的列上进行一次线性扫描(linear scan)。这对于局部建议算法(local proposal algorithms)特别有用,局部法的候选集通常在每次划分时生成。在直方图聚合(histogram aggregation)上进行二分查找,也变为一个线性时间的merge style算法。

为每列收集统计信息可以并行化,给定一个并行化算法来处理split finding。更重要的是,列块(column block)结构也支持列子抽样(column subsampling),它可以很容易地在一个块中选择列的一个子集

时间复杂度分析

d为树的最大深度,K为树的总树目。对于exact greedy algorithm,原始的稀疏感知算法的时间复杂度:

这里,我们使用 来表示在训练数据中未缺失条目(non-missing entries)的数目。另一方面,块结构上的tree boosting的开销为:

这里, 是一次预处理开销(one time preprocessing cost),可以分期(be amortized)。该分析展示了块结构可以帮助节省一个额外的$ log n $因子,其中当n非常大时就很大。对于近似算法,使用二分查找的原始算法时间复杂度为:

这里的q是在数据集中建议候选的数目。其中,q通常为32~100之间,log因子仍会引入间接开销。使用块结构,我们可以将时间减小到:

其中B是在每个块中的行的最大数。同样的,我们可以在计算中节约额外的log q因子。

4.2 内存感知访问(Cache-aware Access)

建议的块结构(the proposed block structure)可以帮助优化split finding的计算复杂度,新算法需要通过行索引(row index)间接取得梯度统计(gradient statistics),因为这些值是以特征的顺序被访问的。这是非连续内存访问(non-continuous memory)操作。枚举划分(split enumeration)的naive实现,在累加(accumulation)与非连续内存读取操作(non-continuous memory fetch)间(详见图8),引入了立即读写依存(immediate read/write dependency)。当梯度统计(gradient statistics)不能装载进CPU cache里,或者cache miss发生时,会减慢split finding。

图8: 短范围内的数据依赖模式,由于cache miss,可引起停转(stall)

对于exact greedy algorithm,我们通过内存感知预取(cache-aware prefetching)算法来减缓该问题。特别的,我们在每个thread上分配一个internal buffer,获取gradient statistics存到该buffer中,接着以一种mini-batch的方式来执行累计(accumulation)。这种预取法将直接读/写依存,改变成一种更长的依存,当行的数目很大时可以帮助减少运行时开销。图7给出了在Higgs数据集和Allstate数据集上cache-aware vs. no cache-aware 的比较。当数据集很大时,我们发现exact greedy algorithm的cache-aware实现比naive版本的实现要快两倍。

图7: 在exact greedy algorithm中,cache-aware prefetching的影响。我们发现,cache-miss会在大数据集(1000w实例)上影响性能。使用cache-aware prefetching,可以提升数据集很大时的性能。

对于近似算法,我们通过选择一个合适的块大小(correct block size)来解决该问题。我们将块大小(block size)定义为在一个块中包含样本的最大数目,它会影响梯度统计的cache存储开销(cache storage cost)。选择一个过小的block size会导致每个thread会小负载(small workload)运行,并引起低效的并行化(inefficient parallelization)。在另一方面,过大的block size会导致cache miss,梯度统计将不能装载到CPU cache中。block size的好的选择会平衡两者。我们比较了在两个数据集上的block size的选择。结果如图9所示。结果展示选择在每个块上有$ 2^{16} $个样本时,会对cache property和parallelization做很好的平衡

图9: 在近似算法中,block size的影响。我们发现,过小的块会引起并行化很低效,过大的块由于cache miss会让训练慢下来

4.3 Out-of-core计算

XGBoost的其中一个目标是,充分利用机器资源来达到可扩展的learning(scalable learning)。除了处理器和内存外,很重要的一点是,使用磁盘空间来处理不能完全装载进主存的数据。为了达到out-of-core计算,我们将数据划分成多个块,将每个块存到磁盘上。然而,这不能整体解决该问题,因为磁盘读(disk reading)会花费大多计算时间。减小开销和增加磁盘IO吞吐量很重要。我们主要使用两种技术来提升out-of-core计算。

块压缩(Block Compression) 块通过列(column)进行压缩,当加载进主存时可以由一个独立的线程即时解压(decompressed on the fly)。它会使用磁盘读开销来获得一些解压时的计算。我们使用一个通用目的的压缩算法来计算特征值。对于行索引(row index),我们从块的起始索引处开始抽取行索引,使用一个16bit的整数来存储每个偏移(offset)。这需要每个块有$ 2^{16} $个训练样本,这证明是一个好的设置。在我们测试的大多数数据集中,我们达到大约26% ~ 29%的压缩率。

块分片(Block Sharding) 第二个技术是,在多个磁盘上以一种可选的方式共享数据。一个pre-fetcher thread被分配到每个磁盘上,取到数据,并装载进一个in-memory buffer中。训练线程(training thread)接着从每个bufer中选择性读取数据。当提供多个磁盘时,这可以帮助增加磁盘读(disk reading)的吞吐量。

表1: 主要的tree boosting实现比较

参考

XGBoost: A Scalable Tree Boosting System

microsoft在《Position-Normalized Click Prediction in Search Advertising》对coec做了介绍。

1.介绍

竞价排名搜索广告的ctr预估系统的目标是:根据其它上下文知识(比如:用户信息),对一个query-ad pair估计CTR。ctr预估对于ad排序、位置分配(allcation),定价(pricing),以及回报(payoff)很关键。通过估计得到的CTR作为query-ad相关度的一种衡量,并且与其它非相关因子相互独立。然而实际上,有许多外围因子影响着基于相关度的ctr系统,通常会在观察到的点击数据(click-through data)上扮演着重要角色。一个经典的示例是:广告展现位置(ad presentation position)。这些外在因子必须小心处理,否则会导致一个次优的ctr预估,许多真实世界的系统都会存在这种缺陷。

我们提出了一个概率因子模型(probabilistic factor model)作为一个总的原则性方法来研究这些效应。该模型很简单并且是线性的,在广告领域会做出经验性的调整。对于纠正在搜索算法上的位置偏差(positional bias)有大量研究,许多研究都是:检测模型(examination model)[12],cascade model[5], 动态贝叶斯网络模型(DBN)[3],而对于搜索广告领域却很少。我们的方法采用了与examination model相似的因子分解假设,也就是说:在item上的点击概率,是一个关于位置先验概率和一个基于相关度的与位置无关的概率的乘积。再者,我们会专门研究广告领域的位置概念,通过合并其它广告特有的重要信号,例如:query-ad keyword match type和广告总数。

来自搜索算法的其它模型(比如:cascade和DBN模型),通常会假设:一个item的估计得到的ctr(estimated CTR)是与展示在搜索结果页的items的相关度(relevance)相互独立的。这些更复杂的假设对于搜索算法结果更合适,其中用户对于结果链接之一上的点击行为具有一个高概率。然而对于广告,在广告上的点击概率总是相当低,通常是一个百分比。因此,效果越高(非点击)的广告是相互接近的因子的乘积。

2.因子模型

假设:

  • i表示一个query-ad pair
  • j表示ad的位置
  • c表示点击次数
  • v表示曝光次数

观察到的CTR是一个条件概率 。对于在竞价搜索广告中的经验假设,我们做出如下简化:

  • 1.一个ad的点击是与它的位置相互独立的 (假设:位置可以物理上进行检查examining)。
  • 2.给定一个ad的位置,检查(examining)一个广告是与它的内容或相关度是相互独立的

正式的,位置依赖的CTR(position-dependent CTR)可以表示为:

…(1)

其中:

  • 第一个因子 :可以简单表示为,它是一个位置归一化的CTR(position-normalized CTR),可以表示ad的相关度
  • 第二个因子 ,可以简单表示为,体现了位置偏差( positional bias)。

有了该CTR因子分解(factorization),我们可以处理关于点击行为的两种自然随机模型,接着在部署模型上通过一个先验进行平滑。【1,9】

3. Binomial模型

很自然的,假设点击数遵循一个二项分布:

。。。

4.POISSON模型

如果尝试次数n足够大,成功概率p (success probability)足够小,那么。由于广告(ad)就是这样一个领域,我们可以导出Poisson模型,它会生成一个相似的且足够有效的更新。该生成模型是:

…(9)

5.GAMMA-POISSON模型

对于empirical和regularization的目的,我们在Poisson模型中在位置因子(positional factor)上引入了一个gamma先验:

…(16)

经验上,观察CTR(observed CTR)几何上会随位置的降低而递减【11】,展示出与gamma信号有一个很好的拟合。实例上,次一点的位置(inferior positions,比如:side bar的底部位置)可能会遭受严峻的数据稀疏性问题,尤其是点击;因此,正则化(regularizing)或平滑(smoothing)这些噪声估计会产生更好的泛化。gamma分布是一个常见的选择,因为它是Poisson的一个共轭先验。

。。。

6.点击模型

一个点击模型或CTR预测模型的目标是:为给定的一个query-ad pair,估计一个位置无偏CTR(positional-unbiased CTR),例如:相关度CTR(relevance CTR) 。上述描述的位置归一化点击模型(positional normalized click model)会做这样的处理,同时也会发生位置先验概率 。factor模型的另一个观点是:在ad位置上做过平滑的kNN模型;当特征空间只包含了query-ad pairs,k=1。对于有足够历史点击数据的query-ad pairs这是可信的,因子模型可以合理执行。而对于一个冷启动问题原则性处理方法是,将queries和ads的一元特征(unigram features)添加到特征空间中,当在预测时遇到新的pairs时对CTR预估做backing-off。

位置归一化点击模型也可以被独立应用,并联合其它点击模型来估计relevance-only CTR。更严厉的,我们会所设位置因子与其它相关度因子相互独立。在模型训练时,需要通过它的位置先验来归一化每个ad曝光。在预测时,CTR预测器会从位置归一化的训练数据中进行学习,并生成完全的relevance-only CTR。

7.实验

7.1 使用人造数据仿真

我们首先在一个通过概率模型(例如:给定一个sound模型)生成的人造数据集上仿造了Gamma-Poisson模型。通过仔细设计模型参数,人造数据可以十分模仿真实的搜索广告数据。尽管模仿数据不能完全反映真实系统,但它至少有两个优点:

  • 1.当从真实噪声中进行抽象时,允许快速研究大量参数
  • 2.通过该数据曝露的真实分布来验证学到的模型,对于真实数据很重要

数据生成如下:

    1. 位置 ,生成一个,以降序对q排序,通过对q进行缩放
  • 2.

参考

lightFM源自于paper: 《Metadata Embeddings for User and Item Cold-start》:

一、介绍

构建推荐系统能在冷启动场景中(新用户、新item)运行良好是个挑战。标准的MF模型在该setting中效果很差:很难有效估计user和item的隐因子,因为协同交互数据很稀疏。

基于内容的(CB)方法,可以通过使用item的metadata来解决该问题。因为这些信息是事先预知的,对于新item(没有协同数据可收集)的推荐依然可以计算。不幸的是,在CB模型中没有迁移学习出来:对于每个用户的建模是以孤立的方式估计得到的,并没有利用其它用户数据。因此,CB模型的执行会比MF模型要差。

最后,解决该问题很关键。我们是一家时尚公司,目标是为我们的用户提供便利的方法进行在线时尚品浏览、购买。为了这个目的,我们维护了一个非常大的商品目标:在写入时,我们会跨网络聚合超过800w的时尚items,并会每天添加上万新的商品。

为我们做出推荐有三个因子。首先,我们的系统包含了一个非常大的items数目。这使得我们的数据很稀疏。第二,我们如下进行处理:通常,最相关的items是那些新释放出的collections,允许我们只有一个短时间窗口来收集数据,并提供有效推荐。最后,我们的用户大比例是首次访问的用户(first-time visitors):我们希望为他们推荐引人注目的推荐,即使只有少量数据。用户和item的冷启动组合,使得纯粹的协同和CB方法不适用。

为了解决该问题,我们使用一个混合content-collaborative模型,称为LightFM,归因于它会对FM进行resemblance。在LightFM中,就像在一个协同过滤模型中一样,users和items被表示成隐向量(embeddings)。然而,正如在一个CB模型一样,这些都通过描述每个商品或用户的内容特征(content features)的函数进行定义。例如,如果该电影“绿野仙踪(Wizard of Oz)”通过以下的features描述:”音乐幻想剧(musical fantasy)”、“朱迪·加兰(Judy Garland)”、以及“Wizard of Oz”,那么它的隐表示可以通过对这些features的隐表示进行求和得到。

通过这么做,LightFM可以将CB和CF的推荐的优点进行联合。在该paper中,我们会对该模型公式化,并在两个数据集上进行实验,展示:

  • 1.在冷启动和低密度场景,LightFM至少与纯CB模型一样好,实质上,当满足以下二者之一(1)在训练集中提供了协同信息 (2) 在模型中包含了用户特征 时,效果要更好。
  • 2.当协同数据很丰富时(warm-start, dense user-item matrix),LightFM至少与MF模型效果一样好。
  • 3.通过LightFM生成的Embeddings,可以编码关于features的重要语义信息,可以被用于相关推荐任务:比如:标签推荐。

这对于真实推荐系统来说有许多好处。因为LightFM在dense和sparse数据上均表现良好,它不需要为每种setting构建和维护多个特定机器学习模型。另外,它可以同时使用user和item的metadata,它可以应用于user和item的冷启动场景。

LightFM python版的Github地址为:https://github.com/lyst/lightfm.

2.LightFM

2.1 动机

LightFM模型的结构受以下两种考虑的启发:

  • 1.该模型必须能从交互数据中学习user和item表示:如果描述为“舞会袍(ball gown)”和”铅笔裙(pencil skirt)”的items均被用户所喜欢,该模型必须能学到ball gowns与pencil skirts相似。
  • 2.该模型必须能为新items和users计算推荐

第1点通过使用隐表示方法来解决。如果ball gowns和pencil skirts均被相同的用户所喜欢,它们的embeddings会更接近;如果ball gowns和机车夹克(biker jackets)不会被相同的用户所喜欢,它们的embeddings会更远。

这样的表示允许迁移学习出现。如果对于ball gowns和pencil skirts的表示很相近,我们可以自信地推荐ball gowns给一个刚与pencil skirts交互过的新用户。

在纯CB模型之上使用降维技术(比如:LSI)也可以达到该目换,因为它们只会编码由feature co-occurrence给定的信息,而非用户动作。例如,假设所有浏览过由“飞行员(aviators)”描述的items的用户,同时也浏览了由“旅行者(wayfarer)”描述的items,但这两个features从未在相同的item中同时描述过。这种情况下,对于wayfarers的LSI vector不会与aviators的相似,即使协同信息建议应该这样做。

第2点通过将items和users表示成它们的content features的线性组合。由于content features被认为是:当一个user或一个item进入该系统时,它允许直接做出推荐。这种结构很容易理解。“牛仔夹克(denim jacket)”的表示看成是denim的表示和jacket的表示的求和(sum);一个来自美国的女性用户(a female user from the US)的表示是US的表示和female users的表示的求和。

2.2 模型

为了公式化描述该模型,假设U是用户集,I是items集合,是user features的集合,是item features的集合。每个用户与多个items交互,正向或者负向。所有user-item交叉pair 是正交互和负交互的联合。

Users和items通过它们的features进行完全描述。每个user u通过一个特征集合描述 。为每个item i它们的特征为。features是提前知道的,可以表示user和item的metadata。

该模型通过d维的user和item的feature embeddings 为每个feature f进行参数化。每个feature也可以通过一个标量bias项(对于user features是,对于item features则是)描述。

user u的隐表示,通过对它的features的隐向量进行求和来表示:

item i的隐表示类似,如下:

user u的bias项,通过对features的biases进行求和得到:

item i的bias项如下:

该模型对于user u 和 item i的预测,接着通过user向量和item向量的点乘,加上对应的偏置给出:

…(1)

有许多函数适合。一个identity函数也能对预测评分很好地运行;在本paper中,我们只对二分类数据预测感兴趣,因而选择sigmoid:

模型的最优化目标是,最大化在该参数上的条件似然。该似然如下:

…(2)

使用ASGD进行训练。4线程。learning rate使用ADAGRAD。

2.3 与其它模型关系

LightFM与协同MF模型间的关系,由user和item的feature sets的结构决定。如果feature sets只包含了每个user和item的指示变量,LightFM相当于MF模型。如果feature sets也包含了metadata features,它们被至少一个item或user所共享,那么LightFM就扩展了MF模型:通过让feature的隐因子来解释用户交互的部分结构。

这在三方面很重要。

  • 1.在大多数应用中,metadata features要比users或items还要少,因为使用一个确定类型/类目的结构,或者因为维护一个固定size的关于最常用项的字典,当使用原始文本特征时。这意味着,从受限的训练数据中,需要估计更少的参数,减小overfitting机率并提升泛化效果。
  • 2.指示变量的隐向量不能为新的、冷启动users和items进行估计。将它们表示成metadata features的组合,可以从训练集中被估计,并做出冷启动预测。
  • 3.如果只有指定变量,LightFM与标准MF模型相当。

当只有metadata特征、没有指示变量时,模型通常不会缩减到一个纯CB模型。LightFM通过对协同交叉矩阵进行因子分解来估计feature embeddings;这不同于CB模型:它会对纯内容共现矩阵进行因子分解。

一个特别的case是,当每个用户通过一个指示变量描述时,并且只与一个item交互时,此时LightFM会变为CB。在该setting中,user vector等价于在LSI公式中的一个document vector,只有在product descriptions中共同出现过的features具有相似的embeddings。

事实上,LightFM一方面包含了在sparse data的纯CB模型,另一方面包含了在dense data上的MF模型。事实上,经验表明,至少与每种场景的单一模型一样好。

参考

Label Partitioning For Sublinear Ranking