技術研究所の(あ)です。
ここ数年の流行りの機械学習ですが、僕もちょっと機械学習を用いた画像分類を試してみる機会がありました。
識別したい対象 (例えば猫) が写っている画像(正例)と、写っていない画像(負例)を用意し、機械学習アルゴリズムで学習させると、「その対象 (猫) が写っているか?」という確信度を返す分類器ができあがります。
試したシステムの説明では「正例と負例は同じくらいの数で学習させるとよい」と書いてありました。
手持ちの写真がたくさん (例えば1万枚) あって、その中に猫の写真が100枚 (集合C としましょう) あったとしたら、猫の写ってない写真を残りの 9900枚 (not-C としましょう) から 100枚選んでやる必要があります。どうせならなるべく偏りがないよう、ランダムにせねばなりません。
C と、not-C から選んだ100枚から、それぞれ同じ割合でランダムに学習用データとテスト用データに切り分ける必要もあります。どうやって選ぶのがスマートかなー、調べれば出てくるよなー、と思ったのですが、その前にちょっと自力で考えてみました。
C や not-C はプログラム上では配列で表されているのが普通でしょう。
要素が n個ある配列から k個ランダムに選ぶには、いちばん単純には、整数 0～n-1 の乱数を発生させ、重複は弾きつつ、k個に達するまで繰り返します (ここでは、「使う『乱数』が本当に偏りなくランダムか?」という話は置いておくことにします)。
k が小さいときはこれで構わないと思いますが、k が大きくなり n に近づくほど重複が増えるので、その回数だけ重複チェックし余計な繰り返しも増えるのはあまりスマートな感じがしません。
重複した度合いによって繰り返し回数が変わるのもいまいちです。
選ばれたものは選ばれた順に配列に入れておけば、s 個目のところで二つに分ければ、ランダムな二つの集合 (s個と k-s個) に分かれます。今の状況設定だと C のほうはもともと k個あるので、ここからランダムに s個選んで切り分ける、ということになります。C と not-C に対してやることが違うのも何かいまいちです (こだわりすぎ? ^^;)。
not-C から k個ランダムに選んだものが、ランダムに並んでいれば s個目で分けるだけでよかったので、C も先にシャッフルしてしまえば同じく s個目で切り分けるだけでよくなります。
とすると、not-C から k個ランダムに選ぶのにもこの手が使えますね。n が k に対して極端に大きくなければ、先に全体をシャッフルして、先頭から s個、k-s個選べばランダムな二グループのサンプルが選べます。
この方法は、(同じ要素を含まない) 三つ以上のグループのサンプルをピックアップしたり、元の集合を任意の数のグループに分割したりするときにも使えます。やりかたとしてもシンプルですし、まずまずスマートではないでしょうか (「意見には個人差があります」^^;)。
ちなみに、n個の配列 a[n] を均等にシャッフルするには random(i) を 0 から i までの整数の乱数を発生させる関数として、
for (i = n-1; i > 0; i--)
swap(a[i], a[random(i)]);
とする、というアルゴリズムが有名です。
と、ここまで考えたところで調べてみたら、案の定、かの Knuth 大先生の本に n個から k個を抽出するエレガントなアルゴリズムが載っているそうです。
「非復元抽出の高速かつ実装が簡単な方法を考える」
http://d.hatena.ne.jp/sleepy_yoshi/20130720/p1
さらには、初期段階で全体の数 n が分からなくても、一回ループを回すだけでランダムな k個の抽出が行える Reservoir Sampling という方法があるそうです。
「大量のテキストからランダムに少数の行を抽出したい – Reservoir Sampling」
これらのアルゴリズム、なぜこれで均等に抽出できるのか、理解するにはちょっと時間が掛かりますが、やはり先達は偉大ですねぇ。自分でもきちんと考えつつ、既存の知見はしっかりと活用していきたいものです。
