劣モジュラ (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\backslash X)\) が任意の \(X\subseteq V\) に成立する対称劣モジュラ関数であれば \(|V|\) の3乗で最小化できる.

クラスタリング(文献1),単純ベイズでの情報量ゲインを使った特徴選択(文献2)などに利用されている.

-- しましま

関連項目

リンク集

Freeware

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-07-24 (日) 23:02:24