演算法工程師應該對youtube那篇“Deep Neural Networks for YouTube Recommendations”印象深刻，文中的演算法架構思想固然很有影響力，而核心的高維向量相似性搜尋看上去也是相當神奇。
facebook的faiss可以說是相似向量搜尋的標杆，而它背後的演算法就是乘積量化。正好我也接觸過一些低維空間的類似問題，所以就寫來記錄一下。
本篇從一維向量搜尋開始，然後說一說二維，最後推廣到高維，並在這個過程中逐漸說明遇到的問題，以便更好的理解乘積量化的原理。
一維向量搜尋介紹
先看這個問題：假設有一個已知的無序的陣列A，再給定某個值x，現在要查詢A中距離x最近的值。這個應該很簡單，直接遍歷一遍就可以了。現在再加一個條件：假設有一系統的值x1，x2，x3。。。，查詢它們距離A中最近的值。這個似乎也還好，因為A是已知的不變的，所以可以進行排序預處理，然後對每個x值二分查詢排序後的A即可。這個辦法也很直接，但和乘積量化還不沾邊。
二維向量搜尋介紹
把一維的推廣到二維就是：給定已知的點集合P={（x1， y1）， （x2， y2）， （x3， y3）。。。（xn， yn）}，然後隨機給一個點p（x， y），找點集P中距離點p最近的點。這個問題似乎也不算多難，geohash，kdtree和四叉樹等很多辦法都可以解決它。但其實和這些“大殺器”相比，還有個相對容易實現但同樣高效的辦法：畫方格。就是說先將連續的座標值“量化”或“離散”成整數值並進行編碼建立倒排，查詢時先將點p（x，y）透過引數進行量化，再查詢倒排即可找到距離最近點。當量化後落到某方格中的點不會太多時，這個過程就非常高效。
再回頭看看一維，直接就有這樣的新解法：將一維陣列量化成多個“線段”並建倒排，對查詢值也同樣地量化再查詢倒排。
向量量化
量化這個詞，我最早在通訊原理裡遇到過，本質就是傳送端對連續值訊號進行離散化並編碼，接收端再從離散值重建連續值訊號。量化是有損的過程。量化方式有很多種，畫方格的只是一個特例。有人已經證明近似最優的量化方式是k-means聚類量化，並以質心表示量化結果，這一過程相當於用Voronoi單元分割向量空間。所謂Voronoi單元就是單元內任意一點到其質心的距離都小於該點到鄰近Voronoi單元的質心的距離。乘積量化就用到了k-means量化。
“畫方格”和k-means量化的一個區別是，畫方格的量化結果正好和編碼重合，這一特點使它用起來很方便，而k-means量化結果仍然是連續值的座標，查詢時就需要遍歷操作。另一個區別是，“畫方格”是在各個維度上獨立量化，而k-means是將向量做為整體進行量化。
高維向量的量化介紹
畫方格量化在高維向量空間會遇到問題：假設每維量化成k個值，D維空間量化後的可能值有k的D次方格。想像下k=2，D=128吧。這完全沒法實現。k-means量化的問題，一是記憶體佔用比較高。D維向量k個質心時空間佔用是
kD
。二是量化和查詢過程都比較耗時。後面的量化就
專指
k-means量化了。
乘積量化
乘積量化的思路是把高維向量分割成多段低維向量，再各個量化。比如，D維高維向量分成m段，每段維度為：D*=D/m
每段單獨用q量化：
這一步其實只解決了記憶體的問題，即用分段後質心（數量較少）的乘積表示未分段時的質心（數量較大）。假設未分段時量化質心數量為k，每個分段量化後的質心數量都為k*，則m段共可表示的質心數量為k*的m次方，它們之間關係是：
現在的
空間佔用
是
相比上面得出的kD減少很多。
向量的距離度量介紹
在查詢時有兩種度量查詢向量與質心距離的方式，一種對查詢向量x進行量化，叫做SDC（Symmetric distance computation），另一種不對x量化，叫ADC（Asymmetric distance computa）。一般情況下ADC效果較好。
從向量中對資料進行“非暴力”查詢
乘積量化有效地降低空間複雜度，查詢的時間複雜度只有一些降低，為
O(nm)
，其中n為輸入資料量。這雖然不是暴力查詢，但複雜度仍然很高。最佳化時間複雜度的辦法是使用倒排索引：先用一個“粗粒度的量化器”q（c）對資料進行量化，質心作為倒排的key，聚類到該質心的向量串成連結串列作為value。這樣就能將查詢過程聚焦到一小部分向量上。這被叫做IVFADC（an inverted file system with the asymmetric distance computation）。具體在value的處理上，並不是直接量化原向量，而是去量化一個殘差向量。
其中y為原向量，q為粗粒度量化器。直觀上，r（y）比y小，量化效果應該會好些——-相同量化粒度的情況下，數值範圍小的精度應該更高。
可以用下圖表示上面的思路。其中c表示粗粒度量化質心，rpq（residual product quantizer）表示對殘差的量化，箭頭表示對映關係。
這樣在查詢時就先對查詢向量x進行粗粒度量化，再去相應倒排裡搜尋最近鄰。假設倒排能均衡地分割n條資料，那每個倒排長度約為：n/kc，kc為粗粒度質心資料，所以總的時間複雜度為
O(n/kc*m)
，相比O（nm）有很大提高。
還要補充，粗粒度量化可能將查詢向量x的最近點聚類到相鄰類中，所以在查詢時一般要用x的幾個粗粒度鄰近質心同時查詢。
最後還有個問題：對查詢向量x的粗粒度量化的耗時。因為按說也要遍歷各粗粒度質心才能拿到最近的幾個質心，這樣當質心數量較多時光這一步就挺耗時的。原文中的解釋是，一是有層次型量化器可以高效地完成x量化；二是當粗質心較多時，相應地倒排連結串列長度就減少。所以對大資料集，粗質心越多，IVFADC效能越好，而對小資料集，直接用ADC就好。
總結
總的來看，faiss背後的原理就關鍵的兩點：
1。用乘積量化減少記憶體。
2。用倒排提高效能。
海量資料用simhash去重和這個問題應該是類似的。
補充個問題
一維、二維最近鄰查詢大家遇到的比較多，尤其二維的，比如在地圖上查詢離定位最近的廁所。之前工作中還有個相關的問題，歡迎思考：假設用矩形表示地圖上的大量景區，現在在大量的定位點傳送過來，要求找到落到每個景區的那些點。如果覺得簡單，那把矩形換成多邊形再試試。
參考文獻：
1。 Product quantization for nearest neighbor search
2。http：//vividfree。github。io/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/2017/08/05/understanding-product-quantization
想獲取更多內容，請關注
海
資料實驗室公眾號。
本期分享到這裡，我們會每天更新內容，咱們下期再見，期待您的再次光臨。有什麼建議，比如想了解的知識、內容中的問題、想要的資料、下次分享的內容、學習遇到的問題等，請在下方留言。如果喜歡請關注。
