最近看了下Faiss的原因，今天让我们来Faiss那点事~
全名叫Facebook AI Similarity Search。顾名思义，Facebook的Ai相似检索。主要用来对海量的,高维的向量进行快速靠谱的检索。
在一些深度模型应用场景下，在线推理时间太长，性能要求高的系统很难接受，为此就需要走延迟召回这条路线，离线学习深度模型的表示型向量，构建Faiss索引库，在线快速召回。

但是Faiss之所以落地，它解决了哪些问题？又是如何解决的呢？

解决问题

试想，有一个向量q，要在另外一个规模在1000个规模大小的向量集合中，选择一个最近的向量，距离可以用欧氏距离或者余弦相似度。怎么选？

暴力选，那就需要q和1000个向量，分别算距离，总共需要1000次, O(n), 海量数据下，根本不可行。

那怎么办呢？
这种情况下，Faiss就出现了，来拯救银河系，具体说是来拯救这个问题。锁定了这个问题，一直没有放松，给出了一系列的解决方案。敲黑板就两点：

1. 数据压缩，减少空间占用
2. Product-Quantization，提高检索效率。

如何解决

背景介绍 - 预热阶段

把大象装冰箱总共分三步，总共分三步。
同理，把检索搞定，也是分三步：

1. 压缩训练 （打开冰箱门）
2. 索引数据 (把数据推进去）
3. 检索 （关上冰箱门）

其中最关键的就是1，2两部分，索引，也是Faiss的核心。围着而Faiss则为这种场景提供了一套解决方案。
Faiss从两个方面改善了暴力搜索算法存在的问题：降低空间占用加快检索速度首先，
Faiss中提供了若干种方法实现数据压缩，包括PCA、Product-Quantization等。

三种不同的索引检索方式

接下来，我们会收看三种不同的索引检索方式：

精确搜索

要做到精确，就不能有损失，那就要用最笨的方式，最慢的方式，多快好省在这里是行不通的。
没错，就是暴力检索，即遍历所有的向量，算出最近的向量。 不要训练啊！！！
距离分为两种：
faiss.indexFlatL2： 欧式距离
faiss.indexFlatIP： 内积
代码如下：
index = faiss.IndexFlatL2(d) # buid the index， d是向量维度
// index = faiss.indexFlatIP(d)
index.add(xb)
D,I = index.search(xb[:5],k) # 返回xb[:5]五个向量最近的K个向量。

倒排文件: indexIVFFlat

向量太多了，怎么办？ 暴力破解，岂不要累的血喷！！！
Faiss的第二大招来了，indexIVFFlat（倒排文件）
名字高大上，说起来也很简单。过程如下：
1） 我要打1w个，...., 说错了，我要建100个类，于是，首先使用k-means建立100个聚类中心。
针对query查询向量q， 则：
2）查询最近的聚类中心，也就是锁定最近的类
3）在该类内部，比较所有向量， 得到与查询向量q最相似的向量。

与上面，精确查找不同的是，建索引前，需要实现制订一个量化器（quantizer）， faiss提供了两种衡量相似度的方法， 用于K-means聚类：
1）faiss.METRIC_L2 # 欧式距离，
2）faiss.METRIC_INNER_PRODUCT。 # 向量内积。

nlist =100 # 聚类中心个数
k = 20 # 查找最相似的k个向量
quantizer = faiss.IndexFlatL2(d) # 量化器 d是向量维度。
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)

index.train(data) # 训练数据data
index.add(data) #添加data 在第一次build索引文件的时候，需要经过Train和Add两个过程 。 后面的话只需要Add就行了。
index.nprobe = 50 # 选择n个维诺空间进行索引, .index.nprobe应该是选择最近的50个类，进行查找最最近的向量。
dis, ind = index.search(query, k)

乘积量化倒排文件: IndexIVFPQ

这个可是Faiss的最大招了。设计的很牛掰。最关键的有下面两个部分：
Product Quantizer， 简称PQ，将矢量编码或解码为代码。
Inverted File System，简称IVF。

• Product Quantizer， PQ
  PQ有一个Pre-train的过程，其实就是对应Faiss的Train阶段，共有两部操作：
  1.Clustering
  2.Assign
  以一个128维的向量库为例：

Cluster具体做法：
(a) 切分为4段，这样每一段的就是32维
(b) 针对每一段，都执行下面操作：
聚类，聚256个类，用8bit就可以表示每个类的类ID。
(c) 经过上面2后，每一个向量，分成四段，每一段都属于1个类。
如果用类 ID表示这段向量的话，那就是4个类ID。如下面图，每个向量最后都成了4个类ID。

也就是N * 32 -> N * 4

Assign具体做法：

同样是以N=128，M=4为例，对于每一个查询向量：
（a） 把128维分成4段32维向量，
（b） 计算每一段向量与之前预训练好的簇心的距离，
由于每一段有256个类心，所以需要每一段需要算256次，4段的话算4256次，于是就得到了一个4256的表。
(c） 接下来，就可以按下面方法算，查询向量与库里任意向量的距离了，计算方法如下：
假定，查询向量为q， 库里向量为d：
分别依次查询，库向量每一段所属的类中心向量 与 查询向量对应段的向量距离。 不好意思，前面那个4256的表，都帮我们计算出来了，即查询向量跟所有类（4256）的距离。查表即可~~~

这样的话，我们的计算就大大简便了。至于简便了多少呢？？让我们来认真算下：

查询向量q和所有的类生成表： 4 * 256
假定库里有n个doc， 则需要查表： 4 N次。
所以啊，最后总共需要 4256 + 4 *N次操作。

image.png

代码：
nlist = 50 # 聚类中心个数
k = 4 # 查询相似的k个向量
m = 8 # number of bytes per vector 每个向量都被编码为8个字节大小
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFPQ(quantizer,d,nlist,m,8) ##注意这个时候 没有相似度 度量参数

index.train(xb)
index.add(xb)
index.nprobe = 3 # 搜索的聚类 个数
D,I = index.search(xq[:5],k)

注意：

1. IndexIVFPQ不支持构建增量索引
2. 第一次构建，需要Train + Add两个操作。
   增量操作，则只需要Add