「第七章」(2015/06/14 (日) 17:49:57) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*第七章 疎な解を持つカーネルマシン(Sparse Kernel Machines)
-前章で見た非線形カーネルに基づく学習アルゴリズムは、学習データ点の全ての$${\bf x}_n, {\bf x}_m$$の組み合わせについてカーネル関数が評価される必要があるため、計算量が増加する欠陥があった。ここでは学習データの部分集合のみについて評価されれば足りるカーネル関数によって予測を行う、疎な(&italic(){sparse})解を持つカーネルベースの手法を扱う。
-SVM(&italic(){support vector machine})は、ここ数年来、回帰・クラス判別・新規性検知における一般的な手法となっている。SVMの特徴は、モデルのパラメータ決定が凸最適化問題に対応していることと、そのために任意の局所解はまた大域的にも最適解である点にある。SVMは決定機械なので事後分布を提供しない。これに対して関連ベクトルマシンはベイズ法に基づいており事後分布を提供し、通常SVMよりもさらに疎な解を与える。
**7.1 最大マージン判別器(&italic(){Maximum Margin Classifiers})
-2クラス判別問題における線形モデル
$$y({\bf x}) = {\bf w}^{\rm T}{\bf \phi}({\bf x}) + b \hspace{1em} (7.1)$$
を考え、目標変数は$$t_n \in \left\{-1,1\right\}$$でその符号の正負によってクラスを弁別するものする。いま仮に学習データ集合が線形分離可能であると仮定すると、全学習データ点を二分するような$${\bf w}$$および$$b$$の選択が複数存在し、それらのうちで最適なものをマージン(&italic(){margin})、すなわち境界平面と学習データ点のどれかとの間の最短距離を最大にするものがどれかという観点から決定する。最大マージン解は計算論的学習理論(&italic(){computational learning theory})ないし統計的学習理論(&italic(){statistical learning theory})において活用される以前にもTongとKollerによって考察された生成判別混合アプローチに基づいた判別手法において既に与えられていた。彼らはパラメータ$$\sigma^2$$を共有するガウスカーネルによるパルツェン密度推定を利用して各クラスごとに入力ベクトル$${\bf x}$$の分布をモデル化した。これはクラス毎の事前分布と相俟って最適な誤判別率を伴う決定境界を定義するが、彼らはそれを使わずに学習した密度モデルとの間の相対的誤差の確率を最小化することによって超平面を定めた。$$\sigma^2 \rightarrow 0$$となるとき、最大のマージンを持つ超平面が最適な決定境界となる。直感的にいうと、$$\sigma^2$$が小さくなるにつれて超平面は遠くのデータ点よりもより近くのデータ点によって支配されるようになっていき、極限において超平面はサポートベクトル以外のデータ点に影響されなくなる。
-すべての学習データ点を正しくクラス分けする(7.1)の形式を持つ超平面を$$y({\bf x})$$とすると、
$$t_ny(x) \hspace{2em} \g \hspace{2em} 0$$
が成り立つ。一方、点$${\bf x}$$から(7.1)の形式の超平面への垂直距離は
$$\frac{t_ny({\bf x})}{\|{\bf w}\|} = \frac{t_n\left({\bf w}^{\rm T}{\bf \phi}({\bf x}_n) + b\right)}{\|{\bf w}\|}$$
で表されるから、最大マージン解は
$$\frac{1}{\|{\bf w}\|}{\rm min}_n\left[t_n\left({\bf w}^{\rm T}{\bf \phi}({\bf x}_n) + b\right)\right]$$
を最大化する$${\bf w},b$$だということになる。$${\bf w},b$$を定数倍しても距離は上の垂直距離は不変なので上の問題は
$$t_n\left({\bf w}^{\rm T}{\bf \phi}({\bf x}_n) + b\right) \geq 1 \hspace{2em} \left(n = 1,...,N\right)$$
という複数の制約の下で
$$\frac{1}{2}\|{\bf w}\|^2 \hspace{1em} (7.6)$$
を最小化する$${\bf w},b$$を求める二次計画問題(&italic(){quadratic programming problem})と等価。
この問題を解くためにラグランジュの未定乗数$$a_n$$を導入すると、以下のラグランジュ関数を得る。
$$L\left({\bf w},b,{\bf a}\right) = \frac{1}{2}\|{\bf w}\|^2 - \sum_{n=1}^{N}a_n\left\{t_n\left({\bf w}^{\rm T}{\bf \phi}({\bf x}_n) + b\right) - 1\right\} \hspace{2em} \left({\bf a} = \left(a_1,...,a_N\right)^{\rm T}\right)$$
これを$${\bf w},b$$について微分して0と等置して得た式によって上式から$${\bf w},b$$を取り除くと、次のような双対表現(&italic(){dual representation})を得る。
$$\tilde{L}({\bf a}) = \sum_{n=1}^{N}a_n - \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk({\bf x}_n,{\bf x}_m) \hspace{1em} (7.10) \hspace{1em} \left(k({\bf x},{\bf x}') = {\bf \Phi}^{\rm T}{\bf \Phi}, \hspace{1em} a_n \geq 0 \left(n = 1,...,N\right), \hspace{1em} \sum_{n=1}^{N}a_nt_n = 0\right)$$
(7.10)はこれ自体別の二次計画問題となっており、その計算複雑性は(7.6)の場合は$$O(M^3)$$であるのに対して(7.10)の場合には$$O(N^3)$$となる。これは一見すると$$N$$よりも$$M$$のほうが大きい場合には上の双対表現への変換は計算複雑性上不利になるように見えるが、カーネル関数を使用して書き換えることで無限次元を含む大きい次元を有する特徴空間を扱うことができ、またカーネル関数が正定値であるべきという制約がラグランジュ関数が上に有界であることを保証することが見やすくもなる。
-新たな入力をクラス分けするには、
$$y({\bf x}) = \sum_{n=1}^{N}a_nt_nk({\bf x},{\bf x}') + b \hspace{1em} (7.13)$$
の符号を調べる。$$a_n = 0$$の場合には対応するデータ点は寄与せず、それ以外の場合のデータ点をサポートベクトル(&italic(){support vector})といい、それらは特徴空間における最大マージンを持つ超平面上に存在する、すなわち$$t_ny({\bf x}) = 1$$。つまりいったんモデルの学習が完了すると、サポートベクトルを除く大半の学習データ点は捨てて構わない。二次計画問題を解き$${\bf a}$$を求めたら$$t_ny({\bf x})=1$$を使って閾値パラメータ$$b$$を求めることができる。
-最大マージン判別器は以下の単純な二次正則化項付き誤差関数の最小化問題として表すことができる。
$$\sum_{n=1}^{N}E_{\infty}\left(y({\bf x}_n)t_n - 1\right) + \lambda\|{\bf w}\|^2 \hspace{1em} (7.19)$$
ただし$$E_{\infty}(z)$$は$$z$$が0以上のとき0、それ以外のときは∞をとる関数。
-最大マージンを持つ超平面はサポートベクトルである学習データ点のみに依存し、それ以外の学習データ点には一切依存しない。
***クラス分布が重複する場合
-これまでのように学習データ点が線形分割可能であるとの仮定の下では、結果として得られるSVMは元の入力空間$${\bf x}$$において学習データ点を完全に分割することができた(境界平面は線形とは限らない)。しかし一般にはクラス別分布は互いに重なり合っている可能性があり、その場合にはこれまでのような完全分割ではよい予測能力が得られないことが実際には多い。
-そこでSVMに学習データに誤分類されたものが含まれるという仮定を追加する(ソフトマージン)。そのためには各学習データ点ごとにスラック変数(&italic(){slack variable})$$\xi_n \geq 0$$を導入し、正しいマージン境界上ないし内側に位置する学習データについては$$\xi_n = 0$$、それ以外の学習データについては$$\xi_n = |t_ - y({\bf x})|$$とすると、決定平面上の学習データ($$y({\bf x}) = 0$$)については$$\xi_n = 1$$、誤分類された学習データについては$$\xi_n > 1$$となる。すると全ての学習データ点について
$$t_ny({\bf x}_n) \geq 1 - \xi_n \hspace{1em} \left(\xi_n \geq 0, \hspace{1em} n = 1,...,N\right) \hspace{1em} (7.20)$$
これによってクラス別分布の重複が許されることになるが、この手法は誤分類に対して与えられるペナルティが$$\xi$$について線形に増加するため、異常値に左右されやすいことにも注意。
-ソフトマージンによるSVMは
$$C\sum_{n=1}^{N}\xi_n + \frac{1}{2}\|{\bf w}\|^2 \hspace{1em} (7.21)$$
を最小化する問題として表すことができる。$$C$$はスラック変数によるペナルティとマージンとの間のトレードオフを制御するパラメータで、学習における誤り最小化とモデル複雑性との間のトレードオフを制御する一種の正則化項とみなすことができる。誤分類された学習データ点について$$\xi_n > 1$$なので、誤分類数の上限は$$\sum_{n}\xi_n$$となる。上の式で$$C \rightarrow \infty$$とすると完全分割可能なSVMに還元される。
-ソフトマージンによるSVMは、(7.20)および$$\xi_n \geq 0$$の制約の下で(7.21)を最小化する問題、すなわち
$$L\left({\bf w},b,\xi,a,\mu_n\right) = \frac{1}{2}\|{\bf w}\|^2 + C\sum_{n=1}^{N}\xi_n - \sum_{n=1}^{N}a_n\left\{t_ny({\bf x}_n) - 1 + \xi_n\right\} - \sum_{n=1}^{N}\mu_n\xi_n \hspace{2em} (7.22)$$
($$a_n,\mu_n$$はラグランジュの未定乗数)をKKT条件(&italic(){Karush-Kuhn-Tucker condition})の下で解くことになる。(7.22)を$${\bf w},b,\xi_n$$それぞれで偏微分して0と等置して(7.22)に代入すると、
$$\tilde{L}(a) = \sum_{n=1}^{N}a_n - \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk({\bf x}_n,{\bf x}_m)$$
(詳細略)
-あるいは$$\nu$$-SVMという等価な手法もある。
*第七章 疎な解を持つカーネルマシン(Sparse Kernel Machines)
-前章で見た非線形カーネルに基づく学習アルゴリズムは、学習データ点の全ての$${\bf x}_n, {\bf x}_m$$の組み合わせについてカーネル関数が評価される必要があるため、計算量が増加する欠陥があった。ここでは学習データの部分集合のみについて評価されれば足りるカーネル関数によって予測を行う、疎な(&italic(){sparse})解を持つカーネルベースの手法を扱う。
-SVM(&italic(){support vector machine})は、ここ数年来、回帰・クラス判別・新規性検知における一般的な手法となっている。SVMの特徴は、モデルのパラメータ決定が凸最適化問題に対応していることと、そのために任意の局所解はまた大域的にも最適解である点にある。SVMは決定機械なので事後分布を提供しない。これに対して関連ベクトルマシンはベイズ法に基づいており事後分布を提供し、通常SVMよりもさらに疎な解を与える。
**7.1 最大マージン判別器(&italic(){Maximum Margin Classifiers})
-2クラス判別問題における線形モデル
$$y({\bf x}) = {\bf w}^{\rm T}{\bf \phi}({\bf x}) + b \hspace{1em} (7.1)$$
を考え、目標変数は$$t_n \in \left\{-1,1\right\}$$でその符号の正負によってクラスを弁別するものする。いま仮に学習データ集合が線形分離可能であると仮定すると、全学習データ点を二分するような$${\bf w}$$および$$b$$の選択が複数存在し、それらのうちで最適なものをマージン(&italic(){margin})、すなわち境界平面と学習データ点のどれかとの間の最短距離を最大にするものがどれかという観点から決定する。最大マージン解は計算論的学習理論(&italic(){computational learning theory})ないし統計的学習理論(&italic(){statistical learning theory})において活用される以前にもTongとKollerによって考察された生成判別混合アプローチに基づいた判別手法において既に与えられていた。彼らはパラメータ$$\sigma^2$$を共有するガウスカーネルによるパルツェン密度推定を利用して各クラスごとに入力ベクトル$${\bf x}$$の分布をモデル化した。これはクラス毎の事前分布と相俟って最適な誤判別率を伴う決定境界を定義するが、彼らはそれを使わずに学習した密度モデルとの間の相対的誤差の確率を最小化することによって超平面を定めた。$$\sigma^2 \rightarrow 0$$となるとき、最大のマージンを持つ超平面が最適な決定境界となる。直感的にいうと、$$\sigma^2$$が小さくなるにつれて超平面は遠くのデータ点よりもより近くのデータ点によって支配されるようになっていき、極限において超平面はサポートベクトル以外のデータ点に影響されなくなる。
-すべての学習データ点を正しくクラス分けする(7.1)の形式を持つ超平面を$$y({\bf x})$$とすると、
$$t_ny(x) \hspace{2em} \g \hspace{2em} 0$$
が成り立つ。一方、点$${\bf x}$$から(7.1)の形式の超平面への垂直距離は
$$\frac{t_ny({\bf x})}{\|{\bf w}\|} = \frac{t_n\left({\bf w}^{\rm T}{\bf \phi}({\bf x}_n) + b\right)}{\|{\bf w}\|}$$
で表されるから、最大マージン解は
$$\frac{1}{\|{\bf w}\|}{\rm min}_n\left[t_n\left({\bf w}^{\rm T}{\bf \phi}({\bf x}_n) + b\right)\right]$$
を最大化する$${\bf w},b$$だということになる。$${\bf w},b$$を定数倍しても距離は上の垂直距離は不変なので上の問題は
$$t_n\left({\bf w}^{\rm T}{\bf \phi}({\bf x}_n) + b\right) \geq 1 \hspace{2em} \left(n = 1,...,N\right)$$
という複数の制約の下で
$$\frac{1}{2}\|{\bf w}\|^2 \hspace{1em} (7.6)$$
を最小化する$${\bf w},b$$を求める二次計画問題(&italic(){quadratic programming problem})と等価。
この問題を解くためにラグランジュの未定乗数$$a_n$$を導入すると、以下のラグランジュ関数を得る。
$$L\left({\bf w},b,{\bf a}\right) = \frac{1}{2}\|{\bf w}\|^2 - \sum_{n=1}^{N}a_n\left\{t_n\left({\bf w}^{\rm T}{\bf \phi}({\bf x}_n) + b\right) - 1\right\} \hspace{2em} \left({\bf a} = \left(a_1,...,a_N\right)^{\rm T}\right)$$
これを$${\bf w},b$$について微分して0と等置して得た式によって上式から$${\bf w},b$$を取り除くと、次のような双対表現(&italic(){dual representation})を得る。
$$\tilde{L}({\bf a}) = \sum_{n=1}^{N}a_n - \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk({\bf x}_n,{\bf x}_m) \hspace{1em} (7.10) \hspace{1em} \left(k({\bf x},{\bf x}') = {\bf \Phi}^{\rm T}{\bf \Phi}, \hspace{1em} a_n \geq 0 \left(n = 1,...,N\right), \hspace{1em} \sum_{n=1}^{N}a_nt_n = 0\right)$$
(7.10)はこれ自体別の二次計画問題となっており、その計算複雑性は(7.6)の場合は$$O(M^3)$$であるのに対して(7.10)の場合には$$O(N^3)$$となる。これは一見すると$$N$$よりも$$M$$のほうが大きい場合には上の双対表現への変換は計算複雑性上不利になるように見えるが、カーネル関数を使用して書き換えることで無限次元を含む大きい次元を有する特徴空間を扱うことができ、またカーネル関数が正定値であるべきという制約がラグランジュ関数が上に有界であることを保証することが見やすくもなる。
-新たな入力をクラス分けするには、
$$y({\bf x}) = \sum_{n=1}^{N}a_nt_nk({\bf x},{\bf x}') + b \hspace{1em} (7.13)$$
の符号を調べる。$$a_n = 0$$の場合には対応するデータ点は寄与せず、それ以外の場合のデータ点をサポートベクトル(&italic(){support vector})といい、それらは特徴空間における最大マージンを持つ超平面上に存在する、すなわち$$t_ny({\bf x}) = 1$$。つまりいったんモデルの学習が完了すると、サポートベクトルを除く大半の学習データ点は捨てて構わない。二次計画問題を解き$${\bf a}$$を求めたら$$t_ny({\bf x})=1$$を使って閾値パラメータ$$b$$を求めることができる。
-最大マージン判別器は以下の単純な二次正則化項付き誤差関数の最小化問題として表すことができる。
$$\sum_{n=1}^{N}E_{\infty}\left(y({\bf x}_n)t_n - 1\right) + \lambda\|{\bf w}\|^2 \hspace{1em} (7.19)$$
ただし$$E_{\infty}(z)$$は$$z$$が0以上のとき0、それ以外のときは∞をとる関数。
-最大マージンを持つ超平面はサポートベクトルである学習データ点のみに依存し、それ以外の学習データ点には一切依存しない。
***クラス分布が重複する場合
-これまでのように学習データ点が線形分割可能であるとの仮定の下では、結果として得られるSVMは元の入力空間$${\bf x}$$において学習データ点を完全に分割することができた(境界平面は線形とは限らない)。しかし一般にはクラス別分布は互いに重なり合っている可能性があり、その場合にはこれまでのような完全分割ではよい予測能力が得られないことが実際には多い。
-そこでSVMに学習データに誤分類されたものが含まれるという仮定を追加する(ソフトマージン)。そのためには各学習データ点ごとにスラック変数(&italic(){slack variable})$$\xi_n \geq 0$$を導入し、正しいマージン境界上ないし内側に位置する学習データについては$$\xi_n = 0$$、それ以外の学習データについては$$\xi_n = |t_ - y({\bf x})|$$とすると、決定平面上の学習データ($$y({\bf x}) = 0$$)については$$\xi_n = 1$$、誤分類された学習データについては$$\xi_n > 1$$となる。すると全ての学習データ点について
$$t_ny({\bf x}_n) \geq 1 - \xi_n \hspace{1em} \left(\xi_n \geq 0, \hspace{1em} n = 1,...,N\right) \hspace{1em} (7.20)$$
これによってクラス別分布の重複が許されることになるが、この手法は誤分類に対して与えられるペナルティが$$\xi$$について線形に増加するため、異常値に左右されやすいことにも注意。
-ソフトマージンによるSVMは
$$C\sum_{n=1}^{N}\xi_n + \frac{1}{2}\|{\bf w}\|^2 \hspace{1em} (7.21)$$
を最小化する問題として表すことができる。$$C$$はスラック変数によるペナルティとマージンとの間のトレードオフを制御するパラメータで、学習における誤り最小化とモデル複雑性との間のトレードオフを制御する一種の正則化項とみなすことができる。誤分類された学習データ点について$$\xi_n > 1$$なので、誤分類数の上限は$$\sum_{n}\xi_n$$となる。上の式で$$C \rightarrow \infty$$とすると完全分割可能なSVMに還元される。
-ソフトマージンによるSVMは、(7.20)および$$\xi_n \geq 0$$の制約の下で(7.21)を最小化する問題、すなわち
$$L\left({\bf w},b,\xi,a,\mu_n\right) = \frac{1}{2}\|{\bf w}\|^2 + C\sum_{n=1}^{N}\xi_n - \sum_{n=1}^{N}a_n\left\{t_ny({\bf x}_n) - 1 + \xi_n\right\} - \sum_{n=1}^{N}\mu_n\xi_n \hspace{2em} (7.22)$$
($$a_n,\mu_n$$はラグランジュの未定乗数)をKKT条件(&italic(){Karush-Kuhn-Tucker condition})の下で解くことになる。(7.22)を$${\bf w},b,\xi_n$$それぞれで偏微分して0と等置して(7.22)に代入すると、
$$\tilde{L}(a) = \sum_{n=1}^{N}a_n - \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk({\bf x}_n,{\bf x}_m)$$
(詳細略)
-あるいは$$\nu$$-SVMという等価な手法もある。
$$\left(\left(a\right)\right)}$$
表示オプション
横に並べて表示：
変化行の前後のみ表示：
