ブログ

DeepLearningなどの手法で近年よく用いられるクロスエントロピー(cross entropy)誤差ですが、実は多項分布に対して最尤法を用いることで導出を行うことができます。当記事では導出の大枠と関連で出てくるソフトマックス関数に関して取りまとめを行いました。

「深層学習」の$2.4$節の「問題の定式化：出力層と損失関数の設計」を元に再構成や追記を行うことで作成を行いました。

前提の理解

ベルヌーイ分布

クロスエントロピー(cross entropy)の式の基本形はベルヌーイ分布の確率関数の積に対し、対数を取ることで導出することができる。よって、ベルヌーイ分布の確率関数の理解が重要になる。一方でベルヌーイ分布の式の形は一見少々難しく見えるので注意が必要である。

確率変数$X$が確率を表すパラメータ$p \in [0,1]$を用いたベルヌーイ分布$Bin(n=1,p)$に従うとき、$X=0, X=1$の確率$P(X=0|p), P(X=1|p)$はそれぞれ下記のように表すことができる。
$$
\large
\begin{align}
P(X=0|p) &= 1 – p \\
P(X=1|p) &= p
\end{align}
$$

上記の確率関数は$X=k, k=0,1$のように考えることで$1$つの式にまとめることができる。
$$
\large
\begin{align}
P(X=k|p) = p^{k} (1-p)^{1-k}, \quad k=0, 1
\end{align}
$$

上記の右辺に$k=1$を代入すると$p^{1} (1-p)^{1-1}=p$、$k=0$を代入すると$p^{0} (1-p)^{1-0}=1-p$がそれぞれ成立する。数式は一見難しく見えるが、$k$は$0$か$1$以外の値を取らないことに基づいて$p^{0}=1, (1-p)^{0}=1$が成立することを考えればシンプルに考えることができる。

多項分布

ベルヌーイ分布は確率変数が$2$値の場合を取り扱う確率分布だが、多項分布では確率変数が$K>2$の値を取りうる場合を取り扱う。一般的な多項分布は$2$項分布と同様に複数回の試行に基づいた確率を考えるが、ここではベルヌーイ分布に対応して$1$回の試行のみに関して考える。

多項分布$\mathrm{Mul}(1,p_1,p_2,…,p_K)$の確率関数はベルヌーイ分布と同様に考えることで下記のように表すことができる。
$$
\large
\begin{align}
P(X=k|p_1,p_2,…,p_K) = \prod_{i=1}^{K} p_{i}^{d_i}, \quad k = 1, 2, …, K
\end{align}
$$

ここで上記の$d_i$は$i=k$のときに$d_i=1$、$i \neq k$のときに$d_i=0$となる変数である。ベルヌーイ分布と同様に$p_{i}^{0}=1, p_{i}^{1}=p_{i}$のように考えられることから、上記を元に$P(X=2|p_1,p_2,…,p_K) = p_{2}, P(X=5|p_1,p_2,…,p_K) = p_{5}$のようにそれぞれ考えることができる。$\displaystyle \prod$が出てくる分さらに難しく見えるが、ほとんどが$p_{i}^{0}=1$のようになることさえ把握しておけばシンプルに理解できる。

最尤法

下記などで詳しく取り扱った。
https://www.amazon.co.jp/dp/B08FYMTYBW/

・参考
問題演習：基本的な最尤法の流れ

導出の詳細

クロスエントロピー(cross entropy)の導出

$n$対のサンプル$(x_1,y_1), …, (x_n,y_n), \quad y_i \in \{1,2,…,K\}$に対し、$y_i=k$のとき$d_{ik}=1$、$y_i \neq k$のとき$d_{ik}=0$となるように$d_{ik}$を定める。

このとき同時確率関数$P(y_1,…,y_K|p_1,p_2,…,p_K)$は下記のように表すことができる。
$$
\large
\begin{align}
P(y_1,…,y_K|p_1,p_2,…,p_K) &= \prod_{i=1}^{n} P(y_i|p_1,p_2,…,p_K) \\
&= \prod_{i=1}^{n} \prod_{k=1}^{K} p_{k}^{d_{ik}}
\end{align}
$$

上記の同時確率関数はパラメータ$p_1,p_2,…,p_K$に関する尤度$L(p_1,p_2,…,p_K)$であると考えることができるので、$L(p_1,p_2,…,p_K)$は下記のように表される。
$$
\large
\begin{align}
L(p_1,p_2,…,p_K) &= P(y_1,…,y_K|p_1,p_2,…,p_K) \\
&= \prod_{i=1}^{n} \prod_{k=1}^{K} p_{k}^{d_{ik}}
\end{align}
$$

ここで上記において、GLMなどと同様に「$p_k$は$f_k(x_i|w)$のように$x_i$にパラメータを作用させて得られる」と考えると下記のように書き直すことができる。
$$
\large
\begin{align}
L(w) &= P(y_1,…,y_K|x_1,…,x_n,w) \\
&= \prod_{i=1}^{n} \prod_{k=1}^{K} f_k(x_i|w)^{d_{ik}}
\end{align}
$$

クロスエントロピー誤差$E(w)$は上記の対数を取り、「『尤度最大化』から『誤差関数の最小化』に変えるにあたってマイナスをかけることで導出できる。
$$
\large
\begin{align}
E(w) &= – \log{L(w)} \\
&= – \log \left[ \prod_{i=1}^{n} \prod_{k=1}^{K} f_k(x_i|w)^{d_{ik}} \right] \\
&= – \sum_{i=1}^{n} \sum_{k=1}^{K} d_{ik} \log{f_k(x_i|w)}
\end{align}
$$

ここで上記の$d_{ik}$は実測値の$y_1,…,y_n$から作成し、$f_k(x_i|w)$は$x_1,…,x_n$を用いて作成した予測値に対応することは抑えておくと良い。

ソフトマックス関数

前項で定義した$f_k(x_i|w)$は確率の予測値であるので、$0$から$1$の値を取るのが望ましい。この際にロジスティック回帰などのGLMではリンク関数を設定するが、DeepLearningでも同様のことを考える。

この際によく用いられるのがソフトマックス関数(softmax function)であり、各出力層の値を$u_k(x_i|w)$とするとき、$f_k(x_i|w)$は$u_k(x_i|w)$を用いて下記のように定義される。
$$
\large
\begin{align}
f_k(x_i|w) = \frac{\exp(u_k(x_i|w))}{\sum_{j=1}^{K} \exp(u_j(x_i|w))}
\end{align}
$$

参考

・深層学習

正規分布(Normal Distribution)の平均$\mu$や分散$\sigma^2$はそれぞれ平均とばらつき度合いを表すパラメータとされますが、それぞれの値によって確率密度関数の形状がどのように変わるかに関して考察されている場合が少ないと思われます。

そこで当記事では正規分布のパラメータが変わると確率密度関数の形状がどのように変化するかに関して取りまとめを行いました。具体的には「①平均を表す$\mu$が変わると確率密度関数$f(x)$が$x$方向に平行移動する」、「②$\sigma$が変化すると確率密度関数の最大値が変わる」、「③正規分布の分散の$1/2$乗の$\sigma$が確率密度関数の変曲点に一致する」などを確率密度関数の数式を元に確認を行いました。

確率密度関数と$\mu$の変化による平行移動

正規分布$N(\mu,\sigma^2)$の確率密度関数

確率変数$X$が$X \sim N(\mu,\sigma^2)$のように正規分布$N(\mu,\sigma^2)$に従う際の確率密度関数を$f(x)$とおくと、$f(x)$は下記のように表すことができる。
$$
\large
\begin{align}
f(x) = \frac{1}{\sqrt{2 \pi \sigma^2}} \exp \left( – \frac{(x-\mu)^2}{2 \sigma^2} \right)
\end{align}
$$

$\mu$の変化と確率密度関数の平行移動

・$N(0,\sigma^2)$
$$
\large
\begin{align}
f(x) = \frac{1}{\sqrt{2 \pi \sigma^2}} \exp \left( – \frac{x^2}{2 \sigma^2} \right)
\end{align}
$$

・$N(\mu,\sigma^2)$
$$
\large
\begin{align}
f(x) = \frac{1}{\sqrt{2 \pi \sigma^2}} \exp \left( – \frac{(x-\mu)^2}{2 \sigma^2} \right)
\end{align}
$$

上記で表した$N(0,\sigma^2), N(\mu,\sigma^2)$に関する確率密度関数の式より、$N(\mu,\sigma^2)$の確率密度関数は$N(0,\sigma^2)$の確率密度関数を$x$方向に$\mu$だけ平行移動させた関数であると考えることができる。

$\sigma$の値の変化による確率密度関数の形状の変化

確率密度関数の最大値

指数関数$f(x) = \exp(x)$は単調増加の関数であり、$x$が増加するとき$f(x)$も$x$に合わせて増加する。よって、確率密度関数の$\displaystyle \frac{1}{\sqrt{2 \pi \sigma^2}} \exp \left( – \frac{x^2}{2 \sigma^2} \right)$は$\displaystyle \frac{x^2}{2 \sigma^2} \geq 0$であることより、$\displaystyle \frac{x^2}{2 \sigma^2} = 0$であるときに最大値$\displaystyle \frac{1}{\sqrt{2 \pi \sigma^2}} \exp(0) = \frac{1}{\sqrt{2 \pi \sigma^2}}$をとることがわかる。

ここで$\displaystyle \frac{1}{\sqrt{2 \pi \sigma^2}} = \frac{1}{\sqrt{2 \pi} \sigma}$を$\sigma$に関して考えると、確率密度関数の最大値が$\sigma$の逆数に比例することがわかる。

これより、「分散が大きくなるにつれ確率密度関数の最大値が小さく」なり、「分散が小さくなるにつれて確率密度関数の最大値が大きく」なることがわかる。これは分散がばらつきの度合いを表すということと直感的に反しない結果であると考えることができる。

確率密度関数の変曲点

正規分布の確率密度関数の形状は、確率密度関数の$x$に関する$1$階微分、$2$階微分の式を元に増減表を描くことで数学的に把握することができる。

以下、$\displaystyle g(x) = \exp \left( – \frac{x^2}{2 \sigma^2} \right)$に対し、$1$階微分の$g'(x)$と$2$階微分の$g^{”}(x)$を計算する。
$$
\large
\begin{align}
g'(x) &= \exp \left( – \frac{x^2}{2 \sigma^2} \right) \times \left( – \frac{x^2}{2 \sigma^2} \right)’ \\
&= – \frac{x}{\sigma^2} \exp \left( – \frac{x^2}{2 \sigma^2} \right) \\
g^{”}(x) &= – \frac{1}{\sigma^2} \exp \left( – \frac{x^2}{2 \sigma^2} \right) – \frac{x}{\sigma^2} \exp \left( – \frac{x^2}{2 \sigma^2} \right) \times \left( – \frac{x^2}{2 \sigma^2} \right)’ \\
&= – \frac{1}{\sigma^2} \exp \left( – \frac{x^2}{2 \sigma^2} \right) – \frac{x}{\sigma^2} \exp \left( – \frac{x^2}{2 \sigma^2} \right) \times \left( – \frac{x}{\sigma^2} \right) \\
&= – \frac{1}{\sigma^2} \exp \left( – \frac{x^2}{2 \sigma^2} \right) + \frac{x^2}{\sigma^4} \exp \left( – \frac{x^2}{2 \sigma^2} \right) \\
&= \frac{1}{\sigma^4} (x^2-\sigma^2) \exp \left( – \frac{x^2}{2 \sigma^2} \right) \\
&= \frac{1}{\sigma^4} (x + \sigma)(x – \sigma) \exp \left( – \frac{x^2}{2 \sigma^2} \right)
\end{align}
$$

上記より、$g(x)$に関して下記のような増減表を作成することができる。
$$
\large
\begin{array}{|c|*9{c|}}\hline x & -\infty & \cdots & -\sigma & \cdots & 0 & \cdots & \sigma & \cdots & \infty \\
\hline g'(x)& 0 & + & + & + & 0 & – & – & – & 0 \\
\hline g^{”}(x)& + & + & 0 & – & – & – & 0 & + & + \\
\hline g(x)& 0 & \nearrow & \nearrow & \nearrow & 1 & \searrow & \searrow & \searrow & 0 \\
\hline
\end{array}
$$

上記より、$g(x)$は$x=0$で最大値をとり、$x = \pm \sigma$で変曲点をとることがわかる。

また、$f(x)$を$x$に着目して考えると定数$C$を用いて$f(x)=Cg(x)$のように表せるので、$f(x)$の変曲点は$g(x)$の変曲点に一致すると考えることができる。

したがって、正規分布$N(0,\sigma^2)$の確率密度関数の変曲点は$x = \pm \sigma$であり、これを$x$方向に平行移動させた$N(\mu,\sigma^2)$の確率密度関数の変曲点は$x = \mu \pm \sigma$であると考えることができる。

参考

・連続型確率分布
https://www.hello-statisticians.com/explain-terms-cat/probdist2.html

正規方程式(normal equation)は回帰式に対して最小二乗法(least square method)などを用いてパラメータの推定を行う際に出てくる数式です。$y = \beta_0 + \beta_1 x$のような単回帰の式の場合はシンプルな一方で、重回帰などを考えるにあたって行列表記を行うと難しそうに見えるので、当記事では行列に基づく正規方程式の導出の詳細を確認し、その直感的な理解に関して取りまとめを行いました。

内容の作成にあたっては「現代数理統計学（学術図書出版社）」の$11.1$節の「回帰モデル」と$11.2$節の「回帰モデルの推定」を主に参考にしました。

基本事項の確認

計画行列と回帰式

$$
\large
\begin{align}
y_i &= \beta_0 + \beta_1 x_i + \varepsilon_i \\
\varepsilon_i & \sim N(0,\sigma^2), \quad i.i.d.
\end{align}
$$

単回帰などを行うにあたっては、$x \in \mathbb{R}, y \in \mathbb{R}$のようなスカラー値を元に上記のように式を表す。同様に$k$次元の重回帰の式を考えると、下記のように表すことができる。
$$
\large
\begin{align}
y_i &= \beta_0 + \beta_1 x_{i1} + … \beta_k x_{ik} + \varepsilon_i \\
\varepsilon_i & \sim N(0,\sigma^2), \quad i.i.d.
\end{align}
$$

ここで上記の$2$式はどちらも$i$番目のサンプルに対応しており、さらに重回帰の式では複数変数を取り扱っており、要素を一つ一つ表すとなかなか表記が大変になる。

ここで表記をシンプルに行うにあたっては$n$対のサンプルに関する計画行列(design matrix)という行列を定義すると以下のように式の整理が行いやすい。
$$
\large
\begin{align}
y &= X \beta + \varepsilon \\
y &= \left(\begin{array}{c} y_{1} \\ \vdots \\ y_{n} \end{array} \right) \\
X &= \left(\begin{array}{cccc} 1 & x_{11} & \cdots & x_{1k} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n1} & \cdots & x_{nk} \end{array} \right) \\
\beta &= \left(\begin{array}{c} \beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{k} \end{array} \right) \\
\varepsilon & \sim N_{n}(0,\sigma^2I_{n})
\end{align}
$$

ここで上記の$X$を計画行列(design matrix)、$\beta$を回帰係数ベクトルという。

残差ベクトル$e$と誤差の二乗和

「計画行列と回帰式」で表したような実際に得られた$y$に対して$X \beta$を用いて計算した予測値との差を考え、$e = y – X \beta$のように定義するとき、$e$は残差ベクトルという。

また、下記で表したように$e^{\mathrm{T}}e$は誤差の二乗和に一致する。
$$
\large
\begin{align}
e^{\mathrm{T}}e &= (y – X \beta)^{\mathrm{T}} (y – X \beta) \\
&= \sum_{i=1}^{n} (y_i – (\beta_{0} + \beta_{1}x_{i1} + … + \beta_{1}x_{ik}))^{2}
\end{align}
$$

正規分布の最尤推定＝最小二乗法

最小二乗法は「残差ベクトル$e$と誤差の二乗和」で確認した誤差二乗和の$e^{\mathrm{T}}e$が最小になるような$\beta$をパラメータの推定量と考える手法である。ここで「最小二乗法」によって導出される結果が「正規分布の最尤推定」の結果に一致することを以下に示す。

観測値を元に作成する計画行列$X \in \mathbb{R}^{n \times (k+1)}$と$X$に対応する$y \in \mathbb{R}^{n}$に対し、パラメータのベクトル$\beta$に関する尤度関数$L(\beta)$は$y$に関する同時確率密度関数を元に下記のように定義される。
$$
\large
\begin{align}
L(\beta) &= f(y|X,\beta,\sigma^2) \\
&= \frac{1}{(2 \pi \sigma^2)^{n/2}} \exp \left( -\frac{1}{2 \sigma^2}(y – X \beta)^{\mathrm{T}} (y – X \beta) \right) \\
&= \exp \left( -\frac{1}{2 \sigma^2}(y – X \beta)^{\mathrm{T}} (y – X \beta) – \frac{n}{2}\log{(2 \pi \sigma^2)} \right)
\end{align}
$$

上記に対して「$L(\beta)$が$\beta$に関して最大 $\iff$ $\log{L(\beta)}$が$\beta$に関して最大」である。このとき$\log{L(\beta)}$は下記のように表すことができる。
$$
\large
\begin{align}
\log{L(\beta)} &= \log \left[ \exp \left( -\frac{1}{2 \sigma^2}(y – X \beta)^{\mathrm{T}} (y – X \beta) – \frac{n}{2}\log{(2 \pi \sigma^2)} \right) \right] \\
&= -\frac{1}{2 \sigma^2}(y – X \beta)^{\mathrm{T}} (y – X \beta) – \frac{n}{2}\log{(2 \pi \sigma^2)}
\end{align}
$$

上記の$\beta$に関する最大化を考えることは$e^{\mathrm{T}}e = (y – X \beta)^{\mathrm{T}} (y – X \beta)$の$\beta$に関する最小化を考えることに一致することが式より確認できる。

よって、「最小二乗法」によって導出される結果が「正規分布の最尤推定」の結果に一致することが示される。

ベクトル・行列に関する微分の公式

・$a^{\mathrm{T}}b$の微分
$$
\large
\begin{align}
\left(\begin{array}{c} \frac{\partial}{\partial a_{1}} \\ \vdots \\ \frac{\partial}{\partial a_{q}} \end{array} \right) a^{\mathrm{T}}b &= \left(\begin{array}{c} \frac{\partial}{\partial a_{1}} \\ \vdots \\ \frac{\partial}{\partial a_{q}} \end{array} \right) \sum_{k=1}^{p} a_{k} b_{k} \\
&= \left(\begin{array}{c} b_{1} \\ \vdots \\ b_{q} \end{array} \right) = b
\end{align}
$$

・対称行列$C$に関して$a^{\mathrm{T}}Ca$の微分
$$
\large
\begin{align}
\left(\begin{array}{c} \frac{\partial}{\partial a_{1}} \\ \vdots \\ \frac{\partial}{\partial a_{q}} \end{array} \right) a^{\mathrm{T}}Ca &= 2 \left(\begin{array}{ccc} c_{11} & \cdots & c_{1q} \\ \vdots & \ddots & \vdots \\ c_{q1} & \cdots & c_{qq} \end{array} \right) \left(\begin{array}{c} a_{1} \\ \vdots \\ a_{q} \end{array} \right) \\
&= 2Ca
\end{align}
$$

詳しい導出は「現代数理統計学（学術図書出版社）」の章末課題$11.2$で取り扱った。

対称行列$X^{\mathrm{T}}X$の半正定値性

「特異値分解(SVD)」の「半正定値行列の固有値」で詳しく取り扱ったが、対称行列$X^{\mathrm{T}}X$は半正定値性を持つ。

正規方程式の導出

導出の詳細

「正規分布の最尤推定＝最小二乗法」の議論で、$\beta$に関する対数尤度$\log{L(\beta)}$は下記のように導出した。
$$
\large
\begin{align}
\log{L(\beta)} = -\frac{1}{2 \sigma^2}(y – X \beta)^{\mathrm{T}} (y – X \beta) – \frac{n}{2}\log{(2 \pi \sigma^2)}
\end{align}
$$

上記は$\beta^{\mathrm{T}} X^{\mathrm{T}} y, y^{\mathrm{T}} X \beta$がどちらもスカラーであり$\beta^{\mathrm{T}} X^{\mathrm{T}} y = y^{\mathrm{T}} X \beta$が成立することに基づいて下記のように変形できる。
$$
\large
\begin{align}
\log{L(\beta)} &= -\frac{1}{2 \sigma^2}(y – X \beta)^{\mathrm{T}} (y – X \beta) – \frac{n}{2}\log{(2 \pi \sigma^2)} \\
&= -\frac{1}{2 \sigma^2}(y^{\mathrm{T}}y – y^{\mathrm{T}} X \beta – \beta^{\mathrm{T}}X^{\mathrm{T}}y + \beta^{\mathrm{T}} X^{\mathrm{T}} X \beta) – \frac{n}{2}\log{(2 \pi \sigma^2)} \\
&= -\frac{1}{2 \sigma^2}(y^{\mathrm{T}}y – 2 \beta^{\mathrm{T}}X^{\mathrm{T}}y + \beta^{\mathrm{T}} X^{\mathrm{T}} X \beta) – \frac{n}{2}\log{(2 \pi \sigma^2)}
\end{align}
$$

上記に対してベクトル$\displaystyle \beta = \left(\begin{array}{c} \beta_{0} \\ \vdots \\ \beta_{p} \end{array} \right)$での微分を考える。
$$
\large
\begin{align}
\left(\begin{array}{c} \frac{\partial}{\partial \beta_{0}} \\ \vdots \\ \frac{\partial}{\partial \beta_{p}} \end{array} \right) \log{L(\beta)} = 2 X^{\mathrm{T}} X \beta – 2 X^{\mathrm{T}}y
\end{align}
$$

上記が零ベクトルに一致する$\beta$を$\hat{\beta}$とおくと、$\hat{\beta}$は下記のように表すことができる。
$$
\large
\begin{align}
2 X^{\mathrm{T}} X \hat{\beta} – 2 X^{\mathrm{T}}y &= 0 \\
X^{\mathrm{T}} X \hat{\beta} &= X^{\mathrm{T}}y \\
\hat{\beta} &= (X^{\mathrm{T}} X)^{-1} X^{\mathrm{T}}y
\end{align}
$$

ここで$\hat{\beta}$の導出に用いた$X^{\mathrm{T}} X \beta = X^{\mathrm{T}}y$を正規方程式(normal equation)とよぶ。また、上記の$\hat{\beta}$は最尤推定量に一致する。

・参考
「現代数理統計学（学術図書出版社）」 章末課題$11.3$

正規方程式の直感的理解

正規方程式の直感的な理解を行うにあたって、$y_i = \beta_{0} + \beta_{1} x_i$の式に対し、そのまま偏微分を行うパターンと$y = X \beta$を用いるパターンの$2$通りで導出を行い、それぞれの式の確認を行う。

・$y_i = \beta_{0} + \beta_{1} x_i$の微分
$y_i = \beta_{0} + \beta_{1} x_i$に関しては誤差の関数$E(\beta_{0},\beta_{1})$は下記のように表される。
$$
\large
\begin{align}
E(\beta_{0},\beta_{1}) = \sum_{i=1}^{n} (y_{i} – (\beta_{0} + \beta_{1} x_i))^2
\end{align}
$$

ここで上記の$E(\beta_{0},\beta_{1})$に対し、$\beta_{0},\beta_{1}$で偏微分を行うとそれぞれ下記のように計算できる。
$$
\large
\begin{align}
\frac{\partial E(\beta_{0},\beta_{1})}{\partial \beta_{0}} &= – 2 \sum_{i=1}^{n} (y_{i} – (\beta_{0} + \beta_{1} x_i)) \\
\frac{\partial E(\beta_{0},\beta_{1})}{\partial \beta_{1}} &= – 2 \sum_{i=1}^{n} (y_{i} – (\beta_{0} + \beta_{1} x_i)) x_i
\end{align}
$$

上記が$0$に一致すると考えるとき、それぞれの式は下記のように整理できる。
$$
\large
\begin{align}
\frac{\partial E(\beta_{0},\beta_{1})}{\partial \beta_{0}} &= 0 \\
– 2 \sum_{i=1}^{n} (y_{i} – (\beta_{0} + \beta_{1} x_i)) &= 0 \\
\sum_{i=1}^{n} (\beta_{0} + \beta_{1} x_i) &= \sum_{i=1}^{n} y_{i} \quad (1)
\end{align}
$$

$$
\large
\begin{align}
\frac{\partial E(\beta_{0},\beta_{1})}{\partial \beta_{1}} &= 0 \\
– 2 \sum_{i=1}^{n} (y_{i} – (\beta_{0} + \beta_{1} x_i)) x_i &= 0 \\
\sum_{i=1}^{n} (\beta_{0} x_i + \beta_{1} x_i^2) &= \sum_{i=1}^{n} x_{i}y_{i} \quad (2)
\end{align}
$$

・$y = X \beta$の微分
$y = X \beta$に関しては誤差の関数$E(\beta)$は下記のように表される。
$$
\large
\begin{align}
E(\beta) &= (y – X \beta)^{\mathrm{T}} (y – X \beta) \\
&= y^{\mathrm{T}}y – 2 \beta^{\mathrm{T}} X^{\mathrm{T}} y + \beta^{\mathrm{T}} X^{\mathrm{T}} X \beta
\end{align}
$$

ここで上記の$E(\beta)$に対し、ベクトル$\beta$で偏微分を行うと下記のように計算できる。
$$
\large
\begin{align}
\frac{\partial}{\partial \beta} E(\beta) = 2 X^{\mathrm{T}} X \beta – 2 X^{\mathrm{T}} y
\end{align}
$$

上記が$0$に一致すると考えるとき、それぞれの式は下記のように整理できる。
$$
\large
\begin{align}
\frac{\partial}{\partial \beta} E(\beta) &= 0 \\
2 X^{\mathrm{T}} X \beta – 2 X^{\mathrm{T}} y &= 0 \\
X^{\mathrm{T}} X \beta &= X^{\mathrm{T}} y \quad (3)
\end{align}
$$

・式の対応
ここで$(1),(2)$式を$(3)$式の形式で表すことを考える。
$$
\large
\begin{align}
\left(\begin{array}{c} \displaystyle \sum_{i=1}^{n} (\beta_{0} + \beta_{1} x_i) \\ \displaystyle \sum_{i=1}^{n} (\beta_{0} x_i + \beta_{1} x_i^2) \end{array} \right) &= \left(\begin{array}{c} \displaystyle \sum_{i=1}^{n} y_{i} \\ \displaystyle \sum_{i=1}^{n} x_{i}y_{i} \end{array} \right) \\
\left(\begin{array}{c} \displaystyle n \beta_{0} + \beta_{1} \sum_{i=1}^{n} x_i \\ \displaystyle \beta_{0} \sum_{i=1}^{n} x_i + \beta_{1} \sum_{i=1}^{n} x_i^2 \end{array} \right) &= \left(\begin{array}{c} \displaystyle \sum_{i=1}^{n} y_{i} \\ \displaystyle \sum_{i=1}^{n} x_{i}y_{i} \end{array} \right) \\
\left(\begin{array}{c} n & \displaystyle \sum_{i=1}^{n} x_i \\ \displaystyle \sum_{i=1}^{n} x_i & \displaystyle \sum_{i=1}^{n} x_i^2 \end{array} \right) \left(\begin{array}{c} \beta_{0} \\ \beta_{1} \end{array} \right) &= \left(\begin{array}{ccc} 1 & \cdots & 1 \\ x_1 & \cdots & x_n \end{array} \right) \left(\begin{array}{c} y_{1} \\ \vdots \\ y_{n} \end{array} \right) \\
\left(\begin{array}{ccc} 1 & \cdots & 1 \\ x_1 & \cdots & x_n \end{array} \right) \left(\begin{array}{cc} 1 & x_1 \\ \vdots & \vdots \\ 1 & x_n \end{array} \right) \left(\begin{array}{c} \beta_{0} \\ \beta_{1} \end{array} \right) &= \left(\begin{array}{ccc} 1 & \cdots & 1 \\ x_1 & \cdots & x_n \end{array} \right) \left(\begin{array}{c} y_{1} \\ \vdots \\ y_{n} \end{array} \right) \\
X^{\mathrm{T}} X \beta &= X^{\mathrm{T}} y
\end{align}
$$

上記のように式の対応を考えることができる。よって、$X^{\mathrm{T}} X \beta = X^{\mathrm{T}} y$の形で表される正規方程式は直感的には左辺が予測に基づく式、右辺が実測値に基づく式であるとそれぞれ解釈しておくと良い。

・参考
最小二乗法・相関係数・決定係数
https://www.hello-statisticians.com/explain-terms-cat/regression1.html

行列・線形代数を学ぶにあたって様々な行列の名称が出てきますが、正方行列、正則行列、正規行列、正定値行列、直交行列、対称行列、エルミート行列など数多くの名称が出てくるので抑えておくのがなかなか大変です。そこで当記事では行列の定義に関して取りまとめを行いました。

基本的な行列定義

正方行列(square matrix)

行と列の要素の数が同じ行列を正方行列(square matrix)という。$n$行$n$列の正方行列$A$は下記のように表すことができる。
$$
\large
\begin{align}
A &= (a_{ij}) \\
&= \left(\begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{array} \right)
\end{align}
$$

転置行列(transposed matrix)

$m$行$n$列の行列$A$に対して$A$の$(i,j)$要素と$(j,i)$要素を入れ替えてできる$n$行$m$列の行列を転置行列(transposed matrix)という。転置行列を$A^{\mathrm{T}}$とおくと、$A^{\mathrm{T}}$は下記のように表すことができる。
$$
\large
\begin{align}
A^{\mathrm{T}} &= (a_{ji}) \\
&= \left(\begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{array} \right)^{\mathrm{T}} \\
&= \left(\begin{array}{ccc} a_{11} & \cdots & a_{1m} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nm} \end{array} \right)
\end{align}
$$

随伴行列(adjoint matrix)

随伴行列は$A^{\dagger}$などで表す。行列$A$の随伴行列は$A$を転置し、その複素共役を取ったものが該当する。

行列の対称性に基づく行列の定義

対称行列(symmetric matrix)

エルミート行列

$A^{\dagger}$を随伴行列とするとき、$A=A^{\dagger}$が成立する$A$をエルミート行列という。
実対称行列の複素数に対する拡張版の概念である。

分散共分散行列

下記などで詳しく取り扱った。
https://www.hello-statisticians.com/explain-terms-cat/pca1.html

行列の直交性に基づく行列の定義

直交行列(orthogonal matrix)

ユニタリ行列(unitary matrix)

特異値分解(SVD; singular value decomposition)は行列を分解する手法の一つで、$n \times n$の行列にとどまらず$m \times n$の行列に用いることができます。当記事では特異値分解や関連する行列分解の手法に関して取りまとめを行いました。

特異値分解

特異値分解の概要

$$
\large
\begin{align}
\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{*}
\end{align}
$$

$m$行$n$列の行列$\mathbf{A}$に対して$m$行$m$列の$\mathbf{U}$、$m$行$n$列の$\mathbf{\Sigma}$、$m$行$n$列の$\mathbf{V}^{*}$を用いて上記のような分解を考えることができる。これを行列$\mathbf{A}$の特異値分解という。

ここで$\mathbf{\Sigma}$は$i$行$i$列の対角成分のみが値を持ち、他の値が$0$の行列である。また、$\mathbf{V}^{*}$は$\mathbf{V}$の随伴行列であるが、ここでは実数のみを考えることから以下転置行列の$\mathbf{V}^{T}$で表す。

$n \times n$対称行列の固有値分解

$n \times n$対称行列(square matrix)の$\mathbf{B}$に関して固有値分解を行うことを考える。まず、$n \times n$の単位行列を$\mathbf{I}_n$とおき、$\det(\mathbf{B}-\lambda \mathbf{E})$の相異なる解を値の大きい順に並べたものを$\lambda_1, \lambda_2, …, \lambda_n$のようにおく。このとき、$\lambda_i$は行列$\mathbf{B}$の固有値であり、$\lambda_i$に対応する固有ベクトルを$\mathbf{u}_i$のようにおくと固有値・固有ベクトルの定義より下記の式が成立する。
$$
\large
\begin{align}
\mathbf{B} \mathbf{u}_i = \lambda_i \mathbf{u}_i
\end{align}
$$

ここで固有値$\lambda_i$と固有ベクトル$\mathbf{u}_i$を用いて下記のように行列$\mathbf{\Lambda}, \mathbf{U}$を定義する。
$$
\large
\begin{align}
\mathbf{\Lambda} &= \left(\begin{array}{ccc} \lambda_{1} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda_{n} \end{array} \right) \\
\mathbf{U} &= \left(\begin{array}{ccc} \mathbf{u}_{1} & … & \mathbf{u}_{n} \end{array} \right)
\end{align}
$$

上記の$\mathbf{U}$は直交行列であり、$\mathbf{U}^{\mathrm{T}} \mathbf{U} = \mathbf{I}_{n}$が成立する。$\mathbf{U}$が直交行列となることは下記で詳しく取り扱った。

対称行列(symmetric matrix)の固有値と固有ベクトルの性質とその導出

このとき、$\mathbf{B}, \mathbf{\Lambda}, \mathbf{U}$に関して下記が成立する。
$$
\large
\begin{align}
\mathbf{B} \mathbf{U} &= \mathbf{U} \mathbf{\Lambda} \\
\mathbf{B} &= \mathbf{U} \mathbf{\Lambda} \mathbf{U}^{-1} \\
&= \mathbf{U} \mathbf{\Lambda} \mathbf{U}^{\mathrm{T}}
\end{align}
$$

$n \times n$対称行列$\mathbf{B}$の固有値分解は上記のように行うことができる。本稿の主題である特異値分解はこの固有値分解の拡張で理解することができる。

$\mathbf{A} \mathbf{A}^{\mathrm{T}}$・$\mathbf{A}^{\mathrm{T}} \mathbf{A}$の計算

$m$行$n$列の行列$\mathbf{A}$に対して$\mathbf{A} \mathbf{A}^{\mathrm{T}}$を考えるとこれは$m$行$m$列の対称行列となる。また、$\mathbf{A}^{\mathrm{T}} \mathbf{A}$を考えるとこれは$n$行$n$列の対称行列となる。

$$
\large
\begin{align}
\mathbf{A} = \left(\begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end{array} \right)
\end{align}
$$
以下、上記のように$3$行$2$列で定義した$\mathbf{A}$を元に$\mathbf{A} \mathbf{A}^{\mathrm{T}}$と$\mathbf{A}^{\mathrm{T}} \mathbf{A}$の行列をそれぞれ確認する。

・$\mathbf{A} \mathbf{A}^{\mathrm{T}}$
$$
\large
\begin{align}
\mathbf{A} \mathbf{A}^{\mathrm{T}} &= \left(\begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end{array} \right) \left(\begin{array}{cc} a_{11} & a_{21} \\ a_{12} & a_{22} \\ a_{13} & a_{23} \end{array} \right) \\
&= \left(\begin{array}{cc} a_{11}^2+a_{12}^2+a_{13}^2 & a_{11}a_{21}+a_{12}a_{22}+a_{13}a_{23} \\ a_{21}a_{11}+a_{22}a_{12}+a_{23}a_{13} & a_{11}^2+a_{12}^2+a_{13}^2 \end{array} \right) \\
&= \left(\begin{array}{cc} a_{11}^2+a_{12}^2+a_{13}^2 & a_{11}a_{21}+a_{12}a_{22}+a_{13}a_{23} \\ a_{11}a_{21}+a_{12}a_{22}+a_{13}a_{23} & a_{21}^2+a_{22}^2+a_{23}^2 \end{array} \right)
\end{align}
$$

・$\mathbf{A}^{\mathrm{T}} \mathbf{A}$
$$
\large
\begin{align}
\mathbf{A}^{\mathrm{T}} \mathbf{A} &= \left(\begin{array}{cc} a_{11} & a_{21} \\ a_{12} & a_{22} \\ a_{13} & a_{23} \end{array} \right) \left(\begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end{array} \right) \\
&= \left(\begin{array}{ccc} a_{11}^2+a_{21}^2 & a_{11}a_{12}+a_{21}a_{22} & a_{11}a_{13}+a_{21}a_{23} \\ a_{12}a_{11}+a_{22}a_{21} & a_{12}^2+a_{22}^2 & a_{12}a_{13}+a_{22}a_{23} \\ a_{13}a_{11}+a_{23}a_{21} & a_{13}a_{12}+a_{23}a_{22} & a_{13}^2+a_{23}^2 \end{array} \right) \\
&= \left(\begin{array}{ccc} a_{11}^2+a_{21}^2 & a_{11}a_{12}+a_{21}a_{22} & a_{11}a_{13}+a_{21}a_{23} \\ a_{11}a_{12}+a_{21}a_{22} & a_{12}^2+a_{22}^2 & a_{12}a_{13}+a_{22}a_{23} \\ a_{11}a_{13}+a_{21}a_{23} & a_{12}a_{13}+a_{22}a_{23} & a_{13}^2+a_{23}^2 \end{array} \right)
\end{align}
$$

上記の例では$\mathbf{A}$に対して$\mathbf{A} \mathbf{A}^{\mathrm{T}}, \mathbf{A}^{\mathrm{T}} \mathbf{A}$がそれぞれ対称行列となることが確認できる。

また、ここで考えた$m$行$n$列の行列$\mathbf{A}$に対する$\mathbf{A} \mathbf{A}^{\mathrm{T}}, \mathbf{A}^{\mathrm{T}} \mathbf{A}$はどちらも半正定値行列である。このことは任意の$m$次元ベクトル$\displaystyle \mathbf{x} = \left(\begin{array}{c} x_{1} \\ \vdots \\ x_{m} \end{array} \right)$と$n$次元ベクトル$\displaystyle \mathbf{y} = \left(\begin{array}{c} y_{1} \\ \vdots \\ y_{n} \end{array} \right)$に対して下記が成立することよりそれぞれ確認できる。
$$
\large
\begin{align}
\mathbf{x}^{\mathrm{T}} \mathbf{A} \mathbf{A}^{\mathrm{T}} \mathbf{x} &= (\mathbf{A}^{\mathrm{T}}\mathbf{x})^{\mathrm{T}} (\mathbf{A}^{\mathrm{T}} \mathbf{x}) \geq 0 \\
\mathbf{y}^{\mathrm{T}} \mathbf{A}^{\mathrm{T}} \mathbf{A} \mathbf{y} &= (\mathbf{A}\mathbf{y})^{\mathrm{T}} (\mathbf{A}\mathbf{y}) \geq 0
\end{align}
$$

半正定値行列の固有値

半正定値行列の固有値は非負である。

前項で示した$\mathbf{A} \mathbf{A}^{\mathrm{T}}, \mathbf{A}^{\mathrm{T}} \mathbf{A}$が半正定値行列であることより、$\mathbf{A} \mathbf{A}^{\mathrm{T}}, \mathbf{A}^{\mathrm{T}} \mathbf{A}$の固有値は非負であることを示すことができる。

また、分散共分散行列に関しても$\mathbf{x}^{\mathrm{T}} \mathbf{X}^{\mathrm{T}} \mathbf{X} \mathbf{x} = (\mathbf{X} \mathbf{x})^{\mathrm{T}} (\mathbf{X} \mathbf{x}) \geq 0$のような表し方ができることから、半正定値行列であることが確認できる。

分散共分散行列の数式表現の詳細はPCAの解説の際に関連で取り扱ったので、合わせてご確認ください。

以下、半正定値行列の固有値が非負であることを示す。

$n \times n$対称行列の固有値分解の内容に基づいて$\mathbf{B}=\mathbf{U} \mathbf{\Lambda} \mathbf{U}^{\mathrm{T}}$と表せると考えるとき、$\mathbf{x}^{\mathrm{T}}\mathbf{B}\mathbf{x}$は下記のように変形することができる。
$$
\large
\begin{align}
\mathbf{x}^{\mathrm{T}}\mathbf{B}\mathbf{x} &= \mathbf{x}^{\mathrm{T}} \mathbf{U} \mathbf{\Lambda} \mathbf{U}^{\mathrm{T}} \mathbf{x} \\
&= (\mathbf{U}^{\mathrm{T}} \mathbf{x})^{\mathrm{T}} \mathbf{\Lambda} (\mathbf{U}^{\mathrm{T}} \mathbf{x})
\end{align}
$$

ここで上記の式における$\mathbf{U}^{\mathrm{T}} \mathbf{x}$を$\mathbf{y} = \mathbf{U}^{\mathrm{T}} \mathbf{x}$のようにおくことを考える。このとき$\mathbf{y}^{\mathrm{T}}\mathbf{\Lambda}\mathbf{y} = \mathbf{x}^{\mathrm{T}}\mathbf{B}\mathbf{x} \geq 0$が成立するが、$\mathbf{\Lambda}$が対角行列であることから$\mathbf{\Lambda}$の全ての値が$0$以上でなければ$\mathbf{y}^{\mathrm{T}}\mathbf{\Lambda}\mathbf{y} \geq 0$は成立しない。

よって半正定値行列の固有値は非負であると考えることができる。

特異値分解の導出

$$
\large
\begin{align}
\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}}
\end{align}
$$

行列$\mathbf{A}$が上記のように表すことができるとき、直交行列$\mathbf{U}$と$\mathbf{V}$はそれぞれ$\mathbf{A} \mathbf{A}^{\mathrm{T}}$、$\mathbf{A}^{\mathrm{T}} \mathbf{A}$の固有ベクトルに基づく行列であることを以下に示す。

$$
\large
\begin{align}
\mathbf{A} \mathbf{A}^{\mathrm{T}} &= (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}}) (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}})^{\mathrm{T}} \\
&= \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}} \mathbf{V} \mathbf{\Sigma}^{\mathrm{T}} \mathbf{U}^{\mathrm{T}} \\
&= \mathbf{U} \mathbf{\Sigma} \mathbf{\Sigma}^{\mathrm{T}} \mathbf{U}^{\mathrm{T}}
\end{align}
$$

$$
\large
\begin{align}
\mathbf{A}^{\mathrm{T}} \mathbf{A} &= (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}})^{\mathrm{T}} (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}}) \\
&= \mathbf{V} \mathbf{\Sigma}^{\mathrm{T}} \mathbf{U}^{\mathrm{T}} \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}} \\
&= \mathbf{V} \mathbf{\Sigma}^{\mathrm{T}} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}}
\end{align}
$$

上記を$n \times n$対称行列の固有値分解の式と同様に考えることで$\mathbf{U}$が$\mathbf{A} \mathbf{A}^{\mathrm{T}}$の固有ベクトルに基づく行列であり、$\mathbf{V}$が$\mathbf{A}^{\mathrm{T}} \mathbf{A}$の固有ベクトルに基づく行列であることがわかる。

SVDと行列のノルム

行列のpノルム(p-norm)の定義・計算方法・計算例の確認

上記などを参考に行列$\mathbf{A} \in \mathbb{R}^{m \times n}$のフロベニウスノルムを$||\mathbf{A}||_{F}$、$2$-normを$||\mathbf{A}||_{2}$とおく。このときSVDにおける対角行列(diagonal matrix)$\mathbf{\Sigma} = \mathrm{diag}(\sigma_{1}, \cdots \sigma_{p}), \, p = \min{(m, n)}$の最大成分を$\sigma_{\max}$とおくと、$||\mathbf{A}||_{F}$と$||A||_{2}$は下記のように表される。
$$
\large
\begin{align}
|\mathbf{A}||_{F} &= \sqrt{\sigma_{1}^{2} + \cdots \sigma_{p}^{2}} \quad (1) \\
||\mathbf{A}||_{2} &= \sigma_{\max} \quad (2)
\end{align}
$$

フロベニウスノルムについては次節でも取り扱った。

$(1)$式の導出

$\mathbf{A}=\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{T}$の$\mathbf{U}$と$\mathbf{V}$が直交行列であることから下記が成立する。
$$
\large
\begin{align}
||\mathbf{A}||_{F} &= ||\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{T}||_{F} \\
&= ||\mathbf{\Sigma}||_{F}
\end{align}
$$

ここで$\mathbf{\Sigma}=\mathrm{diag}(\sigma_{1}, \cdots \sigma_{p})$より下記が成立する。
$$
\large
\begin{align}
||\mathbf{A}||_{F} &= ||\mathbf{\Sigma}||_{F} \\
&= \sqrt{\sigma_{1}^{2} + \cdots \sigma_{p}^{2}} \quad (1)
\end{align}
$$

$(2)$式の導出

$\mathbf{A}=\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{T}$の$\mathbf{U}$と$\mathbf{V}$が直交行列であることから下記が成立する。
$$
\large
\begin{align}
||\mathbf{A}||_{2} &= ||\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{T}||_{2} \\
&= ||\mathbf{\Sigma}||_{2}
\end{align}
$$

ここで$2$-normの定義より下記が成立する。
$$
\large
\begin{align}
||\mathbf{A}||_{2} &= ||\mathbf{\Sigma}||_{2} \\
&= \sigma_{\max} \quad (2)
\end{align}
$$

特異値分解の近似

前節では固有値分解の考え方に基づいて特異値分解の導出を確認したが、行列の行数や列数が大きい場合は固有値や固有ベクトルの計算が複雑になり、同様の計算を行うのは難しい。したがって実際に行列の分解を行うにあたっては近似的な手法が基本的に用いられる。

近似を考える際は$\mathbf{A}$の分解した行列を元に$\mathbf{A}$をどのくらい復元できるかと考えることで近似を評価すると考えれば良い。以下ではフロベニウスノルムによって近似を評価し、これに対して勾配法を適用することによって分解を行うベーシックな手順について取りまとめる。

フロベニウスノルム(Frobenius norm)

特異値分解の近似を考えるにあたっては、$\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}} = \mathbf{U}’ \mathbf{V}’$のような分解に対し、行列ノルムの$||\mathbf{A}-\mathbf{U}’ \mathbf{V}’||$を考え、与えられた$\mathbf{A}$に対してノルムを最小にするように$\mathbf{U}’, \mathbf{V}’$を繰り返し演算によって計算すれば良い。

このように行列のノルムを考える際のシンプルな考え方がフロベニウスノルム(Frobenius norm)である。$m$行$n$列の行列$\mathbf{A} = (a_{ij})$に関するフロベニウスノルム$|\mathbf{A}|_{F}$は下記のように定義できる。
$$
\large
\begin{align}
||\mathbf{A}||_{F} = \sqrt{ \sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij}^2 }
\end{align}
$$

フロベニウスノルムは行列の各要素の二乗の和を計算し、計算した二乗和に対して平方根を考えた値に一致する。フロベニウスノルムはヒルベルト＝シュミットノルム(Hilbert–Schmidt norm)ともいわれることも抑えておくと良い。

上記のフロベニウスノルムの定義から二つの行列$\mathbf{X}, \mathbf{Y}$の差の大小を考えるにあたって、$||\mathbf{X}-\mathbf{Y}||_{F}^{2}$を用いて考えることは妥当であると思われる。

勾配降下法による近似

前項までの内容を元に考えると、$||\mathbf{A}-\mathbf{\tilde{U}}
\mathbf{\tilde{V}}||_{F}^{2}$を最小にする$\mathbf{\tilde{U}}, \mathbf{\tilde{V}}$を計算することで特異値分解を行うことができることがわかる。

$\mathbf{\tilde{U}}$全体に関する勾配を$\nabla_{\mathbf{\tilde{U}}} ||\mathbf{A}-\mathbf{\tilde{U}}\mathbf{\tilde{V}}||_{F}^{2}$とおくと、$\nabla_{\mathbf{U}’} ||\mathbf{A}-\mathbf{\tilde{U}} \mathbf{\tilde{V}}||_{F}^{2}$は下記のように計算できる。
$$
\large
\begin{align} \nabla_{\mathbf{\tilde{U}}} ||\mathbf{A}-\mathbf{\tilde{U}}
\mathbf{\tilde{V}}||_{F}^{2} = -(\mathbf{A}-\mathbf{\tilde{U}}
\mathbf{\tilde{V}}) \mathbf{\tilde{V}}^{\mathrm{T}}
\end{align}
$$

同様に$\mathbf{\tilde{V}}$全体に関する勾配を$\nabla_{\mathbf{\tilde{V}}} ||\mathbf{A}-\mathbf{\tilde{U}}\mathbf{\tilde{V}}||_{F}^{2}$とおくと、$\nabla_{\mathbf{\tilde{V}}} ||\mathbf{A}-\mathbf{\tilde{U}} \mathbf{\tilde{V}}||_{F}^{2}$は下記のように計算できる。
$$
\large
\begin{align} \nabla_{\mathbf{\tilde{V}}} ||\mathbf{A}-\mathbf{\tilde{U}}
\mathbf{\tilde{V}}||_{F}^{2} = -\mathbf{A}^{\mathrm{T}} \mathbf{\tilde{U}} + \mathbf{\tilde{V}} \mathbf{\tilde{U}}^{\mathrm{T}} \mathbf{\tilde{U}}
\end{align}
$$

上記の導出は「関係データ学習」の$4.4.1$節の「$1$次交互勾配降下法」で取り扱われているので、詳しくはそちらを参照ください。

$l^{2}$正則化と勾配降下法

参考

・実$2$次形式と正定値行列
https://www.chaos.cs.tsukuba.ac.jp/ila/chapter5.pdf
・特異値分解とその応用
https://www.chaos.cs.tsukuba.ac.jp/ila/chapter7.pdf
・関係データ学習

超幾何分布(Hypergeometric distribution)は$2$種からなる有限の集団から無作為非復元サンプリングを行う際に考える分布である。当記事では超幾何分布の定義や期待値・分散の導出、有限母集団修正の修正項の導出に関して取り扱った。
「基礎統計学Ⅰ 統計学入門(東京大学出版会)」の$6.1$節の「超幾何分布」や「統計学実践ワークブック」の$5$章の「離散型分布」を参考に作成を行なった。

・離散確率分布まとめ
https://www.hello-statisticians.com/explain-terms-cat/probdist1.html

超幾何分布の定義とその理解

超幾何分布の定義

$2$種の$A,B$から構成される$N$個の集団があり、$A,B$はそれぞれ$M, N-M$個であると考えるとき、この集団から$n$個取り出したとき、$A$の個数を確率変数$Y$で表すと考える。このとき、$n$個を取り出す際に復元抽出(sampling with replacement)を行う場合は$Y$は二項分布$\displaystyle \mathrm{Bin} \left( n,\frac{M}{N} \right)$に従う一方で、非復元抽出(sampling without replacement)を行う場合は$Y$は超幾何分布$\mathrm{HyperGeo}(N,M,n)$に従う。

以下、非復元抽出の場合を考えるにあたって、超幾何分布の確率関数を$P(Y=y|N,M,n)$とおくと、$P(Y=y|N,M,n)$は下記のように表される。
$$
\large
\begin{align}
P(Y=y|N,&M,n) = \frac{{}_M C_{y} \times {}_{N-M} C_{n-y}}{{}_{N} C_{n}} \\
{}_a C_b &= 0, \quad if \quad a<b \quad or \quad b<0
\end{align}
$$

上記の式の解釈にあたっては、「集団全体の$N$から$n$個抽出する組み合わせ」と「($A$に関して$M$から$y$個抽出する組み合わせ) × ($B$に関して$N-M$から$n-y$個抽出する組み合わせ)」の割合であると考えると良い。またここでの問題の定義より、${}_a C_b$に対して$a < b$と$b < 0$が成立するときはないので${}_a C_b = 0$と定義した。元の定義上は$a, b$の定義域を定める方が直接的だが、$a < b$と$b < 0$のときは${}_a C_b = 0$と定める方が取り扱いがシンプルになるのでこの式の形で抑えておく方がわかりやすいと思われる。

超幾何分布に基づく具体的な確率の確認

以下、「基礎統計学Ⅰ 統計学入門(東京大学出版会)」の例に基づいて確認を行う。$N=1000, M=200, n=5$のとき$Y=0, Y=1$のときの確率関数$P(Y=0|N=1000,M=200,n=5), P(Y=1|N=1000,M=200,n=5)$の計算をそれぞれ行う。

・$P(Y=0|N=1000,M=200,n=5)$
$$
\large
\begin{align}
P(Y=0|&N=1000,M=200,n=5) = \frac{{}_{200} C_{0} \times {}_{1000-200} C_{5-0}}{{}_{1000} C_{5}} \\
&= \frac{800 \cdot 799 \cdot 798 \cdot 797 \cdot 796}{5!} \times \frac{5!}{1000 \cdot 999 \cdot 998 \cdot 997 \cdot 996} \\
&= 0.326859…
\end{align}
$$

・$P(Y=1|N=1000,M=200,n=5)$
$$
\large
\begin{align}
P(Y=1|&N=1000,M=200,n=5) = \frac{{}_{200} C_{1} \times {}_{1000-200} C_{5-1}}{{}_{1000} C_{5}} \\
&= \frac{200}{1!} \times \frac{800 \cdot 799 \cdot 798 \cdot 797}{4!} \times \frac{5!}{1000 \cdot 999 \cdot 998 \cdot 997 \cdot 996} \\
&= 0.410626…
\end{align}
$$

超幾何分布を用いた資源調査

超幾何分布の期待値・分散の計算と有限母集団修正

$i$回目の抽出でグループ$A$を引いた場合に$X_i=1$、グループ$B$を引いた場合に$X_i=0$のように確率変数$X_i$を定義する。このとき確率変数$Y$は$Y = X_1 + X_2 + \cdots + X_n$のように表せることに基づいて超幾何分布の期待値$E[Y]$や分散$V[Y]$の導出を行える。

超幾何分布の期待値$E[Y]$の計算

$E[X_i]$は次のように表せる。
$$
\large
\begin{align}
E[X_i] &= 0 \cdot P(X_i=0) + 1 \cdot P(X_i=1) \\
&= P(X_i=1) \\
&= \frac{M}{N}
\end{align}
$$

よって、超幾何分布の期待値$E[Y]$は下記のように考えることができる。
$$
\large
\begin{align}
E[Y] &= E[X_1 + X_2 + \cdots + X_n] \\
&= nE[X_i] \\
&= \frac{nM}{N}
\end{align}
$$

超幾何分布の分散$V[Y]$の計算

$E[X_i^2], E[X_iX_j], \, i \neq j$は次のように表せる。
$$
\large
\begin{align}
E[X_i^2] &= 0^2 \cdot P(X_i=0) + 1^2 \cdot P(X_i=1) \\
&= P(X_i=1) \\
&= \frac{M}{N} \\
E[X_iX_j] &= 0 \cdot (P(X_i=0,X_j=0)+P(X_i=1,X_j=0)+P(X_i=0,X_j=1)) + 1 \cdot P(X_i=1,X_j=1) \\
&= P(X_i=1,X_j=1) \\
&= \frac{M(M-1)}{N(N-1)}
\end{align}
$$

このとき、確率変数$X_i, X_j$に関して下記のように$V[X_i], \mathrm{Cov}(X_i,X_j)$が得られる。
$$
\large
\begin{align}
V[X_i] &= E[X_i^2] – E[X_i]^2 \\
&= \frac{M}{N} – \left( \frac{M}{N} \right)^2 \\
&= \frac{M(N-M)}{N^2} \\
\mathrm{Cov}(X_i,X_j) &= E[X_iX_j] – E[X_i]E[X_j] \\
&= \frac{M(M-1)}{N(N-1)} – \frac{M^2}{N^2} \\
&= \frac{MN(M-1)}{N^2(N-1)} – \frac{M^2(N-1)}{N^2(N-1)} \\
&= \frac{\cancel{M^2N} – MN – \cancel{M^2N} + M^2}{N^2(N-1)} \\
&= -\frac{M(N-M)}{N^2(N-1)}
\end{align}
$$

よって、超幾何分布の分散$V[Y]$は下記のように考えることができる。
$$
\large
\begin{align}
V[Y] &= V[X_1 + X_2 + \cdots + X_n] \\
&= nV[X_i] + 2 \cdot {}_{n} C_{2} \mathrm{Cov}(X_i,X_j) \\
&= nV[X_i] + n(n-1) \mathrm{Cov}(X_i,X_j) \\
&= \frac{nM(N-M)}{N^2} – \frac{n(n-1)M(N-M)}{N^2(N-1)} \\
&= \frac{nM(N-M)}{N^2(N-1)} [(N-\cancel{1})-(n-\cancel{1})] \\
&= \frac{nM(N-M)(N-n)}{N^2(N-1)} \\
&= n \cdot \frac{M}{N} \left( 1-\frac{M}{N} \right) \times \frac{N-n}{N-1}
\end{align}
$$

有限母集団修正

「復元抽出」の場合は二項分布を元に考えることができる。$Z \sim \mathrm{Bin}(n,p)$の分散を$V[Z]$とおくと$V[Z]=np(1-p)$のように表せる。ここで$p=M/N$のように表すとき、$V[Z]$は下記のように表せる。
$$
\large
\begin{align}
V[Z] &= np(1-p) \\
&= n \cdot \frac{M}{N} \left( 1-\frac{M}{N} \right)
\end{align}
$$

このとき$V[Y]/V[Z]$は下記のように計算できる。
$$
\large
\begin{align}
\frac{V[Y]}{V[Z]} = \frac{N-n}{N-1}
\end{align}
$$

上記が有限母集団修正にあたっての修正項に一致する。

参考

・統計学実践ワークブック$5$章： 離散型分布
・統計学実践ワークブック$5$章： 問題$5.3$

機械学習(machine leanring)の大別にあたって「教師あり学習(Supervised Learning)」、「教師なし学習(Unsupervised Learning)」、「強化学習(Reinforcement Learning)」の三つが挙げられることが多いですが、入門コンテンツの多くはミスリードになるような解説が多く、特に「教師なし学習」に関して論文などで調査を行う際などにわからなくなる場合があります。当記事ではその解決にあたって、それぞれの定義に関して詳しく確認を行います。

基本的な考え方

「教師あり学習(Supervised Learning)」、「教師なし学習(Unsupervised Learning)」、「強化学習(Reinforcement Learning)」の三つが機械学習の大別に挙げられることが多いですが、「教師なし学習」を「クラスタリング」などのアルゴリズムと対応させて解説を行うことでミスリードになりやすいので注意が必要です。このような解説がなされることで「教師あり/教師なし」に対応してそれぞれアルゴリズムがあると考えがちですが、この考え方は適切ではありません。

「教師あり/教師なし」に対応するのは「アルゴリズム・学習の仕組み」ではなく、「前処理も含んだ処理全体」です。たとえばDeep Learningを考えた際に、下記のようにそれぞれ「教師あり学習」、「教師なし学習」、「強化学習」の三つの考え方が対応します。

・教師あり学習
-> ImageNetの分類 etc
・教師なし学習
-> Auto Encoder、GAN、BERT etc
・強化学習
-> Deep Q-Network etc

上記のようにDeep Learningを考えた際に「教師あり学習」、「教師なし学習」、「強化学習」の三パターンを考えられることから、「ニューラルネットワーク」のような「学習の仕組み」に基づいて三つの大別を行うことができません。

ここでDeepLearningなどを考える際によく出てくるのが「人間がアノテーションを与えるかどうか」という視点です。たとえばImageNetの分類では画像$X$に対し、正解ラベル$y$を人間が作成し学習を行いますが、Auto EncoderやGANは画像$X$があれば学習を行うことができます。

上図で「通常の教師あり学習」と「教師なし学習に対応するAuto Encoder」を元に具体的な図示を行いましたが、ニューラルネットワークの入力はどちらも$X$である一方で、出力は人間がラベル付けを行なった(human made)$y$と、入力と同様な$X$でそれぞれ異なります。

ここで着目すべきは手法自体はどちらもニューラルネットワークである一方で、出力にラベルを与えたかどうかで「教師あり/教師なし」を判断する場合も多いことです。したがって「ニューラルネットワーク」のような「学習のアルゴリズム」で判断するよりはfit(X,y)と書くかfit(X)と書くかのように関数のように理解する方が良いと思います。fit(X)と書く場合は「教師なし学習」と考える一方で、内部で教師に該当するyを生成しfit(X,y)を実行する場合もあり、この場合はfit(X)の視点で見れば「教師なし学習」、fit(X,y)の視点で見れば「教師あり学習」のように考えることができると思います。

次節で「教師なし学習」を詳しく確認するにあたってBERTの事前学習(pre-training)を取り扱いますが、BERTのMLM(Masked Language Modeling)を題材にすることで「教師なし学習」がより理解できると思います。

ここまで「教師あり/教師なし」に関して確認を行いましたが、「強化学習」も同様に「強化学習に対応するアルゴリズムがある」というよりは、$X$の代わりにエージェントと呼ばれるプレイヤーを定義して学習を行う場合を「強化学習」と呼ぶという理解の方が良いと思います。

強化学習に関しても詳しく確認すると難しくなるので、詳細は次節で確認を行います。

詳細

教師あり学習

教師なし学習

前節では$X$をニューラルネットワークの入力と出力に用いるAuto Encoderを元に「教師なし学習」を確認しましたが、当項ではBERTの事前学習(pre-training)を例に「教師を乱数を用いて”機械的に”作る」場合の確認を行います。

BERTの事前学習であるMLM(Masked Language Modeling)では文章に対応する系列を取り扱うDeepLearningの主流の手法であるTransformerに対し、一定確率でランダムに$X$にあたる入力を消去し、これを出力であてるというタスク設定を行います。

より具体的には$X = (x_1,x_2,x_3,x_4,…) = ($私, は, 本屋, に, 行った, 。, 教科書, を, 買った, 。$)$という文があった際に入力を$($私, は, MASK, に, 行った, 。, 教科書, を, 買った, 。$)$に変化させ、出力で「本屋」を予測するようなタスクをMLM(Masked Language Modeling)では取り扱うと理解すれば良いです。少々分かりにくいので図で表すと下記のように表すことができます。

ここで上記で表したMasked Language Modelingは入力$X$に対して$y$を予測している問題のようにも見えるので「教師あり学習」であると考えがちですが、出力にあたる「本屋」は乱数などを用いて作成したものであり人手でアノテーションを行なったわけではありません。

このような例もあるなど、DeepLearningを考える際には「教師あり/教師なし」という用語は単に「アノテーションを作成するコスト」に着目することが多いです。この解釈にあたっては、「ニューラルネットワーク」単体で見れば常にfit(X,y)であるのに対して、BERTのように前処理まで含めばfit(X)であり教師なし学習という見方ができるとわかりやすいのではないかと思います。

強化学習

強化学習(Reinforcement Learning)に関しては直感的にわかりやすい定義が少ないですが、意思決定主体のエージェント(Agent)を定義し「エージェントの最適行動を考える問題」と理解すると良いと思います。

もう少し詳しく考えると「エージェントが何らかの状態(state)を観測した際に意思決定(action)を行いその結果新しい状態と報酬を観測する場合、一連の意思決定に基づく報酬を最大化する意思決定を考える問題」と考えると良いです。

これに関連して上図のような図がよく用いられますが、この図を元に理解するにあたっては下記に注意すると良いです。

1) 強化学習は逐次的意思決定問題(Sequential Decision Making Problem)を取り扱う
-> 強化学習は系列処理の問題に意思決定の概念を導入し、意思決定によって発生する報酬を元に意思決定方針の最適化を考えると理解しやすいです。図の理解にあたっては1つの時点における意思決定に関連する報酬のみを表示しており、実際は逐次処理の一部であることには注意が必要です。
より具体的には「テレビゲームを行う際に、画面を見てコントローラーでコマンドを入力し、状況が遷移する際に報酬が発生すれば獲得する」を1フレームと見た際に、この1フレームの概略が図に対応すると考えれば良いと思います。

2) 大まかに理解する際は環境(Environment)ではなくエージェント(Agent)ありきで考えるべき
-> 「強化学習には環境とエージェントがある」という解説がされやすいですが、方針の最適化を行うのは環境ではなくエージェントであることは注意しておくと良いです。環境は迷路や囲碁などのようにはっきり定まる場合もあればAtariゲームのように何らかの定義が必要な場合もあります。
したがって、大まかに把握する際はエージェントが自身を取り巻く環境に対し何らかの意思決定を行い報酬などの反応を通して方針を学習すると考えると良いです。

3) DeepLearningなどを用いる際はエージェントの意思決定をDeepLearningを用いて近似する
-> 1)、2)で取り扱ったように強化学習ではエージェントの最適行動方針を学習します。この考えに基づいてDeepLearningを導入するにあたっては、エージェントの最適な意思決定をDeepLearningでいかに近似するかがメインの課題になると理解しておくと良いと思います。

強化学習に関しては下記などで別途取りまとめを行なっているので下記も参考にしてみてください。
https://www.hello-statisticians.com/explain-terms-cat/reinforcement_learning1.html

また、下記のChapter$1$などに強化学習の定義に関してまとめられているので、専門的・学術的なリファレンスに用いる場合は下記を参照すると良いと思います。

その他

半教師あり学習(semi-supervised learning)

深層学習[第2版]の11.4節の内容を元に以下取りまとめます。半教師あり学習(semi-supervised learning)はラベル付きの訓練データ$\mathcal{D}_L$とラベルのない入力のみのデータ$\mathcal{D}_{UL}$がある際に両者を効果的に用いて目的タスクを学習する方法です。

半教師ありの手法に関しては、主に一致性正則化(consistency regularization)、擬似ラベル(pseudo label)、エントロピー最小化(entropy minimization)の$3$つの手法があるので以下それぞれに関して取りまとめを行います。

・一致性正則化(consistency regularization)
一致性正則化(consistency regularization)はラベルのないサンプルの$\mathbf{x}$を中身が変わらない範囲で$\mathbf{x} \to \mathbf{x}’$のように変動させるとき、予測結果が変わらないであろうことに基づく手法です。

関数$f$を元に出力の近似を行う際に出力の変化を測る尺度を$\delta(f(\mathbf{x}),f(\mathbf{x}’))$のようにおき、これに基づいて正則化項を構成し誤差関数に加えることで$\mathcal{D}_{UL}$に基づいて正則化を行うことができると考えることができます。

・擬似ラベル(pseudo label)
擬似ラベル(pseudo label)は先に$\mathcal{D}_L$を用いて教師ネットワーク$T$を学習させたのちに、$\mathcal{D}_{UL}$を教師ラベルを用いて分類し、生徒ネットワーク$S$を教師ネットワークの出力に基づいて学習させるという手法です。

・エントロピー最小化(entropy minimization)
エントロピー最小化(entropy minimization)はネットワークの出力結果の各クラスのスコアのエントロピー$\displaystyle – \sum_{k=1}^{K} f(\mathbf{x})_k \log{f(\mathbf{x})_k}$を最小にする手法です。予測結果の事後確率の分布が1つのクラスのみが大きくなるときエントロピーは小さくなるので、$\mathcal{D}_{UL}$の予測のエントロピーが小さくなるように学習させると考えると良いです。

まとめ

参考

・機械学習中級(筆者作成)
https://www.amazon.co.jp/gp/product/B08CRSY7XN/

・深層学習[第2版]

強化学習(Reinforcement Learning)は数式が多く一見難しそうに見えますが、統計学の確率分布の表記に慣れていれば実はそれほど難しくありません。そこで何回かにわけて強化学習の基本トピックに関して取り扱いを行います。
第$2$回は最適ベルマン方程式の導出にあたって用いる「動的計画法(Dynamic Programming)」を取り扱います。Richard S. Suttonの”Reinforcement Learning, second edition: An Introduction“のChapter$4$を参考に作成を行いました。

基本的な理論の確認

概要

動的計画法(Dynamic Programming)はマルコフ決定過程(MDP; Markov Decision Process)の完全な環境モデル(perfect model of environment)が与えられるとき最適方策(optimal policy)を計算するのに用いられる手法である。

ここで「完全な環境モデル(perfect model of environment)」は、第$1$回で取り扱った状態遷移確率(state-transition probabilities)の$p(s’,r|s,a) = P(S_{t+1}=s’,R_{t+1}=r|S_t=s,A_{t}=a)$が対応すると考えておけば良い。要するに状態$S_t$とエージェントの行動$A_t$が定まった際に、次の状態$S_{t+1}$と同時に発生する報酬$R_{t+1}$の確率分布が既知である場合をこのように考える。

この環境モデル(environment model)の考え方は「モデルフリー(model free)強化学習」と「モデルベース(model based)強化学習」にも関連する。「モデルベース(model based)強化学習」は近年ではalpha Goやalpha Zeroなどのボードゲームにおける強化学習でよく研究されており、環境モデルから最適方策を導出する方法をプランニング(planning)と表すことも抑えておくと良い。

動的計画法を考える際の主要な考え方は価値関数(value function)を「良い方策(good policy)」を探索する際に用いるということである。ここで用いる価値関数は第$1$回で確認したベルマン方程式(Bellman equation)の数式の形を用いる。
$$
\large
\begin{align}
v_{\pi}(s) &= \mathbb{E}_{\pi} [G_{t}|S_{t}(s)] \\
&= \mathbb{E}_{\pi} [R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_{t}(s)] \\
&= \sum_{a} \pi(a|s) \sum_{s’,r} p(s’,r|s,a) \left[ r + \gamma v_{\pi}(s’) \right] \quad (1)
\end{align}
$$

動的計画法のアルゴリズムは上記で表したベルマン最適方程式の式を用いて表現を行う。式の中に出てきた$\pi(a|s)$と$p(s’,r|s,a)$は期待値を考える際の確率分布と同様に理解しておくと良い。

より具体的には「動的計画法」に基づいて「方策評価」を行い、その「方策評価」に基づいて「方策反復法(Policy Iteration)」や「価値反復法(Value Iteration)」を構築し、繰り返し計算によって「最適方策」の計算を行う。

動的計画法の再確認

前項では「強化学習」における「動的計画法」の活用にあたっての概要を確認を行なったが、「強化学習」に関連して「動的計画法(Dynamic Programming)」の解説がなされることは少ないように思われる。

「動的計画法(Dynamic Programming)」に関してはWikipediaを元に考えるが、「対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称」と記載されている。

この具体例に「フィボナッチ数列」が紹介されているが、$a_5 = a_4 + a_3 = (a_3+a_2) + (a_2+a_1) = …$のように考えるのではなく、$a_2 = a_1 + a_0, a_3 = a_2 + a_1$のように考えることを動的計画法を用いたプログラムに挙げられている。

要するに、漸化式を元に$a_0, a_1, a_2, a_3, …$のように順に値を計算していくことを動的計画法(Dynamic Programming)と総称していると理解すると良いように思われる。

ここで次項で扱う「反復方策評価」は漸化式を元に値を順に計算する手法であるので、動的計画法に基づくと考えられる。

一方で「動的計画法」は多義的な表現であり、もう少し適切な表現の方があるようにも思われる。これに関しては、「ベルマン方程式」を考案したベルマン(Richard Ernest Bellman)が「動的計画法」も同時に発表していたことに起因すると思われる。

動的計画法に関しては「トップダウン方式(分割統治法)」と「ボトムアップ方式」の二つがあり、「分割統治法」をメインで紹介されることも多いのでこの辺はミスリードになる場合もあるように思われた。「ボトムアップ方式」は漸化式に関連する問題の解法を考えるにあたって直感的にそのまま用いる解法であるので、「動的計画法」に関して学ぶ際には既知である場合も多いと考えられるが、強化学習の動的計画法は単にシンプルな「ボトムアップ方式」を用いていると考えれば良いと思われる。

当項は単に筆者の考察であり、出典が存在しないのでご注意ください。また、関連する文献をご存知の方がおられたらご指摘ください。

・参考
動的計画法
リチャード・E・ベルマン
ベルマン方程式

反復方策評価(Iterative Policy Evaluation)

反復方策評価(Iterative Policy Evaluation)は$1.1$節の$(1)$式に対して動的計画法の考え方に基づいて繰り返し演算を適用する手法である。
$$
\large
\begin{align}
v_{k+1}(s) & \equiv \mathbb{E}_{\pi} [R_{t+1} + \gamma v_{k}(S_{t+1})|S_{t}(s)] \\
&= \sum_{a} \pi(a|s) \sum_{s’,r} p(s’,r|s,a) \left[ r + \gamma v_{k}(s’) \right] \quad (2)
\end{align}
$$

反復方策評価は具体的には上記で表した繰り返し演算に基づいて価値関数の$v_{\pi}(s)$の近似を行う。ここで$S_{t}=s \to S_{t+1}=s’$が状態の変化を表す一方で、$k \to k+1$は価値関数の変化を表すことに注意が必要である。

方策改善(Policy Improvement)

反復方策評価によって価値関数$v_{\pi}$が収束した際に、価値関数に基づいて方策を改善することが必要になる。この一連の流れを方策改善(Policy Improvement)という。

方策改善は方策改善定理(Policy Improvement Theorem)に基づいており、価値関数に基づいて方策を改善することは既存の方策が最適でない限りは既存のものよりもより良い方策が得られるという考え方である。

方策反復法(Policy Iteration)

方策反復法は方策評価(Policy Evaluation)と方策改善(Policy Improvement)を繰り返す手法である。アルゴリズムは下記のように表される。

上記の一連の処理を方策反復法(Policy Iteration)という。一連の流れは下記のようにも概略を表すことができる。
$$
\large
\begin{align}
\pi_0 \to v_{\pi_0} \to \pi_1 \to v_{\pi_1} \to … \to \pi_{*} \to v_{\pi_{*}}
\end{align}
$$

価値反復法(Value Iteration)

まとめ

具体例の確認