Created by 2GMon
4, 5章で識別の基本的な理論をカバーした
パーセプトロンやWidrow-Hoffの学習規則には限界がある
パーセプトロンの問題は大きく2つある
見つかった決定境界が未知のデータにも通用するかわからない、という問題について考える
パーセプトロンの場合、誤識別が0になる領域のどこに決定境界がひかれるのかわからない
未知のデータに対する識別率は、領域ギリギリよりも真ん中辺りが良さそう
この真ん中を決めるのがSVM
k-NN法と同様に、決定境界を決める問題を、学習データの中からプロトタイプを選ぶ問題に置き換える
決定境界を決めるデータをサポートベクトルとよぶ
各クラスのサポートベクトルと、決定境界の距離をマージンとよぶ
マージンが最大になる決定境界を得る
学習データ $$ X = \{ {\bf x}_1, \cdots , {\bf x}_n \} $$
正解クラスラベル $$ \{ y_1, \cdots , y_n \} (y_i = 1({\bf x}_i \in X_1), y_i = -1({\bf x}_i \in X_2)) $$
決定境界 $$ g_i({\bf x}) = {\bf w}^T {\bf x} + w_0 = 0 $$
マージンを最大化するという問題は、サポートベクトルと決定境界の距離を最大化するということ
点と面の距離の公式から、サポートベクトル${\bf x}_i$と決定境界$g_i({\bf x})$の距離は $$ \min_{i = 1, \cdots, n} \frac{|{\bf w}^T {\bf x}_i + w_0|}{||m||} $$
点$(x_1, y_1)$と平面$ax+by+c=0$との距離$d$は $$ d = \frac{|ax_1+by_1+c|}{\sqrt{a^2+b^2}} $$
決定境界の${\bf w}$や$w_0$を定数バイしても超平面は変わらないので、以下のような制約を設けられる $$ \min_{i = 1, \cdots, n} |{\bf w}^T {\bf x}_i + w_0| = 1$$
よって、サポートベクトルと決定境界の距離は以下のようになる $$ \min_{i = 1, \cdots, n} \frac{|{\bf w}^T {\bf x}_i + w_0|}{||m||} = \frac {1}{||{\bf w}||} $$
マージンを最大化するという問題は$||{\bf w}||$を最小化するという問題になる
誤識別が起こらない範囲で$||{\bf w}||$を最小化する必要がある
誤識別が起こらないという制約は以下のように設けられる $$ y_i({\bf w}^T{\bf x}_i + w_0) \geq 1 \;\; (i = 1, \cdots, n) $$
このように一定の条件が与えられたもとでの最小化問題はラグランジュの未定乗数法で解くことができる
$||{\bf w}||^2$の最小化問題は、ラグランジュ係数$\alpha_i$を導入して、以下の関数$L$の最小値を求める問題に置き換えられる $$ L({\bf w}, w_0, \alpha) = \frac{1}{2}||{\bf w}||^2 - \sum_{i=1}^n \alpha_i(y_i({\bf w}^T{\bf x}_i + w_0) - 1) $$
$g(x, y)=0$という条件の下で、$z=f(x,y)$の最大値(or 最小値)を求める問題は、$L=f(x,y) - \lambda g(x,y)$という新しい関数を導入し、 この関数の極値を求めるという問題に置き換えることができる
最小値では$L$の勾配が0になるので、以下の式が成り立つ $$ \begin{align} \frac{\partial L}{\partial w_0} = 0 & \Rightarrow \sum_{i=1}^n\alpha_i y_i = 0 \\ \frac{\partial L}{\partial {\bf w}} = 0 & \Rightarrow {\bf w} = \sum_{i=1}^n\alpha_i y_i {\bf x}_i \end{align}$$
$ L({\bf w}, w_0, \alpha) = \frac{1}{2}||{\bf w}||^2 - \sum_{i=1}^n \alpha_i(y_i({\bf w}^T{\bf x}_i + w_0) - 1) $に代入して $L(\alpha) = \sum_{i=1}^n\alpha_i - \frac{1}{2} \sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j {\bf x}_i^T {\bf x}_j $を得る (第1項と第2項を入れ替え、符号を逆にしてある)
$L$の符号が入れ替わったので、$L$を最大化すれば良い
これは$\alpha_i$に関する2次計画問題と呼ばれ、数値計算ソフトで簡単に求められる(最急降下法でも可)
$ {\bf w} = \sum_{i=1}^n\alpha_i y_i {\bf x}_i $より$\alpha_i = 0$となるデータは${\bf w}$の決定に全く関与しない
決定境界$ g_i({\bf x}) = {\bf w}^T {\bf x} + w_0 = 0 $にサポートベクトル$x$を代入すると$w_0$が求まる
以上で、線形分離可能な場合はマージンを最大化する決定境界が求まる
線形分離可能な場合にパーセプトロンが停止しないという問題について考える
一般に特徴空間の次元数$d$が大きい場合は、線形分裏面が存在する可能性が高くなる
低次元の特徴ベクトルを高次元に写像する方法が考えられる
元の空間におけるデータ間の距離関係を保存する方式で高次元に非線形変換しても、その高次元空間上での線形識別器の性能は 元の空間の性能を反映することがわかっている
なので、元の空間におけるデータ間の距離関係を保存するような非線形写像が見つかれば良い
元の特徴空間上の2点${\bf x}, {\bf x}'$の距離に基づいて定義される、ある関数$K({\bf x}, {\bf x}')$を考える
この関数はカーネル関数と呼ばれる
非線形写像を$\phi$としたときに、以下の関係が成り立つことを仮定すると $$ K({\bf x}, {\bf x}') = \phi ({\bf x})^T \phi ({\bf x}') $$
写像後の空間での識別関数は以下のように書くことができる $$ g(\phi ({\bf x})) = {\bf w}^T \phi({\bf x}) + w_0 $$
このとき元の空間での2点間の距離が、非線形写像後の空間における内積に反映されるという形式で、近さの情報を保存している
${\bf w} = \sum_{i=1}^n\alpha_i y_i {\bf x}_i$より $$ \begin{align} g(\phi ({\bf x})) & = {\bf w}^T \phi({\bf x}) + w_0 \\ & = \sum_{i=1}^n\alpha_i y_i \phi({\bf x})^T \phi({\bf x}_i) + w_0 \\ & = \sum_{i=1}^n\alpha_i y_i K({\bf x}, {\bf x}_i) + w_0 \end{align} $$
$L(\alpha) = \sum_{i=1}^n\alpha_i - \frac{1}{2} \sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j {\bf x}_i^T {\bf x}_j$より、 学習も $\sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j K({\bf x}_i, {\bf x}_j)$ を最大化するという問題になる
識別関数、最大化の式両方から$\phi$が消えているので、カーネル関数$K$さえ定まれば識別面を得ることができる
このような、複雑な非線形変換を求める操作を避ける方法をカーネルトリックと呼ぶ
カーネル関数が正定値関数という条件を満たすときには、このような非線形変換$\phi$が存在することがわかっている
カーネル関数の例として、以下のようなものがある
非線形変換後の空間で見つかった線形分離超平面は、元の空間では複雑な非線形曲面に対応する
SVMはそのまま多クラスの識別に拡張できないので、2クラス識別問題の組み合わせとして表現する
非線形識別関数を用いて誤識別を減らす方法の1つにニューラルネットワークがある
ニューラルネットワークはニューロンの働きをモデル化した閾値論理ユニットを多数結合したもの
閾値論理ユニットは受け取った重み付き信号の和が閾値を超えると信号を出力する
以下の様な単純な階層構造のものをフィードフォワード型ニューラルネットワークとよぶ
1を出力する出力層のユニットに対応するクラスが識別結果になる
各ユニットでの操作は非線形変換で、この場合フィードフォワード型ニューラルネットワークは重みを調整すれば任意の非線形識別面を近似できることがわかっている
中間層から出力層への重みは判別結果と教師信号を比較することで、誤差評価に基づく学習が使える
中間層に対応する教師信号は存在しないので、入力層から中間層への重みの学習は別の方法を考える必要がある
階層的なネットワークの重みを学習する誤差逆伝播法という方法がある
以降では一般化のために、多くの階層からなるネットワークを考える
学習パターン${\bf x}_p$が入力された時を考える
ユニット$i$の出力：$g_{ip}$
ユニット$i$からユニット$j$への重み：$w_{ij}$とすると
ユニット$j$への入力：$h_{jp} = \sum_i w_{ij} g_{ip}$
ユニット$j$の出力：$f$を閾値関数とすると$g_{jp}=f(h_{jp})$
誤差に基づく学習法を適用すると、学習パターン${\bf x}_p$に対する誤差は出力層のユニット$l$の出力と教師信号$b_{lp}$の2乗和で定義される$$J_p = \frac{1}{2} \sum_l (g_{lp} - b_{lp})^2$$
全学習パターンに対する誤差は$$J = \sum_p J_p$$となり$J$を最小にするように重みを調整する
重みの調整は確率的最急降下法$w_{ij}' = w_{ij} - \rho \frac{\partial J_p}{\partial w_{ij}}$によって行う
$\frac{\partial J_p}{\partial w_{ij}}$はユニット$j$とユニット$i$の結合重みを変化させた時の、誤差$J_p$の変化量を表している
ユニット$j$の出力は最終的な出力に影響をあたえるので、誤差$J_p$はユニット$j$の出力$h_{jp} = \sum_i w_{ij} g_{ip}$の関数といえる。
よって
$\frac{\partial J_p}{\partial w_{ij}} = \frac{\partial J_p}{\partial h_{jp}} \frac{\partial h_{jp}}{\partial w_{ij}} = \frac{\partial J_p}{\partial h_{jp}} g_{ip} \;\; (\because h_{jp} = \sum_i w_{ij} g_{ip})$
$\epsilon_{jp} = \frac{\partial J_p}{\partial h_{jp}}$とおくと、 $$\epsilon_{jp} = \frac{\partial J_p}{\partial g_{jp}} \frac{\partial g_{jp}}{\partial h_{jp}} = \frac{\partial J_p}{\partial g_{jp}} f'(h_{jp}) \;\; (\because g_{jp} = f(h_{jp}))$$
$f$に閾値関数を用いると微分できないので、代わりにシグモイド関数$s(x) = \frac{1}{1 + e^{-x}}$を用いると $$ f'(h_{jp}) = f(h_{jp})(1 - f(h_{jp})) = g_{jp}(1 - g_{jp}) \;\; (\because s'(x) = s(x)(1 - s(x)))$$
よって、$ \epsilon_{jp} = \frac{\partial J_p}{\partial g_{jp}} g_{jp}(1 - g_{jp})$
$\frac{\partial J_p}{\partial g_{jp}}$はユニット$j$が出力層か中間層かで求め方が異なる
ユニット$j$が出力層の場合は$j = l$なので、$J_p = \frac{1}{2} \sum_l (g_{lp} - b_{lp})^2$より $$ \frac{\partial J_p}{\partial g_{jp}} = g_{jp} - b_{jp} $$
ユニット$j$が中間層の場合は、ユニット$j$からの出力が複数の上位ユニット$k$の入力になっているので足しあわせて $$ \frac{\partial J_p}{\partial g_{jp}} = \sum_k \frac{\partial J_p}{\partial h_{kp}} \frac{\partial h_{kp}}{\partial g_{jp}} = \sum_k \epsilon_{kp} w_{jk} $$ $$ (\because \epsilon_{jp} = \frac{\partial J_p}{\partial h_{jp}}, \;\; h_{kp} = \sum_i w_{jk} g_{jp}) $$
各ユニットにおける誤差の変化量$\epsilon_{jp}$は $$ \epsilon_{jp} = \left\{ \begin{array}{ll} (g_{jp} - b_{jp})g_{jp}(1 - g_{jp}) & (出力層)\\ (\sum_k \epsilon_{kp} w_{jk}) g_{jp} (1 - g_{jp}) & (中間層) \end{array} \right. $$
よって$\frac{\partial J_p}{\partial w_{ij}} = \frac{\partial J_p}{\partial h_{jp}} \frac{\partial h_{jp}}{\partial w_{ij}} = \frac{\partial J_p}{\partial h_{jp}} g_{ip} = \epsilon_{jp} g_{ip}$ を用いて重みを更新していく
重みの更新は一定回数以上繰り返されるか、更新量が一定値以下になれば停止する
確率的最急降下法を用いているので局所解に陥る可能性がある