第 7 章 疎な解を持つカーネルマシン
7.1 最大マージン分類器
6.4.7 ニューラルネットワークとの関係
省略
い、そうでない場合無効な制約という。今の問題設定では一般に、tn正負両側に等号を満たす点が 現れるようなパラメータの選び方が存在する。
結局、マージンの最大化は有効な制約のもとで、||w||−1を最大化、すなわち||w||2を最小化する ことに他ならない。これは付録Eの不等式の元での最小化より、未定乗数anを用い、
L(w,b,a)= 1 2||w||2−
∑N n=1
an{tn(wTϕ(xn)+b)−1} (7.7) の停留点を
an ≥ 0 tny(xn)−1 ≥ 0
an{tny(xn)−1} = 0 (7.8)
の条件下で求める問題に帰着する。wとbについての微分から
w =
∑N n=1
antnϕ(xn)
0 =
∑N n=1
antn (7.9)
を得る。これより、w,bを消去すると
L(a)˜ =
∑N n=1
an−1 2
∑N n=1
∑N m=1
anamtntmk(xn,xm) (7.10) を得る。ここでk(x,x′)=ϕ(x)Tϕ(x′)である。本文にはこれをaに対して最大化すると書いてあ るが、最小化ではないだろうか。仮にa1,a2が共に停留点になっていて、L(a1)<L(a2)であるな ら、解としてa1を採用した方が対応する||w||2の値は小さくなるはず。また、anを用いてy(x)は
y(x)=
∑N n=1
antnk(x,xn)+b (7.11)
と書くことができる。既に条件に挙げられているが、全てのデータ点について、an =0あるいは tny(xn)=1が成り立つのであって、後者が成り立つデータ点をサポートベクトルと呼ぶ。aを求め たら、上の式よりサポートベクトルxnにtnをかけることで
tn
∑
m∈S
amtmk(xn,xm)+b
=1 (7.12)
となる。ここでSはサポートベクトルの集合を表す。さらにtnを両辺にかけて、(計算の誤差を少 なくするために)全てのサポートベクトルに関する平均を取ることで
b= 1 NS
tn−∑
m∈S
amtmk(xn,xm)
(7.13)
を得る。
条件が複数あるラグランジュ未定乗数法(複数に限らないかもしれない)は、本文付録のように 幾何学的に考えるよりも、g1(x)=g2(x)=0を満たしていて、極大(小)であるなら微小なベクト ルϵに関して
∇g1(x)ϵ=0 and∇g2(x)ϵ=0⇒ ∇f (x)ϵ=0 (7.14) がなりたち、よって
∇f (x)=λ1∇g1(x)+λ2∇g2(x) (7.15) が成り立つと考えた方がわかりやすいのではないだろうか。
7.1.1 重なりのあるクラス分布
次に、訓練データが完全には線形分離できない場合を考える。すなわち、今までは全てのデータ に対して
tny(xn)≥1 (7.16)
とできる関数が存在するとしてきたが、そもそも存在しない場合を考える。その場合は正の変数
(スラック変数)ξn≥0を導入し、
tny(xn)≥1−ξn (7.17)
の条件下で
C
∑N n=1
ξn+1
2||w||2 (7.18)
を最小にすることを考える。ここでCは制御パラメータである。この最小化問題のラグランジュ 関数は
L(w,b, ξ,a, µ)= 1
2||w||2+C
∑N n=1
ξn−
∑N n=1
an{tny(xn)−1+ξn} −
∑N n=1
µnξn
(7.19) となり、条件は
an ≥ 0 tny(xn)−1+ξn ≥ 0 an(tny(xn)−1+ξn) = 0 µn ≥ 0 ξn ≥ 0
µnξn = 0 (7.20)
である。各変数について微分を行うと
∂L
∂w = 0⇒w=
∑N n=1
antnϕ(xn)
∂L
∂b = 0⇒
∑N n=1
antn=0
∂L
∂ξn = 0⇒an=C−µn (7.21)
となり、結果をラグランジュ関数に代入すると双対系のラグランジュ関数
L(a)˜ =
∑N n=1
an−1 2
∑N n=1
∑N m=1
anamtntmk(xn,xm) (7.22) を得る。条件は
0≤an≤C
∑N n=1
antn=0 (7.23)
であり、この条件でラグランジュ関数を最小化(ここも本文に最大化とあるが最小化だと思う。)
する問題に帰着する。
ここでもan>0となる点をサポートベクトルと呼ぶことにする。これらについては
tny(xn)=1−ξn (7.24)
が成り立つ。0<an<Cなるサポートベクトルについてはξn=0となるので、tny(xn)=1すなわち tn
∑
m∈S
amtmk(xn,xm)+b
=1 (7.25)
が成り立つ。よってbは(数値計算の誤差をなくすため)上の式を満たす全ての点での平均を取り
b= 1 NM
∑
n∈M
tn−∑
m∈S
amtmk(xn,xm)
(7.26)
となる。ここでMは0<an<Cを満たす点の集合である。
7.1.2 ロジスティック回帰との関係
省略
7.1.3 多クラス SVM
省略
7.1.4 回帰のための SVM
ここでは解の疎性を保ちながらSVMを回帰問題に適用する方法を考える。単純な問題では誤差 関数
1 2
∑N n=1
{yn−tn}2+λ
2||w||2 (7.27)
を最小化する。疎な解を得るためには
Eϵ(y(x)−t)=
0 |y(x−t|< ϵ
|y(x−t| −ϵ それ以外 (7.28)
を用いた誤差関数
C
∑N n=1
Eϵ(y(xn)−tn)+1
2||w||2 (7.29)
を考えることにする。この誤差関数を実現するために一つのデータ点に対して、二つの非負のス ラック変数
tn≤y(xn)+ϵ+ξn
tn≥y(xn)−ϵ−ξˆn (7.30)
を用い、誤差関数
C
∑N n=1
(ξn+ξˆn)+1
2||w||2 (7.31)
を考える。これはラグランジュ乗数an≥0,ˆan≥0, µn≥0,µˆn≥0を用いて
L = C
∑N n=1
(ξn+ξˆn)+1 2||w||2−
∑N n=1
(µnξn+µˆnξˆn)
−
∑N n=1
an(ϵ+ξn+yn−tn)−
∑N n=1
ˆan(ϵ+ξˆn−yn+tn) (7.32) を最小化することに帰着する。各変数について微分すると
∂L
∂w = 0⇒w=
∑N n=1
(an−ˆan)ϕ(xn)
∂L
∂b = 0⇒
∑N n=1
(an−ˆan)=0
∂L
∂ξn
= 0⇒an+µn=C
∂L
∂ξˆn
= 0⇒ ˆan+µˆn=C (7.33)
となって、ラグランジュ関数を変形すると L(a˜ ,a)ˆ = − 1
2
∑N n=1
∑N m=1
(an−ˆan)(am−ˆam)k(xn,xm)
−
∑N n=1
(an+ˆan)+
∑N n=1
(an−ˆan)tn (7.34)
を得る。anとˆanは不等式条件のラグランジュ乗数であり非負であり、µnとµˆnも同様であるため、
上の式より
0 ≤ an≤C
0 ≤ ˆan≤C (7.35)
が成り立つ。その他の条件もまとめると
an(ϵ+ξn+yn−tn) = 0 ˆan(ϵ+ξˆn−yn+tn) = 0 (C−an)ξn = 0
(C−ˆan) ˆξn = 0 (7.36)
また、0<an <Cが成り立つデータ点についてはξn =0となるため、ϵ+yn−tn =0が成り立ち、
したがって
b = tn−ϵ−wTϕ(xn)
= tn−ϵ−
∑N m=1
(am−ˆam)k(xn,xm) (7.37)
を得る。実際には、こうして得られたbの値を平均すると信頼性が高い値が得られる。
7.1.5 計算論的学習理論
省略