機械学習ゼミ
劣モジュラ最適化と機械学習
Machine Learning
Machine Learning with Submodular Functions
2018/7/7 研究室ゼミ
福田研究室 修士2年

鈴木 新

機械学習ゼミ 劣モジュラ最適化と機械学習目次
0章：記号の意味
1章：学習における劣モジュラ性
2章：劣モジュラ最適化の基礎
3章：劣モジュラ関数の最大化と貪欲法の適用

4章：最大流とグラフカット※時間の都合上，内容めちゃ省略してます．
（気になる方は本を読んでください）

機械学習ゼミ 劣モジュラ最適化と機械学習2記号の意味𝑆 ∩ 𝑇 ・・・集合𝑆と集合𝑇の共通部分（黄）𝑆 ∪ 𝑇 ・・・集合𝑆と集合𝑇の和集合（黄＋赤＋青）𝑆 ⊆ 𝑇・・・集合𝑆は集合𝑇の部分集合
𝑖 ∈ 𝑇・・・ 𝑖は集合𝑇の要素{𝑖}・・・集合の要素𝑖
𝑆 ∖ 𝑇・・・集合𝑆にあって集合𝑇にはない要素（赤）ex) 𝑆 = {1,2}, T = {1,4,5}だったら𝑆 ∖ 𝑇 = 2

機械学習ゼミ 劣モジュラ最適化と機械学習

𝑆

𝑇𝑆∖𝑇𝑇∖𝑆3

1.1はじめに
本書では、機械学習における組合せ的な側面を考える。
組合せ・・・何らかの選択可能な集まりからその一部を選択すること
機械学習でこの組合せが非常に重要となる

選択可能な対象・要素の集まりからその一部を選択する計算⇒集合関数（離散的な関数）の最適化につながる集合関数とは𝑛個の選択可能な対象の数において
台集合：選択される対象の全体(𝑉 = 1, … , 𝑛 )集合関数：𝑓: 2𝑉 ⇒ ℝ

台集合7, 部分集合𝑆 = {3,5,7}

部分集合𝑆において実数値を出力
機械学習ゼミ 劣モジュラ最適化と機械学習

41.1はじめに（集合関数の最適化）
アイスクリーム売上の需要予測を回帰分析で行いたい．しかし関係がない変数は選ばず有用なものを選びたい．
アイスクリーム売上の予測精度に関連する量が𝑓で表されているとすれば，これを最大とするような項目の集合を求める問題になる．
もし，項目の台集合𝑉が「気温」と「料金」だけだったら組合せは｛気温｝， ｛料金｝， ｛気温，料金｝， ｛なし｝の4通り，しかし現実はそんなことない（10個，100個，1000個あるかも）10個・・・ 210 = 1024通り
100個・・・2100 = 1267650600228229401496703205376通り
1000個・・・ 107150860718626732094842504906000181056140481170553360744375038837035105112493612
249319837881569585812759467291755314682518714528569231404359845775746985748039345
677748242309854210746050623711418779541821530464749835819412673987675591655439460
77062914571196477686542167660429831652624386837205668069376通り

どれを採用するか，全パターンを列挙，判別することは不可能
機械学習ゼミ 劣モジュラ最適化と機械学習

51.1はじめに（集合関数の最適化）
このような現象のことを組み合わせ爆発という．
⇒計算機を用いて集合関数最適化などの組み合わせ計算を扱う難しさの根源になっている．
（フカシギお姉さんでYoutube調べるとわかりやすい動画出てきます．）
https://www.youtube.com/watch?v=Q4gTV4r0zRs

組み合わせ爆発を防ぐために様々なアルゴリズムが開発されている．

機械学習ゼミ 劣モジュラ最適化と機械学習

6

1.2劣モジュラ性の導入
劣モジュラ（関数）最適化

集合関数における凸性にあたる構造, かつ凹関数のような性質ももつ．
「集合関数最適化などの組み合わせ的な計算を扱う難しさ」に直面しないよう考える最適化．
集合𝑆と集合𝑇に関して

𝑓 𝑆 +𝑓 𝑇 ≥𝑓 𝑆∪𝑇 +𝑓 𝑆∩𝑇(∀𝑆, 𝑇 ⊆ 𝑉)

(1.1)

この式↑を満たしていれば「劣モジュラ性を満たしている」といえる
組合せ最適化を考える際，劣モジュラ性を満たすモデル（関数）を作成すれば，組み合わせ爆発の問題を回避出来る可能性．
劣モジュラ関数最大化による大規模クラスタリング，2009，入月ら
機械学習ゼミ 劣モジュラ最適化と機械学習

7

1.2劣モジュラ性の導入
𝒇 𝑺 +𝒇 𝑻 ≥𝒇 𝑺∪𝑻 +𝒇 𝑺∩𝑻∀𝑺, 𝑻 ⊆ 𝑽

(1.1)

𝑆 ⊆ 𝑇 ⊆ 𝑉かつ𝑖 ⊆ 𝑉 ∖ 𝑇
𝑆 ′ = 𝑆 ∪ 𝑖 , T ′ = Tを代入すると集合に要素｛i｝を加えた時の関数値の増分𝑓 𝑆 ∪ {𝑖} − 𝑓 𝑆 ≥ 𝑓 𝑇 ∪ 𝑖
Tに包含される小さい集合Sに要素｛i｝を加えた時の関数値の増分−𝑓 𝑇(∀𝑆 ⊆ 𝑇 ⊆ 𝑉, ∀𝑖 ⊆ 𝑉 ∖ 𝑇) (1.2)

Sを包含する大きい集合Tに要素｛i｝を加えた時の関数値の増分小さい集合に要素を加えた時の方が，大きい集合に要素を加えた時よりも影響が大きい
機械学習ゼミ 劣モジュラ最適化と機械学習（詳細は3章で）8

1.2劣モジュラ性の導入
ざっくりいうと（単調）劣モジュラ性とは…
…1個ずつ要素を追加した際に徐々に影響力が小さくなること！
ゲーマー（ゲームたくさん持ってる人）より初心者（ゲーム持ってない人）にゲームソフト一個あげた方が喜びは大きい＋＋

チケット何枚も持ってる人より，一枚も持ってない人にチケットあげた方が喜ぶ＋＋

https://www.youtube.com/watch?v=Z7eMzSHGGAE&t=339s
機械学習ゼミ 劣モジュラ最適化と機械学習

9

1.2劣モジュラ性の導入劣モジュラ性とは1個要素を追加した際に徐々に影響力が小さくなる
・口コミ効果は同じグループ内で口コミを発信した人が少ないほど大きい●来週の合同ゼミがなくなりました，誰に話すのが効果的？
（コミュ障なので二人までにしか流せません）
朝倉研

ゼミ中止の連絡しなきゃ

福田研
ゼミ幹事

1日経つとその人の隣の人に伝わる場合，誰に話すのが効果的？
機械学習ゼミ 劣モジュラ最適化と機械学習

10

1.2劣モジュラ性の導入
劣モジュラ性とは1個要素を追加した際に徐々に影響力が小さくなる
・口コミ効果は同じグループ内で口コミを発信した人が少ないほど大きい
二人とも福田研に話した場合

1日目

2日目

3日目

4日目（朝倉研で伝わってない人がいる…）
機械学習ゼミ 劣モジュラ最適化と機械学習

11

1.2劣モジュラ性の導入
劣モジュラ性とは1個要素を追加した際に徐々に影響力が小さくなる
・口コミ効果は同じグループ内で口コミを発信した人が少ないほど大きい
福田研，朝倉研それぞれ一人の場合

1日目

2日目3日目でコンプリート！
この差が劣モジュラ性！

3日目

同じ集合(研究室)内で要素増やすよりも他集合で増やした方が効果的（同集合で増やしても効果薄）
機械学習ゼミ 劣モジュラ最適化と機械学習

121.3機械学習における劣モジュラ性
劣モジュラ関数の例
カット関数カバー関数劣モジュラ関数最大化を応用した研究も多い
能動学習
ノンパラメトリック・ベイズ推定
インフルエンサーへのオンライン広告問題

離散的なデータ構造を表すのにも適しているコンピュータービジョン分野

機械学習ゼミ 劣モジュラ最適化と機械学習

13

2. 劣モジュラ最適化の基礎凸関数最小化・凹関数最大化は最適化問題として扱いやすい
劣モジュラ関数最適化において• 劣モジュラ関数の背後には凸性があるため，最小化問題は多項式時間で解ける• 劣モジュラ関数の最大化問題はほとんどの問
題設定においてNP困難であるが，劣モジュラ関数の背後には凹性のような性質があるため，かなり良い近似解を多項式時間で計算できる

多項式時間＝ n𝑐⇔指数時間＝c 𝑛(cは定数)

現実的な時間で解を求めることができない

この章では劣モジュラ関数の紹介と，軽く証明を行います（カバー関数とカット関数，実際に最適化するのは次章以降）

機械学習ゼミ 劣モジュラ最適化と機械学習

14http://www.nikkou-sanraku.jp/introduction/index01.html http://www.homemate-research.com/tourism_map/09/nikkoshi.shtml
https://mapandnews-japan.com/09nikkotoshogu/demomobile.html?csv=poi.csv

2.1.1劣モジュラ関数の具体例（カバー関数）
ある観光地に複数の観光スポットがある．
Wi-Fiパケットセンサー(PS)を4台（有限集合V = {1,2,3,4} ）おける時

PSエリア1

PSエリア2

PSエリア3

PSエリア4

パケットセンサーを置くと点線円内の観光スポットをカバーできる．
この時，パケットセンサーを置く場所の集合をS ⊆ Vとして，関数は𝑆に対応するパケットセンサーが𝑓𝑐𝑜𝑣 𝑆 =カバーする観光スポットの数
機械学習ゼミ 劣モジュラ最適化と機械学習

15

2.1.1劣モジュラ関数の具体例（カバー関数）
例えば， 𝑆 = 1 , 2 , 1,2 の時，𝑓𝑐𝑜𝑣 𝑆 はそれぞれ，
 エリア1に置いたとき
𝑓𝑐𝑜𝑣 1 = 3
 エリア2に置いたとき
𝑓𝑐𝑜𝑣 2 = 6
 エリア1,2に置いたとき
𝑓𝑐𝑜𝑣 1,2 = 8

PSエリア1にWi-FiPSおいたとき

PSエリア2にWi-FiPSおいたとき
PSエリア1,2にWi-FiPSおいたとき
機械学習ゼミ 劣モジュラ最適化と機械学習

16

2.1.1劣モジュラ関数の具体例（カバー関数）
 範囲が重なっているエリアがあるため，線形性は成り立たない
𝑓𝑐𝑜𝑣 1 + 𝑓𝑐𝑜𝑣 2 ≠ 𝑓𝑐𝑜𝑣 1,2
 今回，Wi-FiPSを置ける場所は4か所なので，Wi-FiPS設置個所の部分集合の組み合わせは
24 = 16通り
 この関数（カバー関数）の劣モジュラ性を証明（のイメージ）．
重複部分がある⇒新しいWi-FiPSを置けば置くほど，設置する効果は減少してく．
𝑓 {1} ∪ {2} − 𝑓 1 ≥ 𝑓 1,2 ∪ 3 − 𝑓 1,283118𝑓 𝑆 ∪ {𝑖} − 𝑓 𝑆 ≥ 𝑓 𝑇 ∪ 𝑖 − 𝑓 𝑇(∀𝑆 ⊆ 𝑇 ⊆ 𝑉, ∀𝑖 ⊆ 𝑉 ∖ 𝑇) (1.2)
機械学習ゼミ 劣モジュラ最適化と機械学習

172.1.2劣モジュラ関数の具体例（グラフカット関数）
グラフカット関数
ネットワークやグラフに関する最適化において重要な役割を果たす劣モジュラ関数．無向グラフと有向グラフの2種類のパターンがある．
⇒情報処理の画像処理などに使われる．

2

1

364
5
10711
無向グラフのネットワーク
矢印あれば有向グラフ

8912
CT画像から肝臓の部分だけ取り出したい
http://zellij.hatenablog.com/entry/20131004/p1
機械学習ゼミ 劣モジュラ最適化と機械学習

18

2.1.2劣モジュラ関数の具体例（グラフカット関数）
無向グラフの場合
12個の頂点からなる頂点集合𝜈 = {1, … , 12}と（向きのない）枝集合𝜀が与えられている．
頂点の部分集合S ⊆ 𝜈について，枝の一端がS，もう一端が𝜈 ∖ Sに含まれるような枝集合𝜀の部分集合を𝛿(S) ．|𝛿(S)|を枝の本数とする．

S213645107118129頂点の部分集合
S = {1,2,3}の時，枝の部分集合は左図の点線の部分，つまり𝛿({1,2,3}) = 7となる．
𝛿({1}) = 4
𝛿({1,2}) = 5
𝛿({1,3}) = 8

機械学習ゼミ 劣モジュラ最適化と機械学習

19

2.1.2劣モジュラ関数の具体例（グラフカット関数）
この関数（カバー関数）の劣モジュラ性のチェック．
S

213645107118129頂点の部分集合
S = {1,2,3}の時，枝の部分集合は左図の点線の部分，つまり𝛿({1,2,3}) = 7となる．
𝛿({1}) = 4
𝛿({1,2}) = 5
𝛿({1,3}) = 8

𝛿({1,2}) + 𝛿({1,3}) ≥ 𝛿({1,2,3}) + 𝛿({1})
5874劣モジュラ性を満たす．（他のパターンでやってみても満たすはず…）
機械学習ゼミ 劣モジュラ最適化と機械学習

20

2.1.2劣モジュラ関数の具体例（グラフカット関数）
有向グラフの時はどうなるか

頂点の部分集合S = {1,2,3}の時，枝の部分集合は浸り
図の点線の部分，つまり
𝛿𝑑 ({1,2,3}) = 5となる．
𝛿𝑑 ({1}) = 3
𝛿𝑑 ({1,2}) = 4
𝛿𝑑 ({1,3}) = 5

𝛿𝑑 ({1,2}) + 𝛿𝑑 ({1,3}) ≥ 𝛿𝑑 ({1,2,3}) + 𝛿𝑑 ({1})
4553劣モジュラ性を満たす．
⇒一般式に直してざっくり証明してみよう
機械学習ゼミ 劣モジュラ最適化と機械学習

21

2.1.2劣モジュラ関数の具体例（グラフカット関数）
任意に与えられた頂点部分集合をS, T ⊂ 𝜈は4つに分けられる．

𝜈1 = 𝑆 ∖ 𝑇

𝜈2 = 𝑇 ∖ 𝑆

𝜈3 = 𝑆 ∩ 𝑇

𝜈4 = 𝜈 ∖ (𝑆 ∪ 𝑇)

𝜈
𝜈4𝑆
𝜈1

𝑇
𝜈3

𝜈2

𝜈 = 𝜈1 ∪ 𝜈2 ∪ 𝜈3 ∪ 𝜈4

これより，
𝑆 = 𝜈1 ∪ 𝜈3 , 𝑇 = 𝜈2 ∪ 𝜈3 , 𝑆 ∪ 𝑇 = 𝜈1 ∪ 𝜈2 ∪ 𝜈3
𝜈𝑎 から出て𝜈𝑏 に入るような全ての枝の枝容量の総和を𝐶𝑎,𝑏 と置くと．
𝛿(𝑆) = 𝐶1,2 + 𝐶1,4 + 𝐶3,2 + 𝐶3,4
𝛿(𝑇) = 𝐶2,1 + 𝐶2,4 + 𝐶3,1 + 𝐶3,4
𝛿(𝑆 ∪ 𝑇) = 𝐶1,2 + 𝐶1,4 + 𝐶3,2 + 𝐶3,4
𝛿(𝑆 ∩ 𝑇) = 𝐶1,2 + 𝐶1,4 + 𝐶3,2 + 𝐶3,4

𝛿(𝑆) + 𝛿(𝑇) − 𝛿 𝑆 ∪ 𝑇 − 𝛿 𝑆 ∩ 𝑇
機械学習ゼミ 劣モジュラ最適化と機械学習

𝜈1

𝜈3𝑇
𝜈2

𝜈4
𝜈1 = 1,2 , 𝜈2 = 9 ,𝜈3 = 3 , 𝜈4 = 1,2,3,9以外 ,= 𝐶1,2 + 𝐶2,1 ≥ 0
22

2.1.2劣モジュラ関数の具体例（グラフカット関数）𝜈𝜈𝑎 から出て𝜈𝑏 に入るような全ての枝の枝容量の総和を𝐶𝑎,𝑏 と置くと．
𝛿(𝑆) = 𝐶1,2 + 𝐶1,4 + 𝐶3,2 + 𝐶3,4
𝛿(𝑇) = 𝐶2,1 + 𝐶2,4 + 𝐶3,1 + 𝐶3,4
𝛿(𝑆 ∪ 𝑇) = 𝐶1,2 + 𝐶1,4 + 𝐶3,2 + 𝐶3,4
𝛿(𝑆 ∩ 𝑇) = 𝐶1,2 + 𝐶1,4 + 𝐶3,2 + 𝐶3,4
𝛿(𝑆) + 𝛿(𝑇) − 𝛿 𝑆 ∪ 𝑇 − 𝛿 𝑆 ∩ 𝑇= 𝐶1,2 + 𝐶2,1 ≥ 0

𝜈4𝑆
𝜈1𝑇
𝜈3

𝜈2

𝑇

𝑓 𝑆 +𝑓 𝑇 ≥𝑓 𝑆∪𝑇 +𝑓 𝑆∩𝑇𝜈1 = 1,2 , 𝜈2 = 9 ,𝜈3 = 3 , 𝜈4 = 1,2,3,9以外 ,機械学習ゼミ 劣モジュラ最適化と機械学習

23

3. 劣モジュラ最大化と貪欲法
3章：劣モジュラ最大化と貪欲法
劣モジュラ関数最大化において• 劣モジュラ関数の最大化問題はほとんどの問
題設定においてNP困難であるが，劣モジュラ関数の背後には凹性のような性質があるため，かなり良い近似解を多項式時間で計算できる
主に単調劣モジュラ関数最大化について考えます
単調劣モジュラ関数最大化

目的：𝑓 𝑆 ⇒ 最大
制約： S ⊆ 𝑉, |𝑆| ≤ 𝑘
NP困難な問題⇒厳密な最適解を多項式時間で求めることは困難
機械学習ゼミ 劣モジュラ最適化と機械学習

24

3.1 カバー関数最大化問題ある観光地に複数の観光スポットがある．
Wi-Fiパケットセンサー(PS)を2台（有限集合V = {1,2,3,4} ）おける時
どのエリアに置けば多くの観光地のデータ取れる？

PSエリア1

PSエリア2

PSエリア3

PSエリア4

⇒まずは全組み合わせを考えてみる
𝑓𝑐𝑜𝑣 {1} = 3, 𝑓𝑐𝑜𝑣 {2} = 6, 𝑓𝑐𝑜𝑣 {3} = 4, 𝑓𝑐𝑜𝑣 {4} = 5,𝑓𝑐𝑜𝑣 {1,2} = 8, 𝑓𝑐𝑜𝑣 {1,3} = 7, 𝑓𝑐𝑜𝑣 {1,4} = 8, 𝑓𝑐𝑜𝑣 {2,3} = 9,𝑓𝑐𝑜𝑣 {2,4} = 11, 𝑓𝑐𝑜𝑣 {3,4} = 8,
機械学習ゼミ 劣モジュラ最適化と機械学習

25

3.1.2カバー関数最大化問題
近似アルゴリズム（貪欲法の導入）
全組み合わせを考えると，𝑓𝑐𝑜𝑣 {2,4} = 11が最大となる⇒組み合わせ数が多くなると，列挙しきれなくなる
近似アルゴリズムを用いる⇒アルゴリズムによって近似解が多項式時間に得られる．
⇒最適値と近似解の目的関数の比がどんな場合でも一定値より良くなることが証明されている．

※近似率αα ∗ (問題の最適値) ≤ (近似アルゴリズムが出力する解)
カバー関数の場合，貪欲法を用いる（近似率は0.63)
0.63 ∗ (問題の最適値) ≤ (貪欲法が出力する解)機械学習ゼミ 劣モジュラ最適化と機械学習

26

3.1カバー関数最大化問題
近似アルゴリズム（貪欲法の導入）
Step0. 𝑆を空集合{}とする．

Step1. | 𝑆 |= 𝑘ならば𝑆𝐺𝐴 ≔ 𝑆を出力し終了. | 𝑆 |≠𝑘ならばstep2へ
Step2. 𝑓(𝑆 ∪ 𝑖 )を最大化する𝑖 ∈ V ∖ 𝑆を1つ選び，𝑆 ∪ 𝑖 = 𝑆と置きなおす．
今回の場合集合𝑆 はWi − FiPSの設置場所，𝑘はWi − FiPSの数,
Step1.
{} = 0 < 2より，step2.へ
Step2.
𝑖 = 3が𝑓を最大化．
𝑆 = {2}となる．

機械学習ゼミ 劣モジュラ最適化と機械学習

27

3.1カバー関数最大化問題
近似アルゴリズム（貪欲法の導入）
Step0. 𝑆を空集合{}とする．

Step1. | 𝑆 |= 𝑘ならば𝑆𝐺𝐴 ≔ 𝑆を出力し終了. | 𝑆 |≠𝑘ならばstep2へ
Step2. 𝑓(𝑆 ∪ 𝑖 )を最大化する𝑖 ∈ V ∖ 𝑆を1つ選び，𝑆 ∪ 𝑖 = 𝑆と置きなおす．
今回の場合集合𝑆 はWi − FiPSの設置場所，𝑘はWi‐ FiPSの数,
Step1.
{2} = 1 < 2より，step2.へ
Step2.
𝑖 = 4が𝑓を最大化．
𝑆 = {2,4}となる．

Step1.
{3,4} = 2 = 𝑘より終了
出力解は11となる．
機械学習ゼミ 劣モジュラ最適化と機械学習

28

3.1カバー関数最大化問題
近似アルゴリズム（貪欲法の導入）ある観光地に複数の観光スポット がある．
Wi-Fiパケットセンサー(PS)を2台（有限集合V = {1,2,3,4} ）おける時どのエリアに置けば多くの観光地のデータ取れる？

PSエリア1 PSエリア2 PSエリア3

PSエリア4𝑓({𝑃2 , 𝑃4 })=11が最適解，貪欲法で解くと 𝑓({𝑃3 , 𝑃1 })=10に⇒0.63近似は満たしている．
機械学習ゼミ 劣モジュラ最適化と機械学習

29

3.3カバー関数（センサ配置問題の活用）
・Wi-FiPSは無限には置けない
・実際は計測の精度なども絡んでくる．
⇒近くにWi-FiPS複数ある場合は観測誤差が小さい

観測誤差を小さくなるようWi-FiPSを配置する問題になったり

機械学習ゼミ 劣モジュラ最適化と機械学習

30

4.1.1.最大流とグラフカット
4章：グラフカットと最大流劣モジュラ関数最小化において多項式時間＝ n𝑐⇔指数時間＝c 𝑛(cは定数)• 劣モジュラ関数の背後には凸性があるため，最小化問題は多項式時間で解ける
一般の劣モジュラ関数・・・𝒪(𝑛5 𝐸𝑂 + 𝑛6 )←最悪計算量⇒要素数多い計算，反復計算にはまだ不十分

個々の扱う問題で十分な表現力の範囲で高速に最小化可能な劣モジュラ関数の特殊クラスを考える

機械学習ゼミ 劣モジュラ最適化と機械学習

31

4.1.1.最大流とグラフカット
グラフカットコンピュータービジョンで頻繁に扱われる
数万～数百万オーダーの問題に対しても実用的時間で適用可能なアルゴ
リズム

劣モジュラの視点から見ると，カット関数（劣モジュラ性あり）の最小化を行っている．

カット関数の最小化
最大流アルゴリズム（理論的・実用的に高速なアルゴリズムの適用が可能）

機械学習ゼミ 劣モジュラ最適化と機械学習

32

4.1.1.カットとフロー
𝒱1𝒱22有向グラフ𝒢(𝒱, ℰ)上で，136頂点集合𝒱 = {𝑠} ∪ {𝑡} ∪ 𝑉
6{𝑠}：ソース（特別な頂点）
132
st{𝑡}：シンク（sとは異なる特別な頂点）
𝑉 = {1, . . , 𝑛}:それ以外のn個の頂点 4324枝集合ℰ6各枝𝑒 ∈ ℰには正の枝容量c𝑒 が含ま
𝑉 = {1,2,3,4},頂点数6, 枝数9の場合れている．

𝒔 − 𝒕カット
有向グラフ𝒢(𝒱, ℰ) を順序付きの分割(𝒱1 , 𝒱2 )のうち，𝑠 ∈ 𝒱1 , t ∈ 𝒱2を満たすもの. 𝑉の任意の部分集合𝑆を用いて,( 𝑠 ∪ 𝑆, {𝑡} ∪ (𝑉 ∖ 𝑆))

機械学習ゼミ 劣モジュラ最適化と機械学習

33

4.1.1.カットとフロー
𝜅𝑠−𝑡 {}

𝒔 − 𝒕カットについて，その容量は
𝜅𝑠−𝑡 𝑆 =𝑐𝑒𝑒∈𝛿𝒢𝑜𝑢𝑡 ( 𝑠 ∪𝑆)と定義
この関数を𝑠-𝑡カット関数と呼ぶ右図でいうと
𝜅𝑠−𝑡 {} = 𝑐𝑠,1 + 𝑐𝑠,2 = 10
𝜅𝑠−𝑡 {1} = 𝑐1,2 + 𝑐1,3 + 𝑐𝑠,2 = 9
𝜅𝑠−𝑡 {2} = 𝑐𝑠,1 + 𝑐2,3 + 𝑐2,4 = 13

𝜅𝑠−𝑡 {1}𝜅𝑠−𝑡 𝑆 を最小にするような𝒔 − 𝒕カットを求める．
⇒最大流アルゴリズムを用いると高速に解ける
機械学習ゼミ 劣モジュラ最適化と機械学習

𝜅𝑠−𝑡 {2}344.1.1.フローと最大流問題
最大流アルゴリズムを用いる際に重要なフローを定義する．

フロー• 有向グラフ𝒢({𝑠} ∪ {𝑡} ∪ 𝑉, 𝜀)において,ソース𝑠（入口）からシンク𝑡（出口）へのモノの流れ• 各枝𝑒に， 𝑒の上の流れを表す実数値変数𝜉𝑒 を𝑒上の流れを表すとすると，変数ベクトル𝝃 = 𝜉𝑒 𝒆∈𝜀 をフローと定義
実行可能フロー・・・以下の二つの制約を満たす●容量制約
各枝𝑒に， 𝑒上のフローが0以上𝑐𝑒 以下●流量保存制約𝑠, 𝑡以外の頂点𝑖において，𝑖から出るフローと𝑖に入るフローの量が等しい

流量は𝑠から出ていくフロー𝝃の総和
機械学習ゼミ 劣モジュラ最適化と機械学習実行可能フローの例
流量は2+2=435

4.1.1.フローと最大流問題
最大流問題流量を最大にするような実行可能フローを見つける問題

最大流

1

6

最大流問題の最適解

3s2
1

362t

4
目的関数：
3246
𝜉(𝑠,1) + 𝜉(𝑠,2) ⇒ 最大
制約：
𝜉(1,3) + 𝜉(1,2) − 𝜉 𝑠,1 = 0,
𝜉(2,3) + 𝜉(2,4) − 𝜉 𝑠,2 − 𝜉 1,2 = 0, 流量
保存𝜉(3,𝑡) + 𝜉(3,4) − 𝜉 1,3 − 𝜉 2,3 = 0,
𝜉(4,𝑡) + 𝜉(3,4) − 𝜉 2,4 = 0,0 ≤ 𝜉 𝑠,1 ≤ 6,0 ≤ 𝜉 𝑠,2 ≤ 4,0 ≤ 𝜉 1,2 ≤ 3,0 ≤ 𝜉 1,3 ≤ 2,0 ≤ 𝜉 2,3 ≤ 1,0 ≤ 𝜉 2,4 ≤ 6,0 ≤ 𝜉 3,4 ≤ 2,0 ≤ 𝜉 3,𝑡 ≤ 6,0 ≤ 𝜉 4,𝑡 ≤ 3,

機械学習ゼミ 劣モジュラ最適化と機械学習

容量制約

36

4.1.1.フローと最大流問題
𝑠 − 𝑡カットの容量𝜅𝑠−𝑡 𝑆 はソース側の頂点からシンク側の頂点に入る枝容量の総和
容量制約より実行可能フロー𝜉の流量 ≤ (𝑠 − 𝑡カットの容量𝜅𝑠−𝑡 𝑆 )実行可能フロー𝜉の流量 の最大値・・・最大流流量(𝑠 − 𝑡カットの容量𝜅𝑠−𝑡 𝑆 )の最小値・・・𝑠-𝑡カット容量の最小値
最大流最小カット定理
最大流流量＝𝑠-𝑡カット容量の最小値

機械学習ゼミ 劣モジュラ最適化と機械学習

37

4.1.1. フローと最大流問題
最大流流量＝6, 𝑠-𝑡カット容量の最小値＝6アルゴリズムを用いて最大流流量を求めてみる

機械学習ゼミ 劣モジュラ最適化と機械学習

38

4.1.2.最大流アルゴリズム
ソースsからシンクtへの有効パスをs-tパスと呼ぶ
紹介するアルゴリズム
反復法+増加パスアルゴリズム

機械学習ゼミ 劣モジュラ最適化と機械学習

39

4.1.2.最大流アルゴリズム（反復法）
a)
1

0/6

0/3

s0/42b)

0/2

30/6

2/6

0/2

0/1
40/6t

2/6

10/3

s
1/4

22/2

3

1/6
2/2

1/1
4t
2/30/6s⇒2 ⇒3 ⇒tというs-tパスでmin 4,1,6 = 1よりフローを1流す

32/2

0/1

20/6t

2/3

40/6s⇒1 ⇒3 ⇒4 ⇒tというs-tパスでmin 6,2,2,3 = 2よりフローを2流す
2/2d)
1
3
1/6
2/6

初期状態c)

0/3

s
0/4

0/3

12/2s
2/4

0/3
22/2

1/1
4t
3/3

1/6s⇒2 ⇒4 ⇒tというs-tパスでmin 4 − 3,6,3 − 2 = 1よりフローを1流す

機械学習ゼミ 劣モジュラ最適化と機械学習

40

4.1.2.最大流アルゴリズム（反復法）
これより流量は２＋２＝４
しかし，実際の最大流は６（P42より）⇒単純な反復法だと最大流量を求められない反復法アルゴリズム⇒「残余ネットワーク」と「フロー更新」の考え方を導入

機械学習ゼミ 劣モジュラ最適化と機械学習

41

4.1.2.最大流アルゴリズム（反復法）「残余ネットワーク」と「フロー更新」の導入
残余ネットワーク・・・容量制約を満たしつつ，𝜉をどの程度変化させられるかを表現する有向グラフ
𝜉(𝑖,𝑗) = 0を満たす(𝑖, 𝑗) ∈ ℰ⇒𝒢 𝜉 では(𝑖, 𝑗)は(𝑖, 𝑗)のまま
𝜉𝑐(𝑖,𝑗) = 𝑐(𝑖,𝑗)0 ≤ 𝜉(𝑖,𝑗) ≤ 𝑐(𝑖,𝑗) を満たす(𝑖, 𝑗) ∈ ℰ⇒

𝒢 𝜉 では(𝑖, 𝑗)は(𝑖, 𝑗)のまま実行可能フロー 残余ネットワーク
30/3
121242/6
1ss
122/2
11332

𝜉

𝑐(𝑖,𝑗) = 𝑐(𝑖,𝑗)𝜉(𝑖,𝑗) = 0を満たす(𝑖, 𝑗) ∈ ℰ⇒

𝒢 𝜉 では(𝑖, 𝑗)は(𝑖, 𝑗)のまま
𝜉

𝑐(𝑖,𝑗) = 𝑐(𝑖,𝑗)s⇒2 ⇒4 ⇒3 ⇒tという新しいs-tパスが登場
機械学習ゼミ 劣モジュラ最適化と機械学習

42

4.1.2.最大流アルゴリズム（反復法）

実行可能ネットワーク
12/60/3

s2/42/2

1/12

残余ネットワーク311/64232/2ts22
3/3
421/6
一見これ以上s-tパス無いように見えるが実行可能ネットワーク
2/2
13
3/62/6s
4/4

0/320/2

1/1
3/6

42

131255t

341s⇒2 ⇒4 ⇒ 3⇒tというs-tパスでmin 2,5,2,5 = 2よりフローを2流す
残余ネットワーク
4t

3/3

12

s4

流量は２＋４で６になる 2だけ減らす
機械学習ゼミ 劣モジュラ最適化と機械学習

3223321334t
3343

補足：劣モジュラの凸性の解説
直感的な解説．
台集合𝑉 = 1 の場合，
集合関数はor 1 の2通りの実数値への割り当て集合関数を拡張
𝑓と𝑓 1 間を線形補完

台集合𝑉 = {1,2}の場合
集合関数はor 1 or 2 or 1,2 の4通りの実数値への割り当て集合関数を拡張

劣モジュラの式を満たしている限り凸となる
機械学習ゼミ 劣モジュラ最適化と機械学習

44補足：劣モジュラ関数の種類
𝑓 𝑆 +𝑓 𝑇 ≥𝑓 𝑆∪𝑇 +𝑓 𝑆∩𝑇(∀𝑆, 𝑇 ⊆ 𝑉)

(1.1)

• 単調劣モジュラ関数• 非負劣モジュラ関数• 対象劣モジュラ関数• 正規化された劣モジュラ関数など多くの劣モジュラ関数があります．
単調・・・より多くのものを加えたらより多くに影響を与えられる+劣モジュラ・・・徐々に影響力が小さくなっていく
ちなみに式(1.1)の不等号が逆になると優モジュラ関数，等号になるとモジュラ関数と定義されます．
機械学習ゼミ 劣モジュラ最適化と機械学習

45

プログラムの紹介
ETH ZurichのAndreas Krause先生が劣モジュラ最適化のmatlabプログ
ラムを複数公開しています．

https://las.inf.ethz.ch/sfo/

機械学習ゼミ 劣モジュラ最適化と機械学習

46

参考文献
河原吉伸，永野清仁『劣モジュラ最適化と機械学習』 講談社

『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！
https://www.youtube.com/watch?v=Q4gTV4r0zRs
大人になってからの再学習
http://zellij.hatenablog.com/entry/20131004/p1
Hakky St, 劣モジュラ最適化と機械学習
https://www.slideshare.net/ssuser77b8c6?utm_campaign=profiletracking&ut
m_medium=sssite&utm_source=ssslideview

アルゴリズムが世界を変えるSeason3
https://www.youtube.com/watch?v=Z7eMzSHGGAE&t=339s
Matlab Toolbox for Submodular Function Optimization (v 2.0), Andreas Krause

https://las.inf.ethz.ch/sfo/日光観光関連（山楽，ホームメイト，MAP&NEWS）

機械学習ゼミ 劣モジュラ最適化と機械学習

47