カーネル法

クラシックな機械学習の入門
5. サポートベクターマシン
SVMの概念
双対化によるSVMの定式化：線形分離可能な場合
KKT条件とサポートベクトル
双対化の御利益
ソフトマージンSVM：線形分離できない場合
SVM実装のためのアルゴリズム（ワーキング集合、SMO)
SVMによる回帰
カーネル関数
by 中川裕志（東京大学）
再掲：2乗誤差最小化の線形識別の問題点
この領域に青の
境界線が引っ張
られることあり。
この領域の判断が
困難
そもそも、Yの値は正規分布を想定した理論なのに、｛0、1｝
の2値しかとらないとして2乗誤差最小化を当てはめたところ
に無理がある。
ＳＶＭの定式化
学習データ：
N個の入力ベクトルx1,…,xNと
各々に対応するクラス分け結果 y1,….,yN
ただし、 yi は＋１（正例）かー１（負例）をとる。
新規のデータxに対して、yが y(x)>0なら正、y(x)<0な
ら負になるようにしたい
y (x)  w, x  w0
正しい分類ができた場合は、
y (x)  0かつ y  1
すなわち、
あるいは
y (x)  0かつ y  1
y ( x) y  0
正しく分類できなかっ
た場合は、当然ながら
y ( x) y  0
ｙ（ｘ）＝＋１
ｙ（ｘ）＝０
ｙ（ｘ）＝ー１
正例
Support vector
この長さを最
大化したい：
(SVM10)の
max
margin 
境界面との距離が小
さいデータを選びた
い(ＳＶＭ１０）のmin
| y (x) |
|| w ||
負例
この図から分かるよ
うに対象は線形分離
可能な場合
マージン最大化
 SVMの狙いは識別境界面:y(ｘ)=0から一番近いデ
ータ点までの距離（マージン:margin）を最大化する
こと。以下でその考えを定式化する。
 識別境界面:y(ｘ)=0からあるｘまでの距離は、線形
識別の幾何学的解釈で述べたようにy(ｘ)/||w||
 我々は正しく識別されたデータ、すなわち
yny(xn)>0 のデータにだけ焦点を当てる。
 すると、点xnから境界面までの距離は次式。
yn y (x n ) yn ( w, x n  w0 )

|| w ||
|| w ||
wを定数倍してcwと変換しても、境界面までの距離
yny(xn)/||w||の値は分母子でcが相殺するので不変。
 よって、境界面に一番近い点で次式が成立している
とする。
yn ( w, x n  w0 )  1
したがって、最適なw,w0を求めることは、境界面までの距離が
最小の点の距離（margin)を最大化するという問題に定式化でき、
以下の式となる。
 1

arg max 
minyn ( w, x n  w0 )
w , w0 || w || n


 ( SVM 10)
この最適化はそのままでは複雑なので、等価な問題に変換す
る。
双対問題化
元の問題では、argmax{ min }という一般的な枠組みの問題な
ので、内点法などの効率の良い最適化アルゴリズムが良く研究さ
れている「線形制約凸２次計画問題」に変換する方向に進める。
参考文献：工系数学講座１７「最適化法」（共立出版）
境界面に一番近いデータでは
yn ( w, x n  w0 )  1
したがって、正しく識別された全てのデータは次式の制約を満た
す。
yn ( w, x n  w0 )  1
n  1,, N
ここで、等号が成り立つデータをactive、そうでないデータを
inactiveと呼ぶ。
制約条件： yn ( w, x n  w0 )  1
n  1,, N
 ( SVM 20)
ここで、等号が成り立つデータをactive、そうでないデータを
inactiveと呼ぶ。
定義より、activeなデータは境界面に一番近いデータであり、こ
れがsupport vectorとなる。
このとき、marginを最大化する式(SVM10)から、||w||－１を最大
化するのだが、これは等価的に||w||2を最小化する問題となる。す
なわち、以下の定式化。
1
1 T
2
arg min || w ||  w w
2
2
w ,b
subject to
yn ( w, x n  w0 )  1
n  1,, N
 ( SVM 30)
（SVM30)のような不等式制約を持つ最適化問題は、Lagrange未
定乗数ベクトルaを導入したLagrange関数: L(w, w0,a)を
w,w0（最小化)a(最大化) という最適化問題に双対化する
まず、w, w0について、 L(w, w0,a)の最適化を行う。
N
1
2
L(w, w0 ), a)  || w ||   an 1  yn ( w, x n  w0 )  ( SVM 40)
2
n 1
w, w0に関して微分すると以下の条件が出る。
N
w   an yn x n
 ( SVM 50)
n 1
N
0   an yn
 ( SVM 60)
n 1
(SVM50)(SVM60)を（SVM40)に代入して、wとw0を消すと、
次のように双対問題としての定式化が得られる
SVMの双対問題ー境界面で完全に分離できる場合
N
1 N N

~
max L (a)  max  an   an am yn ym k (x n , x m )
2 n1 m1
 n1

subject to
an  0
n  1,.., N
 ( SVM 80)
N
a y
n 1
n n
0
 ( SVM 70)
 ( SVM 90)
これがカーネル関数（データ
xn,xmの対だけによる）
後で説明する
where k (x n , x m )  x n , x m
また、新規のデータに対する予測は次式の y (x)で行う
N
y (x)   an yn k (x, x n )  w0

（ SVM100)
n 1
上記(SVM70,80,90)を解くアルゴリズムは後に説明する。また、（ＳＶＭ１００）で良い
理由はカーネルの関する記述で述べる（表現定理）
双対化を最適化の観点から見なおそう
最適化問題 P
min f x 
subject togi x   0
i  1,..,m
ラグランジュ関数
Lx,    f x   i 1  i gi x 　m
 f x   T g x  , gはベクトルで書く
双対問題Ｑ
q   min L x,  
x
max q 
subject t o   0

双対定理
弱双対定理
最適化問題Pにおけるfの最適値=f*
双対問題Ｑにおけるqの最適値=q*
q* ≤ f*
強双対定理
目的関数fが凸で、制約条件が線形の場合は q*
= f*であり、対応するラグランジュ乗数λ*が存在
する。
Ｐは制約条件が線形なので、 fが凸なら強双対
定理が成立
双対化を最適化の観点から見なおそう
 元の問題（再掲）
1
arg min || w ||2
2
w , w0
subject to
yn ( w, x n  w0 )  1
n  1,, N
 ( SVM 30)
この問題では目的関数は２乗ノルムなので凸
であり、制約条件が線形な式なので、強双対
定理が成立し、双対問題を解けば、この問題
（主問題）の解が得られる。
鞍点定理からみると
 元の問題（再掲）
1
arg min || w ||2
2
w ,b
subject to
yn ( w, x n  w0 )  1
n  1,, N
 ( SVM 30)
N
1
2
L(w, w0 , a)  || w ||   an 1  yn  w, x n  w0 
2
n 1
 ( SVM 40)
w, w0に関して微分すると以下の条件が出る。
N
w   an yn x n
 ( SVM 50)
n 1
N
0   an yn
 ( SVM 60)
n 1
上記のLagrange関数L(w,w0,a)の最小化の
意味は次のページの図
 Lagrange関数L(w, w0,a)の最小化の意味は下の図で
鞍点にかかる曲線に上から近づく処理であり、
L
L
となるw, w0を代入してのように動く。
 0,
0
w
w0
 この曲線に沿って最適点に a を動かす処理が双対
問題であり、図から分かるように最大化となる
min Lw, w0 , a  という問題
 つまり max
w ,w
a
0
鞍点定理
x , *　min max Lx,    Lx* , *   max min Lx,  
 *
x
 0
 0
 x*は主問題, *は双対問題の解
前のページとの対応はww0=x, a=λ
x
スパースなデータに対する識別器

k (x n , x m )  x n , x m
；カーネル関数を利用して、回帰や
識別を行うことは k(x,y)において、 {x,y} のペアの観測デー
タ（＝教師データ）が膨大だと、正規方程式に現れた XTX

(XTXがちょうどk(xn,xm)を（n,m)成分とする行列）
 の逆行列の計算が計算量的に困難！
 すべての観測データを使うと、重要な境界線が観測データの
集中的に集まっている部分に強い影響を受けてしまう。
 限定された観測データを使って効率よく計算できないものだ
ろうか。
 正例データと負例データのうち、両者の境界にあるもの（これ
をSupport Vectorという）だけを使えば、つまりスパースな
データによるカーネルならずいぶん楽になる。
  Support Vector Machine
KKT条件
minimize f (x)
subject t ogi (x)  0
i  1,..,m 
は
m
L(x,  )  f (x)   i gi (x)
Lagrangian
i 1
を最適化する以下の条件で得られる
m
f (x)   igi (x)  0
( KKT  1)
g i ( x)  0
( KKT  2)
i  0
i gi (x)  0
( KKT  3)
i 1
( KKT  4)
これを KKT条件と呼ぶ。なお i  0なら gi (x)  0なので、
このような giを有効な制約と呼ぶ。
m
f (x)   i gi (x)  0　の解釈
i 1
g2(x)=0
 f (x)
2g2 (x)　1g1(x)　gi(x)は許容領
域から離れる
ほど大きくなる
f(x)は許容領
域の中に入る
ほど大きくなる
許容領域の内部でf(x)が大き
くなるということは、その外側
へ向う有効なgi(x)たちが作る
凸錐の逆方向にf(x)の勾配が
向いている
f (x)
許容領域
g1(x)=0
gi ( x )が許容領域から離れるほど大きいなら
勾配gi ( x )
m
  g (x)  f (x)
i 1
i
i
なので、許容領域に入り込むほど大きいので
f ( x )は許容領域の端で最小
なお、この問題における KKT条件は以下のようになる。
1  yn y ( x n )  0
 (KKT - 2)
an  0
 (KKT - 3)
an (1  yn y (x n ))  0  (KKT - 4)
m
L(x,  )  f (x)   i gi (x)
i 1
だったが、ここでの定
g i ( x)  0
式化では、
N
1
2
L(w, w0 , a)  || w ||   an 1  tn  w, x n  w0 
2
n 1
よって、全てのデータ
は、 an  0 か yn y (x n )  1となる。
an  0の点は y (x)  ( SVM 100)に寄与しない。
寄与するのは yn y (x n )  1の点だけ。
この点たちが　support vector である。
w0の求め方
support vector　Sに含まれるデータ nにおいては　ym y ( x m )  1
 N

よって、 ym   an yn x m , x n  w0   1
 n 1

両辺に ymを掛け、 ym 2  1に注意すると、
w0は以下の式で与えられる。
なお、１個の mだけではなく、  しているのは解の安定性のため
mS
w0 
1


  y m   an y n x m , x n 
| S | mS 
nS

双対化の御利益：
教師データアクセスの観点から
主問題と双対問題は最適化するパラメタ－数
が違う。
主問題パラメタ－数 >>双対問題パラメタ－数な
ら双対問題を解くほうが楽 教科書的
SVMの場合：
主問題のパラメタ－は重みベクトル:w
双対問題にパラメタ－は個別データ:xi
必ずしも教科書的なお得感ではない。
双対化の御利益
SVMの場合：
主問題のパラメタ－は重みベクトル:w
下の定式化なので、全教師データ{yn,xn}が同時
に必要
1
arg min || w ||2
2
w , w0
subject to
高次元ベクトル
yn ( w, x n  w0 )  1
n  1,, N
 ( SVM 30)
データ量が大きくメモリにロード仕切れない場
合に困ったことになる。
データ量は最近、増加傾向
双対化の御利益
 必ずしも教科書的なお得感ではない。
 一方、双対問題では入力データxiyiのと最適化するaiが対応
する形で最適化式に現れるので、どのデータを学習で使うか
制御しやすい。（下の式参照）
 例えば、 ai(i≠j)を固定して、aｊを最適化する操作をjを動かして繰り返
すなど。そのときには k x i , x j  j  1,..., N だけしか使わない。
スカラー
N
1 N N

~
max L (a)  max  an   an am yn ym x n , x m 
2 n1 m1
 n1

subject to
an  0
n  1,.., N
 ( SVM 80)
N
a y
n 1
n n
0
 ( SVM 70)
 ( SVM 90) where k (x n , x m )  x n , x m とも書く
双対化の御利益
入力データ、あるいはカーネル行列
全体がメモリに乗り切らないビッグデ
ータを扱うために、入力（すなわちカ
ーネルk(xn, xm)の一部を取捨選択し
てメモリにロードして使う方法が、こ
N
の双対化で可能になっている。
ビッグデータ時代における御利益
 cf. 台湾大学のLIBSVM （SVMの有名な実
装）
 全データからどのようにメモリにロードする部
分を切り出すかが重要な研究課題
M
k(xn, xm)
この部分だけ
使って最適化：
次に使う部分
ロードし直して最
適化：繰り返す
SVMの定式化
境界面で完全に分離できない場合
y=ー1
y=0
無理やり分離する複雑な
境界面（over fitting)
ξ=1
負例側
y=＋1
ξ>1
ξ＜1
正例側
少々は間違った側に入り
込んでもよいが、ゆるい
境界面の内側には入るよ
うに調整soft margin
ξ=0
スラック変数ξ≥0を導入
正しいsoft marginの境界面の上ないし内側の点ではξ＝0
 その他の点xnでは ξn＝|yn-y(xn)|
中央の識別境界面 y(xn)=0 では、 ξn＝1
間違って識別された点はξn>1
まとめると線形分離できない場合の制約条件のξによる緩和：
1  yn y ( x n )  1  yn y ( x n )  0  1  yn y ( x n )   n
 1  yn y (x n )   n  0 where  n  0
...( SF10)
ξn>1 が許容されるが、できるだけ小さく押さえたい！
最適化は以下のように形式化される。ただし、Cはスラック変
数ξのペナルティとmargin wの按配を制御するパラメター
 N

1
2
minmizeC n  || w || 
2
 n 1


where C  0
...( SF20)
if 1  y  y (x)  0
0
Loss (1  y  y (x))  
 if 1  y  y (x)    0
この関数を用いると次の
関数の最小化問題となる。
 N
1
 N
1
2
2
min C  Loss n (1  yn  y (x n ))  || w ||   min C   n  || w || 
2
2
 n1

 n1

Loss n (1  yn  y ( x n ))
1
|| w ||2
2
n
0
1
yn  y ( x n )
この最適化問題を解くためのLagrangianは以下のようになる。
最後の項はξ≧0 を表す項。
N
N
N
1
2
L(w, w0 , a)  || w || C   n   an 1  yn y (x n )   n    n n
2
n 1
n 1
n 1
where an  0
n  0
ＫＫＴ条件は以下の通り。
an  0
1  yn y ( x n )   n  0
an 1  yn y (x n )   n   0
n  0
n  0
n n  0
where n  1,..., N
y (x n )  w, x n  w0
...( SF 30)
ｗ、ｂ、ξを最適化するためにLagrangianを各々で微分すると右下
の結果が得られる。
N
L
 0  w   an y n x n
右をLagrangianに代入す
w
n 1
N

L
ると下の双対問題が得られ
 0   an y n  0
w0
n 1
線形制約凸２次計画問題
L
 0  an  C  n
となる。
 n
N
1 N N
~
L (a)   an   an am yn ym x n , x m
2 n1 m1
n 1
k x n , x m   x n , x m
制約条件は
n  0
以上をまとめると制約
0  an  C
N
a y
n 1
n n
0
an  0
 an  C
条件は全体で以下のようになる
ＳＶＭ実装上のアルゴリズムの
工夫
さて、いよいよ ai を求める段階になった。
ＳＶＭは「線形制約を持つ凸2次計画問題」な
ので、標準的な実装方法が使える。
ただし、次元が高い場合には、カーネルの行
列をメモリに乗せるだけで大変。
独自の工夫がなされているので、ポイントを
紹介
最適解の探索は、素朴なgradient ascent法
でも解けるが、効率は良くない。
ワーキング集合法
 教師データＳを分割して部分的に解くことを繰り返す。
教師データＳに対して
ai0
Sの適当な部分集合Ｓ’を選ぶ
repeat
S’に対する最適化問題を解く
ＫＫＴ条件を満たさないデータから新たなS’を選択
until 停止条件を満たす
return {ai}
分解アルゴリズム
変数{ai}の集合全体ではなく、ある大きさの部
分集合（ワーキング集合）のみを更新する。
この更新の後、ワーキング集合に新たな点を
加え、他の点は捨てる。
上記の{ai}の選択における極端な方法として、
2個のaiだけを使って更新する方法を
逐次最小最適化アルゴリズム
(Sequential Minimal Optimization
algorithm:SMO algorithm)と言う。
N
1 N N
~
L (a)   an   an am yn ym x n , x m
2 n1 m1
n 1
 なぜ2点か？
 復習：右の
k x n , x m   x n , x m
ような最適化制約条件は n  0 an  0  an  C
だった。
以上をまとめると制約条件は全体で次式
0  an  C
N
a y
n 1
n n
0
( SMO  1)
( SMO  2)
 （ＳＭＯ－２）より、最適化の各ステップで更新され
るaiの個数の最小値は２。なぜなら、1個のaiを更
新したときは、（ＳＭＯ－２）を満たすために、最低
でもう1個のaiを調整のために更新する必要がある
から。
Ｓ’の2点を最適化する更新式
S '＝更新の対象となる 2点  x1 , x 2 とする。
 y a k x , x    y a K
N
N
j 1
a2
new
j
j
 a2
i
old
j

j 1
j
j
i, j
 f xi 
y2  f (x1 )  y1    f (x 2 )  y2 
K11  K 22  2 K12
a1new  a1old  y1 y2 (a2old  a2new )
( SMO9)
( SMO8)
2点の更新式の導出
 対象とする2点をa1 、 a2とする。
 動かすのが2点をa1 、 a2だけなので次式が成立
a1new y1  a2new y2  a1old y1  a2old y2  定数
( SMO  3)
ただし　yi  1か  1(i  1,2)
 まず、 a2をa2oldからa2newに変えることにする。
 a2の取る範囲の制約 0≤a2≤Cから当然 0≤a2new≤C
 ただし、(SMO-3)から次の制約が加わる。
y1  y2の場合
( SMO  3)より
a2new  a1old  a2old  a1new
a2newは最大になっても  a1newが最大値 0だから、
a2new  a1old  a2old
は最小になっても  a1newが最小値  Cだから、
a2new  a1old  a2old  C
よって、
U  max(0, a1old  a2old  C ),
U  a2new  V
V  min(C , a1old  a2old )
とおくと
( SMO  4)
y1   y2の場合
( SMO  3)より
a2new  a2old  a1old  a1new
a2newは最大になっても  a1newが最大値 Cだから、
は最小になっても  a1newが最小値 0だから、
a2new  C  a1old  a2old
a2new  a2old  a1old
よって、
U  max(0, C  a1old  a2old ),
U  a2new  V
V  min(C , a2old  a1old )
( SMO  5)
とおくと
a2newの更新式の導出
N
1 N N

~
max L (a)  max  an   an am yn ym k (x n , x m )  ( SVM 70)
2 n1 m1
 n1

を、 a1 , a2に関連する部分だけに注目して最適化することにする。
vi   y j a j k xi , x j   f xi    y j a j k xi , x j 
N
2
j 3
j 1
for i  1,2 と定義する。
すると ( SVM 70)の a1 , a2に関連する部分 W (a1 , a2 )は次のように書ける。
ただし、 K ij  k xi , x j と略記する。
1
1
K11a12  K 22 a22  y1 y2 a1a2 K12  y1a1v1  y2 a2v2  定数
2
2
ここで a1new y1  a2new y2  a1old y1  a2old y2  a1 y1  a2 y2の両辺に y1を掛け、
W (a1 , a2 )  a1  a2 
y12  1に注意し、 s  y1 y2とおくと上の式は　a1new  sa2new  a1  sa2  
1
1
2
K11   sa2   K 22 a22
2
2
 s   sa2 a2 K12  y1   sa2 v1  y2 a2v2  定数
W (a2 )    sa2  a2 
( SMO6)
W (a2 )の最大化のために a2で微分して  0とおく。
W (a2 )
0
a2
 1  s  sK11   sa2   K 22 a2  K12 a2  sK12   sa2   y2v1  y2v2  0
s 2  1　sy1  y1 y2 y1  y1 y2  y2に注意。
2
new
またこの式の a2が更新された a2 であるから

a2
new
( K11  K 22  2 K12 )  1  s  s K11  K12   y2 (v1  v2 )
 y2  y2  y1  y1 K11  K12   v1  v2 
2
ここで
( SMO7)
vi  f (xi )   y j a j K ij に入っている a1 , a2は古い値なので、
j 1
上記 ( SMO7)が更新式となる。
( SMO7)の両辺に y2を掛け、もう少し書き
a2
new
直して整理してみよう
。
y2 ( K11  K 22  2 K12 )
2
2
j 1
j 1
 y2  y1  y1 K11  K12   f (x1 )   y j a j K1 j  f (x 2 )   y j a j K 2 j
  a1  sa2 および　y1  y1a1  sy1a2  y1a1  y2 a2に注意し書き直すと
 y2  y1  f (x1 )  f (x 2 )   y1a1  y2 a2 K11  K12   y1a1K11  y2 a2 K12  y1a1K 21  y2 a2 K 22
 y2  y1  f (x1 )  f (x 2 )  y2 a2 K11  K 22  2 K12 
 K12  K 21
 a2 の更新式は、両辺に y2を掛け、K11  K 22  2 K12 で割れば、 a2  a2 として
new
old
a2
new
 a2
この結果の
old

y2  f (x1 )  y1    f (x 2 )  y2 
K11  K 22  2 K12
( SMO8)
new
a2 の値に対して ( SMO 4)( SMO5)
の条件で制約した
new
ものを a2 の更新値とする。
a1newは a1new y1  a2new y2  a1old y1  a2old y2の両辺に y1を掛け、今更新した a2 によって
new
a1new  a1old  y1 y2 (a2old  a2new )
( SMO9)
SVMによる回帰
 SVMは本来、2クラス分類器であり、識別モデルで
ある。
 しかし、回帰すなわち生成モデルにも使える。
 線形回帰では次の式を最小化した。
N
2
2




y

y
x


||
w
||
 n
n
n 1
 この考え方を拡張する。
0

E ( y (x)  y )  
| y ( x)  y | 
if | y ( x)  y | 
otherwise
下
図参照
この関数を用いると回帰は、次の
関数の最小化問題となる。
 N
1

min C  E ( y (x n )  yn )  || w ||2 
2
 n1

E  y x   y 
y x   y  
y  y x   
赤、青の2個のヒン
ジ損失の組み合わ
せであることに注意
-ε
0
+ε
y x   y
y+ε
ξ＞０
yn  y ( x n )  
y
y-ε
ˆ  0
y (x n )  yn  
ここで、上図の赤い線の上で正となるスラック変数 と、
青い線の下で正となるスラック変数 ˆを導入する。
すなわち
y ( x n )    yn  y ( x n )  　で０、その外側で
yn  y ( x n )    n
y ( x )  y    ˆ
n
n
n
 ( SVM 100)
 ( SVM 101)
 0という条件は下記。
こうすると最適化問題

N
は

1
ˆ
minˆ C   n   n  || w ||2
w , n , n
2
n 1
subject to
yn  y ( x n )     n
y (x )  y    ˆ
n
n
n
 ( SVM 100)
 ( SVM 101)
n  0
 ( SVM 102)
ˆn  0
 ( SVM 103)
Lagrangianは
N
L  C
n 1
N



N
1
2
 n  ˆn  || w ||  n n  ˆ nˆn
2
n 1
N



  an  yn     n  y x n    aˆn  yn    ˆn  y x n 
n 1
n 1
 ( SVM 110)
N



N
1
2
L  C   n  ˆn  || w ||   n n  ˆ nˆn
2
n 1
n 1
N


N
  an    n  y x n   yn    aˆn   ˆn  y x n   yn
n 1
n 1
y ( x )  w, x  w0
N


 ( SVM 110)
を代入すると


N
1
L  C   n  ˆn  || w ||2   n n  ˆ nˆn
2
n 1
n 1


  an  yn     n  w, x n  w0    aˆn  yn    ˆn  w, x n  w0
N
N
n 1
n 1
その上で w, w0 ,  n , ˆnで微分

Lの最小化のために微分
L
0
w
L
0
w0
L
0
n
N
 w   an  aˆn  x n
n 1

N
 an  aˆn   0
n 1
L
 0  aˆn  ˆ n  C
ˆn
~
この結果を Lに代入し最大化すべき L を求めると
 an   n  C
1 N N
~
L (a,aˆ )     an  aˆn am  aˆm  x n , x m
2 n 1 m 1
N
N
n 1
n 1
   an  aˆn    an  aˆn  yn
 ( SVM 120)
k ( x n , x m )  x n , x m とも書く
~
この L を最適化する an , aˆnを求める問題に帰着した。
この式の導出は次々ページ以降に記述
上の導出過程から次の制約が得られる。
0  an  C
0  aˆn  C
また、回帰モデルは以下のようになる。
N
y ( x )   an  aˆn  x, x n  w0
n 1
 ( SVM 120)
an  0, aˆn  0のときは
( SVM 110）より
N
w0  yn    w, x n w   an  aˆn x nを代入し　n 1
N
 yn     am  aˆm  x n , x m
m 1
（SVM120）の導出
KKT条件は以下のようになり、導入された変数と
an  yn     n  y x n   0
( a  1)
aˆn  yn    ˆn  y x n   0
( a  2)
   (C  a )  0
ˆ ˆ  (C  aˆ )ˆ  0

制約条件を消せる。
ε＋ξ>0, ε＋ξ^>0

n n
n

n
n n
n
n
not ( yn     n  y x n )  0かつ(  yn    ˆn  y x n )  0
N



N
1
2
L  C   n  ˆn  || w ||   n n  ˆ nˆn
2
n 1
n 1

 an aˆn  0


  an  yn     n  w, xn  w0    aˆn  yn    ˆn  w, xn  w0
N
N
n 1
n 1
n  C  an
N

ˆ n  C  aˆn

N


L
n

L
0
ˆ

n
  (C  an ) n  (C  aˆn )ˆn   (C  an ) n  (C  aˆn )ˆn
n 1
n 1

N
N
1
2
 || w ||   an  yn    w, xn  w0    aˆn  yn    w, xn  w0 
2
n 1
n 1

N


N

  (C  an ) n  (C  aˆn )ˆn   (C  an ) n  (C  aˆn )ˆn
n 1
n 1

N
N
1
 || w ||2   an  yn    w, x n  w0    aˆn  yn    w, x n  w0 
2
n 1
n 1
N
w   an  aˆn x n と
n 1
L
 0
w0
N
 a
n 1
n
 aˆn   0
により
N
N
1 N N
   an  aˆn am  aˆm  x n , x m    an  aˆn    an  aˆn  yn
2 n 1 m 1
n 1
n 1
N
N
1 N N
   an  aˆn am  aˆm  x n , x m    an  aˆn    an  aˆn  yn
2 n 1 m 1
n 1
n 1
カーネル
( Mは教師データの次元数 , Nは教師データ数 )

Φ   x1  ,...,  x N 

T
 1 x1   M x1  


 

 
  x    x 
M
N 
 1 N
 1 x1   M x1   1 x1   1 x N  



K  ΦΦT   

  

 
  x    x   x    x 
M
N  M
1
M
N 
 1 N
 M
  i x1 i x1  
 i 1



M

  i x N i x1  
 i 1
M
計画行列
Design Matrix
カーネル関数:k(xi,yj)を要
素とするグラム行列

i x1 i x N    k x , x   k x , x  

1
1
1
N
i 1
 







M
  k x , x   k x , x 
i x N i x N   N 1
N
N 

i 1

M
i x k   x kの第 i成分 : xkiなら　k x k , x l    xki xli  x k , x l : 内積
i 1
 正定値カーネル：対称行列k(xi,xj)が半正定値：グラム行列:
既存のカーネル関数から別のカーネル関数を構成する方法
k ( x, y )  ck1 ( x, y )
 ( k  1)
k ( x, y )  f ( x )k1 ( x, y ) f ( y )
k ( x, y )  q( k1 ( x, y ))
fは任意の関数
qは係数正の多項式
k ( x, y )  exp(k1 ( x, y ))
 ( k  5)
k ( x, y )  k1 ( x, y )k2 ( x, y )
 ( k  6)
k ( x, y )  xT Ay
x  (x a , x b )
 ( k  3)
 ( k  4)
k ( x, y )  k1 ( x, y )  k2 ( x, y )
k ( x, y )  k1 ( ( x ),  ( y ))
 ( k  2)
 ( k  7)
Aは対称半正定値行列
y  (ya , yb )
 ( k  8)
( x, yとも同じ次元に分割）
k ( x, y )  k1 ( x a , y a )  k2 ( x b , y b )
 ( k  9)
k ( x, y )  k1 ( x a , y a )k2 ( x b , y b )
 ( k  10)
のとき
カーネルの例
 問題の非線形性あるいは高次性を非線形な
カーネルで表すことになる
k (x, y )  xT y
 線形カーネル
k (x, y )  (xT y  1) M M  1,2,...
 多項式カーネル
 Gaussianカーネル:RBF
 || x  y ||2 
k (x, y )  exp 

2
2


 以下の分解によりGaussianカーネルがカーネル関数
だといえる
by (k-1)(k-2)(k-4)
|| x  y ||2  xT x  y T y  2xT y 
xT x
yT y
xT y
k ( x, y )  exp(  2 ) exp(  2 ) exp( 2 )
2
2

表現定理
 SVMなどの最適化は下のような形
N
1
2
min || w ||   an 1  tn y (x n ) where
2
n 1
y (x n )  w, x n  w0
 min   f   losstn ,xn  f 
f H
教師データに対す
る損失
正の単調増加関数
である正則化項
 このとき上の最適化問題の解fは下記の形
N
f x    i k x, x n 
i 1
 よって、一般的なカーネルであっても(SVM100)の
形の解を想定できる。
よもやま話：スイスロール－１
多様体に写像
してから識別
境界を切る
よもやま話：スイスロール－２
同じ色のデータ
のうち近接するも
のを繋いで、多
様体を近似的に
求め
色が違うデータを
繋ぐところで切る
この多様体による
制約を考慮して分
類する最適化問題
の定式化は？
捕捉：線形回帰、識別からカーネル関数へ
y ( w )  wT  (x)
という一般化した線形回帰式に対して
 T
1 N
T
J ( w )   w  ( x n )  tn   w w
2
2 n 1
2
ただし
 1 ( x n ) 


 (x n )    
  (x ) 
 M n 
tnは w T  ( x n )がとるべき値。
( Mは教師データの次元数
, Nは教師データ数 )
という正規化項つきの２乗誤差を考えるとき
、
 ( x )についてもう少し組織的に考えてみよう。
カーネル関数と呼ばれる k  x ,  y  で回帰や識別を考え直す
ことにより、より効率の良い方法が見えてくる。
双対表現
まず、L2-正規化項つきのL2-損失（＝２乗誤差関数）を考える。
J ( w) 
1
2
2



w

(
x
)

t

w w

2
N
T
tnはwT  (x n )がとるべき値。
T
n
n
 0
n 1
 J w   0 からJ(w)を最小化するｗを求め、その右辺をaとΦで表す。Nは教師データ数
w
w

w  (x


1
N
n 1
a  ( a1 ,, a N )T
)  tn   ( x n )   an ( x n )  ΦT a
N
T
n
n 1
an  

w  (x

1
T
n
)  tn 
以上の表記を用い、J(w)をJ(a)として書き直すと
1 T
1 T  T
T
T
T
T
J (a)  a Φ Φ Φ Φ a  a Φ Φ t  t t  a Φ ΦT a
2
2
2
t  (t1 ,  , t N )T
wがφ(xn)の
anを重みとす
る線形結合
で書けること
に注目
ここで下記の要素を持つN  Nの Gram行列　K  Φ ΦT を定義する。
K nm   (x n )T  (x m )  k (x n , x m )
: カーネル関数という。
カーネル関数を用いると、J(a)、a、y(w)は次のように書ける
1 T
1 T  T
T
J (a)  a KKa  a Kt  t t  a Ka
2
2
2
J (a)
1
ここで
 0 より
a  K  Ι N  t
a
y ( x )  w T  ( x )  aTΦ ( x )
M個の基底関数φiがあったとすると、カーネル関数は、内積の
形で以下のように書ける。
k (x, y )   (x)T  ( y ) 
M

i 1
i (x)i ( y )
 (x)  ( 1 (x),M (x))T

Download Report