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

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

# 問題

$w_{ij}$ を成分とする任意の正方行列は $w_{ij} = w_{ij}^{\rm S} + w_{ij}^{\rm A}$ という形に書けることを示せ。ただし、$w_{ij}^{\rm S}$ と $w_{ij}^{\rm A}$ はそれぞれ対称行列と反対称行列の成分であり $w_{ij}^{\rm S} = w_{ji}^{\rm S}$ および  $w_{ij}^{\rm A} = -w_{ji}^{\rm A}$ がすべての $i, j$ について成り立つ。さてここで、$D$ 次元における高次の多項式の $2$ 次の項

```math
\sum_{i=1}^D \sum_{j=1}^D w_{ij} x_i x_j \tag{1.131}
```

を考えると、

```math
\sum_{i=1}^D \sum_{j=1}^D w_{ij} x_i x_j = \sum_{i=1}^D \sum_{j=1}^D w^{\rm S}_{ij} x_i x_j \tag{1.132}
```

となり、半対称行列の寄与が消えることを示せ。このことから、一般性を失うことなく、係数 $w_{ij}$ は対称に選んでよく、すべての $D^2$ の成分の選び方が独立ではないことがわかる。これを使って、行列 $w_{ij}^{\rm S}$ の独立パラメータの数が $D(D+1) / 2$ で与えられることを示せ。



# 問題の解釈

この問題の最終目標は、式 $(1.131)$ で示される $2$ 次の多項式のパラメータ数が、実質的に $D(D+1) / 2$ であることを証明することだ。$2$ 次の多項式のパラメータ $w_{ij}$ は一見すると $D^2$ 個あるように見える。しかしそのうち $D(D+1) / 2$ さえ決まれば残りは全て決まってしまう、ということを証明したい。そこでこの問題を、以下のような３つの問題に分解する。

- 証明１　$w_{ij} = w_{ij}^{\rm S} + w_{ij}^{\rm A}$ という形に分解できるように、$w_{ij}^{\rm S}$ と $w_{ij}^{\rm A}$ が設定できることを示す。
- 証明２　$2$ 次の多項式を考える上では、$w_{ij}^{\rm A}$ が消えてしまうことを示す。
- 証明３　残った $w_{ij}^{\rm S}$ の実質的なパラメータ数が $D(D+1) / 2$ 個であることを示す。

ただし、$w_{ij}^{\rm S}$ と $w_{ij}^{\rm A}$ はそれぞれ対称行列と半対称行列の成分だ。

実はこの問題は、演習問題1.15と1.16の足掛かりになる問題である。それらの問題では、多項式の次数を $2$ 次に限らず一般化した話をしている。



# 発想

３つの問題のうち、証明１については少し考えなければいけない。対称行列 $w_{ij}^{\rm S}$ と 反対称行列 $w_{ij}^{\rm A}$ はどう設定すればよいのだろうか？ ちなみに対称行列と反対称行列の定義は問題文中にあったが、例を挙げるとそれぞれ以下のようなものだ。

```math
\left(
\begin{matrix}
1 & 4 & 5 \\
4 & 2 & 6 \\
5 & 6 & 3 
\end{matrix}
\right), \ \ 

\left(
\begin{matrix}
1 & -4 & 5 \\
4 & 2 & -6 \\
-5 & 6 & 3 
\end{matrix}
\right)
```

まずは具体的な例を持ち込んで考える。この簡単な行列を対称行列と反対称行列に分解する問題を考える。

```math
\left(
\begin{matrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9 
\end{matrix}
\right) = 

\left(
\begin{matrix}
? & ? & ? \\
? & ? & ? \\
? & ? & ? 
\end{matrix}
\right) +

\left(
\begin{matrix}
? & ? & ? \\
? & ? & ? \\
? & ? & ? 
\end{matrix}
\right)
```

例えば行列の $(1, 2)$ 成分と $(2, 1)$ 成分に注目する。$2$ と $4$ だ。これを分解するとき、$2 = a + b, \ \ 4 = a - b$ という連立方程式を解けばいいことが分かる。これは簡単に $a = 3, \ \ b = -1$ という答えが得られる。

```math
\left(
\begin{matrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9 
\end{matrix}
\right) = 

\left(
\begin{matrix}
? & 3 & ? \\
3 & ? & ? \\
? & ? & ?
\end{matrix}
\right) +

\left(
\begin{matrix}
? & -1 & ? \\
1 & ? & ? \\
? & ? & ?
\end{matrix}
\right)
```

そうすると、法則性が見えてくる。対称行列には２つの値の平均を、反対称行列には２つの値の差の半分を入れればよい。対角に位置する成分は値が１つずつしかないが、これも１つの値の平均 $(w_{ii} + w_{ii}) / 2$ と差の半分 $(w_{ii} - w_{ii}) / 2$ だと思えばよい。

```math
\left(
\begin{matrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9 
\end{matrix}
\right) = 

\left(
\begin{matrix}
1 & 3 & 5 \\
3 & 5 & 7 \\
5 & 7 & 9
\end{matrix}
\right) +

\left(
\begin{matrix}
0 & -1 & -2 \\
1 & 0 & -1 \\
2 & 1 & 0
\end{matrix}
\right)
```

準備は完了だ。ここからはこの議論を定式化する。



# 解答

### 命題１

***命題***　$w_{ij}$ を成分とする任意の正方行列は $w_{ij} = w_{ij}^{\rm S} + w_{ij}^{\rm A}$ という形に書ける。ただし、$w_{ij}^{\rm S}$ と $w_{ij}^{\rm A}$ はそれぞれ対称行列と反対称行列の成分であり $w_{ij}^{\rm S} = w_{ji}^{\rm S}$ および  $w_{ij}^{\rm A} = -w_{ji}^{\rm A}$ がすべての $i, j$ について成り立つ。

***証明***　$w_{ij}^{\rm S} = (w_{ij} + w_{ji}) / 2, \\ \\ w_{ij}^{\rm A} = (w_{ij} - w_{ji}) / 2$ と設定する。まず、これらがそれぞれ対称行列と反対称行列の成分になっていることを示す。これは

```math
\begin{align}
w_{ij}^{\rm S} & = \frac {w_{ij} + w_{ji}} {2}
               = \frac {w_{ji} + w_{ij}} {2}
               = w_{ji}^{\rm S} \tag{ex1.1} \\
w_{ij}^{\rm A} & = \frac {w_{ij} - w_{ji}} {2}
               = - \frac {w_{ji} - w_{ij}} {2}
               = - w_{ji}^{\rm A} \tag{ex1.2}
\end{align}
```

より示される。次に、$w_{ij} = w_{ij}^{\rm S} + w_{ij}^{\rm A}$ と表されることを示す。これは

```math
w_{ij}^{\rm S} + w_{ij}^{\rm A}
  = \frac {w_{ij} + w_{ji}} {2} + \frac {w_{ij} - w_{ji}} {2}
  = w_{ij} \tag{ex1.3}
```

より示される。（証明終）

### 命題２
***命題***　$D$ 次元における高次の多項式の $2$ 次の項において、式 $(1.132)$ が成り立つ。

```math
\sum_{i=1}^D \sum_{j=1}^D w_{ij} x_i x_j = \sum_{i=1}^D \sum_{j=1}^D w^{\rm S}_{ij} x_i x_j \tag{1.132}
```

***証明***　まず式 $(1.132)$ の左辺を、$i = j, \ i < j, \ i > j$ のそれぞれの場合に分解する。

```math
\sum_{i=1}^D \sum_{j=1}^D w_{ij} x_i x_j = 
  \sum_{i=1}^D w_{ii} x_i^2 + 
  \sum_{i=1}^{D-1} \sum_{j=i+1}^{D} w_{ij} x_i x_j + 
  \sum_{i=2}^D \sum_{j=1}^{i-1} w_{ij} x_i x_j \tag{ex2.1}
```

式 $\rm (ex2.1)$ 右辺第１項において、以下の式が成り立つ。

```math
\begin{align}
w_{ii} x_{ii}^2 & = (w^{\rm S}_{ii} + w^{\rm A}_{ii}) x_i^2 \\
                & = \left( w^{\rm S}_{ii} + \frac {w_{ii} - w_{ii}} {2} \right) x_i^2 \\
                & = w^{\rm S}_{ii} x_i^2 \tag{ex2.2}
\end{align}
```

式 $\rm (ex2.1)$ 右辺第２項と第３項においては、$i$ と $j$ の対称性から以下の式が成り立つ。

```math
\sum_{i=1}^{D-1} \sum_{j=i+1}^{D} w_{ij} x_i x_j
  + \sum_{i=2}^D \sum_{j=1}^{i-1} w_{ij} x_i x_j
  = \sum_{i=1}^{D-1} \sum_{j=i+1}^{D} \left( w_{ij} + w_{ji} \right) x_i x_j
\tag{ex2.3}
```

また、$w_{ij}^{\rm S}$ と $w_{ij}^{\rm A}$ はそれぞれ対称行列と反対称行列の成分であることから、以下の式が成り立つ。

```math
\begin{align}
\left( w_{ij} + w_{ji} \right) x_i x_j
  & = \left( 
    w^{\rm S}_{ij} + w^{\rm A}_{ij} + 
    w^{\rm S}_{ji} + w^{\rm A}_{ji}
  \right) x_i x_j \\
  & = 2 w^{\rm S}_{ij} x_i x_j
\tag{ex2.4}
\end{align}
```

式 $\rm (ex2.3)$ と $\rm (ex2.4)$ から、以下の式が成り立つ。

```math
\begin{align}
\sum_{i=1}^{D-1} \sum_{j=i+1}^{D} w_{ij} x_i x_j
  + \sum_{i=2}^D \sum_{j=1}^{i-1} w_{ij} x_i x_j
& = \sum_{i=1}^{D-1} \sum_{j=i+1}^{D} 2 w^{\rm S}_{ij} x_i x_j \\
& = \sum_{i=1}^{D-1} \sum_{j=i+1}^{D} w^{\rm S}_{ij} x_i x_j
  + \sum_{i=2}^D \sum_{j=1}^{i-1} w^{\rm S}_{ij} x_i x_j
\tag{ex2.5}
\end{align}
```

式 $\rm (ex2.1), (ex2.2), (ex2.5)$ より、

```math
\begin{align}
\sum_{i=1}^D \sum_{j=1}^D w_{ij} x_i x_j 
  & = \sum_{i=1}^D w_{ii} x_i^2 + 
    \sum_{i=1}^{D-1} \sum_{j=i+1}^{D} w_{ij} x_i x_j + 
    \sum_{i=2}^D \sum_{j=1}^{i-1} w_{ij} x_i x_j \\
  & = \sum_{i=1}^D w^{\rm S}_{ii} x_i^2 + 
    \sum_{i=1}^{D-1} \sum_{j=i+1}^{D} w^{\rm S}_{ij} x_i x_j + 
    \sum_{i=2}^D \sum_{j=1}^{i-1} w^{\rm S}_{ij} x_i x_j \\
  & = \sum_{i=1}^D \sum_{j=1}^D w^{\rm S}_{ij} x_i x_j 
\tag{ex2.6}
\end{align}
```

が示された。（証明終）


### 命題３

***命題***　行列 $w_{ij}^{\rm S}$ の独立パラメータの数が $D(D+1) / 2$ で与えられる。

***証明***　行列 $w_{ij}^{\rm S}$ は対称行列なので、上三角（または下三角）部分の要素が決定すれば、全ての要素が決定される。この時、上三角部分の要素数は $D(D+1) / 2$ で表される。（証明終）