MIT OCW, Machine Learning 04日目 宿題

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Assignments

Problem Set 1

Section A: Background

1.

$n$人の集団で,少なくとも二人が同じ誕生日である確率を計算する関数birthday_prob(n)を書け.(Matlab指定だったがPythonでやる)

答案

import math
def birthday_prob(n):
    # n人全員の誕生日が違う場合の数は365Cn x n!. また,n人の誕生日の場合の数は365^n
    comp = (math.factorial(n)*math.factorial(365))/(math.factorial(365-n) * math.factorial(n))
    total = 365**n

    return 1 - comp/total

birthday_prob(23)
-> 0.5072972343239854

2

$X_1, ..., X_n$ はi.i.d.で,$(0, 1)$上のUniform distributionに従うとする.
(a)$E[\max(X_1, ..., X_n)]$, (b)$E[\min(X_1, ..., X_n)]$を求めよ.
答案

確率論でやった.
(a) $X= \max(X_1, ..., X_n)$とする.
$X \leq x \Leftrightarrow (X_1 \leq x) \land ... \land (X_n \leq X)$
独立性より$P(X \leq x) = P(X_1 \leq x) P(X_2 \leq x) ...P(X_n \leq X) = x^n$
PDFは$nx^{n-1} \text{a.e.}$よって
$$E[X] = \int_0^1 xnx^{n-1} = \frac{n}{n+1}$$
(b) $Y = \min(X_1, ..., X_n)$とする.
$$\begin{aligned}X \leq y &\Leftrightarrow P(x \leq X_1)P(x \leq X_2)...P(x \leq X_n) \\ &= (1-P(X_1 < x))...(1-P(X_n < x)) \ \ \ &\text{(独立性)} \\ &= (1-P(X_1 \leq x))...(1-P(X_n\leq x)) &\text{CDFの連続性}\\&=(1-x)^n \end{aligned}$$
PDFは$-n(1-x)^{n-1} \text{ a.e.}$よって
$$E[Y] = \int^1_0 -n(1-x)^{n-1}x dx=\frac{1}{n+1}$$

3.

16の二人組があって,計32人のうち4人が風邪を引いてしまう.このときまだ組める二人組の数の期待値を求めよ.
答案

全ての事象の場合の数$\ _{32}C_4= 35960$
- 2つの組が全員風邪を引く場合の数: $\ _{16} C_2=120$
- 1つの組が二人風邪を引き,もう２つの組が一人づつ風邪を引く場合の数: $16 \times \ _{15}C_2 \times 2 \times 2 = 6720$
- 4つの組で一人づつ風邪を引く場合の数: $\ _{16}C_4 \times 2^4 = 29120$

以上より求める期待値は$(14 \times 120 + 13 \times 6720 + 12 \times 29120) / 35960 = \frac{378}{31}$

4 (Monty Hall)

3つのドアがあって,そのうち1つは当たり,他の２つは外れである. 1つのドアを選ぶと,Monty Hallは他の２つのドアのうち外れのドアを一つだけ教えてくれて,さらにもう一度ドアを選び直させてくれる.
(a) ドアを最初に選んだドアから選び直すべきだろうか？
(b) この試行を1000回おこなうプログラムを書き,結果を説明せよ.
(c) ドアを4つに増やしたほかは同じゲームを考える. 最初に選んだドアからドアを選び直すべきだろうか? そのとき, どのドアを改めて選ぶべきだろうか?
答案.

(a)
最初に選ぶドアを$A$,もう２つのドアを$B,C$とする.$1$で当たり,$0$ではずれ,$-1$でMontyがドアを選ぶという事象を表すことにする.
$P(A=1)=P(B=1)=P(C=1)=1/3$.
$\begin{aligned}P(A=1|B=-1) &=P(A=1 \land B=-1)/P(B=-1) \\ &= (\frac{1}{3} \times \frac{1}{2}) /(\frac{1}{3} \times (\frac{1}{2}+1)) = \frac{1}{3} \end{aligned}$
$\begin{aligned}P(C=1|B=-1) &=P(C=1 \land B=-1)/P(B=-1) \\ &= (\frac{1}{3} \times 1) /(\frac{1}{3} \times (\frac{1}{2}+1)) = \frac{2}{3} \end{aligned}$
$\because P(B=-1) = \sum_{X \in \{A, B, C\}}P(B=-1|X=1)P(X=1)$
だから,ドアを選び変えたほうが良い.
(b)

def monty_trial(change = True):
    # ドアを0, 1, 2とする. 当たりのドアは毎回ランダムに生成され,最初に0のドアを選ぶとする.
    success = random.randint(0, 2)
    chosen = 0

    # 当たりのドアによって場合分けする.
    if success == 0:
        monty = random.randint(1, 2) # モンティがひらくドア
    elif success == 1:
        monty = 2
    else:
        monty = 1

    if change:
        chosen = 3 - monty

    if success == chosen:
        return 1
    else:
        return 0


cnt0 = 0
cnt1 = 0
for i in range(1000):
    cnt0 += monty_trial(True)
    cnt1 += monty_trial(False)

print(cnt0/1000)
print(cnt1/1000)

->

0.663
0.361

から, 確かに理論的な値に近い.

(c) (a)と同じ理由でドアを選び変えるべきだが,対称性から,どちらのドアを選んでも同じ.

5

(a) $X$は正規分布のベクトルで
$$E[X] = (10, 5)^T, cov(X) = \left(\begin{array}{} 2 & 1 \\ 1 & 1 \end{array}\right)$$
とする. $X$のpdfを,joint PDF $P(x_1, x_2)$の形で書け.
(b) $A, B$は$p \times q$行列で,$x$は$q$次元のrandom variable vectorとする.
$$cov(Ax, Bx) = Acov(x) B^T$$
を示せ.

答案.

(a)
確率論で学んだ定義(def. 15-2)を書くと,
$$\begin{aligned}f_X(\mathbf{x})&= \frac{1}{\sqrt{(2\pi)^n |\det V|}} \exp\left[ -\frac{(\mathbf{x}-\mu)V^{-1}(\mathbf{x}-\mu)^T}{2}\right] \\ &= \frac{1}{2\pi} \exp \left[-\frac{(x_1-10, x_2-5) \left(\begin{array}{} 1 & -1 \\ -1 &2 \end{array}\right) (x_1-10, x_2-5)^T}{2} \right] \\ &= \frac{1}{2\pi} \exp(-(x_1^2 -2x_1x_2 - 10x_1 +2x_2^2 + 50)) \end{aligned}$$
が成立する.

(b)
$$\begin{aligned} cov(Ax, Bx) &= E[(Ax-E[Ax])(Bx-E[Bx])^T] \\ &= E[(Ax-AE[x])(Bx-BE[x])^T] \\ &= E[Axx^TB^T - AxE[x]^TB^T - AE[x] x^T B^T + AE[x]E[x]^T B^T] \\ &= AE[xx^T]B^T =Acov(x)B^T \end{aligned}$$

6

Gram-Schmidtの直行化法を使って,
$(0,0,0,0,0,1)^T, (1,2,3,4,5,6)^T, (1,4,9,16,25,36)^T, (1,0,0,0,0,0)^T$を正規直行化せよ

答案.
>

import numpy as np
def GS(arrays):
    n = len(arrays)
    dim = len(arrays[0])

    us = []

    for i in range(n):
        u_proto = arrays[i]
        for j in range(i):
            u_proto = u_proto - us[j] * np.dot(us[j],arrays[i])
        us.append(u_proto/np.linalg.norm(u_proto) )

    return us

GS([np.array([0,0,0,0,0,1]), np.array([1,2,3,4,5,6]), np.array([1,4,9,16,25,36]), np.array([1,0,0,0,0,0])])

->

[array([ 0., 0., 0., 0., 0., 1.]),
array([ 0.13483997, 0.26967994, 0.40451992, 0.53935989, 0.67419986, 0. ]),
array([-0.40396119, -0.54653573, -0.42772361, -0.04752485, 0.59406057, 0. ]),
array([ 0.9047837 , -0.28420368, -0.25125253, -0.10159938, 0.16475576, 0. ])]


MIT OCW, Fundamentals of Probability 21日目 確率過程II

David Gamarnik, and John Tsitsiklis. 6.436J Fundamentals of Probability. Fall 2008. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 21. The Poisson Process Continued

1. Memorylessness in The Poisson Process

Poisson processはBernoulli processの連続時間版で,Bernoulli processのmemorylessnessを受け継いでいる. 特にPoisson processがあって,ある固定した$t^*$や,未来を見ずに決めた$t=S$に観測を始めると,観測しているprocessはPoisson processである. より形式的な性質を証明無しで挙げるが,それらの性質は今後よく使うことにする.
まず,連続時間におけるstopping timeを導入する.

Definition 21-1

random variable $S\geq 0$が stopping timeである
$\Leftrightarrow$ 任意の$s \geq 0$について, $\{S \leq s\}$というeventが起こるか否かが,あるrandom variable $N(t)$の,$t \leq s$における現れに寄ってのみ決まる.

より形式的に・・・

任意の$s\geq 0$について,$\mathcal{F}_s=\sigma(\cup_{t \in [0, s], k \in \{0, 1, ...\}}\{N(t)=k\})$によって$\sigma$-algebra $\mathcal{F}_s$を定義して,$\{S\leq s\} \in \mathcal{F}_s$であるとき,$S$はstopping timeである.

Example

first arrival $T_1$は,$\{T_1 \leq s\}$が$\{N(s) \geq 1\}$と同じことであり,後者は$N(s)$の現れによって決まるから,$T_1$はstopping timeである.

stopping time $S$から観測を始めたarrival process $\{M(t)\}$を,$M(t) = N(S+t)-N(S)$と定める.このとき$\{M(t)\}$はパラメータ$\lambda$をもとのprocessから受け継ぐPoisson processである. さらに,$\{M(t)|t \geq 0\}$ (すなわち$S$以降の未来)は$\{N(\min\{t, S\})|t\geq 0\}$ (すなわち$S$の過去)と独立である.

MIT OCW, Machine Learning 03日目 logistic regression

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 4. Classification Errors, Regularization, Logistic Regression

The Support Vector Machine and Regularization

$$\begin{aligned}&\text{minimize} \frac{1}{2}\|\theta\|^2 + C\sum_{t=1}^n \xi_t \\ &\text{subect to } y_t(\theta^T \mathbf{x}_t +\theta_0)\geq 1-\xi_t \text{ and } \xi_t \geq 0 \text{ for all } t= 1, ..., n \end{aligned}$$
が,relaxationを入れた線形分離のパラメータを求める最適化問題であった.
$y_t(\theta^T \mathbf{x}_t + \theta_0) \geq 1-\xi_t$を変形して,$\xi_t \geq 1 -y_t(\theta^T\mathbf{x}_t + \theta_0)$. $\xi_t \geq 0$だから,$()^+: r \mapsto \max(0, r)$として,example $\mathbf{x}_t$に対するhinge loss
$$\hat{\xi}_t = (1-y_t(\theta^T\mathbf{x}_t + \theta_0))^+$$
を定義する. 束縛条件とrelaxation項をまとめて,
$$\text{minimize } \frac{1}{2}\|\theta\|^2 + C \sum_{t=1}^n \underline{(1-y_t(\theta^T\mathbf{x}_t+\theta_0))^+}_{\hat{\xi_t}}$$
とできる. これは,$\frac{1}{2}\|\theta\|^2$をregularization penaltyとして$C\sum_{t=1}^n \hat{\xi_t}$を目的関数とする最適化問題と見ることが出来る. このように,classification lossのような目的関数とregularization penaltyを含む最適化問題をregularization problemという. 多くの機械学習アルゴリズムはregularization problemと見ることができて,regularization項は目的関数の最小化を安定させたり,事前の知識をアルゴリズムに組み込むために導入される.

Logistic Rgeression, Maximum Likelihood Estimation

labellingの間違いに対処するもう一つの方法に,labelの間違い(ノイズ)がどのように生成されるかをモデル化するというのがある. linear classificatioにおけるノイズの単純なモデルにlogistic regressionがある. decision boundaryから遠く離れたexampleのラベルはより正しい確率が高いというふうに,２つのラベルにprobability distributionを与えるのである.形式的には
$$P(y=1|\mathbf{x}, \theta, \theta_0) = g(\theta^T \mathbf{x}+ \theta_0)$$
とする. ここで$g(z) = (1+\exp(-z))^{-1}$で, logistic functionという. この関数は
$$\log \frac{P(y=1|\mathbf{x}, \theta, \theta_0)}{P(y=-1|\mathbf{x}, \theta, \theta_0)} = \theta^T \mathbf{x} +\theta_0$$
から導かれる.例えば$P(y=1|\mathbf{x}, \theta, \theta_0) = P(y=-1|\mathbf{x}, \theta, \theta_0)=1/2$ならばlog-oddsは$0$であり,$\mathbf{x}$はdecision boundary上に有る.左辺をlog-oddsという.log-oddsの厳密な正当化は後でclass-conditional distributionの仮定をもとに行う.

$1-g(z)=g(-z)$から,
$$P(y=-1|\mathbf{x},\theta,\theta_0)=1-P(y=1|\mathbf{x},\theta,\theta_0) = 1-g(\theta^T\mathbf{x}+\theta_0)=g(-(\theta^T\mathbf{x}+\theta_0))$$
であって,故に
$$P(y|\mathbf{x}, \theta, \theta_0) = g(y(\theta^T\mathbf{x}+\theta_0))$$
である.こうして,labelを確率的に推測するlinear classifierが得られた.training dataのそれぞれのexampleを正しく推測する確率を最大にすることを考える.この確立たちの総乗を
$$L(\theta, \theta_0) = \prod_{t=1}^n P(y_t|\mathbf{x}_t, \theta, \theta_0)$$
と書く.また$L(\theta, \theta_0)$を(conditional) likelihood functionといって,固定されたtraining dataに対するパラメータの関数である. これを最大化する$\theta, \theta_0$をmaximum likelihood estimatesという. また,training dataからmaximum likelihood estimatesを探す手続き(写像)をmaximum likelihood estimatorという.
$L$を最大化するため,logをとって,
$$\begin{aligned}-l(\theta, \theta_0) &= \sum_{t=1}^n -\log P(y_t |\mathbf{x}_t, \theta, \theta_0) \\ &= \sum -\log g(y_t(\theta^T \mathbf{x}_t + \theta_0)) \\ &= \sum \log [1 + \exp(-y_t(\theta^T \mathbf{x}_t + \theta_0))] \end{aligned}$$
を最小化することになる. この関数は凸で,多くの最適化アルゴリズムが存在する. (stochastic) gradient descent(SGD)を導入する.
$-l(\theta, \theta_0)$で偏微分して,
$$\begin{aligned}\frac{d}{d\theta_0} \log[1+\exp(-y_t(\theta^T \mathbf{x}_t + \theta_0))] &= -y_t[1-P(y_t|\mathbf{x}_t,\theta,\theta_0)] \\ \frac{d}{d\theta} \log [1+\exp(-y_t(\theta^T \mathbf{x}_t+\theta_0))] &= -y_t\mathbf{x}_t [1-P(y_t|\mathbf{x}_t,\theta,\theta_0)] \end{aligned}$$
右辺のベクトルは$\log[1+\exp(-y_t(\theta^T \mathbf{x}_t+\theta_0))]$が単位長さあたり最も増加する$\theta_0, \theta$の方向を表しており,
$$\begin{aligned} \theta_0 &\leftarrow \theta_0 +\eta \cdot y_t[1-P(y_t|\mathbf{x}_t, \theta, \theta_0)] \\ \theta &\leftarrow \theta + \eta \cdot y_t\mathbf{x}_t [1-P(y_t|\mathbf{x}_t, \theta, \theta_0)] \end{aligned}$$
によって更新を行う. ここで$\eta$は小さい正数で,learning rateという. $[1-P(y_t|\mathbf{x}_t, \theta, \theta_0)]$は間違ったlabelに分類する確率で,perceptron mistake driven updatesに似ているが,どれほど間違っているかによって更新の大きさを変えるところが重大な相違点である.
stochasticでないgradient descentは, $\theta, \theta_0$を固定して,全ての$t$に$\eta \cdot y_t[1-P(y_t|\mathbf{x}_t, \theta, \theta_0)], \eta \cdot y_t\mathbf{x}_t [1-P(y_t|\mathbf{x}_t, \theta, \theta_0)]$を足し合わせて,その和によって$\theta, \theta_0$を更新する.
最適化が実現したときには
$$\begin{aligned}\frac{d}{d\theta_0} (-l(\theta, \theta_0))&= -\sum_{t=1}^n y_t[1-P(y_t|\mathbf{x}_t,\theta,\theta_0)]=0 &(19)\\ \frac{d}{d\theta}(-l(\theta, \theta_0)) &= -\sum_{t=1}^n y_t\mathbf{x}_t [1-P(y_t|\mathbf{x}_t,\theta,\theta_0)] =0 \ \ \ &(20)\end{aligned}$$
が成立する.$(19)$は,”label 1のexapleを-1に間違えて分類する確率”と”label -1のexampleを+1に間違えて分類する確率 $\times -1$”の総和が$0$であるということであって,間違いが均衡しているということである. あるいは,$(y_1, ..., y_n)^T$というベクトルと,$(1-P(y_1|\mathbf{x}_1,\theta,\theta_0), ..., 1-P(y_n|\mathbf{x}_n,\theta,\theta_0))^T$というベクトルが直行しているということである.
同様に,$(20)$の等式は,exampleのそれぞれの次元$j$において,$(y_1 x_{1j},...,y_n x_{nj})^T$と$(1-P(y_1|\mathbf{x}_1,\theta,\theta_0), ..., 1-P(y_n|\mathbf{x}_n,\theta,\theta_0))^T$が直行しているということである.
この直交性によって$(19,20)$が成立しているとき,training setにはもはや$\theta, \theta_0$をより良くするための情報が無いということがわかる.

ところで,$y_t(\theta^T \mathbf{x}_t+\theta_0)$が常に正である$\theta, \theta_0$をみつけて両方を定数倍してこれらの値を際限なく大きくすると,$y_t[1-P(y_t|\mathbf{x}_t, \theta, \theta_0)]$は$1$に収束し,わざわざ確率的なモデルを使う意味がなくなってしまうので,regularziation項$\|\theta\|/2$を加えて最適化する.すなわち

$$\frac{1}{2}\|\theta\|^2 + C\sum_{t=1}^n \log [1+\exp(-y_t(\theta^T\mathbf{x}_t+\theta_0))]$$
の最少化問題とする.またこれは
$$\frac{\lambda}{2}\|\theta\|^2 + \sum_{t=1}^n \log [1+\exp(-y_t(\theta^T\mathbf{x}_t+\theta_0))] \ \ \ (26)$$
の最小化と同じことであり,どれほどregularizationを強くするかの係数が$\lambda$であるのがわかりやすいので,(26)の記法がよく使われる.っている.

MIT OCW, Fundamentals of Probability 20日目 確率過程I

David Gamarnik, and John Tsitsiklis. 6.436J Fundamentals of Probability. Fall 2008. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 20. The Bernoulli and Poisson Processes

stochastic process(確率過程)の議論をする準備ができた.
discrete-time stochastic processは共通したprobability space $(\Omega, \mathcal{F}, P)$上のrandom variableの列$\{X_n\}$である. あるいは,$n, \omega$を引数に取る関数$X$で,任意の$n$に$X_n:\omega \mapsto X_n(\omega)$というrandom variableということであって,また$\omega \in \Omega$を固定したときには$n$の関数(“time function”,とか “sample path”, “trajectory”という)と見ることも出来る.

1. The Bernoulli Process

Bernoulli processでは$X_n\sim Ber(p)$で,全てがi.i.d.である.$S_n = X_1 +...+X_n$とすると,$S_n\sim bin(n,p)$であって
$$p_{S_n}(k) = \left(\begin{array}{} n \\ k\end{array} \right) p^k(1-p)^{n-k},\ E[S_n]=np \ var(S_n)=np(1-p)$$
である.ただし$p_{S_n}$はPMFとする.
また$T_1$を最初に試行が成功するまでの試行数とすると,$T_n \sim geom(p)$であって,
$$p_{T_1}(k) = (1-p)^{k-1}p, E[T_1] = 1/p$$
である.

1.1 Stationarity and Memorylessness

Bernoulli processには特有の構造が有る.

Bernoulli process $\{X_n\}$を考える.ある自然数$m$を固定して,$Y_n = X_{m+n}$とすると,$\{Y_n\}$は$\{X_n\}$と同じdistributionを持ったBernoulli processである. より厳密には,$(Y_1, ..., Y_k)$は$(X_1, ...,X_k)$と同じdistributionを持っている.この性質をstationarity(定常)性という.
また,より強い性質も成り立つ.$X_1, ..., X_m$の値が与えられても,$\{Y_n\}$は変化しない.形式的には
$$\begin{aligned}P((X_{n+1}, X_{n+2},...) \in A|X_1, ...,X_n) &=_{(1)} P((X_{n+1}, X_{n+2}, ...) \in A) \\ &=_{(2)} P((X_1,X_2, ...) \in A)\end{aligned}$$
である.(1)の等式をmemoryless(無記憶)性という.(2)の等号はstationarity propertyの言い換えである.

1.2 Stopping Times

1.1では観測を始める時刻を$m$に固定して議論したが,観測を始める時間がまた確率的に決まる場合を考える.$N$は非負整数値をとるrandom variableとして,$\{Y_n\}$を$Y_n = X_{N+n}$を議論する. $\{Y_n\}$は一般に$\{X_n\}$と同じパラメータのBernoulli processではない. 例えば$N= \min\{n|X_{n+1}=1\}$とすると$P(Y_1=1)=P(X_{N+1}=1)=1 \neq p$である.この不等号は$N$を$X_{N+1}$の実現値が決まってから,すなわち”未来を見て”決めたことに起因している.
一方$N$がcausallyに決まるとき,つまり過去か現在のprocessのみから決まるとき,形式的には

Definition 20-1

$N$がstopping timeである
$\Leftrightarrow$ 任意の$n$について,$\{N=n\}$というeventが起きるか否かが,$X_1, ...,X_n$の顕れに寄ってのみ決まる
またこのとき,任意の$n$に$h_n$という関数があって,
$$I_{N=n} = h_n(X_1, ..., X_n)$$
が成立する.

として,$N$がstopping timeであるときにはmemorylessnessより強い性質を持つ.
$$\begin{aligned} P((X_{N+1}, X_{N+2},...)\in A|N=n, X_1, ...,X_n) &= P((X_{n+1}, X_{n+2}, ...)\in A) \\&= P((X_1, X_2, ...) \in A)\end{aligned}$$
したがって$N$がstopping timeであれば$\{Y_n\}$はまたBernoulli processである.

1.3 Arrival and Interarrival Times

$Y_k = \min\{n|S_n = k\}, Y_0=0$は$k$th arrival timeといい, $k$th interarrival timeを$T_k = Y_k-Y_{k-1}$とする.
$T_1 = Y_1$はgeometricで,またstopping timeだから,$(X_{T_1+1}, X_{T_1 +2}, ...)$もまたBernoulli processである. $T_2$はもとのprocessのsecond interarrival timeだが$(X_{T_1+1}, X_{T_1 +2}, ...)$のfirst arrival timeであって,よって$T_2$はgeometricである.さらに,新しいprocessは$(X_1, ..,X_{T_1})$と独立であって,$T_2$もまた$(X_1, ...,X_{T+1})$と独立である.特に$T_2$は$T_1$とも独立である.
上の段落の議論を繰り返すと,$T_k$はi.i.d. geometricであることがわかる.結果,$Y_k$は$k$のi.i.d. geometricの和だから,$S_t=X_1 + \cdots X_t$として,
$$\begin{aligned} P(Y_k =t) &= P(S_{t-1}=k-1 \land X_t=1) = P(S_{t-1} =k-1) \cdot P(X_t=1) \\&= \left(\begin{array}{} t-1 \\ k-1\end{array} \right)p^{k-1}(1-p)^{t-k}p = \left(\begin{array}{} t-1 \\ k-1\end{array} \right)p^k(1-p)^{t-k} \end{aligned}$$
である.この$Y_k$のPMFをPascal PMFという.

1.4 Marging and Splitting of Bernoulli Processes

$\{X_n\}$と$\{Y_n\}$は独立なBernoulli processで,パラメータはそれぞれ$p, q$とする. $\{Z_n\}$を,$X_n,Y_n$の”merged” processとして,$Z_n = \max\{X_n, Y_n\}$と定義する.
$$P(Z_n = 1) = 1-P(X_n=0, Y_n=0) = 1-P(X_n=0)P(Y_n=0) = 1-(1-p)(1-q)$$
だから,$Z_n\sim Ber(p+q-pq)$であって,$\{Z_n\}$はまたBernoulli processとなる.

また,$\{Z_n\sim Ber(p)\}$というprocessを”Splitting”するprocessも考えられる.$Z_n = 1$となったらコインを投げ($Ber(q)$),その結果を記録していく仮定を考える.
形式的には$\{U_n\sim Ber(q)\}$として
$$X_n = Z_n \cdot U_n,\ Y_n = Z_n \cdot(1-U_n)$$
とする.$\{X_n\}$はパラメータ$pq$のBernoulli processであり,$\{Y_n\}$はパラメータ$p(1-q)$のBernoulli processである. $\{X_n\}, \{Y_n\}$はdependentである.特に
$P(X_n=1|Y_n=1)=0 \neq pq = P(X_n=1)$である.

2. The Poisson Process

Poisson processはBernoulli processの連続時間への近似と考えることが出来る.時刻0から観測を初めて,時刻$t$までに起きた成功の回数をrandom variableとする.つまり,$N(0)=0$とし,$N(t)$を$(0, t]$の間の成功の回数とすると,$N$はpoisson過程である.
ある$\omega$を固定して,$N(t)$を時刻$t$における$N$の現れとする.これは$t$で成功しているならその点で不連続であり,右連続である:$\lim_{\tau \downarrow t} N(\tau) = N(t)$.
Bernoulli processと同様にいくつかのrandom variableを定義する.
$$Y_0=0,\ Y_k=\min\{t|N(t)=k\},\ T_k = Y_k-Y_{k-1}$$
さらに$P(k;t) = P(N(t)=k)$とする.
$\lambda > 0$として,Poisson processは以下の性質によって定義される.
(a)

互いに素な区間たちがあって,その中で成功が起こる回数はindependentである.形式的には,
$0<t_1<...<t_k$で,$N(t_1), N(t_2)-N(t_1), ..., N(t_k)-N(t_{k-1})$はindependentである.これはBernoulli processの試行の独立性の近似である.

(b)

ある区間における成功の回数のdistributionは$\lambda$と区間の長さのみによって決まる.形式的には,$t_1<t_2$ならば
$$P(N(t_2)-N(t_1)=k) = P(N(t_2-t_1)=k) = P(k; t_2-t_1)$$
である.

(c)

$o_k$という関数があって,
$$\lim_{\delta \downarrow 0} \frac{o_k(\delta)}{\delta}=0$$
かつ任意の$\delta > 0$に
$$\begin{aligned} P(0;\delta) &= 1 - \lambda \delta + o_1(\delta)\\ P(1;\delta) &= \lambda \delta + o_2(\delta) \\ \sum_{k=2}^\infty P(k;\delta)&=o_3(\delta) \end{aligned}$$
である

$o_k$はテイラー展開の2次以降の項を捉えるために導入される.

2.1 The Distribution of N(t)

$\lambda$と$t>0$を固定して,$P(k;t)$のclosed form expressionを考える.$(0, t]$という区間を,同じ区間に複数の成功がないように細かく区切って,Bernoulli processで近似する.
大きな$n$を一つ選び,$\delta = t/n$とする.$[0, t]$を長さ$\delta$ごとに区切り,$n$個の”slot”をつくる. 少なくとも１つの成功があるslotにある確率は
$$p = 1-P(0;\delta) = \lambda \delta + o(\delta) = \frac{\lambda t}{n} +o(1/n)$$
である.ただし$o(\delta)/\delta \rightarrow 0$である.
$k$を固定して,以下のeventたちを定義する.

A: $(0, t]$でちょうど$k$回成功する
B: ちょうど$k$個のslotがそれぞれ1つ以上の成功をもつ
C: 少なくとも1角slotが2つ以上の成功を持つ.

$A, B$は$C$が起きない限り一致する.
$$B \subset A \cup B, \ A \subset B \cup C$$
であって
$$P(B)-P(C) \leq P(A) \leq P(B)+P(C)$$
が成立する.ここで
$$P(C) \leq n \cdot o_3(\delta) = (t/\delta) o_3(\delta)$$
右辺は$n \rightarrow \infty \Leftrightarrow \delta \rightarrow 0$で$0$に収束するから,$P(A)$は$n\rightarrow \infty$で$P(B)$に収束する.
成功があったslotの個数はbinomial distributionに従い,そのパラメータは$n=n, p = \lambda t/n+o(1/n)$であって,
$$P(B) = \left(\begin{array}{} n \\k \end{array}\right)\left(\frac{\lambda t}{n} + o(1/n) \right)^k \left(1 - \frac{\lambda t}{n} +o(1/n)\right)^{n-k}$$
が成立する. $n\rightarrow \infty$とすると,Lec.6と同様の計算で,右辺はPoisson PMFに収束し,
$$P(k;t) = \frac{(\lambda t)^k}{k!} e^{-\lambda t}$$
が成立する.これは$(t)$が$\lambda t$をパラメータとするPoisson random variableであることを示している.また$E[N(t)]=var(N(t))=\lambda t$である.

2.2 The distribution of $T_k$

Bernoulli processと同様に, interarrival times $T_k$がi.i.d. でexponentialなrandom variableであることを示す.

2.2.1 First argument

$$P(T_1 > t) = P(N(t)=0) =P(0;t) = e^{-\lambda t}$$
である.これはexponentila CDFだから,
$$f_{T_1}(t) = \lambda e^{-\lambda t}$$
とPDFが得られる.
$t_1, t_2 >0, \ \delta < t_2$, また$\delta$は十分小さい正数とする.このとき十分狭い区間では複数個の成功は起こらないという仮定のもとで
$$\begin{aligned} P(t_1 \leq T_1 \leq &t_1+\delta, t_2 \leq T_2 \leq t_2 +\delta)\\&\sim P(0;t_1)\cdot P(1;\delta) \cdot P(0;t_2-t_1-\delta) \cdot P(1;\delta) \\ &=e^{-\delta t_1} \lambda \delta e^{-\delta(t_2-\delta)}\lambda \delta \end{aligned}$$
両辺を$\delta^2$で割って$\delta \downarrow 0$とすれば
$$f_{T_1, T_2} (t_1, t_2) = \lambda e^{-\lambda t_1} \lambda e^{-\lambda t_2}, \ t_1, t_2 > 0$$
を得る.よって$T_1, T_2$はindependentで,同じexponential distributionをもつ. 繰り返して,$\{T_k\}$はi.i.d.で,共通したパラメータ$\lambda$をもつexponential distributionに従う.

2.2.2 Second Argument

簡単のため,$\lambda = 1$とする.$0 < s \leq t$として,
$$\begin{aligned} P(Y_1 \leq s, Y_2 \leq t) &= P(N(s) \geq 1, N(t) \geq 2) \\&=P(N(s)=1)P(N(t)-N(s)\geq 1) +P(N(s) \geq 2) \\ &=se^{-s}(1-e^{-(t-s)})+(1-e^{-s}-se^{-s}) \\&=-se^{-t}+1-e^{-s} \end{aligned}$$
両辺を微分して,
$$f_{Y_1, Y_2} (s,t) = \frac{\partial^2}{\partial t \partial s} P(Y_1 \leq s, Y_2 \leq t) = e^{-t}, \ \ 0 \leq s \leq t$$
が成立する.よって,$Y_2=t$を決めると,$Y_1$は$(0, t)$上uniformである.すなわち,2回目の成功が起きるまでの時刻,1回目の成功が起きうる時刻は同様に確からしい.
$T_1 = Y_1, T_2 = Y_2 -Y_1$とすると,
$$f_{T_1, T_2} (t_1, t_2) = f_{Y_1, Y_2}(t_1, t_1+t_2) = e^{-t_1}e^{-t_2}$$
である.

2.2.3 Alternative Definition of the Poisson Process

$T_1, T_2, ...$はi.i.d. で$\lambda$を共通のパラメータ$p$のexponential distributionをもつとする. 成功した時刻$T_1, T_1+T_2, T_1 + T_2 + T_3, ...$を記録していくとして,この定義はまたPoisson processの定義(a),(b),(c)を導く.

2.3 The Distribution of $Y_k$

$Y_k$は$k$個の$exp(\lambda)$のi.i.d.なrandom variableの和だから,PDFは畳み込みを繰り返して構成できる. PDFのもう一つの導出方法を述べる.
小さな区間で2つ以上成功する可能性を無視すると,
$$P(y\leq Y_k \leq y+\delta) = P(k-1;y)P(1;\delta) = \frac{\lambda^{k-1}}{(k-1)!} y^{k-1}e^{-\lambda y}\lambda \delta$$
両辺を$\delta$で割って$\delta \downarrow 0$とし,
$$f_{Y_k}(y) = \frac{\lambda^{k-1}}{(k-1)!}y^{k-1}e^{-\lambda y} \lambda , \ \ y>0$$
が言える.これを自由度$k$のGammaかErlang(アーラン) distributionという.
他の導出に,$y\geq 0$に,$\{Y_k \leq y\}$というeventが
$\{\text{number of arrivals in the interval [0, y] is at least k}\}$
というeventと同じであることを考えれば,CDFは
$$F_{Y_k}(y) = P(Y_k \leq y) = \sum_{n=k}^\infty P(n,y) = 1-\sum_{n=0}^{k-1}P(n, y) = 1 - \sum_{n=0}^{k-1} \frac{(\lambda y)^n e^{-\lambda y}}{n!}$$
であって,$Y_k$のPDFはこれを微分することで得られる.
$$f_{Y_k}(y) = \frac{d}{dy} F_{Y_k}(y) = \frac{\lambda^k y^{k-1}e^{-\lambda y}}{(k-1)!}$$

MIT OCW, Machine Learning 02日目 SVM

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

The Support Vector Machine

大きなgeometric marginがあって線形分離できるという仮定のもとで,有限回の繰り返しでそのようなlinear classifierを与えられることを見た.Support Vector Machine(SVM)は繰り返しでなく直接そのようなlinear classifierを与える. まず,正しく線形分離を行うclassifierを見つけて(fig.1a),それからgeometric marginが最大になるように$\theta$を調節する(fig.1b).このような解は一意である.

figure 1

より形式的には,geometric marginを最大化する最適化問題となる. すなわち,$y_t\theta^T\mathbf{x}_t\geq \gamma$がすべてのtraining dataに成立するという制約条件のもとで,$\gamma_{geom}=\gamma/\|\theta\|$を最大化する. $\gamma_{geom}$を最大化する代わりに,逆数$\|\theta\|/\gamma$か$\frac{1}{2}(\|\theta\|/\gamma)^2$を最小化する問題とすることもできる.
$y_t\theta^T \mathbf{x}_t \geq \gamma$の両辺を$\gamma$で割って
$$\text{minimize } \frac{1}{2}\|\theta/\gamma\|^2 \text{ subject to }y_t(\theta/\gamma)^T \mathbf{x}_t \geq 1 \text{ for all } t= 1,...,n$$
となる.この問題の解は$\gamma$と$\theta$のそれぞれの値を与えず,$\theta$の定数倍によって得られるdecision boundaryは変わらないから,$\gamma=1$としてよい.以上から,結局
$$\text{minimize } \frac{1}{2}\|\theta|^2 \text{ subject to }y_t(\theta/)^T \mathbf{x}_t \geq 1 \text{ for all } t= 1,...,n$$
という最適化問題を解くことになる. この最適化問題はstandard SVM formであり,quadratic programming problem(目的関数が線形制約のもとのパラメータの二次関数)である. この解として得られるgeometric marginは$1/\|\hat{\theta}\|$である. decision boundaryとgeometric marginは$\gamma=1$という設定によって変化していない.

General Formulation, Offset Parameters

パラメータにoffset term $\theta_0$を加えることで,decision boundaryが必ずしも原点を通らなくとも良くなる. このときclassifierは
$$f(\mathbf{x}; \theta, \theta_0) = sign(\theta^T \mathbf{x}+\theta_0)$$
separating hyperplaneは$\theta^T\mathbf{x}+\theta_0=0$なる$\mathbf{x}$の集合である.$\theta_0$の導入によって,原点を通るlinear classifierよりも大きなmarginを取れるようになることが有る. $\theta_0$の導入によって最適化問題は
$$\text{minimize } \frac{1}{2}\|\theta|^2 \text{ subject to }y_t(\theta^T \mathbf{x}_t+\theta_0) \geq 1 \text{ for all } t= 1,...,n$$
となる.$\theta_0$は制約項においてだけ考慮する. $\theta_0$はまさしくgeometric marginを最大化するためにのみ導入されるのである.

Properties of the Maximum Margin Linear Classifier

Benefits

解はtraining dataが与えられるたびに一意に決まり,geometric marginが最大になるようにboundaryを引くから,データのノイズに対して頑強である. さらに,marginの上のexampleたち(support vectors)のみによってパラメータは決まる(これが利点であるか否かを言うには,classifierの良さをより形式的に測る方法を議論する.).

training examplesのみが与えられたときのclassifierの性能をはcross-validationによって計量される. これは単純に,training dataのある部分集合だけを使ってclassifierを訓練し,そのclassifierが選ばれなかったtraing examplesに対する成績を計測していくのである. leave-one-out cross-validationはそのような方法の一つで,traing dataから1つだけexampleを取り出して訓練を行い,取り出されたexampleを正しく判別できたか否かをたしかめ,これをtraing data全てに繰り返す. 右肩に$-i$を置くことで$i$番目のexampleを取り出して訓練したときのパラメーターを表すとすると,
$$\text{leave-one-out CV error } = \frac{1}{n} \sum_{i=1}^n \text{Loss} \left(y_i, f(\mathbf{x}_i; \theta^{-i}, \theta_0^{-i}) \right)$$
である.ただし$\text{Loss}(y, y') = \begin{cases} 1 \ \ (y\neq y') \\ 0 \ \ \text{otherwise} \end{cases}$ とする. leave-one-out CV errorが低いとよくgeneralizeできていると考えられるが,保証されているわけではない.
maximum margin linear classifierにおいて,あるexampleを除いて訓練を行ってそのexampleを判別し損ねるというのは,そのexampleがsupport vectorであるときであって,
$$\text{leave-one-out CV error} \leq \frac{number of support vectors}{n}$$
である. よって,support vectorが少ないほどよい.これを解のsparse(疎)性質という.

Problems

たった一つのexampleであっても,labelが間違っていると完全にmaximum margin classifierを変化させてしまう.

Allowing Misclassified Examples, Relaxation

labelを間違えることはよく有ることだから,これに弱いというのは致命的なので,mislabelに強くする工夫が必要である. うまく判別できないデータが与えられたとして,それがmislabelによるのか,あるいは線形分離不可能だからなのかを知ることは困難である. どちらにせよ, traing exampleに対する正確性と,未知のexampleに対する正確性にはトレードオフの関係が有ることを肝に銘じなければならない.
maximum margin classifierをmislabelに頑強にする最も単純な方法の一つにslack variableの導入が有る. それぞれのexampleに対して,どれほどmarginの内側に来てしまうかを計量し,それのtraing dataの和を小さくするようにobjective functionに付け加えるのである.形式的には
$$\text{minimize} \frac{1}{2}\|\theta\|^2 + C \sum_{t=1}^n \xi_t$$
$$\text{subject to } y_t(\theta^T \mathbf{x}_t+\theta_0) \geq 1-\xi_t \text{ and } \xi_t \geq 0 \text{ for all } t = 1, ... n$$

となる.$\xi_t$がslack variableである. example $\mathbf{x}_t$がmarginを内側にはみ出るとき$\xi_t > 0$となって,objective functionに$C\xi_t$を加え,$1/2\|\theta\|^2$の最少化を阻害し,未知のdataに対する頑強さを減じる. $C$を小さくするとよりmislabelに強いが未知のexampleに弱く,$C$を大きくするとmislabelに弱いが未知のexampleに強くなる.$C$が極端に大きくなると,slack variableを考えないのと同じことになる.

MIT OCW, Fundamentals of Probability 19日目 大数の法則と中心極限定理

David Gamarnik, and John Tsitsiklis. 6.436J Fundamentals of Probability. Fall 2008. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 18. Laws Of Large Numbers

• Lecture 18. Laws Of Large Numbers
  • 1. Useful Inequations
    • • Markov Inequality
      • Chevbyshev Inequality
  • 2. The Weak Law of Large Numbers
    • • Proposition 19-1
      • Theorem 18-1 The Weak Law of Large Numbers (証明略)
      • Theorem 19-1 The Strong Law of Large Numbers
    • 18-3 The Central Limit Theorem (中心極限定理)
      • Theorem 18-2 Central Limit Theorem, CLT
  • 19-2. The Chernoff Bound
    • 19-2.1 Upper Bound
      • Theorem 19-2 (Chernooff Upper Bound) (証明略)
      • Example
    • 19-2.2 Lower Bound
      • Assumption 19-1.
      • Theorem 19-3 (Chernoff Lower Bound)

1. Useful Inequations

Markov Inequality

$X$が非負なrandom variableなら
$$P(X \geq a) \leq E[X]/a$$

proof.

$$I_{\{X\geq a\}} \leq X/a$$
が必ず成立する.両辺のexpectationを考えれば直ちに成立.

Chevbyshev Inequality

$$P(|X - E[X]| \geq \epsilon) \leq var[X]/\epsilon^2$$

proof.

Markov inequalityで,$X = |X-E[X]|$, $a = \epsilon^2$とすれば直ちに成立.

2. The Weak Law of Large Numbers

expectationは無限回の試行の結果の平均と考えることが出来る. “有限回の試行の結果の平均(sample mean)はexpectationに近づく”ということの定式化がlaw of large numbers (大数の法則)である.
大数の弱法則と大数の強法則があり,後者は前者を導く.大数の強法則を僅かに弱くして証明し,弱法則をも導く.まずalmost sure convergenceの証明に使う補題を示す.

Proposition 19-1

$\{X_n\}$をrandom variableの列とする.独立性は仮定しない.
(i) $\sum E[|X_n|^s] < \infty, s>0 \Rightarrow X_n \rightarrow^\text{a.s.} 0$
(ii) $\forall \epsilon>0, \sum P(|X_n|>\epsilon) < \infty \Rightarrow X_n \rightarrow^\text{a.s.} 0$

proof.

(i)
$\sum_{n=1}^\infty E[|X_n|^s] =E[\sum_{n=1}^\infty |X_n|^s <\infty$がmonotone conergence theoremから成立し,ゆえに$\sum_{n=1}^\infty |X_n|^s$というrandom variableは確率1で有限. したがって$|X_n|^s \rightarrow^\text{a.s.} 0$であり,$X_n \rightarrow^\text{a.s.} 0$.
(ii)
任意の$k \in \mathbb{N}$を取って$\epsilon = 1/k$とする. Borel-Cantelli lemmaから$P(\{|X_n| > 1/k \text{ i.o.}\})=0$すなわち$\{|X_n|>1/k\}$というeventは確率1で有限回のみ起こる. したがって$P(\limsup X_n > 1/k) = 0$が任意の$k$に成立する.$\{\limsup |X_n|>1/k\}$は単調で$P(\{\limsup X_n > 0\})=0$に収束する.よって$X_n \rightarrow^\text{a.s.}0$

Theorem 18-1 The Weak Law of Large Numbers (証明略)

$\{X_n\}$がi.i.d.で$E[|X_1|] < \infty$ならば,$S_n = \sum_{i=1}^n X_i$とすると
$$\frac{S_n}{n} \rightarrow^\text{i.p.} E[X_1]$$

Theorem 19-1 The Strong Law of Large Numbers

Theorem 18-1の仮定のもとで
$$\frac{S_n}{n} \rightarrow^\text{a.s.} E[X_1]$$

proof.

$E[X^4] < \infty$を前提に加える. このとき$E[|X|] <\infty$. $|X| \leq 1+x^4$から
$$E[|X|] \leq 1 + E[X^4] < \infty$$
$E[X] = 0$を仮定し,$E[\sum (X_1 + \cdots X_n)^4/n^4] < \infty$を示す.
まず
$$E\left[\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] = \frac{1}{n^4} \sum_{i_1=1}^n \sum_{i_2=1}^n \sum_{i_3=1}^n \sum_{i_4=1}^n E[X_{i_1}X_{i_2}X_{i_3}X_{i_4}]$$
であって,i.i.d.だから,random variableたちの少なくとも１つが他のすべてのrandom variableと異なるとき$E[X_{i_1}X_{i_2}X_{i_3}X_{i_4}] = 0$. したがって,上の式で$0$出ない項は$E[X_i^4]$あるいは$E[X_i^2X_j^2] \ (i \neq j)$という形をしている. $E[X_i^4]$となる$i$は$n$通りで,$E[X_i^2X_j^2] \ (i \neq j)$となる$i, j$の組み合わせは$3n(n-1)$通りある.以上から
$$E\left[\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] = \frac{nE[X_1^4] + 3n(n-1)E[X_1^2 X_2^2]}{n^4}$$
が成立する.$xy \leq (x^2 + y^2)/2$に$x=X_1^2, y=X_2^2$を代入して$X_1^2X_2^2 \leq X_1^4+X_2^4$,expectationをとって$E[X_2^4] = E[X_1^4]$を考えれば$E[X_1^2X_2^2] \leq E[X_1^4]$が成立する.ゆえに
$$E\left[\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] \leq \frac{3n^2 E[X_1^4]}{n^4}=\frac{3E[X_1^4]}{n^2}$$
したがって
$$E\left[\sum_{n=1}^\infty\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] \leq 3E[X_1^4]\sum_{n=1}^\infty \frac{1}{n^2} < \infty$$
ゆえに$(X_1 + \cdots + X_n)^4/ n^4$は確率1で$0$に収束し,$(X_1 + \cdots +X_n)/n$もそうである.これがStrong law of large numbersの主張するところだった.
$E[X_i] \neq 0$である場合,$(X_1 + \cdots + X_n - nE[X_1])/n$が$0$にa.s.収束することは$(X_1 + \cdots + X_n) / n$が$E[X_1]$にa.s.収束することだから,成立.

$E[X^4]<\infty$の仮定を外した場合の証明は省略する.

18-3 The Central Limit Theorem (中心極限定理)

Theorem 18-2 Central Limit Theorem, CLT

$X_1, ...$がi.i.d.で,そのexpectationとvarianceをそれぞれ$\mu< \infty, \sigma^2<\infty$とする.$S_n = X_1 + \cdots +X_n$とすると,
$$\frac{S_n - n\mu}{\sigma\sqrt{n}}$$
が$N(0, 1)$にdistribution convergenceする.

proof.

簡単のため$\mu = 0, \sigma^2 = 1$とする. 1,2次のmomentが有限であることから,$\phi_{X_1}(t)$は$0$において２回微分可能である.
$$\phi_X(t) = 1 - t^2/2 + o(t^2)$$
と書ける.$S_n /\sqrt{n}$のcharacteristic functionは
$$(\phi_X(t/\sqrt{n}))^n = (1 - t^2/2n + o(t^2/n))^n$$
という形をしていて,$t$を固定して$n\rightarrow \infty$の極限は$e^{-t^2/2}$である.これは$N(0,1)$のcharacteristic function$\phi_Z$に等しい.$\phi_{S_n /\sqrt{n}}(t) \rightarrow \phi_Z(t) \forall t$から,たしかにdistribution convergenceが言えた.

CLTは$S_n/$のPDFはCDFについて何も言っていないが,以下の2つの命題が成り立つ.
(a)

$\int|\phi_{X_1}(t)|^r dt < \infty$が成立する$r$があるとき,$S_n$は$n\geq r$で連続で
$(S_n-\mu_n)/(\sigma\sqrt{n})$のPDF$f_n$は$N(0,1)$のPDFに一様収束($\Rightarrow$各点収束)する.すなわち
$$\lim_n \sup_z |f_n(z) - \frac{1}{\sqrt{2\pi}} e^{-z^2/2}|=0$$
である.

(b)

$a, h$を定数,$k$を整数として,$X_i$が$a+hk$という値を取り,$E[X]=0, var[X]=1$とする. $z=(na+kh)/\sqrt{n}$という形の$z$に,
$$\lim \frac{\sqrt{n}}{h} P(S_n=z) = \frac{1}{2\pi}e^{-z^2/2}$$
である.

19-2. The Chernoff Bound

$X, X_1, ...$はi.i.d.で,$S_n = X_1 +\cdots X_n$とする.$E[X]=0$とする. (weak) law of large numbers から, $P(S_n \geq na) \rightarrow 0$が任意の$a>0$で成立.この収束を上下から押さえる関数を与えたい.

19-2.1 Upper Bound

$M(s) = E[e^{sX}]$として,$M(s) <\infty$が$s \in [0, c], c>0$で成り立つとする.
$M_{S_n}(s) = E[e^{s(X_1 +\cdots +X_n)}]=(M(s))^n$. 任意の$s>0$にMarkov inequalityを使って,
$$P(S_n \geq na) = P(e^{sS_n}\geq e^{nsa})\leq e^{nsa}E[e^{sS_n}] = e^{-nsa}(M(s))^n$$
($c <s$では右辺が$\infty$になってしまうが不等号自体は成立する)
$P(S_n \geq a)$が$n$とともに指数的に減少することがわかったが,$s$を操作してより狭い境界を与える.

Theorem 19-2 (Chernooff Upper Bound) (証明略)

ある$s>0, a>0$で$E[e^{sX}] < \infty$ならば,
$$P(S_n\geq na) \leq \exp[n\underline{\sup_{s\geq 0} (sa-\log M(s))}_{\phi(a)}]$$

$s=0$では$sa-\log M(s) = 0 - \log 1 = 0$
また
$$\frac{d}{ds} (sa-\log M(s))|_{s=0} = a - \frac{1}{M(s)} \frac{d}{ds} M(s)|_{s=0}=a - 1E[X] = a> 0$$
$sa-\log M(s)$は$s=0$で$0$をとり,微分係数は正だから,十分小さい$s>$で正の値を取る. $\phi(a)>0$であって,$a>0$を固定すると$P(S_n \geq na)$は$n$によって指数的に減少する.

Example

$X \sim N(0, 1)$について,$M(s) = e^{s^2/2}$. したがって$sa - \log M(s)=sa-s^2/2$ これの最小値は$\phi(a) = a^2/2$.これは
$$P(X \geq a) \leq e^{-a^2/2}$$
を与える.

19-2.2 Lower Bound

Assumption 19-1.

(i) $\forall s \ M(s) = E[^sX] < \infty$
(ii) random variable $X$はcontinuous で, PDFは$f_X$
(iii) $X$は有限の上限,下限を持たない.すなわち$0 < F_X(x) < 1, \forall x\in \mathbb{R}$

Theorem 19-3 (Chernoff Lower Bound)

Assumption 1のもとで,任意の$a > 0$に
$$\lim_{n\rightarrow \infty} \frac{1}{n} \log P(S_n \geq na) = -\phi(a)$$

MIT OCW, Fundamentals of Probability 18日目 確率変数の収束の関係性

David Gamarnik, and John Tsitsiklis. 6.436J Fundamentals of Probability. Fall 2008. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 17. Convergence of Random Variables

• Lecture 17. Convergence of Random Variables
  • 3. The Hierarchy of Convergence Concepts
    • • Theorem 17-2
    • 3.1 Convergence Almost Surely Versus in Probability
    • 3.2 Convergence in Probability Versus in Distribution
    • 3.3 Convergence in Distributuion Versus Characteristic Functions
      • Theorem 17-3 Countinuity of inverse transfroms (証明略)
      • Theorem 17-4 Continuity of inverse transforms (証明略)

3. The Hierarchy of Convergence Concepts

Theorem 17-2

$$[X_n \rightarrow^{\text{a.s.}} X] \Rightarrow [X_n \rightarrow^{\text{i.p.}} X] \Rightarrow [X_n \rightarrow^\text{d}X] \Rightarrow [\phi_{X_n}(t) \rightarrow \phi_X(t), \forall t]$$
最初の２つの矢印の両辺では,すべてが同じprobability space上のrandom variableと仮定している.

proof.

(a) $[X_n \rightarrow^{\text{a.s.}} X] \Rightarrow [X_n \rightarrow^\text{i.p.} X]$
$\epsilon > 0$を固定して,$Y_n = \epsilon I_{\{|X_n-X|\geq \epsilon\}}$とする.$X_n \rightarrow^{\text{i.p.}} X$ならば$Y_n \rightarrow^\text{a.s.} 0$であって,$Y_n$が定数$\epsilon$で抑えられることを考えればDCTより
$\lim_n E[Y_n] =\lim_n\int_{\Omega} \epsilon I_{\{|X_n-X|\geq \epsilon\}} = \int_\Omega \lim_n \epsilon I_{|X_n-X|\geq \epsilon\}} 0$ (測度1で$\lim Y_n(\omega) =0$)
一方で$E[Y_n] = \epsilon P(|X_n-X| \geq \epsilon)$から,$P(|X_n-X|\geq \epsilon) \rightarrow 0$が任意の$\epsilon$に言えて,したがって$X_n \rightarrow^{\text{i.p.}} X$

(b) $[X_n \rightarrow^{\text{i.p.}} X] \Rightarrow [X_n \rightarrow^\text{d} X]$ (略)
(c) $[X_n \rightarrow^d X] \Rightarrow [\phi_{X_n}(t) \rightarrow \phi_X(t), \forall t]$
$X_n \rightarrow^d X$のもとで,Theorem 17-1から,あるprobability space上の$Y, \{Y_n\}$が有って,$Y_n \rightarrow^{\text{a.s.}} Y$である. 任意の$t \in \mathbb{R}$に
$$\lim \phi_{X_n} (t) = \lim \phi_{Y_n} (t) = \lim E[e^{itY_n}] =_{(1)} E[\lim e^{it Y_n}]=E[e^{itY}] = \phi_Y(t) = \phi_X(t)$$
(1): DCTと$Y_n \rightarrow^\text{a.s.}Y$ (Lec. 16, 4(f))

それぞれの矢印の逆命題を議論する.

3.1 Convergence Almost Surely Versus in Probability

$[X_n \rightarrow^\text{d} X] \nRightarrow [X_n \rightarrow^\text{i.p.}X]$
$X_n(\Omega)=\{0, 1\}, P(X_n = 1) = 1/n$,また$\{X_n\}$はindependentとする.このとき$X_n\rightarrow^\text{i.p.} 0$である.一方Borel-cantelliの補題から,$P(\{X_n = 1, \text{i.o.}\})=1$ ($\ \ \sum 1/n = \infty$) ゆえにほとんどすべての$\omega$で$X_n(\omega)$は$0$に収束しない.
しかし,より弱い命題は成立する.すなわち,$X_n \rightarrow^\text{i.p.} X$のときには,部分列$\{X_{n_k}\}$があって,$\lim_k X_{n_k} =X \ \ \text{a.s.}$である. (証明略)
例えば上の例で$n_k = k^2$とすると$X_{n_k} \rightarrow^\text{i.p.} 0$であって,Borel-Cantelliの補題から$P(\{X_n=1, \text{i.o.}\})=0$ $(\sum 1/n^2 < \infty)$だから,たしかに$X_n \rightarrow^\text{a.s.} X$.

3.2 Convergence in Probability Versus in Distribution

$[X_n \rightarrow^\text{d} X] \nRightarrow [X_n \rightarrow^\text{i.p.} X]$
$X, X_n$定数でないi.i.d.とする.このとき明らかに$X_n \rightarrow^\text{d} X$であって,一方$\epsilon$を固定して$P(|X_n-X|\geq \epsilon)$は$n$に関係なく確定した非負実数値を取りうる.すなわち$X_n$は$X$にconverge in probability しない.
ただし$[X_n \rightarrow^\text{d} c] \Rightarrow [X_n \rightarrow^\text{i.p.} c]$である.(証明略)

3.3 Convergence in Distributuion Versus Characteristic Functions

最後に,Theorem 17-2の最後の矢印の逆は必ず成立する.つまり同値関係である.以下の定理は,characteristic functionが似ているrandom variableはdistributionも似ていると主張する.

Theorem 17-3 Countinuity of inverse transfroms (証明略)

$X, X_n$はrandom varirableとする.
$$[\phi_{X_n} (t) \rightarrow \phi_X(t), \forall t] \Rightarrow [X_n \rightarrow^d X]$$

さらに,
(i) characteristic functionたち$\phi_{X_n}$が$\phi_X$に各点収束し
(ii) さらにその極限があるrandom variableのcharacteristic functionである
という命題は非常に便利である.(i)のもとで(ii)が成り立つ条件をTheorem 17-4は主張する.

Theorem 17-4 Continuity of inverse transforms (証明略)

$X_n$はrandom variableで,$\phi_{X_n}$をそのcharacteristic functionとする.$\phi(t) = \lim \phi_{X_n}(t) \forall t$つまり各点収束極限を$\phi_X$とすると,以下のどちらかが成り立つ.
(i) $\phi$は$0$で非連続であり,$X_n$はconverge in distribution しない
(ii) $\phi$は$0$で連続であり,random variable $X$があって,そのcharacteristic functionは$\phi$, さらに$X_n \rightarrow^d X$である.

MIT OCW, Fundamentals of Probability 17日目 確率変数の様々な収束

David Gamarnik, and John Tsitsiklis. 6.436J Fundamentals of Probability. Fall 2008. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 17. Convergence of Random Variables

• Lecture 17. Convergence of Random Variables
  • 1. Definitions
    • 1.1 Almost Sure Convergence (概収束)
      • Definition 17-1
    • 1.2 Convergence in Distribution (分布収束)
      • Definition 17-2
    • 1.3 Convergence in Probability (確率収束)
      • Definition 17-3
  • 2. Convergence in Distribution
    • • Theorem 17-1 (証明略)

1. Definitions

1.1 Almost Sure Convergence (概収束)

Definition 17-1

$X_n$ が$X$にalmost surely converge (概収束)する
$\Leftrightarrow P(A)=1 \text{なる } A \subset \Omega$があって,
$$\lim_n X_n(\omega) = X(\omega) \ \ \forall \omega \in A \text{ つまり各点収束}$$
またこのとき$X_n \rightarrow^{\text{a.s.}}X$と書く.

このとき$X_n, X$は必ず同じprobability spaceのrandom variableでなければならない. さらに,$X_n$たちは一般にhighly dependentである.a.s. convergenceが現れる状況は以下の２つである.
(a)

確率的試行を何度も繰り返すとする.$n$回目の試行に,$Z_n \geq 0$というrandom variableを関連付ける(例えば$n$日目の収入). このとき$X_n = \sum_{i=1}^n Z_n$とすると$n$日目までの収入の合計であって,$X = \sum_{k=1}^\infty X_k$は生涯の収入と考えることが出来る. $X$は$\overline{\mathbb{R}}$でうまく定義されている.

(b)

あるrandom variable$Y$と,可測関数$g_n, g$によって作られる様々なrandom variable$X_n = g_n(Y), X=g(Y)$があって,$\lim_n g_n(y) = g(y)$が任意の$y \in \mathbb{R}$に成立するとき$X_n \rightarrow^{\text{a.s.}} X$である.例えば$g_n(y)=y+y^2/n \rightarrow g(y) =y$.よって
$$Y+Y^2/n \rightarrow^{\text{a.s.}} Y$$

$X_n \rightarrow^{\text{a.s.}} X$であるとき,dominated convergence theorem(優収束定理)から,
$$\phi_{X_n}(t) \rightarrow \phi_X(t)$$
である.一方
$$E[X_n] \rightarrow E[X]$$
は一般には成り立たない.例えば$U$を$[0,1]$上の一様分布として,
$$X_n = \begin{cases} n \ \ \ &\text{if } U \leq 1/n \\ 0 &\text{if } U > 1/n\end{cases}$$
とすると
$$\lim E[X_n] = \lim nP(U \leq 1/n) = 1$$
一方,$X_n \rightarrow^{\text{a.s}} 0$で,$E[X]=0$

1.2 Convergence in Distribution (分布収束)

Definition 17-2

$X, X_n$をrandom variableとし,CDFをそれぞれ$F, F_n$とする.$X_n$が$X$にconverge in distributionする
$\Leftrightarrow$
$$\forall x \in \mathbb{R}, \text{ where }F \text{ is continuous,} \ \ \ \lim_{n\rightarrow \infty} F_n(x) = F(x)$$
またこのとき$X_n \rightarrow^d X$と書く.

重要な性質として,
(a)

$P(X=x) = 0 \Leftrightarrow F$は$x$で連続

(b)

$X_n = 1/n$,また$X=0 \ \ \text{a.s.}$とすると$F_{X_n}(0) = P(X_n \leq 0) = 0$だが,$F_X(0) = 1$である.また,$0$で$F$は非連続だから,連続点のみを考えれば$X_n \rightarrow^d X$.より一般に,$X_n = a_n$また確率1で$X=a$で,$a_n \rightarrow 1$ならば,$X_n \rightarrow^d X$である.
よってconvergence in distributionは実数の収束とconsistent.

(c)

この定義は,random variableたちのmarginal distributionだけを考えていて,異なったprobability spaceにおけるrandom variableについても,cenvergence in distributionは定義されている.

(d)

$Y$がcontinuous random variableで,PDFが$0$において対称とする.$X_n = (-1)^n Y$とすると,$X_n$は全て同じdistributionを持っていて,$X_n \rightarrow^d Y$.しかしほとんどすべての$\omega$で,$X_n(\omega)$は$X(\omega)$に収束しない.

(e)

random variableのdistributionがparametric(例えば,$X_n=e^{\lambda_n}$であるとき)かつそのparameterが収束して,その収束先によって$X$を定義するとき$(\lambda \rightarrow \lambda, X=e^{\lambda})$,$X_n \rightarrow^d X$である.

(f)

discrete random variableの列がcontinuous random variableにconverge in distributionすることがある.例えば$Y_n$が$\{1, ..., n\}$でuniformで,$X_n = Y_n/n$とすると,$X_n$は$[0, 1]$上のuniform random variableにconverge in distributionする.

(g)

continuous random variableの列がdiscrete random variableにconverge in distributionすることがある.例えば$X_n$が$[0, 1/n]$でuniformなら$X_n \rightarrow^d 0$.

(h)

$X$と$X_n$が連続でも,$X_n \rightarrow^d X$だからといってPDFたちが連続であるとは限らない.

(i)

$X, X_n$が整数値を取って,$X_n \rightarrow^d X$ならば,PMFもまた$p_{X_n}(k)\rightarrow p_X(k)$と各点収束する.

1.3 Convergence in Probability (確率収束)

Definition 17-3

(a) 必ずしも同じprobability spaceのrandom variable列でない$\{X_n\}$が$c \in \mathbb{R}$にconverge in probabilityする
$\Leftrightarrow$
$$\forall \epsilon > 0 \ \ \ \lim_{n\rightarrow \infty} P(|X_n-c|\geq \epsilon) = 0$$
このとき$X_n \rightarrow^{\text{i.p.}} c$と書く.
(b) $X, \{X_n\}$は同じprobability spaceのrandom variableたちとする. $X_n - X \rightarrow^{\text{i.p.}} 0$であるとき,$X_n$は$X$にconverge in probabilityするといい,$X_n \rightarrow^{\text{i.p.}} X$と書く.

また重要な性質に
(b)

$X_n \rightarrow^{\text{i.p.}} c$というのは,直感的には,$n$が増加するに従ってほとんどすべてのprobability massが$c$の周りの小さな区間に集まってくるということである. 一方$n$を固定するとその小さな区間からはみ出るprobability massがあってそれはslowly decaying tailをもつ(?). このようなtailはexpected valueに大きな影響が有る. よってconvergence in probability は極限のexpected valueを知るのには役立たない.

(c)

$X_n \rightarrow^{\text{i.p.}} X, Y_n \rightarrow^{\text{i.p.}} Y$で,全てが同じprobability space上のrandom variableなら$(X_n + Y_n) \rightarrow^{\text{i.p.}} (X+Y)$である.

2. Convergence in Distribution

convergence in distributionとalmost sure convergenceの関係を詳しく見ることで,convergence in distributionの意味を把握する.

Theorem 17-1 (証明略)

$X_n \rightarrow^d X$なら,あるprobability spaceと,以下を満たすその上のrandom variable$Y, Y_n$が存在する.
(a) 任意の$n$に$X_n$と$Y_n$が同じCDFをもち,$X$と$Y$も同じCDFを持つ.
(b) $Y_n \rightarrow^{\text{a.s.}} Y$

convergence in distributionでは,random variable $X_n$たちが独立であるか否かは問題ではなく,同じprobability space上で定義されている必要もない. 一方almost sure convergenceでは,random variableたちの強いdependenceが暗示されている. Theorem 17-1はmarginal distributionの保存を言っているが,$X_n$たちの間の特別な形のdependenceを導入していて,結果almost sure convergenceが現れる.
このdependenceは$Y_n, Y$をcommon random number generatorを使って希望する分布上に定義する.例えば$U$を$[0, 1]$上のuniformly distrubutionとする.
すべてのCDFたちが連続で狭義単調増加するとき$Y_n = F^{-1}_{X_n}(U), F^{-1}_X(U)$とすると,(a)を満たしている.またこのとき$Y_n \rightarrow^{\text{a.s.}} Y$である.これはsection 1.1(b)からわかる.