Selected Publications

• How to enforce an efficient Exploration/Exploitation trade-off ? Multi-armed bandit algorithms are among the best answers; some heuristics are needed to handle e.g. dynamic setting and/or large number of options.
• How to design the reward/fitness function most conducive to reach the goal, and most amenable to computational optimization ?

1. Extreme Value Based Adaptive Operator Selection.
   Alvaro Fialho, Luis Da Costa, Marc Schoenauer, and Michele Sebag.
   In 10th International Conference on Parallel Problem Solving From Nature (PPSN X), Springer Verlag, pages 175--184, 2008.
   pdf

   Evolutionary Computation Algorithms suffer from the "Crossing the Chasm" barrier: a significant expertise is needed to tune their parameters and get the best of it. In practice, EC algorithms involve quite a few control parameters to efficiently deal with e.g., non parametric representations or multiple objectives. The parameter setting governs the algorithm efficiency; furthermore, the optimal setting varies along search as the genetic population migrates toward higher fitness regions.
   The approach investigated here (resuming a paper from same authors published at GECCO'08) proceeds as follows:

   • The operator reward refers to its extreme fitness gain (how much an offspring improves on its parents when applying the operator), as opposed to, the average fitness gain;
   • Operators are selected through a dynamic Multi-Armed Bandit algorithm, enforcing an efficient trade-off between Exploitation (selecting the operator with best reward) and Exploration (selecting the operators which have not been selected much recently).

2. Data Streaming with Affinity Propagation.
   Xiangliang Zhang, Cyril Furtlehner, and Michèle Sebag,
   In 19th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML 2008), Springer-Verlag, LNCS (5212).
   pdf
   Affinity Propagation (AP), proposed by Frey and Dueck in 2007, is an examplar-based clustering algorithm, where the combinatorial search for the best examplars is formulated as the minimization of an energy function and tackled using message passing.
   In this paper, a Divide and Conquer approach is proposed to decrease AP quadratic computational complexity. Secondly, AP is extended to online clustering and dynamic data distribution, aka Data Streaming, forming the StrAP algorithm.
   A theoretical analysis of StrAP together with its application to Job Streaming in the context of the EGEE grid will appear in KDD 2009.

3. Ensemble Learning for Free with Evolutionary Algorithms ?
   Christian Gagné, Michele Sebag, Marc Schoenauer, and Marco Tomassini.
   In Dirk Thierens et al., editor, Proc. of Genetic and Evolutionary Conference, pages 1782-1789. ACM SIGEVO, ACM, 2007.
   http://hal.inria.fr/inria-00144010/en/
   Ensemble learning, building and aggregating a population of hypotheses, is among the most efficient approaches in Machine Learning. As Evolutionary Computation (EC)-based Learning also produces a great many hypotheses along the search, Evolutionary Ensemble Learning aims at producing an ensemble of hypotheses, using a co-evolution mechanism to yield diversity. Ultimately, a margin-based criterion is used to extract the best ensemble either along evolution or from the final population.
4. Structural Statistical Software Testing with Active Learning in a Graph
   Nicolas Baskiotis, Michele Sebag.
   In H. Blockeel, J. Ramong, J. Shavlik and Prasad Tadepalli, eds., 17th Annual International Conference on Inductive Logic Programming, Springer Verlag, LNAI (4894), p. 49-62. 2007.
   pdf

   In Structural Statistical Software Testing, the paths in the control flow graph of the program to be tested are exploited to generate test cases. The main limitation of this approach is when most paths are infeasible, i.e. they are never exerted whatever the values of the program input are.
   This paper presents an active learning approach, aimed at sampling the feasible paths in the control flow graph The proposed approach is based on a frugal representation inspired from Parikh maps, and on the identification of the conjunctive subconcepts in the feasible path concept within a Disjunctive Version Space framework. This paper resumes an earlier work on this topic, published at IJCAI 2007 (collaboration Marie-Claude Gaudel and Sandrine Gouraud).