「データ学習アルゴリズム」報告者佐々木稔 2003年9月18日第3章複雑な学習モデル 3.4 サポートベクトルマシン 3.4.1 サポートベクトルマシンの定義 3.4.2 マージン最大化 3.4.3 高次元埋込みと核関数サポートベクトルマシンパターンを２つのカテゴリに識別するためのモデル学習用データ {(xi, yi) ; i = 1, 2,･･･, N} xi (∈RM) は M 次元空間ベクトル yi はカテゴリに応じて +1 またはｰ1 をとる 3.4.1 サポートベクトルマシンの定義実数 R1 から {ｰ1, 1} への関数 sign(a) の定義 1 sign(a)   1 (a  0) (a  0) サポートベクトルマシンの定義 y  sign wx  b x ： RM から RH への関数 w∈RH , b∈R1 サポートベクトルマシンの学習法 • あらかじめ定めておくこと 1. 内積計算をするための非常に高次元な空間 RH 2. 非常に高次元な空間 RH へ射影する関数  •  で射影した先 RH における平面 z  R H  ; w z  b  0 で yi w  xi   b  0 i  1,2,, N  を満たせば、この平面を分離超平面という訓練サンプル集合が線形分離可能だとしても、誤りなく分離する平面は一意に定まらない訓練サンプルをすれすれに通るのではなく、なるべく余裕をもって分ける識別平面が求められるマージン分離超平面から最も近い訓練サンプルとの余裕 w  xi   b Marginw, b  min i 1 w n ここで、 w  w1  w2   wH 2 2 2 2 これが最大となるような分離超平面を定める w, b を見つけるただし、 w=aw, b=ab と定数倍してもマージンは変化しないそこで、マージンを最大化し、かつ、 min yi w xi   b  1 n i を満たすパラメータ w, b を求める w  xi   b  0 w  xi   b  1 1 Marginw, b  w w  xi   b  1 [注34] マージン最大化の意味 • 入力空間は2つのカテゴリの和で書くことができる • 入力はある定まった確率分布に従って独立に得られる超高次元空間 RH で、学習サンプルを正しく識別できない確率 Pemp 新しい入力にサポートベクトルマシンが誤る確率 P  E(n) P  Pemp  1 1 Pemp / E(n) 2  となる確率が (1ｰδ) 以上となる 4 E(n)  h(1 log(2n / h))  (log ) / 4 n h はVC次元と呼ばれる学習モデルの複雑さを表す量学習サンプル xi がすべて || xi ||≦D を満たし、かつ、マージンが A のサポートベクトルマシンの場合、Pemp=0 VC次元 h は、  D2   h  min 2 , H   1  A   マージンを大きくすると VC 次元は小さくなる優れた認識性能が得られる傾向がある 3.4.2 マージン最大化マージンを最大とするパラメータ w, b を求める問題 w∈RH , b∈R1 とする。制約条件 yi w  xi   b 1 i  1,2,, N  の下で、目的関数 1 2 Lw  w 2 を最小とするパラメータ w, b を求める Lagrange未定乗数 αi (≧ 0) ( i=1,2, ･･･, N ) を導入 1 2 N Lw, h,   w  i yi w  xi   b1 2 i 1 この関数で、(w, b) については最小化、 α≧0 については最大化 (w, b) について偏微分すると、 N L  w  i yi xi   0 w i 1 L N  i yi  0 b i 1 この関係を L(w, b, α) に代入して 1 Lw, h,   2 2  y  x     y y  x  x   N i 1 i i i N N i 1 j 1 N i j i j i 1 N N  i  i j yi y j  xi  x j  2 i 1 j 1 i 1 これより、双対問題が得られる N 制約条件 N  y i 1 i i 0 αi≧0 (i =1, 2, ･･･, N) の下で、以下の目的関数を最大化する N 1 N N L   i  i j yi y j  xi  x j  2 i1 j 1 i 1 j i 1 i Lagrange未定乗数に関する最適化問題シンプレックス法などで解を求める非常に規模が大きい問題で、直接解くのは難しい（[注35]参照）解α* が得られたとすると、パラメータ w*, b* は N w*   *i yi xi  i 1 パラメータ b* は、Kuhn-Tackerの定理より、  * yi w*  xi   b*1  0 i を満たすものを求める Kuhn-Tacker の定理凸集合 S 上に定義された（下に凸な）凸関数 f(u) の最小値を条件 gk(u)≦0 (k=1, 2, ･･･, K; gk(u) はすべて凸関数)で求める Lagrange関数 K Lu,   f x  k gk u  k 1 u∈S で gk(u)≦0 (k=1, 2, ･･･, K) が存在し、 u*∈S で L(u, α) が最適解となる (α={αk}) このとき、  * gk u*   0 (k  1,2,K ) k      min L u,  L u ,  max L u , uS * を満たすα*≧0 が存在する * *  0 *   * yi w*  xi   b*1  0 i   0 となるサンプル (xi, yi) は、 * i *   w  xi  b  1 * *   w  xi  b  1 * のどちらかの超平面にのっている超平面上のサンプル xi を「サポートベクトル」という w  xi   b  1 *  0 w  xi   b  1 *  0 i i  0 * i *  0 i *  0 i w  xi   b  0 パラメータ b* は、 b  yi  w xi  * *  *  0 となる訓練サンプルを無視して、  *  0 となる識別平面に近い少数の訓練サンプル i i のみを用いて識別関数を構成する「マージン最大化」の基準から自動的に識別平面付近のサンプルが選択されるため、未学習データにもある程度良い性能を維持できる [注35] • 与えられたデータを完全線形分離できない場合、「ソフトマージン」とよばれる目的関数を使うことで可能となる • いくつかのサンプルが超平面を超えて反対側に入り、多少の識別誤りを許す方法 3.4.3 高次元埋込みと核関数高次元空間への写像 x の定義 1 N N L   i  i j yi y j  xi  x j  2 i1 j 1 i 1 N b  yi  w  xi   yi   i yi  xi  x j  N * * * i 1 高次元空間内での内積計算に膨大な計算量が必要となる内積計算を効率良くする例48 x = (x1, x2), y = (y1, y2) とする R2 から R6 への埋込み関数を x  (1, 2x1, 2x2 , x , x , 2x1x2 ) 2 2 1 2 とすると、  x  y  1 2x1 y1  2x2 y2  x2 y 2  x2 y 2  2x1x2 y1 y2 1 1 (x  y) 2 1 2 2  1 2x1 y1  2x2 y2  x12 y12  x22 y22  2x1x2 y1 y2 よって、 (x) ( y)  1 (x  y) 2 左辺は R6 の内積計算であるが、右辺は R2 の計算で済む（カーネルトリック） 256次元の場合、 1 ( x  y)  1 x1 y1  x2 y2  x256y256 2 2 右辺を展開して整理すると、33153次元になるらしい多項式カーネル (x) ( y)  1 (x  y) p 2次よりも高次元の場合にも使うことができる [注36] パターン識別における従来の方法論 • 与えられたデータを小さな次元の空間上に射影し、誤り率が少ないように識別平面を構成 • 推定すべきパラメータ数を減らして統計誤差を小さくしたサポートベクトルマシンでは、 • 逆に超高次元空間に埋込み、分離平面を決定 • 最適化するパラメータの数は多いが、カテゴリ間距離が大きくなるので統計誤差は少なくなる文字認識や画像認識への応用人手による認識率と同等の性能を持つ高次元空間で表現される複雑なパターン認識において「統計誤差を少なくする小さなモデルを選択する」よりも、「大きなモデルを用意して、統計誤差は別の方法で抑えるようにする」方が良い予測を行う可能性を示す