PRML自習ノート - chapter 11 -
Exercise (11.1) - (11.10)
Exercise (11.1)
便宜上，$${\mathbf{z}^{(l)}\sim p_l(\mathbf{z}^{(l)}), p_l(\mathbf{z})=p(\mathbf{z})\ {\rm for\ all}\ l}$$とする。
このとき，
$$
\begin{align*}
\mathbb{E}\left[\hat{f}\right]&=\frac{1}{L}\sum_{l=1}^L\mathbb{E}\left[f(\mathbf{z}^{(l)})\right]\\
&=\frac{1}{L}\sum_{l=1}^L\prod_{l'=1}^L\int{\rm d}\mathbf{z}^{(l')}p_{l'}(\mathbf{z}^{(l')})f(\mathbf{z}^{(l)})\\
&=\frac{1}{L}\sum_{l=1}^L\int{\rm d}\mathbf{z}^{(l)}p_{l}(\mathbf{z}^{(l)})f(\mathbf{z}^{(l)})\prod_{l'\neq l}\int{\rm d}\mathbf{z}^{(l')}p_{l'}(\mathbf{z}^{(l')})\\
&=\frac{1}{L}\sum_{l=1}^L\int{\rm d}\mathbf{z}^{(l)}p_{l}(\mathbf{z}^{(l)})f(\mathbf{z}^{(l)})\\
&=\frac{1}{L}\sum_{l=1}^L\int{\rm d}\mathbf{z}p(\mathbf{z})f(\mathbf{z})\\
&=\frac{1}{L}L\mathbb{E}\left[f\right]\\
&=\mathbb{E}\left[f\right]\\
\end{align*}
$$
$$
\begin{align*}
\mathbb{E}\left[\hat{f}^2\right]&=\frac{1}{L^2}\sum_{l=1}^L\sum_{l'=1}^L\mathbb{E}\left[f(\mathbf{z}^{(l)})f(\mathbf{z}^{(l')})\right]\\
&=\frac{1}{L^2}\sum_{l=1}^L\sum_{l'=1}^L\prod_{l''=1}^L\int{\rm d}\mathbf{z}^{(l'')}p_{l''}(\mathbf{z}^{(l'')})f(\mathbf{z}^{(l)})f(\mathbf{z}^{(l')})\\
&=\frac{1}{L^2}\sum_{l=1}^L\sum_{l'=1}^L\left(\mathbb{E}[f^2]\delta_{ll'}+\left(\mathbb{E}[f]\right)^2(1-\delta_{ll'})\right)\\
&=\frac{1}{L}\mathbb{E}[f^2]+\left(\mathbb{E}[f]\right)^2-\frac{1}{L}\left(\mathbb{E}[f]\right)^2\\
&=\frac{1}{L}{\rm var}\left[f\right]+\left(\mathbb{E}\left[\hat{f}\right]\right)^2\\
\therefore {\rm var}\left[\hat{f}\right]&=\mathbb{E}\left[\hat{f}^2\right]-\left(\mathbb{E}\left[\hat{f}\right]\right)^2\\
&=\frac{1}{L}{\rm var}\left[f\right]
\end{align*}
$$
Exercise (11.2)
$$
\begin{align*}
z&=h(y)\\
&=\int_{-\infty}^y{\rm d}\hat{y}p(\hat{y})\\
p(z)&=1
\end{align*}
$$
より，
$$
\begin{align*}
\left|\frac{{\rm d}z}{{\rm d}y}\right|&=p(y)\\
p(z)\left|\frac{{\rm d}z}{{\rm d}y}\right|&=p(y)
\end{align*}
$$
が得られる。
つまり，$${y}$$は$${p(y)}$$からのサンプリングデータを表す。
Exercise (11.3)
$${y=\tan\theta}$$と変数変換すると，不定積分$${h(y)}$$は
$$
\begin{align*}
h(y)&=\int{\rm d}y\frac{1}{1+y^2}\\
&=\int\frac{{\rm d}\theta}{\cos^2\theta}\frac{1}{1+\tan^2\theta}\\
&=\int\frac{{\rm d}\theta}{\cos^2\theta}\cos^2\theta\\
&=\int{\rm d}\theta\\
&=\theta+C\\
&=\arctan y +C
\end{align*}
$$
となる。ここで、$${C}$$は$${y}$$に依存しない定数である。
以上より，
$$
\begin{align*}
y&=\tan\left(h(y)-C\right)
&=\tan\left(z-C\right)
\end{align*}
$$
となる。
Exercise (11.4)
$$
\begin{align*}
\frac{\partial y_1}{\partial z_1}&=\frac{\partial }{\partial z_1}\left\{-\frac{z_1}{r}(-4\ln r)^{1/2}\right\}\\
&=-\frac{(-4\ln r)^{1/2}}{r}+\frac{z_1^2(-4\ln r)^{1/2}}{r^3}+\frac{2z_1^2}{r^3(-4\ln r)^{1/2}}\\
\frac{\partial y_1}{\partial z_2}&=\frac{\partial }{\partial z_2}\left\{-\frac{z_1}{r}(-4\ln r)^{1/2}\right\}\\
&=\frac{z_1z_2}{r^3}\left((-4\ln r)^{1/2}+\frac{2}{(-4\ln r)^{1/2}}\right)\\
\frac{\partial y_2}{\partial z_1}&=\frac{\partial }{\partial z_1}\left\{-\frac{z_2}{r}(-4\ln r)^{1/2}\right\}\\
&=\frac{z_1z_2}{r^3}\left((-4\ln r)^{1/2}+\frac{2}{(-4\ln r)^{1/2}}\right)\\
\frac{\partial y_2}{\partial z_2}&=\frac{\partial }{\partial z_2}\left\{-\frac{z_2}{r}(-4\ln r)^{1/2}\right\}\\
&=-\frac{(-4\ln r)^{1/2}}{r}+\frac{z_2^2(-4\ln r)^{1/2}}{r^3}+\frac{2z_2^2}{r^3(-4\ln r)^{1/2}}\\
\end{align*}
$$
より，
$$
\begin{align*}
\left|\frac{\partial(y_1,y_2)}{\partial(z_1,z_2)}\right|&=\left|\frac{\partial y_1}{\partial z_1}\frac{\partial y_2}{\partial z_2}-\frac{\partial y_1}{\partial z_2}\frac{\partial y_2}{\partial z_1}\right|\\
&=\frac{2}{r^2}\\
&=2\exp\left(\frac{y_1^2+y_2^2}{2}\right)\\
\frac{1}{\pi}=p(z_1,z_2)&=\left|\frac{\partial(y_1,y_2)}{\partial(z_1,z_2)}\right|p(y_1,y_2)\\
&=2\exp\left(\frac{y_1^2+y_2^2}{2}\right)p(y_1,y_2)\\
\therefore p(y_1,y_2)&=\frac{1}{2\pi}\exp\left(-\frac{y_1^2+y_2^2}{2}\right)=\left[\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y_1^2}{2}\right)\right]\left[\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y_2^2}{2}\right)\right]
\end{align*}
$$
Exercise (11.5)
$${p(\mathbf{z})=\mathcal{N}(\mathbf{z}|\mathbf{0},\mathbf{I}),\ \mathbf{y}-\boldsymbol\mu=\mathbf{L}\mathbf{z},\ \boldsymbol\Sigma=\mathbf{L}\mathbf{L}^{\rm T}}$$のとき，
$$
\begin{align*}
p(\mathbf{z})&=\left(\frac{1}{2\pi}\right)^{D/2}\exp\left(-\frac{1}{2}\mathbf{z}^{\rm T}\mathbf{z}\right)\\
&=\left(\frac{1}{2\pi}\right)^{D/2}\exp\left(-\frac{1}{2}\left\{\mathbf{L}^{-1}(\mathbf{y}-\boldsymbol\mu)\right\}^{\rm T}\mathbf{L}^{-1}(\mathbf{y}-\boldsymbol\mu)\right)\\
&=\left(\frac{1}{2\pi}\right)^{D/2}\exp\left(-\frac{1}{2}(\mathbf{y}-\boldsymbol\mu)^{\rm T}(\mathbf{L}^{\rm T})^{-1}\mathbf{L}^{-1}(\mathbf{y}-\boldsymbol\mu)\right)\\
&=\left(\frac{1}{2\pi}\right)^{D/2}\exp\left(-\frac{1}{2}(\mathbf{y}-\boldsymbol\mu)^{\rm T}(\mathbf{L}\mathbf{L}^{\rm T})^{-1}(\mathbf{y}-\boldsymbol\mu)\right)\\
&=\left(\frac{1}{2\pi}\right)^{D/2}\exp\left(-\frac{1}{2}(\mathbf{y}-\boldsymbol\mu)^{\rm T}\boldsymbol\Sigma^{-1}(\mathbf{y}-\boldsymbol\mu)\right)\\
\left|\frac{\partial(y_1,y_2,\cdots,y_D)}{\partial(z_1,z_2,\cdots,z_D)}\right|&=|\mathbf{L}|\\
&=|\mathbf{L}|^{1/2}|\mathbf{L}^{\rm T}|^{1/2}\\
&=|\mathbf{L}\mathbf{L}^{\rm T}|^{1/2}\\
&=|\boldsymbol\Sigma|^{1/2}\\
\therefore p(\mathbf{y})&=\left|\frac{\partial(y_1,y_2,\cdots,y_D)}{\partial(z_1,z_2,\cdots,z_D)}\right|^{-1}p(\mathbf{z})\\
&=|\boldsymbol\Sigma|^{-1/2}\left(\frac{1}{2\pi}\right)^{D/2}\exp\left(-\frac{1}{2}(\mathbf{y}-\boldsymbol\mu)^{\rm T}\boldsymbol\Sigma^{-1}(\mathbf{y}-\boldsymbol\mu)\right)\\
&=\mathcal{N}(\mathbf{y}|\boldsymbol\mu,\boldsymbol\Sigma)
\end{align*}
$$
Exercise (11.6)
$${[0,kq(\mathbf{z})]}$$の範囲でランダムに発生した値のうち，$${[0,\tilde{p}(\mathbf{z})]}$$に含まれるものがacceptされるため，acceptされる確率$${p({\rm accept}|\mathbf{z})}$$は$${\frac{\tilde{p}(\mathbf{z})}{kq(\mathbf{z})}}$$である。
$$
\begin{align*}
p({\rm accept})&=\frac{1}{k}\int{\rm d}\mathbf{z}\tilde{p}(\mathbf{z})\\
&=\frac{Z_p}{k}\\
\therefore p(\mathbf{z})&=\frac{1}{Z_p}\tilde{p}(\mathbf{z})\\
&=\frac{1}{p({\rm accept})}\frac{\tilde{p}(\mathbf{z})}{k}\\
&=\frac{p({\rm accept}|\mathbf{z})q(\mathbf{z})}{p({\rm accept})}
\end{align*}
$$
Exercise (11.7)
$${z=b\tan y+c}$$のとき，
$$
\begin{align*}
\frac{{\rm d}z}{{\rm d}z}&=\frac{{\rm d}}{{\rm d}z}(b\tan y+c)\\
1&=\frac{b}{\cos^2 y}\frac{{\rm d}y}{{\rm d}z}\\
&=b(1+\tan^2 y)\frac{{\rm d}y}{{\rm d}z}\\
&=b(1+(z-c)^2/b^2)\frac{{\rm d}y}{{\rm d}z}\\
\therefore q(z)&=\left|\frac{{\rm d}y}{{\rm d}z}\right|q(y)\\
&=\left|\frac{{\rm d}y}{{\rm d}z}\right|\\
&=\frac{b^{-1}}{1+(z-c)^2/b^2}
\end{align*}
$$
Exercise (11.8)
$$
\begin{align*}
\lambda_i&=-\left.\frac{{\rm d}\ln p(z)}{{\rm d}z}\right|_{z=z_{i-1}}\\
&=-\frac{1}{p(z_{i-1})}\left.\frac{{\rm d}p(z)}{{\rm d}z}\right|_{z=z_{i-1}}\\
\lim_{z\rightarrow z_{i-1}}q(z)&=\ln(k_i\lambda_i)\\
&=\ln(p(z_{i-1}))\\
\therefore k_i&=\frac{p(z_{i-1})}{\lambda_i}\\
&=-p(z_{i-1})^{2}\left(\left.\frac{{\rm d}p(z)}{{\rm d}z}\right|_{z=z_{i-1}}\right)^{-1}
\end{align*}
$$
Exercise (11.9)
各サンプリングで得られる$${z}$$の値が特定の$${(z_{i-1},z_i]}$$の範囲に限定される場合を考える。
このとき，$${[0,1]}$$の範囲で等確率で$${x}$$が生成されるとすると($${q(x)=1}$$)，
$$
\begin{align*}
q(z)&=\left(\int_{z_{i-1}}^{z_i}{\rm d}zq(z)\right)\left|\frac{{\rm d}x}{{\rm d}z} \right|q(x)\\
&=\left(\int_{z_{i-1}}^{z_i}{\rm d}zq(z)\right)\left|\frac{{\rm d}x}{{\rm d}z} \right|\\
x&=\left(\int_{z_{i-1}}^{z_i}{\rm d}zq(z)\right)^{-1}\int_{z_{i-1}}^{z}{\rm d}\hat{z}q(\hat{z})\\
&=\frac{1-{\rm e}^{-\lambda_i(z-z_{i-1})}}{1-{\rm e}^{-\lambda_i(z_i-z_{i-1})}}\\
\therefore z&=z_{i-1}-\frac{1}{\lambda_i}\ln\left(1-\left\{1-{\rm e}^{-\lambda_i(z_i-z_{i-1})}\right\}x\right)
\end{align*}
$$
となる。
$${z}$$のサンプリングのアルゴリズムの以下のようになる。
$$
\begin{align*}
1.&\ \ サンプリング対象となる区間((z_{i-1},z_i])を選択\\
2.&\ \ p(x)からxをサンプリング\\
3.&\ \ z=z_{i-1}-\frac{1}{\lambda_i}\ln\left(1-\left\{1-{\rm e}^{-\lambda_i(z_i-z_{i-1})}\right\}x\right)を用いてxをzに変換\\
\end{align*}
$$
Exercise (11.10)
$$
\begin{align*}
\mathbb{E}\left[\left(z^{(\tau)}\right)^2\right]&=\sum_{z^{(\tau)}}\left(z^{(\tau)}\right)^2p\left(z^{(\tau)}\right)\\
&=\sum_{z^{(\tau)}}\left(z^{(\tau)}\right)^2p\left(z^{(\tau)}\right)\\
&=\sum_{z^{(\tau)}}\left(z^{(\tau)}\right)^2p\left(z^{(\tau)}\left|z^{(\tau-1)}\right.\right)p\left(z^{(\tau-1)}\right)\\
&=\sum_{z^{(\tau-1)}}\left\{\left(z^{(\tau-1)}-1\right)^2p\left(z^{(\tau)}=z^{(\tau-1)}-1\left|z^{(\tau-1)}\right.\right)+\left(z^{(\tau-1)}\right)^2p\left(z^{(\tau)}=z^{(\tau-1)}\left|z^{(\tau-1)}\right.\right)+\left(z^{(\tau-1)}+1\right)^2p\left(z^{(\tau)}=z^{(\tau-1)}+1\left|z^{(\tau-1)}\right.\right)\right\}p\left(z^{(\tau-1)}\right)\\
&=\sum_{z^{(\tau-1)}}\left\{\frac{1}{4}\left(z^{(\tau-1)}-1\right)^2+\frac{1}{2}\left(z^{(\tau-1)}\right)^2+\frac{1}{4}\left(z^{(\tau-1)}+1\right)^2\right\}p\left(z^{(\tau-1)}\right)\\
&=\sum_{z^{(\tau-1)}}\left\{\left(z^{(\tau-1)}-1\right)^2+\frac{1}{2}\right\}p\left(z^{(\tau-1)}\right)\\
&=\mathbb{E}\left[\left(z^{(\tau-1)}\right)^2\right]+\frac{1}{2}\\
&=\mathbb{E}\left[\left(z^{(\tau-2)}\right)^2\right]+\frac{2}{2}\\
&\vdots\\
&=\mathbb{E}\left[\left(z^{(0)}\right)^2\right]+\frac{\tau}{2}\\
&=\frac{\tau}{2}
\end{align*}
$$
Exercise (11.11) - (11.17)
Exercise (11.11)
Gibbs samplingにて$${\mathbf{z}=(z_k,\mathbf{z}_{\backslash k})\rightarrow \mathbf{z}^*=(z_k^*,\mathbf{z}_{\backslash k})}$$に更新する場合，
$$
\begin{align*}
p(\mathbf{z})T(\mathbf{z},\mathbf{z}^*)&=p(z_k,\mathbf{z}_{\backslash k})p(z_k^*|\mathbf{z}_{\backslash k})\\
&=p(z_k,\mathbf{z}_{\backslash k})\frac{p(z_k^*,\mathbf{z}_{\backslash k})}{p(\mathbf{z}_{\backslash k})}\\
&=p(z_k^*,\mathbf{z}_{\backslash k})\frac{p(z_k,\mathbf{z}_{\backslash k})}{p(\mathbf{z}_{\backslash k})}\\
&=p(\mathbf{z}^*)p(z_k|\mathbf{z}_{\backslash k})\\
&=p(\mathbf{z}^*)T(\mathbf{z}^*,\mathbf{z})
\end{align*}
$$
となり，詳細つり合い条件を満たす。
Exercise (11.12)
サンプリング例を下図に示す。
このように片方の局在部分からスタートすると，もう片方の局在部分はサンプリングされない状態となるためエルゴード性はない。
Exercise (11.13)
$$
\begin{align*}
p(\mu|x,\tau)&=\frac{p(x,\mu,\tau)}{p(x,\tau)}\\
&=\frac{p(x,\mu,\tau)}{\int{\rm d}\mu p(x,\mu,\tau)}\\
&=\frac{p(x|\mu,\tau)p(\mu,\tau)}{\int{\rm d}\mu p(x|\mu,\tau)p(\mu,\tau)}\\
&=\frac{p(x|\mu,\tau)p(\mu)p(\tau)}{\int{\rm d}\mu p(x|\mu,\tau)p(\mu)p(\tau)}\\
&=\frac{p(x|\mu,\tau)p(\mu)}{\int{\rm d}\mu p(x|\mu,\tau)p(\mu)}\\
&=\frac{\mathcal{N}(x|\mu,\tau^{-1})\mathcal{N}(\mu|\mu_0,s_0)}{\int{\rm d}\mu \mathcal{N}(x|\mu,\tau^{-1})\mathcal{N}(\mu|\mu_0,s_0)}\\
&=\frac{\mathcal{N}(x|\mu,\tau^{-1})\mathcal{N}(\mu|\mu_0,s_0)}{\mathcal{N}(x|\mu_0,s_0+\tau^{-1})}
\end{align*}
$$
$$
\begin{align*}
p(\tau|x,\mu)&=\frac{p(x,\mu,\tau)}{p(x,\mu)}\\
&=\frac{p(x,\mu,\tau)}{\int{\rm d}\tau p(x,\mu,\tau)}\\
&=\frac{p(x|\mu,\tau)p(\mu,\tau)}{\int{\rm d}\tau p(x|\mu,\tau)p(\mu,\tau)}\\
&=\frac{p(x|\mu,\tau)p(\mu)p(\tau)}{\int{\rm d}\tau p(x|\mu,\tau)p(\mu)p(\tau)}\\
&=\frac{p(x|\mu,\tau)p(\tau)}{\int{\rm d}\tau p(x|\mu,\tau)p(\tau)}\\
&=\frac{\mathcal{N}(x|\mu,\tau^{-1}){\rm Gam}(\tau|a,b)}{\int{\rm d}\tau \mathcal{N}(x|\mu,\tau^{-1}){\rm Gam}(\tau|a,b)}\\
&=\frac{\mathcal{N}(x|\mu,\tau^{-1}){\rm Gam}(\tau|a,b)}{{\rm St}(x|\mu,a/b,2a)}\\
\end{align*}
$$
Exercise (11.14)
$$
\begin{align*}
\mathbb{E}\left[z_i'\right]&=\mu_i+\alpha\left(\mathbb{E}\left[z_i\right]-\mu_i\right)+\sigma_i(1-\alpha^2)^{1/2}\mathbb{E}[\nu]\\
&=\mu_i+\alpha\left(\mu_i-\mu_i\right)\\
&=\mu_i\\
{\rm var}\left[z_i'\right]&=\mathbb{E}\left[\left(z_i'-\mathbb{E}\left[z_i'\right]\right)^2\right]\\
&=\mathbb{E}\left[\left(z_i'-\mu_i\right)^2\right]\\
&=\mathbb{E}\left[\left(\alpha(z_i'-\mu_i)+\sigma_i(1-\alpha^2)^{1/2}\nu\right)^2\right]\\
&=\alpha^2\mathbb{E}\left[(z_i-\mu_i)^2\right]+2\alpha\sigma_i(1-\alpha^2)^{1/2}\mathbb{E}\left[(z_i-\mu_i)\right]\mathbb{E}[\nu]+\sigma_i^2(1-\alpha^2)\mathbb{E}\left[\nu^2\right]\\
&=\alpha^2\sigma_i^2+\sigma_i^2(1-\alpha^2)\\
&=\sigma_i^2
\end{align*}
$$
Exercise (11.15)
$$
\begin{align*}
\frac{{\rm d}z_i}{{\rm d}\tau}&=\frac{\partial}{\partial r_i}\left\{H(\mathbf{z},\mathbf{r})\right\}\\
&=\frac{\partial}{\partial r_i}\left\{E(\mathbf{z})+K(\mathbf{r})\right\}\\
&=\frac{\partial}{\partial r_i}K(\mathbf{r})\\
&=\frac{1}{2}\sum_j\frac{\partial}{\partial r_i}r_j^2\\
&=\sum_jr_j\delta_{ij}\\
&=r_i\\
\frac{{\rm d}r_i}{{\rm d}\tau}&=-\frac{\partial}{\partial z_i}\left\{H(\mathbf{z},\mathbf{r})\right\}\\
&=-\frac{\partial}{\partial z_i}\left\{E(\mathbf{z})+K(\mathbf{r})\right\}\\
&=-\frac{\partial}{\partial z_i}E(\mathbf{z})
\end{align*}
$$
Exercise (11.16)
$$
\begin{align*}
p(\mathbf{r}|\mathbf{z})&=\frac{p(\mathbf{z},\mathbf{r})}{p(\mathbf{z})}\\
&=\frac{Z_p\exp\left(-E(\mathbf{z})-K(\mathbf{r})\right)}{Z_H\exp\left(-E(\mathbf{z})\right)}\\
&=\frac{Z_p}{Z_H}\exp\left(-K(\mathbf{r})\right)\\
&=\frac{Z_p}{Z_H}\exp\left(-\frac{1}{2}\|\mathbf{r}\|^2\right)\\
\end{align*}
$$
以上より，題意は示された。
Exercise (11.17)
$$
\begin{align*}
\frac{1}{Z_H}\exp(-H(\mathcal{R}))\delta V\frac{1}{2}\min\left\{1,\exp\left(-H(\mathcal{R}')+H(\mathcal{R})\right)\right\}&=\frac{1}{Z_H}\delta V\frac{1}{2}\min\left\{\exp(-H(\mathcal{R})),\exp\left(-H(\mathcal{R}')\right)\right\}\\
&=\frac{1}{Z_H}\delta V\frac{1}{2}\min\left\{\exp(-H(\mathcal{R}')),\exp\left(-H(\mathcal{R})\right)\right\}\\
&=\frac{1}{Z_H}\exp(-H(\mathcal{R}'))\delta V\frac{1}{2}\min\left\{1,\exp\left(-H(\mathcal{R})+H(\mathcal{R}')\right)\right\}
\end{align*}
$$
以上より，題意は示された。