ParClick：基于EM的点击模型的可扩展并行算法的研究

392≈ParClick：一种基于EM的点击模型的可扩展算法PooyaKhandelUniversity ofAmsterdam阿姆斯特丹，荷兰p.khandel@uva.nlIlyaMarkovIndependentresearcher荷兰阿姆斯特丹ilya.markov@gmail.comAndrewYatesUniversity ofAmsterdam阿姆斯特丹，荷兰a.c. uva.nlAna-Lucia Varbanescu阿姆斯特丹大学荷兰阿姆斯特丹a.l. uva.nl摘要对点击模型的研究通常集中在开发有效的方法来减少用户点击的偏见然而，现有点击模型的主要缺点之一是缺乏可扩展性。在这项工作中，我们解决了期望最大化（EM）为基础的点击模型的可扩展性，通过引入ParClick，一个新的并行算法设计的分区通信聚合映射（PCAM）的方法。 为此，我们首先提供了一个通用的制定基于EM的点击模型。然后，我们设计了一个有效的并行版本的通用点击模型以下的PCAM方法：我们分区用户点击日志和模型参数到单独的任务，分析它们之间的通信，并聚集这些任务，以减少通信开销。最后，我们提供了一个可扩展的，并行实现所提出的设计，以及映射到一个多核机器。我们在Yandex相关性预测数据集上的实验表明，当增加训练数据和计算资源时 ， ParClick 可 以 很 好 地 扩 展 。 特 别 是 ， 与 点 击 链 模 型（CCM）的标准顺序版本相比，ParClick在4000万个搜索会话和40个线程的训练速度快了24.7倍，而效率没有任何下降。CCS概念• 信息系统→用户和交互式检索。关键词点击模型，Web搜索，用户建模，并行计算ACM参考格式：Pooya Khandel ， Ilya Markov ， Andrew Yates ， and Ana-LuciaVarbanescu.2022. ParClick：A Scalable Algorithm for EM-Based ClickModels. 在 ACM Web Conference 2022 （ WWW '22 ） 的 临 -CENTRAL，2022年4月25日至29日，虚拟活动，里昂，法国。ACM，New York，NY，USA，9页。http：//doi.org/10.1145/3485447.35119671介绍用户通过提交查询请求和与搜索引擎，主动地通过搜索引擎查找各种信息这 项研究是在阿姆斯特大坝大学完成的。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上版权的组成部分，这项工作所拥有的其他人比ACM必须尊重。允许使用学分进行摘要 以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。请求权限请发邮件至permissions@acm.org。WWW©2022计算机协会。ACM ISBN 978-1-4503-9096-5/22/04。. . 十五块https://doi.org/10.1145/3485447.3511967搜索结果页面（SERP）。用户交互，如点击、鼠标移动和计时，包含用于增强排名性能的有价值的信息[25]。在这些用户生成的数据中，使用最广泛的信息来源是用户点击[9，25]。用户点击会受到各种类型的偏见的影响，例如位置偏见或注意力偏见[9]。为了准确预测观察到的点击，包括纠正偏差，提出了许多基于概率图模型（PGMs）的点击模型[9]，神经网络[3，4，8]。在实践中使用的最有效的点击模型，例如，基于位置的模型（PBM）和点击链模型（CCM）采用期望最大化（EM）从点击日志中学习它们的参数[9]。这种学习方法缺乏可扩展性。例如，使用标准PyClick1库训练具有8百万个搜索会话的PBM模型在以2.30GHz运行的Intel（R）Xeon（R）Gold 5118 CPU上花费大约12.5小时，而将搜索会话的数量扩展到4000万对于这种方法是不可行的，这是由于训练的大内存占用（即， 训练崩溃内存不足，即使机器有256GB的RAM）。与此同时，一个大型的网络搜索引擎，如谷歌，在一天内处理多达35亿个搜索会话（437倍以上的数据）2这意味着，使用现有的算法，即使是简单的点击模型，如PBM，在单个Google日提高大型点击日志的点击模型的可扩展性对于现实世界的应用程序是非常有益的，因为它能够显著提高处理和/或快速处理大量数据集。具体地说，更好的可扩展性（i）使得分析更大的点击日志变得可行，这反过来又提供了更好的查询覆盖率，因为在训练期间可以看到更多的独特查询，3（ii）使得频繁的再训练，从而提供对用户可能的错误或随时间变化的有效支持，以及（iii）提供采用日益复杂和更有效的点击模型的机会基于PGM的点击模型被广泛用于在线和反事实学习排名[1，18，20，28，30]。 这些模型通常使用最大似然估计（MLE）或EM算法进行训练;然而，已经证明使用EM训练的点击模型表现更好[15]。在我们的工作中，我们专门解决了基于EM的点击模型的可扩展性，旨在设计一个通用的解决方案，支持应用的多样性，这体现在不同的参数，不同的估计函数，以及不同的点击日志数据在 本 文 中 ， 我 们 提 出 了 ParClick ， 一 个 通 用 的 算 法 ，considerably提高了可扩展性的EM为基础的点击模型，通过有效的 并 行 化 。 具 体 来 说 ， 我 们 采 用 分 区 - 通 信 - 聚 合 - 映 射（PCAM）[13]设计方法1https://github.com/markovi/PyClick2 https://www.internetlivestats.com/google-search-statistics3许多点击模型只适用于他们在训练过程中看到的查询WWWPooya Khandel，Ilya Markov，Andrew Yates和Ana-LuciaVarbanescu393）（）（（）下一页提出了一种新的并行算法，该算法能够正确有效地划分用户点击日志和模型参数，并将不同分区的处理分配给并行任务。我们的算法是通用的，因为它支持不同的处理任务（支持多个点击模型），不同的分区和负载平衡策略，从而实现接近最佳的强伸缩性，并可以在任何并行系统或编程模型上实现。我们的原型，在本文中评估，包括两个点击模型，两个负载平衡策略，并实现了多核机器。具体地，我们证明了我们的通用算法的两个案例研究：相对简单的PBM模型，作为一个代表的基于位置的点击模型，和更复杂的CCM模型，作为一个代表的级联点击模型。 我们使用Yandex相关性预测数据集评估了ParClick应用于PBM和CCM的可扩展性[26]。 我们的研究结果表明，ParClick在增加点击日志和分配资源的大小（即， 用于算法的线程和用于机器的核心）。例如，在我们最大的实验中，我们使用40个线程（每个线程一个）训练了4000万个搜索会话的CCM。#24040;，并观察到？7.与标准SE相比顺序版本。总的来说，我们的分析表明，ParClick可以用于训练具有大量搜索会话的基于EM的点击模型，例如，四五概括而言，我们工作的主要贡献如下：(C1)我们制定了一个通用的算法，用于训练基于EM的点击模型。(C2)我们设计了一个并行版本的通用算法，遵循PCAM方法，从而提供了第一个可扩展的，通用算法来训练基于EM的点击模型。（C3）通过大量的实证分析，我们证明了ParClick可以很好地扩展更大的点击日志和更多的计算资源。(C4)我们提供了一个开放源代码，高效的实现ParClick，适用于任何共享内存并行机。4此外，与PyClick相比，此实现的训练速度更快本文其余部分的结构如下。我们在第2节中概述了相关工作。第3节描述了PBM和CCM模型，并解释了如何使用EM算法估计它们的参数。我们将在第4节中详细解释ParClick的设计和实现。我们的实证评估和结果在第5节中介绍。最后，我们在第6节总结了本文。2相关工作为了将我们的研究放在上下文中，本节概述了点击模型的最新进展以及它们如何解决可扩展性。一类点击模型是基于概率图形模型（PGMs）开发的[19]。 这些模型的不同之处在于它们如何区分两个主要事件：用户检查文档和用户被文档吸引。例如，PBM模型假设考试取决于排名[9]。级联模型[10]则假设检查取决于是否检查和/或点击了排名较高的文档。提出了PBM和级联模型的各种扩展[6，12，16，17]。更4https://github.com/uva-sne/ParClick最近的工作集中于利用关于用户、结果和其他搜索特征的进一步信息，以提高点击模型的准确性[7，27，29，32]。另一类点击模型由基于神经的方法形成。鲍里索夫等人[3]提出了一个通用的神经框架，并将用户浏览行为建模为一系列向量。Yu等人[31]介绍了排名偏置神经网络，以自动学习查询和文档的输入表示。通过研究预测点击和估计相关性得分之间的关系，Chen等人。[8]介绍了上下文感知点击模型。此外，Daiet al.[11]利用模仿学习来解决暴露偏差和劣估计。最近，Linet al.[21]提出了GraphCM，它基于图神经网络来提取会话信息并解决数据稀疏问题。所有这些方法都集中在提高点击模型的有效性。然而，到目前为止，计算效率和可扩展性很少受到关注。大多数关于提高效率的研究都集中在EM算法本身，这是一种计算密集型算法。例如，[2]提出了一种使用GPU的EM并行变体，针对高斯混合模型（GMM）的应用进行了优化，但不直接适用于有效的点击模型。相反，在线方法[5，24]被构建为更快地收敛，并形成了Markov等人的OnlineEM方法的基础。[23]用于更新新记录的查询会话的已训练模型的参数，而无需从头开始重新训练。然而，OnlineEM无法从零开始提高训练点击模型的效率. 与我们的工作最接近的研究是[22]，其专注于大规模的baidu浏览模型的有效训练;然而，他们的方法没有直接推广到基于EM的点击模型。在这项工作中，我们提出了第一个通用的并行算法，直接解决基于EM的点击模型的可扩展性。因此，我们的方法是对点击模型领域当前发展的补充：我们的解决方案可以与这些方法相结合，以进一步提高现有和最新技术的效率。即将到来的点击模型。3背景在本节中，我们将详细介绍第4节中介绍ParClick所需的PBM和CCM点击模型。表1给出了本文中使用的符号。3.1基于位置的模型（PBM）在PBM点击模型中，用户点击搜索结果P Cd=1的概率取决于用户检查该搜索结果P Ed=1并发现其相关/有吸引力P Ad= 1的概率。1 [9]。检查概率取决于搜索结果，而吸引力概率取决于查询结果对：P（Cd=1）=P（Ed= 1）·P（Ad= 1）=γr·αqd，（1）其中r是结果d的秩，γr和αqd是PBM的参数它们使用EM迭代估计如下[9]：ParClick：一种基于EM的点击模型的可扩展算法WWW394（）下一页（）下一页（）下一页≥{}（）（）下一页·γ2·。1−αqdr+γ3·αqd.（）t迭代MEM迭代表1：本文中使用的符号符号描述P（Er +1 = 1）= P（Er = 1）·..1−αqdr·γ1+αqdR中国（5）Rq用户d文件r文档的等级α吸引参数γ检查参数所有查询会话的集合s查询会话EM算法中x类型参数的更新函数X设置有概念y的集合包含点击模型参数的V集具有所有吸引力参数的V的子集Γ具有所有检查参数的V的子集vi点击模型的参数H vi参数类型vi基于CM EM的点击模型Ti并行任务D Ti与任务Ti关联的数据更新时影响vi的所有参数的集合N任务数量γr（t +1）=1。Φγ。α（t），γr（t），s，（2）∈CCM参数也使用EM在类似于（2）和（3）[9]的多次迭代中估计。4PARCLICK：一种基于EM的点击模型的在本节中，我们将解释通用并行点击模型训练的设计，并介绍其在ParClick中实现的核心方面。我们首先在4.1节中介绍了基于EM的点击模型的通用公式。接下来，我们的设计遵循[13]中概述的PCAM方法，其中解决问题的并行算法分为四个步骤：分区（第4.2.1节），通信（第4.2.2节），聚合（第4.2.3节）和映射（第4.2.4节）。4.1基于EM的通用点击模型通用的基于EM的点击模型CM可以使用参数V = v1，v2，. . . 不同类型的vk，H vi。点击模型通常有m2种不同类型的参数。为例如，PBM具有两种类型的参数（因此，m=2）：吸引力参数（可能是数十亿）和检查参数（例如，10用于网络搜索）。另一方面，CCM具有四种类型的参数（因此，m=4）：类似于PBM，吸引力参数（可能是数十亿）和三种类型的检查参数（每种类型一个）。对于所有基于EM的点击模型，训练过程是相同的：我们对所有查询会话sj∈S进行遍历，并计算任何∈（t+1）|s S qd|s Sqd1.（吨）（t）受影响的参数viV所需的更新当前查询会话sj.计算新估计数的通用方法αqd=|Sqd|s∈Sqd ΦαPBMαqd，γr，s、（3）EM的每次迭代中的模型参数的值如下（注意，例如，Eq.（6）推广了Eqs.（2）和（3））：其中，t是迭代计数，d在图中的秩r处所示的结果v（t+1）=1.ΦH（v）.n（t），sn，nvi∈V，（6）当发出查询q时，查询会话s，S是所有训练集我|Svi|Ivis∈Svi查询会话，并且Sqd是包含查询q和结果d的训练会话的子集，Φγ和ΦαP BM是针对其中vi（t+1）是在t处模型参数vi的新估计值。其中，ΦH（v）是参数的估计函数我PBM的检查和吸引力参数3.2点击链模型（CCM）CCM是一种级联点击模型，即假设用户从上到下扫描搜索结果。与PBM类似，该模型具有吸引力参数;然而，它与PBM的不同之处在于计算结果的检查概率的方式。在CCM中，点击概率可以通过以下公式计算：P（Cd=1）=αqd·P（Er= 1），（4）与PBM不同的是，CCM中假设总是检查排名第一的结果，并且其他等级的检查取决于前一等级因此，对于CCM，根据三种类型的检查参数γ1、γ2、γ3，通过等式（1）计算PEr=1（五）、ParClick：一种基于EM的点击模型的可扩展算法WWW395（）下一页}{|∈⊆||||在[9]中导出的H vi类型的距离，SviS是所有影响v i值的查询会话，以及 =vjvjV，vj被要求更新vi的值是影响vi的一组其他参数（来自先前迭代t）。我们的最终目标是提供一个可扩展的并行算法来训练一个通用的EM为基础的点击模型使用Eq。（六）、接下来描述该并行算法的设计4.2并行化当按顺序训练点击模型时，单个任务需要计算V中的所有参数，对于每个参数vi，在会话的子集SviS上迭代。由于S和V非常大（数十亿量级），传统的顺序训练变得非常缓慢，因此无法扩展到Web搜索等现实场景。为了解决这种缺乏可伸缩性的问题，我们遵循分区-通信-聚合-映射WWWPooya Khandel，Ilya Markov，Andrew Yates和Ana-LuciaVarbanescu396？vi（）（）{|个文件夹|图1：在ParClick中基于PCAM定义任务：（a）分区：每个参数定义一个任务（b）通信：其他任务需要来自不同任务的数据。(c)聚合：最终，每个任务包含多个吸引力和所有检查参数。（d）映射：将每个任务映射到不同的线程，并且每个线程在单个核上执行（PCAM）方法[13]来设计并行算法以训练基于EM的点击模型。在下面的段落中，我们描述了我们在PCAM的每个阶段采取的定义并行任务的具体操作图1显示了通过PCAM5执行的所有步骤。4.2.1PCAM：分区。在PCAM中，分区是指将问题拆分为可以并行执行的任务，即， 具有最小依赖性的任务。我们的通用点击模型（公式 （6））指示可以在迭代t +1中用输入数据的子集SviS和模型参数的子集从上一次迭代中得到，（t）。基于这一基本观点，因此，我们用于点击模型训练的通用并行算法旨在并行计算多个vi参数。一般来说，有两种划分方法：域分解（即，数据驱动的划分，其中计算跟随数据）和功能划分（即，任务驱动的划分，其中数据跟随计算）。对于我们的问题，域分解需要确定一个有效的划分并且，对于每个分区，识别可以利用来自该分区的数据来计算哪些vi参数通过这种方法，计算某些vi参数可能需要访问多个分区，这可能是昂贵的。相反，功能划分需要确定页面的划分rameter计算到任务中，并将所需的数据与每个任务相关联。 在这种情况下，如果多个任务需要相同的数据，则可能需要数据共享和/或复制。对于这两种情况，接下来的两个步骤-通信和聚合-旨在减少非理想分区的影响。在Eq.在等式（6）中，我们选择从功能划分开始，并且我们定义用于计算每个vi的任务Ti。因此，因此，每个任务都需要访问数据D（Ti）= Svivi基于此定义，将存在|V|任务T ={T1，T2，. . . ，T |V|}中。4.2.2PCAM：沟通。 通信阶段的重点是分析所提出的任务之间的依赖关系，也就是说，确定多个任务所需的数据，而这些数据又应该在任务之间进行通信。 对于这种分析，我们将任务分为独立和相关，如下所示：两个任务Ta和Tb是独立的（因此可以并行执行）当且仅当D TaD Tb=，否则依赖。因此，两个独立的任务不共享数据，因此不需要彼此通信或同步。5基于图2.1 [13]如果共享数据对两个任务都可用，则两个依赖任务仍然可以并行执行（例如，共享内存）。然而，这些共享数据仍然需要由两个任务处理，这降低了并行效率（因为比顺序情况下完成了更多的工作）并妨碍了可伸缩性。共享数据越大，其负面的可伸缩性影响就越大。因此，对于ParClick，我们必须识别哪些任务是依赖的，哪些是独立的;对于依赖的任务，我们还必须估计共享的数据量。我们的分析基于参数类型。计算PBM的吸引力参数的新值取决于查询会话、Sqd和所有检查参数，但不依赖于其他吸引力参数。然而，计算检查参数的新值可能需要所有查询S中的会话和一些吸引力参数。CCM也是如此。因此，我们所有的任务都是相互依赖的，并且需要一些数据共享。然而，我们仍然可以通过通信量来分离吸引力和检查之间的参数（以及计算它们的任务），因为在吸引力任务之间共享的数据在量方面是最小的，而在检查任务之间共享的数据要大得多。4.2.3PCAM：聚合。通常，PCAM使用聚合来减少通信量并增加任务粒度。为此，它的目标是将相关任务聚合成更大的任务，这些任务可以相互独立。为了将初始任务T = T1，T2，. . . ，T V，我们的目标是(i) 聚合具有重要数据共享的相关任务，以及(ii) 保留足够数量的任务（以便很好地利用目标机器由于不同的吸引力任务只共享有限数量的检查参数（最多10个），因此它们不是（i）的理想候选者不同的考试任务共享大量的查询数据和吸引力参数，但它们太少，以满足（ii）。因此，我们选择了一种混合解决方案：我们首先通过将所有检查参数复制到子任务中来将所有检查任务聚合到子任务中，然后将每个吸引力任务与子任务合并。因此，需要额外的步骤来在所有任务完成之后计算全局检查参数，这是在所有任务之间执行检查参数的同步但是，通过这种聚合，我们避免了查询会话的任何额外复制。在将初始任务T第一次聚合为T′之后，我们简化了任务的数量与吸引力参数一样多|一|. 对于实际应用中的基于EM的点击模型，|一|可能是在ParClick：一种基于EM的点击模型的可扩展算法WWW397{}N阿吉.（）下一页T′′这使得所有这些任务的管理和同步在任何共享内存机器（以及大多数超级计算机）上都非常低效因此，我们必须通过合并几个现有的任务T′来进一步聚合任务。在此聚合之后，任务Tk"可能会使用更多查询会话来计算更多吸引力参数和相同的检查参数。通过这种聚合，不会创建额外的依赖关系，但是可以随意减少并行执行的任务数量算法1PCAM：聚合可以假设是任务本地的，即，它们需要由单个任务访问因此，我们（实际上）将这些参数分布在线程之间。检查参数首先由每个任务独立估计，然后组合在一个共享的集合中。因此，我们为每个线程保留检查参数的任务本地副本，允许线程独立计算，同步以确保所有任务都计算了它们的检查，并将结果合并到共享检查中。我们使用[14]中定义的屏障实现同步4.3通用EM Click的并行EM1：创建任务T ′ ={T1′，T2′，. . . ，T ′}模型2：对于Ti′∈T′do′|A |在本节中，我们提出了我们的并行EM算法点击模-3：k=π（Ti）（7）或（8）4：将STk′′与STi′5：将ATk′′与ATi′第六章： 端最后一个需要解决的聚合问题是：考虑到计算检查参数所需的同步，任务的负载平衡对于可伸缩性至关重要;计算时间比其他任务长得多的任务将减慢整个计算速度，并直接降低可伸缩性。但是，这些任务的负载平衡并不容易实现：|不同的任务，因为有不同数量的查询|varies over the tasks as there are adifferent number of queryels，并描述每个任务的工作量的具体实现（即，即所谓的线程功能）。正如第二节所解释的那样问题4.2.3，我们有N个任务T ′′ = T1′′，T2′′，. . . ，T ′′. 这些任务将并行启动（第1-cessSTi"估计每个任务VTi“中CM参数的新值。具体地，每个任务Ti“”计算相关联的吸引力参数ATi“”的集合的新估计和针对检查参数TTi“”估计的值的任务本地副本。通过设计（见第4.2节），ATi“”参数不依赖于任何其他ATj“”，ij;因此它们不需要在任务之间同步相反地，检查参数的任务局部估计值ΓT“”需要同步，i在EM的每次迭代后进行计时，以获得会话中的用户单击每个查询的日志 为了在新任务之间获得平衡的工作负载，我们根据算法1中解释的策略π合并任务。基于用户点击日志的统计分布，可以使用不同的策略 在这项工作中，我们采用了两种政策-循环（RR）和最小利用率（MU）-并将它们相互比较。检查参数r。下面我们讨论每个任务（VT"=AT“”T“”）的相应模型参数的估计过程每个并行任务都从初始化模型参数VTi"（第5行，算法2），使得检查参数在RR策略中，我们遍历任务T ′ ={T1′，T2′，. . . ，T ′}在每个任务中，以类似的方式初始化参数在EM的迭代t并依次合并为新的任务：|A|（第6行，算法2），所有模型参数的新估计值用等式2计算。（6）（第7行，算法2）。注意，如所描述的，π（Ti′）= i mod N.（七）只有当所有Ti′具有非常相似的大小时，此策略才能产生平衡的工作负载;然而，在现实中，情况很少如此。到为了解决这个问题，我们还定义了MU策略，在该策略中，我们将T′中的任务重新分配给占用最少的任务，T"={T"，T "，. . . ，T ′}：在第4.2.3节中，计算检查参数的精确估计值需要任务之间的同步为了同步这些参数并获得它们的正确值，每个任务等待，直到所有其他任务在迭代t完成估计并达到4.2.4（第8行，算法2）中所述的同步屏障。然后，每个任务从所有其他任务读取{T（t+1）}（第9行，Algo-1）。1 2N T′）=arg min{|S||k∈{1，2，. . . ，N}}。（八）Th′′Rithm2）。最后，所有的任务都将Γ（t+1）和{Γ（t+1）}组合成Γ（t+1）π（iTk′′如下（第10行，算法2）：Ti′′Th′′MU策略将产生更平衡的任务，同时需要非常有限的额外预处理;因此，处理时间应该与RR策略相似对这些政策的评价将在第5节中进一步讨论。γ（t+1）1 N=|Sγ|i=1（t+1）Ti′′·|STi′′，γ|Σ，<$γ∈Γ，（9）4.2.4 PCAM：映射。最后，我们设计的最后阶段是从理论算法到实际应用的映射。理想情况下，在良好的聚合下，这一步对于实际实现来说是纯技术性的。但是，在此步骤中，应考虑有关机器架构的其他知识，以潜在地改进前一步骤在我们的例子中，我们在多核机器上执行训练因此，我们将每个任务映射到一个不同的线程，并且每个线程在单个核心上执行由于任务计算新的其中，γ（t+1）是检查参数γTi′′由迭代t+1上的第i个任务计算（第7行，算法2），其中对应任务中的查询会话集合影响其值STi′′，γ.训练过程（第6至11行，算法2）继续进行。M次迭代。当训练完成时，每个任务i包含吸引力参数A（T）的一部分和吸引力参数A（T）的本地任务副本。Ti′′检查参数Γ（T）。这些最终估计值，即，吸引力参数独立，吸引力参数？i∈{1，.，N}A（T）和T（T）表示经训练的点击模型CM，我.γWWWPooya Khandel，Ilya Markov，Andrew Yates和Ana-LuciaVarbanescu398Ti′′Th′′×× ×我这与顺序CM相同，因为算法2保留了计算的顺序。算法2用于点击模型训练的并行期望最大化（EM）一曰： parfori=1.. N是否2：估计CM参数（STi′′）启动并行任务第三章： 结束参数4：函数Estimate CMParams（STi′′）表2：本文使用的数据集数据集D1 D10 D50总1,000,00010,000,00050,000,000#查询会话培训800,0008,000,00040,000,000测试111,9531,361,9037,779,226#独特的设计培训342,8102,630,41110,486,900测试20,987215,084931,829训练和测试数据集中的查询会话数，以及5：初始化V（0）：vi（0）= 0。5|vi ∈ VT ′′6：对于t=0到t=M，进行双EM迭代训练和测试数据中唯一查询的数量基线。为了评估可扩展性，我们比较了所有并行版本-7：估计VTi′′使用等式（六）针对PBM和CCM的有效顺序版本的问题。是-8：同步屏障，如4.2.4所述9：h ∈ {1，. . . ，N}，h i：读取Γ（t +1）10：使用等式11更新Γ （ t +1 ）（九）11：结束12：结束功能4.4实现细节我们在C++6中将ParClick实现为多线程应用程序。具体地，估计CM参数的N个任务被实现为线程。 假设不需要吸引力参数的同步，则它们被本地存储在每个线程中，但是检查参数被存储为共享数组，即，它们对于所有线程都是可访问的。为了优化内存使用，我们不会在所有迭代中保留新相反，我们首先计算参数初始化变量，并将它们作为当前值复制到容器中。然后，我们在每次迭代时计算新的估计，并在每次迭代结束时（第10行，算法2），我们将新的估计复制到当前容器中。我们把这一步称为后处理。请注意，我们扩展了并行实现，以涵盖ParClick的评估，但由于空间不足，省略了此实现的细节5评价本节介绍对ParClick多核版本的评估，重点是强大的可扩展性和对越来越大的数据集的支持。5.1实验装置数据集。我们在Yandex相关性预测数据集的三个子集上运行所有实验[26]：D1，D10和D50，分别由1，10和5000万个第一查询会话组成。 训练集由数据集中前80%的记录组成，测试集由剩下的20%组成。类似于点击模型评估的标准实验设置[ 9 ]，我们从每个测试集中删除那些没有出现在相应训练集中的查询表2报告了每个数据集的属性：6该代码可在线获得（不包括链接，以保留双盲评估过程）。由于之前没有基于EM的点击模型的大规模培训工作，这些基线C++版本是在内部实现我们进一步指出，ParClick由于其并行设计和C++实现，比最先进的Python模型（如PyClick）快几个数量级;我们认为这种苹果对橘子的比较不公平，我们在这项工作中不追求它。计算基础设施。我们在一台多核机器上进行实验，该机器具有4插槽，48核英特尔（R）至强（R）金5118 CPU，运行频率为2.30 GHz，内存为256 GB。基线实验在单个核心上运行; ParClick使用2、4、8、16、32和40个线程运行，每个核心一个线程7。目标和评价指标。 我们分析了以下性能方面的ParClick：可扩展性，并行化成本，和存储使用。 我们用于分析的指标是：（M1）以秒为单位的执行时间;（M2）加速，即，顺序处理时间和并行处理时间之间的比率;（1）如4.4中所述，每个IT的参数估计阶段内的计算时间的百分比（ACE）（第7行所花费的时间）、每个IT的同步时间的百分比（ASE）（第8至9行所花费的时间）和每个IT的P处理时间的百分比（APE）;以及（M3）内存占用。有效性点击模型的有效性通常通过计算对数似然或困惑度来评估[9]。 由于所提出的算法2保留了计算顺序，因此不会发生ParClick的有效性降低。为了验证这一说法，我们测量了所有实验的对数似然;我们观察到与每个数据集的标准顺序版本完全相同的对数似然，而不管线程的数量。5.2实验和结果我们进行了2 2 7 3= 84个实验，因为我们测量了2个模型，2个负载平衡策略，3个越来越大的数据集和7个不同数量的线程的执行时间及其组成部分。表3和表4列出了所有结果，包括训练执行时间（以秒为单位）、加速和ACE。我们观察到，使用更多的线程可以提高所有情况都适用于小型和大型数据集。此外，在我们最大的实验中，即，使用D50，ParClick允许23。8和24。7更快7由于机器的配置方式，我们无法将所有48个内核用于单个实验。ParClick：一种基于EM的点击模型的可扩展算法WWW399表3：不同数据集和线程数的PBM的训练时间、加速和ACE线程培训RRMUD1加速RRMUACE [%]RRMU培训RRMUD10加速RRMUACE [%]RRMU培训RRMUD50加速RRMUACE [%]RRMU12242281.01.077.077.42,0792,0411.01.079.579.511,03611,5661.01.083.683.821131141.91.977.177.01,0751,0721.91.980.580.75,4775,5502.02.082.281.1473.366.23.03.466.470.05976033.43.376.976.53,1633,0483.43.780.479.5830337.36.872.869.23172826.57.272.776.61,3561,3518.18.578.580.616181712.112.868.869.715015613.813.073.972.380473813.715.670.675.332131216.618.464.165.311811217.618.066.869.354753620.121.570.972.140121118.019.062.664.110610419.519.567.768.550548421.823.871.674.2表4：不同数据集和线程数的CCM的训练时间、加速和ACE。线程培训RRMUD1加速RRMUACE [%]RRMU培训RRMUD10加速RRMUACE [%]RRMU培训RRMUD50加速RRMUACE [%]RRMU12,2162,2191.01.098.098.022,745 22,7041.01.098.498.4119,408 118,5591.01.098.798.721,1421,1181.92.095.697.111,867 11,1881.92.097.197.958,48458,0142.02.097.798.246356163.53.690.794.56,2156,0623.73.796.296.330,84331,4553.93.896.496.883313136.77.188.895.23,4093,1766.77.189.995.016,33915,7757.37.591.995.61619416811.413.179.892.41,9251,70511.813.384.593.59,9338,40812.014.180.193.23214111115.620.068.289.81,2971,11117.520.475.389.56,2205,55219.221.478.389.54011310019.622.176.088.41,20196018.923.672.994.16,3604,80418.824.768.394.5训练比PBM和CCM的顺序版本，分别。因此，使用ParClick，PBM的训练时间从几个小时大幅减少到几分钟，CCM的训练时间从一天多减少在下面的段落中，我们将更详细地讨论这些结果，重点是我们的评估目标：可伸缩性、并行化成本和内存占用。可扩展性。 有两个维度的可伸缩性要讨论：输入数据缩放（即，我们的算法如何处理增加的输入数据）和强缩放（即，当更多的资源可用于相同的数据集时，我们的算法如何响应）。为了评估输入数据的可扩展性，我们观察到ParClick可以正确处理所有三个数据集。 对于D50（我们分析中最大的数据集），训练CCM的执行时间约为33小时。此外，我们观察到算法的执行时间随着训练数据集的大小线性增加，即，D10和D50的训练大约是D1的这表明我们的算法可以扩展到大型数据集，而不会因并行性而损失任何效率。为了评估强大的可扩展性，我们评估了通过增加可用于训练的线程数时的ParClick。在理想的情况下，随着线程数量的增加，我们应该看到加速的比例增加 图2和图3分别说明了PBM和CCM的观测到的加速。结果表明，ParClick然而，我们看到超过16个线程的收益递减这种减少是由于线程之间同步的成本增加以及后处理的固定开销，随着每个线程的工作减少，后处理的开销变得更加重要。此外，本发明还提供了一种方法，图2：不同线程数的训练加速PBM。图3：不同线程数的CCM训练加速NUMA效应、缓存效应和超线程在限制较大线程的加速方面更为突出。结合起来，WWWPooya Khandel，Ilya Markov，Andrew Yates和Ana-LuciaVarbanescu400这些因素转化为来自增加线程的不太理想的加速增益结果进一步表明，事实上，提供更好的负载平衡（如MU）的分区方案提供了更好的加速，特别是对于更复杂的模型。因此，尽管该方案略微增加了预处理成本，但对于更好的可扩展性，该方案应该是优选的。企业化成本。虽然并行化为训练我们的模型提供了显着的性能增益，但它并不是免费的。并行化的成本可能成为整体应用程序性能的瓶颈，并且最终可能阻碍可伸缩性并大大降低并行应用程序的效率我们评估并行化成本的开销，由于其他任务比计算。因此，ACE是计算资源被用于实际计算的程度的指示，而ASE和APE表示并行化成本。因此，更高的ACE值表示计算资源的更有效利用;然而，它们与加速没有线性关系。增加线程数量通常会导致ACE性能下降，因为更多线程的同步和后处理需要更长的时间。然而，如表3和表4所示，ACE从1个线程减少到40个线程并不显著。更重要的是，ACE随着输入数据集变大而改进（例如，从对于40个螺纹，D1和D50分别为64.1至74.2，MU负载平衡策略）。这强烈表明ParClick对于大型输入数据集是有效的。此外，我们的研究结果还表明，MU在ACE方面始终优于RR为了进一步了解效率损失在哪里，我们还测量了执行同步和后处理所花费的时间，并计算ASE和APE。由于我们的目标是高ACE，因此ASE和APE应尽可能接近零图4显示了在D50上运行的PBM的ACE、ASE和APE，它们具有不同的线程数和负载平衡策略。数据表明，对于PBM实验，APE相对恒定，每次迭代花费约20%的时间。随着使用的线程越来越多，同步时间也会增加，如ASE越大所示。这两个开销阻碍了通过添加更多线程获得的加速收益类似地，图5比较了在D50上运行的CCM的ACE、ASE和APE，这些CCM具有不同的线程数和负载平衡策略。由于CCM比PBM更复杂，ACE在每次迭代中占用的执行时间更大，而APE与之相比微不足道 正如预期的那样，ASE仍然随着线程数量的增