大量の文書コレクションがあり、その中で互いにおおよそ同じ文書がどれかを特定したいとします。たとえば、ある期間にわたってウェブをクロールした場合、「同じページ」を何度も取得しているはずですが、メタデータにわずかな違いがあったり、小さな編集を経た複数のリビジョンが存在したりすることが考えられます。

この記事では、Jaccard類似度とMinHashという近似トリックによる、近似的な重複排除の手法を探ってみたいと思います。これはこの種の問題でよく使われるアプローチで（たとえばGPT-3論文でもデータセット準備パイプラインの一部として使われていることが述べられています）、私自身は最近まで出会ったことがなかったのですが、とても面白い手法だと感じています。

類似度

近似的な重複排除へのアプローチは、任意の2つの文書間の「類似度」という概念を定義し、その値がある閾値を超えるペアを探すというものになります。たとえば、考えうる文書の全体集合を \(U\) とすると、文書のペアに対する類似度尺度を次のように定義できます。 $$S: U \times U \rightarrow [0,1]$$ そして、\(S(A,B) \geq S_\textrm{crit}\) であれば、2つの文書を「近似的な重複」とみなします。

ここで注目すべきなのは、この定義は一般には推移的ではないということです。3つの文書 \(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指数は集合を比較する関数で、2つの有限集合の類似度を、重なりの大きさと和集合の大きさの比率として特徴付けます。

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

この計算は直感的にも理解しやすいと思います。2つの集合が似ていれば、要素の大半が共通しているはずです。つまり、集合のサイズは近くなり、和集合はわずかに大きくなるだけで、共通部分はわずかに小さくなるだけです。逆に、集合が大きく異なっていたり、サイズが大きく違ったりすれば、和集合は大きくなり、共通部分は小さくなります。

この指標には、値域を定める2つの自然な極限があります。互いに素な2つの集合では分子 \(|A\cap{}B|\) がゼロになり、指数は0になります。一方、集合が同一であれば \(A\cap{}B = A\cup{}B = A = B\) となり、Jaccard類似度は1になります。

Jaccard類似度は集合に対して作用しますが、私たちが最初に持っているのは文書（通常はUnicode文字列として表されます）です。テキスト文書をどうやって集合に変換するかについては最後に触れることにして、ここでは変換済みであるとして話を進めます。これらの集合を「特徴集合（feature sets）」と呼び、個々の要素を文書の「特徴（features）」と呼ぶことにします。

Jaccard類似度のスケーリング

これで「近似的な類似性」の定義ができました。文書を特徴集合に変換し、Jaccard類似度が高い集合を探すのです。

非常に小さなコーパスであれば、この定義をそのまま適用できるかもしれません。しかし、すべての文書ペアを考えると計算量はコーパスサイズに対して \(O(n^2)\) で増大し、すぐに現実的でなくなります。

完全な重複を見つける場合は、ハッシュ化によって二次的なコストを回避します。文書をハッシュ化してハッシュ値ごとにグループ化すれば、同一の文書（そして高い確率で同一の文書だけ）が同じハッシュバケットに入ります。近似的な重複についても同様の近道が欲しいところです。この分野の言葉で言えば、局所性鋭敏ハッシュ（locality-sensitive hash）が欲しいのです。

実は、Jaccard類似度に対してそのような手法が存在します。どのように機能するのか見ていきましょう。

Jaccard類似度の近似

まず、2つの文書間のJaccard類似度を近似する問題を考えます。集合全体を調べる必要がなく、各文書について独立に事前計算できる、小さく固定サイズの「シグネチャ」だけを必要とする近似を見つけます。その後、そのシグネチャの構造を利用して、（高い確率で）類似した文書同士が、しかもほとんど類似した文書だけが同じグループにまとまるようなグループ化の方法を見つけます。

MinHashシグネチャ

Jaccard類似度は2つのサイズの比率、つまり2つの入力集合の共通部分と和集合の比率だったことを思い出してください。

$$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*}

ここで一歩引いて、何を達成したかを考えてみましょう。特徴に対する良いハッシュ関数を選べば、各集合について、その特徴のハッシュ値の最小値からなる「シグネチャ」を個別に計算できます。任意の2つの集合が与えられれば、それらのシグネチャの最小値を取ることで、和集合から一様ランダムに引かれた（ある要素のハッシュ）が得られるのです。

私たちが知りたいのは、その要素が共通部分に存在するか、それとも片方に欠けているかです。しかしこの構成により、それは自明になります！ \(x_\textrm{sig}\) はどちらの集合の要素のハッシュ値としても最小のものです。したがって、たとえばそれが集合 \(A\) に存在すれば、それはその集合における最小ハッシュ値でもあるはずです。そして各集合の最小ハッシュ値は――まさに私たちが持っているものなのです！

したがって、実際には \(x_\textrm{sig}\) を計算する必要はなく、単に \(a_\textrm{min} = b_\textrm{min}\) かどうかを問えばよいのです！任意の2つの集合について、この等式が成り立つ確率は \(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} $$

これら2つのシグネチャが与えられれば、何個のハッシュが一致したかを数えることでJaccard類似度を近似できます：

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

一つ注意点を挙げておきます。ここでのハッシュ族の選択は少し微妙です。特徴の全集合上のランダムな置換を近似しようとしていますが、そのような置換の数は極めて急速に増大するため、私たちのハッシュ族がカバーするのは可能な置換のごく一部に過ぎません。ハッシュ族のメンバーが不適切に相関していないことを確認する必要があります――形式的には、ここで重要な性質は「min-wise independence（最小値独立性）」と呼ばれています。幸い、この問題はかなりよく研究されており、文献で効率的な解法が利用可能です。

すべての文書を比較する

これで各文書を、Jaccard類似度を効率的に近似できる \(k\) 要素のハッシュ値フィンガープリントに圧縮できました。

次の課題は、すべての文書ペアを考慮することなく、コーパス全体から近似的な重複――類似度が高い文書――を見つけることです。上でも触れたように、私たちの戦略は、文書をグループ化するための何らかのキーの集合を定義し、各グループ内でのみ完全な比較を行うことです。グループ化キーは、類似した文書が高い確率で同じグループに入り、類似していない文書はそうならないように構成することを目指します。

完全なシグネチャを使う

最も単純な選択は、\(k\) 個すべてのMinHash値をまとめてグループ化キーとして使い、すべてのMinHash値が一致する場合に限り2つの文書を「近似的な重複」とみなすことです。おそらく、上で引用したGPT-3論文が「SparkのMinHashLSH実装を10個のハッシュで使って文書をファジーに重複排除した」と述べているのは、このことを指していると思われます。各文書を特徴に分割し、各文書について10個のMinHash値（10個の異なるハッシュを使います²）を計算し、その10次元ベクトルで文書をグループ化して、グループごとに1つの文書だけを残したのです。

このアプローチの最大の利点は、そのシンプルさと効率性にあります。単一の高カーディナリティなバイト列で文書をグループ化するのは効率的な操作で、水平スケールも容易であり、ほぼすべてのデータ処理ツールキットで基本的なプリミティブとして提供されています（MapReduce における中核的なプリミティブと言ってもよく、mapフェーズとreduceフェーズの間の「シャッフル」として現れます）。

このアプローチはどのように振る舞うでしょうか。単一の文書ペアについて、各MinHash値が一致する確率は \(J(A,B)\) と期待されるので、10個すべてが一致する確率は \(p=J(A,B)^k\) と期待されます。\(k=10\) の場合、それは次のようになります：

また、いくつかの分位点は次のとおりです：

類似度が0.6程度を下回る文書はほとんど衝突せず、0.95付近で一致の確率が大きくなることが分かります。非常に近い兄弟文書だけが問題なのであれば、このアプローチで十分かもしれません。実際、多くのコーパスではJaccard値がかなり二峰性になるのではないかと――未検証ですが――推測しています。つまり、1と0の近くに2つのクラスタができるのです。無関係な文書の類似度は0に近く、類似した文書は大部分が「ほぼ同一」――たとえば記事のわずかに異なる2つのリビジョンや、タイムスタンプやメタデータだけが異なる同じ内容の2つのコピーなど――になります。

また、\(J^{k}\) という計算は単一の文書ペアについて成り立つことも指摘しておく価値があります。すべてが互いに類似した文書が多数ある場合、ペアごとの確率はまったく独立ではありません。実際には、非常に類似した文書が多数ある場合、それらは高々2つか3つのバケットにハッシュされる可能性が高く、ある意味で重複の「ほぼすべて」を見つけることができます。

さらにファジーに

（注：この議論は主に『Mining of Massive Datasets』の3.4節に基づいています。この戦略を自分で試したことはなく、実際にいつ、どのように使われているかも今のところ分かりません）。

もっと「ファジーな」重複を検出したい場合はどうでしょうか。経験的な調査の結果、1に近いものだけでなく、類似度が0.8や0.7を超えるペアを見つけたいと判断するかもしれません。

\(k\) 個のMinHashハッシュのサブセットをグループ化キーとして使うことで、より低い類似度での衝突確率を高め、その後各バケット内で完全なシグネチャを比較して誤った衝突を除外できます。たとえば、最初の4つのMinHash値でグループ化し、衝突した各グループ内ですべてのMinHash値を使って真の類似度を推定するといった具合です。

ハッシュ数を減らすことはある程度までは有効ですが、限界があります。\(J^r\) は常に \(J\) より小さくなり、\(r\) を小さくしすぎると、偽のマッチの割合が許容できないほど高くなります。

代わりにできるのは、文書ごとに複数のキーを生成し、各キーに異なるMinHashのサブセットを使って、各文書をキーごとに1つずつ、複数のバケットに配置することです。シグネチャとして \(k=20\) 個のハッシュを計算するなら、各文書を \(b=4\) 個の異なるバケットに配置し、各キーの構築には \(r=5\) 個のハッシュを使い、その後各バケット内でペアごとに比較する、といった方法です。

2つの文書が少なくとも1つのバケットで一緒にハッシュされる確率はどれくらいでしょうか。

• 単一のキーで2つの文書が衝突する確率は \(J^r\) です
• したがって、そのキーで衝突しない確率は \(1-J^r\) です
• したがって、どのバケットでも衝突しない確率は \(1-J^r)^b\) です

したがって、少なくとも1回衝突する確率は次のようになります：

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

たとえば、上記の例――5つのハッシュを4グループ使う場合――では、確率曲線は次のようになります：

曲線は先ほどの例ほど急峻ではありませんが、左側にシフトすることに成功しました――衝突確率が50%になるのは \(J=0.7\) 付近です。

\(r\) と \(b\) を1より大きくどのように選んでも、結果の曲線はおおむね同様にS字型になることが分かっており、それらの値を変えることで、感度、再現率、パフォーマンスコストの間で豊富なトレードオフの選択肢が得られます。

おわりに

AIの分野で働く以前、私は一般的なアルゴリズムのトリック、特にほとんどの一般的なスケッチアルゴリズムには比較的精通しているつもりでした。しかし、なぜかMinHashには一度も出会ったことがなく、そのようなアルゴリズム（局所性鋭敏ハッシュ）が存在することや実用的であることすら知りませんでした！

このトリックがどのように機能するかを学び、掘り下げるのは本当に楽しかったです。このブログ記事が、より多くのエンジニアにとって初めての出会いとなったり、誰かの理解の隙間を埋める助けになったりすれば嬉しいです。私は、こうした気の利いた数学的・アルゴリズム的なトリックが大好きなのです！

追記：MinHashとHyperLogLog

この記事を調査・執筆している間に、MinHashの中心的なトリックが、古典的でやや有名なスケッチであるHyperLogLogを少し思い起こさせることに気づきました。

HyperLogLogの中核的なアイデア（さらに古いアルゴリズムに遡ります）は、ストリームの各要素をハッシュ化し、結果として得られるハッシュのストリームにおける「先頭のゼロの数」の実行時の最大値を保存することです。

アルゴリズムの詳細は大きく異なりますが、明確な類似点があります。どちらの場合も、ハッシュ関数を使って入力要素を一様分布にマッピングし、次に実行時の極値（最大値や最小値）を計算します。これにより――適切な計算を経て――入力の定数サイズの要約だけを使って、何らかの分布的特性を推定できるのです。

実際、これらのアルゴリズムは一見した以上に似ていると私は考えています。HyperLogLogは先頭のゼロ（最下位桁のゼロ）を数えます。しかし、ハッシュ関数が \([0, 2^N)\) の一様な値を出力すると仮定すれば、ビットの順序を反転させて最上位側のゼロの数を数えると考えても同じことです。Nビットの数 \(x\) が与えられたとき、上位ビットのゼロの数は \(\log_2(x)\) と密接に関連しています――先頭のゼロが多いほど、\(x\) は小さくなります。したがって、HyperLogLogはMinHashの \(H(x)\) に対して、\(log_2(H(x))\) の実行時の最小値を計算していると考えても同じなのです。

さらに、ある意味でHyperLogLogとMinHashは（ある程度）双対であることが分かっています。2つの異なる集合に対する2つのHyperLogLog構造があれば、それらを組み合わせて和集合のサイズを推定できます。一方、それらの集合に対する2つのMinHash構造があれば、それらを比較して共通部分の（相対的な）サイズを推定できます。

したがって、両方の構造を組み合わせれば、任意の集合の共通部分と和集合の両方について問うことができるスケッチを作ることができます！このアイデアは少なくとも2013年には指摘されており、2つのデータ構造のアイデアを興味深い方法で組み合わせたスケッチに関する現在も続く 文献が存在することが分かっています。私はこれが素敵だと思います！

付録：文書を集合として表現する

文書を集合として表現する方法については後で触れると約束したので、2つの一般的なアプローチについて簡単にメモを残しておきます。

まず、これらの戦略のいずれかを適用する前に、文書を何らかの方法で正規化したい場合があります。たとえば、標準的なUnicode正規化形式に変換したり、大文字小文字を同一視したり、連続する空白を畳み込んだり、同様の変換を行いたいかもしれません。

n-gram（別名「shingle」）

文書を、その文書に現れるすべてのn-gramの集合として表現できます。適切な n の値を選びます。大規模テキスト処理の分野では、文献で「n-gram」の代わりに「shingle」という言葉が使われることがよくありますが、私はそれは不必要に紛らわしいと感じています。どんな n の値でも選べますが、主なトレードオフとして、小さい値は文書をより粗く比較する傾向があり（たとえば、ほとんどの英文はバイグラムを通して見るとかなり似て見えるでしょう）、大きい値はより多くの異なる特徴を生成し、したがってより大きな集合になります。ある限界を超えると感度も失われると思いますが、おそらくそれよりも先にパフォーマンスの問題が生じるでしょう。

私が見つけたある情報源³によれば、nが5から9の間の値が、さまざまなアプリケーションで一般的な選択肢のようです。

単語分割

代わりに、入力を「単語」や「トークン」に分割し、それらを特徴として使うこともできます。上記のGPT-3論文からの抜粋で言及されている「Sparkの標準トークナイザー」は、おそらくこのクラスを指していると思われます。このクラスは単に入力を小文字化し、空白で分割するだけです。

より洗練されたトークナイザを使うこともできますし、トークン化した上でトークンのn-gramを使うことでアプローチをハイブリッド化することもできます。その場合、個々のトークンはバイトや文字よりもはるかにエントロピーが高いはずなので、より小さい n の値を使います。

1. SELECT ... FROM table ORDER by random() LIMIT 1 と書いたことがあれば、あなたは似たようなトリックを使ったことがあります！ ↩︎

2. 興味があれば、Sparkはハッシュ族の選択について、関連する文献参照とともに文書化しています。 ↩︎

3. Mining of Massive Datasets §3.2.2 ↩︎