w - 情報論的学習理論と機械学習 (IBISML)

大規模機械学習のための
事例と特徴のセーフスクリーニング
竹内一郎
名古屋工業大学
本日の講演内容の一部は以下の方々との共同研究です
小川晃平，鈴木良規，中川和也，津田宏治，烏山昌幸，奥村翔太，柴垣篤志（敬称略）
I. Takeuchi, Nagoya Institute of Technology
1/38
スパースモデリング
▶
線形モデル
f (x) = w1 x1 + w2 x2 + . . . + wd xd
▶
カーネルモデル
f (x) = α1 K(x, x1 ) + α2 K(x, x2 ) + . . . + αn K(x, xn )
▶
スパースモデリング
▶
{wj }dj=1 の一部が零（一部の特徴のみで f を表現）
▶
{αi }ni=1 の一部が零（一部の事例のみで f を表現）
I. Takeuchi, Nagoya Institute of Technology
2/38
スパースモデリングの例
▶
LASSO（L1 正則化による特徴のスパース化）
w∗ := arg min λ ∥w∥1 +
| {z }
w∈Rd
L1 正則化
n
∑
(yi − f (xi ))2
i=1
（λ > 0 は正則化パラメータ）
▶
SVM（ヒンジ損失関数による事例のスパース化）
∑
1 ⊤
max{0, 1 − yi f (xi )}
α Kα + C
|
{z
}
2
n
α∗ := arg minn
α∈R
i=1
ヒンジ損失関数
（C > 0 は正則化パラメータ，K はカーネル行列）
I. Takeuchi, Nagoya Institute of Technology
3/38
スパース学習の計算コストとスクリーニング
▶
▶
スパース学習の計算コスト
▶
学習後の最適解において，どの wj やどの αi が零とな
るかわからない
▶
スパース学習の計算コストはオリジナルの次元数 d や
事例数 n に依存する
スクリーニングによる高速化
▶
学習前に wj = 0 となる特徴や αi = 0 となる事例を推
定/同定することをスクリーニングと呼ぶ
▶
これらの特徴や事例を訓練集合から除去することによ
り効率的な学習が可能となる
I. Takeuchi, Nagoya Institute of Technology
4/38
ヒューリスティクスと安全スクリーニング
▶
ヒューリスティクス
wj = 0 となる特徴や αi = 0 となる事例を推測して取り除き，
学習後に最適性を確認
▶
▶
Sure independence screening
▶
Shrinking option in libsvm
(Fan et al., 2007)
(Fan et al., 2005)
安全スクリーニング（safe screening）
wj = 0 や αi = 0 となることが保障された特徴や事例を取り
除く（最適性の確認は不要）
▶
安全特徴スクリーニング
(El Ghaoui et al., 2012)
▶
安全事例スクリーニング
(Ogawa et al., 2013)
I. Takeuchi, Nagoya Institute of Technology
5/38
本日の講演内容
▶
Part 1：SVM の安全事例スクリーニング
Ogawa, Suzuki, and Takeuchi. Safe screening of non-support vectors in
pathwise SVM computation. ICML2013.
▶
Part 2：高次交互作用モデルの安全特徴スクリーニング
Nakagawa, Suzumura, Karasuyama, Tsuda, and Takeuchi. Safe feature pruning
for sparse high-order interaction models. arXiv:1506.08002.
▶
Part 3：安全スクリーニング技術の応用
▶
感度分析
Okumura, Suzuki, and Takeuchi. Quick sensitivity analysis for
incremental data modification. KDD2015.
▶
モデル選択
Shibagaki, Suzuki, Karasuyama, and Takeuchi. Regularization Path of
Cross-Validation Error Lower Bounds. NIPS2015.
I. Takeuchi, Nagoya Institute of Technology
6/38
Part 1
SVM の安全事例スクリーニング
I. Takeuchi, Nagoya Institute of Technology
7/38
SVM の安全事例スクリーニングの例
2
x2
1
0
-1
-2
-3
-2
-1
0
x1
1
2
Before safe screening
人工データ (n = 1000 and d = 2)
I. Takeuchi, Nagoya Institute of Technology
8/38
SVM の安全事例スクリーニングの例
[
[
Before safe screening
人工データ (n = 1000 and d = 2)
I. Takeuchi, Nagoya Institute of Technology
8/38
2
1
0
[
x2
SVM の安全事例スクリーニングの例
-1
-2
-3
-2
-1
0
x1
1
2
Before safe screening
[
After safe screening
人工データ (n = 1000 and d = 2)
I. Takeuchi, Nagoya Institute of Technology
8/38
[
[
SVM の安全事例スクリーニングの例
[
Before safe screening
[
After safe screening
人工データ (n = 1000 and d = 2)
I. Takeuchi, Nagoya Institute of Technology
8/38
[
[
SVM の安全事例スクリーニングの例
[
Before safe screening
[
After safe screening
人工データ (n = 1000 and d = 2)
事例を削除しても解の最適性が保障される
I. Takeuchi, Nagoya Institute of Technology
8/38
サポートベクトルと非サポートベクトル
▶
SVM の分類規則
{
−1 if f (x) < 0,
ŷ =
+1 if f (x) ≥ 0,
f (x) = w∗⊤ x =
n
∑
αi∗ yi K(x, xi )
i=1
主形式
双対形式
ただし，{(xi , yi )}ni=1 は訓練事例集合
▶
SVM は事例に関してスパース
αi∗ = 0 ⇒ 分類関数 f に影響を与えない ⇒ 非 SV
I. Takeuchi, Nagoya Institute of Technology
9/38
マージンと非サポートベクトル
4
• サポートベクトル (SVs)
*
2
X2
0
事例スパース
*
−2
−1
*
*
*
−3
◦ ◦: yi f (xi ) > 1 ⇒ αi = 0
|
{z
}
*
* *
*
*
**
*
*
* **** * * *
*
*
*
*** * *
* ***
* *
* *
*
*
**
* *
** * *
**
*
*
*
*
*
1
• •: yi f (xi ) = 1 ⇒ αi ∈ [0, C]
• 非サポートベクトル (non-SVs)
*
3
⋆ ⋆: yi f (xi ) < 1 ⇒ αi = C
*
*
−3
−2
−1
0
1
2
3
X1
事前に最適解 w∗ において，
yi f (xi ) = (yi xi )⊤ w∗ > 1
が成り立つことがわかれば，事例 (xi , yi ) を捨ててもよい
I. Takeuchi, Nagoya Institute of Technology
10/38
安全事例スクリーニングの基本アイデア１
▶
主問題の解空間 Rd において，最適解 w∗ は未知だが，最適
解を含む球 B
w∗ ∈ B := {w ∥w − m∥ ≤ r},
が既知である状況を考える（m：中心，r：半径）
I. Takeuchi, Nagoya Institute of Technology
11/38
安全事例スクリーニングの基本アイデア１
▶
主問題の解空間 Rd において，最適解 w∗ は未知だが，最適
解を含む球 B
w∗ ∈ B := {w ∥w − m∥ ≤ r},
が既知である状況を考える（m：中心，r：半径）
I. Takeuchi, Nagoya Institute of Technology
11/38
安全事例スクリーニングの基本アイデア１
▶
主問題の解空間 Rd において，最適解 w∗ は未知だが，最適
解を含む球 B
w∗ ∈ B := {w ∥w − m∥ ≤ r},
が既知である状況を考える（m：中心，r：半径）
I. Takeuchi, Nagoya Institute of Technology
11/38
安全事例スクリーニングの基本アイデア２
▶
マージン yi f (xi ) = (yi xi )⊤ w∗ の下限と上限：
下限： (yi xi )⊤ w∗ ≥ min (yi xi )⊤ w = (yi xi )⊤ m − ∥yi xi ∥r,
w∈B
⊤
∗
上限： (yi xi ) w ≤ max(yi xi )⊤ w = (yi xi )⊤ m + ∥yi xi ∥r
w∈B
I. Takeuchi, Nagoya Institute of Technology
12/38
安全事例スクリーニングの基本アイデア２
▶
マージン yi f (xi ) = (yi xi )⊤ w∗ の下限と上限：
下限： (yi xi )⊤ w∗ ≥ min (yi xi )⊤ w = (yi xi )⊤ m − ∥yi xi ∥r,
w∈B
⊤
∗
上限： (yi xi ) w ≤ max(yi xi )⊤ w = (yi xi )⊤ m + ∥yi xi ∥r
w∈B
I. Takeuchi, Nagoya Institute of Technology
12/38
安全事例スクリーニングの基本アイデア２
▶
マージン yi f (xi ) = (yi xi )⊤ w∗ の下限と上限：
下限： (yi xi )⊤ w∗ ≥ min (yi xi )⊤ w = (yi xi )⊤ m − ∥yi xi ∥r,
w∈B
⊤
∗
上限： (yi xi ) w ≤ max(yi xi )⊤ w = (yi xi )⊤ m + ∥yi xi ∥r
w∈B
I. Takeuchi, Nagoya Institute of Technology
12/38
安全事例スクリーニングの基本アイデア３
最適解 w∗ が球 B に含まれている，すなわち，w∗ ∈ B ならば，
min(yi xi )⊤ w > 1 ⇒ (yi xi )⊤ w∗ > 1 ⇒ αi∗ = 0
|
{z
}
|
{z
}
| {z }
w∈B
マージンの下限>1
マージン>1
非 SV
最適解 w∗ が未知であっても，最適解を含む
球 B が既知であれば，非 SV を同定できる！
I. Takeuchi, Nagoya Institute of Technology
13/38
最適解を含む球（定理）
▶
以下のクラスの最適化問題（SVM を含む）を考える：
∑
1
w := arg min J(w) := ∥w∥2 + C
ℓi (w).
2
w∈Rd
n
∗
i=1
ただし，ℓi (w) := ℓ(yi , x⊤
i w) は凸な損失関数とする．
▶
任意の ∈ Rd に対し，最適解 w∗ は以下の球に含まれる：
{ }
w∗ ∈ B := w ∥w − m∥ ≤ r .
ただし，球の中心と半径は，∇ℓi () ∈ Rd を ℓi のにおける
任意の劣勾配すると，以下のように与えられる：
(
)
n
n
∑
∑
1
1
m :=
−C
∇ℓi () , r := + C
∇ℓi () .
2
2
i=1
I. Takeuchi, Nagoya Institute of Technology
i=1
14/38
最適解を含む球（定理）
▶
以下のクラスの最適化問題（SVM を含む）を考える：
∑
1
w := arg min J(w) := ∥w∥2 + C
ℓi (w).
2
w∈Rd
n
∗
i=1
ただし，ℓi (w) := ℓ(yi , x⊤
i w) は凸な損失関数とする．
▶
任意の w̃ ∈ Rd に対し，最適解 w∗ は以下の球に含まれる：
{ }
w∗ ∈ B := w ∥w − m∥ ≤ r .
ただし，球の中心と半径は，∇ℓi (w̃) ∈ Rd を ℓi の w̃ におけ
る任意の劣勾配すると，以下のように与えられる：
(
)
n
n
∑
∑
1
1
m :=
w̃ − C
∇ℓi (w̃) , r := w̃ + C
∇ℓi (w̃) .
2
2
i=1
I. Takeuchi, Nagoya Institute of Technology
i=1
14/38
最適解を含む球（定理）
▶
以下のクラスの最適化問題（SVM を含む）を考える：
∑
1
w := arg min J(w) := ∥w∥2 + C
ℓi (w).
2
w∈Rd
n
∗
i=1
ただし，ℓi (w) := ℓ(yi , x⊤
i w) は凸な損失関数とする．
▶
任意の w̃ ∈ Rd に対し，最適解 w∗ は以下の球に含まれる：
{ }
w∗ ∈ B := w ∥w − m∥ ≤ r .
ただし，球の中心と半径は，∇ℓi (w̃) ∈ Rd を ℓi の w̃ におけ
る任意の劣勾配すると，以下のように与えられる：
(
)
n
n
∑
∑
1
1
m :=
w̃ − C
∇ℓi (w̃) , r := w̃ + C
∇ℓi (w̃) .
2
2
i=1
I. Takeuchi, Nagoya Institute of Technology
i=1
14/38
直感的には
▶
最適解 w∗ を含む球 B を構成するには任意の近似解 w̃ ∈ Rd
を利用する
▶
近似解 w̃ が最適解 w∗ に近いと半径 r が小さくなり，スク
リーニングできる非 SV が増える
MATLAB demo
I. Takeuchi, Nagoya Institute of Technology
15/38
[
[
安全事例スクリーニングの例
[
Before safe screening
I. Takeuchi, Nagoya Institute of Technology
[
After safe screening
16/38
近似解 w̃ の求め方
▶
正則化パラメータ C が小さいときの自明な解を近似解とする
▶
異なる正則化パラメータ C における解を近似解とする
▶
サブサンプリングなどにより近似解を得る（Part 3 参照）
I. Takeuchi, Nagoya Institute of Technology
17/38
実験結果１
Data
Sample Size n
LIBLINEAR
Sc.Rule
Sc.SVM
Sc.Total
acoustic
covtype
yahoo
url
kdd-a
kdd-b
78,832
581,012
1,036,492
2,396,130
8,407,752
19,264,097
0.16
0.54
5.55
10.39
18.20
37.54
0.03
0.09
1.13
1.71
2.37
4.53
0.01
0.11
1.39
6.92
3.37
2.26
0.038
0.199
2.518
8.631
5.740
6.788
最小の正則化パラメータ C0 = (||yy ⊤ ⊙ K||∞ )−1 における自明な最適解を近似
解として C = C0 /0.8 における線形 SVM の最適解を求める計算コスト（秒）
I. Takeuchi, Nagoya Institute of Technology
18/38
実験結果２（C1 < C2 < . . . の解を順次求める）
Data Set
Kernel (γ)
LIBSVM/LIBLINEAR
Sc.Rule
Sc.SVM
Sc.Total
dna
n = 2, 000
d = 180
Linear
RBF (0.1/d)
RBF (1/d)
RBF (10/d)
27.54
138.8
6.13
2.95
0.184
0.6979
0.6239
0.4729
26.14
104.4
3.4
2.43
26.32
105.1
4.024
2.903
DIGIT1
n = 1, 500
d = 241
Linear
RBF (0.1/d)
RBF (1/d)
RBF (10/d)
235.5
801
72.84
5.57
0.4799
1.302
1.281
1.096
231.6
731
63.82
3.08
232.1
732.3
65.1
4.176
satimage
n = 4, 435
d = 36
Linear
RBF (0.1/d)
RBF (1/d)
RBF (10/d)
115.2
21345
448
32.06
0.3319
6.465
7.966
8.181
114
20604
322.3
5.74
114.3
20610
330.3
13.92
gisette
n = 6, 000
d = 5, 000
Linear
RBF (0.1/d)
RBF (1/d)
RBF (10/d)
994.1
418.9
55.74
56.68
32.34
15.19
14.26
10.32
937.4
389.5
37.93
54.44
969.7
404.7
52.19
64.76
mushrooms
n = 8, 124
d = 112
Linear
RBF (0.1/d)
RBF (1/d)
RBF (10/d)
5.22
757.2
143.6
100.2
0.5139
28.23
24.24
16.32
4.25
603.7
95.79
81.21
4.765
631.9
120
97.53
news20
n = 19, 996
d = 1, 355, 191
Linear
RBF (0.1/d)
RBF (1/d)
RBF (10/d)
4403
22.15
4664
59656
26.59
16.05
83.55
166.5
4504
21.52
3760
51310
4531
37.57
3844
51477
shuttle
n = 43, 500
d=9
Linear
RBF (0.1/d)
RBF (1/d)
RBF (10/d)
81.53
58866
55717
51568
1.607
638.1
692.7
738.5
73.31
56118
49999
43053
74.92
56756
50692
43792
I. Takeuchi, Nagoya Institute of Technology
19/38
Part 2
スパース高次交互作用モデルの
安全特徴スクリーニング
I. Takeuchi, Nagoya Institute of Technology
20/38
L1 正則化によるスパース線形モデル（LASSO）
▶
LASSO の主問題
∗
w := arg min λ∥w∥1 +
n
∑
w∈Rd
▶
i=1
LASSO の双対問題
1
γ ∗ := arg minn
γ∈R 2
▶
(yi − w⊤ xi )2
(
)2
n
∑
1
γ i − yi
s.t. xij γi ≤ 1, ∀j
λ
スパース性の条件
n
∑
xij γi∗ < 1
i=1
⇒
wj∗ = 0,
i=1
I. Takeuchi, Nagoya Institute of Technology
21/38
LASSO の安全特徴スクリーニング
▶
▶
双対最適解 γ ∗ を含む領域 R
▶
(El Ghaoui et al., 2012)
▶
(Liu et al., 2014)
▶
(Fercoq et al., 2015)
特徴スクリーニング
γ ∗ ∈ R ならば，
n
n
∑
∑
max xij γi < 1 ⇒ xij γi∗ < 1 ⇒ wj∗ = 0
γ∈R i=1
|
{z
}
|i=1 {z
}
| {z }
スコアの上限が 1 未満
スコアが 1 未満
スパース
双対最適解 γ ∗ が未知であっても，最適解を含む領域
R が既知であれば，係数が零の特徴を同定できる！
I. Takeuchi, Nagoya Institute of Technology
22/38
高次交互作用モデル
▶
オリジナルの特徴（特徴数 d 個）
{(zi , yi )}ni=1 , zi ∈ [0, 1], yi ∈ R
▶
高次交互作用モデル（特徴数 D =
∑r
()
d
ρ=1 ρ
個）
f (zi ) = w1 z1 + w2 z2 + . . . + wd zd
+ w1,2 z1 z2 + w1,3 z1 z3 + . . . + wd−1,d zd−1 zd
+ w1,2,3 z1 z2 z3 + w1,2,4 z1 z2 z4 + . . . + wd−2,d−1,d zd−2 zd−1 zd
▶



X := 

n×D
拡張入力行列 X ∈ Rn×D を考え，LASSO とスクリーニング
(main eﬀect)
1
z1
.
.
.
n
z1
(2
nd
...
1
zd
1 1
z1
z2
.
.
.
.
n
zd
.
.
.
n n
z1 z2
.
.
...
I. Takeuchi, Nagoya Institute of Technology
···
order interactions)
...
.
.
.
...
1
1
zd−1
zd
.
.
.
n
n
zd−1
zd
...
.
.
.
...
1 1
1
z1
z2 · · ·zr
.
.
.
n n
n
z1 z2 · · ·zr
(r
th
...
.
.
.
...
order interactions)
1
1
1
zd−r+1
zd−r+2
· · ·zd
.
.
.
n
n
n
zd−r+1
zd−r+2
· · ·zd





23/38
計算コストとコスト削減のトリック
▶
例えば，d = 5000, r = 5 の場合，D > 1016
▶
すべての高次交互作用特徴のスコアの上限を計算できない
n
∑
γi xij , j = 1, . . . , D.
max γ∈R i=1
▶
高次交互作用項の木構造を利用
I. Takeuchi, Nagoya Institute of Technology
24/38
安全枝刈りルール（Safe Pruning Rule）
ノード（特徴）j のための安全枝刈りルール：spr(j)
n
∑
spr(j) is true ⇒ xij ′ γi∗ < 1 ⇒ wj∗′ = 0 for all j ′ ∈ Des(j),
i=1
ただし，Des(j) はノード j の子孫ノードの集合
I. Takeuchi, Nagoya Institute of Technology
25/38
安全枝刈りルールの動作
spr(z1 ) = false,
I. Takeuchi, Nagoya Institute of Technology
A = {z1 }
26/38
安全枝刈りルールの動作
spr(z1 z2 ) = true,
I. Takeuchi, Nagoya Institute of Technology
A = {z1 }
26/38
安全枝刈りルールの動作
spr(z1 z3 ) = false,
I. Takeuchi, Nagoya Institute of Technology
A = {z1 , z1 z3 }
26/38
安全枝刈りルールの動作
spr(z1 z3 z4 ) = false,
I. Takeuchi, Nagoya Institute of Technology
A = {z1 , z1 z3 , z1 z3 z4 }
26/38
安全枝刈りルールの動作
spr(z1 z4 ) = true,
I. Takeuchi, Nagoya Institute of Technology
A = {z1 , z1 z3 , z1 z3 z4 }
26/38
安全枝刈りルールの動作
spr(z2 ) = true,
I. Takeuchi, Nagoya Institute of Technology
A = {z1 , z1 z3 , z1 z3 z4 }
26/38
安全枝刈りルールの動作
spr(z3 ) = true,
I. Takeuchi, Nagoya Institute of Technology
A = {z1 , z1 z3 , z1 z3 z4 }
26/38
安全枝刈りルールの動作
spr(z4 ) = false,
I. Takeuchi, Nagoya Institute of Technology
A = {z1 , z1 z3 , z1 z3 z4 , z4 }
26/38
安全枝刈りルールの動作
A = {z1 , z1 z3 , z1 z3 z4 , z4 }
I. Takeuchi, Nagoya Institute of Technology
26/38
実験結果
（λ1 > λ2 > . . . の最適解の計算）
180
1.8e+08
IB
SPR
140
1.4e+08
traverse
time
120
100
80
7000
IB
SPR
1.6e+08
1.2e+08
1e+08
8e+07
60
6e+07
40
4e+07
20
2e+07
0
-2 -1.8 -1.6 -1.4 -1.2 -1 -0.8 -0.6 -0.4 -0.2 0
6000
# of feature
160
depth 1
depth 2
depth 3
4000
3000
2000
1000
0
-2 -1.8 -1.6 -1.4 -1.2 -1 -0.8 -0.6 -0.4 -0.2 0
log Lam/LamMax
5000
0
-2 -1.8 -1.6 -1.4 -1.2 -1 -0.8 -0.6 -0.4 -0.2 0
log Lam/LamMax
log Lam/LamMax
protein
450
2.5e+08
IB
SPR
350
traverse
time
300
250
200
1600
IB
SPR
2e+08
1.5e+08
1e+08
150
100
1400
1200
# of feature
400
depth 1
depth 2
depth 3
1000
800
600
400
5e+07
200
50
0
-2 -1.8 -1.6 -1.4 -1.2 -1 -0.8 -0.6 -0.4 -0.2 0
log Lam/LamMax
0
-2 -1.8 -1.6 -1.4 -1.2 -1 -0.8 -0.6 -0.4 -0.2 0
log Lam/LamMax
0
-2 -1.8 -1.6 -1.4 -1.2 -1 -0.8 -0.6 -0.4 -0.2 0
log Lam/LamMax
mnist
Itemset Boosting (Saigo et al., 2006) と比較
I. Takeuchi, Nagoya Institute of Technology
27/38
Part 3
安全スクリーニング技術の応用
（概要）
I. Takeuchi, Nagoya Institute of Technology
28/38
安全スクリーニング技術の応用
▶
▶
安全スクリーニング技術のキモ
▶
よい近似解 w̃ が得られているとき，
▶
最適解 w∗ を含む領域 B がわかり，
▶
最適解の線形スコア θ ⊤ w∗ の下限と上限を計算可能
線形スコアの例（２クラス分類問題）
{
+1 if x⊤ w∗ > 0,
⊤ ∗
ŷ = sign(f (x)) = sign(x w ) =
−1 if x⊤ w∗ < 0.
すなわち，
min x⊤ w > 0 ⇒ ŷ = +1,
w∈B
max x⊤ w < 0 ⇒ ŷ = −1.
w∈B
最適解を知らなくても２クラス分類ができる！
I. Takeuchi, Nagoya Institute of Technology
29/38
逐次学習のための感度分析 (KDD2015)
I. Takeuchi, Nagoya Institute of Technology
30/38
逐次学習のための感度分析 (KDD2015)
I. Takeuchi, Nagoya Institute of Technology
30/38
逐次学習のための感度分析 (KDD2015)
I. Takeuchi, Nagoya Institute of Technology
30/38
逐次学習のための感度分析 (KDD2015)
The computational cost depends only on |A| + |R|.
I. Takeuchi, Nagoya Institute of Technology
30/38
感度分析
▶
方針
∗ を近似解 w̃ とし，更新後の最適解
更新前の最適解 wold
∗
wnew に関する感度分析（２クラス分類など）を行う
▶
▶
実験設定
▶
kdd2010 ベンチマークデータ
ntrain = |D old | > 8 million and ntest > 0.5 million
▶
訓練事例の 0.01, 0.1, 1%を更新
実験結果
% of updated instances
0.01%
0.1%
1%
% of label identification
% of speed-ups
99.987%
99.888%
99.958%
99.887%
99.867%
99.791%
99%以上のテストラベルを 1/1000 の計算コストで確定
I. Takeuchi, Nagoya Institute of Technology
31/38
精度保障付クロスバリデーション
(NIPS2015)
0.32
0.3
Validation Error
0.28
0.26
0.24
0.22
0.2
0.18
0.16
0.001
0.01
0.1
1
10
Regularization Parameter C
100
1000
Model selection can be done with approximation guarantee.
I. Takeuchi, Nagoya Institute of Technology
32/38
精度保障付クロスバリデーション
(NIPS2015)
0.32
0.3
Validation Error
0.28
0.26
0.24
0.22
0.2
0.18
0.16
0.001
0.01
0.1
1
10
Regularization Parameter C
100
1000
Model selection can be done with approximation guarantee.
I. Takeuchi, Nagoya Institute of Technology
32/38
精度保障付クロスバリデーション
(NIPS2015)
0.32
9DOLGDWLRQ(UURU3DWK
0.3
*ULG6HDUFK
Validation Error
0.28
0.26
0.24
0.22
0.2
0.18
0.16
0.001
0.01
0.1
1
10
Regularization Parameter C
100
1000
Model selection can be done with approximation guarantee.
I. Takeuchi, Nagoya Institute of Technology
32/38
精度保障付クロスバリデーション
(NIPS2015)
0.32
9DOLGDWLRQ(UURU3DWK
0.3
$SS9DO(UU3DWK
Validation Error
0.28
0.26
0.24
0.22
0.2
0.18
0.16
0.001
0.01
0.1
1
10
Regularization Parameter C
100
1000
Model selection can be done with approximation guarantee.
I. Takeuchi, Nagoya Institute of Technology
32/38
精度保障付クロスバリデーション
(NIPS2015)
0.32
9DOLGDWLRQ(UURU3DWK
0.3
$SS9DO(UU3DWK
Validation Error
0.28
0.26
0.24
0.22
0.2
ε 0.18
0.16
0.001
0.01
0.1
1
10
Regularization Parameter C
100
1000
Model selection can be done with approximation guarantee.
I. Takeuchi, Nagoya Institute of Technology
32/38
なぜ保障できるか（その１）
▶
∗ の下
安全スクリーニング技術を使うと，評価スコア x⊤ wC
限・上限を正則化パラメータ C の関数として表現可能
▶
∗ の符号が不
正則化パラメータが一定範囲内にあれば，x⊤ wC
変であることを利用
MNPM O
RTQ SUVX[ WZY \^_a] ` VcQ [eb d
KLNK M
V [ WfY \ ] Nhg
PRO QTSVUNZ WYX [/]R\ ^ U`O Zb_ a
,
+*
(' )
&
%
#$
"!
,
-/.120 463 587:;=9 <
IG H JLK
> .?2 0 4 3 5@7 ; 9 <BADC .FEB.?2 0 4 3 < 587 ; 9 <
I. Takeuchi, Nagoya Institute of Technology
+*
(' )
&
%
#$
"!
U Z WYX [ \ LTc
-/.120 463 587:;9 <
GE F HJI
= . 20 4 3 5>7:; 9 <@?BA .DC@. 20 4 3 < 587:; 9 <
33/38
なぜ保障できるか（その２）
∗⊤ x′ is written as
A lower and an upper bounds of wC
i
∗⊤ ′
LB(wC
xi ) =
α(ŵC̃ , x′i ) −
∗⊤ ′
UB(wC
xi ) = −β(ŵC̃ , x′i ) +
C
C̃
C
C̃
(β(ŵC̃ , x′i ) + γ(g(ŵC̃ ), x′i )),
(α(ŵC̃ , x′i ) + δ(g(ŵC̃ ), x′i )),
where, for C ≥ C̃,
1
∗⊤ ′
(∥ŵC̃ ∥∥x′i ∥ + wC̃
xi ) ≥ 0,
2
1
∗⊤ ′
β(ŵC̃ , x′i ) := (∥ŵC̃ ∥∥x′i ∥ − wC̃
xi ) ≥ 0,
2
α(ŵC̃ , x′i ) :=
and
1
⊤ ′
)xi ) ≥ 0,
(∥g(ŵC̃ ), x′i )∥∥x′i ∥ + g(ŵC̃
2
1
⊤ ′
δ(g(ŵC̃ ), x′i ) := (∥g(ŵC̃ ), x′i )∥∥x′i ∥ − g(ŵC̃
)xi ) ≥ 0,
2
γ(g(ŵC̃ ), x′i ) :=
where g(ŵC̃ ), x′i ) is the gradient vector of the objective function at w = ŵC̃ .
I. Takeuchi, Nagoya Institute of Technology
34/38
なぜ保障できるか（その３）
▶
評価誤差の変化の下限・上限を正則化パラメータ C の関数
として計算可能
796 8$:;=<>:?ABD@ CFE ?HBJG IKC
LM6 8$:N;O<>:?ABD@ CFE ?HBJG IKC
354
2
.
)1 22
0
+/- .
(
*+,
')(
I. Takeuchi, Nagoya Institute of Technology
!"# $&%
35/38
なぜ保障できるか（その３）
▶
評価誤差の変化の下限・上限を正則化パラメータ C の関数
として計算可能
796 8$:;=<>:?ABD@ CFE ?HBJG IKC
LM6 8$:N;O<>:?ABD@ CFE ?HBJG IKC
354
2
.
)1 22
0
+/- .
(
*+,
')(
I. Takeuchi, Nagoya Institute of Technology
!"# $&%
35/38
まとめと今後の課題
▶
▶
大規模データのスパース学習に安全スクリーニングは有効
▶
安全事例スクリーニング
▶
高次交互作用モデルの安全特徴スクリーニング
▶
特徴と事例の同時スクリーニング
十分によい近似解 ⇒ 最適解の線形スコアの下限・上限
▶
感度分析
▶
モデル選択
▶
差分プライバシ
I. Takeuchi, Nagoya Institute of Technology
36/38
参考文献
▶
▶
▶
▶
▶
▶
▶
▶
▶
L. El Ghaoui, V. Viallon and T. Rabbani. Safe feature elimination in sparse supervised learning. Pacific
Journal of Optimization, 2012.
J. Liu, Z. Zhao, J. Wang and J. Ye. Safe Screening with Variational Inequalities and Its Application to
Lasso. ICML2014.
J. Fan and J. Lv. Sure independence screening for ultrahigh dimensional feature space. Journal of The
Royal Statistical Society B, 70:849911, 2008.
R. Fan, K. Chang, C. Hsieh, X. Wang and C. Lin. LIBLINEAR: A library for large linear classification.
Journal of Machine Learning Research, vol. 9, pp. 18711874, 2008.
H. Saigo, T. Uno and K. Tsuda. Mining complex genotypic features for predicting hiv-1 drug resistance.
Bioinformatics, 24:24552462, 2006.
K. Ogawa, Y. Suzuki and I. Takeuchi. Safe screening of non-support vectors in pathwise SVM
computation. ICML2013.
K. Nakagawa, S. Suzumura, M. Karasuyama, K. Tsuda and I. Takeuchi. Safe feature pruning for sparse
high-order interaction models. arXiv:1506.08002, 2015.
S. Okumura, Y. Suzuki and I. Takeuchi. Quick sensitivity analysis for incremental data modification and
its application to leave-one-out CV in linear classification problems. KDD2015.
A. Shibagaki, Y. Suzuki, M. Karasuyama and I. Takeuchi. Regularization path of cross-Validation error
lower bounds. NIPS2015.
ご静聴ありがとうございました
I. Takeuchi, Nagoya Institute of Technology
37/38

Download Report