之前在業務中應用了許多Faiss，也看了幾篇關於Faiss的論文，簡單記錄下Faiss的一些屬性和應用。Faiss是Facebook的AI團隊開源的一套用於做聚類或者相似性搜索的軟件庫，底層是用C++實現。Faiss因為超級優越的性能，被廣泛應用於推薦相關的業務當中。接下來分Faiss在推薦業務應用和Faiss的基本原理兩部分進行介紹。
Faiss在推薦業務中的應用
在我的認知裡，基本上50%以上的手機APP的推薦業務會應用到Faiss服務，可見應用之廣。那Faiss究竟是在哪個模塊使用呢，通過下方這個圖給大家介紹：
大家都知道推薦業務包含排序和召回兩個模塊，Faiss比較多的應用在召回模塊。召回業務中有很多是向量生成類的算法，比如Graph Embedding、ALS Embedding、FM Embedding等。ALS就是經典的矩陣分解算法，它可以將User和Item的行為數據利用矩陣分解的方式生成User向量和Item向量，這些向量分別代表User和Item的屬性（工科研究生矩陣論課程學過矩陣分解，不懂的同學要補課了）。
當我們拿到了User和Item的向量，只要計算出哪些Item和User的向量距離較短（最簡單的解法是算歐式距離），就可以得出User偏愛的Item。但是當User和Item的數量巨大的時候，設想下某短視頻平臺，每天有上百萬User登錄，有存量的上千萬的Item短視頻，怎麼能快速的計算出向量距離，就成了一個亟待解決的技術難點，因為推薦業務的召回模塊需要在50ms以內拿到結果。這也就是Faiss的價值所在，Faiss幾乎可以在10ms內完成百萬*百萬以上的向量距離計算，它是怎麼實現的呢？
Faiss原理
向量計算是一個最經典的時空優化問題，在查詢過程中建立更多地索引固然可以提升查詢速度，但是卻有佔據了存儲空間，我們希望系統可以即減少索引又能提升查詢性能。
為了得到時間和空間的最優，Faiss使用了PCA和PQ兩個手段進行向量壓縮和編碼，當然還有其它的一些優化手段，但是PCA和PQ是最為核心的。
PCA降維
PCA是一種降維手段，簡單理解就是將高維向量變為低圍，這樣就可以有效的節省存儲空間，PCA我之前介紹過，今天就不多說了。有興趣可以看下我的博客：CSDN-李博garvin
大家看下圖綠色的點，它其實是二維的，既有縱向座標的屬性也有橫向座標的屬性，可以用PCA方式讓它變為一維，這樣就成了紅色這樣的點簇、
PQ編碼
Product quantization(乘積量化PQ)，PQ是一種建立索引的方式。這裡參考這篇文章為大家說明：http://www.fabwrite.com/productquantization
假設原始向量是1024維，可以把它拆解成8個子向量，每個子向量128維。
然後對每個字向量的全部50k數據分別作Kmeans計算，假設設置Kmeans的K為256。就得到了8組，每組256箇中心點這樣的碼本，這個碼本可以對50k個向量進行編碼。
也就是說把編碼從原始的1024個向量需要32bit，壓縮成了只需要log(256)，8位來表示。這樣每個向量的索引就減少了許多。
參考文檔（衷心感謝以下老師們的貢獻）：
（1）http://www.fabwrite.com/productquantization
（2）https://github.com/facebookresearch/faiss
閱讀更多 比特到商業智能 的文章
