IVF

Reading time ~2 minutes

faiss中有IVF的概念。其实就是inverted file (IVF)。它在2003的《Video Google: A Text Retrieval Approach to Object Matching in Videos》中提出。我们来看下,该paper有两段提及,我们来看下:

一、

文本检索系统通常需要采用一些标准steps。文档首先被解析成words。接着,words通过它们的stems来表示,例如:“walk”、”walking”、”walks”会使用stem ‘walk’来表示。第三,会使用stop list来拒绝常用words,比如:”the”、”an”,它们很常见。剩余words接着会被分配一个唯一的id,每个document会通过一个vector来表示,该vector的components由该文档中所包含的words的词频组成。除了components会以多种方式加权外,在google的case中,一个web page的weighting取决于web pages链接到特定页的数目。上述所有steps都在实际检索前完成,在语料中的所有文档会表示成vectors集合,通过一个inverted file进行组织来更高效的检索。一个inverted file的结构类似于一个理想的book index。在corpus中每个word都有一个entry,它会跟一个该word出现的所有文档(以及在该文档中的位置)的list。

一个text会通过计算词频向量进行检索,并返回最近向量(通过角度)的文档。

二、目标检索(object retrieval)

实现-使用inverted files:在一个经典的文件结构中,所有words会存储在它们出现的文档中。一个inverted file结构,会为每个word生成一个entry(hit list),并存储在所有文档中该word的出现次数。在我们的case中,inverted file会为每个可视化的word生成一个entry,它会存储所有matches,例如:在所有帧中相同word的出现次数。document vector是非常稀疏的,使用一个inverted file可以使得检索非常快。在2GHz的pentium上使用matlab实现,查询一个4k frames的database只需要0.1秒。

三、faiss IVF

上面提到的都是IR中的inverted file。关于faiss IVF,Chris McCormick在它的blog中有提到,我们可以看下:

Inverted File Index(IVF) 是pre-filtering技术,以便你无需对所有vectors做exhaustive search。实现相当简单:首先,你使用聚类(比如:kmeans)将数据集聚类生成较大数目(比如:100个)的数据分区(partitions)。接着,在query时,你会将你的query vector与partition centroids进行对比,(例如:找到10个最近的聚类),接着你只在这些分区上对vectors进行搜索

在IR中,”inverted index”指的是文本搜索索引,它会将词汇表中的每个词映射到数据文档中的所有位置。看起来有点像textbook的索引,将words映射到page numbers,因而称为inverted index。

然而,在我们的上下文中,该技术的意思是,使用k-means聚类将数据集进行划分,以便你可以重定义你的搜索(只需搜索部分分区,忽略其它)。

在构建index时,使用聚类将数据集聚到多个partitions上。在dataset中的每个vector会属于这些clusters/partitions的其中之一。对于每个partition,你都具有一个属于它的所有vectors的list(被称为:inverted file lists)。你具有关于所有这些partition centroids的一个matrix,它会被用于找出哪些partitions会进行search。

按这种方式划分数据集并不完美,因为如果一个query vector落到离它最近cluster的外面,那么它的最近邻很可能停留在多个附近的cluster上。解决该问题的简单方法是,搜索多个partitions。搜索多个附近的partitions很明显会花费更多时间,但它会给出更好的accuracy。

在搜索时,你可以比较你的query vector与所有partition centroids来找到离它最近的partition。可以配置多少个。一旦你发现了这些centroids,你只需从这些partitions中选择dataset vectors,使用product quantizer来进行KNN search。

需要注意一些术语:

  • verb “probe”指的是,选择partitions进行search。代码中你会看到index参数”nprobe”意味着:有多少partitions进行probe。
  • Faiss的作者喜欢使用术语:Voronoi cells(而非“dataset partitions”)。一个Voronoi cell指的是,属于一个cluster的space区域。也就是说,它会包含在space中的所有points(vector与某个cluster的centroid会比其它clusters更接近)。

4.faiss doc上的解释

Inverted list objects & scanners

faiss实现了two low-level APIs来泛化inverted list存储。这对于以key-value数据库存储lists很有用。

  • InvertedLists抽象类定义了inverted lists是如何从搜索代码被访问的。任意提供该interface的对象可以被用来保存lists。
  • InvertedListsScanner提供了细粒度的访问,因为scanning function可以在用户提供的id和code tables上被调用

4.1 IndexIVF回顾

IndexIVF类(以及它的子类)可以被被用于Faiss的所有大规模应用中。它会将input vectors聚类成nlist个groups(nlist是IndexIVF的一个field)。在add时,一个vector会被分配一个groups。在search时,与query vector最相似的groups会被识别出,并进行穷举扫描(exhaustively scan)。

因而,IndexIVF具有两个components:

  • quantizer(也称为:coarse quantizer)index。给定一个vector,quantizer index的search function会返回该vector所属的group。当使用nprobe>1的结果进行search时,它会返回与query vector最接近的nprobe个groups(nprobe是IndexIVF的一个field)。
  • InvertedLists对象。该object会将一个group id()映射到一个(code, id) pairs序列上.

4.2 InvertedLists对象

  • Codes:指的是一个常量size(code_size)的byte strings。例如,36维的IndexIVFFlat具有的code_size=36 * sizeof(float) = 144 bytes。
  • Ids:64-bit integer(负值是保留的,因此有用位只有63bits)

实际上,codes和ids会以两个独立的arrays返回,因为一些applications只需要其中之一,并且memory alignement是不同的。

4.2.1 search方法

该object有有三个相关的方法:

/// get the size of a list
size_t list_size(size_t list_no);

/// @return codes    size list_size * code_size
const uint8_t * get_codes (size_t list_no);
void release_codes (const uint8_t *codes) const;

/// @return ids      size list_size
const idx_t * get_ids (size_t list_no);
void release_ids (const idx_t *ids) const;

通过get_codes(以及get_ids)获得的指针需要通过release_codes(以及release_ids)来释放。如果你喜欢RAII,InvertedLists::ScopedCodes(以及InvertedLists::ScopedIds)会有用。

有一个额外的prefetch_lists方法,它会通过search方法被用来通知InvertedLists对象:一些inverted lists会在不久被用到。

因此,search过程的调用顺序如下:

search(v) {
    list_nos = quantizer->search(v, nprobe)
    invlists->prefetch(list_nos)
    foreach no in list_nos {
        codes = invlists->get_codes(no)
        // linear scan of codes
        // select most similar codes 
        ids = invlists->get_ids(no)
        // convert list indexes to ids
        invlists->release_ids(ids)
        invlists->release_codes(codes)
    }
}

4.2.2 add()方法

添加vectors需要有对InvertedLists对象的read-write权限。这通过add_entries方法提供。其它方法update_entries和resize被用于扩充(bulk)操作,比如,merging、 splitting、removing elements。

4.3 InvertedLists对象的行为

4.3.1 内存管理

如果own_invlists为true,InvertedLists对象通过IndexIVF的destructor被删除。缺省的,ArrayInvertedLists对象会在IndexIVF实例化时被构建,own_invlists被设置为true。缺省的invlists可以被replace_invlists所替代,用户必须决定所属关系(ownership)。

4.3.2 Threading

只读操作允许多线程访问。一些注释关于并发读写操作。

4.3.3 I/O

InvertedLists对象不需要和index object一起存储。如果不是这样,index object只包含处理外存(external storage)的所需信息。

4.4 Build-in InvertedLists类

InvertedLists类主要考虑可扩展性而设计。然而,在Faiss中有两个InvertedLists classes。

4.4.1 ArrayInvertedLists

这是一个std::vector<std::vector<…> >。这是最简单的in-RAM inverted lists实现,开销很少,add时间很快。它有一个特殊状态(status),因为当一个IndexIVF被构建时它会被自动实例化,因此这些vectors会被马上add。

4.4.2 OnDiskInvertedLists

该inverted list data被存储到磁盘的一个内存映射文件上(memory-mapped file)。会存在一个间接表(indirection table),它将list ids映射到file上的offset。 由于data是memory-mapped,没必要显式地从disk上取数据。然而,prefetch函数很有用,可以用上分布式文件系统的并发读。

有意思的是,通过将IO_FLAG_MMAP flag设置为read_index,一个“normal” IndexIVF可以被加载进一个OnDiskInvertedLists中。这使得它可以加载任意数目的indexes,无需担心是否满足RAM。

4.5 InvertedListScanner对象

Inverted list scanning可以在Faiss之外被控制。这使得没必要实现list访问函数作为回调,这不是惯例。

为了支持它,Faiss提供了:

  • encode_vector函数:它可以将inverted list codes计算成一个array中,用来放到不受faiss管理的inverted lists
  • InvertedListScanner对象:可以通过IndexIVF类获得。它会扫描lists、或计算单个query-to-code distance。

该访问非常low-level,但用户具有对scanning的total control,无需实现像InvertedLists对象的回调。

4.6 Encoding vectors

为了编码vectors,calling code应:

  • 对该vector进行quantize,来寻找要存到哪个inverted list
  • 调用encode_vectors来实际编码它

两个函数会进行batch操作以便提高效率。

以下是一个简化代码,它会将nb vectors存储到xb中,来定制inverted lists:

// size nb
idx_t *list_nos = ... ; 
// find inverted list numbers 
index_ivf.quantizer->assign (nb, xb, list_nos);

// size index->code_size * nb
uint8_t *codes = ...; 
// compute the codes to store
index->encode_vectors (nb, xb, list_nos, codes);

// populate the custom inverted lists 
for (idx_t i = 0; i < nb; i++) {
      idx_t list_no = list_nos[i]; 
      // allocate a new entry in the inverted list list_no
      // get a pointer to the new entry's id and code
      idx_t * id_ptr = ... 
      uint8_t * code_ptr =  ...
      // assume the vectors are numbered sequentially
      *id_ptr = i; 
      memcpy (code_ptr, codes + i * index->code_size, index->code_size);
}

详见test_lowlevel_ivf.cpp (add)

4.7 Searching

为了执行search,存在一些loop levels。

以下是执行query的简化代码。它会查询在index中np个vectors xq。

// size nprobe * nq
float * q_dis =  ...
idx_t *q_lists = ...
// perform quantization manually
index.quantizer->search (nq, xq, nprobe, q_dis, q_lists); 

// get a scanner object
scanner = index.get_InvertedListScanner();

// allocate result arrays (size k * nq), properly initialized
idx_t *I = ...
float *D = ...

// loop over queries
for (idx_t i = 0; i < nq; i++) {
    // set the current query
    scanner->set_query (xq + i * d);

    // loop over inverted lists for this query
    for (int j = 0; j < nprobe; j++) {
        // set the current inverted list
        int list_no = q_lists[i * nprobe + j];
        scanner->set_list (list_no, q_dis[i * nprobe + j]);

        // get the inverted list from somewhere
        long list_size = ...
        idx_t *ids = ....
        uint8_t *codes = ....
        // perform the scan, updating result lists
        scanner->scan_codes (list_size, codes, ids, D + i * k, I + i * k, k); 
   }
   // re-order heap in decreasing order
   maxheap_reorder (k, D + i * k, I + i * k);
}

参考

facebook DLRM介绍

# 介绍facebook在2019在《Deep Learning Recommendation Model forPersonalization and Recommendation Systems》。# 摘要facebook开发了一种SOTA的深度学习推荐模型(DLRM)...… Continue reading

ali reranking模型介绍

Published on October 15, 2019

youtube MMoE排序系统

Published on October 11, 2019