はじめに

本記事は, 機械学習の教科書の決定版ともいえる, Christopher Bishop先生による[『Pattern Recognition and Machine Learning （パターン認識と機械学習）』] (https://www.microsoft.com/en-us/research/people/cmbishop/prml-book/) , 通称PRMLの演習問題のうち, 私が解いた問題の解答を記したものです. これは, 私の所属する[生物測定学研究室] (https://www.ut-biomet.org/) の輪読会でPRMLを取り扱っており, その勉強の一環として演習問題を解いたときのものです. なお, 他の演習問題の解答例に関する記事については, [PRML　演習問題　解答集　まとめ] (https://qiita.com/Lab_of_Biomet/items/15e38ca34fafa8176d89) をご覧ください.

問題

反復条件付きモード (ICM) を使って

\begin{align*}
E \left ( \mathbf{x}, \mathbf{y} \right )  = h \sum_i x_i - \beta \sum_{\{i, j\}} x_i x_j - \eta \sum_i x_i y_i
\tag{8.42}
\end{align*}

で与えられるエネルギー関数を最小化することを考える. すべての他の変数を固定して, ある1つの変数 $x_j$ に関する2状態のエネルギー値の差を書き下せ.
またその表現が, グラフにおける $x_j$ の近傍の局所的な量だけに依存することを示せ.

解答

ICMでは $x_i$ を, 例えば $x_i = y_i$ のように初期化する.
次に, ノード$x_j$を1つ選び, その他のノード変数の値を固定したまま $x_j$ の2つの可能な状態 ( $x_j = +1$ 及び $x_j = -1$ ) における全エネルギーを評価する. この問題では、まずこの2状態のエネルギーの値の差を書き下せばよい.
さてここで, ${x_i, x_j}$ が隣接する変数の対であることに注意すると, $x_j$ を1つ選ぶと, 全エネルギー関数に影響を及ぼす $x_i$ は, 2次元画像の場合$x_j$の上下左右に位置するノードであることがわかる. したがって, この場合 $\left ( 8.42 \right )$ 式の第2項における和は4つの項に分解される.

\begin{align*}
E \left ( \mathbf{x}, \mathbf{y} \right )  = h \sum_i x_i - \beta  \left ( x_{j1} x_j + x_{j2} x_j + x_{j3} x_j + x_{j4} x_j \right )  - \eta \sum_i x_i y_i
\tag{8.13.1}
\end{align*}

ここで, $x_{j1}$, $x_{j2}$, $x_{j3}$, $x_{j4}$ はそれぞれ $x_j$ の上下左右に位置するノードを指すこととする.
では $x_j = + 1$ 及び $x_j = - 1$ の時の全エネルギー関数を書き下してみよう. これは $\left ( 8.13.1 \right )$ 式に $x_j$ の値を代入すれば良いだけで, それぞれ

\begin{align*}
E \left ( \mathbf{x}, \mathbf{y} \right )  = h \sum_i x_i - \beta  \left ( x_{j1} + x_{j2} + x_{j3} + x_{j4} \right )  - \eta \sum_i x_i y_i
\tag{8.13.2}
\end{align*}

\begin{align*}
E \left ( \mathbf{x}, \mathbf{y} \right )  = h \sum_i x_i + \beta  \left ( x_{j1} + x_{j2} + x_{j3} + x_{j4} \right )  - \eta \sum_i x_i y_i
\tag{8.13.3}
\end{align*}

したがって, エネルギー値の差は,

\begin{align*}
2\beta  \left ( x_{j1} + x_{j2} + x_{j3} + x_{j4} \right ) 
\tag{8.13.4}
\end{align*}

となる.
この表現は, グラフにおける $x_j$ と隣接するノードの値のみに依存するので, $x_j$ の近傍の局所的な量だけに依存することが示された. (証明終)

※ なお, この解答では2次元画像の場合について考えているが, これがより高次元のデータに対するノイズ除去の問題になったとしても, $x_j$ に隣接するノードについてのみ考えれば良い, ということは変わらない.