Timezone: »
In this paper, we propose the first exact algorithm for minimizing the difference of two submodular functions (D.S.), 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 the optimization of a wide class of set functions. 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 and discriminative structure learning.
Author Information
Yoshinobu Kawahara (Osaka University / RIKEN)
Takashi Washio (Osaka University)
More from the Same Authors
-
2018 Poster: Metric on Nonlinear Dynamical Systems with Perron-Frobenius Operators »
Isao Ishikawa · Keisuke Fujii · Masahiro Ikeda · Yuka Hashimoto · Yoshinobu Kawahara -
2017 Poster: Learning Koopman Invariant Subspaces for Dynamic Mode Decomposition »
Naoya Takeishi · Yoshinobu Kawahara · Takehisa Yairi -
2016 Poster: Dynamic Mode Decomposition with Reproducing Kernels for Koopman Spectral Analysis »
Yoshinobu Kawahara -
2012 Poster: Weighted Likelihood Policy Search with Model Selection »
Tsuyoshi Ueno · Yoshinobu Kawahara · Kohei Hayashi · Takashi Washio -
2010 Spotlight: Minimum Average Cost Clustering »
Kiyohito Nagano · Yoshinobu Kawahara · Satoru Iwata -
2010 Poster: Minimum Average Cost Clustering »
Kiyohito Nagano · Yoshinobu Kawahara · Satoru Iwata -
2009 Poster: Submodularity Cuts and Applications »
Yoshinobu Kawahara · Kiyohito Nagano · Koji Tsuda · Jeffrey A Bilmes -
2009 Spotlight: Submodularity Cuts and Applications »
Yoshinobu Kawahara · Kiyohito Nagano · Koji Tsuda · Jeffrey A Bilmes -
2006 Poster: A Kernel Subspace Method by Stochastic Realization for Learning Nonlinear Dynamical Systems »
Yoshinobu Kawahara · Takehisa Yairi · Kazuo Machida