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

概念介绍

推荐系统(Recommendation system)的链路包括两个重要的步骤：检索（称召回）和排名（分为粗排，精排和重排）检索或召回主要用于衡量系统从全量信息中找出相关内容的能力。它的核心目的是在用户查询的背景下，尽可能多地返回与之相关的信息。如下图所示：

推荐系统(Recommendation system)的目标是从物品的数据库中取出几十个物品展示给用户。推荐系统链路上的第一环是检索或召回，就是从数据库中快速取回一些物品，在实践中，推荐系统有很多条召回通道（如协同过滤、双塔模型、关注的作者等等），每条召回通道取回几百个物品。这些召回通道一共返回几千个物品，然后推荐系统会融合这些物品，并且做去重和过滤，过滤的意思是排除掉不喜欢的物品，召回几千个物品之后，下一步是排序，排序要用机器学习模型预估用户对物品的兴趣，保留评分最高的物品，如果用一个大规模神经网络逐一对几千个物品打分，花费的代价会很大，为了解决计算量的问题，通常把排序分为粗排和精排。粗排一般使用比较简单的模型，快速给几千个物品打分，保留分数最高的几百个物品；精排用一个较大的神经网络给几百个物品打分，不用做截断。精排模型比粗排模型大很多，用的特征也更多，所以精排模型打的分数也更可靠。但是精排模型的计算量也很大，这就是为什么我们用粗排模型先做筛选，然后才用精排模型，这样做可以很好的平衡计算量和准确性。做完粗排和精排得到几百个物品，每个物品都有一个分数，表示用户多物品的兴趣有多高。可以直接把物品按照打的分数排序，然后展示给用户，但此时的结果还是会存在一些不足，需要做一些调整，这一步叫做重排。重排主要是考虑多样性，要根据多样性进行随机抽样，从几百个物品中选择出几十个物品，然后还要使用规则把相似的物品打散，重排的结果就是展示给用户的物品。比如把top50的物品（包含广告）展示给用户。如下图所示：

精排与粗排的唯一区别就是精排用的模型更大，特征更多，模型的输入包括用户特征、物品特征、统计特征。假如要判断用户对某个物品感兴趣，我们就要把该用户的特征、物品的特征和统计特征输入神经网络，神经网络会输出很多数值，比如点击率、点赞率、收藏率、转发率等等，这些数值都是神经网络对用户行为的预估。这些数值越大说明用户对该物品越感兴趣，最后把多个预估值做融合，得到最终的分数。比如求加权和，这个分数决定了这个物品会不会展示给用户，以及物品展示的位置是靠前还是靠后，请注意，这只是对一个物品的打分，粗排要对几千个物品打分，精排要对几百个物品打分。每个物品都用多个预估分数融合成一个分数作为给这个物品排序的依据。推荐系统链路上的最后一环是重排，重排最重要的能力是多样性抽样（比如MMR、DPP），需要从几百个物品中选出几十个物品。多样性抽样的时候有两个依据：一个依据是精排分数的大小，另一个依据是多样性。做完多样性抽样之后会根据规则将相似物品打散。重排的另一个目的是插入广告、运营推广的内容，根据生态要求调整排序。

A/B测试

做A/B测试需要对用户做随机分桶，比如把用户随机分成10个桶，每个桶中有10%的用户，如果用户的数量足够大，那么每个桶的DAU留存、点击率这些指标都是相等的。具体分桶的方法是：首先用哈希函数吧用户ID映射成某个区间内的整数，然后把这些整数均匀随机分成个桶。我们把用户随机分成10个桶，每个桶有10%的用户，接下来才用这样的桶来做A/B测试。比如我们想要考察GNN(图神经网络)对召回通道指标的影响。有1、2、3号桶作为三个实验组，但是GNN的参数不一样，三个桶的神经网络分别是一层、两层、三层。用4号桶作为对照组，这四个桶唯一的区别就是前三个桶用了GNN召回通道，4号桶没有用GNN。如果一个用户落在1号桶，那么给它做推荐的时候，会使用一层的GNN神经网络做召回；如果另一个用户落在了4号桶，那么给它做推荐的时候，则不使用GNN做召回。分别计算每个桶的业务指标，比如DAU、人均使用推荐时长、点击率等等。如果过某个实验组的指标显著优于对照组，则说明对应的策略有效，值得推全（意思是把流量扩大到100%）。

分层实验的目标就是解决流量不够用的问题。主要是因为信息流产品的公司有很多部门和团队，大家都需要做A/B测试，比如：推荐系统（召回、粗排、精排、重排）、用户界面、广告等。如果把用户随机分成10组，1组作对照，9组做实验，那么只能同时做9组实验。这样会导致流量资源完全不够用。解决方案就是分层实验，把实验分成很多层，比如分成：召回、粗排、精排、重排、用户界面、广告等等（例如GNN召回通道就属于召回层）。同层之间的实验需要互斥，例如：GNN实验占了召回层的4个桶，其它召回实验只能使用剩下的6个桶。同层互斥的目的是避免一个用户同时被两个召回实验影响，加入两个实验相互干扰，实验结果会变的不可控；不同层之间流量正交：每一层独立随机对用户做分桶。每一层都可以独立用100%的用户做实验。召回和粗排的用户是随机划分的。召回的2号桶和粗排的2号桶交集很小，举个例子召回层和精排层各自独立随机把用户分成十个桶，分别是和。设系统共有个用户，那么。召回桶和召回桶交集为。所以同一层实验之间是互斥的，两个召回实验不会作用的一个用户上。召回桶和精排桶交集的大小为。一个用户不能同时受两个召回实验的影响。但可以同时受一个召回实验和一个精排实验的影响，一个召回实验和一个精排实验各自作用在个用户上，那么有的用户同时受两个实验的影响。也就是说，同层互斥，不同层正交。如果所有实验都正交，则可以同时做无数组实验。但是同类策略天然互斥（例如精排模型的两种结构），对于一个用户，只能用其中一种；同类策略（例如添加两条召回通道）效果会相互增强(1+1 > 2)或相互抵消(1+1 < 2)，互斥可以避免同类策略相互干扰；不同类型的策略（例如添加召回通道、优化粗排模型）通常不会相互干扰(1+1 = 2)，可以作为正交的两层。

召回 — ItemCF

基于物品的协同过滤(ItemCF)的基本思想：如果用户喜欢物品，而且物品与相似，那么用户很可能喜欢物品。每个物品都交互过若干物品，比如点击、点赞、收藏、转发过的物品，可以量化用户对物品的兴趣，如点击、点赞、收藏、转发各站1分，在这个例子中，用户对四个物品的兴趣分数分别是2,1,4,3，这里有一个没有跟用户交互过得物品，我们要决定是否要把这个物品推荐给用户。假设我们知道物品两两之间的相似度，比如它们的相似度分别是：0.1、0.4、0.2、0.6。使用如下公式：来预估用户对候选物品的兴趣。这一项是用户对第个物品的兴趣，这一项是第个物品与候选物品的相似度。把这两项相乘，再把所有的乘积相加，得到总分，总分表示用户对候选物品的兴趣，在这个例子中从用户到候选物品有4条路径，所以要计算4个分数，然后把它们相加，预估用户对候选物品的兴趣：。

举个例子有2000个候选物品，我们逐一计算用户对候选物品的兴趣分数，然后返回分数最高的100个物品，如何计算两个物品之间的相似度？计算物品相似度的思路是这样的，两个物品受众重合度越高，两个物品越相似。我们可以从数据中挖掘出物品的相似度，把喜欢物品的用户记作集合，是用户的集合；把喜欢物品的用户记作集合，把交集定义为，表示同时喜欢物品的用户，则两个物品的相似度定义为。分子表示对两个物品都感兴趣的用户人数，分母表示集合大小的乘积再取根号，这样计算出的相似度一定是介于0~1之间的数，值越大表示两个物品越相似。为什么相似度是介于0~1之间的呢？这是集合比集合都要小。注意，这个公式没有考虑喜欢的程度，用这个公式只要是喜欢都看作1，不喜欢都看做0。如果想用到喜欢的程度，需要改一下这个公式。比如点击、点赞、收藏、转发各自算1分，喜欢物品的程度最多可以是4分。现在我们考虑用户喜欢物品的程度，则公式更改为。分子把用户对物品喜欢的分数相乘并连加，连加是关于用户取得同时喜欢两个物品。如果兴趣分数的取值是0或1，那么分子就是同时喜欢两个物品的人数就是集合的大小，分母是两个根号的乘积，第一项是用户对物品的兴趣分数，关于所有用户连加开根号，第二项是用户对物品的兴趣分数，关于所有用户连加开根号。这个公式计算的数值介于0~1之间，表示两个物品的相似度，其实这个公式就是余弦相似度(cosine similatity)。把一个物品表示为一个稀疏向量，向量每个元素对应一个用户，元素的值就是用户物品的兴趣分数，两个向量夹角的余弦就是这个这个公式。

基于物品的协同过滤(ItemCF)召回的完整流程：为了能在线上做到实时的推荐，系统必须事先做离线计算，建立两个索引，一个索引是”用户 -> 物品“索引，记录每个用户最近点击、交互过的物品ID。有了这个索引之后，给定任意用户ID，可以找到它近期感兴趣的物品列表。另一个索引是”物品 -> 物品“索引，我们首先要计算物品之间两两相似度，这个计算量会比较大，对于每个物品，索引它最相似的个物品，比如，有了这个索引之后，给定任意物品ID，可以快速的找到它最相似的个物品，而且知道相似度分数。如下图所示：

有了索引之后我们以在线上给用户做实时推荐，比如系统知道用户的ID，首先查看用户—>物品的索引，可以快速找到用户近期感兴趣的物品列表(last-n)，对于last-n列表中的每一个物品，利用物品—>物品的索引，找到top-k相似物品。用户最近有个感兴趣的物品，我们又找到了每个物品的top-k相似物品。那么一共取回个物品，对于取回的个相似物品，用公式预估用户对物品的兴趣分数。按照分数从高到低对物品排序，返回分数最高的100个物品作为推荐结果。这100个物品就是这个ItemCF召回通道的输出，会跟其它召回通道的输出融合起来，然后做排序，最终展示给用户。为什么要使用索引呢？数据库中有上亿个物品，如果挨个用公式计算对所用物品的兴趣分数，计算量会爆炸，索引的意义在避免枚举所有的物品。加入我们记录用户最近感兴趣的个物品，取回每个物品最相似的个物品。那么一共取回个物品打分（用户对物品的兴趣）。用公式给这2000个物品打分，也就是分别预估对这2000个物品的兴趣分数，返回分数最高的100个物品作为ItemCF召回通道的输出。这样的计算量是很小的，可以做到在线实时计算。总结一下，用索引，离线计算量大，线上计算量小。好处是每次线上召回速度都很快，只需要给2000个物品打分，不需要访问上亿个物品。

整个流程是用户登录之后，系统给用户做推荐，知道用户的ID，利用”用户 -> 物品“的索引，找到用户近期感兴趣的物品列表，这个列表记录了用户ID和用户对该物品的兴趣的分数。接下来我们要利用物品->物品的索引，找到每个物品的top-k相似的物品，知道物品的ID我们要取回与它相似的个物品，这些就是top-k相似物品ID和相似度。用同样的方法，根据物品->物品的索引，找到每个物品的top-k相似物品，top-k相似可以召回很多物品，可以用公式计算用户对召回物品的兴趣分数。根据算出的分数做排序，返回排在top-100的物品，做计算的时候需要用到这些列表里的数值，用到上面列表用户对物品的兴趣分数，用到下面列表物品对物品相似度分数，把兴趣分数和相似度分数相乘，如果取回的物品ID有重复的，就选择去重，最后把分数加起来。线上召回流程如下图所示：

Swing模型

Swing模型的原理就是给用户设置权重，解决小圈子的问题。把用户喜欢的物品记作集合，把用户喜欢的物品记作集合，定义两个用户的重合度为：。这个值越大说明两个用户和的重合度高，则它们可能来自一个小圈子，则要降低它们的权重。在计算物品相似度的时候，会把放在分母上，把喜欢物品的用户记作集合，把喜欢物品的用户记作集合。集合是。如果一个用户既喜欢物品，也喜欢物品，那么这个用户就在集合。下面是计算两个物品相似度的公式：。Swing和ItemCF是非常相似的方法，它们之间唯一的区别在于物品相似度。ItemCF考察两个物品的重合的受众比例有多高，如果很多用户同时喜欢两个物品，则判定两个物品相似。ItemCF会额外考虑重合的用户是否来自同一个小圈子，把同时喜欢两个物品的用户记作集合。对于集合中的用户和，把两个用户的重合度记作，两个用户重合度大，则可能来自同一个小圈子，权重降低。总而言之，Swing和ItemCF的区别就是计算物品相似度的时候要降低用户小圈子的影响。

召回 — UserCF

基于用户的协同过滤(UserCF)与基于物品的协同过滤(ItemCF)有很多相似之处，ItemCF是基于物品之间的相似性做推荐，而UserCF是基于用户之间的相似性做推荐。UserCF的原理：比如有很多跟我兴趣非常相似的网友，今天跟我兴趣相似的某个网友看了某个物品，他很感兴趣，对物品点赞、转发。于是系统就知道他喜欢这个物品，而我还没有看到这个物品，那么推荐系统就可能给我推荐这个物品。推荐的理由就是跟我兴趣爱好相似的网友喜欢这个物品。推荐系统如何找到跟我兴趣相似的网友呢？一种方法是：判断两个人感兴趣（点击、点赞、收藏、转发）的物品有多少重合，每个用户都有一个列表，上面存储了用户点击、点赞、收藏、转发的物品ID，对比两个用户的列表，就知道有多大的重合，重合雨多则说明两个人的兴趣越相似。另一种方法是：不是看物品的重合，而是看关注的作者的重合，每个用户都会关注一些作者，对比两个用户关注作者的列表，就知道有多少关注的作者是重合的。关注的作者重合越多，说明两个人的兴趣越相似。

在用UserCF做推荐之前，需要先离线算好每两个用户之间的相似度，例如我们在给左边的用户做推荐，中间是最相似的四个用户，这些分数表示用户之间的相似度，数值越大表示用户越相似。右边的候选物品，左边的用户还没有看过这个候选物品，我们想要预估左边的用户对右边的候选物品兴趣分数有多大。历史数据反映了用户对物品的兴趣，比如点击、点赞、收藏、转发的四种行为各算1分，四位用户对候选物品的兴趣分数分别是，分数越大表示用户对分数越感兴趣，0表示用户没有看过该物品，或者对物品不感兴趣。最后用这个公式来预估用户对候选物品的兴趣。这一项是代表左边用户与第个用户的相似度，这一项是第个用户对候选物品的兴趣，把相似度与兴趣分数相乘，在把所有乘积加起来得到总分，表示用户对候选物品的兴趣。从这个例子中，从左边的用户到右边的候选物品一共有四条路径，所以要计算4个分数，然后把它们相加：(左边用户对候选物品的兴趣)。举个例子有2000个候选物品，计算用户对候选物品的兴趣分数，然后返回分数最高的top-100个物品，如下图所示：

先举例说明两个用户相似和不相似，这两个用户喜欢的物品没有重合，所以不相似。另外两个用户喜欢的物品重合度高，所以判定这两个用户相似。两个用户的相似度是这样计算的，把用户喜欢的物品记作集合，把用户喜欢的物品记作集合。把集合的交集记作，集合包含两个用户共同喜欢的物品，用这个公式计算的相似度。公式中的分子是集合的大小，几两个用户共同喜欢的物品的个数，公式中的分母是大小的乘积取根号，这样计算出的相似度是介于0~1之间的数，数值越接近1表示两个用户越相似。刚才的公式有个不足之处，当公式同等对待热门和冷门的物品，这是不对的，拿书籍推荐举个例子：《哈利波特》是非常热门的物品，不论是大学教授还是中学生都喜欢看《哈利波特》，既然所有人都喜欢看哈利波特，那么哈利波特对于计算用户相似度是没有价值的，越热门的物品越无法反映出用户独特的兴趣，对计算相似就越没有用。重合的物品越冷门，越能反映出用户的兴趣，如果两个用都喜欢《Deep Learning》这本书，两个人很可能是同行，如果两个用户都喜欢更冷门一些的书，比如《深度学习在语音识别中的应用》，说明两个人是小同行，为了更好的计算用户兴趣的相似度，我们需要降低热门物品的权重，计算用户相似度的公式可以改写为：，这里的分子还是集合的大小，只不过换了一种写法，写成了对1的连加，其中的表示物品的序号，1是物品的权重。所有物品的权重都相同，不论是冷门，还是热门，物品的重要应该跟物品的权重相关，越热门的物品权重应该更低，我们把分子中的1改写为，表示第个物品的权重，是喜欢物品的用户数量，反应物品的热门程度。喜欢《哈利波特》的人数很多，就会很大，物品越热门，就越大，也就越小，也就是说物品的权重越小。这样一来《哈利波特》就会对用户相似度的贡献越小，而冷门物品的贡献就比较大。

UserCF的完整流程：事先做离线计算，先建立”用户—>物品“的索引，记录每个用户最近点击、交互过的物品ID，给定任意用户ID，可以找到它近期感兴趣的物品列表；接下来建立”用户—>用户“的索引，对于每个用户，索引他最相似的个用户，给定任意用户ID，可以快速的找到最相似的个用户，而且知道用户相似度的分数。如下图所示：

UserCF的完整流程：线上做召回，有了索引之后，可以在线上做实时推荐。比如系统知道用户的ID，首先通过”用户—>用户“的索引，快速找到与这位用户最相似Top-k个用户，对于每个Top-k相似用户，利用”用户—>物品“的索引，找到用户近期感兴趣的物品列表(last-n)，有了个相似用户，每个用户有个物品，那么一共取回了个物品，对于取回的个相似物品，用公式预估用户对每个物品的兴趣分数。按照兴趣分数，对物品从高到低进行排序，返回分数最高的100个物品，作为召回的结果。这100个物品就是UserCF召回通道的输出，如下图所示：

召回 - 离散特征处理

离散特征在机器学习很常见，性别（男，女）、国家（中国、美国、俄罗斯等）、英文单词、物品ID、用户ID是离散特征。推荐系统会把ID映射成一个向量。离散特征处理分为两步：1、建立字典，把类别映射成序号；2、向量化，把序号映射成向量（One-hot编码，把序号映射成高维稀疏向量；Embedding，把序号映射成低维稠密向量）。例如性别特征：男、女两个类别，在字典里边，男—>1，女—>2。采用One-hot编码，用2维向量表示性别。如果用户不填写性别，那么就是”未知 —> 0 —> [0,0]“；如果用户性别是男，那么”男 —> 1 —> [1,0]“；如果性别是女，那么”女 —> 2 —> [0,1]“。在实践中，类别数量太大时，通常不使用One-hot编码。例如国籍特征，字典把每个国家映射成序号()，Embedding把每个序号映射成向量，这些向量都是低维向量，比如向量大小都是，一个向量就是对一个国家的表示，未知国籍就用全零向量来表示。参数数量为：向量维度 x 类别数量。假设Embedding得到的向量都是4维的，一共有200个国籍，那么就有200个向量，那么参数数量为。如下图所示：

编程实现：可以直接使用TensorFlow、PyTorch提供的Embedding层。在训练神经网络的时候，会自动反向传播学习Embedding层的参数，Embedding层的参数是一个矩阵，矩阵的大小是向量维度 x 类别数量，Embedding层的输入是序号，比如美国的序号是2，Embedding层的输出是个向量，比如美国对应参数矩阵的第二列。Embedding = 参数矩阵 x One-hot向量，Embedding其实就是矩阵向量乘法，跟全连接层非常像。

召回 - 向量召回

矩阵补充(matrix completion)是向量召回最简单的一种方法，现在基本不怎么使用了。Embedding可以把用户ID或者物品ID映射成向量，如下图所示：

模型的输入是一个用户ID和一个物品ID，模型的输出是一个实数，是用户对物品兴趣的预估值。这个数越大，表示用户对物品越感兴趣。下面我们看一下模型的结构，左边的结构只有一个Embedding层，把一个用户ID映射到一个向量，记录向量，这个向量是对用户的表征。而Embedding层的参数是一个矩阵，矩阵中列的数量是用户数量，每一列都是这样大小的向量，Embedding层的参数数量 = 用户数量 x 向量的大小；右边的结构是另外一个Embedding层，把一个物品ID映射到一个向量，记录向量，大小跟向量设置成一样的，向量是对物品的表征，Embedding层的参数是一个矩阵，输出的向量是矩阵的一列，矩阵列的数量是物品的数量。模型一共用了2个Embedding层，它们不共享参数，对向量和求内积得到一个实数，作为模型的输出。这个模型就是矩阵补充模型。

模型训练的基本思路：用户Embedding层参数矩阵记作。每个用户对应矩阵的一列，第号用户对应矩阵的第列，记作向量；物品Embedding层参数矩阵记作，每个物品对应矩阵的一列。第号物品对应矩阵的第列，记作向量。向量和的内积是第号用户对第号物品兴趣的预估值。内积越大，说明用户对物品的兴趣越强。训练模型的目的是学习矩阵和，使得预估值拟合真实观测的兴趣分数。矩阵和是Embedding层的参数。开始训练之前首先要准备一个数据集，数据集是（用户ID，物品ID，兴趣分数）的集合，记作，其中是用户ID，是物品ID，是真实观测的兴趣分数。数据集中的兴趣分数是系统记录的，比如：如果有曝光但是没有点击记为0分，点击、点赞、收藏、转发各算1分，这些行为都说明用户对物品感兴趣，那么兴趣分数最低是0，最高是4。训练的目的就是让模型的输出去拟合兴趣分数。模型中有Embedding层可以把用户ID，物品ID映射成向量，第号用户映射成向量，第号物品映射成向量。训练的时候需要解这样一个优化问题，优化变量是矩阵，它们是Embedding层的参数。优化公式：，这里的三元组是训练集中一条数据，意思是用户对物品的兴趣分数是，这一项是向量与向量的内积，它是模型对兴趣分数的预估，反应第号用户有多喜欢第号物品。这一项是真实兴趣分数与预估值之间的差，我们希望这个差越小越好，这里取差的平方，其越小，越接近真实值。对每一条记录差的平方求和作为优化的目标函数，对目标函数求最小化，优化的变量是矩阵和，求最小化可以使用随机梯度下降算法，每次更新矩阵的一列，这样就可以学习出矩阵和。

在实践中并不会使用矩阵补充，其缺点：仅使用了ID embedding，用两个Embedding层，把物品ID和用户ID映射成两个向量，仅此而已，且没有利用用户（性别、年龄、地理定位、感兴趣的类目）、物品（类目、关键词、地理位置、作者信息）属性。知道这些属性，召回可以做的更精准；负样本的选取方式不对，样本指的是用户和物品的二元组，记作，训练向量召回模型需要正样本和负样本。矩阵补充的正样本指的是曝光之后有点击、交互的行为，矩阵补充的负样本指的是曝光之后，没有点击、交互行为。但是负样本的选取方式是错误的。再就是训练模型的方法不好，矩阵补充模型用向量的内积作为兴趣分数的预估，这样没错，但是效果不如余弦相似度。工业界普遍适用余弦相似度，而不是内积。矩阵补充使用平方损失函数（回归），让预估的兴趣分数拟合真实的兴趣分数。这样做的效果不如用交叉熵损失函数（分类），工业界通常用分类判定一个样本是正样本还是负样本。

在训练好模型之后，可以把模型应用在推荐系统中的召回通道，并且要把训练好的模型存储在正确的地方，便于做召回。训练得到矩阵和，它们是Embedding层的参数。的每一列对应一个用户；的每一列对应一个物品。线上做推荐的时候会用到矩阵和。这两个矩阵可能会很大，为了快速读取和查找需要特殊的存储方式。把矩阵的列存储到key-value表。key是用户ID，value是矩阵的一列。给定一个用户ID，在表中查找并返回一个向量（用户的embedding）。另一个矩阵也很大，矩阵的存储和索引比较复杂，不能简单的用key-value存储。在把Embedding向量做存储之后，可以开始做线上服务，把用户ID作为key值，查询key-value表，得到用户的向量，记作，我们要查找用户最感兴趣的个物品作为召回结果，这叫做最近邻查找。把第号物品的embedding向量记作，计算用户 向量和向量的内积，这是用户对第号物品兴趣的预估，返回内积最大的k个物品，这些物品就是召回的结果。这种最近邻查找有一个严重的问题。如果逐一对比所有物品，时间复杂度正比于物品数量。这种巨大的计算量是不可接受的，根本做不到线上的实时计算。有很多算法可以加速最近邻查找，这些算法非常快，即使有几亿个物品最多也只需要几万次内积，这些算法的结果未必是最优的，但不会比最优结果差多少，快速最近邻查找已经被集成到了许多向量数据库(Milvus、Faiss、HnswLib等等)当中。做最近邻查找需要定义什么是最近邻？也就是衡量最近邻的标准，比如最近邻可以定义为：欧式距离最小（L2距离）、向量内积最大（内积相似度）、向量夹角余弦最大（cosine相似度）。加速最近邻查找的方法：先做数据预处理，把数据划分成很多区域，数据如何划分取决于最近邻的标准，如果采用cosine相似度，那么划分的结果就是扇形。如果使用欧几里得距离，划分的结果就是多边形。划分之后每个区域用一个向量来表示。划分区域之后，每个区域都用一个单位向量来表示，假如有一个点，划分成一万个区域，索引一共有一万个k值，每个向量是一个区域的k值，给定一个向量可以快速取回这个区域所有的点。有了这样一个索引就可以在线上快速做召回。在线上给一个用户做推荐，这个用户的embedding向量记作，首先把这个向量与索引中的向量作对比，计算它们的相似度，如果物品数量是几亿，索引中的向量只有几万而已，这一步的计算开销不大，计算相似度之后，我们发现这个向量与相似，通过索引我们找到这个区域内的所有的点，每个点对应一个物品，接下来计算点与区域内所有点的相似度，如果有几亿个物品被划分到几万个区域，平均每个区域只有几万个点，所以这一步只需要计算几万次相似度，计算量也不大。假如我们要找与向量最相似的三个点，对应三个物品，这三个物品就是最近邻查找的结果。比暴力枚举快了一万倍。

召回 - 双塔模型

双塔模型(DSSM)的结构：我们知道用户ID，还能从用户填写的资料、用户行为中获取许多特征，包括用户的离散特征、连续特征。所有这些特征不能直接输入到神经网络中，需要先做一些处理，比如用Embedding层把一个用户映射到一个向量。用户还有很多离散特征，比如所在城市，感兴趣的话题等等，用Embedding层把离散特征映射一个向量，对于每个离散特征用单独的Embedding层得到一个向量，比如用户所在城市用一个Embedding层、用户感兴趣的话题用另外一个Embedding层，对于性别这样类别很少的离散特征可以用One-hot编码就行，不做Embedding层。用户还有很多连续特征，比如年龄、活跃程度、消费金额等，不同的连续特征有不同的处理方法。最简单方式归一化，让均值是0，标准差是1。有些长尾分布的连续特征需要特殊处理，比如取对数或做分桶等处理。做完特征处理得到很多特征向量，把这些向量都拼起来输入神经网络。神经网络可以是简单的全连接网络，也可以是更复杂的结构，比如是深度交叉网络，神经网络输出一个向量，这个向量就是用户的表征，做召回会用到这个向量。物品的特征也是用类似的方法来处理，用Embedding层处理物品ID和物品离散特征，用归一化、取对数或分桶等方法处理物品连续特征。把得到的特征输入一个神经网络，神经网络输出的向量就是物品的表征，用于做召回。如下图所示：

这样的模型就叫双塔模型(DSSM)，左边的塔提取用户的特征，右边的塔提取物品的特征。双塔模型的不同之处就是使用了ID之外的多种特征，作为双塔的输入。两个塔各输出一个向量，记作，两个向量的内积就是模型最终的输出，预估用户对物品的兴趣，现在更常用余弦相似度()，两个塔的输出分别记作，余弦相似度意思是两个向量夹角的余弦值，他等于这两个向量的内积再除以除以的二范数，再除以的二范数。其实相当于对两个向量先做归一化，然后再求内积。余弦相似度的大小介于-1~1之间。

这里有三种训练双塔模型的方式：

• pointwise训练：独立看待每个正、负样本，做简单的二元分类训练模型，把正样本和负样本组成一个数据集，在数据集上做随机梯度下降双塔模型。
• pairwise训练：每次去一个正样本、一个负样本，组成一个二元组，损失函数为Triplet hinge loss、Triplet logistic loss。
• listwise训练：每次取一个正样本、多个负样本组成一个列表，训练方式类似于多元分类。

训练的时候要用到正样本、负样本，该怎样选择正负样本呢？正样本就是用户点击过的物品，用户点击过一个物品，就说明用户对这个物品感兴趣；负样本的意思是用户不感兴趣的，在实践中负样本的选择是比较讲究的，有几种看起来比较合理的负样本，比如没有被召回的？召回的但是被粗排、精排淘汰的？曝光但是未点击？

pointwise训练是最简单的训练方式，我们把召回看作是最简单的二元分类任务，正样本意思是历史记录显示用户对物品感兴趣，对于正样本，应该鼓励向量对相似度接近1；负样本意思是用户对物品不感兴趣，应该鼓励向量对相似度接近-1，这就是一个很典型的二元分类问题，如果做pointwise训练，可以控制正负样本数量的比例为或，这算是业内的经验。

pointwise训练：做训练的时候每一组的输入是一个三元组，包括一个用户和两个物品，左边的物品是正样本，就是用户感兴趣的物品，右边的物品是负样本，是用户不感兴趣的物品。把用户的特征和物品的特征各自做变换，然后输入神经网络，最后输出三个向量，用户的特征向量记作，两个物品的特征向量记作，两个物品的塔结构是相同的，里边的Embedding层和全连接层都用一样的参数，分别计算用户对两个物品的兴趣，用户对正样本物品的兴趣是向量的余弦相似度，这个值越大越好，最好是接近1，用户对负样本物品的兴趣是向量的余弦相似度，这个值越接近-1越好，

pairwise训练：做pairwise训练的基本想法是希望用户对正样本的兴趣尽量大，对负样本的兴趣尽量小，也就是，而且两者之差越大越好，我们希望看到用户对正样本的兴趣很大，而对负样本的兴趣很小，最好是，这个是一个超参数，需要调整。如果前者比后者大了，则没有损失；否则，如果用户对正样本的兴趣不够大，没有比负样本的兴趣大，就会有损失，损失等于，这样就推导出了下面的损失函数(Triplet hinge loss)：，训练的时候每个样本都是一个三元组，向量是用户的表征，向量是物品正样本和负样本的表征。我们希望损失函数越小越好，训练的过程就是对损失函数求最小化，用梯度更新双塔神经网络的参数。Triplet hinge loss只是一种损失函数，还有Triplet logistic loss，Triplet logistic loss是这样定义的：，也就是让尽量小，而尽量大，都是希望对正样本的兴趣分数尽量高，负样本的兴趣分数尽量低，这里的是大于0的超参数，控制损失函数的形状。可以通过最小化来训练这样的双塔模型，训练样本都是三元组，一个用户、一个正样本和一个负样本物品。pairwise训练流程如下图所示：

listwise训练：做listwise训练的时候，每次取一个正样本和很多负样本，需要一个用户，把它的特征向量记作，去一个正样本意思是历史记录显示用户喜欢这个物品，把这个物品的特征向量记作，还需要取个负样本，把它们的特征向量记作，做训练的时候，要鼓励向量之间的余弦相似度要尽量大，鼓励负样本的余弦相似度尽量小。向量的余弦相似度是一个介于-1~1之间的实数，意思是用户对正样本兴趣的预估分数，这个分数越大越好，最好是接近1；这些余弦相似度对应负样本，它们是用户对个负样本兴趣的预估分数，这个分数越小越好，最好是接近-1。把这个分数输入进softmax激活函数，激活函数输出个分数，这些分数都介于0~1之间，最左边的分数对应正样本，希望这个分数越大越好，最好接近于1。对应于负样本，希望这些分数越小越好，最后都接近于0。是正样本的标签，意思是鼓励接近于1，负样本的标签是，意思是鼓励接近于0。我们用和的交叉熵作为损失函数，训练的时候最小化交叉熵，意思是鼓励softmax函数输出接近标签。其实交叉熵为，训练的时候最小化交叉熵，也就是最大化，这就等价于最大化正样本的余弦相似度，最小化负样本的余弦相似度。listwise训练流程如下图所示：