NN法の定式化

NN法とは

1. 各クラスにプロトタイプベクトルを用意する
2. 入力ベクトルとプロトタイプの距離を測る
3. 最も近いプロトタイプの属するクラスを認識結果とする

距離

• クラス $\omega_1, \cdots, \omega_c$
• クラス $\omega_i$ のプロトタイプベクトル ${\bf p}_i = (p_{i1}, p_{i2}, \cdots, p_{id})$
• 入力ベクトル ${\bf x} = (x_1, x_2, \cdots, x_d)^T$

とした場合に

$$ D({\bf x}, {\bf p_i}) = \sqrt{\mathstrut (x_1 - p_{i1})^2 + (x_2 - p_{i2}) + \cdots + (x_d - p_{id})^2} $$

この単純なユークリッド距離を利用するのは問題があるが、今回はこのままにする。問題については7章で詳しく述べられる

最小距離

• 距離の最小値 $\min D({\bf x}, {\bf p}_i) \;\; (i = 1, \cdots , c)$
• 距離が最小のプロトタイプ $\text{argmin}_i \: D({\bf x}, {\bf p}_i) \;\;(i = 1, \cdots , c)$

これでNN法の定式化ができた

プロトタイプと決定境界の関係

NN法を定式化したもの $\text{argmin}_i \: D({\bf x}, {\bf p}_i) \;\;(i = 1, \cdots , c)$ は何をしているのかを考える

以下では単純のため、2クラスの識別問題を考えることにする。 さらに、図で説明しやすくするために特徴ベクトルを2次元とする

NN法とは、ある特徴ベクトル${\bf x}$が入力された時に、${\bf x}$がクラス$\omega_1$のプロトタイプ${\bf p}_1$に近いのか、 クラス$\omega_2$のプロトタイプ${\bf p}_2$に近いのかを求める問題

つまり、${\bf p}_1, {\bf p}_2$から等距離にある領域を求め、 ${\bf x}$がその領域のどちら側に入っているかを調べることと同じ

${\bf p}_1, {\bf p}_2$から等距離にある領域は${\bf p}_1, {\bf p}_2$を結ぶ直線の垂直二等分線である

そして、この直線のことを決定境界や 識別面などと呼ぶ

プロトタイプが決まると特徴空間が決定境界で分割される

プロトタイプの決め方

ここまでで、プロトタイプを決めればNN法で識別できることがわかった

データに偏りがある場合、重心がクラスの分布の中心から外れるので、正確に識別できないことがある

多次元の場合は決定境界を直感的にイメージできないので、 なんらかの機械的手続きで決定境界を求める必要がある

パーセプトロンの学習規則

誤識別をなくすために決定境界をうまく動かしていく操作を学習という

機械的に学習する方法にパーセプトロンというものがある

ここでNN法について復習

NN法とは、クラス$\omega_1,\omega_2,\cdots,\omega_c$に対して、プロトタイプ ${\bf p}_1,{\bf p}_2,\cdots,{\bf p}_c$を決め、 入力された特徴ベクトル${\bf x}$との距離が最小となるプロトタイプを求めるもの

距離は以下の式で表される $$ \begin{align} D({\bf x}, {\bf p_i}) & = \sqrt{\mathstrut (x_1 - p_{i1})^2 + (x_2 - p_{i2}) + \cdots + (x_d - p_{id})^2} \\ & = \|{\bf x} - {\bf p}_i\| \;\;\;\;\;\;\;\; (i = 1, \cdots , c) \end{align} $$

最小となるプロトタイプは以下の式で表される $$ \text{argmin}_i \: D({\bf x}, {\bf p}_i) \;\;\;\;\;\;\;\; (i = 1, \cdots , c) $$

学習しやすくするために、この式を別の表現に置き換えていく

距離は0または正の値なので、以下の式が成り立つ $$ \text{argmin}_i \: D({\bf x}, {\bf p}_i) = \text{argmin}_i \: D({\bf x}, {\bf p}_i)^2 $$

距離$ D({\bf x}, {\bf p_i}) = \|{\bf x} - {\bf p}_i\| $ の右辺を2乗して展開すると $$ \begin{align} \|{\bf x} - {\bf p}_i\|^2 & = \|x\|^2 - 2 {\bf p}_i^t {\bf x} + \|{\bf p}_i\|^2 \\ & = \|x\|^2 - 2 \left( {\bf p}_i^t {\bf x} - \frac{1}{2} \|{\bf p}_i\|^2 \right) \end{align} $$

右辺第1項はどの${\bf p_i}$を選んでも等しいので、大小比較時には無視できる

$ g_i({\bf x}) = {\bf p}_i^t {\bf x} - \frac{1}{2} \|{\bf p}_i\|^2 $ とすると、 $ \text{argmin}_i \: D({\bf x}, {\bf p}_i) $は $\text{argmax}_i \; {g_i({\bf x})} $と置き換えられる

$ g_i({\bf x}) = {\bf p}_i^t {\bf x} - \frac{1}{2} \|{\bf p}_i\|^2 $を識別関数と言い、 各クラス$\omega_i$に対して識別関数 $ g_i({\bf x}) $を計算する

そして、$ g_i({\bf x}) $が最大値を取るクラス $\omega_i$を出力するのがNN法による識別である

アルゴリズムを適用するために識別関数を変形していく

$$ \begin{align} & p_{ij} = w_{ij} \;\;\;\;\;\;\;\; (j = 1, \cdots, d) \\ & - \frac{1}{2} \|{\bf p}_i\|^2 = w_{i0} \end{align} $$ と置き換えると、以下のようになる $$ \begin{align} g_i({\bf x}) & = {\bf p}_i^t {\bf x} - \frac{1}{2} \|{\bf p}_i\|^2 \\ & = w_{i0} + \sum\limits_{j=1}^d w_{ij}x_j \end{align} $$

表記を簡単にするために、$x_0 = 1$とした$d + 1$次元の特徴ベクトルを${\bf x}$とすると、以下のようになる $$ \begin{align} g_i({\bf x}) & = \sum\limits_{j=0}^d w_{ij}x_j = w_{i0} x_0 + w_{i1} x_1 + \cdots + w_{id} x_d \\ & = {\bf w}_i^t {\bf x} \end{align} $$ $x_0$のことをバイアス項と言う。

置き換えに使った${\bf w} = (w_{i0}, w_{i1}, \cdots, w_{id})^t$は重みベクトル と呼ばれる

$$ \begin{align} & p_{ij} = w_{ij} \;\;\;\;\;\;\;\; (j = 1, \cdots, d) \\ & - \frac{1}{2} \|{\bf p}_i\|^2 = w_{i0} \end{align} $$ なので、重みベクトルはプロトタイプベクトルに$ w_{i0} = - \frac{1}{2} \|{\bf p}_i\|^2 $ を追加したものである

$ g_i({\bf x}) = {\bf w}_i^t {\bf x} $のような 入力の重み付き線形和と、最大値選択機の組み合わせはパーセプトロンと呼ばれている

与えられた学習データに対して、識別関数$g_i({\bf x})$の重みベクトル${\bf w}_i$をうまく決定することができれば、 NN法による識別が可能になる

学習データの集合を$X$とし、クラス$\omega_i$に属するデータの集合を$X_i$としたときに、 $X_i \;\; (i = 1, \cdots, c)$に属する全ての${\bf x}$に対して以下の式が成り立つように重み${\bf w}_i$を調整する $$ g_i({\bf x}) > g_j({\bf x}) \;\; (j = 1,\cdots,c, \; j \neq i) $$

単純にするために、再び2クラス分類問題の例で説明する

2クラス分類の場合は、どちらの識別関数が大きいかの問題になるので、識別関数を以下のように置き換えられる $$g({\bf x}) = g_1({\bf x}) - g_2({\bf x}) = {\bf w}_1^t{\bf x} - {\bf w}_2^t{\bf x} = {\bf w}^t{\bf x}$$

$g({\bf x}) = 0$となる${\bf x}$は各プロトタイプから等距離なので、決定境界上にある

よって、以下の式を満たすように重みベクトル${\bf w}$を調整すれば良い $$ \left\{ \begin{align} g({\bf x}) & = {\bf w}^t {\bf x} > 0 \;\;\; ({\bf x} \in X_1) \\ g({\bf x}) & = {\bf w}^t {\bf x} < 0 \;\;\; ({\bf x} \in X_2) \end{align} \right. $$

以降では、重みベクトルを適当に初期化し、ある学習データに対して上の式と異なる結果が出た時のみ、 重みベクトルを修正するアルゴリズムについて考える

重みベクトル${\bf w}$を要素とする重み空間を考えると、重みベクトルを初期化するということは、 重み空間中の適当な1点を決めること

重み空間で${\bf w}^t{\bf x} = 0$という超平面を考えると、 個々の学習データ${\bf x}$に対して超平面${\bf w}^t{\bf x} = 0$が1つ対応する

${\bf x} = (1, 1)$の場合、以下の図のようになる

${\bf w}_{(0)}$を使って学習データ${\bf x}$を誤識別した時、${\bf w}_{(0)}$を${\bf w}^t{\bf x} = 0$ の反対側に移動させると正しく識別できる

超平面${\bf w}^t{\bf x} = 0$と${\bf x}$は直行するので、${\bf x}$の方向に移動させる

${\bf x} \in X_1$を誤識別した場合は、以下の図のように${\bf w}_{(0)}$を修正すれば良い

重みベクトルを修正する際は1回で正しい領域に移動させる必要はなく、別の学習データに対しても同様に識別を行い、 誤識別が起これば修正するという手順を繰り返せば良い

重みベクトルの修正幅を学習係数$\rho$と呼ぶ

学習データが線形分離可能であれば、全ての学習データに対して正しい識別結果を出力する領域が存在する。 この領域のことを解領域と言う

いままでの手順をまとめると以下のようになる

1. 重みの初期値${\bf w} = {\bf w}_{(0)}$を適当に決める
2. 学習データ集合から1つ${\bf x} \in X$を選び、識別関数 $g({\bf x}) = {\bf w}^t{\bf x}$を求める
3. 誤識別が起きた時のみ、${\bf w}$を修正する $$ \left\{ \begin{align} {\bf w}' & = {\bf w} + \rho {\bf x} \;\; (\omega_1を\omega_2と誤識別した場合) \\ {\bf w}' & = {\bf w} - \rho {\bf x} \;\; (\omega_2を\omega_1と誤識別した場合) \end{align} \right. $$
4. 2, 3を全ての学習データに対して繰り返す
5. 全て正しく識別できれば終了、そうでなければ2へ

学習データが線形分離可能なら、パーセプトロンの学習規則は有限回の繰り返しで終了する。 これをパーセプトロンの収束定理という

• $\rho$が小さい時、修正幅が小さいので、収束に時間がかかる
• $\rho$が大きい時、解の付近で振動して、収束に時間がかかる

パーセプトロンの学習例

以下のような問題の識別関数を求める

• 学習データ $x1 = 1.0, x2 = 0.5, x3 = -0.2, x4 = -1.3$
• クラス $\{x1, x2\} \in X_1, \{x3, x4\} \in X_2$
• 重みの初期値 $w_0 = 0.2, w_1 = 0.3$
• 学習係数 $\rho = 0.5$

1回めの繰り返し

$x3$を誤識別しているので重みの修正がおきる

修正式は${\bf w}' = {\bf w} - \rho {\bf x}$なので $$ \begin{pmatrix} w_0 \\ w_1 \end{pmatrix} = \begin{pmatrix} 0.2 \\ 0.3 \end{pmatrix} - 0.5 \begin{pmatrix} 1.0 \\ -0.2 \end{pmatrix} = \begin{pmatrix} -0.3 \\ 0.4 \end{pmatrix} $$

修正後の重みで$x4$の識別をする

2回めの繰り返し

3回めの繰り返し

全てのデータが正しく識別されたので、ここで終了する。この時得られた識別関数は $g({\bf x}) = 0.75x - 0.3$となる

区分的線形識別関数とk-NN法

パーセプトロンの学習規則は学習データが線形分離可能なら識別面を発見できるが、 線形分離できない場合は以下の解決法がある

• 識別面を非線形にする(なめらかに曲げる)
• 識別面を区分的線形にする(折る)

以降では区分的線形による解決法を考える

区分的線形識別面は複数の平面を組み合わせることでできる

1枚の平面はそれぞれのプロトタイプの垂直二等分線なので、プロトタイプを複数用意すれば良い

これらの複数の平面のうち、識別に関係したところだけを繋げ合わせると区分的線形識別面になる

あるプロトタイプに最も近い他のクラスのプロトタイプとの関係で識別面は決まるので、図の様に組になっている必要はない

区分的線形識別関数は副次識別関数の数を増やせば、非線形な局面を任意の制度で近似できる

副次識別関数の個数を変えると、重みベクトルの学習をしなおさなければならないが、 必要な副次識別関数の個数は重みベクトルの学習が終わらなければわからないため、区分的線形識別関数の学習は困難である

プロトタイプの個数を学習せずに、学習データを全てプロトタイプとする1-NN法という方法もある

一番近いプロトタイプだけでなく、$ k $番目に近いプロトタイプを見て、多数決などでクラスを識別するk-NN法という方法もある

一般に$ k $が大きいほど識別境界はなめらかになる傾向がある

k-NN法は学習データが十分にあれば、非線形性を示すデータにも対処できる場合が多い

k-NN法は、新たな学習手法の良さを評価するためのベースラインとして用いられることもある