{
  "id": "2202.00132",
  "version": "v1",
  "published": "2022-01-31T22:41:35.000Z",
  "updated": "2022-01-31T22:41:35.000Z",
  "title": "Submodularity In Machine Learning and Artificial Intelligence",
  "authors": [
    "Jeff Bilmes"
  ],
  "categories": [
    "cs.LG",
    "cs.AI"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-01-31T22:41:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "machine learning",
      "artificial intelligence",
      "submodularity",
      "submodular combinatorial information functions",
      "example submodular functions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}