Skip to yearly menu bar Skip to main content


Deep Submodular Functions: Definitions and Learning

Brian W Dolhansky · Jeffrey A Bilmes

Area 5+6+7+8 #101

Keywords: [ (Other) Machine Learning Topics ] [ Combinatorial Optimization ]


We propose and study a new class of submodular functions called deep submodular functions (DSFs). We define DSFs and situate them within the broader context of classes of submodular functions in relationship both to various matroid ranks and sums of concave composed with modular functions (SCMs). Notably, we find that DSFs constitute a strictly broader class than SCMs, thus motivating their use, but that they do not comprise all submodular functions. Interestingly, some DSFs can be seen as special cases of certain deep neural networks (DNNs), hence the name. Finally, we provide a method to learn DSFs in a max-margin framework, and offer preliminary results applying this both to synthetic and real-world data instances.

Live content is unavailable. Log in and register to view live content