faiss(1)：简介 安装 与 原理
1. 簡介
Faiss是Facebook AI團隊開源的針對聚類和相似性搜索庫，為稠密向量提供高效相似度搜索和聚類，支持十億級別向量的搜索，是目前最為成熟的近似近鄰搜索庫。它包含多種搜索任意大小向量集（備注：向量集大小由RAM內存決定）的算法，以及用于算法評估和參數(shù)調整的支持代碼。Faiss用C++編寫，并提供與Numpy完美銜接的Python接口。除此以外，對一些核心算法提供了GPU實現(xiàn)。
參考論文：https://arxiv.org/pdf/1702.08734.pdf
源碼地址：https://github.com/huaxz1986/faiss
2. Anaconda安裝Faiss
?基于本機環(huán)境，采用了anaconda進行安裝，這也是faiss推薦的方式，facebook研發(fā)團隊也會及時推出faiss的新版本conda安裝包，在conda安裝時會自行安裝所需的libgcc, mkl, numpy模塊。
- Ubuntu安裝anaconda
- anaconda安裝Faiss
mkl全稱Intel Math Kernel Library，提供經(jīng)過高度優(yōu)化和大量線程化處理的數(shù)學例程，面向性能要求極高的科學、工程及金融等領域的應用。MKL是一款商用函數(shù)庫（考慮版權問題，后續(xù)可以替換為OpenBLAS），在Intel CPU上，MKL的性能要遠高于Eigen, OpenBLAS和其性能差距不是太大，但OpenBLAS提供的函數(shù)相對較少，另外OpenBLAS的編譯依賴系統(tǒng)環(huán)境。
3. Faiss原理
- 核心算法的改進
Faiss對一些基礎的算法提供了非常高效的改進：
- Faiss功能流程說明
faiss的主要功能就是相似度搜索。如下圖所示，以圖片搜索為例，所謂相似度搜索，便是在給定的一堆圖片中，尋找出我指定的目標最像的K張圖片，也簡稱為KNN（K近鄰）問題。當然，隨著word2vec、doc2vec、img2vec、video2vec的出現(xiàn)，向量化描述已經(jīng)成為最大的趨勢。這也是Faiss最受歡迎的主要原因，大大提升了Query的效率。
為了解決KNN問題，在工程上需要實現(xiàn)對已有圖庫的存儲，當用戶指定檢索圖片后，需要知道如何從存儲的圖片庫中找到最相似的K張圖片。基于此，可以推測Faiss在應用場景中會逐漸添加數(shù)據(jù)庫查詢的一些功能，例如增改刪查，從上圖來看，Faiss本質上是一個向量（矢量）數(shù)據(jù)庫。
對于數(shù)據(jù)庫來說，時空優(yōu)化是兩個永恒的主題，即在存儲上如何以更少的空間來存儲更多的信息，在搜索上如何以更快的速度來搜索出更準確的信息。如何減少搜索所需的時間？在數(shù)據(jù)庫中很最常見的操作便是加各種索引，把各種加速搜索算法的功能或空間換時間的策略都封裝成各種各樣的索引，以滿足各種不同的引用場景。
3.1 組件原理分析
Faiss中最常用的是索引Index，而后是PCA降維、PQ乘積量化，這里針對Index和PQ進行說明，PCA降維從流程上都可以理解。
- Index原理
Faiss中有兩個基礎索引類Index、IndexBinary，先從類圖進行分析的。?
Faiss還提供了針對不同場景下應用對Index的封裝類：
基礎索引的說明參考：Faiss indexes涉及方法解釋、參數(shù)說明以及推薦試用的工廠方法創(chuàng)建時的標識等。
索引的創(chuàng)建提供了工廠方法，可以通過字符串靈活的創(chuàng)建不同的索引。
// 使用PCA算法將向量降維到32維, 劃分成100個nprobe (搜索空間), 通過PQ算法將每個向量壓縮成8bit index = faiss.index_factory(d,"PCA32,IVF100,PQ8 ")- 索引說明
索引id是基于PQ量化及Faiss創(chuàng)建不同的索引時選擇的量化器而來，可能會稍有偏差，不影響對Faiss的使用操作。 ? ? ?
默認情況，Faiss會為每個輸入的向量記錄一個次序id，也可以為向量指定任意我們需要的id。部分索引類有add_with_ids方法，可以為每個向量對應一個64-bit的id，搜索的時候返回此id。
import numpy as np import faiss# 構造數(shù)據(jù) import time d = 64 # dimension nb = 1000000 # database size nq = 1000000 # 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.# 為向量集構建IndexFlatL2索引，執(zhí)行強力L2距離搜索 #此處索引是按照默認方式，即faiss給的次序id為主 index = faiss.IndexFlatL2(d) # IndexFlatL2不支持add_with_ids方法，需要借助IndexIDMap進行映射 # id設定為6位數(shù)整數(shù)，默認id從0開始，將其設置從100000開始 # ids = np.arange(100000, 200000) # index2 = faiss.IndexIDMap(index) # index2.add_with_ids(xb, ids) # # print(index2.is_trained) # index.add(xb) # add vectors to the index # print(index2.ntotal) # k = 4 # we want to see 4 nearest neighbors # D, I = index2.search(xb[:5], k) # sanity check # print(I) # 向量索引位置 # print(D) # 相似度矩陣print(index.is_trained) index.add(xb) # add vectors to the index print(index.ntotal) k = 4 # we want to see 4 nearest neighbors # D, I = index.search(xb[:5], k) # sanity check # # print(xb[:5]) # print(I) # 向量索引位置 # print(D) # 相似度矩陣- 索引選擇
關注返回精度，可以使用IndexFlatL2，該索引能確保返回精確結果。一般將其作為baseline與其他索引方式對比，以便在精度和時間開銷之間做權衡。不支持add_with_ids，如果需要，可以用“IDMap”給予任意定義id。
關注內存開銷，可以使用“..., Flat“的索引，"..."是聚類操作，聚類之后將每個向量映射到相應的bucket。該索引類型并不會保存壓縮之后的數(shù)據(jù)，而是保存原始數(shù)據(jù)，所以內存開銷與原始數(shù)據(jù)一致。通過nprobe參數(shù)控制速度/精度。對內存開銷比較關心的話，可以在聚類的基礎上使用PQ量化進行處理。
- 檢索數(shù)據(jù)恢復
Faiss檢索返回的是數(shù)據(jù)的索引及數(shù)據(jù)的計算距離，在檢索獲得的索引后需要根據(jù)索引將原始數(shù)據(jù)取出。 ? ? ?
條條恢復。 給定id，可以使用reconstruct進行單條取出數(shù)據(jù)；
批量恢復。使用reconstruct_n方法從index中回批量復出原始向量
上述方法支持IndexFlat, IndexIVFFlat, IndexIVFPQ等幾類索引類型。
- PCA降維
?PCA通過數(shù)據(jù)壓縮減少內存或者硬盤的使用以及數(shù)據(jù)降維加快機器學習的速度。從數(shù)據(jù)存儲的角度，圖片處理中通過PCA可以將圖片從高維空間（p維）轉換到低維空間（q維, 其中p > q ），其具體操作便是是將高維空間中的圖片向量（n*p）乘以一個轉換矩陣（p*q），得到一個低維空間中的向量（n*q）。
為了使得在整個降維的過程中信息丟失最少，我們需要對待轉換圖片進行分析計算得到相應的轉換矩陣（p*q）。也就是說這個降維中乘以的轉換矩陣是與待轉換圖片息息相關的。
對于Faiss，假設期望使用PCA預處理來減少Index中的存儲空間，那在整個處理流程中，除了輸入搜索圖庫外，我必須多輸入一個轉換矩陣，但是這個轉換矩陣是與圖庫息息相關的，是可以由圖庫數(shù)據(jù)計算出來的。如果把這個轉換矩陣看成一個參數(shù)的話，可以發(fā)現(xiàn)，在Faiss的一些預處理中，我們會引入一些參數(shù)，這些參數(shù)又無法一開始由人工來指定，只能通過訓練出來，所以Index中需要有這樣的一個train() 函數(shù)來為這種參數(shù)的訓練提供輸入訓練樣本的接口。
- Product quantization(乘積量化PQ)
此處Facebook引用了2011年的經(jīng)典論文：Product Quantization for Nearest Neighbor Search
PQ算法可以理解為首先把原始的向量空間分解為m個低維向量空間的笛卡爾積，并對分解得到的低維向量空間分別做量化。即是把原始D維向量（比如D=128）分成m組（比如m=4），每組就是D?=D/m維的子向量（比如D?=D/m=128/4=32），各自用kmeans算法學習到一個碼本，然后這些碼本的笛卡爾積就是原始D維向量對應的碼本。用qj表示第j組子向量，用Cj表示其對應學習到的碼本，那么原始D維向量對應的碼本就是C=C1×C2×…×Cm。用k?表示子向量的聚類中心點數(shù)或者說碼本大小，那么原始D維向量對應的聚類中心點數(shù)或者說碼本大小就是k=(k?)m。
與50位技術專家面對面20年技術見證，附贈技術全景圖總結
以上是生活随笔為你收集整理的faiss(1)：简介 安装 与 原理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 真诚地希望你耐心的把它看完
- 下一篇： [CB]将窗体从属于主窗体