上一篇介紹REALM的文章有幾個遺憾。一個是今年ICML審稿并沒有結束，所以標題不太好；二是對文中提到的Maximum Inner Product Search沒有作充分的介紹。發出去的標題已經沒法改了，這篇文章介紹一下MIPS和最近鄰搜索問題，以及兩個相關的算法。

提示：長公式可以左右滑動查看哦

問題定義

MIPS的定義很簡單，假設你有一堆d維向量，組成集合X，現在輸入了一個同樣維度的查詢向量q (query)，請從X中找出一個p，使得p和q的點積在集合X是最大的。用公式寫出來就是

這個問題和最近鄰問題很像，最近鄰問題只要把上面的定義改成找一個p使得p和q的距離最小，假設這個距離是歐氏距離，則如果X中的向量模長都一樣，那兩個問題其實是等價的。然而在很多實際場景例如BERT編碼后的句向量、推薦系統里的各種Embedding等，這個約束是不滿足的。
最近鄰搜索其實應用非常廣泛，如圖片檢索、推薦系統、問答等等。以問答匹配為例，雖然我們可以用BERT這樣的大型模型獲得很好的準確度，但如果用BERT直接對語料庫中的所有問題進行計算，將耗費大量的時間。所以可以先用關鍵詞檢索或者向量檢索從語料庫里召回一些候選語料后再做高精度匹配。

樸素的算法

對于MIPS問題，一個直觀的蠻力算法就是計算出所有相關的內積，然后將內積排序，找到最大的那個。對于最近鄰問題其實也類似，即使X中向量模長各不相同，也可以提前計算出來，并不會增加排序的時間復雜度。

內積的計算可以轉換成一個矩陣乘法，在CPU和GPU上都有大量的高效實現。當X中有N個向量時，時間復雜度是O(Nd)，當N不大的時候是可以接受的，但是通常在工業界的大規模系統中，X的規模往往很大，樸素算法就顯得力不從心。

Locality-sensitive hashing

對于某些距離度量（例如歐式距離，cosine距離）下的最近鄰問題，可以使用LSH算法來解決。LSH的思路就像下圖示意的那樣，用hash函數把高維空間的點分到幾個桶里去，從而減少距離的計算量。

跟普通的哈希函數不同，這個哈希函數是Locality-sensitive的。具體地說就是它有一個神奇的特點：在空間中離得近的點被分到同一個桶的概率大，離得遠的點則大概率被分到不同的桶里去。或者說對于兩個點x和y，他們被哈希函數分到同一個桶的概率隨著距離的增大單調遞減。

這樣在查詢的時候，只需要精確地比較和查詢向量q處在同一個桶里的那些x。如果桶足夠多，那便可以將N大大降低，從而提高查詢速度。但需要注意的是，LSH是一個近似算法，有可能產生桶內的向量其實都不是最優解的情況，不同哈希函數發生這種情況的概率都不一樣，也是作為評價哈希函數好壞的重要依據之一，對這部分感興趣的朋友可以讀參考文獻。

下面舉一個具體的例子來解釋一下LSH。假設某個最近鄰問題考慮的距離度量是cosine距離，有一個滿足要求的LSH函數（變換），稱為Random Projection。

如上圖所示，其過程很好理解：

隨機取一個空間中的超平面將空間分為兩半，X內位于某一半的點標為0，其他標為1；

重復第一步K次。

完成之后，X中的每個點便得到了一個由K個0，1組成的表示（signature）。例如重復了K=32次，那每個點都被分到了一個用一個int32類型的整數編號的桶里。如果這些點在空間中分布足夠均勻，那么我們將可以期望每個桶里只有N/2^K個點，當K～logN，則查詢的時間復雜度就約為O(dlogN)。

整個過程構建出了一張哈希表，由于LSH可能會錯過最優解，一個可行的增強魯棒性的做法是用同樣的方法多構造幾張哈希表，借助隨機的力量來降低犯錯的概率。參考閱讀[3]是一個講解LSH的視頻，可謂短小精悍，直觀易懂，推薦給大家。

LSH看上去相對于樸素算法確實前進了一大步。但別高興得太早，要達到O(dlogN)的效果必須服從那個很強的假設。而點在空間中分布足夠均勻往往是不太現實的。除此之外，一個LSH只能適用于某些距離度量，對于MIPS，找不到符合要求的LSH。

Asymmetric LSH(ALSH)

[2]里證明了找不到可用于MIPS問題的LSH函數，但他們發現對LSH稍作點改動即可將MIPS問題轉變為歐式距離下的最近鄰搜索問題。改動的關鍵就在于Asymmetric這個詞。在LSH算法中，對查詢向量q和X中的向量做的是同樣（對稱）的變換，而在ALSH中作者對兩者使用了不同（非對稱）的變換。

簡單起見，假設查詢向量q的模長是1。對于X，先做一個放縮變換使得X中所有向量x的所有元素都小于1。然后對X中的向量進行變換P(x)，對查詢向量q做變換Q(x)，P和Q的定義如下：

可以發現，P和Q雖然變換不同，但都會使輸入向量增加m維。進一步觀察可以得到繼而推導出下面這個關鍵的公式上式右邊的第一項是個常數，第三項由于x的每個值都小于1，所以是隨著m的增大以指數的指數的速度趨近于0，因此也就剩下了第二項。第二項包含了我們要求的內積項，而求最大內積就是求最小距離，原問題便轉化成了P(x)和Q(q)間的歐氏距離最近鄰搜索問題。而P(x)和Q(q)仍然是向量，在歐氏距離下是能夠找到LSH函數快速求出最近鄰問題的近似解的。

上面就是ALSH的主要過程，它的核心技巧是通過“非對稱變換”構造向量從而消除x向量模長對MIPS結果的影響。

前面為了簡單起見引入了一個查詢向量q必須是單位向量的約束，[2]中介紹了怎么進一步加強這個變換來消除這個約束，在此就不贅述了。

后記

LSH和ALSH的理論證明部分比較復雜，本文可能會有錯誤的地方。由于目前我們的粉絲數太少，還無法在文章留言，有什么意見和建議大家可以直接到公眾號中給我們發消息。

除了本文介紹的LSH及其變種，在解決向量檢索問題上還有很多有趣的算法和厲害的算法包，我們會在后續的文章中繼續介紹。在今年一月份的時候Google發了一篇叫《Reformer: The Efficient Transformer》的文章，就用到了LSH的算法，近期我們可能也會乘熱打鐵介紹一下這篇文章。

參考閱讀

國內向量檢索引擎Milvus

https://milvus.io/cn/docs/about_milvus/index_method.md

ALSH論文?

https://papers.nips.cc/paper/5329-asymmetric-lsh-alsh-for-sublinear-time-maximum-inner-product-search-mips.pdf

LSH講解視頻（墻外）

https://www.youtube.com/watch?v=Arni-zkqMBA&list=PLZKSpah6NB5LbjWM9JoOSbZZffwCUwJdh&index=8

LSH ppt（Stanford）

https://graphics.stanford.edu/courses/cs468-06-fall/Slides/aneesh-michael.pdf

Reformer: The Efficient Transformer

https://arxiv.org/pdf/2001.04451.pdf

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習在線手冊深度學習在線手冊AI基礎下載（pdf更新到25集）備注：加入本站微信群或者qq群，請回復“加群”獲取一折本站知識星球優惠券，請回復“知識星球”喜歡文章，點個在看

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的REALM后续：最近邻搜索，MIPS，LSH和ALSH的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。