ニューラルネットをプログラムするときに、ランダムな置換 （ここでは $ 0 $ から $ n-1 $ までの数がランダムな順で並んだものと考えます）が 必要になることがあります。例えば、

• SGD with minibatch において、サンプルの配列の中からランダムな順序で 100 ずつ、 順番に取り出したい。ランダムな置換を使って配列のインデックスをかき混ぜればよい。
• Dropout において、n 個の入力のうちランダムに選んだ半分を 0 にセットしたい。 それぞれの入力を確率 0.5 で 0 にするのではちょうど半分になるとは限らない。 ランダムな置換を使えば、$ n / 2 $ 未満の要素を選ぶことによりちょうど半分 をランダムに選ぶことができる。半分ではなく他の比率でも大丈夫。

ランダムな置換を得るには Knuth shuffles という便利なアルゴリズムがあります。これは $ 0, 1, \ldots, n - 1 $ という シーケンスに対し、$i$ 番目と、$ 0, \ldots, i $ からランダムに選んだ $j$ による $j$ 番目とを入れ替える、という操作を $i = 0, 1, \ldots, n-1$ について 繰り返すというものです。

変数の初期化も同時にやってしまうのが以下のコードです。

1
2
3
4
5
6
7
8
9
10
11
12

// get a random permutation of [0, 1, .., n-1] where n = vec.size().
void GetRandomPermutation(std::vector<unsigned int> &vec)
{
  // Knuth shuffles algorithm
  const size_t n = vec.size();
  for (unsigned int i = 0; i < n; ++i)
  {
    unsigned int j = uniform(0, i);
    vec[i] = vec[j];
    vec[j] = i;
  }
}

ここで uniform(0, i) は $0, 1, \ldots,i$ の中から同確率で一つ選んで 返す関数です。

9 行目で $i = j$ の場合、まだ初期化されていない値を自分に代入することになりますが、 そのときは次の 10 行目で $i$ が上書きされるので問題ありません。

このように簡単なアルゴリズムですが、 これで最終的に得られる置換の分布は一様であることが、次のように証明できます。

数学的帰納法を使います。

「$k$ 番目のループ（$ k = 0, 1, \ldots, n-1 $）のあと、$ \mathrm{vec}[p]~~(p \in [0,k]) $ の値が $q \in [0, k]$ である確率は $p, q$ に関わらずすべて $1 / (k + 1)$ である」

という命題を $ \mathrm{Prop}(k) $ とします。証明したいのは $ \mathrm{Prop}(n-1) $ です。
$ \mathrm{Prop}(0) $ は自明です。
$ \mathrm{Prop}(k) $ を真だと仮定して $ \mathrm{Prop}(k+1) $ を証明すればいいわけですが、 $k+1$ 番目のループのあとに

• $ \mathrm{vec}[p]~~(p \in [0,k]) $ が $q \in [0, k]$ である確率は、 「前回のループ後にその値であった確率」×「今回入れ替えられなかった確率」、 つまり $$ (1 / (k + 1)) \cdot ((k + 1) / (k + 2)) = 1 / (k + 2) $$
• $ \mathrm{vec}[p]~~(p \in [0,k]) $ が $k + 1$ である確率は、今回入れ替えられた確率、 つまり $1 / (k + 2)$
• $ \mathrm{vec}[k+1] $ が $q \in [0, k+1]$　である確率はやはり $1 / (k + 2)$

というわけで $ \mathrm{Prop}(k+1) $ が成り立ちます。

やっていることは実に単純ですが、ちょっと自分で思いつくのは難しそうな、 アルゴリズムらしいアルゴリズムですね。