Jaccard類似度とMinHashを用いた類似重複検出
(blog.nelhage.com)- 大規模な文書コレクションでは、Webクローリング中に同じページを複数回取得したり、小さな修正版が混在したりすることがあるため、Jaccard類似度とMinHashは「ほぼ同じ」文書を見つける実用的な方法になる
- Jaccard類似度は、文書を特徴集合に変換したうえで共通部分の大きさ / 和集合の大きさを計算し、しきい値以上のペアを類似重複とみなすが、この関係は一般に推移的ではない
- すべての文書ペアを比較すると、コーパスの大きさに対して**O(n²)**のコストがかかるため、MinHashは各文書を固定サイズのシグネチャに要約し、類似度を確率的に近似する
k個のハッシュ関数を使うと、2つの文書シグネチャで同じ位置の値が一致する比率から類似度を推定でき、ハッシュ関数の選択にはmin-wise independenceのような条件が重要になる- シグネチャ全体またはその一部をグループキーとして使うと、類似文書が同じバケットに入る確率を調整でき、n-gram・トークナイズ方式が検出感度とコストを左右する
類似重複検出の難しさ
- 目標は、大きな文書集合の中から完全に同一ではないが、ほぼ同じ文書を見つけること
- 一定期間Webをクロールすると、同じページを複数回取得しつつメタデータだけが少し異なることがある
- ページの小さな修正版が複数存在する場合もある
- 基本的なアプローチは、2つの文書の間の類似度関数
S(A, B)を定義し、その値がしきい値Scrit以上のペアを類似重複とみなす方法である - 「ほぼ同一」であることは、一般には推移的な関係ではない
AとB、BとCはしきい値以上に類似している可能性がある- その一方で
AとCはしきい値未満であることがある - このため、正確な重複検出よりも大規模な類似重複検出のほうが扱いにくい
Jaccard類似度の定義
-
Jaccard index は、2つの有限集合の類似度を共通部分の大きさ / 和集合の大きさで表す
[ J(A, B) = \frac{|A \cap B|}{|A \cup B|} ]
-
2つの集合が似ていれば、ほとんど同じ要素を持つため、和集合は少ししか大きくならず、共通部分は少ししか小さくならない
-
2つの集合が完全に分離していれば、共通部分の大きさは0なので、Jaccard類似度も0になる
-
2つの集合が同一なら、共通部分も和集合も同じ集合になるため、Jaccard類似度は1になる
-
実際の文書はUnicode文字列のような形なので、まず文書を特徴集合に変換する必要がある
全ペア比較のスケーラビリティ問題
- 文書を特徴集合に変換したうえでJaccard類似度の高いペアを探すという定義自体は単純である
- しかし、すべての文書ペアを比較すると、コストはコーパスの大きさに対して**O(n²)**で増加する
- 正確な重複検出では、文書をハッシュ化して同じハッシュバケットごとにまとめることで、このコストを回避する
- 類似重複検出でも同様の迂回路が必要であり、この分野ではこれを**局所性鋭敏ハッシュ(locality-sensitive hash)**と呼ぶ
- Jaccard類似度にはこの目的に適した手法があり、その中核がMinHashである
MinHashでJaccard類似度を近似する
-
MinHashは、集合全体を毎回比較しなくても、各文書について事前計算した小さな**シグネチャ(signature)**だけでJaccard類似度を近似する
-
基本アイデアは、和集合から一様ランダムに要素を1つ選び、その要素が共通部分にも含まれるかを見るサンプリングである
-
実際にはランダムな順列の代わりに良いハッシュ関数
H(x)を使い、各集合でハッシュ値が最小の特徴を保存する[ a_{min} \leftarrow \min_{x \in A} H(x) ]
[ b_{min} \leftarrow \min_{x \in B} H(x) ]
-
min演算は結合則を持つため、各文書の最小ハッシュ値を独立に前処理できる -
2つの集合の最小ハッシュ値が一致する確率は、2つの集合のJaccard類似度に等しい
複数のハッシュ関数とシグネチャベクトル
-
ハッシュ関数を1つだけ使うと、2つの文書について「同じ/違う」というブール推定しかできない
-
k個の異なるハッシュ関数を使えば、各文書をk個のMinHash値からなるベクトルに要約できる[ A_{sig} = (\min_{x \in A} H_1(x), \min_{x \in A} H_2(x), \dots, \min_{x \in A} H_k(x)) ]
-
2つのシグネチャで同じ位置の値が一致する比率から、Jaccard類似度を近似する
[ J(A, B) \approx \frac{1}{k} \sum_{i=1}^{k} (A_{sig}[i] = B_{sig}[i]) ]
-
ハッシュ関数族の選択は微妙である
- 目標は、特徴空間全体のランダム順列を近似すること
- 実際のハッシュ関数族は、可能なすべての順列のうちごく一部しか表現しない
- 不適切な相関を避ける必要があり、関連する性質はmin-wise independenceと呼ばれる
- この問題は比較的よく研究されており、効率的な解法が文献にある
コーパス全体から候補ペアを見つける
- 各文書を
k個のハッシュ値のフィンガープリントに縮約すれば、Jaccard類似度を効率よく近似できる - 残る問題は、すべての文書ペアを見ずにコーパス全体から類似度の高い文書を見つけること
- 戦略は、文書を何らかのキーでグループ化し、同じグループ内だけで比較するというもの
- グループキーは、類似文書が高い確率で一緒にまとめられ、類似していない文書はできるだけ一緒にまとめられないように設計する必要がある
-
MinHashシグネチャ全体をキーとして使う
- 最も単純な方法は、
k個のMinHash値をすべて1つのグループキーとして使うこと - 2つの文書は、すべてのMinHash値が一致したときだけ類似重複とみなす
- GPT-3論文では、データセット準備パイプラインで類似重複除去を使っており、引用された表現からSparkの
MinHashLSH実装と10個のハッシュを使ったと解釈できる - この方法の利点は単純さと効率性である
- 高カーディナリティのバイト文字列1つでグループ化する処理は、水平スケールしやすい
- MapReduceのmapとreduceの間にある「shuffle」のように、データ処理ツールの基本プリミティブに相当する
- 2つの文書のJaccard類似度が
J(A, B)で、k個の値がすべて一致しなければならないなら、単一ペアに対する衝突確率はJ(A, B)^kである k = 10であれば、類似度がおよそ0.6以下の文書はほとんど衝突しない- 一致確率は類似度がおよそ0.95付近で大きくなる
- 非常に近い文書の兄弟を見つける目的なら、これで十分かもしれない
- この
J^kの計算は単一の文書ペアに対するものである - 非常によく似た文書が多数ある場合、ペアごとの確率は独立ではない
- 実際には、非常によく似た文書群はたいてい2〜3個以下のバケットに入り、重複のほぼすべてを見つけられる
- 最も単純な方法は、
より緩い重複検出
-
類似度が1に近い文書だけでなく、0.8や0.7以上の文書まで見つけたいなら、シグネチャ全体をキーにする方法は厳しすぎることがある
-
k個のMinHashのうち一部だけをグループキーに使うと、より低い類似度でも衝突の可能性が高くなる- たとえば最初の4個のMinHash値でグループ化し、同じバケット内ではシグネチャ全体を使って実際の類似度を推定できる
-
ハッシュ数を減らす方法には限界がある
J^rは常にJより小さいrが小さすぎると、誤った衝突が多くなりすぎる可能性がある
-
その代わり、文書ごとに複数のキーを作って複数のバケットに入れることができる
- たとえば
k = 20個のハッシュを計算し、b = 4個のバケットに入れ、各キーをr = 5個のハッシュで構成できる
- たとえば
-
2つの文書が少なくとも1つのバケットで衝突する確率は次のとおり
[ p = 1 - (1 - J^r)^b ]
-
4個のグループと各グループ5個のハッシュを使う例では、衝突確率が50%になる点はおおよそJ = 0.7付近へ移動する -
rとbがどちらも1より大きい場合、結果の曲線は概ねS字形になり、感度・再現率・性能コストの間を調整する余地を提供する
HyperLogLogとの関連性
- MinHashの中核となるトリックは、HyperLogLog のようなスケッチアルゴリズムと似た点がある
- HyperLogLogはストリームの各要素をハッシュ化し、ハッシュ値における先行0の個数の実行最大値を保存する
- どちらの手法も、ハッシュ関数で入力要素を一様分布に写像したうえで、実行極値を計算し、定数サイズの要約だけで分布的性質を推定する
- HyperLogLogは、ビット順序を逆にして考えると
log2(H(x))の実行最小値を計算する方法と見なせ、MinHashはH(x)自体の最小値を使う - 2つの構造は、ある意味で双対的である
- 2つのHyperLogLog構造を結合すると、2つの集合の和集合の大きさを推定できる
- 2つのMinHash構造を比較すると、2つの集合の共通部分の相対的な大きさを推定できる
- 2つの構造を組み合わせると、任意の集合の共通部分と和集合に関する問いを扱えるスケッチを作れる
- このアイデアは2013年までには知られており、関連する文献や後続研究がある
文書を集合として表現する方法
- JaccardとMinHashを使うには、文字列文書をまず特徴集合に変換しなければならない
- どの方式を使う場合でも、前処理として文書を正規化できる
- 標準のUnicode normalization formに変換する
- 大文字小文字を折りたたむ
- 連続する空白を圧縮する
- これに類する変換
-
n-gramまたはshingle
- 文書は、その中に現れるすべての
n-gramの集合として表現できる - 大規模テキスト処理の文献では「shingle」という語も使われるが、ここでは
n-gramと同じ役割である nの値の選択にはトレードオフがある- 小さい値は文書をより粗く比較する
- たとえば英語テキストの多くは、bigramの観点ではかなり似て見えることがある
- 大きい値は、より識別的な特徴とより大きな集合を作る
- 大きすぎると感度が下がることがあるが、その前に性能上の問題が現れる可能性もある
- Mining of Massive Datasets §3.2.2によれば、多くの応用で
n = 5から9の範囲の値が一般的な選択とされる
- 文書は、その中に現れるすべての
-
単語またはトークン分割
- 入力を「単語」や「トークン」に分割し、それらを特徴として使うこともできる
- GPT-3論文の抜粋はSparkの標準トークナイザに言及しており、これは入力を小文字化して空白で分割するpyspark.ml.feature.Tokenizerを指していると見られる
- より高度なNLTK tokenizerを使うこともできる
- トークン化したあとでトークンのn-gramを使うハイブリッド方式も可能である
- 個々のトークンはバイトや文字よりエントロピーが高いため、この場合はより小さな
nの値を使う
1件のコメント
Hacker News の意見
Jaccard 類似度（Tanimoto 係数）や F1 スコア（Dice 係数）のような集合ベースの指標は、ファジィ集合にも同じように使えるという点がよく見落とされています
ただし、ファジィ集合における共通部分と和集合の概念を表現するのに適切な T-Norm / T-Conorm のペアを選ぶ必要があり、その種類は無数にあります
むしろ、望む意味論に合ったペアを選べるという点では利点です
医用画像セグメンテーションの検証で、セグメンテーション結果と正解が二値マスクではなく確率的／ファジィな形式である場合に、この内容を扱ったことがあります: https://link.springer.com/chapter/10.1007/978-3-319-46723-8_..., https://ora.ox.ac.uk/objects/uuid:dc352697-c804-4257-8aec-08...
通常は 0.5 でしきい値をかけて二値集合を作り、そのうえで Jaccard/Dice の二値版を使いますが、そうすると検証演算子の精度が 2 桁ほど落ちるようです
アルゴリズムが最新手法より 0.001 良いと発表しながら、肝心の検証演算子の誤差範囲が 0.1 である事実は無視している、ということです
フランス政府の大規模データベースで市民レコードを重複排除するために、クライアントがこの手法の独自 Python 実装を作ったことがあり、うまく動作していました
今なら、おそらく datasketch を使うよう勧めたと思います: https://pypi.org/project/datasketch/
調べてみると、このテーマでは新しいツールも引き続き出ていました。たとえば https://pypi.org/project/rensa/ は datasketch の MinHash よりも特化されていて高速なバージョンで、Rust で書かれ、その上に Python を少し載せた形です
私が主著者であることを明記しておきます
仕組みを説明するインタラクティブなチュートリアルも書いてあります: https://github.com/moj-analytical-services/splink, https://www.robinlinacre.com/intro_to_probabilistic_linkage/
datasketch は素晴らしいのですが、私のユースケースには性能が十分ではなく、gaoya は大規模クラスタリングの運用システムで使われています: https://github.com/serega/gaoya
すごい偶然です。ちょうど、誰かが興味を持ちそうな MinHash システムを実装したところです
問題は、大きな正方行列から複数の適切な部分行列の擬似逆行列を見つけることです
Woodbury や Banachiewicz のような行列恒等式を使うと、「近い」部分行列の逆行列を更新して、新しい逆行列を低コストで計算できます
すでに計算済みの逆行列を行／列インデックスをキーとして保存しておき、新しい部分行列ごとに更新の出発点として使える近い既存の逆行列を探せばよいのです
この問題を MinHash で解き、インデックスを最小値ハッシュ処理することで、近い行列どうしが同じハッシュを持つ可能性を高くしました
私の実装では、既存の計算済み逆行列の数が増えるにつれて検索の選択性を調整できるよう、多重解像度ハッシュを使いました
この記事に欠けている背景を少し補うと、この手法は Google の初期にクロール集合の重複排除のために作られたものだと思っていました
LLM を作ることと、普通の Web テキストインデックスを作ることが驚くほど似ている点も興味深いです
Jeffrey Ullman の無料の本 “Mining Massive Datasets” で詳しく読めますし、当時インターネット全体のインデックスを作るために使われた、見事で印象的な手法が多数説明されています
関連資料は “chapter 3 pdf mmds ullman” で検索すれば無料で見つかります
修正: 実は私が間違っていて、Wikipedia によれば DEC が AltaVista 向けに発明したとのことです: https://en.wikipedia.org/wiki/MinHash
いずれにせよ Ullman の本には良い説明があり、Google でどのように使われたかも扱っています
MinHash とその変種を理解しようとしても頭に入りにくかったので、オンライン可視化ツールを作っています: https://websla.sh/tools/minhash
まだ完成しているわけではなく、Jaccard 類似度の計算なども見せたいのですが、今でも複数の文字列を入力して「minhash」が実際に何なのかを自分で見ることができます
ハッシュや小さなニューラルネットワークをベクトル検索エンジンおよび Tanimoto/Jaccard と組み合わせて使う方式は、大規模データセットの重複排除では非常に一般的な戦略です
線形計算量の MapReduce ジョブを使うより賢い場合があります
Google の良いプロジェクトとして、50 万パラメータの RETSim モデルと USearch エンジンを使う事例があります: https://github.com/google/unisim
いま PostgreSQL で似たような問題があります。
feed_itemsが 600000 件あり、スキーマは(feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer)です。特に一部のニュース項目の
contentとsummaryカラムは非常によく似ていますが、同一ではありません。こうしたニュース項目が2つ与えられたときに1つにまとめたいのですが、良い方法はありますか？
大まかな手順は次の通りです。
各行ごとに、ステップ2の配列と同じ長さの「minhashed」整数配列を得ることが目標です。グローバル配列の長さを64として宣言すれば、各行の MinHash 配列も長さ64になります。
うまくいっていれば、この配列を展開して「ソース行」とし、各バケット化された MinHash 値でデータセットを自分自身と join すると、「対象行」カラムが追加されます。
ソース/対象カラムでグループ化して出現回数を数えれば、2つの行がどれだけ似ているかを推定できます。
本質的には、2つの項目が似たバケットにハッシュされるほど類似しており、どの時点から実際のペアごとの Jaccard 類似度やコサイン類似度を計算するかは自分で決めればよいです。
時間予算がどれくらいあるかがポイントです。
2つの項目が非常によく似た テキストを共有していると見るなら、Levenshtein 距離を試す価値があります。
そうすれば Jaccard 類似度を使えます。
記事が気に入りました。NVIDIA で私たちのチームが最近、説明されている ファジー重複排除アルゴリズムの GPU アクセラレーション版を公開しました。このコミュニティも関心を持つのではないかと思います。
リポジトリはこちらです: https://github.com/NVIDIA/NeMo-Curator/
ファジー重複排除スクリプトのドキュメントはこちらにあります: https://docs.nvidia.com/nemo-framework/user-guide/latest/dat...
Python の例もあります: https://github.com/NVIDIA/NeMo-Curator/blob/main/examples/fu...
フィードバックを聞きたいです。
こういう手法は文章で読んでも理解しにくいですが、動くコード例に自分のデータを何度か入れて内部の流れを見てみると、すぐに吸収できるタイプのものです。
この手法は Douglas Eck から初めて学びました: https://research.google/people/douglas-eck/
Google で楽曲クラスタリングに使われていて、ハッシュ化とランダムベクトルについて話していたのを覚えています。
当時は、ランダム性の少ない最適化の方がうまくいくはずだと思っていたので混乱しました。
ここにバンディングと簡単な確率を加えると、巨大なデータセットで Jaccard 類似度を安価かつ非常に並列化しやすい方法で近似できます。
ドキュメントのクラスタリングやデータセットの重複排除手法として見たとき、これより単純な離散アルゴリズム的な方式と比べて、「問題に 機械学習を投入する」アプローチは品質と性能の面でどの程度なのでしょうか？
例えば、事前学習済みの LLM エンコーダで文書ベクトル埋め込みを作り、そのベクトルをベクトル DB に入れてから k-means でクラスタリングする方式です。
k-means を行うには、依然として Jaccard のような距離関数を選ぶ必要があり、k-means は近接重複にはおそらく理想的ではありません。
MinHash を k-means の前処理として使って高速化することもできます。
ベクトル DB が大きな助けになるとは思いません。
数億件の文書があるなら MinHash スケッチ検索を高速化するために使えるかもしれませんが、たいていは過剰な選択である可能性が高いです。
文書を埋め込むたびに、追加する前に近似最近傍を検索するので、MinHash と同じく O(N) です。
HNSW や PQ のようなベクトルインデックスは、コサイン距離向けの MinHash に相当する SimHash LSH よりも、性能/品質のトレードオフが優れています。
品質は、近接重複を何として定義するか、どの埋め込みモデルを使うかに依存します。
最新モデルはうまく機能しますし、ラベル付きデータがあればファインチューニングでさらに良くできます。
主な欠点は、すべての文書を埋め込む追加コストで、特に長い文書では負担が大きいことです。
しかし小型モデル、より良い最適化、より高速なハードウェアのおかげで、このコストは非常に急速に下がっています。