Deduplication: 重複排除
概要
Deduplication（重複排除）は、Dolma 3 データセットのキュレーションにおける中核的なプロセスである。兆トークンスケールのデータセットにおいて、重複したコンテンツを効率的に識別・削除することで、訓練の効率性と品質を向上させる。Dolma 3 では、3 段階の重複排除戦略を採用し、38.7B 文書を 9.7B 文書まで削減した（文書数で 75% 削減）。
重複排除の目的と動機
トークン効率的な訓練
重複排除の主な目的は、トークン効率的な訓練を実現することである:
- 計算コストの削減: 同一または類似のコンテンツを複数回訓練することは、計算リソースの無駄遣いである
- メモリ効率: 重複データを削除することで、より多様なデータをメモリに保持可能
- 訓練時間の短縮: 冗長なデータを排除し、より効率的な訓練サイクルを実現
重複数は品質の弱いシグナル
重複の頻度は、コンテンツの品質を示す弱いシグナルとして機能する:
- 高品質コンテンツ: 多くの場合、一度だけ出現する（オリジナルコンテンツ）
- 低品質コンテンツ: スパム、ボイラープレートテキスト、テンプレート化されたコンテンツは複数のサイトで繰り返される傾向がある
- Web スクレイピングの副産物: 同一コンテンツが複数のドメインにコピーされる現象（ミラーサイトなど）
複数回の繰り返しは収穫逓減
同一のコンテンツを複数回訓練することは、収穫逓減の法則に従う:
- 1 回目: モデルが新しいパターンと知識を学習
- 2 回目: 追加的な学習効果が減少
- 3 回目以降: ほとんど追加的な利益がなく、過学習のリスクが増加
3 段階の重複排除戦略
Dolma 3 では、異なる粒度での重複を対象とした 3 つの段階を組み合わせている。
Stage 1: Exact Deduplication（完全重複排除）
目的: 完全に同一の文書を識別・削除
手法:
- 文書全体のテキストハッシュ（SHA-256 など）を計算
- ハッシュが完全に一致する文書を重複として識別
- グローバル重複排除: すべてのデータソース間で実施
結果:
- 削減率: 67% のデータを重複として識別
- 文書数: 38.7B 文書から 12.8B 文書に削減
- 対象: 完全コピー、ミラーサイト、クローラーの重複取得
完全重複排除は計算コストが低く、ハッシュベースの実装により大規模データセットでも高速に動作する。この段階だけで文書数の 2/3 以上を削減できることは、Web データの重複度の高さを示している。
Stage 2: Fuzzy Deduplication（曖昧重複排除）
目的: ほぼ同一の文書（ヘッダーやフッターのみが異なる文書）を識別・削除
手法: MinHash ベースのアルゴリズム
MinHash は、文書間の Jaccard 類似度を効率的に推定する手法である:
- Shingling: 文書を n-gram（通常は 5-gram や 13-gram）に分割
- MinHash 署名: 各文書に対して固定長の署名を生成
- LSH (Locality-Sensitive Hashing): 類似した署名を持つ文書ペアを効率的に発見
- クラスタリング: 類似度が閾値を超える文書をクラスタ化し、各クラスタから 1 つのみを保持
対象となる重複:
- 異なるドメイン間でコピーされた文書: ニュース記事、ブログ投稿など
- テンプレートベースのコンテンツ: 同一のヘッダー/フッターを持つ文書
- 軽微な編集が加えられたコンテンツ: 日付や名前のみが異なるバージョン
結果:
- 削減率: 23% のデータを重複として識別
- 文書数: 12.8B 文書から 9.8B 文書に削減
MinHash は、文書間の完全な比較（O(n^2) の計算量）を回避し、LSH により O(n) に近い計算量で類似文書を発見できる。これにより、数十億規模の文書に対しても実用的な時間で重複排除が可能になる。
Stage 3: Substring Deduplication（部分文字列重複排除）
目的: 個別文書内の繰り返しコンテンツ（ボイラープレートテキスト、HTML アーティファクト）を削除
手法: Fuzzy suffix-array ベースのアルゴリズム
Suffix array は、文字列の全ての接尾辞を辞書順にソートしたデータ構造である:
- Suffix array 構築: 各文書に対して suffix array を構築
- 繰り返し検出: 500 バイト以上の繰り返し部分文字列を識別
- マーキングと削除: 繰り返し部分をマークし、訓練データから除外
対象となる重複:
- ボイラープレートテキスト: ナビゲーションメニュー、フッター、サイドバー
- HTML アーティファクト: スクリプトタグ、スタイル定義の残骸
- 繰り返しパターン: リスト項目、テーブルデータの反復
結果:
- 削減率: 14% のテキストバイトを削除
- 文書数: 9.8B 文書から 9.7B 文書に削減（文書数自体はほぼ維持）
- データサイズ: 最終的に 36.5T バイトに削減
Stage 3 は文書数をほとんど削減しないが、各文書の品質を大幅に向上させる。ボイラープレートテキストや HTML アーティファクトは、モデルが学習すべき有用な情報をほとんど含まないため、これらを削除することで訓練の効率性が向上する。
Duplodocus ツール
Dolma 3 の重複排除を実現するために、Duplodocus という新しいツールを開発した。
技術的特徴
Native Rust 実装:
- 高性能: メモリ安全性を保ちつつ、C/C++ に匹敵する実行速度を実現
- 並列処理: Rayon などの Rust のエコシステムを活用した効率的な並列化
- メモリ効率: 所有権システムにより、メモリリークやデータ競合を防止
大規模分散実行:
- スケーラビリティ: 数十億規模の文書を処理可能
- 分散ハッシュテーブル: 複数ノード間でハッシュテーブルを分散し、メモリ制約を緩和
- ストリーミング処理: 全データをメモリに読み込むことなく、ストリーミング方式で処理
統合された機能:
- Hash-based exact deduplication: SHA-256 ハッシュによる完全重複排除
- MinHash fuzzy deduplication: Jaccard 類似度ベースの曖昧重複排除
- カスタマイズ可能: パラメータ（n-gram サイズ、類似度閾値など）を柔軟に調整可能
Duplodocus のワークフロー
┌───────────────────────────────────────────────────────────────┐
│ Duplodocus Workflow │
├───────────────────────────────────────────────────────────────┤
│ Input: 38.7B documents │
│ | │
│ v │
│ Stage 1: Hash-based exact deduplication │
│ | - Compute SHA-256 hash for each document │
│ | - Remove duplicates │
│ | - Output: 12.8B documents (67% reduction) │
│ | │
│ v │
│ Stage 2: MinHash fuzzy deduplication │
│ | - Generate MinHash signatures │
│ | - LSH for candidate pairs │
│ | - Cluster similar documents │
│ | - Output: 9.8B documents (23% reduction) │
│ | │
│ v │
│ Stage 3: Suffix array substring deduplication │
│ | - Build suffix arrays │
│ | - Detect repeated substrings (>=500 bytes) │
│ | - Mark and remove │
│ | - Output: 9.7B documents (14% byte reduction) │
│ | │
│ v │
│ Output: 9.7B documents, 36.5T bytes │
└───────────────────────────────────────────────────────────────┘最終結果
3 段階の重複排除プロセスにより、以下の結果を達成した。
削減統計
| 指標 | 初期値 | 最終値 | 削減率 |
|---|---|---|---|
| 文書数 | 38.7B | 9.7B | 75% |
| データサイズ | - | 36.5T バイト | - |
段階別の削減率:
- Stage 1 (Exact): 67% の文書を削除
- Stage 2 (Fuzzy): 残りの 23% を削除
- Stage 3 (Substring): 14% のバイトを削除
Quality-aware Upsampling の基盤
重複排除されたデータは、Quality-aware Upsampling の基盤として機能する:
- クリーンなデータプール: 重複が排除された 9.7B 文書から高品質文書を選択
- 品質スコアの信頼性向上: 重複データが品質分類に与えるノイズを削減
- 効率的な繰り返し: 高品質文書のみを選択的に繰り返すことで、全体的な繰り返しを最小限に抑制
重複排除により、Dolma 3 Mix は以下の最適化が可能になった:
- トピック分類の精度向上: 重複データのノイズを削減
- 品質スコアの信頼性: より正確な品質評価が可能
- アップサンプリングの効率化: 高品質データの選択的な繰り返し
詳細は ?@sec-quality-upsampling を参照。
他の重複排除との比較
C4 (Colossal Clean Crawled Corpus):
- 主に exact deduplication に依存
- Fuzzy deduplication は限定的
- 結果: より多くの近似重複が残る可能性
The Pile:
- データソースごとに異なる重複排除戦略
- 一部のソースは重複排除なし
- 結果: データソース間の一貫性が低い
RedPajama:
- MinHash ベースの fuzzy deduplication を採用
- Substring deduplication は実施せず
- 結果: 文書内のボイラープレートが残る
Dolma 3 の優位性:
- 3 段階の包括的アプローチ: Exact、Fuzzy、Substring の全てを実施
- グローバル重複排除: すべてのデータソース間で統一的に実施
- スケーラビリティ: Duplodocus により兆トークンスケールで高速実行
- オープン性: ツールとパイプラインを完全公開
まとめ
Dolma 3 の重複排除は、以下の特徴を持つ:
主な成果:
- 大規模削減: 38.7B 文書から 9.7B 文書へ（75% 削減）
- 3 段階の戦略: Exact、Fuzzy、Substring の包括的アプローチ
- 高性能ツール: Duplodocus による効率的な大規模処理
技術的革新:
- Native Rust 実装による高性能
- 分散実行によるスケーラビリティ
- Suffix array ベースの substring deduplication
下流への影響:
- Quality-aware upsampling の基盤を提供
- 訓練効率の大幅な向上
- モデル品質の改善
重複排除は、Dolma 3 データセットの品質と効率性を実現する上で不可欠なプロセスであり、Olmo 3 モデルの成功に大きく貢献している。