GSoC 2013 Racing
The technique commonly referred to as "racing" selection [1-3], is applicable in general to rank stochastic variables. It can be broadly described as a procedure that ranks by locating the 'bad ones' as soon as statistically sufficient evidence is gathered. Connected with sound statistical results, the Hoeffding races [1,2] or the Bernstein races [3], for example, are able to significantly reduce the number of evaluations needed to obtain a given confidence level in the ranking.
Two application targets are envisioned for racing methods in PaGMO/PyGMO:
- Racing the algorithms running in different islands [4,5,6] ** An optimizer's performance varies across problems. Having no prior knowledge of which optimizer will be better suited to a given problem, the user is forced to manually try out different optimizers, and different parameter settings within an optimizer. PaGMO greatly facilitates this task, by enabling the user to easily deploy a wide variety of optimizers over the same problem, but the task of further selection and tuning is still left to the user. By implementing racing methods, we aim to automate this process. The user should be able to deploy PaGMO's assorted optimizers on a given problem, and PaGMO should monitor their progress, dynamically allocating effort to the most successful ones, and stopping as soon as possible the execution of those that have statistically been found to be inferior on the present problem. Taking this work one step further, racing can be used not only to select the best optimizer for a given problem, but also for tuning it (racing between different parametrizations of an optimizer, leading to the identification of the highest performing configuration);
- Racing individuals in a population ** individuals in a stochastic optimization problem could be ranked by a racing method. The common practice of evaluating all individuals in a population over a whole training set of instances (such as over a set of possible input values for the Neural Network under optimization), to average out their performance, is needlessly expensive. The optimizer usually demands solely the capacity to distinguish good from bad solutions, and cares nothing for having the best possible estimates of their absolute performance. A racing method is able to allocate per individual the minimal number of evaluations that suffices to distinguish its performance level from that of other individuals it is racing with. A thorough implementation of population racing will accommodate itself to the optimizer's population dynamics: a tournament selection in a genetic algorithm should invoke a race only between the individuals in the tournament (and should those individuals later enter new tournaments/races, their previous evaluations should be remembered, and provide a basis for the new race), in Particle Swarm Optimization, using a ring topology, a particle should invoke a race among those particles that surround it in the ring, so as to determine which one is the best, and should therefore influence its own trajectory. In both these examples, racing is made to deliver greater performance still, by breaking down a population's evaluation in sets of smaller, overlapping, races.
The goal of this project is therefore to provide PaGMO users with the possibility to easily race individuals and algorithms, and with it deliver gains in computation time, and in abstraction of the specific internal details of the used optimizers.
Implementation Details:
- The student will implement a C++ class called pagmo::algorithm::race able to rank different algorithms.
- The student will implement, in the class pagmo::population, a method called race() which will work only if the pagmo::problem is stochastic (i.e. it inherits from pagmo::problem::base_stochastic). The method evaluates individuals of the population over different scenarios (input data instances, random number generator seeds that initialize a simulator on which the evaluation will take place, ...). As statistical evidence is collected, different individuals are gradually dropped from the race, until a satisfactory ranking can be delivered back to the optimizer. At the end, the raced individuals are left with a fitness value which is the average over the multiple runs made.
- The student will implement an algorithm that makes use of the method pop.race to effectively solve a stochastic optimization problem.
All the work will then need to be exposed to Python accordingly.
Below is an example of how a basic API for population racing might look like:
pagmo::problem::rosenbrock prob(10); pagmo::population pop(prob,20); pop.race(); size_t idx0 = pop.get_best_idx();
References
[1] Maron, O., & Moore, A. W. (1994). [http://scholar.google.com/scholar?q=Hoeffding+races%3A+Accelerating+model+selection+search+for+classification+and+function+approximation Hoeffding Races: Accelerating Model Selection Search for Classification and Function Approximation]. In G. T. & J. A. Jack D. Cowan (Ed.), Advances in Neural Information Processing Systems (Vol. 6, pp. 59–66). San Francisco, CA: Morgan Kaufmann.
[2] Maron, O., & Moore, A. W. (1997). [http://scholar.google.com/scholar?q=The+racing+algorithm%3A+model+selection+for+lazy+learners The Racing Algorithm: Model Selection for Lazy Learners]. Artificial Intelligence Review, 11(1-5), 193–225. doi:[http://dx.doi.org/10.1023/A:1006556606079 10.1023/A:1006556606079]
[3] Mnih, V., Szepesvári, C., & Audibert, J.-Y. (2008). [http://scholar.google.com/scholar?q=Empirical+Bernstein+Stopping Empirical Bernstein stopping]. Proceedings of the 25th international conference on Machine learning - ICML ’08 (pp. 672–679). New York, New York, USA: ACM Press. doi:[http://dx.doi.org/10.1145/1390156.1390241 10.1145/1390156.1390241]
[4] Birattari, M., Stützle, T., Paquete, L., & Varrentrapp, K. (2002). [http://scholar.google.com/scholar?q=A+Racing+Algorithm+for+Configuring+Metaheuristics A Racing Algorithm for Configuring Metaheuristics]. GECCO ’02 Proceedings of the Genetic and Evolutionary Computation Conference (pp. 11–18). Morgan Kaufmann Publishers Inc.
[5] Yuan, B., & Gallagher, M. (2004). [http://scholar.google.com/scholar?q=Statistical+Racing+Techniques+for+Improved+Empirical+Evaluation+of+Evolutionary+Algorithms Statistical Racing Techniques for Improved Empirical Evaluation of Evolutionary Algorithms]. In X. Yao, E. K. Burke, J. A. Lozano, J. Smith, J. J. Merelo-Guervós, J. A. Bullinaria, J. E. Rowe, et al. (Eds.), Parallel Problem Solving from Nature - PPSN VIII (pp. 172–181). Springer. doi:[http://dx.doi.org/10.1007/978-3-540-30217-9_18 10.1007/978-3-540-30217-9_18]
[6] Yuan, B., & Gallagher, M. (2007). [http://scholar.google.com/scholar?q=Combining+Meta-EAs+and+racing+for+difficult+EA+parameter+tuning+tasks Combining Meta-EAs and Racing for Difficult EA Parameter Tuning Tasks]. In F. G. Lobo, C. F. Lima, & Z. Michalewicz (Eds.), Parameter Setting in Evolutionary Algorithms (pp. 121–142). Springer. doi:[http://dx.doi.org/10.1007/978-3-540-69432-8_6 10.1007/978-3-540-69432-8_6]
[7] Heidrich-Meisner, Verena, & Christian Igel (2009). [http://scholar.google.com.sg/scholar?q=Hoeffding+and+Bernstein+races+for+selecting+policies+in+evolutionary+direct+policy+search Hoeffding and Bernstein Races for Selecting Policies in Evolutionary Direct Policy Search]. Proceedings of the 26th Annual International Conference on Machine Learning, pp. 401-408. ACM Press. doi:[http://dx.doi.org/10.1145/1553374.1553426 10.1145/1553374.1553426]
Skills Required: Knowledge of boost::math and boost::python libraries.
Skills that help: a competitive spirit
Mentors: Mentors#Luis, Mentors#Dario
Student: Yung Siang Liau
Preparation work
*[before - 16/6] ** Noisy meta-problem ** Literature review ** Discussion on implementation of pop::race() and algorithm::race ** Start with preliminary implementation of pop::race()
** Racing individuals **
*[17/6 - 23/6] ** Implement pop::race() based on F-Race
*[24/6 - 30/6] ** Continue with pop::race()
*[1/7 - 7/7] ** Incorporate racing into selected algorithms that handle stochastic optimization problems, e.g. pso_generational, sga. ** Identify cases where pop::race() turns out to be significantly useful ** Write a tutorial for pop::race()
** Racing algorithms **
*[8/7 - 14/7] ** Implement algorithm::race class based on Hoeffding and Bernstein Race
*[15/7 - 21/7] ** Continue with algorithm::race
*[22/7 - 28/7] ** Include F-Race capability to algorithm::race
*[29/7 - 4/8] ** Reproduce similar results in the literature using algorithm::race for validation ** Write a tutorial for algorithm::race
Additional functionalities
(This part may be further modified depending on the outcomes of the implementation results up to this point, and discussion with mentors about what is possible and more valuable.)
*[5/8 - 11/8] ** Build upon algorithm::race to implement an automatic parameter configuration system
*[12/8 - 18/8] ** Continue with implementation from last week
*[19/8 - 25/8] ** Continue with implementation from last week
*[26/8 - 1/9] ** Produce a working example of the parameter tuning system
Testing and finalization
*[2/9 - 8/9] ** Write a tutorial for the parameter tuning system ** Write more tests and documentation
*[9/9 - 15/9] ** Write more tests and documentation ** Work on the technical paper
*[16/9 - end] ** Same as last week ** Clean things up
F-Race [1] is based on the Friedman Test which a method based on ranks. Hence, the involved statistics will be computed from some ranking information instead of the raw data. In [1], F-Race is used to race different algorithm configurations so that the best configuration can be identified efficiently by allocating computation resources cleverly -- a candidate can be eliminated from the race once it is found to be worse than others with some statistical significance.
In the following the Friedman test will be briefly described, where the notations and formulations are due to [2]. Assume that the data X is made of b blocks of k-variate random variables (X_{i1},X_{i2},\dots,X_{ik}), i={1,\dots,b}, and that these k-variate random variables are mutually independent. In each block i, it is assumed that different observations X_{ij} can be ranked against each other, whose rank will be denoted as R(X_{ij}). In case of ties, an averaged rank will be assigned. For each "treatment" (i.e. an individual or an algorithm in the context of this project), the sum of ranks can be computed as
R_j = \displaystyle\sum_{i=1}^{b} R(X_{ij})
The statistic to be computed is
T_{1} = \frac{(k-1)\displaystyle\sum_{j=1}^{k}\left( R_j - \frac{b(k+1)}{2} \right)^2}{A_1 - C_1}
where
A_1 = \displaystyle\sum_{i=1}^{b}\displaystyle\sum_{j=1}^{k}[R(X_{ij})]^2 and
C_1 = \frac{bk(k+1)^2}{4}
The null hypothesis H_0 states that all the rankings in a block are equally likely. When the null hypothesis is true, the distribution of T_1 can be approximated via a \chi^2 distribution with k-1 degrees of freedom. Thus, H_0 can be rejected (i.e. some "treatments" are genuinely better / worse) with a significant level of \alpha if T_1 exceeds the 1-\alpha quantile of the \chi^2 distribution. Once this null hypothesis is rejected, pair-wise comparison between different treatments i and j can be made to check whether they are statistically significantly different via the following equation
|R_j - R_i| > t_{1-\frac{\alpha}{2}} \left[ \frac{(A_1 - C_1)2b}{(b-1)(k-1)} \left( 1 - \frac{T_1}{b(k-1)}\right) \right]^{\frac{1}{2}}
which holds if i and j are indeed different. Here, t_{1-\frac{\alpha}{2}} is the 1-\frac{\alpha}{2} quantile of a t distribution with (b-1)(k-1) degrees of freedom.
The F-Race algorithm incorporates the above statistical testing procedures in an iterative manner. At each racing iteration, all the active candidates will be re-evaluated with different conditions (e.g. different RNG seeds) and the ranking information will be updated so that a Friedman test can be performed. A candidate will be dropped from the race once it is found to be statistically significantly worse than the best candidate.
References
[1] Birattari, M., Stützle, T., Paquete, L., & Varrentrapp, K. (2002). A Racing Algorithm for Configuring Metaheuristics. GECCO ’02 Proceedings of the Genetic and Evolutionary Computation Conference (pp. 11–18). Morgan Kaufmann Publishers Inc.
[2] Conover, W. J. (1998). Practical nonparametric statistics.
We will first attempt to implement population::race() method based on F-Race. The flexibility of this ranking based method makes racing of individual possible even in the case of multi-objective problems, as long as some ranks between the individuals can be established. Here, we will use the existing get_best_idx() routine from which the ranking information can be extracted. A pseudo-algorithm is shown as follows:
Check that the problem is indeed stochastic, otherwise call and return problem::get_best_idx(N)
LIST = all individuals in the pop
DROPPED_LIST = []
WHILE len(LIST) > N AND max_iter NOT reached:
Change the random seed (to s_i)
Evaluate individuals in LIST w.r.t s_i
Call get_best_idx(N) to get the ranking of each individual in the race
Transform the ranking to the the ranking in Friedman's sense (i.e. check for ties)
Update the container storing the ranking data
Update BestInd based on rank sum
IF NOT reached min_trials:
continue
# Perform Birattari race (two-stage)
Compute statistic T based on ranking data
IF NOT reject_null(T, chi_squared_distribution, delta):
continue
FOR EACH Ind: (**)
t = Pairwise-test statistic between Ind and BestInd
if reject_null(t, student_t_distribution, delta):
LIST = LIST - Ind
DROPPED_LIST.append(Ind)
return construct_race_output(LIST, DROPPED_LIST, N)