Class SubmodularFunction

Inheritance Relationships

Derived Type

Class Documentation

class exemcl::SubmodularFunction

Submodular functions represent a special kind of set function, which map subsets (usually denoted as \(S\)) of some ground set (denoted by \(V\)) to a positive real value (sometimes called the “utility”), whilst maintaining a property of diminishing returns.

Formally, we have the ground set \(V \subset \mathbb{R} \) and a function \(f: \mathcal{P}(V) \rightarrow \mathbb{R}^+\). The function \(f\) is now submodular, iff \(\Delta_f(e \mid A) \geq \Delta_f(e \mid B)\) for arbitrary \(A \subseteq B \subseteq V\) and \(e \in V \setminus B\). The vector \(e\) is sometimes called the “marginal element”. \(\Delta_f\) represents the discrete derivative \(\Delta_f(e | S) := f(S \cup \left\lbrace e \right\rbrace - f(S))\).

This (abstract) class provides an interface to implementing submodular functions of any kind.

Subclassed by exemcl::cpu::ExemplarClusteringSubmodularFunction< HostDataType >

Public Functions

SubmodularFunction(int workerCount = -1)

Provides a base constructor, which updates the worker count of the submodular function.

Parameters

  • workerCount: The number of workers to employ (defaults to -1, i.e. all available cores).

double operator()(const MatrixX<double> &S) const = 0

Calculates the submodular function value for a set.

Return

The submodular function value \(f(S)\).

Parameters

  • S: Set of vectors, to calculate the submodular function for.

double operator()(const MatrixX<double> &S) = 0

Calculates the submodular function value for a set.

Return

The submodular function value \(f(S)\).

Parameters

  • S: Set of vectors, to calculate the submodular function for.

double operator()(const MatrixX<double> &S, VectorXRef<double> elem) const

Calculates the marginal gain of the submodular function, w.r.t to \(S\) and a marginal element \(e\).

Return

The marginal gain of the \(f(S) - f(S \cup \left\{elem\right\})\)

Parameters

  • S: Set of vectors, to calculate the submodular function for.

  • elem: A marginal element.

double operator()(const MatrixX<double> &S, VectorXRef<double> elem)

Calculates the marginal gain of the submodular function, w.r.t to \(S\) and a marginal element \(e\).

Return

The marginal gain of the \(f(S) - f(S \cup \left\{elem\right\})\)

Parameters

  • S: Set of vectors, to calculate the submodular function for.

  • elem: A marginal element.

std::vector<double> operator()(const std::vector<MatrixX<double>> &S_multi) const

Calculates the submodular function for more than one set.

Return

A set of utility values \(\left\{f(S_1), ..., f(S_n)\right\}\).

Parameters

  • S_multi: A set of sets \( S = \left\{S_1, ..., S_n\right\}\), which should be evaluated using the submodular function.

std::vector<double> operator()(const std::vector<MatrixX<double>> &S_multi)

Calculates the submodular function for more than one set.

Return

A set of utility values \(\left\{f(S_1), ..., f(S_n)\right\}\).

Parameters

  • S_multi: A set of sets \( S = \left\{S_1, ..., S_n\right\}\), which should be evaluated using the submodular function.

std::vector<double> operator()(const std::vector<MatrixX<double>> &S_multi, VectorXRef<double> elem) const

Calculates the marginal gain for a multi set and a marginal element.

Return

A set of marginal gain values \(\Delta_f(e | S_1), ..., \Delta_f(e | S_n) \).

Parameters

  • S_multi: A set of sets \( S = \left\{S_1, ..., S_n\right\} \), which should be evaluated using the submodular function.

  • elem: A marginal element \( e \).

std::vector<double> operator()(const std::vector<MatrixX<double>> &S_multi, VectorXRef<double> elem)

Calculates the marginal gain for a multi set and a marginal element.

Return

A set of marginal gain values \(\Delta_f(e | S_1), ..., \Delta_f(e | S_n) \).

Parameters

  • S_multi: A set of sets \( S = \left\{S_1, ..., S_n\right\} \), which should be evaluated using the submodular function.

  • elem: A marginal element \( e \).

std::vector<double> operator()(const MatrixX<double> &S, std::vector<VectorXRef<double>> elems) const

Calculates the marginal gain for a single set \(S\) and a set of marginal vectors.

Return

A set of marginal gain values \(\Delta_f(e_1 | S), ..., \Delta_f(e_n | S) \).

Parameters

  • S: Set of vectors, which should be used to calculate the marginal value in conjunction with elems.

  • elems: A set of marginal vectors \( \left\{e_1, ..., e_n \right\}\).

std::vector<double> operator()(const MatrixX<double> &S, std::vector<VectorXRef<double>> elems)

Calculates the marginal gain for a single set \(S\) and a set of marginal vectors.

Return

A set of marginal gain values \(\Delta_f(e_1 | S), ..., \Delta_f(e_n | S) \).

Parameters

  • S: Set of vectors, which should be used to calculate the marginal value in conjunction with elems.

  • elems: A set of marginal vectors \( \left\{e_1, ..., e_n \right\}\).

unsigned int getWorkerCount() const

Returns the worker count, which is currently assigned to this submodular function.

Return

Worker count.

void setWorkerCount(int workerCount)

Updates the worker count for the submodular function. If the supplied value is below one, the function will try to update the worker count to the number of cores available to the program.

Parameters

  • workerCount: New worker count.

void setMemoryLimit(long memoryLimit)

Limits the usable memory by this class. Must be overridden by the implementing class and yields an exception otherwise.

Parameters

  • memoryLimit: Memory limit (in byte).

~SubmodularFunction() = default

Destructor.

Protected Attributes

unsigned int _workerCount = 1