Submodular Set Function

From GM-RKB
(Redirected from submodular function)
Jump to navigation Jump to search

A Submodular Set Function is a set function where the difference in the value of the function that a single element makes when added to an input set decreases as the size of the input set increases.



References

2015

2014

  • http://submodularity.org/
    • QUOTE: This page collects some material and references related to submodular optimization, with applications in particular in machine learning and AI. Convex optimization has become a main workhorse for many machine learning algorithms during the past ten years. When minimizing a convex loss function for, e.g., training a Support Vector Machine, we can rest assured to efficiently find an optimal solution, even for large problems. In recent years, another fundamental problem structure, which has similar beneficial properties, has emerged as very useful in a variety of machine learning applications: Submodularity is an intuitive diminishing returns property, stating that adding an element to a smaller set helps more than adding it to a larger set. Similarly to convexity, submodularity allows one to efficiently find provably (near-)optimal solutions.

2014

2013

2010

2008

2008

1988

1978