(講義ノート)乱択アルゴリズム第10回

分布からサンプリングした $n$ 個のデータについて、分布は学習することができる。しかし、学習するより早く検査することはできるか？

具体的には何をするか。

分布上の性質は、分布の集合だと考えられる。○○を満たす集合の中に、該当分布が入っているかどうか。

アルゴリズムが以下を満たすとき、 $\epsilon$ 検査器。

以下のような距離がある。 $D^\prime$ はサンプルしデータ点

すべての変数の間での距離である。

||p(s) - q(s)||_{TU} = \max_{S \in D^\prime} |p(s) - q(s)|

下じゃないの？

\int |p(\mathbf{s}) - q(\mathbf{s})| d \mathbf{s}

||p(s) - q(s)||_{r} = {}^{r}\sqrt{\int |p(s) - q(s)|^r ds}

学習するには、何個のサンプルが必要か。 $S$ 回サンプルするとする。経験分布として、要素 $s$ が差プルされた回数を $q(s) = 1/S$ と書ける。

以下の定理が成り立つ。

$S \geq \frac{c n \log n}{\epsilon^2}$ とする。高い確率で、 $\forall s$ で以下が成り立つ。

これが成り立つとき、L1距離を測ってみると、

||p - q||_1 = \sum_s ||p(s) - q(s)|| = \sum_{s : p(s) \leq \epsilon / 3n} ||p(s) - q(s)|| \\ + \sum _{s : p(s) > \epsilon / 3n} ||p(s) - q(s)|| \leq \sum_{s : p(s) \leq \epsilon / 3n} \frac{\epsilon}{2} p(s) + \sum_{s : p(s) > \epsilon / 3n} \frac{\epsilon}{2n} \\ \leq \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon

さらに、 $S \geq c n /\epsilon^2$ で、 $||p-q||_{TV} \leq \epsilon$ ならば、最大負荷は $\Theta(\frac{\log n}{\log \log n})$

分布 $p,u$ が同じ分布であるかどうかを $O(n/\epsilon^2)$ 個のサンプルで検査できるか？できます。

なんなら、 $O(\sqrt{n}/\epsilon^2)$ 個でいいです。

$||p-u||_1>\epsilon$ とする。これの2乗ノルムは $||p-y||_2^2 > (\epsilon / \sqrt{n})^2 = \epsilon^2 / n$ である。

補題として、もし $||p-u||_1 > \epsilon$ ならば、 $||p||_2^2 > 1/n + \epsilon^2 / n$ 。

もし分布が同じであるなら、 $||p||_2^2=1/n$ である。

$||p||_2^2$ を推定する。先の補題で