SoftMatcha 2: 1兆語規模コーパスの超高速かつ柔らかい検索

トップ国際会議 ICML に採択された論文「SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora」の解説資料です。1.4 兆語規模コーパスの類似語検索をわずか 0.3 秒で。その裏にあるアルゴリズムを含め、わかりやすく解説いたします。

なお、本資料は言語処理学会および NLP コロキウムでの発表を加筆修正したものです。

Transcript

1. SoftMatcha 2 1兆語規模コーパスの超高速かつ柔らかい検索 東京大学修士 2 年 米田優峻 (@e869120)
2. 自己紹介 2 米田優峻 / E869120 • 2021 年 東京大学入学 • 2023 年 東京大学理学部情報科学科に進学 • 2025 年 修士課程に進学 主な実績 大学対抗プログラミングコンテスト (ICPC) ‘25 世界大会 2 位 著書累計 10 万部突破
3. 諸注意 • 本講演資料は、 言語処理学会 2026 での口頭発表 (3/10)、 および NLP コロキウムでの発表 (4/1) で用いた資料をより分かりやす く修正したものとなります 。 • 情報科学に関心のある高校生でも理解できるように書いたの で、 ぜひお読みいただければと思います 。 • なお 、 論文は https ://arxiv.org/pdf/ 2602 .10908 にあります 3
4. はじめに 4
5. はじめに • SoftMatcha 2 は、 1 兆語規模の大規模なテキストデータ (このよ うなデータをコーパスと言います ) の中から 高速に類似語検索を 行う ツールです • まずは、 次ページのデモをご覧ください 5
6. オリンピック金メダルと検索すると … → 0.05 秒で類似語が表示！
7. 書き方の多様性と検索 → 同様に類似語が表示！
8. もっと長い文字列でも、一瞬で類似語が表示！
9. さらに、具体的な用例も表示できる！
10. これが今回作成した SoftMatcha 2 となります
11. 背景 11 文字列検索は以前から大きなニーズがあり その大きな理由として、応用範囲が広いことが挙げられる 情報検索 (Google 等) LLM の意図せぬ 挙動の追求 ベンチマーク 汚染の検出
12. しかし、既存の文字列検索では … 12 規模と 利便性 の両立が困難！
13. 既存の検索ツール 13 誤解を恐れずに書くと、既存の検索ツールは 2 つに大別 概要 手製爆弾の場合の 検索例 利点・欠点 完全一致検索 あいまい検索
14. 既存の検索ツール 14 概要 手製爆弾の場合の 検索例 利点・欠点 完全一致検索 完全一致 のみを出力 手製爆弾 あいまい検索 誤解を恐れずに書くと、既存の検索ツールは 2 つに大別
15. 既存の検索ツール 15 概要 手製爆弾の場合の 検索例 利点・欠点 完全一致検索 完全一致 のみを出力 手製爆弾 あいまい検索 意味や表記 揺れも検出 手製爆弾 手製爆薬 (類語) 手製の爆弾 (挿入) 誤解を恐れずに書くと、既存の検索ツールは 2 つに大別
16. 既存の検索ツール 16 誤解を恐れずに書くと、既存の検索ツールは 2 つに大別 しかし、規模と利便性を両立したものはない！ 概要 手製爆弾の場合の 検索例 利点・欠点 完全一致検索 完全一致 のみを出力 手製爆弾 1 兆語規模になるが 類似語検索できない あいまい検索 意味や表記 揺れも検出 手製爆弾 手製爆薬 (類語) 手製の爆弾 (挿入) 類似語検索できるが 10 億語規模が限界 ※密ベクトル検索は例外だが、非常にゆるい結果が返ってくるので、利便性に劣る
17. 本研究の貢献 17 そこで本研究では、新たな手法を提案し 類似度上位 20 件のあいまい検索で 兆語で 秒を達成！
18. 手法 18
19. 類似度の定義 • 類似度上位 20 件の単語を出力するには、パターン間の類似度を 定義する必要がある 19
20. 類似度の定義 • 類似度上位 20 件の単語を出力するには、パターン間の類似度を 定義する必要がある • 類似度はどのように定義するか？ →単語間類似度を使おう！ 20
21. 知識: 単語間のコサイン類似度 • 単語間の類似度を求める方法として、コサイン類似度がある 21 コサイン類似度とは (1/2) 単語には、 意味の関係性を右図のようにベクト ルで表したものがあり 、 単語ベクトルという いちご みかん 野菜 地震 台風 の は
22. 知識: 単語間のコサイン類似度 • 単語間の類似度を求める方法として、コサイン類似度がある 22 コサイン類似度とは (2/2) 単語には、 意味の関係性を右図のようにベクト ルで表したものがあり 、 単語ベクトルという その単語ベクトルの角度の cos 値をコサイン類 似度という 角度が小さいほど cos 値が高く 、 類似度が高い いちご みかん 野菜 地震 台風 の は コサイン 類似度 0.92
23. 類似度の定義 23 まずは「 1 文字パターン」の類似度から考えよう 1 文字の単語の類似度は、当然単語間類似度と同じ 日本 アメリカ 0.67 67 % 類似度 単語間類似度
24. 類似度の定義 24 しかし、 2 単語以上でどうするかという問題がある → 概ね「類似度の最小値 ※」を計算結果とする オリンピック 金メダル 五輪 銀メダル 0.81 79 % 類似度 0.79 ※今回の場合、 0.79 と 0.81 の最小値である 79% を採用
25. 類似度の定義 25 ただし、その方法では最小の単語以外の影響が反映されないので 実際には softmin を使う (後述; 79% ではなく 73% になる ) オリンピック 金メダル 五輪 銀メダル 0.81 73 % 類似度 0.79
26. 類似度の定義 26 挿入削除がある場合は、単語ごとにペナルティを掛ける 情報量のない単語 (“の” など ) ほど影響が小さい オリンピック 金メダル 五輪 の 銀メダル 0.81 51 % 類似度 0.79 挿入 0.7 倍 73% ×0.7 倍
27. 補足: softmin とは何か ここで、 softmin は最小値を少し柔らかくしたもの • イメージとしては以下 • [80%, 100%, 100%] の softmin は 80% ( 他が 100% だと最小値と同じ ) • [80%, 85%, 90%] の softmin は少し下げた約 74% • [80%, 80%, 80%] の softmin は更に下げた約 69% 厳密には、以下の式で表される (𝛼 = 104 に設定) 27 𝑠𝑜𝑓𝑡𝑚𝑖𝑛 𝑥1 , … , 𝑥𝑚 = 1 − log𝛼 1 + ෍ 𝑖=1 𝑚 𝛼1−𝑥𝑖 − 1
28. 補足:なぜ softmin か？ 28 単純な合計 softmin 単純な min 1 単語が全然違っても 上位に来てしまう 類似度がバランスよく 反映される 最悪の単語以外の差が 反映されない 1 単語でどれくらい決まるか 低 高 クエリ : Player 1 上位: Best 1 クエリ : Gold Medal Gold Medals Silver Medals 同類似度
29. そこで、どうやって 類似度の高いパターンを 検索するのか？
30. 手法の概要 30 まず、類似度が一定以上の単語を列挙 (閾値は上位 20 件ちょうど取れそうな値に設定 ) 1 類似度 50% 以上の パターンを列挙 2 完全一致検索で 存在を判定 3 20 件あれば終了 なければ閾値下げ • 完全自動運転 • 完全手動走行 • ほぼ自動運転 • 全て自動的運転 完全自動運転 完全手動走行 ほぼ自動運転 全て自動的運転 50% 47% 完全自動運転 の検索例
31. 手法の概要 31 次に、パターンの候補について コーパス内に存在するかどうかを、完全一致検索で判定 1 類似度 50% 以上の パターンを列挙 2 完全一致検索で 存在を判定 • 完全自動運転 • 完全手動走行 • ほぼ自動運転 • 全て自動的運転 完全自動運転 完全手動走行 ほぼ自動運転 全て自動的運転 3 20 件あれば終了 なければ閾値下げ 50% 47%
32. 手法の概要 32 もし 20 件以上得られれば、それを類似度順にを出力 そうでなければ、閾値を下げて手順 1 からやり直し 1 類似度 50% 以上の パターンを列挙 2 完全一致検索で 存在を判定 3 20 件あれば終了 なければ閾値下げ • 完全自動運転 • 完全手動走行 • ほぼ自動運転 • 全て自動的運転 完全自動運転 完全手動走行 ほぼ自動運転 全て自動的運転 50% 47%
33. しかし、その方法を単純に使うと … 手順 1 で列挙するパターンの 数が多すぎる！
34. しかし、その方法を使うと …？ 34 上位 15 件の類似語※ だけでも、 3 単語で 15 ×15 ×15 = 3375 通り → 毎秒 1000 回の完全一致検索が出来ても 3 秒かかる！ 完全 すべて 全て 無欠 ほぼ 自動 自動的 無人 瞬時 手動 運転 運行 走行 教習 同乗 ※厳密には softmin なので微妙に違うが、簡単のため各単語上位 15 件の組み合わせを列挙する場合を考える
35. しかし、その方法を使うと …？ 35 4 単語になると、 15 ×15 ×15 ×15 = 約 5 万通り → 毎秒 1000 回の完全一致検索が出来ても 1 分かかる！ 人工 知能 の 開発 人為 知能 人造 天然 人間並 知性 頭脳 人間 は で から その 研究 製造 建設 改良
36. しかし、その方法を使うと …？ 36 5 単語になると、 15 ×15 ×15 ×15 ×15 = 約 76 万通り → 毎秒 1000 回の完全一致検索が出来ても 13 分かかる！ 情報 化 社会 の 実現 は で から その 最新 耳寄り 有益 関連 具現 顕在 弱体 細分 福祉 政治 経済 通念 叶い 達成 両立 追求
37. そこで、本研究では 逐次的枝刈りという 独自の工夫を採用
38. 逐次的枝刈りの例 38 手順 0 今回は、完全自動運転と検索した場合の例を考える
39. 逐次的枝刈りの例 39 手順 1 単純にやると、まず類似度一定以上の候補を列挙して … 完全 ほぼ 無欠 完全 手動 ほぼ 手動 無欠 手動 完全 自動的 完全 自動 ほぼ 自動的 ほぼ 自動 無欠 自動的 無欠 自動 完全 自動 運転 完全 自動 走行 完全 手動 運転 完全 手動 走行 完全 自動的 運転 完全 自動的 走行 ほぼ 自動 運転 ほぼ 自動 走行 ほぼ 手動 運転 ほぼ 手動 走行 ほぼ 自動的 運転 ほぼ 自動的 走行 無欠 自動 運転 無欠 自動 走行 無欠 手動 運転 無欠 手動 走行 無欠 自動的 運転 無欠 自動的 走行
40. 逐次的枝刈りの例 40 手順 2 そして、各候補について、コーパスに存在するかを判定 完全一致検索をたくさん行う必要がある！ 完全 ほぼ 無欠 完全 手動 ほぼ 手動 無欠 手動 完全 自動的 完全 自動 ほぼ 自動的 ほぼ 自動 無欠 自動的 無欠 自動 完全 自動 走行 完全 手動 運転 完全 自動的 運転 完全 自動的 走行 ほぼ 自動 運転 ほぼ 自動 走行 ほぼ 手動 運転 ほぼ 手動 走行 ほぼ 自動的 運転 ほぼ 自動的 走行 無欠 自動 運転 無欠 自動 走行 無欠 手動 運転 無欠 手動 走行 無欠 自動的 運転 無欠 自動的 走行 完全 自動 運転 完全 手動 走行
41. そこで、逐次的枝刈りでは 1 文字ずつ調べていく
42. 逐次的枝刈りの例 42 手順 1a まず、 1 単語目「完全」の類似語を列挙 完全 ほぼ 無欠
43. 逐次的枝刈りの例 43 手順 1b 完全一致検索を行い、コーパスにないものを消す 完全 ほぼ 無欠
44. 逐次的枝刈りの例 44 手順 2a 次に、 2 単語目「完全自動」までの類似語を 1 単語目から伸ばして列挙 完全 ほぼ 無欠 完全 手動 ほぼ 手動 完全 自動的 完全 自動 ほぼ 自動的 ほぼ 自動
45. 逐次的枝刈りの例 45 手順 2b 完全一致検索を行い、コーパスにないものを消す 完全 ほぼ 無欠 完全 手動 ほぼ 手動 完全 自動的 完全 自動 ほぼ 自動的 ほぼ 自動
46. 逐次的枝刈りの例 46 手順 3a 完全 ほぼ 無欠 完全 手動 ほぼ 手動 完全 自動的 完全 自動 ほぼ 自動的 ほぼ 自動 完全 自動 走行 完全 自動 運転 完全 手動 走行 完全 手動 運転 ほぼ 自動 走行 ほぼ 自動 運転 次に、 3 単語目「完全自動運転」までの類似語を 2 単語目から伸ばして列挙
47. 逐次的枝刈りの例 47 手順 3b 完全 ほぼ 無欠 完全 手動 ほぼ 手動 完全 自動的 完全 自動 ほぼ 自動的 ほぼ 自動 完全 自動 走行 完全 自動 運転 完全 手動 走行 完全 手動 運転 ほぼ 自動 走行 ほぼ 自動 運転 完全一致検索を行い、コーパスにないものを消す
48. 考えるべきパターンの数が 大幅に減った！
49. その他の工夫として 完全一致検索自体の 高速化も実施
50. 完全一致検索自体の高速化 • 完全一致検索の高速な解法として 、 接尾辞配列が知られている • しかし 、 単純な実装では 、 ディスク上のランダムアクセスが数 十回※ 必要 (1 兆語規模ではデータがメモリに収まらず 、 アクセ スが遅いディスクに載せる必要がある ！) • そこで今回は 、 独自の 2 段階のページング法 を利用し 、 ランダ ムアクセスを事実上 1 回に削減！ 50 ※厳密には、コーパスサイズ n に対して log n 回。 1 兆語の場合は約 40 回
51. 実験方法
52. 実験設定 コーパス • FineWeb -Edu (1.4 兆語) を中心に、複数言語で実験 環境 • AWS i4i.32xlarge を使用 (128 コア／ 1024GB RAM ／30TB SSD) テストデータ • 英語 400 ケース、その他各 100 ケース (いずれも最大 10 単語) • 実行時間の平均値／ワースト 5% を測定 52
53. 結果
54. 検索例 54 文字列 類似度 olympics gold medalist 100.0% olympics gold medallist 89.1% olympic gold medalist 86.4% olympics silver medalist 84.8% : 文字列 類似度 東京から大阪までの 2時間半 100.0% 東京から大阪まで の2時間半 87.5% : 東京から 仙台までが 13時間半 52.3% : まず、上の例の通り、類義語や挿入・削除を含めた単語が 英語・日本語の両方で出力できている
55. 検索時間 (1/3) 55 検索時間は、 FineWeb -Edu (1.4 兆語) に対して 0.090 秒 中央値 0.278 秒 ワースト 5%
56. 検索時間 (2/3) 56 左に示す通り 、 コーパスサイズが増えても 実行時間はほぼ一定 (日本語・ 中国語でも同 様の結果※) 既存手法を大きく圧倒 • 通常モードは 、 500 億語でメモリ超過 (1024 GB にすら収まらず ) • ディスクモード比 600 倍以上高速化 ※詳細は p.3 の arXiv 論文を参照
57. 検索時間 (3/3) 57 さらに、完全一致検索の時点でも 既存手法 (EMNLP ‘25 best paper) を圧倒 0.3 ミリ秒 提案手法 11.1 ミリ秒 Infini -gram ※1 ミリ秒 = 0.001 秒
58. 応用実験
59. 応用実験 • SoftMatcha 2 では非常に高速かつ便利な検索ができる • しかし 、 それだけでなく 、 情報検索や大規模言語モデル、 生成 AI への応用可能範囲も広い 59
60. ベンチマーク汚染とは？ 応用実験 • 今回は応用実験の 1 つとして 、 大規模言語モデル (LLM) の評価 に利用されている ベンチマークの汚染 を調査 60 ChatGPT のような生成 AI の開発では、 学習用データとしてコーパスが用い られるが 、 そのコーパスの中に (ベンチマークの ) 問題がほぼそのまま入って いることがある →その場合、 実質カンニング状態になる 。 これをベンチマーク汚染という
61. 応用実験 • 今回は応用実験の 1 つとして 、 大規模言語モデル (LLM) の評価 に利用されているベンチマークの汚染を調査 • これまでは 、 完全に一致している汚染しか検出されず • 果たして 、 微妙な表現の違いや挿入削除 (コンマの有無など ) を 含めた汚染を検出することが出来るのか ？ 61
62. 結果 62 7 種類のベンチマーク 2,564 問中 完全一致汚染 338 件に加えて 18 件 類似汚染 11 件 数値替え を 8割超※ の的中率で発見 ※汚染と判定した 36 件のうち、実際の汚染が 29 件 (18+11) 、擬陽性が 7 件。グラフは arXiv 論文参照
63. 面白い汚染の例 1 MMLU ベンチマーク • 問題文: The difference between dc and ac in electric circuits is that in dc, charges flow • コーパス : The difference between DC and AC in electric circuits is that in DC, charges flow in one direction . in が抜けていて 、 直後に答えが書いてある ！ 63
64. 面白い汚染の例 2 MATH ベンチマーク • 問題文: The sum of two numbers is 25 and their difference is 11. What is the larger of the two numbers? • コーパス : The sum of two numbers is 139 while their difference is 19 . What is the larger of two numbers? (以降答えが続く ) 数値が変わっているが 、 問題自体は同じ ！ 64
65. まとめ
66. 講演のまとめ • 本研究では、 生成 AI の学習データとして用いられるような 1 兆 語規模コーパスの中から 、 高速に類似語検索を行うツールであ る SoftMatcha 2 を作成した • 1.4 兆語データで検索時間 0.3 秒未満を達成 • さらに 、 応用実験としてベンチマーク汚染の実験を行った 66
67. 最後に • 本研究では、 2,000 億語規模の デモが公開されています • 爆速が体感できます 。 ぜひご体 験ください ！ 67