機械学習の入門
評価方法
by 中川裕志（東京大学）
教師あり学習の評価
予測値の決め方
if p1 | x   th then yˆ  1　(正解) otherwise yˆ  （不正解）
1
機械学習の結果の予測器によって
xが正解（１）である確率が閾値θthより大きけ
れば予測値 ‫ݕ‬ො＝＋１小さければ ‫ݕ‬ො＝ー１
となる。
ここで、閾値への予測値の依存性に注意
閾値と正解の関係
閾値
一般的なデータ処理結果の状態
•
処理ｓで結果のデータ集合が得られた。しかし、結果の中には間違
いもあるし、得られなかったデータの中にも正解がありうる。
データ集合全体｛x｝
TN(True Negative)
正解データの集合
‫ݕ‬ො＝１の
データ集合
FP
(False
positive)
TP
(True
Positive)
FN
(False
Negative)
性能評価尺度
 再現率
 適合率あるいは精度
 フォールアウト
 一般性
 Accuracy
or
Rand Index
TP
recall 
TP  FN
precision 
TP
TP  FP
fallout 
TN
TN  FP
generarity 
accuracy 
TP
TP  TN  FP  FN
TP  TN
TP  FP  TN  FN
再現率ｖｓ精度
•
よく使う評価の表現法
１．０
精度
再現率１００％の自明
なシステム？？
０．０
０
０．５
再現率
１．０
再現率ｖｓ精度に関連した尺度
•
•
•
Break even point
再現率と精度が一致する点
11点平均精度再現率＝0.0 , 0.1, 0.2, ….. 0.9, 1.0 の11点における
精度の平均値
F値ただし、ｂは精度が再現率よりどれだけ重視されているかを示すパラ
メタ― ｂ＝１がよく使われる。
(1  b 2 )  P  R
F 
b2  P  R
2 PR
2
F 

1
1
P R

P
R
ＲＯＣとＡＵＣ
ܶܲ
ܶܲ ൅ ‫ܰܨ‬
ROC曲線
ＲＯＣ曲線の下の部分の面積が
ＡＵＣ（Area Under Curve)
‫ܲܨ‬
‫ ܲܨ‬൅ ܶܰ
理想的な場合（表１．２）
：正解
：不正解
θth=a: TPR=1/4
FPR=0
θth=b: TPR=4/4
FPR=0
θth=c: TPR=4/4
FPR=3/4
現実的な場合(表１．３）
：正解
：不正解
θth=a: TPR=1/4
FPR=0
θth=b: TPR=2/4
FPR=2/4
θth=c: TPR=4/4
FPR=3/4
順位つき結果の評価
 単純な識別では結果は全て同等
 生成モデルの場合は、結果が適合性のよい
順番に並ぶ。（表示も適合順）
 この場合の評価法について
Recall , Precision
処理qに適合する結果（以下、正解、という）の数： |Dq |
処理システムの順位つけられた結果: (d1…….dn)
di が処理qへの正解なら ri=1、そうでなければ ri=0
とする。すると、
 第k順位まで拾ったときの
1
ri
Recall(k ) 

| Dq | 1ik
1
Precision(k )   ri
k 1i  k
平均適合率：average precision
1
AveragePrecsion 
rk  precision(k )

| Dq | 1 k  N
ただし、Nは正解が最後に現れた順位
• 例：
順位
AvPrec
1 1
2 

 

2 1
4 
 0 . 75
１
２
３
４
５
６
正解
か
〇
〇
平均逆順位：Mean Reciprocal Rank(MRR)
1
RR 
: n は初めて正解がでた順位
n
もし、正解がひとつも現れなければ　ＭＲＲ＝０
MRR  全質問に対する RR の平均値
順位
• 例
1 1 
MRR     / 2  0.625
1 4 
１
２
３
４
正解か
第1問
〇
第2問
〇
〇
nDCG
 DCG(Discounted Cumulative Gain)
 結果には関連度(relevancy)：Rが与えられている。Rは適
当な範囲の数値
 順位i番目の結果の関連度をRiとする
 p位までの結果に対するCG(Cumulative Gain):
CGp  i 1 Ri
p
 CGpに順位が低いものに関連度Rの高いものが現れた場
合のペナルティを考慮したのがDCGp
p
Ri
DCGp  R1  i 2
log2 i
or more generally

p
i 1
f i Ri  :
f iはiの減少関数
DCGはRiの決め方や関数fiの定義に強く依
存
そこで理想的な場合のDCG（＝ＩＤＣＧ）と実際
の結果に対するDCGの比を使う nDCG
DCGp
nDCGp 
IDCGp
DCG,nDCGの例
結果： R1=4, R2=1, R3=4, R4=2, R5=1
log23=1.58, log24=2, log25=2.32
DCG5=4+1+4/1.58+2/2+1/2.32=8.96
IDCG5=4+4+2/1.58+1/2+1/2.32=10.70
 nDCG5=8.96/10.70=0.83
 もし、結果が関連度Rの大きい順に並んでいれば、
DCG=IDCGだから nDCG=1
 もし、結果が逆順なら（１，１，２，４，４）
DCG5=1+1+2/1.58+4/2+4/2.32=6.98
 IDCG5=6.98/10.70=0.65
学習と評価（教師ありの場合）
 正解データがある場合。
 正解データ全部を教師データとして機械学習。学習結果のシ
ステムをｓ
 ｓを教師データで評価
 ｓを未知のデータで評価
 本当は、未知データでの評価をしたいが、なにしろ未知
 正解データを教師データとテストデータに分割
 教師データで学習し、テストデータを未知データとみなして評価
 正解データが少ない場合：N-fold cross validation(N-交差検定）
 正解データをN等分。N-1個を教師データとして学習し、残りの1個で評価。
これをN種類繰り返す。
 特殊なケースとして、1個だけを除いて学習し、その1個で評価。これを
データ数繰り返す。Leave-one-out法
教師なしの場合
クラスタリングの場合
人手で正解データを作っておき、教師あり学習と
同じような評価。
一応、再現率も計測できる。
正解データが存在しない場合
学習結果をサンプリングして、人手で評価するし
かない。
再現率は評価できない。
クラスタリングの評価：Purity
生成されたクラスタがどれだけ多数派で占めら
れているかを表す尺度
N : データ数, C : 真のクラス集合  C1 ,...CK ,
生成されたクラスタ数  L
ni , j : 生成されたi番目のクラスタにおいて
j番目の真のクラスに属するデータ数
local　purity 
max ni , j 
1
L
n
j 1
global　purity 
i, j
L
K
 n
i 1 j 1
1
max ni , j  

j
N
i 1
L
1
i, j
 maxn 
L
i 1
j
i, j
1
2
3
5
4
6
purity (1)  , purity (1)  , purity (1) 
7
8
10
local purity
global purity purity  5  4  6  15  0.6
7  8  10
25
問題点何もしない場合
全データが同一クラスタ
１クラスタが１データ purity 
purity 
1
N
1
max ni , j 
N i, j
1


max

n

i, j
j
N
i 1
L
L
1 
i 1
N
1
N
クラスタiで捉えたクラ
スｊのデータ数
Inverse Purity
 



 max ni , j L
K
1  j

n
InversePurity 


i
,
j

N i 1 K
j

1

  ni , j

 i 1
１クラスタに１個のデータしかない場合も
Inverse Purityは1より小さい。
そこでPurityとの調和平均であるF値で評価
F値 
2
1
1

Purity InversePurity
再現率
のような
もの
真のクラスjのデータ総数
1
2
5  4  6 15
Purity 

7  8  10 25
InversePurity 

F値 
3
８個、
７個、
1 5
4
6

7
8




 10   0.598

25  8
7
10

2
1
1

0.6 0.598
 0.599
１０個
テストコレクション
 (a) 入力データ集合、(b) 解くべき問題（識別など）、(c)問題において
＜入力データ、推測結果＞対の集合、を組にしたデータベースをテ
ストコレクションと呼び、機械学習システムの性能評価において必須
の資源である
 ある入力データに対応する推定結果の個数が多いような問題（例え
ば、情報検索）では、＜入力データ、推測結果＞の大規模な集合を
作ることは大規模テストコレクションでは困難
 Pooling method:、同一の入力データ集合に対して、多数のシステム
で同じ問題に対して出した上位N 個の結果を全て集める。N の値と
して、100 程度が多い。この結果に対してのみその適合性を人手で
判断し、それを正解の集合とする
機械学習の入門
線形回帰および識別
by 中川裕志（東京大学）
線形モデル
y=w1x+w0
y
データの分布状況
から線形回帰式を求
める
w0
x
線形モデル
入力ベクトル：x から出力：y を得る関数がxの線形関数
（wとxの内積）
K
y  x, w   wi xi
i 0
ただし、x  [1, x1 ,, xK ]T , w  [ w0 , w1 , , , wK ]T
一般に観測データはノイズを含んでいる。つまり
y  x, w  
はノイズでN (0,  2 )と考える。
得られたN個の観測データの組（y,X）に対して最適なwを推
定する。
そこで、yと
Xw
の2乗誤差を最小化するようにwを選ぶ。
2乗誤差の最小化
 y1 
y    
 yN 
 x1T  1 x11
x1K 



X      


T
x  1 x
xNK 
N1
 N  
 w0 
w 
w 1
  
 
wK 
ˆ  arg min (y  Xw)T ( y  Xw)
w の推定値w
w
 (y  Xw)T ( y  Xw)
0
w
を解くとXT Xw  X T y
w  ( XT X) 1 XT y
 正規方程式と呼ばれる基本式
(y  Xw )T
補遺：正規方程式の導出
(y  Xw)  y  w X (y  Xw)  y y  w X y  y Xw  w X Xw
T
T
T
T
T
T
T
T
T
wT XT y y T Xw w T XT Xw
 (y  Xw)T (y  Xw)
 0 (1)



w
w
w
w
T
xT a
wT XT y
aT x
y T Xw
T
 aより
X y
 aより
 y T X  XT y
w
x
w
x
T
wT XT Xw wT XT Xw  wT XT X w
 XT Xw  wT XT X  2 XT Xw


w
w
w
 (1)  2 XT y  Xw   2 XT y  2 XT Xw  0  XT y  XT Xw



 





1
 w  XT X XT y
f ( g x ) g x  f ( g x )
を使えば
rule cf　行列で微分する場合の chain 
x
x
g x 
 (y  Xw )T (y  Xw)  (y..)  (y..)T (y..)  (y..)T  (y..)T (y..)


w
w
 (y..)
w
 (y..)T
  XT (y  Xw)  XT (y  Xw)  2 XT (y  Xw)
正規方程式を解く簡単な例
 1 x1 
X   


1 x N 
1
x
 1

 y1 
w 
正規方程式　X T Xw  X T yは
y  
w   0
 
 w1 
 y N 
 y1 
 1 x1 
 1 

1
1
w
 
  
   0   


  w1   x1  x N   
 xN  
 y N 
1 x N 

 N
N
 x
i

i 1

 N

y
x

i
i 
 w0   
i 1
i 1
    N

N
w
xi2   1   xi yi 


 i 1

i 1
N
X X  
N
w0 


N  xi2    xi 
i 1
 i 1 
N
N
N
N
2
N
N
X T X　w  X T y

  xi 
i 1

N 

 N 2
  xi
 i 1N
 x
i
 
i 1
1
1
T

N
N
N

N
w1 
N
i
i 1
i
i 1
i
i 1
i
i 1


N  xi2    xi 
i 1
 i 1 
N
N
2
i

i
i 1
N

i
i 1
N
i
i 1
i
i
i 1
i 1
 N 
2
N  xi    xi 
i 1
 i 1 
N
N
N  xi yi   xi  yi
i 1
i 1
i 1


N  xi2    xi 
i 1
 i 1 
N
N
2
N
x  y  x x y  y x Nx y  x  y
2
N
2
i
1
 w0 
N
N
N
1
yi  w1  xi

N i 1
i 1
用語：誤差、損失、目的関数
 線形モデルで最小化したかったのは２乗誤差
 真のモデルにおける値(２乗誤差におけるy)と
予測値(２乗誤差におけるXw)の差異を表す関数を
損失関数（単に損失）あるいはLossと呼び、Lで表す
ことが多い。
 上記のような最適化問題において最小化（一般的に
は最適化）したい関数を目的関数と呼ぶ。
 線形モデルの２乗誤差最小化では
２乗誤差＝損失＝目的関数
線形識別
との領域の
境界面を線形関数
として求める
線形識別
x  [ x1 , x2 , , xM ]T
 データ:
 xがいくつかのクラス（あるいはカテゴリー）：Cｋのどれか
に属する。
 例：新聞記事が「政治」「経済」「スポーツ」「芸能」「社会」などのクラ
スのどれかに属する場合。この場合、データ：ｘは例えば、記事に
現れる単語の集合、など。
 データ：xがK個のクラスの各々に属するかどうかの判定
は（－１＝属さない，１＝属する）の２値を要素とするK次
元ベクトル：yi＝（-1,1,-1,..,1)で表される。
 ただし、１つのクラスに属するか属さないかだけを識別すの場合は
2クラス分類という。当然、 yi＝ー1 or yi ＝ 1
 この属するか否かの判断をする式が線形の場合を線形識
別という。
 線形識別の関数
y (x)  x, w  w0
あるいは
 1  ~  w0 
~
~
  とおくなら y (x)  ~
x   , w
x, w
x
w
 一般化線形識別の関数は以下
y (x)  f ( x, w  w0 )
fは非線形でもよい
 ２クラス分類
 クラスC１に属するかC2（＝notC1）に属するかは、次
の通り
 if y(x)≥0 then データ：ｘはC１に属する
otherwiseデータ：ｘはC2に属する
(すなわちC1に属さない）
2値分類の直観的説明
 y={-1,1}、xは2次元とする。（下図を参照）
 {y,x}を教師データとして、2乗誤差の最小化を行っ
て正規方程式を求めると、下図ののようなクラス
を分類する分離平面が得られる。
x2
y=１
境界面
y=-1
x1
線形識別関数の幾何学的解釈
 w0
xd 
|| w ||
xa
識別境界線
xb
xd
y(x)
|| w ||
w
xc
y ( x a )  x a , w  w0  0 ,
y ( x b )  x b , w  w0  0
0  y ( x a )  y ( x b )  ( x a  x b ), w

wは ( x a  x b )すなわち識別境界線と直交。
原点から識別境界線へ
の垂線の交点を
x dとおく。
0  y (x d )  x d , w  w0
x d は w に並行で横ベクトルだ
これを上式に代入して
から、 x d , w  | x d ||  || w ||
整理すると
x d , w  w 0  || x d ||  || w ||  w 0  0

x
| x d | 
w0
|| w ||
線形識別関数の幾何学的解釈
xa
識別境界線
xb
x
xd
r
w
y(x)
|| w ||
xc
 w0
|| w ||
x  xc  r
w
|| w ||
両辺とwの内積をとり、w0を足すと
|| w ||2
 y (x c )  r
y(x)  x, w  w0  x c , w  w0  r
|| w ||
|| w ||
y ( x)
y(xc )  0 だから r 
|| w ||
w, w
wの計算方法:2クラス分類の場合
~ で書けるとする
クラスC1 , C2の境界が y ( x)  ~
x, w
.
~
y
(x
) が正ならクラス
 すると新規のデータ：xは
C1に,負ならC２属する
N個の教師データ~
xn , yn (n  1, N )があったとき
.
ただしクラス１ならyn  1, 0ならyn  1
T
~
x1 

~ 
X  
 ~ T 
 xN 
 y1 
 
Y  
y 
 N

~~ 
XW  


~
~
x1 , w

~
~
xN , w





 すると、観測データ（教師データ）において個々のクラスに
分類されたか否かの観点からの２乗誤差は次式となる


T ~ ~
~
~~
E ( W )  XW  Y XW  Y

 もう少し詳しく書くと



T ~ ~
~~
XW  Y XW  Y 
~
 ~
x1 , w
~
 ~
x1 , w


~
~
 y1  x N , w  y N 


2
~ y
 y    ~
x ,w
1
N
N
~
~ y 
x1 , w
1



~
~ y 
xN , w
N 

2


T ~ ~
~
~~
E ( W )  XW  Y XW  Y

~
~
 これを最小化する W は W で微分して０とおけ
ば、線形回帰のときと同様の計算により求まる。
 微分は次式：



AT A
AT
~~
~ ~~
2
A  A  XW  Y   2 XT XW  Y
W
W
 
~
E W ~ T ~ ~
~  X XW  Y  0
W
~
~ T ~ 1 ~ T

W  (X X) X Y



 新規のデータxnewに対する予測を行うy(xnew)も求ま
る。
~
~ T ~ 1 ~ T
W  ( X X) X Y
xnew ) 
 y1 (~
~ ~ ~ T ~ 1 ~ T


~
~

y ( xnew )  
  xnew W  xnew ( X X) X Y
 yK (~
xnew )
y(xnew)が大きいほどクラス C1 に属する可能性が高い。
機械学習の入門
サポートベクターマシン
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
n 1
N
0   an yn
n 1
 ( SVM 50)
 ( SVM 60)
(SVM50)(SVM60)を（SVM40)に代入して、wとw0を消すと、
次のように双対問題としての定式化が得られる
SVMの双対問題ー境界面で完全に分離できる場合
1 N N
N

~
max L (a)  max  an   an am yn ym k (x n , x m )
2 n1 m1
 n1

 ( SVM 80)
subject to
an  0
n  1,.., N
N
a y
n 1
n
n
0
 ( SVM 90)
where k (x n , x m )  x n , x m
 ( SVM 70)
これがカーネル関数（データ
xn,xmの対だけによる）
後で説明する
また、新規のデータに対する予測は次式のy (x)で行う
N
y (x)   an yn k (x, x n )  w0
n 1

（SVM100)
上記(SVM70,80,90)を解くアルゴリズムは後に説明する。また、（ＳＶＭ１００）で良い
理由はカーネルの関する記述で述べる（表現定理）
双対化を最適化の観点から見なおそう
最適化問題 P
min f  x 
subject to gi  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 to   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   ( SVM 40 )
2
n 1
w , w0に関して微分すると以下の条件が出る。
N
w   an yn x n
n 1
 ( SVM 50)
N
0   an yn
n 1
 ( SVM 60)
上記の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 , xm )  xn , x m
；カーネル関数を利用して、回帰や
識別を行うことは k(x,y)において、 {x,y} のペアの観測デー
タ（＝教師データ）が膨大だと、正規方程式に現れた XTX

(XTXがちょうどk(xn,xm)を（n,m)成分とする行列）
 の逆行列の計算が計算量的に困難！
 すべての観測データを使うと、重要な境界線が観測データの
集中的に集まっている部分に強い影響を受けてしまう。
 限定された観測データを使って効率よく計算できないものだ
ろうか。
 正例データと負例データのうち、両者の境界にあるもの（これ
をSupport Vectorという）だけを使えば、つまりスパースな
データによるカーネルならずいぶん楽になる。
  Support Vector Machine
KKT条件
minimize f (x)
subject to gi (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, xn  w0 
2
n 1
よって、全てのデータは、 an  0 か yn y ( x n )  1となる。
an  0の点は y (x)  ( SVM 100)に寄与しない。
寄与するのは yn y ( x n )  1の点だけ。
この点たちが　support ve ctor である。
w0の求め方
support vector　Sに含まれるデータnにおいては　ym y (x m )  1
 N

よって、ym   an yn x m , xn  w0   1
 n1

2
両辺にymを掛け、ym  1に注意すると、
w0は以下の式で与えられる。
1


x
,
x

w0 
y
a
y



m
n n
m
n 
| S | mS 
nS

SVMの定式化
境界面で完全に分離できない場合
y=ー1
y=0
ξ=1
負例側
無理やり分離する複雑な
境界面（over fitting)
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(xn ) 1 yn y(xn )  0  1 yn y(xn )  n
1 yn y(xn ) n  0 where n  0
...(SF10)
ξn>1 が許容されるが、できるだけ小さく押さえたい！
最適化は以下のように形式化される。ただし、Cはスラック変
数ξのペナルティとmargin wの按配を制御するパラメター
 N

1
2
minmize C  n  || w || 
2
 n 1


where C  0
...( SF 20)
if 1  y  y (x)  0
0
Loss (1  y  y (x))  
 if 1  y  y (x)    0
この関数を用いると次の
関数の最小化問題となる。
1
1
 N
 N
2
2
min C  Loss n (1  yn  y (xn ))  || w ||   min C   n  || w || 
2
2
 n1

 n1

Loss
n
(1  y n  y ( x n ))
1
|| w ||2
2
n
0
1
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, xn  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  a n  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
an  0
 an  C
以上をまとめると制約条件は全体で以下のようになる
0  an  C
N
a y
n 1
n n
0
ＳＶＭ実装上のアルゴリズムの
工夫
さて、いよいよ 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だから、 a2new  C  a1old  a2old
は最小になっても  a1newが最小値 0だから、 a2new  a2old  a1old
よって、
U  max( 0, C  a1old  a2old ),
U  a2new  V
V  min( C , a2old  a1old )
( SMO  5)
とおくと
a2newの更新式の導出
1 N 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
j 3
2
for i  1,2
と定義する。
j 1
すると( SVM 70)のa1 , a2に関連する部分 W (a1 , a2 )は次のように書ける。
ただし、K ij  k xi , x j と略記する。
1
1
2
W (a1 , a2 )  a1  a2  K11a1  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を掛け、
y12  1に注意し、s  y1 y2とおくと上の式は　a1new  sa2new  a1  sa2  
1
1
2
W (a2 )    sa2  a2  K11   sa2   K 22 a22
2
2
 s  sa2 a2 K12  y1   sa2 v1  y2 a2v2  定数
( SMO6)
W ( a2 )の最大化のためにa2で微分して  0とおく。
W (a2 )
0
a2
 1  s  sK11   sa2   K 22 a2  K12 a2  sK12   sa2   y2v1  y2v2  0
2
s 2  1　sy1  y1 y2 y1  y1 y2  y2に注意。
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  y2a2に注意し書き直すと
 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 )  y2a2 K11  K 22  2 K12 
K12  K 21
K11  K 22  2K12 で割れば、a2  a2 として
 a2 の更新式は、両辺にy2を掛け、
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 の更新値とする。
new
a1newはa1new y1  a2new y2  a1old y1  a2old y2の両辺にy1を掛け、今更新したa2 によって
a1new  a1old  y1 y2 (a2old  a2new )
( SMO9)

Download Report