淘寶推薦、視頻搜索背后的檢索技術竟是它！深度揭秘達摩院向量檢索引擎Proxima

量子位的朋友們 2021-03-09 17:48:24 來源：量子位

本文作者
大沙，阿里巴巴達摩院機器智能實驗室 資深技術專家
鶴沖，阿里巴巴達摩院機器智能實驗室 資深技術專家

人工智能，簡稱 AI，是計算機發明時就存在的一個技術領域。它的一大核心特點就是可以類人腦地輔助人類工作。其通過一系列數學的方法，如概率論、統計、線性代數等，分析和設計出能讓計算機自動學習的算法。

如下圖所示，人工智能算法可以對物理世界的人/物/場景所產生各種非結構化數據（如語音、圖片、視頻，語言文字、行為等）進行抽象，變成多維的向量。這些向量如同數學空間中的坐標，標識著各個實體和實體關系。我們一般將非結構化數據變成向量的過程稱為 Embedding，而非結構化檢索則是對這些生成的向量進行檢索，從而找到相應實體的過程。

非結構化檢索本質是向量檢索技術，其主要的應用領域如人臉識別、推薦系統、圖片搜索、視頻指紋、語音處理、自然語言處理、文件搜索等。隨著 AI 技術的廣泛應用，以及數據規模的不斷增長，向量檢索也逐漸成了 AI 技術鏈路中不可或缺的一環，更是對傳統搜索技術的補充，并且具備多模態搜索的能力。

一 業務場景

1 語音/圖像/視頻檢索

向量檢索的第一大類應用就是對語音、圖像、視頻這些人類所接觸到的，也最為常見的非結構化數據的檢索。傳統的檢索引擎只是對這些多媒體的名稱和描述進行了索引，而并沒有嘗試對這些非結構數據的內容進行理解和建立索引，因此傳統引擎的檢索結果具有非常大的局限性。

隨著人工智能的發展，AI 的能力使得我們可以快速且成本較低地對這些非結構化數據進行理解，這樣就使得對這些非結構化的數據內容進行直接檢索成為了可能。這其中，很重要的一環就是向量檢索。

如下圖所示，以圖片搜索為例，我們先以離線的方式對所有歷史圖片進行機器學習分析，將每一幅圖片（或者圖片里分割出來的人物）抽象成高維向量特征，然后將所有特征構建成高效的向量索引，當一個新查詢（圖片）來的時候，我們用同樣的機器學習方法對其進行分析并產出一個表征向量，然后用這個向量在之前構建的向量索引中查找出最相似的結果，這樣就完成了一次以圖片內容為基礎的圖像檢索。

2 文本檢索

向量檢索其實很早就已經在常見的全文檢索中用到了。我們這里用地址檢索為例來簡單介紹下向量檢索技術在文本檢索中的應用情況和價值。

如下圖左邊的例子，我們想在標準地址庫中搜索“浙一醫院”（而標準地址庫中恰恰又沒有“浙一”這個關鍵詞，“浙一醫院”的標準地址是“浙江大學醫學院附屬第一醫院”），如果我們只使用文本分詞（“浙一”和“醫院”），在標準地址庫中是不會找到相關結果的（因為“浙一”這個地址不存在）。但是我們如果能夠利用對人們歷史語言，甚至之前的點擊關聯進行分析，建立起語義相關性的模型，把所有的地址都用高維特征來表達，那么“浙一醫院”和“浙江大學醫學院附屬第一醫院”的相似度可能會非常高，因此可以被檢索出來。

另外一個例子，如下圖右邊所示，同樣是地址查詢，如果我們想在標準地址庫中搜索“杭州阿里巴巴”的地址，在僅使用文本召回的時候，幾乎沒辦法找到相似的結果，但是我們如果通過對海量用戶的點擊行為進行分析，將點擊行為加上地址文本信息合并形成高維向量，這樣在檢索的時候就可以天然的將點擊率高的地址召回并排列在前面。

3 搜索/推薦/廣告

在電商領域的搜索/推薦/廣告業務場景中，常見的需求是找到相似的同款商品和推薦給用戶感興趣的商品，這種需求絕大多數都是采用商品協同和用戶協同的策略來完成的。新一代的搜索推薦系統吸納了深度學習的 Embedding 的能力， 通過諸如 Item-Item (i2i)、User-Item (u2i)、User-User-Item (u2u2i)、User2Item2Item (u2i2i) 等向量召回的方式實現快速檢索。

算法工程師通過對商品的相似和相關關系，以及被瀏覽和被購買的用戶行為的抽象，將它們表征成高維向量特征并存儲在向量引擎中。這樣，當我們需要找一個商品的相似商品（i2i）時，就可以高效快捷地從向量引擎中檢索出來。

4 幾乎覆蓋了所有的 AI 場景

其實，向量檢索的應用場景遠不止上面提到的這些類型。如下圖所示，它幾乎覆蓋了大部分的可以應用AI的業務場景。

二 向量檢索的現狀和挑戰

1 繁多的檢索算法

向量檢索本質為了求解 KNN 和 RNN 兩個問題，KNN（K-Nearest Neighbor）是查找離查詢點最近的 K 個點，而 RNN (Radius Nearest Neighbor) 查找查詢點某半徑范圍內的所有點或 N 個點。在涉及到大數據量的情況下，百分之百準確求解 KNN 或 RNN 問題的計算成本較高，于是引入了求近似性解的方法，因此大數據量檢索實際要解決的是 ANN（Approximate Nearest Neighbor）的問題。

為求解 ANN 的問題，業內提出了不少的檢索算法。常用的算法，最早可以溯源到 1975 年提出的 KD-Tree，其基于歐式空間，采用多維二叉樹數據結構解決 ANN 檢索問題。20 世紀 80 年代末，產生了空間編碼和哈希的思想，主要以分形曲線和局部敏感哈希為代表。分形曲線和局部敏感哈希屬于空間編碼和轉換的思想，類似思想的算法還有 Product Quantization (PQ) 等，這些量化算法將高維問題映射到低維進行求解，從而提高檢索效率。21 世紀初，采用鄰居圖解決 ANN 問題的思想也開始萌芽，鄰居圖主要基于“鄰居的鄰居可能也是鄰居”的假設，預先建立數據集中所有點的鄰居關系，形成具有一定特性的鄰居圖，檢索時在圖上進行游走遍歷，最后收斂得到結果。

向量檢索的算法繁多且缺乏通用性，應對不同數據維度和分布有不同算法，但總體可歸為三類思想：空間劃分法、空間編碼和轉換法、以及鄰居圖法。空間劃分法以 KD-Tree、聚類檢索為代表，檢索時快速定位到這些小集合，從而減少需要掃描的數據點的量，提高檢索效率。空間編碼和轉換法，如 p-Stable LSH、PQ 等方法，將數據集重新編碼或變換，映射到更小的數據空間，從而減少掃描的數據點的計算量。鄰居圖法，如 HNSW、SPTAG、ONNG 等，通過預先建立關系圖的方法，去加快檢索時的收斂速度，減少需要掃描的數據點的量，以提高檢索效率。

2 面臨的技術挑戰

向量檢索在發展過程中，也涌現出了一些優秀的開源作品，如 FLANN、Faiss 等。這些作品對業內一些常用和有效的 ANN 算法進行了統一實現和優化，通過運行庫的方式，形成一些工程化的檢索方案。基于這些運行庫和改進，業內也產生了一些服務化的工程引擎，如 milvus、vearch 等。

雖然向量檢索發展多年，并逐漸成為非結構化檢索的主流方法，但仍存在了不少的技術挑戰和問題。

超大規模索引的精度和性能

源于非結構化數據的繁多而復雜，向量檢索天生便是用于應對這種大規模的數據檢索，但面對億級，甚至十億級以上的場景，許多檢索算法仍面臨了挑戰，工程實現也存在著一些問題，要么構建成本巨大，要么檢索效率低下。

另外，維數的增加也造成了一些向量檢索方法的效率下降，在高維空間下華而不實，同時工程上也增加了數據計算和存儲成本。其次，算法上缺乏完全通用性，無法對數據實現泛一致性檢索，即任何數據分布上，檢索算法都是有效的。

目前，業內在處理高維十億級別的數據時仍顯得力不從心，多采用多片索引分別檢索合并的方法，增加了實際計算成本。

分布式構建和檢索

向量檢索目前多通過數據分片的方式實現水平擴展，然而過多的分片容易造成計算量的上升，從而導致檢索效率的下降。在分布式方面，仍存在向量索引快速合并算法的難題，這便導致了數據一旦分片之后，無法很好套用 Map-Reduce 計算模型合并成效率更高的索引。

流式索引的在線更新

傳統的檢索方法能很方便的實現增查改刪（CRUD）的操作，向量檢索依賴數據分布和距離度量，部分方法還有數據集訓練的要求，數據點的變更甚至動一發而牽全身。因此，要實現向量索引的從 0 到 1 的全流式構建，并滿足即增即查、即時落盤、索引實時動態更新的要求，對算法和工程仍存在著一些挑戰。

目前，對于非訓練的檢索方法，能較方便的支持全內存索引的在線動態新增和查詢，然而面對即時落盤、內存不足、在線向量動態更新和刪除等要求，操作成本很大，滿足不了實時性。

標簽+向量的聯合檢索

在大多數業務場景下，需要同時滿足標簽檢索條件和相似性檢索的要求，如查詢某些屬性條件組合下相似性的圖片等，我們稱這種檢索為“帶條件的向量檢索”。

目前，業內采用多路歸并的方式，即分別檢索標簽和向量再進行結果合并，雖可以解決部分問題，但多數情況下結果不甚理想。主要原因在于，向量檢索無范圍性，其目標是盡可能保證 TOPK 的準確性，TOPK 很大時，準確性容易下降，造成歸并結果的不準確甚至為空的情況。

復雜的多場景適配

向量檢索是一種通用能力，但目前尚無通用算法可以適配任意場景和數據，就算同一種算法適配不同數據時，也存在參數配置的差異。如對于多層聚類檢索算法，使用什么聚類算法、分多少層、聚多少類、檢索時使用什么樣的收斂閾值，這些在面對不同場景和數據時都是不一樣的。正是因為這些超參調優的存在，大大加大了用戶的使用門檻。

想讓用戶變得更簡單，必然需要考慮場景適配的問題，主要包括數據適配（如：數據規模、數據分布、數據維度等）和需求適配（如：召回率、吞吐、時延、流式、實時性等）兩方面。基于不同的數據分布，通過選擇合適的算法和參數，以滿足實際的業務需求。

三 達摩院向量檢索技術揭秘

Proxima 是阿里巴巴達摩院自研的向量檢索內核。目前，其核心能力廣泛應用于阿里巴巴和螞蟻集團內眾多業務，如淘寶搜索和推薦、螞蟻人臉支付、優酷視頻搜索、阿里媽媽廣告檢索等。同時，Proxima 還深度集成在各式各類的大數據和數據庫產品中，如阿里云 Hologres、搜索引擎 Elastic Search 和 ZSearch、離線引擎 MaxCompute (ODPS) 等，為其提供向量檢索的能力。

Proxima 是通用化的向量檢索工程引擎，實現了對大數據的高性能相似性搜索，支持 ARM64、x86、GPU 等多種硬件平臺，支持嵌入式設備和高性能服務器，從邊緣計算到云計算全面覆蓋，支持單片索引十億級別下高準確率、高性能的索引構建和檢索。

1 核心能力

如上圖所示，Proxima 的主要核心能力有以下幾點：

• 超大規模索引構建和檢索：Proxima 精于工程實現和算法底層優化，引入了復合性的檢索算法，基于有限的構建成本實現了高效率的檢索方法，單片索引可達幾十億的規模。
• 索引水平擴展：Proxima 采用非對等分片的方法實現分布式檢索。對于鄰居圖索引，解決了有限精度下圖索引快速合并的難題，與 Map-Reduce 計算模型可有效進行結合。
• 高維 & 高精度：Proxima 支持多種檢索算法，并對算法做了更深層的抽象，形成算法框架，依據不同數據維度和分布選擇不同算法或算法組合，根據具體場景需求實現精度和性能之間的平衡。
• 流式實時 & 在線更新：Proxima 采用扁平化的索引結構，支持在線大規模向量索引的從 0 到 1 的流式構建，并利用鄰居圖的便利性和數據特點，實現了索引即增即查、即時落盤，以及實時動態更新。
• 標簽+向量檢索：Proxima 在索引算法層實現了“帶條件的向量檢索”方法，解決了傳統多路歸并召回結果不理想的情況，更大程度的滿足了組合檢索的要求。
• 異構計算：Proxima 支持大批量高吞吐的離線檢索加速，同時解決了 GPU 構建鄰居圖索引的難題，另一方面也成功解決了小批量+低延時+高吞吐的資源利用問題，并將其全面應用在淘寶的搜索推薦系統中。
• 高性能和低成本：有限成本下實現最大化性能并滿足業務的需求是向量檢索需要解決的主要問題。Proxima 實現了對多種平臺和硬件的優化，支持云服務器和部分嵌入式設備，通過與分布式調度引擎的結合實現離線數據檢索和訓練，通過扁平化索引和磁盤檢索的方案實現了對冷數據的快速檢索。
• 場景適配：結合超參調優和復合索引等方法，通過對數據采樣和預實驗，Proxima 可以解決一些數據場景智能適配的問題，從而提高系統的自動化能力，以及增強用戶的易用性。

2 業內對比

目前，業內普遍使用的向量檢索庫是 Facebook AI 團隊開源的 Faiss (Facebook AI Similarity Search) 引擎。Faiss 非常優秀，也是不少服務化引擎的基礎核心，但 Faiss 在大規模通用檢索場景方面仍存在一些局限性，如流式實時計算、離線分布式、在線異構加速、標簽&向量聯合檢索、成本控制以及服務化等方面。

例如，針對公開的十億規模的 ANN_SIFT1B 數據集（來源?http://corpus-texmex.irisa.fr），在 Intel(R) Xeon(R) Platinum 8163 CPU & 512GB 內存的服務器上，由于 Faiss 要求的計算資源過于龐大，無法實現單機十億規模的索引的構建和檢索。而 Proxima 在同樣的環境和數據量下單機可以輕松完成十億規模的索引的構建和檢索。

考慮到測試的可行性，達摩院團隊在同樣是 2 億規模的數據量下，針對索引構建和檢索對比了 Faiss 和 Proxima，另外，同樣 2000 萬規模的數據量下，對比了 Faiss 和 Proxima 單卡的異構計算能力，對于十億規模的數據量 Proxima 則單獨給出測試數據，具體結果如下。

檢索對比

Proxima 的檢索性能優于 Faiss 數倍，并且能實現更高精度的召回，針對 TOP1 的檢索更是技勝一籌。除此，Faiss 在一些算法實現上也存在設計缺陷，例如 HNSW 的實現，針對大規模索引，檢索性能非常低。

構建對比

Faiss 兩億規模索引的構建時間需要 45小時，采用 HNSW 優化的情況下可縮短到 15小時，而相同資源下 Proxima 一個多小時便可構建完索引，并且索引的存儲更小，精度更高（見檢索對比）。

異構計算

Proxima 采用了和 Faiss 不一樣的 GPU 計算方法，特別針對“小批量+低延時+高吞吐”的在線檢索場景進行優化。

Proxima 在小批量場景表現出了驚人的優勢，小批量、低延時、高吞吐，并能充分利用 GPU 資源。目前，該檢索方案也大規模應用在阿里的搜索推薦業務上。

十億規模

Proxima 支持流式索引和半內存構建檢索模式，真正做到了有限資源下，單機十億規模級別的索引構建，以及高性能高精度檢索。Proxima 這種高性能低成本能力為 AI 大規模離線訓練和在線檢索提供了強有力的基礎支持。

四 技術展望

隨著 AI 技術的廣泛應用以及數據規模的不斷增長，向量檢索作為深度學習中的主流方法，其具備的泛檢索和多模態搜索的能力也將進一步得到發揮。物理世界的實體和特征，通過向量化技術進行表征和組合，映射到數字世界，借助計算機進行計算和檢索，挖掘潛在邏輯和隱式關系，更智能的服務于人類社會。

未來，向量檢索除了要面對數據規模的不斷增長，算法上仍需要解決混合空間檢索、稀疏空間檢索、超高維、泛一致性等問題。工程上，面對的場景將越來越廣泛，也越來越復雜，如何形成強有力的系統化體系，貫穿場景和應用，將是向量檢索下一步發展的重點。

— 完 —