. . . .
.
.
.
.
.
.
.
スパース正則化およびマルチカーネル学習のための最
適化アルゴリズムと
CV
・
PR
への応用
冨岡 亮太
1
,
鈴木 大慈
1
,
杉山 将
2
1東京大学
2東京工業大学
2009-08-31 @ PRMU/CVIM
仙台
http://www.ibis.t.u-tokyo.ac.jp/ryotat/prmu09/
. . . .
Outline
.
. .
1
イントロ
-
スパース正則化とは
具体例
問題設定
.
. .
2
Dual Augmented Lagrangian
法（提案法）
Proximal minimization
からのアプローチ
Legendre
変換
実験評価
マルチカーネル学習
.
. .
3
デモンストレーション
.
. .
4
まとめ
. . . . イントロ - スパース正則化とは
Outline
.
. .
1
イントロ
-
スパース正則化とは
具体例
問題設定
.
. .
2
Dual Augmented Lagrangian
法（提案法）
Proximal minimization
からのアプローチ
Legendre
変換
実験評価
マルチカーネル学習
.
. .
3
デモンストレーション
.
. .
4
まとめ
. . . . イントロ - スパース正則化とは 具体例
Outline
.
. .
1
イントロ
-
スパース正則化とは
具体例
問題設定
.
. .
2
Dual Augmented Lagrangian
法（提案法）
Proximal minimization
からのアプローチ
Legendre
変換
実験評価
マルチカーネル学習
.
. .
3
デモンストレーション
.
. .
4
まとめ
. . . . イントロ - スパース正則化とは 具体例
Lasso
回帰
(1/3)
入出力の組み
(x
1
,
y
1
), (x
2
,
y
2
), . . . , (x
m
,
y
m
)
．
x
i
∈ R
n
．
仮定：
y
i
=
〈w, x
i
〉 + ϵ
i
,
ϵ
i
∼ N (0, σ
2
).
経験誤差：
L(w ) =
1
2
P
m
i=1
(
y
i
− 〈w, x
i
〉)
2
=
1
2
∥y − Xw∥
2
.
動機
1
：現実には多くの場合
m < n
．
動機
2
：なるべく少ない数の変数で説明したい！
（
w
の非ゼロ要素の数
∥w∥
0
が少なければ少ないほどよい）
問題
1:
minimize
∥w∥
0
,
subject to L(w )
≤ C.
問題
2:
minimize
L(w ),
subject to
∥w∥
0
≤ C
′
.
どちらも
NP
困難
!!
. . . . イントロ - スパース正則化とは 具体例
Lasso
回帰
(1/3)
入出力の組み
(x
1
,
y
1
), (x
2
,
y
2
), . . . , (x
m
,
y
m
)
．
x
i
∈ R
n
．
仮定：
y
i
=
〈w, x
i
〉 + ϵ
i
,
ϵ
i
∼ N (0, σ
2
).
経験誤差：
L(w ) =
1
2
P
m
i=1
(
y
i
− 〈w, x
i
〉)
2
=
1
2
∥y − Xw∥
2
.
動機
1
：現実には多くの場合
m < n
．
動機
2
：なるべく少ない数の変数で説明したい！
（
w
の非ゼロ要素の数
∥w∥
0
が少なければ少ないほどよい）
問題
1:
minimize
∥w∥
0
,
subject to L(w )
≤ C.
問題
2:
minimize
L(w ),
subject to
∥w∥
0
≤ C
′
.
どちらも
NP
困難
!!
. . . . イントロ - スパース正則化とは 具体例
Lasso
回帰
(1/3)
入出力の組み
(x
1
,
y
1
), (x
2
,
y
2
), . . . , (x
m
,
y
m
)
．
x
i
∈ R
n
．
仮定：
y
i
=
〈w, x
i
〉 + ϵ
i
,
ϵ
i
∼ N (0, σ
2
).
経験誤差：
L(w ) =
1
2
P
m
i=1
(
y
i
− 〈w, x
i
〉)
2
=
1
2
∥y − Xw∥
2
.
動機
1
：現実には多くの場合
m < n
．
動機
2
：なるべく少ない数の変数で説明したい！
（
w
の非ゼロ要素の数
∥w∥
0
が少なければ少ないほどよい）
問題
1:
minimize
∥w∥
0
,
subject to L(w )
≤ C.
問題
2:
minimize
L(w ),
subject to
∥w∥
0
≤ C
′
.
どちらも
NP
困難
!!
. . . . イントロ - スパース正則化とは 具体例
Lasso
回帰
(1/3)
入出力の組み
(x
1
,
y
1
), (x
2
,
y
2
), . . . , (x
m
,
y
m
)
．
x
i
∈ R
n
．
仮定：
y
i
=
〈w, x
i
〉 + ϵ
i
,
ϵ
i
∼ N (0, σ
2
).
経験誤差：
L(w ) =
1
2
P
m
i=1
(
y
i
− 〈w, x
i
〉)
2
=
1
2
∥y − Xw∥
2
.
動機
1
：現実には多くの場合
m < n
．
動機
2
：なるべく少ない数の変数で説明したい！
（
w
の非ゼロ要素の数
∥w∥
0
が少なければ少ないほどよい）
問題
1:
minimize
∥w∥
0
,
subject to L(w )
≤ C.
問題
2:
minimize
L(w ),
subject to
∥w∥
0
≤ C
′
.
どちらも
NP
困難
!!
. . . . イントロ - スパース正則化とは 具体例
Lasso
回帰
(2/3)
p-
ノルムの
p
乗（のようなもの）
∥w∥
p
p
=
P
n
j=1
|w
j
|
p
:
(
p
≥ 1
ならば
凸
p < 1
ならば
非凸
−3
0
−2
−1
0
1
2
3
1
2
3
4
|x|
0.01|x|
0.5|x|
x
2∥w∥
1
の正則化は凸の中ではもっとも
∥w∥
0
の正則化に近い！
. . . . イントロ - スパース正則化とは 具体例
Lasso
回帰
(2/3)
p-
ノルムの
p
乗（のようなもの）
∥w∥
p
p
=
P
n
j=1
|w
j
|
p
:
(
p
≥ 1
ならば
凸
p < 1
ならば
非凸
−3
0
−2
−1
0
1
2
3
1
2
3
4
|x|
0.01|x|
0.5|x|
x
2∥w∥
1
の正則化は凸の中ではもっとも
∥w∥
0
の正則化に近い！
. . . . イントロ - スパース正則化とは 具体例
Lasso
回帰
(3/3)
問題
1:
minimize
∥w∥
1
,
subject to L(w )
≤ C.
問題
2:
minimize
L(w ),
subject to
∥w∥
1
≤ C
′
.
問題
3:
minimize
L(w ) + λ
∥w∥
1
.
[From Efron et al. (2003)]
注意：
上の
3
つの問題はいずれも等価．
正則化項やロス項に単調な非線形変換をしても等価．
この発表では問題
3
を扱う．
. . . . イントロ - スパース正則化とは 具体例
なぜ
ℓ
1
-
正則化か？
凸の中で最も
∥ · ∥
0
に近い．
原点で微分不可能（有限の
λ
で
ゼロに打ち切ることができる．
）
凸でない正則化
→
繰り返し（重み付き）
ℓ
1
-
正
則化問題を解けばよい．
ベイズ周辺化尤度最大化
→
（特殊な場合に）繰り返し
（重み付き）
ℓ
1
-
正則化問題を解
けばよい．
(Wipf&Nagarajan, 08)
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2 0 0.5 1 1.5 2. . . . イントロ - スパース正則化とは 具体例
一般化
損失項を一般化
· · ·
例：
ℓ
1
-
ロジスティック回帰
minimize
w
∈R
nP
m
i=1
− log P(y
i
|x
i
;
w ) + λ
∥w∥
1
ただし，
P(y
|x; w) = σ (y 〈w, x〉)
(
y
∈ {−1, +1})
−50 0 5 0.5 1 u σ (u) h σ(u) = 1 1+exp(−u) i正則化項を一般化
· · ·
例：グループラッソー
(Yuan&Lin,06)
minimize
w
∈R
nL(w ) + λ
X
g
∈G
∥w
g
∥
2
ただし，
G
は
{1, . . . , n}
の適当な分割で，
w =
(
w
g1)
(
w
g2)
..
.
(
w
gq)
，
q =
|G|
．
. . . .
イントロ - スパース正則化とは 具体例
さらに一般化：カーネルを導入
マルチカーネル学習
(Multiple Kernel Learning, MKL):
(Lanckriet, Bach,
et al., 04)
H
1
,
H
2
, . . . ,
H
n
を
RKHS
，
K
1
,
K
2
, . . . ,
K
n
をそれに付随するカーネル関数
とする．f = f
|{z}
1
∈H1
+
|{z}
f
2
∈H2
+
· · · + fn
|{z}
∈H
nで予測することで性能を上げよう！
minimize
f
j∈H
j,b
∈R
L(f
1
+
f
2
+
· · · + f
n
+
b) + λ
n
X
j=1
∥f
j
∥
H
j⇓
（表現定理）
minimize
α
j∈R
m,b
∈R
f
ℓ
³
n
X
j=1
K
j
α
j
+
b1
´
+ λ
n
X
j=1
∥α
j
∥
K
jただし，
∥α
j
∥
K
j=
q
α
j
⊤
K
j
α
j
．
・
・
・カーネル行列で重み付けされたグループラッソー．
. . . .
イントロ - スパース正則化とは 具体例
さらに一般化：カーネルを導入
マルチカーネル学習
(Multiple Kernel Learning, MKL):
(Lanckriet, Bach,
et al., 04)
H
1
,
H
2
, . . . ,
H
n
を
RKHS
，
K
1
,
K
2
, . . . ,
K
n
をそれに付随するカーネル関数
とする．f = f
|{z}
1
∈H1
+
|{z}
f
2
∈H2
+
· · · + fn
|{z}
∈H
nで予測することで性能を上げよう！
minimize
f
j∈H
j,b
∈R
L(f
1
+
f
2
+
· · · + f
n
+
b) + λ
n
X
j=1
∥f
j
∥
H
j⇓
（表現定理）
minimize
αj
∈R
m,b
∈R
f
ℓ
³
X
n
j=1
K
j
α
j
+
b1
´
+ λ
n
X
j=1
∥α
j
∥
K
jただし，
∥α
j
∥
Kj
=
q
α
j
⊤
K
j
α
j
．
・
・
・カーネル行列で重み付けされたグループラッソー．
. . . . イントロ - スパース正則化とは 具体例
絞り込み
損失項は（多くの場合）損失関数
f
ℓ
とデザイン行列
A
に分解可能．
2
乗損失
f
ℓ
Q
(z) =
1
2
∥y − z∥
2
,
A =
Ã
x
1⊤..
.
xm
⊤!
f
ℓ
Q
(Aw ) =
1
2
∥y − Xw∥
2
ロジスティック損失
f
ℓ
L
(z) =
m
X
i=1
log(1 + exp(
−y
i
z
i
)),
A =
Ã
x
1⊤..
.
xm
⊤!
f
ℓ
L
(Aw ) =
m
X
i=1
− log σ(y
i
〈w, x
i
〉)
. . . . イントロ - スパース正則化とは 問題設定
Outline
.
. .
1
イントロ
-
スパース正則化とは
具体例
問題設定
.
. .
2
Dual Augmented Lagrangian
法（提案法）
Proximal minimization
からのアプローチ
Legendre
変換
実験評価
マルチカーネル学習
.
. .
3
デモンストレーション
.
. .
4
まとめ
. . . . イントロ - スパース正則化とは 問題設定
問題設定
以下の最適化問題を効率良く解くためのアルゴリズムが求められている．
minimize
w
∈R
nf
ℓ
(Aw ) + φ
λ
(w ).
ただし，
A
∈ R
m
×n
（
m:
サンプル数，
n:
未知変数の数）．
f
ℓ
は凸で
2
回微分可能．
φ
λ
(w )
は例えば，
φ
λ
(w ) = λ
∥w∥
1
など，凸だが，微分不可能であっ
てもよい．また，
ηφ
λ
= φ
ηλ
を仮定．
特定の
f
ℓ
に依存したアルゴリズム（
LARS
など）ではもの足りない．
No Free Lunch –
観測の数が変数の数より少ない場合
(m
≪ n)
や
A
のコンディションが悪い場合が応用上重要．
. . . . イントロ - スパース正則化とは 問題設定
どこが難しいか？
今までの見方
:
φ
λ
(w )
の微分不可能性が原因．
正則化項を微分可能な関数で上から押
さえる．
FOCUSS
(Rao & Kreutz-Delgado, 99)
Majorization-Minimization
(Figueiredo et al., 07)
微分不可能性を陽に考慮する．
Sub-gradient L-BFGS (Andrew &
Gao, 07; Yu et al., 08)
我々の見方
:
A
が変数の間にからみを導入するのが原因．
. . . . イントロ - スパース正則化とは 問題設定
どこが難しいか？
我々の見方
:
A
が変数の間にからみを導入するのが原因．
A = I
n
（単位行列の場合）
min
w
∈R
nµ
1
2
∥y − w∥
2
2
+ λ
∥w∥
1
¶
=
n
X
j=1
min
w
j∈R
µ
1
2
(
y
j
− w
j
)
2
+ λ
|w
j
|
¶
.
⇒ w
j
∗
= ST
λ
(
y
j
)
=
y
j
− λ (λ ≤ y
j
),
0
(
−λ ≤ y
j
≤ λ),
y
j
+ λ
(
y
j
≤ −λ).
解析的に解ける！
λ
−
λ
本発表では
φ
λ
として，上の最小化が解析的に求められるもののみを扱う．
. . . .
イントロ - スパース正則化とは 問題設定
先行研究
Iterative Shrinkage/Thresholding (IST)
法
(Figueiredo&Nowak, 03;
Daubechies et al., 04,...):
.
アルゴリズム
.
.
.
.
.
.
.
.
.
.
.
1適当に初期解
w
1
を決める．
.
.
.
2停止条件が満たされるまで反復：
w
t+1
← argmin
w
∈R
n¡
Q
η
t(w ; w
t
) + φ
λ
(w )
¢
ただし，
Q
η
(w ; w
t
) =
|
L(w
t
) +
∇L
⊤
{z
(w
t
)(w
− w
t
}
)
(1) 損失項を 1 次近似
+
1
2η
∥w − w
t
∥
2
2
|
{z
}
(2)
前の反復か
らの距離
2にペ
ナルティ
.
注意：
Q
η
(w ; w
t
)
の最小化は普通の勾配ステップ（サイズ
η
）を与える．
. . . . イントロ - スパース正則化とは 問題設定
先行研究：
IST
法
argmin
w
∈R
n¡
Q
η
t(w ; w
t
) + φ
λ
(w )
¢
=
argmin
w
∈R
nµ
const. +
∇L
⊤
(w
t
)(w
− w
t
) +
1
2η
t
∥w − w
t
∥
2
2
+ φ
λ
(w )
¶
=
argmin
w
∈R
nµ
1
2η
t
∥w − ˜
w
t
∥
2
2
+ φ
λ
(
w )
¶
|
{z
}
ここの最小化は解析的にできると仮定
=: ST
η
tλ
( ˜
w
t
)
ただし，
w
˜
t
=
w
t
− η
t
∇L(w
t
)
（勾配ステップ先）．
結局
w
t+1
← ST
| {z }
η
tλ
縮小
¡
w
t
− η
t
∇L(w
t
)
¢
|
{z
}
勾配ステップ
長所
：簡単．
短所
：
A
の悪スケーリングに弱い．
. . . . イントロ - スパース正則化とは 問題設定
先行研究：
IST
法
argmin
w
∈R
n¡
Q
η
t(w ; w
t
) + φ
λ
(w )
¢
=
argmin
w
∈R
nµ
const. +
∇L
⊤
(w
t
)(w
− w
t
) +
1
2η
t
∥w − w
t
∥
2
2
+ φ
λ
(w )
¶
=
argmin
w
∈R
nµ
1
2η
t
∥w − ˜
w
t
∥
2
2
+ φ
λ
(w )
¶
|
{z
}
ここの最小化は解析的にできると仮定
=: ST
η
tλ
( ˜
w
t
)
ただし，
w
˜
t
=
w
t
− η
t
∇L(w
t
)
（勾配ステップ先）．
結局
w
t+1
← ST
| {z }
η
tλ
縮小
¡
w
t
− η
t
∇L(w
t
)
¢
|
{z
}
勾配ステップ
長所
：簡単．
短所
：
A
の悪スケーリングに弱い．
. . . . イントロ - スパース正則化とは 問題設定
先行研究：
IST
法
argmin
w
∈R
n¡
Q
η
t(w ; w
t
) + φ
λ
(w )
¢
=
argmin
w
∈R
nµ
const. +
∇L
⊤
(w
t
)(w
− w
t
) +
1
2η
t
∥w − w
t
∥
2
2
+ φ
λ
(w )
¶
=
argmin
w
∈R
nµ
1
2η
t
∥w − ˜
w
t
∥
2
2
+ φ
λ
(w )
¶
|
{z
}
ここの最小化は解析的にできると仮定
=: ST
η
tλ
( ˜
w
t
)
ただし，
w
˜
t
=
w
t
− η
t
∇L(w
t
)
（勾配ステップ先）．
結局
w
t+1
← ST
| {z }
η
tλ
縮小
¡
w
t
− η
t
∇L(w
t
)
¢
|
{z
}
勾配ステップ
長所
：簡単．
短所
：
A
の悪スケーリングに弱い．
. . . . イントロ - スパース正則化とは 問題設定
先行研究：
IST
法
argmin
w
∈R
n¡
Q
η
t(w ; w
t
) + φ
λ
(w )
¢
=
argmin
w
∈R
nµ
const. +
∇L
⊤
(w
t
)(w
− w
t
) +
1
2η
t
∥w − w
t
∥
2
2
+ φ
λ
(w )
¶
=
argmin
w
∈R
nµ
1
2η
t
∥w − ˜
w
t
∥
2
2
+ φ
λ
(w )
¶
|
{z
}
ここの最小化は解析的にできると仮定
=: ST
η
tλ
( ˜
w
t
)
ただし，
w
˜
t
=
w
t
− η
t
∇L(w
t
)
（勾配ステップ先）．
結局
w
t+1
← ST
| {z }
η
tλ
縮小
¡
w
t
− η
t
∇L(w
t
)
¢
|
{z
}
勾配ステップ
長所
：簡単．
短所
：
A
の悪スケーリングに弱い．
. . . . イントロ - スパース正則化とは 問題設定
ここまでのまとめ
最適化問題：
minimize
w
∈R
nf
ℓ
(Aw ) + φ
λ
(w ).
を解きたい．ただし，
f
ℓ
は凸で
2
階微分可能．
φ
λ
(w )
は例えば
φ
λ
(w ) = λ
∥w∥
1
で，
以下の最小化が陽に求まるもの．
ST
λ
(z) = argmin
w
∈R
nµ
1
2
∥w − z∥
2
2
+ φ
λ
(w )
¶
φ
λ
の微分不可能性
⇒ST
による打ち切
り．
スパース性が計算効率を高める！
A
のスケーリングにロバストにしたい．
λ
−
λ
z
ST(z)
. . . .
Dual Augmented Lagrangian 法（提案法）
Outline
.
. .
1
イントロ
-
スパース正則化とは
具体例
問題設定
.
. .
2
Dual Augmented Lagrangian
法（提案法）
Proximal minimization
からのアプローチ
Legendre
変換
実験評価
マルチカーネル学習
.
. .
3
デモンストレーション
.
. .
4
まとめ
. . . .
Dual Augmented Lagrangian 法（提案法） Proximal minimization からのアプローチ
Outline
.
. .
1
イントロ
-
スパース正則化とは
具体例
問題設定
.
. .
2
Dual Augmented Lagrangian
法（提案法）
Proximal minimization
からのアプローチ
Legendre
変換
実験評価
マルチカーネル学習
.
. .
3
デモンストレーション
.
. .
4
まとめ
. . . .
Dual Augmented Lagrangian 法（提案法） Proximal minimization からのアプローチ
.
Proximal Minimization (Rockafellar, 1976)
.
.
.
.
.
.
.
.
.
.
.
1適当に初期解
w
1
を決める．
.
.
.
2停止条件が満たされるまで反復：
w
t+1
← argmin
w
∈R
n³
f
ℓ
(Aw )
| {z }
線形近似しない
+φ
λ
(w ) +
1
2η
t
∥w − w
t
∥
2
2
|
{z
}
前の反復からの
距離
2にペナル
ティ
´
f
η
(w ) = min
w
˜
∈R
n³
f
ℓ
(A ˜
w ) + φ
λ
( ˜
w ) +
2η
1
∥ ˜
w
− w∥
2
2
´
とおくと，
事実 1: fη(w )
≤ f (w) = f
ℓ(Aw ) + φλ(w )．
事実 2: fη(w
∗
) =
f (w
∗
)．
このままではもとの最適化問題と同程度に難しい．
−
λ
0
λ
f
η(w)
f(w)
. . . .
Dual Augmented Lagrangian 法（提案法） Proximal minimization からのアプローチ
.
IST 法（既存手法）
.
.
.
.
.
.
.
.
.
.
.
1適当に初期解
w
1
を決める．
.
.
.
2停止条件が満たされるまで反復：
w
t+1
← ST
η
tλ
³
w
t
+ η
t
A
⊤
(
−∇fℓ
(
Aw
t
))
´
.
Dual Augmented Lagrangian 法（提案法）
.
.
.
.
.
.
.
.
.
.
.
1適当に初期解
w
1
を決める．
.
.
.
2停止条件が満たされるまで反復：
w
t+1
← ST
η
tλ
³
w
t
+ η
t
A
⊤
α
t
´
ただし，
α
t
=
argmin
α
∈R
mµ
f
ℓ
∗
(
−α) +
1
2η
t
∥STη
tλ
(
w
t
+ η
t
A
⊤
α)
∥
2
2
¶
. . . .
Dual Augmented Lagrangian 法（提案法） Proximal minimization からのアプローチ
数値例
IST
DAL
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2. . . .
Dual Augmented Lagrangian 法（提案法） Proximal minimization からのアプローチ
.
Dual Augmented Lagrangian 法
.
.
.
.
.
.
.
.
.
.
.
1適当に初期解
w
1
を決める．
.
.
.
2停止条件が満たされるまで反復：
w
t+1
← ST
η
tλ
³
w
t
+ η
t
A
⊤
α
t
´
ただし，
α
t
=
argmin
α
∈R
m³
f
ℓ
∗
(
−α)
| {z }
損失関数 f
ℓの凸共役
+
1
2η
t
∥ST
η
tλ
(w
t
+ η
t
A
⊤
α)
∥
2
2
´
.
凸共役（Legendre 変換）
.
.
.
.
.
.
.
.
f
∗
(y ) = sup
x
³
y
⊤
x
− f (x)
´
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Outline
.
. .
1
イントロ
-
スパース正則化とは
具体例
問題設定
.
. .
2
Dual Augmented Lagrangian
法（提案法）
Proximal minimization
からのアプローチ
Legendre
変換
実験評価
マルチカーネル学習
.
. .
3
デモンストレーション
.
. .
4
まとめ
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Legendre
変換
関数
f (x )
を関数
f
∗
(
y )
に移す変換（フーリエ変換のようなもの）
f
∗
(y ) = sup
x
³
y
⊤
x
− f (x)
´
f (x )
-f*(y) y. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Legendre
変換
関数
f (x )
を関数
f
∗
(
y )
に移す変換（フーリエ変換のようなもの）
f
∗
(y ) = sup
x
³
y
⊤
x
− f (x)
´
f (x )
-f*(y) y. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Legendre
変換
関数
f (x )
を関数
f
∗
(
y )
に移す変換（フーリエ変換のようなもの）
f
∗
(y ) = sup
x
³
y
⊤
x
− f (x)
´
f (x )
-f*(y) y. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Legendre
変換
関数
f (x )
を関数
f
∗
(
y )
に移す変換（フーリエ変換のようなもの）
f
∗
(y ) = sup
x
³
y
⊤
x
− f (x)
´
f (x )
-f*(y) y. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Legendre
変換
関数
f (x )
を関数
f
∗
(
y )
に移す変換
（フーリエ変換のようなもの）
f
∗
(y ) = sup
x
³
y
⊤
x
− f (x)
´
-f*(y) y例
1
（
2
乗誤差関数）
：
f (x) =
x
2
2σ
2
⇒ f
∗
(
y ) = sup
x
µ
xy
−
x
2
2σ
2
¶
=
µ
(σ
2
y )y
−
(σ
2
y )
2
2σ
2
¶
=
σ
2
y
2
2
f(x)
f*(y)
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Legendre
変換の性質
f
∗
(y )
はいつも凸．
∵ f
∗
(
y )
≥ xy − f (x)
| {z }
線形な下限
f
が凸なら
f
∗∗
(x) = f (x)
．
∵ f (x) ≥ xy − f
∗
(
y )
（ただし等号が成り立つとは
限らない）
f(x)
f*(y)
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Legendre
変換
: f
∗
(
y ) = sup
x
¡
y
⊤
x
− f (x)
¢
例
2
（ロジスティック損失関数）
：
f (x) = log(1+ exp(
−x))
⇒ f
∗
(
−y) = sup
x
(
−xy − log(1 + exp(−x)))
=
³
−(log
1
−y
y
)
y
− log(1 +
y
1
−y
)
´
=
y log(y ) + (1
− y) log(1 − y) (
エントロピーの符号反転
)
f(x)
f*(y)
0
1
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Legendre
変換
: f
∗
(
y ) = sup
x
¡
y
⊤
x
− f (x)
¢
例
3
（
ℓ
1
正則化関数）
:
f (x) =
|x| ⇒ f
∗
(
y ) = sup
x
(
xy
− |x|) =
(
0
(
|y| ≤ 1),
+
∞ (otherwise).
f(x)
f*(y)
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
双対を使う
.
主問題の目的関数を双対を使って表現
.
.
.
.
.
.
.
.
f
ℓ
(A
w
) + φ
λ
(
w
) =
max
v
∈R
n,α
∈R
m³
w
⊤
(v
− A
⊤
α)
− (f
ℓ
∗
(
−α) + φ
∗
λ
(v ))
|
{z
}
w に関し線形な下限
´
∵)
max
v
∈R
n,α
∈R
m³
w
⊤
(v
− A
⊤
α)
− f
ℓ
∗
(
−α) − φ
∗
λ
(v )
´
=
max
α
∈R
m³
−w
⊤
A
⊤
α
− f
ℓ
∗
(
−α)
´
+
max
v
∈R
n³
w
⊤
v
− φ
∗
λ
(v )
´
=
f
ℓ
(Aw ) + φ
λ
(w )
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Proximal minimization
の式に代入
w
t+1
← argmin
w
∈R
nµ
f
ℓ
(Aw ) + φ
λ
(w ) +
1
2η
t
∥w − w
t
∥
2
2
¶
=
argmin
w
∈R
n(
max
v
∈R
n,α
∈R
m³
−f
ℓ
∗
(
−α) − φ
∗
λ
(
v ) + w
⊤
(
v
− A
⊤
α)
´
+
1
2η
t
∥w − w
t
∥
2
2
)
min
と
max
の順番を交換し，あとは計算，計算．
．
．
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Proximal minimization
の式に代入
w
t+1
← argmin
w
∈R
nµ
f
ℓ
(Aw ) + φ
λ
(w ) +
1
2η
t
∥w − w
t
∥
2
2
¶
=
argmin
w
∈R
n(
max
v
∈R
n,α
∈R
m³
−f
ℓ
∗
(
−α) − φ
∗
λ
(
v ) + w
⊤
(
v
− A
⊤
α)
´
+
1
2η
t
∥w − w
t
∥
2
2
)
min
と
max
の順番を交換し，あとは計算，計算．
．
．
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
Proximal minimization
の式に代入
w
t+1
← argmin
w
∈R
nµ
f
ℓ
(Aw ) + φ
λ
(w ) +
1
2η
t
∥w − w
t
∥
2
2
¶
=
argmin
w
∈R
n(
max
v
∈R
n,α
∈R
m³
−f
ℓ
∗
(
−α) − φ
∗
λ
(
v ) + w
⊤
(
v
− A
⊤
α)
´
+
1
2η
t
∥w − w
t
∥
2
2
)
min
と
max
の順番を交換し，あとは計算，計算．
．
．
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
.
Dual Augmented Lagrangian 法
.
.
.
.
.
.
.
.
(1)
この計算は解析的にできると仮定．
w
t+1
← ST
η
tλ
³
w
t
+
A
⊤
α
t
´
λ
−
λ
. . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
.
Dual Augmented Lagrangian 法
.
.
.
.
.
.
.
.
(1)
この計算は解析的にできると仮定．
w
t+1
← ST
η
tλ
³
w
t
+
A
⊤
α
t
´
(2)
この計算はスパースであればあるほど効率的
Ã
“アクティブな”
未 知 変 数 の 数
に線形
!
α
t
=
argmin
α
∈R
mµ
f
ℓ
∗
(
−α) +
1
2η
t
∥ST
η
tλ
(w
t
+ η
t
A
⊤
α)
∥
2
2
¶
−λ 0 λ φλ∗(w) Φλ∗(w). . . .
Dual Augmented Lagrangian 法（提案法） Legendre 変換
.
Dual Augmented Lagrangian 法
.
.
.
.
.
.
.
.
(1)
この計算は解析的にできると仮定．
w
t+1
← ST
η
tλ
³
w
t
+
A
⊤
α
t
´
(2)
この計算はスパースであればあるほど効率的．
Ã
“アクティブな”
未 知 変 数 の 数
に線形
!
α
t
=
argmin
α
∈R
m³
f
ℓ
∗
(
−α)
| {z }
A のスケーリン
グの影響を受け
ない
+
1
2η
t
∥ST
η
tλ
(w
t
+ η
t
A
⊤
α)
∥
2
2
|
{z
}
∂
∂α
:
AST
η
tλ
(w
t
+ η
t
A
⊤
α)
∂
∂α
2: η
t
A
+
A
+
⊤
（A+
は
A
の
“
アクティブな
”
列から
なる部分行列
; ℓ
1-
正則化の場合）
´
(3) A
のスケーリングの悪さの影響を受けにくい．
. . . .
Dual Augmented Lagrangian 法（提案法） 実験評価
Outline
.
. .
1
イントロ
-
スパース正則化とは
具体例
問題設定
.
. .
2
Dual Augmented Lagrangian
法（提案法）
Proximal minimization
からのアプローチ
Legendre
変換
実験評価
マルチカーネル学習
.
. .
3
デモンストレーション
.
. .
4
まとめ
. . . .
Dual Augmented Lagrangian 法（提案法） 実験評価
実験（設定）
問題：
LASSO
（
2
乗損失＋
ℓ
1
正則化）
対抗手法：
l1_ls
（内点法）
SpaRSA
（ステップサイズ改良 IST）
ランダムデザイン行列
A
∈ R
m
×n
(m:
サンプル数
n:
未知変数の数
)
A=randn(m,n);
（良条件数）
A=U*diag(1./(1:m))*V’;
(悪条件数）
2
つの状況
中規模 (n = 4m, n < 10000)
大規模 (m = 1024, n < 1e + 6)
. . . .
Dual Augmented Lagrangian 法（提案法） 実験評価
結果（中規模）
良条件数
悪条件数
100
1000
10000
0.01
0.1
1
10
100
1000
10000
CPU time (secs)
DALchol (η1=1000) DALcg (η1=1000) SpaRSA l1_ls
100
1000
10000
1
10
100
#iterations
100
1000
10000
6
8
10
Number of observations
(a) Normal conditioning
Sparsity (%)
100
1000
0.01
0.1
1
10
100
1000
10000
CPU time (secs)
DALchol (η1=100000) DALcg (η1=100000) SpaRSA l1_ls
100
1000
1
10
100
1000
10000
#iterations
100
1000
0
2.5
5
Number of samples
(b) Poor conditioning
Sparsity (%)
. . . .
Dual Augmented Lagrangian 法（提案法） 実験評価
結果（大規模）
1
10
100
1000
10000
10
4
10
5
10
6
CPU time (secs)
DALchol (η 1=1000) DALcg (η 1=1000) SpaRSA l1_ls
1
10
100
1000
10000
10
4
10
5
10
6
#iterations
0
5
10
Number of unknown variables
Sparsity (%)
10
4
. . . .
Dual Augmented Lagrangian 法（提案法） マルチカーネル学習
Outline
.
. .
1
イントロ
-
スパース正則化とは
具体例
問題設定
.
. .
2
Dual Augmented Lagrangian
法（提案法）
Proximal minimization
からのアプローチ
Legendre
変換
実験評価
マルチカーネル学習
.
. .
3
デモンストレーション
.
. .
4
まとめ
. . . .
Dual Augmented Lagrangian 法（提案法） マルチカーネル学習
目的
本来やりたいこと：
minimize
f
∈H,b∈R,d∈R
nm
X
i=1
ξ
i
+
λ
2
∥f ∥
2
H(d)
subject to
y
i
(
f (x
i
) +
b)
≥ 1 − ξ
i
(
i = 1, . . . , m)
K (d ) =
n
X
i=1
d
j
K
j
,
d
j
≥ 0,
X
j
d
j
≤ 1.
. . . .
Dual Augmented Lagrangian 法（提案法） マルチカーネル学習
表現定理を適用
minimize
α
∈R
m,b
∈R,d∈R
nm
X
i=1
ξi
+
λ
2
α
⊤
K (d )α
subject to
y
i
((
K (d )α)
i
+
b)
≥ 1 − ξi
(
i = 1, . . . , m)
K (d ) =
n
X
i=1
d
j
K
j
,
d
j
≥ 0,
X
j
d
j
≤ 1.
max(0, 1−yf)
. . . .
Dual Augmented Lagrangian 法（提案法） マルチカーネル学習
損失関数を定義
minimize
α
∈R
m,b
∈R,d∈R
nL(K (d )α + b1)
+
λ
2
α
⊤
K (d )α
subject to
K (d ) =
n
X
i=1
d
j
K
j
,
d
j
≥ 0,
X
j
d
j
≤ 1.
max(0, 1−yf)
. . . .
Dual Augmented Lagrangian 法（提案法） マルチカーネル学習
