takahiro_itazuriの公倍数的ブログ

本やWebを通して学習したことをまとめるブログです。最大公約数(つまり、共通部分)的なという表現と対比して、「なるべく包括的にカバーしつつ、更に+αの要素も加えられたらいいな」という意味で公倍数的ブログと名付けました。

【ML基礎】線形識別法

線形識別器とパーセプトロン

$d$次元ベクトル$x$に対して、線形な識別関数を線形識別関数という。線形識別関数は以下のようにあらわされる。
\begin{align}
g(x) = w_0 + \sum_{i=1}^{d} w_i x_i
\end{align}
ここで以下のようにする。
\begin{align}
X &= {(1,x^T)}^{T} = {(1, x_1, x_2, \cdots, x_d)}^{T} \\
W &= {(w_0, w_1, w_2, \cdots, w_d)}^{T}
\end{align}
すると、以下のようになる。
\begin{align}
g(x) = W^T X
\end{align}

クラス$c_i$の線形識別関数を
\begin{align}
g_i (x) = W_{i}^{T} X
\end{align}
とすれば、$x$を判別する演算は、この式の線形和の計算と$i$に関する最大化によって簡単に構成することができる。このような線形演算と最大化による識別系をパーセプトロンと呼ぶ。

2クラス分類

2クラス分類において、クラス$c_1, c_2$に対して、それぞれ線形識別関数$g_1, g_2$が与えられた時、その識別関数の最大化によって、クラスが決定する。したがって、2クラスの場合においては、新しく識別関数$g$を
\begin{align}
g(x) = g_1 (x) + g_2 (x)
\end{align}
と定義すると、$g(x) > 0$ならばクラス$c_1$、$g(x) < 0$ならばクラス$c_2$と判別することと等価になる。

この時、クラス$c_1, c_2$を表すラベルとして、$\{ 1, -1 \}$を用いた時、$g(x)$の値をクラスラベルに変換する活性化関数$f$が以下のように定義できる。
\begin{align}
f (a) =
\begin{cases}
1 & (a > 0) \\
{-1} & (a < 0)
\end{cases}
\end{align}

ここでデータセットとして、データ$x_n$と正解のクラスラベル$t_n$の組が$N$個与えられた時、$W^T X_n t_n > 0$となる性質から、損失関数$E$を誤認識をしたデータセットに対して、以下のように定義する。
\begin{align}
E(W) = - \sum_n W^T X_n t_n
\end{align}

すると、勾配降下法により重み係数$W$は以下の式で更新される。
\begin{align}
W & \gets W - \epsilon \nabla E(W) \\
& = W - \epsilon (- \sum_n X_n t_n) \\
& = W + \epsilon \sum_n X_n t_n
\end{align}
$\epsilon$は更新の幅を決めるハイパーパラメータです。また$t_n$は$1$または$-1$を取るので、第二項の符号を変えます。

ただし、これは学習データの集合が線形分離可能であることを大前提としています。

Pythonコード
import numpy as np
import matplotlib.pyplot as plt

def predict(w, x):
    return np.dot(w, x)

def activation_function(x):
    if x > 0:
        return 1
    else:
        return -1

# datasets
data = np.array([[1, 1, 1], [1, -1, 1], [-1, 1, 1], [-1, -1, 1]])
label = np.array([1, -1, -1, -1])

# 正解データのグラフ描画
ax = plt.subplot(1, 2, 1)
plt.xlim(-2, 2)
plt.ylim(-2, 2)
plt.gca().set_aspect("equal", adjustable="box")
plt.title("ground truth")

for i in range(len(data)):
    if label[i] == 1:
        plt.plot(data[i][0], data[i][1], "ro")
    else:
        plt.plot(data[i][0], data[i][1], "bo")


# 初期化
w = np.array(np.random.normal(loc=0.0, scale=1.0, size=3))

epochs = 100
learning_rate = 0.1
for e in range(epochs):
    for i in range(len(data)):
        plabel = activation_function(predict(w, data[i]))
        if plabel != label[i]:
            w += learning_rate * data[i] * label[i]

# 予測
ax = plt.subplot(1, 2, 2)
plt.xlim(-2, 2)
plt.ylim(-2, 2)
plt.gca().set_aspect("equal", adjustable="box")
plt.title("result")

for i in range(len(data)):
    plabel = activation_function(predict(w, data[i]))
    
    if plabel == 1:
        plt.plot(data[i][0], data[i][1], "ro")
    else:
        plt.plot(data[i][0], data[i][1], "bo")

x = np.arange(-2, 2, 0.1)
y = (-1) / w[1] * (w[0] * x + w[2])
plt.plot(x, y, "g")

plt.savefig("LinearDiscriminantFunction")

f:id:takahiro_itazuri:20180121123605p:plain

フィッシャーの線形判別法

2クラス分類において、クラス$c_i$に属する$N_i$個のデータ集合を$C_i$とすると、平均ベクトルは以下のようにしてなる。
\begin{align}
\bar{x}_i = \frac{1}{N_i} \sum_{x_n \in C_i} x_n
\end{align}
またクラス内の共分散行列は以下のようになる
\begin{align}
\hat{S}_i = \frac{1}{N_i} \sum_{x_n \in C_i} (x_n - \bar{x}_i) (x_n - \bar{x}_i)^T
\end{align}
そして、ばらつきは以下のようになる。
\begin{align}
\hat{s}_{i}^{2} = \frac{1}{N_i} \sum_{x_n \in C_i} (x_n - \bar{x}_i)^T (x_n - \bar{x}_i)
\end{align}

次に線形識別関数$g$で射影した空間上においては、クラス$c_i$に対して、平均は以下のようになる。
\begin{align}
\tilde{x}_i &= \frac{1}{N_i} \sum_{x_n \in C_i} g(x_n)
&= w_0 + w^T \bar{x}_i
\end{align}
また、ばらつきは以下のようになる。
\begin{align}
\tilde{s}_{i}^{2} &= \frac{1}{N_i} \sum_{x_n \in C_i} (g(x_n) - \tilde{x}_i)^2 \\
&= \frac{1}{N_i} \sum_{x_n \in C_i} (g(x_n) - \tilde{x}_i) (g(x_n) - \tilde{x}_i)^T \\
&= \frac{1}{N_i} \sum_{x_n \in C_i} w^T (x_n - \bar{x}_i) (x_n - \bar{x}_i)^T w \\
&= w^T \hat{S}_i w
\end{align}

ここで、射影前の特徴空間上でのクラス内変動行列を
\begin{align}
S_I = \sum_{i=1}^{2} \sum_{x_n \in C_i} (x_n - \bar{x}_i) (x_n - \bar{x}_i)^T
\end{align}
と定義し、クラス間変動行列を
\begin{align}
S_B &= N_1 (\bar{x}_1 - \bar{x}) (\bar{x}_1 - \bar{x})^T + N_2 (\bar{x}_2 - \bar{x}) (\bar{x}_2 - \bar{x})^T \\
&= \frac{N_1 N_2}{N} (\bar{x}_1 - \bar{x}_2) (\bar{x}_1 - \bar{x}_2)^T
\end{align}
と定義する。
上述の議論と同様に、射影後の空間におけるクラス内変動は
\begin{align}
\tilde{S_I} &= \sum_{i=1}^{2} N_i \tilde{s}_{i}^{2} \\
&= w^T S_I w
\end{align}
となり、クラス間変動は
\begin{align}
\tilde{S_B} &= \sum_{i=1}^{2} (\tilde{x}_i - \tilde{x}) (\tilde{x}_i - \tilde{x})^T \\
&= \frac{N_1 N_2}{N} (\tilde{x}_1 - \tilde{x}_2)^2 \\
&= w^T S_B w
\end{align}
で与えられる。

ここでフィッシャーの線形判別法は、「射影した先の空間上でクラス分類がしやすくなっていればよい」という発想で、「クラス内変動に対するクラス間変動の日利率を最大化をする」解き方である。
したがって、評価関数として
\begin{align}
{J}_{F} (w) = \frac{{\tilde{S}}_{B}}{{\tilde{S}}_{I}} = \frac{N_{1} N_{2}}{N}
\frac{(\tilde{x}_{1} - \tilde{x}_{1})^2}{N_1 \tilde{s}_{1}^{2} + N_2 \tilde{s}_{2}^{2}}
\end{align}
を考える。
この評価関数$J_F (w)$を最大化する重み係数$w$を求めればよい。この評価関数をフィッシャーの評価基準という。

したがって、1次の最適性条件より
\begin{align}
\frac{\partial J_F (w)}{\partial w} = 0
\end{align}
を満たす$w$である。