HN 日本語サマリー

← 一覧へ戻る
プログラミング

ランダムは実際には十分にランダムではない場合

When random is not actually random enough (ersc.io)

68 pointsby steveklabnik36 コメント

要約

多くのコードベースで見られる一般的なパターンは、オブジェクトのセットからランダムに1つを選択する際に、単純な剰余演算子(%)を使用して乱数を範囲にクランプすることです。しかし、この方法は元の乱数生成器の均一分布を維持しないため、選択されるオブジェクトの確率分布が歪んでしまうという隠れた問題があります。この問題を解決するには、より高レベルで汎用的なAPI、例えば相対整数重みを受け取るrandom_choice関数を使用することが推奨されます。これは、確率分布を明示的に定義することで、より正確で意図した通りのランダム選択を可能にします。

全文翻訳

ランダムが十分にランダムでないとき

コードベースの至る所で見かける、多くの人が書いたことがある一般的なパターンがあります。それは、オブジェクトのセットからランダムに1つを選ぶというものです。すべてのオブジェクトが選ばれる確率は同じであるべきです。非常にシンプルで直接的な解決策は、大きな乱数を選び、その数値を剰余演算子で選択肢の数にクランプすることです。

Set<T> choices = ten_things();
u64 r = random_u64(); // [0..UINT64_MAX] の範囲で均一な確率
T chosen = choices[r % 10];

私が若い頃、特にC言語(標準ライブラリには rand() 以上のものは提供されていません)や、当時よく使っていたHaskellで、この選択肢を何度も選んだことを懐かしく思い出します。結局のところ、このような問題に直面したとき、それは非常に直接的で直感的な解決策であり、どんなに質素で貧弱なコードベースや言語であっても、乱数を選ぶための「何らかの」メカニズムは必ずあるからです。

しかし、この解決策には隠れた問題があります。それは、元の random_u64() 関数の均一分布を維持しないということです。つまり、選ばれた chosen オブジェクトのばらつきは、私たちが直感的に考えるようなものにはなりません。各アイテムが 1/10 の確率で選ばれると考えるかもしれませんが、実際にはそうではありません。

均一な選択の(非)維持

まず、より簡単な問題から始めましょう。区間 [0, 9] から整数を1つ選びます。選択肢は10個あります。乱数選択関数が均一分布を持っていると仮定すると、各整数は 1/10 = 10% の確率で選ばれることになります。

次に、この整数を使って、上記の剰余演算子のように、3つのオブジェクトのセットから値をランダムに選びます。直感的(暗黙的)な希望は、この操作によって3つのオブジェクトのいずれかが 1/3 = 33.3% の確率で選ばれることです。つまり、結果の確率分布が入力変数の均一分布を「尊重」することを望んでいます。

残念ながら、そうはなりません。結果を表にまとめるだけで、それが明らかになります。

入力値  -> 選択肢
-----------------------------
{0, 3, 6, 9} -> オブジェクト #1 を選択
{1, 4, 7}    -> オブジェクト #2 を選択
{2, 5, 8}    -> オブジェクト #3 を選択

つまり、10個の入力のうち4つが選択肢1になり、選択肢2と3はそれぞれ3つの入力しかありません。これは、選択肢1が意図した33%ではなく40%の時間で選ばれることを意味し、同様に選択肢2と3は30%の時間しか選ばれません。

これは古典的な誤りの一つです。特に random_u64() しか利用できない場合に顕著です。さて、本来の正しい動作は、l から h までの各整数が 1/((h-l)+1) の確率で選ばれる random_between(l, h) 関数です。このような関数は、予想されるように、より複雑です!

私の考えでは、この問題は二重です。一つは、均一な乱数関数しか提供しないのはAPI設計として最適ではないということです。特に、その最も有用なバリアントの1つが誤って実装されやすいことを考えると。しかし、そもそも間違ったドメインで精神的に作業している良い例でもあります。

明示的な分布を与えるのは(うまくいけば)簡単

まず、random_u64() のようなAPIは少し低レベルすぎ、専門的すぎると感じます。私たちは本当に均一な数値をサンプリングしたいのではなく、「どのくらいの頻度で何かが起こるか」を表現するための、より一般的な演算子を求めているのです。

一方では、単にランダムな数値を選ぶ必要はめったになく、通常は可能な選択肢の中からオブジェクトを選びたいのです。第二に、特定のオブジェクトを他のオブジェクトよりも選ばれやすくしたり、選ばれにくくしたりすることがしばしば役立ちます。均一分布だけが価値のあるものではありません! random_u64() はこれらのどちらにも役立ちません。random_between(0, 9) は、一見すると最初のものにしか役立ちません(後述)。

ほとんどの場合、これらの問題に直接向き合わせる、より一般的な演算子、つまり離散的なオプションのセットとその選択確率を受け取る random_choice() 関数に頼るのが有用だと考えています。言い換えれば、確率分布自体を明示的に記述するべきです。これにより、前述の動作や、より興味深い多くの動作を表現できます。

通常、確率について話すときは、それらが合計で 1.0 になると考えます。元の例を次のように再定式化すると、誤った「偏った」選択がすぐに目につくでしょう。

T chosen = random_choice([
  (First,  0.4), // 40% の確率?!
  (Second, 0.3), // 30% の確率
  (Third,  0.3), // 30% の確率
])

これは(多くの例のうちの)1つだと思いますが、汎用的なAPI、より抽象的なAPIは、実際にはコードの多くをより理解しやすく、正しく書くことを容易にします。もちろん、random_u64() や random_between() も引き続き利用可能であるべきですが、random_choice() は、成功の穴に落ちるのを助けてくれるため、はるかに優れたデフォルトのツールだと考えています。

APIの改善:相対整数重み

前述のインターフェースは教育的には良いですが、浮動小数点数の不安定性は、合計が正確に 1.0 になる必要がある、必要な重みを正確に選択する能力を曖昧にする可能性があります。また、1.0 に合計する必要があるという要件は、各確率的な選択肢の適切なスケールを計算する必要があるため、煩わしいです。そして、浮動小数点数に関わる問題に直面したときは、それを排除して別のことをするという、実績のある確実な方法を使用します。

Pythonのようなほとんどの標準ライブラリは、まさにこれを行いますが、相対整数重みを使用します。「相対」部分とは、数値が100に合計されないことを意味します。代わりに、それらを合計し、任意の選択肢の重みはその選択肢の確率と合計の比率になります。前の重みは (4, 3, 3) で表現されます。4 + 3 + 3 = 10 であり、したがって 3 / 10 = 0.3 となります。

相対整数重みの良い点の1つは、より直感的に動作するため、正しく使用する可能性が高くなることです。箱の中の物の数を数えて、青い物が10個、赤い物が5個ある場合、選択肢を [(Blue, 10), (Red, 5)] と単純に記述でき、結果の選択は期待どおりに分布します。

また、このAPIの実装は、random_u64() だけでなく random_between(l, h) があれば、直感的に行うのがはるかに簡単です。これは、random_u64() が低レベルすぎるもう一つの兆候だと思います。整数重みが 15 + 12 + 3 = 30 であるとしましょう。次に、乱数 choice = random_between(0, 29) を生成します。選択された値が [0, 14] の間なら最初のオプション、15, 26 の間なら2番目のオプション、[27, 29] なら3番目のオプションです。つまり、整数重みを [l, h] 区間のサブセットにマッピングし、その区間から均一に選択するだけです。これは非常に有用でシンプルなので、私の意見では、他の関数と一緒にも提供されるべきです。

誤ったメンタルドメインでの作業

私にとってのもう一つのより微妙な問題は、自分がどのドメインで作業しているかを認識することです。前述の例では、議論したい対象は数値ではなく、確率変数です。通常、これらの確率変数を大文字の X、Y、Z などで呼びます。

通常の数値と同様に、確率変数にも代数があり、加算や減算ができ、指数も含まれます。しかし、これらの演算子も、ここでそうであったように、基になる分布と期待される結果に影響を与えます。しかし、最も重要なことは、非線形演算子は確率変数の期待値を尊重しないということです。特に、期待値 E[f(X)] に対する関数 f は、常に f(E[X]) と同じではありません。

ここで起こったことです。注意しないと、値 x = random_u64() の何らかのプロパティを維持しようとしていると考えてしまいがちですが、実際には基になる random_u64() 関数のプロパティを維持しようとしています。

私たちのケース

私たちはAntithesisの顧客です。彼らのプラットフォームでは、重要なコードパスをランダムに実行することで、実質的にバグを見つけます。これは、オペレーティングシステム全体に対する大規模な決定論的ファザーです。そしてファザーと同様に、コードカバレッジを指針として考えることは有用です。「このコードはテストされたか」は、「ファザーはこのパスを見つけたか」と尋ねるのと同じであり、ファザーがそのパスを見つけなかった場合、そのコードはテストされていません。

カバレッジを増やすことは、正のパスと負のコードパスを表現し、それらをテストで見つけることです。負のパスは、見つかった場合にバグとなる悪いケースです。例えば、データ自体のハッシュをキーとしてキャッシュからデータを読み取り、キーがデータの再計算されたハッシュと一致することを assert!() する場合などです。

正のパスは、例えば「小さい」アップロードと「大きい」アップロードで異なる動作をするアップロード関数が、実際に両方のケースをテストしていることを保証することかもしれません。このような場合、分布を直接表現するのは非常に便利です。

enum BlobSize {
  Small,  // 1KiB: 高速パス
  Medium, // 1MiB: ストリーミング書き込みパス
  Large,  // 2MiB: より多く
  XLarge, // 8MiB: より多く、より多く
}

let choices = vec![
  (Small,  88),
  (Medium, 04),
  (Large,  04),
  (XLarge, 04),
];

if let Some(size) = weighted_choice(choices) {
   // ... 選ばれたサイズのブロブをアップロード ...
};

この場合、テスト下では、約7/8のアップロードが小さいデータブロブで、約1/8が大きなブロブ(3つの異なるサイズ)になります。これらの数値を操作できることは、状態空間を探索するのに非常に役立ちます!この例を拡張して、例えばポアソン分布などを表現することも非常に簡単です。

ここで見つけたもう一つの有用なケースは、ある条件の下で choices のセットを拡張することです。例えば、何らかの「良い」または「悪い」ことが起こったときに、検索を誘導するために上記のベクトルに何かを追加するために choice.push() を使用することです。これは上記の例で確率を再調整する必要がありますが、それを避けるためにこの例を異なる構造にすることも想像できます。

そして、これが今回の投稿につながります。先週起こったことです。最近、Antithesis関連のコードのレビューを行った結果、実質的に常に離散的な重み付き選択肢しか求めていなかったため、random_u64() の使用をすべて(重み付き) random_choice() に置き換えることができました。さらに新しい呼び出しの導入は、通知があるまで一時停止することにしました。この教訓は、コミットメッセージに埋もれたままにしないほど重要だと考えました。なぜなら、私はそれを常に忘れてしまうからです。

次に元のサンプルコードのようなものを見かけたら、自問してみてください。望ましい分布を直接表現できないか? もしそうなら、はるかに豊かなツールで遊ぶことができるでしょう!