プリキュアで学ぶ劣モジュラ関数 - むしゃくしゃしてやった，今は反省している日記Machine Learning Advent Calendar 2015 1日目の企画です． 機械学習・人工知能系の国際会議（ICML, NIPS, AAAIなど）のチュートリアルや論文を眺めたことのある人なら，Submodular Function（劣モジュラ関数）という単語に見覚えがあるかもしれません．実際，ICML 2013，AAAI 2015や今年のIBISでも劣モジュラ関数のチュートリアル講演がなされています．今回は，劣モジュラ関数についてプリキュアで解説したいと思います． 劣モジュラ関数とは 劣モジュラ関数は集合関数（ある集合の部分集合を引数に取り，実数値を返す関数）の一種です．具体的には以下の定義を満たす関数です． $f: 2^E \to \mathbb{R}$ が劣モジュラ関数 $\iff$ 全ての$X \subseteq Y$ と $i \not\in Y$ に対して
