劣モジュラ - 機械学習の「朱鷺の杜Wiki」劣モジュラ (submodular)† 離散最適化問題を解くとき，目的関数に劣モジュラ性があれば，多項式時間で解くことができる． 有限集合 \(V\) に対して，その任意の部分集合 \(X\subseteq V\) から実数への関数を \(f(X)\) とする．この関数が劣モジュラ関数であるとは，任意の部分集合 \(X,Y\subseteq V\) に対して次の性質があること： \[f(X)+f(Y)\ge f(X\cap Y)+f(X\cup Y)\] これは次の性質と等価 \[X\subseteq Y\subseteq V,\, x\in V\backslash Y,\;f(X\cup\{x\})-f(X)\ge f(Y\cup\{x\})-f(Y)\] 劣モジュラ関数を最小化する部分集合は，\(|V|\) の5〜6乗の多項式時間で解くことができる． さらに，\(f(X)=f(V\ba
