大規模データの線形識別 - Top Page | 中川研究室

大規模データの線形識別
Recent Advances of Large-scale Linear
Classification
Guo-Xun Yuan, Chia-Hua Ho, and Chih-Jen Lin
を中心にまとめた
データの性質
 入力データの次元と入力データ数
入力データの各次元を素性とも言う
次元の高い場合はsparse（有効な素性が少ない）
次元が低い場合はdense（多数の素性が有効）
入力データの次元小
103以下
入力データの次元大
104以上
入力データ数小
Mega
新規理論をとりあえず試す正解タグ付きテキストコーパス
toy data
など
（場合によっては画像も）
入力データ数大
Giga-Tera
計測される数値データ
（センサーデータ、市場
データ、など）
正解タグなしの生テキストコー
パス
ストリーム
時系列到着
センサーデータ
Twitter、ソーシャルメディアなど
データの性質
 次元が大きい（１０の4乗以上）の場合は線形識別も
非線形識別の精度に大きな差はない。
 次元が低いと非線形識別のほうが精度がかなりよ
い。非線形化すなわち高次元化による特徴抽出能
力の改善のため
 教師データ（タグ付けデータ）と生データ
 教師データが大きければ、それを相手に学習
 教師データがなければクラスタリングなど
 小さな教師データと多数の生データ（実際は多い）
 Semi-supervised learning, Active learning などチャレンジング
記法
 yi , xi    1,1 R n , i  1,..,l
decision function: d x   wT x   b
l
w  i 1 i xi 


 x   xなら linear
 
以下では　wT  wT b xTi  xTi 1 とし、
bは陽には書かない
線形識別　linear classificationは以下の最適化問題を含む
l
min f w   r w   C   w; xi , yi 
w
i 1

r w  : 正則化項　 w; xi , yi：損失
正則化項:r＋損失:ξの最小化
各種の損失関数（右図）
 L1 w; x, y   max0,1  ywT x 
ξL2
 L 2 w; x, y   max0,1  yw x 
T
ξ(y,w,x)
2
 LR w; x, y   log1  exp( yw x) 
T
ξL1
ξLR
ywTx
各種の正則化項
1 n 2
rL 2 w   w 2   wi
2 i 1
2
n
rL1 w   w 1   wi
0
i 1
学習アルゴリズム
• 以下では種々の学習アルゴリズムについて
述べる
双対化
双対問題を解くほうが良いこともある。双対化
とは以下の通り：
minimize f ( x)
P rimalproblem:
subject t o
gi x   0
i  1,..,n
Dual problem:
q   inf L x,   where
maximizeq 
subject t o　i  0
L x,    f ( x)  i 1 i gi  x 
n
i  1,..,n
双対化




1
2
w 2 gi w   max 0,1  yi wT xi  0
2
1
n
2
SVM dual : infL x,    inf w 2  i 1 i max 0,1  yi wT xi
2
SVM primal：　f (w ) 
 w  i 1 yi i xi n
1 n
n
n
T
 max i 1  j 1 i yi xi x j y j  j  i 1 i
2
1
 min  T Q  1T 
subject to 0  i  C
2
1
2
T
この制約は max 0,1  yi w xi  i and min w 2  Ci
2
という線形分離できない場合の定式化から出る


(数理手法IV　カーネル法　サポートベクターマシン　参
照）
比較
 Gradient Descentのような低次の手法はupdateは簡単
でメモリも少ない。収束が遅く、解は精密ではないが、
実は性能に大差ない
 ニュートン法のような高次の手法は、収束は早いが、
updateのコストは高い（例えば、Hessian-1の計算とか
LBFGSとか）。また、解空間がスムーズ（2階微分可能）
でないといけない。精密な最適化には有効。
 exp/logの計算はコストが高いことを忘れないように
 並列化する場合はコア間、ノード間の通信のコストも大き
いことに注意
Pegasos：Shalev-Schwalz et al. ICML 2007
L2正則化＋L1損失のSVM
1
min f w; B   w  C  max0,1  y w x 
2
w
2
2
T
i
iB
Bは全学習データ
Pegasosの更新は次式の劣微分による
w  w  f w; B 
where f w; B   w  C  yi xi
B   i | i  B,1  yi wT xi  0,
iB 
  Cl / k　, lはベクトル w， xiの次元、 kは繰り返し回数
更新の後、wを半径(Cl)-1/2の球にproject


w  min 1, Cl w 2 w
以上を収束するまで繰り返す。
Trust Region Newton Method(TRON):導入
 データの次元:nが大きいと▽2f(w)はn×nなのでメモ
リに置くのも逆行列の計算も大変。
逆行列計算はBFGSなどによる
 まずlogistic regressionについて


l
1 T
min f w   w w  C  log 1  exp  yi wT xi
w
2
i 1
l


f w   w  C  1  exp  yi wT xi
i 1
 2 f w   I  CX T DX

X  x1T  xTl

T


1

 1 yi xi
Dは対角行列


Dii  1  exp  yi wT xi

1
1  1  exp y w x  
i
 するとNewton法は以下のようになる。
w k 1  w k  s k
 
 

1
T

 f w k   2 f w k s k  I  CX T DX s k
i
[Dij]が対角行列であることの直観的説明
1
min f w   w w  C  log1  exp y w x 
2
l
T
T
w
l

i
i 1

f w   w  C  1  exp  yi wT xi

X  x1T  xTl

i 1
T
2  2で具体例




1

 1 yi xi  2 f w   I  CX T DX
Dii  1  exp  yi wT xi

i

1


1  1  exp y w x  
i

i

i


x
x 2   11
 x12
X  x1
T


exp  yi wT xi yi xi yi xi
T
1  exp y w x 
2
T
i
x21 
x1T   x11
X   T  

x22 
x 2   x21
1
T
 2  log 1  exp  yi wT xi   1  exp  yi wT xi
i
Dは対角行列
i
i


1
 1 yi xi
  xi Dii xi
T
i
x12 
x22 
2
2

x
D

x
x11 x12 D11  x21 x22 D22 
2
T
T
11
11
21 D22
  log 1  exp  yi w xi   xi Dii xi  

2
2
x
x
D

x
x
D
x
D

x
D
i 1
i 1
12
11
22
22 
 11 12 11 21 22 22
x21D22   x11 x12   x11 x21   D11 0   x11 x12 
x D
  11 11







Ｄは対角行列
 x12 D11 x22 D22   x21 x22   x12 x22   0 D22   x21 x22 
2



2
 D11  0  0 ..0 x0... 0   0  0 


 

DX       0 ...0 x0.        
 0  D   .0 x0...
 0  0
11 

 

 xiがsparse 

w k 1  w k  s k
 
 
 f w 


 f w k   2 f w k s k  I  CX T DX s k  s k
w
k 1
w
k
k
 (I+ε)-1はεが小さいと近似計算もできそう。
 １次近似なら(I+ε)-1= I－ε
w
k 1
 I  CX
 w  f w
k
k
T
DX

 したがって、データが高次元Sparseならlogistic regressionは
Hessianの計算を避けられて、効率よく計算できる。
Trust Region Newton Method(TRON):
C.-J Lin et.al. SIAM J. Optimization 9 (1999)
 以下の問題をfの2次の展開qを用いて解く
l
min f w   r w   C   w; xi , yi 
w
rは L 2, は微分可能
i 1
1
T
f w  d   f w   qd   f w  d  dT  2 f w d
2
予め決めた閾値
 最適化問題
step 1 min qd 
d
subject to d 2  
f w  d   f w 
 0 then w  w  d
qd 
step 3 Adjust  according to 
step 2 if  
Trust Region bound Δkの変え方
 k   k 1の規則
1   2  1
1   2  1   3
 k 1   1 min d k ,  2  k ,  2  k 
 k 1   1 k ,  3 k 
 k 1   k ,  3 k 
if
if
if
 k  1 , 2 
k  2
 k 1
まだ最適値からは遠いので
f w  d   f w 

qd 
小  小さく
大  大きく
f w  d   f w 
1
T
qd   f w  d  dT  2 f w d
2
もう最適値に近いので
ｄ
ｄ
このアイデアは目的関数
が凸で微分可能なあたり
にポイントがある！
Coordinate Descent
C.-J. Hsieh, et.al. ICML2008
Target: L1損失- L2正則化のSVM 双対化し
て解く。下に定義
1 T
min f α   α Q α  eT α
α
2
subject to 0   i  C i  1,..., l
D
where Qij  yi y j xTi x j
Coordinate Descent
Coordinate Descentは順番に1変数づつ選び、
他の変数は固定して最適化。
1
min f D α  dei   f D α   Qii d 2  i f D α d
d
2
f Dは fの双対


subject to 0   i  d  C where ei  0
,..0,1,0,...0
 i 1

dを計算することによる  iの更新式は下式
D




f
α   
i

 i  min max  i 
,0 , C 
Qii

 

CD10
T
Coordinate Descent つづき
(CD10)のQiiはαiの最適化の中で1回計算すれ
ばよいが
  f α   Qα   1   y y x x   1 は　x x t  1,.., l
l
D
i
i
t 1
i t
T
i
t
t
の計算コストが Onl  でうれしくない。そこ


u
T
i
t
で
l
 y x
t 1
t
t
t
を保持しておけば
i f D α   Qα i  1  yiuT xi  1 (CD20)
となり計算コストは


u  u＋ yi  i   i xi
以下の計算のための On  でうれしい。
CD30
 i (CD10)の更新前、 i (CD10)の更新後
L1損失-L2正則化のSVMの
Coordinate Descent アルゴリズム
l
αの初期化、および u   yi i xi
i 1
Qii i  1,..., lの計算
while α is not optimal
For i  1,..l
(CD20)により G  yiuT xi  1の計算
i  i

 

G
,0 , C 
 i  min max  i 
Qii  


u  u  yi  i   i xi
Newton+ Coordinate Descent
J. H. Friedman, T. Hastie, and R. Tibshirani,
“Regularization paths for
generalized linear models via coordinate
descent,” Journal of Statistical
Software, vol. 33, no. 1, pp. 1–22, 2010.
 最小化する目的関数 f は以下
L1正則化項
l
f w   w 1  Lw 　where Lw 　 C   w; xi , yi 
i 1
繰り返しごとに解くの
は2次近似した以下の問題
1 T
min qd   w  d 1  w 1  Lw  d  d Hd (NCD10)
d
2
where H   2 Lw   I
T
小さなvはHをpositive保つため導入
 ただし、L1正則化項（1-norm)のために全体を一度
に解けないので、coordinate descentを導入
 (NCD10)を１変数化してみると以下のようになる
q d  ze j   qd 
 w  d  ze j  w 1  Lw  d  ze j  
T
1
 wd 1
 w 1  Lw  d
T
1
d  ze j T H d  ze j 
2
1
 dT Hd
2
1
 w j  d j  z  w j  d j  G j z  H jj z 2 where G  Lw   Hd
2
 L1正則化における次元ご
との最適化の手法を利用すると
 Gj 1
if G j  1  H jj w j  d j 
 H
jj

 Gj 1
z  
if G j  1  H jj w j  d j 
 H jj
  w j  d j  otherwise


( NCD 20)
(NCD20)の直観的説明
1 2
Hz を求める。　w  d は定数なので無視。
z
2
1 2  g1 z  if z  w  d 
w  d  z  Gz  Hz  
2
 g 2 z  if z  w  d 
min w  d  z  w  d  Gz 
g1 z   w  d  z  Gz 
1 2
1
Hz , g 2 z    w  d  z  Gz  Hz 2
2
2
g1 z の2次関数としての最小値が  w  d より大きいのは
g1 z 
G 1
0 z 
 w  d 　すなわち G  1  H w  d 
z
H
G 1
then z  
otherwise z  w  d 
H
g 2 z の2次関数としての最小値が  w  d より小さいのは
g 2 z 
G 1
0 z 
 w  d 　すなわち G  1  H w  d 
z
H
G 1
then z  
otherwise z  w  d 
H
g2(z)
g1(z)
z
-(w+d)
(NCD20)を各次元に対して行うと最適化問題
(NCD10)の1回の繰り返しができる。
さて、 (NCD10)を直線探索で繰り返して近似
精度を上げる
直線探索による近似アルゴリズム
w,0   ,0  が与えられた
for k  1,2,...
( NCD10)の近似解 dを coordinate descent法( NCD 20)で得る


f w  d   f w    w  d 1  w 1  Lw  d を満たす
T


ような   max 1,  ,  2 ,... を見つける
w  w  d
メモリに乗り切らないビッグデータの
処理に関して
 ディスクとメモリのデータ転送
学習中にディスクとメモリのデータ転送回数が増える
のはもちろん問題だが
ビッグデータを（分割するにしても）メモリに1回転送す
る時間も膨大
 分散環境（地理的な場合も含む）にデータがある
場合
分散環境での学習はもっと厄介
あまり公表された成果がない。Googleがちらっとブロ
グで言った程度
オンライン学習による方法
元来が1データ毎の学習なので自然な方法
L1-正則化&L2-損失のSVMは以下の更新式


2
1

w  w   S  w 2  C max 0,1  yi wT xi 
 Sは sub - gradient
2

 if 1  yi wT xi  0 then w  1   w  Cyi xi
理論的決め方なし
収束速度が遅い
Coordinate Descentのように双対化して解く


u  u＋ yi  i   i xi
CD30
ηを決める必要なし
収束の遅さを改善するために高次情報を使う
1

w  w  H   w  C max0,1  y w x 
2
1
2
S

T
i
2


i

2
1

H   2  w 2  C max 0,1  yi wT xi   対角行列になることが多い
2

 H 1の計算が重くない
バッチ学習による方法
 ディスクアクセスを減らすために一度のあるまとまり
のデータ（＝ブロック）を読み込み学習
 ブロックBだけではなく、メモリにcacheデータも残す
1
min f D α   αT Q α  eT α subject to 0   i  C i  1,..., l
α
2
where Qij  yi y j xTi x j を解くために
ブロック Bは全データ  B1 , Bm から 1個づつ選んで最適化
条件： 0   i  di  C for i  B and di  0 for i  B　1
min f D α  d   f D α   dTBQBBd B  dTB Qα  e B
d
2
l
1 T
T
T
 d BQBBd B   yi di u xi  d Be B where u   yi i xi
2
iB
i 1
QBBは Qのうち Bに関する部分行列



Download Report