矩阵补充，最近邻查找

矩阵补充，最近邻查找

矩阵补充是向量召回最简单的一种方法，现在不常用，学习矩阵补充是为了更好的理解后面学到的双塔模型

下图，输入用户ID和物品ID后从Eebedding层拿到对应的向量做内积，内积的结果就是矩阵补充

模型训练

基本思路

数据集

训练

下图公式中

• (u，i，y) 是训练集中的一条数据，表示用户u对物品i的真实兴趣分数是y。

• <au,bi>是向量a,b的内积，是矩阵补充模型对兴趣分数的预估，反映第u号用户有多喜欢第i号物品

  

• y - <au,bi> 是真实兴趣分数y与预估值的差，我们希望这个差越小越好。我们取该差的平方，差的平方越小，则预估值越接近真实值y

• Σ(u，i，y)∈Ω 表示对每条记录的差的平方求和作为优化的目标函数

• min A,B 对目标函数求最小化，优化的变量是矩阵A和B。求最小化可以用随机梯度下降等算法每次更新矩阵A和B的一列，这样就可以学出矩阵A和B

为什么这个模型叫矩阵补充？我们拿下图绿色位置的数据训练出模型。有了模型我们可以预估出灰色位置的分数，也就是把矩阵的元素给补全，这就是为什么该模型叫矩阵补充。

把矩阵元素补全后，就可以做推荐，给定一个用户，选出用户对应行中分数较高的物品推荐给该用户。

矩阵补充缺点

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

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

缺点3：训练模型的方法不好

• 矩阵补充模型用内积<au,bi>`作为兴趣分数的预估，效果不如余弦相似度，工业界普遍使用余弦相似度

• 用平方损失函数(回归)，让预估的兴趣分数拟合真实的兴趣分数，不如用交叉熵损失（分类）。工业界通常用交叉熵损失做分类判断一个样本是正样本还是负样本

模型存储

线上做推荐时，要用到矩阵A和B,这两个矩阵可能很大。比如小红书有几亿用户，几亿篇笔记，这两矩阵列数都是好几亿，为了快速读取快速查找，需要特殊的存储方式，如下：

线上服务

在训练好矩阵补齐模型后，并且把embedding向量做存储之后，可以开始做线上服务。 将其运用在推荐系统中的召回通道，比如在用户刷小红书时快速找到这个用户感兴趣的几百篇笔记。

近似最近邻查找 （Approximate Nearest Neighbor Search）

问题：上述最近邻查找如果枚举所有物品，则时间复杂度正比与物品数量，计算量很大，在线上这是不可接受的。需要对最近邻查找进行优化。

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

快速最近邻查找算法已被集成到很多向量数据库系统中。比较有名的包括：Milvus、Faiss、HnswLib等

如果系统不支持余弦相似度，可以把所有向度做归一化让他们的二范数全等于1，则向量之间的内积就等于余弦相似度

加速最近邻查找的思路

1. 划分区域。每个区域用一个向量表示，这些向量的长度都是1。
2. 建立索引。表示每个区域的向量作为key，把区域中所有点（物品embedding向量）的列表作为value

3. 将用户embedding向量a与索引中的各个key做对比（如果物品数量是几亿，索引中key也只有几万而已，这步计算量不大)

4. 计算用户embedding向量与key向量区域中所有物品的相似度（这一步计算量也不大）。假如我们要向量a找最相似的三个点

总结

矩阵补充是学术界的模型，效果不好。工业界不用矩阵补充模型而是用更先进的双塔模型。

工业界会用一些开源的向量数据库，如Milvus等，其都支持近似最近邻查找。