判別分析とは

---

与えられたデータについて、その特徴量の情報から各サンプルがどのグループに属するかを判別する方法を 判別分析 といいます。

設定

いま、2群 $G_1,G_2$ の判別を考えます。このとき、群 $G_j$ に属する $i$ 番目のサンプルを、

$${{\mathbf{x}}_i}^{(j)}:=(x_{i1},x_{i2},\dots ,x_{ip}{)}^{\top }$$

と定義します。 $p$ はデータを説明するための特徴量の数です。ここで、各特徴量の重みを表す $p$ 次元ベクトル $\mathbf{w}$：

$$\mathbf{w}:=(w_1,w_2,\dots ,w_p{)}^{\top }$$

を考え、${{\mathbf{x}}_i}^{(j)}$ を重みつけし、特徴量の次元を1次元に射影したサンプルを次で定義します：

$${y_i}^{(j)}:={\mathbf{w}}^{\top }{{\mathbf{x}}_i}^{(j)}$$

いま、群 $G_1,G_2$ のどちらかに属するかわからないサンプル $\mathbf{x}$ があるとします。このとき、$\mathbf{x}$ がどちらの群に属するかの情報を与える関数 $f(\mathbf{x})$ を 判別関数 といいます。

フィッシャーの線形判別

---

2群 $G_1,G_2$ への分類を行うために、フィッシャーの線形判別 とよばれる方法を用いることができます。

群内分散・群間分散

各群 $G_j$ 内の射影したサンプルの分散（群内分散）は、

$$\frac{1}{n_j-1}\sum _{i=1}^{n_j}({y_i}^{(j)}-{\bar{y}}^{(j)}{)}^2={\mathbf{w}}^{\top }{\Sigma }_j\mathbf{w}$$

で与えられます。ここで ${\Sigma }_j$ は群 $G_j$ のサンプル ${{\mathbf{x}}_1}^{(j)},\dots ,{{\mathbf{x}}_{n_j}}^{(j)}$ の分散共分散行列です。いっぽう、群 $G_1,G_2$ 間の分散（群間分散）は、2群のサンプル平均の差を考えることで、

$$({\bar{y}}^{(1)}-{\bar{y}}^{(2)}{)}^2=[{\mathbf{w}}^{\top }({\bar{\mathbf{x}}}^{(1)}-{\bar{\mathbf{x}}}^{(2)}){]}^2$$

と定義します。

フィッシャーの線形判別関数

判別関数を構成するために、最も適切な重み $\mathbf{w}$ の条件を考えます。いま、各群のサンプル平均どうしは離れていたほうがよく、一方で群内での分散は小さいほうが適するため、

$$\lambda (\mathbf{w};\mathbf{x})=\frac{[{\mathbf{w}}^{\top }({\bar{\mathbf{x}}}^{(1)}-{\bar{\mathbf{x}}}^{(2)}){]}^2}{{\mathbf{w}}^{\top }\Sigma \mathbf{w}}$$

という基準を最大化することを考えます。ここで $\Sigma$ は統合分散共分散行列：

$$\Sigma :=\frac{(n_1-1){\Sigma }_1+(n_2-1){\Sigma }_2}{n_1+n_2-2}$$

です。最適な射影方向を定める重みは、

$$\frac{\partial \lambda (\mathbf{w};\mathbf{x})}{\partial \mathbf{w}}=0⟺\hat{\mathbf{w}}={\Sigma }^{-1}({\bar{\mathbf{x}}}^{(1)}-{\bar{\mathbf{x}}}^{(2)}{)}^2$$

と与えられます。これを用いて、分類未知のサンプル $\mathbf{x}$ は $y={\hat{\mathbf{w}}}^{\top }\mathbf{x}$ のように射影されることになります。一方、各群のサンプル平均 ${\bar{\mathbf{x}}}^{(j)}$ を $\hat{\mathbf{w}}$ で射影した後の重心位置は、

$$\frac{{\bar{y}}^{(1)}+{\bar{y}}^{(2)}}{2}=\frac{{\hat{\mathbf{w}}}^{\top }{\bar{\mathbf{x}}}^{(1)}+{\hat{\mathbf{w}}}^{\top }{\bar{\mathbf{x}}}^{(2)}}{2}=\frac{1}{2}({\bar{\mathbf{x}}}^{(1)}-{\bar{\mathbf{x}}}^{(2)}){\Sigma }^{-1}({\bar{\mathbf{x}}}^{(1)}+{\bar{\mathbf{x}}}^{(2)})$$

であるので、それらの差分として フィッシャーの線形判別関数 を次のように定義します：

フィッシャーの線形判別関数

$$f(\mathbf{x}):={\hat{\mathbf{w}}}^{\top }\mathbf{x}-\frac{1}{2}({\bar{\mathbf{x}}}^{(1)}-{\bar{\mathbf{x}}}^{(2)}){\Sigma }^{-1}({\bar{\mathbf{x}}}^{(1)}+{\bar{\mathbf{x}}}^{(2)})$$

$f(\mathbf{x})>0$ のとき：

$\mathbf{x}$ は群 $G_1$ と推定される

$f(\mathbf{x})<0$ のとき：

$\mathbf{x}$ は群 $G_2$ と推定される

マハラノビス距離による判別

$$D^2:=\lambda (\hat{\mathbf{w}};\mathbf{x})=({\bar{\mathbf{x}}}^{(1)}-{\bar{\mathbf{x}}}^{(2)}){\Sigma }^{-1}({\bar{\mathbf{x}}}^{(1)}-{\bar{\mathbf{x}}}^{(2)})$$

をサンプル $\mathbf{x}$ から重心位置への マハラノビス距離（の平方）といいます。一方、

$${D_j}^2:=(\mathbf{x}-{\bar{\mathbf{x}}}^{(j)}){{\Sigma }_j}^{-1}(\mathbf{x}-{\bar{\mathbf{x}}}^{(j)})$$

をサンプル $\mathbf{x}$ から群 $G_j$ のサンプル平均 ${\bar{\mathbf{x}}}^{(j)}$ へのマハラノビス距離（の平方）といいます。ここで、フィッシャーの線形判別関数との間に、

$$f(\mathbf{x})=\frac{{D_2}^2-{D_1}^2}{2}$$

の関係があるため、

2次判別関数

$$g(\mathbf{x}):={D_2}^2-{D_1}^2$$

$g(\mathbf{x})>0$ のとき：

${D_1}^2$ のほうが小さく、$\mathbf{x}$ は群 $G_1$ と推定される

$g(\mathbf{x})<0$ のとき：

${D_2}^2$ のほうが小さく、$\mathbf{x}$ は群 $G_2$ と推定される

のように判別することも可能です。この場合、統合した分散共分散行列 $\Sigma$ の代わりに、各群ごとの分散共分散行列 ${\Sigma }_j$ を用いることになります。

正準判別

---

多群の判別において、サンプルを低次元に射影して重心位置との比較で判別を行う方法は、正準判別 という名前で呼ばれます。いま、$g$ 個の群があるとき、各群のサンプル平均を ${\bar{\mathbf{x}}}^{(j)}$、分散共分散行列を ${\Sigma }_j$ とし、系の全サンプルの平均を $\bar{\mathbf{x}}$ とするとき、群内変動行列 $S_W$ および 群間変動行列 $S_B$ を以下で定義します：

$$S_W:=\sum _{j=1}^g{n}_j({\bar{\mathbf{x}}}^{(j)}-\bar{\mathbf{x}})({\bar{\mathbf{x}}}^{(j)}-\bar{\mathbf{x}}{)}^{\top }$$

$$S_B:=\sum _{j=1}^g(n_j-1){\Sigma }_j$$

これらに対し、比 ${S_W}^{-1}{S}_B$ を最大化するような射影軸 $\hat{\mathbf{w}}$ は ${S_W}^{-1}{S}_B$ の固有ベクトルとして複数得られます。

サポートベクターマシン

---

基本理論

2群 $G_1,G_2$ のいずれかに属する $p$ 個の特徴量からなる トレーニングデータ ${\mathbf{x}}_1,{\mathbf{x}}_2.\dots ,{\mathbf{x}}_n$ と、属するクラスを表すクラスラベル：

$$y_i=\{\begin{array}{ll}1& (\text{if}{\mathbf{x}}_i\in G_1)\\ -1& (\text{if}{\mathbf{x}}_i\in G_2)\end{array}$$

が与えられているとします。いま、分類未知のサンプル $\mathbf{x}$ に対し、トレーニングデータから $\mathbf{x}$ がどちらの群に属するかを判別するための判別器を構成することを考えましょう。サポートベクターマシン (SVM) と呼ばれる手法では、もとのサンプルをある関数 $\varphi$ で変換した $\varphi (\mathbf{x})$ について、判別関数：

$$f(\mathbf{x})={\mathbf{w}}^{\top }\varphi (\mathbf{x})+b$$

を考え、$f(\mathbf{x})$ の正負に応じて $\mathbf{x}$ に対応するクラスラベル $y$ を貼ることで判別を行います：

$$\{\begin{array}{llc}f(\mathbf{x})\ge 0& ⟺& y=1\\ f(\mathbf{x})<0& ⟺& y=-1\end{array}$$

つまり、トレーニングデータ ${\mathbf{x}}_i$ については、

$$y_{i}f({\mathbf{x}}_{\mathbf{i}})>0$$

をみたすため、これを最適化の制約条件とします。

$f(\mathbf{x})=0$ は2群を完全に分離するような判別平面を与えることになりますが、SVMにおいてはこれを最適化するために各トレーニングデータ ${\mathbf{x}}_i$ と平面の最短距離を考えます。これを マージン といい、次で表されます^[1]：

$$\frac{|{\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_i)+b|}{||\mathbf{w}||}$$

つまり、SVMは $\mathbf{w},b$ についての以下のような最適化問題として表すことができます：

SVM

$$\underset{\mathbf{w},b}{\max }\underset{i\in \{1,\dots ,n\}}{\min }\frac{|{\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_i)+b|}{||\mathbf{w}||}\text{s.t.}{y}_i({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_{\mathbf{i}})+b)>0$$

サポートベクトル

上記の最適化問題は、$y_i=\pm 1$ であることに注目すると、制約条件をより厳しくして、

$$\underset{\mathbf{w},b}{\max }\underset{i\in \{1,\dots ,n\}}{\min }\frac{|{\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_i)+b|}{||\mathbf{w}||}\text{s.t.}{y}_i({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_{\mathbf{i}})+b)\ge |({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_{\mathbf{i}})+b)|$$

とすることも可能です。ここで、${\mathbf{x}}_i$ のうち判別平面に一番近い $\varphi ({\mathbf{x}}_i)$ を与えるものを サポートベクトル といい、これを ${\mathbf{x}}_s$ とするとき、そのマージン $M$ は以下を満たすはずです：

$$M:=\underset{i\in \{1,\dots ,n\}}{\min }|{\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_i)+b|=|{\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_s)+b|=y_i({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_s)+b)$$

すなわち、サポートベクトルにのみ注目するとき、最適化問題はサポートベクトルが与えるマージン $M$ を用いて $\mathbf{w}\to \mathbf{w}/M,b\to b/M$ と置き換えることで正規化することができます：

$$\underset{\mathbf{w},b}{\max }\frac{1}{||\mathbf{w}||}\text{s.t.}{y}_i({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_{\mathbf{i}})+b)\ge 1$$

さらに、$||\mathbf{w}|{|}^2$ に関する最小化問題に置き換えることまでできて、

SVM：別表現

$$\underset{\mathbf{w},b}{\min }||\mathbf{w}|{|}^2\text{s.t.}{y}_i({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_{\mathbf{i}})+b)\ge 1$$

という表現を得ます。

カーネル関数とSVMの種類

パラメータ $\mathbf{w}$ について、

$$\mathbf{w}=\sum _{i=1}^n{\alpha }_i\varphi ({\mathbf{x}}_i)$$

というトレーニングデータでの線形展開を考えます。これを用いると、最適化問題の別の形式として、

SVM：カーネル関数による表現

$$\underset{{\alpha }_1,\dots ,{\alpha }_n,b}{\min }\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)\text{s.t.}{y}_i\left(\sum _{j=1}^n{\alpha }_{j}K({\mathbf{x}}_{\mathbf{j}},{\mathbf{x}}_i)+b\right)\ge 1$$

と表すこともできます。ここで、トレーニングデータの内積を用いる関数 $K$：

$$K({\mathbf{x}}_i,{\mathbf{x}}_j):=\varphi ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)$$

を カーネル関数 といいます。SVMはカーネル関数によって線形・非線形に大別できます：

名称	表式	SVM形式
線形カーネル	${{\mathbf{x}}_i}^{\top }{\mathbf{x}}_j$	線形SVM
多項式カーネル	$(c_1{{\mathbf{x}}_i}^{\top }{\mathbf{x}}_j+c_0{)}^d$	非線形SVM
ガウシアンカーネル	$\exp \left(-\frac{||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2}{2{\sigma }^2}\right)$	非線形SVM

ハードマージン・ソフトマージン

すべてのトレーニングデータが線形分離可能でない場合、そのような ${\mathbf{x}}_i$ に対し、

$${\xi }_i:=1-y_i({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_{\mathbf{i}})+b)\ge 0$$

のペナルティ（線形分離可能であれば $0$ ）を課して、最適化問題を次のように書き換えます：

ソフトマージンSVM

$$\underset{\mathbf{w},b,\mathbf{\xi }}{\min }\frac{1}{2}||\mathbf{w}|{|}^2+C\sum _{i=1}^n{\xi }_i\text{s.t.}{\xi }_i\ge 1-y_i({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_{\mathbf{i}})+b)\ge 0$$

ここで $C$ はペナルティの強さを制御するパラメータであり、このような形式のSVMを ソフトマージンSVM と呼びます。対して、すべてのデータが線形分離可能であれば、今までの最適化条件の下 ハードマージンSVM を用いることができます。

参考

---

書籍

永田靖・棟近雅彦『多変量解析入門』（サイエンス社, 2001）第7章

『統計学実践ワークブック』（学術図書出版社, 2020）第23章

サイト

線形SVM | Qiita

SVMをおさらい（ソフトマージン線形SVMの編）| Qiita

脚注

---

1. ここでは絶対値とベクトルの大きさの表記を分けるために、ベクトルの ノルム $||\mathbf{w}||=\sqrt{\mathbf{w}\cdot \mathbf{w}}$ で書いています。 ↩︎