集合からの類似要素検索

randomized-algorithm

目標

$q$ の値に近い上位 $100 r$ % の要素を集合 $S$ から確率 $p$ でとりだす。

方法

ランダムにとりだして値が近い要素を採用する。

  • ランダムに $1$ 個とりだしたとき、上位 $100 r$ % に入っていない確率: $(1 - r)$
  • ランダムに $k$ 個とりだしたとき、上位 $100 r$ % に入っていない確率: $(1 - r)^k$

よって、$(1 - r)^k \le 1 - p$ となる $k$ を求めれば目的を達成できる。

たとえば、$r=0.05$, $p=0.9$ なら $0.95^k \le 0.1$ より $k = 45$ となる。 これは集合のサイズ $|S|$ に依存しない!

たとえば、$6,905$ 個のサンプルを取り出すと、集合のサイズにかかわらず、$99.9$ % の確率で上位 $0.1$ % の要素を抽出できる。

まとめ

  • $k \ge \frac{\ln(1-p)}{\ln(1-r)}$ 個の要素をランダムに取り出して、最も近い要素を選べばよい。
\begin{aligned}
(1 - r)^k & \le 1 - p \\
\Leftrightarrow \ln\left( (1 - r)^k \right) & \ge \ln(1 - p) \\
\Leftrightarrow k \ln(1 - r) & \ge \ln(1 - p) \\
\Leftrightarrow k & \ge \frac{\ln(1 - p)}{\ln(1 - r)}
\end{aligned}