はじめに
本記事は, 機械学習の教科書の決定版ともいえる, Christopher Bishop先生による『Pattern Recognition and Machine Learning （パターン認識と機械学習）』, 通称PRMLの演習問題のうち, 私が解いた問題の解答を記したものです. これは, 私の所属する生物測定学研究室の輪読会でPRMLを取り扱っており, その勉強の一環として演習問題を解いたときのものです. なお, 他の演習問題の解答例に関する記事については, PRML 演習問題 解答集 まとめをご覧ください.
問題
$6.1$ 節で紹介した最小二乗法線形回帰問題の双対表現を示せ. また, 解のベクトル $\mathbf { a }$ の要素 $a _ { n }$ がベクトル $\boldsymbol { \phi } \left (\mathbf { x } _ { n } \right )$ の要素の線形結合で表されることを示せ. それらの係数をベクトル $\mathbf { w }$ として, 双対表現の双対表現がもともとの表現に戻ることを, $\mathbf { w }$ をパラメータベクトルとして示せ.
解答
問題文からわかるように, 以下の3つに分けて解いていきましょう。
6.1-1
$6.1$ 節で紹介した最小二乗法線形回帰問題の双対表現を示せ.
方針
要は, $6.1$ 節で説明されていた内容を復習する問題ですね。「双対表現を示す」＝「パラメータベクトル $\mathbf { w }$ で表していた形式から, $\mathbf { a }$ で表す形式に変換する」と捉えておけば良いでしょう.
証明
\begin {align*}
J ( \mathbf { w } ) = \frac { 1 } { 2 } \sum _ { n = 1 } ^ { N } \left\{ \mathbf { w } ^ { \mathrm { T } } \boldsymbol { \phi } \left( \mathbf { x } _ { n } \right) - t _ { n } \right\} ^ { 2 } + \frac { \lambda } { 2 } \mathbf { w } ^ { \mathrm { T } } \mathbf { w }
\tag{6.2}
\end{align*}
の変形について考えていきます. なお, $(6.2)$ 式は, 行列形式で書き直すと以下のように書き直せます.
\begin {align*}
J ( \mathbf { w } ) & = \frac { 1 } { 2 } \left ( \mathbf { \Phi } \mathbf { w } - \mathbf { t } \right ) ^ \mathrm { T } \left ( \mathbf { \Phi } \mathbf { w } - \mathbf { t } \right ) + \frac { \lambda } { 2 } \mathbf { w } ^ { \mathrm { T } } \mathbf { w } \\
& = \frac { 1 } { 2 } \mathbf { w } ^ { \mathrm { T } } \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { \Phi } \mathbf { w } - \mathbf { w } ^ { \mathrm { T } } \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { t } + \frac { 1 } { 2 } \mathbf { t } ^ { \mathrm { T } } \mathbf { t } + \frac { \lambda } { 2 } \mathbf { w } ^ { \mathrm { T } } \mathbf { w }
\tag{6.1.1}
\end{align*}
これを, $\mathbf { w }$ で偏微分し, これが $\mathbf { 0 }$ となることを考えてみましょう. すると,
\begin {align*}
\frac { \partial J ( \mathbf { w } ) } { \partial \mathbf { w } } & = \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { \Phi } \mathbf { w } - \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { t } + \lambda \mathbf { w } = \mathbf { 0 }
\tag{6.1.2}
\end{align*}
したがって,
\begin {align*}
\mathbf { w } & = - \frac { 1 } { \lambda } \mathbf { \Phi } ^ { \mathrm { T } } \left ( \mathbf { \Phi } \mathbf { w } - \mathbf { t } \right ) \equiv \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { a }
\tag{6.1.3}
\end{align*}
と変形できます. なおここで, $\mathbf { a } = - \frac { 1 } { \lambda } \left ( \mathbf { \Phi } \mathbf { w } - \mathbf { t } \right )$ と定義しました.
この結果を, もとの $(6.1.1)$ 式に代入し直せば,
\begin {align*}
J ( \mathbf { a } ) & = \frac { 1 } { 2 } \mathbf { a } ^ { \mathrm { T } } \mathbf { \Phi } \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { \Phi } \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { a } - \mathbf { a } ^ { \mathrm { T } } \mathbf { \Phi } \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { t } + \frac { 1 } { 2 } \mathbf { t } ^ { \mathrm { T } } \mathbf { t } + \frac { \lambda } { 2 } \mathbf { a } ^ { \mathrm { T } } \mathbf { \Phi } \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { a } \\ & = \frac { 1 } { 2 } \mathbf { a } ^ { \mathrm { T } } \mathbf { K } \mathbf { K } \mathbf { a } - \mathbf { a } ^ { \mathrm { T } } \mathbf { K } \mathbf { t } + \frac { 1 } { 2 } \mathbf { t } ^ { \mathrm { T } } \mathbf { t } + \frac { \lambda } { 2 } \mathbf { a } ^ { \mathrm { T } } \mathbf { K } \mathbf { a } \\ & = \frac { 1 } { 2 } ( \mathbf { K } \mathbf { a } - \mathbf { t } ) ^ { \mathrm { T } } ( \mathbf { K } \mathbf { a } - \mathbf { t } ) + \frac { \lambda } { 2 } \mathbf { a } ^ { \mathrm { T } } \mathbf { K } \mathbf { a }
\tag{6.1.4}
\end{align*}
が得られますね. なお, 行列 $\mathbf { K } = \mathbf { \Phi } \mathbf { \Phi } ^ { \mathrm { T } }$ と定義しました. これにより, 最小二乗法線形回帰問題の双対表現を示すことができました.
6.1-2
また, 解のベクトル $\mathbf { a }$ の要素 $a _ { n }$ がベクトル $\boldsymbol { \phi } \left (\mathbf { x } _ { n } \right )$ の要素の線形結合で表されることを示せ.
方針
この証明が一番難しいですね. 後で見るように, ベクトル $\mathbf { a }$ が, $\mathbf { K }$ の各行の張る空間に存在するベクトルと仮定しても問題がないことから考えればいいようです.
証明
一般に, 標本サイズ $N$ は特徴空間の次元（あるいは基底関数の数） $M$ よりも大きいことが想定されます. したがって, 行列 $\mathbf { K } = \mathbf { \Phi } \mathbf { \Phi } ^ \mathrm{ T }$ はランク落ちしていることが想定されます. すなわち, 行列 $\mathbf { K }$ は $M$ 個の非ゼロの固有値をもち, $N - M$ 個のゼロである固有値をもつ, ということです. ここから, 解のベクトル $\mathbf { a }$ を $\mathbf { a } = \mathbf { a } _ { \parallel } + \mathbf { a } _ { \perp }$ のように, 分解することを考えます. ここで, $\mathbf { a } _ { \parallel }$, $\mathbf { a } _ { \perp }$ とは $\mathbf { a } _ { \parallel } ^ \mathrm{ T } \mathbf { a } _ { \perp } = \mathbf { 0 }$ および $\mathbf { K } \mathbf { a } _ { \perp } = \mathbf { 0 }$ を満たすようなベクトルです. この分解を $(6.1.4)$ 式の $J \left ( \mathbf { a } \right )$ に適用することを考えてみましょう. すると, $\mathbf { K } \mathbf { a } _ { \perp } = \mathbf { 0 }$ を利用することで,
\begin {align*}
J ( \mathbf { a } ) & = \frac { 1 } { 2 } \mathbf { a } ^ { \mathrm { T } } \mathbf { K } \mathbf { K } \mathbf { a } - \mathbf { a } ^ { \mathrm { T } } \mathbf { K } \mathbf { t } + \frac { 1 } { 2 } \mathbf { t } ^ { \mathrm { T } } \mathbf { t } + \frac { \lambda } { 2 } \mathbf { a } ^ { \mathrm { T } } \mathbf { K } \mathbf { a } \\
& = \frac { 1 } { 2 } \left ( \mathbf { a } _ { \parallel } + \mathbf { a } _ { \perp } \right ) ^ { \mathrm { T } } \mathbf { K } \mathbf { K } \left ( \mathbf { a } _ { \parallel } + \mathbf { a } _ { \perp } \right ) - \left ( \mathbf { a } _ { \parallel } + \mathbf { a } _ { \perp } \right ) ^ { \mathrm { T } } \mathbf { K } \mathbf { t } + \frac { 1 } { 2 } \mathbf { t } ^ { \mathrm { T } } \mathbf { t } + \frac { \lambda } { 2 } \left ( \mathbf { a } _ { \parallel } + \mathbf { a } _ { \perp } \right ) ^ { \mathrm { T } } \mathbf { K } \left ( \mathbf { a } _ { \parallel } + \mathbf { a } _ { \perp } \right ) \\
& = \frac { 1 } { 2 } \mathbf { a } _ { \parallel } ^ { \mathrm { T } } \mathbf { K } \mathbf { K } \mathbf { a } _ { \parallel } - \mathbf { a } _ { \parallel } ^ { \mathrm { T } } \mathbf { K } \mathbf { t } + \frac { 1 } { 2 } \mathbf { t } ^ { \mathrm { T } } \mathbf { t } + \frac { \lambda } { 2 } \mathbf { a } _ { \parallel } ^ { \mathrm { T } } \mathbf { K } \mathbf { a } _ { \parallel }
\tag{6.1.5}
\end{align*}
が得られます. これは, 最小化したい二乗和誤差関数が $\mathbf { a } _ { \perp }$ に依存しないということを意味しています. したがって, 最小二乗法線形回帰問題の解のベクトル $\mathbf { a }$ として $\mathbf { a } = \mathbf { a } _ { \parallel }$ を採用しても, 問題ないということがわかります. ここで, $\mathbf { a } _ { \perp }$ は $\mathbf { K } \mathbf { a } _ { \perp } = \mathbf { 0 }$ を満たすので, $\mathbf { K }$ の各行のベクトルと垂直なベクトルであると言えます. 一方で, $\mathbf { a } _ { \parallel }$ は $\mathbf { K }$ の各行のベクトルと垂直ではないため, $\mathbf { K }$ の各行のベクトルと線形従属, すなわち $\mathbf { K }$ の各行の張る空間（線形包）に存在することがわかります.
ここから,
\begin {align*}
\mathbf { a } = \mathbf { a } _ { \parallel } & = \mathbf { K } \mathbf { v } \\
& = \mathbf { \Phi } \mathbf { \Phi } ^ \mathrm{ T } \mathbf { v } \\
& = \mathbf { \Phi } \mathbf { u }
\tag{6.1.6}
\end{align*}
を得ることができます. ここで, $\mathbf { v }$ は任意のベクトル, $\mathbf { u } = \mathbf { \Phi } ^ \mathrm{ T } \mathbf { v }$ を満たすベクトルとします.
あるいは, $\mathbf { a }$ の各要素に注目するならば,
\begin {align*}
a _ { n } = \sum _ { i = 1 } ^ { M } u _ { i } \phi _ { i } \left( \mathbf { x } _ { n } \right)
\tag{6.1.7}
\end{align*}
と書くこともできますね.
これらから, 解のベクトル $\mathbf { a }$ の要素 $a _ { n }$ がベクトル $\boldsymbol { \phi } \left (\mathbf { x } _ { n } \right )$ の要素の線形結合で表されることを示すことができました.
6.1-3
それらの係数をベクトル $\mathbf { w }$ として, 双対表現の双対表現がもともとの表現に戻ることを, $\mathbf { w }$ をパラメータベクトルとして示せ.
方針
「双対表現の双対表現がもともとの表現に戻る」というのは, $a _ { n }$ を $\boldsymbol { \phi } \left (\mathbf { x } _ { n } \right )$ の要素の線形結合で表したときに, 元の二乗和誤差の式
\begin {align*}
J ( \mathbf { w } ) = \frac { 1 } { 2 } \sum _ { n = 1 } ^ { N } \left\{ \mathbf { w } ^ { \mathrm { T } } \boldsymbol { \phi } \left( \mathbf { x } _ { n } \right) - t _ { n } \right\} ^ { 2 } + \frac { \lambda } { 2 } \mathbf { w } ^ { \mathrm { T } } \mathbf { w }
\tag{6.2}
\end{align*}
が再現できることを証明しろ, ということですね. これは, 6.1-2が証明できれば比較的に簡単に証明できます.
証明
双対表現の双対表現を考えろということなので, $(6.1.6)$ 式を $(6.1.4)$ 式に代入することを考えればいいですね. 代入すると,
\begin {align*}
J ( \mathbf { u } ) & = \frac { 1 } { 2 } ( \mathbf { K } \mathbf { \Phi } \mathbf { u } - \mathbf { t } ) ^ { \mathrm { T } } ( \mathbf { K } \mathbf { \Phi } \mathbf { u } - \mathbf { t } ) + \frac { \lambda } { 2 } \mathbf { u } ^ { \mathrm { T } } \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { K } \mathbf { \Phi } \mathbf { u } \\
& = \frac { 1 } { 2 } \left( \boldsymbol { \Phi } \boldsymbol { \Phi } ^ { \mathrm { T } } \boldsymbol { \Phi } \mathbf { u } - \mathbf { t } \right) ^ { \mathrm { T } } \left( \boldsymbol { \Phi } \boldsymbol { \Phi } ^ { \mathrm { T } } \boldsymbol { \Phi } \mathbf { u } - \mathbf { t } \right) + \frac { \lambda } { 2 } \mathbf { u } ^ { \mathrm { T } } \boldsymbol { \Phi } ^ { \mathrm { T } } \boldsymbol { \Phi } \boldsymbol { \Phi } ^ { \mathrm { T } } \boldsymbol { \Phi } \mathbf { u }
\tag{6.1.8}
\end{align*}
を得ることができます.
ここで, $\boldsymbol { \Phi } ^ { \mathrm { T } } \boldsymbol { \Phi }$ はフルランクの行列であるので, $(6.1.3)$ 式, $(6.1.6)$ 式から
\begin {align*}
\mathbf { w } = \mathbf { \Phi } ^ { \mathrm { T } } \mathbf { a } =
\mathbf { \Phi } ^ { \mathrm { T } } \boldsymbol { \Phi } \mathbf { u }
\tag{6.1.9}
\end{align*}
という変換が成り立つことを踏まえれば,
\begin {align*}
J ( \mathbf { w } ) & = \frac { 1 } { 2 } \left ( \mathbf { \Phi } \mathbf { w } - \mathbf { t } \right ) ^ \mathrm { T } \left ( \mathbf { \Phi } \mathbf { w } - \mathbf { t } \right ) + \frac { \lambda } { 2 } \mathbf { w } ^ { \mathrm { T } } \mathbf { w }
\tag{6.1.1}
\end{align*}
が成り立つことがわかります. したがって, 最小二乗線形問題における二乗和誤差関数が, 双対表現の双対表現をとることで, もともとの形式に戻ることを示すことができました.