1. No category

SVMの
2次計画問題に関する解法の考察
東京理科大学工学部経営工学科
沼田研究室
4400079 戸田健一
卒業研究発表
1
発表構成
1. はじめに
2. クラス判別とSVM
2-1. クラス判別問題
2-2. サポートベクターマシン
2-3. 線形分離不可能な場合のSVM
2-4. 非線形SVM
3.
4.
5.
6.
7.
Sequential Minimal Optimization(SMO)
2段階SMO
実験
実験結果，考察
まとめ
参考文献
2
1.はじめに
z
z
z
z
パターン認識問題におけるクラス判別手法：
サポートベクターマシン(SVM)[1],抄録[3]
SVM：2次計画問題を解く
→データが多くなるにつれて計算量が非常に多くなる
Sequential Minimal Optimization (SMO) [2],[3],抄録[1],[2]：
SVMによる2次計画問題の計算量を減少
本研究の目的：
2段階SMOの提案，評価
3
２. クラス判別とSVM
2-1. クラス判別問題
x i = ( xi1 , xi2 , L , xim )
⎧ 1 x i ∈ χ1
yi = ⎨
所属クラス： から
⎩− 1 x i ∈ χ 2
学習データ：
判別境界：
f (x ) = w T x − b = 0
を作成し，
T
L (1)
最終的な判別関数： g (x i ) = sign ( f (x i ) ) = sign (w x i − b) ⎧1 x≥0
sign(x) = ⎨
⎩− 1 x < 0
⎧ 1 x i ∈ χ1
=
y
⎨
i
が，なるべく と一致するような
⎩− 1 x i ∈ χ 2
w,bを求める問題：クラス判別問題
4
2-2. サポートベクターマシン
H 1 : f ( x) = 1
H 2 : f (x) = −1
マージンの大きさ： 2
w
w
f ( x) = 0
複数の判別境界候補の中で
もっともマージンを大きくする超平面を
最良とみなす（マージン最大化基準）
図2 サポートベクターマシン
5
2-2. SVM（定式化）
⎧ ≥ 1 x i ∈ χ1
制約条件： w x i − b ⎨
⎩≤ −1 x i ∈ χ 2
(
T
目的関数：
2
w 最大化
)
yi w T x − b ≥ 1
1
w
2
2
最小化
6
2-2. SVM（定式化）
SVMの数理計画問題：
1
2
⎧
⎪minimize w
L (2)
⎨ w ,b 2
⎪⎩subject to yi ⋅ w T x i − b ≥ 1
(
)
これまでは線形分離可能を仮定
線形分離不可能な場合はどうするか？
7
2-3. 線形分離不可能な場合のSVM
線形分離不可能な場合の
SVMによる数理計画問題：
(P)
補正した分だけ
ペナルティを加算
n
1
⎧
2
w + C ∑ ξi
⎪minimize
w ,b ,ξ 2
i =1
⎪
T
L (3)
⎨subject to yi ⋅ w x i − b ≥ 1 − ξ i ⎪ ξi ≥ 0
⎪
⎩
誤判別しているとき
(
)
判別関数値を補正
C：マージン最大化の評価に対する
誤判別の程度の重みを決めるパラメータ
8
2-3. 線形分離不可能な場合のSVM
ラグランジュ関数 L [4],[5]を導入：
制約式を足しこむ
n
1
2
L ( w , b, ξ , α , γ ) = w + C ∑ ξ i
2
i =1
n
{ (
)
}
n
− ∑ α i yi w T x i − b − (1 − ξ i ) − ∑ γ iξ i L ( 4)
i =1
i =1
： 双対問題
L(w を，α,γについて最大化する問題
, b, ξ, α, γ )
⎧maximize L(w,b,ξ, α, γ )
α
⎪
(i = 1,..., n)
(D) ⎨subject to α i ≥ 0 ⎪
(i = 1,..., n)
γ i ≥ 0 ⎩
9
2-3. 線形分離不可能な場合のSVM
主問題(P)と双対問題(D)について
Karush-Kuhn-Tucker条件(KKT条件)：
∂L
∂L
∂L
(i = 1,..., n ), = 0 = 0, = 0(i = 1,..., n ) L (5)
∂ξ i
∂wi
∂b
∂L
∂L
(i = 1,..., n ), ≤ 0 (i = 1,..., n ) ≤ 0 L ( 6)
∂α i
∂γ i
(i = 1,..., n ), γ i ≥ 0 (i = 1,..., n ) α i ≥ 0 L (7 )
αi
(停留点)
(主実行可能性)
(双対実行可能性)
∂L
∂L
= 0(i = 1,..., n ), α i
= 0(i = 1,..., n ) L (8)
∂α i
∂γ i
(相補性)
を満たすとき, (P),(D)は最適解である
10
2-3. 線形分離不可能な場合のSVM
停留点の条件：
∂L
(i = 1,..., n )
= 0 ∂wi
∂L
=0
∂b
∂L
= 0 (i = 1,..., n)
∂ξ i
n
w = ∑ yiα i x i
i =1
n
∑ yα
i =1
i
i
=0
α i = C − ξ i (i = 1,..., n)
L(w, b, ξ, α, γ )
をラグランジュ関数： に代入
n
n
n
⎧
T
−
x
maximize
α
y
y
α
α
∑
∑∑
i
i j i j i xj
⎪
i =1
i =1 j =1
⎪
(D) ⎨subject to 0 ≤ α i ≤ C (i = 1,..., n)
L (9)
n
⎪
yiα i = 0
⎪
∑
i =1
⎩
11
2-3. 線形分離不可能な場合のSVM
H 1 : f ( x) = 1
H 2 : f (x) = −1
双対変数を用いた判別関数：
n
f (x ) = ∑ yiα i xTi x − b (10)
i =1
KKT条件による最適解の条件：
αi = 0
⇒ yi f (x i ) ≥ 1
0 < α i < C ⇒ yi f (x i ) = 1
αi = C
⇒ yi f (x i ) ≤ 1
f ( x) = 0
図3 最適解の条件
12
2-4. 非線形SVM
学習データを高次元に写像，高次元空間で線形判別
もとの次元の空間では非線形判別境界が作成可能
n
n n
⎧
T
(
)
−
h
x
maximize
α
y
y
α
α
∑
∑∑
i
i j i j
i h(x j )
⎪
i =1
i =1 j =1
⎪
(i = 1,..., n)
L(9)'
⎨subject to 0 ≤ αi ≤ C n
⎪
yiαi = 0
⎪
∑
i =1
⎩
(
図4 非線形SVM
)
T
h(x i ) h(x j ) をカーネル関数 K x i , x j で置換することにより
個々の学習データに対する写像が不要に
13
2-4. 非線形SVM
カーネル関数を用いた定式化：
n
n
n
⎧
⎪maximize ∑ α i − ∑∑ yi y jα iα j K (x i , x j )
i =1
i =1 j =1
⎪
(D) ⎨subject to 0 ≤ α i ≤ C
L (11)
n
⎪
yiα i = 0
⎪ ∑
i =1
⎩
双対変数を用いた判別関数：
n
f (x ) = ∑ yiα i K (x i , x ) − b (12)
i =1
14
3. Sequential Minimal Optimization
一般的な2次計画問題の解法：
学習データが多くなるにつれて問題のサイズが増大
多くの計算量が必要，実行時間が長くなる
Sequential Minimal Optimization(SMO)：
部分問題を生成し、逐次最適化
行列演算が不要になり、高速に解くことができる
n
n
n
⎧
⎪maximize W (α ) = ∑ α i − ∑∑ yi y jα iα j K (x i , x j )
i =1
i =1 j =1
⎪
L (10)
⎨subject to 0 ≤ α i ≤ C
n
⎪
yiα i = 0
⎪ ∑
i =1
⎩
15
3. SMO
2変数αi1, αi2を選び
他の変数を定数とみなして部分問題に
目的関数W：2変数の2次関数
制約条件：
n
∑ yα
i =1
i
i
= 0 ⇔ yi1α i1 + yi2α i2 +
n
∑α y
i =1
i ≠ i1 ,i2
i
⇔ yi1α i1 + yi2α i2 = Const.
i
=0
図5 部分問題の最適解
を代入 目的関数W:1変数の2次関数に
16
3. SMO
H 1 : f ( x) = 1
H 2 : f (x) = −1
双対変数を用いた判別関数：
n
f (x ) = ∑ yiα i K (x i , x ) − b (10)
i =1
KKT条件による最適解の条件：
αi = 0
⇒ yi f (x i ) ≥ 1
0 < α i < C ⇒ yi f (x i ) = 1
αi = C
⇒ yi f (x i ) ≤ 1
f ( x) = 0
図6 最適解の条件
17
3. SMO
SMOのアルゴリズム
Step1. KKT条件を満たしていないαi2を順番に選ぶ.
すべてのαi2がKKT条件を満たしていれば、最適解となり終了．
Step2. 以下の優先度でαi1を選ぶ．
2-1. 0<αi<Cであるαi1 について，
αi1, αi2の更新幅がなるべく大きくなるようなαi1を選ぶ．
2-2. αi=0, αi=Cであるαi1 について，
αi1, αi2の更新幅がなるべく大きくなるようなαi1を選ぶ．
2-3. ランダムにαi1を選ぶ．
Step3. αi1, αi2に関する部分問題を解く．
部分問題の最適解を得たらStep1へ．
18
4. 2段階SMO
SVM：
判別境界付近の学習データのみが判別境界に関係
2段階SMO:
予備問題で暫定的なサポートベクターを作り本問題を解く
19
4. 2段階SMO
解を修正
μ1
μ2
図7 2段階SMO
20
5. 実験
図8 実行画面
21
6. 実験結果，考察
表1 線形SVMによる実行時間
学習データ数
100
200
500
SMO
2段階SMO 短縮時間比率
実行時間(s)
1.4322
4.092
7.6386
1.3316
3.8412
7.2482
0 .9 2 9 8
0 .9 3 8 7
0 .9 4 8 9
表2 非線形SVMによる実行時間
学習データ数
100
200
500
SMO
2段階SMO 短縮時間比率
実行時間(s)
1.8604
13.311
67.1788
1.2678
11.9574
60.1366
0 .6 8 1 5
0 .8 9 8 3
0 .8 9 5 2
22
7.まとめ
SMOをより高速化させるべく２段階SMOを提案，評価
→速度向上はわずかなものにとどまった
２段階目でKKT条件を満たさない学習データが多かった
より効率の良い学習データの絞込み
整然としてない学習データに対する絞込み方法の考案が必要
23
参考文献
[1] 前田英作： 痛快！サポートベクトルマシン； 情報処理，42巻7号，pp．
676-683，2001.
[2] J.Platt： Sequential Minimal Optimization -A Fast Algorithm for Training
Support Vector Machines； Microsoft Technical Report，1998.
[3] Mak： The Implementation Of Support Vector Machines Using The
Sequential Minimal Optimization Algorithm； McGill University Master's
thesis， 2000.
[4] 矢部博，八巻直一： 非線形計画法； 朝倉書店， 1999.
[5] 福島雅夫： 非線形最適化の基礎； 朝倉書店， 2001.
24
訂正
p.183,上から11行目 誤：式(5)の判別関数に…
正：式(6)の判別関数に…
p.183,下から5行目 誤：Boland社の…
正：Borland社の…