Boltzmann Machineの基礎

はじめに

Boltzmann Machineについてまとめる。

目的

　幅 $w$、高さ $h$ の白黒画像を考える。各画素の値 0 と 255 を -1 と 1 で表し、画像の左上から右下に向かって画素値を並べると、1つの $n$ 次元ベクトル ${\bf x}$ (観測値)となる。ここで、$n=w\times h$ とした。$N$ 枚の画像があれば、$N$ 個の $n$ 次元ベクトル ${\bf x}^{\mu},\;\mu=1,\cdots,N$ を得ることができる。いま、確率分布 $P({\bf X}|\Theta)$ を適当に仮定する。ここで、${\bf X}=\left\{X_{i}\in \left\{-1,1\right\} |\; i=1,\cdots,n \right\}$ は $n$ 次元の確率変数、$\Theta$ は適当なパラメータの集合を表す。観測値 ${\bf x}^{\mu}$ は、確率分布 $P({\bf X}|\Theta)$ に従ってサンプルされた1つの実現値であると解釈する。パラメータ $\Theta$ を調節し、観測値 ${\bf x}^{\mu}$ が従う確率分布 $P({\bf X}|\Theta)$を求めることがここでの目的である。

Boltzmann 分布

　確率分布 として次のBoltzmann 分布を仮定する。 \begin{equation} P_{B}({\bf X}|{\boldsymbol \theta}, {\boldsymbol \omega}) = \frac{1}{ Z_{B}({\boldsymbol \theta}, {\boldsymbol \omega}) } \exp\left[-\Phi({\bf X}|{\boldsymbol \theta}, {\boldsymbol \omega})\right] \label{boltzmann} \end{equation} ここで、$Z_{B}({\boldsymbol \theta}, {\boldsymbol \omega})$ は次式で定義される規格化因子（統計物理学に於ける分配関数）である。 \begin{equation} Z_{B}({\boldsymbol \theta}, {\boldsymbol \omega})=\sum_{X_1=\pm1}\cdots \sum_{X_n=\pm1}\;\exp\left[-\Phi({\bf X}|{\boldsymbol \theta}, {\boldsymbol \omega})\right] \end{equation} また、$\Phi({\bf X}|{\boldsymbol \theta}, {\boldsymbol \omega})$ はエネルギー関数と呼ばれ、次式で定義される。 \begin{equation} \Phi({\bf X}|{\boldsymbol \theta}, {\boldsymbol \omega}) = -\sum_{i\in \Omega}\;\theta_{i}\;X_{i} - \sum_{(i,j)\in E} \omega_{ij}\;X_{i}\;X_{j} \end{equation} $\Omega$ は全画素の集合、$E$ は隣接画素の集合である。エネルギー関数は2つのことを表現している。

1. $\theta_i > 0$ なら、画素値が1である画素が多いほど第1項は小さくなる。$\theta_i < 0$なら、画素値が-1である画素が多いほど第1項は小さくなる。
2. $\omega_{ij} > 0$ なら、画素値の等しい隣接画素が多いほど第2項は小さくなる。$\omega_{ij} < 0$ なら、画素値の異なる隣接画素が多いほど第2項は小さくなる。

第1項をバイアス項、第2項を相互作用項(平滑化項)と呼ぶ。式(\ref{boltzmann})の形から、エネルギーが低いほど確率は高くなることが分る。確率分布としてBoltzmann分布を仮定することにより、観測値 ${\bf x}^{\mu}$ の統計性を再現するように2つのパラメータ $({\boldsymbol \theta},{\boldsymbol \omega})$ を求める問題に帰着した。

最尤法

　全観測値 $D=\left\{{\bf x}^{\mu}\;|\;\mu=1,\cdots,N\right\}$ の出現確率は、各観測値の出現確率の積で与えられる。 \begin{equation} L_{D}({\boldsymbol \theta},{\boldsymbol \omega})=\prod_{\mu=1}^{N}\;P_{B}({\bf x}^{\mu}|{\boldsymbol \theta}, {\boldsymbol \omega}) \label{ld} \end{equation} ここで、確率変数 ${\bf X}$ ではなく観測値 ${\bf x}^{\mu}$ を使用していることに注意する。$L_{D}$ が最大となるようにパラメータ $({\boldsymbol \theta}, {\boldsymbol \omega})$ を決める手法を最尤法(Maximum Likelihood Estimation)と呼ぶ。実際の計算では、式(\ref{ld})の右辺の対数を取った量 \begin{equation} L_{D}({\boldsymbol \theta},{\boldsymbol \omega})=\sum_{\mu=1}^{N}\;\ln{P_{B}({\bf x}^{\mu}|{\boldsymbol \theta}, {\boldsymbol \omega})} \label{logld} \end{equation} の最大化を行う。
　$\theta_i$で微分し結果を0とおく。 \begin{eqnarray} \frac{\partial L_{D}({\boldsymbol \theta},{\boldsymbol \omega})}{\partial \theta_i}&=& \sum_{\mu}\;\frac{1}{P_{B}({\bf x}^{\mu}|{\boldsymbol \theta}, {\boldsymbol \omega})}\; \frac{\partial P_{B}({\bf x}^{\mu}|{\boldsymbol \theta}, {\boldsymbol \omega})}{\partial \theta_i}\nonumber\\ &=&0 \label{eq10} \end{eqnarray} いま、 \begin{eqnarray} \frac{\partial P_{B}({\bf x}^{\mu})}{\partial \theta_i}&=& -\frac{1}{Z_{B}^2}\; \frac{\partial Z_{B}}{\partial \theta_i}\;\exp\left[-\Phi({\bf x}^{\mu})\right] -\frac{1}{Z_B}\;\exp\left[-\Phi({\bf x}^{\mu})\right] \frac{\partial \Phi({\bf x}^{\mu})}{\partial \theta_i}\label{eq11} \\ \frac{\partial \Phi({\bf x}^{\mu})}{\partial \theta_i} &=&-x^{\mu}_i \label{eq12} \\ \frac{\partial Z_{B}}{\partial \theta_i} &=& \sum_{X_1=\pm1}\cdots \sum_{X_n=\pm1}\;X_i\exp\left[-\Phi({\bf X})\right] \label{eq13} \end{eqnarray} が成り立ち(余白の都合上、$({\boldsymbol \theta}, {\boldsymbol \omega})$を省略した)、式(\ref{eq12})(\ref{eq13})を式(\ref{eq11})に代入すると \begin{eqnarray} \frac{\partial P_{B}({\bf x}^{\mu})}{\partial \theta_i}&=& -\frac{1}{Z_{B}^2}\; \left\{ \sum_{X_1=\pm1}\cdots \sum_{X_n=\pm1}\;X_i\exp\left[-\Phi({\bf X})\right] \right\} \exp\left[-\Phi({\bf x}^{\mu})\right] \nonumber \\ &&\hspace{1cm}+\frac{1}{Z_B}\;\exp\left[-\Phi({\bf x}^{\mu})\right] x^{\mu}_i \nonumber \\ &=& -\frac{P_{B}({\bf x}^{\mu})}{Z_{B}}\; \left\{ \sum_{X_1=\pm1}\cdots \sum_{X_n=\pm1}\;X_i\exp\left[-\Phi({\bf X})\right] \right\} +P_{B}({\bf x}^{\mu})\; x^{\mu}_i \label{eq14} \end{eqnarray} を得る。式(\ref{eq14})を式(\ref{eq10})に代入して \begin{equation} \sum_{\mu}\; \frac{1}{Z_{B}}\; \left\{ \sum_{X_1=\pm1}\cdots \sum_{X_n=\pm1}\;X_i\exp\left[-\Phi({\bf X})\right] \right\} =\sum_{\mu}\; x^{\mu}_i \end{equation} を得る。左辺の$\mu$についての和は$N$に置き換えることができるから \begin{equation} \frac{1}{Z_{B}}\; \left\{ \sum_{X_1=\pm1}\cdots \sum_{X_n=\pm1}\;X_i\exp\left[-\Phi({\bf X})\right] \right\} =\frac{1}{N}\sum_{\mu}\; x^{\mu}_i \label{eq15} \end{equation} が成り立つ。 確率変数についての期待値を \begin{equation} E_B(v) = \frac{1}{Z_{B}}\; \left\{ \sum_{X_1=\pm1}\cdots \sum_{X_n=\pm1}\;v\;\exp\left[-\Phi({\bf X})\right] \right\} \end{equation} と表記すれば式(\ref{eq15})は \begin{equation} E_B(X_i) =\frac{1}{N}\sum_{\mu}\; x^{\mu}_i \label{boltzmann1} \end{equation} と書くことができる。ここで、観測値に対する経験分布を定義する。 \begin{equation} Q_{D}({\bf X}) = \frac{1}{N}\;\sum_{\mu}\;\delta({\bf X},\vec{x}^{\;\mu}) \label{empirical} \end{equation} すなわち、変数 ${\bf X}$ が観測値 $\vec{x}^{\;\mu}$ と一致した場合に $1/N$ を、それ以外の場合は0を返す関数である。 これを使うと式(\ref{boltzmann1})は \begin{equation} E_B(X_i) =\sum_{{\bf X}}\; Q_{D}({\bf X})\;X_i \label{boltzmann1-1} \end{equation} と書き換えることができる。 左辺は確率変数についての1次の期待値、右辺は観測値についての1次の期待値である。
　次に、$\omega_{ij}$で微分し結果を0とおく。 \begin{eqnarray} \frac{\partial L_{D}({\boldsymbol \theta},{\boldsymbol \omega})}{\partial \omega_{ij}}&=& \sum_{\mu}\;\frac{1}{P_{B}({\bf x}^{\mu}|{\boldsymbol \theta}, {\boldsymbol \omega})}\; \frac{\partial P_{B}({\bf x}^{\mu}|{\boldsymbol \theta}, {\boldsymbol \omega})}{\partial \omega_{ij}}\nonumber\\ &=&0 \label{eq16} \end{eqnarray} さらに、 \begin{eqnarray} \frac{\partial P_{B}({\bf x}^{\mu})}{\partial \omega_{ij}}&=& -\frac{1}{Z_{B}^2}\; \frac{\partial Z_{B}}{\partial \omega_{ij}}\;\exp\left[-\Phi({\bf x}^{\mu})\right] -\frac{1}{Z_B}\;\exp\left[-\Phi({\bf x}^{\mu})\right] \frac{\partial \Phi({\bf x}^{\mu})}{\partial \omega_{ij}}\label{eq17} \\ \frac{\partial \Phi({\bf x}^{\mu})}{\partial \omega_{ij}} &=&-x^{\mu}_i x^{\mu}_j \label{eq18} \\ \frac{\partial Z_{B}}{\partial \omega_{ij}} &=& \sum_{X_1=\pm1}\cdots \sum_{X_n=\pm1}\;X_i X_j\exp\left[-\Phi({\bf X})\right] \label{eq19} \end{eqnarray} が成り立つから、同様な計算を繰り返せば、 \begin{equation} E_B(X_i X_j) =\sum_{{\bf X}}\; Q_{D}({\bf X})\;X_i X_j \label{boltzmann2} \end{equation} を得る。左辺は確率変数についての2次の期待値、右辺は観測値についての2次の期待値である。式(\ref{boltzmann1-1})と(\ref{boltzmann2})をBoltzmannの学習方程式と呼ぶ。

計算量の爆発

　これまでの議論から、確率分布 $P_{B}({\bf X}|{\boldsymbol \theta}, {\boldsymbol \omega})$ を決めるには、次のBoltzmannの学習方程式を解けば良いことが分った。 \begin{eqnarray} E_B(X_i|{\boldsymbol \theta}, {\boldsymbol \omega}) &=&\frac{1}{N}\sum_{\mu=1}^{N}\; x^{\mu}_i \\ E_B(X_i X_j|{\boldsymbol \theta}, {\boldsymbol \omega}) &=&\frac{1}{N}\sum_{\mu=1}^{N}\; x^{\mu}_i x^{\mu}_j \end{eqnarray} ただし、 \begin{equation} E_B(v|{\boldsymbol \theta}, {\boldsymbol \omega}) = \frac{1}{Z_{B}}\; \left\{ \sum_{X_1=\pm1}\cdots \sum_{X_n=\pm1}\;v\;\exp\left[-\Phi({\bf X|{\boldsymbol \theta}, {\boldsymbol \omega}})\right] \right\} \end{equation} である。 学習方程式の右辺は観測値についての期待値であり計算は容易である。一方、左辺は確率変数の取り得る全ての値についての和であり、$2^n$個の項の和を計算しなければならない。 $n$は通常、1000や10000のオーダとなるので、厳密解を得ることは不可能である。

隠れ変数がある場合

　ここでは、何らかの理由により $n$ 個の画素のうち $m$ 個の画素が観測されない場合を考える。観測される画素値を可視変数、観測されない画素値を隠れ変数と呼び、それぞれ ${\bf V}$、${\bf H}$で表すことにする。すなわち ${\bf X}=({\bf V},{\bf H})$ である。画像中の可視画素の集合を $\Gamma$、隠れ画素の集合を $\Lambda$ とする。このとき、Boltzmann関数(\ref{boltzmann})は、 \begin{equation} P_{B}({\bf V}, {\bf H}|{\boldsymbol \Theta}) = \frac{1}{ Z_{B}({\boldsymbol \Theta}) } \exp\left[-\Phi({\bf V},{\bf H}|{\boldsymbol \Theta})\right] \label{boltzmann-0} \end{equation} と書くことができる。ただし、${\boldsymbol \Theta}=({\boldsymbol \theta}, {\boldsymbol \omega})$ とした。式変形が容易なように、統計物理学で使われる自由エネルギー $F$ を導入する。 \begin{equation} F({\bf V}|{\boldsymbol \Theta})= -\ln{ \left( \sum_{H_1=\pm1}\cdots\sum_{H_m\pm1}\; \exp \left[ -\Phi({\bf V},{\bf H}|{\boldsymbol \Theta}) \right] \right) } \label{free} \end{equation} $P_{B}({\bf V}, {\bf H}|{\boldsymbol \Theta})$ を隠れ変数について周辺化したものは、自由エネルギー $F$ を使って 書くことができる。 \begin{eqnarray} P_{V}({\bf V}|{\boldsymbol \Theta}) &\equiv& \sum_{H_1}\cdots\sum_{H_m}\;P_{B}({\bf V}, {\bf H}|{\boldsymbol \Theta}) \label{marginalvv}\\ &=&\frac{1}{Z_B({\boldsymbol \Theta})}\; \exp{ \left[ -F\left({\bf V}|{\boldsymbol \Theta}\right) \right] } \label{marginalv} \end{eqnarray} この式を使って次式を最大化することを考える。 \begin{equation} L_{D}({\boldsymbol \Theta})=\sum_{\mu=1}^{N}\;\ln{P_{V}(\vec{v}^{\;\mu}|{\boldsymbol \Theta})} \label{logld-0} \end{equation} ここで、$\vec{v}^{\;\mu}$ は可視変数の観測値である。 議論を一般化するため、パラメータ群 ${\boldsymbol \Theta}$ を代表するパラメータ $\xi$ を考え、これによる偏微分を 考える。 \begin{equation} \frac{\partial L_D}{\partial \xi} = 0 \Leftrightarrow E_V\left(\frac{\partial F({\bf V}|{\boldsymbol \Theta})}{\partial \xi} \right) = \frac{1}{N}\;\sum_{\mu}\; \frac{\partial F(\vec{v}^{\;\mu}|{\boldsymbol \Theta})}{\partial \xi} \label{general} \end{equation} ここで、${\bf V}$ についての期待値 \begin{equation} E_V(\nu)=\sum_{V_1}\cdots \sum_{V_n}\; \nu\;P_{V}({\bf V}|{\boldsymbol \Theta}) \end{equation} を定義した。式(\ref{general})の右辺を考える。 \begin{eqnarray} \frac{\partial F(\vec{v}^{\;\mu}|{\boldsymbol \Theta})}{\partial \xi} &=& \sum_{{\bf H}} \left\{ \frac{P_B(\vec{v}^{\;\mu}, {\bf H}|{\boldsymbol \Theta})}{\sum_{{\bf H}^{\prime}}\;P_B(\vec{v}^{\;\mu}, {\bf H}^{\prime}|{\boldsymbol \Theta})} \; \frac{\partial \Phi(\vec{v}^{\;\mu},{\bf H}|{\boldsymbol \Theta})}{\partial \xi} \right\} \nonumber \\ &=& \sum_{{\bf H}} \left\{ P_{H/V}({\bf H}|\vec{v}^{\;\mu}, {\boldsymbol \Theta}) \; \frac{\partial \Phi(\vec{v}^{\;\mu},{\bf H}|{\boldsymbol \Theta})}{\partial \xi} \right\} \end{eqnarray} 最後の式で、ベイズの公式 \begin{equation} P_{H/V}({\bf H}|\vec{v}^{\;\mu}, {\boldsymbol \Theta}) = \frac{P_B(\vec{v}^{\;\mu}, {\bf H}|{\boldsymbol \Theta})}{\sum_{{\bf H}^{\prime}}\;P_B(\vec{v}^{\;\mu}, {\bf H}^{\prime}|{\boldsymbol \Theta})} \end{equation} を使用した。さらに変形を続けると \begin{eqnarray} \frac{1}{N}\;\sum_{\mu}\; \frac{\partial F(\vec{v}^{\;\mu}|{\boldsymbol \Theta})}{\partial \xi} &=& \frac{1}{N}\;\sum_{\mu}\; \sum_{{\bf H}} \left\{ P_{H/V}({\bf H}|\vec{v}^{\;\mu}, {\boldsymbol \Theta}) \; \frac{\partial \Phi(\vec{v}^{\;\mu},{\bf H}|{\boldsymbol \Theta})}{\partial \xi} \right\} \\ &=& \sum_{{\bf V}} \sum_{{\bf H}} \left\{ P_{H/V}({\bf H}|{\bf V}, {\boldsymbol \Theta}) \; \frac{\partial \Phi({\bf V},{\bf H}|{\boldsymbol \Theta})}{\partial \xi} Q_D({\bf V}) \right\} \end{eqnarray} となる。最後の式で経験分布(\ref{empirical})を使用した。次に、式(\ref{general})の左辺を考える。 \begin{equation} \frac{\partial F({\bf V}|{\boldsymbol \Theta})}{\partial \xi} = \sum_{{\bf H}} \left\{ \frac{P_B({\bf V}, {\bf H}|{\boldsymbol \Theta})}{\sum_{{\bf H}^{\prime}}\;P_B({\bf V}, {\bf H}^{\prime}|{\boldsymbol \Theta})} \; \frac{\partial \Phi({\bf V},{\bf H}|{\boldsymbol \Theta})}{\partial \xi} \right\} \end{equation} したがって、 \begin{eqnarray} E_V\left(\frac{\partial F({\bf V}|{\boldsymbol \Theta})}{\partial \xi} \right) &=& \sum_{{\bf V}}\sum_{{\bf H}} P_B({\bf V},{\bf H}|{\boldsymbol \Theta}) \; \frac{\partial \Phi({\bf V},{\bf H}|{\boldsymbol \Theta})}{\partial \xi} \end{eqnarray} を得る。ただし、式(\ref{marginalvv})を使った。以上の議論から隠れ変数がある場合の学習方程式は \begin{equation} \sum_{{\bf V}}\sum_{{\bf H}} P_B({\bf V},{\bf H}|{\boldsymbol \Theta}) \; \frac{\partial \Phi({\bf V},{\bf H}|{\boldsymbol \Theta})}{\partial \xi} = \sum_{{\bf V}} \sum_{{\bf H}} \left\{ P_{H/V}({\bf H}|{\bf V}, {\boldsymbol \Theta}) \; \frac{\partial \Phi({\bf V},{\bf H}|{\boldsymbol \Theta})}{\partial \xi} Q_D({\bf V}) \right\} \end{equation} となる。　$\xi=(\theta_i, \omega_{ij})$ として、次式を得る。 \begin{eqnarray} \sum_{{\bf V}}\sum_{{\bf H}} P_B({\bf V},{\bf H}|{\boldsymbol \Theta}) \; X_i &=& \sum_{{\bf V}} \sum_{{\bf H}} \left\{ P_{H/V}({\bf H}|{\bf V}, {\boldsymbol \Theta}) \; X_i \;Q_D({\bf V}) \right\} \\ \sum_{{\bf V}}\sum_{{\bf H}} P_B({\bf V},{\bf H}|{\boldsymbol \Theta}) \; X_i\;X_j &=& \sum_{{\bf V}} \sum_{{\bf H}} \left\{ P_{H/V}({\bf H}|{\bf V}, {\boldsymbol \Theta}) \; X_i\;X_j \;Q_D({\bf V}) \right\} \end{eqnarray} ただし、 \begin{equation} X_{i} = \left\{ \begin{array}{l} V_{i}\;(i \in \Gamma) \\ H_{i}\;(i \in \Lambda) \end{array} \right. \end{equation} である。

隠れ変数の意味

　確率分布 $P_B({\bf V}, {\bf H}|{\boldsymbol \Theta})$ を隠れ変数で周辺化して得られる $P_V({\bf V}|{\boldsymbol \Theta})$ のエネルギー関数は、式(\ref{marginalv})の形から自由エネルギー $F$ である。 \begin{equation} F({\bf V}|{\boldsymbol \Theta})= -\ln{ \left( \sum_{H_1=\pm1}\cdots\sum_{H_m\pm1}\; \exp \left[ -\Phi({\bf V},{\bf H}|{\boldsymbol \Theta}) \right] \right) } \label{free0} \end{equation} $P_B({\bf V}, {\bf H}|{\boldsymbol \Theta})$ のエネルギー関数 $\Phi$ に比べ複雑さが増していることが分る。この複雑さは、分布関数 $P_V({\bf V}|{\boldsymbol \Theta})$ の表現力を高めている。言い換えると、隠れ変数を導入することにより、学習モデルの表現能力は向上するのである。

参考文献

ディープボルツマンマシン入門 ボルツマンマシン学習の基礎, 安田宗樹, 人工知能学会誌 28巻 3号, 2013年5月.