LinUCB介绍

Reading time ~1 minute

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的算法

参考

youtube推荐强化学习介绍

Alex Beutel等在《Top-K Off-Policy Correctionfor a REINFORCE Recommender System》中提出使用强化学习来提升youtube推荐。主要是从bias/variance的角度出发,具体方法如下:# 摘要工业界推荐...… Continue reading

DSIN介绍

Published on May 27, 2019

MIND召回介绍

Published on May 25, 2019