Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Y1248T(Y. T.)

PRML　演習問題 4.2（標準）　解答

Last updated at Posted at 2020-06-08

この記事では統計学・機械学習の教科書である、C. M. Bishop 著「パターン認識と機械学習」（略称：PRML）の演習問題を私が解いた結果を載せています。この本は私が所属する研究室の輪読会で現在扱われていて、勉強の一環として演習問題を解いています。

問題

二乗和誤差関数 $(4.15)$ の最小化を考える。学習データ集合におけるすべての目的変数ベクトルが線形制約

\mathbf{a}^{\rm T} \mathbf{t}_n + b = 0 \tag{4.18}


> を満たすと仮定する。ここで、$\mathbf{t}_n$ は $(4.15)$ における行列 $\mathbf T$ の $n$ 番目の行に相当する。この制約の結果として、最小二乗解 $(4.17)$ によって与えられるモデルの予測 $\mathbf{y}(\mathbf{x})$ の要素もまたこの制約を満たす、つまり、以下の式を満たすことを示せ。

>```math
\mathbf{a}^{\rm T} \mathbf{y}(\mathbf{x}) + b = 0 \tag{4.19}

上記を示すため、パラメータ $w_0$ がバイアスとしての役割を持つように、基底関数が $\phi_0(\mathbf{x}) = 1$ であると仮定する。

問題の解釈

ここでは $\mathbf{t}_n$ の表記に 1-of-K 符号化を採用しているので、

\mathbf{1}^{\rm T} \mathbf{t}_n - 1 = 0

が成り立つ。ここで、$\mathbf{1}$ は要素が全て $1$ で長さが $\mathbf{t}_n$ と等しいベクトルである。問題にされている命題が成り立つならば、

\mathbf{1}^{\rm T} \mathbf{y}(\mathbf{x}) - 1 = 0

が成り立つ。すなわち、最小二乗法で推定された $\mathbf{y}(\mathbf{x})$ の要素の和は $1$ になるということである。これは分類の問題を考える上でとても良い性質に思える。なぜなら、$\mathbf{y}(\mathbf{x})$ の $k$ 番目の要素 $y_k(\mathbf{x})$ が、$\mathbf{x}$ がクラス $C_k$ に分類される確率 $p(\mathbf{x} \in C_k | \mathbf{x})$ と対応するかのように扱えるからである。

本文にもある通り、実際はこれを確率のように扱うことはできない。 $y_k(\mathbf{x})$ が $[0, 1]$ の範囲に収まるとは限らないからである。しかし要素の和が $1$ になるという性質は、最小二乗法による推定値に関する考察を深める上で重要な性質であることは間違いない。

本文に載っている情報

まず、各クラス $C_k$ に属しているか否か $t_k \in \left\{ 0, 1 \right\}$ は各クラスごとの線形モデルで記述される。

y_k(\mathbf{x})
 = \mathbf{w}_k^{\rm T} \mathbf{x} + w_{k0}
 = \widetilde{\mathbf{w}}_k^{\rm T} \widetilde{\mathbf{x}}
 \tag{4.13}

ただし

\widetilde{\mathbf{w}}_k
 = \begin{pmatrix} w_{k0} \\ \mathbf{w}_k \end{pmatrix}, 
\widetilde{\mathbf{x}}
 = \begin{pmatrix} 1 \\ \mathbf{x} \end{pmatrix}

である。この方程式がクラスの個数 $K$ と同じ数だけあることになる。それらをまとめて行列で表記すると

\mathbf{y}(\mathbf{x})
 = \widetilde{\mathbf{W}}^{\rm T} \widetilde{\mathbf{x}}
 \tag{4.14}

ただし

\widetilde{\mathbf{W}}
  = \left( \widetilde{\mathbf{w}}_1, \dots , \widetilde{\mathbf{w}}_K \right)

である。すると、二乗和誤差関数は

\begin{align}
E_D(\widetilde{\mathbf{W}})
  & = \frac{1}{2}
      \sum_{n=1}^N \sum_{k=1}^K
      \left\{ y_k(\mathbf{x}_n) - t_{nk} \right\} ^ 2
      \\

  & = \frac{1}{2}
      {\rm Tr}
      \left\{
        \left(
          \widetilde{\mathbf{X}} \widetilde{\mathbf{W}} - \mathbf{T}
        \right) ^ {\rm T}
        \left(
          \widetilde{\mathbf{X}} \widetilde{\mathbf{W}} - \mathbf{T}
        \right)
      \right\}
      \tag{4.15}

\end{align}

ただし

\widetilde{\mathbf{X}}
 = \begin{pmatrix} 
   \widetilde{\mathbf{x}}_1^{\rm T} \\
   \vdots \\
   \widetilde{\mathbf{x}}_N^{\rm T}
   \end{pmatrix}, 

\mathbf{T}
 = \begin{pmatrix} 
   \mathbf{t}_1^{\rm T} \\
   \vdots \\
   \mathbf{t}_N^{\rm T}
   \end{pmatrix}

\ \ \ \ \therefore

\widetilde{\mathbf{X}} \widetilde{\mathbf{W}} - \mathbf{T}
 = \begin{pmatrix} 
   \left\{ \mathbf{y}(\mathbf{x}_1) - \mathbf{t}_1 \right\} ^{\rm T} \\
   \vdots \\
   \left\{ \mathbf{y}(\mathbf{x}_N) - \mathbf{t}_N \right\} ^{\rm T}
   \end{pmatrix}

である。

方針

本文にもある通り、二乗和誤差関数を最小化するパラメータの推定は以下で表される。

\begin{align}
\widetilde{\mathbf{W}}
 & = (\widetilde{\mathbf{X}}^{\rm T} \widetilde{\mathbf{X}}) ^ {-1}
   \widetilde{\mathbf{X}}^{\rm T} \mathbf{T}
 = \widetilde{\mathbf{X}}^{\dagger} \mathbf{T}
 \tag{4.16} \\
\mathbf{y} (\mathbf{x})
 & = \widetilde{\mathbf{W}} ^ {\rm T} \widetilde{\mathbf{x}}
 = \mathbf{T}^{\rm T} 
   \left( \widetilde{\mathbf{X}}^{\dagger} \right) ^ {\rm T} 
   \widetilde{\mathbf{x}}
 \tag{4.17}
\end{align}

この表し方を使うと $\mathbf{a}^{\rm T} \mathbf{t} = 0 \ \Rightarrow \ \mathbf{a}^{\rm T} \mathbf{y}(\mathbf{x}) = 0 $ を示すことは容易だが、題意を示すのは容易ではない。

そこで、回帰直線の切片を表すバイアスパラメータ $w_{k0}$ をその他のパラメータとは別に求めることで、$\mathbf{y} (\mathbf{x})$ を「$\mathbf{X}$ の平均 $+$ $\mathbf{X}$ の平均との差」「$\mathbf{T}$ の平均 $+$ $\mathbf{T}$ の平均との差」という形に分解して書きあらわすことにする。すると、与えられた命題を示すことができる。

余談だが、英語版のWikipediaのこちらのページには行列の計算の公式がまとまっていて便利である。https://en.wikipedia.org/wiki/Matrix_calculus

解答

命題１

二乗和誤差関数を最小化するバイアスパラメータ $\mathbf{w_{\rm 0}} = (w_{10} , ... , w_{K0})^{\rm T}$ は

\mathbf{w}_0
= \bar{\mathbf{t}} - \mathbf{W}^{\rm T} \bar{\mathbf{x}}
\tag{ex4.2.1}


> で表される。ただし $\bar{\mathbf{x}}, \bar{\mathbf{t}}$ は行列 $\mathbf{X}, \mathbf{T}$ の各列の平均、つまり

>```math
\bar{\mathbf{x}} = \frac{1}{N} \mathbf{X}^{\rm T} \mathbf{1}, \ \ \ 
\bar{\mathbf{t}} = \frac{1}{N} \mathbf{T}^{\rm T} \mathbf{1} \tag{ex4.2.2}

である。

証明　まず、二乗和誤差関数について、切片とパラメータを分けて表記する。すなわち

E_D(\widetilde{\mathbf{W}})
  = \frac{1}{2}
      {\rm Tr}
      \left\{
        \left(
          \mathbf{X} \mathbf{W} +
          \mathbf{1} \mathbf{w}_0^{\rm T} -
          \mathbf{T}
        \right) ^ {\rm T}
        \left(
          \mathbf{X} \mathbf{W} +
          \mathbf{1} \mathbf{w}_0^{\rm T} -
          \mathbf{T}
        \right)
      \right\}
      \tag{ex4.2.3}

とする。次にこれを $\mathbf{w}_0$ の関数と見なして整形する。

\begin{align}

E_D(\widetilde{\mathbf{W}})
  & = \frac{1}{2}
      {\rm Tr}
      \left\{
        (\mathbf{1} \mathbf{w}_0^{\rm T})^{\rm T}
        \mathbf{1} \mathbf{w}_0^{\rm T} +
        (\mathbf{1} \mathbf{w}_0^{\rm T})^{\rm T} \mathbf{H} + 
        \mathbf{H}^{\rm T} \mathbf{1} \mathbf{w}_0^{\rm T} + 
        \mathbf{H}^{\rm T} \mathbf{H}
      \right\}
      \\

  & = \frac{1}{2}
      {\rm Tr}
      \left\{
        N \mathbf{w}_0 \mathbf{w}_0^{\rm T} +
        \mathbf{w}_0 \mathbf{1}^{\rm T} \mathbf{H} + 
        (\mathbf{w}_0 \mathbf{1}^{\rm T} \mathbf{H})^{\rm T} + 
        \mathbf{H}^{\rm T} \mathbf{H}
      \right\}
      \\

  & = \frac{N}{2} {\rm Tr} (\mathbf{w}_0 \mathbf{w}_0^{\rm T}) + 
      {\rm Tr} (\mathbf{w}_0 \mathbf{1}^{\rm T} \mathbf{H}) + 
      \frac{1}{2} {\rm Tr} (\mathbf{H}^{\rm T} \mathbf{H})

\tag{ex4.2.4}
\end{align}

ただし $ \mathbf{H} = \mathbf{X W - T}$ とし、行列の一般的な性質 ($\mathbf{AB})^{\rm T} = \mathbf{B}^{\rm T} \mathbf{A}^{\rm T}$, $\rm{Tr}(\mathbf{A}^{\rm T}) = \rm{Tr}(\mathbf{A})$, $\rm{Tr}(\mathbf{A+B}) = \rm{Tr}(\mathbf{A}) + \rm{Tr}(\mathbf{B})$ を使った。これを $\mathbf{w}_0$ で偏微分すると

\begin{align}

\frac {\partial} {\partial \mathbf{w}_0} E_D(\widetilde{\mathbf{W}})

 & = N \mathbf{w}_0 + (\mathbf{1}^{\rm T} \mathbf{H})^{\rm T} \\

 & = N \mathbf{w}_0 + (\mathbf{X W - T})^{\rm T} \mathbf{1} \\

 & = N \mathbf{w}_0 + 
     \mathbf{W}^{\rm T} \mathbf{X}^{\rm T} \mathbf{1} -
     \mathbf{T}^{\rm T} \mathbf{1} \\

 & = N \mathbf{w}_0 + N
     (\mathbf{W}^{\rm T} \bar{\mathbf{x}} - \bar{\mathbf{t}})
     \tag{ex4.2.5}

\end{align}

変形には、行列の一般的な性質 $\frac {\partial} {\partial \mathbf{X}} {\rm Tr} (\mathbf{X} \mathbf{X}^{\rm T}) = 2 \mathbf{X}$, $\frac {\partial} {\partial \mathbf{X}} {\rm Tr} (\mathbf{X} \mathbf{A}) = \mathbf{A}^{\rm T}$ を使った。これを $\mathbf{0}$ とすることで、二乗和誤差関数を最小化する $\mathbf{w}_0$ が

\mathbf{w}_0 = \bar{\mathbf{t}} - \mathbf{W}^{\rm T} \bar{\mathbf{x}}

であることが示された。（証明終）

命題２

二乗和誤差関数を最小化する $\mathbf{W}$ は

\begin{align}
\mathbf{W}
& = (\widehat{\mathbf{X}}^{\rm T} \widehat{\mathbf{X}}) ^ {-1}
\widehat{\mathbf{X}}^{\rm T} \widehat{\mathbf{T}}
\tag{ex4.2.6}
\end{align}


> で表される。ただし $\widehat{\mathbf{X}}, \widehat{\mathbf{T}}$ は行列 $\mathbf{X}, \mathbf{T}$ の各列の平均からの乖離、つまり

>```math
\begin{align}
\widehat{\mathbf{X}}  & = \mathbf{X} - \overline{\mathbf{X}}, &
\overline{\mathbf{X}} & = \mathbf{1} \bar{\mathbf{x}}^{\rm T} 
 \tag{ex4.2.7} \\
\widehat{\mathbf{T}}  & = \mathbf{T} - \overline{\mathbf{T}}, &
\overline{\mathbf{T}} & = \mathbf{1} \bar{\mathbf{t}}^{\rm T} 
 \tag{ex4.2.8} \\
\end{align}

である。

証明　二乗和誤差関数 $\rm (4.2.11)$ に命題１で示した解を代入すると以下のようになる。

\begin{align}

E_D(\widetilde{\mathbf{W}})

 & = \frac{1}{2}
     \rm{Tr}
     \left\{
       \left(
         \mathbf{X} \mathbf{W} +
         \overline{\mathbf{T}} -
         \overline{\mathbf{X}} \mathbf{W} - 
         \mathbf{T}
       \right) ^ {\rm T}
       \left(
         \mathbf{X} \mathbf{W} +
         \overline{\mathbf{T}} -
         \overline{\mathbf{X}} \mathbf{W} - 
         \mathbf{T}
       \right)
     \right\}
     \\

 & = \frac{1}{2}
     \rm{Tr}
     \left\{
       \left[
         \left(
         \mathbf{X} - \overline{\mathbf{X}}
         \right) \mathbf{W} -
         \left(
         \mathbf{T} - \overline{\mathbf{T}}
         \right)
       \right] ^ {\rm T}
       \left[
         \left(
         \mathbf{X} - \overline{\mathbf{X}}
         \right) \mathbf{W} -
         \left(
         \mathbf{T} - \overline{\mathbf{T}}
         \right)
       \right]
     \right\}
     \\

 & = \frac{1}{2}
     \rm{Tr}
     \left\{
       \left(
         \widehat{\mathbf{X}} \mathbf{W} - \widehat{\mathbf{T}}
       \right) ^ {\rm T}
       \left(
         \widehat{\mathbf{X}} \mathbf{W} - \widehat{\mathbf{T}}
       \right)
     \right\}
     \\

 & = \frac{1}{2}
     \rm{Tr}
     \left\{
       \left( \widehat{\mathbf{X}} \mathbf{W} \right) ^ {\rm T}
       \widehat{\mathbf{X}} \mathbf{W} - 
       \left( \widehat{\mathbf{X}} \mathbf{W} \right) ^ {\rm T}
       \widehat{\mathbf{T}} -
       \widehat{\mathbf{T}} ^ {\rm T}
       \widehat{\mathbf{X}} \mathbf{W} -
       \widehat{\mathbf{T}} ^ {\rm T} \widehat{\mathbf{T}}
     \right\}
     \\

 & = \frac{1}{2} \rm{Tr}
     \left(
       \mathbf{W} ^ {\rm T} \widehat{\mathbf{X}} ^ {\rm T}
       \widehat{\mathbf{X}} \mathbf{W}
     \right) - 
     \rm{Tr}
     \left(
       \mathbf{W} ^ {\rm T}
       \widehat{\mathbf{X}} ^ {\rm T} 
       \widehat{\mathbf{T}}
     \right) +
     \frac{1}{2} \rm{Tr}
     \left(
       \widehat{\mathbf{T}} ^ {\rm T} \widehat{\mathbf{T}}
     \right)
     \tag{ex4.2.9}

\end{align}

これを $\mathbf{W}$ で偏微分すると以下のようになる。

\begin{align}

\frac {\partial} {\partial \mathbf{W}} E_D(\widetilde{\mathbf{W}})

 & = \frac{1}{2}
     \left\{
     \widehat{\mathbf{X}}^{\rm T} \widehat{\mathbf{X}} + 
     \left( \widehat{\mathbf{X}} ^ {\rm T} \widehat{\mathbf{X}} \right) ^ {\rm T}
     \right\} \mathbf{W} - 
     \widehat{\mathbf{X}} ^ {\rm T} \widehat{\mathbf{T}}
     \\

 & = \widehat{\mathbf{X}}^{\rm T} \widehat{\mathbf{X}} \mathbf{W} - 
     \widehat{\mathbf{X}} ^ {\rm T} \widehat{\mathbf{T}}
     \tag{ex4.2.10}
     
\end{align}

式変形には命題１で使用した一般的な行列の性質、および $\frac {\partial} {\partial \mathbf{X}} {\rm Tr} (\mathbf{X}^{\rm T} \mathbf{A} \mathbf{X}) = (\mathbf{A} + \mathbf{A} ^ {\rm T}) \mathbf{X}$ を用いた。これを $\mathbf{O}$ とすることで、二乗和誤差関数を最小化する $\mathbf{W}$ が

\mathbf{W}
 = \left(
   \widehat{\mathbf{X}}^{\rm T} \widehat{\mathbf{X}}
   \right) ^ {-1}
   \widehat{\mathbf{X}}^{\rm T} \widehat{\mathbf{T}}

であることが示された。（証明終）

命題３

学習データ集合におけるすべての目的変数ベクトルが線形制約

\mathbf{a}^{\rm T} \mathbf{t}_n + b = 0 \tag{4.18}


> を満たすとき、最小二乗解 $(4.17)$ によって与えられる、新たな点 $\mathbf{x}^\star$ におけるモデルの予測 $\mathbf{y}(\mathbf{x}^\star)$ について以下の式が成り立つ。

>```math
\mathbf{a}^{\rm T} \mathbf{y}(\mathbf{x^\star}) + b = 0 \tag{4.19}

証明　命題１、２で示された式で $\mathbf{y}(\mathbf{x}^\star)$ を表現すると、以下のようになる。

\begin{align}

\mathbf{y}(\mathbf{x}^\star)

 & = \mathbf{W} ^ {\rm T} \mathbf{x}^\star + \mathbf{w}_0
     \\

 & = \mathbf{W} ^ {\rm T} \mathbf{x}^\star +
     \bar{\mathbf{t}} - 
     \mathbf{W} ^ {\rm T} \bar{\mathbf{x}}
     \\

 & = \bar{\mathbf{t}} + 
     \mathbf{W} ^ {\rm T} (\mathbf{x}^\star - \bar{\mathbf{x}})
     \\

 & = \bar{\mathbf{t}} + 
     \widehat{\mathbf{T}} ^ {\rm T}
     \left( \widehat{\mathbf{X}} ^ \dagger \right) ^ {\rm T}
     (\mathbf{x}^\star - \bar{\mathbf{x}})
     \tag{ex4.2.11}
     
\end{align}

ただし

\widehat{\mathbf{X}} ^ \dagger = \left( \widehat{\mathbf{X}}^{\rm T} \widehat{\mathbf{X}} \right) ^ {-1} \widehat{\mathbf{X}}^{\rm T}

と置いた。すると、命題について以下のようになる。

\begin{align}

\mathbf{a}^{\rm T} \mathbf{y}(\mathbf{x}^\star)

 & = \mathbf{a}^{\rm T} \bar{\mathbf{t}} + 
     \mathbf{a}^{\rm T} \widehat{\mathbf{T}} ^ {\rm T}
     \left( \widehat{\mathbf{X}} ^ \dagger \right) ^ {\rm T}
     (\mathbf{x}^\star - \bar{\mathbf{x}})
     \\

 & = \mathbf{a}^{\rm T} \bar{\mathbf{t}} + 
     \left(
     \mathbf{a}^{\rm T} \mathbf{T} ^ {\rm T} - 
     \mathbf{a}^{\rm T} \overline{\mathbf{T}} ^ {\rm T}
     \right)
     \left( \widehat{\mathbf{X}} ^ \dagger \right) ^ {\rm T}
     (\mathbf{x}^\star - \bar{\mathbf{x}})
     \\

 & = - b + 
     \left( - \mathbf{b}^{\rm T} + \mathbf{b}^{\rm T} \right)
     \left( \widehat{\mathbf{X}} ^ \dagger \right) ^ {\rm T}
     (\mathbf{x}^\star - \bar{\mathbf{x}})
     \\

 & = - b \tag{ex4.2.12}

\end{align}

なお、この変形では $\mathbf{a}^{\rm T} \bar{\mathbf{t}} = -b, \ \overline{\mathbf{T}} \mathbf{a} = - \mathbf{b}$ を利用している。この性質は $\mathbf{a}^{\rm T} \mathbf{t}_n + b = 0$ が成り立てばほぼ自明であるが、以下のように示される。

\begin{align}

& \mathbf{a}^{\rm T} \bar{\mathbf{t}}
 = \frac{1}{N} \mathbf{a}^{\rm T} \mathbf{T} ^ {\rm T} \mathbf{1}
 = - \frac{1}{N} \mathbf{b}^{\rm T} \mathbf{1}
 = -b \\

& \overline{\mathbf{T}} \mathbf{a}
 = \mathbf{1} \overline{\mathbf{t}} ^ {\rm T} \mathbf{a}
 = \mathbf{1}
   \left( \mathbf{a} ^ {\rm T} \overline{\mathbf{t}} \right) ^ {\rm T}
 = -\mathbf{b}

\end{align}

以上より、題意は示された。（証明終）

公式解答の誤植

最後に、解答執筆中に見つけた公式解答 https://www.microsoft.com/en-us/research/wp-content/uploads/2016/05/prml-web-sol-2009-09-08.pdf の誤植をメモしておく。

  • $(97)$ と $(98)$ の間の式の各項にかけられている $2$ は不要である。
  • $(99)$ の最後の式の第二項の前の符号は $+$ である。
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?