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
An electrical network is an interconnection of electrical components (e.g., batteries, resistors, inductors, capacitors, switches, transistors) or a model of such an interconnection, consisting of electrical elements (e.g., voltage sour ...
s. Recently, submodular functions have also found immense utility in several real world problems in
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
and
artificial intelligence
Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machine
A machine is a physical system using Power (physics), power to apply Force, forces and control Motion, moveme ...
, including
automatic summarization,
multi-document summarization,
feature selection
In machine learning and statistics, feature selection, also known as variable selection, attribute selection or variable subset selection, is the process of selecting a subset of relevant features (variables, predictors) for use in model construc ...
,
active learning, sensor placement, image collection summarization and many other domains.
Definition
If
is a finite
set, a submodular function is a set function
, where
denotes the