機械学習分野における離散最適化手法の応用研究～離散凸最適化を中心に～離散構造と最適化：展開と連携
九州大学マス・フォア・インダストリ研究所
2012年11月29&30日

永野 清仁

Kiyohito Nagano

東京大学 生産技術研究所
1/40

OUTLINE
 機械学習関連分野 と 最適化研究
 劣モジュラ関数の定義と性質
 劣モジュラ関数最大化とその応用

 劣モジュラ関数最小化とその応用
 その他の話題・まとめ

2
機械学習分野における離散最適化手法の応用研究 ～離散凸最適化を中心に～

機械学習 (Machine Learning)：
データの解析

有用な規則や判断基準を抽出

機械学習と関連する研究分野
・ 学習理論・ 確率・統計学

・ データマイニング

・ 連続最適化
SVMの研究は90年代の中頃から

・ パターン認識・ コンピュータビジョン
・ 人工知能など
3・ 離散最適化
注目されはじめたのは2000年代の中頃から

機械学習と連続最適化が交わる研究 (1/2)
 Support Vector Machine (SVM)
凸最適化問題になる！
 研究は90年代の中頃から

関数値

 機械学習における凸最適化の成功例

Sra, Nowozin, Wright 編 (2011)

凸関数

4x

機械学習と連続最適化が交わる研究 (2/2)
 Regularized Optimization
Minimize L(w) + g R(w)w∈Rnloss 関数 L のみの最小化では過適合で汎化誤差が小さくならない⇒ regularizer R を加えて最小化 (g は正のパラメータ)
 R としては l1ノルム, l2ノルムなど (l1ノルムだと疎な解になる)
 R として変数間の関係を考慮 → structured sparsity 例：SVM, 圧縮センシング, 行列補完, LASSO など
5 現在の機械学習における中心的なテーマ

機械学習と離散最適化の交わりについて
 歴史は長くない (2005年くらいから?) 連続の世界における凸性に対応する (とみなせる) 劣モジュラ関数(submodular function) が中心的な役割を担っている
 国際的な動向
 ICML 2008 のチュートリアル講演“Beyond Convexity: Submodularity in Machine Learning”
by Andreas Krause and Carlos Guestrin.
 NIPSワークショップ “Discrete Optimization in Machine Learning”
が 2009年～2012年の間, 4年連続開催
6

OUTLINE
 機械学習関連分野 と 最適化研究
 劣モジュラ関数の定義と性質
 劣モジュラ関数最大化とその応用

 劣モジュラ関数最小化とその応用
 その他の話題・まとめ

7
機械学習分野における離散最適化手法の応用研究 ～離散凸最適化を中心に～

劣モジュラ関数について – overview – 多岐に渡る分野で現れる
ネットワーク計画, ゲーム理論, オークション理論, 機械学習 など
 離散領域 {0, 1}n上の 凸関数 とみなせる

n 次元 0-1 ベクトル全体

 同時に 凹関数 のような性質も持つ

convexconcave 劣モジュラ関数の最小化問題 (制約なしなら多項式時間で解ける),最大化問題 (NP困難なものの中でも易しい方) は基本問題

8定義：集合関数
 有限集合 N = {1, ... , n} , N のべき集合 2N = { S : S ⊆N }
 2N 上で定義された実数値関数 f : 2N → R を 集合関数 とよぶ(このとき N を f : 2N → R の台集合 とよぶ)
N
15926S

実数値 f (S) ∊R

4378

定義：集合関数
 有限集合 N = {1, ... , n} , N のべき集合 2N = { S : S ⊆N }
 2N 上で定義された実数値関数 f : 2N → R を 集合関数 とよぶ(このとき N を f : 2N → R の台集合 とよぶ)

集合関数の例
12
仕事1, 仕事2 がある

10NS43fN(S)= ∊R{1, 2}, f を次のように決める

6
仕事しないならかかる時間
0 8
57f ({ }) = 0

仕事1のみにかかる時間が 4f ({1})= 4

仕事2のみにかかる時間が 4f ({2})= 4

仕事1と2の両方をこなすと 5f ({1,2}) = 5
この f は仕事時間を表す集合関数(実は劣モジュラ関数にもなっている)定義：集合関数
 有限集合 N = {1, ... , n} , N のべき集合 2N = { S : S ⊆N }
 2N 上で定義された実数値関数 f : 2N → R を 集合関数 とよぶ
 集合関数 f : 2N → R は {0, 1}n 上の関数とみなせる{1,2,3}x3x2{1,2}{1,3}{2,3}1{1,2}{2}{1} {2} {3}x11 x1{0, 1}n∈02NS11≃ x2 O∈{ } {} {1}(1,1,1)

IS(IS の第 i 成分) =1 if i∈S0 if i∉S定義：劣モジュラ関数 (submodular function)
 有限集合 N = {1, ... , n} , N のべき集合 2N = { S : S ⊆N }
 集合関数 f : 2N → R は 劣モジュラ if ∀S, T ⊆NNT

S
1f (S) + f (T) ≥ f (S∪T) + f (S∩T)

2765438

例. カット関数 k : 2N→ R
グラフ G = (N, E) with 枝重み we ≥ 0 (e∈E)
N ={1, ... , n }k (S) = Se∈E has one endpoint in S
we :and one in N – Sk は劣モジュラ
12S214510611378129定義：劣モジュラ関数 (submodular function)
 有限集合 N = {1, ... , n} , N のべき集合 2N = { S : S ⊆N }
 集合関数 f : 2N → R は 劣モジュラ if ∀S, T ⊆N
1f (S) + f (T) ≥ f (S∪T) + f (S∩T)

NT

S
5264378 多岐に渡る分野で現れる
ネットワーク計画, ゲーム理論, オークション理論, 機械学習 など
 離散世界の凸関数 (Lovász ’83 など)

 同時に凹関数のような性質も持つ
h(x)

h(x)

x13凸関数x凹関数

定義：劣モジュラ関数 (submodular function)
 有限集合 N = {1, ... , n} , N のべき集合 2N = { S : S ⊆N }
 集合関数 f : 2N → R は 劣モジュラ if ∀S, T ⊆Nf (S) + f (T) ≥ f (S∪T) + f (S∩T)

NTS
1524

3
768

 [劣モジュラ性の特徴付け]f は劣モジュラ if and only if∀S, T ⊆N s. t. S⊆T and i ∉ Tf (S ∪{i }) – f (S ) ≥ f (T∪{i }) – f (T )「限界効用逓減の法則」
14T

NSi

劣モジュラ関数の凸性 (と凹性)
劣モジュラ関数 f : 2N → R の連続関数 F : Rn → R への補間を考える{2}x2{1,2}

≃{}

{1}

101 x1{0, 1}n 上でのみ関数値が定まっている

何らかのルールで補間x2
1015凸になる補間: Lovász extension
1x1

凹っぽい補間 : Multilinear extension劣モジュラ関数の凸性 (と凹性) – 凸な補間
f : 2N → R の補間その①: Lovász extension FL : Rn → R
Lovász (1983)

劣モジュラ関数 f1x2x1016Lovász extension FL は 凸

1f ({}) = 0f ({1}) = 4f ({2}) = 4f ({1, 2}) = 5

多面体的凸な補間0x1
1FL(x) = max {4x1+x2 , x1+4x2}

定義. FL(x) = maxn {xT z : S zi ≤ f(S),∀S⊆N} (x∊Rn≥0)z∊Ri∈S

劣モジュラ関数の凸性 (と凹性) – 凹っぽい補間f : 2N → R の補間その②: Multilinear extension FM : Rn → R
Calinescu, Chekuri, Pál & Vondrák (2011)

劣モジュラ関数 f1x2

凹っぽい補間x10

17Multilinear extension FM1f ({}) = 0f ({1}) = 4f ({2}) = 4f ({1, 2}) = 5x10

1FM(x) = 5x1x2 + 4x1(1–x2) + 4(1–x1)x2

定義. FM(x) = S f (S) P xi P (1–xi) (x∊Rn≥0)S⊆N(非負方向の直線に沿って凹)i∈Si∉S

この補間は今日は基本的に扱わない劣モジュラ関数の凸性 (と凹性) – 凹っぽい補間f : 2N → R の補間その②: Multilinear extension FM : Rn → R
Calinescu, Chekuri, Pál & Vondrák (2011)

劣モジュラ関数 f1x2

凹っぽい補間x10

18

Multilinear extension FM01f ({}) = 0f ({1}) = 4f ({2}) = 4f ({1, 2}) = 5x1
角度を変えて眺める
1FM(x) = 5x1x2 + 4x1(1–x2) + 4(1–x1)x2

定義. FM(x) = S f (S) P xi P (1–xi) (x∊Rn≥0)
S⊆N(非負方向の直線に沿って凹)i∈Si∉S

この補間は今日は基本的に扱わない基本問題：劣モジュラ関数の最小化
以下, 劣モジュラ関数 f の各関数値 f (S) の計算は基本操作とする

劣モジュラ関数最小化

Minimize f (S)sub. toS ⊆N ={1,2,..., n}

 2n 個の候補の中から最適解を見つける問題

Lovászextension 凸関数最小化の離散版に対応を利用
 この問題を解く 多項式時間アルゴリズム が知られている• 楕円体法： Grötschel, Lovasz, & Schrijver（1981, 1988）• 組合せ的： Iwata, Fleischer, & Fujishige (2001),Schrijver (2000), Orlin (2009)19

基本問題：劣モジュラ関数の最大化
f : 2N → R を 単調 な劣モジュラ関数とし, k を定数とする
S⊆T なら f (S) ≤ f (T)(応用上最も重要な形の)劣モジュラ関数最大化

Maximize f (S)sub. toS ⊆N のサイズは k 以下

 NP困難だが, 0.632-近似アルゴリズムがある (Nemhauser ら ’78)
最適値の0.632倍以上の関数値を達成する
S を必ず出力する多項式時間アルゴリズム

 サイズ制約より複雑なマトロイド制約下の最大化も Multilinear
extension を用いて同じ近似率 0.632 が達成可能
20(Calinescu, Chekuri, Pál & Vondrák, 2011)

OUTLINE
 機械学習関連分野 と 最適化研究
 劣モジュラ関数の定義と性質
 劣モジュラ関数最大化とその応用

 劣モジュラ関数最小化とその応用
 その他の話題・まとめ

21
機械学習分野における離散最適化手法の応用研究 ～離散凸最適化を中心に～

劣モジュラ関数の最大化とその機械学習分野への応用
f : 2N → R を 単調 な劣モジュラ関数とし, k を定数とする劣モジュラ関数最大化

max f (S)s. t. |S| ≤ k 機械学習周辺分野への応用• センサ配置問題（Gusetrin ら, ICML 2005 など）• ネットワークの伝播モデル（Kempe, Kleinberg, Tardos, KDD 2003）• 特徴選択（Krause & Gusetrin, UAI 2005）などなど
22

劣モジュラ関数の例：被覆関数
C2C1• 観測される点 U• C1, ... , Cn は点集合 U の部分集合

C4• 添字集合 N = {1, ... , n}

C3f ({2,3})n ==44

Ci ：場所 i にセンサを置いたときに観測できる点集合
被覆関数 f : 2N → R を次式で定義

各 S ⊆N で f (S) = ( ⋃ Ci のサイズ)
i ∈S

命題
23

被覆関数は単調な劣モジュラ関数

最大化の応用：センサ配置問題
max f (S)s. t. |S| ≤ kf は単調劣モジュラ,k は定数f : 2N → R を被覆関数だとすれば, この問題は k 台のセンサを最適配置する問題と解釈できる

C1C424

C2C3

k = 2 のときの最適配置

最大化の応用：ネットワークの伝播モデル[Kempe, Kleinberg & Tardos, KDD ’03]

0.3
0.7
0.3

0.3

0.4

0.1

0.2

新商品を k 人に持たせる

人々は（確率的に）周囲の影響を受ける

最も効果的な k 人を選ぶ問題は劣モジュラ関数最大化25劣モジュラ関数の最大化の近似アルゴリズム

max f (S)s. t. |S| ≤ kf は 単調劣モジュラ貪欲アルゴリズム
初期化： S = {}while |S| < k dof (S∪{i}) が最大な i ∈N – S で S := S ∪ {i}定理 (Nemhauser, Wolsey, & Fisher, 1978) このアルゴリズムは0.632-近似アルゴリズム
 近似比 0.632 は本質的に最良（Feige, 1998）
 効率的なアルゴリズム
26

計算時間を犠牲にしても, より良い品質が保証される解が得られないか?

劣モジュラ性カットアルゴリズム[Kawahara, Nagano, Tsuda, Bilmes, NIPS 2009]

Lovász extension FL を用いて連続緩和問題を考えて,凹性カット法 (Tuy, 1960) の変種を適用する

max f (S )max FL (x )s. t. |S| ≤ kS ⊆N

連続緩和

多面体的凸関数s. t. S i xi ≤ k0≤ xi ≤1 ,∀iD0

ギャップがない (by the convexity of FL )• この平面切除アルゴリズムは 厳密解 or (1-e)-近似解 を出力• 0-1 整数計画問題を繰り返しとく27• それなりに大きいサイズの問題も扱える (n ≈ 5000)劣モジュラ性カットアルゴリズム[Kawahara, Nagano, Tsuda, Bilmes, NIPS 2009]

アルゴリズムは次を保持する• current polytope D ⊆D0• current solution S ⊆N
• current best value g

反復 j :• Compute a hyperplane H s. t.
FL (x) ≤ g for any x ∈ D ⋂ H–
• Update x ∈ D := D ⋂ H+ ,compute new S ⊆N and update g

28

D0IS d2d1

H–

HH+DDnewnew IS定理 このアルゴリズムは有限回の反復で停止し, 最適解を出力

OUTLINE
 機械学習関連分野 と 最適化研究
 劣モジュラ関数の定義と性質
 劣モジュラ関数最大化とその応用

 劣モジュラ関数最小化とその応用
 その他の話題・まとめ

29
機械学習分野における離散最適化手法の応用研究 ～離散凸最適化を中心に～

劣モジュラ関数の最小化とその機械学習分野への応用
劣モジュラ関数最小化

min f (S)s. t. S ⊆N ={1,2,..., n} 機械学習周辺分野への応用• クラスタリング(Narasimhan ら, NIPS 2005; Nagano, Kawahara, & Iwata, NIPS 2010)• 密な部分グラフを抽出（Nagano, Kawahara & Aihara, ICML 2011)
劣モジュラ関数の基本分割の概念を利用している• Structured sparsity（Bach, NIPS 2010 & NIPS 2011）
Regularized optimization

30

min L(w) + g R(w) でw∈Rn
複雑な regularizer R も Lovasz 拡張を用いて記述(なども Group LASSO も含む)

クラスタリング データ点 N = {1, ... , n} と k ≤ n について, N を k 個の部分集合
S1, …, Sk ≠{} (それぞれクラスタとよぶ) に分ける
 同じクラスタ内の点は似ていて、 異なるクラスタ間の点は似ていないようにする
 クラスタリングは教師なし学習の一種
 多くの場合, クラスタ数 k が事前に与えられているわけではない

Clustering methods
k-means, spectral clustering, maximum margin, etc

S1S2
S3 k = 331

Example: clustering of networksネットワークの場合のクラスタリング
データがネットワーク G = (N, E) として与えられているとする
各枝はその両端の点は関係していることを意味し, 重みは関係の強さ“最適” な k-クラスタリングを求める問題
k-分割 {S1, … , Sk} の中で赤い枝の重み和

1 kS k (Si) の最小化
2 i=1S1S2

minimum k-cut (NP-hard)

目的関数:S32

ki=1k (Si)

一般化Ski=1 f (Si)Sk

[Narasimhan et al., NIPS ’05]

f は一般の劣モジュラ関数

クラスタリング with 劣モジュラ関数
f : 2N → R は一般の劣モジュラ関数 with f ({}) = 0

最適 k-クラスタリング問題 [Narasimhan et al., NIPS ’05]mink

Si=1 f (Si)s. t. {S1,..., Sk} は N の k-分割

k は何らかの方法で見つける

NP-hard いくつかの自然な規準におけるクラスタリングを一般化
f が対称 (f(S)=f(N – S)) なとき, 2分割を繰り返す方法は 2-近似

33

クラスタリング with 劣モジュラ関数
f : 2N → R は一般の劣モジュラ関数 with f ({}) = 0

最適 k-クラスタリング問題 [Narasimhan et al., NIPS ’05]mink

Si=1 f (Si)s. t. {S1,..., Sk} は N の k-分割

k は何らかの方法で見つける

NP-hardMinimum Average Cost (MAC) clustering [NKI, NIPS ’10]
平均を取ったバージョンの目的関数を扱う

クラスタ数と分割を同時に決める
他の手法と competitive
すべての b - MAC クラスタリングはトータルで多項式時間で求まる

34

アルゴリズムでは Dilworth
truncation (1944) を使う

クラスタリング with 劣モジュラ関数
f : 2N → R は一般の劣モジュラ関数 with f ({}) = 0

最適 k-クラスタリング問題 [Narasimhan et al., NIPS ’05]mink

Si=1 f (Si)s. t. {S1,..., Sk} は N の k-分割

k は何らかの方法で見つける

NP-hardMinimum Average Cost (MAC) clustering [NKI, NIPS ’10]
min
S S∊P f (S) /(|P |–b)
平均を取ったバージョンのs.目的関数を扱う
t. P は N の分割|P | > b

where 0 ≤b < nb - MAC clustering
35

If b is small, P is coarse
If b is large, P is fine=→|P| andaveragea partitionP areb =k1クラスタ数と分割を同時に決める
naturalcost function
determined at the same time
他の手法と competitive S

S1
2
competitive with othermethods
N={1,...,n}すべての b - MAC クラスタリングはkallトータルで多項式時間で求まる
b - MAC clusterings canSbe
computed in poly time in total
cost: 0 → Si f (SDilworthSi f (Si)
アルゴリズムではi)The algorithm usestruncation
を使う# of sets:
1 (1944)→kk–1
Dilworthtruncation(1944)

MAC クラスタリングアルゴリズム [NKI, ’10] について
 部分集合 S と T が交差している if S∖T, T∖S, S∩T すべて非空 集合関数 g : 2N → R は 交差劣モジュラ if
交差している S と T で g (S) + g (T) ≥ g (S∪T) + g (S∩T)
 関数 g : 2N → R の Dilworth truncation g’ : 2N → R の定義は

g’ (S) = min { S g (T): P は N の分割 } (S ⊆ N)T∊P
 g’ の各関数値は O(n) 回劣モジュラ関数最小化を実行すると求まる

この事実を用いる

36

Theorem すべての b-MAC クラスタリングはトータルでO(n2) 回の劣モジュラ関数最小化で求まる

Experimental results
We compared the MAC algorithm with
(1) k-means method(2) spectral-clustering method with normalized-cut (Ng+, 2002)(3) maximum-margin clustering (Xu+, 2005)# of clusters k is selected through 5-fold cross-validation
Gaussian

CircleIris

LibrasGlassk-means

1.0

0.88

0.79

0.85

0.93

norm cut

0.88

0.86

0.84

0.87

0.93

max margin

0.99

1.0

0.96

0.90

0.97

MAC

0.99

1.0

0.99

0.97

0.97

360 samples‘Gaussian’, ‘Circle’:
synthetic datasets‘Iris’, ‘Libras’, ‘Glass’:
real world datasetsfrom the UCI repository

Clustering accuracy (the larger, the better)
37

MAC clustering is competitive with standard clustering methods

OUTLINE
 機械学習関連分野 と 最適化研究
 劣モジュラ関数の定義と性質
 劣モジュラ関数最大化とその応用

 劣モジュラ関数最小化とその応用
 その他の話題・まとめ

38
機械学習分野における離散最適化手法の応用研究 ～離散凸最適化を中心に～

オンライン予測版の劣モジュラ最適化
 オンライン版最小化 (Hazan & Kale, NIPS 2009, JMLR 2012)• T 日間のうち t 日目の劣モジュラ関数を ft :2N→ R とする• 私は t 日目に, 前日までの情報に基づいて (ft を知らない状態で) St⊆N を決める
• f1 (S1)+ … +fT (ST) が小さくなるようにしたい(正確に言えば, regret を小さくなるようにしたい) オンライン版最大化 (Streeter & Golovin. NIPS 2008)
 オンライン版の基多面体上の最適化 (本ワークショップの畑埜先生のはなし)39まとめ・課題 劣モジュラ関数は凸性と凹性を持つ
 機械学習周辺分野における劣モジュラ最適化の応用研究が近年特に活発になされている
 劣モジュラ関数などの一般化である L凸関数, M凸関数の機械学習における応用は課題

おわり
40