社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS
信学技報
TECHNICAL REPORT OF IEICE.
Wolfe の最小ノルム点アルゴリズムによる SVM 学習
北村 昌士†
武田
朗子†
岩田
（注 †）
覚†
† 東京大学大学院情報理工学系研究科数理情報学専攻
113–8656 東京都文京区本郷 7–3–1
あらまし
本論文では, 凸多面体上のノルム最小点を有限回の反復で厳密に計算する Wolfe のアルゴリズムを, ヒンジ
ロス付き SVM の学習に適用する. 提案手法が, LIBSVM 等の既存手法よりも速く動作することを数値実験によって
示す. また, 元の問題の変種問題を解くことで高速化を図った LIBLINEAR と比較しても, サンプル数が特徴数より十
分多い時には, 提案手法の方が高精度の判別器を高速に構成することを数値実験で確認する.
キーワード
SVM, 最小ノルム点, Wolfe のアルゴリズム
Exact SVM Training by Wolfe’s Minimum Norm Point Algorithm
Masashi KITAMURA† , Akiko TAKEDA† , and Satoru IWATA†
† Department of Mathematical Informatics
Graduate School of Information Science and Technology
The University of Tokyo
Hongo 7–3–1, Bunkyo-ku, Tokyo 113–8656, Japan
1. は じ め に
行可能解は有限回の反復で最適解に到達し, Wolfe のアルゴリ
ズムは, 実際上も効率的なアルゴリズムであると言われている.
判別問題を解くために広く使われている機械学習の手法に
ただし, 部分集合の選び方は組合せの数だけあるので, Wolfe の
SVM がある. 本研究では, ヒンジロス付き SVM の構成に, 凸
アルゴリズムが多項式時間アルゴリズムであるかどうかは未解
多面体上のノルム最小点を求める Wolfe [21] のアルゴリズムが
決である.
利用できることを示す. 特に, サンプル数が特徴数よりも十分
に大きいとき, 既存手法と比べて, 提案手法の方が高速に動作す
ることを数値実験で確認する.
既存手法:
SVM の定式化の幾何的な解釈を利用したアル
ゴリズムは既に複数提案されている. Keerthi 等 [11] は, 二乗
ロスを用いた SVM をハードマージン SVM の定式化に変形し,
ヒンジロス付き SVM の定式化は, 二つの縮約凸包間で距離
その双対問題が凸包間で距離最小の点対を求める問題となるこ
最小の点対を求める問題として幾何的に解釈できる. この問題
とを指摘した. さらに, 距離最小の点対を求める古典的なアル
は, 二つの縮約凸包の Minkowski 差上で最小ノルム点を求め
ゴリズムである GSK アルゴリズムと MDM アルゴリズムを
る問題と等価である. Wolfe のアルゴリズムは, 凸多面体上の
組み合わせて適用する手法を提案している. 同時に, Wolfe の
線形最適化問題を繰り返し解くことによって最小ノルム点を得
アルゴリズムは, 大きなサイズのデータには向いていないと記
る. そこで, 本論文では, 線形最適化の効率的な方法を具体的に
されている. それ以来, Wolfe のアルゴリズムをハードマージ
与えることによって, Wolfe のアルゴリズムによるヒンジロス
ン SVM に利用することを提案した [17] を除いて，Wolfe のア
付き SVM 学習を実現する.
ルゴリズムは, SVM の解法としては殆ど使われてこなかった.
Wolfe のアルゴリズムは, 凸多面体上の端点集合の部分集合
C-SVM [5] や ν-SVM [17] といったヒンジロス付き SVM の
で構成される単体の中での最小ノルム点を暫定解とする組合せ
双対問題は, 縮約凸包間で距離最小の点対を求める問題として
的なアルゴリズムである. さらに, 暫定回のノルムが単調に小さ
解釈できる. この幾何的な解釈に基づいて, GSK アルゴリズム
くなっていくことから, 線形計画問題の単体法 [7] と同様に, 実
や MDM アルゴリズムを適用する手法が提案された [14], [19].
特に, [13] で提案されたクリッピング法は, 他の幾何的な解釈に
（注 1）
：本論文は, MLSP ’14 に採択された論文 [12] を元に加筆, 修正したもの
である.
基づくアルゴリズムより, 速く収束することが実験的に示され
ている. これらは全て, 局所改善を繰り返すことによって近似
—1—
解を得るアルゴリズムである.
ヒンジロス付き SVM 学習の別の流れとしては, 非線形最適
2. 準
備
化に基づく解法がある. 特に, 逐次極小最適化 (SMO) と呼ば
本節では, ν-SVM の双対問題が, 縮約凸包間で距離最小の点
れるアルゴリズムを用いた LIBSVM [4] は, 効率的な SVM 学
対を求める問題であることを紹介した後, Wolfe の最小ノルム
習のライブラリとして広く知られている.
点アルゴリズムを記述する.
SVM に関連して, 高次元特徴空間の取り扱いを可能とする
カーネル法 [17] が導入され, SVM の適用範囲は飛躍的に拡大し
2. 1 記
号
２値判別問題で学習するのは, f (x) := sign(w · x + b) の
には, 計算時間が莫大になるという難点がある. そこで, 取り扱
た だ し, sign(a) は, a >
= 0
の と き +1 を, そ う で な い 時 −1 を 返 す 関 数 で あ る. f
う対象を線形カーネルに限って高速化を図った解法も提案され
は x ∈ Rd を引数に取り, +1 か −1 を返す判別関数とな
てきた. 例えば, 確率勾配法に基づく Pegasos [18], 切除平面法
る.
た. しかし, 非線形カーネルには, 極めて大量のデータを扱う際
を用いた SVM
perf
[10], 座標降下法を用いた LIBLINEAR [8]
傾 き w と 定 数 項 b で あ る.
学 習 に 用 い る デ ー タ は, ベ ク ト ル xi ∈ Rd と ラ ベ ル
yi ∈ {−1, 1} の m 個のペア (xi , yi ) (i = 1, . . . , m) であ
る. そこで, S := {x1 , . . . , xm } と定義し, ラベルによって,
といったライブラリがある.
これらの線形カーネル SVM 学習ライブラリの効率の良さは,
S+ := {xi ∈ S | yi = +1}, S− := {xi ∈ S | yi = −1} とす
判別関数の h(x) = w · x + b において, b = 0 を仮定することと,
d
る. 一般に, 集合 A, B ⊂
=R に対して, 両者の Minkowski 差は
及び, 制約条件に ϵ > 0 までのずれを許容することに由来する.
A ⊖ B := {a − b | a ∈ A, b ∈ B} で定義される。
しかし, これらの仮定により得られる解は, 元の最適解とは異な
2. 2 ν-SVM の幾何的解釈
る. つまり, 正確さを犠牲にして収束性を改善している. これら
C-SVM [5] と ν-SVM [17] は, ヒンジロス付き SVM の標準
のライブラリの反復回数のオーダーは, Pegasos では O(1/ϵ),
的なものである. ハイパーパラメーターの C と ν を適切に定
SVMperf では O(1/ϵ2 ), LIBLINEAR では O(log(1/ϵ)) であ
めれば, この二つは同じ判別器を構成するので, 両者は本質的に
り, LIBLINEAR の優位性が示唆される. 実際, 数値実験の結
同じものである [17].
果でも, LIBLINEAR は, Pegasos や SVM
perf
と同等以上の性
能を有すると報告されている [8].
提案手法:
ν ∈ (0, 1] をハイパーパラメーターとし, η := 2/νm とする
と, ν-SVM の双対問題は以下のようになる [17]:
既存手法と異なり, Wolfe のアルゴリズムを用い
た提案手法は, 有限回の反復で最適解を得ることが理論的に保
証されている. これは, Wolfe のアルゴリズムが組合せ的な性
∑m ∑m
minimize
i=1
j=1
λi λj yi yj xi · xj
0<
= λi <
= η (i = 1, . . . , m),
∑m
∑m
i=1 λi = 2.
i=1 λi yi = 0,
subject to
質をもつことに起因する. また, 多項式時間アルゴリズムであ
(1)
るかどうかは未解決であるが, 実用的には高速に動作すること
最適解 (w∗ , b∗ ) を用いて, 判別関数 f (x) := sign(w∗ · x + b∗ )
が知られている.
を得ることができる. 最適化問題 (1) が最適解を持ち, f が意
Wolfe のアルゴリズムを線形カーネル SVM 学習に適用する
味のある判別関数となるためには, ν がある定数 νmin と νmax
場合, 特徴数の大きさの行列を保存する必要があるので, 大きな
の間の区間 (νmin , νmax ] になくてはならない [6].
サイズのデータには適していないと言われている [11]. 特に, 非
d
次に, (1) の幾何的解釈を紹介する. 集合 A⊂
=R に対し, ハ
イパーパラメーター η ∈ (0, 1] で定まる
{
}
∑
∑
<
<
RCHη (A) :=
λa a 0 = λa = η (a ∈ A),
λa = 1
線形カーネルを使用する多くの場合, この行列の大きさはサン
プル数と一致し, 非常に大きくなり得る. このことから, Wolfe
のアルゴリズムは SVM 学習に適してないように見える. しか
a∈A
し, 本研究では, 線形カーネルを用いた実験により, 提案手法
が, 他の幾何的な解釈に基づくアルゴリズムや LIBSVM より
a∈A
を, A の縮約凸包と呼ぶ. 最適化問題 (1) は,
速く動作することを明らかにした. また, 多項式カーネルの様
に, カーネル行列のランクが低ければ, 行列分解を用いること
で, 同様のことが言えることを確認した.
minimize
∥z+ − z− ∥2
subject to
z+ ∈ RCHη (S+ ),
z− ∈ RCHη (S− )
提案手法は, サンプル数が特徴数に比べて十分大きい時には,
LIBLINEAR より高速に動く. また, LIBLINEAR は, ヒンジ
ロス付き SVM の定式化の変種問題を解いているので, 元の問
題を直接解いている既存手法の方が, 多くの場合良い予測性能
を持つ.
本論文の構成:
第 2 節では, SVM と Wolfe のアルゴリズ
ムを簡単に紹介する. 次に, 第 3 節で, Wolfe のアルゴリズム
(2)
と書き直すことができる [2], [6].
Minkowski 差 R⊖ := RCHη (S+ ) ⊖ RCHη (S− ) を用いて,
(2) を
minimize
∥z∥2
subject to
z ∈ R⊖
(3)
の線形カーネル ν-SVM への適用方法を示す. さらに, 第 4 節
と書き直すこともできる. 縮約凸包 RCHη (S± ) が凸多面体な
で, 非線形カーネルの場合を検討する. 続いて, 第 5 節で, 高速
ので, R⊖ も凸多面体である. 以上から, 多面体 R⊖ 上の最小ノ
化技法を提案する. 最後に, 第 6 節で, 数値実験の結果を示す.
ルム問題 (3) を解くことにより, 判別関数を得ることができる.
—2—
Optimization(z, R⊖ ) が実現できることを確かめればよい.
Algorithm 1 Wolfe’s algorithm
Input: a polytope P .
z := an arbitrary vector in P and I := {z}.
loop
v ∗ := Optimization(z, P ).
if z · z − z · v ∗ = 0 or v ∗ ∈ I then return z.
I := I ∪ {v ∗ }.
loop
p := Projection(I).
if p is in the relative interior of CH(I) then
z := p and break.
end if
z := Intersection(I, p, z).
I := Reduction(I, z).
end loop
end loop
d
有 限 集 合 A⊂
=R を 用 い て P := RCHη (A) と 表 せ
る な ら ば, [14], [19] で 示 唆 さ れ た Algorithm 2 に よ り,
Optimization(z, P ) を実現することができる. この事実を用
いて, Optimization(z, R⊖ ) を実現する方法とその計算時間を以
下に示す.
∈
命 題 1. 任 意 の ベ ク ト ル z
Rd に 対 し, v ∗
∈
argmin {z · v | v ∈ R⊖ } を O(md + m lg m) 時間で計算するこ
とができる.
証明.
縮約凸包上での線形最適化 Optimization(z, RCHη (S+ ))
∗
∗
と
, v−
と Optimization(−z, RCHη (S− )) の出力をそれぞれ v+
∗
∗
と置く. すると, v+ ∈ RCHη (S+ ) と
− v−
し, v ∗ := v+
Algorithm 2 Optimization(z, RCHη (A))
t := ⌈1/η⌉.
sort i such that z · aσ(i) <
= z · aσ(i+1) (i = 1, . . . , |A| − 1)
(break ties arbitrarily), where σ is an ordering of indices.
λi := η (σ(i) = 1, . . . , t − 1).
λi := 1 − (t − 1)η (σ(i) = t).
λi := 0 (σ(i) = t + 1, . . . , |A|).
∑
v ∗ := |A|
i=1 λi ai .
return v ∗ .
v− ∈ RCHη (S− ) を満たす任意のベクトル v := v+ − v− に対
∗
∗ <
− z · v−
し, z · v ∗ = z · v+
= z · v+ − z · v− = z · v が成り立つ.
よって, v ∗ ∈ argmin {z · v | v ∈ R⊖ } となる.
以上の手続きは, m 回の内積計算と, 長さが高々 m の配列の
ソート 2 回から成り, O(md + m lg m) 時間で実行できる. □
4. 非線形カーネルの場合
本節では, 一般の非線形カーネルを用いた ν-SVM 学習に
Wolfe のアルゴリズムを適用する方法を検討する.
2. 3 Wolfe のアルゴリズム
カーネル関数 k(·, ·) を用いた ν-SVM は, (1) において xi · xj
凸多面体上の最小ノルム点を求める Wolfe [21] のアルゴリズ
d
ムを概述する. Wolfe のアルゴリズムでは, 凸多面体に P ⊂
=R
に対する最小ノルム点問題
minimize
∥z∥2
subject to
z∈P
を k(xi , xj ) に置き換えることで得られる. 第 (i, j) 成分が
k(xi , xj ) である半正定値対称行列 K ∈ Rm×m をカーネル行
列と呼ぶ. 第 i 成分が 1 である単位ベクトル ei ∈ Rm を用い
て, E+ := {ei | yi = +1}, E− := {ei | yi = −1} とおく. この
(4)
とき, ν-SVM の双対問題は
を解く. アルゴリズムの全体は, Algorithm 1 である (CH は凸
minimize
(λ+ − λ− )⊤ K(λ+ − λ− )
包を表す). Wolfe のアルゴリズムでは, 次の四つの手続きを必
subject to
λ+ ∈ RCHη (E+ ),
(5)
λ− ∈ RCHη (E− )
要とする.
•
Optimization(z, P ): z · v が最小の点 z ∈ P を返す.
•
と書き直せる. さらに, λ := λ+ − λ− , E⊖ := RCHη (E+ ) ⊖
Projection(I): I のアファイン包上のノルム最小点を
RCHη (E− ) と置き換えることで, (5) の目的関数を λ⊤ Kλ, 制
返す.
•
約条件を λ ∈ E⊖ と表せる. その上で, カーネル行列 K を Rm
Intersection(I, p, z): I の凸包と線分 pz の共通部分で最
も p に近い点を返す.
•
Reduction(I, p): p が I ′ の凸包の相対的内点となる I の
上の計量と解釈して, u, v ∈ Rm の内積を u · v := u⊤ Kv で定
√
め, u ∈ Rm のノルムを ∥u∥K := u⊤ Ku で与える. その結
果, (5) は
真部分集合 I ′ で極小のものを返す.
Optimization(z, P ) の実現は, P がどのような形で与えられ
d
るかに依る. 有限集合 A⊂
=R を用いて P := CH(A) と表され
るならば, 全ての a ∈ A に対して z · a を計算し, ソートを行う
ことによって, O(|A|d + |A| lg |A|) 時間で Optimization(z, P )
を実行できる. 他の手続きについては [21] に書かれている.
Projection(I) を実行するためには, O(d2 ) のメモリ空間が必要
であることに注意する.
minimize
∥λ∥2K
subject to
λ ∈ E⊖
(6)
と変形できる. Minkowski 差 E⊖ は凸多面体なので, (6) は (4)
の特殊ケースとなる. 新たに定義したノルムと内積を用いた
Wolfe のアルゴリズムを P := E⊖ に適用することによって,
(6) の最適解が得られる.
このように, 非線形カーネルの場合でも, SVM 学習に Wolfe
のアルゴリズムを適用できる. ただし, O(m2 ) のメモリ空間が
3. 線形カーネルの場合
必要なことに注意する.
本節では, Wolfe のアルゴリズムによって, 縮約凸包間で
距 離 最 小 の 点 対 を 計 算 で き る こ と を 示 す.
そ の た め に は,
—3—
高速に動作する.
5. 高 速 化
6. 1 比 較 対 象
5. 1 選択アルゴリズム
LIBSVM (LS) は, C-SVM （ ν-SVM ）を解く定番ライブ
Optimization(z, RCHη (S)) は, ソートを用いて実現できる
が, 実は, z · xi の順序全てを知る必要はない. 置換 σ を
ラリである. C-SVM と ν-SVM は, ハイパーパラメーターを
適切に設定すれば, 本質的に同じ問題となる [17].
z · xσ(i) <
= z · xσ(i+1) (i = 1, . . . , m − 1) を満たすように定め,
t := ⌈1/η⌉ とする. 点 xσ(t) の係数 λσ(t) に 1 − (t − 1)η を割り
リである. LIBILENAR は, 線形カーネル SVM しか扱うこと
当て, 点 xσ(j) (j = 1, · · · , t − 1) の係数 λj に η を割り当てれ
ができない. LIBLINEAR の判別関数は, 定数項 b を持ってい
ば, 最適解を得られる. 従って, σ(t) と集合 Jt := {σ(j) | j < t}
ないが, w の最後の要素に b を付け加え, 全てのデータ xi の最
さえ見つければ良い. 実際, ソートを用いることなく, σ(t) を
後の要素に 1 を付け加えることで, 定数項 b を判別関数に持た
O(m) 時間で見つけるアルゴリズムが知られている [3]. さらに,
せることができる [8]. この定数項を付け加えた方法を, LLB と
σ(t) が分かっているならば, Jt も O(m) 時間で得られる. こう
呼ぶことにする.
して, 命題 1 の計算量は, O(md) に改善できる. ただし, 非線
形カーネルを使う場合は, d が m になることに注意する.
LIBLINEAR (LL) は, C-SVM の変種問題を解くライブラ
ν-SVM を解く別の方法として, MDM アルゴリズム [15] に
クリッピングという技法を用いた ClipMDM (CM) [13] があ
5. 2 並 列 化
る. このアルゴリズムは, 各反復で, 現在の実行可能解 z におい
Optimization(z, RCHη (S)) を実行するとき, 全ての xi ∈ S
て最も勾配の急な方向を探し, その方向に沿って z を実行可能
に対して, z · xi を計算する必要があった. しかし, i =
| j を満た
領域内で動かす. 各反復でのカーネル関数の評価は O(m) 回で
すとき, z · xi と z · xj の計算は無関係なので, 並列計算を行う
よい.
ことができる.
6. 2 諸 条 件
5. 3 カーネル行列分解
ClipMDM と Wolfe のアルゴリズムでは, 初期解を設定す
非線形カーネルを使うとき, 実行可能領域が m 次元である
る必要がある. ClipMDM では, 重心ベクトルを初期解とした.
(6) を解く必要がある. カーネル行列のランクが小さければ, こ
Wolfe のアルゴリズムでは, Optimization において, z · xi の代
の次元を下げることができる.
わりに ∥xi ∥2 でソートを行って得られたものを初期解とした.
カーネル行列 K のランクを r とすると, r × m の行列 Z を
⊤
LIBSVM と LIBLINEAR では, 制約条件のずれを ϵ = 10−9
用いて, K = Z Z とコレスキー分解することができる, (6) は
まで許容し, ClipMDM と Wolfe のアルゴリズムでは, 目的関
以下のように書き換えられる:
数のずれを 10−10 までを許容した. ClipMDM と Wolfe のア
minimize
subject to
ルゴリズム を C# で実装したので, C で実装された LIBSVM
(Zλ)⊤ (Zλ)
(7)
λ ∈ E⊖ .
や LIBLINEAR と比べると, 少し不利になっている.
線形カーネル ν-SVM 学習に当たって, Wolfe のアルゴリズム
さらに, Z の第 i 列ベクトルを zi とし, Z+ := {zi | yi = +1},
では, ３種類の変種を用意した. Wolfe-Sort (WSo) は, 線形最
Z− := {zi | yi = −1} とすると, (7) は
適化 Optimization においてソートを用いるものである. Wolfe-
minimize
subject to
Select (WSe) は, ソートの代わりに選択アルゴリズムを用いて
∥z∥2
z ∈ RCHη (Z+ ) ⊖ RCHη (Z− )
と書き直せる. これは, {(zi , yi ) | i = 1, . . . , m}⊂
=R × {−1, 1}
をデータとして持つ線形カーネルの問題であるとみなせる.
r
2
実装したものである. Wolfe-Parallel (WPa) は Wolfe-Select
を並列化したものである. Wolfe-Select では, 決定性アルゴリ
ズム [3] ではなく, 乱択アルゴリズム [16] を用いた.
非線形カーネルの場合でも, Wolfe のアルゴリズムの変種
カーネル行列 K の分解には O(m r) 時間が一度必要である.
を３種類用意した. Wolfe-Kernel (WKe) は, Wolfe-Select の
しかし, 一度分解してしまえば, ν を変えて繰り返し ν-SVM を
非線形カーネル版であり, (6) を解く. Wolfe-Decomposition
解く場合でも, 再び分解を行う必要はないので, r が m に比べ
(WDe) は, 各 ν でカーネル行列の分解を行い, (7) を解く.
て十分小さいとき, この方針は有用なものとなり得る.
Wolfe-Preprocessing (WPr) では, カーネル行列 K が, Z ⊤ Z
ランク r が小さくなるカーネルとして典型的なものは, 多項
式カーネルである. 多項式カーネルの次元を g とすると, r は
高々 d Hg = d+g−1 Cd となる.
6. 数 値 実 験
本節では, 数値実験により, 提案手法の性能を調べる. 実験結
と分解された形で与えられているものとして問題を解く.
実験は, 8GB のメモリを搭載した Intel(R) Core(TM) i7-
3770 3.40GHz を用いて行った. 並列化の時に使用したコア数
は 4 である.
6. 3 入力データ
人工データ:
人工データの生成方法について述べる. m, d
果から, 線形カーネル SVM に関して, データ数 m が 特徴数 d
をそれぞれサンプル数, 特徴数とする. ただし, m は偶数である
より十分大きければ, 実験対象のアルゴリズムの中では, 提案手
とする. 標準正規分布にしたがって生成された m/2 個のサン
法が最も高速に動作する. 非線形カーネルを用いた場合, カー
プルを用意し, それらのラベルを +1 とする. 平均ベクトルを
√
1.5/ d(1, . . . 1)⊤ , 分散共分散行列を, 固有値が全て [0.12 , 1.52 ]
ネル行列のランクが低い時には, 提案手法が LIBSVM よりも
—4—
に含まれるランダム行列とし, これらを用いて正規分布にした
表 1 サンプル数と特徴数
がって発生させた m/2 個のサンプルには, ラベル −1 をつけ
る. こうして得られた m 個のサンプルを人工データとする.
実データ:
実験で用いた実データは, svmguide1 [9], code-
rna [20], covtype [1], diabetes [1], heart [1] である. サンプル
数, テスト数, 特徴数は, 表 1 にある. cod-rna と covtype の元
データ名
サンプル数
テスト数
特徴数
svmguide1
3,089
4,000
4
cod-rna
53,581
5,954
8
covtype
522,910
58,102
54
diabetes
768
8
heart
270
13
のデータは, テストサンプルを含んでいなかったので, 元のデー
タから無作為に選んだ 90% を学習に用い, 残りの 10% をテス
トデータとして使用した.
いる. 実際上, 最も正答率の高い ν を見つけるために, 多数の ν
について問題を解く必要があるので, どんな ν に対しても, あ
6. 4 数 値 実 験
線形カーネル（人工データ）: 人工データを用いた数値実験
によって, 線形カーネル ν-SVM に対する提案手法の漸近的な
計算時間を調べた. ハイパーパラメーターとして ν := 0.8 を用
い, LIBSVM, LIBLINEAR では, それに対応する C を使った.
実行時間を計測した結果を図 1 に示す. 左側のグラフは, 特徴
数を d = 10 に固定し, サンプル数を m を変化させたときの実
行時間を表す. 右側のグラフは, サンプル数を m = 5, 000 に固
定し, 特徴数を d を変化させた時の実行時間を表す.
ほぼ全ての場合で, Wolfe のアルゴリズムが, LIBLINEAR,
LIBSVM, ClipMDM よりも高速に動作している. 左側のグラ
フを見ると, Wolfe-Select は Wolfe-Sort より約 2 倍速く動作
している. また, Wolfe-Parallel は Wolfe-Select より約 1.2 倍
速く動作している. このことから, 第 5 節で述べた高速化技法
が有効であることが示唆される. 右側のグラフでは, d が大きく
なるにつれて, Wolfe のアルゴリズムと LIBLINEAR の差は縮
まっていくが, d = 1, 000 の場合でも, Wolfe のアルゴリズムの
方が高速である. 閾値は d = 2, 000 あたりであると読み取れる.
まり時間がかからないことが重要である. svmguide1 において,
Wolfe のアルゴリズムは, ほとんどの ν に対して LIBLINEAR
より遅くなっているが, 平均で比較するとさほど差があるとは
言えない.
非線形カーネル（実データ）:
非線形カーネルを用いた時
の実行時間を, 実データ diabetes, heart を用いて調べる. 実験
では, 多項式カーネル k(u, v) := (u · v)g /d と RBF カーネル
k(u, v) := exp(−∥u − v∥2 /γ) を用いた. パラメーターとして,
多項式カーネルの次数は g = 2 とし, RBF カーネルの γ は
2, 000 とした. 多項式カーネルを用いた時, カーネル行列のラン
クは d Hg (= 36, 91) と m(= 768, 270) より小さくなっていた
が, RBF カーネルを用いた時のランクは m(= 768, 270) であっ
た. 図 4 と図 5 から, 次元の低い多項式カーネルでは, Wolfe
のアルゴリズムが LIBSVM より高速だが, RBF カーネルを用
いたときは, LIBSVM の方が速くなっている. 第 5.3. で述べ
たように, カーネルのランクが低い場合に, 提案手法が有用であ
ることが分かった.
特徴数 d を固定したとき, Wolfe-Select の実行時間は m1.0
に比例し, LIBLINEAR は m1.3 に比例する. サンプル数 m を
固定したとき, Wolfe-Select の実行時間は d1.5 に比例し, LIB-
7. む す び
LINEAR は d0.9 に比例する. サンプル数 m が, 特徴数 d に比
本論文では, Wolfe のアルゴリズムを ν-SVM に適用した. 数
べて十分大きい時には, Wolfe のアルゴリズムが, LIBLINEAR
値実験によって, サンプル数が特徴数に比べて十分大きい時に,
よりも高速に動作することが示唆される.
Wolfe のアルゴリズムが高速に動作すること, 高精度な判別器
線形カーネル（実データ）:
線形カーネルを用いて, 実デー
タ svmguide1, cod-rna, covtype に対して, 実行時間, 正答率
を調べ, 実データに対しても提案手法が有用であることを確か
めた. 表 1 にあるように, cod-rna と covtype のサンプル数は
特徴数と比べて十分に大きい. ν-SVM（ C-SVM ）の学習に要
した時間を計測した後, テストデータに対する正答率を調べた.
図 2 は実行時間を計測した結果で, 図 3 は正答率を調べた結
果である. 収束までに時間が掛かりすぎるので, ClipMDM の
適用対象から cod-rna と covtype を除き, LIBSVM の適用対
象から covtype を除いた. 同じ問題を解いているので, Wolfe
のアルゴリズム, ClipMDM, LIBSVM は, 同じ正答率を持って
いる. これらは, 最良の ν を設定した時に, LIBLINEAR より
も良い予測性能を出した.
cod-rna と covtype においては, Wolfe のアルゴリズムが, ど
の ν においても最も速く動作している. 特に, cod-rna におい
て, Wolfe のアルゴリズムの実行時間は, いずれも 1 秒以下で
あるが, LIBLINEAR の計算時間は最悪ケースで 7 秒に達して
を構成すること, 高速化の技法が有効に機能していることを確
かめた.
文
献
[1] K. Bache and M. Lichman. UCI machine learning repository, 2013.
[2] K. P. Bennett and E. J. Bredensteiner. Duality and geometry in SVM classifiers. In Proceedings of the 17th International Conference on Machine Learning, pages 57–64.
Morgan Kaufmann, 2000.
[3] M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E.
Tarjan. Time bounds for selection. Journal of Computer
and System Sciences, 7:448–461, 1973.
[4] C. C. Chang and C. J. Lin. LIBSVM: A library for support
vector machines. Technical report, 2011.
[5] C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20:273–297, 1995.
[6] D. J. Crisp and C. J. C. Burges. A geometric interpretation
of ν-SVM classifiers. In Advances in Neural Information
Processing Systems. MIT Press, Cambridge, MA, 2000.
[7] G. B. Dantzig. Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.
[8] R. E. Fan, K. W. Chang, C. J. Hsieh, X. R. Wang, and C. J.
—5—
図 1 人工データでの実験
図2
線形カーネルでの実行時間
図 3 線形カーネルでの正答率
図 4 多項式カーネルでの実行時間
Lin. LIBLINEAR: A library for large linear classification.
Journal of Machine Learning Research, 9:1871–1874, 2008.
[9] C. W. Hsu, C. C. Chang, and C. J. Lin. A practical guide to
support vector classification. Technical report, Department
of Computer Science, National Taiwan University, 2003.
[10] T. Joachims. Training linear svms in linear time. In Proceedings of the ACM Conference on Knowledge Discovery
and Data Mining (KDD), 2006.
[11] S. S. Keerthi, S. K. Shevade, C. Bhattacharya, and K. R. K.
Murthy. A fast iterative nearest point algorithm for sup-
—6—
図 5 RBF カーネルでの実行時間
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
port vector machine classifier design. IEEE Transactions
on Neural Networks, 11:124–136, 2000.
M. Kitamura, A. Takeda, and S. Iwata. Exact SVM training
by Wolfe’s minimum norm point algorithm. In Proceedings
of 2014 IEEE International Workshop on Machine Learning for Signal Processing, 2014.
´ Barbero, and J. R. Dorronsoro. Clipping algoJ. L´
opez, A.
rithms for solving the nearest point problem over reduced
convex hulls. Pattern Recognition, 44:607–614, 2011.
M. E. Mavroforakis and S. Theodoridis. A geometric approach to support vector machine (SVM) classification.
IEEE Transactions on Neural Networks, 17:671–682, 2006.
B. F. Mitchell, V. F. Dem’yanov, and V. N. Malozemov.
Finding the point of a polyhedron closest to the origin.
SIAM Journal on Control, 12(1):19–26, 1974.
R. Motwani and P. Raghavan, editors. Randomized Algorithms. Cambridge University Press, 1995.
B. Sch¨
olkopf, A. J. Smola, R. C. Williamson, and P. L.
Bartlett. New support vector algorithms. Neural Computation, 12:1207–1245, 2000.
S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: Primal estimated sub-gradient solver for svm. In Proceedings
of the 24th International Conference on Machine Learning,
2007.
Q. Tao, G.W. Wu, and J. Wang. A generalized S-K algorithm for learning ν-SVM classifiers. Pattern Recognition
Letters, 25(10):1165–1171, 2004.
A. V. Uzilov, J. M. Keegan, and D. H Mathews. Detection
of non-coding RNAs on the basis of predicted secondary
structure formation free energy change. BMC Bioinformatics, 7(173), 2006.
P. Wolfe. Finding the nearest point in a polytope. Mathematical Programming, 11:128–149, 1976.
—7—
© Copyright 2024 ExpyDoc
