Inverted Index for embeddings基于向量的倒排

A brief introduction on inverted index used in industry

学过information retrieval的同学们或多或少都接触过一些像倒排索引(inverted index)，正排索引的概念。对于一个文件管理系统而言，倒排索引关系着检索的效率。比如一个管理文章的图书系统，其中一个倒排链可能存储了所有包含“black”字眼的文章的id，于是如果我们在搜索栏里输入”black”，系统能够锁定这些文章，然后再通过更精细的条件匹配找到我们需要的文章。

倒排链在广告系统中也非常常用，且应用在召回环节。广告系统的任务是，给定一个用户流量，从系统中的千万个广告中匹配个位数的相关广告给该用户。匹配的广告要：第一，和用户相关，如果不相关会降低用户的用户体验；第二，该用户要与匹配的广告相关，不然就损害了广告主的利益；第三，因为大部分互联网广告都是广告主竞价的模式，所以平台希望最终展示给用户的广告都是竞价符合一定标准的。只有用户，广告主，平台的三方利益兼顾了，广告系统的生态才能欣欣向荣。

广告系统的链路一般都是由几个模块构成：召回(从千万广告中找到万个相关的广告)，粗排，精排，甚至还有重排等。这个多模块的架构是出于系统限制的考虑设计的。比如，在召回环节，因为有限的计算资源和时间限制，只能用简单的模型来快速筛选。而到了精排环节，就可以用深度模型去处理广告了因为广告池到了该环节已经变小了。传统召回都用DMP(Data managment platform)去管理用户数据(用户标签和人群画像)。比如，对于一个普通的男性用户，他的标签有：年龄，性别，地址等等。这个男性可以属于多个人群(比如他即可能是个城市白领，也能是一个御宅)。广告主在投放广告的时候，会给自己的广告选标签。比如卖卫生巾的广告主会要求把卫生巾广告投放给女性用户。这种对比广告和用户标标签的召回就非常依赖于倒排链。

召回，作为整个链路的第一个环节，是广告系统的上限及下限。如果召回的物品毫无关联，后链路再好也没办法选出用户满意的广告。基于DMP的召回系统，运用规则去匹配广告，不能精确定位用户的个人喜好。因为规则是基于大量人群的统计学方法去挖掘的。很多公司为了克服这个问题都把用户模型提到了召回环节，包括了Facebook EBR，百度Mobius等等。场景不一样但模型和检索方式都大同小异：一个双塔模型，用户塔生成用户embedding，物品塔生成的物品embedding存储起来。用户embedding和物品embedding的内积可以算出用户维度的信息比如CTR。最后召回可以转换成CTR排序，也就是说召回环节想要召回出CTR最高的物品（高CTR代表用户更倾向点击）。由于内积与CTR是正相关，所以CTR排序最终又转换成最大内积问题。用白话说，召回想要从千万个物品embedding中找出与用户embedding的内积最大的前几万个。

如何用embedding来召回面临着两个问题：

• 以前我们学的Nearest Neighbor方法都是给定一个Query，从Corpus中找出L2 norm最小的向量，属于NN问题，不满足我们的最大内积问题Maximum inner-product(MIP)的设定
• 如果我们找到了一个方法，我们也需要遍历千万的Corpus做向量内积，明显会超时

以下篇幅我们一一讲解如何解决上面两个问题。第一个问题，我们可以用现有的方法把MIP问题转化成一个NN问题。如此我们就可以用NN的方法去操作了。最终NN找到的相邻的向量，都是具有和Query向量最大内积的向量。第二个问题，如何快速检索出这些向量。我们需要借助approximate nearest neighbor (ANN)的方法，用精度换时间。可以通过实验找出一个sweet spot，保证召回率和时间都在可控的范围内。

其实基于ANN的检索非常有趣。ANN的思想很像编程里的divide-and-conquor，我们来细说一下。