- 講師:山崎俊彦
- 参考書:CG-ARTS協会発行「ディジタル画像処理」
- 参考書:R. Szeliski, Computer Vision Algorithms and Applications, Springer (PDF版はインターネット上で無料公開)
In [1]:
import numpy as np
import matplotlib.pyplot as plt
主成分分析(PCA)¶
In [2]:
N = 20
seed = 0
In [3]:
X = np.linspace(0,1,N)
Y = X + np.random.RandomState(N).normal(loc=0, scale=5e-2, size=N)
data = np.vstack((X, Y))
In [4]:
def Rotate(x,radian):
A = np.array([
[np.cos(radian), -np.sin(radian)],
[np.sin(radian), np.cos(radian)]
])
return np.dot(A, data)
In [5]:
fig = plt.figure(figsize=(10,4))
ax = fig.add_subplot(1,2,1)
ax.scatter(X,Y,color="black"), ax.set_title("Original")
X_tra, Y_tra = Rotate(data, radian=-1/4*np.pi)
ax = fig.add_subplot(1,2,2)
ax.scatter(X_tra, Y_tra, color="red"), ax.set_title("Rotated"), ax.set_ylim(-1/2*np.sqrt(2),1/2*np.sqrt(2))
plt.tight_layout()
plt.show()
- $2$ 次元空間で左上図のようなデータがあったとする。この時、このデータを表現するのに $(x,y)$ の二次元が必要だろうか?
- データ全体を右に $1/4\pi$ 回転させると、右上図のようなデータれるとなる。この場合、$y^{\prime}$ 軸方向はノイズとみなせ、$x^{\prime}$ 軸のみでデータを表現していると言える。
- この例のように、$K$ 次元のデータであっても、で0他の偏りによって $M(<K)$ 次元で表現できることが多々ある。
- こういった場合に、「$M$ 方向の軸をどのように決めるか?」、「$M$ をどうやって決めるか?」などが問題となる。
※ 詳しくは主成分分析(PCA)に記載。
線形判別分析(LDA)¶
入力ベクトル $\mathbf{x}$ を $K$ クラスの一つ $C_k$ に割り当てる関数である識別(決定面が超平面となるとき、線形識別(linear discriminant))を、「次元の削減」という観点から捉えることができる。
2クラス分類¶
$D$ 次元入力ベクトルを得て、それを以下の式で $1$ 次元に射影するとする。
$$y = \mathbf{w}^T\mathbf{x}\qquad (4.20)$$- ある閾値を設定し、$y\geq-w_0$ の場合クラス $C_1$、そうでない場合クラス $C_2$ であるとすると、標準的な線形分類器が得られる。
- 一般に、$D$ 次元から $1$ 次元へ射影することによって相当量の情報量の損失を発生させる。
- 重みベクトル $\mathbf{w}$ の要素を調整することで、クラスの分離を最大にする射影を選択したい。
- $\mathbf{w}$ 上へ射影された際のクラス分離度の最も簡単な測定法は、射影されたクラスの平均の分離度(以下の式)を見ることである。 $$m_2-m_1 = \mathbf{w}^T\left(\mathbf{m}_2-\mathbf{m}_1\right) = \mathbf{w}^T\left(\frac{1}{N_2}\sum_{n\in C_2}\mathbf{x}_n -\frac{1}{N_1}\sum_{n\in C_1}\mathbf{x}_n\right)\qquad (4.21)\ \&\ (4.22)$$
- 上の式は $\mathbf{w}$ の値を大きくすればいくらでも大きな値にすることができるので、$\mathbf{w}$ が単位長である($\sum_i w_i^2 = 1$)という制約を加える。
- ラグランジュ乗数を用いてこれを解くと、$\mathbf{w}\propto(\mathbf{m}_2-\mathbf{m}_1)$ が得られる。
- クラス分布の非対角な共分散が強い場合など、一般に、各クラスの平均値だけを見ていても上手く判別する事ができない。
- そこでフィッシャーが提案した方法が、「射影されたクラス平均間の分離度を大きくすると同時に、各クラス内では小さな分散を与える関数を最大化する」
- クラス $C_k$ から射影されたデータのクラス内分散は以下で与えられる。 $$s_k^2 = \sum_{n\in C_k}(y_n-m_k)^2\qquad (4.2)$$
- 全データ集合に対する総クラス内分散が $s_1^2+s_2^2$ であると定義する。
- フィッシャーの判別基準は、クラス間分離度とクラス内分散の比率で表される。 $$ \begin{aligned} J(\mathbf{w}) &= \frac{(m_2-m_1)^2}{s_1^2 + s_2^2} & (4.25)\\ &= \frac{\mathbf{w}^T\mathbf{S}_{\mathrm{B}}\mathbf{w}}{\mathbf{w}^T\mathbf{S}_{\mathrm{W}}\mathbf{w}} & (4.27)\\ \mathbf{S}_{\mathrm{B}} &= (\mathbf{m}_2-\mathbf{m}_1)(\mathbf{m}_2-\mathbf{m}_1)^T & (4.27)\\ \mathbf{S}_{\mathrm{W}} &= \sum_{n\in C_1}(\mathbf{x}_n-\mathbf{m}_1)(\mathbf{x}_n-\mathbf{m}_1)^T + \sum_{n\in C_2}(\mathbf{x}_n-\mathbf{m}_2)(\mathbf{x}_n-\mathbf{m}_2)^T& (4.27)\\ \end{aligned} $$
- $\mathbf{S}_{\mathrm{B}}$ をクラス間共分散行列(between-class covariance matrix)と呼ぶ。
- $\mathbf{S}_{\mathrm{W}}$ を(総)クラス内共分散行列(within-class covariance matrix)と呼ぶ。
- $J(\mathbf{w})$ を $\mathbf{w}$ に関して微分すると、以下の式が満たされる場合に $J(\mathbf{w})$ が最大となる事がわかる。 $$ \begin{aligned} \frac{dJ(\mathbf{w})}{d\mathbf{w}} &= \frac{\left(\mathbf{w}^T\mathbf{S}_{\mathrm{B}} + \mathbf{S}_{\mathrm{B}}\mathbf{w}\right)\left(\mathbf{w}^T\mathbf{S}_{\mathrm{W}}\mathbf{w}\right) - \left(\mathbf{w}^T\mathbf{S}_{\mathrm{B}}\mathbf{w}\right)\left(\mathbf{w}^T\mathbf{S}_{\mathrm{W}} + \mathbf{S}_{\mathrm{W}}\mathbf{w}\right)}{\left(\mathbf{w}^T\mathbf{S}_{\mathrm{W}}\mathbf{w}\right)^2}\\ \left(\mathbf{w}^T\mathbf{S}_{\mathrm{B}}\mathbf{w}\right)\left(\mathbf{w}^T\mathbf{S}_{\mathrm{W}} + \mathbf{S}_{\mathrm{W}}\mathbf{w}\right) &= \left(\mathbf{w}^T\mathbf{S}_{\mathrm{B}} + \mathbf{S}_{\mathrm{B}}\mathbf{w}\right)\left(\mathbf{w}^T\mathbf{S}_{\mathrm{W}}\mathbf{w}\right)\\ \left(\mathbf{w}^T\mathbf{S}_{\mathrm{B}}\mathbf{w}\right)\mathbf{S}_{\mathrm{W}}\mathbf{w}&= \left(\mathbf{w}^T\mathbf{S}_{\mathrm{W}}\mathbf{w}\right)\mathbf{S}_{\mathrm{B}}\mathbf{w}\qquad (4.29) \end{aligned} $$
- $(4.27)$ から、$\mathbf{S}_{\mathrm{B}}\mathbf{w}$ は常に $(\mathbf{m}_2-\mathbf{m}_1)$ と同じ方向を持つ。
- $\mathbf{w}$ の方向だけが重要で、大きさは考慮する必要がないので、スカラーファクタ $\left(\mathbf{w}^T\mathbf{S}_{\mathrm{W}}\mathbf{w}\right)$ と $\left(\mathbf{w}^T\mathbf{S}_{\mathrm{B}}\mathbf{w}\right)$ を無視できる。
- $(4.29)$ の両辺に $\mathbf{S}_{\mathrm{W}}^{-1}$ を左からかけて、フィッシャーの線形判別(Fisher's linear discriminant)が得られる。 $$\mathbf{w}\propto\mathbf{S}_{\mathrm{W}}^{-1}(\mathbf{m}_2-\mathbf{m}_1)\qquad (4.30)$$
- フィッシャーの線形判別(Fisher's linear discriminant)は、厳密には識別子ではなく、むしろ $1$ 次元へ削減する際のデータの射影方向の選択を行なっている。
In [6]:
from kerasy.ML.decomposition import LDA
In [7]:
N1 = 100; N2 = 100
cov = [[10,1],[1,3]]
In [8]:
x1 = np.random.RandomState(seed).multivariate_normal([0,7], cov, N1)
x2 = np.random.RandomState(seed+1).multivariate_normal([8,6], cov, N2)
x1min = np.min(x1); x1max = np.max(x1)
x2min = np.min(x2); x2max = np.max(x2)
m1 = np.mean(x1, axis=0); m2 = np.mean(x2, axis=0)
m = (m1+m2)/2
data = np.r_[x1,x2]
In [9]:
X = np.linspace(-100,100,1000)
In [10]:
fig = plt.figure(figsize=(12,6))
for i,tf in enumerate([True, False]):
model = LDA()
model.fit(x1, x2, mean_only=tf)
w1,w2 = model.w
alpha = -w2/w1
beta = m[1] - alpha*m[0]
x_features = model.transform(data)
axT = fig.add_subplot(2,2,i+1)
axT.plot(X,X*(-w2/w1)+beta, color="black", label="linear discriminant")
axT.scatter(x1[:,0], x1[:,1], color="blue", label="class1")
axT.scatter(x2[:,0], x2[:,1], color="red", label="class2")
axT.scatter(m1[0],m1[1],color="green",marker="*",s=200), axT.scatter(m2[0],m2[1],color="green",marker="*",s=200,label="mean")
axT.set_xlim(x1min,x1max), axT.set_ylim(x2min,x2max)
axT.set_xticks([]), axT.set_yticks([]), axT.legend(), axT.set_title("Only Mean" if tf else "Fisher's linear discriminant")
axB = fig.add_subplot(2,2,3+i)
axB.hist(x_features[:N1], alpha=0.3, color="blue", label="class1")
axB.hist(x_features[N1:], alpha=0.3, color="red", label="class2")
axB.set_xticks([]), axB.set_yticks([]), axB.legend()
plt.tight_layout()
plt.show()
In [ ]: