サポートベクトル回帰におけるDecremental アルゴリズムの一般化に関する一考察

サポートベクトル回帰における

Decremental

アルゴリズムの

一般化に関する一考察

A Study on Generalization of Decremental Algorithm

for Support Vector Regression

烏山 昌幸

1

_{竹内 一郎}

1

_{中野 良平}

2

Masayuki Karasuyama

1

_{Ichiro Takeuchi}

1

_{Ryohei Nakano}

2

1

_{名古屋工業大学}

1

_{Nagoya Institute of Technology}

2

_中部大学

2

_{Chubu University}

Abstract: Incremental and decremental algorithm of the Support Vector Machines (SVM) [1, 2, 3]

efficiently updates trained SVM parameters whenever a data point is added to or removed from the training set. When we need to add or remove many data points, the computational cost of these methods becomes inhibitive because we have to repeatedly apply the method for each data point. In this paper, we generalize the existing decremental algorithm of Support Vector Regression (SVR) [2, 3] in such a way that several data points can be removed more efficiently. In our proposed approach, which we call generalized decremental SVR (GDSVR), we consider a path-following problem in multi-dimensional parameter space. The experimental results show that GDSVR can reduce the computational cost of leave-m-out cross-validation (m > 1). In particular, we observed that the number of breakpoints, which is the main computational cost of the involved path-following, were reduced fromO(m) to O(√m).

1

はじめに

サポートベクトル回帰 (Support Vector Regression: SVR) はサポートベクトルマシン (Support Vector Ma-chines: SVM) [4] の回帰分析への拡張であり，カーネ ルトリックや解のスパース表現，２次最適化問題への 帰着など SVM の主要な特徴を引き継ぐ回帰手法とし て知られている． 与えられたデータに対して最適化が完了した後に， データ点が追加または削除される場合を考える．この 時，通常は最適化問題を最初から解き直さなければな らない．こういった場合に再学習を行わずに最適解を 適応的に更新する方法が SVM，SVR 共に提案されて いる [1, 2, 3]．これらは全て最適化におけるパス追跡 [5] の考え方を利用した方法として捉えることができる． パス追跡は本来，最適化問題の設定パラメータの変化 に対する解パラメータの変動を追いかける手法であり， SVM の正則化係数に対するパス [6] や SVR の正則化 連絡先：名古屋工業大学大学院工学研究科       〒 466-8555 名古屋市昭和区御器所町        E-mail: [email protected] 係数・無反応領域に対するパス [7] などが研究されてい る．パス追跡ではパスの区分線形性が重要となり，パ スの折れ曲がる点 (breakpoint) を監視しながらパスを 追いかける． [1, 2, 3] では一度に変更されるデータ点の数は１つと して考えられていたが，交差検証を行う場合など，複 数のデータ点を一度に削除して再学習しなければなら ないケースがある．複数データ点の変更には従来法で はデータ点の数だけ手続きを繰り返さなければならな い．本稿では，SVR において複数データ点が削除され た場合に，１つのデータ点の削除を繰り返すのではな く，一度に複数データを削除し最適解を効率良く更新 するアルゴリズムを提案する．提案法では多次元上の パス追跡を考えることにより，パラメータ空間上で最 短のパス経路をたどる．これにより，breakpoint の数 が減少し更新にかかる計算コストが削減されることを 示す． 本稿では，まず 2 節で多次元パスによる複数データ 点の削除法について述べ，3 節の実験で交差検証にか かる計算時間の比較により提案法の効果を示す．最後 に，5 節でまとめと今後の展望について述べる． 人工知能学会研究会資料 SIG-DMSM-A803-13 (3/4)

2

SVR

の一般化

Decremental

ア

ルゴリズム

2.1

SVR

n 個の訓練データ点を{(xi, yi)}ni=1とする．ただし， 入力ベクトルを xi ∈ Rd，出力変数を yi ∈ R とした. SVR の回帰関数は以下のように表される: f (x) = n ∑ i=1 iK(x, xi) + b. ただし，K : Rd_{× R}d _{→ R はカーネル関数であり，} {i}ni=1，b はモデルパラメータである．パラメータ {i}ni=1は以下の最適化問題により得られる: max {}n i=1 −1 2 n ∑ i=1 n ∑ j=1 ijK(xi, xj) −ε n ∑ i=1 |i| + n ∑ i=1 yii s.t. n ∑ i=1 i = 0, −C ≤ i≤ C, i = 1, · · · , n. C, ε∈ R+_{はそれぞれ，正則化係数と無反応領域の幅} である [8]．最適性条件である KKT 条件より，最適解 は以下の関係を満たす: yi− f(xi)≥ ε ⇒ i= C, yi− f(xi) = ε ⇒ i∈ [0, C], yi− f(xi)∈ [−ε, ε] ⇒ i= 0, yi− f(xi) =−ε ⇒ i∈ [0, −C], yi− f(xi)≤ ε ⇒ i=−C. 上記の関係性を利用した以下の集合を定義しておく: I = {i : |yi− f(xi)| < ε, i= 0}, E = {i : |yi− f(xi)| = ε, |i| ∈ [0, C]}, (1) O = {i : |yi− f(xi)| > ε, |i| = C}. 以降では，これらの集合によって指定されるインデッ クスをもつ部分行列や部分ベクトルを下付きの添え字 を使って表す．v_Iはベクトル v∈ Rn_{の部分ベクトル} であり，その要素は集合_{I によって指定される. 行列} についても同様に，M_E,O は M ∈ Rnn_{の部分行列} で，行が集合_{E，列が集合 O によって指定される．ま} た，M_E,Eは M_E と略記する．

2.2

パラメータの更新方法

今，インデックス集合_{R ⊂ {1, · · · , n} に対応する} データ点_{(xi, yi)}i_∈Rを学習されたモデルから取り除 きたいとする．α_Rの全ての要素が 0 の時，これらの データ点を除いても KKT 条件は成り立っているためパ ラメータを変更する必要はない．そうでない場合，つ まり α_R ̸= 0 な場合は最適性条件を満たしたまま αR を 0 にすることを目指す． ここで，ベクトル y = [y1,· · · , yn]T, f = [f (x1),· · · , f(xn)]T, s = sign(y− f), を定義しておく．これらを使うと，_{E に関する条件 |yi−} f (xi)| = ε と等式制約 ∑n i=1i= 0 をまとめて [ K_E 1 1T 0 ] [ α_E b ] + [ K_E,Oα_O− y_E + εs_E 1Tα_O ] = 0, (2) と表すことができる．ただし，K はカーネル行列 Ki,j = K(xi, xj) とする．∆αRを αRの変化量として αR← α_R+ ∆α_R としても式 (2) が，削除されないデータ点 ˜ E = E \ R について成り立ち続けるためには [ K_Ee 1 1T 0 ] [ ∆α_Ee ∆b ] + [ K_E,Re 1T ] ∆α_R= 0, (3) を満たす必要がある．１つだけのデータ点を削除する 従来の方法 (|R| = 1) と異なり，変化させるパラメー タの更新方向 ∆α_Rを決めなければならない．後の計 算機実験でも触れるが，この方向の決定はアルゴリズ ムにかかる計算コストに大きな影響を及ぼす．ただし， α_Rを 0 にするのが目的であるため，∆α_Rは単純に ∆α_R=−α_R, (4) とすれば最短パスを通ることができる． はステップ 長を表す．式 (4) と式 (3) を使って以下のような更新式 を導きだすことができる: [ ∆α_E˜ ∆b ] =  ϕ, (5) ただし， ϕ = M 1 [ K_E,R˜ 1T ] α_R, M = [ K_E˜ 1 1T 0 ] , とする．ステップ長  を決定するためには集合 ˜E, ˜O = O \ R, ˜I = I \ R に変化が起こる点 (breakpoint) を監 視する必要がある．具体的にはこれらの集合の要素に 変化が起こらない最大の大きさに  を設定する． > 1 となった場合は  = 1 とすることで α_R= 0 に到達す ることになる．各集合の定義 (1) を考慮すると，パラ

メータ更新後に以下の条件が満たされていなければな らない: sii ≤ C i∈ ˜E, (6a) sii ≥ 0 i∈ ˜E, (6b) si(yi− f(xi)) ≥ ε i∈ ˜O, (6c) −ε ≤ yi− f(xi) ≤ ε i∈ ˜I. (6d) 各不等式について  の最大値を計算すると，|E| × 2 + |O|+|I|×2 個の値が得られる．これらの値の集合を H と表記すると，最終的な  は ← min(H ∪{1}) によっ て定めることができる．i∈ ˜E に関する制約 (式 (6a) と 式 (6b)) については，式 (5) を使って  を計算するこ とができる．i∈ ˜O と i ∈ ˜I に関する制約 (式 (6c) と式 (6d)) については f (xi) の変化量 ∆f = [K_{:, ˜E} 1] [ ∆α_E˜ ∆b ] + K:,_R∆α_R =  ψ, (7) を使うことで  が計算できる．ただし，ψ = [K_{:, ˜E}1]ϕ− K:,RαRであり，K:, ˜E と K:,Rの添え字”:”は K のす べての行を示す． が決まれば，α_E˜と b は式 (5) によっ て更新できる． ˜_{E, ˜O, ˜I を更新する点はパス追跡におけ} る breakpoint に相当する．もし，i 番目のデータ点が 式 (6a)∼ (6d) のいずれかの制約の境界に達した場合， ˜ E, ˜O, ˜I は達した制約に応じて以下の更新を行う: ˜ E ← ˜E \ i, _{O ← ˜}˜ _{O ∪ i, (8a)} ˜ E ← ˜E \ i, _{I ← ˜I ∪ i,}˜ _(8b) ˜ O ← ˜O \ i, _{E ← ˜}˜ _{E ∪ i, (8c)} ˜ I ← ˜I \ i, _{E ← ˜}˜ _{E ∪ i. (8d)} ˜ E, ˜O, ˜I の更新後は，ϕ, ψ を再計算して次の breakpoint までの幅  を計算する．ϕ を式 (5) で計算する場合，逆 行列の計算が必要になるが，この逆行列は最初に一回 計算しておけば，その後は部分行列の逆行列の公式 [9] や，コレスキー分解の rank one update [10] を用いる

と o(n2_{) で効率よく更新できる．アルゴリズム全体の} 流れは以下のようになる:   Initialize : α, b← SV R({(xi, yi)}ni=1) setE, O, I calculate M 1 Decremental Algorithm (Inputs: α, b,E, O, I, M 1,R ): ˜ E ← E \ R, ˜O ← O \ R, ˜I ← I \ R while α_R̸= 0 update M 1 calculate ϕ, ψ,H ← min(H ∪ {1}) [ αT ˜ E b ] T _{← [ α}T ˜ E b ] T_{+ ϕ} α_R← α_R− α_R update ˜E, ˜O, ˜I end  

3

計算機実験

一般化 Decremental アルゴリズムの性能を評価する ために，m 個抜き交差検証 (leave-m-out cross-validation) にかかる CPU 時間の比較を行った (m 個抜きの交差検 証は n/m-fold 交差検証であるといえる)．比較には従来 の Decremental アルゴリズムとして AOSVR [3] を，通 常の SVR の再学習として SMO[11] による学習を比較 する．SMO の実装は LIBSVM[12] を利用した．カーネ ルは RBF カーネル: K(xi, xj) = exp ( −γ||xi− xj||2 ) とし，γ = 1 とした. 正則化係数 C と無反応領域幅 ε は，C = 1, ε = 0.1 とする．ここでは回帰曲線の汎 化性は特に重要ではないため，これらのパラメータの 最適化は行っていない．データとして以下の４つを利 用した: (a) Abalone (UCI), (b) Space ga (StatLib), (c) cpu (Delve), (d) kin40k1．訓練データにはこれら のデータからランダムに抽出したサブセットを用いた． データサイズは n = 500, 1000, 2000 の３通りとし，そ れぞれについて m 個抜き交差検証を行う．m の値は 5, 10, 20, n/10 の４通りとした (m = n/10 のとき 10-fold 交差検証となる)．それぞれの訓練データは，yiを 平均 0 分散 1 に，xiの各次元を [0, 1] に正規化する． 図 1 に CPU 時間の対数プロットによる比較を示す． 一般化 Decremental アルゴリズムを適用した SVR を GDSVR(Generalized Decremental SVR) と呼ぶことと する．各プロットは横軸が m，縦軸が CPU 時間 (sec) の対数プロットとなっている．GDSVR はほぼ全ての 設定で，他の手法よりも高速となった．AOSVR は m によらず１つ抜き交差検証 (m = 1) と同程度の計算時

1_{available at http://ida.first.fraunhofer.de/∼anton/}

(a) Abalone data set 5 10 20 50 10−1 100 101 102 n = 500

CPU Time (sec)

5 10 20 100 100

101

102 n = 1000

m (The number of leaving out data points)5 10 20 200

100 101 102 103 n = 2000 GDSVR AOSVR LIBSVM

(b) Space_ga data set

5 10 20 50 100

n = 500

CPU Time (sec)

5 10 20 100 100

101

102 n = 1000

m (The number of leaving out data points)5 10 20 200

100 101 102 103 n = 2000 GDSVR AOSVR LIBSVM

(c) cpu data set

5 10 20 50 100

n = 500

CPU Time (sec)

5 10 20 100 100

101

102 n = 1000

m (The number of leaving out data points)5 10 20 200

100 101 102 103 n = 2000 GDSVR AOSVR LIBSVM

(d) kin40k data set

5 10 20 50 100

101

102 n = 500

CPU Time (sec)

5 10 20 100 100

101

102

103 n = 1000

m (The number of leaving out data points)

5 10 20 200 101 102 103 n = 2000 GDSVR AOSVR LIBSVM 図 1: m 個抜き交差検証における CPU 時間 (sec) の対数プロット 間がかかる．これは m 個のデータを学習済みモデルか ら削除するのに１つ抜きを m 回繰り返すためである． 一方，GDSVR では，m 個のデータ点を一度に最短パ スで削除できるため効率が良く，m の増加とともに計 算時間が減少した．LIBSVM は，特に m が小さい場合 に計算時間が大きい．しかし，m が大きくなるにつれ 計算時間の減少する割合は最も大きい．m が大きいと， 全体データで学習されたパラメータとデータ点削除後 のパラメータの違いは大きくなる．そのため，ある程 度以上大きい m では全体データからの更新よりも，ス クラッチからの再学習のほうが高速になる．

4

考察

パス追跡の計算コストは breakpoint の数に比例す るため，AOSVR と GDSVR においてその比較を行っ た．図 2 は交差検証のうちの１回の学習に発生した breakpoint 数の平均である．α_Rの空間について，集 合 ˜_{E, ˜O, ˜I の要素が不変である領域の境界が一様に分布} していると仮定すると，breakpoint の数は通ったパス の長さに比例することになる．ここで，α_R ̸= 0 の要 素が全て同じ値と仮定する．その時 AOSVR では，m 回の一次元パス追跡を繰り返すため breakpoint の数が m に比例する．一方 GDSVR はパスの長さが m の平 方根に比例するため (図 3 に|R| = 2 の場合を示した)， breakpoint の数は√m に比例することになる．よって， AOSVR と GDSVR の breakpoint の数の期待値の割合 は m :√m となる．実際，図 2 ではそのような結果が 見て取れる．

5

まとめ

本稿では SVR の Decremental アルゴリズムの複数 データ点の同時削除への拡張を行った．パス追跡では breakpoint の数が計算時間に大きな影響を与えるが， 一般化された Decremental アルゴリズムでは最短のパ スをたどることで breakpoint の数が減るため，計算コ ストの削減が可能になる．SVR の交差検証を使った実 験では，提案法 GDSVR は従来の一次元パス追跡の繰 り返しや再学習よりも効率的にモデルを更新できるこ とを実証した．今後の課題として他のカーネルマシン への適用や Incremental アルゴリズムの一般化などが 挙げられる．

参考文献

[1] Cauwenberghs, G. and Poggio, T.: Incremen-tal and DecremenIncremen-tal Support Vector Machine Learning, in Leen, T. K., Dietterich, T. G. and Tresp, V. eds., Advances in Neural Information

Processing Systems, Vol. 13, pp. 409–415,

Cam-bridge, Massachussetts (2001), The MIT Press. [2] Martin, M.: On-line Support Vector Machines

for Function Approximation, Technical report, Software Department, Universitat Politecnica de Catalunya (2002).

[3] Ma, J. and Theiler, J.: Accurate Online Support Vector Regression, Neural Computation, Vol. 15, No. 11, pp. 2683–2703 (2003).

(a) Abalone data set 5 10 20 50 0 50 100 150 200 250 300 n = 500

The ave. num. of breakpoints

5 10 20 100 0 100 200 300 400 500 600 700 n = 1000

m (The number of leaving out data points) 5 10 20 200 0 200 400 600 800 1000 1200 1400 n = 2000 GDSVR AOSVR

(b) Space_ga data set

5 10 20 50 0 50 100 150 200 250 300 350 n = 500

The ave. num. of breakpoints

5 10 20 100 0 100 200 300 400 500 600 700 n = 1000

m (The number of leaving out data points) 5 10 20 200 0 200 400 600 800 1000 1200 1400 n = 2000 GDSVR AOSVR

(c) cpu data set

5 10 20 50 0 50 100 150 200 250 n = 500

The ave. num. of breakpoints

5 10 20 100 0 100 200 300 400 500 600 n = 1000

m (The number of leaving out data points) 10 205 200 0 200 400 600 800 1000 1200 n = 2000 GDSVR AOSVR

(d) kin40k data set

5 10 20 50 0 50 100 150 200 250 300 350 400 450 n = 500

The ave. num. of breakpoints

5 10 20 100 0 200 400 600 800 1000 1200 n = 1000

m (The number of leaving out data points) 10 205 200 0 500 1000 1500 2000 2500 3000 n = 2000 GDSVR AOSVR 図 2: 交差検証中の１回の学習で発生した breakpoint 数の平均 R = {1, 2} αR αR α₂ α1 α1 α₂ ึᮇαR ࣃࢫ breakpoints - - E˜, ˜O, ˜I ࡀ୙ኚ ࡞   㡿ᇦ ࡢቃ⏺ AOSVR GDSVR 図 3: m = 2 の場合の AOSVR と GDSVR のパスの概略図．左のプロットでは AOSVR は α_Rの要素を 1 つずつ 0 にしている．それに対して右のプロットの GDSVR では α_Rを最短パスで 0 にしている．破線で囲まれた領域は ˜ E, ˜O, ˜I が不変であるような領域を表す．これらの領域とパスの交点が breakpoint に相当する．パス追跡において breakpoint での行列・ベクトルの更新は計算コストの大部分をしめる．この図では，AOSVR は原点に到達する までに 5 つ breakpoint を持つが，GDSVR では 3 つの breakpoint で済む．領域境界の一様な分布と，1= 2を 仮定すると，breakpoint の数の期待値の割合はパスの長さの比 2 :√2 となる．

[4] Vapnik, V. N.: The Nature of Statistical Learning

Theory, Springer-Verlag (1995).

[5] Gal, T.: Postoptimal Analysis, Parametric

Pro-gramming and Related Topics.

[6] Hastie, T., Rosset, S., Tibshirani, R. and Zhu, J.: The Entire Regularization Path for the Support Vector Machine, Journal of Machine Learning

Research, Vol. 5, pp. 1391–1415 (2004).

[7] Wang, G., Yeung, D.-Y. and Lochovsky, F. H.: A kernel path algorithm for support vector ma-chines, in Twenty-fourth International

Confer-ence on Machine Learning, pp. 951–958 (2007).

[8] Cristianini, N. and Shawe-Taylor, J.: An

Intro-duction to Support Vector Machines and other kernel-based learning methods, Cambridge

Uni-versity Press (2000).

[9] Schott, J. R.: Matrix Analysis For Statistics, Wiley-Interscience (2005).

[10] Golub, G. H. and Loan, van C. F.: Matrix

Com-putations, Johns Hopkins University Press, 3rd

edition (1996).

[11] Platt, J. C.: Fast Training of Support Vector Ma-chines using Sequential Minimal Optimization, in Sch¨olkopf, B., Burges, C. J. C. and Smola, A. J. eds., Advances in Kernel Methods — Support

Vector Learning, pp. 185–208, Cambridge, MA

(1999), MIT Press.

[12] Chang, C.-C. and Lin, C.-J.: Libsvm - a library for support vector machines, http://www.csie. ntu.edu.tw/cjlin/libsvm/.