講演抄録/キーワード |
講演名 |
2011-11-09 15:45
離散DC計画問題のためのプリズム法とその応用 ○河原吉伸・鷲尾 隆(阪大/JST) IBISML2011-56 |
抄録 |
(和) |
本稿では,2つの劣モジュラ関数の差で表される評価関数の最小化のための厳密解法を提案する.提案するアルゴリズムは,分枝限定法の枠組みの中で,本問題の構造の特殊性を利用したものである.任意の集合関数最適化はこの問題へと定式化する事が可能であり,機械学習で扱われる多くの問題においても広く適用可能である.本稿では,特に特徴選択へ適用した場合の数値例を示す. |
(英) |
In this paper, we propose the first exact algorithm for minimizing the difference of two submodular functions (D.S.), {\em i.e.}, the discrete version of the D.C.\@ programming problem. The developed algorithm is a branch-and-bound-based algorithm which responds to the structure of this problem through the relationship between submodularity and convexity. The D.S. programming problem covers a broad range of applications in machine learning because this generalizes any set-function optimization. We empirically investigate the performance of our algorithm, and illustrate the difference between exact and approximate solutions respectively obtained by the proposed and existing algorithms in feature selection. |
キーワード |
(和) |
劣モジュラ最適化 / 機械学習 / 分枝限定法 / 特徴選択 / エネルギー最小化 / / / |
(英) |
submodular optimization / machine learning / branch and bound method / feature selection / energy minimization / / / |
文献情報 |
信学技報, vol. 111, no. 275, IBISML2011-56, pp. 93-98, 2011年11月. |
資料番号 |
IBISML2011-56 |
発行日 |
2011-11-02 (IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IBISML2011-56 |