[搜广推]王树森推荐系统——矩阵补充最近邻查找

矩阵补充（工业界不常用）

模型结构

• embedding可以把 用户ID 或者 物品ID 映射成向量
• 输入用户ID 和 物品ID，输出向量的内积（一个实数），内积越大说明用户对这个物品越感兴趣
• 模型中的两个embedding层不共享参数
  

基本想法

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

数据集

• (用户ID，物品ID，兴趣分数)的集合，记作 $\Omega =\{(u,i,y)\}$
• 数据集中的兴趣分数是系统记录的，比如:
  • 曝光但是没有点击，记为0分
  • 点击、点赞、收藏、转发，各记1分
  • 分数最低是0，最高是4

训练

有一个用户-物品交互矩阵，其中行代表用户，列代表物品，矩阵中的元素代表用户对物品的评分。由于用户通常只对少数物品进行评分，这个矩阵往往是稀疏的。因此需要补全这个矩阵

• 把用户ID、物品ID映射成向量。
  • 第 $u$ 号用户 --> 向量 $a_u$
  • 第 $i$ 号物品 --> 向量 $b_i$
• 训练时要求解优化问题，得到参数A和B
  $$mi{n}_{A,B}\sum _{(u,i,y)\in \Omega }(y-<a_u,b_i>{)}^2$$
  其中，A和B是embedding参数矩阵，不是用户-物品交互矩阵
• 解得A，B之后，根据A和B计算用户-物品交互矩阵中未曝光物品（灰色位置）的兴趣分数补全矩阵
• 向用户推荐补全的矩阵中分数较高的物品

缺点

在实践中效果不好…

缺点1:仅用 ID embedding，没利用物品、用户属性。

• 物品属性:类目、关键词、地理位置、作者信息。
• 用户属性:性别、年龄、地理定位、感兴趣的类目。
• 双塔模型可以看做矩阵补充的升级版

缺点2:负样本的选取方式不对。

• 样本:用户-物品的二元组，记作(u,i)。
• 正样本:曝光之后，有点击、交互。(正确的做法)
• 负样本:曝光之后，没有点击、交互。(错误的做法，这是一种想当然的做法，其实没有效果)

缺点3:做训练的方法不好。

• 內积〈au,bi〉不如余弦相似度。
• 用平方损失(回归)，不如用交叉熵损失(分类)

模型存储

1. 训练得到矩阵A和B

• A的每一列对应一个用户。
• B的每一列对应一个物品。

2. 把矩阵A的列存储到 key-value 表。

• key是用户ID，value是A的一列。
• 给定用户ID，返回一个向量(用户的embedding)

3. 矩阵B的存储和索引比较复杂

线上服务

把用户 ID作为 key，查询 key-value 表，得到该用户的向量，记作a°

最近邻查找:查找用户最有可能感兴趣的k个物品，作为召回结果。

• 第 $i$ 号物品的 embedding 向量记作 $b_i$
• 內积$<a,b_i>$是用户对第 $i$ 号物品兴趣的预估。
• 返回內积最大的k个物品。

缺点：如果枚举所有物品，时间复杂度正比于物品数量。

加速最近邻查找

支持最近邻查找的系统:Milvus、Faiss、HnswLib等等。
度
衡量最近邻的标准:

• 欧式距离最小(L2距离)
• 向量内积最大(内积相似度)
• 向量夹角余弦最大(cosine相似度，目前常用)

如何用cosine相似度计算最近邻

1. 在进行线上服务之前对数据进行预处理，划分成很多区域

• 如何划分取决于用什么标准衡量最近邻
  • 欧式距离最小：多边形
  • cosine相似度：扇形
    

2. 划分之后每个区域用一个向量表示

• 这些向量长度都是1（单位向量）
• 根据向量和点建立索引，把每个区域的向量作为key，区域中所有点的列表作为value，这样给定一个向量就可以取回那个区域所有的点
  

3. 线上做召回时，把一个用户的向量a和所有索引向量对比，选出最相似的
4. 通过索引找到物品列表，计算区域内每个物品与用户向量的相似度，选出最相似的k个点

这k个点就是最近邻查找的结果