Naive Greedy

The naive greedy algorithm is the simplest greedy approach for optimizing submodular functions. The approach simply iterates through each example in the ground set that has not already been selected and calculates the gain in function value that would result from adding that example to the selected set. This process is embarassingly parallel and so is extremely amenable both to parallel processing and distributed computing. Further, because it is conceptually simple, it is also simple to implement.

The naive greedy algorithm can be specified for any function by passing in optimizer=’naive’ to the relevant selector object. Here is an example of specifying the naive greedy algorithm for optimizing a feature-based function.

API Reference

The naive greedy algorithm for optimization.

This optimization approach is the naive greedy algorithm. At each iteration of selection it will simply calculate the gain one would get from adding each example, and then will select the example that has the highest gain. This algorithm is conceptually simple and easy to parallelize and put on a GPU, but can be slower than other alternatives because it involves repeatedly evaluating examples that are not likely to be selected next.

Parameters

self.function : base.SubmodularSelection
A submodular function that implements the _calculate_gains and _select_next methods. This is the function that will be optimized.
self.verbose : bool
Whether to display a progress bar during the optimization process.

Attributes

self.function : base.SubmodularSelection
A submodular function that implements the _calculate_gains and _select_next methods. This is the function that will be optimized.
self.verbose : bool
Whether to display a progress bar during the optimization process.
self.gains_ : numpy.ndarray or None
The gain that each example would give the last time that it was evaluated.