Modular Greedy¶
The modular greedy optimizer uses the modular upper-bounds for the gain of each example to do selection. Essentially, a defining characteristic of submodular functions is the diminishing returns property where the gain of an example decreases with the number of selected examples. In contrast, modular functions have constant gains for examples regardless of the number of selected examples. Thus, approximating the submodular function as a modular function can serve as an upper-bound to the gain for each example during the selection process. This approximation makes the function simple to optimize because one would simply calculate the gain that each example yields before any examples are selected, sort the examples by this gain, and select the top \(k\) examples. While this approach is fast, this approach is likely best paired with a traditional optimization algorithm after the first few examples are selected.
API Reference¶
The stochastic greedy algorithm for optimization.
This optimization approach is the stochastic greedy algorithm proposed by Mirzasoleiman et al. (https://las.inf.ethz.ch/files/mirzasoleiman15lazier.pdf). This approach is conceptually similar to the naive greedy algorithm except that it only evaluates a subset of examples at each iteration. Thus, it is easy to parallelize and amenable to acceleration using a GPU while maintaining nice theoretical guarantees.
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.
- epsilon : float, optional
- The inverse of the sampling probability of any particular point being included in the subset, such that 1 - epsilon is the probability that a point is included. Default is 0.9.
- random_state : int or RandomState or None, optional
- The random seed to use for the random selection process.
- 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.