【王树森推荐系统】召回05：矩阵补充、最近邻查找

概述

• 这节课和后面几节课将详细讲述向量召回，矩阵补充是向量召回最简单的一种方法，不过现在已经不太常用这种方法了
• 本节课的矩阵补充是为了帮助理解下节课的双塔模型
• 上节课介绍了embedding，它可以把用户ID和物品ID映射成向量

矩阵补充

模型结构

• 下面的模型图是基于embedding做推荐
  
• 模型的输入是一个用户ID和一个物品ID，模型的输出是一个实数，是用户对物品兴趣的预估值，这个数越大，表示用户对物品越感兴趣
• 左边的结构只有一个embedding层，把一个用户ID映射成向量，记作向量 a，这个向量是对用户的表征
• 回忆一下上节课的内容：embedding 的参数是一个矩阵，矩阵中列的数量是用户数量，每一列都是图中 a 那么大的向量，embedding 层的参数数量等于用户数量 × 向量 a 的大小

• 右边的结构是另一个 embedding 层，把一个物品ID映射到向量，记作 b，大小和向量设置成一样的，向量 b 是对物品的表征。embedding 层的参数是一个矩阵，输出的向量 b 是矩阵的一列，矩阵中列的数量是物品的数量
  
• 模型一共用了两个 embedding 层，它们不共享参数
  
• 对向量 a 和向量 b 求内积得到一个实数作为模型的输出，这个模型就是矩阵补充模型
  

训练

基本想法

• 用户 embedding 参数矩阵记作 $A$。第 $u$ 号用户对应矩阵第 $u$ 列，记作向量 $a_u$
• 第 $u$ 号用户对应矩阵的第 $u$ 列，记作向量 $a_u$
  
• 物品 embedding 的参数矩阵记作 $B$。第 $i$ 号物品对应矩阵第 $i$ 列，记作向量 $b_i$
  
• 内积 $<a_u,b_i>$ 是第 $u$ 号用户对第 $i$ 号物品兴趣的预估值，内积越大，说明用户 $u$ 对物品 $i$ 的兴趣越强
• 训练模型的目的是学习矩阵 $A$ 和 $B$ ，使得预估值拟合真实观测的兴趣分数。矩阵 $A$ 和 $B$ 是 embedding 层的参数

数据集

• 数据集：(用户ID, 物品ID, 兴趣分数) 的集合，记作 $\Omega =\{(u,i,y)\}$ 。含义为该用户对该物品真实的兴趣分数在系统里有记录
• 数据集中兴趣分数的记录方法如下：
  • 曝光但是没有点击 → 0分
  • 点击，点赞，收藏，转法 → 各算 1 分，这些行为都说明用户对物品感兴趣
  • 分数最低是 0，最高是 4
• 训练的目的是让模型输出拟合兴趣分数

训练

• 把用户ID和物品ID映射成向量
  • 第 $u$ 号物品 → 向量 $a_u$
  • 第 $i$ 号物品 → $b_i$
• 求解优化问题，得到参数 $A$ 和 $B$ （它们是优化变量，embedding层的参数）
• 我们希望预估值和真实值的差越小越好，我们对其取平方。差越小，则预估值越接近真实值。对所有差的平方求和，作为优化的目标函数
• 求最小化可以用随机梯度下降等方法，每次更新矩阵 $A$ 和 $B$ 的一列，这样就可以学出矩阵 $A$ 和 $B$
  

矩阵补充

• 系统里面物品很多，一个用户看过的物品只是系统的极少数
  
• 矩阵中大部分都是灰色，只有少部分是绿色，也即曝光给用户的物品只是少数，而我们并不知道没曝光给用户的物品用户感不感兴趣
• 我们用绿色位置的数据去训练模型，我们就可以知道灰色位置的分数，也就是把矩阵的元素给补全，这就是为什么模型叫矩阵补充
• 把矩阵元素补全之后我们就可以做推荐，给定一个用户，我们选出对应用户的行中分数较高的物品推荐给该用户

在实践中效果并不好…

• 缺点1：仅使用ID embedding，没利用物品，用户属性
  • 物品属性：类目，关键词，地理位置，作者信息等等
  • 用户属性：性别，年龄，地理定位，感兴趣的类目等等
  • 考虑以上的属性，推荐可以更加精准
  • 双塔模型可以看作矩阵补充的升级版，它不单单使用用户ID和物品ID，还会结合各种物品属性和用户属性，双塔模型的实际表现是非常好的
• 缺点2：负样本的选取方式不对
  • 样本：用户——物品的二元组，记作 $(u,i)$
  • 正样本：曝光之后，有点击，交互（正确的做法）
  • 负样本：曝光之后，没有点击，交互（错误的做法）。这是一种想当然的做法，学术界的人可能以为这样没错，但可惜在实践中不 work。后面的课程会讲解正负样本怎么选。
• 缺点3：做训练的方法不好
  • 内积不如余弦相似度，工业界普遍用余弦相似度而不是内积
  • 用平方损失（回归）不如用交叉熵损失（分类）。工业界一般做分类来判断一个样本是正样本还是负样本

线上服务

在训练好模型后，可以将模型用于推荐系统中的召回通道。比如在用户刷小红书的时候，快速找到这个用户可能感兴趣的一两百篇笔记

模型存储

做完训练之后，要把模型存储在正确的地方便于做召回。

1. 训练得到矩阵 $A$ 和 $B$ ，它们是 embedding 层的参数。这辆个矩阵可能会很大，比如小红书有几亿个用户和几亿篇笔记，那么这几个矩阵的列数都是好几亿。为了快速读取和快速查找，需要特殊的存储方式
   • $A$ 的每一列对应一个用户
   • $B$ 的每一列对应一个物品
2. 把矩阵 $A$ 的列存储到 key-value 表。
   • key 是用户的ID，value 是 $A$ 的一列
   • 给定用户ID，返回一个向量（用户的embedding）
3. 矩阵 $B$ 的存储和索引比较复杂。不能简单地用 key-value 表

线上服务

在训练好模型，并且把 embedding 向量做存储之后，可以开始做线上服务，某用户刷小红书的时候，小红书开始在后台做召回：

1. 把用户ID作为 key，查询 key-value 表，得到该用户的向量，记作 $a$
2. 最近邻查找：查找用户最有可能感兴趣的 k 个物品，作为召回结果
   • 第 $i$ 号物品的 embedding 向量记作 $b_i$
   • 内积 $<a,b_i>$ 是对第 $i$ 号物品兴趣的预估
   • 返回内积最大的 k 个物品

这种最近邻查找有一个问题：如果枚举所有物品，时间复杂度正比于物品数量，这种计算量是不可接受的。比如小红书有几亿篇笔记，逐一计算向量 $a$ 和每一个向量 $b$ 的内积是不现实的，做不到线上的实时计算

近似最近邻查找（ANN）

• 有很多种算法加速最近邻查找，这些算法非常快，即使有几亿个物品也只需要几万次内积，这些算法的结果未必是最优的，但是不会比最优结果差多少

• 支持的系统有：Milvus, Faiss, HnswLib等等

• 衡量最近邻的标准：

  • 欧氏距离最小（L2距离）
  • 向量内积最大（内积相似度）
  • 向量夹角余弦最大（cosine相似度，推荐系统最常用），把所有向量都做归一化，让它们的二范数都等于 1，那么此时内积等于余弦相似度

• 如下图，其中 a 是一个用户的embedding，我们需要召回用户感兴趣的物品，这就需要计算 a 与所有点的相似度。如果用暴力枚举，计算量正比于点的数量，即物品的数量

• 想要减少最近邻的查找的计算量，必须避免暴力枚举

• 我们在查找之前，先对数据做预处理，对数据进行如下图的划分：对于如何划分取决于最近邻的标准
  • 如果是余弦相似度，那么划分结果就是这样的扇形
  • 如果是欧式距离，那么结果就是多边形

• 划分之后，每个区域用一个向量表示，比如下面的蓝色区域用那个蓝色箭头的向量表示。黄色区域用图中黄色的向量表示。
• 这些向量的长度都是 1。
• 划分之后建立索引，把每个区域的向量作为 key，区域中所有点的表作为 value。给定一个蓝色向量，就应该取回蓝色扇形中所有的点

• 现在在划分之后，每个区域都用一个单位向量来表示。那么如果我们划分成 1w 个区域，索引上就会一共有 1w 个 key 值。每个向量是一个区域的key值

• 给定一个向量，就可以快速取回区域中的所有点。这样我们就可以快速做召回了
  
• 现在我们要做推荐，给定一个用户的 embedding 向量 a。我们首先把向量 a 和索引中的向量做对比，计算它们的相似度
• 如果物品数量是几亿，索引中的 key 数量也只有几万而已，这一步的计算开销不大

• 计算相似度之后，我们会发现橙色的向量和 a 最相似
• 通过索引，我们可以找到这个区域内所有的点，每个点对应一个物品
• 接下来计算 a 和区域内所有点的相似度。如果一共有几亿个物品被划分到了几万个区域，平均每个区域只有几万个点，所以这一步只需要计算几万次相似度，计算量不大

• 假如我们想要找到和向量 a 夹角最小的三个点，那么我们会找到蓝色框住的三个点，代表三个物品。这三个物品就是最近邻查找的结果
• 哪怕有几亿个物品，用这种方法查找，最终也只需要几万次查找，比暴力枚举快 1w 倍

总结