Timezone: »

 
Spotlight
Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection
Abir De · Soumen Chakrabarti

Wed Dec 07 09:00 AM -- 11:00 AM (PST) @
in Lightning Talks 3B-1 »
Submodular functions and variants, through their ability to characterize diversity and coverage, have emerged as a key tool for data selection and summarization. Many recent approaches to learn submodular functions suffer from limited expressiveness. In this work, we propose FlexSubNet, a family of flexible neural models for both monotone and non-monotone submodular functions. To fit a latent submodular function from (set, value) observations, our method applies a concave function on modular functions in a recursive manner. We do not draw the concave function from a restricted family, but rather learn from data using a highly expressive neural network that implements a differentiable quadrature procedure. Such an expressive neural model for concave functions may be of independent interest. Next, we extend this setup to provide a novel characterization of monotone $\alpha$-submodular functions, a recently introduced notion of approximate submodular functions. We then use this characterization to design a novel neural model for such functions. Finally, we consider learning submodular set functions under distant supervision in the form of (perimeter, high-value-subset) pairs. This yields a novel subset selection method based on an order-invariant, yet greedy sampler built around the above neural set functions. Our experiments on synthetic and real data show that FlexSubNet outperforms several baselines.
Keywords: data selection · neural set function

Author Information

Abir De (IIT Bombay)
Soumen Chakrabarti (Indian Institute of Technology Bombay)

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

More from the Same Authors