假設我們有一大批文件，想要找出其中哪些文件彼此之間大致相同。舉例來說，我們可能在一段時間內爬取了網路，預期會多次抓到「同一個頁面」，但在中繼資料上有些微差異，或是某個頁面經過小幅修改後的多個版本。

在這篇文章中，我想探討透過 Jaccard 相似度與 MinHash 近似技巧來進行近似去重的方法。這是處理這類問題的常見作法（例如 GPT-3 論文就提到將其作為資料集前處理流程的一部分），但我直到最近才接觸到，覺得相當有趣。

相似度

我們進行近似去重的策略，是先定義任意兩份文件之間的「相似度」概念，再找出相似度高於某個門檻的配對。也就是說，若所有可能文件的集合為 \(U\)，我們可以定義文件配對之間的相似度度量： $$S: U \times U \rightarrow [0,1]$$ 並將 \(S(A,B) \geq S_\textrm{crit}\) 的兩份文件視為「近似重複」。

值得注意的是，這個定義一般來說不具遞移性：我們很可能遇到三份文件 \(A, B, C\)，使得 \(S(A,B)\geq{}S_\textrm{crit}\) 且 \(S(B,C) \geq{} S_\textrm{crit}\)，但 \(S(A,C) < S_\textrm{crit}\)。這表示「大致相同」並不是一個等價關係，這也是為什麼相較於尋找完全相同的匹配，近似去重無論在概念上或在大規模實作上都更為棘手的原因之一。

Jaccard 相似度

在多個領域中被廣泛使用、包含大規模文字處理的相似度度量之一，就是 Jaccard 指數，也稱為 Jaccard 相似係數。

Jaccard 指數是一個用來比較集合的函式，它以兩個有限集合的交集大小與聯集大小的比值來描述兩者的相似程度：

$$J(A,B) = \frac{|A\cap{}B|}{|A\cup{}B|}$$

我覺得這個計算方式頗符合直覺：如果兩個集合相似，它們應該大多擁有相同的元素。這表示兩個集合的大小相近，聯集只會稍大一點，交集也只會稍小一點。如果集合差異很大，或大小相差很多，聯集就會很大而交集很小。

它有兩個非常自然的極限情況，界定了其值域：對於兩個互斥的集合，分子 \(|A\cap{}B|\) 為零，指數趨近於零。但若兩集合完全相同，\(A\cap{}B = A\cup{}B = A = B\)，此時 Jaccard 相似度為 1。

請注意，Jaccard 相似度是作用在集合上，但我們的起點是文件（通常以 Unicode 字串表示）。有關如何將文字文件轉成集合，我會在文末再回來討論，現在就先假設已經完成了。我會把這些集合稱為「特徵集合」，其中的每個元素則是文件的「特徵」。

擴展 Jaccard 相似度的計算

現在我們已經有了「近似相似」的定義：將文件轉換為特徵集合，再尋找 Jaccard 相似度高的集合。

對於非常小的語料庫，或許可以直接套用這個定義。然而，若要考慮所有文件配對，計算量會隨著語料庫大小以 \(O(n^2)\) 成長，很快就會變得不可行。

要尋找完全重複的文件時，我們透過雜湊來避免二次方的成本；將文件雜湊後依雜湊值分組，相同的文件（而且以很高的機率，只有相同的文件）會被分到同一個雜湊桶中。我們想為近似重複找到類似的捷徑；用這個領域的術語來說，我們想要的是一個局部敏感雜湊。

事實上，針對 Jaccard 相似度確實存在這類技術！讓我們來看看它的運作原理。

近似 Jaccard 相似度

我們先來考慮近似兩份文件之間 Jaccard 相似度的問題。我們會找到一種近似方法，它不需要檢視整個集合，只需要一個小而固定大小的「簽章」，而且可以針對每份文件獨立預先計算。接著，我們會利用這個簽章的結構，找出將文件分組的方法，使得（以相當高的機率）相似的文件、而且大多只有相似的文件會被分到同一組。

MinHash 簽章

回想一下，Jaccard 相似度是兩個大小的比值：兩個輸入集合的交集與聯集。

$$J(A,B) = \frac{|A\cap{}B|}{|A\cup{}B|}$$

要估計這類面積比值，一種經典策略是取樣。如果我們能以適當意義上的均勻方式產生隨機元素，並能查詢這些元素是否存在於比值的兩側，我們就能得到一個會趨近真實值的經驗估計。

在這個例子中，我們知道聯集至少和交集一樣大，因此我們想要從 \(A\cup{}B\) 中均勻隨機取樣。單看集合本身並不清楚該怎麼做，但如果允許對每個集合做預先計算，其實可以用很低的成本做到！

• 首先，我們把問題看似弄得更複雜一點。假設特徵是某個有限範圍內的整數 \(0 \leq f_i \leq F\)，然後在 \(\mathbb{Z}_F\) 上隨機挑一個排列，稱之為 \(P(x)\)。接著，我們可以透過挑選在這個排列下值最小的特徵，來選出一個隨機元素¹：

$$ x_{\textrm{random}} \leftarrow{} \argmin_{x\in{}A\cup{}B}{P(x)} $$

• 要直接處理真正的隨機排列其實不太可行，但我們可以用一個好的雜湊函式來近似。這樣也能避免特徵必須表示為固定範圍整數的限制；只要接受極微小的碰撞風險並只儲存雜湊值，我們就能將任何合理的特徵空間對映到固定大小的雜湊值：

$$ x_{\textrm{sig}} \leftarrow{} \min_{x\in{}A\cup{}B}{H(x)} $$

• 接下來，我們要利用 min 具有結合性的特性，將上式改寫為可對每個集合單獨預處理的形式：

\begin{align*} a_{\textrm{min}} &\leftarrow{} \min_{x\in{}A}H(x) \\ b_{\textrm{min}} &\leftarrow{} \min_{x\in{}B}H(x) \\ x_{\textrm{sig}} &\leftarrow{} \min(a_\textrm{min},b_\textrm{min}) \end{align*}

讓我們退一步，想想我們完成了什麼。如果我們在特徵上選了一個好的雜湊函式，就可以為每個集合單獨計算一個「簽章」，也就是其所有特徵中雜湊值最小的那一個。給定任意兩個集合，我們只要取這兩個簽章的最小值，就能得到一個從它們聯集中均勻隨機抽出的元素（的雜湊值）。

我們想知道這個元素是否存在於交集中，或是其中一邊缺失了它。但這個構造也讓這件事變得微不足道！我們知道 \(x_\textrm{sig}\) 是任一集合中所有元素的最小雜湊值。因此，如果它出現在例如集合 \(A\) 中，它必定也是該集合中的最小雜湊值。而我們恰好已經知道每個集合的最小雜湊值——那正是我們手上的資料！

因此，我們其實不需要去計算 \(x_\textrm{sig}\)；只要問 \(a_\textrm{min} = b_\textrm{min}\) 是否成立就好！對於任意兩個集合，這個等式成立的機率恰好等於 \(J(A, B)\)！

使用更多雜湊函式

這個機率是在 \(\mathbb{Z}_F\) 的所有排列空間上取的（換句話說，帶有一些前提，等同於「在我們對雜湊函式的選擇上」）。只用單一雜湊函式與單一 min-hash 時，對於每一對集合我們只有一個二元估計——「相等」或「不相等」。

我們可以改為從某個合適的雜湊函式族中挑選 \(k\) 個不同的雜湊函式，將每份文件濃縮成一個 \(k\) 維向量，以此改進估計：

$$ A_\textrm{sig} = \begin{pmatrix} \displaystyle\min_{x\in{}A}H_1(x) & \displaystyle\min_{x\in{}A}H_2(x) & \cdots{} & \displaystyle\min_{x\in{}A}H_k(x) \end{pmatrix} $$

給定兩個這樣的簽章，我們可以透過計算有多少個雜湊值相符來近似 Jaccard 相似度：

$$ J(A,B) \approx{} \frac{1}{k}\sum_{i=1}^{k} (A_\textrm{sig}[i] = B_\textrm{sig}[i]) $$

有一點需要提醒：這裡雜湊函式族的選擇有些微妙。我們試圖近似特徵全域上的一個隨機排列，但這類排列的數量增長得極快，因此我們的雜湊函式族只會代表所有可能排列中的極小一部分。我們必須確保雜湊函式族中的成員不會有不當的相關性——形式上，這裡關鍵的性質稱為「最小值獨立（min-wise independence）」。幸好，這個問題已有相當充分的研究，文獻中也有高效率的解法可供使用。

比較所有文件

到目前為止，我們已將每份文件壓縮成一個由 \(k\) 個雜湊值組成的指紋，這讓我們能高效率地近似 Jaccard 相似度。

下一個問題是要在整個語料庫中找出近似重複——也就是相似度高的文件——而且不需要考慮每一對文件。如前所述，我們的策略是定義一組可用來分組文件的鍵，然後只在每個分組內進行完整的比較。我們的目標是設計分組鍵，讓相似的文件以很高的機率被分到同一組，而不相似的文件則不會。

使用完整簽章

最簡單的選擇就是直接將全部 \(k\) 個 MinHash 值一起作為分組鍵，並將兩份文件視為「近似重複」若且唯若它們所有的 MinHash 值都相符。我相當確定這就是上面引用的 GPT-3 論文所說「我們使用 Spark 的 MinHashLSH 實作，以 10 個雜湊值對文件進行模糊去重……」的意思。他們將每份文件切成特徵，為每份文件計算 10 個 MinHash 值（使用了 10 個不同的雜湊函式²），再以這個 10 維向量將文件分組，每組只保留一份文件。

這個方法最大的優點在於簡單與高效率。以單一高基數的位元組字串來分組文件，是一種高效率且容易水平擴展的操作，幾乎任何資料處理工具都將其作為基本原語提供（可以說這就是 MapReduce 的核心原語，以 map 與 reduce 階段之間的「shuffle」形式呈現）。

這個方法的表現如何？對於單一文件配對，我們預期每個 MinHash 值相等的機率為 \(J(A,B)\)，因此 10 個全部相符的機率為 \(p=J(A,B)^k\)。當 \(k=10\) 時，結果如下圖所示：

以及一些分位數：

可以看到，相似度在 0.6 左右以下的文件幾乎不會碰撞，而在 0.95 左右時相符的機率就會變得很高。如果我們主要關心的是非常接近的「近親」文件，這個方法或許就已足夠。事實上我懷疑——但尚未驗證——在許多語料庫中，Jaccard 值的分布會呈現相當明顯的雙峰：集中在接近 1 與接近 0 的兩個群集。無關的文件相似度接近 0，而相似的文件大多是「幾乎完全相同」——例如一篇文章的兩個小幅修訂版，或同一內容但帶有不同時間戳記或中繼資料的兩個副本。

另外值得注意的是，\(J^{k}\) 的計算是針對單一文件配對而言。若我們有許多彼此都很相似的文件，這些配對之間的機率完全不是獨立的。實務上，面對許多非常相似的文件，它們很可能會被雜湊到至多兩、三個桶子中，因此在某種意義上，我們會找出「幾乎所有」的重複。

更模糊的匹配

（註：以下討論主要參考《Mining of Massive Datasets》第 3.4 節。我自己還沒實際嘗試過這個策略，也還不清楚它在實務上是否、或何時會被使用。）

如果我們想偵測「更模糊」的重複呢？或許經過一些實證研究後，我們決定想找出相似度高於 0.8 或 0.7 的配對，而不只是「接近 1」的情況。

透過將 \(k\) 個 MinHash 雜湊值中的一個子集作為分組鍵，我們可以在較低相似度下提高碰撞機率，再於每個桶子內比較完整簽章來剔除誤判的碰撞。舉例來說，我們可以用前 4 個 MinHash 值來分組，然後——在每個發生碰撞的分組內——再用全部 MinHash 值來估計真正的相似度。

使用較少的雜湊值有幫助，但效果有限；\(J^r\) 永遠會小於 \(J\)，如果把 \(r\) 壓得太小，誤判匹配的比率就會變得無法接受。

我們可以改為為每份文件產生多個鍵，將每份文件放入多個桶子中，每個鍵對應一個桶子，且每個鍵使用不同的 MinHash 子集。舉例來說，如果我們計算 \(k=20\) 個雜湊值作為簽章，可以將每份文件放入 \(b=4\) 個不同的桶子，每個鍵用 \(r=5\) 個雜湊值來建構，然後比較每個桶子內的每一對文件。

那麼兩份文件至少在一個桶子中被雜湊到一起的機率是多少？

• 兩份文件使用單一鍵發生碰撞的機率為 \(J^r\)
• 因此它們不會因該鍵而碰撞的機率為 \(1-J^r\)
• 因此它們在任何一個桶子中都不碰撞的機率為 \((1-J^r)^b\)

因此，它們至少碰撞一次的機率為：

\[ p = 1 - (1-J^r)^b \]

例如，上述以 4 組、每組 5 個雜湊值的例子，會產生如下的機率曲線：

這條曲線沒有先前的例子那麼陡峭，但我們已成功將其向左平移——碰撞機率在 \(J=0.7\) 附近達到 50%。

事實上，對於任何大於 1 的 \(r\) 與 \(b\) 組合，所得的曲線大致上都呈現類似的 S 形，因此調整這些數值可以在敏感度、召回率與效能成本之間提供豐富的取捨空間。

結語

在投入 AI 領域之前，我自認對常見的演算法技巧已算相當熟悉，包含大多數常見的 sketch 演算法。但不知為何，我從未接觸過 MinHash，甚至不知道這類演算法（局部敏感雜湊）存在或具有實用性！

我非常享受學習這個技巧的運作原理並深入探究的過程。希望這篇部落格文章能讓更多工程師第一次認識它，或幫助某些人補足理解上的空隙。我就是喜歡這種精巧的數學／演算法技巧！

後記：MinHash 與 HyperLogLog

在研究並撰寫這篇文章的過程中，我意識到 MinHash 的核心技巧讓我聯想到一個經典且頗為有名的 sketch：HyperLogLog。

HyperLogLog 的核心概念（可追溯到一個更早的演算法）是對串流中的每個元素進行雜湊，並在產生的雜湊串流中，持續保存「前導零個數」的最大值。

兩種演算法在細節上差異很大，但有明顯的相似之處：在兩種情況下，我們都使用雜湊函式將輸入元素對映到均勻分布，再計算一個連續極值，透過適當的計算，就能僅用固定大小的摘要來估計某種分布特性。

事實上，我認為這兩個演算法比初看之下更為相似：HyperLogLog 計算前導零（最低有效位元中的零）。然而，我們假設雜湊函式會在 \([0, 2^N)\) 區間內輸出均勻分布的值，因此不妨將位元順序反轉，改為計算最高有效位元中零的個數。但對於一個 N 位元的數 \(x\) 而言，高位零的個數與 \(\log_2(x)\) 密切相關——前導零愈多，\(x\) 就愈小。因此，我們同樣可以將 HyperLogLog 視為在計算 \(log_2(H(x))\) 的連續最小值，相較於 MinHash 計算的是 \(H(x)\) 的連續最小值。

此外，某種意義上 HyperLogLog 與 MinHash 具有（某種程度的）對偶性：給定兩個不同集合的 HyperLogLog 結構，我們可以將它們合併，並估計其聯集的大小。給定這兩個集合的兩個 MinHash 結構，我們可以比較它們並估計其交集的（相對）大小。

因此，如果結合這兩種結構，就能產生一個 sketch，讓你對任意集合的交集與聯集提出問題！這個想法至少在 2013 年就已被提出，而事實上，關於以有趣方式結合這兩種資料結構概念的 sketch，相關研究 文獻至今仍持續發展中。我覺得這很巧妙！

附錄：將文件表示為集合

我曾承諾會回到如何將文件表示為集合的問題，因此也在此簡要說明兩種常見作法。

首先，在套用這兩種策略之前，我們可能會想先對文件做某種正規化。例如，我們很可能會想轉換為標準的 Unicode 正規化形式，也可能希望進行大小寫折疊、合併連續空白，或執行類似的轉換。

n-gram（亦稱「shingle」）

我們可以將一份文件表示為其中出現的所有 n-gram 所組成的集合，並選取一個合適的 n 值。在大規模文字處理領域，文獻中常以「shingle」一詞來代替「n-gram」，但我覺得那只是徒增混淆。我們可以選用任何 n 值，主要的取捨在於，較小的數值會傾向以較粗略的方式比較文件（例如，透過 bigram 的視角，大多數英文文本看起來可能都頗為相似），而較大的數值則會產生更多相異的特徵，因而形成更大的集合。到了某個極限，我預期敏感度也會下降，但我猜效能問題會更早出現。

根據我找到的一個來源³，在多種應用中，n 介於 5 到 9 之間似乎是常見的選擇。

以詞彙切分

我們也可以嘗試將輸入切分成「詞」或「詞元（token）」，並將它們作為特徵。上面 GPT-3 論文摘錄中提到的「Spark 標準 tokenizer」，我認為指的就是這個類別，它只是將輸入轉為小寫後再依空白切分。

我們可以使用更精密的 tokenizer，或者將兩種作法混合，先做 tokenization 再對 token 取 n-gram。在這種情況下，我們會使用較小的 n 值，因為單一 token 的熵應該遠高於位元組或字元。

1. 如果你曾寫過 SELECT ... FROM table ORDER by random() LIMIT 1，你就已經用過類似的技巧了！ ↩︎

2. 如果你感到好奇，Spark 有文件說明其對雜湊函式族的選擇，並附有相關的文獻參考。 ↩︎

3. Mining of Massive Datasets §3.2.2 ↩︎