🪄

LLM 向け MinHash でテキストの重複除去のメモ

2023/07/23に公開

dedup

重複除去

minhash

tech

LLM 向けデータセットでは, 重複や繰り返し(repeatation)が少ないことが重要となります.

Scaling Laws and Interpretability of Learning from Repeated Data
https://arxiv.org/abs/2205.10487

Deduplicating Training Data Makes Language Models Better
https://arxiv.org/abs/2107.06499

CCNet(LLaMa などで使われた), RefinedWeb(Falcon)でも dedup は重要な役割を果たしています.

情報

基本は Suffix Array で exact match と MinHash(LSH, Locally Sensitive Hash)で fuzzy match でテキストの重複除去を行うのが昨今(2023/07 時点)での主流のようです.
(SimHash は遅いので大規模では使わないっぽ?)

Shingle, Shingling = 小(?)集合 = 屋根のタイル(繰り返し模様のピース)の意味合いのようです.
(Single と見間違いしやすくややこしいネ)

N-grams を Shingle ともいうようです.

https://en.wikipedia.org/wiki/N-gram

MinHash

https://en.wikipedia.org/wiki/MinHash

AltaVista なつかしー! DEC 64bit Alpha はいい石じゃった...
(ARPANET 時代からのインタネット歴 50 年の 68 才主ふの感想)

ハッシュを用いた類似検索技術とその応用

Python での最小例

基本は↑の text-dedup を参考にしてみます.

とりま datasketch つかってみます.

$ python -m pip install datasketch

日本語の場合は分かち書き(単語に分解)したほうがいいような気もしますので, 分かち書きしてみます.
SudachiPy 使ってみます. モードは B がいいでしょうか.

from datasketch import MinHash

from sudachipy import tokenizer
from sudachipy import dictionary
tokenizer_obj = dictionary.Dictionary().create()

text1 = "東京は元気です"
text2 = "東京は晴れ"
text3 = "吾輩は猫である"

# Use mode B
split_mode = tokenizer.Tokenizer.SplitMode.B
toks1 = [m.surface() for m in tokenizer_obj.tokenize(text1, split_mode)]
toks2 = [m.surface() for m in tokenizer_obj.tokenize(text2, split_mode)]
toks3 = [m.surface() for m in tokenizer_obj.tokenize(text3, split_mode)]

print("data1", toks1)
print("data2", toks2)
print("data3", toks3)

m1, m2, m3 = MinHash(), MinHash(), MinHash()
for d in toks1:
    m1.update(d.encode('utf-8'))
for d in toks2:
    m2.update(d.encode('utf-8'))
for d in toks3:
    m3.update(d.encode('utf-8'))
print("Estimated Jaccard for data1 and data2 is", m1.jaccard(m2))
print("Estimated Jaccard for data1 and data3 is", m1.jaccard(m3))

s1 = set(toks1)
s2 = set(toks2)
s3 = set(toks3)
actual_jaccard1 = float(len(s1.intersection(s2)))/float(len(s1.union(s2)))
actual_jaccard2 = float(len(s1.intersection(s3)))/float(len(s1.union(s3)))
print("Actual Jaccard for data1 and data2 is", actual_jaccard1)
print("Actual Jaccard for data1 and data3 is", actual_jaccard2)

data1 ['東京', 'は', '元気', 'です']
data2 ['東京', 'は', '晴れ']
data3 ['吾輩', 'は', '猫', 'で', 'ある']
Estimated Jaccard for data1 and data2 is 0.375
Estimated Jaccard for data1 and data3 is 0.109375
Actual Jaccard for data1 and data2 is 0.4
Actual Jaccard for data1 and data3 is 0.125

Voila!
いい感じに類似性が算出できました(数値が高いほうが似ている)

実践

実際のところは, 文(ドキュメント)から N 単語づつ取り出して処理して重複判定するようです.

や,

RefinedWeb の論文(G.3)

https://arxiv.org/abs/2306.01116

Deduplicating Training Data Makes Language Models Better
https://arxiv.org/abs/2107.06499

あたりを参考にしてみてください.

N-gram

3 or 5 がよく使われるようです.

The Stack では 5-gram.

英語だと単語ごとですが, 日本語だと分かち書きしたもの単位がいいかしら.
また, 句点は含めません.

さらなる高みへ

pyspark

spark というなんか pandas っぽいデータ解析ツール(Java でつらい...)で minhash 計算できるので, pyspark でそれを使って高速化できるでしょう. 詳細は text-dedup のコード見てみてくださいネ

C++ 化

さらに速度欲しい場合, pure C++ で書くのも手でしょう.

simdjson(JSON parse)
murmurhash3(hash 関数)

あたりでいけそう.

情報