線形識別関数による2クラス分類

# はじめに
線形識別関数を使った2クラス分類について、数式を使った理論的な解説を行います。


# 線形識別関数
まず線形識別関数がどういうものなのかについて説明します。ここで考える問題は2クラス分類です。2クラス分類は、与えられたオブジェクトの性質に基づいて、オブジェクトを2つのクラスに分類する問題です。オブジェクトの形質を数値化した説明変数を$d$次元のベクトルとして、$\boldsymbol{x}:=(x_1,\dots,x_d)^\mathrm{T}\in\mathbb{R}^d$と書くことにします。またオブジェクトのクラスを表す2値変数を$y\in\lbrace1,2\rbrace$とします。$y=1$はクラス1、$y=2$はクラス2に属していることを表しています。

### 線形識別関数の定義
線形識別関数は変数$\boldsymbol{x}\in\mathbb{R}^d$、係数ベクトル$\boldsymbol{w}\in\mathbb{R}^d$、バイアス$w_0\in\mathbb{R}$に対して、

```math
f(\boldsymbol{x}):=\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+w_0
```
で定義されます。したがって、線形識別関数のパラメータ数は$d+1$個です。

### 線形識別関数による分類
線形識別関数を使った2クラス分類では、説明変数$\boldsymbol{x}$のオブジェクトのクラスを以下の式で予測します。

```math
\text{識別クラス} = \begin{cases}
1 & (f(\boldsymbol{x}) \geq 0) \\
2 & (f(\boldsymbol{x}) < 0)
\end{cases}
```
2つのクラスの識別境界は$f(\boldsymbol{x})=0$、つまり、

```math
\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+w_0=0
```
で与えられます。これは$d$次元空間内の$d-1$次元の超平面を表しています。この超平面により、空間は2つの領域に分割されています。超平面の表側の領域にいるのか、裏側の領域にいるのかでクラスが定まるというのが、線形識別関数による2クラス分類のモデルです。このモデルのもとでは、識別境界に近いほど識別が難しい微妙なデータと考えるのが自然です。線形識別関数の絶対値は、ちょうど識別境界からの距離になっています。

# 線形識別関数のパラメータ推定
次に学習データが与えられたときに、どのように線形識別関数$f(\boldsymbol{x})$のパラメータを決定するか、つまりどういう超平面を設定するのか、について説明していきます。クラス1の学習データの数を$N_1$、クラス2の学習データの数を$N_2$として、全データ数を$N=N_1+N_2$とします。$i$番目のデータの説明変数を$\boldsymbol{x}^{(i)}$、クラスを$y^{(i)}$で表すことにします。$i$番目のデータに対する線形識別関数による予測クラスを$\hat{y}^{(i)}$とします。これは$f(\boldsymbol{x}^{(i)})\geq 0$のとき$\hat{y}^{(i)}=1$、$f(\boldsymbol{x}^{(i)})<0$のとき$\hat{y}^{(i)}=2$となります。

### 単純な手法
最も単純なパラメータの決定方法は、不正解率

```math
\frac{1}{N}\sum_{i=1}^N|\hat{y}^{(i)}-y^{(i)}|
```
が最小になるようにパラメータ$\boldsymbol{w}$と$w_0$を決定することです。ただし、この関数はパラメータに対して、不連続な関数となっているため最適解を見つけるのが難しくなっています。実際、解析的な解を得ることはできません。したがって、より扱うことが容易な損失関数を設定するが必要があります。

### 最小2乗誤差基準
解析的に最適解、つまりパラメータを決定できるような損失関数を考えることにします。損失関数は1つのデータから定まる損失$l_i$の和$L=\sum_{i=1}^Nl_i$で与えられるとするのが自然です。そして$l_i$は$f(\boldsymbol{x}^{(i)})$について、連続でかつ単純な関数になっている方が望ましいです。そこで以下のような二次関数を考えます。

```math
l_i=\left(f(\boldsymbol{x}^{(i)})-t^{(i)}\right)^2
```
このとき$t^{(i)}$は以下のような条件を満たす定数です。もし線形識別関数のパラメータが最適化されている場合、$f(\boldsymbol{x}^{(i)})$は$i$番目のデータのクラスが1のとき$f(\boldsymbol{x}^{(i)})>0$であり、逆に2のときに$f(\boldsymbol{x}^{(i)})<0$です。このときに損失は小さくなっていて欲しいので、

```math
t^{(i)} \begin{cases}
>0 & (y^{(i)}=1) \\
<0 & (y^{(i)}=2)
\end{cases}
```
であることが要請されます。最も単純なのは、

```math
t^{(i)} =\begin{cases}
+1 & (y^{(i)}=1) \\
-1 & (y^{(i)}=2)
\end{cases}
```
とクラスに応じて符号を設定して、絶対値は共通にすることです。より一般には、絶対値を共通にする必要はなく、よりクラス1もしくは2らしいデータに対して設定する$t^{(i)}$については絶対値を大きくして、微妙なデータについては0付近の値を設定するればよいです。このように決めた$t^{(i)}\ (i=1,\dots,N)$に対して、損失関数は

```math
L=\sum_{i=1}^N \left(f(\boldsymbol{x}^{(i)})-t^{(i)}\right)^2
```
となります。これは$t^{(i)}\in\mathbb{R}$を目的変数とする**線形回帰モデル**の**最小2乗法**での損失関数と一致しています。以下で、この損失関数の最適解を解析的に求めることができることを示していきます。

##### 最適なパラメータの決定
以下の記述を簡単にするために、係数ベクトルにバイアス項も含めた$d+1$次元のベクトル$\bar{\boldsymbol{w}}:=(w_0,w_1,\dots,w_d)^{\mathrm{T}}$を導入し、それに対応して$\bar{\boldsymbol{x}}:=(1,x_1,\dots,x_d)^{\mathrm{T}}$とします。すると線形識別関数はベクトル内積だけで、$f(\boldsymbol{x})=\bar{\boldsymbol{w}}^\mathrm{T}\bar{\boldsymbol{x}}$と表せます。さらに$N\times(d+1) $行列$X$を

```math
X:=(\bar{\boldsymbol{x}}^{(1)},\dots,\bar{\boldsymbol{x}}^{(N)})^\mathrm{T}
```
と定義しデータ行列と呼びます。また$\boldsymbol{t}:=(t^{(1)},\dots,t^{(N)})^\mathrm{T}\in\mathbb{R}^N$を教師ベクトルと呼びます。以上の記法を用いると、損失関数は以下のように行列とベクトルの積を使って表せます。

```math
L(\bar{\boldsymbol{w}})=(\boldsymbol{t}-X\bar{\boldsymbol{w}})^\mathrm{T}(\boldsymbol{t}-X\bar{\boldsymbol{w}})
=\bar{\boldsymbol{w}}^\mathrm{T}X^\mathrm{T}X\bar{\boldsymbol{w}}-2\boldsymbol{t}^\mathrm{T}X\bar{\boldsymbol{w}}+ \boldsymbol{t}^\mathrm{T}\boldsymbol{t}
```
これはパラメータ$\bar{\boldsymbol{w}}$についての2次形式になっています。この関数を$\bar{\boldsymbol{w}}$で微分して$0$になる$\bar{\boldsymbol{w}}$の値こそが、求めたかった最適なパラメータになります。それは

```math
X^\mathrm{T}X\bar{\boldsymbol{w}}_\mathrm{opt}=X^\mathrm{T}\boldsymbol{t}
```
という線形方程式の解です。ここで$X^\mathrm{T}X$の逆行列が存在するとすれば、

```math
\bar{\boldsymbol{w}}_\mathrm{opt}=(X^\mathrm{T}X)^{-1}X^\mathrm{T}\boldsymbol{t}
```
が最適なパラメータです。このようにして行列の計算で最適なパラメータを求めることができました。ここで行った計算は、線形回帰モデルの回帰係数を最小二乗法で求める計算と同じです。

##### コメント
このやり方は最適なパラメータが解析的に求まるという点では良いですが、最初に人の手で$N$個の教師データ$t^{(i)}$をうまく定める必要があるため面倒な手法になっています。

### 他の方法
上記とは異なる方法を考えていきます。線形識別関数は、ベクトル$\bar{\boldsymbol{x}}$を$\bar{\boldsymbol{w}}$の方向の1次元空間へ射影する関数（長さも変える）とみることができます。この説明変数を圧縮した**1次元空間の位置**でクラス分けをするのが、線形識別関数を使った2クラス分類です。ここで、この1次元空間の中でクラス$y=1,2$に対応する領域を$T_y:=\lbrace f(\boldsymbol{x}^{(i)}):i\in C_y\rbrace\subset\mathbb{R}$とします。ここで$C_y$は学習データのうち、クラス$y$に分類されているデータのラベルの集合です。一般に$T_1\cap T_2\neq\emptyset$です。以下では、2つの領域$T_1$と$T_2$がうまく分離できるように、パラメータ$\bar{\boldsymbol{w}}$を決定するという見方で議論をしていきます。

##### クラス間変動
1つ目の方法は、それぞれの領域の重心が遠くなるようにパラメータ$\bar{\boldsymbol{w}}$を決定するという方法です。領域$T_y$の重心$m_y$は

```math
m_y:=\frac{1}{N_y}\sum_{i\in C_y}f(\boldsymbol{x}^{(i)})
```
で定義されます。これは$\boldsymbol{\mu}^{(i)}:=\frac{1}{N_y}\sum_{i\in C_y}\bar{\boldsymbol{x}}^{(i)}$とすると、$m_y=\bar{\boldsymbol{w}}^{\mathrm{T}}\boldsymbol{\mu}^{(i)}$となります。したがって、この方法では、

```math
(m_1-m_2)^2=\bar{\boldsymbol{w}}^{\mathrm{T}}(\boldsymbol{\mu}^{(1)}-\boldsymbol{\mu}^{(2)})(\boldsymbol{\mu}^{(1)}-\boldsymbol{\mu}^{(2)})^{\mathrm{T}}\bar{\boldsymbol{w}}=:\bar{\boldsymbol{w}}^{\mathrm{T}}S_B\bar{\boldsymbol{w}}
```
が最大になる$\bar{\boldsymbol{w}}$を選択します。上の損失関数も2次形式なので解析的に解を導出できます。ここでは省略します。

##### クラス内変動
2つ目の方法は、それぞれの領域が大きく広がることがないようにパラメータ$\bar{\boldsymbol{w}}$を決定するという方法です。この方法ではクラス内分散

```math
\begin{align}
\sigma_y^2:&=\frac{1}{N_y}\sum_{i\in C_y}\left(\bar{\boldsymbol{w}}^{\mathrm{T}}(\boldsymbol{x}^{(i)}-\boldsymbol{\mu}^{(y)})\right)^2
\\
&=\bar{\boldsymbol{w}}^{\mathrm{T}}\left(\frac{1}{N_y}\sum_{i\in C_y}(\boldsymbol{x}^{(i)}-\boldsymbol{\mu}^{(y)})^{\mathrm{T}}(\boldsymbol{x}^{(i)}-\boldsymbol{\mu}^{(y)})\right)\bar{\boldsymbol{w}}
=:\bar{\boldsymbol{w}}^{\mathrm{T}}S_y\bar{\boldsymbol{w}}
\end{align}
```
を考えます。そして$\sigma_1^2+\sigma_2^2$が小さくなるように$\bar{\boldsymbol{w}}$を決定します。

上記の2つの方法は、最小2乗誤差基準とはことなり、事前に$t^{(i)}$のようなパラメータを設定する必要がありません。


# 線形判別分析

# 参考文献
+ [平井有三, 『はじめてのパターン認識』, 2012, 森北出版](https://amzn.to/34GHbdU)