# 情報論的機械学習/情報論的学習理論 課題

- 板書
https://hackmd.io/@MOVXPNekTwaXcZi1E6bx9w/SkdJjFYuB
[dropbox](https://www.dropbox.com/sh/ju6dm6y4cbgte9z/AACMp-wOXsKZz9TwMhG18KGxa?dl=0)
[google drive](https://drive.google.com/drive/folders/1dDiSTmb1bTJNaw_EvGDbdvfjJMHV5Edv)
- 書籍
- 73B1のkogaの席の上にある
- 提出期限、提出場所
- 2/4(火)
- 6号館1階入って左(?)の山西先生のレポートボックス
- 課題
- 10問あるうちの2問を解く
<details>
<summary> 課題の写真 </summary>

- 
- 
- 

</details>

$\newcommand{\x}{\mathcal{X}}$
$\newcommand{\bx}{\mathbf{x}}$
$\newcommand{\y}{\mathcal{Y}}$
## 課題1

### 問題
定義域 $\x = {\{0, 1\}}^d$, 値域 $\y = \{0, 1\}$
$\y$の下で、与えられた$\mathbf{x} =(x_1, \cdots, x_d) \in \x$に対する確率的決定リストを考える
確率的決定リストは以下のように表される
\begin{align}
(f_1(\bx), \theta_1)(f_2(\bx), \theta_2)\cdots(f_m(\bx), \theta_m) --- (1)
\end{align}
ここで、$f_i(\bx)$はブール関数であり、$\x \rightarrow \{0, 1\}$(訳者注 間違いか?) かつ $0 \leq \theta_i \leq 1~(i = 1, \cdots, m)$である
式(1)の意味は、与えられた$x$に対して$f_i(x) = 1$なる最小のインデックス$i$に対して$\theta_i$の確率で$y = 1$がassignされ、$1 - \theta_i$の確率で$y = 0$がassignされる。
つまり、確率的決定リストというのは実数ベクトル$\theta = (\theta_1, \cdots, \theta_m)$とモデル$M = \{f_1, \cdots, f_m\}$によって定められる条件付確率分布$p(y|x; \theta, M)$を定義するものである
ここで、$f_i$が$k (\leq n)$個以内の要素の積とする。(例えば、$k = 3$なら$f(x) = x_1 x_2 x_3$や$f(x) = x_3 x_6$など)
この分布を$k$-確率的決定リストと呼ぶ
このとき、$n$個の互いに独立なデータ$(\mathbf{x_1}, y_1), \cdots (\mathbf{x_n}, y_n)$を入力、[MDL](http://ibisforest.org/index.php?MDL)の方式によって得られるk-確率的決定リストを出力とした学習アルゴリズムを記せ

### 参考資料
[論文](https://link.springer.com/content/pdf/10.1007/BF00992676.pdf)
[論文: Text classification using ESC-based stochastic decision lists](https://dl.acm.org/doi/pdf/10.1145/319950.319966?download=true)([論文元サイト](https://dl.acm.org/doi/10.1145/319950.319966))
[Google Books](https://books.google.co.jp/books?id=XfVDsu3nER8C&pg=PA16&lpg=PA16&dq=%E7%A2%BA%E7%8E%87%E7%9A%84%E6%B1%BA%E5%AE%9A%E3%83%AA%E3%82%B9%E3%83%88&source=bl&ots=m9rJAZQnvc&sig=ACfU3U066mn-bkPKHf7TmncmboSGVyqEpQ&hl=en&sa=X&ved=2ahUKEwjZqJO0roLnAhVF7GEKHdu2CV0Q6AEwCHoECC0QAQ#v=onepage&q=%E7%A2%BA%E7%8E%87%E7%9A%84%E6%B1%BA%E5%AE%9A%E3%83%AA%E3%82%B9%E3%83%88&f=false)
### 解答(服部)
\subsection{問題}
定義域 $\x = {\{0, 1\}}^d$, 値域 $\y = \{0, 1\}$

$\y$の下で、与えられた$\mathbf{x} =(x_1, \cdots, x_d) \in \x$に対する確率的決定リストを考える． \\
確率的決定リストは以下のように表される．
\begin{align}
(f_1(\bx), \theta_1)(f_2(\bx), \theta_2)\cdots(f_m(\bx), \theta_m) --- (1)
\end{align}
ここで、$f_i(\bx)$はブール関数であり、$\x \rightarrow \{0, 1\}$(?) かつ $0 \leq \theta_i \leq 1~(i = 1, \cdots, m)$である． \\
式(1)の意味は、与えられた$x$に対して$f_i(x) = 1$なる最小のインデックス$i$に対して$\theta_i$の確率で$y = 1$がassignされ、$1 - \theta_i$の確率で$y = 0$がassignされる． \\
つまり、確率的決定リストというのは実数ベクトル$\theta = (\theta_1, \cdots, \theta_m)$とモデル$M = \{f_1, \cdots, f_m\}$によって定められる条件付確率分布$p(y|x; \theta, M)$を定義するものである． \\
ここで、$f_i$が$k (\leq n)$個以内の要素の積とする(例えば、$k = 3$なら$f(x) = x_1 x_2 x_3$や$f(x) = x_3 x_6$など)． \\
この分布を$k$-確率的決定リストと呼ぶ． \\
このとき、$n$個の互いに独立なデータ$(\mathbf{x_1}, y_1), \cdots (\mathbf{x_n}, y_n)$を入力、MDLの方式によって得られるk-確率的決定リストを出力とした学習アルゴリズムを記せ．

\subsection{解答}
以下の解答は\cite{Yamanishi1992}を大いに参考にした． \\
確率的決定リストのモデルを選択することを考える． \\
$\bx^n = (\bx_1, \cdots \bx_n)$，$y^n = (y_1, \cdots y_n)$とする． \\
以下のアルゴリズムで選択する． \\

パラメータ$\lambda$と符号長を求める関数$l(y^n | \bx^n : \theta \prec M)$を決める． \\
$l$の例として，$l(y^n || \bx^n : \theta \prec M) = \log P(y^n | \bx^n : \theta \prec M)$のような，条件付き確率分布$P$を用いたものが考えられ，これはKraftの不等式を満たす． \\
確率的決定リストのモデルの候補の集合$\Gamma_k^m$を用意する．方法としては，PCでのランダム生成，手動での生成などが考えられる． \\
$\Gamma_k^m$に属する$M$すべてについて，$l$を最小化する$\theta = \bar{\theta}$を計算する． \\
求まった$\bar{\theta}$に対して，$l(y^n | \bx^n : \bar{\theta} \prec M) + \lambda(\bar{\theta} | M) + l(M)$を計算する． \\
$\Gamma_k^m$に属する$M$のうち，上記の値を最小にするモデルの中からランダムに1つのモデルを選択する．

[論文](https://link.springer.com/content/pdf/10.1007/BF00992676.pdf)より引用
<details>
<summary> 引用部分 </summary>

Below, we more precisely describe the MDL algorithm for learning $G^k_{DL}(n)$, which we denote as $\mathcal{A}_{MDL}$.
$\mathcal{A}_{MDL}$ uses a hypothesis space $\mathcal{H}_N(G^k_{DL}(n))$, which depends on sample size $N$. Fix an adjustment parameter $\lambda$ and a code-length function $l : \Gamma_k^n \rightarrow \mathbf{R}^{+} \cup \{0\}$ such that $\Sigma_{M\in \Gamma_k^n} 2^{-l(M)} \leq 1$.
1 ° $\mathcal{A}_{MDL}$ draws $N$ independent examples$D^N$.
2 ° For each $M \in \Gamma_k^n$, $\mathcal{A}_{MDL}$ calculates $\bar{\theta} = \mathrm{argmin}_{\theta \in \Theta_N(M)} l(y^N | X^N : \theta \prec M)$ and
$l_{\lambda}(y^N : \bar{\theta} \prec M | x^N) \overset{def}{=}l(y^N|x^N : \bar{\theta} \prec M) + \lambda (l(\bar{\theta} | M) + l(M))$
3° $\mathcal{A}_{MDL}$ chooses one countable model $\hat{M} \in \Gamma_k^n$ which attains the minimum of $l_{\lambda}(y^N|x^N:\theta \prec M)$ If there exist more than one $M$ that attain the minimum, $\mathcal{A}_{MDL}$ choose $M$ from among them such that $l(\bar{\theta}|\hat{M}) + l(\hat{M})$ is shortest.
4° $\mathcal{A}_{MDL}$ outputs $P(Y|X : \bar{\theta} \prec \hat{M}) \in \mathcal{H}_N(G_{DL}^k(n))$.

</details>

<details>
<summary> 教科書の4ページを力尽きるまでまとめる</summary>

訳しながら考えてみる
確率的決定リストの学習法はMDLの考えにより以下のように与えられる
論文の$N$は問題の$n$
論文の$t$は問題の$f$
論文では$k$は与えられている
論文の$p_j$は問題の$\theta_j$
論文の$n$は問題の$d$ <!-- 佐藤追記 -->

$\theta = (p_1(0), \cdots p_m(0), p_1(1), \cdots p_m(1))$とする
ここで，$p_i(0) = 1 - p_i(1) (i=1\cdots m)$
$D_i = (\mathbf{x_i}, y_i)$とする
$S = \{D_1, \cdots D_n \}$とする
$S$の中で$f_1(\bx) = \cdots = f_{j-1}(\bx) = 0$かつ$f_{j} = 1$を満たすものの個数を$N_j$とおく
そのうち，$y=1$のものの個数を$N_j^{+}$，$y=0$のものの個数を$N_j^{-}$とおく
ここで，$N_1 + \cdots N_m = n$，$N_j^{+} + N_j^{-} = N_j (j = 1, \cdots, m)$が成立する
$k$と$\theta$と$M = \{f_1,\cdots, f_m\}$によって与えられる条件付き確率分布を$P(Y | \mathbf{X} : \theta \prec M)$とする．
$n$個のデータ$D_1 \cdots D_n$が与えられたとき，$\mathbf{x}^n = \mathbf{x_1} \cdots \mathbf{x_n}$に対する$y^n = y_1, \cdots, y_n$の条件付き尤度(以下尤度という)は以下のように与えられる
\begin{align}
P(y^n | \mathbf{x}^n : \theta \prec M) = \prod_{i=1}^n P(y_i | \mathbf{x}_i : \theta \prec M) \\
= \prod_{j=1}^m p_j^{N_j^{+}} (1 - p_j)^{N_j^{-}}
\end{align}

ここで，Kraftの不等式$\sum_{y^n} 2^{-l(y^n : \theta \prec M)} = \sum_{y^n} P(y^n | \mathbf{x}^n : \theta \prec M) = 1 \leq 1$が満たされるため，
$\theta$と$M$と与えられた$\mathbf{x}^n$に対する$y^n$の記述長は$-\log P(y^n | \mathbf{x}^n : \theta \prec M)$と表される．
$\tilde{p_j} = \frac{N_j^{+}}{N_j}^{-}$とし，$\mathbf{\tilde{p_j}} = (\tilde{p_j}, 1 - \tilde{p_j})$と$\mathbf{p_j} = (p_j, 1 - p_j)$のKullback-Leibler divergenceを$D(\mathbf{\tilde{p_j}} || \mathbf{p_j}) = \tilde{p_j} \log(\frac{\tilde{p_j}}{p_j}) + (1 - \tilde{p_j})\log(\frac{1 - \tilde{p_j}}{1 - p_j})$とおく
記述長はエントロピー関数$H(x) \overset{\mathrm{def}}{=} -x \log x - (1 - x) \log (1 - x)$を用いて以下のように表される
\begin{align}
l(y^n | \mathbf{x}^n : \theta \prec M) \overset{\mathrm{def}}{=} -\log P(y^n | \mathbf{x}^n : \theta \prec M) \\
= -\log \prod_{j=1}^m p_j^{N_j^{+}}(1 - p_j)^{N_j^{-}} \\
= \sum_{j=1}^m N_j\{H(\tilde{p_j} + D(\mathbf{\tilde{p_j}} || \mathbf{p_j}))\}
\end{align}

ここで力尽きた

</details>

## 課題2
### 問題
$\x = \{0, 1, \cdots, m\}$とする
$\x$に対する離散確率分布を
\begin{align}
P(X = i; \theta) = \theta_i~(i=0, \cdots, m), \sum_{i=0}^m \theta_i = 1, \theta_i \geq 0
\end{align}
とする

離散確率分布のクラスを用いた逐次予測をしたいとする
$x_1, x_2, \cdots, x_t, \cdots$が逐次的に与えられる
このとき，離散確率分布を用いてベイズ予測または逐次正規化最大尤度予測による予測分布を提示し，その分布の累積予測損失を理論的に確認せよ

### 解答？（古賀）
<details>
<summary> 前半はたぶんこれ、後半詰んだ </summary>

$t - 1$までに$\x = i$である数を$c_i$とする.$\sum_{i=0}^{m}c_i=t-1$
$k={\{0,m\}}^d$として、
\begin{align}
P(k \cdot {x}^{t-1}|\hat{\theta}(k \cdot {x}^{t-1})) &={\left(\frac{c_k + 1}{t}\right)}^{c_k + 1} \prod_{i=0,i\neq k}^{m} {\left(\frac{c_i}{t}\right)}^{c_i}\\
&=\frac{1}{t^t}\frac{{(c_k+1)}^{c_k+1}}{{c_k}^{c_k}}\prod_{i=0}^{m} {\left(\frac{c_i}{t}\right)}^{c_i}\\
\int P(x \cdot x^{t-1}:\hat{\theta}(x \cdot x^{t-1})) dx &= \sum_{j=0}^{m} P(j \cdot {x}^{t-1}|\hat{\theta}(j \cdot {x}^{t-1}))\\
&=\frac{1}{t^t} \sum_{j=0}^{m} \frac{{(c_j+1)}^{c_j+1}}{{c_j}^{c_j}} \prod_{i=0}^{m} {\left(\frac{c_i}{t}\right)}^{c_i}\\
P_{SNML}(x=k|x^{t-1}) &=\frac{P(k \cdot {x}^{t-1}|\hat{\theta}(k \cdot {x}^{t-1}))}{\int P(x \cdot x^{t-1}:\hat{\theta}(x \cdot x^{t-1})) dx}\\
&=\frac{{(c_k+1)}^{c_k+1}}{{c_k}^{c_k}} \frac{1}{\sum_{j=0}^{m} \frac{{(c_j+1)}^{c_j+1}}{{c_j}^{c_j}}}
\end{align}
(予測分布終わり)
累計対数予測損失は,
\begin{align}
\sum_{t=1}^{n}\left\{ -\log P_{SNML}(x_t|x^{t-1})\right\} &= \sum_{t=1}^{n} \left\{-\log \left\{\frac{{(c_{x_t}+1)}^{c_{x_t}+1}}{{c_{x_t}}^{c_{x_t}}} \frac{1}{\sum_{j=0}^{m} \frac{{(c_j+1)}^{c_j+1}}{{c_j}^{c_j}}}\right\}\right\}\\
&= \sum_{t=1}^{n} \left\{ \log\frac{{c_{x_t}}^{c_{x_t}}}{{(c_{x_t}+1)}^{c_{x_t}+1}} + \log\sum_{j=0}^{m} \frac{{(c_j+1)}^{c_j+1}}{{c_j}^{c_j}}\right\}\\ (以下まったく自信なし)
&\leq \sum_{t=1}^{n} \left\{ \log\sum_{j=0}^{m} \frac{{(c_j+1)}^{c_j+1}}{{c_j}^{c_j}} \right\}\\
&= \sum_{t=1}^{n} \left\{ \log\sum_{j=0}^{m} (c_j+1) {\left( 1 + \frac{1}{c_j} \right) }^{c_j} \right\}\\
&\leq \sum_{t=1}^{n} \left\{ \log\sum_{j=0}^{m} (c_j+1) e \right\}\\
&= \sum_{t=1}^{n} \left\{ 1 + \log\sum_{j=0}^{m} c_j+1 \right\}\\
&= n + \sum_{t=1}^{n} \log\left\{ 1+m+1 +\sum_{j=0}^{m} c_j \right\} \\
&= n + \sum_{t=1}^{n} \log (m+2 + t-1)\\
&= n + \sum_{t=1}^{n} \log(m+t+1) \\
\end{align}
(詰んだ)

- 
- 
</details>

## 課題3
備考: 1/7授業の範囲と言われた気もする?けど違う気もする
### 問題
指数分布というのは以下のように記される$\mu$をパラメータとする確率密度関数である．
\begin{align}
p(x; \mu) = \mu \exp(-\mu x),
\end{align}

密度関数が以下の式で与えられる混合指数分布を考える
\begin{align}
p(x; \theta) = \sum_{i = 0}^k \pi_i p(x; \mu_i),
\end{align}
ただし，$p(x; \mu_i)$は指数分布であり，$\mu_i \neq \mu_j (i \neq j)$，$\sum_{i = 0}^k \pi_i = 1, \pi_i \geq 0 (i=0, \cdots, k)$である
また，$\theta = (\pi_0, \cdots, \pi_k, \mu_0, \cdots, \mu_k)$とした
独立なデータ列$x^n = x_1, \cdots, x_n$について$\theta$と$k$を予測する方法を示せ

### 解答(佐藤)
<details>
<summary> 解答(ところどころ板書の誤植みたいなのを変えたので微妙かも) </summary>

$\newcommand{\loge}[1]{\ln #1}
\newcommand{\logb}[1]{\log_2 #1}
\newcommand{\R}{\mathbb{R}}$
$\mathcal{X}$をデータの定義域とする．データ列を$x^n = x_1\dots x_n \in \mathcal{X}^n$，それに対応する潜在変数の列を$z^n = z_1\dots z_n \in \{0,\dots,k\}^n$とおく．ここで，データ列を構成する$x_t\,(t=1,\dots,n)$はすべて独立であるとする．潜在変数の列に関しても同様に独立であるとし，また$x^n$と$z^n$も独立であるとする(ただし$x_t$は$z_t$にのみ依存する)．このとき
\begin{equation}
p(x^n ; \theta) = \prod_{t=1}^n p(x_t ; \theta)
\end{equation}
などが成立する．

モデルクラスを
\begin{equation}
\mathcal{P}_k =
\left\{\sum_{i=0}^{k} \pi_i
p(x; \mu_i) : \theta \in \R^{2k+1} \right\}
\end{equation}
と定義する．ただし，
\begin{equation}
\mu_i > 0,\,\pi_i \geq 0\, (i=0,\dots,k),\quad \sum_{i=0}^k \pi_k = 1
\end{equation}
である．また，$\theta = (\mu_0,\dots, \mu_k, \pi_0, \dots, \pi_{k-1})$とする($\pi_k$は，総和が1であることから他が決まれば自動的に決まる)．

潜在変数を，
\begin{equation}
p(z=i; \theta) = \pi_i,\quad\,p(x,z=i; \theta) = \pi_i\, p(x; \mu_i)
\end{equation}

モデルクラスの

$Q$関数を
\begin{equation}
Q(\theta|\theta') := \sum_{z^n} p(z^n |x^n , \theta') \loge p(x^n, z^n; \theta)
\end{equation}
と定義する．右辺を計算すると，
\begin{align}
Q(\theta | \theta') &= \sum_{z^n} \left( \prod_{t=1}^n p(z_t | x_t; \theta')\right) \loge \prod_{t=1}^n p(x_t, z_t; \theta) \\
&= \sum_{t=1}^n \sum_{i=0}^k p(z_t = i\,| x_t; \theta') \loge \left(\pi_i \,p(x_t; \theta_i)\right)\\
&= \sum_{t=1}^n \sum_{i=0}^k \gamma_i(t) \loge \left(\pi_i \,p(x_t; \theta_i)\right)
\end{align}

ここで，$\theta' = (\mu'_0,\dots, \mu'_k, \pi'_0, \dots, \pi'_{k-1})$であり，また
\begin{align}
\gamma_i(t) &= p(z_t = i\,| x_t; \theta') \\
&= \frac{\pi_i' \,p(x_t, \mu'_i)}{\sum_{j=0}^k \pi_j' \,p(x_t, \mu'_j)}
\end{align}
と$\gamma_i(t)$を定義した．

さて，$Q$を変分法を用いて最大化すると，$i=0,1,\dots,k$に対して
\begin{equation}
\left\{
\begin{aligned}
\hat{\pi_i} &= \frac{1}{n}\sum_{t=1}^n \gamma_i(t) \\
\hat{\mu_i} &= \underset{\mu_i}{\mathrm{argmax\,}}
\sum_{t=1}^n \gamma_i(t) \loge \left(\hat{\pi_i} \,p(x_t; \mu_i)\right)
\end{aligned}
\right.
\end{equation}
となる．

$\hat{\mu_i}$を具体的に求める．$p(x_t; \mu_i) = \mu_i \exp(- \mu_i x_t)$を右辺の argmax の中身($F$とおく)に代入すると，

\begin{align}
F &= \sum_{t=1}^n \gamma_i(t) \loge \left(\hat{\pi_i} \cdot \mu_i \exp(- \mu_i x_t)\right) \\
&= \sum_{t=1}^n \gamma_i(t) \left( \loge\hat{\pi_i} + \loge\mu_i - \mu_ix_t \right) \\
\frac{\partial F}{\partial \mu_i} &= \sum_{t=1}^n \gamma_i(t) \left( 0 + \frac{1}{\mu_i} - x_t \right) \\
&= \frac{1}{\mu_i} \sum_{t=1}^n \gamma_i(t) - \sum_{t=1}^n \gamma_i(t)x_t
\end{align}

$\frac{\partial F}{\partial \mu_i} = 0$となるときの$\mu_i$を$\hat{\mu_i}$とおくと，

\begin{equation}
\hat{\mu_i} = \frac{\sum_{t=1}^n\gamma_i(t)}{\sum_{t=1}^n\gamma_i(t)x_t}
\end{equation}
となる．これを利用して，EM アルゴリズムで最尤な$\theta$を探せばよい．すなわち，

<!-- \begin{enumerate}
\item 初期値 $\theta' = (\{ \mu'_i \},\,\{ \pi'_i \})$ からスタートする．
\item 上に示した方法で，$\theta'$をもとに$\hat{\mu}_i,\,\hat{\pi}_i$を求める．
\item $\theta = (\{ \hat{\mu}_i \},\,\{ \hat{\pi}_i \})$とおく．
\item $\theta$が収束していれば終了．していなければ$\theta' \gets \theta$として 2. に戻る．
\end{enumerate} -->

- 1. 初期値 $\theta' = (\{ \mu'_i \},\,\{ \pi'_i \})$ からスタートする．
- 2. 上に示した方法で，$\theta'$をもとに$\hat{\mu}_i,\,\hat{\pi}_i$を求める．
- 3. $\theta = (\{ \hat{\mu}_i \},\,\{ \hat{\pi}_i \})$とおく．
- 4. $\theta$が収束していれば終了．していなければ$\theta' \gets \theta$として 2. に戻る．

最終的に求まった$\theta$は最尤推定量であり，これを$\hat{\theta}$とおく．
以上で$\theta$を推定する手順は終了である．

続いて，最適なパラメータの個数$k$を推定する方法を述べる．そのために正規化最尤符号長$\mathcal{L}_\mathrm{NML}(x^n, z^n; k)$を計算し，これを最小化することを試みる．
\begin{align}
&\mathcal{L}_\mathrm{NML}(x^n, z^n; k) \\
&= -\logb p_\mathrm{NML}(x^n, z^n; k) \\
&= -\logb p(x^n, z^n; \hat{\theta}(x^n,z^n), k) + \logb \sum_{w^n} \sum_{y^n} p(y^n, w^n; \hat{\theta}(y^n,w^n), k) \\
&= \frac{1}{\loge 2}\left( -\loge p(x^n, z^n; \hat{\theta}(x^n,z^n), k) + \loge \sum_{w^n} \sum_{y^n} p(y^n, w^n; \hat{\theta}(y^n,w^n), k) \right)
\end{align}
であるから，$\mathcal{L}_\mathrm{NML}(x^n, z^n; k)$を最小化することは
\begin{equation}
-\loge p(x^n, z^n; \hat{\theta}(x^n,z^n), k) + \loge \sum_{w^n} \sum_{y^n} p(y^n, w^n; \hat{\theta}(y^n,w^n), k)
\end{equation}
を最小化することと等価である．以下，これの最小化を考える．

第1項($-\loge p(x^n, z^n; \hat{\theta}(x^n,z^n), k)$)から計算する．
\begin{align}
&-\loge p(x^n, z^n; \hat{\theta}(x^n,z^n), k) \\
&= -\loge \left( \prod_{i=0}^k p(x_i^n | z=i ; \hat{\mu}(x_i^n, z_i^n)) \prod_{i=0}^k \left( \frac{n_i}{n}\right)^{n_i} \right) \\
&= -\sum_{i=0}^k \loge p(x_i^n; \hat{\mu}(x_i^n)) + \sum_{i=0}^k n_i \loge \frac{n_i}{n}
\end{align}

ここで，$x_i^n$は「$z=i$となる$x^n$のデータ(部分)列」であり，$z_i^n$は$x_i^n$に対応する$z^n$の部分列である．また，$n_i$は$x_i^n$の長さ，すなわち「$x^n$のうちで$z=i$となったデータの個数」である．($x_i^n$は $p(Z=i | x_t; \theta)$が$i$で最大となるような$x_t$を集めればよい?? $p(Z=i | x_t; \theta)$は
\begin{equation}
p(Z=i | x_t; \theta) = \frac{\pi_i \, p(x_t | \mu_i)}{\sum_{j=0}^k \pi_j \, p(x_t | \mu_j)}
\end{equation}
で求まる．)

第2項($\loge \sum_{w^n} \sum_{y^n} p(y^n, w^n; \hat{\theta}(y^n,w^n), k)$)を計算する．これを$\loge C_n(k)$とおくと，次の漸化式が成立することが知られている:
\begin{equation}
C_n(k+1) = \sum_{\substack{r_1 + r_2 = n \\ r_1, r_2 \geq 0}}
\frac{n!}{r_1! r_2!} \left(\frac{r_1}{n}\right)^{r_1} \left(\frac{r_2}{n}\right)^{r_2} C_{r_1}(k) \tilde{C}_{r_2}
\end{equation}

ただし，$C_0 (k) = 1, C_j(0) = \tilde{C}_j\;(j=1,\dots,n)$である．
ここで，$\tilde{C}_n$ は各成分の parametric complexity :
\begin{equation}
\tilde{C}_n = \loge \sum_{y^n} p(y^n, \hat{\mu}(y^n))
\end{equation}
である．まずは$\tilde{C}_n$を計算する．この際に以下で定義される$g$-関数を導入する:
\begin{equation}
g(\overline{\theta}; \theta) := \sum_{x^n : \hat{\theta}(x^n) = \overline{\theta}} p(x^n; \theta)
\end{equation}
すなわち，$x^n$に関する$\theta$の最尤推定量$\hat{\theta}(x^n)$が$\overline{\theta}$と一致するようなすべての$x^n$にわたって$p(x^n; \theta)$を足し合わせたものを，$g(\overline{\theta}; \theta)$と定義する．
これは，$\overline{\theta}$に関して確率変数となる($\int g(\overline{\theta}; \theta) \,d\overline{\theta}=1$)ことが知られている(すなわち，$g(\overline{\theta}; \theta)$は$\theta$の最尤推定量が従う確率分布)．この$g$-関数を用いると，$\tilde{C}_n$を
\begin{equation}
\tilde{C}_n = \loge \left(\int g(\hat{\theta}; \hat{\theta})\,d\hat{\theta} \right)
\end{equation}
と計算できる．以下，指数分布に対してこれを計算する．

指数分布に関して，$\hat{\theta} = \dfrac{n}{\sum_{t=1}^n x_t}$であることを用いると，
\begin{align}
p(x^n; \theta) &= \prod_{t=1}^n \theta \exp(-\theta x_t) \\
&= \theta^n \exp\left(-\theta \sum_{t=1}^n x_t\right)\\
&= \theta^n \exp\left(-\frac{n\theta}{\hat{\theta}}\right) \\
&= p(x^n | \hat{\theta}(x^n)) g(\hat{\theta}(x^n); \theta)
\end{align}
となる．ここで，$g(\hat{\theta}(x^n); \theta)$は，形状パラメータ$n$, スケールパラメータ$1/\theta$のガンマ分布:
\begin{equation}
g(\hat{\theta}(x^n); \theta) = \frac{\theta^n n^n}{\Gamma(n) \hat{\theta}(x^n) ^ {n+1}} \exp\left(-\theta \cdot \frac{n}{\hat{\theta}(x^n)}\right)
\end{equation}
となることが知られている．これに$\theta = \hat{\theta}(x^n)$を代入することで
\begin{equation}
g(\hat{\theta}(x^n);\hat{\theta}(x^n)) = \frac{n^n}{e^n (n-1)!} \cdot \frac{1}{\hat{\theta}(x^n)}
\end{equation}
を得る．これを$\hat{\theta}$の関数とみて積分すれば$\tilde{C_n}$が求まるが，このままでは積分が発散してしまうので，$\hat{\theta}$の範囲を
$\hat{\Theta} = [\theta_\mathrm{min},\, \theta_\mathrm{max}]$に制限した上で積分する．すると，

\begin{equation}
\int g(\hat{\theta}; \hat{\theta})\,d\hat{\theta} = \frac{n^n}{e^n (n-1)!} \loge \frac{\theta_\mathrm{max}}{\theta_\mathrm{min}}
\end{equation}
となる．以上より，
\begin{align}
\tilde{C}_n &= \loge\left({\frac{n^n}{e^n (n-1)!} \loge \frac{\theta_\mathrm{max}}{\theta_\mathrm{min}}}\right)\\
&= n \loge n - n - \loge{(n-1)!} + \loge\loge \frac{\theta_\mathrm{max}}{\theta_\mathrm{min}}
\end{align}
を得る．これを用いて漸化式を解き，各$k$について$\mathcal{L}_\mathrm{NML}$を計算し，$\mathcal{L}_\mathrm{NML}$が最小となるような$k$を最適な$k$として採用すれば良い．
</details>

参考文献
- http://eda.mmci.uni-saarland.de/events/mdldm19/slides/mdldm19-part3.pdf
- https://ieeexplore.ieee.org/document/6574252

## 課題4
備考: 1/14授業の範囲
### 問題
$x_1, x_2, \cdots,$が確率分布$p(x; \theta, M_1)$から独立に選ばれるとする
このモデルがある時刻において$M_1$から$M_2$ ($\theta$は実数パラメータ, $M$はモデル)に遷移するとする
このとき，モデル遷移確率は未知の$0 \leq \alpha \leq 1$について
\begin{align}
p(M'|M;\alpha) = \begin{cases}1 - \alpha & \mathrm{if} M' = M, \\ \alpha & \mathrm{if} M' \neq M,\end{cases}
\end{align}
と表される
変化は一度しか起こらないとする
$n$個のデータ列を観測した後に変化点を検知する方法を記せ
## 課題5
備考: チャレンジングな問題らしい
### 問題
制約付きボルツマンマシンは密度関数が以下のように与えられる確率モデルである
観測された変数$x = {(x^{(1)}, \cdots, x^{(d)})}^T$と潜在変数$z = {(z^{(1)}, \cdots, z^{(k)})}^T$について
\begin{align}
p(x, z; W) = \frac{\exp(x^T W z)}{\sum_x \sum_z \exp(x^T W z)}
\end{align}
ここで，$W = (W_{ij}) \in R^{d \times k}$をパラメータ行列とする
このとき，独立なデータ列$x^n = x_1, \cdots x_n$に対して$W$を推定する方法を記せ．また，データ列から最善の$k$を選択する方法を記せ
## 課題6
### 問題
課題1-5で登場しなかった確率モデルを選択し、パラメータ推定とモデル選択の方法を示せ
## 課題7
### 問題
情報論的機械学習を実世界に適用する可能性と困難さを議論せよ。議論には数個の具体例を入れること
## 課題8
### 問題
情報、符号長、確率の関係性を説明せよ。MLEを使ったモデルを機械学習に用いるのが妥当であるという理由を述べよ
## 課題9
### 問題
教科書のone sectionをまとめよ。
"Information-theoretic Learning Theory"
"Information-theoretic Learning and Data Mining"
## 課題10
### 問題
黒板を写したノートを提出せよ