rastudylife

機械学習や統計についての勉強ログ

はじパタからみる識別規則3(関数編)

今回は識別規則を関数という観点から勉強する.


はじパタ第6章内容

  • 識別関数と識別規則

2クラス問題の識別規則
まず2クラスへ識別する方法を考える.
2クラス問題の線形識別関数は f(x)=w^T+w_0(d次元入力ベクトル x=(x_1,...,x_d)^T,係数ベクトル w=(w_1,..,w_d)^T,バイアス項w_0)で識別される.識別境界をf(x)=0とすれば,識別規則はf(x)\geq0の時に識別クラスはC_1f(x) < 0の時に識別クラスはC_2となる.
ここで,係数ベクトルwをノルム||w||で割って正規化したものをnとする.nの転置n^Tを識別境界線上の位置ベクトルPとかけると,Pを単位法線ベクトル上に射影した長さ\Delta_wになる.この\Delta_wは,原点から識別超平面までの距離を表す.ベクトルx'が法線ベクトルへ射影した長さが\Delta_wより長くなる時に識別関数は正の値を取り,短くなる時に識別関数は正の値を取る.

多クラス問題の識別規則
次に,K(>2)以上のクラスへ識別する方法を考える. 
まず,一つのクラスと他の全てのクラスを識別する(一対多)方法.
K-1個の2クラス識別関数f_j(x)について正の時C_j,負の時C_kと識別する.欠点として,複数の識別関数が正となる空白領域のクラスが決定できないことや,正のクラスの学習データ数が少なくなることがある.
次は,2クラス識別関数f_{ij}(x)K(K-1)/2個用意し,多数決で識別クラスを決める方法.欠点は,識別関数間でクラスの矛盾が生じる空白領域のクラスが決定できないことや,直接データに関係のない識別関数ができることである.
そこで,識別関数値が最大のクラスを識別クラスにする方法を用いる.
識別クラス:arg max_j f_j(x) = arg max_j (w_j ^T x + w_{j0})
とすると,iとjの識別境界はf_i(x)=f_j(x)となるので,f_{ij}(x)=(w_i - w_j)^T x + (w_{i0} - w_{j0}) = 0を満たすK個の識別境界ができることになる.この方法では,必ずクラスは決定でき,クラスの占める領域は単連結で凸である.

  • 識別関数のパラメータw, w_0の決定

以下に実際にパラメータを決定する方法を三種類述べる.

[2乗誤差最小化標準]
2クラス問題の場合
識別関数の出力値と教師入力との差を最小にするパラメータを求める手法
係数ベクトル(w):w=(w_0, w_1, ..., w_d)^T
i番目の学習用入力ベクトル(x_i):x_i=(x_{i0} =  1, x_1, ..., x_{id})^T
を用いて線形識別関数は次のように表せる.
線形識別関数 f(x)=w_0 + w_1 x_1 + ... + w_d x_d = w^T x

教師入力 (t_i):t_iが+1のときx_iが所属するクラスはC_1t_iが-1のときx_iが所属するクラスはC_2
とおく.
次に,x_iを学習データ数N個分並べたデータ行列X = (x_1, ..., x_N)^T
t_iを学習データ数N個分並べたデータ行列t = (t_1, ..., t_N)^T
と定義する.

これらを使って,評価関数は次のように表される.
二乗誤差の評価関数(E(w)):\Sigma_{i=1}^{N} (t_i - f(x_i))^2 = (t - Xw)^T (t - Xw) = t^T t - 2t^T Xw + w^T X^T X^T X^w
評価関数を微分すると-2X^T t + 2X^T X w これが0のとき\hat{w}=(X^T X)^{-1} X^T tである.この式を正規方程式という.
学習データに対する予測値\hat{t}\hat{t}=X \hat{w}=X(X^T X)^{-1}X^T t
X(X^T X)^{-1}X^T tは教師データt\hat{t}に変換する行列でハット行列と呼ばれる.

多クラス問題の場合
上記の線形識別関数を他クラスの場合で考えると
線形識別関数 f_k (x)=w_k ^T xk = 1, ... ,K
他クラス問題では教師入力データもK個必要なので,
t_i = (t_{i1}, ... , t_{iK})^Tとして,t_{ik}はi番目の学習入力がk番目のクラスに属するときのみ1で,それ以外は0を取る.
N個の学習データX=(x_1, ..., x_N)^Tに対する教師データを並べた行列を
T=(t_1,...,t_N)^Tt_i=(0,...,1,..,0)^Tとすれば,
二乗誤差を最小にするパラメータ\hat{W}\hat{W}=(X^T X)^{-1}X^T Tで与えられ,
識別関数は,f(x)=\hat{W}^T x =(w_1,..., w_k)^T x = (f_1(x),..., f_k(x))^Tとなる.
識別規則は,識別クラス=arg max_j f_j(x)となる.

[フィッシャーの判別関数]
フィッシャーの線型判別関数では,データを線形変換して一次元に写像した後,それぞれのクラスの平均や分散を比較することにより,最もクラスを分離するのに適する判別線を求める方法である.

2クラス問題の場合
2クラスC_1, C_2の学習データをそれぞれN_1, N_2とする.
平均ベクトル\mu_k=\frac{1}{N_k} \Sigma_{i\in C_k} {x_i}と表せられる.
これをm_k=w^T \mu_k写像する.
平均値の差 m_1 - m_2 = w^T (\mu_1 - \mu_2) が大きいほどクラスの分離がはっきりしている.
この平均の差の二乗をクラス間変動という.クラス間変動 (m_1 - m_2)^2
クラス内変動 S_k^2=\Sigma_{i\in{C_k}} (y_i - m_k)^2
このクラス内変動がよくわからなかったのだが,以下のサイトで理解ができた.
www.hellocybernetics.tech
クラス内変動は,各クラスの分散の和で,より良いクラス分けのためには,クラス内での分散は小さくなくてはいけない,ということのようだ.
なおかつクラス間変動,すなわちクラス間の平均の差は大きければ大きいほど良いので,次のような式になる.

          J(w)=\frac{{m_1 - m_2}^2} {S_1^2 + S_2^2}

この式を最大にするwを見つけることがフィッシャーの基準という.

クラス内変動とクラス間変動は次のように変換できる.
クラス間変動 (m_1 - m_2)^2 = w^T S_B wS_Bは線形変換される前の学習データのクラス間変動行列)
クラス内変動 S_k^2=\Sigma_{i\in{C_k}} (y_i - m_k)^2 = w^T S_k w よって全クラス内変動はw^T S_w w

これらを用いて,フィッシャーの基準は次のように書ける.

          J(w)=\frac{w^T S_B w} {w^T S_w w}

この式を最大化する解は一般化固有値問題 S_B w = \lambda S_w w を解くことでもとまる.
          w \propto S_w^{-1} S_B w \propto S_w^{-1} (\mu_1 - \mu_2)
また,w = \Sigma_{pool}^{-1} (\mu_1 - \mu_2) (\Sigma_{pool} = \frac{1}{N} S_w)とも表現できる.

フィッシャーの基準において,クラス識別のためのバイアス項 w_0 は次のように表せる.w_0 = \overline{m} - w^T (P(C_1) \mu_1 + P(C_2) \mu_2)

多クラス問題の場合
ニクラス問題の場合と同様に,クラス間変動行列とクラス内変動行列の比を最大化することが目的になる.
クラス内変動  S_k=\sum_{i\in{C_k}} (x_i - \mu_k)(x_i - \mu_k)^T,(\mu_k=\frac{1}{N_k} \sum_{i\in{C_k}} x_i
全クラスのクラス内変動の和 S_w=\sum_{k=1}^K S_k
クラス間変動 S_B=\sum_{k=1}^k (\mu_k - \mu)(\mu_k - \mu)^T
これらを線形変換した後のクラス内変動とクラス間変動は以下の通り.
\tilde{S_w}=W^TS_wW
\tilde{S_B}=W^TS_BW
全変動\tilde{S_T}=\tilde{S_w}+\tilde{S_B}
変動行列の最大値を求めるために,スカラー量に変換しなければならない.
その一つの方法としては,以下の式の最大値を求めるという方法がある.
J(W)=Tr({\tilde{S_w}}^{-1} \tilde{S_B}) = Tr( (W^T S_w W)^{-1} W^T S_B W )

[ロジスティック回帰]
線形関数を(0, 1)に回帰するというパターン認識方の一種.

2クラス問題の場合
クラスC_1の事後確率P(C_1|x)=\frac{p(x|C_1)P(C_1)}{p(x|C_1)P(C_1)+p(x|C_2)P(C_2)}
a=ln \frac{p(x|C_1)P(C_1)}{p(x|C_2)P(C_2)}とおけば,以下のように表される.
P(C_1|x)=\frac{1}{1+exp(-a)}=\sigma(a) これをロジスティック関数という.
また,ロジスティック関数の逆関数 a=ln(\frac{\sigma(a)}{1-\sigma(a)})=ln \frac{P(C_1|x)}{P(C_2|x)}
これをロジット関数といい,事後確率の比をオッズ,対数をログオッズという.
オッズ比を計算すると,100%近くまで成功の割合が増加した場合の数値がより上昇する.

次にパラメータの最尤推定を考える.
まず,モデルの出力を確率変数tで表す.
tが1になる確率を\piというパラメータで表し,0になる確率を1 - \piで表す.
確率変数t\piをもつベルヌーイ試行に従う.
f(t|\pi)=\pi^t (1-\pi)^{1-t}(t=0または1)
N回の試行に基づく尤度関数は L(\pi_1,...\pi_N)=\prod_{i=1}^N f(t_i|\pi_i)=\prod_{i=1}^N \pi_i^{t_i}(1-\pi_i)^{(1-t_i)}
対数をとって負の符号をつけた負の尤度関数は-ln L(\pi_1,...\pi_N)=L'(\pi_1,...\pi_N)=-\sum_{i=1}^N (t_i ln \pi_i + (1-t_i)ln(1-\pi_i) 交差エントロピー誤差関数と呼ばれる.
これに\pi_i=\sigma(x_i)=\frac{exp(w^T x_i)}{1+exp(w^T x_i)}を代入して整理すると,L'(\pi_1,...\pi_N)=-\sum_{i=1}^N (t_i w^T x_i - ln(1+exp(w^T x_i)))
この関数を最小にするパラメータwを求めるので,w微分すると,
\frac{\partial L(w)}{\partial w}=-\sum_{i=1}^N (t_i x_i - \frac{x_i exp(w^T x_i)}{1 + exp(w^T x_i)})=\sum_{i=1}^N x_i(\pi_i-t_i)
解析的に解を求めることはできないので,最急降下法ニュートン-ラフソン法を用いる.

多クラス問題の場合
各クラスごとに線形変換を求め,事後確率を計算し最大事後確率を与えるクラスに分類する.
線形変換 a_k=w_k^T x (k=1,...k) について,事後確率 P(C_k|x)=\pi_k(x)=\frac{exp a_k}{\sum_{j=1}^K {exp a_j}}が最大となるクラスに分類する.
この関数をソフトマックス関数という.
線形関数でうまく分離できない場合,入力ベクトルを非線形関数\varphi()でM+1次元データ\varphi(x)=(\varphi_0=1,\varphi_1(x),....,\varphi_M (x))^Tに変換するとうまく分離できるようになる場合がある.


はじパタ第7章内容
パーセプトロン型学習規則]
2クラスの学習データが線形分離可能な場合に,識別関数のパラメータを逐次的に求めるアルゴリズム
線形識別関数 f(x)=w^T xについて,f(x)\geq 0のときx\in C_1f(x)> 0のときx\in C_2とする2クラス問題を考える.
入力 x=(x_0=1,x_1,...x_d)^Tに,それぞれの重み w=(w_0, w_1, ..., w_d)^Tをつけて,その総和を出力するネットワークモデルをパーセプトロンと呼ぶ.
パーセプトロンの学習規則では,一つ前の入力データの分類が正しければ重みをそのまま使用し,誤っていれば前の学習データに比例した変更を加え新しい係数ベクトルを重みとする.
これは以下のように表される.
f(x_i)\geq 0であればw_{i+1}=w_i
(↑どちらのクラスに属していても,分類が正しい時はf(x)\geq0となる)
f(x_i)< 0であればw_{i+1}=w_i+\eta x_i

また,テストデータのノイズの影響を考慮して,学習データが識別超平面からある値h>0より近い距離にあれば誤りとしてwを更新するようにする.このマージンhより小さなノイズに対して正しく識別できるようになる.ステップ関数を用いて,a>0の場合 f_{step}(a)=1,それ以外の場合 f_{step}(a)=0とする.i番目の学習におけるw_iの変更量\Delta w_iは符号反転を使った学習データについて,\Delta w_i = \eta f_{step}(h - w_i^Tx_i / ||w_i||)x_i = ( h > w_i^T x_i / ||w_i||の場合,\eta x_i)(それ以外の場合,0)
ある識別関数f(x)=w^T xに対して取れるマージンの大きさD(w)は,クラスC_1, C_2の学習データを識別関数の法線ベクトル上に射影した長さの最小値の半分である.これをクラス間マージン\rho(w)とよぶ.\rho(w)=min_{x \in c_1} \frac{w^T x}{||w||} - max_{x \in c_2} \frac{w^T x}{||w||} と表される.また,最大マージンはD_{max}\frac{1}{2} \rho_{max}で与えられる.
符号反転を行った場合は,すべての学習データを超平面の法線ベクトル上へ射影した長さの最小値D(w)=min_{x\in{C_1,C_2}} \frac{w^T x}{||w||}がマージンとなり,最大マージンはD_{max}=max_w D(w)となる.2クラスの学習データが線形分離可能であれば,パーセプトロンに学習規則は有限の学習回数で収束する.

多層パーセプトロンの誤差逆伝搬法
入力層と出力層の間に,隠れ素子で構成されたグループである隠れ層を加えたアルゴリズムを多層パーセプトロンの誤差逆伝搬法という.
隠れ層の素子V_j (j=1,...,M)には入力層から h_j^n = \Sigma_{i=0}^d w_{ji} x_i^n=w_j^T x^n の入力が入り,出力関数g(u)を介してV_j^n=g(h_j^n)が出力される.このg(u)非線形であり,この非線形出力関数の例としてシグモイド関数g(u)=\frac{1}{1+exp(-\beta u)}が挙げられる.
隠れ素子から出力素子への結合係数の学習は出力素子へ与えられる教師信号を用いて,二乗誤差最小化を最急降下法に従って行う.



はじパタ第8章内容
[サポートベクトルマシン]

(1)2クラス線形識別関数の場合
標準座標系を考え,クラスラベル付きデータの集合をD_L={(t_i, x_i)}(i=1,...,N)とする.
学習データ x_i\in R^dがどのクラスに属するのかを指定するのがt_i={-1, +1}である.
まず,線形識別関数のマージンを\kappaとすると,すべての学習データで |w^T x_i + b|\geq \kappa が成り立ち,これを\kappaで正規化したものをwbとおけば,線形識別関数は以下のように表される.
          t_i=+1 のとき w^T x_i + b \geq +1
          t_i=-1 のとき w^T x_i + b \leq -1
この場合分けは,t_i(w^T x_i + b)\geq 1のようにまとめられる.
クラス間マージンは,以下のように各クラスのデータをwの方向へ射影した長さの差の最小値で与えられる.
\rho(w, b ) = min_{x_i\in C_{t_i=+1}} \frac{w^T x_i}{||w||} - max_{x_i\in C_{t_i=-1}} \frac{w^T x_i}{||w||} = \frac{1-b}{||w||} - \frac{-1-b}{||w||} = \frac{2}{||w||}
最適な超平面の式をw_0^T x + b_0 = 0とすれば,この超平面は最大クラス間マージン\rho(w_0, b_0) = max_w \rho(w,b)を与えられ,最大マージンD_maxは最大クラス間マージンの1/2で与えられるので,最適識別超平面はt_i(w^T x_i + b)\geq 1の制約の下でwのノルムを最小にする解w_0 = min||w||として求めることができる.

マージン最大の最適識別超平面は,以下の不等式制約最適化問題の主問題を解くことで得られる.
          評価関数(最小化):L_p (w)=\frac{1}{2}w^T w
          不等式制約条件:t_i(w^T x_i + b) \geq 1

この問題は,次のラグランジュ関数として定式化される.\tilde{L_p} (w, b, \alpha)=\frac{1}{2}w^T w - \Sigma_{i=1}^{N} \alpha_i (t_i (w^T x_i + b) - 1)

この主問題に対する相対問題は次の通り.
          評価関数(最大化):L_d (\alpha)=\alpha^T 1 - \frac{1}{2} \alpha^T H \alpha
          制約条件:\alpha^T t=0

相対問題のラグランジュ問題はラグランジュ未定乗数を\betaとすれば,次のように定式化される.\tilde{L}_d (\alpha, \beta)=\alpha^T 1 - \frac{1}{2} \alpha^T H \alpha - \beta \alpha^T t

最終的に,KKT条件の\alpha_i (t_i (w^T x_i + b) - 1 )=0がすべてのiで成り立でば良いので,
t_i (w^T x_i + b) - 1 )=0 で \alpha_i > 0
t_i (w^T x_i + b) - 1 )\neq 0 で \alpha_i = 0 となる.
\alpha_i > 0となるx_iをサポートベクトルという.
最適なバイアスb_0はサポートベクトルの一つx_sを用いてt_s (w_0^T x_s + b_0) - 1 = 0を解いて求めるか,その平均を求める.
最大マージンD_{max}\frac{1}{||w_0||}=\frac{1}{\sqrt{w_0^T w_0}}=\frac{1}{\sqrt{\Sigma_{i=1}^N \tilde{\alpha_i}}}となる.

(2)2クラスで線形分離不可能な場合(ソフトマージン識別器,C-SVM
線形分離不可能な場合は(1)のときの制約条件をすべて満たす解は求まらない.スラック変数\xi_iを導入し,以下のように損失関数として定式化する.
\xi_i = max[0, 1 - t_i (w^T x_i + b)] = f_{+} (1 - t_i (w^T x_i  + b)) (f_{+} (x) = x (x>0の場合) f_{+} (x) = 0 (それ以外の場合) )
t_i(w^T x_i + b) + \xi_i \geq 1
\xi_i=0(マージン内で正しく識別できる場合)
0<\xi_i \leq 1(マージン境界を越えるが正しく識別できる場合)
\xi_i > 1(識別境界を越えて誤識別される場合))

ソフトマージン識別器の主問題は次のように定義される.
           評価関数(最小化):L_p (w, \xi) = \frac{1}{2} w^T w + C \Sigma_{i=1}^N \xi_i
           不等式制約条件:t_i (w^T x_i + b) - 1+ \xi_i \geq 0, \xi_i \geq 0
全ての学習データのスラック変数の和\Sigma_{i=1}^N \xi_iは誤識別数の上限を与え,パラメータCは誤識別数に対するペナルティの強さを表す.

この問題は,次のラグランジュ関数として定式化される.\tilde{L_p} (w, b, \alpha, \xi, \mu)=\frac{1}{2}w^T w + C \Sigma_{i=1}^{N} \xi_i - \Sigma_{i=1}^{N} \alpha_i (t_i (w^T x_i + b) - 1 + \xi_i) - \Sigma_{i=1}^N \mu_i \xi_i

この主問題に対する相対問題は次の通り.
          評価関数(最大化):L_d (\alpha)=\alpha^T 1 - \frac{1}{2} \alpha^T H \alpha
          制約条件:0 \leq \alpha_i \leq C, \alpha^T t=0

解ベクトルはw_0 = \Sigma_{i=1}^N \alpha_i t_i x_iで得られる.\alpha \neq 0の要素がサポートベクトルとなる.

(3)線形分離不可能な場合(非線形特徴写像を用いた解法)
線形分離可能でない学習データは,非線形変換で高次元特徴空間へ写像することにより線形分離可能となる可能性があるという予測を頼りに非線形写像を考える.d次元の学習データx \in R^dと,その非線形写像の集合\{\varphi_j (x)\}_{j=1}^{M}について,非線形写像空間のベクトルを\varphi(x)=(\varphi_0 (x)=1, \varphi_1 (x),...,\varphi_M (x))^Tで表す.([trx:w_0 (x)=1]はバイアス項)
非線形特徴空間での線形識別関数をh(\varphi(x))=\Sigma_{j=0}^M w_j \phi_j (x) = w^T \phi(x)で表す.この線形空間内でSVMを考えれば,最適識別超平面はw_0=\Sigma_{i=1}^N \alpha_i t_i \phi(x_i)となるが,このとき識別関数がh(\varphi(x))=w_0^T \varphi(x)=\Sigma_{i=1}^{N} \alpha_i t_i \varphi^T (x_i)\varphi(x) =\Sigma_{i=1}^{N} \alpha_i t_i K(x_i, x)のようにもとのベクトル関数である核関数K(x_i, x)を用いて表せれば都合が良い.

ソフトマージン識別器のラグランジュ未定乗数\alpha_iは次の相対問題を解くことにより,得られる.
          評価関数(最大化):L_d (\alpha)
                     = \Sigma_{i=1}^N \alpha_i - \frac{1}{2}\Sigma_{i=1}^N\Sigma_{j=1}^N \alpha_i \alpha_j t_i t_j \varphi^T (x_i)\varphi(x_j)
                     = \Sigma_{i=1}^N \alpha_i - \frac{1}{2}\Sigma_{i=1}^N\Sigma_{j=1}^N \alpha_i \alpha_j t_i t_j K (x_i, x_j)
          制約条件:0 \leq \alpha_i \leq C, \alpha^T t = 0
          
核関数K(x_i, x)の計算をx_ixのd次元空間での内積空間で済ますと,高速な計算が可能になり,内積カーネルと呼ばれる.

(4)2クラスで線形分離不可能な場合(\nu -SVM
学習機械が達成できる誤り率と機械の複雑さには関連性があり,機械が複雑であるほど再代入誤り率は低くできる.そこで,機械の複雑さと誤り率との間のトレードオフを新しいパラメータvを介して明示的に取り入れたものが \nu -サポートベクトルマシンとよばれる.

主問題は次のように定義される.
           評価関数(最小化):L_p (w, \rho, \xi) = \frac{1}{2} w^T w -\nu\rho + \frac{1}{N} \Sigma_{i=1}^N \xi_i
           不等式制約条件:t_i (w^T \varphi(x_i) + b) - \rho + \xi_i \geq 0, \xi_i \geq 0
           
この問題は,次のラグランジュ関数として定式化される.\tilde{L_p} (w, b, \xi, \rho, \alpha, \mu) = \frac{1}{2}w^T w - \nu\rho + \frac{1}{N} \Sigma_{i=1}^{N} \xi_i - \Sigma_{i=1}^{N} \alpha_i (t_i (w^T \varphi(x_i) + b) - \rho + \xi_i) - \Sigma_{i=1}^N \mu_i\xi_i

この主問題に対する相対問題は次の通り.
          評価関数(最大化):L_d (\alpha)= -\frac{1}{2} \Sigma_{i=1}^N \Sigma_{i=1}^N \alpha_i \alpha_j t_i t_j K(x_i, x_j)
          制約条件: 0 \leq \alpha_i \leq \frac{1}{N}, \Sigma_{i=1}^N \alpha_i t_i = 0, \nu = \Sigma_{i=1}^N \alpha_i
\nuはマージン誤り,上限サポートベクトルの割合の上限を与えている.

(5)1クラス識別関数(1クラス \nu - SVM
主問題は次のように定義される.
           評価関数(最小化): L_p (w, \xi) = \frac{1}{2} w^T w -\rho + \frac{1}{nu N} \Sigma_{i=1}^N \xi_i
           不等式制約条件: w^T \varphi(x_i) - \rho + \xi_i \geq 0, \xi_i \geq 0
           
この主問題に対する相対問題は次の通り.
          評価関数(最大化):L_d (\alpha)= -\frac{1}{2} \Sigma_{i=1}^N \Sigma_{i=1}^N \alpha_i \alpha_j t_i t_j K(x_i, x_j)
          制約条件: 0 \leq \alpha_i \leq \frac{1}{\nu N}, \Sigma_{i=1}^N \alpha_i = 1

正例か外れ値かの識別関数は  f(x) = sgn(\Sigma_{i=1}^N \alpha_i K(x_i, x) - \rho) sgn(a) = +1 (a > 0), sgn(a) = 0 (a = 0), sgn(a) = -1 (a < 0)
f(x)=1のとき正例,f(x)=-1のとき外れ値である.