Deep Submodular Functions: Learning and Applications in Data Science

In this talk, we'll first review how submodular functions are useful in data science for various data manipulation problems (e.g., summarization and partitioning), and how certain submodular functions (e.g., sums of concave composed with modular functions (SCMs)) are particularly useful due to their practical viability and scalability. We then introduce a new class of submodular functions called deep submodular functions (DSFs). We motivate DSFs by addressing a limitation of SCMs. We then situate DSFs within the broader context of classes of submodular functions in relationship both to various matroid ranks and SCMs.  Notably, we find that DSFs constitute a strictly broader class than SCMs (thus justifying their mathematical study), although they retain all of the attractive properties of SCMs. Interestingly, some DSFs can be seen as special cases of deep neural networks (DNNs), hence the name, but DSFs still do not comprise all submodular functions.  Finally, we show how to learn DSFs in a max-margin framework, and offer some preliminary but encouraging empirical learning results on both synthetic and real-world data instances.

Joint work with Brian Dolhansky.