作者：來自 Elastic?Valentin Crettaz

本文是三篇系列文章中的第一篇，將深入探討向量搜索（也稱為語義搜索）的復雜性，以及它在 Elasticsearch 中的實現方式。

本文是三篇系列文章中的第一篇，將深入探討向量搜索（也稱為語義搜索）的復雜性以及它在 Elasticsearch 中的實現方式。

第一部分重點介紹嵌入向量的基礎知識以及向量搜索的底層工作原理。

借助第一篇文章中學到的所有知識，第二部分將指導你了解如何在 Elasticsearch 中設置向量搜索。

在第三部分中，我們將利用前兩部分中學到的知識，在此基礎上深入研究如何在 Elasticsearch 中編寫強大的混合搜索查詢。

在深入探討本文的真正內容之前，讓我們回顧一下向量的一些歷史，它是語義搜索中的關鍵概念。

向量搜索并不新鮮

可以肯定的是，自 2022 年 11 月 ChatGPT 問世以來，我們每天都會聽到或讀到有關 “向量搜索” 的信息。向量搜索無處不在，而且非常普遍，我們常常會覺得這是一項剛剛問世的尖端新技術，但事實是，這項技術已經存在了 60 多年！該主題的研究始于 1960 年代中期，第一篇研究論文于 1978 年由信息檢索專家 Gerard Salton 及其康奈爾大學的同事發表。Salton 在密集和稀疏向量模型方面的工作構成了現代向量搜索技術的根基。

在過去的 20 年里，許多基于他的研究的向量 DBMS 被創建并推向市場。其中包括由 Apache Lucene 項目提供支持的 Elasticsearch，該項目于 2019 年開始研究向量搜索。

向量現在無處不在，如此普遍，因此在使用它們之前，首先要很好地掌握它們的基本理論和內部工作原理。在深入研究之前，讓我們快速回顧一下詞匯搜索和向量搜索之間的區別，以便我們更好地理解它們的區別以及它們如何相互補充。

向量搜索與詞匯搜索

介紹向量搜索的一個簡單方法是將其與你可能習慣的更傳統的詞匯搜索進行比較。向量搜索（通常也稱為語義搜索）和詞匯搜索的工作方式截然不同。詞匯搜索是我們在 Elasticsearch 中多年來一直使用的搜索類型。簡而言之，它不會嘗試理解索引和查詢內容的真正含義，而是會盡力將用戶在查詢中輸入的單詞或其變體（例如詞干、同義詞等）的文字與之前已使用相似性算法（例如 TF-IDF）索引到數據庫中的所有文字進行詞匯匹配。
?

我們可以看到，左上角的三個文檔被標記并分析。然后，將生成的術語編入倒排索引，該索引只是將分析的術語映射到包含它們的文檔 ID。請注意，所有術語都只出現一次，并且沒有一個與任何文檔共享。搜索 “nice german teacher” 將匹配所有三個文檔，分數各不相同，即使它們都沒有真正抓住查詢的真正含義。

如下圖 2 所示，在處理多義詞或同形異義詞時，情況會變得更加棘手，即拼寫相同但含義不同的單詞（right、palm、bat、mean 等）。讓我們以 “right” 這個詞為例，它可以表示三種不同的含義，看看會發生什么。

搜索 “I’m not right” 會返回一個與第一個返回結果含義完全相反的文檔。如果你搜索完全相同的術語，但以不同的順序排列它們以產生不同的含義，例如 “turn right”? 和 “right turn”，則會產生完全相同的結果（即第三個文檔 “Take a right turn”）。誠然，我們的查詢過于簡單，沒有使用短語匹配等更高級的查詢，但這有助于說明詞匯搜索不了解索引和搜索內容背后的真正含義。如果這不清楚，請不要擔心，我們將在第三篇文章中重新討論這個例子，看看向量搜索在這種情況下如何提供幫助。

公平地說，當你可以控制如何索引結構化數據（想想映射、文本分析、提取管道等）以及如何編寫查詢（想想巧妙編寫的 DSL 查詢、查詢術語分析等）時，你就可以使用詞匯搜索引擎創造奇跡，這是毫無疑問的！Elasticsearch 在詞匯搜索功能方面的記錄令人驚嘆。它在過去幾年中取得的成就以及它在多大程度上普及和改進了詞匯搜索領域，這確實令人驚嘆。

但是，當你負責為需要提出自由文本問題的用戶提供查詢非結構化數據（想想圖像、視頻、音頻、原始文本等）的支持時，詞匯搜索就顯得力不從心了。此外，有時查詢甚至不是文本，它可能是圖像，我們很快就會看到。詞匯搜索在這種情況下不足的主要原因是非結構化數據既不能像結構化數據那樣被索引，也不能被查詢。處理非結構化數據時，語義（semantics）就會發揮作用。語義是什么意思？很簡單，就是含義！

我們以圖像搜索引擎（例如 Google 圖片搜索或 Lens）為例。你拖放一張圖片，Google 語義搜索引擎就會找到并返回與你查詢的圖片最相似的圖片。在下面的圖 3 中，我們可以在左側看到德國牧羊犬的圖片，在右側看到所有已檢索到的類似圖片，第一個結果是與提供的圖片相同的圖片（即最相似的圖片）。

盡管這對于我們人類來說聽起來簡單而合乎邏輯，但對于計算機來說，情況就完全不同了。這就是向量搜索能夠實現和幫助實現的。正如世界最近所見證的那樣，向量搜索釋放的力量是巨大的。現在讓我們揭開它的面紗，看看下面隱藏著什么。

嵌入向量

正如我們之前所見，使用詞匯搜索引擎，文本等結構化數據可以輕松標記為可在搜索時匹配的術語，而不管這些術語的真實含義如何。然而，非結構化數據可以采用不同的形式，例如大型二進制對象（圖像、視頻、音頻等），并且根本不適合相同的標記（tokenizing）過程。此外，語義搜索的整個目的是以這樣的方式索引數據，以便可以根據其所代表的含義進行搜索。我們如何實現這一點？答案就在兩個詞中：機器學習！或者更準確地說是深度學習！

深度學習（Deep Learning）是機器學習的一個特定領域，它依賴于基于人工神經網絡的模型，該模型由多層處理組成，可以逐步提取數據的真正含義。這些神經網絡模型的工作方式深受人腦的啟發。下面的圖 4 顯示了神經網絡的外觀，包括輸入層和輸出層以及多個隱藏層：

神經網絡的真正壯舉是它們能夠將單個非結構化數據轉換為一系列浮點值，這些浮點值被稱為嵌入向量或簡稱為嵌入。作為人類，只要我們在二維或三維空間中可視化它們，我們就能很好地理解什么是向量。向量的每個分量表示二維 x-y 平面或三維 x-y-z 空間中的坐標。

但是，神經網絡模型工作的嵌入向量可以有幾百甚至幾千個維度，并且僅表示多維空間中的一個點。每個向量維度代表非結構化數據的一個特征（feature）或特性。讓我們用一個深度學習模型來說明這一點，該模型將圖像轉換為 2048 維的嵌入向量。該模型會將我們在圖 3 中使用的德國牧羊犬圖片轉換為下表所示的嵌入向量。請注意，我們僅顯示第一個和最后一個元素，但表中還會有 2,042 個列/維度。

	is_red	is_dog	blue_sky	…	no_gras	german_shepherd	is_tree
German shepherd embeddings	0.0121	0.9572	0.8735	…	0.1198	0.9712	0.0512

每一列都是模型的一個維度，代表底層神經網絡試圖建模的特征或特性。提供給模型的每個輸入都將根據該輸入與 2048 個維度的相似程度進行表征。因此，嵌入向量中每個元素的值表示該輸入與特定維度的相似度。在這個例子中，我們可以看到模型檢測到狗和德國牧羊犬之間有很高的相似性，并且還檢測到了一些藍天。

與詞匯搜索（其中術語可以匹配也可以不匹配）相比，使用向量搜索，我們可以更好地了解一段非結構化數據與模型支持的每個維度的相似程度。因此，嵌入向量可以作為非結構化數據的極好的語義表示。

秘訣

現在我們知道了深度學習神經網絡如何將非結構化數據切分為嵌入向量，從而捕捉大量維度上數據的相似性，我們需要了解這些向量的匹配是如何進行的。答案其實很簡單。彼此接近的嵌入向量表示語義上相似的數據片段。因此，當我們查詢向量數據庫時，搜索輸入（圖像、文本等）首先使用與索引所有非結構化數據相同的模型轉換為嵌入向量，最終目標是找到與該查詢向量最近的相鄰向量。因此，我們需要做的就是弄清楚如何測量查詢向量與數據庫中索引的所有現有向量之間的 “距離” 或 “相似性”，僅此而已。

距離和相似性

幸運的是，借助向量算法，測量兩個向量之間的距離是一個很容易解決的問題。那么，讓我們來看看現代向量搜索數據庫（例如 Elasticsearch）支持的最流行的距離和相似度函數。警告，前方有數學知識！

L1 距離

兩個向量 x 和 y 的 L1 距離（也稱為曼哈頓距離）是通過將它們所有元素的成對絕對差相加來測量的。顯然，距離 d 越小，兩個向量越接近。公式非常簡單，如下所示：

從視覺上看，L1 距離可以用下面的圖 5 來表示：

設兩個向量 x 和 y，例如 x = (1, 2) 和 y = (4, 3)，則兩個向量的 L1 距離為 | 1 - 4 | + | 2 - 3 | = 4。

L2 距離

L2 距離，也稱為歐幾里得距離，兩個向量 x 和 y 的測量方法是先將它們所有元素的兩兩差值的平方相加，然后對結果取平方根。它基本上是兩點之間的最短路徑（也稱為斜邊）。與 L1 類似，距離 d 越小，兩個向量越接近：

L2 距離如下圖6所示：

讓我們重復使用與 L1 距離相同的兩個樣本向量 x 和 y，現在我們可以計算 L2 距離為?。取 10 的平方根將得出 3.16。

Linf 距離

兩個向量 x 和 y 的 Linf（代表 L 無窮大）距離，也稱為切比雪夫距離或棋盤距離，簡單定義為任意兩個元素之間的最長距離或沿其中一個軸/維度測量的最長距離。公式非常簡單，如下所示：

Linf 距離的表示如下圖 7 所示：

同樣，取相同的兩個樣本向量 x 和 y，我們可以計算 L 無窮距離為 max ( | 1 - 4 | , | 2 - 3 | ) = max (3, 1) = 3。

余弦相似度

與 L1、L2 和 Linf 不同，余弦相似度不測量兩個向量 x 和 y 之間的距離，而是測量它們的相對角度，即它們是否都指向大致相同的方向。相似度 s 越高，兩個向量越 “接近”。公式同樣非常簡單，如下所示：

兩個向量之間余弦相似度的表示方法如下圖 8 所示：

此外，由于余弦值始終在 [-1, 1] 區間內，-1 表示相反的相似性（即兩個向量之間呈 180° 角），0 表示不相關的相似性（即呈 90° 角），1 表示相同（即呈 0° 角），如下圖 9 所示：

再次，讓我們重復使用相同的樣本向量 x 和 y，并使用上述公式計算余弦相似度。首先，我們可以計算兩個向量的點積，即 （1x4)+(2x3) = 10。然后，我們將兩個向量的長度（也稱為幅度）相乘：。最后，我們將點積除以乘積的長度 10 / 11.18034 = 0.894427（即 26° 角），該值非常接近 1，因此兩個向量可以被認為非常相似。

點積相似度

余弦相似度的一個缺點是它只考慮兩個向量之間的角度，而不考慮它們的大小（即長度），這意味著如果兩個向量大致指向同一方向，但其中一個比另一個長得多，則兩者仍將被視為相似。點積相似度（也稱為標量或內積）通過同時考慮向量的角度和大小來改善這一點，從而提供更準確的相似度度量。

兩個等效公式用于計算點積相似度。第一個與我們之前在余弦相似度的分子中看到的相同：

第二個公式只是將兩個向量的長度乘以它們之間角度的余弦：

點積相似度如下圖 10 所示：

最后一次，我們取樣本 x 和 y 向量，并使用第一個公式計算它們的點積相似度，就像我們之前對余弦相似度所做的那樣，即 (1x4)+(2x3) = 10。
?

使用第二個公式，我們將兩個向量的長度相乘：?并將其乘以兩個向量之間 26° 角的余弦，得到?11.18034 x cos(26°) =? 10。

值得注意的是，如果先對所有向量進行歸一化（即，它們的長度為 1），那么點積相似度將與余弦相似度完全相同（因為 |x| |y| = 1），即兩個向量之間角度的余弦。正如我們稍后會看到的，歸一化向量是一種很好的做法，它可以讓向量的大小變得無關緊要，從而使相似度只關注角度。它還可以加快索引和查詢時的距離計算，這在處理數十億個向量時可能是一個大問題。

快速回顧

哇，到目前為止我們已經了解了很多信息，所以讓我們暫停一下，快速回顧一下我們所處的位置。我們已經了解到……

• …語義搜索基于深度學習神經網絡模型，該模型擅長將非結構化數據轉換為多維嵌入向量。
• …模型的每個維度都代表非結構化數據的特征或特性。
• …嵌入向量是一系列相似度值（每個維度一個），表示給定的非結構化數據與每個維度的相似程度。
• …兩個向量越 “近”（即最近鄰居），它們所代表的語義相似概念就越多。
• …距離函數（L1、L2、Linf）使我們能夠測量兩個向量的接近程度。
• …相似度函數（余弦和點積）使我們能夠測量兩個向量朝同一方向的距離。

現在，我們需要深入研究的最后一部分是向量搜索引擎本身。當查詢進入時，查詢首先被向量化，然后向量搜索引擎找到與該查詢向量最近的相鄰向量。測量查詢向量與數據庫中所有向量之間的距離或相似度的蠻力（brute-force）方法可以適用于小型數據集，但隨著向量數量的增加，它很快就會失效。換句話說，我們如何索引數百萬、數十億甚至數萬億個向量，并在合理的時間內找到查詢向量的最近鄰居？這就是我們需要變得聰明并找出索引向量的最佳方法的地方，這樣我們就可以盡快鎖定最近的鄰居，而不會過多地降低精度。

更多有關距離和相似性的知識，請詳細閱讀 “Elasticsearch：向量相似度技術和評分”

向量搜索算法和技術

多年來，許多不同的研究團隊投入了大量精力來開發非常巧妙的向量搜索算法。在這里，我們將簡要介紹主要的算法。根據用例，有些算法比其他算法更適合。

線性搜索

我們之前簡要介紹了線性搜索或平面索引，當時我們提到了將查詢向量與數據庫中存在的所有向量進行比較的蠻力（brute-force）方法。雖然它可能在小型數據集上效果很好，但隨著向量數量和維度的增加（O（n）復雜度），性能會迅速下降。

幸運的是，有一種更有效的方法，稱為近似最近鄰 (approximate nearest neighbor -?ANN)，其中嵌入向量之間的距離是預先計算的，并且相似的向量以保持它們靠近的方式存儲和組織，例如使用集群、樹、哈希或圖形。這種方法被稱為 “近似”，因為它們通常不能保證 100% 的準確性。最終目標是盡可能快速地縮小搜索范圍，以便只關注最有可能包含相似向量的區域，或者降低向量的維數。

K 維樹 - K - Dimensional trees

K 維樹或 KD 樹是二叉搜索樹的泛化，它將點存儲在 k 維空間中，并通過將搜索空間連續二等分為較小的左樹和右樹來工作，其中向量被索引。在搜索時，算法只需訪問查詢向量周圍的幾個樹枝（圖 11 中的紅點）即可找到最近的鄰居（圖 11 中的綠點）。如果請求的鄰居超過 k 個，則黃色區域會擴展，直到算法找到更多鄰居。

KD 樹算法的最大優點是它允許我們快速地只關注一些局部的樹分支，從而排除大部分向量的考慮。然而，這種算法的效率會隨著維數的增加而降低，因為與低維空間相比，需要訪問的分支要多得多。

倒排索引

倒排索引 (inverted file index - IVF) 方法也是一種空間分區（space-partitioning）算法，它將彼此接近的向量分配到它們的共享質心。在 2D 空間中，最好使用 Voronoi 圖來可視化，如圖 12 所示：

我們可以看到，上面的二維空間被劃分為 20 個簇，每個簇的質心都用黑點表示。空間中的所有嵌入向量都被分配給質心最接近的簇。在搜索時，算法首先通過找到最接近查詢向量的質心來確定要關注的簇，然后它可以簡單地將焦點集中在該區域，如果需要，還可以將焦點集中在周圍的區域，以找到最近的鄰居。

在高維空間中使用時，此算法會遇到與 KD 樹相同的問題。這稱為維數災難，當空間體積增加太多以至于所有數據看起來都很稀疏，并且獲得更準確結果所需的數據量呈指數增長時，就會發生這種情況。當數據稀疏時，這些空間分區算法將數據組織成簇變得更加困難。幸運的是，還有其他算法和技術可以緩解這個問題，如下所述。

量化 - Quantization

量化是一種基于壓縮的方法，它允許我們通過降低嵌入向量的精度來減少數據庫的總大小。這可以通過使用標量量化 (scalar quantization -?SQ) 來實現，即將浮點向量值轉換為整數值。這不僅可以將數據庫的大小減少 8 倍，還可以減少內存消耗并加快搜索時向量之間的距離計算。

另一種技術稱為乘積量化 (product quantization -?PQ)，它首先將空間劃分為低維子空間，然后使用聚類算法（類似于 k 均值 - k-means）將彼此接近的向量分組到每個子空間中。

請注意，量化不同于降維，降維是減少維數（dimensionality reduction），即向量只是變短了。

分層可導航小世界 (Hierarchical Navigable Small Worlds - HNSW)

如果僅從名稱來看它看起來很復雜，別擔心，其實它并不復雜！簡而言之，分層可導航小世界是一種基于多層圖形的算法，非常流行且高效。它被許多不同的向量數據庫使用，包括 Apache Lucene。下圖 13 中可以看到 HNSW 的概念表示。

在頂層，我們可以看到一個由極少數向量組成的圖，這些向量之間的鏈接最長，即相似度最低的連接向量圖。我們越深入底層，找到的向量就越多，圖就越密集，向量之間的距離也越來越近。在最低層，我們可以找到所有向量，其中最相似的向量彼此距離最近。

在搜索時，算法從頂層的任意入口點開始，找到最接近查詢向量的向量（以灰色點表示）。然后，它移動到下一層并重復相同的過程，從上一層留下的相同向量開始，依此類推，一層接一層，直到到達最低層并找到查詢向量的最近鄰居。

局部敏感哈希 (Locality-sensitive hashing - LSH)

與迄今為止介紹的所有其他方法一樣，局部敏感哈希力求大幅減少搜索空間，以提高檢索速度。通過這種技術，嵌入向量被轉換為哈希值，所有這些都通過保留相似性信息來實現，這樣搜索空間最終就變成了一個可以查找的簡單哈希表，而不是需要遍歷的圖或樹。基于哈希的方法的主要優點是，包含任意（大）維數的向量可以映射到固定大小的哈希，這極大地加快了檢索時間，而不會犧牲太多的精度。

通常，對數據進行哈希處理的方法有很多種，特別是對嵌入向量進行哈希處理的方法，但本文不會深入討論每種方法的細節。傳統的哈希方法通常會為看起來非常相似的數據產生非常不同的哈希。由于嵌入向量由浮點值組成，我們取兩個在向量算法中被認為非常接近的浮點值樣本（例如 0.73 和 0.74），并將它們通過幾個常見的哈希函數運行。從下面的結果可以看出，常見的哈希函數顯然無法保留輸入之間的相似性。

Hashing function	0.73	0.74
MD5	1342129d04cd2924dd06cead4cf0a3ca	0aec1b15371bd979cfa66b0a50ebecc5
SHA1	49d2c3e0e44bff838e1db571a121be5ea874e8d9	a534e76482ade9d9fe4bff3035a7f31f2f363d77
SHA256	99d03fc3771fe6848d675339fc49eeb1cb8d99a12e6358173336b99a2ec530ea	5ecbc825ba5c16856edfdaf0abc5c6c41d0d8a9c508e34188239521dc7645663

雖然傳統的哈希方法試圖最小化相似數據片段之間的哈希沖突，但局部敏感哈希的主要目標恰恰相反，即最大化哈希沖突，以便相似的數據以高概率落入同一個存儲桶中。通過這樣做，在多維空間中彼此接近的嵌入向量將被哈希為落入同一個存儲桶中的固定大小值。由于 LSH 允許這些哈希向量保持其接近度，因此該技術對于數據聚類和最近鄰搜索非常有用。

所有繁重的工作都發生在需要計算哈希值的索引時，而在搜索時，我們只需要對查詢向量進行哈希處理，以查找包含最近嵌入向量的存儲桶。一旦找到候選存儲桶，通常會進行第二輪以確定與查詢向量最近的相鄰向量。

讓我們總結一下

為了介紹向量搜索，我們必須在本文中介紹相當多的內容。在比較了詞匯搜索和向量搜索之間的差異之后，我們了解了深度學習神經網絡模型如何設法捕獲非結構化數據的語義并將其含義轉碼為高維嵌入向量，即表示數據沿模型每個維度的相似性的浮點數序列。還值得注意的是，向量搜索和詞匯搜索不是競爭關系，而是互補的信息檢索技術（我們將在本系列的第三部分深入研究混合搜索時看到）。

之后，我們介紹了向量搜索的一個基本構建塊，即距離（和相似度）函數，它使我們能夠測量兩個向量的接近度并評估它們所代表的概念的相似性。

最后，我們回顧了最流行的向量搜索算法和技術的不同類型，這些算法和技術可以基于樹、圖、集群或哈希，其目標是快速縮小多維空間的特定區域，以便找到最近的鄰居，而不必像線性蠻力搜索那樣訪問整個空間。

請繼續關注本系列的其他部分：

• 第 2 部分：如何在 Elasticsearch 中設置向量搜索
• 第 3 部分：使用 Elasticsearch 進行混合搜索

使用此自定進度的 Search AI 動手學習親自嘗試向量搜索。您現在可以開始免費云試用或在本地機器上試用 Elastic。

原文：A quick introduction to vector search - Elasticsearch Labs