第18回情報論的学習理論ワークショップ

劣モジュラ関数による構造と学習の橋渡し：
構造正則化, 確率的劣モジュラ
大阪大学 産業科学研究所

河原 吉伸

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

2

劣モジュラ関数
次式を満たす集合関数 F : 2V ! R を 劣モジュラ関数 と呼ぶ：
[定義]

F (S) + F (T )F (S [ T ) + F (S \ T ) (8 S, T ✓ V )⇒ 集合関数における凸関数として捉えられる（ただし凹的な性質も持つ）
凸性（連続関数）

対応する概念

自然に現れる構造

劣モジュラ性（集合関数）
V 1
2

5

4
6

3

集合関数

7 部分集合実数値

F (S) + F (T )  F (S \ T ) + F (S [ T )(S, T ✓ V )3補足） べき集合と特性ベクトルべき集合（対応する {0, 1}d の空間）x3

{1,2,3}

{3}

⇡

{}

x1
x2

(1,1,0){0, 1}d

2

2V

o

部分集合

S

つまり，集合関数は {0, 1}d 上の実数値関数とも見なせる

2{2}(1,0,1)(0,1,1){1,2} {1,3} {2,3}{1}(0,0,1)

特性ベクトル

IS

第 i 成分 =

1 if
0 if

i2S
i 62 S

4例）マルコフ確率場と劣モジュラ性
機械学習や統計分野などでよく用いられる構造的な確率モデル：
元の画像（隠れ変数） x

xi
観測画像 yyi
MRF事前分布Pr(x) =

1
exp
Z

X

(i,j)2E✓˜ij (xi , xj )!

5例）マルコフ確率場と劣モジュラ性
MRFの最大事後確率（MAP）推定：x̂ = arg max

NX

k 番目の観測

Pr(x|y (k) )✓ij

x2{0,1}V k=1= arg max

N Y
X

x2{0,1}V k=1 i2V(k)

Pr(yi )|xi ) Pr(x)✓= arg max N log(Pr(x)) +x2{0,1}V✓x2{0,1}VN X
X

k=1 i2V= arg min NX(k)log(Pr(yi |xi ))✓˜ij (xi , xj ) + N log Z +minx2{0,1}V

X

i2V

◆

N
XX

i2V k=1(i,j)2E

pairwise terms

等価

xj

xi

✓i (xi ) +X(i,j)2E(k)log(Pr(yi |xi ))◆unary terms✓ij (xi , xj )エネルギー最小化

6例）マルコフ確率場と劣モジュラ性• １階エネルギー最小化：

minx2{0,1}VX✓i (xi ) +i2V

X✓ij (xi , xj )⇒ 一般に「NP困難」(i,j)2E

一種のスムースネス• １階のエネルギー関数における劣モジュラ性： ⇒ 物理的，応用的に妥当な仮定✓ij (1, 0) + ✓ij (0, 1)✓ij (1, 1) + ✓ij (0, 0)（attractiveなイジング模型などはこの特殊ケース）• 劣モジュラな１階エネルギー関数最小化は効率的に解ける⇒ CVで用いられるグラフカット

7例）マルコフ確率場と劣モジュラ性
劣モジュラ関数は，グラフ上の隣接構造よりもさらにリッチな表現が可能（ピクセル間の平滑性 ⇒ スーパーピクセル内の平滑性）．
Int J Comput Vis (2009) 82: 302–324

ピクセル間の平滑性✓ij (1, 0) + ✓ij (0, 1)✓ij (1, 1) + ✓ij (0, 0)

✓ij

min

x2{0,1}VX

i2V✓i (xi ) +

xj

ピクセル間
の平滑性

＋
色の情報

＋

＋

…

xi

(Kohli+ 09) よりX(i,j)2E✓ij (xi , xj )min

x2{0,1}VX

i2V

スーパーピクセルの平滑性✓i (xi ) +X(i,j)2E✓ij (xi , xj ) +X✓c (xc )c2C

この場合でも，（一般化された）グラフカットで高速に解ける⇒ より一般にどういう分布を用いて学習に用いることができるのか？

8

本講演のトピック
今日の講演では，MRFとカット関数（劣モジュラ関数）との関係に代表される，劣モジュラ関数を用いた構造的学習について，特に• 劣モジュラ関数と，構造的な学習モデルとの関係は？
• この関係を，どのようにして学習に用いることができるのか？
という点に注目する．そして，その具体的なアプローチとしての• 「劣モジュラ関数を用いた構造正則化学習」• 「劣モジュラ関数から得られる確率分布を用いた学習」に焦点をあてて話を進める．

9

正則化とスパース性
lpノルムによる正則化：

min l(w) +w2Rdp· kwkpl1-正則化（p = 1）：l2-正則化（p = 2）：w1w1
損失関数値の等位集合

w2

w2
解が軸に乗りやすいため，疎な解が得られやすい

10

構造正則化
正則化の考え方を拡張して，既知の構造的関係に近づくように，
パラメータが推定されるような正則化項を設計して加える：
構造正則化項min l(w) +· ⌦(w)

induced for L(w ) + ⌦(w )w2Rd Sparsity patterns
P
Lasso: ⌦(w ) =損失関数

i |wi |

こういった変数間の組合せ的PGroup Lasso (Yuan and Lin, 2006):⌦(w)=
g 2G kwg k構造を正則化項として組込む
Group Lasso when groups overlap: ⌦(w ) =グラフ構造

グループ構造階層構造

P

g 2G kwg k

その他，有向グ
ラフ上のパスや，
２次元グリッド
上でのブロック構造など．

11

構造正則化の例
これまでに様々なタイプの構造正則化が提案され応用されてきた：• グループ lasso (Yuan & Lin 07)­ 与えたグループ単位でスパース性が得られる正則化．グループを階層的に構成した階層的 lasso (Jenatton+ 11) や，DAG上のパスを形成するよう構成したパス・コーディング (Mairal & Yu 13) などの拡張がある．

• （隠れ）グループ lasso (Jacob+ 09)­ 与えたグループの補集合単位でのスパース性が得られる正則化．グ
ラフ上で隣接する２変数をグループとする`グラフ lasso’も含まれる．

• 結合 lasso (Tibshirani+ 05), 一般化結合 lasso (Tibshirani & Taylor 11)­ グラフ上で隣接するノードに対応する２変数の値が近くなるようなス
パース性が得られる正則化．ハイパーグラフを用いた高階の場合への拡張 (Takeuchi+ 15) などがある．

− その他にも，種々の応用中の構造に対する正則化が提案されている．

12

劣モジュラ関数を用いた正則化• 近年，多くの構造的スパース性が，劣モジュラ関数（の緩和）を正則化として用いて得られることが指摘される (Bach 10, 11)．
構造正則化項min l(w) +· ⌦(w)

induced for L(w ) + ⌦(w )w2Rd Sparsity patterns
P
Lasso: ⌦(w ) =損失関数

i |wi |

劣モジュラ関数の連続緩和

Group Lasso (Yuan and Lin, 2006): ⌦(w ) =Group Lasso when groups overlap: ⌦(w ) =グラフ構造

グループ構造階層構造

P

g 2G kwg kP

g 2G kwg k

その他，有向グ
ラフ上のパスや，
２次元グリッド
上でのブロック構造など．

13

劣モジュラ関数に基づく議論の利点• 劣モジュラ関数という一般的な枠組みの中で議論が可能⇒ ­ 種々の構造を，統一的な枠組みの中で扱うことができる（最終的には，実装なども共通化できる）．
­ 組合せ最適化分野で議論されてきた，様々な理論やアルゴリ
ズムが利用できる．
• 特に，劣モジュラ関数がグラフ表現可能な場合には，学習に伴う最適化が高速に計算可能となる．

14例） 結合正則化
一般化結合（generalized fused）正則化 (Tibshirani & Taylor 11)：
各変数に対応するノードを持つ（有向）グラフ G=(E, V) 上で，隣接する変数の値が近くなるような正則化．

⌦F,1 (w) =X(i,j)2E

aij |wiwj |隣接行列の要素=（等価）

カット関数のl∞ノルムによる緩和（ロヴァース拡張）

F (S) =

X(i,j)2E{aij : i 2 S, j 2 V \ S}

一階エネルギー関数におけるスムースネスを課すのと等価

隣接する変数に関する係数が近い値になる

15例） 結合正則化
数値例： 左図のような値のパラメータβを用いて，y ＝ Xβ＋ε（ノイズ）のようにデータを生成.* 中図： ラッソによる推定．右図： ２次元格子状グラフを用いた一般化結合正則化（＋l1項）による推定．
真のパラメータ

ラッソによる推定

一般化結合正則化による推定*) 訓練データは80サンプル．ノイズは標準偏差0.05のガウス雑音．
正則化パラメータは5-fold CVにより選択．

16例） グループ型の正則化
グループ型の正則化：

Sparsity patterns induced for L(w ) + ⌦(w

変数上に，グループ構造 G （各要素が V の部分集合）が与えられたときに，
P
Lasso: ⌦(w ) = i |wi |各グループ内の変数が同時にゼロになりやすくなるような正則化．

⌦F,p (w) =X

g2G

dg kwg kp

Group Lasso (Yuan and Lin, 2006): ⌦(w ) =(グループ正則化 (Yuan & LinGroup07)) Lasso when groups overlap: ⌦(w ) =⇡（ほぼ等価）

P

g 2G kw

P

g 2G kwg

被覆関数のlpノルムによる緩和：F (S) =

X

{dg : g 2 G, g \ S 6= ;}グループへの重み

グループ内のものは同時にゼロになりやすい．

Sparsity tutorial II, ECML 2

17例） グループ型の正則化
数値例： グループは 1〜3, 2〜6, 5〜9, 8〜12, … のように設定．

minw ku1wk +1 |w| +

2 ⌦group (w) の計算例*
u
w*

0.5

(a)

0

0.5

(b)
1
0

10

20

*) u は（−1,＋1）でランダムに生成

3040

d¯g = 2 ， 1 =50

2 = 0.3 ．

18

劣モジュラ関数のlpノルムを用いた凸緩和
lpノルムと，w のサポート上の単調劣モジュラ関数 F から成る関数

11ph(w) = kwkp + F (supp(w))
prのタイトな斉次凸下界（ただし，1/p + 1/r = 1 ）：˜ F,p (w) = sup w> s such that ksS kr  F (S) (8S ✓ V )
⌦
r
s2RV

例） F (S) = |S|

1/2(Obozinski & Bach 12)

の場合：

w1

w1

l2

F

w2

w2

19

劣モジュラ関数から得られる構造正則化
劣モジュラ関数から得られる構造正則化の例：• グループ型の正則化­ グループlasso (Yuan & Lin 07) と同様のスパース性が，被覆関数の緩和により得られる (Obozinski & Bach 12)．この拡張として，階層的構造 (Jenatton+ 11) や，DAG上のパスを形成するパス正則
化 (Mairal & Yu 13) などの拡張が提案されている．

• 結合 lasso (Tibshirani+ 05), 一般化結合 lasso (Tibshirani & Taylor 11)­ 無向グラフのカット関数のロヴァース拡張として得られる(Bach 11)．
ハイパーグラフを用いた高階への拡張 (Takeuchi+ 15) や，有向グ
ラフを用いた拡張 (Bo+, in press) などがある．

• その他の正則化­ スケールフリー・ネットワーク正則化 (Defazio & Caetano 12) など．

20

高階結合正則化• 与えたグループ内（eg. 商品カテゴリ）のパラメータのとる値が，一致しやすくなるような正則化を用いる：
01⌦ho ( ) =

X

g2G

VI

@

X

i2{j1 ,...,js( ikjs )c1,i +kjs (✓max✓1k ) +kjt (✓0

k
✓max
)+

1}

X

k A
i )c0,i( jt

i2{jt+1 ,...,jd }このあたりは色々とパラメータβ をソートしたときの索引

パラメータを大きい順に並べた図
3.0

10
✓max

✓1 + c1(Ui)✓max✓0c0(V \Ui)

ji

2.5

2.0

ji

1.5

5

jt

1.0

0.5

js

0.0

こういったグループに含まれるパラメータ✓1 = ✓0の値が近くなりやすい
0

0.5

1.0

1
s
t
d
1
s
t
d
i
K. Takeuchi, Y. Kawahara & T. iIwata, “Higher order fused regularization forsupervised learningwith grouped parameters,”
in Proc.
of ECML-PKDD’15,
pp.577-593,
2015.
(a) values of theset functions(b) parameters
sortedby the decreasing order

21

適用例： アルツハイマー病の分類• 3D脳画像（MRI）を用いて，患者の症状の分類を行う：
y

？

症状１

（例： AD／NC, MCIC／MCIS）
（難）

（易）

aij

症状２
（脳画像： x ）• 3次元格子状グラフの結合正則化項を加えたロジスティック回帰を用いる：
min

w2Rd ,c2RnX>

log(1 + exp( yi (w wi + c))) +i=1

ロジスティック回帰の損失関数

1 |w| +

2

X(i,j)2E

aij |wiwj |一般化Fused正則化項

B. Xin, Y. Kawahara, Y. Wang & W. Gao, “Efficient generalized fused Lasso with application to the diagnosis of
Alzheimer’s disease,” in Proc. of the 28th AAAI Conf. on Artificial Intelligence (AAAI’14), pp.2163-2169, 2014.

22

適用例： アルツハイマー病の分類• データ：Alzheimer’s Disease Neuroimaging Initiative (ANDI) database
1.5T MRI (62 AD, 71 NC, 54 MCIC, 87 MCIS)，および 3.0T MRI (66 AD, 104 ND, 8 MCIC,
31 MCIS) スキャンデータから構成．

• 前処理：DARTEL VBM pipeline*)を適用し，0.2より大きいGMから成る
JOURNAL OF2873個の8mm立方のボクセルを使用．
PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. , NO. , MONTH YEAR10TABLE 2
Classification accuracies(Acc.), sensitivities(Sens.) and specificities(Spec.) by the algorithms to AD.

(10-CV平均の) 分類精度（Acc），感度（Sens），特異度（Spec）の比較：
15ADNC
Acc.
SVM
MLDA
LR
L1
GSR

Sens.

30ADNC
Spec.

82.71% 80.65% 84.51%
84.21% 84.51% 83.87%
80.45% 74.19% 85.92%
81.20% 75.81% 85.92%
84.21% 80.65% 87.32%

Acc.

Sens.

15MCI
Spec.

89.41% 75.76% 98.08%
84.11% 82.69% 86.36%
87.06% 81.82% 90.38%
87.65% 78.79% 93.27%
88.82% 77.27% 96.15%

Acc.

Sens.

30MCI
Spec.

67.38% 40.74% 83.91%
63.83% 65.52% 61.11%
63.83% 50.00% 72.41%
68.79% 48.15% 81.61%
70.92% 50.00% 83.91%

Acc.

Sens.

Spec.

82.05% 25.00% 96.77%
64.10% 58.06% 87.50%
79.49% 25.00% 93.55%
87.18% 50.00% 96.77%
89.74% 62.50% 96.77%

なお最近の医療画像解析分野で報告された方法のMCI分類性能は69.4% (B.Cheng+,12)*) J. Ashburner et al., “A fast diffeomorphic image registration algorithm,” Neuroimage 38(1): 95-113, 2007.

MLDA
LR
L1
GFL

84.21% 84.51% 83.87%
80.45% 74.19% 85.92%
81.20% 75.81% 85.92%
84.21% 80.65% 87.32%

84.11% 82.69% 86.36%
87.06% 81.82% 90.38%
87.65% 78.79% 93.27%
88.82% 77.27% 96.15%

63.83% 65.52% 61.11%
63.83% 50.00% 72.41%
68.79% 48.15% 81.61%
70.92% 50.00% 83.91%

64.10% 58.06% 87.50%
79.49% 25.00% 93.55%
23
87.18% 50.00% 96.77%
89.74% 62.50% 96.77%

JOURNAL OF PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. , NO. , MONTH YEAR

適用例： アルツハイマー病の分類

absence of results for “genlasso” and “CVX” when thedata dimension is large. From Figure 5(b), we see that• 各スパース手法で（全データ10-CVにより）選択された脳部位（変数）：
our algorithm outperforms both existing algorithms andscales to large size problems.
YEAR
9

構造なし（Lasso）
5

GFRと同数の特徴数の場合構造あり（GFL）
A PPLICATION : T HE D IAGNOSIS OF AD

Top50の特徴

In the diagnosis of AD, two fundamental issues are
AD/NC (Normal healthy Controls) classification and
MCI (Mild Cognitive Impairment) conversion prediction, namely MCIC /MCIS classification. Let xi 2 Rd ,be subject’s sMRI features and yi = {0, 1} be subject’s（最良）(a) fold 1(b) fold3
fold 5fold 7 ). We propose(e) fold(f) overlap
diseasestatus (c)(AD/NCor MCIC(d)
/MCI
to9
S
use overlogistic
regression loss and formulate the diagnosis
Fig. 6. Consistency of selected voxels
different folds of the cross validation. The results of 5 different folds are shown in (a)-(e)
of AD
as 10
GSR
inare
theshown
following
waytop row illustrates results from GFL and the bottom row
espectively and the overlapped voxelsof allfolds
in (f). The

lustrates results from l1 . The percentage of the overlapped voxels are: GFL(66%) vs. l1 (22%).
N• 異なる一般化Fused項の程度と選択された脳部位：
X
T

min

w2Rd ,c2R

log (1 + exp ( yi (w xi + c))) + ⌦gsr (w).

i=1

(a)

(14)
We define W as the adjacency matrix of the graph Fig. 6. Compare GSR with
illustrated in Figure 1. Problem (14) is an exact instance voxels in a 3d brain modelof Problem (6), thus the proposed optimization in Section phied voxels, the bottom roslice. (a) GSR (best accu
4 can be directly applied.
81.20%);
l1 (similar(a) 2 = 0, 81.20%(b) 2 = 0.1 80.45% (c) 2 = 0.2, 80.45% (d) 2 = 0.4, 81.95% (e) 2 = 0.6, 84.21%(f) 2(c)= 0.8,
83.46% vox
Data. Data used in our experiments is obtained
from
the1 Alzheimer’s
Initiative
Fig. 7. Different levels of cohesion.
We fixand change 2 Disease
from left toNeuroimaging
right
an increasingorder. The illustration is the selected
λ2in 大24

劣モジュラ関数に基づく議論の利点（再掲）• 劣モジュラ関数という一般的な枠組みの中で議論が可能⇒ ­ 種々の構造を，統一的な枠組みの中で扱うことができる（最終的には，実装なども共通化できる）．
­ 組合せ最適化分野で議論されてきた，様々な理論やアルゴリ
ズムが利用できる．
• 特に，劣モジュラ関数がグラフ表現可能な場合には，学習に伴う最適化が高速に計算可能となる．

25

最適化について• 構造正則化では，微分可能な凸関数と，微分不可能な凸関数の和から成る評価関数を最小化する必要がある：

min l(w) +w2Rd

微分可能な凸関数· ⌦F,p (w)微分不可能な凸関数• 一般的なアプローチ：⇒ 近接勾配法，交互方向乗数法（ADMM）など⇒ 近接演算子（proximity operator）の反復計算に帰着：

1
prox ⌦F,p (u) = arg minw2Rd ku
2

wk22 +· ⌦F,p (w) (u 2 Rd )

26

最適化について近接演算子の計算：• ロヴァース拡張で表される場合⇒ 最小ノルム点アルゴリズムで計算可能 (Bach 10)• 一般のlpノルムの場合⇒ 分割アルゴリズム (Groenevelt 89) で計算可能(Obozinski & Bach 12)• F がグラフ表現可能な場合（一般のlpノルム）⇒ パラメトリック・フロー (Gallo+ 89) で計算可能(Mairal+11, Kawahara & Yamaguchi 15)

27

近接演算子の計算⌦F,p (w) に関する近接演算子の計算は，劣モジュラ多面体上の分離凸関数の最小化へ帰着できる (Kawahara & Yamaguchi 15)：
1
min kuw2Rd 2

wk22 +

1· ⌦F,p (w) = min max
kud
w2R t2P+ (F ) 2=mint2P+ (F )

X

i2V

min

wk22 +

wi 2R

⇢

X 1/r
ti |wi |

i2V

1
(wi
2

1/r

ui )2 + ti |wi |凸関数

劣モジュラ多面体上での分離可能な凸関数の最小化
F がグラフ表現可能な場合，パラメトリック最大流アルゴリズム（(Gallo+ 89)など）で高速に計算できる

28

グラフ表現可能な劣モジュラ関数
補助的な追加ノードを持つ s-t 有向グラフのカット関数として表現
可能な劣モジュラ関数 (Jegelka+,11）⇒ フロー演算による高速な最小化が可能
F (S) = min Ñ ({s} [ S [ Y ) + const.
Y ✓W

s-t 有向グラフ Ñ ：u1

有向グラフのカット関数

W （追加ノード）

u2
2

s
1

3

V

多くの構造正則化項を与える劣モジュラ関数
はグラフ表現可能u3t(Kawahara & Yamaguchi 15)

29参考） 近接演算子の計算時間の比較例
近接演算子の計算時間の比較例：
一般化結合正則化
410

グループ型正則化*
一般的に用いられる
410
従来アルゴリズム

TT
MNP
PARA

計 102
算
時 0
間 10

Time (log) [s]

（Log）

（Log）

Time (log) [s]

計
算 102
時
間

−2

10

0

10

PARA
SLEP
ADMM

−2

10
−4

10

2

10

3

10

4

10

10

Dimensionality d (log)

5

10

6

2

10

10

3

4

10

Dimensionality d (log)次元（Logスケール） パラメトリック最大流に 次元（Logスケール）
よる高速アルゴリズム

5

10*) PARAと，SLEP・ADMMは，全く同じ疎性を与える正則化を計算している訳ではない30

本講演のトピック
今日の講演では，MRFとカット関数（劣モジュラ関数）との関係に代表される，劣モジュラ関数を用いた構造的学習について，特に• 劣モジュラ関数と，構造的な学習モデルとの関係は？
• この関係を，どのようにして学習に用いることができるのか？
という点に注目する．そして，その具体的なアプローチとしての• 「劣モジュラ関数を用いた構造正則化学習」• 「劣モジュラ関数から得られる確率分布を用いた学習」に焦点をあてて話を進める．

31

劣モジュラ関数から得られる確率分布
劣モジュラ関数が持つ離散構造を利用できる確率分布（対数劣モ
ジュラ分布，対数優モジュラ分布）：

1
Pr(S) = exp(±F (S))
Z

正規化係数（分配関数）：Z=

劣モジュラ関数P

S✓V exp(±F (S))

• 多くの構造的な（２値ベクトル上の）確率分布を含む• 劣モジュラ最適化による効率的な計算へ帰着できる場合がある

32

対数優モジュラ分布の例
1対数優モジュラ分布： Pr(S) =exp( F (S))
Z

劣モジュラ関数例） レギュラーなMRF

F (S) =

X(i,j)2E{aij : i 2 S, j 2 V \ S} の場合
隣接行列の要素• 厳密なエネルギー最小化が可能なMRF• より一般の劣モジュラ関数を用いることで，高階なMRFなどで同様の枠組みで扱うことができる．

33

対数劣モジュラ分布の例
1対数劣モジュラ分布： Pr(S) =exp(F (S))
Z

劣モジュラ関数例） 行列式点過程

F (S) = log |KS |KS は半正定値行列 K のS に対応する部分行列の場合• 行列式点過程自体は，古くから研究される離散分布 (Macchi 75) ．
• （対数）劣モジュラ分布としての性質と，その一般化（劣モジュラ点過程）の議論はごく最近 (Iyer & Bilmes 15) ．
• 行列式点過程は，機械学習へも利用される (Klesuza & Tasker 13)．

34

対数劣モジュラ分布の例
行列式点過程は，機械学習へも利用される (Klesuza & Tasker 13)．
ランダムなサンプル：X

条件付き分布からのサンプル

Pr(Y = S|X)
/ det(LS (X))

Diverse2:
left,pointssampledrandomly;ontheright,
repulsion
betweenOnOnthetheleft,
pointsarearesampledrandomly;ontheright,
repulsion
between
pop
>
qset
(X)
ij =setiof
i (X)j (X)qj (X)o theselectionaL
diverseoflocations.
theselectionof ofa diverse
locations.

i 2 V の価値（given）

カーネル

35

対数劣モジュラ分布の例
行列式点過程は，機械学習へも利用される (Klesuza & Tasker 13)．
ランダムなサンプル：X                    
         !  "        #   
      !  $  %      !  "    &    #    '   
 % (         '     )*++$         ,      #  "     &  % $    $       

多様性のある要約-  #   '         !       (    .   
/           -    &  0   $       1++++   11 2         2      !  "   2!  $  %      *3.  
2        $ 4.$ 
2$         , 
2/,      %' 

 



Pr(Y = S|X)
/ det(LS (X))



Figure 12: A sample cluster from the DUC 2004 test set, with one of the four human36

推論と分配関数
周辺化計算：
1
Pr(S 2 [X, Y ]) =
Z

X

X✓A✓Y

Y
Z
exp( F (A)) = e F (X) XZY
ただし，[X, Y ] = {A | X ✓ A ✓ Y } ，ZX =条件付き確率：Pr(S = A | S 2 [X, Y ]) =(Xe (F (X[A) F (X))

A✓Y \X

Y
exp( F (A))/ZX
0⇒ 推論計算では，分配関数の計算が必要になる⇒ 分配関数の計算は#P困難（近似は困難）

if A 2 [X, Y ]otherwise

37

変分法によるアプローチ• モジュラ関数は，分配関数が厳密に計算可能
分配関数に関する有用な性質：
モジュラ関数 l ，u に対して，l(S)  F (S)  u(S) (8S ✓ V ) ならX
X
X
exp(+l(S)) 
exp(+F (S)) 
exp(+u(S))
・
S✓V

・

X

S✓V

S✓V

exp( l(S))

X

S✓V

S✓V

exp( F (S))

X

exp( u(S))

S✓V

上と下から，モジュラ関数の分配関数でおさえられる
l ，u としては劣勾配・優勾配が利用可能

38

凸関数の劣勾配凸関数 f の劣勾配：@f (w) = {g | f (u)f (w) + (uw)> g} (8u 2 Rd )

f

w
… …

…

@f (w)…

39

劣モジュラ関数の劣勾配
劣モジュラ関数に対しても劣勾配（モジュラ関数）が定義できる：@F (X) = {s 2 Rd | F (Y )F (X) + s(Y )s(X), 8Y ✓ V }x2| V |=2の場合のF ({2})
概念図@F ({2})@F (;)0@F ({1, 2})
x1 + x2 = F ({1, 2})@F ({1})x1
F ({1})

40

変分法によるアプローチ （再掲）• モジュラ関数は，分配関数が厳密に計算可能
分配関数に関する有用な性質：
モジュラ関数 l ，u に対して， l(S)  F (S)  u(S) (8S ✓ V )X
X
X
exp(+l(S)) 
exp(+F (S)) 
exp(+u(S))
・
S✓V

・

X

S✓V

S✓V

exp( l(S))

X

S✓V

S✓V

exp( F (S))

X

exp( u(S))

S✓V

上と下から，モジュラ関数の分配関数でおさえられる
l ，u としては優勾配・劣勾配が利用可能

41

変分法によるアプローチ（劣勾配）劣勾配 s 2 @F (X) を用いると，任意の X ✓ V に対して
(Z =)

X

S✓V

exp( F (S)) X

exp ( s(S) + s(X)S✓V

ZX (s)
ただし，次の関係が知られている (Djolonga & Krause 14)：

min Z; (s) 

s2@F (;)

min ZX (s)s2@F (X)

つまり，X = ; のときが最も良い上界を与える

F (X))

42

最小ノルム点問題との関係
優モジュラ分布の分配関数の上界

min Z; (s)等価(Djolonga & Krause 14)

s2@F (;)

基多面体上での分離強凸最小化

mins2B(F )

X

log(1 + e si )i2V

等価(Nagano & Aihara 13)

最小ノルム点アルゴリズム(Fujishige+ 06) が適用可能（現時点では，実用的に最も高速な（一般の）劣モジュラ関数の最小化
アルゴリズム）

最小ノルム点問題

mins2B(F )

X

i2V

s2i

43

平均場近似との関係
優モジュラ分布の分配関数の上界

min Z; (s)等価(Djolonga & Krause 14)✓

min D1 (P ||Q)Q

P (S)
D1 (P ||Q) = log supS✓V Q(S)mins2B(F )

s2@F (;)

Renyiダイバージェンス最小化

基多面体上での分離強凸最小化>

F̂ (q) = sup s q
s2B(F )◆

等価Xlog(1 + e si )

i2V

（強）双対
(Djolonga & Krause 15)

L-fieldsmax

q2[0,1]V

H[q]F̂ (q)

独立なベルヌーイ確率変数のエントロピー

1
1exp( q(S))
P (S) =
exp( F (S)) ， Q(S) =
Z
Zp
q

44

平均場近似との関係
優モジュラ分布の分配関数の上界

min Z; (s)X Y [i2S]
Eq [F ] =qi
(1

Renyiダイバージェンス最小化

min D1 (P ||Q)Q

P (S)
D1 (P ||Q) = log supS✓V Q(S)
KLの最小化min DKL (P ||Q)Q

基多面体上での分離強凸最小化

Xmin

s2B(F )

s2@F (;)

✓

i

S✓V

等価
(Djolonga & Krause 14)（強）双対(Djolonga & Krause 15)F̂ (q) = sup s q
s2B(F )

等価

log(1 + e si )

i2V

>

◆

qi )[i62S] F (S)L-fieldsmax

q2[0,1]V

H[q]F̂ (q)

独立なベルヌーイ確率変数のエントロピー
平均場近似

等価

max

q2[0,1]VH[q]

Eq [F ]

45

平均場近似との関係
優モジュラ分布の分配関数の上界

min Z; (s)等価(Djolonga & Krause 14)✓

min D1 (P ||Q)Q

P (S)
D1 (P ||Q) = log supS✓V Q(S)mins2B(F )

s2@F (;)

Renyiダイバージェンス最小化

基多面体上での分離強凸最小化>

F̂ (q) = sup s q
s2B(F )◆

等価Xlog(1 + e si )

i2V

（強）双対
(Djolonga & Krause 15)

L-fieldsmax

q2[0,1]V

H[q]F̂ (q)

独立なベルヌーイ確率変数のエントロピー⇒ D1 (P ||Q) に基づいた期待値伝搬法などの設計も可能となる

46

変分法によるアプローチ （再掲）• モジュラ関数は，分配関数が厳密に計算可能
分配関数に関する有用な性質：
モジュラ関数 l ，u に対して， l(S)  F (S)  u(S) (8S ✓ V )X
X
X
exp(+l(S)) 
exp(+F (S)) 
exp(+u(S))
・
S✓V

・

X

S✓V

S✓V

exp( l(S))

X

S✓V

S✓V

exp( F (S))

X

exp( u(S))

S✓V

上と下から，モジュラ関数の分配関数でおさえられる
l ，u としては優勾配・劣勾配が利用可能

47

変分法によるアプローチ （再掲）• モジュラ関数は，分配関数が厳密に計算可能
分配関数に関する有用な性質：
モジュラ関数 l ，u に対して， l(S)  F (S)  u(S) (8S ✓ V )X
X
X
exp(+l(S)) 
exp(+F (S)) 
exp(+u(S))
・
S✓V

・

X

S✓V

S✓V

exp( l(S))

X

S✓V

S✓V

exp( F (S))

X

exp( u(S))

S✓V

上と下から，モジュラ関数の分配関数でおさえられる⇒ 劣モジュラ関数の最小化を何回か計算すれば最適化できる

48

L-fieldの適用例 (Kjolonga & Krause 15)
Scalable Variational Inference in Log-supermodular Models(a) Original image.

(b) BP (1, 10).

(c) BP (0.1, 1).

(d) BP (1, 1).

(e) BP (0.1, 0.1).

(f) HOP (1, 10).

(g) Ground truth.

(h) DR (1, 10).

(i) DR (0.1, 1).

(j) DR (1, 1).

(k) DR (0.1, 0.1).

(l) HOP (1, 1).

Figure 2: Example marginals from the different approximation procedures for the original image (a) with ground truth

49

関連する論文• 対数優モジュラ分布のMAP推定とその変分法による最適化(Djolonga & Krause 14)．
• 対数優モジュラ分布，対数劣モジュラ分布上での近似推論のためのMCMC（ギブス・サンプリングなど） (Gotovos+ 15)• 上記のダイバージェンス的な解釈，期待値伝搬法や分散化などによる大規模化 (Djolonga & Krause 15)．
• 行列式点過程の対数優モジュラ分布としての定式化と推論(Iyer & Bilmes 14)．
• 上記の劣モジュラ点過程としての一般化や，分配関数の近似
率 (Iyer & Bilmes 15)．

50

まとめ
• 劣モジュラ関数と，構造的な学習モデルとの関係に着目し，­ 劣モジュラ関数の緩和を用いた構造正則化とその最適化­ 劣モジュラ関数から得られる確率分布を用いた推論と，従来からある概念との関係を中心に紹介した．
• 劣モジュラ関数を用いた構造正則化については下記も参考になる．
••

F. Bach, “Learning with submodular function: A convex optimization
perspective,” Foundations and Trends in ML, 6(2-3): 145-373, 2013.
河原吉伸，永野清仁, “劣モジュラ最適化と機械学習,” 講談社, 2015．

謝辞： 紹介した自身の研究の一部は次の方々との成果を含みます．
B. Xin氏，Y. Wang氏（北京大），山口勇太郎氏（東大），永野清仁氏（未来大），竹内孝氏, 岩田具治氏（CS研）, 永田啓介氏（アステラス）, 鷲尾隆氏（阪大）．