Faiss库

Faiss是一个用于高效相似性搜索（similarity search）和密集向量聚类的库。它包含的算法可以搜索任意大小的向量集，甚至可以是不适合RAM的向量集。它还包含用于评估和参数调整的支持代码。

Faiss是用C++编写的，可以被Python调用。一些最有用的算法是在GPU上实现的。

什么是相似性搜索？

给定一组$d$维向量$x_i$，Faiss将对它构建RAM中的一种数据结构。结构构造完毕后，当给定$d$维的新向量$x$时，它将有效执行操作：

$$j=arg\underset{i}{\min }||x-x_i||$$

其中$||\cdot ||$为欧几里得距离（$L^2$）。

对于Faiss，数据结构是一个 index，一个可以用add方法添加向量的的对象。请注意，假设$x_i$的 index是固定的。

argmin是对索引的搜索操作。

除此之外，Faiss还有以下功能：

• 不仅可以返回最近的邻居，还可以返回第二、第三、第k个最近的邻居
• 一次搜索多个向量，而不是一个（批处理）。对于许多索引类型，这比逐个搜索向量要快
• 以精度换取速度，即实现速度快10倍或占用内存少10倍的方法，代价是有10%概率会给出错误的结果
• 执行最大内积搜索$arg{\max }_i⟨x,x_i⟩$，而不是最小欧几里德距离搜索。这对其他距离（$L_1、L_{inf}$等）的支持有限。
• 返回查询点给定半径内的所有元素（范围搜索）
• 将索引存储在磁盘上，而不是存储在RAM中。

获取一些数据

Faiss处理固定d维的向量集合，通常需要10到100秒。这些集合可以存储在矩阵中。我们假设按行存储，即向量数$i$的第$j$个分量存储在矩阵的第$i$行$j$列中。Faiss只使用32位浮点矩阵。

我们需要两个矩阵：

xb表示数据库(database)，它包含所有必须索引的向量，我们将在其中搜索。它的尺寸是$nb\times d$。

xq为查询(query) 向量，我们需要找到最近的邻居。它的大小是$nq\times d$。如果我们有一个查询向量，nq=1。

在下面的例子中，我们将使用在d=64维的服从均匀分布的向量。为了差异化，我们在第一维度上添加了小的递增增量，增量取决于向量索引值。

import numpy as np
import faiss
d = 64                           # dimension
nb = 100000                      # database size
nq = 10000                       # nb of queries
np.random.seed(1234)             # make reproducible
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.
xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.

建立索引并向其中添加向量

Faiss是围绕Index对象构建的。它封装了数据库向量集，并可选地对它们进行预处理，以提高搜索效率。索引有很多种类型，我们将使用最简单的版本，只对它们执行L2距离搜索：IndexFlatL2。

所有索引(indexes)都需要知道它们所操作的向量的维数，在我们的例子中是d。然后，大多数索引还需要一个训练阶段，以分析向量的分布。对于IndexFlatL2，我们可以跳过此操作。

建立和训练索引时，可以对索引执行两个操作：add 和 search。

为了向索引中添加元素，我们称之为add on xb。我们还可以显示索引的两个状态变量：is_trained（表示是否需要训练的布尔值）和ntotal（表示索引向量的数量）。

一些索引还可以存储与每个向量对应的整数ID（不是IndexFlatL2）。如果没有提供id，add只使用向量序号作为id，即第一个向量得到0，第二个向量得到1，以此类推。

index = faiss.IndexFlatL2(d)   # build the index
print(index.is_trained)
index.add(xb)                  # add vectors to the index
print(index.ntotal)

输出：

True
100000

搜索

可以对索引执行的基本搜索操作是k近邻搜索，即对于每个查询向量(query vector)，在数据库中查找其k近邻。

该操作的结果可以方便地存储在大小为$nq\times k$的整数矩阵中，其中I的第i行包含查询向量i的邻居的id，按距离的递增排序。除此矩阵外，搜索操作还返回一个$nq\times k$浮点矩阵D，其中包含相应的平方距离。

为了健全性检查（sanity check），我们可以首先在数据库内搜索它内部的几个向量，以确保其最近的邻居确实是向量本身。

k = 4                          # we want to see 4 nearest neighbors
D, I = index.search(xb[:5], k) # sanity check
print('Size of I:',np.shape(I))
print('Size of D:',np.shape(D))
print(I)
print(D)
D, I = index.search(xq, k)     # actual search
print('Size of I:',np.shape(I))
print('Size of D:',np.shape(D))
print(I[:5])                   # neighbors of the 5 first queries
print(I[-5:])                  # neighbors of the 5 last queries

结果：

健全性检查的输出应如下所示：

Size of I: (5, 4)
Size of D: (5, 4)

[[  0 393 363  78]
 [  1 555 277 364]
 [  2 304 101  13]
 [  3 173  18 182]
 [  4 288 370 531]]
 
[[0.        7.175174  7.2076287 7.251163 ]
 [0.        6.323565  6.684582  6.799944 ]
 [0.        5.7964087 6.3917365 7.2815127]
 [0.        7.277905  7.5279875 7.6628447]
 [0.        6.763804  7.295122  7.368814 ]]
 

即，每个查询的最近邻实际上是向量的索引，对应的距离为0。在一行之内，距离在增加。

实际搜索的输出类似于

Size of I: (10000, 4)
Size of D: (10000, 4)
# 第一近邻，第2近邻，第3近邻，第4近邻
[[ 381  207  210  477]
 [ 526  911  142   72]
 [ 838  527 1290  425]
 [ 196  184  164  359]
 [ 526  377  120  425]]
 
[[ 9900 10500  9309  9831]
 [11055 10895 10812 11321]
 [11353 11103 10164  9787]
 [10571 10664 10632  9638]
 [ 9628  9554 10036  9582]]

---

由于向向量的第一个分量添加了递增的增量。因此，前几个向量的近邻向量位于数据集的开头，而在10000左右的向量的近邻向量在数据集中的索引也在10000左右。

参考：

[1]https://faiss.ai/

[2] https://github.com/facebookresearch/faiss/wiki/Getting-started