机器学习 (ML)(十三) — 推荐系统探析

发表于 2024-10-29 分类于人工智能阅读次数： 127 本文字数： 15k 阅读时长 ≈ 49 分钟

召回 - 双塔模型

训练双塔模型需要正样本和负样本，选对正、负样本大于改进模型结构。选择正样本：如果物品给用户曝光之后，会有点击行为，就说明用户对物品感兴趣。把用户和物品二元组作为作为正样本，但是选取正样本有个问题需要解决，就是少部分物品占据了大部分点击，正样本是有点击的物品，导致正样本属于热门物品。拿过多的热门物品作为正样本，会对冷门物品不公平，这样会使热门物品更热，冷门物品更冷。解决方案是：对冷门物品过采样，或降采样热门物品。过采样 (up-sampling)：一个样本出现多次；降采样 (down-sampling)：一些样本被抛弃，以一定概率抛弃一些样本。抛弃的概率与样本的点击次数正相关。

选择负样本：无样本就是用户不感兴趣的物品，没有被召回的物品是负样本；召回了，但是没有被选中和曝光是负样本；曝光了，但是没有被用户点击的也是负样本。负样本分类：

简单负样本：未被召回的物品，大概率是用户不感兴趣的，几亿个物品中只有几千个物品被召回，所以从全体物品中做抽样就可以了，抽到的物品作为负样本。问题在于怎样做抽样？均匀抽样还是非均匀抽样？均匀抽样的坏处是对冷门物品不公平，如果在全体物品中做均匀抽样产生负样本，负样本大多是冷门物品。总拿热门物品做正样本，冷门物品做负样本，这会使热门物品更热，冷门物品更冷。所以负样本采用非均匀采样，目的是打压热门物品，负样本抽样的概率与热门物品（点击次数）正相关。热门物品成为负样本的概率大，物品的热门程度可以用点击次数来衡量。可以这样做抽样：每个物品的抽样概率正比于点击次数的 0.75 次方，0.75 是一个经验值。
Batch内负样本：设一个 batch 内有个正样本，那么一个用户可以跟个样品组成负样本。那么这个 batch 内有个负样本，这些都是简单负样本（因为第一个用户不喜欢第二个物品）。对于第一个用户来说第二个物品相当于从全体物品随机抽样的，第一个用户大概率不会喜欢第二个物品，batch 负样本存在一个问题，(用户，物品) 这个二元组都是通过点击行为选取的，第一个用户和第一个物品之所以成为正样本，原因是用户点击了物品，所以一个物品出现在 batch 内的概率正比于点击次数。也就是它的热门程度，物品成为负样本的概率应该是正比于点击次数的 0.75 次方，但这里却是正比于点击次数 1 次方，也就是说热门物品成为负样本的概率过大，这样会造成偏差。修正偏差方案是参考论文：Sampling-Bias-Corrected Neural Modeling for Large Corpus Item Recommendations，假设物品被抽样到的概率记作，则 $点击次数$ ，反映出物品的热门程度，双塔模型通常用于计算相似度，预估用户对物品的兴趣分数：，其中是用户的特征向量，是物品的特征向量，训练的时候要尽量鼓励正样本的余弦相似度大，鼓励负样本的余弦相似度小。根据上面论文中的建议：训练双塔模型的时候应该把调整为，这样可以纠偏。避免过分打压热门的物品，训练结束之后，在线上做召回时还是使用，线上做召回不用做调整。
困难负样本：是被排序淘汰的样本，比如物品被召回，但是被粗排淘汰，例如召回 5000 个物品进行粗排，粗排按照分数做截断，只保留前 500 个物品，那么被淘汰的 4500 个物品都可以被视作负样本，为什么被粗排淘汰的负样本叫做困难负样本呢？这些物品被召回，说明它们跟用户的兴趣多少有些关系，被粗排淘汰，说明用户对物品的兴趣不够强烈，所以被分为了负样本，这些正、负样本做二元分类的话，这些困难负样本容易被分错，容易被错误的判定为正样本，更困难的负样本是通过了粗排，但是精排分数靠后的物品，比方说精排给 500 个物品打分，排名在后 300 个物品都是负样本，能够通过粗排进入精排，说明物品已经比较符合用户兴趣了，但未必是用户最感兴趣的，所以在精排中排名靠后的物品视为负样本。训练双塔模型其实是一个二元分类任务，让模型区分正负样本。把全体物品作为简单负样本，则分类准确率会很高。因为它们明显跟用户兴趣不符，被粗排淘汰的物品也是负样本，但它们多少跟用户兴趣有些相关，所以分类比较困难，分类准确率会稍微低一些。精排分类靠后的物品也是负样本，这些物品跟正样本有些相似，所以它们很容易判定为正样本，对它们做分类非常困难，比较常用的做法是把简单负样本和困难负样本混合起来作为训练数据。比如 50%（全体物品中随机非均匀抽样）是简单负样本，另外 50%（从粗排和精排淘汰的物品中随机抽样）是困难负样本。
常见的错误：可以把曝光但没有点击的物品作为负样本，这是错误的。用双塔模型去召回训练，效果肯定会变差。训练召回模型不能用这样的负样本，训练排序模型会用这类负样本。

选择负样本的原理：召回的目的是快速找到用户可能感兴趣的物品。凡是用户感兴趣全部取回来，然后再交给后面的排序模型逐一做甄别，召回模型的任务是区分用感兴趣的物品和不感兴趣的物品，而不是区分比较感兴趣的物品和非常感兴趣的物品。这就是选择负样本的基本思路。

全体物品 (easy)：可以把全体物品当做负样本，把它们叫做简单负样本，这些物品绝大多数都是用户不感兴趣的，双塔模型很容易区分这些负样本；
被排序淘汰 (hard)：被召回但被粗排或精排淘汰的叫做困难负样本，这些物品能被召回说明它们跟用户的兴趣有一定的相关性，被排序模型过滤掉，说明它们跟用户的兴趣不够强烈，他们可以作负样本，这样的负样本跟正样本有点相似，做分类的时候难以区分，所以算是困难负样本。
有曝光没点击：看起来可以作为负样本，但其实不能，只要用了这样的负样本，双塔模型的效果肯定会变差，一个物品可以通过精排模型的甄别并曝光给用户，说明物品已经非常匹配用户的兴趣点，每次给用户展示几十个物品，用户不可能每个都点击，没有点击不代表不感兴趣，所以不应该把有曝光没点击的物品作为召回的负样本，他只适合训练排序模型，不适合训练召回模型。

如下图所示，这是训练好的两个塔，它们分别提取用户、物品特征，在开始双塔训练之后，线上服务之前，先用右边物品的塔提取物品的特征，把物品特征向量记作，这里有多少个物品就有多少个向量（几亿），把 < 特征向量 , 物品 ID> 保存到向量数据库，向量数据库存储物品向量和物品 ID 的二元组，用作最近邻查找，左边的用户塔不要事先计算并存储向量，而是当用户线上发起推荐请求的时候，调用神经网络在线上计算一个向量，然后把向量作为 query 去数据库中做检索，查找最近邻，也就是跟向量相似度最高的个红色向量，每个红色向量对应一个物品，k- 近邻查找一共召回了个物品，作为这条召回通道的结果返回。

左边是物品向量 b 离线存储，右边用户向量 a 线上召回

双塔模型的召回：离线存储，把物品向量存入向量数据库；线上召回，查找用户最感兴趣的个物品，给定用户 ID 和画像，线上用神经网络算用户向量，然后最近邻查找（把向量作为 query，调用向量数据库做最近邻查找，数据库返回余弦相似度最大的个物品，作为召回结果。）。

事先存储物品向量，线上现算用户向量，为什么要区别对待物品向量和用户向量呢？没做一次召回只用到一个向量，而要用到几亿物品向量，拿神经网络现算一个用户向量，计算量不大，但是几亿个物品向量显然是算不起的。所以不得不离线算好物品向量，那能不能把几亿个用户向量提前算好并存储起来，进一步减少线上负担呢？这样做当然可以，早期的时候就是这样做的。这样工程实现很简单，但这样不利于推荐的效果。用户的兴趣点是动态变化的，所以应该线上实时计算用户向量，而不是事先计算好存储起来。但是事先存储物品向量是可以的，是因为物品特征相对稳定，短期内不会发生变化。

模型的更新包括模型的全量更新和模型的增量更新：

全量更新：每天凌晨，用昨天全天的数据训练模型，而不是随机初始化。把昨天 1 天的数据去打包成 TFRecord 文件，在昨天模型参数的基础上做训练。把昨天的数据过一遍，每条数据只用 1 次，也就是训练只做 1 epoch。训练完成之后，发布新的用户塔（是在线上实时计算用户向量，作为召回的 query）神经网络和物品向量（几亿个向量存入向量数据库，向量数据库会重新建索引，在线上可以做最近邻查找），全量更新的实现相对比较容易，对数据流、整个系统的要求不高，全量更新不需要实时的数据流，对训练生成的速度没有要求。只需要把每天的数据落表，在凌晨做个批处理，把数据打包成 TFRecord 文件就可以，全量更新对系统的要求也很低，每天做一次全量更新，所以只需要把神经网络和物品向量每天发布一次就够了。
增量更新：做 online learning 更新模型参数，每隔几十分钟就把新的模型参数发布出去。为什么要做增量更新呢？这是因为用户的兴趣会随时发生变化，增量更新对数据流的要求比较高，要实时收集线上数据做流式处理，实时生成训练模型需要的 TFRecord 文件，然后对模型做 online learning，做梯度下降ID Embedding 的参数，也就是从早到晚，训练数据文件不断生成，不断做梯度下降更新模型的 Embedding 层，注意 online learning 不更新神经网络其他部分的参数，全连接层的参数都是锁住的，不做增量更新，只更新 Embedding 层的参数，只有做全量更新的时候，才会更新全连接层。模型更新之后，再把算出的用户 ID Embedding 发布出去，用户的 ID Embedding 是一个哈希表的形式，给定用户 ID，可以查出 ID Embedding 向量。发布用户 ID Embedding 的目的是为了线上计算用户向量。最新的用户 ID Embedding 能够捕捉到用户最新的兴趣点，对推荐很有帮助。发布用户 ID Embedding 的过程会有延迟，通过对系统做优化，可以将延迟降低到几十分钟或者更短。如下图所示：
全量更新 vs 增量更新

为什么只做增量更新不好呢？如果你只看一个小时的数据它是有偏的，分钟级数据差别更大。在不同的时间段用户的行为是不一样的，比如中午和傍晚的数据明显不一致，如果你只看 5 分钟的数据，那么偏差就更大了，它跟全天数据的统计值差别更大，做全量更新数据的时候，要随机排列数据，也就是 random shuffle，这样就是为了消除偏差，全量更新是在 random shuffle 数据上做，而增量更新是按照数据从早到晚的顺序上做训练。同样使用一天的数据，这两种排列顺序的方式会导致训练的效果有差别，把数据按照从早到晚的顺序进行排列，效果不如把数据随机打乱，所以全量训练的效果比增量训练更好，这就是为什么我既要做全量训练又要做增量训练。全量训练的模型更好，增量训练能够实时捕捉用户的兴趣。

双塔模型，如下图所示，左边的用户塔，右边是物品塔：

双塔模型结构

召回 - 自监督学习

自监督学习的目的是把物品塔训练的更好，为什么要做自监督学习呢？在实际的推荐系统模型中，数据上的问题会影响双塔模型的表现，推荐系统都有头部效应：少部分的物品占据了大部分的点击，大部分的物品点击次数不高。训练双塔模型的时候，用点击数据作为正样本，模型学习物品的表征，靠的就是点击行为。如果一个物品给几千个用户曝光，有好几百个用户点击，那么物品的表征就会学的比较好，反过来，长尾物品的表征就学的不够好，这是因为长尾物品的点击和曝光次数太少，训练的样本数量不够，一种比较好的方法就是自监督学习。对物品做 data augmentation，可以更好的学习长尾物品的向量表征。请参考文献：Self-supervised Learning for Large-scale Item Recommendations。

推导损失函数：现在考虑 batch 内第个用户，第个物品，这个数值分别是，把这个数值输入 softmax 激活函数，得到个概率值，记作。这里的组成一对正样本，如果双塔模型的预估足够准确，那么应该比其它个余弦相似度大很多，softmax 的输出值应该接近于 1，把这个概率值记作向量，上面的个数值是标签，全都是 0，只有对应的是标签是 1，它对应正样本，把这个标签记作向量，只有第个元素是 1，其它都是 0。做训练的时候我们希望向量尽量接近，越接近说明双塔模型的预估越准确，用和的交叉熵作为损失函数 ()。把替换成 softmax 函数输出的第个数值，就得到，这就是 listwise 训练双塔模型的损失函数。训练的时候要最小化损失函数。如下图所示：

listwise 训练双塔模型的损失函数

Batch内负样本会过度打压热门物品，造成偏差，如果使用 Batch内负样本就需要做纠偏。物品被抽样到的概率为： $点击次数$ ，预估用户对物品的兴趣为：，做训练的时候，把替换为，这样起到纠偏的作用，热门物品不至于过分打压，训练结束，线上做召回的时候还是用原本的余弦相似度 ()，训练双塔模型，每次要用一个 batch 的样本，从点击数据中随机抽取个用户 - 物品二元组，组成一个 batch，则 batch 训练双塔模型的损失函数为，它对应 batch 内第个用户，双塔模型预测的越准，损失函数也就越小。训练双塔模型的时候要做梯度下降，减小损失函数 () 是项的平均，序号指的是第个用户，的意思是 batch 中一共有个用户。

自监督学习：下面是两个物品和物品，对两个物品做随机变换，得到物品的特征和，对两个物品做另一种变换，得到特征为和。把这些特征输入物品塔，模型一共只有一个物品塔，物品塔输出的向量分别是，它们都是物品的向量表征，但是由于下边的随机变换导致这两个向量不完全相等，两个向量是同一个物品的表征，如果物品塔足够好，两个向量应该有很高的相似度，训练的时候会鼓励两个向量的余弦相似度尽量的大。右边的物品塔输出的向量分别是，他们都是物品的向量表征，同样的道理，两个向量应该有很高的相似度。但是不同物品的向量表征应该离的尽量远，也就是这些向量应该分散开，而不是集中在一小块区域。向量对应两个不同的物品，它们的相似度应该比较低才对。做训练的时候，应该降低向量的相似度。如下图所示：

自监督学习会使用多种特征变换，它们分别是：

Random Mask：随机选择一些离散特征（比如类目），把它们遮住。比方说选出类目这个特征，例如某物品的类目特征是向量 $数码摄影$ 。一个物品可以有多个类目，如果不做 Random Mask，正常的特征处理方法是对数码和摄影分别做 Embedding 得到两个向量，再取加和或者平均，最终输出一个向量，表征物品的类目。如果对类目特征做 Mask 后，这物品的类目特征就变成了，意思是默认的缺失值，然后对做 Embedding，得到一个向量表征类目，也就是说做 Mask 后，物品的类目特征直接丢弃，数码和摄影都没了。
Dropout(仅对多值离散特征生效)：一个物品可以有多个类目，那么类目就是一个多值离散特征，Dropout 意思是随机丢弃特征中 50% 的值。例如某物品的类目特征包括 $美妆摄影$ ，做 Dropout 随机丢弃 50% 的值，碰巧丢弃了摄影特征，该物品的类目只包括 $美妆$ 。请注意，Random Mask 与 Dropout 的区别是 Random Mask 是把整个类目的特征都丢弃，而 Dropout 只是随机丢弃 50% 的值。
互补特征 (complementary)：假设物品一共有四种特征：ID、类目、关键词、城市。正常的做法是将这四个特征分别作 Embedding，然后拼接起来输入物品塔，最后得到物品的向量表征。互补特征 (complementary) 意思是把这些特征随机分成两组，例如：{ID、关键词} 和 {类目、城市}，对于第一组保留关 ID、键词，把另外两个特征替换成 default，如：{ID,default, 关键词，default}。物品塔把第一组特征作为输入，然后输出一个向量，作为物品的表征。第二组保留类目和城市，把另外两个特征替换成 default，如：{default, 类目，default，城市}。物品塔把第二组作为输入，然后输出一个向量，作为物品的表征。训练的是鼓励余弦相似度尽量大。
- Mask一组关联的特征：例如物品的受众性别是一种特征： $男女中性$ ，物品类目是另一种特征： $美妆数码摄影$ ，物品的受众性别和类目不是独立的，而是存在某种关联。 $女$ 和 $女装$ 两个值同时出现的概率比较大。的意思是受众性别为女性，类目为女装两者同时出现的概率。 $女$ 和 $数码$ 两个值同时出现的概率比较小。很明显数码类的物品受众性别普遍为男性而不是女性。加入我们知道类目是女装，那么受众性别大概率是女性，可以看出它们存在关联。某特征取值为的概率，记作，以受众性别为例：有 20% 的物品受众性别为男性；30% 的物品受众性别为女性；有 50% 的物品受众性别为中性。一个特征取值为，另一个特征取值为，则同时发生的概率，记作为，比如说一个物品的受众性别是女性，类目是女装，那么这个概率为： $女女装$ ，比如说一个物品的受众性别是女性，类目是数码，那么这个概率为： $女数码$ 。我们离线计算特征两两之间的关联，具体用 mutual information 来衡量：。两个特征关联越强，mutual information 关联就越大。具体实现：设一共有种特征，离线计算特征两两之间，得到的矩阵，表示特征之间的关联。每次随机选一个特征作为种子，然后在种特征中选取种子最相关的种特征。把种子特征以及相关的种特征做 Mask，即把它们都遮住，保留其余的种特征。Mask 关联特征的好处是实验效果好，比 Random Mask、dropout、互补特征的方法效果好一点。Mask 关联特征的坏处是：方法复杂，实现难度大，不容易维护。

如何对变换后的特征训练模型？要从全体物品中做均匀抽样，得到个物品，作为一个，冷门物品和热门物品被抽样到的概率是相同的。注意，与训练双塔的区别，双塔用到的数据是根据点击进行抽样的，热门物品被抽到的概率大，均匀抽样到个物品后，对物品特征做变换，要用两种不同的特征变换，每个物品被表征为两个向量：，第个物品的损失函数，公式记作：。

这里考虑 batch 中第个物品的特征向量和个物品特征向量，如下图所示，计算第个物品的特征向量与个物品的特征向量的余弦相似度，分别为：，把这数值输入 softmax 激活函数得到个概率值，其中与代表正样本，和都是对同一个物品的表征，只是使用不同的特征变换，导致两个向量不相等，如果物品塔足够好，那么这两个向量的余弦相似度应该很高。其余的都是负样本，她们的余弦相似度应该很小。所以 softmax 输出的概率值应该接近 1，其余个概率值应该接近于 0，把这个概率值记作向量，把上面 m 个标签记作，只有第个元素是 1，其余的都是 0。如果接近，也说明物品塔训练的比较好。即使做随机特征变换对物品的向量表征也影响不大。用和的交叉熵作为损失函数 ()。把替换成 softmax 函数输出的第个数值，就得到，训练的时候要最小化损失函数。自监督学习的损失函数公式为：，一个 batch 中有个物品，对项损失函数取平均：作为自监督学习的损失。训练的过程中做梯度下降，让损失减小。

自监督模型训练

召回 - Deep Retrieval

Deep Retrieval 是一种基于深度学习的检索模型，旨在提高大规模推荐系统中的候选项检索效率和准确性。它通过将候选项编码到一个离散的潜在空间中，利用深度神经网络的强大表示能力，实现端到端的学习过程。经典的双塔模型把用户、物品表示为向量，线上做紧邻查找。Deep Retrieval 则把物品表征为路径 (path)，线上查找用户最匹配的路径。论文可以参考 Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations。

Deep Retrieval 的索引：物品表征为路径，索引把路径关联起来，如下图所示，神经网络分为三层，深度为，宽度为，也就说每一层有个节点，Deep Retrieval 用到了路径这个概念，把一个物品表示为路径 (path)，比如 [2,4,1]。一个物品可以表示为多条路径，比如 {[2,4,1],[4,1,1]}。路径可以有重合的节点，Deep Retrieval 用到两个索引：一个索引是 item -> List<path>，训练神经网络的时候要用到这个索引，一个物品可以对应多条路径，假设结构有 3 层，就用三个节点来表示一条路径：，是节点。另一个索引是：path -> List<item>，一条路径会对应多个物品，线上做召回的时候会用到这个索引。给定一条路径会取回很多个物品作为召回的结果。

Deep Retrieval 设计了一种神经网络，给定用户特征，神经网络可以预估用户对路径的兴趣分数，用这种神经网络，可以根据用户特征，召回多条路径。假设结构有 3 层，就用三个节点来表示一条路径：，给定用户特征，预估用户对节点的兴趣，记作。然后给定和，预估用户对下一层的节点的兴趣，记作。最后给定，预估用户对再下一层的节点的兴趣，记作。神经网络模型预测用户对路径的兴趣分数，记作。这三项都是神经网络算出的。

如下图所示，模型的输入是用户特征，记作，把这个特征输入到神经网络，其最后是 softmax 激活函数，把 softmax 输出的向量记作 , 如果结构的每一层有个节点，那么就是一个维向量，Deep Retrieval 的结构是有 3 层，每层有个节点，向量对应于层，向量的个元素是神经网络给层的个节点打的分数。分数越高，节点就越有可能被选中。根据向量 , 我们从个节点选出一个节点，记作。接下来将向量和向量一起输入到下一层神经网络，从结构的第二层选出一个节点。向量不变，直接作为下一层的输入，对节点做 Embedding 得到另一个向量，记作。对向量，然后输入另一个神经网络，这个神经网络的输出层也是用 softmax 激活函数，把 softmax 输出，记作向量，它也是个维向量，对应结构中第二层，向量的个元素是为层的个节点打分，根据向量，从个节点选出一个节点，记作。最后把向量和节点一起输入到下一层的神经网络，向量和不变，直接作为下一层的输入，对节点做 Embedding 得到另一个向量，记作，对这三个向量做，然后输入神经网络。在这个例子中，一共用了三层神经网络，它们不共享参数，下面这个神经网络的输出层也用 softmax 激活函数，把 softmax 输出记作向量。他是个维向量，对应结构中的第三层，向量有个元素，分别对应第三层的个节点，根据分数，从个节点中选出一个，记作节点。到此为止，已经从三层中各选出了一个节点组成了路径。

线上召回：给定用户特征，召回一批物品，召回：用户 -> 路径 -> 物品，召回的第一步是给定用户特征，用 beam search 召回一批路径；第二步是给定路径，利用索引 path->List<item>，召回一批物品；最后一步，对召回的物品做打分和排序，选出一个子集。作为 Deep Retrieval 召回通道的输出。线上召回的最终流程：user -> path -> item。

假设 Deep Retrieval 的结构有 3 层，每层有个节点，那么一共有条路径。用神经网络给所有个路径打分显然计算量太大，用 beam search 寻找比较好的路径，可以减少计算量。beam search 在机器学习和 NLP 中用很多应用。做 beam search 的时候，需要设置一个超参数 beam size，beam size 越大计算量越大，search 的结果也会越好。先看看最简单的情况，beam size = 1，如下图所示，最左边是结构的第一层，一共有个节点。用神经网络的第一层给个节点打分，一共有个分数，神经网络输出的向量的个元素就是这个分数，我们设置了 beam size = 1，所以每次只选一个节点，选分数最高的节点，比如说选中了 5 号节点，中间是结构的第二层，也是有个节点，从第一层 (L1) 的 5 号节点出发，有个路径通往第二层 (L2)，我们要从条路径中选择 1 条。神经网络的第二层把用户特征和第一层的 5 号节点作为输入，计算出这个分数，记作，这些分数当中，如果 4 号节点的分数最高，则选中 4 号节点。我们从条路径中选择出了 1 条路径，从第一层的 5 号节点到第二层的 4 号节点，只选 1 条路径，是因为设置了 beam size = 1，如果 beam size = 10，则需要选出 10 条路径。最右边是结构的第三层 (L3)，从第一层的 5 号节点出发，到达第二层的 4 号节点，然后有条路径通往第三层，我们要从条路径中选择 1 条，用神经网络第三层把用户特征、第一层的 5 号节点和第二层 4 号节点作为输入，计算出个分数，记作，比如说 1 号节点分数最高，那么就选中 1 号节点，结构有三层，所以每条路径有 3 个节点，这条选中的红色路径可以表示为，用户对路径 [a,b,c] 的兴趣分数，记作，其中是神经网络的输出，最优的路径是分数最大的路径，记作：。

选中的路径 path = [5,4,1]

有个路径，想找到最优路径代价很大。我们设置了 beam size = 1，这就相当于贪心算法，选中的节点分别最大化，但是独立对求最大化，未必会最大化这三项的乘积。所以贪心算法选中的路径未必是最优路径。如果把 beam size(4) 设置大一些，结果会比贪心算法好，当然 beam size 越大，计算量也就越大。

做训练的时候，要同时学习神经网络的参数和物品的表征。我们把神经网络打分，记作，它表示用户对路径 [a,b,c] 的兴趣分数。做训练的时候要学习这个神经网络的参数，一个物品可以被表征为多条路径 {[a,b,c]}，需要学习物品的表征，建立物品和路径的对应关系，学到物品之后，会建立两个索引，一个是物品到路径，记作 item -> List<path>，另一个是路径到物品，记作 path -> List<item>。Deep Retrieval 做训练的时候，只需要正样本，正样本是 (user, item) 的二元组，只要用户点击过物品，就算是正样本。假设我们把物品表征为这条路径，记作：，神经网络预估对 path = [a,b,c] 这条路径的兴趣，把神经网络预估的分数记作：。如果用户点击过物品，就认为用户对这条路径感兴趣，应该让变大，这样定义损失函数，记作：，越大，则损失越小。通过最小化损失函数来学习神经网络的参数，这个神经网络的作用是判断用户对路径有多感兴趣，如果用户点击过物品，就认为用户对条路径都感兴趣，应该让神经网络给这些路径打的分数更高。除了学习神经网络的参数，还需要学习物品的表征，用户 (user) 对路径 path = [a,b,c] 的兴趣记作：，其中是用户的特征。物品 (item) 和路径 (path) 的相关性，记作：。这个分数越高，说明物品和路径有越强的关联。我们计算物品与很多条路径的相关性分数，即，接下来算出，给一个物品选出条路径，把这个物品表征为条路径，这里先看一下，连加里是两项的乘积，一项是用户对路径的兴趣，另一项是用户是否点击过该物品。关于用户做连加，得到物品与路径的相关性。

如下图所示，左边是一个物品，这些边表示用户点击过这个物品，也就是说中间的用户全都对该物品感兴趣，记作，右边是一条路径，右侧的边表示用户对路径的兴趣分数，值介于 0~1 之间，这些分数全都是神经网络算出的，用户是物品与路径之间的中介，把左右两边的分数相乘并做连加就是物品与路径之间的相关性分数。这里的用户全都点击过左边的物品，如果其中很多用户也对路径感兴趣，就判断物品和路径有很强的关联，可以把路径作为物品的表征。

我们已经算出了物品和路径之间的相关性分数，我们需要根据这些分数选出条路径，作为物品的表征。这样定义损失函数，记作：，是物品与某条路径的相关性，对条路径的分数取连加，这些路径与物品越相关，加和也就越大，选择的物品与路径越相关，则损失函数值就越小，假如最小化这个损失函数，那么就相当于根据分数 (score) 做排序，取排序结果的 Top-J，对于每个物品选择分数最高的这条路径，用这条路径作为物品的表征，但是取分数最高的路径不太好，有可能发生这样的情况，非常多的物品集中在了一条路径上。我们希望每条路径上物品数量比较平衡，不希望少数的路径有很多的物品。为了让路径上的物品保持平衡，需要用正则项来约束路径，约束记作：，如果某条路径上已经有了很多个物品，会受到惩罚，避免关联到更多的物品。

学习物品表征的算法：这是一种贪心算法，假设已经把物品表征为条路径，记作。每次固定其中的条路径，记作，并从未被选中的路径中，选出作为一条新的，记作：，其中作为新选中的序号，是损失函数，物品与这条路径的相关性越高，损失函数值就越小，我们需要选中的路径与物品是密切相关的，这一项是正则，控制路径上的物品不要太多，从候选的路径中，选出能让损失函数和正则项最小化的一条路径，作为新的路径。这样选择可以让选中的路径有较高的分数：，让路径跟物品密切相关，同时也能避免一条路径上有过多的物品，避免让索引失去平衡。

Deep Retrieval 的训练分为两块：一块是更新神经网络，另一块是更新物品的表征。交替做着两部分的训练，就可以同时学习到神经网络和物品表征。

更新神经网络：Deep Retrieval 有一个神经网络，它能判断用户对路径的兴趣，记作：，给定用户特征，神经网络给路径打分记作，分数越高，说明用户对路径的兴趣越大。训练神经网络用到两方面的数据：1. 物品 -> 路径的索引；2. 用户点击过的物品。如果用户点击过物品，而且物品对应路径 (path)，就认为用户对路径感兴趣，则更新神经网络的参数，使变大。也就是训练神经网络的时候，把物品作为中介，将用户和路径关联起来。
更新物品的表征：让每个物品关联到这条路径，建立物品 -> 路径索引。想要把物品关联到路径，需要判断物品与路径的相关性：物品 <- 用户 -> 路径，需要将用户作为物品与路径之间的中介。找到点击过物品的所有用户，然后用神经网络计算用户对路径的兴趣分数，把分数加起来就是物品与路径的相关性，我们让每个物品关联上条路径。满足两个条件，才会把物品和路径关联起来：一个条件是物品和路径要有很高的相关性；另一个条件是一条路径上不能关联过多的物品。给每个物品找到满足这两个条件的路径，就可以把物品和路径关联起来，建立起物品 -> 路径索引。

召回 - 其它召回

GeoHash召回：有一类是根据用户的地理位置做召回，只有 GeoHash 召回属于地理位置召回，之所以用这条召回通道，是因为用户可能对附近发生的是感兴趣。推荐系统应该推荐一些用户附近的内容，系统维护地理位置只有一个 GeoHash 索引，GeoHash 意思是经纬度编码成 Hash 码方便检索，GeoHash 表示地图上一个长方形的区域，索引是 GeoHash-> 优质物品列表。做召回的时候给定用户 GeoHash，会取回这个区域内比较新的优质物品，这条召回通道没有个性化，召回只看地理位置，每次召回本地的优质物品，完全不考虑用户的兴趣，由于没有用个性化，所以才用优质物品。物品本身质量好，即使没有个性化，用户也会查看。同城召回与 GeoHash 召回的原理是一样的，用户可能对同城发生的事感兴趣，索引采用城市 -> 有事物品列表。这条召回通道也没有个性化。

作者召回：如果你对一个坐着感兴趣，系统就会给你推荐这个作者发布的新物品。带社交属性的推荐系统都会有一个作者召回这样一个通道，这时系统维护了两个索引：一个是用户 -> 关注的作者；另一个是作者 -> 发布的物品。物品的列表是按照时间倒排的，也就是说新发布的物品排在最前面。线上做召回的时候，给定用户 ID-> 关注的所有作者 -> 每个作者新发布的物品。这样就得到了一批物品。

缓存召回：基本想法是复用之前次推荐精排的结果。缓存召回有一个问题，缓存大小是固定的，需要退场机制，确保缓存最多有个物品。有很多规则作为退场机制，比如一旦物品曝光给用户，就要从缓存中退场。如果超出缓存的大小，就移除最先进入缓存的物品。每个物品最多被召回 10 次，达到 10 次就退场。每个物品在缓存最多保存 3 天，达到 3 天就退场。在这些规则的基础上还能细化规则。

召回 - 曝光过滤 & Bloom Filter

曝光过滤是这样一个问题。在推荐系统中，如果用户看过某个物品，就补在把这个物品曝光给这个用户，因为重复曝光同一个物品会损害体验。曝光过滤需要记录已经曝光给他的物品，在做完召回之后，对于每个召回的物品，判断每个物品是否已经给该用户曝光过，排除掉已经曝光过的物品。例如一个用户看过个物品，本次召回个物品，如果暴力对比，则需要的时间复杂度。所以实践中不做曝光过滤，而是做布隆过滤 (Bloom Filter)，曝光过滤通常都是用布隆过滤 (Bloom Filter) 做的。它可以判断一个物品 ID 是否在已曝光的物品集合中。如果布隆过滤 (Bloom Filter) 的判断是 no，那么该物品 ID 一定不在集合中；如果布隆过滤 (Bloom Filter) 的判断是 yes，那么该物品 ID 很可能在集合中（会有误伤，错误判断微博光的物品为已曝光，将其过滤掉）。如果用布隆过滤 (Bloom Filter) 做曝光过滤，肯定能过滤掉曝光过的物品，用户绝对不可能看到重复的物品，但也会有误伤。布隆过滤 (Bloom Filter) 是一种数据结构，它把物品集合表征为一个维的二进制向量，每个元素是一个 bit，要么是 0、要么是 1。每个用户都有一个曝光物品的集合，对物品表征为一个向量，向量需要的存储。布隆过滤 (Bloom Filter) 有个 Hash 函数，每个 Hash 函数把物品 ID 映射成介于 0~(m-1) 之间的整数。都是需要设置的参数。

举例，，也就是说只用一个 Hash 函数，布隆过滤 (Bloom Filter) 需要一个二进制向量来做存储，向量的长度是 , 也就是存储需要花费，初始时向量是全零的，我们知道一个用户有哪些已经曝光过的物品，如下图所示，这是第一个物品的 ID，记作，Hash 函数把它映射到第 2 个位置，把这个位置的元素置为 1，这是第二个物品的 ID，记作，Hash 函数把它映射到第 9 个位置，把这个位置的元素置为 1，Hash 函数把第三个物品 ID 映射到第 2 个位置，这个位置已经是 1，不需要修改。Hash 函数把第 4 个物品的 ID 映射到第 6 个位置，把这个位置置为 1，Hash 函数把第 5,6 个物品 ID 映射到第 6 个位置，不需要修改这个数值。如何用这个向量做曝光过滤？用户发起推荐请求之后，召回很多物品，这有一个的物品，之前没有被曝光过，它被映射到向量的第 3 个位置，这个位置的元素是 0，所以布隆过滤 (Bloom Filter) 判断这个物品没有被曝光。这个判断是正确的，布隆过滤 (Bloom Filter) 认为没有曝光，那么这个物品肯定没有曝光，布隆过滤 (Bloom Filter) 不会把已曝光的物品错判为已曝光。这个物品 () 已曝光，Hash 函数把它映射到向量第 6 个位置，这个向量位置的元素是 1，说明该物品已经被曝光，这个物品 () 没有曝光，Hash 函数把它映射到第 9 个位置，这个向量的位置是 1，布隆过滤 (Bloom Filter) 认为它已曝光。但这其实是一个误判，布隆过滤 (Bloom Filter) 有一定概率把未曝光的物品误判为已曝光。导致未曝光的物品被过滤掉，造成误伤。

Bloom Filter (k = 1)

假设 Hash 函数的数量为时，初始的时候二进制向量的值都是 0，一个已曝光的物品，记作，用 3 个不同的 Hash 函数 () 映射到二进制向量的不同位置上，把这 3 个位置上的元素全都置为 1；这是一个已曝光的物品，记作，用 3 个不同的 Hash 函数 () 映射到二进制向量的不同位置上，把这 3 个位置上的元素全都置为 1，如果某个位置上的元素为 1，则不用修改。这是个召回的物品，没有曝光，记作，用 3 个不同的 Hash 函数 () 映射到二进制向量的 3 个位置，假设这个物品已经曝光，这 3 个位置的元素肯定都是 1，但是其中有一个位置是 0，说明这个物品未曝光，布隆过滤 (Bloom Filter) 判断未曝光，那么这个物品一定没有曝光。这个物品，记作，已曝光过，映射的这 3 个位置的元素都是 1，布隆过滤 (Bloom Filter) 则判断已曝光，则这个物品将被过滤掉。这个召回的物品没有曝光，记作，3 个 Hash 函数把物品 ID 映射到 3 个位置，由于 3 个位置全都是 1，布隆过滤 (Bloom Filter) 判断这个物品曝光过，这其实是一个误判，布隆过滤 (Bloom Filter) 有一定概率把未曝光的物品误判为已曝光。导致未曝光的物品被过滤掉，造成误伤。

曝光物品集合大小为，二进制向量维度为，使用个 Hash 函数，这个公式：给出了布隆过滤 (Bloom Filter) 误伤概率的大小。越大，物品的曝光数量也就越多，那么误伤的概率也就越大。曝光的物品越多，往二进制向量写的 1 也就越多，那么布隆过滤 (Bloom Filter) 就越容易出现误伤，如果向量中的 1 很多，那么未曝光物品的个位置为 1 的概率也就越大。是二进制向量的长度，越大，那么两个物品的 Hash 值就越不容易冲突，出现误伤的概率也就越小，但是值越大，需要的存储也就越多。是 Hash 函数的数量，太大、太小都不好，它的大小有最优值。设定可容忍的误伤概率为，比方说能容忍个 % 的错误，则，确定了误伤概率，那么就有最优的参数，的大小正比于，也就是说每个曝光物品占几个 bits 的存储，用户历史记录上有个曝光物品，只需要将，就可以将误删概率降低到 1% 以下。

曝光过滤的链路：如下图所示，上面推荐系统的链路，用多路召回，然后经过粗排、精排、重排，最终选出一批物品曝光给用户，下面是曝光过滤的链路，把曝光的物品记录下来，更新布隆过滤 (Bloom Filter)，用于过滤召回的物品，app 的前端都有埋点，所有曝光过的物品都被记录下来，这个落表的速度要足够快，否则会出问题。用户推荐页面两次刷新间隔也就几秒钟，快的话也就 10~20 秒，在下一次刷新之前就要把本次曝光的结果写入到布隆过滤 (Bloom Filter) 上，否则下一次刷新很有可能出现重复的物品，所以要用实时流处理，比如把曝光的物品写入 Kafka 消息队列 + Flink 做实时计算，Flink 实时读取 Kafka 消息队列中物品的 Hash 值，把结果写入到布隆过滤 (Bloom Filter) 的二进制向量上，用这样的实时数据链路，在发生几秒之后，这位用户的布隆过滤 (Bloom Filter) 就会被修改，之后就能避免重复曝光。但实时流这部分也是最容易出问题的，如果服务停止或延迟比较大，那么用户上一次刷新的物品又会再次出现，曝光过滤具体用在召回完成之后，召回服务器请求曝光过滤服务，曝光过滤服务把召回用户的二进制向量发送给召回服务器，在召回服务器上用布隆过滤 (Bloom Filter) 计算召回物品的 Hash 值，再跟二进制向量作对比，把已经曝光的物品过滤掉，剩余的物品都是未曝光的，然后发送给排序服务服务器。

布隆过滤 (Bloom Filter) 的缺点：布隆过滤 (Bloom Filter) 把物品的集合表示成一个二进制向量。每往集合中添加一个物品，只需要把向量个位置的元素置为 1，布隆过滤 (Bloom Filter) 只支持添加物品，不支持删除物品。从集合中移除物品，无法消除它对向量的影响。不能简单的把这个物品对应的个位置的元素由 1 改成 0，否则会影响其它物品。这是因为向量的元素，对所有物品是共享的。实践中，每天都需要从物品集合中移除不需要的物品（年龄大于 1 个月的物品），想要删除一个物品，需要重新计算整个集合的二进制向量。