京东电商推荐系统实践( 三 ) _推荐系统

文章插图

这里我列了 paper 中 wand 算法的伪代码。出于时间关系，我们不会过算法逻辑的细节。我认为它的主要的思路是通过快速使用 upper bound 做截断和跳转，可以略过很多明显不符合的候选 doc，从而减少计算 score 的次数。当然这种方法对于线性模型来说，有一个缺点，当我们需要多样性的时候，没办法很好的实现在模型中增加多样性的。
wand 算法目前已经应用非常广泛了，在很多开源的索引如 lucene 中，也会用到这种方法快速计算文本相关分。

文章插图

刚刚我们介绍了使用倒排索引做第一轮排序，以及一个常见的排序加速算法，回过来我们思考一下倒排索引本身，它适用于什么场景，不适用于什么场景。
首先它适用于 kv 查找这种场景，并且 kv 查找也属于实际应用很多的情况。但是对于更复杂的方式，类似 graph 的召回方式不友好，比如找用户看过的商品中相似商品的相关商品，这时实现起来会比较麻烦，这是它的一些限制。再一个，我们需要有较好的截断策略，例如底层使用 relevence score 截断，排序使用 GBDT 。
当然，索引还会受到机器本身的内存限制，限于机器的大小，很多时候我们需要多机分片部署索引，这样会带来一定的复杂性。虽然有些限制，但是索引是目前应用很广泛、有效的方式，包括在推荐、搜索等领域都会使用到。
2. KNN 召回

文章插图

除了索引召回，KNN 也是现在较常用的一种召回方式。首先，我们把所有的候选集转换成 embedding，我们把用户兴趣也可以转换成 embedding，通过定义 embedding 之间距离计算公式，我们可以定义 KNN 召回问题，也就是在全部候选池中，找到与用户最接近的 k 个结果。

文章插图

定义好 KNN 召回的问题，下一步就是如何找到最近的 K 个候选集。由于整个候选集非常大，每次都使用用户的 embedding 去全量计算距离是不现实的，只能使用一种近似算法。我们今天分享其中的一种近似算法。是 facebook 开源的 KNN 计算库 faiss 使用的。其原理：
首先需要对全部候选集进行分块，每一块都会有自己的质心。paper 中使用 Lloyd 算法，将整个空间划分开。分块后，就需要对每一块构建索引，进而通过索引实现快速检索的功能。
右图是索引构建和检索的方法。
上半部分是如何构建索引（这里的优化点是使用了二级索引）：首先拿到 y 候选集之后，做一个 quantizer 分类得到一个一级索引，把它放到索引表中，另外还得到残差 compute residual，可以对残差再进行一次 quantizer，得到一个二级索引，通过两级索引来加快检索的速度，同理，在真正的 quary 的时候，拿到的是用户的向量 x，先做一个 quantizer，得到 k 近邻的一级索引，然后查找 k 个一级索引，同时拿到 k 个二级索引，然后在二级索引中查找，然后这里还有很多加速的算法（这里就不展开了），通过这样一种多层的查询方式来做到加速 K 近邻的算法。
PS：关于 KNN 的一些思考，KNN 是一种有效的方式，但是不是唯一有效的方式。比如之后分享的 TDM，能够比 KNN 更加灵活。
▌实验平台

文章插图

最后简单介绍下分层实验平台，因为大家想快速迭代特征和模型，离不开实验，经常会遇到的情况是实验流量不够用了，这时就需要对实验做分层。分层的逻辑见右图，通过在不同的 Layer 使用不同的哈希函数，保证每个 Layer 之间流量是正交的，这样就可以在不同的 Layer 上做不同的实验。

文章插图

分层实验的具体做法：召回->排序->后处理->业务，另外还有一部分对齐流量，用来做全量的验证。
分层的优点，可以用于做实验的流量多，适合快速迭代；缺点，需要严格控制层与层之间的关系，防止相互干扰。
作者：孟崇，京东推荐架构负责人。负责京东推荐系统的 ranking 算法架构和模型训练。硕士毕业于中科院自动化所，先后在 yahoo、猎豹移动和京东从事推荐的工作，有丰富的推荐算法经验。