← 投稿一覧

Rejection Samplingとは？

※ この記事は英語原文からAIによる翻訳です。

りんごゲームでは、盤面の数字はランダムに見えますが、合計は必ず10の倍数になっています。このような制約を満たすランダムデータはどうやって生成するのでしょうか？簡単な方法の一つがreject samplingです。これは多くの分野で広く使われている汎用的な手法なので、それ自体を理解しておく価値があります。

基本的なアイデア

Rejection samplingは、特定の制約条件を満たすランダムサンプルを生成する手法です。手順はシンプルです。サンプリングしやすい分布から候補を生成し、制約条件を満たすか確認し、満たせば採用、そうでなければ破棄します。破棄した場合はやり直しです。

それだけです。制約付きの分布から直接サンプリングする方法を導出する必要はありません。必要なのは二つだけ：候補を生成する方法と、それを検証する方法です。

アルゴリズム

1. シンプルな分布からランダムな候補を生成する。
2. 候補が制約条件を満たすか確認する。
3. 満たすなら採用。完了。
4. 満たさないなら破棄し、ステップ1に戻る。

採用されたサンプルが得られるまで繰り返します。各試行は独立しているため、プロセスに記憶はありません。

例

円の内部の点をサンプリングする。 単位円の内部に一様に分布するランダムな点が欲しいとします。円形領域から直接サンプリングするのは少し面倒です。簡単な方法：外接正方形から一様に点をサンプリングします（xとyをそれぞれ-1から1の間で選択）。そしてx² + y² ≤ 1かどうか確認します。円の内側にあれば採用、そうでなければ破棄。円は正方形の約78.5%を占めるので、5個中約4個が通過します。非常に効率的です。

有効なパスワードの生成。 大文字、数字、特殊文字がそれぞれ1つ以上含まれるランダムなパスワードが必要だとします。一つの方法：全文字セットから必要な長さのランダム文字列を生成し、ルールを満たすか確認します。満たせば使用、満たさなければ再生成。一般的なパスワードの長さ（12文字以上）では、ほとんどのランダム文字列が通過するので、通常数回の試行で十分です。

正方形から一様にサンプリングされたランダムな点。円の内側の点は採用（青）、外側の点は破棄（グレー）。

なぜ便利なのか

最大の利点はシンプルさです。制約付きの分布のための専用サンプリングアルゴリズムを作る必要がありません。候補の生成と制約条件の検証ができれば十分です。実装は通常、whileループとランダム生成器、そしてif文だけです。

これは、制約条件の検証は簡単だが生成プロセスに直接組み込むのが難しい場合に特に有用です。実際に多くの問題がこの形をしています。

主な限界：acceptance rate

Rejection samplingは、候補のうち適切な割合が検査を通過するときにうまく機能します。重要な指標はacceptance rate - ランダムな候補が制約条件を満たす確率です。

Acceptance rateが1/10なら、採用されるサンプル1つあたり平均10個の候補が必要です。それは問題ありません。しかし1/1,000,000なら、1つを得るために100万個を生成する必要があります。それは問題です。

高次元空間では、acceptance rateが極端に小さくなる可能性があります。100次元空間の小さな領域からサンプリングしようとして、外接ボックスで一様に点を生成すると、ほぼすべての候補が失敗します。このような場合には、より賢い方法（MCMC、importance samplingなど）が必要です。

実際には、acceptance rateが適切な場合 - おおよそ1%以上であれば - rejection samplingは良い最初の選択肢です。それ以下なら、代替手法を探すべきです。

りんごゲームに戻ると

りんごゲームでは、ランダムに生成された盤面の数字の合計が10で割り切れる確率は約1/10なので、acceptance rateは約10%です。そのためrejection samplingが効率的です - 平均10回試すだけで有効な盤面が得られます。盤面がランダムに見えるのは、実際にほぼランダムだからです。制約条件が10個中9個の候補をフィルタリングするだけです。