Markov Chains and Monte Carlo Methods 02日目

Ioana A. Cosma and Ludger Evers, Markov Chains and Monte Carlo Methods
http://users.aims.ac.za/~ioana/notes.pdf
CC-by-nc-sa 2.5

• • • 1.3 General state space Markov chains
      • Definition 1.23 (Markov chain)
      • Example 1.15 (Gaussian random walk on R\mathbb{R})
      • Definition 1.24 (Irreducibility)
      • Example 1.16 (Gaussian random walk (continued))
      • Definition 1.25 (Recurrence)
      • Definition 1.26 (Harris Recurrence)
      • Definition 1.27 (Stationary distribution)
      • Proposition 1.28 (証明略)
      • Definition 1.29 (Detailed balance)

1.3 General state space Markov chains

$|S| > |\mathbb{N}|$の場合の議論を始める. より一般的な場合にも定義できるのだが,ここでは$S=\mathbb{R}^d$とする.

Definition 1.23 (Markov chain)

$\{X_t\}$はdiscrete time stochastic processで, state spaec $S$は$S=\mathbb{R}^d$とする. $X$ がMarkov property を満たす
$\Leftrightarrow$
$$\forall A \in \mathcal{F}.\ P(X_{t+1}\in A| X_0=x_0,...,X_t=x_t)=P(X_{t+1}\in A|X_t=x_t)$$

ただし$\mathcal{F}$は$S$の可測集合族とする.
以後,Markov chainはhomogeneousとする.すなわち $(X_{t+1}\in A|X_t=x_t)$は$t$によらない. このときtransition kernel $K: S \times S \rightarrow \mathbb{R}_0^+$によって
$$P(X_{t+1}\in A| X_t=x_t) = \int_A K(x_t, x_{t+1})dx_{t+1}\ \ \ \ \ (1.3)$$
として得られる. $K(x, y)$というのは$X_t=x_t$が与えられたときの$X_{t+1}$のconditional probability densityである. def. 1.8における$K(i, j)=k_{ij}$というのはdiscrete spaceにおけるconting measureであって,(1.3)の式に合致する.
さらに
$$\begin{aligned}&P(X_{t+m}\in A|X_t=x_t) \\&= \int_A \int_S \cdots \int_S K(x_t, x_{t+1})K(x_{t+1},x_{t+2})\cdots K(x_{t+m-1},x_{t+m})dx_{t+1}\cdots dx_{t+m-1}dx_{t+m}\end{aligned}$$
だから,$m$-step transiton kernelは
$$K^{(m)}(x_0, x_m) = \int_S\cdots \int_SK(x_t,x_{t+1})\cdots K(x_{m-1},x_m)dx_{m-1}\cdots dx_1$$
であり,
$$P(X_{t+m}\in A| X_t=x_t) = \int_A k^{(m)} (x_t, x_{t+m})dx_{t+m}$$
と簡潔に書ける.

Example 1.15 (Gaussian random walk on $\mathbb{R}$)

$\mathbb{R}$上のrandom walkを
$$X_{t+1} = X_t + E_t, \ \ E_t \sim N(0, 1)$$
とすると,
$$X_{t+1}|X_{t} = x_t \sim N(x_t, 1)$$
と同値. $Et_t$は$X_0, E_1,...,E_{t-1}$と独立とし, $X_0 \sim N(0,1)$とすれば,
$$\begin{aligned} P(X_{t+1}\in A| X_t=x_t,...,X_0=x_0) &= P(E_t\in A-x_t|X_t=x_t,...,X_0=x_0) \\ &=P(E_t\in A-x_t)=P(X_{t+1}\in A|X_t=x_t) \end{aligned}$$
よって$X$はMarkov chainであり,しかも
$$P(X_{t+1}\in A| X_t=x_t) = P(E_t \in A - x_t) = \int_A \phi(x_{t+1}-x_t)dx_{t+1}$$
である.ただし$\phi(z)=\frac{1}{\sqrt{2\pi}}\exp(-\frac{1}{2}z^2)$である.したがって$K(x, x_{t+1}) = \phi(x_{t+1}-x_t)$.
$m$-step transition kernelは(1.3)によって計算できるが,非常に複雑になる. それよりも
$$X_{t+m} = X_t + E_t + ... + E_{t+m-1}$$
を利用すれば,$X_{t+m} |X_t = x_t \sim N(x_t, m)$が成立して,
$$P(X_{t+m}\in A| X_t=x_t) = P(X_{t+m}-X_t\in A-x_t) = \int_A \frac{1}{\sqrt{m}}\phi \left(\frac{x_{t+m}-x_t}{\sqrt{m}}\right)dx_{t+m}$$
したがって
$$K^{(m)}(x_t, x_{t+m}) = \frac{1}{\sqrt{m}}\phi \left(\frac{x_{t+m}-x_t}{\sqrt{m}} \right)$$
が$m$-step kernelとして得られる.

Definition 1.24 (Irreducibility)

$S$上の分布$\mu$が与えられて, Markov chain $X$が$\mu$-irreducibleである
$\Leftrightarrow$
$$P(X_{t+m}\in A| X_t=x) = \int_A K^{(m)}(x, y)dy > 0$$
が任意の$\mu (A) > 0$なる$A \in \mathcal{F}$と任意の$x \in S$に成立するような$m \in \mathbb{N}_0$が存在するとき$\mu$-irreducibleといい,特に任意の$A$に$m=1$で成立するときstrongly $\mu$-irreducibleという.

Example 1.16 (Gaussian random walk (continued))

ex. 1.15で$X_{t+1}|X_t = x_t \sim N(x_t, 1)$を見た. $P(X_{t+1}\in A|X_t=x_t)>0$が任意のnullでない$A$に成立するから,これは任意のcontinuous distributionにstrongly irreducibleである.

periodicity, recurrence, そしてtransienceのような概念を$S$が連続的なMakov chainに導入するため, atomsやsmall setsのような概念を導入する必要があって,これらはこのノートの範囲を超えるので,recurrenceのみを一般化する.
section 1.2.3で定義した$|S|\leq |\mathbb{N}|$の場合のrecurrenceとは,全てのstateがそれを初期のstateとしたとき,平均して無限回訪れられることであった. $S$が連続である場合には,あるstate一点ではなく,stateの集合たちを考えることになる. $V_A=\sum_{t=0}^\infty 1_{\{X_t \in A\}}|X_0=x$として,$A$が訪れられる回数をあらわす. expected valueを考えると
$$E[V_A|X_0=x] = E[\sum_{t=0}^\infty 1_{\{X_t \in A\}}|X_0=x] = \sum_{t=0}^\infty E(1_{\{X_t \in A\}}|X_0=x) =\sum_{t\geq 0} \int_A K^{(t)}(x, y)dy$$
である. recurrenceをMarkov chain全体に定義する前に,集合のrecurrenceを定義する.

Definition 1.25 (Recurrence)

(a) $A \subset S$がMarkov chain $X$においてrecurrentである
$\Leftrightarrow$ 任意の$x \in A$に
$$E(V_A|X_0=x) = \infty$$
(b) Markov chain $X$がrecurrent
$\Leftrightarrow$
(i) $X$はある分布$\mu$に対して$\mu$-irreducibleであって,かつ
(ii) 任意の$A \in \mathcal{F}, \mu(A) > 0$はrecurrent

定義より,recurrent setとは平均して無限回訪れられる集合であって,より強い命題に,その集合が無限回訪れられる確率が1であるというのがある. この強い性質によって定義できるrecurrenceをHarris Recurrenceという.

Definition 1.26 (Harris Recurrence)

(a) $A \subset S$が$X$にHarris-recurrentである
$\Leftrightarrow \forall x \in A P(V_A=\infty|X_0=x)=1$
(b) Markov chain $X$がHarris-recurrent
$\Leftrightarrow$
(i) $X$はある$\mu$に$\mu$-irreducible
(ii) 任意の$A \in \mathcal{F}, \mu(A) > 0$はHarris-recurrent

Harris recurrenceはrecurrenceを導くことは明らかで,discreteの場合2つは一致する.
どちらの概念も成立を証明することは非常に困難だが,あるMarkov chainがirreducibleで唯一のstationary distributionをもつならばrecurrentであるという命題を主張する. その前に,stationaryを定義する.

Definition 1.27 (Stationary distribution)

分布PDF$f_{\mu}$をもつ分布$\mu$がtransition kernel $K$をもつ$X$のstationary distibutionである
$\Leftrightarrow \forall y \in S.\ \ f_\mu(y) = \int_S f_\mu(x)K(x, y)dx$

Proposition 1.28 (証明略)

$X$が$\mu$-irreducible Markov chainで,$\mu$を唯一のstationary distibutionにもつなら,$X$はrecurrentである.

また,def. 1.27によってstationarityを確かめるのは困難なので,discreteの場合と同様により簡単な十分条件を定義する.

Definition 1.29 (Detailed balance)

transition kernel $K$がdistribution $\mu$にdetailed balanceである
$\Leftrightarrow \forall x,y \in S. \ \ f_\mu(x)K(x, y)=f_\mu(y)K(y,x)$

theorem 1.22と同様に,$\mu$によってdetailed balanceなMarkov chain $X$はtime-reversibleで$\mu$は$X$のstational distibutionである.

Markov Chains and Monte Carlo Methods 01日目

Ioana A. Cosma and Ludger Evers, Markov Chains and Monte Carlo Methods
http://users.aims.ac.za/~ioana/notes.pdf
CC-by-nc-sa 2.5
http://creativecommons.org/licenses/by-nc-sa/2.5/za/legalcode

• Chapter 1. Markov Chains
  • 1.1 Stochastic processes
    • • Definition 1.1 (Stochastic process)
      • Definition 1.2 (Sample path)
      • Theorem 1.3 (Kolmogorov)
  • 1.2 Discrete Markov chains
    • 1.2.1 Introduction
      • Definition 1.4 (Discrete Markov chain)
      • Proposition 1.5
      • Example 1.1 (Phone line)
      • Example 1.2 (Random walk on $\mathbb{Z}$)
      • Proposition 1.6
      • Definition 1.7 (Homogeneous Markov Chain)
      • Definition (initial distribution)
      • Definition 1.8 (Transition kernel)
      • Example 1.3 (Phone line(continued))
      • Example 1.4 (Random walk on $\mathbb{Z}$ (continued))
      • Definition 1.9 (m-step transition kernel)
      • Proposition 1.10
      • Example 1.5 (phone line(continued))
    • 1.2.2 Classificaton of states
      • Definition 1.11 (classification of states)
      • Example 1.6
      • Definition 1.12 (Irreducibility)
      • Definition 1.13 (Period)
      • Example 1.7 (Ex. 1.6 continued)
      • Proposition 1.14
    • 1.2.3 Recurrence and transience
      • Definition 1.15 (Recurrence and transience)
      • Proposition 1.16
      • Proposition 1.17
      • Example 1.8 (ex.16, 1.7 continued)
    • 1.2.4 Invariant distribution and equilibrium
      • Definition 1.18 (Invariant distribution)
      • Example 1.9 (Phone line (continued))
      • Example 1.10 (Random walk on Z (continued))
      • Theorem 1.19 (convergence to equilibrium)
      • Example 1.11 (Phone line (continued))
      • Example 1.12
    • 1.2.5 Reversibility and detailed balance
      • definition 1.20 (Time-reversed chain)
      • Example 1.13(Photo line(cont.))
      • Definition 1.21 (Detailed balance, 詳細釣り合い条件)
      • Theorem 1.22
      • Example 1.14

Chapter 1. Markov Chains

1.1 Stochastic processes

Markov chain は無記憶性という特別な性質を持つ確率過程の一種である. Markov chainをよく学ぶため,まずはStochastic processの概念を形式的に定義する.

Definition 1.1 (Stochastic process)

$X$がstochastic processである
$\Leftrightarrow X$は $X=\{X_t: t \in T\}$という，$T$を添字集合とした確率変数の集合であって,domainとrange$X_t: \Omega \rightarrow S$は共通である. $t$は”time”(時刻)で,$S$は”state space”(状態空間)と呼ばれる.

$T$には様々な集合が考えられるが,我々が当面扱うのは$T$が離散的な集合である場合(stochastic processes in discrete time)で,例えば$T \subset \mathbb{N}$や$T\subset \mathbb{Z}$の場合である. ほかには$T=[0, \infty)$のような連続時間における過程や$T=\mathbb{R}^2$のような空間的な過程を考えることもある.
また,$S$がどのような集合かも問題で，$S$が離散的な集合であれば($X_t$がr.v.として離散的であれば)，このような過程を離散過程(discrete process)という.

Definition 1.2 (Sample path)

$\omega\in \Omega$について,$\{X_t(\omega); t \in T\}$を$X$の$\omega$におけるsample path という.

$T=\mathbb{N}_0$ならばsample pathは点列で，$T=\mathbb{R}$ならばsample pathは$\mathbb{R} \rightarrow S$なる関数である.
fig.1.1はsample pathの例である.

stochastic processは$X_t$のそれぞれの分布のみではなく,それらの依存関係によっても特徴づけられる. この依存関係の構造はprocessのfinite-dimentional distributionsによって表現できる．すなわち
$$P(X_{t_1}\in A_1, ..., X_{t_k} \in A_k)$$
という具合である. $S\subset \mathbb{R}$であればjoint distibution function(同時分布)は
$$F_{(t_1,...,t_k)}(x_1,...,x_k) = P(X_{t_1}\in (-\infty, x_1], ..., X_{t_k} \in (-\infty, x_k])$$
と記述できる.

$X$が
$$F_{(t_1,...,t_{j-1},t_j,t_{j+1},...,t_k)}(x_1,...,x_{j-1},+\infty,x_{j+1},...,x_k) = F_{t_1,...,t_{j-1},t_{j+1},...,t_k)}(x_1,...,x_{j-1},x_{j+1},...,x_k)$$
を満たすとき,$X$のfinite dimentional distribution functionはconsistentであるという.
stochastic process $X$について,$X$がfinite dimentional distributionsによって完全に記述できるか否かについての部分的な答えが以下の定理である.

Theorem 1.3 (Kolmogorov)

$F_{(t_1,...,t_k)}$はconsistent なfinite-dimensional distribution functionの族とする. このとき,以下を満たすprobability spaceとstochastic process $X$が存在する.
$$F_{(t_1,..,t_k)}(x_1,...,x_k) = P(X_{t_1}\in(-\infty, x_1], ..., X_{t_k} \in (-\infty, x_k])$$

この定理から,あるprocessのfinite-dimensional distributionsを与えれば，そのprocessを特徴づけられる(本当か?). ただし,あるfinite-dimensional distributionsによって特徴づけられる$X$は一意ではない. しかし,そのdistributionsはたかだか可算個のr.v.によるeventの全てに確率を一意に割り当てることができて，この講義の範囲ではそれで十分である.

1.2 Discrete Markov chains

1.2.1 Introduction

この節ではMarkov chainのうち，とくに$|S|= |\mathbb{N}|$であるときを考える. これをdiscrete Markov processと呼ぶことはすでに述べた($|S|<\infty$の時も含むが,深くは考えない). discrete Markvo processでは$S$を$\mathbb{N}$として一般性を失わない.

Definition 1.4 (Discrete Markov chain)

$X$はdiscrete stochastic processで，しかも時間についてもdiscreteとする.
$X$がMarkov chain (with discrete state space)
$\Leftrightarrow P(X_{t+1}=x_{t+1}|X_t=x_t,...,X_0=x_0) = P(X_{t+1}=x_{t+1}|X_t=x_t)$
またこの性質をMarkov propertyという.

この定義は，ある時刻における状態がその直前の時刻における状態のみによって決まる(確率的)ということの定式化である.

Proposition 1.5

Markov propertyが成立する$\Leftrightarrow$
任意の$k \in \mathbb{N}$と$t_1<...<t_k\leq t$について
$$P(X_{t+1}=x_{t+1}|X_{t_k}=x_{t_k},...,X_{t_1}=x_{t_1})=P(X_{t+1}=x_{t+1}|X_{t_k}=x_{t_k})$$

Example 1.1 (Phone line)

電話線が使われている状態(1とする)と使われていない状態(0とする)があって，毎分この電話線を監監視する過程$\{X_t|t \in \mathbb{N}_0\}$のstochastic processを考える. $\{X_t\}$がMarkov chainと仮定する. すなわち,これまでどれほど長く電話をしていても1分間後にその電話が切れている確率は変わらず，同様にどれほど長く電話がかかってこなかったとしても1分後に電話がかかってきている確率は変わらない仮定する. Markov assumptionは$\{X_t\}$が同じ分布であることを要求しないので,$P(X_{t+1}=1|X_t=0)=0.8$($t$は昼頃), $P(X_{t+1}=1|X_t=0)=0.1$($t$は深夜)というふうに，時刻によって利用のパターンが異なるモデルにも適用できる.

Example 1.2 (Random walk on $\mathbb{Z}$)

$X_0=0$から始まるrandom walkという確率過程を考える. 全ての時刻で，次の時刻に今あるstateにとどまるか,+1進むか,-1進むかを確率的に選ぶ過程である. 現在あるstateにかかわらず,そのstateにとどまる確率を$1-\alpha-\beta$, -1進む確率を$\alpha$, $+1$進む確率を$\beta$とする.$\alpha, \beta \geq 0, \alpha + \beta \leq 1$である.
$X_{t+1}$を,$P(E_t=-1)=\alpha, P(E_t=0)=1-\alpha-\beta, P(E_t=1)=\beta$任意の$t$に成立するr.v. $E_t$によって
$$X_{t+1} = X_t + E_t$$
と記述する.このとき
$$\begin{aligned} &P(X_{t+1}=x_t-1|X_t=x_t)=\alpha, \\ &P(X_{t+1}=x_t|X_t=x_t)=1-\alpha-\beta, \\ &P(X_{t+1}=x_{t}-1|X_t=x_t)=\beta\end{aligned}$$
であることは明らかである.さらに
$$\begin{aligned} &P(X_{t+1}=x_{t+1}|X_t=x_t,...,X_0=x_0) \\ =&P(E_t=x_{t+1}-x_t|E_{t-1}=x_t-x_{t-1},..,E_0=x_1-x_0,X_0=x_o)\\ =&P(E_t=x_{t+1}-x_t) \ \ \ (\because \{E_t\}\text{の独立性})\\ =&P(X_{t+1}=x_{t+1}|X_t=x_t) \end{aligned}$$
が成り立つから,$\{X_t|t\in \mathbb{N}_0$はMarkov chainである.

Markov chainの分布は初期分布$P(X_0=x_0)$によって完全に定まる.さらに*transition probabilitiesを $P(X_{t+1}=x_{t+1}|X_t=x_t)$と定めると,以下の命題が成立する.

Proposition 1.6

discrete Markov chain $\{X_t | t \in \mathbb{N}_0\}$について，
$$P(X_t=x_t,...,X_0=x_0)=P(X_0=x_0)\cdot \prod_{\tau=0}^{t-1} P(X_{\tau+1}=x_{\tau+1}|X_\tau = x_\tau)$$

proof.

$$\begin{aligned} P(X_t=x_t,...,X_0=x_0) =&P(X_0=x_0) \\ &P(X_1=x_1|X_0=x_0)\\ &P(X_2=x_2|X_1=x_1,X_0=x_0) \\ &\cdots \\ &P(X_t=x_t|X_{t-1}=x_{t-1},...,X_0=x_0) \\ &=P(X_0=x_0)\prod_{\tau=0}^{t-1}P(X_{\tau+1}=x_{\tau+1}|X_\tau =x_\tau) \end{aligned}$$

この証明の1つめの等号は全てのr.v.の組に成立するが,2つ目の等号が成立するのはMarkov chain特有である.
Homogeneous Markov chainという更に特別なクラスは$t$によって$X_t$が変化せず，非常に扱いやすい.以下,全てのMarkov chainはhomogeneousとする.

Definition 1.7 (Homogeneous Markov Chain)

Markov chain $\{X_t|t \in \mathbb{N}_0$がhomogeneous
$\Leftrightarrow P(X_{t+1}=j|X_t=i)=p_{ij} \in [0, 1]$という$t$によらない実数$p_{ij}$が,任意の$i,j \in S$に存在する.

Definition (initial distribution)

initial distributionを$\mathbf{\lambda_0}=(P(X_0=i))_{i \in S}$と書く．$\mathbf{K}$と$\mathbf{\lambda_0}$の組によってhomogeneous Markov chainの分布は完全に定まる(後述).

Definition 1.8 (Transition kernel)

$$\mathbf{K}=(k_{ij})_{ij}, \ \ k_{ij}=P(X_{t+1=j}|X_t=i)$$
という行列$\mathbf{K}$をhomogeneous Markov chain $X$のtransition kernelとかtransition matrixという．
$\sum_{j}k_{ij}=\sum_j P(X_{t+1}=j|X_t=i)=P(X_{t+1}\in S|X_t=i)=1$が成立する.

Example 1.3 (Phone line(continued))

$P(X_{t+1}=0|X_t=0)=0.9, \ P(X_{t+1}=1|X_t=0)=0.1$
$P(X_{t+1}=0|X_t=1)=0.3, \ P(X_{t+1}=1|X_t=1)=0.7$
とするとき,transition kernelは
$$\mathbf{K} = \left(\begin{array}{} 0.9 & 0.1 \\ 0.3 & 0.7 \end{array} \right)$$
となる. transition probabilityを有向グラフを使って表現することが有る. Markov graphという. この例のMarkov graphはfig. 1.4のようになる.

Example 1.4 (Random walk on $\mathbb{Z}$ (continued))

前に挙げたrandom walkのhomogeneous Markov chainのtransition kernelは行，列ともに無限大のToeplitz matrix(テープリッツ行列)で，具体的には
$$\left(\begin{array}{} \ddots & \ddots & \ddots & \ddots & \ddots \\ \ddots & \alpha & 1-\alpha-\beta & \beta & 0 \\ \ddots & \ddots & \alpha &1-\alpha-\beta & \beta &\ddots \\ \ddots & \ddots & \ddots & \ddots & \ddots \end{array} \right)$$
という形をしている.

Definition 1.9 (m-step transition kernel)

homogeneous Markov chain $\{X_t\}$について,$\mathbf{K}^{(m)} = (k^{(m)}_{ij})_{ij}, \ k^{(m)}_{ij} = P(X_{t+m}=j|X_t=i)$を$m$-step transition kernelという.

Proposition 1.10

$X$をhomogeneous Markov chainとすると,
i. $\mathbf{K}^{(m)} = \mathbf{K}^m$
ii. $P(X_m=j) = (\mathbf{\lambda_0}^T \mathbf{K}^{(m)})_j$
が成立する.

proof.

i. $\mathbf{K}^{(m_1+m_2)} = \mathbf{K}^{(m_1)} \cdot \mathbf{K}^{(m_2)}$を示す.
$$\begin{aligned} P(X_{t+m_1+m_2}=k|X_t=i) &=\sum_j P(X_{t+m_1+m_2}=k,X_{t+m_1}=j|X_t=i)\\&=\sum_j P(X_{t+m_1+m_2}=k|X_{t+m_1}=j,X_t=i)P(X_{t+m_1}=j|X_t=i) \\ &= \sum_j P(X_{t+m_2}=k|X_t=j)P(X_{t+m_1}=j|X_t=i) \\&=\sum_j \mathbf{K}_{ij}^{(m_1)} \mathbf{K}_{jk}^{(m_2)} = (\mathbf{K}^{(m_1)} \mathbf{K}^{(m_2)})_{i,k} \end{aligned}$$
ゆえに$\mathbf{K}^{(2)}=\mathbf{K}^2$がたしかに成立し,帰納法により$\mathbf{K}^{(m)}=\mathbf{K}^m$である.
ii. $$P(X_m=j) = \sum_i P(X_m=j,X_0=i) =\sum_i P(X_m=j|X_0=i)P(X_0=i)=(\lambda_0^T\mathbf{K}^m)_j$$

Example 1.5 (phone line(continued))

$$\mathbf{K}=\left(\begin{array}{} 0.9 & 0.1 \\ 0.3 & 0.7 \end{array} \right)$$
のm-step transition kernelは
$$\mathbf{K}^{(m)} = \mathbf{K}^m = \frac{1}{4}\left(\begin{array}{} 3+(\frac{3}{5})^m& 1-(\frac{3}{5})^m \\ 1+(\frac{3}{5})^m & 3-(\frac{3}{5})^m \end{array} \right)$$

1.2.2 Classificaton of states

Definition 1.11 (classification of states)

(a) ある$m \geq 0$があって,$k^{(m)}_{ij} = P(X_{t+m}=j|X_t=i)>0$が成り立つとき$i$は$j$を導くといい,$i \leadsto j$と書く.
(b) $i \leadsto j,\ j \leadsto i$であるとき$i,j$はcommunicateするといい,$i \sim j$と書く.このとき$\cdot \sim \cdot$は同値関係である.

$S$に同値関係を入れられたから,$S$は$\sim$で同値類別できる. ある同値類$C$の全ての元で他の$S$の元に出るpathが無いとき($\Leftrightarrow [\forall i \in C i \leadsto j \Rightarrow j \in C]$), $C$はclosedであるという. ある同値類の元は様々な性質を共有していることをあとで示す.

Example 1.6

$$\mathbf{K} = \left(\begin{array}{}\frac{1}{2} & \frac{1}{4} & 0 & \frac{1}{4} & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{3}{4} & 0 & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & \frac{3}{4} & 0 & 0 & 0 & \frac{1}{4} \\ 0 & 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} \end{array} \right)$$
をtransition kernelにもつMarkov chainのMarkov graphはfig. 1.5のとおりである. $2 \sim 4, 2 \sim 5, 3 \sim 6, 4\sim 5$が見て取れて,同値類別は$S\backslash \sim = \{\{1\},\{2,4,5\},\{3,6\}\}$であり，特に$\{3, 6\}$のみがclosedである.

Definition 1.12 (Irreducibility)

$S$の全ての元が互いにcommunicateするとき$S$はirreducibleであるという.

phone lineの例とrandom walkの例はreducibleであり,example 1.6はirreducibleである. ところで,ex. 1.6において,$2$から再び$2$に至るのは,$2$から$4$,$4$から$5$,$5$から$2$というステップを踏まなければならないので,$P(X_t=2|X_\tau=2) = \begin{cases} = 0 \ \ &(t \notin \tau + 3\mathbb{N}) \\ >0 &\text{otherwise} \end{cases}$
である. このような振る舞いをperiodicityという.

Definition 1.13 (Period)

(a) $i \in S$のperiod $d(i)$を
$$d(i) = gcd\{m\geq 1| K^{(m)}_{ii} > 0\}$$
と定める. periodを持たないstateも存在する.
(b) $d(i) = 1$なら,$i$はaperiodicという.
(c) $d(i) > 1$なら,$i$はperiodicという.

Example 1.7 (Ex. 1.6 continued)

すでに述べたように$d(2)=3$である. 同様に$d(4)=d(5)=3$である.
また$\mathbf{K}_{1,1},\mathbf{K}_{3,3}, \mathbf{K}_{6,6}>0$だから,$d(1)=d(3)=d(6)=1$.すなわち$3,6$はaperiodicである.
ある同値類(以後,communicateによる同値類をcommunicating classか,単にclassという)においてperiodを共有しているのは偶然ではない.

Proposition 1.14

(a) あるclassの全ての元はperiodを共有する.
(b) irreducible chainでは全ての元はperiodを共有する.

1.2.3 Recurrence and transience

ex. 1.6のMarkov chainを辿り続けると,そのうち$3, 6$を往復するだけになる. このような振る舞いを定式化するため, number of visits in state $i$:
$$V_i = \sum_{t=1}^\infty 1_{\{X_t =i\}}$$
を導入する. 初期値が$i$であるときの条件付き期待値は
$$E[V_i|X_0=i] = E\left[\sum_t 1_{\{X_t=i\}} | X_0=i \right] = \sum_{t=0}^\infty E[1_{\{X_t=i\}}|X_0=i] = \sum_t P(X_t=i|X_0=i) = \sum_{t} k^{(t)}_{ii}$$
この値が有限か無限かによってstateを分類する.

Definition 1.15 (Recurrence and transience)

(a) $i$がrucurrent
$\Leftrightarrow\ E(V_i|X_0=i)=\infty$
(b) $i$がtransient
$\Leftrightarrow\ E(V_i|X_0=i)<\infty$

すなわち,$i$がa.s.無限回訪れられるというのがrecurrentで，a.s.有限回訪れられるというのがtransientである.
prop. 1.14から,あるcommunication classの元たちはrecurrentであるか否かを共有する.

Proposition 1.16

あるcommunicating classにおいて，全ての元がrecurrentであるか，全ての元がtransientであるかのどちらかが成立する.

proof.

$i \sim j$ならば,$i$から$j$に至る長さ$m_{ij}$のpathがあり,$j$から$i$に一有る長さ$m_{ji}$のpathがある. すなわち$k^{(m_{ij})}_{ij}, k_{ji}^{(m_{ji})}>0$である.
$E(V_i|X_0=i) = \sum_t k^{(t)}_{ii} < \infty$とすると，
$$\begin{aligned} EV(V_j|X_0=j) &=\sum_{t} k^{(t)}_{jj} = \frac{1}{{k_{ij}^{(m_{ij})} k^{(m_{ji})}_{ji}}}\sum_t \underline{k_{ij}^{(m_{ij})}k_{jj}^{(t)}k_{ji}^{(m_{ji})}}_{(1)} \\ &\leq \frac{1}{{k_{ij}^{(m_{ij})} k^{(m_{ji})}_{ji}}} \sum_t k^{(m_{ij}+t+m_{ji})}_{ii} \\ &\leq \frac{1}{{k_{ij}^{(m_{ij})} k^{(m_{ji})}_{ji}}} \sum_{s\geq0} k_{ii}^{(s)} < \infty\end{aligned}$$
((1): $j$から$i$に行って,さらに$t$後にまた$i$に戻って,そこから$j$に戻るという確率)
よって$j$もまたtransientである.
また$i$がrecurrentであるとき,
$$\begin{aligned}E[V_j|X_0=j] = \sum_t k^{(t)}_{jj} &\geq \sum_{t=0}^{m_{jj}+ m_{ij}} k^{(t)}_{jj} + \sum_{\tau \geq 0}k^{(m_{ji})}_{ji} k^{(\tau)}_{ii} k^{(m_{ij})}_{ij} \\ &\geq \sum_{t=0}^{m_{jj}+ m_{ij}} k^{(t)}_{jj} + k^{(m_{ji})}_{ji} k^{(m_{ij})}_{ij}\sum_{\tau \geq 0} k^{(\tau)}_{ii} \geq \infty \end{aligned}$$
から,$j$もrecurrent.

Proposition 1.17

(a) closedでないclassはtransient
(b) 有限かつclosedなclassはrecurrent

Example 1.8 (ex.16, 1.7 continued)

ex.1.6において,$\{1\}, \{2,4,5\}$はclosedでないからtransient.
一方$\{3,6\}$は有限かつclosedなのでrecurrent.

1.2.4 Invariant distribution and equilibrium

invariant distributionを導入して,Markov chainの長期的な振る舞いを調べる.

Definition 1.18 (Invariant distribution)

$\mathbf{\mu} = (\mu_i)_{i \in S}$は$S$上のprobablility distributionとする. また$X$がMarkov chainでtransition kernel $\mathbf{K}$をもつとする. $\mathbf{\mu}$が$X$のinvariant distribution (stationary distibution)
$\Leftrightarrow \mathbf{\mu}^T \mathbf{K} = \mathbf{\mu}^T$

さらにこのとき,右から$\mathbf{K}$を掛けることで,
$$\forall i\in \mathbb{N}. \mu^T = \mu^T \mathbf{K}^{n}=\mu^T \mathbf{K}^{(n)}$$
が成立する.したがってprop. 1.10より
$$P(X_m=j) = (\mu \mathbf{K}^{(m)}_j) = (\mu)_j$$
が任意の$m$に成立する. つまり,$X$の分布は時刻によって変化しない.

Example 1.9 (Phone line (continued))

$$\mathbf{K} = \left(\begin{array}{} 0.9 & 0.1 \\ 0.3 & 0.7 \end{array} \right)$$
のstationary distributionを見つける.
$\mu^T \mathbf{K}=\mu^T$を変形して,$\mathbf{K}^T\mu = \mu$.よって$\mu$は$\mathbf{K}^T$のeigenvector(固有ベクトル)であって,ただし確率の公理から$\mu$のそれぞれの要素は非負で，総和は1である.これを解くと,$\mu=[\frac{3}{4}, \frac{1}{4}]^T$である.
Markov chainは必ずしもstationary distributionを持たない.$\mathbb{Z}$上のrandom walkがその例である.

Example 1.10 (Random walk on Z (continued))

$$\mathbf{K}= \left(\begin{array}{} \ddots & \ddots & \ddots & \ddots & \ddots \\ \ddots & \alpha & 1-\alpha-\beta & \beta & 0 \\ \ddots & \ddots & \alpha &1-\alpha-\beta & \beta &\ddots \\ \ddots & \ddots & \ddots & \ddots & \ddots \end{array} \right)$$
であることはすでに言った.$\mu = [1, 1,...]^T$は$\mu^T \mathbf{K}=\mu^T$の唯一の解だが,$\mu$は無限次元のベクトルなので正規化できない.

ある種のMarkov chainは長期的にはstationary distributionに至る.

Theorem 1.19 (convergence to equilibrium)

$X$がirreducibleかつaperiodicなMarkov chainで,stationary distribution $\mu$をもつとする.このとき
$$\lim_{t \rightarrow \infty}P(X_t = i) \rightarrow \mu_i$$
が任意の$i \in S$に成立する.

proof. (sketch)

$X$のinitial distribution, transition kernelをそれぞれ$\lambda$, $\mathbf{K}$とする. initial distribution $\mu$(stational)とtransition matrix $\mathbf{K}$をもつ新しいMarkov chain $Y$を定める. また$T$を$X, Y$が初めて$i\in S$に同時に到達する時刻の確率変数を$T$とする.すなわち
$$T = \min \{t\geq 0| X_t=Y_t=i\}$$
さらに$P(T<\infty)=1$であり，また新しいprocess $Z$を
$$Z_t = \begin{cases} X_t \ \ &(t \leq T) \\ Y_t &(t > T)\end{cases}$$
によって定める. $Z$の概略はfig.1.6のようになる. $Z$はinitial distribution $\lambda$をもち,transition kernel $\mathbf{K}$である. したがって$X$と$Z$は常に同じ分布を持つ.すなわち$\forall j. \ P(X_t=j)=P(Z_t=j)$である.
$Y$のinitial distributionはstationaryなので,$\forall t\forall j.\ P(Y_t = j) = \mu_j$である. $t \rightarrow \infty$において$P(\{Y_t = Z_t\})=1$であって,ゆえに
$$P(X_t=j)=P(Z_t=j)\rightarrow P(Y_t=j)=\mu_j$$

Example 1.11 (Phone line (continued))

phone lineの例で,$\mu=(3/4, 1/4)$だから,$P(X_t=0) \rightarrow 3/4, P(X_t=1) \rightarrow 1/4$.

Example 1.12

Theorem 1.19におけるaperiodicityの仮定が必須であることを示す.
$S=\{1, 2\}$, $\mathbf{K} = (\begin{array}{} 0 & 1 \\ 1 & 0\end{array})$とする. これは明らかにirreducibleだがperiod 2である. stationary distibutionは$(1/2, 1/2)$だが,これは決定論的な過程だから,明らかに$X$はこれに収束しない.

1.2.5 Reversibility and detailed balance

$P(X_{t+1}|X_t)$のように,現在(あるいは過去)を条件にした未来の状態の確率を論じてきたが，今度は逆に未来の状態を条件にした過去あるいは現在の状態の確率を議論する.
$$P(X_t=j|X_{t+1}=i) = P(X_{t+1}=i|X_t=j)\cdot \frac{P(X_t=j)}{P(X_{t+1}=i)}$$
のように条件付き確率の前後が交換できるのはBayesの定理の教えるところである.
chainを逆に辿っていくような新しいMarkov chainの定義を動機づける.

definition 1.20 (Time-reversed chain)

$\tau \in \mathbb{N}$について,$\{X_t | t = 0,...,\tau\}$をMarkov chainとする. $\{Y_t:t=0,..,\tau\}$を$Y_t = X_{\tau - t}$とすると,$Y$を$X$のtime-reversed chainという.
$$\begin{aligned} P(Y_t = j|Y_{t-1}=i)&=P(X_{\tau-t}=j|X_{\tau-t+1}=i)=P(X_s=j|X_{s+1}=i)\\ &=P(X_{s+1}=i|X_s=j)\cdot \frac{P(X_s=j)}{P(X_{s+1}=i)} = k_{ji}\frac{P(X_s=j)}{P(X_{s+1}=i)} \end{aligned}$$
である.

$X$がhomogeneousでも$Y$がhomogeneousとは限らない.
しかし,$X$のinitial distributionがstational $\mu$であれば,$P(X_{s+1}=i)=\mu_i, P(X_s=j)=\mu_j$が任意の$s$に実数として決まって,
$$P(Y_t=j|X_{t-1}=i)=k_{ji}\frac{\mu_j}{\mu_i} \ \ \ \ \ \ (1.2)$$
が成立するから,$\{Y_t\}$はhomogeneousである.

Example 1.13(Photo line(cont.))

すでに挙げた例で,
$\mathbf{K} = (\begin{array}{} 0.9 & 0.1 \\ 0.3 & 0.7 \end{array}), \mu = (3/4, 1/4)^T$だから, 式(1.2)により
$$\begin{aligned} &P(Y_t=0|Y_{t-1}=0) = k_{00}\frac{\mu_0}{\mu_0}=k_{00}=P(X_t=0|X_{t-1}=]1) \\ &P(Y_t=0|Y_{t-1}=1)=k_{01}\frac{\mu_0}{\mu_1} =0.3 =k_{10}=P(X_t=0|X_{t-1}=1) \\ &P(Y_t=1|Y_{t-1}=0)=k_{10}\frac{\mu_1}{\mu_0}=0.1 = k_{01}=P(X_t=1|X_{t-1}=0) \\ &P(Y_t=1|Y_{t-1}=1) =k_{11}\frac{\mu_1}{\mu_1}=k_{11}=P(X_t=1|X_{t-1}=1) \end{aligned}$$
以上よりこの例では$X$と$Y$は同じtransition probabilityをもつ. このようなchainはtime-reversibleであるという.

time-reversible であるか否かを判別する基準を導入する.

Definition 1.21 (Detailed balance, 詳細釣り合い条件)

transition kernel $\mathbf{K}$がdistribution $\mu$によってdetailed balanceを満たす
$\Leftrightarrow \forall i,j\in S. \ \ \mu_ik_{ij}=\mu_jk_{ji}$

detailed balanceは後で学ぶMarkov Chain Monte Carlo(MCMC)の議論でも極めて重要な役割を果たす. detailed balanceを満たす$\mu$はstationary distributionであり，これはdef. 1.19の定義よりも扱いやすいことが多い.

Theorem 1.22

$X$はMarkov chainで,そのtransition matrix を$\mathbf{K}$はdetailed balanceを$\mu$によって満たすとする.このとき
(i) $\mu$は$X$のstationary distributionである.
(ii) $\mu$がinitial distributionであれば,$X$はtime-reverisbleである．

proof.

(i)仮定より
$$(\mu^T K)_i = \sum_j \mu_j k_{ji} =_{(2)}\sum_j \mu_i k_{ij}= \mu_i \sum_j k_{ij} =_{(1)}\mu_i$$
((1): distributionの定義 (2): detailed balanceの定義)
よって確かに$\mu^T\mathbf{K}=\mu^T$だから,$\mu$はstationary distributionである.
(ii) $Y$を$X$のtime-reversalとする.
$$P(Y_t=j|Y_{t-1}=i)=_{(1)}k_{ji}\frac{\mu_j}{\mu_i}=_{(2)}\frac{k_{ij}\mu_i}{\mu_i}=k_{ij}=P(X_t=j|X_{t-1}=i)$$
(1): 式1.2 (2): detailed balanceの定義
よって確かに$X,Y$はtransition matrixを共有する

一方,stationary distributionを持つからと行ってtime-reversibleであるとは限らない.

Example 1.14

$S=\{1, 2, 3\}$.
$$\mathbf{K} = \left( \begin{array}{} 0 & 0.8 & 0.2 \\ 0.2 & 0 & 0.8 \\ 0.8 & 0.2 & 0\end{array} \right)$$
というMarkov chainを考えると,stationary distributionは$\mu = (1/3, 1/3, 1/3)^T$. Markov graphはfig.1.7の通り.

(1.2)からtime-reversed chain $Y$のtransition matrixが
$$\left( \begin{array}{} 0 & 0.2 & 0.8 \\ 0.8 & 0 & 0.2 \\ 0.2 & 0.8 & 0\end{array} \right)$$
と得られるが,これは$\mathbf{K}$と異なる行列である.

MIT OCW, Machine Learning 10日目 モデル選択の理論1

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 9

Kernel Optimization

kernelのあるパラメータを変えて,問題により適したkernelをつくることができる. 例えばradial basis kernelの$\beta$のようなパラメータを変化させたり,$\mathbf{x}$の次元に重み付けをしてから$\phi$に渡すような方法が考えられる. パラメータのよさの基準には,cross-validationやgeneralization errorに関連した基準(marginなど)が用いられる. marginは$\phi$を定数倍すると同時に倍化するため,normalization $\|\phi(\mathbf{x})\|=1$という制限を加える.normalizationは例えば
$$\tilde{K}(\mathbf{x}, \mathbf{x'})=\frac{K(\mathbf{x, x'})}{\sqrt{K(\mathbf{x,x'})K(\mathbf{x,x'})}}$$
で実現できる.
他のkernel optimizationの方法にkernel alignentがある. すなわち,パラメータやGram matrixを理想的なkernelに近づけるように調整するのである. 例えばclassificationでは
$$K^*_{ij}=y_iy_j$$
を標的となるkernelのGram matrixとする.というのは,$\alpha_j = 1/n$とすれば,
$$\sum_{j=1}^n \alpha_j y_j K^*_{ij}=y_i$$
と,全てのtraining exampleが等しいmarginで正しく分類できるためである.
kernelをこの標的に近づける方法を考える.
$$K(\mathbf{x}, \mathbf{x'};\theta) = \sum_{i=1}^m \theta_i K_i(\mathbf{x,x'}), \theta_i \geq 0, \sum_{i=1}^m \theta_i=1$$

のように,kernelたちのconvex combinationによってkernel $K$を構成するとき,$\theta_i$が我々が選べるパラメータである. $K$のGram matrix $K_{ij}(\phi)$を,標的のGram matrix $K^*_{ij}$に近づけるため,Gram matrixをベクトルと考えて,その内積を
$$<K^*, K_\theta> = \sum_{i,j=1}^n K^*_{ij}K_{ij}(\theta)$$
と定める. こうして$\theta$は$K^*$と$K(\theta)$のcosine類似度
$$\frac{<K^*, K_\theta>}{\sqrt{<K^*,K^*><K_\theta,K_\theta}}$$
を最大化させる$\theta$を求めれば良い.

Model (kernel) selection

少ないtraining exampleに複雑すぎるmodel(kernel)を使うと,over-fittingという問題が起きる. 問題によって使うkernelの種類を制限することがある. kernelを選ぶことで
linearな$K_1$があるとき,discriminant functionは
$$f_1(\mathbf{x}; \theta, \theta_0) = \theta^T \phi^{(1)}(\mathbf{x})+\theta_0$$
という形をしている.$\phi^{(1)}(\mathbf{x})$は$K_1(\mathbf{x, x'})=\phi^{(1)}(\mathbf{x})^T\phi^{(1)}(\mathbf{x'})$となる関数で,$\mathbf{x}$の$K_1$によるfeature representationという. $\theta, \theta_0$を変えることで可能なdiscriminant functionの集合
$$\mathcal{F}_1 = \{f_1(\cdot; \theta, \theta_0): \theta \in \mathbb{R}^d_1, \theta_0 \in \mathbb{R}\}$$
を構成できる. 同様にquadratic kernelによって可能な集合$\mathcal{F}_2$がある. このように

Model Selection Preliminaries

$S_n = \{(\mathbf{x}_1, y_1)...,(\mathbf{x}_n,y_n)\}$はtraining setとする. $\mathcal{F}_i$をmodelとして選んで,$\hat{f}_i \in \mathcal{F}_i$をbest fitting discriminant functionとすると,$\hat{f}_i$は
$$J(\theta, \theta_0) = \sum_t Loss(y_t, f(\mathbf{x}_t; \theta, \theta_0))+\lambda_n \|\theta\|^2$$
を最小化する.$Loss$はhinge lossでもlogisticでも他の何でもよい. $\lambda_n$は$n$によってへｋ擦るregularization parameterである. $\hat{f}_i=f(\mathbf{x};\hat{\theta}, \hat{\theta_0})$が新しいexampleにどれほどgeneralizeできているかが問題となる.
それぞれの$(\theta,\theta_0)$すなわちそれぞれのdiscriminant functionはexpected lossあるいはrisk
$$R(\theta,\theta_0) = E_{(\mathbf{x},y)\sim P}\left\{Loss^* (y, f(\mathbf{x};\theta,\theta_0)) \right\}$$
をもつ.ここで$P$は問題となるデータを生成している分布で，普通は未知であり,$(\mathbf{x},y)$もそこから生成されていると考える. これが,我々が最小化したいgeneralization errorである. $S_n$によって決まる$\hat{f}_i$のrisk $R(\hat{f}_i)$を最小化する$\mathcal{F}_i$を選ぶことが最終的な目標である. ただし$S_n$は$P$から生成されるので,$R(\hat{f}_i)$も$\hat{f_i}$も確率変数である(理論的には便利な仮定だが,実際に$S_n$が正しく$P$から生成されているとは限らない).
$P$が既知であるなら$argmax_y P(y|\mathbf{x})$を考えれば良いが，ここでは$P$は未知として,$S_n$だけを使って$\hat{f}_i \in \mathcal{F}_i$を，さらには$\mathcal{F}_i$をも選ばなければならない.
簡単のため,$\mathcal{F}_1, \mathcal{F}_2$を，linearとquadraticなdiscriminant functionの集合とし,$\mathcal{F_1, F_2}$のみを議論する. $\mathcal{F}_1 \subset \mathcal{F}_2$だから,$\mathcal{F}_2$から選ぶことで必ずtraining setにおけるerrorが小さい$f$を得られるが,example とlabelの関係が線形であるときにも非線形な$\mathcal{F}_2$から選ぶと，over-fittingしているかもしれない. 真の分布が線形分離可能であるとき,quadraticなdecison boundaryはノイズに影響されてgeneralizeがうまく行っていないということである. したがって$\mathcal{F}$が複雑になるほどtraining setに対する性能が向上する一方でtest setに対する性能は低下していく(fig.1). よって適切な複雑さを選ぶことが重要になってくる.

Model selection criteria: structural risk minimization

expected risk
$$R(\hat{f}_i) = E_{(\mathbf{x}|y)\sim P}\left\{ Loss^* (y, \hat{f_i}(\mathbf{x})) \right\}$$
とempirical risk(training errro)
$$R_n(\hat{f}_i) = \frac{1}{n} \sum_{t=1}^n \left( Loss^* (y, \hat{f_i}(\mathbf{x})) \right)$$
を関連付けることができれば,$R_n(\hat{f}_i)$を計算することで$R(\hat{f}_i)$を議論することが出来る. モデルが複雑になるほどtraining errorがgeneralization errorを表現しなくなっていくと考えられるので,$R_n$と$R$の関係を以下のように記述する.
$$R(\hat{f}_i) \leq R_n(\hat{f_i}) +C(n, \mathcal{F}_i, \delta) \ \ \ \ (16)$$
$C$はcomplexity penaltyといって,$\mathcal{F}_i$が複雑になるほど増大し,$n$によって減少する.
(16)はupper bound guarantee of generalization errorを与える. このupper boundが最小になるような$\mathcal{F}_i$を選べば良い. fig.2 はモデルの複雑さとこのboundの関係である.

$\mathcal{F}_i$が有限集合である時の不等式(16)の意味を考える.
$$P(\max_{f\in\mathcal{F}_i} |R(f)-R_n(f)|>\epsilon) \leq \delta$$
の上限を見積もる. これは少なくとも1つの$f$について，そのtraining errorとriskの差が$\epsilon$を上回る確率で,sample spaceは$S_n$の選び方である.
$\delta = P(\max_{f \in \mathcal{F}_i} |R(f)-R_n(f)|>\epsilon) \ \ (6)$は
$$R(f) \leq R_n(f) + \epsilon \ \ \text{for all } f \in \mathcal{F}_i$$
という主張が成立しない確率と言える. $\delta$を固定すると,(6)をみたす最小の$\epsilon =\epsilon(n, \mathcal{F}_i, \delta)$がcomplexity penaltyとなる.
$(6)$によって$\delta$を計算することはふつう不可能だから，上限を与える.
$$\begin{aligned}P(\max_{f \in \mathcal{F}_i} |R(f)-R_n(f)|>\epsilon)&=P(\exists f : |R(f)-R_n()|>\epsilon) \\ &\leq \sum_{\mathcal{F_i}} P(|R(f)-R_n(f)|>\epsilon)\ \ \ (8)\end{aligned}$$
$f$を固定して$P(|R(f)-R_n(f)|>\epsilon)$を考える. training sample $(\mathbf{x}_t, y_t)$がi.i.d.に得られて,$s_t = \begin{cases} 1 \ \ &\text{ if } y_tf(\mathbf{x}_t)\leq 0 \\ 0 &\text{otherwise}\end{cases}$とすると empirical error $R_n(f)$は$s_t$の和で,
$$R_n(f) = \frac{1}{n}\sum_{t=1}^n s_t$$
$E[s_t]=R(f)$だから,
$$P(|R(f)-R_n(f)|>\epsilon) = P(|q-\frac{1}{n}\sum_t s_t|>\epsilon)$$
ただし$q=R(f)$で,確率のsample spaceは$P(s_t=1)=q$をみたす$s_1, ..., s_n$である.
Hoeffding’s inequalityから
$$P(|q-\frac{1}{n}\sum_{t=1}^n s_t| > \epsilon)\leq 2 \exp(-2n\epsilon^2)$$
が成立する. この上限は$f$によらない. この結果を(8)に代入して，
$$P(\max_{f \in \mathcal{F}_i}|R(f)-R_n(f)|>\epsilon) \leq 2|\mathcal{F}_i|\exp(-2n\epsilon^2)=\delta$$
が成立する. $\epsilon$に解いて,
$$\epsilon=\epsilon(n,\mathcal{F}_i, \delta) = \sqrt{\frac{\log|\mathcal{F}_i|+\log(2/\delta)}{2n}}$$
である.これが$\mathcal{F}_i <\infty$の場合のcomplexity penaltyである.
以上より,少なくとも$1-\delta$の確率で
$$R(f) \leq R_n(f) + \sqrt{\frac{\log|\mathcal{F}_i| + \log (2/\delta)}{2n}}, \text{ uniformly for all }f \in \mathcal{F}_i$$
が成立する. model selectionでは$\{\mathcal{F}_i\}$のそれぞれについて$\hat{f_i}$を選び，$\hat{f}_i, |\mathcal{F}_i|$によってboundを計算し,boundが最小となる$\mathcal{F}_i$を選ぶ． このとき$n$と$\delta$は固定する．

Example

$\delta=0.05$とし,training error 0, generalization error が最大10%であるようにtraining exampleの個数$n$を見積もる.
$$R(f) \leq 0 + \sqrt{\frac{\log |\mathcal{F}_i| + \log (2/0.05)}{2n}}\leq 0.10$$
だから,
$$n = \frac{\log|\mathcal{F}_i| + \log (2/0.05)}{2(0.10)^2}$$
である.

Model selection criteria: Bayesian score, Bayesian information criterion

linear regressionの例を通じてBayesian scoreについての理解を深める. モデル$\mathcal{F}$は$d$次元のインプット$\mathbf{x}$を$y \in \mathbb{R}$に写す写像で,
$$P(y|\mathbf{x}, \theta, \sigma^2) = N(y; \theta^T \mathbf{x}, \sigma^2)$$
とする. $\sigma^2$を固定して,$\theta$だけを動かすとする. $D=\{(\mathbf{x}_1, y_1),...,(\mathbf{x}_n, y_n)\}$が与えられたとき,likelihoodは
$$L(D;\theta) = \prod_{t=1}^n N(y_t; \theta^T\mathbf{x}_t,\sigma^2) = \prod_t \frac{1}{\sqrt{2\pi \sigma^2}}\exp(-\frac{1}{2}(y_t-\theta^T\mathbf{x}_t)^2)$$
以前は$L$を最大化する$\hat{\theta}$を唯一つ選んだが，Bayesian analysisではlinear regression functionたちを$L(D;\theta)$によって重み付けして，それら全てを利用する.
このような枠組みでは,$D$を得た後の$\theta$の知識はposterior distribution $P(\theta|D)$であって,これは$L(D;\theta)$と相似である.つまり$P(\theta|D) \propto L(D;\theta)$.
しかし例えば$D=\phi$の場合には$\forall \theta. L(D;\theta)=1$だから,$P(\theta|D)$が発散してしまう．　よってprior distribution $P(\theta)$を導入する.
$$P(\theta) = N(\theta; 0, \sigma^2_P \cdot I)$$
すると
$$P(\theta|D) \propto L(D;\theta) P(\theta)$$
で,normalization constantは
$$P(D|\mathcal{F}) = \int L(D;\theta)P(\theta)d\theta$$
であり,marginal likelihoodともいう. これは$\mathcal{F}$と$D$にのみよる. regressionでは
$$\begin{aligned} \log P(D|\mathcal{F}) &= -\frac{n}{2} \log(2\pi\sigma^2) + \frac{d}{2} \log \lambda - \frac{1}{2} \log |\mathbf{X^TX}+\lambda I| \\ &-\frac{1}{2\sigma^2}(\|\mathbf{y}\|-\mathbf{y^TX}(\mathbf{X^TX}+\lambda I)^{-1}\mathbf{X^ty})\end{aligned}$$

ここで$\lambda = \sigma^2/\sigma^2_P$はnoise とpriorの比で,$\mathbf{X}=[\mathbf{x}_1,...,\mathbf{x}_n]^T, \mathbf{y}=[y_1,...,y_n]^T$である.
このときposteriorは
$$P(\theta|D) = \frac{L(D;\theta)P(\theta)}{P(D|\mathcal{F})}$$
と正規化される.$P(\theta|D)=N(\theta;\mu,\Sigma)$とposteriorも正規分布する.
$$\begin{aligned} \mu = (\mathbf{X^TX}+\lambda I)^{-1}\mathbf{X^Ty} \\ \Sigma = \sigma^2 (\mathbf{X^TX}+\lambda I)^{-1} \end{aligned}$$

新たな$\mathbf{x}$に対する推測は
$$P(y|\mathbf{x},D) = \int P(y|\mathbf{x},\theta)P(\theta|D)d\theta$$
で与えられる. 真のBayesianはまさに全ての$\theta$について上の積分を行うが,我々はfeature mapping $\mathbf{x} \mapsto \phi(\mathbf{x})$で特徴づけられるregression modelに$\theta$を制限して議論することになる.linearな$\phi^{(1)}$とquadraticな$\phi^{(2)}$をfeature mappingとする.
$$\begin{aligned} \mathcal{F}_1: \ \ &P(y|\mathbf{x},\theta,\sigma^2) = N(y;\theta^T\phi^{(1)}(\mathbf{x}),\sigma^2), \theta \in \mathbb{R}^{d_1}, P(\theta|\mathcal{F}_1) \\ \mathcal{F}_2: &P(y|\mathbf{x},\theta,\sigma^2)=N(y;\theta^T \phi^{(2)}(\mathbf{x}),\sigma^2) , \theta \in \mathbb{R}^{d_2}, P(\theta|\mathcal{F}_2) \end{aligned}$$
が比較するmodelである. modelにPrior distribution $P(\theta|\mathcal{F})$を含むのには利点も欠点もあるが，どちらにせよ含まないのと大した差はない.
$\mathcal{F_1, F_2}$のうち,よりmarginal likelihood (Bayesian score)が大きい方を選ぶことになる. すなわち,$D$を与えられたら,$P(D|\mathcal{F}_i) > P(D|\mathcal{F}_j)$ならば$\mathcal{F}_i$を選ぶのである.

Model selection criteria: Bayesian information criterion(BIC)

Bayesian information criterion(BIC)はBayesian scoreに対するasymptotic(漸近的な) 近似であって，その単純さのためによく使われる.
$$BIC = l(D,\hat{\theta}) - \frac{d}{2}\log (n)$$
である.ここで$l(D;\theta)$はtraining dataに対するmaximum likelihoodの対数であって,$d$はmodelのindependent parameterの個数, $n$はtraining exampleの個数である. $BIC$は$n$が十分大きいときBayesian scoreに漸近する. Bayesian scoreの計算は困難なことが多いので,かわりにBICを使う. Bayesian scoreと同様に,BICが大きい方のmodelを選ぶ.

MIT OCW, Machine Learning 09日目 カーネル化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.

Lecture 8

Support Vector Machine Revisited

SVMをdual form(exampleが内積でのみ現れる形)に変換する. すべてのexampleを$\phi$で$d$次元のfeature spaceに写し,$\{\phi(\mathbf{x_t}, y_t)\}_{t=1}^n$が線形分離可能であるようにし,feature spaceにおいてmarginを最大化するパラメータを考える.この問題は
$$\text{minimize } \|\theta\|^2/2 \text{ subject to } y_t(\theta^T \phi(\mathbf{x}_t) + \theta_0) \geq 1, t=1,...,n \ \ \ (1)$$
という最適化問題に一致する. もちろんslack variableも導入できるが,これは後に回す. このような最適化問題(凸,線形制約)は,Lagrange multipliersによってdual formに変形できる. $\alpha_t \geq 0$を導入し,$\alpha = \{\alpha_1,...,\alpha_n\}$によって
$$J(\theta, \theta_0;\alpha)=\|\theta\|^2/2 - \sum_{t=1}^n \alpha_t \left[y_t(\theta^T\phi(\mathbf{x}_t)+\theta_0)-1 \right]$$
を$\alpha$によって最大化することを考えるのである.$J(\theta, \theta_0)=\max_{\alpha\geq 0} J(\theta, \theta_0, \alpha)$の最小化が$(1)$に一致することを示す.
$\theta, \theta_0$を少なくとも1つの束縛条件が満たされていないように設定する.$y_i(\theta^T \phi(\mathbf{x}_i)+\theta_0)<1$であるとすると任意の$\alpha_i>0$に$-\alpha_i[y_i(\theta^T \phi(\mathbf{x}_i)+\theta_0)-1]>0$.$\alpha_i =\infty$とすれば$J(\theta,\theta_0)=\infty$.だから,Lagrange multiplier $\alpha$は制約条件を満たさせる働きがあるとわかる.
Slater conditionsという条件を満たしているとき,ある変数で最大化し,他の変数で最小化するというLagrange multipliersの最適化問題の最大化最小化の順序を交換できる.つまり
$$\min_{\theta, \theta_0} \max_{\alpha\geq 0} J(\theta, \theta_0;\alpha) = \max_{\alpha\geq 0} \min_{\theta, \theta_0} J(\theta, \theta_0, \alpha)$$
である. 左辺をprimal formといい,右辺をdual formという. dual formについて,まず$\min_{\theta, \theta_0}J$を解く.微分して
$$\begin{aligned} \frac{d}{d\theta_0}J &= - \sum_{t=1}^n \alpha_t y_t =0\\ \frac{d}{d\theta} J &= \theta - \sum_{t=1}^n \alpha_t y_t \phi(\mathbf{x}_t)=0 \end{aligned}$$
またしても,最適な$\theta$は$\{\phi(\mathbf{x}_t)\}_t$の張る空間の元となった.これらをもとの式に代入して,
$$\begin{aligned} J(\alpha) &= \min_{\theta,\theta_0}J(\theta, \theta_0,\alpha) \\ &= \begin{cases} \sum_t \alpha_t - (1/2) \sum_i \sum_j \alpha_i \alpha_j y_iy_j [\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)], &\text{ if } \sum_t \alpha_t y_t = 0 \\ -\infty &\text{otherwise} \end{cases} \end{aligned}$$
よって,dual formの解は
$$\begin{aligned} \text{maximize } &\sum_t \alpha_t - (1/2) \sum_i \sum_j \alpha_i \alpha_j y_iy_j [\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)] \\ \text{subject to } & \alpha_t \geq 0, \sum_t \alpha_t y_t = 0\end{aligned}$$
の解である. これがSVMのdual formとかkernel formといい,quadratic optimization problemであり,Gram matrix $\mathbf{K} = (k_{i,j}) = (\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j))$によって,特徴づけられる.
maximum margin hyperplaneはsupport vectorと呼ばれる少数のexampleによって決まることをすでに見たが,これは$\phi$によって写像されたexampleたちにも同様で,ほとんどの$\hat{\alpha}_t$は$0$になり,$\hat{\alpha_t}>0$なるとき,$\mathbf{x_t}$や$\phi(\mathbf{x_t})$をまたsupport vectorという.
$\hat{\alpha}_t$が決まると,$SV$をsupport vectorの集合として,
$$\begin{aligned} \hat{y}(\mathbf{x}) &= \hat{\theta}^T\phi(\mathbf{x})+\hat{\theta_0} \\ &= \sum_{t} \hat{\alpha_t}y_t [\phi(\mathbf{x}_t)^T\phi(\mathbf{x})] + \hat{\theta_0} \\ &= \sum_{t \in SV} \hat{\alpha_t}y_t [\phi(\mathbf{x}_t)^T\phi(\mathbf{x})] + \hat{\theta_0} \end{aligned}$$
によって新しいexample $\mathbf{x}$の推測$\hat{y}({\mathbf{x}})$が計算できる.
$\hat{\theta_0}$は$\hat{\alpha}$を求めた後で,
$$\forall i \in SV. \ y_i(\hat{\theta}^T \phi(\mathbf{x}_i)+\hat{\theta_0}) = y_i \sum_{t \in SV}\hat{\alpha_t}[\phi(\mathbf{x}_t)^T\phi(\mathbf{x}_i)]+y_i\hat{\theta_0}=1$$
を解くことで得られる.
この解のgeometric marginは$1/\|\hat{\theta}_0\|$で得られる.つまり
$$\hat{\gamma_{geom}} = \left( \sum_{i=1}^n \sum_{j=1}^n \hat{\alpha_i}\hat{\alpha_j}y_iy_j K(i,j) \right)^{-\frac{1}{2}}$$

geometric marginを最大にするようなkernelが最適なkernelと言えるが,定数倍によってgeometric marginもその分定数倍になるので,kernelの比較には正規化が必要である.

Kernel Optimization

kernelのあるパラメータを変えて,問題により適したkernelをつくることができる. パラメータの最適化には,cross-validationやgeneralization errorに関連した基準(marginなど)が用いられる.

MIT OCW, Discrete Stochastic Processes 03日目

Robert Gallager. 6.262 Discrete Stochastic Processes. Spring 2011. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Assignment Problem set 2.
問
解答

Exercise 1.10

答案.

$X,Y$はただの実数確率変数とする(拡大実数確率変数ならあきらかに命題は成り立たない)
$\{\omega|Z(\omega)=\pm \infty\} \subset \{\omega| X(\omega)=\pm \infty\} \cup \{\omega| Y(\omega)=\pm \infty\}$である.
($X(\omega)=\infty, Y(\omega)=-\infty$)のような場合が有るから,一般には等号ではない)
また,$X, Y$はreal r.v.だから,$Pr(X=\pm \infty)=Pr(Y=\pm \infty)=0$.
$Pr(Z=\pm \infty) \leq Pr(X=\pm \infty \lor Y=\pm \infty) \leq Pr(X=\pm \infty) + Pr(Y=\pm \infty) \leq 0$
よって示せた.

Exercise 1.17

答案.

(a) $$\begin{aligned}E[Y] &= \int^\infty_1 \frac{2}{(y+1)(y+2)}dx(y=floor(x)) = \sum_{y\geq 0} \frac{2}{(y+1)(y+2)} \\ &= 2 \sum_{y\geq 0} \left(\frac{1}{y+1} -\frac{1}{y+2} \right) = 2 \end{aligned}$$
(b) $p_Y(y) = F_Y(y)-F_Y(y-1)=2\left(\frac{1}{y(y+1)}-\frac{1}{(y+1)(y+2)}\right)=\frac{4}{y(y+1)(y+2)}$
さらに$\sum_{y\geq 1} y p_Y(y)= \sum 4/(y+1)(y+2) = 4 \sum (1/(y+1) - 1/(y+2)) = 2$
(c) $$E[X|Y=y] = \sum_{1\leq x \leq y} x/y = \frac{1}{y}\sum_{1\leq x\leq y}x=\frac{1}{y} \frac{1}{2}y(y+1)=\frac{y+1}{2}$$
$E[E[X|Y]y(Y)]=E[Xg(Y)]$の公式で$g=1$とすれば
$$E[X]= E[\frac{y+1}{2}]=\frac{3}{2}$$
がたしかに成立.
さらに,$p_X(x) = \sum_{y=1}^\infty p_{X|Y}(x|y)p_Y(y)=\sum_{y\geq x} \frac{4}{y^2(y+1)(y+2)}$
$\sum xp_X(x)$の計算が非常に面倒なのはもはや明らかだろう.
(d)
$$E[Z|Y=y] = \sum_{1\leq z \leq y^2} \frac{z}{y^2} =\frac{1}{y^2} \sum_{1\leq z\leq y^2} z = \frac{1}{y^2}\frac{1}{2}y^2(y^2+1)=\frac{y^2+1}{2}$$
さらに$E[Z] = 1/2+ E[y^2]/2$
ここで$E[Y^2]=\sum_y y^2 p_Y(y) = 4\sum y^2/(y(y+1)(y+2))\geq 4\sum 1/(y+2) \rightarrow \infty$
したがって$E[Y^2]=\infty$ゆえに$E[Z]=\infty$.

Exercise 1.31

答案.

(a) $x \leq 0, r \geq 0$で$|e^{rx}|\leq 1$
ゆえに$r \geq 0$で$\int^0_{-\infty} e^{rx}dF(x) \leq \int^0_{-\infty} dF(x) \leq 1$
2つめの広義積分も同様.
(b) $0\leq r \leq r_1$ならば$0\leq e^{rx} \leq e^{r_1x}$が全ての$x$に成立するから
$0 \leq \int e^{rx}dF(x) \leq \int^\infty_0 e^{r_1x} dF(x)$である.
(c) (b)と同様.
(d) $r=0$で$g_X(r)$は存在する.また$r_1>0$において右の項が存在するとき(a)から左の項も存在し,$g_X(r_1)$は定義されて, $0\leq r\leq r_1$で$g_X(r)$は定義されている.$r_1< 0$でも同様である.
(e) (模範解答)
$f_X(x)=e^{-x}$とすると,$g_X(1)=\infty$.
$f_X(x)=(ax^{-2})e^{-x}, x\geq 1$とすると$g_X(1)<\infty$.

Exercise 1.33

答案.

CLTを使う.
$$Pr(\frac{S_n-nE[X]}{\sqrt{n}\sigma} \leq y) = \int^y_{-\infty} \frac{1}{\sqrt{2\pi}}\exp(-\frac{x^2}{2})dx$$
それぞれの小問で求める極限を$I$とする. $E[X]=\delta, \sigma=\sqrt{\delta(1-\delta)}$に注意する.
(a) $$\begin{aligned}I &= \lim_nPr(n\delta-m \leq S_n \leq n\delta + m) \\ &=\lim_n Pr(-\frac{m}{\sqrt{n}\delta} \leq \frac{S_n-n\bar{X}}{\sqrt{n}\sigma} \leq \frac{m}{\sqrt{n}\sigma}) \\ &=\lim_n \int^{\frac{m}{\sqrt{n}\sigma}}_{-\frac{m}{\sqrt{n}\sigma}} \frac{1}{\sqrt{2\pi}}\exp(-\frac{x^2}{2})dx \\&=0 \end{aligned}$$
(b) $$\begin{aligned}I &= \lim_nPr(0 \leq S_n \leq n\delta + m) \\ &=\lim_n Pr(-\frac{n\delta}{\sqrt{n}\delta} \leq \frac{S_n-n\bar{X}}{\sqrt{n}\sigma} \leq \frac{m}{\sqrt{n}\sigma}) \\ &=\lim_n \int^{\frac{m}{\sqrt{n}\sigma}}_{-{\sqrt{n}}} \frac{1}{\sqrt{2\pi}}\exp(-\frac{x^2}{2})dx \\&=1/2 \end{aligned}$$
(c) $$\begin{aligned}I &= \lim_nPr(n\delta-n/m \leq S_n \leq n\delta + n/m) \\ &=\lim_n Pr(-\frac{n}{m}\frac{1}{\sqrt{n}\sigma} \leq \frac{S_n-n\bar{X}}{\sqrt{n}\sigma} \leq \frac{n}{m}\frac{1}{\sqrt{n}\sigma}) \\ &=\lim_n Pr(-\frac{\sqrt{n}}{m\sigma} \leq \frac{S_n-n\bar{X}}{\sqrt{n}\sigma} \leq \frac{\sqrt{n}}{m\sigma})\\ &=\lim_n \int^{\frac{\sqrt{n}}{m\sigma}}_{-\frac{\sqrt{n}}{m\sigma}} \frac{1}{\sqrt{2\pi}}\exp(-\frac{x^2}{2})dx \\&=1 \end{aligned}$$

Exercise 1.38

答案.

$$\begin{aligned}\frac{S_n}{\sqrt{n}\sigma} - \frac{S_{2n}}{\sqrt{2n}\sigma}&=\frac{\sqrt{2}S_n -S_{2n}}{\sigma\sqrt{2n}} \\ &=\frac{\sqrt{2}-1}{\sqrt{2}}\frac{S_n}{\sqrt{n}\sigma}-\frac{1}{\sqrt{2}}\frac{\sum_{i=n+1}^{2n} X_i}{\sqrt{n}\sigma} \end{aligned}$$
IIDだから$T_n=\sum_{i=n+1}^{2n}X_i$とするとCLTによって左の項は$N(0, \frac{3-2\sqrt{2}}{2})$,右の項は$N(0,\frac{1}{2})$に収束する.よってその差は$N(0,2-\sqrt{2})$に収束する.

Exercise 1.42

(a) $E[X]= (-1+1)\cdot (1-10^{-10})/2 +10^{12} * 10^{-10}=100$
$var[X] = E[X^2]-E[X]^2 = 10^{14}-2\cdot 10^{-10}+10^4$
$E[S_n]=nE[X]=100n$
$var[S_n]=n E[X] =n [10^{14}-2\cdot10^{-10}+10^4] \sim n10^{14}$
(b) $10^{12}$が$10^6$回出ないということであって,求める確率は$(1-10^{-10})^{10^6}$
(c) union bound: $Pr(\cup A_n) \leq \sum Pr(A_n)$
$1-F_{S_n}(10^6) = Pr(S_n > 10^6) = Pr(\cup_{m>10^6} S_n=m) \leq \sum_{m>10^6}Pr(S_n=m)$
$Pr(S_n=m)\leq 10^{-10}$が必ず成立するから,
$1-F_{S_n}(10^6) \leq 10^6 \cdot 10^{-10}=10^{-4)}$