论文笔记 | RecSys2019 | Sampling-Bia

作者: ktulu7 | 来源:发表于2020-04-12 20:02 被阅读0次

youtube-two-tower-title.jpg

论文地址：https://dl.acm.org/doi/abs/10.1145/3298689.3346996

一为什么读这篇

很早之前就收藏的，除了16年那篇YouTube DNN，本篇应该是YouTube首次明确的指出用双塔结构做召回，从这篇中参考一下G家用双塔的工程技巧。

二截止阅读时这篇论文的引用次数

2020.2.21 3次

三相关背景介绍

同样没往arXiv上挂，感觉G家那边做推荐的好像不稀罕arXiv，直接往会议投就完了，中了19年9月的RecSys。和YouTube MultiTask差不多是同一拨人做的，9个作者中英混合。一作Xinyang Yi12年本科毕业于清华，16年PHD毕业于德州大学奥斯汀分校，同时也是MMoE，YouTube MultiTask的合著者之一。值得注意的是，《MMoE》，《YouTube MultiTask》，加上这篇，三篇最后都有同一个作者Ed Chi，这个是他们的老板，G家的首席科学家(L8)，美籍华人，在google快10年了，G家多个产品的推荐系统都是他领导的，所以能在G加不少paper上看到他的名字。

四关键词

retrieval

two-tower

sampleing-bias-corrected

item frequency estimate

五论文的主要贡献

1 公开YouTube在召回阶段做双塔的方法细节

2 提出校正softmax，以解决候选item个数过多，流式训练中item动态变化的问题

3 提出item频率预估，用于配合校正softmax

六详细解读

0 摘要

处理数据稀疏性和呈幂律分布的item的常见方法是从内容特征中学习item的表示。本文使用双塔神经网络，其中一个塔（item塔）编码item的多种内容特征。训练此类双塔模型的一般方法是优化来自in-batch negatives的损失函数，其中的item是采样自一个随机mini-batch。然而，in-batch损失受采样偏差的影响，可能会损害模型性能，尤其是在分布高度倾斜的情况下。本文提出了一种从流式数据中估计item频率的新算法，通过理论分析和模拟，证明了该算法可以在无需固定item词表的情况下生效，并且能够产生无偏估计，同时能够适应item分布的变化。之后将这种采样偏差校正的建模方法应用于YouTube推荐的召回系统，该系统的召回语料达上千万视频。

1 介绍

给定三元组{user, context, item}，构建可扩展的召回模型通常解法是：1）分别学习查询{user, context}和item{item}的表示。2）使用查询和item表示之间的简单评分函数（例如点积）来获取查询得到的推荐。context通过表示具有动态性质的变量，例如一天中的时间，用户使用的设备等。表示学习的挑战通常有两个：1）对于许多工业级别的应用来说item语料规模会相当大。2）采集自用户反馈的训练数据对许多item来说非常稀疏，从而导致模型预测的长尾内容有很大的方差。面对众所周知的冷启动问题，现实世界的系统需要适应数据分布的变化，以更好地获取新鲜内容。

如图1所示是一个双塔模型的例子，左右两侧分别对{user, context}和{item}进行了编码。

youtube-two-tower-fig1.jpg

MLP模型通常对来自固定词汇的item进行负采样训练，然而由于item的内容特征和共享网络参数，在计算所有item的embedding时，在许多负采样上训练通常是低效的。本文考虑过batch softmax优化，它是在随机batch中对所有item计算其概率的方法，是训练双塔DNN的一般方法。然而如本文实验所示，batch softmax会受到采样偏差的影响，并且可能在没有校正的情况下会严重限制模型性能。

本文提出了使用item频率预估的方法来校正batch softmax中的采样偏差。与输出item词表是固定的MLP模型相反，本文针对了词表和分布随时间变化的流式数据的状况。本文提出的新算法通过梯度下降来绘制和预估item的频率。本文也介绍了一种用于流式数据的序列训练策略，及其相关系统的索引和serving组件。

2 相关工作

2.1 内容感知和神经网络推荐

本文和NCF有两方面不同：1）本文利用双塔神经网络对user-item的交互进行建模，以便可以在亚线性的时间内对大量的item进行预测。2）NCF的学习依赖于point-wise损失（平方或log损失），而本文引入了多分类softmax损失并对item频率显式建模。

2.2 极限分类

在大量类别上如何训练softmax分类模型。

2.3 双塔模型

双塔模型源自NLP，例如对句子相似度的建模《Learning Text Similarity with Siamese Recurrent Networks》，回应建议《Smart Reply: Automated Response Suggestion for Email》，基于文本的信息检索《End-to-End Retrieval in Continuous Space》《Learning Semantic Textual Similarity from Conversations》。

3 建模框架

查询和item分别用特征向量 $\left\{x_{i}\right\}_{i=1}^{N}$ 和 $\left\{y_{j}\right\}_{j=1}^{M}$ 表示。这里 $x_{i} \in \mathcal{X}, y_{j} \in \mathcal{Y}$ 都是一系列特征的组合（例如稀疏ID和密集特征），同时有非常高的维度。假设user和context完全用 $x_{i}$ 表示。

我们的目的是用两个参数化的embedding函数（ $u: \mathcal{X} \times \mathbb{R}^{d} \rightarrow \mathbb{R}^{k}, v: \mathcal{Y} \times \mathbb{R}^{d} \rightarrow \mathbb{R}^{k}$ ）构建模型，该模型参数 $\theta \in \mathbb{R}^{d}$ ，映射查询和候选的特征到k维的embedding空间。模型的输出是两个embedding的内积，即：
$s(x, y)=\langle u(x, \theta), v(y, \theta)\rangle$
目标是从有T个样本的训练集中学习模型参数 $\theta$ ，定义如下：
$\mathcal{T}:=\left\{\left(x_{i}, y_{i}, r_{i}\right)\right\}_{i=1}^{T}$
其中 $\left(x_{i}, y_{i}\right)$ 是查询 $x_{i}$ 和item $y_{i}$ 组成的对。 $r_{i} \in \mathbb{R}$ 是与每一对关联的奖赏（分数）。

给定查询 $x$ ，从有 $M$ 个item（ $\left\{y_{j}\right\}_{j=1}^{N}$ ）中挑选候选 $y$ 的通常选择是基于softmax函数，即：
$\mathcal{P}(y | x ; \theta)=\frac{e^{s(x, y)}}{\sum_{j \in[M]} e^{s\left(x, y_{j}\right)}}$
通过进一步与奖赏 $r_{i}$ 关联，认为如下的加权对数似然是损失函数：
$L_{T}(\theta):=-\frac{1}{T} \sum_{i \in[T]} r_{i} \cdot \log \left(\mathcal{P}\left(y_{i} | x_{i} ; \theta\right)\right)$
当 $M$ 非常大时，对包含所有的候选进行计算是不可行的，例如softmax公式的分母部分。一个常见的想法是构造部分函数时使用item的一个子集。本文聚焦于处理流式数据，因此不像训练MLP模型那样从固定的语料中进行负采样，本文仅考虑使用in-batch中的item中作为相同批次中所有查询的负样本。更精确地说，给定一个含有 $B$ 个对 $\left\{\left(x_{i}, y_{i}, r_{i}\right)\right\}_{i=1}^{B}$ 的mini-batch，对于每个i，batch softmax为：
$\mathcal{P}_{B}\left(y_{i} | x_{i} ; \theta\right)=\frac{e^{s\left(x_{i}, y_{i}\right)}}{\sum_{j \in[B]} e^{s\left(x_{i}, y_{j}\right)}}$
在本文目标应用中的in-batch item通常是从幂律分布中采样的，即上式会引入大量的偏差，流行的item由于被包含在batch中的可能性很高，因此会被过度惩罚为负的。受采样softmax模型中logQ校正的启发，本文通过如下公式校正每个logit $s\left(x_{i}, y_{j}\right)$ ：
$s^{c}\left(x_{i}, y_{j}\right)=s\left(x_{i}, y_{j}\right)-\log \left(p_{j}\right)$
这里的 $p_{j}$ 定义为一个随机batch中item j的采样概率，下一节会介绍它的预估。通过校正，得到：
$\mathcal{P}_{B}^{c}\left(y_{i} | x_{i} ; \theta\right)=\frac{e^{s^{c}\left(x_{i}, y_{i}\right)}}{e^{s^{c}\left(x_{i}, y_{i}\right)}+\sum_{j \in[B], j \neq i} e^{s^{c}\left(x_{i}, y_{j}\right)}}$
则相应的损失函数如下，即batch损失函数：
$L_{B}(\theta):=-\frac{1}{B} \sum_{i \in[B]} r_{i} \cdot \log \left(\mathcal{P}_{B}^{c}\left(y_{i} | x_{i} ; \theta\right)\right)$
注意 $L_{B}$ 无需固定的查询或候选集。相应的，该公式可以应用于随着时间改变分布的流式训练数据，算法1是对本文提出方法的完整描述。

youtube-two-tower-alg1.jpg

归一化和温度

根据经验，通过给embedding增加归一化，例如， $u(x, \theta) \leftarrow u(x, \theta) /\|u(x, \theta)\|_{2}$ ， $v(y, \theta) \leftarrow v(y, \theta) /\|v(y, \theta)\|_{2}$ ，可以提升模型的可训练性，进而得到更好的召回质量。

此外，给每个logit增加温度 $\tau$ 可以完善预测，即：
$s(x, y)=\langle u(x, \theta), v(y, \theta)\rangle / \tau$
实践中， $\tau$ 是一个需要调优的超参。

4 流式频率预估

对于一个流式的随机batch，问题是预估每个batch中每个item $y$ 的命中概率。一个关键的设计准则是当有多个训练jobs（workers）时，要有一个完全分布的预估来支持分布式训练。

我们可以利用全局step，并对一个item的频率预估 $p$ 转化为预估 $\delta$ ，其表示为两次连续命中item所需的平均step。例如，如果一个item每50step采样一次，则得到 $p=0.02$ 。使用全局step提供了两点优势：1）通过读取和修改全局step，多个worker在频率预估中隐式的同步。2）预测 $\delta$ 通过简单的滑动平均来更新，该更新适用于分布的改变。

由于使用固定的item词汇表不切实际，本文应用哈希数组来记录流IDs的采样信息。注意引入哈希技术可能会带来哈希冲突问题，本文会在本节最后提出改进算法来解决这个问题。

youtube-two-tower-alg2.jpg

如算法2所示，保留两个大小为 $H$ 的数组 $A$ 和 $B$ 。哈希函数 $h$ 将任意item映射为 $[H]$ 中的一个整数。对于给定的item $y$ ， $A[h(y)]$ 记录了当 $y$ 被采样时最近的step， $B[h(y)]$ 包含对 $y$ 的预估 $\delta$ 。使用数组A来辅助更新数组B。一旦在step $t$ 时出现item $y$ ，通过如下公式（公式6）更新数据组B：
$B[h(y)] \leftarrow(1-\alpha) \cdot B[h(y)]+\alpha \cdot(t-A[h(y)])$
在更新B后，将步长 $t$ 赋给数组 $A[h(y)]$ 。

对于每个item，假设两个连续命中之间的step遵循由随机变量 $\Delta$ 表示的分布，其均值为 $\delta=\mathbb{E}(\Delta)$ 。本文的目的是从流式采样中预测 $\delta$ 。每当在第 $t$ 个step的batch中出现item时， $t-A[v(y)]$ 是一个新的采样 $\Delta$ 。因此可将上述更新理解为以固定学习率 $\alpha$ 运行SGD，以学习此随机变量的均值。形式上，在没有碰撞的情况下，下面的结果将显示在线预估的偏差和方差。证明略。。

分布式更新

数组A，B和全局step参数分布在参数服务器上。

多个哈希

受count-min sketch算法的启发，本文扩展了算法2，利用多个哈希函数来消除由于冲突带来的item频率的过度预估。改进如算法3所示。

youtube-two-tower-alg3.jpg

5 YouTube的神经网络召回系统

5.1 建模概述

如图2所示。在任何时候，seed video（用户当前观看的视频）提供了用户当前兴趣的最强信号。因此，本文利用了大量的种子视频的特征以及用户的观看历史记录。

youtube-two-tower-fig2.jpg

训练标签

视频点击被视为正样本，此外，对于每次点击，构建奖赏 $r_{i}$ 来反映用户对视频不同程度的交互。例如， $r_{i}=0$ 表示点击的视频只有很少的观看时长，而 $r_{i}=1$ 则表示全部观看完成。这个奖赏被用于损失函数中的样本权重。

视频特征

视频特征包括categorical和dense特征。categorical特征包括video id，channel id等。创建一个embedding层将每个categorical特征映射为dense向量。通常需要处理两种categorical特征，一些特征（例如视频id）严格具有一个categorical值，因此用一个embedding向量表示。另一种（如视频主题）可能是categorical值的稀疏向量，因此表示该特征的最终embedding将是稀疏向量中每个值的embedding的加权和。

为了处理超出词典范围的实体，将实体随机赋给一组固定的哈希桶。在YouTube中哈希桶对于模型捕捉可用的新实体非常重要，尤其是在下节所述的序列训练中。

用户特征

使用用户观看历史捕获用户的兴趣。将观看历史视为词袋（BOW），用视频id embedding的平均值来表示。在查询塔，用户和种子视频特征融合为输入层。

对于相同类型的ID，在相关的特征上共享embedding，例如，同样集合的视频id embedding用于种子，候选，用户观看历史。也做了不共享embedding的实验，但并发现模型质量有明显提升。

5.2 序列训练

YouTube每天生成新的训练数据，训练数据根据天来组织。模型训练按以下方式使用此顺序结构。训练器从最旧的训练数据到最新的训练数据按序列使用数据。一旦训练器得到了最新的训练数据后，便会等待第二天训练数据的到达。通过这种方式，模型能跟上最新的数据分布变化。训练数据实际上是以流的方式被消耗的。通过算法2（或算法3）预测item频率，公式6的在线更新能使模型适应新的频率分布。

5.3 索引和模型serving

召回系统中的索引流水线周期性的生成TensorFlow SavedModel用于在线serving。索引流水线由3个阶段组成：候选样本生成，embedding inference，embedding索引，如图3所示。

youtube-two-tower-fig3.jpg

6 实验

6.1频率预估模拟

学习率 $\alpha$ 的效果

youtube-two-tower-fig4.jpg

多个哈希的效果

youtube-two-tower-fig5.jpg

6.2 维基百科页面召回

youtube-two-tower-table1.jpg

6.3 YouTube实验

本文使用的YouTube训练数据包括多天的，每天都包含数十亿的点击视频。

设置

如图2所示，查询塔和候选塔的输入特征embedding会共享，当它们在两边都可用时。两边的塔都使用3层DNN，隐层单元个数分别为[1024,512,128]。用学习率为0.2的Adagrad进行训练，batchsize为8192。至于频率预估，设置 $H=50 M, m=1, \alpha=0.01$ 。在本节的实验中，每隔几个小时就会定期构建从YouTube语料库中选择的大约1000万个视频的索引。索引语料库会随着时间变化，例如新鲜视频的上传。但它通常覆盖了90%以上的训练样本。

离线实验

对于所有点击是视频赋 $r_{i}=1$ 。当检索点击视频时通过召回来评估模型效果。本文为离线实验简化了奖励函数，因为对于连续的奖赏定义合适的离线指标并不明显。为了兼容序列训练，设置训练器完成15天（ $d_{0}$ ）后的训练再开始评估模型效果，并开始等待新数据。对于 $d_{0}$ 后的每天，保留10%的数据用于评估。为了说明每周的模式，本文报告了7天平均的离线结果，即从 $d_{0}+1$ 到 $d_{0}+7$ 。

youtube-two-tower-table2.jpg

在线实验

因为通过用户的点击来推荐视频并不是理想的，因此对于线上实验，本文通过奖励（权重）的方式来训练模型，以反映用户对点击视频的真正参与度。

youtube-two-tower-table3.jpg

七小结

相比MMoE那两篇，这篇看起来还是有点费劲的，本文不单是简单的网络结构的修改，而是训练方法上，流程上的优化，公式也比较多。干货也有不少，也有不少工程实践上的细节，例如样本加权，embedding归一化，超参温度 $\tau$ 的影响等等，非常值得学习参考。

素质四连

要解决什么问题

YouTube召回系统中大规模候选带来的采样偏差

用了什么方法解决

提出流式item频率预估算法，融入校正softmax进行训练

效果如何

YouTube在线互动指标提升0.37%个点

还存在什么问题

pass

算法背后的模式和原理

损失函数优化