MIT OCW, Fundamentals of Probability 23日目 Markov Chain 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 24. Markov Chains II. Mean Reccurence Time
  • 24.1 Markov Chains with a Single Recurrence Class
    • • Lemma 24.1
      • Lemma 24.2
      • Exercise 1.
      • Exercise 2.
    • 24.2 Uniqueness of the Stationary Distibution
      • Theorem 24-3 (証明略)
    • 24.3 Ergodic Theorem
      • Theorem 24-9 (証明略)

Lecture 24. Markov Chains II. Mean Reccurence Time

24.1 Markov Chains with a Single Recurrence Class

前章でrecurrenceの関係$\leftrightarrow$は同値関係であり,$\mathcal{T}$をtransientの集合とすると,$\mathcal{X} \backslash \mathcal{T}$は$\leftrightarrow$によって同値類別できることを見た.また同値類は$R_1, ..., R_r$とする.$\leftrightarrow$でできた同値類のそれぞれをclassとよぶことにする

Lemma 24.1

任意の同値類$R_k$において,$i \in R_k$かつ$j \notin R_k$ならば$p_{i,j}=0$
すなわち,一旦ある同値類$R_k$に入ったら,その後どう遷移しようと$R_k$からは抜け出せない.

proof.

$p_{i, j} > 0 \Rightarrow i \rightarrow j$. $i$はrecurrentだから$j \rightarrow i$であり,$j \in R_{k}$. これは矛盾.

$$T_i = \min \{n \geq 1: X_n=i|X_0=i\}$$
というrandom variableを,$\infty$を許して導入する.これをthe first passage timeという.

Lemma 24.2

任意の$i \in \mathcal{T}$に, $P(X_n=i, i.o.)=0$である. すなわち,有限時間ステップの経過後にchainが$i$に戻ってくることは殆ど全く無く,また$E[T_i]= \infty$である.

proof.

定義より$i \rightarrow j, j\nrightarrow i$なる$j \notin \mathcal{T}$がある. ゆえに$P(T_i = \infty)>0$であって,$T_i\geq 0$だから$E[T_i]=\infty$が成立する.
$I_{i,m}$を, chainが少なくとも$m$回$i$に戻ってくるというeventとする. $P(I_{i, 1})=P(T_i < \infty)$である.またLemma24.1から$P(I_{i,1})<1.$
state $i$に$m-1$回目に到達したときから見て,次に$i$に到達する確率というのは,$i$から$i$に1回推移する確率に等しいというのがMarkov性から言えるので,$(I_{i,m}|I_{i,{m-1}})=P(T_i < \infty)$が成り立ち,また明らかに$I_{i, m} \subset I_{i, m-1}$であって, $P(I_{i,m})=P(I_{i,m}|I_{i,m-1})P(I_{i,m-1})=P(T_i < \infty)P(I_{i,m-1}) =\cdots =P(T_i<\infty)^m$. $P(T_i<\infty)<1$だから,probabilityの連続性を使って,$P(\cap_m I_{i,m})=\lim P(I_{i,m})=\lim_m P(T_i<\infty)^m = 0$.$X_n=i , \text{ i.o.}$は$\cap _m I_{i,m}$と一致するから,補題が示せた.

Exercise 1.

$\mathcal{T} \neq \mathcal{X}$を示せ.

答案.

$\mathcal{X} = \mathcal{T}$を仮定する. $P(X_n=i, \text{ i.o.})=0$が任意の$i \in \mathcal{X} = \{1, ...,N\}$に成立するから,$P(X_n\in \mathcal{X}, \text{ i.o.})=0$つまり有限時間ステップの後,殆ど必ずこのMarkov chainはどのstateにも到達していない. これは不合理.

Exercise 2.

$i\in \mathcal{T}$で $\pi$は任意のstationary distributionとする. $\pi_i = 0$を示せ.

答案.

$\pi_i >0$を仮定する.$\pi_i = \sum_{1 \leq k \leq N} p_{k,i}\pi_k$である.$i \in \mathcal{T}$なら,少なくともひとつの$\pi_k>0,p_{k,i}>0$なる$k$がある.$k \in {R}$ならば$i \leftrightarrow k$で$k \in \mathcal{T}$に反するから$k \in \mathcal{T}$である.$\pi_k >0$なので，同じ論法で$k \leftarrow l \in \mathcal{T}$なる$l$があって,$l\neq i, k$.繰り返して,$i \leftarrow k \leftarrow l \leftarrow \cdots \leftarrow l_n \leftarrow \cdots$なる$\{l_n\} \subset \mathcal{T}$がある. $|\mathcal{T}|<|\mathcal{X}|<\infty$から,この列はいつか終わり,その終点$l_M$では$0 \neq \pi_{l_M} = \sum_{1 \leq j \leq N} p_{j, l_M}\pi_j = \sum 0 \pi_j = 0$ これは矛盾.

Exercise 3.

M.c. $\{X_n\}$がrecurrent class $R$をもち,$i \in R$ならば$P(X_n=i, \text{ i.o.})=1$を示せ.また,$P(T_i > t) \leq Cq^t$が任意の$t \geq 0$になりたつような$0<q<1, C>0$が存在することを示し,最後に$E[T_i]<\infty$を示せ.

答案.

ある$j \in i$があって$i \rightarrow j \rightarrow i$だから,$P(T_i < \infty)=1$. Lemma 24.2の証明と同じ論法で$P(X_n=i \text{ i.o.})=P(\cup_m I_{i, m})=\lim_m P(T_i <\infty))^m=1$.
ビーンもうダメ

recurrent class　がただ一つであるMarkov chainの例をいくつか挙げる. 特に$\mathcal{T}=\phi$であるとき,このMarkov chainはirreducibleという.$\mu_i = E[T_i]$を$\infty$を許して定義するとき,これを$i$におけるmean recurrence timeという.

24.2 Uniqueness of the Stationary Distibution

Theorem 24-3 (証明略)

recurrence class がただ一つしか無い有限Markov chainは固有のstationary distribution $\pi$をもち,$\pi_i = 1/ \mu_i$である.特に$i$がrecurrentであるとき,またそのときにのみ$\pi_i>0$となる.

24.3 Ergodic Theorem

$N_i(t)$を,$0, 1, ..., t$の間に$i \in \mathcal{X}$にchain が到達した回数とする. $N_i(t)/t \rightarrow \pi_i$である.このように,$t$に依存する確率変数を$t$で割った確率変数の極限のもつ性質をergodic properties(エルゴード性)という. これは,chaihの時間的な平均$N_i(t)/t$が,空間的な平均$\pi_i$に近づくという著しい主張である.

Theorem 24-9 (証明略)

任意の$k \in \mathcal{X}$を初期状態$X_0=k$として, また任意の$i \in \mathcal{X}$に,$\lim_{t \rightarrow \infty} N_i(t)/t = \pi_i\ \ \text{a.s.}$であり, $\lim_{t \rightarrow \infty} E[N_i(t)]/t = \pi_i$である.

正直わからないのでなにかいい本を探してじっくり読みたい(願望)

MIT OCW, Fundamentals of Probability 22日目 Markov Chain 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 23. Markov Chains

23.1 Introduction

Definition 23-1

$\{X_n \}_{n\geq 1}$がMarkov chain
$\Leftrightarrow$ $X(\Omega) = \mathcal{X}$はたかだか可算集合で,
$$P(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, ..., X_1=x_1) = P(X_n=x_n|X_{n-1}=x_{n-1})$$
$\mathcal{X}$をstatesといい,$X_n = s \in \mathcal{X}$なら,$\{X_n\}$は$n$においてstate $s$をとる という. 特に無限であると言わない場合,$|\mathcal{X}| <\infty$の場合を考える.このとき$\mathcal{X} = \{1, ..., N\}$として一般性を失わない.

Proposition 23-1

Markov chain $\{X_n\}_{n \geq 1}$について,
(a) 任意の$s, x_1, ..., x_n \in \mathcal{X}$と$m \in \mathbb{N}$について,
$$P(X_{n+m}=s|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2},...,X_1=x_1)=P(X_{n+m}=s|X_{n-1}=x_{n-1})$$

(b) 任意の$x_1, ...,x_n \in \mathcal{X}$と$k \in \{1, ...,n\}$について,
$$\begin{aligned} &P(X_n=x_n|X_{n-1}=x_{n-1},...,X_1=x_1|X_k=x_k)\\&=P(X_n=x_n,X_{n-1}-x_{n-1}, ..., X_{k+1}=x_{k+1}|X_k=x_k)P(X_{k-1}=x_{k-1},...,X_1=x_1|X_k=x_k) \end{aligned}$$

23.2 Examples

random walkはMarkov chainの一つである.
サイコロを繰り返しふって,$X_n$は$n$回の試行で過去出た出目6の回数とする. このとき$P(X_n=x+1|X_{n-1}=x) = 1/6, P(X_n=x|X_{n-1}=x)=5/6$であり,また$y\neq x, x+1$なら $P(X_n=y|X_{n-1}=x)=0$である.これは右へ進む確率$1/6$,その場にとどまる確率$1/6$のrandom walkとみなせる.

23.3 Homogeneous Finite State Markov Chain

Definition 23-2

Markov chain $\{X_n\}$がhomogeneousである
$\Leftrightarrow \forall n\ P(X_{n+1}=y|X_n=x)=P(X_2=y|X_1=x)$

$p(x, y)=P(X_{n+1}=y|X_n=x)$と書くようにすると,$N\times N$行列$P=(p_{i,j})$という行列ができる.これを$\{X_n\}$のtransition matrixという. $\sum_j p_{i,j}=1$である. 任意の行について,その行の要素の和が1であり,全ての要素が非負な行列を stochastic matrixという.
さて,
$$\begin{aligned} P(X_{n+2}=j|X_n=i) &= \sum_{1 \leq k \leq N} P(X_{n+2}=j|X_{n+1}=k,X_n=i) P(X_{n+1}=k|X_n=i)\\&=_{\text{}}\sum_{1\leq k\leq N} P(X_{n+2}=j|X_{n+1}=k)P(X_{n+1}=k|X_n=i)\\&=_{}\sum_{1 \leq k \leq N}p_{k,j}p_{i,k} \end{aligned}$$
だから,$P^2$の$(i, j)$成分($p^{(2)}_{i,j}$と書く)は,$\{X_n\}$を1つ飛ばしにしたMarkov chainのtransition matrixと考えることが出来る. 同じ論法で$r \in \mathbb{N}$に,$P^r$は$r-1$飛ばしのMarkov chainのtransition matrixである. $P^r$の$r\rightarrow \infty$での振る舞いを理解するのは大切である. Markov chainの多くを占めるクラスで,$j$のみによって$\lim_{r \rightarrow \infty} p_{i,j}^{r}$が存在することを後で見る.この性質をmixingという.
$e_j$で$\mathbb{R}^N$の$j$番目の標準基底ベクトルを表すことにする.また$e$を全ての要素が1である$N$次元ベクトルとする. $X_0 = i$とすると, $X_n$のprobability vectorは$e^T_i P^n$であり,$X_0$がprobability vector $\mu$によって決まるなら, $X$のprobability vectorは$\mu^T P^n$になる.

23.4 Stationary Distribution

$\mathcal{X} = \{1, 2\}, p_{1, 1,}=p_{1,2}=1/2, p_{2,1}=1, p_{2,2}=0$という単純なMarkov chainを考える. $\mu_1 = P(X_0=1)=2/3, \mu_2=P(X_0=2)=1/3$なる$\mu =(\mu_1, \mu_2)^T$から$n=0$でのstateが生成されるとき,$P(X_1=1)=(1/2)P(X_0=1)+P(X_0=2) = 2/3, P(X_1=2)=1-P(X_1=1)=1/3$.
よって$P(X_0=i)=P(X_1=i)\ \ \ i=1,2$で,$X_0, X_1$は同じ分布を持つと言える.これは任意の$n$も言える.

Definition 23-2

probability vector $\pi = (\pi_i), 1 \leq i \leq N$がstationary distribution
$\Leftrightarrow P(X_0)=\pi_i$と初期状態を決めると$\forall 1\leq i\leq N,1 \leq n, \ \ P(X_n=i)=\pi_i$

さらにこのとき(Markov chain$\{X_n\}$にsteady stateがあって,初期状態がそれによって決められたとき)$\{X_n\}$はsteady stateにあるという.

定義から,$\pi$がsteady stateである必要十分条件は,$\pi_i \geq 0, \sum \pi_i=1$かつ
$$\forall i\ \ \pi_i = \sum_{1 \leq k \leq N} p_{k,i}\pi_k$$
が成り立つことである. これはベクトル形式で書くと
$$\pi^T = \pi^T P$$
である.

Theorem 23-4

$\mathcal{X}<\infty$なMarkov chainは少なくとも１つのstationary distributionをもつ.

proof. 略 linear programming(線形計画法)の知識が必要らしい・・・ あとで確率論的な証明を与える.

23.5 Classification of States, Rucurrennt and Transient States

state 有限, homogeneousなMarkov chainがtransition matrix $P$を持っているとき, 有向グラフが作れる.
ノード集合$V= \mathcal{X}$, $p_{i,j} > 0$なる$i, j\in V$はedge集合の元;$(i, j) \in E$とする. $i$から$j$へ至るpathがあるとき$i$は$j$とコミュニケートする(i communicates with j)といい,$i \rightarrow j$と書く. これは$\sum_n p_{i,j}^{(n)}>0$ということである. $i\rightarrow j$だが$j\rightarrow i$でないというのは,chainが$i$から始まって$j$に至ると,再び$i$に戻ることはほとんど必ずないということである.

Definition 23-5

$i \in \mathcal{X}$がtransient
$\Leftrightarrow i \rightarrow j$だが$j \nrightarrow i$なる$j\in \mathcal{X}$が存在する

$i$がtransientでないとき,recurrentであるという.
$i\rightarrow j, j \rightarrow i$なるとき$i \leftrightarrow j$と書く.この関係は同値関係である.recurrent statesは同値類$R_1, ..., R_r$に分割でき,$T$をtransient stateの集合とすると,
$\mathcal{X} = T \cup R_1 \cup ... \cup R_r$と,互いに素な集合の和集合として書ける.

MIT OCW, Fundamentals of Probability Assignmets 1

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.

Exercise 1.

(a) 可算個の可算集合の和は可算集合であることを示せ
(b) $\mathbb{Q}$が可算集合であることを示せ

答案.

(a) $A_i=\{a^i_1,a^i_2,...\}$が,$i=1,2,...$と可算個あるとき,$\cup_i A_i$の任意の元は$a^i_j$と書ける. $\mathbb{N} \rightarrow \mathbb{N}^2$なる全単射な写像が在ることを言えばよく,例えば
$n$について,$m(m+1)/2 \leq n < (m+1)(m+2)/2$なる$m$がただ一つあって,$n \mapsto (m(m+1)/2 - (m-n), n-m+1)$は条件を満たす.
(b) 任意の有理数は2つの正数の組で表せるから,(a)の単純な拡張で示せる.

Exercise 2.

$\{x_n\}, \{y_n\}$は実数列で,それぞれ$x, y \in\mathbb{R}$に収束するとする. $x_ny_n$が$xy$に収束することを示せ.

答案.

定義より$\forall \epsilon > 0 \exists N \text{ s.t. } n \geq N \Rightarrow |x_n-x|<\epsilon \land |y_n-y|<\epsilon$.よって$n \geq N$ならば
$$\begin{aligned}|x_ny_n - xy| &= |(x_n-x)(y_n-y)+x_ny + xy_n -2xy| \\ &\leq |x_n-x||y_n-y|+|x_ny+xy_n-2xy| \\ &\leq |x_n-x||y_n-y|+|y||x_n-x|+|x||y_n-y)| \\ &\leq \epsilon^2 + (|x|+|y|)\epsilon \end{aligned}$$
$|x|, |y|$は$n$によらないから,確かに$|x_ny_n-xy| \rightarrow 0 \Leftrightarrow x_ny_n \rightarrow xy$

Exercise 3.

$f: A \times B \rightarrow \mathbb{R}, A, B \neq \phi$とする.
(b) $$\sup_{x \in A} \inf_{y \in B} f(x, y) \leq \inf_{y\in B} \sup_{x \in A} f(x, y)$$
を示せ.

答案.

$\inf_{y \in B} f(x, y) \leq (f(x, y)) \leq \sup_{x \in A} f(x, y)$である. 左辺で$\sup$,右辺で$\inf$を取ると,成立.

Exercise 4.

$\{A_n\}$は集合列で,$\lim_n A_n = A \Leftrightarrow \forall \omega \lim I_{A_n}(\omega)=I_A(\omega)$を示せ.

答案.

$$\lim A_n = A \Leftrightarrow A= \cup_{k\in\mathbb{N}} \cap_{n \geq k} A_n = \cap_{k \in \mathbb{N}} \cup_{n \geq k} A_n$$
が集合列の極限の定義である.
$\omega \in \cap_{k \in \mathbb{N}} \cup_{n \geq k} A_n \Leftrightarrow [\exists N \text{ s.t. } n \geq N \Rightarrow \omega \in A_n ]$だから,問の右の矢印が成立.
ﾋﾞｰﾝもうだめ

Exercise 5. (The union bound)

$(\Omega, \mathcal{F})$はmeasurable spaceとする. $\{A_i\}\subset \mathcal{F}$は必ずしも互いに素でない集合列とする.
$$P(\cup_{i=1}^\infty A_i) \leq \sum_{i=1}^\infty P(A_i))$$
を示せ.

答案.

$B_1=A_1, B_i = A_i \backslash \cup_{j=1}^{n-1} A_i$とすると$\cup A_i = \cup B_i$で,$\{B_i\}$は互いに素,完全加法性から
$$P(\cup B_i) = \sum_{i} P(B_i)$$
だが,任意の$i$に$P(A_i) \geq P(B_i)$.以上より$\sum P(A_i) \geq P(\cup A_i) = P(\cup B_i) =\sum P(B_i)$

Exercise 6.

$\Omega = \mathbb{N}$とする. $\mathcal{F}_0$を,$\Omega \backslash A$か$A$の少なくとも一方が有限集合である$A$の集合とする. また,任意の$A \in \mathcal{F}_0$に,$A$が有限なら$P(A)=0$,$A^C$が有限なら$P(A)=1$とする.このとき,
(a) $\mathcal{F}_0$はfieldだが$\sigma$-fieldでないことを示せ.
(b) $P$は$\mathcal{F}_0$で有限加法性をもつことを示せ.
(c) $P$は$\mathcal{F}_0$で可算加法性を持たないことを示せ.
(d) $A_i \in \mathcal{F}_0, \cap_{i=1}^\infty A_i =\phi$, $\lim P(A_i)\neq 0$なる減少列$A_i$を構成せよ.

答案.

(a) $A_i = \{2, 4, ..., 2i\}$とする. $A=\cup_{i\geq 1} A_i=2\mathbb{N} = \{2i|i \in \mathbb{N}\}$とすると, $A, A^C$はともに無限集合で,$A \notin \mathcal{F}_0$よって$\sigma$-fieldでない.
また,$|\phi|=0$から$\phi \in \mathcal{F}_0$であり,明らかに$\mathcal{F}_0$は補集合に閉じている.さらに$A_1, A_2 \in \mathcal{F}_0$について,$|A_1|< \infty,|A_2|=\infty$ならば$|A_2^C|< \infty$であって, $A_2 \subset A_1 \cup A_2$だから$|(A_1\cup A_2)^C| < \infty$だから$A_1 \cup A_2 \in \mathcal{F}_0$. $A_1,A_2$の要素数の関係性が今示したものでないときは$A_1 \cup A_2 \in \mathcal{F}_0$なのは明らか.
(b),(c)　略
(d) $A_i = \{i,i+1, i+2, ...\}$とすると,$\cap_i\{A_i\}=\phi, P(A_i)=1 \rightarrow 1$

MIT OCW, Machine Learning 05日目 線形回帰

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 5. Linear Regression, Active Learning

regression (回帰)とは,exampleに対して,labelではなく連続なresponse(観測値)を推測することであって,ここでは実数とする. またここではlinear regression modelのみを扱うが,これは簡単にlinearでないmodelに拡張できる(次章).

$\mathbf{x} \mapsto E[y|\mathbf{x}]=\theta^T \mathbf{x}+\theta_0$という写像がlinear regression modelであって,つまりdecision boundaryの直線が推測値になる. また,推測値の周りの観測値の分布が問題となるが,ここではresponseを期待値として,$\mathbf{x}$に依存しない分散$\sigma^2$の正規分布を使う. PDFは
$$N(y; \mu, \sigma^2) = \frac{1}{\sqrt{2\pi \sigma^2}} \exp \left(-\frac{1}{2\sigma^2}(y-\mu)^2 \right)$$
ここで,$\mu= \theta^T \mathbf{x} + \theta_0$だから,
$$P(y|\mathbf{x}, \theta, \theta_0) = N(y; \theta^T\mathbf{x}+\theta_0, \sigma^2)$$
となる.
training data $\{(\mathbf{x}_1, y_1), ..., (\mathbf{x}_n, y_n)\}$について,conditional likelihoodを最大化することで最適なパラメータ$\theta, \theta_0, \sigma^2$を見つける.
$$L(\theta, \theta_0, \sigma^2) = \prod_{t=1}^n \frac{1}{\sqrt{2\pi \sigma^2}} \exp \left( - \frac{1}{2\sigma^2} (y_t - \theta^T \mathbf{x}_t -\theta_0)^2 \right)$$
がLikelihoodであって, またlogをとって,
$$\begin{aligned} l(\theta, \theta_0, \sigma^2) &= \sum_{t=1}^n \log \left[ -\frac{1}{2\sigma^2} (y_t-\theta^T \mathbf{x}_t -\theta_0)^2 \right] \\ &= \sum \left[ -\frac{1}{2}\log(2\pi) - \frac{1}{2} \log \sigma^2 - \frac{1}{2\sigma^2} (y_t - \theta^T \mathbf{x}_t - \theta_0^2) \right] \\ &= \text{const. } - \frac{n}{2}\log \sigma^2 - \frac{1}{2\sigma^2} \underline{\sum_{t=1}^n (y_t - \theta^T \mathbf{x}_t - \theta_0^2)}_{\text{MSE}} \end{aligned}$$
まずは$\sigma^2$に関係なく. mean squared error(MSE)
$$\sum_{t=1}^n (y_t - \theta^T \mathbf{x}_t - \theta_0)^2$$
を最大化する$\theta, \theta_0$をみつける.
これは行列
$\mathbf{X} = \left(\begin{array}{} \mathbf{x}_1^{(1)} & \mathbf{x}_1^{(2)} &\cdots & \mathbf{x}_1^{(d)} & 1 \\ \mathbf{x}_2^{(1)} & \mathbf{x}_2^{(2)} & \cdots & \mathbf{x}_2^{(d)} & 1 \\ \vdots \\ \mathbf{x}_n^{(1)} & \cdots & \cdots & \mathbf{x}_n^{(d)} & 1 \end{array} \right)$ ( $\mathbf{x}_t^{i}$はtraining data の$t$番目のexampleの第$i$次元とする)
と$\mathbf{y} = (y_1, ..., y_n)^T$を使うと,
$$\begin{aligned} \text{MSE } = \sum_{t=1}^n \left(y_t - \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right]^T \left[\begin{array}{} \mathbf{x}_t \\ 1 \end{array} \right] \right)^2 &= \sum \left( y_t - [\mathbf{x}_t^T, 1] \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right] \right)^2 \\ &= \left\| \left[\begin{array}{} y_1 \\ \vdots \\ y_n \end{array} \right] - \left[ \begin{array}{} \mathbf{x}_1^T, 1 \\ \vdots \\ \mathbf{x}_n^T, 1 \end{array} \right] \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right] \right\|^2 \\ &= \left\| \mathbf{y} - \mathbf{X}\left[\begin{array}{} \theta \\ \theta_0\end{array} \right] \right\|^2 \\ &= \mathbf{y}^T \mathbf{y} - 2 \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right]^T \mathbf{X}^T \mathbf{y} + \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right]^T \mathbf{X}^T \mathbf{X} \left[\begin{array}{} \theta \\ \theta_0 \end{array} \right] \end{aligned}$$
となる.これを最小化する解を$\hat{\theta}, \hat{\theta_0}$とすると,
$$\left[\begin{array}{} \hat{\theta} \\ \hat{\theta_0}\end{array} \right] = \mathbf{(X^T X)^{-1} X^T y} \ \ \ \ (14)$$
である. これが$\mathbf{y}$の関数と考えると線形であり,この性質は後で使う.
$\hat{\sigma^2}$は, $\hat{\theta}, \hat{\theta_0}$をによってMSEの最小値を与えられた後で,
$$\hat{\sigma^2} = \frac{1}{n} \sum (y_t - \hat{\theta}^T \mathbf{x}_t - \hat{\theta_0})^2$$
で決定できる.

Bias and Variance of the Parameter Estimates

$\mathbf{x}, y$が,未知のパラメータ$\theta^*, \theta_0^*, \sigma^*$の線形モデルに従っていて,(14)で計算した$\hat{\theta}, \hat{\theta_0}$がどれほど適切なのかを議論する. このとき$\hat{\theta}, \hat{\theta_0}$は$\theta^*, \theta_0^*$の推測と考えることが出来る.仮定より
$$y_t = \theta^{*T} \mathbf{x}_t + \theta^*_0 + \epsilon_t, \ \epsilon_t \sim N(0, \sigma^{*2})$$
が成り立つ.
$$\mathbf{y} = \mathbf{X} \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right] + \mathbf{e},\ \mathbf{e} = (\epsilon_1, ... , \epsilon_n)^T$$
と行列表示する.$E[\mathbf{e}]=0, E[\mathbf{ee^T}] = \sigma^{*2} \mathbf{I}$で,また$\mathbf{X}$と$\mathbf{e}$は独立である. (14)に代入して,
$$\begin{aligned} \left[ \begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right] &= (\mathbf{X^T X})^{-1} \mathbf{X}^T ( \mathbf{X} \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right] + \mathbf{e}) \\ &=(\mathbf{X^T X})^{-1} \mathbf{X}^T \mathbf{X} \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right] + (\mathbf{X^T X})^{-1} \mathbf{X}^T \mathbf{e} \\ &= \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right] + \mathbf{(X^TX)^{-1} X^T e} \end{aligned}$$
である. $E[\mathbf{e}] = \mathbf{0}$だから, 両辺の期待値を取れば,
$$E\left[ \left[ \begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right]\right] = \left[ \begin{array}{} \theta^* \\ \theta_0^* \end{array} \right]$$
である. このように,推測値の期待値が真の値に一致するとき, 推測はunbiased(不偏)であるという.
さらに,
$$\begin{aligned} cov[ \left[ \begin{array}{} \hat{\theta} \\ \hat{\theta_0} \end{array} \right] | \mathbf{X}] = \sigma^{*2} (\mathbf{X}^T \mathbf{X})^{-1} \end{aligned}$$
であって,つまり$\hat{\theta}, \hat{\theta_0}$は$\mathbf{X}$のノイズを受け継ぎ,そのノイズがどのような形をしているかは$\mathbf{X}$の関数として書ける.
さて,
$$\begin{aligned} E[\|\mathbf{z}-\mathbf{z}^*\|^2] &= E[ \|\mathbf{z}-E[\mathbf{z}] + E[\mathbf{z}] - \mathbf{z}^* \| ^2 \\ &=E[\|\mathbf{z}-E[\mathbf{z}]\|^2] + 2E[(\mathbf{z} - E[\mathbf{z}])^T](E[\mathbf{z}] - \mathbf{z}^*) + \|E[\mathbf{z}] - \mathbf{z}^*\|^2 \\ &= \underline{E[\|\mathbf{z}-E[\mathbf{z}]]\|^2}_{\text{variance}^2} + \underline{\|E[\mathbf{z}] - \mathbf{z}^*\|^2}_{\text{bias}^2} \end{aligned}$$
が任意の$\mathbf{z}$に $\mathbf{z}^*$を固定するたびに成り立つ. さらにvarianceは
$$\begin{aligned}E[\|\mathbf{z}-E[\mathbf{z}]\|^2] &= E[(\mathbf{z}-E[\mathbf{z}])^T (\mathbf{z} - E[\mathbf{z})] \\ &=E\left[ Tr [(\mathbf{z}-E[\mathbf{z}])][\mathbf{z}-E[\mathbf{z}]]^T \right] \\ &= Tr\left[ E\left[ (\mathbf{z}-E[\mathbf{z}])(\mathbf{z} -E[\mathbf{z}])^T \right]\right] \\ &= Tr[cov(\mathbf{z})] \end{aligned}$$

以上から, biasが$\mathbf{0}$であることを考えれば
$$\begin{aligned} E\left[ \left\| \left[\begin{array}{} \hat{\theta} \\ \hat{\theta_0}\end{array} \right]-\left[ \begin{array}{} \theta^* \\ \theta^*_0 \end{array} \right] \right\| |\mathbf{X} \right] &= \sigma^{*2} Tr[(\mathbf{X^TX})^{-1}] \end{aligned}$$
さらに,
$$\begin{aligned} \mathbf{X^TX} &= \sum_{t=1}^n \left[\begin{array}{} \mathbf{x}_t \\ 1 \end{array} \right] [\mathbf{x}^T_t, 1] \\ &= n \cdot \frac{1}{n}\sum_{t=1}^n \left[\begin{array}{} \mathbf{x}_t \\ 1 \end{array} \right] [\mathbf{x}^T_t, 1] \\ &\sim n \cdot E_{\mathbf{x} \sim P} \left[ \left[\begin{array}{} \mathbf{x} \\ 1 \end{array} \right] [\mathbf{x}^T, 1]\right] = n \cdot \mathbf{C} \\ (\mathbf{C} : &\text{もとの分布によって決まる定数行列}) \end{aligned}$$
だから,
$$E\left[ \left\| \left[\begin{array}{} \hat{\theta} \\ \hat{\theta_0}\end{array} \right]-\left[ \begin{array}{} \theta^* \\ \theta^*_0 \end{array} \right] \right\| |\mathbf{X} \right] \sim \frac{\sigma^{*2}}{n} \cdot Tr[\mathbf{C}^{-1}]$$
すなわち,$n$が十分大きいとき,推定したパラメータの分散は$\frac{\sigma^{*2}}{n} \cdot Tr[\mathbf{C}^{-1}]$である.