漸近理論

漸近理論#

関係する定理#

マルコフの不等式#

マルコフの不等式

非負の確率変数 $X$ と任意の定数 $c > 0$ に対して、

P (X \geq c) \leq \frac{E [X]}{c}

が成立する。

マルコフの不等式は 期待値よりも極端に大きな値を取る確率が低い ことを意味する。

例えば $c = 5 E [X]$ とおけば

P (X \geq 5 E [X]) \leq \frac{E [X]}{5 E [X]} = \frac{1}{5}

from scipy.stats import expon
mean = 2  # 期待値 E[X] = 2 の指数分布は scale=2
dist = expon(scale=mean)
threshold = 5 * mean # 5 * E[X]
# P(X >= 5 * E[X]) = 1 - CDF(threshold)
prob = 1 - dist.cdf(threshold)
upper_bound = 1 / 5 # マルコフの不等式の上限
print(f"P(X >= 5E[X]) = {prob:.2g}")
print(f"Markov Inequality Upper Bound = {upper_bound:.2g}")

P(X >= 5E[X]) = 0.0067
Markov Inequality Upper Bound = 0.2

チェビシェフの不等式#

チェビシェフの不等式

$E [X] = μ, Var [X] = σ^{2}$ がいずれも有限な確率変数 $X$ を考える。

このとき任意の $c > 0$ に対して

P (| X - μ | \geq c) \leq \frac{σ^{2}}{c^{2}}

が成立する。

チェビシェフの不等式は 期待値から値が極端に離れる確率が低い ことを意味する。

例えば $c = 5 σ$ とおけば

P (| X - μ | \geq 5 σ) \leq \frac{σ^{2}}{5 σ^{2}} = \frac{1}{5}

例：2シグマ範囲#

期待値からの2シグマ範囲には正規分布だと95%が入る。

import numpy as np
from scipy.stats import norm
mu = 0       # 平均
sigma = 1    # 標準偏差
lower = mu - 2 * sigma
upper = mu + 2 * sigma
dist = norm(loc=mu, scale=sigma)
# P(∣X−μ∣ ≤ 2σ) = P(μ−2σ ≤ X ≤ μ+2σ) = cdf(μ+2σ) - cdf(μ-2σ)
p_2sigma = dist.cdf(upper) - dist.cdf(lower) # P(-2σ <= X <= 2σ)
print(f"P(∣X−μ∣ ≤ 2σ) = {p_2sigma:.3f}")

P(∣X−μ∣ ≤ 2σ) = 0.954

../../_images/c69ce4956fb68baae3345189481a8997bfe33f94ea7782d1efef2c4fb3da09b9.png

チェビシェフの不等式による任意の分布への下限は

\begin{array}{r} \begin{aligned} P (X \in [μ - 2 σ, μ + 2 σ]) = P (| X - μ | \leq 2 σ) & \geq 1 - P (| X - μ | \geq 2 σ) \\ = 1 - \frac{σ^{2}}{4 σ^{2}} \\ = 1 - \frac{1}{4} \\ = \frac{3}{4} \end{aligned} \end{array}

となり、正規分布以外でも75%以上あることがわかる

例：期待値からのズレ#

$n$ 個のサンプル $X_{1}, \dots, X_{n}$ がi.i.d.であるとする。これらのサンプルの標本平均 $\bar{X}$ がその期待値 $E [\bar{X}]$ からどれだけズレるかを見てみる

P (| \bar{X} - E [\bar{X}] | \geq c) \leq \frac{Var [\bar{X}]}{c^{2}}

もし $c = 1$ なら、標本平均と期待値の差の絶対値が1以上になる確率はその分散が上限になるということ。

P (| \bar{X} - E [\bar{X}] | \geq 1) \leq Var [\bar{X}] = \frac{Var [X]}{n}

例えばサンプルが商談から成約したかどうかであり、真の成約率が20%という確率変数 $X \sim B e r (p = 0.2)$ の実現値だとすると、 $E [\bar{X}] = 0.2, Var [\bar{X}] = p (1 - p) = 0.16$ で、このとき $c = 0.1$ とおけば

P (| \bar{X} - 0.2 | \geq 0.1) \leq \frac{0.16}{n \times {0.1}^{2}} = \frac{16}{n}

となり、仮に $n = 100$ なら16%程度の確率が上限（分布によらない上限）になることがわかる

../../_images/9b1d669715fe02314d62c1a4435070542d53a072664858ae0eceda87c39b85f1.png

ヘフディングの不等式#

チェビシェフの不等式は幅広い範囲で有用ではあるものの、裾の確率を緩く評価してしまう。

例えば上記の期待値からのズレの例

P (| \bar{X} - 0.2 | \geq 0.1) \leq \frac{16}{n}

では、 $n = 1000$ であっても「 $1.6 %$ は起こるかもしれない」というかなり安全に寄った評価をしてしまう。これは実際にシミュレーションすると0%になるレベルの稀少な事例にもかかわらず。

../../_images/c84b8204a17a5b07e664b8b3257fb34aa2ba12ac420c06a98c8d2a5e9fde2aa2.png

このような裾の確率をより厳しく抑えるのに役立つのが ヘフディングの不等式 (Hoeffding’s inequality)

定理（ヘフディングの不等式）

$X_{1}, \dots, X_{n}$ を独立な確率変数、 $\bar{X} = \frac{1}{n} \sum_{i = 1}^{n} X_{i}$ をその標本平均とし、各 $X_{i}$ は区間 $[a_{i}, b_{i}]$ に値を取るとすると、任意の $c > 0$ に対して

P (| \bar{X} - E [\bar{X}] | \geq c) \leq 2 \exp (- \frac{2 n^{2} c^{2}}{\sum_{i = 1}^{n} (b_{i} - a_{i})^{2}})

が成り立つ。

すべての確率変数 $X_{i}$ が区間 $[0, 1]$ に値を取る場合はもっと単純に

P (| \bar{X} - E [\bar{X}] | \geq c) \leq 2 \exp (- 2 n c^{2})

となる。

前出の成約率の例だと、 $n = 1000, c = 0.1$ のとき

\begin{array}{r} \begin{aligned} P (| \bar{X} - E [\bar{X}] | \geq 0.1) & \leq 2 \exp (- 2 \times 1000 \times {0.1}^{2}) \\ = 2 \exp (- 20) \\ \approx 4.122 \times 10^{- 9} \approx 0 \end{aligned} \end{array}

となり、観測結果に近くなる。

しかし $n = 100, c = 0.1$ のとき

\begin{array}{r} \begin{aligned} P (| \bar{X} - E [\bar{X}] | \geq 0.1) & \leq 2 \exp (- 2 \times 100 \times {0.1}^{2}) \\ = 2 \exp (- 2) \\ \approx 0.27 \end{aligned} \end{array}

とだいぶ大きく評価することもある様子…？

確率収束#

（定義）確率収束

サンプル数 $n$ を無限大に近づけていったとき、確率変数列 ${X_{n}}_{n = 1}^{\infty}$ が定数 $c$ から外れる確率がゼロに近づく、すなわち任意の $ε > 0$ について

lim_{n \to \infty} P (| X_{n} - c | > ε) = 0, \forall ε > 0

ならば、「 $X_{n}$ は $c$ に確率収束（convergence in probability）する」といい

\underset{n \to \infty}{plim} X_{n} = c

あるいは

X_{n} \overset{p}{\to} c, (n \to \infty)

と表す

平均2乗収束#

（定義）平均2乗収束

確率変数列 ${X_{n}}_{n = 1}^{\infty}$ が確率変数 $X$ に平均2乗収束するとは

lim_{n \to \infty} E [(X_{n} - X)^{2}] = 0

となることをいう。

チェビシェフの不等式を使うと「確率変数列がある確率変数に平均2乗収束するならば確率収束する」という命題が導かれる → 大数の法則

例：大数の法則#

（定理）大数の（弱）法則

$X_{1}, \dots, X_{n}$ はi.i.d.で、 $E [| X_{i} |] < \infty$ とする。このとき、標本平均 $\bar{X}$ は $μ = E [X_{i}]$ に確率収束する

lim_{n \to \infty} P (| \bar{X} - μ | > ε) = 0

例：推定量の一致性#

推定量 $\hat{θ}$ が真のパラメータ $θ$ に確率収束

\hat{θ} \overset{p}{\to} θ

するとき、その推定量は一致性（consistency）を持つという

概収束#

（定義）概収束

確率変数列 ${X_{n}}$ が確率変数 $X$ について

P ({ω | lim_{n \to \infty} | X_{n} (ω) - X (ω) | = 0}) = 1

となるとき概収束（almost sure convergence）するといい、

X_{n} \to X a.s.

と表す。

分布収束#

（定義）分布収束

確率変数列 ${X_{n}}$ が確率変数 $X$ に分布収束（convergence in distribution）するとは、

lim_{n \to \infty} P (X_{n} \leq x) = P (X \leq x) = F_{X} (x)

が $F_{X} (x)$ のすべての連続な点で成り立つことをいい、 $X_{n} \overset{d}{\to} X$ と表す。

例：中心極限定理#

確率変数列 ${X_{n}}_{n = 1}^{\infty}$ はi.i.d.で平均 $μ := E [X_{i}]$ と分散 $σ^{2} := V a r (X_{i})$ が存在するとする。このとき、以下の分布収束が成り立つ

\sqrt{n} (\bar{X} - μ) \overset{d}{\to} N (0, σ^{2}), n \to \infty

ここで $N (0, σ^{2})$ を $\bar{X}$ の漸近分布（asymptoticd distribution）という。

（※なお、 $N (0, σ^{2})$ は正規分布を表す記号ではなく、正規分布に従う確率変数を意味するので注意。ややこしい記法だが標準的でよく見られる書き方である）

なお、上の式は

\bar{X} - μ \overset{d}{\to} \frac{1}{\sqrt{n}} N (0, σ^{2}) = N (0, \frac{σ^{2}}{n})

のように整理できる。

（ $σ^{2}$ は未知だが標本分散を用いてもこの関係性が成り立つ）

参考#

絶対に分かる機械学習理論 - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ