皆さんは with high probability (w.h.p.) という用語をご存知でしょうか。機械学習とかグラフ理論とか色んな文脈で出てきますが文脈に応じて定義が違うのでこれらを整理したいと自分は常々思っています。
例えば、アルゴリズムを扱う文脈 (以後、文脈1と呼ぶ) では、「アルゴリズム $A$ が w.h.p. で $T(n)$ 時間で動く」と言ったときは、ある定数 $c>0$ が存在して
$$ \Pr[A \text{ runs in time }T(n)] \geq 1-n^{-c}$$
が成り立つことを意味します。
一方で、ランダムグラフなどの文脈 (以後、文脈2と呼ぶ) では「ランダムに生成されたグラフ $G$ が w.h.p. で性質$\mathcal{P}$ を満たす」と言ったときは、
$$\lim_{n\to \infty} \Pr[G\text{ satisfies }\mathcal{P}] = 1$$
が成り立つことを意味します。
つまり、文脈1の方が漸近のスピードにより厳しい条件を課しています。
自分は両方の文脈に出会うことが多いのでいつも困惑してしまいますが、
文脈2の w.h.p. は asymptotically almost surely (a.a.s.) と言うこともあるようなので、
・文脈1 → w.h.p.
・文脈2 → a.a.s.
と使い分けるようにしています。基本的には両者が同時に出てくることは高確率でないとは思うのですが、自分はレアケースを引いてしまいました...
他にも似たような数学用語として
・almost surely (a.s.)
・almost everywhere (a.e.)
などがありますが、a.e. は測度論で使われる用語、a.s.は確率論で使われる用語で、
・almost surely は 「確率1で」
・almost everywhere は「測度0を除いて」
という意味になるので、基本的には連続の空間で意味をなす用語です。
0 件のコメント:
コメントを投稿