Submodular set function: Difference between revisions

Revision as of 03:53, 31 May 2022

Revision as of 20:08, 18 June 2022

Line 1:

{{Use American English|date = January 2019}}

{{Short description|FunctionSet-to-real onmap subsets that has awith diminishing returns property}}

In mathematics, a '''submodular set function''' (also known as a '''submodular function''') is a [[set function]] whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural [[diminishing returns]] property which makes them suitable for many applications, including [[approximation algorithms]], [[game theory]] (as functions modeling user preferences) and [[electrical network]]s. Recently, submodular functions have also found immense utility in several real world problems in [[machine learning]] and [[artificial intelligence]], including [[automatic summarization]], [[multi-document summarization]], [[feature selection]], [[Active learning (machine learning)|active learning]], sensor placement, image collection summarization and many other domains.<ref name="LB" /><ref name="TIWB" /><ref name="KG1" /><ref name="KG" />