無作為抽出のトリック
この記事で、「ある集合の上位 5% を 95% の確率で選択するためには、全体のデータ数によらず 59 件取得すれば十分である」という命題を使用しました。これを証明しましょう。
集合 U の部分集合 Q があり、 Q の要素数は U の要素数に対して割合が p だとします。このとき更に U の部分集合である P を考えます。P に Q の要素が全く含まれない確率は ですから、 P のうち少なくとも 1 つの要素が Q に含まれる確率は です。ここで
とおくと
が得られます。このとき , とすると、 です。つまり、ある集合から無作為に複数の要素を選択する際、ある 5% の要素を 95% の確率で選択するためには、 59 個の要素を選択すれば十分である、ということになります。
なんだか狐につままれたような気分になりますが「95% の確率で選択する」というところがミソですね。シンプルですがなかなか強力な技だと思います。
参考文献: A. J. Smola and B. Schölkopf, “Sparse Greedy Matrix Approximation for Machine Learning", inProceedings of 17th International Conference on Machine Learning, pp. 911-918, 200.