Timezone: »
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 cuttingplane method and is implemented as an iterative smallscale binaryinteger linear programming procedure. It is well known that this problem is NPhard, and the approximation factor achieved by the greedy algorithm is the theoretical limit for polynomial time. As for (nonpolynomial 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 cuttingplane mechanism. Moreover, we also provide a method that produces successively decreasing upperbounds of the optimal solution, while our algorithm provides successively increasing lowerbounds. 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 A Bilmes (University of Washington, Seattle)
Jeffrey A. Bilmes is a professor at the Department of Electrical and Computer Engineering at the University of Washington, Seattle Washington. He is also an adjunct professor in Computer Science & Engineering and the department of Linguistics. Prof. Bilmes is the founder of the MELODI (MachinE Learning for Optimization and Data Interpretation) lab here in the department. Bilmes received his Ph.D. from the Computer Science Division of the department of Electrical Engineering and Computer Science, University of California in Berkeley and a masters degree from MIT. He was also a researcher at the International Computer Science Institute, and a member of the Realization group there. Prof. Bilmes is a 2001 NSF Career award winner, a 2002 CRA Digital Government Fellow, a 2008 NAE Gilbreth Lectureship award recipient, and a 2012/2013 ISCA Distinguished Lecturer. Prof. Bilmes was, along with Andrew Ng, one of the two UAI (Conference on Uncertainty in Artificial Intelligence) program chairs (2009) and then the general chair (2010). He was also a workshop chair (2011) and the tutorials chair (2014) at NIPS/NeurIPS (Neural Information Processing Systems), and is a regular senior technical chair at NeurIPS/NIPS since then. He was an action editor for JMLR (Journal of Machine Learning Research). Prof. Bilmes's primary interests lie in statistical modeling (particularly graphical model approaches) and signal processing for pattern classification, speech recognition, language processing, bioinformatics, machine learning, submodularity in combinatorial optimization and machine learning, active and semisupervised learning, and audio/music processing. He is particularly interested in temporal graphical models (or dynamic graphical models, which includes HMMs, DBNs, and CRFs) and ways in which to design efficient algorithms for them and design their structure so that they may perform as better structured classifiers. He also has strong interests in speechbased humancomputer interfaces, the statistical properties of natural objects and natural scenes, information theory and its relation to natural computation by humans and pattern recognition by machines, and computational music processing (such as human timing subtleties). He is also quite interested in high performance computing systems, computer architecture, and software techniques to reduce power consumption. Prof. Bilmes has also pioneered (starting in 2003) the development of submodularity within machine learning, and he received a best paper award at ICML 2013, a best paper award at NIPS 2013, and a best paper award at ACMBCB in 2016, all in this area. In 2014, Prof. Bilmes also received a most influential paper in 25 years award from the International Conference on Supercomputing, given to a paper on highperformance matrix optimization. Prof. Bilmes has authored the graphical models toolkit (GMTK), a dynamic graphicalmodel based software system widely used in speech, language, bioinformatics, and humanactivity recognition.
Related Events (a corresponding poster, oral, or spotlight)

2009 Spotlight: Submodularity Cuts and Applications »
Wed Dec 9th 01:14  01:15 AM Room None
More from the Same Authors

2020 Session: Orals & Spotlights Track 32: Optimization »
Hamed Hassani · Jeffrey A Bilmes 
2020 Poster: Curriculum Learning by Dynamic Instance Hardness »
Tianyi Zhou · Shengjie Wang · Jeffrey A Bilmes 
2019 Poster: On Mixup Training: Improved Calibration and Predictive Uncertainty for Deep Neural Networks »
Sunil Thulasidasan · Gopinath Chennupati · Jeffrey A Bilmes · Tanmoy Bhattacharya · Sarah Michalak 
2018 Poster: Metric on Nonlinear Dynamical Systems with PerronFrobenius Operators »
Isao Ishikawa · Keisuke Fujii · Masahiro Ikeda · Yuka Hashimoto · Yoshinobu Kawahara 
2018 Poster: Diverse Ensemble Evolution: Curriculum DataModel Marriage »
Tianyi Zhou · Shengjie Wang · Jeffrey A Bilmes 
2018 Poster: Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions »
Wenruo Bai · William Stafford Noble · Jeffrey A Bilmes 
2017 Workshop: Discrete Structures in Machine Learning »
Yaron Singer · Jeff A Bilmes · Andreas Krause · Stefanie Jegelka · Amin Karbasi 
2017 Poster: Learning Koopman Invariant Subspaces for Dynamic Mode Decomposition »
Naoya Takeishi · Yoshinobu Kawahara · Takehisa Yairi 
2016 Poster: Deep Submodular Functions: Definitions and Learning »
Brian W Dolhansky · Jeffrey A Bilmes 
2016 Poster: Dynamic Mode Decomposition with Reproducing Kernels for Koopman Spectral Analysis »
Yoshinobu Kawahara 
2015 Poster: Submodular Hamming Metrics »
Jennifer Gillenwater · Rishabh K Iyer · Bethany Lusch · Rahul Kidambi · Jeffrey A Bilmes 
2015 Spotlight: Submodular Hamming Metrics »
Jennifer Gillenwater · Rishabh K Iyer · Bethany Lusch · Rahul Kidambi · Jeffrey A Bilmes 
2015 Poster: Mixed Robust/Average Submodular Partitioning: Fast Algorithms, Guarantees, and Applications »
Kai Wei · Rishabh K Iyer · Shengjie Wang · Wenruo Bai · Jeffrey A Bilmes 
2014 Workshop: Discrete Optimization in Machine Learning »
Jeffrey A Bilmes · Andreas Krause · Stefanie Jegelka · S Thomas McCormick · Sebastian Nowozin · Yaron Singer · Dhruv Batra · Volkan Cevher 
2014 Poster: DivideandConquer Learning by Anchoring a Conical Hull »
Tianyi Zhou · Jeffrey A Bilmes · Carlos Guestrin 
2014 Poster: Learning Mixtures of Submodular Functions for Image Collection Summarization »
Sebastian Tschiatschek · Rishabh K Iyer · Haochen Wei · Jeffrey A Bilmes 
2014 Session: Oral Session 1 »
Jeffrey A Bilmes 
2014 Session: Tutorial Session B »
Jeffrey A Bilmes 
2014 Session: Tutorial Session B »
Jeffrey A Bilmes 
2014 Session: Tutorial Session B »
Jeffrey A Bilmes 
2013 Workshop: Discrete Optimization in Machine Learning: Connecting Theory and Practice »
Stefanie Jegelka · Andreas Krause · Pradeep Ravikumar · Kazuo Murota · Jeffrey A Bilmes · Yisong Yue · Michael Jordan 
2013 Poster: Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints »
Rishabh K Iyer · Jeffrey A Bilmes 
2013 Oral: Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints »
Rishabh K Iyer · Jeffrey A Bilmes 
2013 Poster: Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions »
Rishabh K Iyer · Stefanie Jegelka · Jeffrey A Bilmes 
2013 Tutorial: Deep Mathematical Properties of Submodularity with Applications to Machine Learning »
Jeffrey A Bilmes 
2012 Workshop: Discrete Optimization in Machine Learning (DISCML): Structure and Scalability »
Stefanie Jegelka · Andreas Krause · Jeffrey A Bilmes · Pradeep Ravikumar 
2012 Poster: Weighted Likelihood Policy Search with Model Selection »
Tsuyoshi Ueno · Yoshinobu Kawahara · Kohei Hayashi · Takashi Washio 
2012 Poster: Submodular Bregman Divergences with Applications »
Rishabh K Iyer · Jeffrey A Bilmes 
2011 Workshop: Discrete Optimization in Machine Learning (DISCML): Uncertainty, Generalization and Feedback »
Andreas Krause · Pradeep Ravikumar · Stefanie S Jegelka · Jeffrey A Bilmes 
2011 Poster: Fast approximate submodular minimization »
Stefanie Jegelka · Hui Lin · Jeffrey A Bilmes 
2011 Poster: Online Submodular Set Cover, Ranking, and Repeated Active Learning »
Andrew Guillory · Jeffrey A Bilmes 
2011 Poster: Prismatic Algorithm for Discrete D.C. Programming Problem »
Yoshinobu Kawahara · Takashi Washio 
2011 Spotlight: Online Submodular Set Cover, Ranking, and Repeated Active Learning »
Andrew Guillory · Jeffrey A Bilmes 
2010 Workshop: Discrete Optimization in Machine Learning: Structures, Algorithms and Applications »
Andreas Krause · Pradeep Ravikumar · Jeffrey A Bilmes · Stefanie Jegelka 
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 Workshop: Discrete Optimization in Machine Learning: Submodularity, Polyhedra and Sparsity »
Andreas Krause · Pradeep Ravikumar · Jeffrey A Bilmes 
2009 Poster: Label Selection on Graphs »
Andrew Guillory · Jeffrey A Bilmes 
2009 Poster: Entropic Graph Regularization in NonParametric SemiSupervised Classification »
Amarnag Subramanya · Jeffrey A Bilmes 
2009 Spotlight: Entropic Graph Regularization in NonParametric SemiSupervised Classification »
Amarnag Subramanya · Jeffrey A Bilmes 
2008 Workshop: Structured Input  Structured Output »
Karsten Borgwardt · Koji Tsuda · Vishwanathan S V N · Xifeng Yan 
2007 Workshop: Machine Learning in Computational Biology (Part 2) »
Gal Chechik · Christina Leslie · Quaid Morris · William S Noble · Gunnar Rätsch · Koji Tsuda 
2007 Workshop: Machine Learning in Computational Biology (Part 1) »
Gal Chechik · Christina Leslie · Quaid Morris · William S Noble · Gunnar Rätsch · Koji Tsuda 
2006 Workshop: New Problems and Methods in Computational Biology »
Gal Chechik · Quaid Morris · Koji Tsuda · Gunnar Rätsch · Christina Leslie · William S Noble 
2006 Demonstration: The Vocal Joystick »
James Landay · Richard Wright · Kelley Kilanski · Xiao Li · Jon Malkin · Jeffrey A Bilmes 
2006 Poster: A Kernel Subspace Method by Stochastic Realization for Learning Nonlinear Dynamical Systems »
Yoshinobu Kawahara · Takehisa Yairi · Kazuo Machida 
2006 Poster: Multidynamic Bayesian Networks »
Karim Filali · Jeffrey A Bilmes