Deep Submodular Functions
  We start with an overview of a class of submodular functions called SCMMs
(sums of concave composed with non-negative modular functions plus a final
arbitrary modular). We then define a new class of submodular functions we call
{\em deep submodular functions} or DSFs. We show that DSFs are a flexible
parametric family of submodular functions that share many of the properties and
advantages of deep neural networks (DNNs). DSFs can be motivated by considering
a hierarchy of descriptive concepts over ground elements and where one wishes
to allow submodular interaction throughout this hierarchy. Results in this
paper show that DSFs constitute a strictly larger class of submodular functions
than SCMMs. We show that, for any integer $k>0$, there are $k$-layer DSFs that
cannot be represented by a $k'$-layer DSF for any $k'<k$. This implies that,
like DNNs, there is a utility to depth, but unlike DNNs, the family of DSFs
strictly increase with depth. Despite this, we show (using a "backpropagation"
like method) that DSFs, even with arbitrarily large $k$, do not comprise all
submodular functions. In offering the above results, we also define the notion
of an antitone superdifferential of a concave function and show how this
relates to submodular functions (in general), DSFs (in particular), negative
second-order partial derivatives, continuous submodularity, and concave
extensions. To further motivate our analysis, we provide various special case
results from matroid theory, comparing DSFs with forms of matroid rank, in
particular the laminar matroid. Lastly, we discuss strategies to learn DSFs,
and define the classes of deep supermodular functions, deep difference of
submodular functions, and deep multivariate submodular functions, and discuss
where these can be useful in applications.
