PRML演習12.17の解答

\[ \newcommand\l{\left} \newcommand\r{\right} \newcommand\cmt[1]{\class{Cmt}{\mbox{#1}}} \newcommand\b[1]{\class{Bold}{\mathrm{#1}}} \newcommand\bx{\b{x}} \newcommand\bz{\b{z}} \newcommand\bW{\b{W}} \newcommand\bm{\b{m}} \newcommand\bmu{\b{\mu}} \newcommand\bA{\b{A}} \newcommand\bB{\b{B}} \newcommand\bX{\b{X}} \newcommand\ba{\b{a}} \newcommand\bb{\b{b}} \newcommand\bu{\b{u}} \newcommand\bI{\b{I}} \newcommand\bw{\b{w}} \newcommand\bOmega{\b{\Omega}} \newcommand\barz{\overline\bz} \newcommand\barx{\overline\bx} \newcommand\Tr{\operatorname{Tr}} \newcommand\T{\mathrm T} \newcommand\E{\mathbb E} \newcommand\pdiff[2]{\frac{\partial #1}{\partial #2}} \]

平面は\(\ \bmu\ \)、\(\ \bm_1\ \)、\(\ \bm_2\ \)で与えられる。 平面上に\(\ \bx_n\ \)の近似点\(\ \bx_n'\ \)を取る。(正射影でなくてもよい) \(\ \bx_n'\ \)は平面上にあるので、\(\ \bW = \pmatrix{\bm_1 & \bm_2}\ \)として、 \[ \begin{align} \bx_n' &= \bmu + z_{n1}\bm_1 + z_{n2}\bm_2 \\ &=\bmu + \bW\bz_n~~~\cmt{※1} \end{align} \] と表される。\(\ \bx_n\ \)と\(\ \bx_n'\ \)の再構成コストは \[ J_n = \l\|\bx_n-\bx_n'\r\|^2=\l\|\bx_n-\bmu-\bW\bz_n\r\|^2 \] で与えられるとする。このとき、全データ点のトータルの再構成コストは \[ J = \sum_{n=1}^N \l\|\bx_n-\bx_n'\r\|^2 = \sum_{n=1}^N \l\|\bx_n-\bmu-\bW\bz_n\r\|^2 \] となる。

(\(\ \bmu,\ \bW,\ \bz_n\ \)の推定方法)
(1)\(\ \bx_n,\ \bz_n\ \)の分布を考えて最尤推定で\(\ \bmu,\ \bW,\ \E(\bz_n)\ \)を点推定する。 また、最尤推定はEMアルゴリズムで実行する。\(\ \Rightarrow\ \)12.2.2節
(2)\(\ \bx_n,\ \bz_n\ \)の分布は考えない。全データ点のトータルの再構成コスト \(J\) を最小にするように\(\ \bmu,\ \bW,\ \bz_n\ \)を点推定する。\(\ \Rightarrow\ \)この問題

\(\bmu,\bW,\bz_n\) は独立していると仮定すると、\(J\)の最小解は \[ \l\{ \begin{align} \pdiff{J}{\bmu}&=\b{0}\\ \pdiff{J}{\bW}&=\b{0}\\ \pdiff{J}{\bz_n}&=\b{0}\ (n=1,\ldots,N)\\ \end{align} \r. \] という連立方程式で与えられる。直接解いてもいいが、問題文の要求はこれを反復法で解くことを示唆している。
反復の手順は、 \[ \begin{align} &(1)\ \bW,\bz_n を反復の前回値 \bW^{old},\bz_n^{old} に固定して、\pdiff{J}{\bmu}=\b{0}となる\bmu^{new}を求める \\ &(2)\ \bmuを\bmu^{new}に固定し、\bWを\bW^{old}に固定し、\bz_{i\ne n}を\bz_i^{old}に固定して、\pdiff{J}{\bz_n}=\b{0}となる\bz_n^{new}を求める \\ &(3)\ \bmuを\bmu^{new}に固定し、\bz_nを\bz_n^{old}に固定して、\pdiff{J}{\bW}=\b{0}となる\bW^{new}を求める \\ &(4)\ \bmu,\bW,\bz_nが収束するまで(1),(2),(3)を反復する \\ \end{align} \] とする。\(\bmu\) についてはヤコビ法で \(\bW,\bz_n\) についてはガウスザイデル法みたいになっている。変則に見えるが、このような反復にすると問題文で要求されている(12.58),(12,59)によく似た \(\bW, \bz_n\) の更新式を導くことができる。

(収束値が解になっていること)
反復が収束したとき、\(\bW^{old}=\bW^{new},\bz_n^{old}=\bz_n^{new}\) となり、このとき \[ \l\{ \begin{align} \l(\pdiff{J}{\bmu}\r)_{\bmu^{new},\bW^{new},\bz_n^{new}}&=\b{0}\\ \l(\pdiff{J}{\bW}\r)_{\bmu^{new},\bW^{new},\bz_n^{new}}&=\b{0}\\ \l(\pdiff{J}{\bz_n}\r)_{\bmu^{new},\bW^{new},\bz_n^{new}}&=\b{0}\ (n=1,\ldots,N)\\ \end{align} \r. \] が成立するので、収束値は元の連立方程式の解になっている。

(収束するかどうか)
ヤコビ法とガウスザイデル法の組合せみたいなものなので、 \(J\) が \(\bmu,\bW,\bz_n\) について 凸関数ならば反復は収束すると思われる。(証明？)

実際には試してみて収束すればOK、しなければ別の手を考える。という場面も多いので、収束すると仮定して話をすすめることにも価値はある。

(12.95)より \[ \begin{align} J&=\sum_{n=1}^N\|\bx_n-\bmu-\bW\bz_n\|^2 \\ &=\sum_{n=1}^N\l(\bx_n-\bmu-\bW\bz_n)^\T(\bx_n-\bmu-\bW\bz_n\r) \\ &=\sum_{n=1}^N\l(\bx_n^\T\bx_n-\bx_n^\T\bmu-\bx_n^\T\bW\bz_n-\bmu^\T\bx_n+\bmu^\T\bmu +\bmu^\T\bW\bz_n-\bz_n^\T\bW^\T\bx_n+\bz_n^\T\bW^\T\bmu+\bz_n^\T\bW^\T\bW\bz_n\r) \end{align} \] これより、 \[ \begin{align} \b{0}=\pdiff{J}{\bmu} &=\sum_{n=1}^N\l\{-\bx_n-\bx_n+2\bmu+\bW\bz_n+\bW\bz_n\r\}~~~\cmt{※2} \\ &=\sum_{n=1}^N\l\{-2\bx_n+2\bmu+2\bW\bz_n\r\} \\ \end{align} \] よって、\(\bmu\) の更新式は \[ \bmu^{new} = {1\over N}\sum_{n=1}^N(\bx_n-\bW\bz_n) = \barx-\bW\barz \] で与えられる。ただし \(\bW,\barz\) は反復の前回値である。この \(\bmu^{new}\) を(12.95)に入れて、 \[ \begin{align} J_{\bmu^{new}} &= \sum_{n=1}^N\l\|\bx_n-(\barx-\bW\barz)-\bW\bz_n\r\|^2 \\ &= \sum_{n=1}^N\l\|(\bx_n-\barx)-\bW(\bz_n-\barz)\r\|^2 \\ \end{align} \] を得る。

\(\bz_n\)の更新値\(\bz_n^{new}\)は、\(J\)を最小にする\(\bz_n\)の\(\bmu=\bmu^{new}\)のときの値である。 つまり、\(\pdiff{J}{\bz_n}=\b{0}\) と \(\bmu=\bmu^{new}(\bW,\bz_1,\ldots,\bz_N)\) の交点である。 \[ \small \begin{align} \b{0} &=\pdiff{J}{\bz_n} =\pdiff{}{\bz_n}\sum_{i=1}^N\|\bx_i-\bmu-\bW\bz_i\|^2 \\ &=\pdiff{}{\bz_n}\|\bx_n-\bmu-\bW\bz_n\|^2 \\ &=\pdiff{}{\bz_n}\{(\bx_n-\bmu-\bW\bz_n)^\T(\bx_n-\bmu-\bW\bz_n)\} \\ &=\pdiff{}{\bz_n}\{ (\bx_n-\bmu)^\T(\bx_n-\bmu) -2(\bW\bz_n)^\T(\bx_n-\bmu) +(\bW\bz_n)^\T(\bW\bz_n)\} \\ &=-2\bW^\T(\bx_n-\bmu)+2\bW^\T\bW\bz_n~~~\cmt{※3, ※4} \\ \end{align} \] よって \[ \bW^\T\bW\bz_n = \bW^\T(\bx_n-\bmu) \] ここで、\(\bmu = \bmu^{new}=\barx-\bW\barz\)とすると \[ \begin{align} \bW^\T\bW\bz_n&=\bW^\T(\bx_n-\barx+\bW\barz) \\ \therefore \bW^\T\bW(\bz_n-\barz)&=\bW^\T(\bx_n-\barx) \\ \end{align} \] よって\(\bz_n\)の更新式は \[ (\bz_n-\barz)^{new}=(\bW^\T\bW)^{-1}(\bx_n-\barx) \] となる。ただし \[ \begin{align} (\bz_n-\barz)^{new}&=\bz_n^{new}-\barz^{new} \\ \barz^{new}&={1\over N}\l(\bz_n^{new}+\sum_{i=1,i\ne n}^N \bz_i \r)\\ \end{align} \] である。が、反復計算において、\(\bz_n, \barz\) を個別に扱うことはなく、必ず \((\bz_n-\barz)\)の形で処理される。また、式中の \(\bW,\bz_{i\ne n}\) は反復の前回値である。
\(n=1,\ldots,N\) について並べて行列表記すると \[ \small \begin{align} \pmatrix{(\bz_1-\barz)^{new}&\cdots&(\bz_N-\barz)^{new}} &=\pmatrix{(\bW^\T\bW)^{-1}\bW^\T(\bx_1-\barx)&\cdots&(\bW^\T\bW)^{-1}\bW^\T(\bx_N-\barx)} \\ &=(\bW^\T\bW)^{-1}\bW^\T\pmatrix{(\bx_1-\barx)&\cdots&(\bx_N-\barx)} \\ \end{align} \] となる。ここで \[ \begin{align} \bOmega &= \pmatrix{(\bz_1-\barz)&\cdots&(\bz_N-\barz)} \\ \widetilde\bX &= \pmatrix{(\bx_1-\barx)^\T\\\vdots\\(\bx_N-\barx)^\T} \\ \end{align} \] と置くと、 \[ \bOmega^{new} = (\bW^\T\bW)^{-1}\bW^\T\widetilde\bX^\T \] となる。ただし \(\bOmega^{new}\) は \(\bOmega\) の \((\bz_n-\barz)\) を \((\bz_n-\barz)^{new}\) としたものである。
この式は、(12.58)で\(\ \E[\bz_n]\ \)を\((\bz_n-\barz)^{new}\)に置き換えたものになっている。

\(\bW\)の更新値\(\bW^{new}\)は、\(J\)を最小にする\(\bW\)の\(\bmu=\bmu^{new}\)のときの値である。 つまり、\(\pdiff{J}{\bW}=\b{0}\) と \(\bmu=\bmu^{new}(\bW,\bz_1,\ldots,\bz_N)\) の交点である。 \[ \begin{align} \b{0}&=\pdiff{J}{\bW} =\pdiff{}{\bW}\sum_{n=1}^N\|\bx_n-\bmu-\bW\bz_n\|^2 \\ &=\sum_{i=n}^N\pdiff{}{\bW}(\bx_n-\bmu-\bW\bz_n)^\T(\bx_n-\bmu-\bW\bz_n) \\ &=\sum_{n=1}^N\pdiff{}{\bW}\{ (\bx_n-\bmu)^\T(\bx_n-\bmu) -2(\bW\bz_n)^\T(\bx_n-\bmu) +(\bW\bz_n)^\T(\bW\bz_n) \} \\ &=\sum_{n=1}^N\{-2(\bx_n-\bmu)\bz_n^\T+2\bW\bz_n\bz_n^\T\}~~~\cmt{※5, ※6} \\ \end{align} \] よって \[ \bW\sum_{n=1}^N \bz_n\bz_n^\T = \sum_{n=1}^N (\bx_n-\bmu)\bz_n^\T \] ここで、\(\bmu=\bmu^{new}=\barx-\bW\barz\)とすると \[ \begin{align} \bW\sum_{n=1}^N\bz_n\bz_n^\T&=\sum_{n=1}^N(\bx_n-\barx+\bW\barz)\bz_n^\T \\ \therefore \bW\sum_{n=1}^N(\bz_n-\barz)\bz_n^\T &=\sum_{n=1}^N(\bx_n-\barx)\bz_n^\T \\ \therefore \bW\l\{\sum_{n=1}^N(\bz_n-\barz)\bz_n^\T-\sum_{n=1}^N(\bz_n-\barz)\barz^\T\r\} &=\sum_{n=1}^N(\bx_n-\barx)\bz_n^\T-\sum_{n=1}^N(\bx_n-\barx)\barz^\T~~~\cmt{※7, ※8} \\ \therefore \bW\l\{\sum_{n=1}^N(\bz_n-\barz)(\bz_n-\barz)^\T\r\} &=\sum_{n=1}^N(\bx_n-\barx)(\bz_n-\barz)^\T \\ \end{align} \] これより \(\bW\) の更新式は、 \[ \begin{align} \bW^{new} &=\l\{\sum_{n=1}^N(\bx_n-\barx)(\bz_n-\barz)^\T\r\} \l\{\sum_{n=1}^N(\bz_n-\barz)(\bz_n-\barz)^\T\r\}^{-1} \\ \end{align} \] となる。ただし、\(\bz_n,\barz\) は反復の前回値である。 右辺の総和は行列の積で表すことができて \[ \small \bW^{new}=\l\{ \pmatrix{(\bx_1-\barx)&\cdots&(\bx_N-\barx)} \pmatrix{(\bz_1-\barz)^\T \\ \vdots \\ (\bz_N-\barz)^\T} \r\} \l\{ \pmatrix{(\bz_1-\barz)&\cdots&(\bz_N-\barz)} \pmatrix{(\bz_1-\barz)^\T \\ \vdots \\ (\bz_N-\barz)^\T} \r\}^{-1} \] となる。上記の\(\ \bOmega,\ \widetilde\bX\ \)を使うと \[ \bW^{new} = \widetilde\bX^\T\bOmega^\T(\bOmega\bOmega^\T)^{-1} \] となる。これは、(12.59)で\(\E[\bz_n]\)を\(\ \bz_n-\barz\ \)に置き換えたものになっている。