Question

1. 推荐系统帮助用户在很多互联网服务中发现感兴趣的内容，包括视频推荐、app 推荐、以及在线广告 targeting 。在很多情况下，这些系统在严格延迟latency 的要求下，将数十亿用户连接到来自数百万甚至数十亿规模的内容语料库中的 item 。

   一种常见的做法是将推荐视为检索和排序问题retrieval-and-ranking problem ，并设计一个两阶段系统。也就是说，一个 scalable 检索模型首先从大型语料库中检索一小部分相关的 item，然后一个排序模型基于一个或多个目标（例如点击或用户评分）对检索到的 item 进行重排 re-rank 。这里我们聚焦于为个性化推荐构建一个真实世界的、可扩展scalable 的检索系统。

   给定 {user, context, item} 三元组，构建可扩展检索模型的常见解决方案是：

   • 分别学习 {user, context} 的 query representation 和 {item} 的 item representation 。
   • 在 query representation 和 item representation 之间使用简单的评分函数（如内积）来获得为 query 量身定制的推荐。

   其中，context 通常表示具有动态性质的变量，如一天中的时间、用户正在使用的设备。

   面对众所周知的冷启动问题cold-start problem，现实世界的系统需要适应数据分布data distribution的变化，以便更好地呈现新鲜的内容fresh content 。

   近年来，由于深度学习在计算机视觉和NLP 方面的成功，有大量工作将深度神经网络DNN 应用于推荐。deep representation 非常适合在低维 embedding 空间中编码复杂的用户状态和 item 内容特征。这里以双塔 DNN 模型为例，如下图所示，其中左塔编码了 {user, context} 、右塔编码了 {item} 。

   

   DNN 模型计算 softmax 时通常不会考虑所有可能的 item，而是使用来自固定词表fixed vocabulary 的负样本来优化训练。但是在流式streaming在线训练online learning场景下，词表不再固定（因为新item 的不断涌入），因此另一种优化方式是考虑 batch softmax 优化，其中 item 概率是在一个随机 batch 中的所有 item 上计算的，从而作为训练双塔 DNN 的通用方法。

   然而正如实验所示，batch softmax 受采样偏差sampling bias 的影响，可能会严重限制模型性能，特别是在item 分布高度倾斜的情况下。MLP 模型研究了重要性采样importance sampling 以及相应的偏差缩减 bias reduction 技术。受到这些工作的启发，论文 《Sampling-Bias-Corrected Neural Modeling for Large Corpus Item Recommendations》提出使用估计的 item 频率来纠正 batch softmax 的采样偏差sampling bias。与固定词表相比，论文提出的方法可以处理流式数据streaming data ，其中词表和item 分布随着时间发生变化。此外，论文还提出了一种通过梯度下降来估计 item 频率的新算法。另外，论文应用偏差校正建模bias-corrected modeling，并扩展scale 它来构建个性化的 YouTube 推荐检索系统。最后，论文还介绍了一种序贯sequential训练策略，旨在结合流式数据以及系统的indexing 组件、serving 组件。

   论文主要贡献：

   • 流式频率估计Streaming Frequency Estimation：论文提出了一种新的算法，从而在词表和 item 分布动态变化的情况下估计流式数据中的 item 频率。论文的分析结果给出了估计的方差和偏差。论文还提供了仿真来证明该方法在捕获数据动态方面的有效性。
   • 建模框架Modeling Framework：论文为构建大规模检索系统提供了一个通用的建模框架。具体而言，论文将估计的item 频率融合到 batch softmax 的交叉熵损失中，以减少 in-batch item 的采样偏差。
   • YouTube 推荐：论文描述了如何应用建模框架为 YouTube 推荐构建大规模检索系统。论文介绍了端到端系统，包括训练组件、索引组件、服务组件。
   • 离线和在线实验：论文对两个真实世界的数据集进行了离线实验，并证明了采样偏差校正的有效性。论文还表明，为 YouTube 构建的检索系统可以提高在线实验中的互动engagement 指标。

2. 相关工作：这里我们概述了相关工作，并强调了这些工作与我们贡献的联系。

   • 内容感知和神经推荐器Neural Recommender：利用用户和 item 的内容特征对于提高泛化能力和缓解冷启动问题至关重要。

     有一系列研究侧重于将内容特征纳入经典的矩阵分解matrix factorization: MF 框架。例如，广义矩阵分解模型（如 SVDFeature 和 Factorization Machine: FM）可用于融合 item 内容特征。这些模型能够捕获双线性bi-linear ，即特征之间的二阶交互。

     近年来，深度神经网络 DNN 已被证明可以有效提高推荐准确性。由于高度的非线性，DNN 相比于传统的分解方法，可以提供更强大的捕获复杂特征交互的能力。《Neural Collaborative Filtering》直接应用了协同过滤的直觉，并提供了一种 neural CF: NCF 的架构来对 user-item 交互进行建模。在 NCF 框架中，user embedding 和 item embedding 被拼接起来并通过多层神经网络传递从而获得最终预测。我们的工作在两个方面与 NCF 不同：

     • 我们利用双塔神经网络对 user-item 交互进行建模，以便可以在亚线性时间内对大量 item 语料库进行推断。
     • NCF 的学习依赖于 point-wise 损失（例如平方损失或者对数损失），而我们引入了多类 softmax 损失并显式建模了 item 频率。

     在另一项工作中，深度循环模型（如 LSTM）将时间信息和历史事件融合到推荐中。除了学习独立的 user representation 和 item representation 之外，还有另一些工作专注于设计神经网络，特别 是learned to rank 系统。值得一提的是，多任务学习 multi-task learning 一直是优化复杂推荐系统多个目标的核心技术。《Wide Deep Learning for Recommender Systems》 引入了一个 Wide & Deep 框架，该框架具有联合训练的 wide 线性模型和 deep 神经网络模型。

   • 极端分类 Extreme Classifcation：softmax 是模型中最常用的函数之一，可用于预测高达数百万个 label 的大型输出空间。

     许多研究一直专注于为大类别large number of classes 训练 softmax 分类模型。当类别数量非常大时，一种广泛使用的加速训练技术是对类别子集进行采样。《Adaptive Importance Sampling to Accelerate Training of a Neural Probabilistic Language Model》 表明，良好的采样分布应该能够适应模型的输出分布。为了避免计算采样分布的复杂性，很多现实世界的模型采用简单的分布，例如均匀分布。最近 《Adaptive Sampled Softmax with Kernel Based Sampling》 设计了一种高效且自适应的 kernel based 采样方法。尽管 sampled softmax 在各个领域取得了成功，但是不适用于 label 具有内容特征的情况。在这种情况下，自适应采样仍然是一个悬而未决的问题。

     各种工作表明， tree-based 的标签结构，例如 hierarchical softmax ，可用于构建大规模分类模型，同时显著减少推断时间。这些方法通常需要基于某些离散属性categorical attributes 的预定义树结构。因此，它们不适用于融合多种类型的输入特征。

   • 双塔模型：构建具有双塔的神经网络最近已经成为几种 NLP 任务的流行方法，包括建模 sentence 相似性、response 建议、基于文本的信息检索。我们的工作对这方面的研究做出了贡献，具体而言是证明了双塔模型在构建大规模推荐系统方面的有效性。

     值得注意的是，与上述文献中的很多语言任务相比，我们关注的是语料库规模更大的问题，这在我们的目标 application （如 YouTube ）中很常见。通过在线实验，我们发现显式建模 item 频率对提高该 setting 中的检索准确性至关重要。然而，这个问题在现有的工作中并未得到很好的解决。

19.1 模型

19.1.1 模型框架

1. 我们考虑推荐问题的常见 setting，其中我们有一个 query 集合 $ \{x_i\}_{i=1}^N $ ，以及一个 item 集合 $ \{y_j\}_{j=1}^M $ 。其中 $ N $ 为 query 数量、 $ M $ 为 item 数量。

   令 query 集合由特征向量集合 $ \left\{\mathbf{\vec x}_i\right\}_{i=1}^N $ 来表示，item 集合由特征向量集合 $ \left\{\mathbf{\vec y}_j\right\}_{j=1}^N $ 来表示。这里 $ \mathbf{\vec x}_i\in \mathcal X,\mathbf{\vec y}_j\in \mathcal Y $ 都是各种特征（例如稀疏的 ID 特征和稠密的数值特征）的混合，并且可能维度非常高。其中 $ \mathcal X $ 为 query 特征空间、 $ \mathcal Y $ 为 item 特征空间。在个性化场景中，我们假设 $ \mathbf{\vec x}_i $ 完全捕获了用户信息和上下文信息。

   推荐任务的目标是检索给定 query 的 item 子集。

   注意，我们从有限数量的 query 和 item 开始解释，但是我们的建模框架并没有这样的假设。

   即 query 集合以及 item 集合可能都不是固定的，而是动态增加的。

2. 我们旨在建立一个具有两个 parameterized 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 $ 和 query/item 特征映射到一个 $ k $ 维 embedding 空间。我们聚焦于 $ u(\cdot),v(\cdot) $ 是由两个深度神经网络表示的情况。

   模型的输出是两个 embedding 的内积，即：

   $ s\left(\mathbf{\vec x},\mathbf{\vec y}\right) = u\left(\mathbf{\vec x};\theta\right)^\top v\left(\mathbf{\vec y};\theta\right) $

   任务目标是是从由 $ T $ 个样本组成的训练集 $ \mathcal T:=\left\{(\mathbf{\vec x}_i,\mathbf{\vec y}_i,r_i)\right\}_{i=1}^T $ 中学习模型参数 $ \theta $ ，其中 ：

   • $ (\mathbf{\vec x}_i,\mathbf{\vec y}_i ) $ 表示 query $ \mathbf{\vec x}_i $ 和 item $ \mathbf{\vec y}_i $ 的 pair 对。
   • $ r_i\in \mathbb R $ 为每个 pair 对的奖励reward 。通常我们将互动 engagement的视频视为正的 label，但是我们构建了一个奖励 $ r_i $ 来反映用户对视频互动的程度。例如， $ r_i=0 $ 表示观看时间很短的点击行为， $ r_i=1 $ 表示整个视频都看完了的点击行为。

3. 直观地看，检索问题可以被视为一个多分类问题。给定一个 query $ x $ ，从 $ M $ 个 item $ \{y_j\}_{j=1}^M $ 中挑选候选item $ y $ 的概率的常见选择是基于 softmax 函数，即：

   $ p(y\mid x;\theta) = \frac{\exp\left(s\left(\mathbf{\vec x},\mathbf{\vec y}\right)\right)}{\sum_{j=1}^M \exp\left(s\left(\mathbf{\vec x},\mathbf{\vec y}_j\right)\right)} $

   进一步地，我们考虑以下加权对数似然函数作为损失函数，权重为 reward：

   $ \mathcal L_T(\theta) := - \frac{1}{T}\sum_{i=1}^T r_i\times \log \left(p(y_i\mid x_i;\theta) \right) $

   当 $ M $ 非常大时，在计算 $ p(y\mid x;\theta) $ 中的分母时包含所有候选 item 是不可行的。一个常见的想法是使用 item 的子集。我们聚焦于处理流式数据streaming data 。因此，与从固定语料库中抽取负样本来训练 MLP 模型不同，我们考虑仅使用 in-batch 的 item 来作为同一个 batch 内所有其它 query 的负样本。准确地说，给定mini-batch 中的 $ B $ 个 pair 对 $ \mathcal B=\left\{\left(x_i,y_i,r_i\right)\right\}_{i=1}^B $ ，batch softmax 为：

   $ p_B\left(y_i\mid x_i;\theta\right) =\frac{\exp\left(s\left(\mathbf{\vec x}_i,\mathbf{\vec y}_i\right)\right)}{\sum_{j=1}^B \exp\left(s\left(\mathbf{\vec x}_i,\mathbf{\vec y}_j\right)\right)},\quad 1\le i\le B $

4. 在我们的目标 application 中，in-batch 的 item 通常从幂律分布中采样而来。结果， $ p_B\left(y_i\mid x_i;\theta\right) $ 引入了对 full softmax 的很大的 bias：热门的 item 由于被包含在一个 batch 中的可能性很高，从而被过度惩罚为负样本。受到 sampled softmax 模型中使用的 logQ 校正的启发，我们通过以下等式校正：

   $ s^c\left(\mathbf{\vec x}_i,\mathbf{\vec y}_j\right) = s\left(\mathbf{\vec x}_i,\mathbf{\vec y}_j\right) - \log(p_j) $

   这里 $ p_j $ 表示在一个随机 batch 中 item $ j $ 的采样概率。我们把 $ p_j $ 的估计estimation 推迟到下一节详述。

   $ p_j $ 的物理意义：在所有正样本中，样本 item $ j $ 出现的概率。因为训练 batch 都是正样本的 pair 。

   通过校正，我们有（注意，对于 positive 样本我们仍然使用 $ s(\cdot,\cdot) $ 函数）：

   $ p_B^c\left(y_i\mid x_i;\theta\right) =\frac{\exp\left(s \left(\mathbf{\vec x}_i,\mathbf{\vec y}_i\right)\right)}{(s \left(\mathbf{\vec x}_i,\mathbf{\vec y}_i\right)+\sum_{j=1,j\ne i}^B \exp\left(s^c\left(\mathbf{\vec x}_i,\mathbf{\vec y}_j\right)\right)} $

   然后我们得到batch 损失函数为：

   $ \mathcal L_B(\theta) := - \frac{1}{B}\sum_{i=1}^B r_i\times \log \left(p_B^c(y_i\mid x_i;\theta) \right) $

   我们以学习率 $ \gamma $ 来在 SGD 中更新模型参数，即：

   $ \theta\leftarrow \theta - \gamma \times \nabla_\theta \mathcal L_B $

   注意， $ \mathcal L_B $ 不需要一组固定的 query 或候选 item。因此，上述更新方程可用于分布随时间变化的流式训练数据streaming training data 。

5. 采样方差校正的训练算法：

   • 输入：

     • embedding 函数 $ u(\cdot,\theta),v(\cdot,\theta) $ 。
     • 学习率 $ \gamma $ 。

   • 输出：训练好的模型参数 $ \theta $ 。

   • 算法步骤：

     • 反复迭代直到模型收敛，迭代步骤为：

       • 从stream 中接收或者随机采样一个 batch 的训练样本 $ \left\{\left(x_i,y_i,r_i\right)\right \}_{i=1}^B $ 。
       • 根据频率估计frequency estimation 算法来预估每个 $ y_i $ 的采样概率 $ p_i $ 。
       • 计算损失函数 $ \mathcal L_B(\theta) $ 。
       • 更新模型参数 $ \theta\leftarrow \theta - \gamma \times \nabla_\theta \mathcal L_B $ 。

     • 返回训练好的模型参数 $ \theta $ 。

6. 最近邻搜索Nearest Neighbor Search：一旦学习了 embedding 函数 $ u(\cdot,\theta),v(\cdot,\theta) $ ， 那么 inference 包含两个步骤：

   • 计算 query embedding $ u(\mathbf{\vec x};\theta) $ 。
   • 对从 embedding 函数 $ v(\cdot,\theta) $ 预先计算的一组 item embedding 执行最近邻搜索。

   对于近似的最大内积搜索maximum inner product search: MIPS 问题，低延迟检索通常采用基于哈希技术的高效相似性搜索系统，而不是计算所有item 的内积来得到 top item 。因为这不是我们关注的重点，因此不再详述。

7. 归一化和温度Normalization and Temperature：经验上，我们发现增加embedding 归一化可以提高模型的可训练性trainability ，从而导致更好的检索质量。即：

   $ u\left(\mathbf{\vec x},\theta\right) \leftarrow \frac{u\left(\mathbf{\vec x},\theta\right)}{\left\|u\left(\mathbf{\vec x},\theta\right)\right\|_2},\quad v\left(\mathbf{\vec x},\theta\right) \leftarrow \frac{v\left(\mathbf{\vec x},\theta\right)}{\left\|v\left(\mathbf{\vec x},\theta\right)\right\|_2} $

   此外，我们添加温度 $ \tau $ 到每个 logit 从而锐化sharpen 预测结果，即：

   $ s\left(\mathbf{\vec x},\mathbf{\vec y}\right) = \frac{u\left(\mathbf{\vec x};\theta\right)^\top v\left(\mathbf{\vec y};\theta\right)}{\tau} $

   在实践中， $ \tau $ 是一个超参数，并根据最大化检索指标（如recall 或 precision）来调优。

19.1.2 频率估计

1. 在本节中，我们详细说明流的频率估计streaming frequency estimation 。

2. 考虑随机batch 的一个stream，其中每个 batch 包含一组 item 。问题是估计每个 batch 中，命中hitting 每个 item 的概率（即包含每个 item 的概率）。

   一个关键的设计准则是：当有多个训练jobs （即 workers ）时，可以用一个完全分布式的估计distributed estimation 来支持分布式训练。

   在单机训练或分布式训练中，一个 unique global step 代表 trainer 消耗的 data batch 编号，并且和每个采样的 batch 关联。在分布式setting 下，global step 通常通过参数服务器parameter servers 在多个 workers 之间同步。因此，我们可以利用 global step ，将一个 item 的频率 $ p $ 的估计转换为 $ \delta $ 的估计，其中 $ \delta $ 表示item 的两次连续 hit 之间的平均step 。例如，如果每隔 50 step 采样到一个 item，那么我们有 $ p=0.02 $ 。

   使用 global step 为我们提供了两个好处：

   • 通过读取和修改 global step，多个 worker 隐式地同步了频率估计。
   • $ \delta $ 的估计可以通过简单的移动平均更新moving average update 来实现。这种方式可以适应分布的变化 distribution change。

3. 为了记录不同 item 的平均hit间隔，使用固定的 item 词表通常不现实（因为不断有新的item 出现），这里我们应用哈希数组来记录。注意，引入哈希可能会导致潜在的哈希冲突，我们在后文中重新讨论这个问题并提出改进算法。

   我们分配两个长度为 $ H $ 的数组 $ A $ 和 $ B $ 。假设 $ h(\cdot) $ 是一个将任何 item 映射到 $ \{1,2,\cdots,H\} $ 中的整数的哈希函数，其中哈希映射可以基于 ID 或者其他任何item 特征。那么对于给定的 item $ y $ ， $ A[h(y)] $ 记录当 $ y $ 被 hit 时的latest step， $ B[h(y)] $ 记录 $ y $ 的 $ \delta $ 估计。

   我们使用数组 $ A $ 来帮助更新数组 $ B $ 。 一旦item $ y $ 在 global step t 中出现（即hit ），我们依次更新数组 $ B $ 和数组 $ A $ 为：

   $ B[h(y)] \leftarrow (1-\alpha)\times B[h(y)] + \alpha \times (t - A[h(y)])\\ A[h(y)] = t $

   其中：

   • $ t-A[h(y)] $ 为 item $ y $ 最近一次出现的间隔。
   • $ B[h(y)] $ 基于加权平均来更新 item $ y $ 的出现间隔，其中：最近的出现间隔权重为 $ \alpha $ ，历史平均出现间隔的权重为 $ (1-\alpha) $ 。
   • $ A[h(y)] $ 更新为 $ t $ ，即 item $ y $ 的最新的出现 gloal step 。

   为了得到 item $ y $ 的采样概率估计 $ \hat p $ ，我们可以简单地认为 $ \hat p = 1/B[h(y)] $ 。

   物理意义：item 出现频率 = 1 / item 出现的平均周期。这里 B 记录每个 item 出现的平均周期（以移动均值来更新）。

4. 流式频率估计算法Streaming Frequency Estimation：

   • 输入：

     • 学习率 $ \alpha $ 。
     • 长度为 $ H $ 的数组 $ A $ 和 $ B $ 。
     • 哈希函数 $ h(\cdot) $ ，其输出空间为 $ \{1,2,\cdots,H\} $ 。

   • 输出：每个 item $ y $ 的采样概率 $ \hat p $ 。

   • 算法步骤：

     训练期间：

     • $ \text{ for global steps } t = 1,2,\cdots $ 迭代，直到停止条件。迭代步骤为：

       采样一个 batch 的 item $ \mathcal B $ 。对于每个 item $ y\in \mathcal B $ ，执行：

       $ B[h(y)] \leftarrow (1-\alpha)\times B[h(y)] + \alpha \times (t - A[h(y)])\\ A[h(y)] = t $

     推断期间：

     对于任意 item $ y $ ，采样概率为 $ \hat p = 1/B[h(y)] $ 。

5. 对于给定的 item，假设两次连续 hit 之间的 step 遵循随机变量 $ \Delta $ 表示的分布，其中随机变量的均值为 $ \delta = \mathbb E[\Delta] $ 。这里我们的目标是从样本流 stream 中估计 $ \delta $ 。

   随机变量 $ \Delta $ 表示 item 出现的周期。

   每当这个 item 在 global step t 的 batch 中出现时， $ t-A[h(y) ] $ 是 $ \Delta $ 的一个新样本。因此，上述更新可以理解为以固定学习率 $ \alpha $ 运行 SGD 来学习这个随机变量的均值。

   理论上，如果没有哈希碰撞的情况下，接下来的命题Proposition 显示了这个在线估计的偏差bias和方差variance。

   命题：假设 $ \{\Delta_1,\cdots,\Delta_t\} $ 为随机变量 $ \Delta $ 独立同步分布采样得到的采样序列。令 $ \delta = \mathbb E[\Delta] $ 。考虑一个在线估计online estimation ，其中 $ i\in \{1,2,\cdots,t\},\alpha \in (0,1) $ ：

   $ \delta_i = (1-\alpha)\times \delta_{i-1} + \alpha \times \Delta_i $

   则：

   • 估计的偏差为： $ \mathbb E[\delta_t] - \delta=(1-\alpha)^t\times\delta_0 - (1-\alpha)^{t-1}\times\delta $ 。
   • 估计的方差为： $ \mathbb E\left[\left(\delta_t - \mathbb E[\delta_t]\right)^2\right]\le (1-\alpha)^{2t}\times(\delta_0-\delta)^2 + \alpha \times\mathbb E\left[\left(\Delta_1-\alpha)^2\right)\right] $ 。

   其中 $ \delta_0 $ 为 $ \delta $ 的初始估计。

   证明见原始论文。

   上式表明：

   • 当 $ t\rightarrow \infty $ 时，估计的偏差 $ |\mathbb E[\delta_t] - \delta|\rightarrow 0 $ 。

   • 理想的初始化 $ \delta_0= \delta/(1-\alpha) $ 将导致每一个step 的无偏估计。

   • 估计的方差的上界由 $ (1-\alpha)^{2t}\times(\delta_0-\delta)^2 + \alpha \times\mathbb E\left[\left(\Delta_1-\delta)^2\right)\right] $ 给出。可以看到学习率 $ \alpha $ 在两个方面影响方差：

     • 较大的学习率导致依赖于初始误差 $ (\delta_0 - \delta) $ 的第一项更快下降。
     • 较大的学习率增加了取决于 $ \Delta_1 $ 方差的第二项，并且这一项不会随着时间而减少。

6. 分布式更新：我们考虑分布式训练框架，其中模型的 parameter 分布在一组称作参数服务器parameter server 的服务器上，多个 worker 独立地处理训练数据，并与参数服务器通信以获取和更新模型parameter。

   Streaming Frequency Estimation 算法可以扩展到这个 setting。

   • 数组 A 、B、global step 这些参数分布在参数服务器上。
   • 每个 worker 采样一个 mini-batch 的 item ，并从参数服务器获取 $ A[h(y)], B[h(y)] $ 。
   • 然后每个 worker 更新 $ A[h(y)], B[h(y)] $ 并发送回参数服务器。

   因此，Streaming Frequency Estimation 算法可以和神经网络的异步随机梯度下降训练一起执行。

7. 多重哈希 Multiple Hashing：受到 count-min sketch 中类似思想的启发，我们扩展了Streaming Frequency Estimation 算法以利用多个哈希函数来缓解由于哈希碰撞而导致的 item 频率高估。我们给出 $ m $ 个数组 $ \{A_i\}_{i=1}^m $ 和 $ m $ 个数组 $ \{B_i\}_{i=1}^m $ 。每个数组 $ A_i,B_i $ 的更新遵循 Streaming Frequency Estimation 算法相同的步骤。

   考虑到哈希碰撞， $ B_i[h(y)] $ 可能是对 item $ y $ 的 hit 间隔的低估，因为可能另一个不同的 item $ y^\prime $ 也被存储到该分桶。因此在推断时，我们使用 $ m $ 个估计值的最大值来表示 hit 间隔。

8. 多重哈希Streaming Frequency Estimation：

   • 输入：

     • 学习率 $ \alpha $ 。
     • 长度为 $ H $ 的 $ m $ 个数组 $ \{A\}_{i=1}^m $ 和 $ m $ 个数组 $ \{B\}_{i=1}^m $ 。
     • 输出空间为 $ \{1,2,\cdots,H\} $ 的 $ m $ 个哈希函数 $ \{h(\cdot)\}_{i=1}^m $ 。

   • 输出：每个 item $ y $ 的采样概率 $ \hat p $ 。

   • 算法步骤：

     训练期间：

     • $ \text{ for global steps } t = 1,2,\cdots $ 迭代，直到停止条件。迭代步骤为：

       采样一个 batch 的 item $ \mathcal B $ 。对于每个 item $ y\in \mathcal B $ ，执行：

       $ B_i[h_i(y)] \leftarrow (1-\alpha)\times B_i[h_i(y)] + \alpha \times (t-A_i[h_i(y)])\\ A_i[h_i(y)]\leftarrow t $

     推断期间：

     对于任意 item $ y $ ，采样概率为 $ \hat p = 1/\max_i\{B_i[h_i(y)]\} $ 。

19.1.3 Youtube 的神经检索系统

1. 我们应用所提出的建模框架并对其进行扩展scale，以针对 YouTube 中的一个特定产品构建大规模神经检索系统neural retrieval system 。该产品根据用户正在观看的视频（称为种子视频）生成视频推荐。

   推荐系统由两阶段组成：检索retrieval、排序 ranking 。在检索阶段我们有多个检索器，每个检索器在给定用户和种子视频的条件下生成数百个候选推荐视频。这些候选视频随后由排序模型进行打分和重排。

   在本节中，我们聚焦于在检索阶段构建一个新的、额外的检索器。

   这里的检索模型对每个种子视频输出数百个候选推荐，因此每个种子视频就是一个 trigger。假如用户有很多种子视频，那么就将这些 trigger 召回的结果进行合并。因此可以看到：模型每次仅处理一个种子视频，而不是将所有种子视频馈入到模型中。

   至于是处理单个种子视频、还是处理历史种子视频序列，哪个效果更好，可能需要通过实验来分析。

2. 模型概览：我们构建的 YouTube 神经检索模型由 query 网络和候选candidate 网络组成，如下图所示。在任何时间点，用户正在观看的视频（即种子视频），提供了关于用户当前兴趣的强烈信号。 因此，我们利用了用户观看历史中的大量种子视频的特征。构建候选 tower 是为了从候选视频特征中学习。

   • 训练 label：视频点击被视为正的 label。此外，对于每次点击我们构建了一个奖励 $ r_i $ 来反映用户对视频的不同程度的互动engagement 。例如， $ r_i=0 $ 表示观看时间很短的点击视频， $ r_i=1 $ 表示整个视频都看完了。奖励用于损失函数的样本加权。

   • 视频特征：我们使用的视频特征包括离散特征和连续特征。

     离散特征包括视频ID、频道 ID。对于这些实体entity 中的每一个，我们都创建 embedding 层从而将每个离散特征映射到稠密向量。

     通常我们处理两种类型的离散特征：

     • 某些特征是离散的单个值，如视频 ID 对于每个视频仅有一个取值。因此我们有一个 embedding 向量来表示它。
     • 某些特征是离散的多个值，如视频的主题可能包含多个取值。因此我们有多个 embedding 向量，并取它们的加权作为该特征的 embedding 。

     为了处理 out-of-vocabulary 的实体，我们将这些 oov 实体随机分配到一组固定的哈希桶中，并学习每个哈希桶的 embedding。哈希桶对于模型捕获 YouTube 中可用的新实体很重要。

     对哈希之后的 ID 进行 embedding，这解决了需要人工为实体分配 ID 的映射工作。

   • 用户特征：除了种子视频之外，我们还使用了用户的观看历史来捕获用户的兴趣。其中一个用户特征的例子是：用户最近观看的 $ k $ 个视频id 的序列。我们将观看历史视为 bag of words: BOW，并通过视频 id 的 embedding 的均值来表示它。

     在 query 塔中，用户特征和种子视频特征在input layer 融合，然后通过前馈神经网络传递。

   • 对于相同类型的 id，embedding 是在相关特征之间共享的。例如，同一组视频id embedding 用于种子视频、候选视频、用户历史观看视频。

     我们实验了非共享 embedding ，但是没有观察到显著的模型质量提升。

   

3. 序贯训练sequential training：我们的模型在 Tensorflow 中实现，并在分布式系统（包含多个 worker 和 parameter server ）上使用分布式梯度下降进行训练。在 YouTube 中，每天都会生成新的训练数据，训练集也相应地按天进行组织。

   模型训练以下列方式利用这种序贯结构sequential structure：trainer 按照从最老的训练样本到最近的训练样本按顺序使用数据。一旦 trainer 赶上最新一天的训练数据，它就会等待第二天的训练数据到达。通过这种方式，模型能够跟上最新的数据分布的变化。

   训练数据本质上是由 trainer 以流式streaming 的方式消费的，我们应用Streaming Frequency Estimation算法 （如果使用多个哈希，则使用多重哈希 Streaming Frequency Estimation算法 ）来估计 item 频率。

4. Indexing 和 Model Serving：检索系统中的 index pipeline 会定期创建一个 Tensorfow SavedModel 用于在线 serving。index pipeline 分为三个阶段：候选样本生成candidate example generation 、embedding inference、embedding indexing，如下图所示。

   • 在候选样本生成阶段，基于一定的标准从 YouTube 语料库中挑选一组视频。这些视频的特征被提取并添加到候选样本中。
   • 在embedding inference 阶段，Neural Retrieval Model 的右塔（候选 item 塔）用于计算候选样本的 embedding。
   • 在 embedding indexing 阶段，我们训练一个基于树和量化哈希技术的、 Tensorfow-based 的embedding index model。我们掩盖了细节，因为这不是本文的重点。
   • 最后，serving 中使用的 SavedModel 是通过Neural Retrieval Model的 query 塔和 indexing model 拼接在一起而创建的。

   

19.2 实验

1. 这里我们展示了实验结果，以证明所提出的 item 频率估计和建模框架的有效性。

19.2.1 频率估计仿真

1. 为了评估Streaming Frequency Estimation算法和多重哈希Streaming Frequency Estimation算法的有效性，我们从仿真研究开始，首先将应用每个算法来拟合固定的 item 分布，然后在某个 step 后改变 item 分布。

   具体而言，在我们的 setting 中，我们使用一组固定的 $ M $ 个 item，并且每个 item 都根据概率 $ q_i\propto i^2, 1\le i\le M $ 独立采样，其中 $ \sum_i q_i = 1.0, q_i \ge 0 $ 。

   我们在一个输入流input stream 上进行仿真，其中每个 step 都采样一个 batch 的 item $ \mathcal B $ 。这里 $ \mathcal B $ 中的每个 item 都是以概率 $ q_i $ 进行有放回的采样。因此我们要拟合的 item 的 hit 概率为 $ p_i = |\mathcal B|\times q_i $ 。

   我们在前 $ t $ 个 step 保持固定的采样分布，然后在剩下的 step 中切换为另一个采样分布 $ q_i\propto (M-1-i)^2 $ 。

   为了评估 esitmation 的准确性accuracy，我们计算 esitmation的概率集合 $ \left\{\hat p_i\right\}_{i=1}^M $ 和实际的概率集合 $ \{p_i\}_{i=1}^M $ 之间的 $ L_1 $ 距离，然后进行归一化从而作为估计误差estimation error 。即：

   $ \text{estimation error} = \frac{1}{2|\mathcal B|} \sum_i|\hat p_i - p_i| $

   具体而言，我们报告了学习率 $ \alpha $ 的影响，以及多重哈希的影响。

2. 学习率 $ \alpha $ 的影响：我们设置 $ M=1000 $ 、 $ B=128 $ 、数组 $ A $ 和 $ B $ 的长度均为 $ H=5000 $ 。此外，我们使用全零来初始化数组 $ A $ 、用值 100 来初始化数组 $ B $ 。分布切换发生在 step $ t=10000 $ 的地方。我们使用一个哈希函数并运行Streaming Frequency Estimation算法。

   下图给出了不同的学习率 $ \alpha $ 在一组 global step 上的估计误差。可以看到：

   • 三条曲线都收敛到某个误差水平 error level，该误差水平来自于哈希冲突和估计方差estimation variance 。
   • 学习率越高，算法对分布变化的适应能力越强，但是最终方差更高，如前述的命题所示。

   可以在学习初期以高的学习率快速收敛，然后用低的学习率降到更低的方差，这样可以结合两方面的优势。

   

3. 多重哈希的影响：在第二个仿真中我们运行多重哈希Streaming Frequency Estimation算法，并使用不同数量（以参数 $ m $ 表示）的哈希函数进行实验。对于不同的 $ m $ ，我们选择不同的数组大小 $ H $ ，从而使得哈希桶的总数保持不变。

   下图显示了 $ m=1,2,4 $ 的估计误差曲线。可以看到：多个哈希函数可以减少估计估计误差，即使是在参数数量相同的情况下。

   

19.2.2 Wikipedia Page 检索

1. 在本节中，我们在维基百科数据集上进行页面 page 检索实验，以展示采用偏差校正sampling-bias-corrected 的 batch loss 的效果。

2. 数据集：我们考虑预测维基百科页面之间的站内链接intra-site link 的任务。

   • 对于给定的一对源页面和目标页面 $ (x,y) $ ，如果存在从 $ x $ 到 $ y $ 的链接，则label = 1，否则 label = 0 。
   • 每个页面都由一组内容特征表示，包括页面 URL、页面标题中 n-grams 单词组成的 bag-of-word: BOW 的 representation、页面类目的 bag-of-word: BOW 的 representation。

   我们对英文的 graph 进行了实验，它包含 530 万个页面、43亿条链接、51 万个标题 n-grams、40.34 万个unique 类目。

3. 模型：我们将链接预测视为检索问题，其中给定一个源页面，任务是从页面语料库中检索目标页面。因此，我们训练了一个双塔神经网络，其中左塔映射源页面特征、右塔映射目标页面特征。

   • input feature embedding 在两个塔之间共享。
   • 每个塔都有两个全连接的 ReLU 层，维度为 [512,128] 。

4. baseline：

   • 我们将所提出的、采用偏差校正的 batch softmax （即 $ p^c_B\left(y_i\mid x_i;\theta\right) $ ，记作 correct-sfx） 和没有任何校正的 batch softmax（即 $ p_B\left(y_i\mid x_i;\theta\right) $ ，记作 plain-sfx ）进行比较，从而证明偏差校正的效果。

   • 此外，我们还考虑了推荐任务的隐式反馈建模中广泛采用的均方损失。损失是在观察到的 pair 对上的 MSE 和正则化项的组合。这个正则化项迫使所有未观察到的 pair 对的距离尽可能到一个常数的先验prior（通常为 0.0，表示不存在链接）。

     具体而言，这个损失函数为：

     $ \mathcal L = \frac{1}{|\Omega|}\sum_{(x_i,y_i)\in \Omega}\left(u(\mathbf{\vec x}_i)^\top v(\mathbf{\vec y}_i) - r_i\right)^2 + \lambda\times \frac{1}{|\Omega^c|}\sum_{(x_i,y_i)\in \Omega^c} \left(u(\mathbf{\vec x}_i)^\top v(\mathbf{\vec y}_i)\right)^2 $

     其中：

     • $ \Omega $ 为所有观察到的pair 对； $ \Omega^c $ 为 $ \Omega $ 的补集，表示未观察到的 pair 对。
     • $ \lambda $ 为一个正的超参数，表示正则化系数。

     在矩阵分解中，这种损失通常使用交替最小二乘法alternating least square: ALS 或者坐标下降法coordinate descent: CD 来训练。最近，Krichene 等人通过随机梯度下降 SGD 扩展了 Gramian 计算方法到非线性的场景。我们称之为 mse-gramian 。

5. 配置：

   • 对于所有方法，我们使用batch size = 1024、 Adagrad 优化器、学习率 0.01、训练step 数 1000 万。

   • 对于频率估计，我们使用 $ m=1 $ 、 $ H=4 $ 千万、 $ \alpha =0.01 $ 。

   • 我们保留 10% 的链接用于评估，其中评估指标为 Recall@K 。该指标本质上是针对页面语料库在 top k 个候选中包含真实 label 的平均概率。

   • mse-gramian 中的超参数 $ \lambda $ 通过线性搜索进行调优，并报告最佳结果。

   • 归一化和温度Normalization and Temperature：

     • 我们发现归一化输出层总是可以提高模型性能和训练稳定性，因此我们只显示出归一化的结果。
     • 我们对 plain-sfx 和 correct-sfx 实验了多个温度值 $ \tau $ 。

6. 实验结果如下表所示。可以看到：

   • 对于每个温度值，correct-sfx 大大优于相应的 plain-sfx。
   • 温度对于性能的影响很有趣，这表明在应用归一化输出层时必须仔细调优温度超参数。
   • 基于 batch softmax 的方法比 mse-gramian 具有更好的性能。

   

19.2.3 YouTube 实验

1. 我们基于前面所述的神经检索系统在 YouTube 上进行了离线和在线实验。我们使用的 YouTube 训练数据包含每天数十亿次点击的视频，并且数据集包含多天。

2. 配置：

   • 如前所述，input feature embedding 在 query 塔和候选塔之间共享。我们对两个塔都使用三层 DNN，隐层维度为 [1024, 512, 128]。
   • 对于模型训练，我们使用 Adam 优化器、学习率 0.2、batch size = 8192。
   • 对于频率估计，我们使用 $ H=5 $ 千万、 $ m=1 $ 、 $ \alpha = 0.01 $ 。
   • 我们应用序贯训练。对于本节中的实验，每隔几个小时周期性地构建从 YouTube 语料库中选择的、大约 1000 万个视频的索引。索引的语料库可能会随着时间的推移而发生变化，例如有新上传的视频。

3. 离线实验：我们为所有点击的视频分配 $ r_i=1 $ ，并通过点击视频的召回率来评估模型性能。我们简化了离线实验的奖励函数。

   为了结合序贯训练，我们在 $ d_0 $ 天（设置为 15 天）之后评估模型性能，此时 trainer 完成追赶catch-up 阶段并开始等待新的数据。对于 $ d_0 $ 之后的每一天，我们保留 10% 的数据进行评估。为了说明每周的模式pattern，我们报告了连续 7 天的平均离线结果，即 $ d_0+1 $ 到 $ d_0+7 $ 。

   结果如下表所示。再次可以看到：

   • 和 mse-gramian 相比，使用 batch softmax 有着显著提升。
   • 在具有不同温度 $ \tau $ 的设置中，correct-sfx 的表现优于 plain-sfx 。

   

4. 在线实验：我们还在 YouTube 上的 A/B test 测试框架中进行在线实验。对于控制组的用户，视频是从生产系统中推荐的。对于实验组，将神经检索系统中的候选 item 添加到检索阶段之后（从而一起进入排序阶段）。

   由于仅仅向用户推荐他/她可能点击的视频还不够（还需要考虑观看完播率 $ r_i $ ），因此在线实验中，我们用奖励训练模型，从而反映用户对点击视频的真实互动engagement 。因此我们报告了点击一致的互动指标（即在点击基础之上再考虑互动），结果如下表所示。

   可以看到：

   • 增加神经检索系统大大改善了以前的生产系统。
   • 使用 correct-sfx 的模型比使用 plain-sfx 的 baseline 表现好得多，这证明了采样偏差校正的有效性。