データ学習アルゴリズム」

「データ学習アルゴリズム」
報告者佐々木稔
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] パターン識別における従来の方法論
• 与えられたデータを小さな次元の空間上に射影し、
誤り率が少ないように識別平面を構成
• 推定すべきパラメータ数を減らして統計誤差を
小さくした
サポートベクトルマシンでは、
• 逆に超高次元空間に埋込み、分離平面を決定
• 最適化するパラメータの数は多いが、カテゴリ間
距離が大きくなるので統計誤差は少なくなる
文字認識や画像認識への応用
人手による認識率と同等の性能を持つ
高次元空間で表現される複雑な
パターン認識において
「統計誤差を少なくする小さなモデルを選択する」
よりも、
「大きなモデルを用意して、統計誤差は別の方法
で抑えるようにする」
方が良い予測を行う可能性を示す

Download Report