没有合适的资源?快使用搜索试试~ 我知道了~
基于参数化动作强化学习的Web搜索匹配方案生成
1040→基于参数化动作强化学习的Web搜索匹配方案生成罗紫燕1, 2,赵林峰,<$,赵,<$,程伟1, 4,陈思豪,<$,陈琪1,王海东1,刘传杰1,杨茂1,张林涛11Microsoft2加州大学圣地亚哥分校3 东北大学4华北电力大学5加州大学伯克利分校discat@foxmail.com,zhao. northeastern.edu,weicheng5993@foxmail.com,sihao@berkeley.edu{cheqi,xuehui,haidwa,chuanli,maoyang,lintaoz}@microsoft.com摘要为了实现良好的结果质量和较短的查询响应时间,搜索引擎在倒排索引上使用特定的匹配计划,以帮助从数十亿个网页中检索一小部分相关文档。 匹配计划由一系列匹配规则组成,其中包含离散的匹配规则类型和连续的停止配额。目前,匹配计划是由专家根据多年的经验手工设计的,这在处理异构查询和变化的 在这项工作中,我们制定的匹配计划生成作为一个部分Ob-servable马尔可夫决策过程(POMDP)与参数化的行动空间,并提出了一种新的强化学习算法参数化的行动软演员-评论(PASAC),以有效地提高在这两个空间的探索。在我们的场景中,我们还发现了原来的优先级经验重放(PER)的倾斜优先级问题,并引入分层优先级经验重放(SPER)来解决这个问题。我们是第一个将此任务推广到所有查询的小组,将其作为零先验知识的学习问题,并成功地将深度强化学习应用于真实的网络搜索环境。我们的方法大大优于精心设计的生产匹配计划,在文档质量几乎不变的情况下,索引块访问减少了70%以上,即使有模型推断成本,查询响应时间也减少了9%我们的方法也击败了一些开源基准测试的基线1。CCS概念• 信息系统搜索引擎架构和可扩展性。1我们的代码可在https://github.com/RL-matchplangeneration/Match-Plan-上找到作者对这项研究做出了同样的[2]本书主要是作者在微软实习期间完成的。本文在知识共享署名4.0国际(CC-BY 4.0)许可下发布。作者保留在其个人和公司网站上以适当的署名传播作品的权利WWW©2021 IW 3C 2(国际万维网大会委员会),在知识共享CC-BY 4.0许可下发布。ACM ISBN 978-1-4503-8312-7/21/04。https://doi.org/10.1145/3442381.3449862关键词深度强化学习,信息检索,参数化动作软Actor-Critic,搜索引擎ACM参考格式:ZiyanLuo1,2,Cheng , <$,Linfeng Zhao1, 3,Cheng ,<$,Wei Cheng1, 4,Cheng , <$ , Sihao Chen1 , 5 , <$ , QiChen1 , Hui Xue1 and HaidongWang1,Chuanjie Liu1,Mao Yang1,Lintao Zhang1. 2021年基于参数化动作强化学习的Web搜索匹配方案生成 在网络会议2021(WWW '21)的会议记录,2021年4月19日至23日,斯洛文尼亚卢布尔雅那。ACM,纽约州纽约市,美国,12页。https://doi.org/10.1145/3442381.34498621引言如今,大多数基于关键字的搜索引擎使用倒排索引来帮助从数十亿文档中检索相关结果,以实现亚秒级的响应时间[27]。 倒排索引将每个关键字映射到相关文档的列表(倒排列表),该列表为查询提供初始候选项。然后,这些候选人通过一些排名模型重新排名,并最终呈现给用户[15]。随着Web上文档的爆炸式增长,与流行关键字相关的文档集合变得如此之大,以至于无法在有限的时间内处理为了进一步提高搜索效率,搜索引擎开始将来自不同领域的文档分成不同的倒排列表,根据文档质量组织这些倒排列表,并将匹配计划应用于在线候选人生成过程,其中将来自不同关键字和不同领域的倒排列表合并。图1显示了匹配计划的执行匹配计划由一个接一个执行的匹配规则序列组成匹配规则定义搜索引擎如何在一段时间内匹配文档。例如,匹配关键字出现在从倒排列表开始的文档正文、URL或标题字段中的N个候选项(规则A),匹配关键字只出现在从倒排列表的当前扫描位置开始的文档URL或标题字段中的M个候选项(规则B),等等。每个匹配规则具有离散的匹配规则类型(例如, 规则A)和几个连续停止配额(例如,匹配候选计数N)。请注意,不同的匹配规则具有不同的执行成本。在图1中,规则A是昂贵的,因为在规则A中需要检查的候选者的数量比其他规则大。一旦WWWLuo,Zhao and Cheng,etal.1041文档2文档2文档2Doc3文档3文档3预处理网站2021原始查询图1:匹配计划执行的示例。预处理后,多个倒排列表表示不同的条款和不同的领域检索的倒排索引中,文件的质量降序组织。搜索引擎通过执行由一系列匹配规则组成的匹配计划来扫描倒排列表匹配规则定义搜索引擎如何在一段时间内匹配文档它由一个离散的匹配规则类型(例如规则A)和几个连续的停止配额(例如MCCN,其中“MCC”代表匹配的候选计数)组成<一旦剩余文档的质量太低而无法考虑,搜索引擎将选择终止匹配计划的执行如果剩余文档的质量太低而不能考虑,则搜索引擎可以终止匹配计划的执行传统上,匹配计划是由工程师根据他们的专业知识精心手工制作的,以便在结果质量和响应时间之间做出合理的权衡。然而,工程师在进行匹配方案设计时仍然面临着一些挑战。首先,随着匹配规则类型和停止配额类型数量的增加,工程师设计一个适合大多数查询的匹配计划其次,由于倒排索引的数据分布在不同的机器之间和随着时间的推移而变化,因此工程师定期为不同的机器设计不同的匹配计划也是一个挑战。最后,手工制作的静态设计不能动态地修改匹配规则的基础上,中间系统状态,因为它的开环性质,这是适应一些角落的情况。研究人员开始利用学习算法来帮助生成匹配计划。很难将传统的监督学习算法直接应用于我们的任务,因为最佳匹配计划(标签)是未知的。之前的工作[20]试图使用具有离散化状态空间和预定义动作参数(停止配额)的表格Q学习自动生成匹配计划。它每次都为特定的查询类学习一个策略,并且只在离散空间中使用表格方法来解决它,这限制了它在实际搜索场景中对更广泛查询的推广能力。在本文中,我们将匹配计划生成扩展到一般情况,使得状态信号和匹配计划被完全参数化并从头开始学习,而无需任何预定义的知识(例如,停止配额)。我们将匹配计划生成问题表示状态由动态系统运行时信号(例如,当前匹配的文档)和静态查询特征(例如,查询嵌入)。动作空间称为参数化或离散-连续混合,其中动作具有离散动作类型和连续动作参数。奖励是结果质量和查询响应时间的函数。 该公式类似于参数化动作RL(PARL)[14],而我们的设置要求所有动作共享相同的动作参数。此外,我们的环境是复杂的。我们能够观察到的运行时信号是有限的,它们只是中间系统状态的一个缩影只有在执行了整个匹配计划之后才能获得奖励,并且只有很少的匹配计划可以匹配所需的文档,这导致稀疏的奖励信号。我们提出了一种新的深度强化学习算法,参数化动作软演员-评论家(PASAC),以解决这些挑战,它学会在参数化动作空间环境中采取行动,并最大化参数化动作空间中的预期回报和熵我们提出了分层优先经验重放(SPER),以解决倾斜的优先级问题的原始PER通过引入“缓冲区分层”,以优化在不同的奖励范围内的所有查询。为了处理固有的部分可观测性,我们在可变长度匹配计划上应用了循环策略[9]我们提出了一个代理集成这些技术。代理在生产环境中使用从Bing 2收集的查询数据集进行训练和评估。由代理生成的匹配计划优于设计良好的生产匹配计划,特别是在延迟方面:我们的方法在测试数据集上实现了超过70%的索引块访问减少,结果质量几乎不变,即使有模型推理成本,查询响应时间也减少了9%。我们进行消融研究,以验证组件的有效性 我们还测试了一些现有的PARL基准,我们的代理击败了我们的基线方法,并在可比方法中执行最先进的结果。2https://wbing.com搜索引擎高质量低质量Term 领域文件(过帐清单)web title –URL –倒置机身–2021年指数标题URLbody匹配单据Doc7、Doc8规则A(MCC N)已执行的比赛计划标题正文URL规则B(MCC M)标题URL规则C(MCCK)(已终止)标题基于参数化动作强化学习的Web搜索匹配方案生成WWW1042--O∈[)T S×S ×A → R S ×A →S AT(S A TR)S A T R O)?X{}的t索引服务器系统信号奖励(rt)运行查询查询统计RL代理编码查询嵌入州(st)假设高质量的文档更有可能出现在索引的前面它建议我们尽早停止,跳过张贴列表长尾上的低质量文档工程师们手工设计了一些匹配策略,可以有效地修剪候选文档集,称为匹配计划。通常,匹配计划由一系列匹配规则组成,其中每个匹配规则可以由多个状态控制。 注意,不同的匹配规则具有不同的执行成本,因为需要一些索引块访问(“IBA”)来检查候选。通常,高成本战略总是对应于高质量的结果。在图1中,规则A是昂贵的,因为匹配规则类型时间步长相关行动(at)时间步长无关规则A中需要检查的候选项比其他规则大。在此基础上,我们提出了一种学习方法,可以自动平衡质量(即,相关性分数由Bing的生产环境分级)和延迟(即索引块访问)。图2:生成过程的一个片段的概述。绿色框表示在每个(时间)步骤中连续预测离散-连续动作的更新量,而蓝色框在每个事件中是固定的圆角矩形是产生相应数量的过程。(1)给定一个随机抽样的查询,我们收集一些查询统计,如它的长度,并提取一个查询嵌入。(2)我们使用所有先前计算的动作a1,..,在索引服务器上进行测试,并将系统信号(如延迟)作为对RL代理的反馈我们将所有三个量连接起来,并将它们(以及过去的观察结果)作为智能体的输入。代理计算匹配规则类型和配额参数,并在索引服务器上再次运行它以获取下一个系统信号,并重复直到停止操作或服务器端终端信号。整个动作序列{a1,..,aN}是一个完整的匹配计划。2背景2.1搜索引擎中的处理过程当用户在网站中键入查询时,[4]将由搜索引擎执行:首先,查询将通过自然语言处理技术进行解析和预处理,如分词,停止词删除等。然后,将扫描给定查询的过帐列表,该列表可能包含数百万个文档。在这一匹配程序中,需要在短时间内从大量候选人那里收回高质量的相关文件,这使得这一程序具有时间敏感性。在排序过程中,将按相关性分数对召回的文档进行排序 这意味着排名过程更加关注结果的质量而不是延迟。在我们的工作中,我们关注的问题,有效地召回候选人在匹配过程中。我们在Bing部署的生产环境上进行实验我们简要介绍了Bing中的基线系统和Match的发展在生产环境中,通过简单的统计信息(即查询的长度)将查询分类为几个预定义的类别之一,然后基于手工制作的规则选择匹配计划因此,现有的粗分类在优化匹配过程中仍有很大的潜力。在我们的工作中,我们还包括查询3问题陈述在[20]中,为匹配计划生成预定义了动作参数,其中动作空间是一组离散的匹配规则(动作),状态空间也被离散化。我们完全参数化匹配计划,以允许代理生成任何有效的计划。3.1问题公式化我们将匹配计划生成问题建模为离散时间部分可观察马尔可夫决策过程(POMDP)[11],因为我们假设我们可以观察到的运行时信号是有限的,远远不足以描述完整的中间系统状态。 我们使用一个参数化(离散-连续混合)的动作空间来表示每一步的任何可能的选择。POMDP由元组(,观测值集由下式给出,将底层状态映射到观测值上的概率分布的观测函数由下式给出。智能体与环境交互以最大化具有折扣因子γ0, 1的累积奖励。在前面的参数化动作RL像[2,14]一样工作,动作空间表示为:优化如下。2.2 Bing中的匹配过程优化A=k∈Ad{(k,xk)|xk∈Xk},随着互联网上越来越多的文档被抓取,倒排索引中的倒排列表变得太长,无法在有限的时间内检索匹配优化建立在其中,每个离散动作a d=K=k1,...,k K具有相应的连续作用参数空间a。根据匹配的性质,我们引入了一个略有不同的公式配额WWWLuo,Zhao and Cheng,etal.1043X∈一...(())(())H·|()计划生成:A={(k,x)|k∈A d,x∈X}=A d×X,其中离散动作空间(用于匹配规则)d共享动作参数空间R N,即连续动作空间(用于配额)。 这样的表述导致离散和连续动作之间的解纠缠动作空间,其中一类参数化动作(P-DQN [26]和MP-DQN [2])可能不被平凡地应用。我们有一个很大的动作空间,这样的公式过于复杂,使代理不可能收敛。因此,我们的模型只包含一个离散的动作空间和一个共享的参数空间。参数化与离散化动作空间。处理我们问题的另一种方法是将上述连续动作空间离散化。我们使用参数化的动作空间而不是离散化的动作空间,主要是由于以下动机:1)粗粒度配额控制可能导致不精确的控制。相反,动作空间太大,使得模型难以收敛。很难平衡这两个问题;2)生成离散化配额不能利用数值排序的先验知识。此外,在第5节中,实验表明,使用参数化的动作空间比离散化的动作空间性能更好。环境 该环境与Bing的索引服务器通信,以发送动作序列并接收状态和奖励。在一集的开始,随机选择一个查询,目标是找到一个最佳的匹配计划的奖励。对于每一步,代理生成一个匹配规则并将其发送到索引。执行后,索引将状态信号返回给代理。请注意,环境只包含Bing索引的一个碎片 因为索引在不同的机器中均匀分布,我们假设如果我们在一台机器上实现最佳性能,整个机器集群也将处于最佳设置。我们还在指数的其他碎片测试了我们的算法和模型,结果几乎保持不变。3.2 环境建模代理和环境之间的交互如图2所示。POMDP的关键组成部分如下:状态 在每个时间步,代理接收具有时间步相关特征和时间步独立特征的状态。如图2所示,时间步长相关部分包含选定的运行时系统信号(例如,索引位置、匹配文档计数、IBA、匹配文档质量等) 倒排索引系统。时间步长独立部分包括一些统计特征和查询的语义嵌入,以允许代理识别不同的查询。 这样的统计特征被用在当前的生产系统中,例如查询的长度和流行度。有关状态特征的详细信息包含在附录中。行动上代理在每个步骤选择包括匹配规则类型和分配的配额的参数化动作。在Ad中有29种匹配规则,并且每个匹配规则也有一个配额X的参数所有输出的配额仅对当前步骤有效 还有一个特别的动作要注意:停止(由代理商)。 环境可能会终止并返回终端信号,但这只发生在极端情况下,例如查询延迟太长,超出预算。 为了更好地平衡延迟和性能,我们允许代理选择停止或不停止作为另一种类型的离散动作,这是对其他29个匹配规则的补充。奖励 我们在奖励中使用两个标准:延迟和质量。出于延迟考虑,由于执行时间由于高速缓存而有噪声,因此我们使用索引块访问(“IBA”),其在不同的外部环境中是恒定的。 性能由返回的前K个文档的相关性得分(“RS”)表示,这些文档由Bing工程师构建的排名模型进行分级。RS被训练成NDCG的近似[20]。我们的比赛计划生成模型训练依赖于一台机器。但也有少数(如。零个/一个)标记的文档标记查询集太小,无法训练模型。因此,我们使用RS代替NDCG来表示相关性,因为RS比NDCG具有更平滑和连续的值空间,并且更稳定,更容易让模型学习。奖励rt由IBA和RS计算rt=(λ1RSt−λ2 IBAt)−(λ1 RSt−1−λ2 IBAt−1), (1)其中λ1,2是两个评估度量的权重,其用于在相关性和效率之间进行权衡。具体地,初始值RS 0和IBA 0都是零。4方法在搜索引擎中使用强化学习生成匹配计划是一项具有挑战性的任务首先,我们环境中的动作空间包含离散和连续动作,而大多数强化学习算法关注的问题是动作空间是离散的还是连续的。其次,搜索引擎的环境是复杂的异构查询表示和状态。在我们的场景中,查询是异构的,这需要一个高维表示;在我们的状态中使用的许多中间信号也有一个大的和连续的值范围最后,稀疏奖励也是训练收敛的挑战[1]。特别是在培训初期,由于政策培训不足,积极的奖励很少。4.1参数化动作软Actor-CriticSoftActor-Critic(SAC)[6]是一种最先进的控制RL算法,已证明其采样效率和学习稳定性以及超参数鲁棒性。然而,SAC仅在连续作用下得到了较好的研究,可以用于离散作用。因此,PASAC提出了参数化的行动空间。PASAC的伪代码包含在附录中的算法1和网络结构中。参数化动作策略中的最大熵 PASAC以非策略方式优化随机策略,并优化最大化预期未来回报和最大熵目标的策略:J π =Est,xt,ktτπ γt r st,xt,kt+α π (2)不···基于参数化动作强化学习的Web搜索匹配方案生成WWW1044()下一页()下一页∈Aθ˜.Σ不ψ不不Q函数,γ∈ [0,1]是折现率,st∈ S是时间点的状态(st,xt,kt)2θ不 不 不不动作是从连续演员网络输出的均值和方差生成的高斯分布中采样的(如日志+HcπstDktπDϕ不不θ不 不 不类似地,连续策略ππ的目标是:Jπ(π)=Est<$D。Extπ。αc测井曲线ππ(xt|st)<$−Qθ(st,kt,xt)。.其中D表示经验重放,θ表示联合软Q网络的参数,α d和α c表示离散和连续执行器网络的参数,αd是离散策略熵的离散温度参数,αc是连续策略熵的连续温度参数软Q网络。每一个完整的动作都由离散和连续两部分组成,a t= k t,x t。因此,在PASAC中,评价网络估计联合软Q函数Qθ st,kt,xt,其中θ是评价网络的参数这种策略使两个不同参与者的输出的离散和连续的行为保持相关。离散行动者网络输出分类概率-作为表示[f(k1),f(k2),.,f(kn)]对于n维t t t磁盘访问操作,其中ref(·)图3:PASAC的框架及其与搜索引擎环境的交互是sof tmax函数。关节软Q函数取连续动作xt和表示向量[f(k1),f(k2),.,f(kn)]作为输入。这个Q函数估计离散和连续作用的联合Q值,而不是Q值仅用于连续动作,这与P-DQN不同它可以被训练以最小化软Bellman残差:其中π是策略,T是时间步数,r是奖励J(θ)= E1。Qt(s,x,k)−y<$2<$, (5)步骤t,a t是在时间步骤t的动作,τ是由策略π引起的轨迹分布,α是温度参数,它决定熵项相对于报酬的相对重要性,从而控制最优策略y的随机性。 He reH(π(·|st))是策略π在状态st处的入口。PASAC的架构 原始SAC包含一个评价网络来评估连续动作的Q值,以及一个演员网络来估计连续动作的高斯分布的均值和方差。在PASAC中,有离散和连续的行动者分支(网络),它们用于同时生成离散和连续的行动。 这两个参与者网络的参数并不完全相同,并且共享前几层来编码状态信息。 PASAC包含一个评价网络,用于估计离散和连续动作的Q值。PASAC的架构如图2所示具有参数化动作空间的策略网络 以生成其中目标yt是yt = rt + γ Qt +1(st +1,xt +1,kt +1)− ht,(6)和来自最大熵的项ht=αdlogπ(kt+1|st+1)+αc logπ(xt+1|其中,表示目标联合软Q网络的参数。双阿尔法调谐。 [7]使用α损失自动调整熵的温度。该方法使策略能够在训练期间和跨环境自适应地受SAC的启发,我们提出了两个α损失来分别调整离散和连续策略熵的温度该方法允许独立探索离散和连续策略。此外,它提供了一个更有效和平衡的探索策略。 为了训练温度参数α d和α c,梯度下降应用于以下目标:离散行动,离散行动者网络为所有离散行动估计分类策略ππ,并且要执行的离散行动是J(αd)=Ekt<$π t.−αd。log.π(kt|st)+Hd.(八)从分类分布中采样π π(k |[23]。连续ϕ...J(αc)=Ext<$πt−αc好吧SAC通常会这样做)。连续行动者网络生成当reH<$i是光盘检索的目标对象y时,H<$c是通过输出每个参数的高斯分布的均值和方差,为连续动作提供随机策略通过最大化它们各自的熵目标来分别更新它们。离散策略ππ的目标由下式给出:D连续策略的目标熵现任国家元首。 为了将PASAC应用于匹配计划生成任务,我们应用递归神经网络来处理我们设置中的部分可观测性[9],因为我们根据经验发现,J (λ)= E.E.α log.π (k)|s)−Q (s,k,x)..系统信号不能提供下一状态的足够信息(三)联合Q值Recurrent Critic Network(联合软Q函数)离散动作连续动作离散行动者网络离散动作连续动作(参数)连续演员网络循环状态编码网络状态反馈环境(四)ππ(xt|(st)(九)RNN参数的训练使用整个轨迹的时间(BPTT)。WWWLuo,Zhao and Cheng,etal.1045中文(简体)端()下一页()()端不 不不 不不 不D← −()算法1参数化动作软Actor-Critic输入:初始参数θ1、θ2、θ 1、θ 214000初始化目标网络初始化经验回放缓冲区对于每一集,对于每个环境步骤,示例一个光盘读取操作kt<$π(kt|(st)样本参数xt <$π<$(xt|(st)存储转换D ← D <$(st,f(kt),xt,rt,st+1)对于每个梯度步长,从重放缓冲区D中取样一个小批次更新关节软Q函数参数θi<$θi−λQ<$θiJQ(θi)for i∈[1, 2]更新离散策略权重←12000100008000600040002000050 25 0 25 50 75 100 125奖励更新连续策略权重←调整离散策略熵的温度αd<$αd−λαd <$αdJ(αd)连续策略熵的调温αcαcλαcαcJαc更新目标网络θ<$i<$τθi+(1−τ)θ<$i,其中i∈ [ 1, 2]图4:事件1000和10000时原始PER中查询样本优先级分布的散点图软Q函数[6]暗示了该策略的潜在改进。 受此启发,我们通过将优先级修改为:p(s,a)=|δ(s,a)|+λ(s,a)+ λ,(10)端输出:优化参数θ1、θ2、θ 1、θ 24.2分层优先体验回放在脱离策略的RL算法中,经验st,a t,r t,st +1存储在重放存储器中,并且代理从存储器中均匀地采样小批量,而不是使用当前经验进行训练。最近,许多非策略强化学习算法使用优先经验重放[21](PER),并取得了比普通经验重放更好的结果。在PER中,来自重放存储器的采样可以以与TD错误成比例的概率pi被优先化,以增加采样效率。倾斜的优先级。在我们的复杂环境中,我们发现PER的倾斜优先级属性:高度优先的样本通常集中在奖励空间的小范围内,如图4所示。在这种情况下,那些奖励在一定范围内的经验更容易被采样,这使得智能体在某些状态子空间中表现不佳。具体来说,在我们的设置中,它会导致一些角落查询的训练不足为了缓解 倾 斜 的 优 先 级 问 题 , 我 们 提 出 了 分 层 优 先 经 验 重 放(SPER),以取代原来的PER。缓冲区分层。 重放缓冲器被划分成相同容量的若干个仓(层)。 每个bin存储奖励空间的特定范围内的转换。 当从SPER采样时,通过优先化采样从每个仓获取相同数量的转变。每个箱可以被视为PER,并且每个箱中的采样程序与PER [21]中的相同。TD错误和策略丢失的优先级在SAC中,策略损失是策略的Kullback-Leibler散度和缩放指数其中δ st,at是TD误差,δ st,at是应用于参与者的损失,例如策略损失,并且超参数λ是策略损失的权重,则λ d是基本优先级,以确保即使新样本的损失很高,在训练开始时也以适当的概率对事务进行采样。 为了优化PASAC代理的优先重放,SPER将策略丢失添加到PER中的优先级,这使得具有更大改进潜力的事务比仅仅使用TD错误更有可能被采样。 DDPGfD [24]采用类似的方法,但动机不同。在我们的设置中,我们在SPER中存储经验的轨迹而不是交易来训练递归神经网络[12]。5实验我们研究了基于Bing中真实查询的自制数据集上的匹配计划生成问题,解决了以下问题:Q1. 所提出的算法是否比工程师调整的启发式手工方法或其他RL算法更好Q2. 我们把这个问题表述成一个PARL问题,而不是离散化的行动空间?Q3. 我们的方法在真实搜索场景中的改进情况如何Q4. 应用SPER及其组件的效果如何Q5. 建议的代理人是否在其他PARL长凳上工作良好标记基线?5.1实验设置数据集预处理。对于匹配计划的生成,我们在一个数据集上进行了实验,该数据集具有从Bing的搜索日志中采样的大约100,000个查询我们从以下几个方面过滤数据集我们跳过了一些没有嵌入或需要匹配计划之外的额外操作的特殊查询一千集10000集优先·⋄基于参数化动作强化学习的Web搜索匹配方案生成WWW1046·我们跳过所有高级查询(例如,原始查询包含因为这样的高级功能无法在查询嵌入中表达。我们只在为英语国家设计的市场中使用查询,以避免包含一些扭曲的数据。过滤后,数据集大小约为36,000。在真实的搜索场景中,我们永远不知道用户想要搜索什么。为了模拟这种情况,我们随机选择3,000个查询作为测试数据集,其余的查询作为训练数据集。基线。 对于Bing中当前实现的系统中的匹配计划,每个查询都被分类到一个预定义的查询类中,该查询类具有一些启发式手工规则。 我们使用每个查询的生产匹配计划作为基线。生产对于大多数查询都很好,因此在许多查询上优于生产并不是微不足道的。比赛计划生成的评估方法。在实验中使用以下度量:平均相对改善(ARI)。ARI是为评估不同的RL代理而设计的它表示所有测试查询的最终回报(一个事件中的奖励总和)的平均改善。 它是我们实验中最重要的指标,因为它与我们的优化目标(最终收益)紧密相连。给定代理图5:平均相对改善(ARI)的比较实验。X轴是千集的数量。Y轴表示ARI。请注意,为了回答Q1,以下所有方法都与我们的基线一致,即:目前的启发式手工制作的亲,.|(Ri|(Ri–Bing中使用的规则,如第5.1节所述ARI = i=1基线|D|哪里|D|表示测试数据集大小,R i(十一)和RiDQN。深度Q学习(DQN)[16]是一种著名的Q学习,的,离政策的方法处理离散的行动空间。在在我们的场景中,我们一致地离散连续动作空间,阿登特基线(配额)分为20(DQN-20)和100个离散值(DQN-100)表示给定代理测试数据集中的第i个查询更好和平等。更好意味着测试数据集中由我们的方法生成的匹配计划优于基线的查询的百分比平等的定义也是如此模特训练 系统状态以固定的间隔在训练和测试阶段之间交替。我们所报道的实验结果都是测试阶段的结果 在测试阶段,它在整个测试数据集上依次评估代理。在训练阶段,智能体在每集的训练数据集中随机选择一个查询。我们在测试数据集上每5,000次训练就评估代理每个实验用不同的随机种子重复三次实施细节。每个比较实验和PASAC都使用PyTorch在一个TeslaP100 GPU上进行训练。在所有实验中,等式1中的λ1,λ 2被设置为1。关于实验实施的更多细节可以在附录中找到5.2比较方法我们比较了PASAC代理与几个国家的最先进的方法。方法稍微调整以适应我们的场景。为了回答Q2,采用了一些具有离散动作设置的最先进的RL方法。比较中的所有代理都是用LSTM [9,10]实现的,没有像SPER这样的高级组件来进行公平的比较。分别PA-DDPG。 深度确定性策略约束(DDPG)[13]是一种最先进的方法,它基于离线策略和Q学习,但学习确定性策略。为了适应我们的场景,我们主要参考PA-DDPG [8]将DDPG应用于我们的问题。TD 3。Twin Delayed DDPG(TD3)[5]提高了DDPG的稳定性和效率 我们在PA-DDPG中采用了类似的方法来适应我们的场景。详情见附录。SAC-离散。SAC-离散(SAC-D)[3]是SAC的替代版本,可应用于离散动作设置。我们在DQN中采用相同的方法来离散连续动作空间,以使SAC-D 在我们的设置(SAC-D-20 和SAC-D-100)中可用。5.3性能比较图5显示了所有比较方法的测试数据集上的ARI表1显示了所有提到的方法的更好,平等和ARIDQN-20和SAC-D-20未绘制,因为性能与DQN-100和SAC-D-100相似,但不令人满意。如图5和表1所示,在离散行动环境中解决这一问题将导致更糟糕的结果。平均而言,DQN在所有比较实验中表现最差,并且表现出较大的方差。实验结果表明,DQN的ε-贪婪探索策略不能有效地探索大的离散动作空间。它也可能受到Q值高估的影响正如预期的那样,SAC-D优于DQN,因为不仅算法········WWWLuo,Zhao and Cheng,etal.1047表1:所有提到的方法的更好、平等和ARI。在这里,我们只显示每个代理公司简介 公司简介 D-SAC-20D-SAC-100 PA-DDPGTD3PASACPASAC+SPERARI-1.500-1.9570.2100.460-2.4920.83841.2801.912更好26.70%27.43%40.47%49.30%39.97%41.90%50.53%60.10%等于3.70%4.50%10.10%6.03%3.17%4.67%6.07%11.60%它本身显示了优越性,正如许多作品所总结的那样,但它的探索由调谐阿尔法控制是更有效的,在我们的设置,以及,这导致更好的结果在这里。然而,这种离散化也会导致控制配额的准确性下降。对于离散-连续混合作用空间集的方法,PA-DDPG的性能最差。TD 3解决了DDPG中的高估问题,并且在我们的实验中表现得比PA-DDPG更好。然而,PA-DDPG和TD 3都未能充分探索我们设置中的大动作和状态空间,因为在确定性策略学习中,学习alpha来控制随机性比固定动作空间噪声更具适应性。综合考虑上述问题,PASAC在稳定性和效率方面都表现最好。5.4绩效评价为了回答问题3,我们首先检查我们的方法在第3节中提到的奖励的每个部分上的性能在测试阶段,我们对每个查询的缩放索引块访问(IBA)改进和缩放相关性得分(RS)改进进行了统计。表2:与基线相比,我们的方法的(平均)IBA、(平均)RS、文档回忆延迟(延迟)、考虑参考时间的文档回忆延迟(延迟+推断)注:“+”代表改进。IBARS延迟延迟+推理改进+75.77%-1.47% +28.14%+8.97%在图6和表2中,我们发现我们的方法只实现了1/4的IBA,而文档的质量几乎没有变化。 因为生产配合计划是由工程师手工制定的,不能灵活控制定额。此外,我们发现,使用我们的方法,匹配计划序列是3。比使用生产规则短78%因此,由于不合适的配额和匹配规则的冗余匹配规则,浪费了大量时间。此外,由于Bing的高缓存命中率,我们的方法只减少了28的生产文档召回延迟。平均每个查询14%。考虑到我们模型的推理时间,我们的方法仍然将延迟提高了8。百分之九十七我们只使用没有任何优化的模型进行推理(例如,修剪以节省计算,使用蒸馏或量化为16位或8位权重进行压缩),可以进一步压缩和优化。因此,该结果已经表明了该方法应用于Bing实际生产的可行性和优越性。5.5消融研究响应于Q4,我们比较了使用PASAC应用不同重放缓冲区的结果。策略损失应用于优先级计算图6:测试阶段IBA和RS改善的分布直方图由于RS改善的实际范围相当大,我们只显示[-10,10],因为数据在这个范围之外太稀疏。在所有这些实验中。 我们进一步比较了在优先级计算中有或没有策略损失的情况下应用SPER的结果。从图7(上图)中,我们可以观察到PER的性能甚至比原始经验重放缓冲区更差。一个原因可能是,PER没有考虑倾斜的优先级问题,并且总是对具有类似“困难”的小范围查询进行采样以找到相关文档。然而,其他查询没有得到充分的训练。因此,在我们的环境中简单地应用PER是不合理的。在对SPER进行改进后,Agent的性能优于PER和原来的经验重放缓冲区。从图7(下图)中,我们发现优先级中具有策略丢失的SPER性能更好。一个原因可能是,使用优先级,基于参数化动作强化学习的Web搜索匹配方案生成WWW1048[客户端]X(())∈A图7:在ARI上使用不同的经验重放缓冲区和SPER进行实验,有或没有策略丢失.政策损失考虑样本具有较大改进潜力的另一种情况:政策损失高,政策参数可以改进。5.6基准游戏为了在更广泛的背景下评估我们的代理并回答Q5,我们在两个开放的基准游戏上进行了实验,以评估我们的算法,Platform-v0和Goal-v0 [2]。 这些游戏遵循稍微不同的公式[2],每个离散动作都有一个单独的连续动作参数空间。我们假设环境是完全可观察的,因此在基准测试中,PASAC代理中没有使用递归网络。对于基准测试,我们使用Microsoft NNI3来选择hyperpa,rameters。检索空间和最佳试验曲线见附录。我们发布的代码可重复性(见摘要)。我们报告最好的最终指标。 PASAC在这两个基准上的表现都明显优于PA-DDPG。 对于Platform-v0,返回值的范围为0,1。Goal-v0的最大回报率为50,而PASAC几乎可以在训练一半后不断实现这一目标我们的实验结果符合[2]中报告的PA-DDPG性能较差的情况。我们观察到PASAC+SPER具有几乎相同的性能3https://github.com/microsoft/nni表3:使用PA-DDPG [8]对基准Platform-v0和Goal-v0的平均评估结果(所有培训奖励和最终评估奖励的平均值(重复100次))。平均评估回报PASAC PASAC+SPER PA-DDPG[8]粤ICP备16037773号-1进球-v043.1143.85-6.208作为帕萨克。 这验证了如果应用PER,分层采样可以更好地适应具有偏斜优先级排序问题的环境。6相关工作我们的相关工作包括[20]。它工作在离散的状态和动作空间与表格RL方法。它每次学习一个特定的查询类的策略,并解决它只在离散空间,这限制了它在异构查询的推广我们的算法基于Soft Actor-Critic [6],这是一种基于非策略Q学习的策略梯度方法。SAC优化了基于能量的随机策略.以前的工作深度确定性策略约束(DDPG)[13]也是基于离线策略和Q学习的,但学习确定性策略。 Twin Delayed DDPG(TD3)[5]提高了DDPG的稳定性和效率。参数化动作强化学习(parameterized Action reinforcementLearning,PARL)是指将动作空间参数化(离散-连续混合)的强化学习设置。 目前的PARL方法主要来源于DQN和DDPG,包括两大类方法:基于DDPG的PA-DDPG [8]和基于DQN的P-DQN[26]。他们使用不同的策略来结合离散和连续的行动。P-DQN [26]为每个离散动作学习多个连续动作策略网络MP-DQN [2]扩展了P-DQN,以解决正常PAMDP中Q值是联合作用参数向量Q s′,k′,xQs′的函数的问题,这可能导致假梯度。然而,在我们稍微修改的设置中不存在这样的问题,因为匹配计划生成中的动作参数空间固有地被定义为对于每个kd共享。[14]的目的是通过在它们之间交替来迭代优化离散和连续动作的方法我们专注于非策略算法,并通过将它们存储在重放存储器中来利用过去的经验[17,22]。 优先经验重放[21]通过优先考虑具有高TD错误的转换来重用现有经验来提高效率。在POMDP上应用RL有不同的方法[11],而我们专注于使用递归网络[9](RDPG)和时间反向传播(BPTT)[25]。7结论为了自动地为不同的查询生成好的匹配计划,我们将匹配计划的生成公式化为通用的PARL框架。我们提出了一种新的算法,参数化的行动软演
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功