Timezone: »

Submodularity Cuts and Applications
Yoshinobu Kawahara · Kiyohito Nagano · Koji Tsuda · Jeff Bilmes

Tue Dec 08 07:00 PM -- 11:59 PM (PST) @ None #None

Several key problems in machine learning, such as feature selection and active learning, can be formulated as submodular set function maximization. We present herein a novel algorithm for maximizing a submodular set function under a cardinality constraint --- the algorithm is based on a cutting-plane method and is implemented as an iterative small-scale binary-integer linear programming procedure. It is well known that this problem is NP-hard, and the approximation factor achieved by the greedy algorithm is the theoretical limit for polynomial time. As for (non-polynomial time) exact algorithms that perform reasonably in practice, there has been very little in the literature although the problem is quite important for many applications. Our algorithm is guaranteed to find the exact solution in finite iterations, and it converges fast in practice due to the efficiency of the cutting-plane mechanism. Moreover, we also provide a method that produces successively decreasing upper-bounds of the optimal solution, while our algorithm provides successively increasing lower-bounds. Thus, the accuracy of the current solution can be estimated at any point, and the algorithm can be stopped early once a desired degree of tolerance is met. We evaluate our algorithm on sensor placement and feature selection applications showing good performance.

Author Information

Yoshinobu Kawahara (Osaka University / RIKEN)
Kiyohito Nagano (Tokyo Institute of Technology)
Koji Tsuda (University of Tokyo)
Jeff Bilmes (University of Washington, Seattle)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors