※本記事は、Stanford大学のCS336「Language Modeling from Scratch」コース（Spring 2025）のLecture 14「Data 2」の内容を基に作成されています。本講義は、Percy Liang氏（スタンフォード大学コンピュータサイエンス准教授、基盤モデル研究センター（CRFM）ディレクター）とTatsunori Hashimoto氏（スタンフォード大学コンピュータサイエンス助教授）によって行われました。
Stanfordのオンライン人工知能プログラムの詳細については https://stanford.io/ai をご覧ください。本コースの受講に関する情報は https://online.stanford.edu/courses/ で確認できます。コースのスケジュールとシラバスについては https://stanford-cs336.github.io/spri... をご参照ください。
本記事では、講義の字幕情報を基に内容を要約・解説しております。内容は原講義の見解を正確に反映するよう努めていますが、要約や解釈による誤りがある可能性もありますので、正確な情報や文脈については、オリジナルの講義動画をご視聴いただくことをお勧めいたします。コース全体のプレイリストは「Stanford CS336 Language Modeling from Scratch」でご確認いただけます。
1. フィルタリングアルゴリズム (Filtering Algorithms)
1.1 フィルタリングの基本概念と要件
これは2回目のデータに関する講義です。前回の講義では、BERTの訓練に使用されたデータセットから、HOMOまで、様々な言語モデルの訓練に使用された異なるデータセットについて歴史的な概観を行いました。その中で私が強調したかったことの一つは、データは空から降ってくるものではないということです。
データは多くの場合、ライブサービスに存在しており、明示的にクロールまたはダンプされる必要があります。そして、大量の処理が必要になります。この処理には、生のHTMLをテキストに変換すること、あらゆる種類の品質と言語、毒性のフィルタリング、重複除去などが含まれます。
この講義では、特に品質フィルタリングと重複除去がどのように機能するかの仕組みについて深く掘り下げたいと思います。まず、フィルタリングのための異なるアルゴリズムを見ていきます。これらは主にモデルベースです。つまり、分類器を訓練するか、フィルタリングするために何らかのモデルを訓練します。次に、このプリミティブがあらゆる種類の異なるタイプのフィルタリングに使用できることを示します。最後に、重複除去のためのいくつかのアルゴリズムを見ていきます。
この講義は少し異なり、古典的なビッグデータ処理アルゴリズムに多く焦点を当てます。そして皆さんの一部には楽しい数学も含まれるでしょう。
フィルタリングアルゴリズムから始めましょう。基本的な高レベルの図はこうです。あなたには何らかのターゲットデータが与えられており、それはあまり多くありません。それが高品質なデータだとしましょう。そして、あなたには大量の生データがあります。これをCommon Crawlだと想像してください。あなたの目標は、その生データのサブセットを見つけることです。それをT'と呼びましょう。これはTに類似したものです。
これは、基本的にどんなフィルタリングパイプラインでも認識すべきパターンです。このフィルタリングアルゴリズムに何を求めますか？明らかにTから汎化してほしいのです。あなたはすでにTを持っているので、全く同じデータTを取得することに意味はありません。したがって、何らかの汎化が必要です。そして、極めて高速である必要もあります。例えば、ウェブ全体でそれを実行する必要があります。これが巨大なモデルを実行しているなら、それは訓練と同じくらい高価になる可能性があります。それは確実に避けたいことです。そうでなければ、むしろ訓練した方が良いかもしれません。
この高レベルな抽象的プリミティブを実装する3つの異なる方法を見ていきます。
1.2 N-gramモデルによるフィルタリング
n-gramモデルの訓練から始めます。これは前回の講義で出てきたものです。Kneser-Ney平滑化を使ってn-gramモデルを訓練できます。他の形式の平滑化も使用できますが、Kneser-Neyはn-gram種類のモデリング統計的言語処理時代から受け継がれています。この分野で人々が使用する傾向がある特定の実装があり、KenLMと呼ばれています。これはオープンソースで、もともと機械翻訳のために開発され、Kneser-Ney平滑化を実装しています。Kneser-Neyについて読むことができ、非常に興味深いのですが、ここではあまり詳細については話しません。
これはデータフィルタリングで非常に人気があります。特にこれでなければならない特別な理由はありませんが、これが人々が使用するものです。n-gramモデリングの良い点は非常にシンプルなことです。私がモデルの適合と言うとき、これをn-gramの数を数えて、正規化することと考えるべきです。
少し深く掘り下げてみましょう。出発点は言語モデルの最尤推定です。テキストのコーパスがあり、条件付き確率を推定したいとします。例えば、最後のn-1語「the cat」が与えられたときのnの確率です。あなたがすることは、n-gramの数を数えて、条件付きコンテキストのn-1グラムの数で割ることです。これは原理的には非常に簡単です。
これを効率的に実装するには少し作業が必要です。しかし、主な問題はスパースなカウントがあることです。多くのn-gramは、非常に妥当であるにもかかわらず、特にnが大きくなると、正確に0回しか現れません。これが、n-gramモデルが適切にスケールできなかった理由の全体でした。なぜなら、次元の呪いに直面するからです。
これを緩和するために、一部の人々は見たことのないn-gramを処理するためにKneser-Ney平滑化を考案しました。これについてより詳細がありますが、大まかに言うと、このカウントをサポートするのに十分なデータがない場合、低次のn-gramを使用できると言っています。コンテキストから一つの単語を削除し、「cat」が与えられたときに「in」が現れる回数を数え、それに補間またはバックオフしようとします。
n-gramモデリングがどのように動作するかについてはこれで全てです。ニューラル言語モデルの時代であっても、n-gramモデルがどのように動作するかを知ることは良いことだと思います。
n-gramをダウンロードしましょう。これはWikipediaで訓練されたモデルです。ダウンロードして、いくつかの文を通してみましょう。
この文は「Stanford University was founded in 1885」です。これは実際にWikipediaから取った抜粋です。したがって、妥当であるべきです。確率を計算すると、まずlog probを計算し、次にこの正規化によってパープレキシティを計算すると、187が得られます。それは何らかの数値です。
そして、ここに別の例があります。これはCS 336のウェブサイトから取ったものです。どの程度うまくいくか見てみましょう。これはより高いパープレキシティで、可能性が低いということを意味します。このようなものはWikipediaに実際には現れないので、理にかなっています。異常に高くないのは、まだかなり良い形の英語だからです。そして、そこにある多くのn-gramも、Wikipediaに現れると思います。
ASDFはどうでしょうか？これは単なるでたらめで、より高いパープレキシティが割り当てられます。そして「da, da, da, da」があります。これはかなり高いパープレキシティが割り当てられるはずです。しかし、何らかの理由で、この特定のn-gramはかなり低いパープレキシティを割り当てています。これはn-gramモデルなので、特に賢くも良くもありません。
しかし、最良のモデルは必要ありません。モデルを作成するためのデータフィルタリングをしているだけです。これは非常に粗雑で高速でも構いません。
CCNetは、当時はFacebookだったと思いますが、そこから出た論文です。前回話したものです。彼らは基本的にこれを行い、実際に—段落のテキストを見ました。それらがアイテムで、パープレキシティの昇順で段落をソートし、上位3分の1だけを保持しました。これが最初のLlamaデータセットを作成するために使用したものです。これはヒューリスティックですが、何かを本当に素早く書き下ろさなければならない場合、これは理にかなっています。
Kneser-Ney言語モデリングは高速ですが、粗雑です。
ターゲットデータにn-gramモデルを適合させ、それを使用して生データをスコア化し、最高スコアの文書を選択できます。
1.3 Fasttextを用いた線形分類器
もう一つできることはfasttextです。これはある意味で、より人気があります。これもFacebookからのものです。彼らは多くのオープンソースツールをリリースしましたが、KenLMは、それより前に作られたと思います。ここで、彼らはテキスト分類のためにそれを開発しました。この論文は2016年のものです。多くの人々があらゆる種類の高度なニューラルモデルを開発していました。そして彼らは、まあ、実際にはほぼ線形分類器がうまく機能することを示しました。はるかに高速でした。そのため、ソフトウェアパッケージは実際に非常に人気になりました。
ここでの動機は、例えば、bag-of-words分類を行っている場合でした。長さLの文があり、語彙サイズがV、64クラスに分類したいとします。すると、すぐにこのV×Kの行列を定義する必要があり、VとKが両方とも大きい場合、これはかなり大きくなり、スパース性の問題に陥ります。動作方法は、文書を取って、線形分類を行うことです。
これはかなり単純です。問題は、パラメータ数が巨大なことです。fasttextは、まあ、線形的な—基本的に次元削減を行いましょうと言います。代わりに、語彙空間を隠れ次元にマッピングします。これはKより小さく、おそらく16より小さく、それからHから分類します。
予測、順伝播を見ると、非線形性がないことに注意してください。単なる線形分類器です。望むなら行列分解と考えることもできます。そして、パラメータ数は大幅に削減されます。実装は、かなり最適化されていると思います。並列化されており、非同期SGDを使用しています。
質問は、これはbag-of-wordsです。単語だけでなく、n-gramも見たいのです。この論文は、n-gramにもかなりシンプルな方法で拡張しています。文を取って、n-gramに分割します。ここで、問題はbigramの数がかなり大きくなる可能性があることです。実際に無制限になる可能性があります。トークナイザーについて話したときのことを思い出してください。
単語に分割するだけなら、どれだけの単語があるかはわかります。シンプルなことは、ハッシュ化を行うことです。いくつかのビン数を定義します、おそらく1000万ですが、この例では8です。そして、すべてのbigramをそれにハッシュ化します。「the cat」は2にマップされ、「cat in」は1にマップされ、というようにです。もちろん、いくつかの衝突があるかもしれませんが、それに耐えます。
ある意味で、損失を最小化するとき、衝突は考慮されます。互いに何の関係もない2つの単語がある場合、重みは何らかの形でおそらくその2つの平均を表すことになるでしょう。また、多くの場合、K=2クラスでfasttext分類を使用することに注意してください。この文書は良いか悪いか？その場合、これは通常の基本的に二値分類、線形分類です。
もちろん、BERTやLlamaのような高級なモデルを使用できることを想像するのにあまり想像力は必要ありません。唯一のことは、それが遅くなるということです。したがって、分類に巨大なモデルを使用する場合、実際にモデルを訓練するためにそれらのフロップを使用すべきかもしれないというトレードオフに陥ります。それが唯一の懸念です。ウェブは非常に大きいからです。
そして覚えておいてください、あなたはウェブをかなり絞り込んでいます。そのため、分類器に多くの計算を費やすことになります。ウェブの1%に絞り込んでいるとしましょう。つまり、あなたが費やす計算量は、データセットを順伝播させることの100分の1でなければならないということです。
1.4 重要度サンプリング (Importance Sampling)
私が話す最後の手法は、重要度サンプリングを使用した言語モデルのためのデータ選択と呼ばれるものです。ここでの基本的なアイデアは、生データセットRがあり、ターゲットデータがあるということです。そして、重要度重み推定器を構築します。これは、言語n-gramモデルやfasttext分類器の類似物です。そして、それを使用して多くの文書を取得します。
まず、重要度リサンプリングの簡単な復習をしましょう。これは粒子フィルタリングやモンテカルロ手法など、多くの文脈で現れます。ターゲット分布があります。これは分布であり、データセットではありません。理想的にはここからサンプルを抽出したいのですが、サンプルを抽出できる提案分布Qしかありません。
例えば、語彙が0、1、2、3の場合、これがターゲット分布だとしましょう。そして提案分布がこれだとします。あなたがすることは、Qからサンプルすることです。なぜなら、それがサンプルできる唯一のものだからです。いくつかのサンプルを取得するとしましょう。Qは0により多くの質量を持っているので、より多くの0を取得することに注意してください。
そして、あなたがすることは、この重要度比p/qを見ることによって、サンプルに対する重みを計算することです。qからサンプルしたという事実を補正しようとしています。そのため、それを割りたいのですが、実際にはpが欲しいのです。そして正規化して、サンプルに対する分布を取得します。そして、リサンプルして、分布のバランスを取ります。
今度は、pが3により多くの確率分布質量を持っていたので、より多くの3があることがわかります。これはかなり基本的ですが、構成要素です。
データ選択をどのように行うかに移りましょう。分布ではなく、ターゲットデータセットがあります。小さなデータセットがあります。そして、この生データセット、提案データセットDqと呼ぶものもあります。これは大きなものです。DpにpフィッタをθすることができるでしょうDqにq分布をフィッタして、先ほど話した重要度サンプリングを実行できます。
主な問題は、Dpが本当に小さいことです。ターゲット分布は高品質データだということを覚えておいてください。あなたはそれをあまり持っていません。それが全体のポイントです。より多くのそれを取得しようとしています。
それをあまり持っていないのです。そして、良いモデルを推定するには小さすぎます。そこで、アイデアは、ハッシュn-gramを使用することです。これは、fasttextでも既に見たものです。持っているテキストを取って、それから本質的に—今はunigramを行っています。各unigramをハッシュ化します。
そして、基本的にすべての—ハッシュされたn-gramの確率を推定します。この場合、「the cat in the hat」がこれにハッシュされます。「the hat」と「hat」が同じ値にハッシュされるハッシュ衝突があることに注意してください。しかし、まあいいでしょう。これは全て粗雑です。そして、これらのそれぞれの確率を推定します。
そして、新しいテキストの確率を評価するために、新しいテキストをハッシュ化し、確率を掛け合わせます。少し運が悪く、確率がゼロになってしまいました。望むなら、多少の平滑化を行うことができます。Pythonでは、ハッシュが非決定的であることがわかります。これを実行するたびに、何か他のものを取得することになります。
論文は、これが実際に少し役立つことを示しています。利得はそれほど大きくありません。しかし、ヒューリスティック分類であるfasttextと比較して、BERTスタイルモデルを使用したglueベンチマークでの利得があります。いくらかの向上があります。
fasttextとの比較です。ここでの主なアイデアは、分布全体をモデル化することが、ある意味で、より原理的なアプローチだということです。なぜなら、あなたの分布からデータをサンプルしたく、異なる分布qがあるからです。そして今、本質的に補償しようとしています。そのため、これは多様性にとってより良い可能性があります。なぜなら、分布を一致させようとしているからです。一方、fasttextでは、本質的に何かが分布内にあるかどうかを分類しようとしています。そして、分布の一致について何の保証もありません。
しかし、fasttextのように高速でもあります。そして、どちらもより良いモデルを持つことによって改善できます。n-gramに基づく線形モデルを使用する代わりに、nを増やすことができます。ニューラルアプローチも使用できます。
1.5 フィルタリング手法の統一的フレームワーク
この部分をまとめるために、n-gramモデル、線形分類器、重要度サンプリングを見てきました。しかし、一般的なフレームワークは、おそらく取り去る価値があるものだと思います。それは、ターゲットデータセットと生データセットが与えられ、ターゲットに類似したサブセットを見つけるというセットアップです。
これらすべての手法は基本的なレシピを持っています。それは、生データとターゲットデータセットに基づいて何らかのモデルを推定し、それがスコアリング関数を与え、そのスコアリング関数に基づいて生データセット内の例を保持するというものです。通常、高いスコアが保持されます。
KenLMケースでこれを説明しましょう。スコアは単純にターゲット下での確率、またはトークン数で正規化したい場合はパープレキシティです。ここではrは使用されません。そして、スコアが閾値より大きい例を保持します。望むなら、閾値周辺で少し無作為化することもできます。
判別分類器を使用することもできます。この場合、スコアは、この例が生データセットではなくターゲットから来た確率です。そして、スコアが閾値より大きい例を保持します。
重要度サンプリングでは、スコアは2つの生成モデルの比率です。この場合、n-gramモデルになる可能性があります。ターゲット分布対生分布のpです。このスコアを使用するために、これは実際に重要度重みです。その比率に比例した確率でリサンプルします。
高いレベルでは、すべてが本質的に同じことを行っています。生と対照的にターゲットのように見えるものを教える何らかの分布を適合させ、それを生データセットに適用します。
ここで一時停止して、何か質問があるかもしれません。
ちょっとした高レベルの哲学的なことです。良いデータとは何かというアイデアがありますが、実際にそれがどのようなものか、良い文書がどのように見えるかについてはあまり話していません。これが行っていることは、n-gramモデルのような環境で単語が隣同士にフィットすることを確認することです。一つが他の後に来る時です。しかし、より大きなレベルで意味をなすことを保証するものではありません。それが必要な場合は、nを増やしてn-gramにしますか？
質問は、n-gramモデルを使用している場合、ローカルなコンテキストのみを見ているということのようです。そして、品質を評価するのにはそれは良くないかもしれません。すべてをシャッフルしても、n-gramモデルには良く見えるからです。確実に、敵対的に操作するのは非常に簡単だという危険があります。n-gramモデルが高いと思う例を構築することは確実にできます。
私が示したものの一つは、たまたまかなり高いものです。しかし、何らかの形で、平均的にはうまくいっています。ある意味で、文書が文法的な英語のように見え、ニュースや科学論文のように見える場合、そのモデルがそれに高い確率を割り当てることを確認したいだけです。悪い例をいくつか得ても、世界の終わりではありません。
そうです。これらを、あなたが本当にナンセンスなウェブページをフィルタリングアウトするものとして考えるべきです。
真のナンセンスをフィルタリングアウトすることは、これを見る良い方法だと思います。いくつかの例を見ていく中で、これらの分類器が品質だけに使用されるわけではないことが、おそらくもう少し明確になると思います。他のいくつかの使用例では、なぜそれが機能すべきかがもっと説得力があると思います。
2. フィルタリングの応用
2.1 言語識別 (Language Identification)
同じデータフィルタリング機構を異なるタスクで使用することができます。言語識別、品質フィルタリング、毒性フィルタリングについて話します。
言語識別では、特定の言語のテキストを見つけたいということです。おそらく英語、おそらく日本語です。そして、すべての言語で訓練すればいいではないかと問うかもしれません。なぜそうしないのですか？
問題は、特定の言語で高品質データのキュレーションと処理を行うことがしばしば困難であることです。また、あなたが一つの言語のみを気にしている場合の問題もあります。他のすべての言語からのデータがある場合、特定の言語、その言語に対してより少ない計算とトークンを費やすことになります。そして、それがその言語でのパフォーマンスを損なう可能性があります。
例えば、2022年頃に訓練されたと思いますが、bloomはわずか30%の英語で訓練されました。その結果、英語のパフォーマンスは本来あるべきほど良くなかったかもしれません。他の言語では強力でした。そこで、計算制約のあるレジームでは、あなたが気にしている言語の品質を確実に損なうリスクがあります。
とは言え、十分な容量があり、巨大なモデルを訓練している場合、多言語モデルを確実に訓練でき、言語間で正の転移すら起こる可能性があります。フロンティアモデルはすべて大部分多言語で訓練されており、時には100以上の言語、100以上の言語で訓練されています。
これを行う一つの簡単な方法はfasttextです。fasttextはシンプルな分類器を訓練するためのツールキットです。また、既製のモデルもいくつか付属しています。通常使用されるものの一つは、言語識別モデルを持っていることです。
これは単なる既製の分類器です。多くの異なる言語をサポートしており、基本的にWikipediaを含む多言語サイトで訓練されました。Wikipediaは多くの異なる言語を持っており、翻訳サイト、そして何らかの理由で東南ヨーロッパのニュースでも訓練されました。
DOMAはこれを使用します。基本的にfasttext分類器を実行し、英語確率が0.5より大きいページを保持します。
試してみましょう。ダウンロードできるlanguage IDというモデルがあります。そして、どの程度うまくいくか見てみましょう。「The quick brown fox jumps over the lazy dog」です。予測がどこにあるか見てみましょう。これは英語と言っています。これがラベル、英語です。そして英語の確率は0.71です。もっと高いと思ったでしょう。私にはかなり英語に見えます。
文を複製しても、確率は変わりません。これは良いことです。同じことを言っても、より英語になるわけではありません。カジュアルな英語があります。これは奇妙です。これは、the quick brown foxより英語らしいです。
ドイツ語は、実際にかなり分類されます。すみません、これはドイツ語です。ラベルはドイツ語になっています。それはドイツ語です。数学は英語として比較的弱く分類されます。コードは最も高いのがロシア語のようです。「Hello」は明らかにイタリア語です。これはフランス語です。「Bonjour」です。それは良いです。そして、これは—私が思うに、スペイン語も英語も入れた難しいものです。この場合、スペイン語を支持するようです。
これで感覚がつかめます—つまり、これらの分類器で遊んでみるのは常に良いことです。分類器だからといって、ダウンロードできて、誰もが使っているからといって、常に機能するとは限りません。明らかに、短い文では、何が起こっているかについての情報が少ないので、信頼性が低いと思います。低リソース言語は困難です。実際に—方言の英語について、これが英語ではないと見なされる可能性があるという懸念があります。類似した言語を区別したい場合も、それも簡単に混同される可能性があり、コード切り替えもあります。真実が何なのかわかりませんが、うまくいけば、言語の一つになるでしょう。
一つのケーススタディについて話すと、open web mathは2年前のこの論文でした。ここでの目標は、数学的テキストの大きなコーパスをキュレートすることでした。ここで、私は数学を言語だと仮定して言っています。
まず、彼らはフィルタリングにいくつかのルールを使用しました。次に、proof fileと呼ばれる証明の大きなデータセット上でKenLMを訓練し、パープレキシティがある閾値以下の場合に保持しました。
そして、私たちが話してきたfasttext分類器を訓練して、数学的な書き方を予測しました。これはハックですが、分類器の閾値を設定しました。ルールに基づいて数学と識別された場合は、比較的低くします。ルールに基づいて数学と識別されない場合は、より高くする必要があります。
その結果、150億トークンを生成し、実際には指定されていない20倍多いデータで訓練されたモデルよりも良い成績を収めるモデルを訓練しました。これはデータフィルタリングの有用性の良い例の一つです。すべてのデータで訓練することもできます。
しかし、数学のような特定のドメインを気にする場合は、出かけて行ってより多くのそれを取得し、そのデータセットをターゲットにすることができます。そしてそれで訓練すれば、はるかにデータ効率的になることができます。
2.2 品質フィルタリング (Quality Filtering)
品質フィルタリングについて話しましょう。品質フィルタリングは、明らかに実際には—つまり、多くのもののキャッチオールであり、品質とは何かということです。いくつかの論文はモデルベースの品質フィルタリングを明示的に使用しないことを覚えておいてください。しかし、より最近の論文は単に諦めて、まあ、はるかに良く機能するだけだと言っています。
GPT-3については前回少し話しましたが、彼らが持っていた高品質ソース、または彼らが持っていたCommon Crawl以外のソースから正例を取ることによって品質分類器を訓練しました。負例は単にCommon Crawlです。彼らは線形分類器を訓練し、このスコアに基づいて確率的に文書を保持します。これは数値を基本的に閾値を鋭くするものです。
最初のLlamaペーパーでは、Wikipediaによって参照されたページを使用しました。Wikipediaそのものではなく、正例として使いました。負例はCommon Crawlからサンプルされたもので、正に分類された文書を保持しました。実際にはサンプリングはなかったと思います。これは興味深いことです。
phi-1は、彼らの哲学が興味深い別の論文です。彼らは教科書のように見える本当に高品質なデータを望んでおり、非常に小さなモデルを訓練したかったのです。そこで、彼らは合成データでも訓練しましたが、フィルタリングされたデータでも訓練しました。フィルタリングされたデータについては、stackのPythonサブセットを取りました。
stackを覚えておいてください。これはGitHubからのコードの前処理されたデータセットです。そして、彼らはプロンプトを定義しました。これは効果的に、基本的なコーディング概念を学ぶことが目標である学生にとっての教育価値を決定するようGPT-4に求めました。
そして、彼らはGPT-4にプロンプトを送り、このPythonサブセットから10万の文書を分類しました。それが正例になりました。彼らはこれらの例でランダムフォレスト分類器を訓練しました。ランダム分類器に供給された埋め込みは、何らかの事前訓練されたモデルからのものでした。そして、彼らは分類器によって分類されたRからデータを選択しました。分類器を実行し、全てのRに対して実行し、そのデータを取得しました。
これは興味深いことです。なぜなら、ランダムフォレスト分類器があるからです。この場合、Tはどこから来るのでしょうか？Tは先験的に存在しません。Tは何らかのプロンプトでGPT-4にプロンプトすることから来ます。
これは、モデルが良くなるにつれて、ますます見るようになることです。Books1は素晴らしいかもしれない、またはWikipediaは素晴らしいかもしれないというソースを見る代わりに、良いモデルがあれば、欲しいデータの種類をモデルに単純に尋ねることができます。もっと化学データが欲しいかもしれないし、多くの証明や初等数学などを行うもっと数学的なデータが欲しいかもしれません。そして、かなり洗練された言語モデルにTを与えてもらいます。Tを得たら、これまで話してきたレシピに変わります。
phi-1の結果は、再び良く見えます。彼らはベースラインを持っていました。stackのPythonサブセット、これがRだったものを単に取りました。コーディングデータセットであるhuman evalでのパフォーマンスは、96Kステップの訓練後でわずか12%でした。そして、この新しい高級データセットで全く同じモデルアーキテクチャを訓練しました。36後にはすでに17でした。そこで、彼らは成功を宣言しました。
これらは品質フィルタリングのいくつかの例です。
品質フィルタリングについて何か質問はありますか？
ターゲットデータセットでLLMを使用して最も高価なモデルを使用することから逃れることができるのに、あなたが—LLMを使用しないで使用する—[聞き取れない]
そうです。なぜここでGPT-4を使用することから逃れることができるのかというポイントです。10万の例を作成するためだけに使用しているからです。そして作成するために—そして、はるかに高速な分類器を蒸留するためにそれを使用しています。10万は、おそらく数千万または数億のRのサイズよりもはるかに少ないです。
2.3 毒性フィルタリング (Toxicity Filtering)
毒性フィルタリングについて少し話しましょう。DOMAペーパーがどのように毒性フィルタリングを行うかについて話します。
Jigsaw Toxic Commentsと呼ばれるデータセットがあります。これは、人々がオンラインでより良い議論を持てるよう支援しようとするプロジェクトから生まれました。問題のあるコンテンツがいつあるかを識別できる分類器を構築したかったのです。
彼らはデータ、Wikipediaのトークページのコメントを取り、アノテーターにtoxic、severe toxic、obscene threat、insult、identity hateでアノテートさせました。DOMAの人々は2つのfasttext分類器を訓練しました。一つは基本的にヘイトに対応し、もう一つはNSFWに対応しています。
データセットのいくつかの例がこちらです。モデルをダウンロードして試してみましょう。
最初の例は「are you threatening me for dispute neutrality?」です。これはsafe for workと分類されます。問題ないように見えるからです。そして2番目のものはNSFWとしてフラグが立てられます。これらの文は両方とも問題ありません。感覚をつかんでもらうためです。あまり多くの例を見せたくありませんが、アイデアは分かるでしょう。自分の時間で試すことができます。
フィルタリングについては以上です。
3. 重複除去 (Deduplication)
3.1 重複の種類：完全重複と近似重複
重複除去について話しましょう。重複には2つのタイプがあります。完全重複と近似重複です。認識すべきことは、ウェブは実際にミラーリングに基づいて本質的に多くの完全重複を持っているということです。Project Gutenbergを見ると、全く同じサイトが多くの異なるURLでミラーされているのがわかります。
Common Crawlが行うようにクロールするだけだと、これらがミラーであることを知る方法がなく、全く同じコンテンツを取得することになります。そして近似重複があります。これは基本的に、数トークンで異なる同じテキストです。両方を扱うアルゴリズムをお見せします。
近似重複はいつ起こるでしょうか？利用規約とライセンス、MITライセンスのようなものがあります。これはウェブ上に何回現れるかわからないほど存在します。あらゆる場所にコピー&ペーストされています。おそらく—わからないですが。おそらく人々がそれを取って実際に何かを変更したり、混乱してコピー&ペーストして、コンマを削除したりすることもあります。それは全て可能です。
そして場合があります—これらのデータセットを見ると、近似重複は—近似重複がどのように見えるかのアイデアを与えてくれます。
時々、この記事があり、誰かが「best actor in a negative role」を「most impactful character」に言い換えたようですが、他の全ては同じに見えます。これは単にここにコンマが欠けているだけです。そのコンマがどこに行ったのか本当にわかりませんが、単なるアノテーター処理エラーの可能性があります。
そして、これは興味深いものです。明らかにこの非常に広告的なテキストがあり、カナダをUSAに置き換え、他のフライトも置き換えています。これはおそらく何らかのテンプレートシステムから生成されており、エンティティをスロットに入れています。
これらの近似重複は明らかに異なります。しかし明らかに、大量の—この文書を持ったら、この文書はあまり価値を与えません。そう言っておきましょう。
極端な場合、C4を見ると—C4は英語のように見える文を探すルールのセットに基づいてフィルタリングされたことを覚えておいてください—実際に英語であるこの文が、驚くべきことに61,000回現れているのがわかります。何らかの理由で、実際にこれがどこから来るかを追跡すると、MITライセンスではありません。
これは、落書きマスクの絵があるAmazonのランダムな製品で、このテキストがあります。そして明らかに、これは—何らかの理由で、61,000のコピーがある理由がわからないのですが、それがそれです。
アイデアは、このテキストが必ずしも悪いということではありません。完璧に良い英語です。しかし、これに対して61,000エポックを取りたくはありません。単に無意味だからです。
重複除去は品質フィルタリングの補完的なものです。品質フィルタリングは、このデータ片を決して訓練したくないと言います。重複除去は、まあ、これは良いかもしれないが、61,000コピーではなく、少数だけが欲しいと言います。
重複除去により言語モデルが向上することを示す研究があります。最初の最も明白なことは、より効率的に訓練できることです。重複除去はトークン数を減らします。情報を捨てていなければ、多くの労力を節約できます。そして第二に、暗記も回避できます。
これについてはあまり話していませんが、データで訓練された言語モデルは、そのデータを暗記することができます。これは著作権やプライバシーの理由で悪いことです。訓練セットを再生成することができるからです。重複除去は一つのツールです。完璧では決してありませんが、これらのリスクの一部を軽減するのに役立ちます。
3.2 重複除去の設計空間
重複除去を設計空間の観点から考える方法がこちらです。まず、重複除去する単位について考える必要があります。アイテムとは何でしょうか？文でしょうか？段落でしょうか？文書でしょうか？
2番目の質問は、どのようにマッチするかです。何が重複と考えられるでしょうか？完全一致でしょうか？共通サブアイテムの割合でしょうか？
そして最終的なことは、どのようなアクションを取るかです。すべてのインスタンスを削除するのか、1つだけ残してすべてを削除するのか、ということです。
重要な挑戦、これはアルゴリズムの挑戦ですが、重複除去は根本的にアイテムを他のアイテムと比較することについてだということです。品質分類では、アイテムを取って、それを高品質か否かで分類することができます。重複除去は根本的にペアワイズなものです。
そして覚えておいてください、これらのデータセットは大きいです。何か2次的なことをしようとすると、それは一種のノーゴーです。スケールするために線形時間アルゴリズムが必要ですが、それでもペアワイズな何かを行う必要があります。
これすべての構成要素はハッシュ関数です。復習として、ハッシュ関数は、文であったり文書であったりするアイテムを、ハッシュ値にマップする関数です。ハッシュ値は整数や文字列です。値はアイテムよりもはるかに小さいものです。
ハッシュ関数について関連することは、潜在的にハッシュ衝突を起こす可能性があることです。これは、同じハッシュ値にマップされる2つの異なるアイテムがあることを意味します。一般的に、皆さん全員が辞書やハッシュテーブルを使用したことがあると思いますが、ハッシュ衝突は一般的に悪いものです。
しかし後で見るように、実際に限定的な量であれば良いものになり得ます。多くの種類のハッシュ関数があり、効率性と衝突耐性の間でトレードオフします。衝突耐性は衝突しないということを意味します。
暗号学的ハッシュ関数があり、これらはBitcoinのような、セキュリティに敏感なアプリケーションで使用されます。本当に衝突を望まないのです。そうでなければ、誰かがあなたのお金を盗んだり、物事を危険にさらしたりする可能性があるからです。これらは遅いです。しかし、衝突耐性はないが高速なハッシュ関数もあります。これらは一般的にハッシュテーブルで使用されます。
ここではクリプトグラフィーを行っているわけではないので、高速性を望み、一般的に後者のカテゴリーを使用します。文字列を取って値を返すMurmurHashと呼ばれるものを使用します。しかし、他の多くのハッシュも使用できます。
3.3 完全重複除去：ハッシュ関数とBloom Filter
完全重複除去から始めましょう。シンプルな例です。アイテムは単なる文字列で、完全一致が欲しく、1つだけ残してすべて削除したいとします。アイテムの束があります。
最初にすることは、ハッシュ値からそのハッシュを持つアイテムのリストへのマッピングを計算することです。それができたら、各グループから1つのアイテムを保持します。各グループはハッシュ値に対応し、完全一致の場合、ハッシュ衝突がないと仮定すると、基本的に完全重複除去を行います。「hello」がここに2回現れ、今度は1回現れます。
もちろん、「Hello」（大文字の感嘆符付き）は完全に異なるアイテムです。完全一致を行っているからです。
良い点は、これが非常にシンプルなことです。何をしているかは明確です。高精度です。つまり、必要でなかった、または必要だったものを決して捨てることはありません。
しかし、欠点は近似重複には機能しないことです。他の良い点は、これが実装するのに非常にシンプルなことです。MapReduceの方法でこれを書きましたが、スケールして並列化することがかなり簡単です。これは実際にC4がデータセットを準備するために使用するものです。
彼らの重複除去の単位は3文スパンです。完全一致を使用し、1つだけ残してすべて削除します。私をいつも悩ませているが、他の誰も気にしていないように見える一つのことは、3文スパンを見ているときです。この文書があって、この3文スパンがあります。
重複としてマークされた場合、手術を行って、それらの文を取り出すだけです。結果として得られる文書は一貫性すらないかもしれません。しかし、人々は誰が気にするかと言って先に進みます。
重複除去を行う別の方法があります。これはMapReduceほどではありませんが、よりハッシュテーブル的です。ブルームフィルターを皆さんの一部は見たことがあると思いますが、そうではないので、効率的で近似的だと思うので、それについて話します。より効率的です。しかし明らかに、常に正確なことを行っているわけではありません。しかし、私たちはそれほど選り好みしていません。
良い点は、非常にメモリ効率的なことです。更新できますが、削除はできません。基本的に集合の表現で、集合のメンバーシップを尋ね、noを返す場合、それは確実にnoです。
しかし、yesを返す場合、ハイパーパラメータを適切に設定すれば、ほとんどの場合yesです。しかし、noである小さな確率、偽陽性があります。パラメータを設定して、望むなら偽陽性率を下げることができます。
これがどのように見えるかを説明しましょう。5つのアイテム、the cat in the hatがあるとします。後で、集合に現れないいくつかのアイテムでテストします。最初に、mビンにマップするハッシュ関数を定義します。mはここでは8になります。
ブルームフィルターを構築するために、非常にシンプルなことを行います。ビン数でビット配列を作り、すべてのアイテムを通し、ハッシュし、2にハッシュします。
2番目のアイテムを更新し、7にハッシュし、7番目のアイテムを更新します。in the hatです。このビット配列を埋めるだけです。ビット配列では、アイテムを追跡しません。偽陽性があるかどうかはわかりません。
入れたすべてのアイテムが実際にアイテムの中にあることを確認しましょう。クエリするには、そのアイテムハッシュがテーブルにあるかどうかを計算するだけです。実際、すべてが通るはずです。
今度は、非アイテムを見て、どのように行うかを見ましょう。非アイテムの一部で0を得ることがわかります。これが望むものです。しかし、アイテムの一部で、ブルームフィルターは、ああ、実際に集合の中にあると言います。ここでの間違いの数は4です。
偽陽性率を計算すると、これは間違いの数を手順が正を生成した総数で割ったもので、偽陽性率はこの場合0.44で、かなり悪いです。もちろん、これはビン8です。ビンが成長すれば、これは良くなります。
実際、エラー確率は1/ビン数で成長します。しかし、これを見て、それは本当に良くないと言うでしょう。エラー確率を10のマイナス10乗にしたい場合、多くのビンが必要になります。それはメモリに害を与えません。
ここにより賢い解決策があり、より多くのハッシュ関数を使用することです。
2つのハッシュ関数を使うとしましょう。本質的に、まだ同じビット配列を持っています。しかし、すべてのアイテムに対して、2回ハッシュします。seed 0の下で2にハッシュされます。それを入れます。seed 1で5にハッシュされます。それをそこに入れます。すべてのアイテムはKにハッシュされます。必ずしも異なるわけではありませんが、k個のスロットです。
そしてcatを通し、このテーブルを埋めます。クエリを行うとき、要素を取り、すべてのKハッシュ関数に対してテーブルが1に設定されている場合、1を返します。入れた場合、Kビットを設定する必要があるからです。テストしている場合、K個の場所をチェックして、すべて設定されているかチェックする必要があります。
実際、すべてが通ります。今度は—間違いの数は3になりました。偽陽性率は減少しました。素晴らしいです。もちろん、これはおもちゃの例ですが、適度なメモリ消費で偽陽性率を本当に下げることができます。
一時停止して、これをもう少し形式的に分析する前に。
3.4 近似重複除去：MinHashとLocality Sensitive Hashing (LSH)
より一般的に何が起こるかを考えてみましょう。1,000のビン、10のハッシュ関数があり、100のアイテムをハッシュするとします。質問は、偽陽性率は何かということです。考え方は、集合にないテストの入力を考慮し、それが特定の場所、例えばiにハッシュするということです。
そして、n個のアイテムをブルームフィルターに入れて、何かがiに当たる確率を見ます。何かがiに当たれば、それは悪い兆候です。
ここでウォームアップしましょう。nが1だとしましょう。1つの要素だけを挿入します。Kも1です。1つのハッシュ関数のみを使用します。質問は、iと私が入れている要素の間にハッシュ衝突がある確率は何かということです。答えは単にビン数の1です。
すべてが独立だと仮定すると、0.001になります。今度は、nはまだ1ですが、kハッシュ関数を使用します。本質的に、1回だけでなくK回ミスしなければならないという基準になります。
これは1回ミスする確率です。1からそれを引いたものは当たる確率です。それをK回乗したものはK回当たる確率で、1からそれを引いたものはK回ミスする確率です。確率はここで少し下がります。
n個のアイテムを挿入している場合、n後のテストビンが1である確率を尋ねています。K回ではなく、K回n回ミスしなければなりません。
基本的に、この表現ですがK回nです。最後に、テストアイテムも何かをハッシュしているので、K回ミスするチャンスを得ます。偽陽性率は実際に—Kが本当に役立つのは、偽陽性率をKで下げることができることです。
Fは0.63から0.01になります。実際に表現Fここを見て、この漸近的計算として、固定比に対するKの最適値を計算できます。そして、これによりKはMをNでスケールする次数であることがわかります。使用すべきハッシュ関数の数は、ビン数をハッシュするアイテム数で割った次数です。
それを行えば、fは0.5になり、偽陽性率は0.5のK乗になります。この特定のケースでは、最適ではありませんでした。なぜなら、最適値は実際にはK=6で、偽陽性率は0.01ではなく0.008だからです。
これについてもっと読むことができます。計算メモリと偽陽性率をトレードオフできる講義ノートがあります。ブルームフィルターには、望む偽陽性率、持っているメモリ量、投入したい計算量などを制御できるハイパーパラメータがあります。
Kが下がったことに気づきました。Kが下がったとき、Kは本来あるべきよりも高いです。最適なKが下がったと言っているので、なぜFが下がるのでしょうか？
非常に大きなKの値を使用すると、実際にはかなり悪いです。ブルームフィルターを埋め尽くしてしまうからです。小さすぎるものを使用するのも、あまり良くありません。最適値があります。
上がるか下がるかは、どちら側にいるかによります。DOMAでは、偽陽性率を10のマイナス15乗に設定し、ブルームフィルターを使用して段落レベルで完全重複除去を行いました。
これが完全重複除去でした。完全重複除去の問題は、道徳的に重複であるにもかかわらず検出できないこれらの近似ミスの一部を捉えないことです。
どのように近似集合メンバーシップを行うでしょうか？近似集合メンバーシップについて話すために、類似度尺度の概念が必要です。よく使用される一般的なものは、Jaccard類似度です。
2つの集合A、Bのジャカードは、それらの交集合と和集合の比率です。例として、1234と1235があるとすると、ジャカードを計算すると、交集合のサイズは3、和集合のサイズは5で、したがってジャカードは0.6です。
2つの文書は、ジャカード類似度がある閾値を超えた場合に近似重複であると言います。一般的に、閾値はかなり高く、コンマが欠けているようなものだけを一致させたい場合は0.99のようになります。
これについて意味的なものは何もないことに注意してください。「not」のような単語が欠けている可能性があり、もちろんそれは意味を完全に変えるか、何らかの内容語です。しかし、これは表面的にかなり類似して見える文書を取得しようとしているだけです。
アルゴリズムの挑戦は、線形時間で近似重複をどのように見つけるかです。それに向けて取り組むために、ジャカード類似度を書き換えてみます。これもまた、ペアワイズです。1つの要素のジャカードは計算できません。2つの要素がある場合のみ計算できます。1つの要素で計算できるハッシュ関数の観点で書こうとします。
minhashと呼ばれるハッシュ関数があり、ハッシュ衝突の確率がまさにJaccard ABであるという良い性質があります。通常、ハッシュ衝突は何としても避けたいと思うことを覚えておいてください。本当に嫌いなものです。しかしここでは、より多くのハッシュ衝突が欲しいということではなく、類似度によって制御されたハッシュ衝突のレベルが欲しいということです。
類似度は衝突確率と等しいという問題を正しく述べるために。より類似したものほど、より多く衝突すべきです。それが直感です。
MinHashは次のように定義されます。集合を取り、これらすべての要素をハッシュし、これらは数値を返すことを覚えておいてください。最小の要素を取るだけです。初見では、このことを見たことがなければ、なぜMinを取るだけで実際に期待値がジャカードに等しいというこの性質が得られるのか明らかではないかもしれません。しかし、議論は実際にかなりシンプルです。
考え方は、5つのアイテムがあり、2つの集合があるということです。Aは1234を持ち、Bは1235を持っています。この特性行列表現を見てみます。Aは1234を持ち、Bは1235を持っています。
ランダムハッシュ関数は、アイテムに対する置換を誘導します。置換は例えば32145かもしれません。この右そこのハッシュ関数です。
そして今、Aで最初の項目は何か、Bで最初の項目は何かを見てみましょう。それは最小ハッシュに対応する項目です。各項目は、ハッシュ関数がランダムであると仮定しているので、最初である同じ確率を持っています。
1、2、または3が最初であれば、MinHashは実際に同じになります。最小—これらが最初の場合、ここでの最小はここでの最小と等しいからです。しかし最小—最初の—最小ハッシュが4または5の場合、Aでの最初はBでの最初にならず、MinHashは異なります。
そして今、MinHashが等しい確率はまさに1、2、または3であることがわかります。これはまさに交集合と同一です。
交集合にいて、その項目が最初であれば、衝突を得ます。交集合にいなければ、それが最初だと、一方では最小を得て、他方では他の値を得るので衝突を得ません。
これを信じない場合は、経験的にチェックできます。1,000を生成して—AとBでこれを実行し、衝突を得る確率をチェックしています。推定ジャカードは0.6であることがわかります。正確に0.6ではありません。丸めがあると思いますが、かなり近いです。
今、ジャカード類似度、ペアワイズ関数を、アイテムに対する確率的単項関数に削減しました。しかし実際には—まだ終わっていません。今、アイテムをハッシュできます。しかし、衝突はこれら2つが類似していることを教えてくれません。類似したものがハッシュされる可能性が高いということですが、もう少し強いものが欲しいです。
ここで局所性敏感ハッシュ法が登場します。これまでのところ、2つのハッシュ集合を取るハッシュ関数があり、集合はジャカード確率で衝突します。しかし、本当に欲しいのは、理想的にはジャカードA、Bがある閾値を超えている場合かつその場合のみ、AとBが衝突することです。
何らかの形で、確率を鋭くする必要があります。ジャカードが閾値を超えている場合、ほぼ確率1でハッシュされることを望みます。閾値を下回っている場合、基本的に確率ゼロまたは非常に小さいことを望みます。
どうすればこれができるでしょうか？同じトリックを取ることです。より多くのハッシュ関数を使用することです。
ここで、構築はn個のハッシュ関数をr個のハッシュ関数のbバンドに分割することです。例えば、12個のハッシュ関数、3つのバンドがあり、各バンドは4つのハッシュ関数を持つとします。H1からH4、H5からH8、H9からH12があります。
そして、何らかのバンドで、すべてのハッシュ関数が同じ値を返す場合、AとBは衝突すると宣言します。
AとBがある場合、MinHashを使用して12個すべてのハッシュ関数でAとBの両方をハッシュします。そして、例えばこのバンドで、H1、H2、H3、H4のハッシュ値がすべて一致する場合、衝突する、またはこのバンド、またはこのバンドと言います。キーとなるのは、閾値周辺の確率を鋭くするand/or構造です。
AとBが衝突する確率を計算する必要があります。同様に、simをジャカード類似度を指すために使用します。ジャカード類似度0.8があるとしましょう。その場合、5つのバンドがあり、各バンドは10個のハッシュ関数を持ちます。合計50個のハッシュ関数です。
固定バンドがマッチする確率は何でしょうか？固定バンドがマッチする確率は単に0.8のr乗です。単一のハッシュ関数の確率は単にジャカード、0.8だからです。
何らかのバンドがマッチする確率は何でしょうか？これは固定バンドがマッチしない確率です。これはそれらすべてがマッチしない確率です。
そして、少なくとも1つがマッチする確率です。衝突確率は0.43であることがわかります。この確率を再形成しています。bとrが1の場合、1つのハッシュ関数がある場合、衝突確率は0.8でしょう。今は0.3です。
しかし、頭の中に持つべき図はこれです。x軸は類似度です。そして、類似度から衝突確率へのマッピングがこのように見えることを望みます。閾値が0.5である場合、ここの下のすべてが0に近く、ここの上のすべてが1に近いことを望みます。
どのように見えるかを見てみましょう。様々な類似度値に対して、b=10、r=10に設定します。これが起こることは、これらの低確率の一部を潰し、これらの高確率の一部を鋭くすることです。
しかし、もう少し鋭くしたいかもしれません。10から20にrを増やします。
それが行うことは、曲線を右に移動させて一致を困難にし、閾値も鋭くすることです。それを行うと、これらの確率が上がることがわかります。そして今、これらの確率ははるかに小さくなります。以前は、0.7確率でさえ—0.7類似度は0.24の確率を持っていました。これはかなり高いです。
本当にこれを望まないので、これを潰したいです。それを潰すことで、今では0.007まで下げることができ、かなり良いと思います。しかし今、これらの確率の一部も潰しました。目標はすべてを右にシフトすることではありません。そうでなければ、完全重複除去をした方が良いかもしれません。
別のトリックがあります。バケットまたはビンの数であるbを増やすと、基本的にこれらの確率、0.9のようなものを90年代にすることができます。そして、これらの確率はまだかなり低いです。
この図は、bを増やすと、この曲線を左にシフトできることを示しています。rを増やすと曲線を鋭くして右に移動させ、bを増やすと曲線を左にシフトできるので、bとrの適切な設定で、本当に鋭いシグモイドを得ることができます。
これが実際にどのように見えるかの例です。前回見た近似重複除去にMinHash LSHを使用するこの論文があります。彼らの値は、b=20、r=450です。このrは大きく、本当に鋭い閾値が欲しいということを意味します。
計算できる公式があり、閾値は0.99であると言っています。つまり、100語ごとに、基本的に1語だけが異なることを許可できるということです。これはかなり厳格な重複除去です。固定バンドがマッチする確率はこれのr乗で、0.05です。そして衝突確率は0.64です。
興味深いことの1つは、閾値で衝突確率を計算していることです。ある意味で、それは0と1の間のどこかにあるべきです。
そして、1-1/eに収束することがわかります。これは約0.6です。閾値周辺では、どちらにでも行ける可能性があります。しかし、閾値を上回るとすぐに、衝突の確率が非常に高くなります。閾値を下回ると、衝突の確率が非常に低くなります。
3.5 Jaccard類似度とMinHashの理論的背景
MinHashの理論的背景について詳しく説明しましょう。MinHashは次のように定義されます。集合を取り、これらすべての要素をハッシュし、これらは数値を返すことを覚えておいてください。最小の要素を取るだけです。初見では、このことを見たことがなければ、なぜMinを取るだけで実際に期待値がジャカードに等しいというこの性質が得られるのか明らかではないかもしれません。しかし、議論は実際にかなりシンプルです。
考え方は、5つのアイテムがあり、2つの集合があるということです。Aは1234を持ち、Bは1235を持っています。この特性行列表現を見てみます。Aは1234を持ち、Bは1235を持っています。
ランダムハッシュ関数は、アイテムに対する置換を誘導します。置換は例えば32145かもしれません。この右そこのハッシュ関数です。
そして今、Aで最初の項目は何か、Bで最初の項目は何かを見てみましょう。それは最小ハッシュに対応する項目です。各項目は、ハッシュ関数がランダムであると仮定しているので、最初である同じ確率を持っています。
1、2、または3が最初であれば、MinHashは実際に同じになります。最小—これらが最初の場合、ここでの最小はここでの最小と等しいからです。しかし最小—最初の—最小ハッシュが4または5の場合、Aでの最初はBでの最初にならず、MinHashは異なります。
そして今、MinHashが等しい確率はまさに1、2、または3であることがわかります。これはまさに交集合と同一です。
交集合にいて、その項目が最初であれば、衝突を得ます。交集合にいなければ、それが最初だと、一方では最小を得て、他方では他の値を得るので衝突を得ません。
これを信じない場合は、経験的にチェックできます。1,000を生成して—AとBでこれを実行し、衝突を得る確率をチェックしています。推定ジャカードは0.6であることがわかります。正確に0.6ではありません。丸めがあると思いますが、かなり近いです。
今、ジャカード類似度、ペアワイズ関数を、アイテムに対する確率的単項関数に削減しました。しかし実際には—まだ終わっていません。今、アイテムをハッシュできます。しかし、衝突はこれら2つが類似していることを教えてくれません。類似したものがハッシュされる可能性が高いということですが、もう少し強いものが欲しいです。
3.6 LSHによる確率の最適化
ここで局所性敏感ハッシュ法が登場します。これまでのところ、2つのハッシュ集合を取るハッシュ関数があり、集合はジャカード確率で衝突します。しかし、本当に欲しいのは、理想的にはジャカードA、Bがある閾値を超えている場合かつその場合のみ、AとBが衝突することです。
何らかの形で、確率を鋭くする必要があります。ジャカードが閾値を超えている場合、ほぼ確率1でハッシュされることを望みます。閾値を下回っている場合、基本的に確率ゼロまたは非常に小さいことを望みます。
どうすればこれができるでしょうか？同じトリックを取ることです。より多くのハッシュ関数を使用することです。
ここで、構築はn個のハッシュ関数をr個のハッシュ関数のbバンドに分割することです。例えば、12個のハッシュ関数、3つのバンドがあり、各バンドは4つのハッシュ関数を持つとします。H1からH4、H5からH8、H9からH12があります。
そして、何らかのバンドで、すべてのハッシュ関数が同じ値を返す場合、AとBは衝突すると宣言します。
AとBがある場合、MinHashを使用して12個すべてのハッシュ関数でAとBの両方をハッシュします。そして、例えばこのバンドで、H1、H2、H3、H4のハッシュ値がすべて一致する場合、衝突する、またはこのバンド、またはこのバンドと言います。キーとなるのは、閾値周辺の確率を鋭くするand/or構造です。
AとBが衝突する確率を計算する必要があります。同様に、simをジャカード類似度を指すために使用します。ジャカード類似度0.8があるとしましょう。その場合、5つのバンドがあり、各バンドは10個のハッシュ関数を持ちます。合計50個のハッシュ関数です。
固定バンドがマッチする確率は何でしょうか？固定バンドがマッチする確率は単に0.8のr乗です。単一のハッシュ関数の確率は単にジャカード、0.8だからです。
何らかのバンドがマッチする確率は何でしょうか？これは固定バンドがマッチしない確率です。これはそれらすべてがマッチしない確率です。
そして、少なくとも1つがマッチする確率です。衝突確率は0.43であることがわかります。この確率を再形成しています。bとrが1の場合、1つのハッシュ関数がある場合、衝突確率は0.8でしょう。今は0.3です。
しかし、頭の中に持つべき図はこれです。x軸は類似度です。そして、類似度から衝突確率へのマッピングがこのように見えることを望みます。閾値が0.5である場合、ここの下のすべてが0に近く、ここの上のすべてが1に近いことを望みます。
どのように見えるかを見てみましょう。様々な類似度値に対して、b=10、r=10に設定します。これが起こることは、これらの低確率の一部を潰し、これらの高確率の一部を鋭くすることです。
しかし、もう少し鋭くしたいかもしれません。10から20にrを増やします。
それが行うことは、曲線を右に移動させて一致を困難にし、閾値も鋭くすることです。それを行うと、これらの確率が上がることがわかります。そして今、これらの確率ははるかに小さくなります。以前は、0.7確率でさえ—0.7類似度は0.24の確率を持っていました。これはかなり高いです。
本当にこれを望まないので、これを潰したいです。それを潰すことで、今では0.007まで下げることができ、かなり良いと思います。しかし今、これらの確率の一部も潰しました。目標はすべてを右にシフトすることではありません。そうでなければ、完全重複除去をした方が良いかもしれません。
別のトリックがあります。バケットまたはビンの数であるbを増やすと、基本的にこれらの確率、0.9のようなものを90年代にすることができます。そして、これらの確率はまだかなり低いです。
この図は、bを増やすと、この曲線を左にシフトできることを示しています。rを増やすと曲線を鋭くして右に移動させ、bを増やすと曲線を左にシフトできるので、bとrの適切な設定で、本当に鋭いシグモイドを得ることができます。
これが実際にどのように見えるかの例です。前回見た近似重複除去にMinHash LSHを使用するこの論文があります。彼らの値は、b=20、r=450です。このrは大きく、本当に鋭い閾値が欲しいということを意味します。
計算できる公式があり、閾値は0.99であると言っています。つまり、100語ごとに、基本的に1語だけが異なることを許可できるということです。これはかなり厳格な重複除去です。固定バンドがマッチする確率はこれのr乗で、0.05です。そして衝突確率は0.64です。
興味深いことの1つは、閾値で衝突確率を計算していることです。ある意味で、それは0と1の間のどこかにあるべきです。
そして、1-1/eに収束することがわかります。これは約0.6です。閾値周辺では、どちらにでも行ける可能性があります。しかし、閾値を上回るとすぐに、衝突の確率が非常に高くなります。閾値を下回ると、衝突の確率が非常に低くなります。
重複除去について何か質問があれば、一時停止します。
合成データの台頭に関するある質問で、ほとんどの重複関数が正確な[聞き取れない]ヒットに基づいているが、合成データのインスタンスを書き換えた場合、それは台頭している。その使用例に対してどのように重複除去するのかと思っていました。
合成データが台頭していることを考えると、言い換えに敏感な何かを使用してどのように重複除去するかという質問です。いくつかの論文があります。例えば、Sam Pritchettは言及しませんでしたが、基本的に埋め込みを見て、より意味的な類似性の概念を得ることができます。これはすべて同じフレームワークに適合します。
ある意味で、LSHは近似最近傍を見つけるために考案されたからです。埋め込みを持ち、すべての文書を埋め込み、その空間で最近傍を見つけることができます。明らかに、文書を埋め込むために埋め込みを実行する場合、より高いコストがあります。また、文書が—近似重複が本当に近似重複である体制で作業しています。
より曖昧な重複除去を行う場合は、非常に注意深くある必要があると思います。あまりに寛容であると、多くのデータを捨ててしまう可能性があります。
別の質問ですか？
解釈によりすべてがより良くなることを知っています。実際にデータを重複除去しなければならない状況はありますか？非常に高品質なので、実際に繰り返されることを望みますか？
データが高品質である場合、重複を望むかもしれないという質問です。それは実際に正しいです。多くの言語モデリング論文で、高品質ソースの束がある中間訓練体制があります。実際に高品質データに対して複数のエポックを取りたいのです。
重複除去は、すべてのものがあり、何らかのランダムなものの60,000コピーがある事前訓練のためのものだと思います。それを片付けたいだけです。しかし、最適なことは—まあ、明らかに最適ではありません。最適なことが何かはわかりません。しかし、多くの回数出現する文書がある場合、それにより多くの重要性があることを示すこともできるでしょう。
おそらく正しいことは、カウント数を取ることです。平方根や対数など何かを取って、比例して訓練データに現れるのではなく、より多くのエポックを取るのに十分重要であることを認識することです。
4. まとめと今後の課題
4.1 アルゴリズムツールの総括
まとめましょう。この講義は主にアルゴリズムツールを提供することでした。フィルタリングを行う方法として、n-gramモデル、線形分類器、重要度サンプリングを見てきました。フィルタリングによって、言語識別、品質フィルタリング、毒性フィルタリング、何でも、ターゲットデータセットがある場合に行うことができます。そのデータセットをもっと取得したい場合、これらのツールを適用できます。
または、ターゲットデータセットがなく、強力な言語モデルがある場合、その言語モデルにプロンプトして、より低品質なデータセットを合成または濾過してTに到達させることができます。そうすれば高速な分類器を得て、レースが始まります。
第二に、重複除去を見てきました。これは、本質的に無駄にしている計算量を削減するために重要です。ここでのアルゴリズムツールはハッシュ化です。
ハッシュ化により、これらの種類のペアワイズな類似性と衝突の概念を取り、それらを単項関数に変えることができます。これにより線形時間特性を持つことができるからです。そして、基本的に複数のハッシュ関数を使用し、これらの種類のand/or構造を使用することで、LSHの例のように基準を形成する方法について、いくつかの巧妙な方法を見ました。
今、あなたはすべてのツールを持っています。ある意味で、データをどのように教えるかと問うなら、これは始まりに過ぎません。実際にはデータと時間を過ごし、それを見て、フィルタリングし、モデルを訓練する必要があります。そして、それが何が機能し、何が機能しないかについての直感を構築する方法です。うまくいけば、課題4で少しそれを行うことができるでしょう。
4.2 実践における注意点と限界
データ講義はこれで終わりです。来週は、強化学習とアライメントを始めます。これが私たちの最後のユニットになります。
実践において、いくつかの重要な制限と注意点があります。合成データの台頭を考えると、より意味論的な類似度の概念が必要になってきています。埋め込みを使用してより曖昧な重複除去を行うことは可能ですが、あまりに寛容であると多くのデータを捨ててしまうリスクがあります。
また、高品質データについては、実際に重複を望む場合があることも認識すべきです。中間訓練レジームでは、高品質ソースに対して複数のエポックを取ることが有益です。重複除去は主に、60,000コピーのようなランダムなコンテンツがある事前訓練のためのものです。
最適なアプローチは完全に明らかではありませんが、おそらく文書の出現回数を取り、平方根や対数などの何らかの変換を適用して、比例的ではなく、その重要性を認識して訓練データに現れるようにすることでしょう。
最も重要なことは、これらのアルゴリズムツールを持っていても、実際にデータと時間を過ごし、それを見て、フィルタリングし、モデルを訓練することが必要だということです。それが何が機能し、何が機能しないかについての直感を構築する方法です。うまくいけば、課題4で少しそれを行うことができるでしょう。
Stanford CS336 Language Modeling from Scratch | Spring 2025 | Lecture 14: Data 2
For more information about Stanford's online Artificial Intelligence programs visit: https://stanford.io/ai To learn more about enrolling in this course visit: https://online.stanford.edu/courses/cs336-language-modeling-scratch To follow along with the course schedule and syllabus visit: https://stanford-cs336.github.io/spring2025/ Percy Liang Associate Professor of Computer Science Director of Center for Research on Foundation Models (CRFM) Tatsunori Hashimoto Assistant Professor of Computer Science View the entire course playlist: https://www.youtube.com/playlist?list=PLoROMvodv4rOY23Y0BoGoBGgQ1zmU_MT_
youtu.be
