部分空間法　CLAFIC

# はじめに
- 本記事は　はじめてのパターン認識　第九章　部分空間法のパートの勉強まとめです。
- 部分空間法にはいくつか種類があるようですが、ここでは本に倣って相関行列を用いたCLAFIC法を勉強しました。

# 部分空間法とは
- 分類器の一種。
- 各クラスのデータが成す部分空間の効率的な表現（基底ベクトル）を学習。
- 未知データを各クラスの部分空間に射影したときの大きさでクラス分類を決定。
- 識別に要する時間が少ない。

# CLAFIC法の導出
部分空間法の一種である部分空間法の導出を行います。

入力データからクラスを識別する分類器を作成したいと考えます。
これにあたって、あるテストデータセットDが与えられているとします。
Dは説明変数の集まり $\boldsymbol{X}$ と、そのデータの属するクラス $\boldsymbol{Y}$ から成っており、そのデータの各組を$\boldsymbol{x}, y$ のように表します。
また、$y$ は クラス $C_1, C_2..., C_K$ のK個のクラスのいずれかであるとしましょう。
つまり、以下のように定義します。

```math
データセット：\boldsymbol{D} = \{\boldsymbol{X}, \boldsymbol{Y}\} \\
説明変数：\boldsymbol{x} \in \boldsymbol{X}, \quad
\boldsymbol{x} \in R_d \\
クラス：y \in \boldsymbol{Y}, \quad y \in \{C_1, C_2, ... , C_K\}
```

これら各クラスに属するデータ群は、説明変数が十分にクラス識別に役立つとすれば、d次元の説明変数から成る空間中でクラスごとにまとまって分布いると考えることができます。
この、空間中でのクラスごとの分布をどうにか効率的に表現できれば、新しい入力に対してどのクラス分布が最も当てはまるか評価できそうです。
クラス分布の効率的な表現は、もとのd次元空間からクラスごとに $d_i$次元 $(d_i \leq d)$ の部分空間として抜き出して表現できればよさそうです。
クラス $C_i$ の部分空間を $S_i$ とし、これを張る基底ベクトルの組 $\boldsymbol{u_i}$ を 

```math
\boldsymbol{u_i} = \{\boldsymbol{u_i1}, \boldsymbol{u_i2}, ..., \boldsymbol{u_id_i} \}
```
と表します。

すると、データセットの説明変数 $\boldsymbol{x}$ からクラスごとに適切なクラス分布の基底ベクトルの組 $\boldsymbol{u}$ を求めることが分類器の学習だといえます。


さて、ここでは基底ベクトルの適切さを「各クラスのデータセットの部分空間上での長さ」と定義します。
つまり、部分空間に次元を落として射影したときに、正射影ベクトルが長ければ元の入力ベクトルをよく表現できており、適切な部分空間（とその基底ベクトル）だと判断します。
これは、以下のような数式で表現できます。

```math
{\begin{eqnarray}
max(E \{ \sum_{j = 1}^{d_i} (x^T u_{ij})^2 | x\in C_i \}) )
& = max(& E \{\sum_{j = 1}^{d_i} (x^T u_{ij}) (x^T u_{ij})^T | x \in C_i \} )\\
& = max(& E \{ \sum_{j = 1}^{d_i} x^T u_{ij} u_{ij}^T x | x \in C_i \} ) \\
& = max(& E \{ x^T ( \sum_{j = 1}^{d_i} u_{ij} u_{ij}^T ) x | x \in C_i \} ) \\
& = max(& E \{ x^T P_i x | x \in C_i \} )\\
\end{eqnarray}
}
```

ただし $\sum_{j = 1}^{d_i} u_{ij} u_{ij}^T = P_i$ と置いています。この行列は重要なので射影行列と呼びます。

上記は$\boldsymbol{u_{ij}}$を大きくすればしただけ大きくなってしまいます。
そこで解を得るために $\boldsymbol{u_{ij}}$ の大きさに対して制約を設けますが、今 $\boldsymbol{u_{ij}}$ は基底ベクトルでもあるので大きさを1に揃えるときれいです。

```math
条件：||u_{ij}||=1
```

さて、ラグランジュの未定乗数法で最大化をすると以下になります。

```math
{\begin{eqnarray}
L_i (u_{ij}) & = & \sum_{j = 1}^{d_i} E \{(x^T u_{ij})^2 \} - \sum_{j = 1}^{d_i} \lambda_{ij} (u_{ij}^T u_{ij} - 1)\\
& = & \sum_{j = 1}^{d_i} u_{ij}^T E\{ x^T x | x \in C_i \} u_{ij} - \sum_{j = 1}^{d_i} \lambda_{ij} (u_{ij}^T u_{ij} - 1)\\
& = & \sum_{j = 1}^{d_i} u_{ij}^T Q_i u_{ij} - \sum_{j = 1}^{d_i} \lambda_{ij} (u_{ij}^T u_{ij} - 1)\\
\end{eqnarray}
}
```

```math
{\begin{eqnarray}
\frac{\partial L_i(u_{ij})}{\partial u_{ij}}  =  2 Q_i u_{ij} - 2 \lambda_{ij} u_{ij} = 0\\
\end{eqnarray}
\\
\therefore Q_i u_{ij} = \lambda_{ij} u_{ij}
}
```

ただし、クラス$C_i$ に属するデータセットで構成された相関行列
```math
E \{ x^T x | x \in C_i \} 
```
を$Q_i$ と置いています。

上記の意味するところは、クラス$C_i$ に属するデータセットで構成された相関行列の固有ベクトルを基底ベクトルにすることで、適切な部分空間が得られるということです。

さて、固有ベクトルは複数存在する場合がありますが、どの固有ベクトルを選択すればよいでしょう。
ここである固有ベクトル $u_{ij}$ だけを基底ベクトルとした部分空間の適切さを評価してみます。

```math
{\begin{align}
E \{(x^T u_{ij})^2 \} &= u_{ij}^T Q_i u_{ij} \\
& =  u_{ij}^T \lambda_{ij} u_{ij} \\
& =  \lambda_{ij} u_{ij}^T u_{ij}\\
& =  \lambda_{ij} \quad (\because ||u_{ij}|| = 1)\\
\end{align}
}
```

この結果より、固有値が大きい固有ベクトルほど基底ベクトルとしてふさわしそうです。
そして基底ベクトルの組では選択した固有ベクトルの組の固有値の和になります。

```math
{\begin{align}
\sum_{j=1}^{d_j} E \{(x^T u_{ij})^2 \} &= \sum_{j=1}^{d_j} \lambda_{ij}
\end{align}
}
```

さて、これは部分空間で用いる基底の数＝次元 $d_i$ が大きければ大きいほど大きくなってしまいます。
そこで$d_i$をシステマチックに制限して各クラスで平等に評価できるようにしたいです。
各クラスで累積固有値が $\kappa$ 程度で一定になるようにしてみます。なお $\kappa$ は忠実度と呼ばれます。

すると、各クラスに対して以下となる $d_i$ を部分空間の次元とすることで、各クラスのデータセットの射影の期待値が一定にそろいます。

```math
累積固有値：a(d_i) = \sum_{j = 1}^{d_i} \lambda_{ij} \\ 
次元の選択基準：a(d_i - 1) \leq \kappa < a(d_i)
```



未知データに対するクラスの判定では、射影ベクトルが最長、かつ、threshold以上を条件にすればよいです。

```math
クラス推定：{全てのj≠iについてx^T P_j x < x^T P_i xであればx \in C_i} \\
リジェクト条件：　{\max_i[\frac{x^T P_i x}{x^T x}]}

```


# 参考
- https://www.iwanttobeacat.com/entry/2018/07/02/220900
    - pythonでCLAFICを実装している数少ない記事です
- はじめてのパターン認識