情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences 2009 (IBIS2009)

重み付きカーネルマシンの多次元パス追跡法に関する一考察

A Study on Multi-dimensional Path Following for Weighted Kernel
Machines
烏山 昌幸∗
Masayuki Karasuyama

原田 尚幸†
Naoyuki Harada

竹内 一郎‡
Ichiro Takeuchi

Abstract: We propose multi-dimensional path following for weighted kernel machines.
In some situations of data modeling, each data point has a weight which represents theimportance or conﬁdence of the data point. We can easily implement such weighting
schema in kernel machines by introducing multiple regularization parameters. In this paper,
we derive the piece-wise linear path of these parameters which extends the idea of wellknown regularization path. Conventional algorithm only deals with the change of single
regularization parameter. On the other hand, our approach can handle the change ofmultiple parameters simultaneously. Experimental results show that proposed algorithm
can eﬃciently update optimal parameters. Our approach is especially beneﬁcial for adaptive
learning or online learning of weighted model.
Keywords: weighted kernel machines, support vector machines, path following.

1

まえがき
パターン認識において訓練データからモデルを推定する場合に，各々のデータ点ごと（あるいは，いつかのデータ点のグループごと）に異なる重みを与えたい場合がある．重みはデータの分散を考慮して適応的に定められたり [1]，データの性質に関する事前知識などから決められる．後者の具体例としては，経済データにおいて最近のデータ点ほど重要視されるようにしたり [2, 3]，ス
パムメールのフィルタリングにおいてメールのカテゴリ
ごとに異なる重みを与えたり [4] といった事例がある．

n 個の訓練データ点を {(xi , yi )}ni=1 とする．ただし，xi ∈ X ⊆ Rd であり，yi ∈ {1, −1} なら 2 値分類問
題，yi ∈ R なら回帰問題として考えることができる．サ
ポートベクトルマシン (SVM)[5] に代表されるカーネル∗ 名古屋工業大学大学院工学研究科, 466-8555 名古屋市昭和区御器所町, tel. 052-735-7524, e-mail krsym@ics.nitech.ac.jp,
Nagoya Institute of Technology, Gokisocho, Showa, Nagoya, 4668555 Japan† 名古屋工業大学大学院工学研究科, 466-8555 名古屋市昭和区御器所町, tel. 052-735-7524, e-mail harada@goat.ics.nitech.ac.jp,
Nagoya Institute of Technology, Gokisocho, Showa, Nagoya, 4668555 Japan‡ 名古屋工業大学大学院工学研究科, 466-8555 名古屋市昭和区御器所町, tel. 052-735-7524, e-mail takeuchi.ichiro@nitech.ac.jp,
Nagoya Institute of Technology, Gokisocho, Showa, Nagoya, 4668555 Japan法の多くでは特徴写像 Φ : X → F による線形モデル

f (x) = wT Φ(x) + b の推定を以下のような最適化問題に帰着させる:
min
w,b

n
∑
1
∥w∥22 + C
L(yi , f (xi )).
2
i=1

ただし，L(y, f (x)) は訓練誤差を測る損失関数，C > 0
は正則化パラメータとする．ここで，n 個の正則化パラ
メータ Ci > 0, i = 1, · · · , n, を考えることでデータ点ごとに個別の重みを課すことができる:

min
w,b

n
∑
1
∥w∥22 +Ci L(yi , f (xi )).
2
i=1

例えばデータ点 i = 1, · · · , n, が時系列順に並んでいるとして，最近のデータをより重視させたいのであればCi < Ci+1 となるように設定すればよい．
これらの最適化問題を解く際には Ci はあらかじめ固
定された値に設定しておくことが多い．しかし，Ci を様々な方法で変化させ，それぞれの設定に対して最適な

f (x) を得たい場合がある．例えば，• どのデータ点をどの程度重視するかを適応的に決めたい場合

• 新しくデータ点が追加され，データセット全体の重要度の振り分けを再調整したい場合（古いデー
タ点の重要度を下げる等）といった状況がある．
正則化の度合いを変化させたい場合に，単一の正則化
パラメータ C を用いた SVM においては正則化パス [6]と呼ばれる方法で C の変化に対する最適な f (x) の変化

主変数 w, b, ξi に関して微分して 0 とおくと，

∂L
=0 ⇔
∂w
∂L
=0
∂b

⇔

∂L
=0
∂ξi

⇔

w=

n
∑

αi yi Φ(xi ),

i=1
n
∑

αi yi = 0,i=1αi = Ci − ρi , i = 1, · · · , n,を求めることができる．これは最適化においてパス追跡(Path Following) やパラメトリック計画法 (Parametic
Programming) と呼ばれる手法 [7] を利用しており，正則化係数の連続的な変化に対する f (x) の変化を解析的に計算することができる．そのため最適な C を探すモが得られる．これらをラグランジュ関数 (1) に代入する
ことで以下の双対問題が得られる:

−

max
n

{αi }i=1

デル選択時などにおいて有効であった．一方で個別の正則化パラメータを導入した場合，上で示したような状況

n
n
n
∑
1 ∑∑
αi αj yi yj K(xi , xj ) +αi
2 i=1 j=1
i=1

n
∑

s.t.

yi αi = 0, 0 ≤ αi ≤ Ci ,i=1

では n 個の Ci が同時に変化することを考えたい．そこで本稿では，多変数に対するパス追跡 [8] を導入するこ

ただし，K(xi , xj ) = Φ(xi )T Φ(xj ) はカーネル関数とすとで各データ点ごとの重みを動かした時のモデルの変化

る．f (x) の双対表現は以下のようになる:を効率的に追跡する方法を提案する．

f (x) =

重み付き SVM のパス追跡

2

αi yi K(x, xi ) + b.

i=1

個別正則化パラメータのパス追跡として SVM による

2 値分類問題 (yi ∈ {1, −1}) を例に解説する．同様の理論はサポートベクトル回帰（SVR）等の他のカーネルマ
シンにおいても適用が可能である．

2.1

n
∑

バイアス b は yi f (xi ) − 1 = 0 となるような i を使って求める．最適解において yi f (xi ) − 1 の値は KKT 条件の相補性条件αi {yi f (xi ) − 1 + ξi } = 0,i = 1, · · · , n,ξi (αi − Ci ) = 0,i = 1, · · · , n,

SVM と KKT 条件

SVM では損失関数 L として以下のヒンジ損失関数を使う:と主問題，双対問題の不等式制約を考慮することにより

yi f (xi ) − 1 > 0 ⇒yi f (xi ) − 1 = 0 ⇒L(y, f (x)) = max{0, 1 − yf (x)}.
個別正則化パラメータを使った場合，以下のような最適化問題に帰着できる:

yi f (xi ) − 1 < 0ξi = 0,αi = 0,ξi = 0, 0 ≤ αi ≤ Ci ,⇒ ξi > 0,αi = Ci ,といった関係を持つことがわかる．この関係を使って以n∑minw,b,{ξi }ni=11∥w∥22 +
Ci ξi ,
2
i=1

s.t.

yi f (xi ) ≥ 1 − ξi ,下の集合を定義しておく:O

ξi ≥ 0, i = 1, · · · , n.

= {i : yi f (xi ) > 1, αi = 0},(2a)M = {i : yi f (xi ) = 1, 0 ≤ αi ≤ Ci },

(2b)

I

(2c)

= {i : yi f (xi ) < 1, αi = Ci }.

このように訓練誤差に個別の重みを課した SVM は Weighted

SVM[9] や Fuzzy SVM[10] と呼ばれることもある．ラグ

以降では，部分行列や部分ベクトルを表わすため，集合をランジュの未定乗数 αi , ρi ≥ 0, i = 1, · · · , n, を導入する

下付きの添え字として用いることとする．例えば，ベクトとラグランジュ関数は以下のようになる:ル v = [v1 , · · · , vn ]⊤ の要素のうち集合 I = {I1 , · · · , I|I| }L =に対応する部分ベクトル [vI1 , · · · , vI|I| ]⊤ は v I と表わn∑1
2||w|| +
Ci ξi
2
i=1

−

n
∑
i=1

αi {yi f (xi ) − 1 + ξi } −す．同様に，部分行列については n × n 行列 M に対し
n∑i=1て M M,O とした場合，行が M，列が O に対応する部

ρi ξi . (1)分行列とする．

多次元パス追跡の導入

2.2であるため ∆c が決まれば全てのパラメータの変化が計

正則化パス [6] では単一の C を変化させた時のパラ
メータ α = [α1 , · · · , αn ]⊤ , b の変化を追跡するが，ここでは個別正則化パラメータのベクトル


C1
 . 
. 
c=
 . ,
Cn

算できることになる．ただし，I, M, O の定義 (2a)-(2c)より，以下の不等式条件が満たされていなければならない:

yi {f (xi ) + ∆f (xi )} < 1,i ∈ I,(9a)0 ≤ αi + ∆αi ≤ Ci + ∆Ci , i ∈ M,

(9b)

yi {f (xi ) + ∆f (xi )} > 1,(9c)i ∈ O.

を c(old) から c(new) へと変化させたい場合を考える．ア

本稿ではこの不等式が定義する領域を Critical Region[8]ルゴリズムは [6] と同様に集合 O, M, I を監視して最適と呼ぶこととする．Critical Region の中ではパラメー
タ α, b の変化は式 (6)-(8) によって求めることができる．

性を満たしながらパラメータを変化させる．
⊤

今，c を ∆c = [∆C1 , · · · , ∆Cn ] だけ変化させた時

ここで ∆c をステップ幅 η ≥ 0 を使ってのパラメータ α, b の変化を考える．∆ を付けた変数は各∆c = η(c(new) − c(old) ),変数の変化量を表わすものとする．αi = Ci , i ∈ I, αi =(10)0, i ∈ O であることに注意すると yi f (xi ) は以下のようとして定めるとする．これは，c を c(old) から c(new) へに書くことができる:

直線的に動かすことに対応している．ただし，η を大き∑

yi f (xi ) =Qij αj +j∈M∑

くしていくと，ある値で Critical Region の境界に達す

Qij Cj + yi b,

る．式 (10) のように η を定めたことで，境界に達するj∈I

ステップ幅は容易に計算できる．具体的には，式 (10) をただし，Qij = yi yj K(xi , xj ) とした．c が ∆c だけ変化したとしても，(2b) よりマージン上の点では yi ∆f (xi ) =0 でなければならない:∑

Qij ∆αj +j∈M∑

Qij ∆Cj + yi ∆b = 0, i ∈ M. (3)j∈I

また双対問題の和制約を考慮すると，∑yj ∆αj +j∈M∑

yj ∆Cj = 0,(11)と書くことができる．ただし，
[
]
y⊤
(new)
(old)
−1
I
ϕ = −M(cI− cI ),
QM,I

(12)

(4)

j∈I

が得られる．式 (3),(4) の連立方程式を行列で表記すると以下のようにまとめられる:
[
] [
]
∆b
y⊤
I
M
+
∆cI = 0,∆αM
QM,I

式 (6) に代入して整理すると，
[
]
∆b
= ηϕ,
∆αM

とした．また，不等式中の ∆f (xi ) は
[
]
[
]
∆b
y ⊙ ∆f = y Q:,M
+ Q:,I ∆cI∆αM= η ψ,

(13)
(14)

(5)
を使って計算できる．ただし，⊙ を行列の要素ごとの積，

ψを

ただし，

[
M=

0
yM

y⊤
M
QM

]

(new)

ψ = [ y Q:,M ] ϕ + Q:,I (cI,とした．(5) を解くと
[
]
[
]
⊤
∆b
y
I
= −M −1
∆cI ,
∆αM
QM,I

(old)

− cI

),

とした．式 (11),(14) を使うと不等式 (9) を満たしたま
まどこまで η を大きくできるかが評価できる．
式 (6),(13) を考慮すると，式 (9) の不等式は ∆c に関(6)

して一次であることがわかる．そのため，各不等式は cの空間において半空間を定義しており，その共通部分として定義される Critical Region は凸多面体となる．各となる．また，不等式について境界値に達する η の値（η をそれ以上大

∆αO

= 0,

(7)

きくすると半空間から出てしまうような値）の集合を∆αI= ∆cI ,

(8)

H と定義する（η をどれだけ大きくしても境界値に達しC2
borders of current Critical Regionη∗ dc(new)

計算機実験

3

path
d = c(new) − c(old)

ここでは，忘却係数モデル [13, 14] のオンライン学習
を使って提案法の有効性を検証する．忘却係数モデルでは，ある C を 1 つ決めてから各正則化パラメータを減ηdc

衰率 λ ∈ (0, 1) を使って定義する:

c(old)
C1

Ci = Cλn−i ,図 1: n = 2 での概念図．c は c(old) から c(new) へと動
く途中であるとする．c から η ∗ d だけ進むと c(new) に到達するが，ηd だけ進んだ地点で不等式の定義する境界（破線）にぶつかるため一旦そこまで止まる．O, M, Iを更新することで新たな Critical Region が構成される
ので同様の手順で c(new) に向けて進めるだけ進む．
ない不等式もあるが，こういった場合は η = ∞ と考える）．c + ∆c が c(new) となるような η を η ∗ とすると，η ∗ が H のどの要素よりも小さければ η ∗ による更新でアルゴリズムは終了する (c が c(new)となる)．つまりス

テップ幅 η はmin(H ∪ {η ∗ }),によって定められる（図 1 に 2 次元での概念図を示した)．η ∗ 以外の η によってパラメータが更新された場合は，達した境界に応じて O, M, I の要素を移動させなければならない．このように Critical Region が切り替わる点を breakpoint と呼ぶ．O, M, I に変化が起こる
ため breakpoint では連立方程式 (12) の再計算が必要になるが，逆行列もしくはコレスキー分解のランク 1 更新

[11, 12] を利用することで再計算は O(|M|2 ) で可能になる．式 (6)-(8) よりパラメータ α, b の変化は全て ∆c に対して線形であることがわかるが，連立方程式の更新に
よりパラメータの変化は breakpoint で折れ曲がる（区分線形性）．アルゴリズムの流れを Algorithm 1 に示した:

i = 1, · · · , n.

これはデータ点 i = 1, · · · , n が時系列に並んでいる場
合などに，最近のデータほど重視させる方法の 1 つである．学習済みの忘却係数モデルに対して新たなデータ点(xn+1 , yn+1 ) が追加される時，以下のような更新を行う
ことにする:• 最も古い学習データ点 (x1 , y1 ) を学習データから除く (C1 = 0 とする)．
• 新しいデータ点 (xn+1 , yn+1 ) を学習データに加え，
Cn+1 = C とする．
• i = 2, 3, · · · , n に対して Ci ← λCi となるように重みを減少させる．
以上を考慮すると多次元パス追跡での更新方向は以下のようになる:



 

0
Cλn−1

 

 Cλn−1   Cλn−2 




..
..

 


 

.
.
(new)
(old)
c
−c
=
−
.
 Cλ2   Cλ 

 


 

 Cλ  CC

0

今回は全ての実験で λ = 0.99 とした．
また，以下の 2 つの手法について計算時間の比較を行う:

Algorithm 1 Multi-dimentional Path Following for
Weighted SVM
1: given optimal α, b for c(old)2: initialize M, O, I
3: calculate M−1c ̸= c(new) do
calculate ϕ, ψ using M −1

4: while
5:
6:
7:
8:
9:
10:

calculate H using ϕ, ψη ← min(H ∪ {η ∗ })update α, b, c using step length η
update M, O, I
update M −1

11: end while

逐次１次元パス追跡 提案法では全ての正則化パラメー
タを同時に動かすことができるが，比較として各

Ci を 1 つずつ動かしてモデルの更新を行う．ただし，ある Ci を減少させたい場合に，減少後の値
λCi より αi が小さいのであれば α, b を更新する必要はない（更新しなくても最適性条件が満たされているため）．

SMO SVM の 2 次計画問題の解法はパラメータ αi を 2つずつ最適化する Sequential Minimal Optimization (SMO) [15] が広く使われている．今回は最適化する 2 点を maximum violating pair [16, 17] により選択し，KKT 条件を ε = 10−6 以下の精度で

10

3

4

MD-PathSD-PathSMO(1e-6)

CPU time (msec)

2

x2

1

0

-1

10

2

-2

0

-3
-3

-2

-1

0

1

2

10
200

3

300

400

500

n

x1

図 2: 2 つの正規分布を用いて人工データを生成した．原図 3: 人工データによる CPU 時間比較 (MD-Path:多次点を平均として時間 t に対し不変な分布と，原点を中心

元パス追跡，SD-Path:逐次 1 次元パス追跡)とする半径 2 の円周上を時間 t とともに平均ベクトル µが動くような分布とした．
満たしたら停止することとした．また，α の初期値としてデータ点が追加される前の解を利用する

alpha seeding [18] を行った．
どの手法においても初期解 α, b とカーネル関数 K(xi , xj )表 1: 人工データの平均実行時間 (msec)
method \ n
200
300
400
500
多次元

2.50

4.93

9.90

22.80

逐次 1 次元

6.80
68.50

20.27
128.7348.30
400.75128.24447.64

SMO(1e-6)

はあらかじめ計算しておく．カーネルには以下の RBF
カーネルを用いた:K(xi , xj ) = exp(−∥xi − xj ∥2).
2σ 2

表 2: 人工データの平均 breakpoint 数
method \ n
200
300
400
500
多次元
逐次 1 次元

13.10
16.02

13.35
19.07

15.74
22.36

22.37
38.20

また，パス追跡においては初期逆行列 M −1 も用意された状況を想定して計算コストを選択した．

3.1

多次元

人工データ

人工データとして時刻 t = 1, · · · , n, に伴い平均が変化する正規分布から生成されたデータセットを用いる (図2):p(xt |yt = +1)

表 3: 人工データの平均サーチ回数
method \ n
200
300
400
500

=

p(xt |yt = −1) =µ(t) =N (0, I),N (µ(t), 0.25I),[]
cos(2πt/n)2.
sin(2πt/n)

逐次 1 次元

14.10
39.76

14.35
60.13

16.74
81.81

23.37
132.04

表 4: 人工データの CPU 時間比とサーチ回数比
ratio \ n
200 300 400 500
計算時間比（一/多）

2.72

4.11

4.88

5.62

サーチ回数比（一/多）

2.82

4.19

4.89

5.65

1 であり，表 2 には多次元と逐次 1 次元パス追跡において breakpoint の数を記録した結果を示した．多次元パス追跡の breakpoint 数が全体的にやや少ないが，CPU

ただし，I ∈ R

2×2

は単位行列である．n = 200, 300,

時間の差に対して breakpoint 数の差は比較的に小さい．

400, 500 として，初期の学習を t = 1, · · · , n/2 までのデータ点で行う．残りの n/2 個を 1 つずつ追加してモデルを更新していき（この時，同時に最古のデータ点が削ある方向を決めて一方向にパス追跡をする場合，各breakpoint での計算量が同じであるとすると，全体の計算コストは breakpoint の数にほぼ比例する．ただし，除されるため訓練データ数は常に n/2），1 つの追加あ

逐次 1 次元パス追跡は途中で方向を変える（動かす Ci

たりにかかった平均計算時間の比較を行う．x はそれぞを変える）ことになるため，breakpoint だけでなく探索れの次元を平均 0，分散 1 に正規化し，C = 100，RBF

幅 η のサーチ回数を考慮する必要がある．以降では，探2

カーネルのパラメータ σ = 1 とした．

索幅を得るための計算とパラメータの更新を合わせて探図 3 は計算時間の測定結果である．多次元パス追跡が

索幅サーチと呼ぶこととする (Algorithm 1 の 5 行目か全ての n で他の手法と比べて高速であるのが確認でき

ら 8 行目に相当)．breakpoint では探索幅のサーチと連る．また，どの手法も対数プロット上で n に対してほ立方程式の更新の 2 つが主な計算コストとなるが，目的

ぼ線形に時間が増加している．図 3 を表にしたものが表地に到達する最後の更新では探索幅サーチのみを行えばMulti-dimensional PathC2c(old)

3.2

時系列実データによる実験

Single-dimensional Pathborders of Critical Region

時系列実データによるオンライン学習での比較を行う．

Fisher river データ1 を用いて過去７日間の気温，降水量，川の水量 (x ∈ R21 ) から翌日の水量の増減 (y ∈ {1, −1})を予測する．x の各次元は平均 0 分散 1 に正規化し，初期データ数 n = 365 に対して計 365 個の新たなデータ点

(new)

c

を 1 つずつ追加する．正則化パラメータとカーネルパラ
メータを C ∈ {101 , 102 , 103 , 104 }, σ 2 ∈ {10−1 , 100 , 101 }の中でそれぞれ値を設定して結果を比較する．

C1

図 5 は各手法で 1 回の追加にかかった平均時間の対数
図 4: breakpoint 数とサーチ回数．図のパスにおいてはプロットである．多次元と逐次 1 次元パス追跡を比較す

多次元パス追跡では 2 回の breakpoint，3 回の探索幅

ると，C が小さく，σ が大きい時に多次元パス追跡の方サーチが発生するのに対して，逐次 1 次元パス追跡ではが速い．C が大きくなるとある程度までは逐次 1 次元パ

2 回の breakpoint，4 回のサーチが発生する．

スの計算時間が減り，両者の違いは小さくなる．SMO

連立方程式を更新する必要はない．この状況は多次元パとの関係については C が大きいほどパス追跡が有利でス追跡では c(new) に到達する最後の更新にだけ起こる

あった，また σ は大きいほど SMO はパス追跡と比較しが，逐次 1 次元パス追跡では 1 つの Ci に関するパス追て遅い．SMO と C の関係については C が大きい時に跡が終わるたびに発生する（図 4 に例を示した）．多次計算コストが大きくなることが知られている [17]．

元パス追跡，逐次 1 次元パス追跡についてそれぞれ，探表 5-7 には breakpoint 数を示した．小さい σ では

索幅サーチの回数を Sm , Ss ，breakpoint 数を Bm , Bs とbreakpoint 数にほとんど差はないが，σ の大きい表 7 では多次元と逐次 1 次元パス追跡に差が見られた．breakpoint が c のパス上に一様に分布していると仮定すると，して，逐次 1 次元パス追跡が p 回の 1 変数パス追跡を繰り返すとすると，Sm= Bm + 1,(15)p が大きい場合は多次元空間上で c(new) へ直線的に動く多次元パス追跡は，1 変数ずつ動かす逐次 1 次元パス

Ss

= Bs + p,(16)

追跡に比べて breakpoint は減少する．表 8-10 の探索幅
サーチの回数を見ると，多次元と逐次 1 次元パス追跡のといった関係がある．今回の実験では p は最大で n/2+1

breakpoint 数に差が大きい個所では逐次一次元のサーである．実際にサーチ回数を記録した結果を表 3 に示す．

チ回数が breakpoint に比べて大きい (p が大きい) 傾向

breakpoint 数と比べて多次元と逐次 1 次元パス追跡で大きな差が出ているのが確認できる．表 4 は多次元と逐次 1 次元パス追跡で計算時間の比とサーチ回数の比をが見られる．ただし，breakpoint の絶対数が少ない表 5
ではサーチ回数が多くとも breakpoint 数に差はあまり比較したものである．全ての n で 2 つの比に非常に近表 8-10 の探索幅サーチ回数については，全ての表にい値が確認されている．ここで，一回の探索幅サーチにおいて C が小さい時に多次元と逐次 1 次元パス追跡にかかる時間を TS ，連立方程式の更新にかかる時間を TL

大きな差が確認できる．ただし，逐次 1 次元パス追跡はとし，各繰り返しにおいて TS , TL は常に一定であるとC が大きくなるとサーチ回数が急激に減少し，多次元パ仮定すると初期化を除いた多次元パス追跡と逐次 1 次元ス追跡と同程度のサーチ回数となっている．これは逐次パス追跡の計算時間の比はおおよそ

1 次元パス追跡において実際に 1 変数パス追跡が行われ

Bm (TS + TL ) + TS : Bs (TS + TL ) + pTS ,

(17)

ない．

た回数 p が減少したためである．SVM において，ある程度以上 C を大きくすると上限 Ci に達する（もしくはとなるが，式 (17) がサーチ回数の比 Sm : Ss に等しい

近い値を持つ）ようなパラメータ αi は少なくなる．ことして整理するとの場合には，減少させる Ci について減少後の値 λCi がTS= 1,
TS + TL

αi より大きいことが多くなり Ci に関するパス追跡が不要となる．表 11-13 は多次元と逐次 1 次元パス追跡で計算時間の比とサーチ回数の比である．ほとんどの設定でとなるため，仮定のもとでは計算コスト比がサーチ回数比に近い場合は TL ≪ TS であると考えられる．

計算時間の比とサーチ回数の比は近い値を持っている．
1 StatLib http://lib.stat.cmu.edu/index.php から入手可能

10

4

10

4

10

10

10

3

2

1

10

1

10

2

10

3

10

10

10

10

4

MD-PathSD-PathSMO(1e-6)

3

CPU time (msec)

10

4

MD-PathSD-PathSMO(1e-6)
CPU time (msec)

CPU time (msec)

MD-PathSD-PathSMO(1e-6)

2

1

10

1

10

2

10

3

10

4

10

10

10

3

2

1

10

1

10

2

10

C

C

C

(a) σ 2 = 0.1(b) σ 2 = 1(c) σ 2 = 10

3

10

4

図 5: Fisher river データによる CPU 時間の比較 (MD-Path:多次元パス追跡，SD-Path:逐次 1 次元パス追跡)

表 5: σ 2 =0.1 の平均 breakpoint 数
method \ C
101
102
103
104
多次元
逐次 1 次元

3.20
3.24

3.07
2.02

3.07
2.01

3.08
2.01

表 6: σ 2 =1 の平均 breakpoint 数
method \ C
101
102
103
104
多次元
逐次 1 次元

10.06
16.82

8.76
11.85

9.83
9.21

9.52
8.77

表 7: σ 2 =10 の平均 breakpoint 数
method \ C
101
102
103
104
多次元
逐次 1 次元

4

32.43
66.59

31.13
61.85

27.05
46.51

29.08
36.44

まとめ
本稿では，重み付きカーネルマシンの多次元パス追跡

表 8: σ 2 =0.1 の平均サーチ回数
method \ C
101
102
103
104
多次元

4.20

4.07

4.07

4.08

逐次 1 次元

135.75

4.03

4.01

4.01

表 9: σ 2 =1 の平均サーチ回数
method \ C
101
102
103

104

多次元

11.06

9.76

10.83

10.52

逐次 1 次元

171.88

40.15

13.03

10.56

表 10: σ 2 =10 の平均サーチ回数
method \ C
101
102
103

104

多次元

33.43

32.13

28.05

30.08

逐次 1 次元

302.67223.67131.2264.02

A. Zapranis, “Financial time series modelling withdiscounted least squares backpropagation,” Neurocomputing, vol. 14, no. 2, pp. 123–138, 1997.

法を提案した．具体例として，SVM の個別正則化パラメータに関するパラメータ α, b の区分線形性を導出し，[3] L. Cao and F. Tay, “Support vector machine with

パス追跡によるモデルの連続的な変化の追跡が可能であadaptive parameters in ﬁnancial time series forecasting,” IEEE Transactions on Neural Networks,
vol. 14, no. 6, pp. 1506–1518, 2003.

ることを示した．計算機実験では多次元のパス追跡が 1
次元パス追跡の繰り返しや従来の SVM Solver より効率的であることを確認した．

参考文献[1] R. J. Carroll and D. Ruppert, Transformation andweighting in regression. London, UK, UK: Chapman & Hall, Ltd., 1988.
[2] A. Refenes, Y. Bentz, D. Bunn, A. Burgess, and[4] A. Kolcz and J. Alspector, “SVM-based ﬁlteringof e-mail spam with content-speciﬁc misclassiﬁcation costs,” in In Proceedings of the TextDM 01
Workshop on Text Mining - held at the 2001 IEEE
International Conference on Data Mining, 2001.
[5] V. N. Vapnik, The Nature of Statistical Learning
Theory. Springer-Verlag, 1995.

Computer Sciences, vol. E86-A, no. 8, pp. 1979–
1984, 2003.

表 11: σ 2 =0.1 の計算回数比とサーチ回数比

ratio \ C

101

102

103

104

計算時間比（一/多）

32.32
28.69

0.99
0.92

0.99
0.91

0.98
0.90

サーチ回数比（一/多）表 12: σ 2 =1 の計算回数比とサーチ回数比
ratio \ C
101
102
103
104
計算時間比（一/多）

15.54

4.11

1.20

1.00

サーチ回数比（一/多）

14.42

3.62

1.14

0.99

表 13: σ 2 =10 の計算回数比とサーチ回数比
ratio \ C
101
102
103
104
計算時間比（一/多）

9.05

6.96

4.68

2.13

サーチ回数比（一/多）

9.03

6.80

4.40

2.05

[6] T. Hastie, S. Rosset, R. Tibshirani, and J. Zhu,
“The entire regularization path for the support
vector machine,” Journal of Machine Learning
Research, vol. 5, pp. 1391–1415, 2004.
[7] T. Gal, Postoptimal Analysis, Parametric Programming, and Related Topics.
Walter de
Gruyter, 1995.
[8] E. N. Pistikopoulos, M. C. Georgiadis, and
V. Dua, Process Systems Engineering: Volume 1:
Multi-Parametric Programming. WILEY-VCH,
2007.
[9] X. Yang, Q. Song, and Y. Wang, “A weighted
support vector machine for data classiﬁcation,”International Journal of Pattern Recognition and
Artificial Intelligence, vol. 21, no. 5, pp. 961–976,
2007.
[10] C.-F. Lin and S.-D. Wang, “Fuzzy support vector machines,” IEEE Transactions on Neural Networks, vol. 13, no. 2, pp. 464–471, 2002.
[11] J. R. Schott, Matrix Analysis For Statistics.
Wiley-Interscience, 2005.
[12] G. H. Golub and C. F. Van Loan, Matrix computations. Baltimore, MD, USA: Johns Hopkins
University Press, 1996.
[13] F. Liu, T. Zhang, and R. Zhang, “Modiﬁed kernel RLS-SVM based multiuser detection over multipath channels,” IEICE Transactions on Fundamentals of Electronics, Communications and[14] H. Funaya, Y. Nomura, and K. Ikeda, “A support
vector machine with forgetting factor and its statistical properties,” in Proc. Intl. Conf on Neural
Information Processing (ICONIP 08).
[15] J. C. Platt, “Fast training of support vector machines using sequential minimal optimization,” inAdvances in Kernel Methods — Support Vector
Learning (B. Schölkopf, C. J. C. Burges, andA. J. Smola, eds.), (Cambridge, MA), pp. 185–
208, MIT Press, 1999.
[16] S. Keerthi, S. Shevade, C. Bhattacharyya, andK. Murthy, “Improvements to platt’s smo algorithm for svm classiﬁer design,” Neural Computation, vol. 13, no. 3, pp. 637–649, 2001.
[17] L. Bottou and C.-J. Lin, “Support vector machine
solvers,” in Large Scale Kernel Machines (L. Bottou, O. Chapelle, D. DeCoste, and J. Weston,eds.), pp. 301–320, Cambridge, MA.: MIT Press,
2007.
[18] D. DeCoste and K. Wagstaﬀ, “Alpha seeding for
support vector machines,” in Proceedings of theInternational Conference on Knowledge Discovery
and Data Mining, pp. 345–359, 2000.