文件 LocalSearchQuantizer.h

namespace faiss

实现了 k-means 聚类以及许多变体。

版权所有 (c) Facebook, Inc. 及其关联公司。

此源代码已获得 MIT 许可，该许可位于此源树根目录中的 LICENSE 文件中。

IDSelector旨在定义要处理的向量子集（用于删除或作为搜索子集）

PQ4 SIMD 打包和累积函数

基本内核使用 bbs = nb * 2 * 16 向量累积 nq 查询向量，并生成该输出矩阵。 对于 nq * nb <= 4 来说，这很有趣，否则寄存器溢出量会太大。

这些函数的实现分布在 3 个 cpp 文件中，以减少并行编译时间。 模板被显式实例化。

此文件包含用于计算距离的内核的回调。

在整个库中，向量以 float * 指针的形式提供。 当批量处理（添加/搜索）多个向量时，大多数算法都可以得到优化。 在这种情况下，它们作为矩阵传递。 当 n 个大小为 d 的向量作为 float * x 提供时，向量 i 的分量 j 为

x[ i * d + j ]

其中 0 <= i < n 且 0 <= j < d。 换句话说，矩阵始终是紧凑的。 当指定矩阵的大小时，我们称其为 n*d 矩阵，这意味着行优先存储。

I/O 函数可以读取/写入到文件名、文件句柄或抽象介质的对象。

读取函数返回应该使用 delete 释放的对象。 这些对象中的所有引用都归该对象所有。

反向列表的定义 + 一些实现该接口的常见类。

由于 IVF（反向文件）索引对于大规模用例非常有用，因此我们将与它们相关的几个函数分组到这个小库中。 大多数函数都适用于 IndexIVF 和嵌入在 IndexPreTransform 中的 IndexIVF。

此文件中实现了超出 L2 和内积的额外度量标准

实现了一些神经网络层，主要用于支持 QINCo

定义了一些对向量集应用转换的对象。通常，这些是预处理步骤。

struct LocalSearchQuantizer : public faiss::AdditiveQuantizer
#include <LocalSearchQuantizer.h>

LSQ/LSQ++ 的实现，如下两篇论文所述

Revisiting additive quantization Julieta Martinez, et al. ECCV 2016

LSQ++: Lower running time and higher recall in multi-codebook quantization Julieta Martinez, et al. ECCV 2018

此实现主要从 Julieta Martinez 的 Julia 实现翻译而来：(https://github.com/una-dinosauria/local-search-quantization, https://github.com/una-dinosauria/Rayuela.jl)

训练的代码存储在 codebooks 中，在 PQ 和 RQ 中称为 centroids。

公共函数

LocalSearchQuantizer(size_t d, size_t M, size_t nbits, Search_type_t search_type = ST_decompress)
LocalSearchQuantizer()
~LocalSearchQuantizer() override
virtual void train(size_t n, const float *x) override

训练量化器

参数:

x – 训练向量，大小为 n * d

virtual void compute_codes_add_centroids(const float *x, uint8_t *codes, size_t n, const float *centroids = nullptr) const override

编码一组向量

参数:

  • x – 要编码的向量，大小为 n * d

  • codes – 输出编码，大小为 n * code_size

  • n – 向量的数量

  • centroids – 要添加到 x 的质心，大小为 n * d

void update_codebooks(const float *x, const int32_t *codes, size_t n)

根据编码更新码本

参数:

  • x – 训练向量，大小为 n * d

  • codes – 编码后的训练向量，大小为 n * M

  • n – 向量的数量

void icm_encode(int32_t *codes, const float *x, size_t n, size_t ils_iters, std::mt19937 &gen) const

使用迭代条件模式 (icm) 编码给定码本的向量。

参数:

  • codes – 输出编码，大小为 n * M

  • x – 要编码的向量，大小为 n * d

  • n – 向量的数量

  • ils_iters – 迭代局部搜索的迭代次数

void icm_encode_impl(int32_t *codes, const float *x, const float *unaries, std::mt19937 &gen, size_t n, size_t ils_iters, bool verbose) const
void icm_encode_step(int32_t *codes, const float *unaries, const float *binaries, size_t n, size_t n_iters) const
void perturb_codes(int32_t *codes, size_t n, std::mt19937 &gen) const

向编码添加一些扰动

参数:

  • codes – 要扰动的编码，大小为 n * M

  • n – 向量的数量

void perturb_codebooks(float T, const std::vector<float> &stddev, std::mt19937 &gen)

向码本添加一些扰动

参数:

  • T – 模拟退火的温度

  • stddev – 训练数据中每个维度的标准差

void compute_binary_terms(float *binaries) const

计算二元项

参数:

binaries – 二元项，大小为 M * M * K * K

void compute_unary_terms(const float *x, float *unaries, size_t n) const

计算一元项

参数:

  • n – 向量的数量

  • x – 要编码的向量，大小为 n * d

  • unaries – 一元项，大小为 n * M * K

float evaluate(const int32_t *codes, const float *x, size_t n, float *objs = nullptr) const

用于计算重建误差的辅助函数

参数:

  • codes – 编码后的码，大小为 n * M

  • x – 要编码的向量，大小为 n * d

  • n – 向量的数量

  • objs – 如果不为空，则将每个向量的重建误差存储到其中，大小为 n

公共成员

size_t K

每个码本的码的数量

size_t train_iters = 25

训练中的迭代次数

size_t encode_ils_iters = 16

编码中局部搜索的迭代次数

size_t train_ils_iters = 8

训练中局部搜索的迭代次数

size_t icm_iters = 4

icm 中的迭代次数

float p = 0.5f

温度因子

float lambd = 1e-2f

正则化因子

size_t chunk_size = 10000

一次编码的向量数

int random_seed = 0x12345

随机生成器的种子

size_t nperts = 4

每个码中的扰动数量

如果非 NULL，则使用此编码器进行编码（对象拥有）

lsq::IcmEncoderFactory *icm_encoder_factory = nullptr
bool update_codebooks_with_double = true
namespace lsq
struct IcmEncoder

由 faiss::gpu::GpuIcmEncoder 继承

公共函数

explicit IcmEncoder(const LocalSearchQuantizer *lsq)
inline virtual ~IcmEncoder()

计算二元项

virtual void set_binary_term()
virtual void encode(int32_t *codes, const float *x, std::mt19937 &gen, size_t n, size_t ils_iters) const

给定码本，对向量进行编码

参数:

  • codes – 输出编码，大小为 n * M

  • x – 要编码的向量，大小为 n * d

  • gen – 随机数生成器

  • n – 向量的数量

  • ils_iters – 迭代局部搜索的迭代次数

公共成员

std::vector<float> binaries
bool verbose
const LocalSearchQuantizer *lsq
struct IcmEncoderFactory

被 faiss::gpu::GpuIcmEncoderFactory 继承

公共函数

inline virtual IcmEncoder *get(const LocalSearchQuantizer *lsq)
inline virtual ~IcmEncoderFactory()
struct LSQTimer
#include <LocalSearchQuantizer.h>

一个辅助结构体，用于统计训练期间的耗时。它不是线程安全的。

公共函数

inline LSQTimer()
double get(const std::string &name)
void add(const std::string &name, double delta)
void reset()

公共成员

std::unordered_map<std::string, double> t
struct LSQTimerScope

公共函数

LSQTimerScope(LSQTimer *timer, std::string name)
void finish()
~LSQTimerScope()

公共成员

double t0
LSQTimer *timer
std::string name
bool finished