* 劣モジュラ (submodular) [#kf962377]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

離散最適化問題を解くとき,目的関数に劣モジュラ性があれば,多項式時間で解くことができる.

有限集合 \(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)などに利用されている.

> -- しましま

** 関連項目 [#z5945bbd]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[submodular]]
#br
-[[最適化]]
-[[クラスタリング]]
-[[特徴選択/情報ゲイン]]
#br
-[[検索:劣モジュラ submodular]]

** リンク集 [#d1901f7f]

//関連するWWW資源があればリンクしてください.

- [[Beyond Convexity: Submodularity in Machine Learning>http://www.submodularity.org]] @ ICML2008 tutorial (劣モジュラ最適化の基礎に加え,特徴選択やクラスタリングへの応用も)
- [[組み合わせ最適化>http://www.kurims.kyoto-u.ac.jp/~iwata/]] @ 岩田 覚 (劣モジュラ関数のチュートリアルを含む)
- [[Satoru Iwata "Submodular Function Minimization">http://videolectures.net/nipsworkshops2010_iwata_sfm/]] @ videolectures.net
#br
-[[ORWiki:劣モジュラ最適化]]
-[[ORWiki:劣モジュラ関数]]
-[[Wikipedia:Supermodular_function]]

*** Freeware [#d25cea13]

-[[SFO: A Toolbox for Submodular Function Optimization>http://www.submodularity.org]] (matlab)

** 関連文献 [#zfb08fd6]

//この%項目%に関連する書籍や論文を紹介してください.

- 室田 一雄 "離散凸解析の考えかた 最適化における離散と連続の数理" 共立出版 (2007)~
Amazon.co.jpへのリンク:&amazon(4320018532);
- 室田 一雄 "離散凸解析" 共立叢書 現代数学の潮流, 共立出版 (2001)~
Amazon.co.jpへのリンク:&amazon(4320016904);
- 文献1~
M.Narasimhan, N.Jojic, and J.Bilmes, "Q-Clustering", NIPS18 (2006)
- 文献2~
A.Krause and C.Guestrin "Near-optimal Nonmyopic Value of Information in Graphical models" UAI2005

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS