劣モジュラ性を用いたデータ生成過程の学習
大阪大学 産業科学研究所/ 日本科学技術機構(さきがけ)

河原 吉伸

Email: kawahara@ar.sanken.osaka-u.ac.jp
web: http://www.ar.sanken.osaka-u.ac.jp/~kawahara/

2

発表の概要
機械学習における組合せ的計算によるアプローチの重要性と難しい点，劣モジュラ性利用の動機
 劣モジュラ性の導入的説明と特徴選択への利用
 劣モジュラカット法を中心として，劣モジュラ性を用いた大域的解法の紹介3

特徴選択（1）例） 治療日数を決定する親変数の中から，1. 治療日数を予測するのに有用な変数を選ぶ
2. 治療日数の要因を特定する

重症度0?
𝑒1

治療日数…

年齢0?
0?

投薬

治療日数= 𝑏11 ×投薬+𝑏12 ×重症度+𝑏13 ×年齢+ ⋯ + 𝑒1
(𝑥2 )
(𝑥3 )
(𝑥1 )
(𝑦)

4

特徴選択（1）例） 治療日数を決定する親変数の中から，
1. 治療日数を予測するのに有用な変数を選ぶ
2. 治療日数の要因を特定する
データ生成過程の学習

重症度0?
𝑒1

治療日数…

年齢0?
0?

投薬

治療日数= 𝑏11 ×投薬+𝑏12 ×重症度+𝑏13 ×年齢+ ⋯ + 𝑒1
(𝑥2 )
(𝑥3 )
(𝑥1 )
(𝑦)

5

特徴選択（2）

𝑑次元の入力 𝒙 = *𝑥 1 , 𝑥 2 , ⋯ , 𝑥 𝑝 + が与えられた時に，その部分集合を選ぶ（目的１） 予測モデルの獲得（汎化誤差最小化）⇒ 一般に，精度と計算効率のバランスが重要（目的２） データを生成する機構の同定⇒ 大域的な最適性を持った解のみが有意⇒ 全探査的なアプローチが必要（組合せ最適化）⇒ 組合せ爆発の発生（サイズが大きくなると現実的時間内での計算が困難）6

特徴選択（2）𝑑次元の入力 𝒙 = *𝑥 1 , 𝑥 2 , ⋯ , 𝑥 𝑝 + が与えられた時に，その部分集合を選ぶ（目的１） 予測モデルの獲得（汎化誤差最小化）⇒ 一般に，精度と計算効率のバランスが重要（目的２） データを生成する機構の同定⇒ 大域的な最適性を持った解のみが有意⇒ 全探査的なアプローチが必要（組合せ最適化）⇒ 組合せ爆発の発生（サイズが大きくなると現実的時間内での計算が困難）

7

劣モジュラ性の利用

近年，劣モジュラ性（凸性に対応する離散構造）が，組合せ的計算において有用であるという事が知られてきた⇒ 組合せ的なデータ解析の飛躍的進歩の寄与への期待
凸性（連続関数）

対応する概念劣モジュラ性（集合関数）

自然に現れる構造

12

46

機械学習では，サポートベクターマシンなどで，凸性が有効に利用されてきた3集合関数 𝑓

5
7部分集合

実数値

𝑓 𝑆 + 𝑓 𝑇 ≤ 𝑓 𝑆 ∩ 𝑇 + 𝑓(𝑆 ∪ 𝑇)

8

機械学習問題における利用例


クラスタリング：– Q-Clustering (Narashimhan, Jojic & Bilmes (NIPS’06)）– MAC Clustering (Nagano, Kawahara & Iwata (NIPS’10))– バランス・クラスタリング (Kawahara, Nagano & Okamoto (PatRec(in press)))



特徴選択：
– Dictionary学習 (Krause & Cevher (ICML’10))– 正則化関数としての劣モジュラ関数 (Bach (NIPS’10))

能動学習：– 画像分類への応用 (Hoi et al. (ICML’06))



その他の工学的問題：– センサ配置 (Krause, Singh & Guestrin (JMLR))– グラフ・マイニング (Thoma et al. (SDM’09))– ネットワークの構造推定 (Chechetka & Guestrin (NIPS’08), Steer et al.
(ICML’09), Gomez Rodriguez et al. (KDD’10))

9（補）集合関数
集合関数 𝑓 ∶→𝑉2ℝ(2𝑉 = *𝑆 ∶ 𝑆 ⊆ 𝑉 +)– 有限集合 𝑉 = *1, … , 𝑛+ の部分集合 𝑆 ⊆ 𝑉 から実数への関数
V 124

S

67

3

V = {1, 2, …, 7}

5

S = {3, 5, 7}

こういった一つ一つの部分集合が，𝑓 により実数値に対応づけられる

10

劣モジュラ性とは （1）

連続関数における凸性に対応する集合関数の構造：
連続関数における凸性

集合関数における劣モジュラ性

共通する部分が多い– 最小化に関する効率的なアルゴリズム構築が可能：• Queyranneのアルゴリズム(Queyranne,1998)や最小ノルム点アルゴリズム(Fujishige,1980)など．
– いくつかの凸関数への連続緩和が知られている：• Lovász拡張(Lovász,1983)や，(Nemhauser et al.,1978),(Feige,STOC’06) など．

11

劣モジュラ性とは （2）劣モジュラ関数： 次式を満たす集合関数 𝑓 (𝑆 ⊆ 𝑇 ⊆ 𝑉, 𝑖 ∈ 𝑉 ∖ 𝑇)

𝑓 𝑆 + 𝑖 − 𝑓 𝑆 ≥ 𝑓 𝑇 + 𝑖 − 𝑓(𝑇)Diminishing Returns （規模の経済性，限界効用逓減の法則など）
small imp.

Tlarge imp.

|𝑆| |𝑆 + 𝑖|

|𝑇| |𝑇 + 𝑖|

𝑉
Si

12

劣モジュラ性とは （3）Location S = {Y1,Y2,Y3,Y4,Y5}

Location S = {Y1,Y2}
Y1

Y2

Y1

Y2

Y4
Y5

Y3
Yi

‘large’ imp.

T𝑉Si

‘small’ imp.

* Borrowed from IJCAI09 tutorial “Intelligent Information Gathering and Submodular Function Optimization”

13

劣モジュラ関数の例
組合せ最適化をはじめとして，情報理論やグラフ理論，ゲーム理論，経済学など，多くの数理工学や社会科学の分野において頻繁に現れる．
– 情報理論• 同時エントロピー，（対称）相互情報量，情報利得関数など– グラフ理論• カット関数，ネットワークのカット容量，マトロイドのランクなど– その他• 経済学における効用関数（優モジュラ）, Convex game，被覆関数，正定値対称行列の行列式，自乗重相関係数（負の自乗誤差）など

14

凸性との関係（Lovász拡張）（1）Lovász拡張： 集合関数 𝑓の連続関数への拡張の一つ（定義） 任意の実ベクトル 𝒑 ∈ ℝ𝑛 の要素の値を大きい順に𝑝1 > 𝑝2 > … > 𝑝𝑚と並べたとき，任意の集合関数 𝑓 に対して，Lovász拡張 𝑓 は次のように定義される（𝑈𝑘 = *𝑖 ∈ 𝑉 ∶ 𝑝𝑖 ≧ 𝑝𝑘 +）：𝑓 𝒑 =𝑚−1
𝑘=1 𝑝𝑘 − 𝑝𝑘+1

𝑓: 2𝑉 ↦ ℝ
（集合関数）

𝑓(𝑈𝑘) + 𝑝𝑚 𝑓(𝑈𝑚)Lovasz拡張𝑓 : ℝ𝑛 ↦ ℝ（連続関数）

15凸性との関係（Lovász拡張）（2）Lovász拡張： 集合関数 𝑓の連続関数への拡張例） 𝑉 = 2. 𝑓 0 = 0, 𝑓 𝑉 = 0.2, 𝑓 1= 0.8, 𝑓(*2+) = 0.5

𝒑 = (0.2,0.6)における 𝑓
1. 𝒑の要素を降順に並べる．
𝑝1 = 0.6 > 𝑝2 = 0.2（𝑈1 = 2 , 𝑈2 = (*1,2+）
2. 定義に従って，
𝑓 𝒑 = 0.6 − 0.2 × 𝑓 2+ 0.2 × 𝑓 𝑉 = 0.24

16凸性との関係（Lovász拡張）（3）Lovász拡張： 集合関数 𝑓の連続関数への拡張（定義） 任意の実ベクトル 𝒑 ∈ ℝ𝑛 の要素の値を大きい順に
𝑝1 > 𝑝2 > … > 𝑝𝑚と並べたとき，任意の集合関数 𝑓 に対して，Lovász拡張 𝑓 は次のように定義される（𝑈𝑘 = *𝑖 ∈ 𝑉 ∶ 𝑝𝑖 ≧ 𝑝𝑘+）：
𝑓 𝒑 =𝑚−1
𝑘=1 𝑝𝑘 − 𝑝𝑘+1

𝑓(𝑈𝑘 ) + 𝑝𝑚 𝑓(𝑈𝑚)

定理 (Lovász,1983)：
A set-function 𝑓 is submodular if and only if its Lovász
extension 𝑓 is convex.

17

正則化学習による特徴選択（1）

正則化損失関数最小化としての特徴選択：
min𝑝𝒘∈ℝ⟺

𝑛𝑖=1 𝑙 𝑦𝑖 , 𝑓(𝑥𝑖 )+ 𝜆 ⋅ Ω(𝒘)

損失関数

正則化項

min𝑝𝒘∈ℝ

𝑛𝑖=1 𝑙 𝑦𝑖 , 𝑓(𝑥𝑖 )s.t. Ω 𝒘 ≤ 𝑘パラメータへの拘束を加える事で，モデルパラメータを𝒘をスパースにする（多くの次元が0）18

正則化学習による特徴選択（2）

正則化項の選択により，スパースな解を得る事ができる．
解が軸に乗りやすいため，スパースな解が得られやすい

𝛼2𝛼2

損失関数値の等高線

𝛼1𝑙2 正則化

𝛼1𝑙1 正則化

19

特徴選択における劣モジュラ性の利用


正則化損失関数最小化としての特徴選択：
min𝑝𝒘∈ℝ⟺

𝑛𝑖=1 𝑙 𝑦𝑖 , 𝑓(𝑥𝑖 )
損失関数

min𝑝𝒘∈ℝ+ 𝜆 ⋅ Ω(𝒘)正則化項

𝑛𝑖=1 𝑙 𝑦𝑖 , 𝑓(𝑥𝑖 )s.t. Ω 𝒘 ≤ 𝑘

1. 損失関数における劣モジュラ性
2. 正則化における劣モジュラ性 (Bach,NIPS’10)

20損失関数における劣モジュラ性（1）

特徴選択における損失関数には，集合関数としてみた場合，優モジュラ性（負の劣モジュラ性）を有するものが多い：
min𝑝𝒘∈ℝ

𝑛𝑖=1 𝑙 𝑦𝑖 , 𝑓(𝑥𝑖 )+ 𝜆 ⋅ Ω(𝒘)

正則化項により，スパースな解を得る事で特徴の部分集合を選択

直接的に，集合関数最適化として特徴の部分集合を選択

max 𝑔(𝑆) s.t. Ω 𝑆 ≤ 𝑘𝑆⊆𝑉（劣モジュラ最大化）

劣モジュラ関数．
例えば，自乗重相関係数（負の自乗誤差）や相互情報量

21

損失関数における劣モジュラ性（2）例） 損失関数： 自乗誤差

𝑙 𝑦𝑖 , 𝑓 𝒙𝑖 = 𝑦𝑖 − 𝑓 𝒙𝑖
モデル： 線型モデル 𝑓 𝒙𝑖 = 𝒘 ⋅ 𝒙𝑇𝑖
正則化項： 𝑙0 ノルム
Ω 𝑤 = 𝑤02

𝑉 ≔ *1, ⋯ , 𝑝+（パラメータ𝒘 ∈ ℝ𝒑 のインデックス）𝑔 𝑆⇒𝑗≔ −Σ𝑖 𝑦𝑖 − Σ𝑗∈𝑆 ⊆𝑉 𝑤 𝑗 𝑥𝑖

max 𝑔(𝑆)𝑆⊆𝑉2(劣モジュラ(Das&Kempe’08))

s.t. 𝑆 ≤ 𝑘𝛼2（サイズ制約下の劣モジュラ関数最大化）

𝛼1

22

劣モジュラ最適化における位置づけ（劣モジュラ最適化問題）

凸最小化

劣モジュラ最小化

凸最大化
DC計画

劣モジュラ最大化
離散DC計画問題
制約付き劣モジュラ最小化（NP困難）

対応する
連続最適化

問題自体の難しさ

𝑙0 正則化特徴選択

23

劣モジュラ最大化の厳密解法
劣モジュラ最大化：
max 𝑓(𝑆)𝑆⊆𝑉

s.t. 𝑆 ≤ 𝑘– NP困難（従って，（強）多項式時間で計算可能な厳密アルゴリ
ズムの実現は絶望的）– 𝑓が単調増加関数の場合，貪欲法で (1 − 1/𝑒)-近似が得られる事が知られている (Nemhauser et al., 1978)⇒ 厳密解法（大域的最適化アルゴリズム）– 制約生成アルゴリズム (Nemhauser et al.,1978)– 劣モジュラカット法 (Kawahara et al.,NIPS’09)

24

劣モジュラ・カット（動機）（問題点） 実行可能解が 𝑛 ≔ 𝑉 と共に指数関数的に増加
𝑛𝑛𝑛（解の数）=++ ⋯+(𝑘 : cardinality)𝑘𝑘−1
1（疑問） 最適性を保証しつつ，実行可能解を効率的に減らす事はできないか？
（解決案） Lovasz拡張を通した凸性と劣モジュラ性の関係を用いて，連続の大域的最適化の手法を適用する

25

劣モジュラ・カット（1）

現在，最良値 𝛾 と探索域 𝐷(𝑆) を知っているとする



劣モジュラ最大解の連続への緩和を考える：

max 𝑓(𝑆) s.t. 𝑆 ∈ 𝐷(𝑆)

問題 ①

問題 ②

𝑆⊆𝑉0, 1 𝑉
⇓0, 1 𝑛max 𝑓(𝒙) s.t. 𝑥 ∈ 𝑃(𝑆)𝒙∈𝑃Lovasz拡張

26

劣モジュラ・カット（1）

現在，最良値 𝛾 と探索域 𝐷(𝑆) を知っているとする



劣モジュラ最大解の連続への緩和を考える：
𝑥1

0,1 𝑉 の時の実行可能領域（多面体の頂点）

1,0,1-𝑛 の時の実行可能領域（多面体の表面と内部）

11𝑥2𝑥3

27

劣モジュラ・カット（3）

現在，最良値 𝛾 と探索域 𝐷(𝑆) を知っているとする

劣モジュラ・カット： Lovász拡張を通した凸性より，𝑓 𝒙 ≤ 𝛾 for
𝐴𝑥 ≤ 𝑏 となる線形制約（valid cut）
連続空間における現在の実行可能領域 𝑃

𝑑2

この領域 (𝐴𝑥 ≤ 𝑏) においては，常に 𝑓 𝒙 ≤ 𝛾を満たす

劣モジュラカット
𝐴𝑥 = 𝑏𝑑1

等高線（𝑓 𝒙 = 𝛾）

28

劣モジュラ・カットの構成


基本的な手順：1. 一次独立な方向 𝒅1 , ⋯ , 𝒅𝑛 を決める
2. 各方向 𝒅𝑖 と等高線との交点𝒚𝑖 （𝛾-拡張）を計算する
3. 𝒚1 , … , 𝒚𝑛 を通る超平面を求める
𝑑2②𝑦1𝑦2𝑑1③

等高線（𝑓 𝒙 = 𝛾）①

29

劣モジュラ・カットの構成（𝛾拡張の計算）
𝜸-拡張： 方向 𝒅 に対して，次式を満たす点
𝒚=𝒙+𝜃⋅𝒅⇒ Lovász拡張に関しては，Closedに計算可能
𝑓例）


𝛾𝑓(𝑆)

単に（傾きが既知の）直線上で値が𝛾となる点を探せばいい

𝑓(𝑆(𝑖,𝑗) )
𝒅

𝑆

0.5

𝑆(𝑖,𝑗) 𝜃部分集合𝑆から𝑖 ∈ 𝑆を取り除き，さらに𝑗 ∈ 𝑉 ∖ 𝑆を足した集合

30

Cutting-Plane法への適用

反復的に，劣モジュラカットを生成し，実行可能領域を絞っていく．最終的に大域解が得られる．
SFM (disc.)
max f (S)s. t. S ⊆ S (Pi )① 連続緩和CFM (cont.)（Lovász拡張）

max f (x)s. t. x ∈ Pi^②

③元の離散の空間へ戻す 凸関数最大化の為のカッティング・プレイン法に基づいて，⇒ 劣モジュラカット（線形の）制約を生成する．
max f (S)
Pi+1 ← Pi ∩ H+
s. t. S ⊆ S (Pi+1 )…

収束まで繰り返す

31

ε-近似解法の導入


劣モジュラカット法で厳密解を求めるには，それなりの計算時間がかかってしまう．
⇒「指定した ε > 0 に対し ε-近似解*を効率よく求めたい」

制約生成アルゴリズムを上界評価に利用：
劣モジュラカット法⇒ 下界の評価

制約生成アルゴリズム＋組み合わせ ⇒ 上界の評価

現在の解の精度保証が可能*) ここでは，ε-近似解とは最適解からの誤差がε以内の解をいう

32

制約生成アルゴリズム（Nemhauser&Wolsey,1981）（元の問題）

max f (S)max hs. t. |S| ≤ kS ⊆Vs. t. h ≤ f (S )|S| ≤ kS ⊆Vh, SS

最適値 h*

等価

制約生成アルゴリズム：• 小さい Q⊆2V からスタート• 各反復: Q⊆2V を集合族として大きくしていく

maxhh,xs. t. h ≤ f (T) + ∑ rj (T) xj , ∀T∈2VS xj ≤ kj∈V–Tj∈Nxj ∈{0,1} , ∀j∈Vrj (S) = f (S ⋃ {j}) – f (S)33

人工データへの適用例（収束の様子）例）

n =45, k = 8の場合計算された上界関数
値計算された下界

反復回数

厳密解

貪欲法による解34

人工データへの適用例（説明）K-配置問題： 次の劣モジュラ関数の最大化
mf (S) = ∑ max j∈S cij （ C={cij}は非負行列 ）i =1– 複数のnに対して，ランダムに非負行列 C を生成し，劣モジュラカット法，及び，従来手法（制約生成アルゴリズム）を適用．
– 劣モジュラカット法に関しては，厳密解に加え，ε = 0.05,0.001の場合の近似解も計算．

35

人工データへの適用例（計算時間）
厳密解（制約生成アルゴリズム）

k=5

k=8

計算
時間（厳密解（劣モジュラカット）

log

スケール）

ε = 0.05

ε = 0.001

36

実データへの適用例（文書分類）（１）

文書分類における重要単語の選択に対して，劣モジュラカット法，及び，貪欲法を適用（Reuter-21587を利用）（選択の基準） 単語を与えた事による情報利得関数
I (C ; w) = H(C) - H(C |w)⇒ 単語の生成プロセスが，単純ベイズ仮定の下に行われるとすると，I (C;w)は単語選択に関して劣モジュラ性を有する．
（カテゴリ）



トップ5つのカテゴリに関して，両アルゴリズムを用いて２値分類として単語を選択して評価．

（単語）

37

実データへの適用例（文書分類）（２）（カテゴリ）（選ばれた単語）（利得） （精度）38

発表のまとめ

特徴選択を例に，データ生成過程学習における厳密解探索法の動機と問題点，その解決における劣モジュラ性が持つ重要性について述べた．

特徴選択における損失関数および正則化項に現れる劣モジュラ性とその性質について述べた．

特徴選択などの多くの機械学習が含まれる劣モジュラ最大化のための厳密解法を紹介した．特に，劣モジュラカット法において，劣モジュラ性がアルゴリズム構築に有用である事について述べた．

39

謝辞


本発表に関連して，次の方々に感謝致します：– 永野清仁氏（東大），津田宏治氏（AIST），Jeff A. Bilmes氏（Univ. of Washington），岡本吉夫氏（JAIST），岩田覚氏（京大），Stefanie Jegelka氏（MPI），Karsten M. Borgwardt氏（MPI），鷲尾隆氏（阪大）



明日(11/4)，本発表に（尐し？）関連したポスター発表があります．
「最小平均費用クラスタリング」 （P4-30）
永野清仁（東大）, 河原吉伸（阪大）, 岩田覚（京大）
また本発表で紹介した研究の一部は，次のプログラムの下に実施されたものです：– JSTさきがけ「知の創生と情報社会」，ERATO「湊離散構造処理系プロジェクト」，
GCOE「計算世界観の深化と展開」，科学研究費補助金（若手B・22700147）