Unconstrained Submodular Maximization

A collection of optimization algorithms for Unconstrained Submodular Maximization (USM) of non-monotone non-negative set functions.

Maximizing a non-monotone submodular function is NP-hard. This means there is no guarantee an optimal solution can be found within a polynomial number of function evaluations. As maximization is NP-hard, finding a 'maximum' is often done using approximation algorithms resulting in an approximate solution. This repository contains Python implementations of a couple of optimization algorithms tackling USM.

Basic example

As a minimal example, we can use the simple submodular function used in Andreas Krause's great tutorial slides at www.submodularity.org. This function defines the following mapping:

| input_set | output | |-----------|--------| | {} | 0 | | {1} | -1 | | {2} | 2 | | {1, 2} | 0 |

Here, the ground set of interest is defined as: { 1, 2 }. Thus, the goal is to find the subset of this ground set that maximizes the submodular function. In this case, the optimal solution is {2} Here, we can do this as follows:

from typing import Set, TypeVar

from submodmax.abstract_optimizer import AbstractSubmodularFunction, AbstractOptimizer
from submodmax.randomized_double_greedy_search import RandomizedDoubleGreedySearch

E = TypeVar('E')

# Define the submodular function to maximize
class ExampleFunction(AbstractSubmodularFunction):
    def evaluate(self, input_set: Set[int]) -> float:
        if input_set == set():
            return 0
        elif input_set == {1}:
            return -1
        elif input_set == {2}:
            return 2
        elif input_set == {1, 2}:
            return 0
        else:
            raise Exception(f"The input set was not expected: {input_set}")

# Intialize the submodular function
submodular_objective_function = ExampleFunction()

# -------------
# Define the ground set
ground_set: Set[int] = {1, 2}

# Choose an optimization algorithm
#   and initialize it with:
#   * the submodular function 
#   * the ground set
optimizer: AbstractOptimizer = RandomizedDoubleGreedySearch(
    objective_function=submodular_objective_function,
    ground_set=ground_set,
    debug=False
)

# Run the optimization algorithm to get a solution
local_optimum: Set[int] = optimizer.optimize()
true_optimum: Set[int] = {2}
print(local_optimum)
if true_optimum == local_optimum:
    print(f"Found correct local optimum: {local_optimum}")
else:
    print(f"Found {local_optimum}, but should be {true_optimum}")

Installation

You can install this repositiory as a python package in a Python 3.6+ environment as follows:

git clone https://github.com/joschout/SubmodularMaximization.git
cd SubmodularMaximization/
python setup.py install develop [--user]

To use it in your project, you can use:

from submodmax import <what-you-need>

Included submodular maximization algorithms

First, this repository includes the three algorithms proposed by Feige, U., Mirrokni, V. S., and Vondrák, J. in their paper:

Feige, U., Mirrokni, V. S., & Vondrák, J. (2011). Maximizing Non-monotone Submodular Functions. SIAM J. Comput., 40(4), 1133–1153. https://doi.org/10.1137/090779346

These algorithms are called:

Random Set
Deterministic Local Search
Smooth Local Search

Next, this repository contains two of the algorithms propsed by Buchbinder, N., Feldman, M., Naor, J. S., and Schwartz, R. in their paper:

Buchbinder, N., Feldman, M., Naor, J. S., & Schwartz, R. (2015). A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM Journal on Computing, 44(5), 1384–1402. https://doi.org/10.1137/130929205

For a lack of a better name, this repository calls these algorithms:

Deterministic Double Greedy Search (Deterministic USM in the original paper)
Randomized Double Greedy Search (Randomized USM in the original paper)

Usage

The following describes how to use this repository in your own implementation.

The submodular function to be maximized

A submodular function can be represented as an object of a class implementing one of two interfaces, depending on whether the maximization algorithm can use marginal increments to speed things up:

General submodular functions should implement the AbstractSubmodularFunction interface.
Submodular functions for which the maximization algorithm only computes marginal increments, for which we can use a computational trick to speed things up. I.e., if the submodular objective function is sequentially evaluated, we might only need to take into account the difference between the sets between two consecutive evaluations, and update the previous function value using this information. In this package, we refer to this as function value reuse. These submodular functions should implement the AbstractSubmodularFunctionValueReuse interface.

General submodular functions - evaluation without function value reuse

Without function value reuse, submodular functions can be implemented similar to the basic example, which can also be found in ./examples/example_Andreas_Krause.py

More specifically, the submodular function to be maximized should be contained in an object of a class inheriting from AbstractSubmodularFunction. This class looks as follows:

class AbstractSubmodularFunction:
    def evaluate(self, input_set: Set[E]) -> float:
        raise NotImplementedError('Abstract Method')

That is, AbstractSubmodularFunction requires its subclasses to implement an evaluate() method, taking as input a Set[E] and resulting in a float. This method should evaluate the set function on the given set, returning the value of the function. This class corresponds to the 'value oracle', which should be able to return the value of the function to be maximized for every possible subset of the ground set.

Typically, your own class inheriting AbstractSubmodularFunction can contain instance variables for parameters required by the objective function.

Speeding up submodular functions evaluation with function value reuse

Submodular optimization often corresponds to repeated evaluation of the function to be optimized, using different sets as input. Evaluating the function can be costly: the computational effort is often a function of the elements in the set. However, some optimization algorithms (such as Buchbinder's Greedy Search) sequentially evaluate the submodular function on input sets where two consecutive input sets do not differ much. Often, only one element is added or removed at a time. For such functions, it is sometimes possible to reuse the function value obtained from the previous evaluation, and update it with the difference corresponding to the changed set. This difference is called the marginal increment. This trick is also used in Andreas Krause's SFO toolbox, as described in:

Krause, Andreas. "SFO: A toolbox for submodular function optimization." The Journal of Machine Learning Research 11 (2010): 1141-1144.

Using marginal increments to update the previous function value can drastically reduce the work, compared to re-evaluating the function on the whole input set.

The following example plot shows the evaluation time for the Interpretable Decision Set objective function, for gradually larger input sets. Here, the evaluation time in function of the input set size improves dramatically when the function value of the previous evaluation is reused and updated with the marginal increment, compared to the evaluation time of recomputing the function on the whole input set.

Comparison of the run time for evaluating the IDS objective function with and without function value reuse

Defining your own submodular function

To use this package in your own code, you can have a look at the basic example in ./examples/value_reuse/example_Andreas_Krause.py. More specifically, the submodular function to be maximized should be contained in an object of a class inheriting from AbstractSubmodularFunctionValueReuse. This c

SubmodularMaximization

Install / Use

README