劣モジュラ関数とは

劣モジュラ関数は集合関数（ある集合の部分集合を引数に取り，実数値を返す関数）の一種です．具体的には以下の定義を満たす関数です．

$f: 2^E \to \mathbb{R}$ が劣モジュラ関数
$\iff$ 全ての$X \subseteq Y$ と $i \not\in Y$ に対して
\[
f(X \cup \{ i \}) - f(X) \geq f(Y \cup \{ i \}) - f(Y)
\]

注: $2^E$ は $E$ の全ての部分集合の集合を表す記号です．

はい，全然分からん！そこでプリキュアの出番です．

$E$ を全てのプリキュアの集合としましょう．つまり
$E =$ {キュアブラック, キュアホワイト, ... , キュアスカーレット }
です．

（↓$E$のイメージ図）

劇場版シリーズ最新作『映画プリキュアオールスターズ　みんなで歌う♪奇跡の魔法！』2016年3月19日（土）全国劇場にて公開決定！「プリキュア」シリーズ劇場作品20作目！#precure https://t.co/WAhtg1Thas pic.twitter.com/Bu6kIsMtve

— 東映アニメーション (@toeianime_info) 2015, 11月 28

プリキュアを何人か集めてきた集合を $X$ としたとき，その中に含まれるプリキュアの色の種類を $f(X)$ として定義します．

たとえば
$X =$ {キュアマリン, キュアピーチ, キュアピース, キュアフローラ}
にすると，$X$には全部で3色のプリキュアがいるので $f(X) = 3$ です．

$X$ を含む集合として
$Y =$ {キュアマリン, キュアピーチ, キュアピース, キュアフローラ, キュアミント, キュアエース}
を取ると，今度は $f(X) = 5$ です．

ここで，$X$ と $Y$ にキュアマーチを足して，$f$ の値がどう変化するかをみてみます（つまり $i =$ キュアマーチ）．
$X \cup \{ i \} =$ {キュアマリン, キュアピーチ, キュアピース, キュアフローラ, キュアマーチ}
ですから，$f$ の値は1増えます．
一方で，
$Y \cup \{ i \} =$ {キュアマリン, キュアピーチ, キュアピース, キュアフローラ, キュアミント, キュアエース, キュアマーチ}
ですが，$Y$ には既に緑のキュアミントがいるので，$f$ の値は変化しません．

この例で分かるとおり，$X \subseteq Y$ を満たす2つの集合 $X$, $Y$ に新しい要素 $i$ を追加したとき，色の増え方は必ず ($X$ に対する増え方) $\geq$ ($Y$ に対する増え方) になります．これが上の定義が言っていることです．
つまり，劣モジュラ関数は，手持ちの集合が大きくなればなるほど増え方が鈍っていく関数*1です．

ちなみに，この関数は $X \subseteq Y$ ならば $f(X) \leq f(Y)$ という性質（単調性）も持っていますが，劣モジュラ関数が必ず単調であるとは限りません．ただし，以下で見るように，単調な劣モジュラ関数でも機械学習にたくさんの応用があります．

応用例: センサー配置問題

有名な応用としてセンサー配置問題があります．ここではセンサーの代わりにプリキュアを配置することにしましょう．賢いゆいちゃんは，街にゼツボーグが出てきたときのために，プリキュアを事前に配置して迎え撃つことにしました．過去の出現パターンから，ゼツボーグが出てくる可能性のある場所（候補点）はある程度絞り込めたとします．

プリキュアは人目についてはいけないので，配置できる場所は限られますが，ある程度の範囲ならプリキュア1人でカバーできます．さて，4人のプリキュアをどこに配置したら最も多くの候補点をカバーできるでしょうか？

たとえばこんな配置が考えられます．この配置だと9箇所カバーできています．

この例では $E$ をプリキュアを配置できる座標の集合, $f(X)$ を配置 $X$ によってカバーされる候補点の数とすると，実は $f$ は単調な劣モジュラ関数になります．そして，この問題は

$|X| \leq 4$ という制約のもとで $f(X)$ を最大化せよ

という問題になります．

このように単調な劣モジュラ関数 $f$ に対して

$|X| \leq k$ という制約のもとで $f(X)$ を最大化せよ

という問題は，単調劣モジュラ関数最大化と呼ばれ，貪欲法とよばれる非常に実用的なアルゴリズムが知られています．

貪欲法は，$X = \emptyset$ からスタートして，$f(X \cup \{s\}) - f(X)$ が最大となる $s$ を選んで $X$ に追加することを $k$ 回繰り返すだけの非常にシンプルなアルゴリズムです．
しかしながら性能は驚くほど高く，理論的には最悪でも最適値の 1-1/e ≒ 63% の解を出力することが保証されており，経験的には最適値の90%〜ほぼ100%に近い解を出力します．
貪欲法のおかげで，単調劣モジュラ関数最大化は「実用上解けるNP困難問題」として

• 線形回帰モデルにおける変数選択
• 文書要約
• 感染型マーケティング

などに幅広く応用されています．

書籍・リンク

実は，劣モジュラ関数の研究者の中には日本人研究者が数多くいます(私もその端くれ)．残念ながら，Web上の日本語情報は多くありませんが，いくつか紹介しておきます．

• NIIの吉田さんによる「劣モジュラ関数最大化」に関するPFIセミナーの動画．

Live stream by Ustream

• 劣モジュラ関数研究者では知らない人はいない，藤重先生の動画．

機械学習プロフェッショナルシリーズにも，もうすぐ劣モジュラ最適化の本が出ます．

劣モジュラ最適化と機械学習 (機械学習プロフェッショナルシリーズ)

• 作者: 河原吉伸,永野清仁
• 出版社/メーカー: 講談社
• 発売日: 2015/12/09
• メディア: 単行本（ソフトカバー）
• この商品を含むブログを見る

英語の情報は http://submodularity.org がよくまとまっています．過去のICMLなどのチュートリアル動画へのリンクがあります．