Submodularity In Machine Learning and Artificial Intelligence
  In this manuscript, we offer a gentle review of submodularity and
supermodularity and their properties. We offer a plethora of submodular
definitions; a full description of a number of example submodular functions and
their generalizations; example discrete constraints; a discussion of basic
algorithms for maximization, minimization, and other operations; a brief
overview of continuous submodular extensions; and some historical applications.
We then turn to how submodularity is useful in machine learning and artificial
intelligence. This includes summarization, and we offer a complete account of
the differences between and commonalities amongst sketching, coresets,
extractive and abstractive summarization in NLP, data distillation and
condensation, and data subset selection and feature selection. We discuss a
variety of ways to produce a submodular function useful for machine learning,
including heuristic hand-crafting, learning or approximately learning a
submodular function or aspects thereof, and some advantages of the use of a
submodular function as a coreset producer. We discuss submodular combinatorial
information functions, and how submodularity is useful for clustering, data
partitioning, parallel machine learning, active and semi-supervised learning,
probabilistic modeling, and structured norms and loss functions.
