試験問題例

導入

No.01: 汎化能力について説明せよ

学習した問題とその答えの情報などを用い、未知の問題に対して正しい答えを導く能力のこと。

確率統計

No.02: 確率統計外れ値がある場合の期待値の問題点と他の統計量との違いを具体例を交えて説明せよ

年収の平均値が400万円、中央値が350万円の合計50人の集団50人に、年収10億円の人が1人加わったとする。すると、その集団の平均年収は約2350万円となるが、一方の中央値はほとんど変わらない。

このように、外れ値がある場合、期待値はごく一部の外れ値に強く影響され、データを代表とする値とならないことがある。一方で、中央値や最頻値ではそのようなことが起こらない。このことを、「外れ値に対してロバストである（頑健性がある）」と呼ぶ。

No.03: ２つの確率変数の和の分散を各々の分散と共分散を用いて表せ

$$ V(X+Y) = V(X)+V(Y)+2Cov(X,Y) $$

No.04: 分散共分散行列について説明せよ

分散の概念を多次元確率変数に拡張して行列としたもの。

N個の確率変数について、各確率変数同士の共分散を並べたN×N行列。
対角には分散が、非対角には共分散が並ぶ。
半正定値対称。
各確率変数が独立なら対角行列。

No.05: 相関係数及び正の相関・負の相関・無相関について説明せよ

2つの確率変数X,Yの相関係数は

$$\frac{Cov(X,Y)}{\sqrt{V(X)}\sqrt{V(Y)}}$$

で定義され、この値は$-1$以上$1$以下となる。相関係数が正、負、$0$のときそれぞれ正の相関がある、負の相関がある、無相関であるという。

No.06: 独立と無相関性について説明せよ

2つの連続型/離散型の確率変数$X,Y$は同時確率密度/質量関数がそれぞれの周辺確率密度/質量関数の積で表されるとき独立であるという。
2つの確率変数$X,Y$が独立な時、
- 積の期待値はそれぞれの期待値の積と一致する。（$E[XY] = E[X]E[y]$）
- 和の積率母関数はそれぞれの積率母関数の積と一致する。（$M_{X+Y}(t) = M_X(t)M_Y(t)$）
- 無相関である。（逆は成り立たない。）

No.07: 畳み込みについて説明せよ

2つの独立な確率変数$X,Y$の周辺確率密度関数を$p_x,p_y$とすると$X$と$Y$の和$Z$の確率密度関数は

$$p_z(z) = \int p_x(x) p_y(z-x) dx$$

と計算できる。このように、関数 $g(=p_x)$ を平行移動しながら関数 $f(=p_y)$ に重ね足し合わせる二項演算（$f\ast g$）のことを畳み込み(convolution)と呼ぶ。

No.08: ２項分布の積率母関数を求め、期待値と分散を導出せよ

成功する確率$p$、失敗する確率$1-p$の実験を同じ条件で独立に繰り返すことをベルヌーイ試行という。このベルヌーイ試行を$n$回行った時の成功回数を確率変数とする離散確率分布を二項分布(binomial distribution)と呼ぶ。

$$ P(X=k)=\left(\begin{array}{l}{n} \\ {k}\end{array}\right) p^{k}(1-p)^{n-k} $$

積率母関数$M_X(t)$は、

$$ \begin{align} M_X(t) &= E\left(e^{tX}\right) \\ &= \sum_{x=0}^n e^{tx} P(X=x)\\ &= \sum_{x=0}^n e^{tx} \left(\begin{array}{l}{n} \\ {x}\end{array}\right) p^{x}(1-p)^{n-x}\\ &= \sum_{x=0}^n e^{tx} \left(\begin{array}{l}{n} \\ {x}\end{array}\right) \left(pe^t\right)^{x}(1-p)^{n-x}\\ &= (pe^t+q)^n \quad (\because \text{ Binomial theorem}) \end{align} $$

これを用いると、期待値$E(X)$は

$$ \begin{aligned} E(X) &=\left.\frac{d M_{X}(t)}{d t}\right|_{t=0} \\ &=\left.n\left(\mathrm{e}^{t} p+1-p\right)^{n-1} p \mathrm{e}^{t}\right|_{t=0} \\ &=n(1-p+p)^{n-1} p \\ &=n p \end{aligned} $$

同様にして、分散$V(X)$は

$$ \begin{aligned} E\left(X^{2}\right) &=\left.\frac{d^{2} M_{x}(t)}{d t^{2}}\right|_{t=0} \\ &=\left.\left(n p\left(\mathrm{e}^{t} p+1-p\right)^{n-1} \mathrm{e}^{t}\right)^{\prime}\right|_{t=0} \\ &=n(n-1) p\left(\mathrm{e}^{t} p+1-p\right)^{n-2} p \mathrm{e}^{t}+n p\left(\mathrm{e}^{t} p+1-p\right)^{n-1} \mathrm{e}^{t} \\ &=n(n-1) p^{2}+n p \\ V\left(X\right) &=E\left(X^{2}\right)-E\left(X\right)\\ &=np\left(1-p\right) \end{aligned} $$

と求められる。

No.09: ポアソン分布の積率母関数を求め、期待値と分散を導出せよ

ポアソン分布(Poisson distribution)は、単位時間中に平均$\lambda$回起こる事象の生起回数の確率分布で、確率質量関数は$\dfrac{e^{-\lambda} \lambda^x}{x!}$と表される。

ここで、積率母関数$M_X(t)$とその微分が

$$ \begin{align} M_X(t) &= \sum_{x=0}^\infty e^{tx} \cdot \frac{e^{-\lambda} \lambda^x}{x!} \\ &= e^{-\lambda} \sum_{x=0}^\infty \frac{(\lambda e^t)^x}{x!} \\ &= e^{-\lambda} e^{\lambda e^t} \quad \left(\because \text{ McLaughlin expansion : } e^t=\sum_{x=0}^\infty \frac{t^x}{x!}\right) \\ &= e^{\lambda (e^t-1)}\\ M_X^\prime(t) &= \lambda e^t e^{\lambda (e^t-1)} \\ M_X^{\prime\prime}(t) &= \lambda e^t e^{\lambda (e^t-1)} + \lambda^2 e^{2t} e^{\lambda (e^t-1)} \end{align} $$

であるから、期待値$E(X)$と分散$V(X)$はそれぞれ以下で表される。

$$ \begin{align} E(X) &= M_X^\prime(0) = \lambda \\ V(X) &= M_X^{\prime\prime}(0) - M_X^\prime(0)^2 = \lambda \end{align} $$

No.10: 正規分布の積率母関数を求め、期待値と分散を導出せよ

正規分布(normal distribution)の確率密度関数は

$$f(x) = \dfrac{1}{\sigma \sqrt{2 \pi}} \exp \left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$$

で表されるので、積率母関数$M_X(t)$は

$$ \begin{align} M_X(t) &= \int_{-\infty}^\infty e^{tx} f(x) dx \\ &= \exp \left(\mu t+\frac{\sigma^2 t^2}{2} \right) \underbrace{\int_{-\infty}^{\infty} \frac{1}{\sigma \sqrt{2 \pi}} \exp \left(- \frac{\{x-(\mu+\sigma^2t)\}^2}{2\sigma^2} \right) dx}_{=\int_{-\infty}^{\infty}\mathcal{N}\left(\mu+\sigma^2 t, \sigma^2\right) = 1} \\ &= \exp \left(\mu t+ \frac{\sigma^2 t^2}{2} \right) \end{align} $$

期待値は$\mu$、分散は$\sigma^2$となる。（導出は省略。）

No.11: ガンマ分布の積率母関数を求め、期待値と分散を導出せよ

ガンマ分布は、ガンマ関数 $\Gamma(\alpha) = \int_0^\infty x^{\alpha-1} e^{-x} dx \quad (>0)$を用いて

$$ \begin{align} f(x) = \begin{cases} \dfrac{\lambda^\alpha}{\Gamma(\alpha)} x^{\alpha-1} e^{-\lambda x} & (x \geq 0) \\ 0 & (x < 0) \end{cases} \end{align} $$

と表される。したがって、積率母関数は

$$ \begin{align} M_X(t) &= \int_0^\infty e^{tx} \frac{\lambda^\alpha}{\Gamma(\alpha)} x^{\alpha-1} e^{-\lambda x} dx \\ &= \frac{\lambda^\alpha}{\Gamma(\alpha)} \int_0^\infty \left(\frac{y}{\lambda - t} \right)^{\alpha -1} \exp(-y) \frac{1}{\lambda -t} dy \quad \left(\because y = (\lambda -t)x\right) \\ &= \frac{\lambda^{\alpha}}{\Gamma(\alpha)}\frac{1}{\left(\lambda-t\right)^{\alpha}}\int_0^{\infty}y^{\alpha-1}e^{-y}dy\\ &= \frac{\lambda^\alpha}{\Gamma(\alpha)} \frac{\Gamma(\alpha)}{(\lambda -t)^\alpha}\\ &= \lambda^\alpha (\lambda -t)^{-\alpha} \end{align} $$

となるので、

$$ \begin{align} M_X(t)^{\prime} &= \frac{\alpha}{\lambda-t}M_X(t)\\ &= \frac{\alpha\lambda^{\alpha}}{\left(\lambda-t\right)^{\alpha+1}}\\ M_X(t)^{\prime\prime} &= \frac{\left(\alpha + 1\right)}{\lambda-t}M_X(t)^{\prime}\\ &= \frac{\alpha\left(\alpha + 1\right)\lambda^{\alpha}}{\left(\lambda-t\right)^{\alpha+2}} \end{align} $$

から、期待値は$\dfrac{\alpha}{\lambda}$、分散は$\dfrac{\alpha}{\lambda^2}$となる。

No.12: 独立同一分布について説明せよ

$n$個の確率変数$X_1,\cdots,X_n$が「独立に」、「同じ分布に」従うとき、独立同一分布に従うという。

このとき、同時確率密度関数は、各標本の確率密度関数を$g(x)$とすると

$$ f(x_1,x_2,\cdots,x_n) = g(x_1)g(x_2)\cdots g(x_n) $$

で表される。ここでこれらが期待値$\mu$、分散$\sigma^2$の独立同一分布に従う標本だとすると、標本平均$\overline{X}_n = \displaystyle \frac{1}{n} \sum_{i=1}^n X_i$の期待値と分散は、期待値が$\mu$のままである一方、分散は$\dfrac{\sigma^2}{n}$と減少する。

つまり標本数を増やすことで、母集団の標本平均値が安定することが分かる。

No.13: チェビシェフの不等式について説明せよ

分散を持つ確率分布に従う任意の確率変数に対して、$k>0$のとき

$$P(|X-E(X)| \geq k) \leq \frac{V(X)}{k^2}$$

が成り立つ。この不等式を使うことで、「確率分布の具体的な形はわからないが、期待値と分散がわかる」といった場合に、確率の上限を計算することが可能になる。

なお、この不等式は以下のように証明できる。

$$ \begin{align} V(X) &= \int_{-\infty}^{\infty} (x-E(X))^2 f(x) dx \\ &\geq \int_I (x-E(X))^2 f(x) dx \quad (I = \{ x: |x-E(X)| \geq k \}) \\ &\geq k^2 \int_I f(x) dx \\ &= k^2 P(|X-E(X)| \geq k) \end{align} $$

No.14: 大数の弱法則について説明せよ

標本平均$\overline{X}_n$が期待値に確率収束するということ。

$$ \forall \varepsilon > 0 \lim_{n \to \infty} P(|\overline{X}_n - \mu| \geq \varepsilon) = 0 $$

これより，標本を十分に多く取れば標本平均を真の期待値とみなしてよいことがわかる。これは各標本の期待値を$\mu$、分散を$\dfrac{\sigma^2}{n}$とすると、チェビシェフの不等式より、

$$ \left(0\leq\right)P(|\overline{X}_n - \mu| \geq \varepsilon) \leq \frac{\sigma^2/n}{\varepsilon^2} $$

であり、$n \to \infty$のときに右辺が0に収束することから、左辺も0に収束することにより示される。

この法則は、実際には分散が存在しなくても成り立つ。

No.15: 大数の強法則について説明せよ

標本平均が概収束(almost sure convergence)するということ。つまり、無限列$\{X_n\}$の確率分布が$\mu$に収束する。

$$ \overline{X}_n \to \mu \quad \textrm{with probability } 1 $$

これにより、標本平均が母平均に収束することが分かる。

No.16: 確率収束と概収束の違いについて説明せよ

確率収束は$X_n$の確率分布を$n$ごとに考えるのに対し，概収束は無限列$\{ X_n \}$の確率分布を考える。

$$ \begin{align} X_n = \begin{cases} 0 & \textrm{with probability } 1-\frac{1}{n} \\ 1 & \textrm{with probability } \frac{1}{n} \end{cases} \end{align} $$

となるような確率分布を考えると、 \

$$ \begin{align} \lim_{n \to \infty} \textrm{Pr}(|X_n| - 1 > \varepsilon) &= 0 \\ \sum_{n=1}^\infty \textrm{Pr}(|X_n| = 1) &= \infty \end{align} $$

となり、0に確率収束するが、概収束はしないことが分かる。厳密には「ボレル・カンテリの補題」を用いて示される。

No.17: 中心極限定理について説明せよ

標本平均を標準化する。

$$ \overline{Z}_n = \dfrac{\overline{X}_n-\mu}{\sigma / \sqrt{n}} $$

このとき、任意に固定した$a < b$に対して$n \to \infty$のとき、次式が成り立つ。

$$ P(a \leq \overline{Z}_n \leq b) \to \int_a^b \dfrac{1}{\sqrt{2\pi}} e^{-x^2/2} dx $$

これを、「$\overline{Z}_n$の分布が標準正規分布に弱収束（または分布収束）する」と言ったり、$\overline{Z}_n$は漸近的に標準正規分布に従うと言ったりする。ここで、

$$ \overline{Z}_n \to Z (\text{ weakly }) \Longleftrightarrow \lim_{n \to \infty} M_{\overline{Z}_n}(t) = M_Z(t) $$

つまり、「弱収束すること」と「積率母関数が各点収束すること」は同値である。

まとめると、$n$が大きいとき、標本平均は期待値$\mu$、分散$\frac{σ^2}{n}$の正規分布にほぼ従う。

No.18: 弱収束・分布収束について説明せよ

弱収束・分布収束は

$$ \lim_{n \to \infty} M_{\overline{Z}_n}(t) = M_Z(t) $$

と同値であり、積率母関数が各点収束することである。これは、確率収束や概収束よりも弱い収束である。

No.19: 仮説検定について説明し、社会・科学における利用例とその役割について自由に述べよ

仮説検定とは、「母集団についての何らかの命題を標本に基づいて検証すること」である。

帰無仮説の元で成り立つ確率が高々$\alpha$であるような事象を考える。ここで$\alpha$は有意水準と呼ばれ、5%か1%に設定されることが多い。（検定を行う前に決める。）

次に、標本を観測してその事象が成り立っているかを調べる。

成り立っていれば、帰無仮説がほとんど起こらないことを証明しているので、帰無仮説を棄却する。
成り立っていなければ、帰無仮説が現実と矛盾することを証明するだけの「十分な根拠がない」として帰無仮説を採択する。

社会においては、例えば新たに開発した薬に効能が本当にあるのかどうかを検証する時などに用いられる。プラセボに対する薬の試験を考える（「薬の効果を有意的に主張できるか」を調べる）と、

帰無仮説は、「薬の効果を主張できない」に当たり、「薬に対する反応の平均がプラセボに対するそれと等しい。」という仮説
対立仮説は、「薬の効果を主張できる」に当たり、「薬に対する反応の平均がプラセボに対するそれとは異なる。」という仮説

である。(Wikipedia より)

No.20: 帰無仮説と対立仮説について説明せよ

帰無仮説は元の仮説で、何の関係もない、差異はみられない、仮説などそもそもなかった、などを意味する仮説で、対立仮説と排反な仮説である。

No.21: 有意水準について説明せよ

仮説検定において、帰無仮説を棄却する基準となる確率のこと。検定を行う前に決められ、通常1%か5%に設定される。なお、有意水準は「帰無仮説が正しいのに、謝って棄却してしまう確率（第一種の過誤）」でもある。

No.22: 正規分布の片側検定・両側検定について説明せよ

#	検定方法	例
両側検定	あるパラメータが目標値と等しいかを調べる検定方法	ある装置の複製を作ったときに、元の装置と同じ性能が得られるかを調べるときなどに使用される。正規分布においては、有意水準$\alpha$に対して、確率分布の両端の面積が$\frac{\alpha}{2}$の領域を棄却域とし、現実の正規化標本平均$Z$が棄却域に入ったら、帰無仮説を棄却する。
片側検定	あるパラメータが比較対象より大きいかどうかを調べる検定方法	新しく開発した装置の性能が従来の装置よりも良いかどうかを調べるときなどに使用される。正規分布においては、有意水準$\alpha$に対して、確率分布の右端の面積が$\alpha$の領域を棄却域とし、現実の正規化標本平均$Z$が棄却域に入ったら、帰無仮説を棄却する。

No.23: 二標本検定について例を交えて説明せよ

期待値がそれぞれ$\mu_X, \mu_Y$の二つの分布に従って取り出した独立同一分布に従う標本

$$ \{X_i\}_{i=1}^{n_X}, \{Y_i\}_{i=1}^{n_Y} $$

から帰無仮説$\mu_X = \mu_Y$を検定するような手法。

例えば、ある反応での化合物の生成量を予測する問題を考える。

触媒Xと触媒Yでそれぞれ何度か実験を行い、それぞれの生成量を調べると、触媒Xの方が平均生成量が少なかった。このとき、触媒Yの方が優れていると結論付けてよいかはわからないので、「触媒Xとの平均生成量の差が有意であるかどうか」を二標本検定で調べる。

二つの標本はそれぞれ$\mathcal{N}\left(\mu_X,\sigma^2\right),\mathcal{N}\left(\mu_Y,\sigma^2\right)$に従うとすると、標本平均の差$\overline{X}-\overline{Y}$は平均$\mu_X-\mu_Y$、分散$\frac{\sigma^2}{n_X}+\frac{\sigma^2}{n_Y}$の正規分布に従う。

母分散が既知の時：標本平均の差を標準化すると標準正規分布に従うので、棄却域を計算することができる。
母分散が未知の時： $t$検定を行う。まず、分散$\sigma^2$を標本から以下のように推定する。
$$ \hat{\sigma}^2 = \dfrac{\sum_{i=1}^{n_X} (X_i - \overline{X})^2 + \sum_{i=1}^{n_Y} (Y_i - \overline{Y})^2}{n_X + n_Y - 2} $$
このとき、$\hat{Z}$は自由度$\phi = n_X + n_Y - 2$の$t$分布に従うので、その$t$分布の棄却域を計算すればよい。

制約なし最適化

No.24: 制約なし最適化最適化問題における最適性条件について説明せよ

最適化問題の最適解であるための必要条件を最適性条件という。

No.25: 制約なし最適化問題の最適性条件について説明せよ

$x^{\ast}$が(局所)最適解であるための必要条件は

$$\frac{\partial}{\partial x} f(x^{\ast}) = 0$$

である。

No.26: 凸関数の定義を述べよ

任意の$\theta \in [0, 1]$と$x, y \in dom(f)$に対して

$$f(\theta x + (1 - \theta) y) \leq \theta f(x) + (1 - \theta)f(y)$$

が成立するとき、$f$を凸関数という

No.27: fが１階微分可能なときfが凸関数であるための必要十分条件について説明せよ

任意の$x, y$に対して

$$f(x) \ge f(y) + \nabla f (x)^T (x - y)$$

が成立することである。なお、このとき接線の方程式を$g$として$g \leq f$が成立する

No.28: fが２階微分可能なときfが凸関数であるための必要十分条件について説明せよ

ヘッセ行列が半正定値であること。すなわち、任意の$x$に関して

$$\nabla^2 f(x) \ge 0$$

が成立することである。

No.29: 凸集合について説明せよ

任意の$\theta \in [0, 1]$と$x, y \in S$に対して$\theta x + (1 - \theta) y \in S$となるとき、$S$を凸集合という。このとき、$x$と$y$を結ぶ線分上の全ての点が$S$に属する。

No.30: 凸最適化問題における最適解の必要十分条件について説明せよ

凸関数 $f$ において、$x^{\ast}$が(局所)最適解であるための必要十分条件は

$$\frac{\partial}{\partial x} f(x^{\ast}) = 0$$

である。

No.31: 劣勾配と劣微分について説明せよ

任意の$x$に対して$f(x) \ge f(x^{\prime}) + \theta^T (x - x^{\prime})$を満たすような$a$を(点$x^{\prime}$における)劣勾配といい、劣勾配全体の集合を(点$x^{\prime}$における)劣微分といい、$\partial f(x^\prime)$で表す。

なお、$f$が微分可能であれば、劣勾配は$f$の微分に一致する。

No.32: ヘッセ行列とニュートン法について説明せよ

2回微分可能な関数$f$に対して$H(x) = \nabla^2 f (x)$を点$x$におけるヘッセ行列という。つまり、

$$ [\nabla^2 f(x)]_{j,j^\prime} = \dfrac{\partial^2 f(x)}{\partial x^{(j)} \partial x^{(j^\prime)}} $$

である。ニュートン法は　、ステップ幅を$\varepsilon_k \in (0,1]$として、

$$x_{n+1} = x_n - \varepsilon_k H(x_n)^{-1} \nabla f(x_n)$$

という更新式によって(最適性条件を満たす)最適解$x^{\ast}$を求めるアルゴリズムである。一般の勾配降下法が一次微分の情報のみを用いるのに対し、二次微分の情報も用いるため、効率よく最適解に達することができるとされている。

No.33: 正割条件を導出し準ニュートン法との関係について説明せよ

目的関数$f(x)$の$x_k$周りでの二次近似$f_k(x)$は

$$ f_k(x) = f(x_k) + \nabla f(x_k)^T(x-x_k) + \frac{1}{2}(x-x_k)^T \nabla ^2 f(x_k)(x-x_k) $$

であり、これを$x$で微分すると、その勾配$\nabla f_k(x)$は

$$ \nabla f_k(x) = \nabla f(x_k)+\nabla^2 f(x_k)(x-x_k) $$

となる。$x=x_{k-1}$とすると、$\nabla f(x_{k-1}) = \nabla f_k(x_{k-1})$のとき、

$$ \nabla^2 f(x_k)(x_k-x_{k-1}) = \nabla f(x_k) - \nabla f(x_{k-1}) $$

を得る。これを正割条件(secant condition)という。

なお、準ニュートン法では、正割条件を満たす$H_k$の中で性質の良いものを選ぶ。

制約付き最適化

No.34: 制約付き最適化等式制約付き最適化問題の最適性条件について説明せよ

等式制約付き最適化問題

$$ \min_{x \in dom(f)} f(x) \quad \textrm{subject} \ \textrm{to} \ g(x) = 0 $$

の最適性条件は、$x^\ast$が最適解のとき、$\nabla f(x^\ast)$と$\nabla g(x^\ast)$が平行になることである。

No.35: ラグランジュ未定乗数法について説明せよ

$\min_x \{ f(x) \mid g(x)=0 \}$という等式制約付き最適化問題があったときに、ラグランジュ関数$L(x, \lambda) = f(x) + \lambda^T g(x)$を最適化することでこの最適化問題を解く方法をラグランジュの未定乗数法という。

このとき、$\dfrac{\partial }{\partial x}L = 0, \dfrac{\partial}{\partial \lambda}L = 0$が最適性条件となる。

No.36: 双対上昇法について説明せよ

適当な初期値からラグランジュ関数の最小化と双対変数の勾配上昇を交互に実行することで主変数を最適化する方法である。このときに扱う問題はラグランジュ双対問題で、

$$ \begin{align} f^\ast &= \max_{\lambda \in \mathbb{R}^m} \omega(\lambda) \\ \omega(\lambda) &= \inf_{x \in \chi} L(x,\lambda) \\ L(x,\lambda) &= f(x) + \lambda^T g(x) \end{align} $$

更新式は$\varepsilon_k (>0)$をステップ幅として

$$ \begin{align} x_{k+1} &= \textrm{argmin}_{x \in \chi} L(x,\lambda_k) \\ \lambda_{k+1} &= \lambda_k + \varepsilon_k g(x_{k+1}) \end{align} $$

となる。

No.37: 射影勾配法について説明せよ

射影勾配法(gradient projection method)は、不等式制約付き最適化問題

$$ \min_{x \in \chi} f(x) \ \textrm{subject} \ \textrm{to} \ h(x) \leq 0 $$

を解く手法の一つであり、

勾配降下$\tilde{x}_{k+1} = x_k - \varepsilon_k \nabla f(x_k)$
実行可能領域への射影$x_{k+1}=P_k \tilde{x}_{k+1}$

を繰り返して最適化を行う。これらをまとめると、更新式は、$x_{k+1}=P_k(x_k-\varepsilon \nabla f(x_k))$となる。射影が簡単に計算できる時には効率が良い。

No.38: KKT条件について説明せよ

不等式制約付き最適化問題における最適性条件である。一般には必要条件だが、凸最適化問題では必要十分条件となる。

$\min_x \{ f(x) \mid g(x) = 0, h(x) \le 0 \}$なる最適化問題において、条件式は

$\nabla f(x^{\ast}) + \nabla g(x^{\ast})^T \lambda^{\ast} + \nabla h(x^{\ast})^T \mu^{\ast} = 0$
$g(x^{\ast}) = 0$
$h(x^{\ast}) \le 0$
$\mu^{\ast} \ge 0$
$\mu_i^{\ast} h_i(x^{\ast}) = 0 \quad i = 1, \dots, n$

である。

教師あり学習

No.39: 教師あり学習教師あり学習について説明し、独自の応用例とその実現可能性・社会的影響について自由に述べよ

手持ちの正解付きデータを使って新たなデータに対する正解を予測するような機械学習の手法のこと。

代表的な統計手法はとしては回帰と分類がある。前者は降水量の予測、後者は文字画像の認識などに使用される。

No.40: 最小二乗回帰について説明せよ

訓練出力との二乗誤差

$$E_D(\mathbf{w}) = \frac{1}{2}\sum_{n=1}^N\left\|\mathbf{t}_n-\mathbf{y}\left(\mathbf{x}_n, \mathbf{w}\right)\right\|^2$$

を最小にするモデルパラメータ$\mathbf{w}$を求める手法。

ここで、$y\left(\mathbf{x}_n, \mathbf{w}\right)$が$\mathbf{w}$に関して線形な線形モデル$\left(y\left(\mathbf{x}_n, \mathbf{w}\right) = \mathbf{w}^T\boldsymbol{\phi}(\mathbf{x}_n)\right)$のとき、

$$ \begin{aligned} \mathbf{w}_{\text{ML}}&=\left(\boldsymbol{\Phi}^T\boldsymbol{\Phi}\right)^{-1}\boldsymbol{\Phi}^T\mathbf{t}\\ \boldsymbol{\Phi}_{nj}&= \phi_j(\mathbf{x}_n) \end{aligned} $$

と解が解析的に求まるという利点があるが、ノイズを含む訓練標本に過剰に適合する過適合という現象が起こるという欠点もある。

No.41: 正則化の役割と具体例について説明せよ

モデルの複雑さに罰則を科すことで、不良設定問題を解いたり過学習を防いだりする手法のこと。理論的正当化はオッカムの剃刀にある。

具体的には正則化最小二乗回帰という手法があり、

$$ E_D(\mathbf{w}) + \lambda E_{\mathbf{w}}(\mathbf{w}) = \frac{1}{2}\sum_{n=1}^N\left\|\mathbf{t}_n-\mathbf{y}\left(\mathbf{x}_n, \mathbf{w}\right)\right\|^2 + \frac{\lambda}{2}\mathbf{w}^T\mathbf{w} $$

を計算する。最小二乗回帰と同様に解析的に解を求めると、

$$ \mathbf{w}_{\text{ML}} = \left(\lambda\mathbf{I} + \boldsymbol{\Phi}^T\boldsymbol{\Phi}\right)^{-1}\boldsymbol{\Phi}^T\mathbf{t} $$

となる。

No.42: 交差確認法の役割と具体例について説明せよ

採用した正則化パラメータ$\lambda$やガウス幅$h$などのハイパーパラメータの精度を判断するために交差確認法を行う。訓練データセットサイズが小さい場合でも適用することができる。

具体的には訓練標本$Z = \{(x_i,y_i)\}_{i=1}^n$を$k$分割して、$\{Z_i\}_{i=1}^k$を作る。$Z_i$以外を使ってモデルを学習し、残った$Z_i$を使ってテスト誤差を確認する。これをすべての組み合わせに対して繰り返し、その平均を出力する。

最終的には、この平均が最も小さくなるようなハイパーパラメータを採用することにする。

No.43: マージンについて説明せよ

サポートベクターマシンなどにおいて、分類境界から最も近いデータ点までの距離をマージンという。

データが線形分離できる場合：マージンの逆数の2乗であるハードマージンを最小化(マージンを最大化)するように分類境界を定める。
そうでない場合：ペナルティを加えたソフトマージンを最小化するように境界を定める。

マージンが大きい分類器は訓練データのずれに対して頑健であり、汎化誤差が小さくなりやすい。

No.44: 教師あり学習におけるカーネルトリックの役割と具体例を述べよ

モデルの学習のための式中に現れる$\phi(x)$などの特徴量を直接計算しなくても、その内積$\phi(x_i)^T \phi(x_j)(=K(x_i,x_j))$さえわかれば式を計算することができる。

そこで、カーネル関数を用いて式を書き直すと、標本数に対する計算量は悪化するが、特徴空間が高次元の場合であっても(無限次元であっても)計算量は変わらない。

例えばカーネルトリックを使えば、非線形の基底を用いる分類問題

$$ \min_\theta [C\sum_i \max (0,1-f_\theta (x_i) y_i) + \theta^T K \theta ] $$

をステップ幅$\varepsilon (>0)$で、更新式を

$$ \theta \leftarrow \theta - \varepsilon \left( C\sum_i \partial_\theta \max (0,1-f_\theta (x_i) y_i) + 2 K \theta \right) $$

とする劣勾配法を適用して解くことができる。

探索

No.45: 探索深さ優先探索について説明し、完全性・計算量・最適性に関して述べよ

行き止まりになるまで進み、ゴールが見つからなかったら直前の分岐に戻って別の道を探すアルゴリズムである。探索時のオープンリストをスタックにすることで実現できる。

最大分岐数を$b$、最大の深さを$m$として、

完全性(必ず解が見つかるか): ($m$が有限ならば)Yes
時間計算量: $O(b^m)$
空間計算量: $O(bm)$
最適性(一番近くの解が見つかるか): No

No.46: 幅優先探索について説明し、完全性・計算量・最適性に関して述べよ

分かれ道にきたらそれぞれの道を一歩ずつ進み、ゴールが見つからなかったらそれぞれの道をもう一歩ずつ進むアルゴリズムである。探索時のオープンリストを待ち行列にすることで実現できる。

最大分岐数を$b$，一番浅い解の深さを$d$として，

完全性: Yes
時間計算量: $O(b^d)$
空間計算量: $O(b^d)$
最適性: Yes

No.47: 反復深化探索について説明し、完全性・計算量・最適性に関して述べよ

深さに制限をつけて深さ優先探索を行い、徐々に深さを深くしていくアルゴリズムである。

最大分岐数を$b$，一番浅い解の深さを$d$として，

完全性: Yes
時間計算量: $O(b^d)$
空間計算量: $O(bd)$
最適性: Yes

No.48: A*探索について説明せよ

A*探索は、グラフ探索アルゴリズムの1つであり、あるノード$n$を経由する場合のコストを

$$ f(n) \equiv g(n) + h(n) $$

と分割する。ここで$g(n)$はスタートから$n$までに要するコストを表し、$h(n)$は$n$からゴールまでに要するコストを表している。最適値については$\ast$をつけて表すことにすれば

$$ f^{\ast}(n) \equiv g^{\ast}(n) + h^{\ast}(n) $$

となる。最適経路上の任意のノード$n^{\ast}$では$f(n^{\ast}) = f^{\ast}(n^{\ast})$であることを利用し、$f^{\ast}(n)$の推定値$\hat{f}(n) \equiv \hat{g}(n) + \hat{h}(n)$がより小さくなるノードを優先的に探索する。

ここで、$\hat{g}(n)$は探索済みノードから$n$に遷移する場合の最小値、$\hat{h}(n)$は$h(n)$のヒューリスティック推定値であり、8パズル問題などではマンハッタン距離などが使われる。

No.49: ミニマックス探索について説明せよ

想定される最大の損害が最小になるように決断を行う戦略のことである。

ゲーム木のすべての局面のうち、

自分の手番では評価を最大化するような手
相手の手番では評価を最小化するような手

を選択するとして、最も評価を最大化できるような手を選ぶ探索手法をミニマックス探索という。

No.50: アルファ・ベータ探索について説明せよ

max 計算の下界を$\alpha$
min 計算の上界を$\beta$

として、ミニマックス探索における不要な部分を枝刈りして探索効率を上げた探索手法をアルファ・ベータ法という。

No.51: モンテカルロ木探索について説明せよ

適当な深さ（一定回数以上試行した局面についてはより深く探索するようにする）まで
その時点の評価値に基づいて

手を進め、それ以降はランダムにプレイ(ロールアウトを行う)して、勝敗判定を行い、勝率や試行回数などから計算される評価値を得る。

モンテカルロ木探索とは、これを繰り返すことで最適手順を探索する方法であり、UCBスコアを用いれば、無限回の試行で最適手順に収束することが知られている。

強化学習

No.52: 強化学習強化学習について説明し、独自の応用例とその実現可能性・社会的影響について自由に述べよ

ある環境内におけるエージェントが、現在の状態を観測し、取るべき行動を決定する問題を扱う機械学習の一種。エージェントは行動を選択することで環境から報酬を得、それを基に方策(policy)を学習する。

具体的には、ロボットの障害物回避などに用いられる。

No.53: マルコフ決定問題および期待割引報酬和最大化について説明せよ

現在の状態$s$を観測して行動$a$を選択するマルコフ決定過程において、得られる報酬が最大となるような方策を求める問題をマルコフ決定問題という。よく用いられる指標として期待割引報酬和があり、次の式で表される。

$$ E\left( \sum_{t=0}^\infty \gamma^t R(s_t, a_t, s_{t+1}) \right) $$

ここで$\gamma$は0以上1未満の値をとり、割引率と呼ばれる。$\gamma$を大きくするとより長期的な視点で報酬を最大化し、$\gamma$を小さくするとより短期的な視点で報酬を最大化する。

No.54: ベルマン方程式について説明せよ

状態$s$で行動$a$をとり、その後政策$\pi$に従って行動を続けたときに得られる割引報酬の期待値を表す状態行動価値関数$Q^\pi(s,a)$の定義式

$$ Q^\pi(s,a) = E \left(\sum_{t=0}^\infty \gamma^t R(s_t,a_t,s_{t+1}) | s_0=s,a_0=a \right) $$

から導かれる方程式であり、具体的には「次に得られる報酬」と「その後に得られる報酬和」の期待値である。

$$ Q^\pi(s, a) = E\left(R(s, a, s^{\prime}) + \gamma Q^\pi(s^{\prime}, a^{\prime})\right) $$

No.55: 政策反復法の欠点について説明せよ

ベルマン方程式ではすべての状態$s$、行動$a$に対して$Q^\pi(s,a)$を計算する必要があるため、計算量が大きくなってしまう。

特に状態や行動が連続値をとる場合には厳密に計算することができなかったり、ノイズを含む標本に過適合しやすかったりといった問題がある。

No.56: ベルマン二乗残差の最小化について説明せよ

状態行動価値関数$Q^\pi$を何らかのモデルで近似し、ベルマン方程式の両辺の値の差(残差)を2乗したもの

$$ [E(R(s, a, s') + \gamma Q^\pi(s', a'))-Q^\pi(s, a)]^2 $$

をベルマン二乗残差という。これを最小化する問題は通常の回帰問題になっている。

No.57: 逆強化学習について説明せよ

報酬関数も未知であるときに、それをデータから学習するような強化学習を逆強化学習(Inverse Reinforcement Learning; IRL)という。

報酬関数を$R_\beta (s_t,a_t,s_{t+1})$のようにモデル化し、"良い"行動例をいくつか教えて良い行動に対する報酬が大きくなるようにパラメータ$\beta$を学習する。

教師なし学習

No.58: 教師なし学習教師なし学習について説明し、独自の応用例とその実現可能性・社会的影響について自由に述べよ

正解の与えられていないデータのみから意味のある情報を取り出すような機械学習の手法の一つ。クラスタリングという手法がよく用いられる。音声信号の分離などに用いられる。

No.59: 主成分分析について説明せよ

射影誤差が最小となるような射影によって、高次元データを低次元データに圧縮する変換を主成分分析(Principal component analysis; PCA)という。$d$次元のデータを$m$次元に射影することを考える($1 \leq m \ll d$)。

すると、射影誤差が最小となる射影$T$が"良い"射影だと考えることができる。つまり、

$$ T_{PCA} = \textrm{argmin}_{T \in \mathbb{R}^{m \times d}} \left[ \sum_i \| T^TTx_i-x_i\|^2\right] \quad \textrm{subject to } T^TT=I_m $$

が最も良い射影だと言える。このとき、

$$ \sum_i \| T^TTx_i-x_i\|^2 = -\textrm{tr} (TCT^T) - \textrm{tr} (C) \quad (C = \sum_i x_i x_i^T) $$

となるので、

$$ T_{PCA} = \textrm{argmax}_{T \in \mathbb{R}^{m \times d}} \ \textrm{tr}(TCT^T) \quad \textrm{subject to } T^TT=I_m $$

という関係が導ける。つまり、$C$の固有ベクトルを正規化して固有値の大きいものから$\xi_1,\dots, \xi_d$と選べば

$$ T_{PCA} = (\xi_1,\dots, \xi_m)^T $$

が求められる。

No.60: 固有値問題について説明せよ

行列$C$の固有値$\lambda_i$および固有ベクトル$\xi_i$を求める問題を固有値問題という。これらは固有方程式

$$ C\xi = \lambda \xi $$

の解として与えられる。固有ベクトルはすべて互いに直交し、内積はゼロになる。

No.61: ｋ-平均クラスタリングについて説明せよ

クラスタ中心$\{\mu_y\}_{y=1}^c$を適当に初期化した後、

各データ点が属するクラスの割当て
$$ \mu_y \leftarrow \dfrac{1}{n_y} \sum_{i:y_i=y} x_i \quad (i=1,\dots,c) $$
各クラスのクラスタ中心の更新
$$ y_i \leftarrow \textrm{argmin}_{y \in \{1,\dots,c\}} \|x_i-\mu_y\|^2 \quad (i=1,\dots c) $$

を交互に行うことで、ラベルなしのデータ点にクラスラベルをつけるアルゴリズム。

これはクラスタ内散布和の最小化問題の局所最適解を求めるアルゴリズムになっていて、k-平均クラスタリングによって得られたクラスタは凸になっている。

No.62: ｋ-平均クラスタリングにおけるカーネルトリックについて説明せよ

非線形な基底関数$\phi$によってデータ点$x_i$を$\phi(x_i)$に変換することで、非線形なクラスタの分類を行うことが可能になる。また、この$\phi$の内積などをカーネル関数に置き換えることで、特徴量を直接計算することなくk-平均クラスタリングを適用できる。

自然言語処理

No.63: 自然言語処理について独自の応用例とその実現可能性・社会的影響について自由に述べよ

No.64: 系列ラベリングが適用できる具体的な応用例を挙げ、定式化を与えよ

系列ラベリングの応用例として

形態素解析
固有名認識
DNA解析
音声解析
動作認識

などがある。このとき、入力は記号列で出力はラベル列である。

No.65: 隠れマルコフモデルの定義を与え、それを用いて品詞タグ付けを行う方法を説明せよ

隠れマルコフモデル(以下HMMとする)は、

状態集合$S$
出力記号集合$\Sigma$
初期状態分布$\pi_i$
状態遷移確率$a_{ij}$
出力確率$b_{io}$

の組で表現される。品詞タグ付けの例では、状態集合は品詞の集合、出力記号集合は単語の集合となっている。

パラメータ$\pi_i, a_{ij}, b_{io}$が与えられたとき、生成確率

$$ p(s_{1:T}, o_{1:T}) = \pi \Pi_{t=T-1} a_{s_t,s_{t+1}} b_{s_t,o_t} $$

が最大となるような状態系列をビタビアルゴリズム等で求めることで品詞タグ付けを行う。

No.66: トレリス構造について説明し、品詞タグ付けとの関係を説明せよ

トレリス構造は、生成確率が最も高くなるような状態系列を求めるための枠組みである。縦軸は各状態、横軸は時刻に対応しており、トレリス上のパスは状態系列を表す。品詞タグ付けでは、縦軸は品詞、横軸は単語列となっている。

No.67: 隠れマルコフモデルのビタビアルゴリズムを説明せよ

ビタビアルゴリズムとは、（観測データ系列の）生成確率が最大となるような状態系列を動的計画法によって求めるアルゴリズムである。時刻$t$で状態$s_t=k$にいたる状態系列の最大確率を

$$ q_t(k) \equiv \max_{s_{1:t-1}} p(s_{1:t-1}, o_{1:t}, s_t=k) $$

と定義すると、

$$ q_{t+1}(k) = \max_{i} [ q_t(i) a_{i, k} ] b_{k, o_{t+1}} $$

と書けるので、動的計画法によって$q_t(k)$を順に求めることができる。

状態数を$K$、系列の長さを$T$とすると、素朴に計算すると計算量$O(K^T)$かかるが、ビタビアルゴリズムでは$O(TK^2)$で済む。これは各系列位置で各状態への最適経路は一つ前の系列位置での各状態への最適経路とそこからの遷移確率を用いて$O(K)$で計算でき、これが状態数と系列の長さ分だけあるので、合計で$O(TK^2)$の計算量になるからである。

No.68: 隠れマルコフモデルのパラメータの教師付き学習方法を説明せよ

訓練データの状態系列が既知であるときには人手で正解を付与したデータであるタグ付きコーパスなどから教師つき学習によってパラメータを推定することができる。パラメータの推定方法の1つに最尤推定法がある。最尤推定法では、学習データの尤度(生成確率)を最大化するようにパラメータを決定する。

HMMのパラメータ$\pi_i,a_{i,j},b_{i,o}$を求めるためには

$$ \begin{align} p(o_{1:T},s_{1:T})&=p(s_1) \prod_{t=1}^T p(s_{t+1}|s_t)p(o_t|s_t)=\pi_{s_1} \prod_{t=1}^T a_{s_t,s_{t+1}}b_{s_t,o_t} \\ &\textrm{s.t. } \sum_{i \in S} \pi_i = 1, \sum_{j \in S} a_{i,j} = 1, \sum_{a \in \Sigma} b_{i,o} = 1 \end{align} $$

を最大化すれば良いので、これを計算すると、結果は

$$ \begin{align} \pi_i &= \dfrac{C(s_1=i)}{\sum_{i \in S} C(s_1=i)} \\ a_{i,j} &= \dfrac{C(i,j)}{\sum_{j \in S} C(i,j)} \\ b_{i,o} &= \dfrac{C(i,o)}{\sum_{o \in \Sigma} C(i,o)} \end{align} $$

となる。

No.69: 前向き・後向き確率の定義を与え、効率的な計算方法を説明せよ

時刻$t$・状態$i$にいたる全ての系列の確率の和を前向き確率
時刻$t$・状態$i$から最後に至る全ての系列の確率の和を後ろ向き確率

という。それぞれ

$$ \begin{align} \alpha_t(i) &\equiv p(o_{1:t}, s_t=i | \theta^{old}) \\ \beta_t(i) &\equiv p(o_{t+1:T} | s_t=i, \theta^{old}) \end{align} $$

で表される。これは動的計画法で再帰的に計算できて

$$ \begin{align} \alpha_{t+1}(i) &= \sum_{j \in S} [a_{j,i} \alpha_t(j)] b_{i, o_{t+1}} \\ \beta_{t-1}(i) &= \sum_{j \in S} [a_{i,j} b_{j, o_t} \beta_t(j)] \end{align} $$

となる。

No.70: Baum-Welch アルゴリズムについて説明せよ

訓練データの状態列が未知であるときに、状態および状態遷移の期待値とパラメータを交互に推定していくアルゴリズムである。詳しく言えば、「現在のパラメータ$\theta^{old}$によって状態の期待値を計算する」「状態の期待値を使ってパラメータを更新する」を収束するまで繰り返す。ここで、状態の期待値は

$$ \begin{align} \gamma_t(i) &\equiv p(s_t=i| o_{1:T},\theta^{old}) \\ \xi_t(i,j) &\equiv p(s_t=i, s_{t+1}=j| o_{1:T},\theta^{old}) \end{align} $$

と定義される。これらは前向き確率・後ろ向き確率を用いて効率的に計算できる。

No.71: ビタビアルゴリズムと前向き・後向きアルゴリズムの関係について説明せよ

ビタビアルゴリズムは「積の最大値」
前向き・後ろ向きアルゴリズムは「積の和」

を順に求めている点で類似している。両方とも分配法則を利用しているので、半環なら同じアルゴリズムが適用できる。

No.72: ログ線形モデルによる品詞タグ付け方法について説明せよ

ログ線形モデルでは、特徴ベクトルを$\boldsymbol{\phi}$として

$$ p(y|x) \propto exp(\mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}, y)) $$

という生成分布を考えて、パラメータ$\mathbf{w}$を最尤推定する。ここで$\mathbf{x}$はデータであり、$y$はそのラベルである。

品詞タグ付けの場面では、$\mathbf{x}$は入力された単語列、$y$はその品詞列(隠れ状態)であり、$\mathbf{w}^T \boldsymbol{\phi}(\mathbf{x}, y)$を最大化するような$y$を求める問題となる。

No.73: 条件付き確率場の定義を与え、隠れマルコフモデルに対する優位性を説明せよ

条件付き確率場とは、ログ線形モデルによる構造予測において用いられる枠組みである。

単純なログ線形モデルでは$\mathbf{w}^T \phi(\mathbf{x}, y)$を最大化するような$y$を求めるのが困難であるが、特徴ベクトルを状態・遷移に分解できると仮定することでHMMで行うような動的計画法のアルゴリズムが利用できる。

No.74: 条件付き確率場のビタビアルゴリズムを説明せよ

HMMのビタビアルゴリズムとほぼ同様である。

No.75: 条件付き確率場のパラメータ推定アルゴリズムを説明せよ

HMMのアルゴリズムとほぼ同様である。

No.76: CKY法について具体例（曖昧性のある文脈自由文法）を挙げて説明せよ

Chomsky標準形(CNF)のCFGの構文解析アルゴリズム。

No.77: 確率文脈自由文法(PCFG)の定義を与え、それを用いて構文解析を行う方法を説明せよ

CFG(文脈自由文法)に生成規則が適用される確率を導入したものをPCFGという。

入力された単語列に対して、それを生成するような構文木のうち確率が最大となるものを単語列に対応する構文木とする。確率を導入することで曖昧性が解消される。

No.78: 確率文脈自由文法(PCFG)による構文解析のビタビアルゴリズムを説明せよ

通常の(CFGにおける)のCKY法ではCKY表の各セルに「生成される非終端記号」を書き込んでいくが、PCFGにおけるCKY法では、各セルに「非終端記号とそれを生成する確率の最大値」を書き込んでいく。これによって、効率的に生成確率を求めることができる。

No.79: 確率文脈自由文法(PCFG)の学習方法について説明せよ

構文木のデータセット(ツリーバンク)を利用して学習を行う。ツリーバンクにおける品詞の出現頻度に基づいて生成規則の確率を推定する。

No.80: 確率文脈自由文法(PCFG)による自然言語構文解析の精度が低い原因を具体例を挙げて説明し、構文解析精度を上げる方法を議論せよ

同じ品詞列でも単語によって構文木の形が変わるから。例えば We applied the algorithm to parsing. と We selected the approach to parsing. がその一例である。そのため、品詞だけでなく単語の意味や熟語なども使って構文解析を行う必要がある。

No.81: 確率文脈自由文法(PCFG)の応用例(自然言語の構文解析以外)を挙げ、その実現可能性・社会的影響について自由に述べよ

試験問題例

導入

確率統計

制約なし最適化

制約付き最適化

教師あり学習

探索

強化学習

教師なし学習

自然言語処理

Table of Contents

Published

Last Updated

Category

Tags

Contact

Other contents