Stochastic Greedy¶
The stochastic greedy algorithm is a simple approach that, for each iteration, randomly selects a subset of data and then finds the best next example within that subset. The distinction between this approach and the sample greedy algorithm is that this subset changes at each iteration, meaning that the algorithm does cover the entire data set. In contrast, the sample greedy algorithm is equivalent to manually subsampling the data before running a selector on it. The size of this subset is proportional to the number of examples that are chosen and determined in a manner that results in the same amount of computation being done no matter how many elements are selected. A key idea from this approach is that, while the exact ranking of the elements may differ from the naive/lazy greedy approaches, the set of selected elements is likely to be similar despite the limited amount of computation.
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.