Bidirectional Greedy¶
Most submodular optimizers assume that the function is monotone, i.e., that the gain from each successive example is positive. However, there are some cases where the key diminishing returns property holds, but the gains are not necessarily positive. In these cases, the naive greedy algorithm is not guaranteed to return a good result.
The bidirectional greedy algorithm was developed to optimize non-monotone submodular functions. While it has a guarantee that is lower than the naive greedy algorithm has for monotone functions, it generally returns better sets than the greedy algorithm.
API Reference¶
The bidirectional greedy algorithm.
This is a stochastic algorithm for the optimization of submodular functions that are not monotone, i.e., where f(A union {b}) is not necessarily greater than f(A). When these functions are not monotone, the greedy algorithm does not have the same good guarantees on convergence, whereas the bidirectional greedy algorithm does.
Generally, it is difficult to control the number of examples that are returned by the bidirectional greedy algorithm. This can be done by tuning a hyperparameter that regularizes the gains until you get the right set size. Here we take another approach and randomly select examples for consideration until we achieve the appropriate set size. This means that not all examples will be considered for addition.
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.