十一、Pinterest Recommender System

  1. 虽然已经有很多关于高级推荐系统及其实际应用的论文发表,但是通常不可能直接构建 state-of-the-art 的推荐系统。最初的产品initial product 必须用一个小的工程团队、有限的计算资源、以及缺乏训练数据来构建,直到推荐系统被启用 bootstrapped 。工业级的推荐系统通常处理包含数十亿个 itemWeb-scale 数据。由于内容是通过用户隐式反馈 implicit user feedback 收集的,因此内容content 通常标记不佳并且有很大噪音noisy 。因此,很多从业者在构建初始系统时选择使用临时的启发式方法 heuristicstrade-off 。但是,系统的进一步增长grow 会使得系统迅速复杂化,从而难以应对接下来的变化。

    在论文 《Related Pins at Pinterest: The Evolution of a Real-World Recommender System》 中,作者给出了在 Related Pins 背景下以独特的机会在三年的时间范围内观察这些问题。Related Pins 的初始版本是在 2013 年推出的,是 Pinterest 首次进入推荐系统的尝试之一。尽管在改善内容发现 content discovery 取得了成功,但是 Related Pins 最初在工程上受到的关注很少。2014 年,Pinterest 上大约 10%pins saved 是通过 Related Pins 发现discovered 的。2015 年,一个小团队开始迭代并进一步开发 Related Pins。现在,Related Pins 通过多个产品界面product surfaces 推动了超过 40% 的保存save 和曝光 impression ,并且是 Pinterest 上的主要发现机制primary discovery mechanisms 之一。论文通过对 Related Pins 的纵向研究,探索了现实世界中推荐系统的挑战。在描述 Pinterest 系统的逐步演变时,作者提出了应对这些挑战的解决方案、trade-off 的理由、以及学到的关键洞察key insights

    现实世界的推荐系统已经作为音乐推荐 music suggestion、图像搜索 image search 、视频发现video discovery、电影发现 movie discovery 。其中很多论文描述了 final system,然而并没有描述如何逐步增量地incrementally 构建系统。《Hidden technical debt in machine learning systems》 描述了现实世界推荐系统面临的很多挑战,我们提供了在 Related Pins 中这些挑战的具体例子,并提出了独特的解决方案。

    • 对于 Related Pins ,我们首先考虑最简单、性价比最高highest-leverage 的产品,从而达到增量式的里程碑incremental milestones 并证明可行性 viability。我们最初的推荐算法由一个简单的候选生成器candidate generator 以及很多启发式规则 heuristic rules 组成。尽管它仅在三周内建成,但是它利用了 user-curated boards 中的强烈信号strong signal 。我们继续添加更多的候选源candidate sources,因为我们发现了覆盖率 coverage 和召回率recall 之间的gap
    • 随着时间的推移,我们引入了 memorization layer 来提高热门的结果popular resultsMemboost 在工程复杂度和计算强度方面都是轻量级的,但是它能显著地利用大量的用户反馈user feedback 。我们不得不考虑位置偏差 position bias ,并以反馈回路 feedback loops 的形式处理复杂性complexity ,但是发现付出的代价是值得的。
    • 接下来我们添加了一个机器学习的 ranking 组件,因为我们认为它具有最大的影响潜力。我们从只有九个特征的基础线性模型开始。当我们发现模型和训练方法的缺点时,我们开始尝试使用更高级的方法。

    每个组件最初都是在工程和计算资源上有很多限制的情况下构建的,因此我们优先考虑了最简单和最高效的解决方案。我们展示了有机增长organic growth 如何导致一个复杂的系统,以及我们如何管理这种复杂性。

11.1 系统介绍

  1. Pinterest 是用于保存saving 和发现 discovering 内容content 的可视化发现工具visual discovery tool 。用户将他们在 Web 上找到的内容另存为 pins,并在 boards 上创建这些 pins 的集合。

    Related Pins 利用这些人类收藏的human-curated 内容基于给定的 query pin 来提供个性化的 pin 推荐。下图给出了 pin 特写视图pin closeup view

    Pinterest 其它几个部分也包含 Related Pins 推荐,包括主页feedhome feed 、访客(身份未验证的访问者)的 pin page 、相关想法related ideasinstant ideas 按钮、电子邮件email、通知 notification、搜索结果 search result 、浏览选项卡Explore tab

  2. Pinterest 上的用户互动user engagement 通过以下操作来定义:

    • 用户通过点击来查看有关 pin 的更多详细信息从而特写closeup 这个 pin
    • 然后,用户可以点击从而访问关联的 Web 链接。如果用户长时间 off-site,那么被视为长按 long click
    • 最后,用户可以将 pin 保存到自己的 board 上。

    我们对推动相关pin 的保存倾向 Related Pins Save Propensity 很感兴趣,它的定义是:保存 Related Pins 推荐的 pin 的数量除以用户看到的 Related Pins 推荐的 pin 的数量。

  3. Pinterest 数据模型data model 中,每个 pin 都是一个带链接link 和描述文本description的图像实例 image instance ,其中图像是通过一个图像签名 signature 来唯一标识的。尽管每个 pin 位于单个 board 上,但是同一个图像可以用于不同 board 上的很多 pin :当 pin 保持到一个新的 board 上时,会创建该 pin 的拷贝。

    pin 信息通常在image signature level 上进行汇总,从而提供了比单个pin 实例相比更丰富的元数据 meta-data (比如pin 粒度的点击量、保存量)。为方便起见,将来对 query pinresult pin 的引用实际上指的是 pin 的集合,该集合中的pin 具有相同image signature

  4. Related Pins 系统包含以下三个主要组件components 。随着时间的推移,这些组件已经被陆续引入到系统中,并且每个组件以各自的方式发生了巨大的演变 。下图给出了我们体系结构的各种快照snapshots ,说明了整个系统以及三个组件的演变 evolution。本文后续部分将更详细地探讨它们的发展。

    • Candidate Generation组件:我们首先将候选集合candidate set(符合Related Pin 推荐的pin 集合)的范围从数十亿缩小到大约 1000 个可能和 query pin 相关relatedpin

      我们已经开发并迭代了几种不同的候选生成器 candidate generators 来做到这一点。

    • Memboost 组件:我们系统的一部分会记住历史上特定queryresultpair 对上的互动。我们描述了在使用历史数据时,如何通过使用点击除以期望点击的方式来解决位置偏见position bias 问题。

      引入记忆会增加带有反馈回路feedback loops 系统的复杂性,但是会显著提高互动 engagement

    • Ranking 组件:我们应用一个机器学习的 ranking modelpin 上,对这些pin 排序从而最大化我们的 Save Propensity 的目标互动指标 target engagement metric 。该模型结合了query 特征、candidate pins 特征、用户画像特征、session 上下文特征、Memboost 信号等特征的组合。

      我们采用了 learning-to-rank 技术,采用历史用户互动user engagement 来训练系统。

11.2 Candidate Generation 的演变

  1. 最初的 Related Pins 系统仅包含一种形式的候选生成 candidate generation:通过抽取经常共现co-occurringpins 来利用 pin-board graph 。这些候选pins 作为推荐直接显示给用户(上图的 (a) )。

    后来我们引入了 Memboostmachine-learned ranking 时,候选生成的问题从 precision 转移到了 recall:生成和 query pin 相关的各种各样diversepins 集合。由于我们发现了覆盖率 coverage 和召回率 recall 方面的差距,这导致我们添加了新的候选源 candidate sources(上图的 (d) )。

11.2.1 Board 共现

  1. 我们主要的候选生成器candidate generator是基于用户收藏的 user-curated boardspinsgraph ,但是随着时间的推移我们改变了这个方法从而产生更相关relevant 的结果并覆盖更多的 query pins

  2. 启发式候选Heuristic Candidates :原始的 Related pins 是在离线 Hadoop Map/Reduce 作业中计算的。我们输入boards 的集合,输出在同一个 board 上共现的 pin pair 对。由于有太多的 pin pair 对,因此对于每个 pin query 我们随机采样这些 pair 对从而为每个pin query 产生大致相同数量的候选。

    我们还基于粗略rough 的文本和类目category 匹配来添加启发式的相关性得分heuristic relevance score 。这个相关性得分是通过检查示例结果example results 来手动调优 hand-tuned 的。

    我们选择该方法是因为它很简单。由于工程资源有限,该方法是由两名工程师在短短三周内实现的。另外,由于人类收藏human-curated board graph 已经是非常强烈的信号,因此该方法被证明是一种相当有效的方法。

  3. 在线随机游走Online Random Walk:我们发现:

    • board 共现co-occurrence 越高候选item 质量越好,如下图所示。

      然而,原始的方法主要是基于启发式得分heuristic score,它并没有试图最大化 board 共现。

    • 我们还注意到,罕见rarepin (仅出现在少量board 上)没有太多的候选item

    为了解决这些局限性,我们通过在线遍历 board-to-pin graph ,在 serving time 生成候选 item

    现在我们使用一个叫做 Pixie 的随机游走服务random walk service 来生成候选itemPixie 完整的描述不在本文讨论范围之内,但是从广义上讲,Pixiepins & boards 二部图bipartite graph 加载到一台具有大存储容量的机器上。二部图的边代表一个 board 关联了一个 pin 。我们根据一些启发式规则heuristic rules 裁剪该二部图,从而在 board 上删除 high-degree 节点和 low-relevance 节点。Pixiequery pin 开始在二部图上进行多次随机游走(大约 100,000 步),并在游走的每一步都有 reset 概率,最终汇总 pin 的访问次数。这样可以有效地计算出二部图上 query pinPersonalized PageRank

    该系统可以更有效地利用 board 的共现,因为高度相关联highly connectedpins 更可能被随机游走访问到。它还可以增加罕见pins 的候选覆盖率candidate coverage,因为它可以检索距离 query pin 好几个hops 的候选item

    pins 的共现代表了 pin-board-pin 的二阶邻近性,而随机游走方法可以检索 pin-board-pin-board-pin 这类的高阶邻近性从而提高罕见 pins 的候选覆盖率。

11.2.2 Session 共现

  1. board 共现在生成候选集时提供了良好的召回recall,但是死板 rigid 的、基于 board 的分组具有固有的缺陷inherent disadvantages

    • boards 通常过于宽松broad,因此board 上的任何 pin pair 对可能仅仅是很微弱地相关。对于生命周期很长的 boards 而言尤其如此,因为 board 的主题 topic 会随着用户额兴趣而漂移drift
    • boards 也可能过于狭窄narrow 。例如,威士忌和用威士忌调制的鸡尾酒可能被安排在不同的、但是相邻的 boards 上。

    这两个缺点可以通过结合用户行为的时间维度temporal dimension 来解决:在同一个会话session 期间保存的 pins 通常以某种方式关联。我们建立了一个名为 Pin2Vec 的额外侯选源 candidate source ,从而利用这些 session 共现 co-occurrence 信号。

    Pin2Vec 是在 d 维空间中嵌入 N 个最热门的 pins 的一种学习方法,目标是将同一个 session 中保存的pins 之间的距离最小化。Pin2Vec 神经网络的架构类似于 Word2Vec。学习问题learning problem 被表述为 N 路分类问题,其中输入和输出均为 Npins 之一,如下图所示。

  2. 为了产生训练数据,我们认为同一个用户在特定时间窗口内保存的 pins 是相关的。每个训练样本都是这样的一对 pins

    给定 pin pair 对的其中一个 pin 作为输入,一个 embedding matrixpin ID 映射到 d 维向量,然后一个 softmax layerembedding 向量映射回预测的输出pin ID 。这个 pair 对的另一个 pin 作为预期的输出,然后我们通过最小化网络的交叉熵损失来训练 embedding 。我们还使用负样本采样从而使得训练过程更简单。

    • 模型是通过 TensorFlow 来构建和训练的,结果得到了 Npins 中每个 pindembedding
    • serving 时,当用户queryNpins 中的某个时,我们通过在 embedding 空间中查找 query pin 最近的邻居来生成候选集。
    • 我们发现,session-based 候选集和 board-based 候选集结合起来会大大提高相关性 relevance 。从概念上讲,session-based 方法以紧凑compact 的向量 representation 捕获了大量用户行为。

11.2.3 补充的候选

  1. 在取得上述进展的同时,出于两个原因,我们开始开发新的候选生成技术:

    • 首先,我们想解决冷启动问题:罕见pins 没有很多候选,因为它们没有出现在很多 boards 上。
    • 其次,在添加了 Ranking 模块之后,我们希望在结果的多样性 diversity 带来更多互动 engagement 的情况下扩大我们的候选集。

    出于这些原因,我们开始利用其它的 Pinterest discovery 技术。

  2. 基于搜索的候选search-based candidates:我们利用 Pinteresttext-based search 来生成候选,其中使用 query pin 的注释annotations (来自于 web link 或者描述descriptioin 的单词)作为 query tokens 。每个热门的 search query 都有 Pinterest Search 提供的预计算的 pin 集合来支持。

    这些基于搜索的候选相对于 基于board 共现的候选而言相关性较低,但是从探索exploration 的角度来看,这是一个不错的折衷trade-off 方案:基于搜索的候选产生了更多样化diversepin 集合,而且这些 pin 集合仍然和 query pin 具有相关性。

  3. 视觉相似的候选visually similar candidates:我们有两个视觉候选源。

    • 如果某个imagequery image 是几乎重复 near-duplicate 的,那么我们将该image 添加到 Related Pins 推荐结果中。
    • 如果没有和 query image 几乎重复的image,那么我们使用 Visual Search 后端基于 query image embedding 向量的最近邻查找lookup来返回视觉相似的 image

11.2.4 分段的候选

  1. 最后我们要解决内容激活问题content activation problem :罕见的pins 不会作为候选pins 出现,因为它们不会出现在很多 board 上。

    Pinterest 开始专注于国际化时,我们希望向国际用户展示更多的以他们自己语言的结果。大部分内容是来自美国的英语。尽管确实存在本地化内容 local content,但是这些内容不是很热门,也没有链接到热门的 pins ,因此不会被其它侯选源来生成。

    为了解决这个问题,我们为上述许多生成技术生成了按本地化分段segmented by locale 的附加 additional 候选集。例如,对于 board 共现,我们将 board-pin graph 的输入集合过滤为仅包含本地化 localepins

    这种方法也可以扩展到存在内容激活问题的其它维度,例如特定于性别gender-speci fic 的内容或者新鲜fresh 的内容。

11.3 Memboost 的演变

  1. 最初的 Related Pins 版本已经获得了大量的互动engagement 。作为从大量互动日志中学习的第一步,我们构建了 Memboost 来记住每个query 的最佳 pins 结果。我们选择在尝试全面学习之前实现Memboost,因为它更轻量级 lightweight ,并且我们直觉上相信它会有效。

  2. 我们最初只是向简单地合并每个结果的历史点击率historical click-through rate。但是,日志数据容易受到位置偏见 position bias 的影响:显示在更前面位置的 item 更容易被点击。下图说明了每个平台platform 上不同 rank 的全局点击率的 bias (排名越小则显示越靠前)。为解决这个问题,我们选择了计算 clicks over expected clicks: COEC

  3. COEC:令 result pin rquery pin q 上获得的总点击量。令 为平台 rank result pin rquery pin q 上获得的总曝光量。每个曝光贡献了一定比例的期望点击expected clicksresult pin rquery pin q 上的期望点击量为:

    其中 为平台 rank 的全局先验global prior 的点击率。

    我们将这些定义扩展到其它互动行为(不仅仅是点击),将这些互动行为的权重设为

    现在 为对所有互动行为泛化的 COEC

  4. Memboost score:为了获得一个 zero-centered score,其中正值和负值分别表示结果比期望多互动多少和少互动多少,我们使用 COEC 的对数。

    另外我们还引入平滑来处理低互动或低曝光的 item 。因此,总体的 Memboost score 为:

    Memboost score 用于调整现有的 pin score,并根据调整后的 score 来排序得到最终结果:

    历史上,Memboost 权重 通过 A/B test 来人工调优hand-tuned ,从而最大化互动engagement 。然而,这种做法会给评分函数带来不良的耦合影响:尝试使用新的 ranker 或者改变评分函数可能会产生更大或更小的初始得分 initial scores,从而无意中改变了 Memboost 权重的相对大小。人工调优的权重对于新的条件condition (系统改变、不同的时间段等等)不再是最优的。

    为了消除这种耦合,我们现在在改变模型时共同训练 Memboost 参数。我们将 Memboost 作为特征, Memboost 的临时变量取值(clicksEclicks 等等)作为特征馈入到基于机器学习的 ranker 中。

  5. Memboost Insertion:有时,已知某些 item 是好的(基于它们的 Memboost scores ),但是由于候选生成器和 ranking sytem 等上游的变化,这些 item 不再出现在候选结果中。

    为了处理这些情况,我们设计了一个 Memboost insertion 算法。该算法将 Memboost score 最高的 top-n item 插入到候选结果中,如果这些item 并未出现在候选结果中。

  6. Memboost 作为一个整体,通过在系统中添加反馈回路 feedback loops ,显著增加了系统的复杂性。从理论上讲,它可以破坏corrupting 或者稀释diluting 实验结果:例如,实验中的正样本可能被挑选出来并泄漏到控制组和对照组。重新评估历史的实验(例如添加了新的模型特征)变得更加困难,因为这些实验的结果可能已经被记住了。

    这些问题存在于任何基于记忆memorization-based 的系统中,但是 Memboost 具有显著的正向效果,因此我们也就接受了这些潜在的不足。

  7. 我们目前正在实验替代 Memboost insertion 的方法。Memboost insertion 会减缓开发速度development velocity ,因为有害harm 结果的实验可能不再显示为负向的 A/B test 结果。而且新的 ranking 方法的试验效果可能被稀释,因为 top 结果可能被Memboost insertion 所主导。 Memboost insertion 也可以无限期地维持候选items ,即使候选生成器不再生成这批候选 items (这批候选 itemsMemboost insertion 产生)。

    一种常见的替代 memorization 方法是将 item-id 作为 ranking 特征。但是,这需要一个大的模型(模型规模和被记忆的 item 数量呈线性关系),因此需要大量的训练数据来学习这些参数。这样的大型模型通常需要分布式训练技术。取而代之的是,Memboost 预先聚合了每个result 的互动统计量engagement statistics,这使得我们能够在单台机器上训练主力 ranking 模型。

11.4 Ranking 的演变

  1. 在引入 Ranking 之前,Candidate GenerationMemboost 已经工作了相当长的一段时间。我们假设下一个最大的潜在提升 potential improvement 将来自于我们在系统中添加一个 ranking 组件,并应用 learning-to-rank 技术。

    第一个 learning-to-rank 模型大幅度提升了 Related Pins 的互动engagement ,使得用户保存save 和点击click 结果提升了 30% 以上。

  2. 在我们的application 中,ranker 在特定query 的上下文中对候选 pins 进行重新排序re-order。其中 query 包括 query pin、浏览的用户、以及用户上下文user context 。这些 query 部分和候选 pin 各自贡献了一些异质heterogeneous 的、结构化structured 的原始数据,例如注释annotations、类目categories、或者最近的用户活动user activity 。如下表所示,给出了ranking feature extractor 中样本可用的原始数据。

    我们定义了很多特征抽取器feature extractors ,这些特征抽取器输入原始数据并生成单个特征向量

    • 某些特征抽取器直接将原始数据拷贝到特征向量中,例如topic 向量和 category 向量。
    • 另一些特征抽取器则计算原始数据的变换,如 Memboost 数据的归一化normalized 或者 re-scaled 的版本。
    • 一些特征抽取器将 one-hot encoding 应用于离散字段 categorical fields,例如性别、国家。
    • 最后,一些特征抽取器计算匹配分match scores,例如 query pincandidate pin 之间的类目向量 category vector 的余弦相似度,或者 query imagecandidate image 之间的 embedding 距离。

    ranking 模型 输入特征向量并产生最终的 ranking score。这个 ranking 模型是从训练数据中学习的,其中训练数据在后文中描述。

  3. 我们的第一个 ranking 系统仅使用 pin 原始数据。随着我们获得了额外的工程能力来构建必要的基础架构,我们将更多数据(如 Memboost 数据和用户数据)引入到 ranking 系统。我们还引入了从用户最近活动recent activities 中抽取的个性化特征,如用户最近的search query

11.4.1 选择

  1. 在构建 ranking 系统时,我们面临三个重大largely 的正交orthogonal 的决策:

    • 训练数据集收集方法training data collection method
    • 学习目标函数learning objective
    • 模型类型model type

    正交指的是决策之间互不影响。

  2. 训练数据集收集:我们探索了训练数据的两个主要数据源:

    • Memboost scores 作为训练数据。从概念上讲,在没有足够日志数据来进行可靠的 Memboost 估计 estimate 的情况下,ranker 可以学习预测 query-result pair 对的 Memboost scores

      即,对于无法从日志数据计算 Memboost scoresquery-result pair 对,可以通过模型来预测。

    • 单个 Related Pins session: 会话session 定义为单个用户以单个 query pinRelated Pins 进行交互的结果。我们可以将这些交互直接作为训练数据的样本。

  3. 模型目标函数:在 《Learning to rank for information retrieval》 中,learning-to-rank 方法大致可以分为 point-wise 方法、pair-wise 方法、list-wise 方法。这些方法之间的主要区别在于:损失函数是一次考虑一个候选item 、两个候选item 、还是多个候选item

    在我们的工作中,我们探索了 point-wise 方法和 pair-wise 方法,如下表所示。

  4. 模型形式formulation :模型的精确precise 形式 form 决定了模型来描述特征和score 之间复杂关系的能力。下表比较了我们使用的两种模型类型model types

11.4.2 决策演变

  1. 下表给出了我们在 Related Pins Ranking 中探索的训练数据、目标函数以及模型的各种组合。

  2. 第一版V1Memboost 训练数据、相关性pair 标签relevance pair labelspair-wise 损失函数、线性 RankSVM 模型。

    在我们的第一版中,我们选择使用 Memboost 数据,因为我们发现 Memboost 数据是高质量的信号:它是在很长一段时间内数百万用户行为的聚合。

    我们为每个query 显式采样 pair,其中:

    • 是针对 query pinMemboost scores 最高pin
    • 是针对 query pinMemboost scores 最低 pin
    • 是从 Pinterest 随机采样的一个热门的 pin ,用于稳定排名(如论文 《Optimizing search engines using clickthrough data》 所示)。

    我们认为,由于候选生成器提供了一定程度的相关性relevance ,因此具有较低 Memboost scorespin 仍然比随机 pin 更相关relevant

    当我们从 Memboost 数据中人工检查 pair 对时,我们发现大约 70% 的时间可以猜测哪个 pinMemboost score 更高。这表明训练数据是相当干净clean 的 。相比之下,从每个user session 中采样的 pair 对的噪声很大,我们无法确定用户保存了两个pin 中的哪一个。

    因此,我们可以使用一个小得多的语料库,并且在几分钟之内在单台机器上训练一个模型。

  3. 第二版V2:转向单个individualRelated Pins sessions

    我们希望使用用户特征和上下文特征,但是使用 Memboost 数据固有地inherently会排出个性化,因为 Memboost 数据是在很多用户上聚合的,从而失去了与单个用户以及 session 上下文的关联。此外,我们发现只有热门的内容才具有足够的交互,从而提供可靠的 Memboost 数据。这些局限性促使我们转向单个 Related Pins sessions

    每个记录loggedsession 均由 query pin、浏览的用户、最近的动作上下文 action contextresult pins 列表a list of result pins来组成。每个 result pin 还具有一个对应的互动标签engagement label(可以为以下之一:仅仅曝光impression、特写closeup、点击click、长点击 long click、保存 save)。

    出于训练的目的,我们裁剪记录loggedpin 集合,按照 rank order 取每个互动的 pin 以及紧紧排在它前面的两个前序的 pins 。我们假设用户可能看到了紧紧排在互动pin 之间的前序pins

    V2 版中,我们继续使用 pair-wise 损失,但是pin relevance pairs 由动作的相对顺序来定义:save > long click > click > closeup > impression only

  4. 第三版 V3:转向一个 RankNet GBDT 模型。

    我们发现,简单的线性模型能够从 ranking 中获得大部分的互动增益engagement gain。但是,线性模型有几个缺点:

    • 首先,它迫使 score 和每个特征的依赖关系为线性的。为了让模型表达更复杂的关系,工程师必须人工添加这些特征的转换(分桶 bucketizing、分区间percentile、数学转换mathematical transformations、归一化normalization)。

    • 其次,线性模型无法添加仅依赖于 query pin 而不依赖于候选 pin 的特征。例如,假设特征 代表一个类似于 query category = Art 的特征,每个候选 pin 将具有相同的特征(因为 query 是同一个),所以对于ranking 结果毫无影响。

      query-specific 特征必须和候选pin 的特征进行手动交叉,例如添加一个特征来表示 query pin category + candidate pin category 。设计这些交叉特征费时费力。

    为避免这些缺点,我们转向梯度提升决策树gradient-boosted decision trees: GBDT

    除了允许对单个特征进行非线性响应外,决策树还固有地考虑了特征之间的交互,这对应于树的深度。例如,可以对推理reasoning 进行编码,如 “如果 query pin categoryArt ,那么视觉相似性应该是更强的相关性信号 relevance signal” 。通过自动学习特征交互feature interactions,我们消除了执行人工特征交叉的需要manual feature crosses ,加快了开发速度。

  5. 第四版V4:转向 point-wise 分类损失、二元标签binary label、逻辑回归 GBDT 模型。

    尽管我们最初选择了 pair-wise learning,但是我们也已经在 point-wise learning 中取得了良好的结果。由于我们在线实验的主要目标指标target metric 是用户保存 result pin 的倾向 propensity ,因此使用包含 closeupsclicks 的训练样本似乎会适得其反,因为这些动作可能不会影响保存倾向save propensity

    我们发现给样本提供简单的 binary 标签(saved 或者 not saved ),并且重新加权 reweighting 正样本来对抗类别不平衡,这在增加保存倾向方面被证明是有效的。将来,我们仍然可以使用不同的 pair 采样策略来实验 pair-wise ranking loss

11.4.3 Previous-Model Bias

  1. 在我们努力改进 ranking 的过程中,我们遇到了一个重大的挑战。因为互动日志engagement logs 用于训练,所以我们引入了直接反馈环direct feedback loop,如论文 《Hidden technical debt in machine learning systems》 所述:当前部署currently deployed 的模型极大地影响了为将来模型future models 生成的训练样本。

    我们直接观察到了这个反馈环的负面影响negative impact 。当我们训练第一个 ranking model 时,日志反映了用户对仅由候选生成器排序的结果的互动。所学的模型被用于对这批候选进行排序。在接下来的几个月里,训练数据只反映了现有模型中排序较高的 pins 的互动(如下图(a) 所示)。

    当我们尝试使用相同的特征和最近的互动数据来训练一个模型时,我们无法击败已经部署的模型。我们认为反馈环带来了一个问题,即训练时 pin 分布和 serving 时的 pin 分布不再匹配。

  2. 为了缓解训练数据中的 previous-model bias,我们为 unbiased data collection 分配了一小部分流量:对于这些请求,我们显示了来自所有候选来源的随机样本,并且没有 ranking 而随机排序。这将训练数据和之前的模型隔离开来(如上图(b) 所示)。

    虽然未排序unrankedresult 质量较低,但是它们为训练新的 ranking model 提供了有价值的数据。为了避免过多降低任何特定用户的体验,每个用户只在一小部分随机query 中获取未排序的 pins 。尽管训练数据的数量被限制在总流量的这一小部分,但是最终得到的模型要比用有偏的数据biased data 训练的模型表现得更好。

11.4.4 衡量指标

  1. 能够探索这些不同选项的一个重要step 是能够快速迭代。测试变更效果的金标准gold standard 是在线 A/B test 实验,其中我们主要根据 save propensity 来评估 ranking

    所有的变更都要经过在线实验,但是在线 A/B test 通常需要几天或者几周的时间来收集数据。我们认为,通过离线评估来马上测试变更效果从而近似approximate 不同模型的性能是有帮助的。在这个过程中,我们重复使用了很多训练数据生成器来采样每个 Related Pins sessions,但是选择了一个紧跟着训练日期的不同日期范围、以及一个和训练采样策略稍微不同的采样策略。对于每个session,我们使用被测模型对用户实际看到的pins 进行重新打分rescore,然后度量score 和记录的用户行为之间的一致性。

  2. 我们已经尝试了多种度量方法,包括 normalized discounted cumulative gain: NDCGPR AUC

    为了确定这些离线指标在多大程度上预测了在线 A/B test 影响,我们检查了我们过去几次 ranking model 变更的结果。我们检查了通过离线评估预测差异的方向和大小,并将其与实际实验结果进行比较。我们发现:PR AUC 指标对于 A/B test 实验中的 closeupsclick-throughs 具有极强的预测性,但是我们很难用离线评估来预测 save 行为。

    目前,我们将离线指标用作健全性检查sanity check 和潜在影响potential impact的粗略估计rough estimation

11.4.5 Serving 架构

  1. Related Pins 在峰值负载下每秒可以处理数万个query。为了处理这种规模,我们利用了几个现有的 Pinterest 系统。

  2. 我们的第一版 pin ranking 是在离线的 Map-Reduce 作业中预计算pre-computed的,并由 Terrapin 提供服务(这是一个不可变的 key-valuelookup service )。这需要大量的 Map-Reduce 作业来为每个 querycandidatejoin 原始数据、计算特征、并对 item 进行打分。

    由于集群的限制,我们一次只能对几百万个 query 进行rank,从而覆盖了 50% 的用户 query 。我们通过一次在不同的segments 上运行 reranking 作业并合并结果来 scale up,但是这种方法本质上inherently 无法在合理reasonable 的时间内提供完全覆盖。

    离线排序也显著降低了开发速度:每个变更模型的实验(特征开发、训练数据变更)都需要离线重新排序reranking 所有的 query,这是一个耗时的过程。

  3. 为此,我们转向在线 ranking serving systempin 的原始数据存储在叫做 RealPin 的分片shardedkey-value store 中,通过image signature 作为key

    为了执行ranking,我们将一个请求request 和计算特征和score 所需的候选pins 列表、其它原始数据组装assemble 在一起:query pin 原始数据(从 RealPin 检索到)、离线的用户原始数据(从 Terrapin 而来)、最近的用户活动(从一个叫做 UserContextServiceservice 而来)。

    • RealPin root server 将请求复制到 RealPin leaves server,将合适的候选子集路由到每个leaf server
    • leaf server 在本地检索 pin 原始数据,并调用我们自定义的特征抽取器custom feature extractorscorer
    • leaf server 发送 top 候选以及相应的 scoreroot server,然后由root server 收集名返回全局的 top 候选集。

    我们选择了这种 serving 架构来提高数据局部性 data locality 。基于 Hadoop 的系统在每次query 时都需要传输大量的pin 原始数据。我们还看到,由于 pin 原始数据的传输,其它的 online pin scoring 系统受到网络的限制。通过将计算下推到存储候选pin 原始数据的节点,可以避免大量的数据传输。

11.5 挑战

  1. Changing Anything Changes Everything:根据《Hidden technical debt in machine learning systems》,机器学习系统固有地会纠缠信号tangle signals。输入从来都不是真正独立的,这就产生了 Changing Anything Changes Everything: CACE 原则:系统的一个组件可以针对系统的现有状态进行高度优化。改进另一个组件可能会导致整体性能下降。这是一个 system-level 的局部最优点 local optimum,可能会使得进一步的进展变得困难。我们的通用解决方案是为每个实验联合 train/automate 尽可能多的系统。

    我们提供了一些例子,这些例子说明了在我们的简单推荐系统中出现的这一特殊挑战,以及我们的缓解措施。

    • 例子一:在我们的推荐系统 pipeline 的各个阶段中使用了很多超参数。回想一下,我们使用手动调优hand-tuned的权重对 Memboost 进行调优,并通过耗时耗力的 A/B test 来进行优化。随着系统其它部分的改变,这些很快就过时了。联合训练 Memboost 权重避免了这个问题。同样地,ranking learner 也有需要调优的超参数。

      为了避免导致超参数变得次优 sub-optimal的其它变更,我们实现了一个用于自动调参automated hyperparameter tuning 的并行系统。因此,我们现在可以在每次变更模型时调优超参数。

    • 例子二:对原始数据的 “改进” 可能会损害我们的结果,因为我们的下游模型是基于旧的特征定义进行训练的。即使修复了一个 bug(例如在计算 pin 的类目向量时),我们现有的模型将依赖于有缺陷的特征定义,因此这个 fix 可能会对我们的系统产生负面影响。如果变更来自于另一个团队,这尤其会成为问题。在《Hidden technical debt in machine learning systems》中,这被称作不稳定的数据依赖unstable data dependency

      目前,我们必须使用更新后的原始数据手动重新训练我们的模型,同时将新模型和更新后的原始数据部署到生产环境中。除了耗时之外,这个解决方案也不太理想,因为它需要我们了解上游的变化。理想情况下,我们将自动对我们的模型进行连续的再训练 continual retraining,从而将上游数据upstream data 的任何变化考虑进来。

    • 例子三:最后,我们经历了 candidate generationranking 之间复杂的相互依赖关系。模型变得和训练数据的特点相协调。例如,变更或引入一个 candidate generator 会导致 ranker 的恶化,因为训练数据的分布不再和 serving 时的 ranking 数据的分布相匹配。这是我们在训练数据收集中看到的一个问题。

      如果引入一个 candidate generator 无法提高性能,那么如何确定这是由于 candidate generator 性能较差、还是由于ranker 并没有针对这个 candidate generator 的候选上训练过?

      我们目前的解决方案是:在用新训练的模型运行实验之前,将candidate generator 得到的候选插入训练集一段时间。

      这个问题强调了尽可能简化系统的必要性,因为可能的非预期交互unintended interactions 的数量随着系统组件的数量而迅速增加。

  2. 内容激活:有大量的内容没有互动量,但是这些内容可能是潜在相关potentially relevant 的和高质量 high quality 的。每天都有数百万张新图像上传到 Pinterest。此外还有大量的 dark 内容,这些dark 内容是高质量的,但是很少出现。

    平衡fresh or dark 内容和完善的、高质量的内容,这代表了经典的探索和利用问题 explore vs exploit problem 。这是 Pinterest 的一个开放问题。我们深入探讨了如何针对本地化localization 的情况解决内容激活 content activation 问题。

    由于 Pinterest 是一种日益国际化的产品,因此我们特别努力确保国际用户能够看到他们自己语言的内容。出于两个主要原因,使得Related Pins 本地化很困难:

    • 首先,一开始就没有多少本地化的候选,因为这些本地化内容并没有出现在很多 board 上。
    • 其次,本地化内容的历史互动要少得多,这导致我们的模型对本地化内容的排名更低,即使我们确实有本地化的候选。

    我们尝试了几种方法来解决这些问题,最终能够将本地化 result的占比从 9% 增加到 54% ,如下图所示。

    • Local pin swap:对于我们生成的每个相关relatedpin,我们检查是否存在具有相同图像的本地化替代local alternative 。如果存在,那么我们将result pin 换本地化替代的pin

      结果,我们增加了本地化的pin 曝光、以及本地化的 pin save,而不会改变结果的相关性。

    • Local pin boost:当返回的候选集中存在和浏览者相同语言的 pin (即本地化的pin )时,我们试图人为地将本地化的pin 的排名提升到 result set 中更高的位置。

      事实上证明这并不是特别有效,因为此时的候选集并没有包含很多本地化的 pin,因此该解决方案的覆盖率coverage 较低。

    • Localizing candidate sets:我们修改了 board-based 的候选生成方法,从而在 pin 采样之前对语言进行过滤,并生成针对每种语言的 segmented corpus

      此外,为了增加对这些本地化的 pin 的曝光,我们选择以不同的比例将本地化的候选混合到 result 中。

十二、DLRM

  1. 个性化personalization 和推荐系统 recommendation systems 目前已经被部署在大型互联网公司的各种任务中,包括广告点击率预估CTR prediction 和排序 ranking。尽管这些方法已经有很长的历史,但是直到最近这些方法才包含神经网络。有两个基本观点primary perspectives 有助于个性化和推荐的深度学习模型的架构设计architectural design

    • 第一种观点来自推荐系统。这些系统最初采用内容过滤content filtering,其中一群专家将产品划分为不同的类目categories,用户选择他们喜欢的类目,而系统根据用户的偏好进行匹配。

      该领域随后发展为使用协同过滤collaborative filtering,其中推荐是基于用户历史的行为,例如对item 的历史评分。

      邻域 neighborhood方法通过将用户和item 一起进行分组grouping 从而提供推荐。

      潜在因子latent factor方法通过矩阵分解技术从而使用某些潜在因子来刻画用户和item

      这些方法后来都取得了成功。

    • 第二种观点来自预测分析 predictive analytics,它依靠统计模型根据给定的数据对事件的概率进行分类classify 或预测predict

      预测模型从简单模型(例如线性模型和逻辑回归)转变为包含深度网络的模型。为了处理离散数据categorical data ,这些模型采用了 embedding 技术从而将 one-hot 向量和 multi-hot 向量转换为抽象空间abstract space 中的稠密表示dense representation 。这个抽象空间可以解释为推荐系统发现的潜在因子空间space of the latent factors

    在论文 《Deep Learning Recommendation Model for Personalization and Recommendation Systems》 中,论文介绍了一个由上述两种观点结合而成的个性化模型。该模型使用 embedding 来处理代表离散数据的稀疏特征sparse features、使用多层感知机multilayer perceptron: MLP 来处理稠密特征 dense features,然后使用 《Factorization machines》 中提出的统计技术显式的交互interacts 这些特征。最后,模型通过另一个 MLP 对交互作用进行后处理post-processing从而找到事件的概率。

    作者将这个模型称作深度学习推荐模型 deep learning recommendation model: DLRM,如下图所示。该模型的 PyTorchCaffe2 的实现已经发布。

    此外,作者还设计了一种特殊的并行化方案,该方案利用 embedding tables 上的模型并行性model parallelism 来缓解内存限制 memory constraints,同时利用数据并行性data parallelism 从全连接层扩展 scale-out 计算。作者将 DLRM 与现有的推荐模型进行了比较,并在 Big Basin AI 平台上实验了 DLRM 的性能,证明了它作为未来算法实验algorithmic experimentation 、以及系统协同设计system co-designbenchmark 的有效性。

12.1 模型设计和架构

  1. 这里我们将描述 DLRM 的设计。我们将从网络的高级组件high level components 开始,并说明如何以及为什么将它们以特定方式组装assembled 在一起,以及对未来的模型设计产生的影响。

    然后我们描述组成模型的低级算子low level operators 和原语primitives ,以及对未来的硬件和系统设计产生的影响。

12.1.1 DLRM 组件

  1. 通过回顾早期模型,我们可以更容易理解 DLRM 的高级组件。我们避免全面的科学文献综述,而将重点几种在早期模型中使用的四种技术上,这些技术可以被解释为 DLRM 的重要高级组件。

  2. Embedding:为了处理离散数据,embedding 将每个类目 category 映射到抽象空间abstract space 中的稠密表示dense representation

    具体而言,每个 embedding lookup 可以被解释为使用一个 one-hot 向量 (第 位为1、其它位为0,索引 代表了第 个类目 )来获得 embedding table 中的相应行向量 row vector

    其中 为类目总数, 为抽象空间的维度。

    在更复杂的场景中,embedding 也可以表示多个item 的加权组合,其中包含一个 multi-hot 向量的权重:

    其中 : 代表对应的 item 代表这些 item 的权重。

    包含 embedding lookupmini-batch 可以写作:

    其中 为一个稀疏矩阵。

    DLRM 利用 embedding tables 将离散特征映射到稠密表示。然而,即使设计了这些有意义的 embedding 之后,如何利用它们来生成准确的预测?为了回答这个问题,我们回到潜在因子方法latent factor methods

  3. 矩阵分解Matrix Factorization:回忆一下,在推荐问题的典型公式中,我们得到了对某些item 进行评分的某些用户的集合 。其中,集合 由元组 索引组成,表示第 个用户在第 item 上已经评分。我们用向量 来表示representitem 、用向量 来表示第 个用户,从而找到所有评分ratings

    矩阵分解方法通过最小化以下公式来求解这个问题:

    其中 为第 个用户在第 item 上的评分。

    ,我们可以将完整的评级矩阵 近似为矩阵乘积:

    其中 为总的 item 数量, 为总的用户数量。

    注意: 可以解释为两个 embedding tables,其中每一行代表潜在因子空间latent factor space 中的 user/item。这些 embedding 向量的内积可以得出对评级有意义的后续预测,这是因子分解机factorization machinesDLRM 设计的关键观察。

  4. 因子分解机Factorization Machine:在分类问题中,我们要定义一个从输入数据点 target label 的预测函数 。例如,我们可以通过定义 来预测点击率click-through rate: CTR,其中 +1 表示点击label-1 表示未点击label

    因子分解机Factorization machines: FM 通过以下定义形式的模型,将二阶交互second-order interactions 融合到带有离散数据的线性模型中:

    其中:

    • 为模型参数,且
    • upper(.) 函数严格选择矩阵的上三角部分。

    FM 和多项式核polynomial kernel 的支持向量机SVM 显著不同,因为FM 像矩阵分解一样将二阶交互矩阵分解为潜在因子latent factor (或 embedding 向量),从而更有效地处理稀疏数据。

    通过仅捕获不同 embedding 向量pair 对之间的交互,FM 显著降低了二阶交互的复杂度,从而产生线性计算复杂度。

    根据原始公式,FM 的算法复杂度为 ,但是经过数学转换之后,计算复杂度降低到

  5. 多层感知机Multilayer Perceptrons:最近机器学习的成功很大程度上归功于深度学习的兴起。其中,最基本的模型是多层感知机multilayer perceptron: MLP ,它是一个由全连接层fully connected layers: FC 和激活函数 交替组成的预测函数prediction function

    其中权重矩阵 bias 向量

    这些方法被用来捕获更复杂的交互interactions 。例如,已经表明:给定足够的参数、具有足够深度depth 和宽度 widthMLP 能够以任何精度precistion 拟合数据。

    这些方法的变体已经广泛应用于各种application ,包括计算机视觉和 NLP。一个具体的例子是神经协同过滤 Neural Collaborative Filtering: NCF 被用作 MLPerf benchmark 的一部分,它使用 MLP 而不是内积来计算矩阵分解中 embedding 之间的交互。

12.1.2 DLRM 架构

  1. 目前为止,我们已经描述了推荐系统和预测分析中使用的不同模型。现在,让我们结合它们的直觉intuitions 来构建 state-of-the-art 的个性化模型。

    令用户和 item 使用很多连续continuous 的、离散categorical 的特征来描述。

    • 为了处理离散特征,每个离散特征将由相同维度的 embedding 向量来表示,从而推广了矩阵分解中潜在因子的概念。
    • 为了处理连续特征,所有的连续特征整体上将被一个 MLP 转换(这个 MLP 我们称之为 bottom MLP 或者 dense MLP),这将产生和 embedding 向量相同维度的 dense representation

    注意:每个离散特征会得到一个 embedding,而所有连续特征整体才能得到一个 embedding

    我们将根据 FM 处理稀疏数据的直觉,通过 MLP 来显式计算不同特征的二阶交互。这是通过获取所有 representation 向量(包括每个离散特征的 embedding 向量、连续特征整体的 representation 向量)之间的 pair 对的内积来实现的。

    这些内积和连续特征 representation (即经过原始连续特征经过 bottom MLP 之后得到的)拼接起来,馈入另一个 MLP(我们称之为 top MLP 或者 output MLP)。最终这个 MLP 的输出馈入到一个 sigmoid 函数从而得到概率。

    我们将这个模型称作 DLRM

  2. 和早期模型的比较:许多基于深度学习的推荐模型使用类似的基本思想来生成高阶项 term 从而处理稀疏特征。例如:Wide and DeepDeep and CrossDeepFMxDeepFM 网络等等,它们设计了专用网络specialized networks 来系统地构建高阶交互 higher-order interactions 。然后,这些网络将它们专用网络和 MLP 的结果相加,并通过线性层和sigmoid 激活函数产生最终的概率。

    DLRM 特别地模仿因子分解机,以结构化方式与 embedding 交互,从而在最终 MLP 中仅考虑 embedding pair 对之间的内积所产生的的交叉term,从而显著降低了模型的维度。我们认为,在其他网络中发现的、超过二阶的更高阶交互可能不一定值得额外的计算代价和内存代价。

    DLRM 和其它网络之间的主要区别在于:网络如何处理 embedding 特征向量及其交叉项 cross-term 。具体而言:

    • DLRM(以及 xDeepFM)将每个embedding 向量解释为表示单个类目category 的单元unit,交叉项仅在类目之间产生。

    • Deep and Cross 这样的网络将embedding 向量中的每个元素视为单元,交叉项在元素之间产生。

      因此,Deep and Cross 不仅会像 DLRM 那样通过内积在不同embedding 向量的元素之间产生交叉项,而且会在同一个embedding 向量内的元素之间产生交叉项,从而导致更高的维度。

12.2 并行性

  1. 现代的个性化和推荐系统需要大型复杂的模型来利用大量的数据。DLRM 尤其包含大量参数,比其它常见的深度学习模型(例如 CNNRNNGAN)多几个数量级。这导致训练时间长达数周或者更长。因此,更重要的是有效地并行化这些模型,以便在实际数据规模上解决这些问题。

  2. 如前所述,DLRM 以耦合的方式coupled manner 处理离散特征(通过 embedding)和连续特征(通过 bottom MLP)。 embedding 贡献了大部分参数,每个lookup table 都需要超过几个 GB 的内存,使得 DLRM 的内存容量和带宽bandwidth代价昂贵。

    • 由于embedding 的太大,因此无法使用数据并行data parallelism ,因为数据并行需要在每个设备上拷贝超大的 embedding。在很多情况下,这种内存限制需要将模型分布在多个设备上,从而满足内存容量要求。
    • 另一方面,MLP 参数在内存中较小,但是却有相当可观的计算量。因此,对于 MLP 而言,数据并行是首选的,因为这样可以在不同的设备上同时处理样本,并且仅在累计更新accumulating updates时才需要通信。

    我们的并行化 DLRM 联合使用模型并行model parallelism和数据并行 data parallelism:针对embedding 使用模型并行、针对 MLP 使用数据并行,从而缓解 embedding 产生的内存瓶颈memory bottleneck,同时并行化 MLP 上的前向传播和反向传播计算。

    由于 DLRM 的体系结构和较大的模型尺寸,因此将模型并行和数据并行相结合是 DLRM 的独特要求。Caffe2PyTorch (以及其它流行的深度学习框架)均不支持这种组合并行性,因此我们设计了一个自定义的实现。我们计划在未来的工作中提供其详细的性能研究。

  3. 在我们的设置setup中,top MLP 和交互算子interaction operator 要求从 bottom MLP 和所有 embedding 中访问部分 mini-batch。由于模型并行已用于在设备之间分布 embedding,因此这需要个性化的 all-to-all 通信。

    embedding lookup 的最后,每个设备都针对 mibi-batch 中所有样本的,将对应的 embedding table 中的embedding 向量驻留在这些设备上。需要驻留的embedding 向量需要沿着 mibi-batch 维度分割,并传送到适当的设备,如下图所示(如黄色embedding 向量都传送到 Device 3 )。

    PyTorchCaffe2 都不提供对模型并行的原生支持,因此我们通过将 embedding 算子显式映射到不同的设备来实现它。然后使用 butterfly shuffle 算子实现个性化的all-to-all 通信,该算子将生成的 embedding 向量适当的分片slice,并将其传输到目标设备 target device 。在当前版本中,这些传输是显式拷贝,但是我们打算使用可用的通信原语(如 all-gathersend-recv)进一步优化这一点。

    下图为用于 all-to-all 通信的butterfly shuffle

  4. 我们注意到,对于数据并行 MLP,反向传播中的参数更新以 allreduce 进行积累accumulated,并以同步synchronous 的方式应用于每个设备上的拷贝参数replicated parameters ,从而确保每个设备上的更新参数updated parameters 在每次迭代之前都是一致consistent 的。

    • PyTorch 中,通过 nn.DistributedDataParallelnn.DataParallel 模块启用数据并行,这些模块在每个设备上拷贝模型并插入allreduce 以及必要的依赖。
    • Caffe2 中,我们在梯度更新之前人工插入 allreduce

1.3 实验

  1. 为了衡量模型的准确性accuracy、测试模型的整体性能、并描述各个算子operator 的特征,我们需要为DLRM 创建或获取一个数据集。

    我们提供了三种类型的数据集:随机数据集random dataset、人工合成数据集synthetic dataset、公共数据集public dataset 。从系统的角度来看,前两个数据集可用于试验模型。具体而言,它允许我们通过动态生成的数据来试验不同的硬件属性和瓶颈,同时消除对数据存储系统的依赖。后者允许我们对真实数据集进行实验,并度量模型的的准确性accuracy

    • 随机数据集:回忆一下,DLRM 接受连续continuous 特征和离散categorical 特征作为输入。

      • 对于连续特征,可以通过使用 numpy.random packagerand 或者 randn 调用具有默认参数的均匀分布或正态分布(高斯分布)生成随机向量来建模。 然后可以通过生成一个矩阵来获得一个 mini-batch 的输入,其中矩阵的每一行代表 mini-batch 中的一个样本。

      • 对于离散特征,我们需要确定给定的的 multi-hot 向量中有多少个非零元素。benchmark 允许非零元素数量是固定的、或者是 1~k 范围内的一个随机数。

        然后,我们生成相应数量的整数索引,数量范围在 1~m 范围内,其中 membedding 矩阵 的行数。

        最后,为了创建一个 mini-batchlookup,我们拼接上述索引,并用lengthsCaffe 中的 SparseLengthsSum)、或者 offsetsPyTorch 中的nn.EmbeddingBag)来描述每个单独的 lookup

    • 人工合成数据集:有很多理由支持对应于离散特征的索引的自定义生成。例如,如果我们的application 使用一个特定的数据集,但出于隐私的目的我们不愿意共享它,那么我们可以选择通过索引分布来表达离散特征。这可能会替代联邦学习federated learning 等应用于 application 中的隐私保护技术。此外,如果我们想要测试系统组件system components,例如研究内存行为memory behavior,我们可能希望在合成的 trace 中捕获原始 trace 访问的基本局部性fundamental locality

      让我们说明如何使用合成数据集。假设我们有索引的 trace,这些索引对应于某个离散特征的所有 embedding lookup 轨迹。我们可以在这个 trace 中记录去重访问unique accesses 和重复访问repeated accesses 之间的距离频次,然后生成合成 trace。具体生成算法参考原始论文。

    • 公共数据集:Criteo AI Labs Ad KaggleCriteo AI Labs Ad Terabyte 数据集是公开的数据集,由用于广告点击率预测的点击日志组成。

      每个数据集包含 13 个连续特征和 26 个离散特征。通常,连续特征使用简单的对数变换 log(1+x) 进行预处理。离散特征映射到相应的 embedding index,而未标记的离散特征映射到 0 或者 NULL

      • Criteo Ad Kaggle 数据集包含 7 天内的 4500 万个样本,每天的样本量大致相等。在实验中,通常将第 7 天拆分为验证集和测试集,而前面6 天用作训练集。
      • Criteo Ad Terabyte 数据集包含 24 天的样本,其中第 24 天分为验证集和测试集,前面 23 天用作训练集。每天的样本量大致相等。
  2. 模型配置:DLRM 模型在 PyTorchCaffe2 框架中实现,可以在 Github 上获得。模型分别使用 fp32 浮点数作为模型参数,以及 int32(Caffe2)/int64(PyTorch) 作为模型索引。实验是在 BigBasin 平台进行的,该平台具有双路 Intel Xeon 6138 CPU @ 2.00GHz 以及 8Nvidia Tesla V100 16GB GPUs

  3. 我们在 Criteo Ad Kaggle 数据集上评估了模型的准确性accuracy,并将 DLRMDeep and Cross network: DCN 的性能进行了比较,后者没有进行额外的调优。我们和 DCN 进行比较,因为它是在相同数据集上具有综合结果comprehensive results 的少数模型之一。

    • DLRM 既包含用于处理连续特征的 bottom MLP(该 bottom MLP 分别由具有 512/256/64 个节点的三个隐层组成),又包括top MLP (该 top MLP 分别由具有 512/256 个节点的两个隐层组成)。
    • DCN 由六个 cross layer 和一个具有 512/256 个节点的深度网络组成。embedding 的维度为 16

    这样产生的 DLRMDCN 两者都具有大约 540M 的参数。

    我们使用 SGDAdagrad 优化器绘制了两个模型在完整的单个 epoch 内的训练准确率(实线)、验证准确率(虚线)。我们没有使用正则化。

    可以看到:DLRM 获得了稍高的训练准确率和验证准确率,如下图所示。我们强调,这没有对模型的超参数进行大量的调优。

  4. 为了分析我们模型在单设备上的性能,我们考虑了一个具有8 个离散特征、512 个连续特征的模型。每个离散特征都通过一个包含 1M 个向量的 embedding table (即类目总数有1M )进行处理,向量维度为 64。而连续特征被组装assembled 为一个 512 维的向量。bottom MLP 有两层,而 top MLP 有四层。我们让具有 2048K 个随机生成样本的数据集上分析了该模型,其中 mini-batchbatch size = 1K

    Caffe2 中的这个模型实现在 CPU 上运行大约 256 秒,在 GPU 上运行大约 62 秒,每个算子的分析如下图所示。正如预期所示:大部分时间都花在了执行 embedding lookup 和全连接层上。在 CPU 上,全连接层占了很大一部分计算,而 GPU 上全连接层的计算几乎可以忽略不计。

十三、Applying Deep Learning To Airbnb Search

  1. Airbnbhome sharing platform 是一个双边市场,其中房东host 可以出租他们的空间(称作listings ),以供来自世界各地的潜在租客guest 预订。典型的预订开始于租客在 airbnb.com 上搜索特定地理位置的房屋。search ranking 任务是从库存中的成千上万个listing 中挑选一个有序的 listing 列表来响应租客。

    search ranking 的第一个实现是手动制作的评分函数scoring function 。用梯度提升决策树gradient boosted decision tree: GBDT 模型代替手动评分函数是 Airbnb 历史上房屋预订量方面最大的改进之一,随后还有多次成功的迭代。在线预订量的收益最终饱和,其中很长一段时间的实验都是中性的(即没有提升)。这为尝试对系统进行全面改造提供了时机。

    从这一背景出发,论文 《Applying Deep Learning To Airbnb Search》讨论了作者将互联网上的一个大规模搜索引擎之一切换为深度学习的经验。本文针对是拥有机器学习系统、并开始考虑神经网络的团队。论文的目的并不是推进前沿的、新的建模技术,而是讲述了如何将神经网络应用于现实产品。

    • 首先,论文对模型体系结构随着时间的演变进行了总结。
    • 然后,论文给出了特征工程feature engineering 和系统工程 system engineering 的注意事项。
    • 最后,论文描述了一些工具和超参数探索。
  2. Airbnbsearch ranking 模型是模型生态系统的一部分,所有这些模型都有助于决定向租客展示哪些listing 。这些模型包括:预测房东接受租客预订请求可能性的模型、预测租客将旅行体验评为五星好评5-star的概率的模型等等。论文目前的讨论集中在这个生态系统中的一个特定模型上,并且被认为是排序难题ranking puzzle 中最复杂的一块。这个模型负责根据租客预订的可能性来对可用的 listing 进行排序。

    典型的租客搜索会话search session 如下图所示。

    • 租客通常会进行多次搜索,点击一些 listing 从而查看它们的详情页。
    • 成功的 session 以租客预订一个listing 而结束。

    租客的搜索以及他们和产品的交互被作为日志而记录下来。在训练期间,新模型可以访问交互日志,也可以访问产品中之前使用的模型。新模型被训练从而学习一个评分函数,该函数将日志中预订 listing 的曝光分配到尽可能高的排名。

    然后,新模型在 A/B test 框架中进行在线测试,从而查看新模型和当前模型的对比,看看新模型是否可以实现统计意义上显著的预订量提升。

13.1 模型演变

  1. 我们向深度学习的转变不是原子atomic 操作的结果,而是一系列迭代改进的最终结果。

    • 下图 (a)显示了我们的主要离线指标 normalized discounted cumulative gain: NDCG 的相对提升,其中预订listing 的曝光 impression 被分配为相关性1.0、其它listing 的曝光被分配为相关性 0.0X 轴描述了模型及其投入生产的时间。
    • 下图 (b) 显示了模型在线预订量的相对增长。

    总体而言,这代表了 Airbnb 上最有影响力的机器学习应用之一。以下各节简要描述了每个模型。

  2. Simple NNAndrej Karpathy 对模型架构有一些建议:不要成为英雄don’t be a hero 。在 “我们为什么不能成为英雄?” 的驱动下,我们从一些复杂的自定义架构开始,结果却被它们的复杂性淹没,最终浪费了很多时间。

    我们最终想方设法上线的第一个体系架构是具有ReLU 激活的、简单的单隐层(32 个神经元)神经网络NN 。事实证明该神经网络和 GBDT 相比,预订量指标是中性neutral 的(即效果既不正向、也不负向)。

    NNGBDT 模型具有相同的特征,其训练目标也和 GBDT 保持不变:最小化 L2 回归损失regression loss,其中预订 listing 的效用utility 分配为 1.0、未预订 listing 的效用分配为 0.0

    整个练习exercise的价值在于,它验证了整个 NN pipeline 已经准备就绪,并且能够为实时流量提供服务。稍后在特征工程和系统工程部分讨论该 pipeline 的具体细节。

  3. Lambdarank NN:不是英雄not being a hero 让我们有了一个开始,但没有走很远。最终我们及时的将 Karpathy 的建议调整为:在开始的时候不要成为英雄don’t be a hero, in the beginning

    我们的第一个突破是将Simple NNLambdarank 思想相结合。在离线时,我们使用 NDCG 作为主要指标。Lambdarank 为我们提供了一种直接针对 NDCG 优化 NN 的方法。这涉及为Simple NNregression based 公式的两个关键改进:

    • 转向 pairwise 偏好公式,其中预订者看到的listing 被用于构建 pairwise{booked listing, not-booked listing} ,从而作为训练样本。在训练期间,我们将预订 listing 和未预订listing 之间得分差异的交叉熵损失最小化。
    • 通过交换组成该pair 对的两个listing 的位置position而导致的 NDCG 差异,从而加权每个 pairwise 损失。这使得预订listing 的排名优化rank optimization 朝向搜索结果列表的头部,而不是底部。例如,把预订listing 的排名从位置2 提升到 1,将优于把预订listing 的排名从位置10 提升到 9

    下面给出了 TensorFlow 中的部分实现,尤其是如何对 paiwise loss 进行加权:

  4. Decision Tree/Factorization Machine NN:虽然目前服务于生产流量的主力排序模型是神经网络,但是我们仍然在研究其它模型。值得一提的模型有:

    • GBDT 模型,其中使用使用替代方法对搜索进行采样从而来构建训练数据。
    • 因子分解机factorization machine:FM 模型,它通过将 listingquery 都映射到一个 32 维的空间,从而预测一个 listing 在给定 query 的情况下被预订的概率。

    这些研究search ranking 问题的新方法揭露了一些有趣的东西:尽管这些模型在测试数据上的性能和神经网络相当,但是它们排名靠前uprankedlisting 却大不相同。

    受到 《Deep & Cross Network for Ad Click Predictions》 这样的神经网络体系架构的启发,新模型试图结合所有三种模型(GBDT 模型、FM 模型、NN 模型)的优势:

    • 对于 FM 模型,我们将最终预测作为特征纳入NN 模型。
    • 对于 GBDT 模型,我们将每棵树激活的叶节点的索引作为离散特征纳入 NN 模型。

    下图给出了一个概览。

  5. Deep NNDeep NN 模型的复杂性是惊人的,而且 《Hidden Technical Debt in Machine Learning Systems》 中提到的一些问题开始出现。在我们的最后一次飞跃中,我们能够通过简单地将训练数据扩展 10 倍,并切换到具有两层隐层的 DNN 来消除所有这些复杂性。

    Deep NN 网络的典型配置:

    • 一个输入层input layer。其中,在将离散特征扩展到 embedding 之后,输入一共有 195 个特征。
    • 第一个隐层 hidden layer。其中,该层具有 127 个全连接的 ReLU 激活的神经元。
    • 第二个隐层 hidden layer。其中,该层具有 83 个全连接的 ReLU 激活的神经元。

    馈入 DNN 的特征大部分是简单的 listing 属性,诸如价格、设施amenities、历史预订量等等。这些特征通过最少的特征工程来提供。除此之外,还包括从其它模型输出的特征:

    • 启用了智能定价Smart Pricing 功能的 listing 价格,该特征由专门的模型提供。
    • 候选 listing 和用户历史查看listing 的相似度similarity,这是基于co-view embedding 来计算得到。

    这些模型利用了不直接隶属于 search ranking 训练样本的数据,为 DNN 提供了额外的信息。

    为了更深入地了解 DNN,我们在下图中绘制了它的学习曲线 learning curve。我们在训练集和测试集上对比了 NDCG ,其中训练集有 17 亿的 pair 对。

    可以看到:我们能够弥合close 训练集和测试集之间的泛化距离 generalization gap

  6. 我们能否跳过演变evolution 的所有阶段直接启用 DNN?我们试图在追溯部分中回答这一问题。

    顺便说一句,虽然 DNN 在某些图像应用上取得了人类水平的性能,但我们很难判断我们在类似的比较中处于什么位置。问题的部分原因是,目前尚不清楚在 search ranking 问题中如何定义人类水平的性能。通过浏览日志信息,我们很难准确地判断哪些 listing 将会被预订。我们在日志中找不到客观的事实,只能根据租客的预算budget 和口味 tastes进行tradeoff ,而租客的口味大多数情况下还是看不到的。一些学者指出,即使是对于熟悉的shopping items,也很难进行人工评估。对于我们的 application,由于库存的新颖性novelty,这些困难将进一步加剧。

    说到困难,接下来我们讨论一些鲜为人知的事情:失败的尝试。

13.2 失败的模型

  1. 上一节中介绍的一个成功的 launch 后又接着另一个成功的launch 的叙述并没有讲出完整的故事。现实中失败的尝试比成功的尝试更多。复述每一次失败的尝试比较耗时,所以我们选择了两个特别有趣的失败来讲述。这些模型很有趣,因为它们说明了一些外部非常有效和受欢迎的技术,但是内部使用时可能会失效。

  2. Listing IDAirbnb 上的每个 listing 都有相应的唯一IDNN 提供的一个令人兴奋的新能力是使用这些 listing id 作为特征。想法是使用 listing id 作为 embedding 的索引 index ,这使得我们能够学习每个 listing 的向量 representation,从而编码 listing 独有的属性property

    我们之所以兴奋,是因为其它application 已成功地将如此高基数cardinality 的离散特征映射到 embedding,例如在 NLP application 中学习 word embedding 、在推荐系统中学习 video id embeddinguser id embedding

    但是,在我们尝试的不同变体中,listing id 大多数会导致过拟合。下图绘制了一次这类尝试的学习曲线,我们看到 NDCG 在训练集上有显著提升,但是在测试集上却没有任何改善。

    这种成熟的技术在 Airbnb 上失败的原因是由于底层市场underlying marketplace 的某些独特属性propertyembedding 需要每个 item 有大量数据才能收敛到合理的值。

    • item 可以无限地重复时,例如在线视频或语言中的单词,那么 item 拥有的用户交互数量也没有限制。为 item 兴趣获取大量的数据相对容易。
    • 另一方面,listing 受到物理世界的限制。即使是最受欢迎的 listing,一年最多也就可以预订 365 次。平均每个listing 的预订量要少得多。这一基础限制 fundamental limitation 生成的数据在 listing-level 非常稀疏。过拟合就是这种限制的直接后果。

  3. 多任务学习Multi-task Learning :虽然预订有物理限制,但是用户对listing 详情页的查看并没有物理限制。下图显示了 listing 的详情页查看量和预订量的比例的分布,预订量通常比查看量稀疏了几个数量级(横轴为查看量和预订量之比,纵轴为listing 数量)。更进一步,我们发现,不出所料,对listing 详情页的长时间观看long view 和预订相关。

    为了解决 listing id 过拟合的问题,我们建立了一个多任务学习模型。该模型使用两个独立的输出层同时预测预订概率和 long view 的概率:

    • 一个以预订 listing 作为正样本来优化损失,从而预测预订概率。
    • 另一个以 long view listing 作为正样本来优化损失,从而预测 long view 概率。

    两个输出层共享一个公共的隐层,如下图所示。更重要的是,listing id embedding 是共享的。背后的想法是,模型能够将 long view 中学到的知识迁移到预订任务中,从而避免过拟合。

    由于 long view 标签的数量比预订标签的数量多几个数量级,因此对预订损失施加了较高的补偿权重,从而保持对预订目标的关注。

    《Beyond Clicks: Dwell Time for Personalization》 所建议的,每个 long view 标签的损失进一步由 log(view_duration) 进行缩放。

    最终在线listing 评分时,我们仅使用预订预测 booking prediction

    但是当在线测试时,该模型大幅增加了 long view,而预订量保持不变。人工检查了具有较高 long viewlisting,我们发现了可能导致这种gap 的几种原因:

    • 这种 long view 可能是由于高端的、但价格昂贵的listing 所驱动(所以用户会停留一段时间来慎重考虑)。
    • listing 的描述太长,且难以阅读。
    • 极其独特、且有时很幽默的 listing
    • 还有一些其它原因。

    同样,正是 Airbnb 市场的独特性,使得 long view 和预订相关,但是也有很大的正交部分(即不相关的部分),这使得基于 long view 来预测预订具有挑战性。更好地理解 listing view 仍然是我们研究的主题。

13.3 特征工程

  1. 我们开始的 baseline GBDT pipeline 具有广泛的特征工程。典型的变换包括计算比率ratio、窗口平均等等。这些特征工程技巧是经过多年实验积累的。然而,目前还不清楚这些特征是否是最好的,或者是否随着市场动态变化而更新。

    NN 的一大吸引力在于引入了特征自动化feature automation:馈入原始数据并让特征工程在以数据驱动的 NN 的隐单元中自动进行。

    然而,本节内容是专门针对特征工程的,因为我们发现让NN 有效工作不仅仅是提供原始数据,也需要特征工程。这种特征工程不同于传统的特征工程:在将特征输入到模型之前,无需人工对特征执行数学计算,而是将重点转移到确保特征符合某些属性properties ,以便神经网络可以自己有效地进行数学计算。

  2. 特征归一化Feature Normalization:在我们第一次训练NN 的尝试中,我们简单地将所有用于训练 GBDT 模型的特征输入到神经网络中。这种情况非常糟糕,损失函数在训练过程中达到饱和,后续的step 没有任何效果。我们将问题追溯到以下事实:特征未能正确地归一化。

    • 对于决策树,只要特征的相对顺序有意义,那么特征的确切数值几乎无关紧要。
    • 神经网络对于特征的数值非常敏感。超出正常特征范围的馈入值可能会导致较大梯度的反向传播。由于梯度消失,这可以使得 ReLU 这类激活函数永久死亡。

    为了避免这种情况,我们确保将所有特征限制在较小的取值范围内,并且大部分分布在 [-1,1] 区间、均值映射到 0 。总的来说,这涉及检查特征,并应用以下两种转换中的任何一种:

    • 如果特征分布类似于正态分布,我们将其变换为:

      其中 为特征均值, 为特征标准差。

    • 如果特征分布类似于幂律分布power law distribution,我们将其变换为:

      其中 median 为特征的中位数。

  3. 特征分布Feature Distribution:除了将特征映射到有限的数值范围,我们还确保大多数特征都具有平滑的分布。为什么要纠结于分布的平滑性smoothness ?以下是我们的一些理由。

    • 发现错误spotting bugs:在处理上亿个特征样本时,如何验证其中一小部分没有 bug?范围检查很有用,但是很有限。我们发现分布的平滑性是发现错误的宝贵工具,因为错误的分布通常和典型的分布形成鲜明对比。

      举个例子,我们在某些地区记录的价格中发现了 bug 。对于超过 28 天的区间,记录的价格是每月价格、而不是每日价格。这些错误在原始分布图上显示为尖峰。

    • 促进泛化facilitating generalization:确切回答为什么 DNN 善于泛化是研究前沿的一个复杂课题。同时,我们的工作知识working knowledge 是基于以下观察:在为我们的 application 构建的 DNN 中,各层的输出在其分布方面变得越来越平滑。下图显示了来自一些样本的最终输出层分布、以及隐层分布。为了绘制隐层的分布,零值被省略,并且应用了 log(1 + relu_output) 转换。

      这些图激发了我们的直觉:为什么 DNN 可以很好地泛化到我们的 application 中。当建立一个基于数百个特征的模型时,所有特征取值的组合空间非常庞大,并且在训练过程中常常会覆盖一定比例特征组合。来自较低层的平滑分布确保了较高层可以正确地对未看过unseen 的值进行插值。将这种直觉一直扩展到输入层,我们尽力确保输入特征具有平滑的分布。

      我们如何测试模型是否在样本上良好地泛化?真正的测试当然是模型的在线性能,但是我们发现以下技术可以作为完整性检查sanity check :将测试集中给定特征上所有的值都缩放(例如将 price 特征缩放为 2 倍或者 3 倍或者 4 倍),然后观察 NDCG 的变化。我们发现,在这些从未见过的price 取值上,该模型的性能是非常稳定的。

      在调试debugged 并应用适当的归一化之后,大多数特征都获得了平滑分布。但是,有少数几个特征,我们不得不进行专门的特征工程。一个例子是listing 的地理位置geo-location,以经度和纬度来表示。下图 (a)(b) 显示了原始经纬度的分布。为了使得分布更加平滑,我们计算的是距展示给用户的地图的中心点的偏移量。如下图 (c)所示,质量似乎集中在中心,因为地图的尾部被zoomed out 了很多。因此,我们使用经度/纬度偏移量的 log() ,从而得到了下图 (d) 的分布。这使得我们能够构造两个平滑分布的特征,如下图 (e)(f) 所示。

      需要明确的是,原始经度/纬度到地图中心的距离变换是有损的多对一函数many-to-one function。因为它可以将多个经度/纬度转换为相同的偏移量。这使得模型可以基于距离属性而不是特定的地理位置属性来学习全局属性。要学习特定于局部地理位置的属性,我们使用了稍后描述的高基数high cardinali离散特征。

    • 检查特征完整性checking feature completeness:在某些情况下,调查某些特征缺乏平滑性会导致发现模型缺失missing 的特征。

      例如,我们有一个 listing 未来已预订天数占available days 的比例作为一个特征(即占用率occupancy),这个特征是listing 质量的信号。背后的直觉是:高质量的 listing 会提前售罄。但是,由于缺乏平滑性,占用率的分布却令人困惑,如下图 (a) 所示。

      经过调查,我们发现了另一个影响占用率的因素:listing 有不同的最低住宿时间minimum required stay 要求,有的会要求最低住宿几个月。因此这些 listing 得到了不同的占用率。但是,我们没有在模型中添加最低住宿时间作为特征,因为它取决于日历并且被认为过于复杂。但是在查看了占用率分布之后,我们增加了 listing 的平均住宿时间作为一个特征。

      在占用率通过平均住宿时间归一化之后,我们可以看到下图 (b) 中的分布。在一个维度中缺乏平滑性的特征可能在较高维度上变得平滑。这有助于我们思考这些维度是否可以应用在我们的模型中。

  4. 高基数离散特征High Cardinality Categorical Features :过拟合的 listing id 并不是我们尝试的唯一高基数离散特征。还有其它尝试,如 NN 的承诺所言,我们用很少的特征工程就取得了很高的回报。一个具体的例子最能说明这一点。

    租客对于城市各个街区neighborhoods 的偏好是一个重要的位置信号location signal 。对于 GBDT 模型,该信息是由一个精心设计的 pipeline 提供的,该 pipeline 跟踪了各个街区和城市的层级分布 hierarchical distribution 。建立和维护该 pipeline 的工作量很大,而且它也没有考虑诸如预订 listing 价格之类的关键因素。

    NN 的世界中,处理这类信息本身就是简单的。我们基于 query 中指定的城市、以及对应于listinglevel 12 S2 cell 创建的一个新的离散特征,然后使用哈希函数将这二者整体映射到一个整数。例如,给定 query “旧金山” 以及位于 Embarcadero 附近的 listing,我们选择 listing 所在的 S2 cell539058204),然后将将 {"San Francisco", 539058204} 哈希映射到 71829521 从而建立我们的离散特征。然后该离散特征被映射到一个 embedding ,接着馈入 NN 。在训练期间,该模型通过反向传播来学习 embedding,该 embedding 编码了在给定城市query 的情况下由 S2 cell 代表的街区的位置偏好location preference

    下图可视化了为 query “旧金山” 学到的各街区的 embedding (通过 t-SNE )。这符合我们对该地区的直觉理解:embedding 值不仅突出了该城市的主要 points of interest: poi ,它还表明了人们更喜欢位于西湾west bay 以南一点的位置,而不是靠近主要交通拥堵桥梁的位置。

13.4 系统工程

  1. 这部分是关于加速训练training 和加速打分scoring 。我们pipeline 的一个quick summary

    • 来自租客的搜索query 命中了一个进行检索retrieval 和评分scoringJava server
    • 这个 server 还生成日志,这些日志存储为序列化的 Thrift 实例。
    • 日志使用 Spark pipeline 来处理从而创建训练数据。
    • 使用 TensorFlow 来训练模型。
    • 使用 ScalaJava 编写的各种工具用于评估模型和计算离线指标。
    • 模型上传到执行检索和评分的 Java server

    所有这些组件都在 AWS 实例上运行。

  2. Protobufs and DatasetsGBDT 模型是以 CSV 格式来提供训练数据的,并且我们重复使用这个pipeline 的大部分,从而使用 feed dict 馈入 TensorFlow 模型。

    乍一看,这似乎不是一个机器学习的问题,并且在我们的优先级清单中是相当低的。但是当我们发现 GPU 利用率接近 25% 时,我们马上警醒了。大部分训练时间都花在解析 CSV 和通过 feed dict 拷贝数据上。我们实际上是在用骡子拖着一辆法拉利。

    重构 pipeline 以产生 Protobufs 训练数据,并使用 Dataset 可以将训练速度提高 17 倍,并将 GPU 利用率提高到大约 90% 。这最终允许我们将训练数据从几周扩展到几个月。

  3. 重构静态特征refactoring static features:我们的很多特征都是很少变化的 listing 属性。例如,地理位置location、卧室数量、便利设施amenities 、租客规则guest fules 等等。将所有这些特征作为训练样本的一部分将产生输入瓶颈input bottleneck

    为了消除这种磁盘流量,我们仅使用 listing id 作为离散特征。所有静态特征都被打包为由 listing id 索引的、不可训练non-trainableembedding 。对于在训练期间发生突变的特征,这需要在少量噪声和训练速度之间进行trade-off

    注意:这个 embedding 就是这些静态特征拼接而成的,因此是不可训练的。

    这个 embedding 常驻在 GPU 内存,消除了每个训练样本数千KB 的数据,这些数据通常是通过 CPU 从磁盘加载的。这种效率使得探索全新类型的模型成为可能,该模型考虑了用户历史交互的数十个listing 的详细信息。

  4. Java NN library:在 2017 年初,当我们开始将 Tensorflow 模型投入生产时,我们发现没有有效的解决方案可以在 Java stack 中对模型进行评分scoring 。 通常需要在 Java 和另一种语言之间来回转换数据,这个过程中引入的延迟latency 对我们而言是一个障碍。

    为了满足严格的搜索延迟要求,我们在 Java 中创建了一个自定义的神经网络评分库。虽然到目前为止这对我们很有帮助,但是我们希望重新讨论这个问题,看看有没有最新的替代方案。

13.5 超参数

  1. 尽管在 GBDT 世界中有一些超参数,如树的数量、正则化等,但是 NN 却将超参数的规模提升到一个新的高度。在最初的迭代中,我们花了大量时间探索超参数世界。调研所有选项和试验组合上的努力并没有给我们带来任何有意义的改进。但是,这个练习exercise 确实让我们对我们的选择有了一些信息,我们将在下面描述。

  2. dropout:我们最初的印象是,dropout 和神经网络的正则化相对应,因此必不可少。然而对于我们的 application,我们尝试了不同的 dropout 形式,所有这些都会导致离线指标略有下降。

    为了理解dropout 和我们的失败,我们目前对 dropout 的解释更接近于一种数据增强技术。当随机性的引入模拟了有效的场景时,这种技术是有效的。对于我们的情况,随机性只能产生无效的场景。

    作为替代方案,我们在考虑特定特征的分布的情况下,添加了人工制作的噪声,从而使得离线 NDCG 降低了大约 1%。但是我们在在线性能方面没有取得任何统计意思上的显著提升。

  3. 初始化initialization:出于纯粹的习惯,我们通过将所有权重和 embedding 初始化为零来开始我们的第一个模型,结果发现这是开始训练神经网络的最差的方法。在研究了不同的技术之后,我们目前的选择是对网络权重使用 Xavier 初始化,对 embedding 使用 {-1 ~ +1} 范围内的均匀随机初始化。

  4. 学习率 learning rate:这里面临着各种各样的策略,但是对于我们的 application,我们发现很难使用默认的设置来改善 Adam 的性能。当前,我们使用了 LazyAdamOptimizer 变体,我们发现使用 large embedding 训练时该变体会更快。

  5. batch sizebatch size 的变化对于训练速度有着显著影响,但是对于模型本身的确切影响却难以把握。我们发现最有用的指南是《Don’t Decay the Learning Rate, Increase the Batch Size》 。但是我们并没有完全遵守该论文的建议。在 LazyAdamOptimizer 解决了学习率问题之后,我们选择了 200 的固定 batch size,这似乎对当前模型有效。

13.6 特征重要性

  1. 一般来说,特征重要性的估计和模型的可解释性interpretability 是神经网络不擅长的一个领域。评估特征的重要性对于确定工程工作的优先级和指导模型迭代是至关重要的。

    NN 的优势在于找到特征之间的非线性相互作用。当理解特定特征扮演了什么角色时,这也是一个弱点,因为非线性相互作用使得很难孤立地研究任何特征。接下来,我们讲述解释神经网络的一些尝试。

  2. 分数分解 Score Decomposition:在 NN 的世界中,试图了解单个特征的重要性只会导致混乱。我们第一个朴素的尝试是获取网络产生的最终得分,然后尝试将其分解为来自每个输入节点input node 的贡献。

    在查看了结果之后,我们意识到这个想法存在概念上的错误:没有一种干净clean 的方法来区分一个特定的输入节点对像 ReLU 这样的非线性激活的影响。

  3. 消融测试 Ablation Test:这是对这个问题的又一次简单的尝试。这里的想法是一次移除一个特征,重新训练模型并观察性能的差异。然后,我们可以将这些特征的重要性与移除它们所导致的性能下降成正比。

    然而这里的困难在于,通过移除一个特征获得的任何性能差异都类似于在重新训练模型时观察到的离线指标中的典型噪声。这可能是因为我们的特征集合中存在大量的冗余,模型似乎能够从剩余的特征中弥补一个缺失的特征。

    这导致了忒休斯之船悖论Ship-of-Theseus paradox :你能一次从模型中删除一个特征,声称该模型没有显著的性能下降吗?

    忒修斯悖论:如果忒修斯的船上的木头被逐渐替换,直到所有的木头都不是原来的木头,那这艘船还是原来的那艘船吗?

    即:假定某物体的构成要素被置换后,但它依旧是原来的物体吗?

  4. 排列测试Permutation Test:在接下来的尝试中,我们从针对随机森林提出的排列特征重要性permutation feature importance 中得到启发。我们在测试中随机排列了特征在各个样本中的取值之后,在测试集上观察了模型的性能。我们的期望是,特征越重要,扰动它导致的模型退化degradation 就越大。

    但是,该操作会导致有些荒谬的结果。原因是在一次排列permuting 一个特征时,我们假设不同特征之间彼此独立,这是错误的。例如,预测预订概率的最重要特征之一就是 listing 中的房间数。而房间数量和价格、住宿人数、便利设施等特征息息相关。对特征进行独立排列会创建在现实生活中从未发生过的样本,并且特征在无效空间invalid space 中的重要性使我们误入歧途。

    但是,该测试在确定没有发挥作用的特征方面有些用处。如果随机排列特征完全不影响模型性能,则可以很好地表明模型可能不依赖于该特征。

  5. TopBot Analysis:有一个自主开发的工具旨在解释这些特征,并且不会以任何方式干扰它们。这个工具叫做 TopBot,它提供了一些有趣的洞察 insight

    TopBot 是自上而下分析器top-bottom analyzer 的缩写,它将一个测试集作为输入,并使用模型对每个测试querylisting 进行排序。然后它为每个query 从排名在 toplisting 生成特征取值的分布图,并将该分布图和排名在 bottomlisting 生成特征取值的分布图进行比较。这个比较comparison 表明了模型是如何利用不同取值范围内的特征。

    下图显示了一个例子。排名最高的listing 的价格分布偏向于较低的值,这表明模型对于价格的敏感性sensitivity 。但是,当比较排名top 和排名 bottomlisting 的评论数量的分布时,这两个分布看起来非常相似,表明这个版本的模型未按预期使用评论,从而为下一步研究提供了方向。

13.7 回顾

  1. 下图总结了目前为止的深度学习之旅。

    • 根据无处不在的深度学习成功案例,我们从乐观主义的顶峰开始,认为深度学习将取代 GBDT 模型,并为我们带来惊人的收益。
    • 许多最初的讨论集中在保持其他一切不变,用神经网络替代当前的模型,看看我们能够得到什么收益。当最初没有实现这些收益时,这让我们陷入了绝望的深渊。
    • 随着时间的推移,我们意识到转向深度学习根本不是一个简单的模型替代,更确切的说这是关于系统扩展sytem scaling 。因此,它需要重新思考围绕模型的整个系统。

    如果仅局限于较小的规模,像 GBDT 这样的模型在性能上可以说是同等水平并且更易于处理,我们继续使用 GBDT 来解决中等规模的问题。那么,我们会向其他人推荐深度学习吗?答案是 Yes。这不仅是因为深度学习模型的在线性能大幅提升。还有部分原因是与深度学习如何改变了我们未来的 roadmap 有关。早期机器学习的重点主要放在特征工程上,但是在转向深度学习之后,试图手动特征工程已经失去了前景。这让我们可以在更高的层次上研究问题。比如,如何改进我们的优化目标?我们是否准确地代表了所有的用户?在迈出将神经网络应用于search ranking 第一步的两年之后,我们觉得我们才刚刚开始。

十四、Improving Deep Learning For Airbnb Search

  1. Airbnb 是一个双边市场,汇集了拥有出租房屋的房东hosts 、以及来自世界各地的潜在租客guestsAirbnbsearch ranking 问题是对住宿地点(称为 listing )进行排名,从而响应用户的 query。这些 query 通常包括位置location、客人数量、入住/退房日期checkin/checkout dates

    过度到深度学习是 Airbnb search ranking 发展过程中的一个重要里程碑。我们在 《Applying Deep Learning to Airbnb Search》 对旅程(指的是超越之旅journey beyond)的描述让我们和许多行业从业人员进行了交谈,使得我们能够交换见解insights 和批评critiques。此类对话中经常出现的一个问题是:下一步是什么?我们试图在论文 《Improving Deep Learning For Airbnb Search》中回答这个问题。

    用于ranking 的深度学习的推出引起了很多庆祝,不仅因为它带来的预订量增益,还因为它给我们未来的路线图roadmap 带来了变化。最初的看法是,在深度学习上的 Airbnb ranking 使我们能够接触到这个巨大的机器学习思想宝,这个宝库似乎每天都在增长。我们可以简单地从文献综述中挑选出最好的想法,一个接一个地推出,从此过上幸福的生活。

    但是事实证明,这是乐观情绪的山峰the peak of optimism 。熟悉的陷入绝望之谷valley of despair 的模式很快就出现了:在其他地方取得了令人印象深刻的成功的技术在我们自己的application 中证明是非常中性neutral 的。这导致了我们在第一次launch 之后对如何迭代深度学习的策略进行了全面修订。

    在本文中,我们描述了在 《Applying Deep Learning to Airbnb Search》 推出之后的主要改进。除了深入研究核心机器学习技术本身,我们还关注导致突破的过程process 和缘由reasoning 。现在从更大的角度来看,我们更重视在如何迭代 DNN 方面的经验教训,而不是任何单独的技术。

    我们希望那些专注于在工业环境中应用深度学习的人会发现我们的经验很有价值。我们通过查看我们为改进 DNN 架构所作的努力来展开讨论。

    • 对于架构,我们描述了一个新的 ranking 神经网络,重点关注将我们现有的 DNN 发展到两层全连接网络之外的过程。
    • 在处理 ranking 中的位置偏差positional bias 时,我们描述了一种新颖的方法,该方法在处理库存inventory 方面取得了显著的提升。
    • 为了解决冷启动问题,我们描述了我们对问题的看法,以及我们为改善平台上新 listing 的处理所做的改变。

14.1 架构优化

  1. 什么是深度学习?嗯,添加更多的 layer。至少,在回顾了引领当前深度学习时代的一系列进展之后,这是我们朴素的解读。但是,当我们试图复制 《Revisiting Unreasonable Effectiveness of Data in Deep Learning Era》中总结的 scaling 数据和添加更多layer 的好处时,我们遇到的只是中性的测试结果。

    为了解释为什么增加layer 没有显示任何收益,我们从文献中借用了更多的想法,例如应用残差学习residual learningbatch normalization 等等。尽管如此,NDCG 在离线测试中仍然没有提升。

    我们从这些练习 exercise 中得出的结论是:增加layerconvolutional neural networks: CNN 卷积神经网络中的有效技术,但是不一定适用于所有 DNN 。对于向我们这样的全连接网络fully connected networks: FCN ,两个隐层就足够了,模型容量不是我们的问题。

    如果更深的网络不是适合我们的架构,那么我么假设:更专业的网络可能是适合我们的架构。因此,我们尝试了可以显式处理 querylisting 之间交互的架构,例如 Deep and Wide ,其中 query-listing 的特征交叉添加到 wide 部分。接下来是 《Attention is All you Need》 中基于 attention 的网络变体。这样做的目的是使得从query 特征派生的隐层将注意力集中在从listing 特征派生的隐层的某些部分上。这些努力的简短总结是,它们也未能改变现状。

    在尝试将成功的深度学习架构引入product application 时,在翻译任务translation 中经常忽略的是:一个体系架构的成功和它的应用上下文application context 有着错综复杂的联系。人们报告的架构性能提升来自于解决与它进行比较的baseline 的某些缺点。由于深度学习普遍缺乏可解释性explainability ,因此很难准确推断出新架构正在解决什么缺点、以及如何解决这些缺点。因此,确定这些缺点是否也同样困扰着自家产品,就变成了一种猜测。

    为了提高我们成功的几率,我们放弃了 “下载论文 --> 实现 --> A/B test ” 的循环。相反,我们决定基于一个非常简单的原则来推动这个过程:用户主导、模型跟随 users lead, model follows

  2. 用户主导、模型跟随 Users Lead, Model Follows :这里的想法是:首先量化一个用户问题user problem ,随后调整模型以响应用户问题。

    沿着这些思路,我们观察到 《Applying Deep Learning to Airbnb Search》 中描述的一系列成功的 ranking 模型不仅与预订量的增加有关,而且还与搜索结果的平均 listing 价格降低有关。这表明模型迭代越来越接近租客的价格偏好price preference ,其中每轮迭代时平均价格低于前面模型的平均价格。

    我们怀疑,即使在连续降价之后,模型的价格选择和租客的价格偏好之间也可能存在 gap 。为了量化这种gap,我们观察了每个租客看到的搜索结果的价格中位数、以及该租客预订 listing 的价格之间的 gap 的分布。由于价格服从对数正态分布log-normal distribution ,因此在对价格取对数之后计算差异。下图给出了差异的分布情况。X 轴显示了预订价格和搜索结果中间价median price 的对数偏移,Y 轴是这个对数偏移对应的用户数。

    我们预期的是:预订价格将围绕着搜索结果的中间价对称分布,并且类似于以零点为中心的正态分布。实际上相反,这个分布在负向侧negative side 更大,表明租客更偏好较低的价格。这给了我们一个具体的用户问题来调查:是否需要将更接近租客价格偏好的低价listing 排名更高。

    假设有两个普通的listing,它们除了价格在其它方面都相同,我们的直觉理解是租客更喜欢更便宜的 listing 。我们的ranking 模型是否真正理解了 cheaper is better 的原则?我们并不完全确定。

  3. Enforcing Cheaper Is Better 强迫cheaper is better :我们不清楚模型如何解释 listing 价格的原因是:模型是一个 DNN。一些熟悉的工具,如检查逻辑回归模型中相应权重、或者 GBDT 模型中的部分依赖图partial dependence graphs,在 DNN 环境中都不再有效。

    为了使得价格更可解释 interpretable ,我们对模型架构进行了以下更改:

    • DNN 的输入特征中移除价格。我们将这个修改的 DNN 模型记作 ,其中 DNN 模型参数, 为用户特征,query 特征, 为移除了价格的 listing 特征。

    • 模型的最终输出修改为:

      其中 为待学习的参数, 定义为:

      其中 price 为原始的价格特征,而 为根据日志的listing 价格的中位数计算得出的常数。

    -tanh(.) 项允许我们通过相对于价格单调递减的output score 来强制执行 cheaper is better 。易于解释的 参数使得我们能够准确描绘出价格的精确影响。

    通过训练数据我们学习到参数取值为: 。我们在下图中绘制了在 ranking 过程中, 遇到的典型取值所对应 tanh(.) 项的结果。X 轴表示归一化的价格( 值),Y 轴表示 tanh(.) 项的结果。

    当对 《Applying Deep Learning to Airbnb Search》 中的带两个隐层的 DNN 进行在线 A/B test 时,搜索结果的平均价格下降了 -5.7%,这与离线分析相一致。但是价格的可解释性付出了沉重的代价,因为预订量下降了 -1.5%

    我们的假设是:价格和其它特征密切相关,将价格从模型中分离出来导致欠拟合。NDCG 在训练集和测试集上都下降了,该事实支持这一假设。

  4. 广义单调性Generalized Monotonicity:为了在模型中保留 cheaper is better 的直觉,但是允许价格和其它特征相互作用,我们开始研究在某些输入特征方面是单调monotonicDNN 架构。

    lattice networks 为这个问题提供了一个优雅的解决方案。但是,将我们的整个系统切换到 lattice networks 是一个巨大的挑战,我们寻求一种破坏性较小的机制。因此,我们构建了下图中所示的架构,除Tensorflow 中原生节点之外,该架构不依赖于任何专门的计算节点。

    我们讨论架构的逐步构建,确保从输入价格节点到最终输出的所有路径在价格方面都是单调的:

    • 我们将 作为 DNN 的输入,该输入相对于价格单调递减。

    • input layer,我们没有将 乘以权重参数,而是将它乘以权重参数的平方。因为在任何 参数(都是实数)的情况下, 都是相对于价格单调递减的。因此第一层隐层的输入对于价格也是单调递减的。

    • 对于隐层,我们使用 作为激活函数,该激活函数保持了单调性。

    • 给定相对于 单调递减的两个函数 ,那么 也是相对于 单调递减的。其中 可以为任意实数。

      我们在第二个隐层和输出层使用这个属性,所有权重都是平方的。在下图中,这在第二个隐层和输出层用粗实线表示。即:粗实线表示平方权重,虚线表示常规的权重。

    • 添加一个既没有价格作为输入、也没有任何单调性约束的子网subnet,从而允许其它特征之间的不受约束的交互。

    尽管比 Enforcing Cheaper Is Better 中描述的架构更加灵活,但是在线测试的结果非常相似:预订量下降了 -1.6%

    Enforcing Cheaper Is Better 中描述的架构一样,该架构强制模型在任何情况下的输出都是相对于价格单调递减的。这种架构的失败表明:价格的单调性是一个过于严格的约束。

  5. 软单调性Soft Monotonicity:虽然前面描述的架构揭示了 DNN 在支持模型约束方面的能力,但是它也教会了我们 DNN 的另一个特点:它们的行为就像团队中的一位明星工程师star engineer。给定一个问题,让他自己解决,他通常会想出一个合理的解决方案。但是强迫他往某个方向走,灾难很快就会随之而来。

    所以在我们的下一次迭代中,我们决定通过配置上下文setting context 来管理 DNN ,而不是通过控制control 来管理 DNN 。我们没有强制要求模型的输出是价格的单调函数,而是添加了一个软提示soft hintcheaper was better

    通常,每个训练样本包含一对listing,一个是预订的 listing、另一个是未预订的 listing 。将 DNN 应用于这两个listing 的特征并产生对应的logits,并且定义损失函数为:

    为了添加价格提示price hint,我们为每个训练样本引入了第二个label,指示两个listing 中哪个价格更低、哪个价格更高。然后我们修改损失函数如下:

    alpha 超参数提供了一种方法来控制:结果是按照相关性relevance 排序还是按照价格price 排序。

    为了测试这个想法,我们将 alpha 超参数调整到最小值,这样在离线测试中,我们得到了和 baseline 模型相同的 NDCG。这使得我们能够在不损害相关性的情况下尽可能地推动 cheaper is better 的直觉,至少在离线指标上是这样的。

    在在线 A/B test 中,我们观察到搜索结果的平均价格下降了 -3.3% ,但是预订量也下降了 -0.67%

    离线分析的局限性在于:它仅对日志中可用的、reranking 中的 top 结果(因为这些日志是reranking 模块胜出的流量)进行评估。在在线测试期间,将新训练的模型应用于整个库存inventory 空间揭示了将价格损失作为训练目标的一部分的真实代价。

  6. 执行个体条件期望 Putting Some ICE :降价实验带来的灾难让我们处于一种矛盾的状态:搜索结果中的listing 价格似乎高于房客偏好价格,但是压低价格却让房客不高兴。

    为了了解新模型的不足之处,有必要比较 baseline 模型是如何利用价格特征的,但是这被全连接 DNN 缺乏可解释性所掩盖。如前所述,像部分依赖图partial dependence plots 这样的概念没有用,因为这种方式依赖于给定的特征对模型的影响独立于其它特征的假设。试图给出价格的部分依赖图会产生平缓倾斜sloping straight 的直线,这表明 DNN 对价格有一些轻微的线性依赖,这与我们所知道的相矛盾。

    为了取得进展,我们缩小scaled downDNN 可解释性的问题。我们没有试图对价格如何影响DNN 做一般性的陈述statement,而是聚焦于一次解释单个搜索结果。借用《Peeking Inside the Black Box: Visualizing Statistical Learning With Plots of Individual Conditional Expectation》 中的个体条件期望individual conditional expectation:ICEplots 的想法,我们从单个搜索结果中获取listing,在保持所有其它特征不变的情况下对价格选取一定的范围,并构建模型得分的plot

    下面给出了一个示例。图中x 轴为价格、y 轴为模型预估的 listing score。每条曲线代表了单次搜索结果中的一个 lising (在多个价格上的score)。因为单次搜索返回多个 listing 结果,所以下图中有多条曲线。

    该图表明,《Applying Deep Learning to Airbnb Search》 中的两层全连接层 DNN 已经理解了 cheaper was better。对日志中随机选择的搜索集合重复 ICE 分析进一步加强了这个结论。

    失败的架构通过试图进一步压低价格从而影响了模型质量。

  7. 双塔架构Two Tower Architecture :回到下图,租客显然是在通过这个plot 传递一个信息。但是,那些致力于用相关性relevance 换取价格price 的架构错误地解释了这个信息。需要对下图进行重新解释,这个解释必须和价格保持一致,也必须和相关性保持一致。

    当我们计算租客搜索结果的中间价与其预订价格之间的差异,并计算按城市分组的均值时,就出现了上图的替代解释alternate explanation 。正如预期的那样,各城市之间存在差异。但是和头部城市相比,尾部城市的差异要大得多。尾部城市也通常位于发展中市场developing markets。下图展示了某些选定城市的搜索结果中间价和预订价格之间的差异的平均值。

    这就产生了一个假设,即:搜索结果中间价与其预订价格之间差异plot 背后的 DNN 正遭受多数暴政tyranny of the majority,它聚焦于针对统治了预订量的热门区域调优的 price-quality tradeoff 。将这个 trade-off 推广到长尾的query 效果不佳,并且该模型也不适应本地条件(即长尾城市)。

    该假设与馈入 DNN 特征的另一个观察相吻合。鉴于DNN 是使用 pairwise 损失训练的,pair 对的两个listing 中有差异的特征似乎具有最大影响力。query 特征,这对于pair 对的两个listing 都是公共的,似乎没有什么影响,并且删除query 特征对于 NDCG 的影响非常微小。

    新的想法是,该模型充分理解了 cheaper is better,但它缺少的是合适价格right price 的概念。理解这一概念需要密切关注query 特征,如位置location,而不是纯粹基于listing 特征进行区分。这启发了该架构的下一次修订,新架构由双塔two towers 组成。

    • 第一个塔由query 特征和用户特征馈入,生成了一个 100 维的向量,该向量从概念上代表了 query-user 组合的ideal 理想listing
    • 第二个塔根据listing 特征构建了一个 100 维的向量。两个塔输出向量之间的欧氏距离用于衡量给定listingquery-user 的理想listing 之间的距离。

    训练样本由listing pair 对组成:一个已预订listing、一个未预订listing

    损失函数的定义是:和已预订listing 相比,未预订listing 与理想情况的接近程度。因此,对这个双塔模型进行训练可以使得pair 对中的预订listing 更接近理想listing 、同时将未预订listing 远离理想listing 。这类似于《A Unified Embedding for Face Recognition and Clustering》 中引入的 triplet loss 。这里的主要区别在于:我们没有在三元组triples 上训练,而是只有listing pair ,并且三元组中缺失的anchor listing 是由 query-user 塔来自动学习。

    querylistingpairwise training 如下图所示。

    Tensorflow 代码如下所示,实际实现可能略有不同从而优化训练速度:

  8. 测试结果:当进行线上 A/B test 时,其中 baseline《Applying Deep Learning to Airbnb Search》 中的两层全连接层的 DNN ,双塔架构的预订量增加了 +0.6% 。这一增长是由搜索便利性ease of search 的提高所推动的,因为在线 NDCG 提高了 0.7% 。尽管这个双塔架构的目标不是直接降低价格,但是我们观察到搜索结果的平均价格降低了 -2.3%,这是相关性增加的副作用 side effect。预订量的增加抵消了价格下降对于收入的影响,整体收入增加了 +0.75%

    搜索便利性:搜索结果中,目标listing 排名更靠前因此有利于用户预订。

    除了提高搜索结果的质量之外,双塔架构还允许我们优化在线 DNNscoring 延迟。

    • 对于全连接架构,评估第一个隐层贡献了 scoring 延迟的最大部分。评估第一个隐层的计算复杂度可以表示为 ,其中 是和 listing 无关的 queryuser 特征的数量,listing 特征的数量, 为第一层的隐单元数量。

      为了评估包含 listing 的结果集(该结果集对应于单个 query 的搜索结果),总的算法复杂为

    • 在新架构的双塔中,query 塔独立于 listing。这允许在整个搜索结果集针对该塔仅评分一次,并且仅评估每个listinglisting dependent tower 。第一个隐层的计算复杂度降低到 ,其中 listing 塔和 query 塔的隐层神经元数量。

      当在线测试时,这导致 99th 百分位数的 scoring 延迟降低了 -33%

  9. 架构回顾:就在我们庆祝成功的时候,随着 DNN 迭代的启动,疑虑也悄然而至。架构是否按预期工作?或者 DNN 是否偶然发现了其它意外情况?

    过去,DNN 的不可解释的性质使得回答此类疑问变得极其困难。但是考虑到双塔架构的直觉是针对用户问题user problem 而开发的,我们现在可以使用这些直觉来更好地了解 DNN 的运作方式。

    重温价格的 ICE 图,我们看到了一个显著的变化。如下图所示,我们看到分数在某些价格附近达到峰值,而不是总是向下倾斜(对应于 cheaper is better )。这更接近 right price for the trip(旅行的正确价格) 的解释。

    在这种情况下,一个经常被提出的问题是,低质量的listing 是否可以通过简单地降低价格从而在新模型中提升排名。仔细检查 ICE 曲线发现,某些价格附近的分数峰值仅发生在高质量listing 中,这些listing 通常一开始就排名靠前。对于大多数listing ,该图仍然保持着与价格相关的单调递减曲线。

    正确价格right price 、理想listing 这些概念的核心是query 塔生成的向量,因此自然而然的后续工作是准确地研究这些向量到底是什么样子的。为了进行分析,我们随机采样了一批搜索来运行了双塔 DNN,并收集了 query塔的输出向量。由于 100 维向量对于人类是不可解释的,因此我们应用 t-SNE 将这些向量降维到 2 维空间,如下图所示。图中标出了部分城市对应的 query ,每个点代表一个 query。某些 query 标记有 city/guest-count/trip-length 信息。点的颜色代表query 的预订订单价格,越便宜颜色越绿、越贵颜色越蓝。令人欣慰的是,租客数量guest count 和行程长度trip length 等参数相似的值形成了大的簇clusters 。在大的簇内部,直觉上感觉相似的城市(比如都是发达市场或者发展中市场)被放置在彼此相对接近的地方。

    值得强调的是,簇不仅仅是价格簇price clusters。和query 对应的预订listing 的价格由点的颜色来表示,我们看到簇具有所有范围all range 的颜色。虽然莫斯科通常比巴黎更便宜,但是莫斯科的预订价格很容易超过巴黎的预订价格,这取决于租客数量、停留时间duration of stay 、离旅游景点的距离、周末 vs 工作日、以及许多其他因素。

    价格与所有其它维度有着千丝万缕的联系,掌握旅行的正确价格意味着同时掌握所有其它因素。我们所作的分析都不能作为双塔架构确实发展出这种掌握grasp 的有力证据。但是,针对价格的 ICE 图、query 塔输出的t-SNE 可视化、以及对跨城市price movements的额外分析给了我们足够的信息,让我们相信这一机制正在按预期发挥作用。

    放下一系列的架构操作,接下来我们继续解决ranking 的挑战,该挑战不仅影响房客,也影响 Airbnb 社区的另一半,即房东。

14.2 冷启动改善

  1. 在旅游领域的机器学习application 中,任何时候都有很大一部分用户是新用户,或者在很长一段时间后才使用该产品。此时用户处于连续冷启动状态 continuous cold start

    处理 user level 冷启动是核心排序公式 core ranking formulation 本身的一部分。所以在提到冷启动问题时,我们把注意力几种在 item level 冷启动上(即如何处理新item 的排名)。和前面改进 DNN 架构的情况一样,我们探索的起点不是文献综述,而是对用户问题user problem 的观察。

  2. 使用 NDCG 来量化预订listing 在搜索结果中的位置,这对我们来说是衡量模型性能最可靠的方法。因此,调查用户问题的一个自然的地方是:寻找 NDCG 低于 NDCG 整体水平的细分市场。

    考虑平台上新listing 、老listing 中,预定listing 的在线 NDCG 之间的差异,我们观察到了 -6% 的差距。而模型预估的 NDCG 和在线预定的 NDCG 之间的差异只有 0.7% 。这表明该模型让房客更难发现值得预订的新listing

    为了更好地理解这一点,我们从 DNN 中移除了所有的、listing 上基于房客历史互动生成的输入特征,例如一个listing 的历史预订量。删除这些互动特征engagement features导致离线 NDCG 下降了 -4.5%。显然,DNN 非常依赖于互动特征。由于新listing 没有这些互动特征,因此 DNN 被迫根据剩余特征做出宽泛broad 的判断,从而接近新listing 的平均表现。

  3. 冷启动方法视为 Explore-Exploit:冷启动问题的一个可能的框架是将它视为探索和利用explore-exploit 之间的tradeoff

    排序策略可以通过利用exploiting 当前库存inventory 的知识来短期地专门优化预订量,并且只押注那些有良好记录的listing 。但是为了市场的长期成功,它需要支付一些成本来探索explore 新的库存。

    这种tradeoff 可以作为新listing 的显式排名提升boost 来实现,它为新listing 分配更高的排名(相比较于 DNN 所确定的排名)。这允许新listing 以较低的预订代价cost 收集租客的反馈。这种通用的方式在电商排序application 中很流行,例如在 《Re-ranking results in a search》 中。这种 boost 可以通过曝光次数限制、或者引入时间衰减来进一步细化refined

    我们的第一次迭代是为了测试这种 boost 。通过在线 A/B test,与没有 boost 相比,boost 并没有带来新listing 的预订量的提升或下降(效果中性),并且为新listing 带来了 +8.5% 的首页曝光次数。

    但是, explore-exploit 范式带来了严峻的挑战:

    • listingranking boost 被两种相反的力量拉向不同的方向:

      • 由于搜索结果相关性relevance 降低,短期内用户体验user experience 下降。我们可以准确地衡量这一影响。
      • 由于库存增加,长期来看用户体验有所改善。我们发现这种影响很难量化。

      缺乏对最佳boost 量的明确和客观的定义导致了激烈的内部辩论,没有一个解决方案让每个团队都满意。

    • 即使能够确定探索exploration 成本的总体预算,很明显,预算的正确使用取决于特定地域location 的供需supply and demand 情况。

      • 当需求量demand 很大时,探索的容忍度就很高。当需求量很少时,探索的容忍度就没那么高。
      • 在商品供给受到限制的区域,探索和扩大库存的需求很高。当大量优质listing 空置时,几乎没有动力承担探索成本。

      供需反过来又受到位置location 、季节性seasonality 、租客容量capacity 等参数的影响。因此,为了最优地使用全局探索预算,需要数千个局部参数localizing parameters ,这是一项无法手动完成的任务。

  4. 预估将来的用户互动User Engagement:为了让系统更易于管理,我们退了一步,开始问:是什么让一个新的 listing 与众不同?

    答案当然是缺乏用户产生的互动特征engagement features ,例如预订量、点击量、评论量等等。价格、位置location、遍历设施amenities 等其它属性,新listing 和其它listing 一样。理论上,如果我们有一个预言机可以 100% 准确预测新listing 的互动特征,那么它可以最佳地解决冷启动问题。

    因此,我们没有将冷启动视为 explore-exploit tradeoff ,而是将其重新定义为一个评估新listing 互动值 engagement values的问题。问题的重新定义揭示了一些重要的东西:它允许我们为问题定义一个客观的理想 objective ideal ,并不断地朝着它努力。

    为了解决冷启动问题,我们引入了一个新的组件component 来为 DNN 提供数据,该组件在训练和评估时预测新listing 的用户互动特征。为了衡量估计器estimator 的准确性accuracy,我们采用了以下步骤:

    • 从日志中采样 个搜索结果。对于每个搜索结果,从 top 100 个位置随机抽取一个 listing。这些代表了受到租客充分关注的 listing 样本,因此它们的互动特征已经充分融合converged

    • 表示从日志中获取的抽样listing 的排名。我们将排名表示为 real,从而表示listing 的互动特征是真实租客互动的结果。从排名中,我们计算 real discounted rank 为:

    • 接下来,对于每个抽样的listing,我们删除所有互动特征,并用被estimator 预测的互动特征来代替它们。我们使用预估的互动特征对listing 进行评分,在相应的日志搜索结果中找到它的新排名,然后从中计算 discounted rank 。我们用 来表示。

    • 对于每个抽样的listing,我们计算互动估计中的误差为

    • 为了获取整体误差,我们对所有抽样的listing 的互动估计误差engagement estimation error 进行平均。

    理想的互动估计器会产生零误差。要在两个估计器之间取舍,可以选择误差较小的估计器。

    为了验证,我们对比了两种估计方法:

    • baseline 是生产中使用的系统,它为缺失的特征分配默认值,包括新listing 的互动特征默认值。默认值是通过手动分析相应特征而创建的常量。

    • 我们对比了一个 estimator,这个 estimator 通过新listing 地理位置附近的其它listing 的互动特征均值来估计了新listing 的互动特征。

      为了提高准确性accuracy,它只考虑和新listing 的房客容量capacity 相匹配的相邻listing ,并计算滑动时间窗口的均值从而考虑季节性seasonality

      例如,为了估计一个容纳两人的新listing 的预订量,我们选取了新listing 的很小半径内的、容量为两人的所有listing 的平均预订量。

      这在概念上类似于朴素贝叶斯推荐器Naive Bayes recommender (它使用生成式方法generative method 来估计缺失信息)。

  5. 测试结果:

    • 在离线分析中,与使用默认值相比,上述互动估计器将互动估计误差降低了 -42%
    • 在在线 A/B test 中,我们观察到新listing 的预订量提高了 +14%,同时新listing 的首页曝光量增加了 +14% 。除了对新listing 的影响之外,整体预订量增加了 +0.38%,表明用户体验的整体改善。

14.3 Positional Bias

  1. 我们研究位置偏差positional bias 的出发点是完全不相关unrelated 的。与新listingNDCG 较低的观察结果类似,另一个表现低于预期的细分市场是精品酒店boutique hotels 和传统住宿加早餐酒店traditional bed and breakfasts。这个细分市场作为库存的一部分正在迅速增长。

    从观察中得出的一个假设是:由于位置偏差,在训练数据中未充分表达under-represented的库存没有得到最佳排名。但是和新listing 表现与冷启动之间的联系不同,没有充分理由相信位置偏差是这个case 的唯一罪魁祸首。还有多个其它假设。

    虽然我们发现关注用户问题user problem 要比简单地从文献综述中引入想法要好得多,但是用户问题并不是万灵药。在用户问题和模型缺陷之间建立因果关系远远不是简单直接的。在目前的场景中,我们是在黑暗中射击shooting in the dark

    但是与此同时,我们决定寻找模型中的最大gap 来解释观察结果。文献综述对于确定我们模型中潜在的主要gap 至关重要。

  2. 相关工作:给定用户 发出的 query ,用户从搜索结果中预订 listing 的概率可以分解为两个因素:

    • listing 和用户相关relevant 的概率。这个概率可以表示为 ,从而明确它和 listing、用户、query 的依赖关系。

    • 给定listing 在搜索结果中的位置 的条件下,用户检查examinedlisting 的概率。这可能取决于用户(例如,移动设备上的用户可能对 top 结果有更高的bias )或query (例如,提前期lead days 较短的用户可能不太关注底部结果)。

      我们将这个概率表示为 ,它独立于 listing

    使用 《Click Models for Web Search》 中描述的position based 模型的简化建设,我们将用户预订listing 的概率简单地表示为两个分解概率的乘积:

    通过直接训练一个模型来预测预订,该模型学会预测了依赖于 。这反过来又取决于位置 ,这是先前previousranking 模型做出的决定。因此,当前的模型变得依赖于先前的模型(指的是模型的前一个版本)。

    理想情况下,我们希望模型专注于 ,并仅按照相关性relevancelisting 进行排序。为了实现这一点, 《Unbiased Learning-to-Rank with Biased Feedback》描述了一种具有两个关键概念的方法:

    • 一个预测 的倾向性模型propensity model
    • 用预测的倾向的倒数来加权每个训练样本。

    虽然构建倾向性模型通常涉及扰乱perturbing 搜索结果从而收集反事实counterfactuals 的样本,但是 《Estimating Position Bias Without Intrusive Interventions》 描述了在没有额外干扰的情况下构建倾向模型的方法。

  3. 位置作为控制变量Position As Control Variable:我们的解决方案有两个关键亮点。

    • 首先,它是非侵入式non-intrusive 的,不需要对搜索结果进行任何随机化。

      我们依赖 Airbnb 搜索结果的一些独特属性,这些属性使得listing 即使在排序分不变的情况下也可能出现在不同的位置:

      • listing 代表给定日期范围内只能预订一次的物理实体physical entities 。随着listing 被预订并从搜索结果中消失,这会改变剩余listingposition
      • 每个listing 都有自己独特的日历可用性unique calendar availability,因此对于跨日期范围的相似query ,不同的listing 会出现在不同的position
    • 其次,我们没有明确建立一个倾向模型。相反,我们在 DNN 中引入位置position 作为特征,并通过dropout 进行正则化。在评分过程中,我们将position 特征设置为零。

    接下来我们描述为什么这种方法有效的直觉intuition 。我们以前面描述的 DNN 为基础,将query特征、用户特征、listing 特征作为输入。利用符号 query 特征)、 (用户特征)、listing 特征)、DNN 参数),我们将 DNN 的输出表示为:

    这反映了《Click Models for Web Search》position based 模型所作的假设,其中:

    • 估计了 ,我们称之为相关性预测relevance prediction
    • 预估 ,我们称之为位置偏差预测positional bias prediction

    很明显 缺少listing 的位置 作为输入,而它试图估计的量依赖于 。因此,我们的第一步是将 作为输入特征添加到 DNN。因为相关性预测和位置偏差预测都是由 DNN 的输入馈送fed的,因此向输入中添加 会将我们的 DNN 变为:

    假设 独立于 listing ,位置偏差预测对 的任何依赖性dependence 都可以被视为误差error 。我们假设有足够数量的训练数据,待学习的参数 能够最小化该误差。我们将这个假设理解为:

    其中从 中移除

    评分时,我们将位置特征 设置为零。在给定的query 中,DNN 评分的 listing 中是不变的。我们使用 来表示给定搜索的 query 特征和用户特征。因此,位置偏差预测变为 ,它是对给定搜索结果中所有listing 不变invariant 的,我们将其记作 。那么DNN 的评分变为:

    这使得两个listing 得分的比较独立于位置偏差positional bias ,并且仅依赖于listing 相关性relevance 。本质上,我们在排序模型中添加了position 作为控制变量control variable

  4. Position Dropout:在 position based 模型的假设下,增加position 作为控制变量有效地消除了listing 排序中的位置偏差预测,但是它引入了一个新的问题:相关性预测现在依赖于位置特征position feature 。这使得 DNN 在训练期间依赖位置特征来预测相关性,但是在评分期间无法利用学到的、位置相关的知识(因为评分期间位置特征总是为零)。

    将具有位置特征的 DNN 和没有位置特征的baseline 进行比较,我们可以看到离线 NDCG 下降了大约 -1.3% 。因此,直接将位置作为控制变量引入模型似乎会损害相关性预测。为了减少相关性预测对于位置特征的依赖项,我们使用 dropout 对其进行正则化。在训练期间,我们随机性地将listingposition 设为0,这个概率由 dropout rate 来控制。

    dropout rate 在无噪声noise-free 地访问位置特征从而准确地推断位置偏差 vs 有噪声noisy地访问位置特征从而远离相关性预测之间进行tradeoff。我们尝试通过以下步骤找到平衡的 tradeoff

    • 扫描一个范围内的 dropout rate ,并在测试集上计算两种 NDCG

      • 第一个是在测试期间将position 为零,这衡量了相关性预测并表示为
      • 第二个通过保留位置特征来衡量相关性和位置偏差组合在一起的预测,记作
    • 从而获得位置偏差预测。这里的直觉是:通过比较有位置输入和没有位置输入的排序质量,我们可以估计位置对于排序的贡献。

      我们得到了 针对位置偏差预测的曲线,如下图所示。Y 轴为 X 轴为位置偏差预测。

    • 为了在相关性预测和位置偏差预测之间取得平衡,我们在曲线上选择一个点,该点在 X 轴上的位置偏差预测足够先进advanced,而且不会导致Y 轴上的相关性预测下降太多。

    通过这个练习exercise,我们最终选择了 0.15dropout rate

  5. 测试结果:我们通过在线 A/B test 测试了这个想法,其中:对照组是没有位置偏差的 DNN;实验组是相同的 DNN,但是使用位置作为特征进行训练,并以 0.15dropout rate 进行正则化。在在线测试中,我们观察到预订量增加了 0.7%

    除了预订量增加之外,收入增长 1.8% 也是一个惊喜。收入增长这个副作用说明了位置偏差是如何在模型的多次迭代中累计起来的。

    对于排序模型来说,了解价格的影响相对容易,因为价格是一个非常清晰的特征,并且数据强烈表明人们更喜欢较低的价格。质量quality、地域location 等平衡力量balancing forces 更难学习。因此,最初的简单模型严重依赖较低的价格。

    经过多次模型迭代,我们提高了对质量和地域的理解,但那时对更便宜的价格的bias 已经在训练数据中根深蒂固。这种黏性使得接下来的模型高估了对较低价格的偏好。消除positional bias使得模型更接近客人的真实偏好,并在价格、质量、地域之间取得更好的平衡。观察到的收入增长是其直接后果。

    最后,我们观察到精品酒店的预订量增加了 1.1%

十五、HOP-Rec

  1. 推荐系统在现代无处不在,并且已经广泛应用于推荐音乐、书籍、电影等 item 的服务。真实世界的推荐系统包括很多有利于推荐的 user-item 交互,包括播放时间、喜欢、分享、以及贴标签 tag 。协同过滤collaborative filtering: CF 通常用于利用这种交互数据进行推荐,因为CF 在各种推荐策略之间性能表现较好,并且不需要领域知识domain knowledge

    有两种主流的 CF 模型:潜在因子模型latent factor model 和基于图的模型graph-based model

    • 潜在因子模型通过分解 user-item 矩阵来发现 user-item 交互背后的共享潜在因子shared latent factor 。矩阵分解matrix factorization: MF 是此类方法的典型代表。

      此外,最近的文献更多地关注从隐式数据优化 item 排序,而不是预测显式的item score 。大多数此类方法假设用户对未观察到的 item 不太感兴趣,因此这些方法旨在区分观察到的itempositive)和未观察到的 itemnegative)。

      总而言之,潜在因子模型通过分解观察到的用户和 item 之间的直接交互来捕获用户偏好。

    • 基于图的模型探索了由用户、item、及其交互构建的简单 user-item 二部图bipartite graph 中固有的inherent 、顶点之间的高阶邻近性high-order proximity

      在某种程度上,这种基于图的方法放松了基于因子分解的模型所做出的假设(即:假设用户对未观察到的 item 不太感兴趣),因为它们显式地对user-item 交互二部图中的用户和 item 之间的高阶邻近性进行建模。

      总而言之,基于图的模型从由 user-item 交互构建的图中捕获用户间接偏好。

    在论文 《HOP-Rec: High-Order Proximity for Implicit Recommendation》中,作者提出了高阶临近性增强推荐模型 high-order proximity augmented recommendation: HOP-Rec,这是一个结合了这两种隐式推荐方法(潜在因子模型和基于图的模型)的、统一而有效的方法。HOP-Rec 通过在user-item 二部图上进行随机游走,从而为每个用户发现邻域item 的高阶间接信息high-order indirect information 。通过对游走路径中不同阶数使用置信参数confidence parameterHOP-Rec 在分解用户偏好的潜在因子时同时考虑item 的不同阶数。

    下图说明了在观察到的交互中对用户和 item 之间的高阶邻近性建模的思想。

    • (a) 表示由观察到的 user-item 交互构建的二部图。
    • (b) 给出了一条从源顶点 到目标顶点 的路径。
    • (c) 以矩阵的形式记录了用户和 item 之间的直接交互(一阶邻近性)。
    • (d) 以矩阵的形式显示了用户和 item 之间的高阶关系(高阶邻近性)。

    具体而言,用户 的潜在偏好item 按照它们在图 (b) 中的路径中出现的阶数进行排序。例如,观察到的item 和用户 具有一阶关系,未观察到的 item 和用户 具有二阶关系。HOP-Rec 显式地建模这种高阶间接偏好信息high-order indirect preference information

    在真实世界四个大规模数据集上的实验结果表明,HOP-Rec 显著优于几种state-of-the-art 的推荐算法,并表明将高阶邻近性和因子分解模型相结合对于一般的 top-N 隐式推荐问题很有帮助。

15.1 模型

15.1.1 因子分解模型和图模型

  1. 交互图Interaction Graph 的定义:user-item 交互由一个二元邻接矩阵 来表示,二部交互图bipartite interaction graph 基于二元邻接矩阵 来构建。其中:

    • 为用户集合,item 集合, 为顶点集合。
    • 表示是否存在交互,边集合