Bidirectional Greedy¶
The bidirectional greedy algorithm.
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. The most obvious of these is a difference in submodular functions. 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.
param self.function: | |
---|---|
A submodular function that implements the _calculate_gains and _select_next methods. This is the function that will be optimized. | |
type self.function: | |
base.BaseSelection | |
param self.verbose: | |
Whether to display a progress bar during the optimization process. | |
type self.verbose: | |
bool |
-
self.
function
¶ A submodular function that implements the _calculate_gains and _select_next methods. This is the function that will be optimized.
Type: base.BaseSelection
-
self.
verbose
¶ Whether to display a progress bar during the optimization process.
Type: bool
-
self.
gains_
¶ The gain that each example would give the last time that it was evaluated.
Type: numpy.ndarray or None