Articles dans des revues avec comité de lecture
  1. inria-00369788, version 1 MATH:MATH_OC «Continuous lunches are free plus the design of optimal optimization algorithms», Auger, Anne; Teytaud, Olivier, Auger A., Teytaud O., Auger A. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI This paper analyses extensions of No-Free-Lunch (NFL) theorems to countably infinite and uncountable infinite domains and investigates the design of optimal optimization algorithms. The original NFL theorem due to Wolpert and Macready states that, for finite search domains, all search heuristics have the same performance when averaged over the uniform distribution over all possible functions. For infinite domains the extension of the concept of distribution over all possible functions involves measurability issues and stochastic process the- ory. For countably infinite domains, we prove that the natural extension of NFL theorems, for the current formalization of probability, does not hold, but that a weaker form of NFL does hold, by stating the existence of non-trivial distributions of fitness leading to equal performances for all search heuristics. Our main result is that for continuous domains, NFL does not hold. This free-lunch theorem is based on the formalization of the concept of random fitness functions by means of random fields. We also consider the design of optimal optimization algorithms for a given random field, in a black-box setting, namely, a complexity measure based solely on the number of requests to the fitness function. We derive an optimal algorithm based on Bellman's decomposition principle, for a given number of iterates and a given distribution of fitness functions. We also approximate this algorithm thanks to a Monte-Carlo planning algorithm close to the UCT (Upper Confidence Trees) algorithm, and provide experimental results. Anglais Algorithmica, (2009) (2009) internationale springer 10.1007/s00453-008-9244-5 () Articles dans des revues avec comité de lecture 1 (2009)

  2. inria-00369786, version 1 MATH:MATH_OC «The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments», Lee, Chang-Shing; Wang, Mei-Hui; Chaslot, Guillaume; Hoock, Jean-Baptiste; Rimmel, Arpad; Teytaud, Olivier; Tsai, Shang-Rong; Hsu, Shun-Chin; Hong, Tzung-Pei, Lee C.-S., Wang M.-H., Chaslot G., Hoock J.-B., Rimmel A., Teytaud O., Tsai S.-R., Hsu S.-C., Hong T.-P., Lee C.-S. et al, National University of Tainan - NUTN - NUTN - maastricht university - univ. Maastricht - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - Dept. of Information Management - CJCU - Dept. of Computer Science and Information Engineering - Kaoshiung university In order to promote computer Go and stimulate further development and research in the field, the event activities, “Computational Intelligence Forum” and “World 99 Computer Go Championship,” were held in Taiwan. This study focuses on the invited games played in the tournament, “Taiwanese Go players versus the computer program MoGo,” held at National University of Tainan (NUTN). Several Taiwanese Go players, including one 9-Dan professional Go player and eight amateur Go players, were invited by NUTN to play against MoGo from August 26 to October 4, 2008. The MoGo program combines All Moves As First (AMAF)/Rapid Action Value Estimation (RAVE) values, online “UCT-like” values, offline values extracted from databases, and expert rules. Additionally, four properties of MoGo are analyzed including: (1) the weakness in corners, (2) the scaling over time, (3) the behavior in handicap games, and (4) the main strength of MoGo in contact fights. The results reveal that MoGo can reach the level of 3 Dan with, (1) good skills for fights, (2) weaknesses in corners, in particular for “semeai” situations, and (3) weaknesses in favorable situations such as handicap games. It is hoped that the advances in artificial intelligence and computational power will enable considerable progress in the field of computer Go, with the aim of achieving the same levels as computer chess or Chinese chess in the future. Anglais IEEE Transactions on Computational Intelligence and AI in games, (2009) (2009) internationale IEEE () Articles dans des revues avec comité de lecture 1 (2009)

  3. inria-00343509, version 1 MATH:MATH_OC;INFO:INFO_LG «Combiner connaissances expertes, hors-ligne, transientes et en ligne pour l'exploration Monte-Carlo», Chatriot, Louis; Fiter, Christophe; Chaslot, Guillaume; Gelly, Sylvain; Hoock, Jean-Baptiste; Perez, J.; Rimmel, Arpad; Teytaud, Olivier, Chatriot L., Fiter C., Chaslot G., Gelly S., Hoock J.-B., Perez J., Rimmel A., Teytaud O., Chatriot L. et al, TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - maastricht university - univ. Maastricht - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI Nous combinons pour de l'exploration Monte-Carlo d'arbres de l'apprentissage arti- RÉSUMÉ. ficiel à 4 échelles de temps : – regret en ligne, via l'utilisation d'algorithmes de bandit et d'estimateurs Monte-Carlo ; – de l'apprentissage transient, via l'utilisation d'estimateur rapide de Q-fonction (RAVE, pour Rapid Action Value Estimate) qui sont appris en ligne et utilisés pour accélérer l'explora- tion mais sont ensuite peu à peu laissés de côté à mesure que des informations plus fines sont disponibles ; – apprentissage hors-ligne, par fouille de données de jeux ; – utilisation de connaissances expertes comme information a priori. L'algorithme obtenu est plus fort que chaque élément séparément. Nous mettons en évidence par ailleurs un dilemne exploration-exploitation dans l'exploration Monte-Carlo d'arbres et obtenons une très forte amélioration par calage des paramètres correspondant. We combine for Monte-Carlo exploration machine learning at four different time ABSTRACT. scales: – online regret, through the use of bandit algorithms and Monte-Carlo estimates; – transient learning, through the use of rapid action value estimates (RAVE) which are learnt online and used for accelerating the exploration and are thereafter neglected; – offline learning, by data mining of datasets of games; – use of expert knowledge coming from the old ages as prior information. Français Revue d'Intelligence Artificielle, (2008) (2008) nationale Hermès () computer-go,transient learning, expert knowledge,offline learning, online learning, Monte-Carlo Tree Search, UCT Articles dans des revues avec comité de lecture 1 (2008)

  4. inria-00173221, version 1 MATH:MATH_OC «comparison-based algorithms are robust and randomized algorithms are anytime.», Gelly, Sylvain; Ruette, Sylvie; Teytaud, Olivier, Gelly S., Ruette S., Teytaud O., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Mathématiques d'Orsay - LM-Orsay - CNRS : UMR8628 - Université Paris Sud - Paris XI Randomized search heuristics (e.g., evolutionary algorithms, simulated annealing etc.) are very appealing to practitioners, they are easy to implement and usually provide good performance. The theoretical analysis of these algorithms usually focuses on convergence rates. This paper presents a mathematical study of randomized search heuristicswhich use comparison based selectionmechanism. The twomain results are: (i) comparison-based algorithms are the best algorithms for some robustness criteria, (ii) introducing randomness in the choice of offspring improves the anytime behavior of the algorithm. An original Estimation of Distribution Algorithm combining (i) and (ii) is proposed and successfully experimented. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais Evolutionary Computation Journal, (2007) (2007) internationale MIT Press () Anytime optimization; non-linear optimization; comparison-based algorithms; complexity; theory; randomized search heuristics Articles dans des revues avec comité de lecture 1 (2007)

  5. inria-00164033, version 1 INFO:INFO_AI;INFO:INFO_LG;MATH:MATH_ST;STAT:TH «Change Point Detection and Meta-Bandits for Online Learning in Dynamic Environments», Hartland, Cédric; Baskiotis, Nicolas; Gelly, Sylvain; Sebag, Michele; Teytaud, Olivier, Hartland C., Baskiotis N., Gelly S., Sebag M., Teytaud O., Hartland C. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI Motivated by realtime website optimization, this paper is about online learning in abruptly changing environments. Two extensions of the UCBT algorithm are combined in order to handle dynamic multi-armed bandits, and specifically to cope with fast variations in the rewards. Firstly, a change point detection test based on Page-Hinkley statistics is used to overcome the limitations due to the UCBT inertia. Secondly, a controlled forgetting strategy dubbed Meta-Bandit is proposed to take care of the Exploration vs Exploitation trade-off when the PH test is triggered. Extensive empirical validation shows significant improvements compared to the baseline algorithms. The paper also investigates the sensitivity of the proposed algorithm with respect to the number of available options. apprentissage en ligne Anglais CAp, (2007) (2007) nationale cepadues 237-250 () online learning; meta bandits; ucb; dynamic environments Articles dans des revues avec comité de lecture 1 (2007)

  6. inria-00173239, version 1 MATH:MATH_OC «On the hardness of offline multiobjective optimization», Teytaud, Olivier, Teytaud O., Teytaud O., TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI It is empirically established that multiobjective evolutionary algorithms do not scale well with the number of conflicting objectives. We here show that the convergence rate of all comparison-based multiobjective algorithms, for the Hausdorff distance, is not much better than the convergence rate of the random search, unless the number of objectives is very moderate, in a framework in which the stronger assumptions are (i) that the objectives are conflicting (ii) that lower bounding the computational cost by the number of comparisons is a good model. Our conclusions are (i) the relevance of the number of conflicting objectives (ii) the relevance of criteria based on comparisons with random-search for multi-objective optimization (iii) the very-hardness of more than 3- objectives optimization (iv) some hints about cross-over operators. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais Evolutionary Computation Journal, (2007) (2007) internationale MIT Press () Multi-objective optimization;evolutionary algorithm;complexity Articles dans des revues avec comité de lecture 1 (2007)

  7. inria-00112840, version 1 INFO:INFO_LG;MATH:MATH_OC «Universal Consistency and Bloat in GP», Gelly, Sylvain; Teytaud, Olivier; Bredeche, Nicolas; Schoenauer, Marc, Gelly S., Teytaud O., Bredeche N., Schoenauer M., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI In this paper, we provide an analysis of Genetic Programming (GP) from the Statistical Learning Theory viewpoint in the scope of symbolic regression. Firstly, we are interested in Universal Consistency, i.e. the fact that the solution minimizing the empirical error does converge to the best possible error when the number of examples goes to infinity, and secondly, we focus our attention on the uncontrolled growth of program length (i.e. bloat), which is a well-known problem in GP. Results show that (1) several kinds of code bloats may be identified and that (2) Universal consistency can be obtained as well as avoiding bloat under some con- ditions. We conclude by describing an ad hoc method that makes it possible simultaneously to avoid bloat and to ensure universal consistency. Anglais Revue d'Intelligence Artificielle, (2006) (2006) non spécifiée Hermes-Lavoisier () Articles dans des revues avec comité de lecture 1 (2006)

  8. inria-00112838, version 1 INFO:INFO_LG «Bayesian Networks: a Non-Frequentist Approach for Parametrization, and a more Accurate Structural Complexity Measure», Gelly, Sylvain; Teytaud, Olivier, Gelly S., Teytaud O., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI The problem of calibrating relations from examples is a classical problem in learning theory. This problem has in particular been studied in the theory of empirical processes (providing asymptotic results), and through statistical learning theory. The application of learning theory to bayesian networks is still uncomplete and we propose a contribution, especially through the use of covering numbers. We deduce multiple corollaries, among which a non-frequentist approach for parameters learning and a score taking into account a measure of structural entropy that has never been taken into account before. We then investigate the algorithmic aspects of our theoretical solution, based on BFGS and adaptive refining of gradient calculus. Empirical results show the relevance of both the statistical results and the algorithmic solution. Anglais Revue d'Intelligence Artificielle, (2006) (2006) non spécifiée Hermes-Lavoisier () Articles dans des revues avec comité de lecture 1 (2006)

  9. hal-00078115, version 2 PHYS:MECA:MEFL;SPI:MECA:MEFL;INFO:INFO_NE «Optimal estimation for Large-Eddy Simulation of turbulence and application to the analysis of subgrid models», Moreau, Antoine; Teytaud, Olivier; Bertoglio, Jean-Pierre, Moreau A., Teytaud O., Bertoglio J.-P., Moreau A. et al, Laboratoire des sciences et matériaux pour l'électronique et d'automatique - LASMEA - CNRS : UMR6602 - Université Blaise Pascal - Clermont-Ferrand II - Laboratoire de Mecanique des Fluides et d'Acoustique - LMFA - CNRS : UMR5509 - Université Claude Bernard - Lyon I - Ecole Centrale de Lyon - Institut National des Sciences Appliquées de Lyon - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI The tools of optimal estimation are applied to the study of subgrid models for Large-Eddy Simulation of turbulence. The concept of optimal estimator is introduced and its properties are analyzed in the context of applications to a priori tests of subgrid models. Attention is focused on the Cook and Riley model in the case of a scalar field in isotropic turbulence. Using DNS data, the relevance of the beta assumption is estimated by computing (i) generalized optimal estimators and (ii) the error brought by this assumption alone. Optimal estimators are computed for the subgrid variance using various sets of variables and various techniques (histograms and neural networks). It is shown that optimal estimators allow a thorough exploration of models. Neural networks are proved to be relevant and very efficient in this framework, and further usages are suggested. Anglais Physics of Fluids, (2006-10-04) (2006) 18 105101 () large eddy simulation ; optimal estimation ; neural networks ; turbulence ; passive scalar ; turbulent combustion physics/0606053 Articles dans des revues avec comité de lecture 1 (2006)

  10. hal-00185086, version 1 INFO:INFO_TI «An adaptative filtering method to evalute normal vectors and surface areas of 3d objects. Application to snow images from X-ray tomography», Flin, Frédéric; Brzoska, Jean-Bruno; Coeurjolly, David; Pieritz, Romeu; Lesaffre, Bernard; Coléou, Cécile; Lamboley, Pascal; Teytaud, Olivier; Vignoles, Gérard; Delesse, Jean-François, Flin F., Brzoska J.-B., Coeurjolly D., Pieritz R., Lesaffre B., Coléou C., Lamboley P., Teytaud O., Vignoles G., Delesse J.-F., Flin F. et al, Météo-France - METEO-FRANCE - Météo France - Laboratoire d'InfoRmatique en Images et Systèmes d'Information - LIRIS - CNRS : UMR5205 - Université Claude Bernard - Lyon I - Université Lumière - Lyon II - Institut National des Sciences Appliquées de Lyon - Ecole Centrale de Lyon - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire des Composites Thermostructuraux - LCTS - CEA : DAM/DMAT - DEN/DTEC - CNRS : UMR5801 - Université Sciences et Technologies - Bordeaux I - Laboratoire Bordelais de Recherche en Informatique - LaBRI - CNRS : UMR5800 - Université Sciences et Technologies - Bordeaux I - Ecole Nationale Supérieure d'Electronique, Informatique et Radiocommunications de Bordeaux - Université Victor Segalen - Bordeaux II Estimating the normal vector field on the boundary of discrete 3D objects is essential for rendering and image measurement problems. Most of the existing algorithms do not provide an accurate determination of the normal vector field for shapes that present edges. We propose here a new and simple computational method in order to obtain accurate results on all types of shapes whatever their local convexity degree is. The presented method is based on the gradient vector field analysis of the object distance map. This vector field is adaptively filtered around each surface voxel using angle and symmetry criteria, so that as many relevant contributions as possible are accounted for. This optimizes the smoothing of digitization effects while preserving relevant details of the processed numerical object. Thanks to the precise normal field obtained, a projection method can be proposed to derive immediately the surface area from a raw discrete object. An empirical justification of the validity of such an algorithm in the continuous limit is also provided. Some results on simulated data and snow images from X-ray tomography are presented, compared to the Marching Cubes and Convex Hull results and discussed. Anglais IEEE Transactions on Image Processing, (2005) (2005) internationale 14 5 585-596 () Articles dans des revues avec comité de lecture 1 (2005)

Communications avec acte
  1. inria-00369782, version 1 MATH:MATH_OC «A Statistical Learning Perspective of Genetic Programming}», Amil, Merve; Bredeche, Nicolas; Gagné, Christian; Gelly, Sylvain; Schoenauer, Marc; Teytaud, Olivier, Amil M., Bredeche N., Gagné C., Gelly S., Schoenauer M., Teytaud O., Amil M. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI This paper proposes a theoretical analysis of Genetic Programming (GP) from the perspective of statistical learning theory, a well grounded mathematical toolbox for machine learning. By computing the Vapnik-Chervonenkis dimension of the family of programs that can be inferred by a specific setting of GP, it is proved that a parsimonious fitness ensures universal consistency. This means that the empirical error minimization allows convergence to the best possible error when the number of test cases goes to infinity. However, it is also proved that the standard method consisting in putting a hard limit on the program size still results in programs of infinitely increasing size in function of their accuracy. It is also shown that cross-validation or hold-out for choosing the complexity level that optimizes the error rate in generalization also leads to bloat. So a more complicated modification of the fitness is proposed in order to avoid unnecessary bloat while nevertheless preserving universal consistency. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais (2009) (2009) internationale Springer Proceedings of EuroGP 09 EuroGP Tuebingen Allemagne (2009) (2009) Communications avec acte 1 (2009)

  2. inria-00369783, version 1 MATH:MATH_OC «Grid coevolution for adaptive simulations; application to the building of opening books in the game of Go», Audouard, Pierre; Chaslot, Guillaume; Hoock, Jean-Baptiste; Rimmel, Arpad; Perez, J.; Teytaud, Olivier, Audouard P., Chaslot G., Hoock J.-B., Rimmel A., Perez J., Teytaud O., Audouard P. et al, Go expert - Go expert - maastricht university - univ. Maastricht - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI This paper presents a successful application of parallel (grid) coevolution applied to the building of an opening book (OB) in 9x9 Go. Known sayings around the game of Go are refound by the algorithm, and the resulting program was also able to credibly comment openings in professional games of 9x9 Go. Interestingly, beyond the application to the game of Go, our algorithm can be seen as a ”meta”-level for the UCT-algorithm: ”UCT applied to UCT” (instead of ”UCT applied to a random player” as usual), in order to build an OB. It is generic and could be applied as well for analyzing a given situation of a Markov Decision Process. G.: Mathematics of Computing/G.0: GENERAL Anglais (2009) (2009) internationale Springer EvoGames Tuebingen Allemagne (2009) (2009) Communications avec acte 1 (2009)

  3. inria-00386477, version 1 MATH:MATH_OC «Adding expert knowledge and exploration in Monte-Carlo Tree Search», Chaslot, Guillaume; Fiter, Christophe; Hoock, Jean-Baptiste; Rimmel, Arpad; Teytaud, Olivier, Chaslot G., Fiter C., Hoock J.-B., Rimmel A., Teytaud O., Chaslot G. et al, maastricht university - univ. Maastricht - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI We present a new exploration term, more efficient than clas- sical UCT-like exploration terms and combining efficiently expert rules, patterns extracted from datasets, All-Moves-As-First values and classi- cal online values. As this improved bandit formula does not solve several important situations (semeais, nakade) in computer Go, we present three other important improvements which are central in the recent progress of our program MoGo: { We show an expert-based improvement of Monte-Carlo simulations for nakade situations; we also emphasize some limitations of this modification. { We show a technique which preserves diversity in the Monte-Carlo simulation, which greatly improves the results in 19x19. { Whereas the UCB-based exploration term is not efficient in MoGo, we show a new exploration term which is highly efficient in MoGo. MoGo recently won a game with handicap 7 against a 9Dan Pro player, Zhou JunXun, winner of the LG Cup 2007, and a game with handicap 6 against a 1Dan pro player, Li-Chen Chien. Anglais (2009) (2009) internationale Springer Advances in Computer Games Pamplona Espagne (2009) (2009) Communications avec acte 1 (2009)

  4. inria-00380125, version 1 INFO:INFO_NE;MATH:MATH_OC «On the huge benefit of quasi-random mutations for multimodal optimization with application to grid-based tuning of neurocontrollers», Chaslot, Guillaume; Hoock, Jean-Baptiste; Teytaud, Fabien; Teytaud, Olivier, Chaslot G., Hoock J.-B., Teytaud F., Teytaud O., Chaslot G. et al, maastricht university - univ. Maastricht - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI In this paper, we study the optimization of a neural network used for controlling a Monte-Carlo Tree Search (MCTS/UCT) algorithm. The main results are: (i) the specification of a new multimodal benchmark function; this function has been defined in particular in agreement with [1] which has pointed out that most multimodal functions are not satisfactory for some real-world multimodal scenarios (section 2); (ii) experimentation of Evolution Strategies on this new multimodal benchmark function, showing the great efficiency of quasi-random mutations in this framework (section 3); (iii) the proof-of-concept of the application of ES for grid-based tuning Neural Networks for controlling MCTS/UCT (see section 3). Anglais (2009) (2009) internationale ESANN Bruges Belgique (2009-04-22) (2009) Communications avec acte 1 (2009)

  5. inria-00386476, version 1 MATH:MATH_OC «A Novel Ontology for Computer Go Knowledge Management», Lee, Chang-Shing; Mei-Hui, Wang; Hong, Tzung-Pei; Chaslot, Guillaume; Hoock, Jean-Baptiste; Rimmel, Arpad; Teytaud, Olivier; Kuo, Yau-Hwang, Lee C.-S., Mei-Hui W., Hong T.-P., Chaslot G., Hoock J.-B., Rimmel A., Teytaud O., Kuo Y.-H., Lee C.-S. et al, Department of Computer Science and Information Engineering - NUTN - maastricht university - univ. Maastricht - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - CREDIT Research Center - National Cheng Kung University In order to stimulate the development and research in computer Go, several Taiwanese Go players, including three professional Go players and four amateur Go players, were invited to play against the famous computer Go program, MoGo, in the Taiwan Open 2009. The MoGo program combines the online game values, offline values extracted from databases, and expert rules defined by Go expert that shows an excellent performance in the games. The results reveal that MoGo can reach the level of 3 Dan in Taiwan amateur Go environment. But there are still some drawbacks for MoGo that should be solved, for example, the weaknesses in semeai and how to flexibly practice the human knowledge through the embedded opening books. In this paper, a new game record ontology for computer Go knowledge management is proposed to solve the problems that MoGo is facing. It is hoped that the advances in intelligent agent and ontology model can provide much more knowledge to make a progress in computer Go and achieve as much as computer chess or Chinese chess in the future. Anglais (2009) (2009) internationale IEEE FUZZ Jeju Corée, République de (2009) (2009) Communications avec acte 1 (2009)

  6. inria-00386475, version 1 MATH:MATH_OC «Optimizing Low-Discrepancy Sequences with an Evolutionary Algorithm», Rainville, François-Michel De; Gagné, Christian; Teytaud, Olivier; Laurendeau, Denis, Rainville F.-M. D., Gagné C., Teytaud O., Laurendeau D., Rainville F.-M. D. et al, Département de génie électrique et de génie informatique - Université Laval - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Many elds rely on some stochastic sampling of a given com- plex space. Low-discrepancy sequences are methods aim- ing at producing samples with better space-lling properties than uniformly distributed random numbers, hence allow- ing a more ecient sampling of that space. State-of-the-art methods like nearly orthogonal Latin hypercubes and scram- bled Halton sequences are congured by permutations of in- ternal parameters, where permutations are commonly done randomly. This paper proposes the use of evolutionary al- gorithms to evolve these permutations, in order to optimize a discrepancy measure. Results show that an evolution- ary method is able to generate low-discrepancy sequences of signicantly better space-lling properties compared to sequences congured with purely random permutations. Anglais (2009) (2009) internationale ACM 8 pages Genetic and Evolutionary Computation Conference Montréal Canada (2009) (2009) Communications avec acte 1 (2009)

  7. inria-00433866, version 1 MATH:MATH_OC «Boosting Active Learning to Optimality: a Tractable Monte-Carlo, Billiard-based Algorithm», Rolet, Philippe; Sebag, Michèle; Teytaud, Olivier, Rolet P., Sebag M., Teytaud O., Rolet P. et al, Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Abstract. This paper focuses on Active Learning with a limited num- ber of queries; in application domains such as Numerical Engineering, the size of the training set might be limited to a few dozen or hundred exam- ples due to computational constraints. Active Learning under bounded resources is formalized as a finite horizon Reinforcement Learning prob- lem, where the sampling strategy aims at minimizing the expectation of the generalization error. A tractable approximation of the optimal (in- tractable) policy is presented, the Bandit-based Active Learner (BAAL) algorithm. Viewing Active Learning as a single-player game, BAAL com- bines UCT, the tree structured multi-armed bandit algorithm proposed by Kocsis and Szepesv´ri (2006), and billiard algorithms. A proof of a principle of the approach demonstrates its good empirical convergence toward an optimal policy and its ability to incorporate prior AL crite- ria. Its hybridization with the Query-by-Committee approach is found to improve on both stand-alone BAAL and stand-alone QbC. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS, G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization, G.: Mathematics of Computing/G.3: PROBABILITY AND STATISTICS/G.3.7: Probabilistic algorithms (including Monte Carlo), G.3.13: Statistical computing Anglais (2009) (2009) internationale 302-317 ECML Bled Slovénie (2009) (2009) Communications avec acte 1 (2009)

  8. inria-00374910, version 1 MATH:MATH_OC «Optimal robust expensive optimization is tractable», Rolet, Philippe; Sebag, Michele; Teytaud, Olivier, Rolet P., Sebag M., Teytaud O., Rolet P. et al, Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Following a number of recent papers investigating the possibility of optimal comparison-based optimization algorithms for a given distribution of probability on fitness functions, we (i) discuss the comparison-based constraints (ii) choose a setting in which theoretical tight bounds are known (iii) develop a careful implementation using billiard algorithms, Upper Confidence trees and (iv) experimentally test the tractability of the approach. The results, on still very simple cases, show that the approach, yet still preliminary, could be tested successfully until dimension 10 and horizon 50 iterations within a few hours on a standard computer, with convergence rate far better than the best algorithms. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization, I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.8: Problem Solving, Control Methods, and Search Anglais (2009) (2009) internationale 8 pages Gecco 2009 Montréal Canada (2009) (2009) ACM Communications avec acte 1 (2009)

  9. inria-00369787, version 1 MATH:MATH_OC «Upper Confidence Trees and Billiards for Optimal Active Learning», Rolet, Philippe; Sebag, Michèle; Teytaud, Olivier, Rolet P., Sebag M., Teytaud O., Rolet P. et al, Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI This paper focuses on Active Learning (AL) with bounded compu- tational resources. AL is formalized as a finite horizon Reinforcement Learning problem, and tackled as a single-player game. An approximate optimal AL strat- egy based on tree-structured multi-armed bandit algorithms and billiard-based sampling is presented together with a proof of principle of the approach. Anglais (2009) (2009) nationale CAP09 Hammamet, Tunisie Tunisie (2009) (2009) Communications avec acte 1 (2009)

  10. inria-00380539, version 1 INFO:INFO_LG «Creating an Upper-Confidence-Tree program for Havannah», Teytaud, Fabien; Teytaud, Olivier, Teytaud F., Teytaud O., Teytaud F. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Monte-Carlo Tree Search and Upper Confidence Bounds pro- vided huge improvements in computer-Go. In this paper, we test the generality of the approach by experimenting on another game, Havannah, which is known for being especially difficult for computers. We show that the same results hold, with slight differences related to the absence of clearly known patterns for the game of Havannah, in spite of the fact that Havannah is more related to connection games like Hex than to territory games like Go. Anglais (2009) (2009) internationale ACG 12 Pamplona Espagne (2009-05-11) (2009) Communications avec acte 1 (2009)

  11. inria-00369781, version 1 MATH:MATH_OC «On the parallel speed-up of Estimation of Multivariate Normal Algorithm and Evolution Strategies», Teytaud, Fabien; Teytaud, Olivier, Teytaud F., Teytaud O., Teytaud F. et al, Institut National de la Recherche en Informatique et en Automatique - INRIA FUTURS - INRIA - UFR Sciences - Université Paris-Sud XI - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Motivated by parallel optimization, we experiment EDA-like adaptation-rules in the case of $\lambda$ large. The rule we use, essentially based on estimation of multivariate normal algorithm, is (i) compliant with all families of distributions for which a density estimation algorithm exists (ii) simple (iii) parameter-free (iv) better than current rules in this framework of $\lambda$ large. The speed-up as a function of $\lambda$ is consistent with theoretical bounds. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.3: Numerical Linear Algebra, G.: Mathematics of Computing/G.3: PROBABILITY AND STATISTICS Anglais (2009) (2009) internationale springer Proceedings of EvoStar workshop 2009 EvoNum EvoNum (evostar workshop) Tuebingen Allemagne (2009) (2009) Communications avec acte 1 (2009)

  12. inria-00369780, version 1 MATH:MATH_OC «Why one must use reweighting in Estimation Of Distribution Algorithms», Teytaud, Fabien; Teytaud, Olivier, Teytaud F., Teytaud O., Teytaud F. et al, Institut National de la Recherche en Informatique et en Automatique - INRIA FUTURS - INRIA - UFR Sciences - Université Paris-Sud XI - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We study the update of the distribution in Estimation of Distribution Algorithms, and show that a simple modification leads to unbiased estimates of the optimum. The simple modification (based on a proper reweighting of estimates) leads to a strongly improved behavior in front of premature convergence. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization, G.: Mathematics of Computing/G.3: PROBABILITY AND STATISTICS Anglais (2009) (2009) internationale GECCO Montréal Canada (2009) (2009) Communications avec acte 1 (2009)

  13. inria-00287883, version 1 MATH:MATH_OC «Introduction de connaissances expertes en Bandit-Based Monte-Carlo Planning avec application au Computer-Go», Chatriot, Louis; Gelly, Sylvain; Hoock, Jean-Baptiste; Pérez, Julien; Rimmel, Arpad; Teytaud, Olivier, Chatriot L., Gelly S., Hoock J.-B., Pérez J., Rimmel A., Teytaud O., Chatriot L. et al, TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI Nous ajoutons différentes astuces d'expertise Go dans un programmation de planification Monte-Carlo à partir de bandits, via des simulations virtuelles ajoutées aux statistiques de bandits. Français (2008) (2008) nationale JFPDA Metz France (2008-06) (2008) Communications avec acte 1 (2008)

  14. inria-00287867, version 1 MATH:MATH_OC «On the Parallelization of Monte-Carlo planning», Gelly, Sylvain; Hoock, Jean-Baptiste; Rimmel, Arpad; Teytaud, Olivier; Kalemkarian, Yann, Gelly S., Hoock J.-B., Rimmel A., Teytaud O., Kalemkarian Y., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Bull - société Bull We provide a parallelization with and without shared-memory for Bandit-Based Monte-Carlo Planning algorithms, applied to the game of Go. The resulting algorithm won the first non-blitz game against a professionnal human player in 9x9 Go. Anglais (2008) (2008) internationale ICINCO Madeira Portugal (2008-05) (2008) Parallelization;Monte-Carlo Planning;Bandits Communications avec acte 1 (2008)

  15. inria-00287874, version 1 MATH:MATH_OC «On the almost optimality of blind active sampling.», Teytaud, Olivier, Teytaud O., Teytaud O., Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We show that blind active sampling is almost optimal in the case of large covering numbers in regression with finite precision. Anglais (2008) (2008) nationale CAP 2008 Porquerolles France (2008-05) (2008) Communications avec acte 0 (2008)

  16. inria-00287863, version 1 MATH:MATH_OC «When does quasi-random work ?», Teytaud, Olivier, Teytaud O., Teytaud O., Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We experiment the efficiency of quasi-random mutations in evolution strategies in continuous domains from various points of views: (i) non-convexity (ii) convergence rate (iii) non-asymptotic behavior (iv) noise. We conclude that quasi-random mutations are great. Anglais (2008) (2008) internationale Parallel Problem Solving from Nature Dortmund Allemagne (2008-09) (2008) Evolution strategies; derandomization; non-asymptotic results Communications avec acte 1 (2008)

  17. inria-00287845, version 1 MATH:MATH_OC «Lower bounds for evolution strategies using VC-dimension», Teytaud, Olivier; Fournier, Hervé, Teytaud O., Fournier H., Teytaud O. et al, Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Saclay - Ile de France - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Parallélisme, Réseaux, Systèmes d'information, Modélisation - PRISM - CNRS : UMR8144 - Université de Versailles-Saint Quentin en Yvelines We derive lower bounds for comparison-based or selection-based algorithms, improving existing results in the continuous setting, and extending them to non-trivial results in the discrete case. We introduce for that the use of the VC-dimension of the level sets of the fitness functions; results are then obtained through the use of Sauer's lemma. In the special case of optmization of the sphere function, improved lower bounds are obtained by bounding the possible number of sign conditions realized by some systems of equations. The results include several applications to the parametrization of sequential or parallel algorithms of type $\mul$-ES. Anglais (2008) (2008) internationale 10 pages Parallel Problem Solving from Nature Dortmund Allemagne (2008-09) (2008) VC-dimension;Convergence rate;Evolution Strategies Communications avec acte 1 (2008)

  18. inria-00173209, version 1 MATH:MATH_OC «Continuous lunches are free!», Auger, Anne; Teytaud, Olivier, Auger A., Teytaud O., Auger A. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI This paper investigates extensions of No Free Lunch (NFL) theorems to countably infinite and uncountable infinite do- mains. The original NFL due to Wolpert and Macready states that all search heuristics have the same performance when averaged over the uniform distribution over all possible functions. For infinite domains the extension of the concept of distribution over all possible functions involves measur- ability issues and stochastic process theory. For countably infinite domains, we prove that the natural extension of NFL theorems does not hold, but that a weaker form of NFL does hold, by stating the existence of non-trivial distribution of fitness leading to equal performance for all search heuristics. Our main result is that for continuous domains, NFL does not hold. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais (2007) (2007) internationale GECCO London Royaume-Uni (2007) (2007) Optimisation;Free lunches;NFL Communications avec acte 1 (2007)

  19. inria-00173259, version 1 MATH:MATH_ST «Inductive-deductive systems: a mathematical logic and statistical learning perspective», Baskiotis, Nicolas; Sebag, Michele; Teytaud, Olivier, Baskiotis N., Sebag M., Teytaud O., Baskiotis N. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI The theorems about incompleteness of arithmetic have often been cited as an argument against automatic theorem proving and expert systems. However, these theorems rely on a worst-case analysis, which might happen to be overly pessimistic with respect to real-world domain applications. For this reason, a new framework for a probabilistic analysis of logical complexity is presented in this paper. Specifically, the rate of non-decidable clauses and the convergence of a set of axioms toward the target one when the latter exists in the language are studied, by combining results from mathematical logic and from statistical learning. Two theoretical settings are considered, where learning relies respectively on Turing oracles guessing the provability of a statement from a set of statements, and computable approximations thereof. Interestingly, both settings lead to similar results regarding the convergence rate towards completeness. F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES, G.: Mathematics of Computing/G.3: PROBABILITY AND STATISTICS Anglais (2007) (2007) nationale CAP Grenoble France (2007) (2007) Inductive-Deductive Systems; learning theory Communications avec acte 1 (2007)

  20. inria-00173207, version 1 MATH:MATH_OC «DCMA, yet another derandomization in covariance-matrix-adaptation», Teytaud, Olivier; Gelly, Sylvain, Teytaud O., Gelly S., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI In a preliminary part of this paper, we analyze the neces- sity of randomness in evolution strategies. We conclude to the necessity of ”continuous”-randomness, but with a much more limited use of randomness than what is commonly used in evolution strategies. We then apply these results to CMA- ES, a famous evolution strategy already based on the idea of derandomization, which uses random independent Gaus- sian mutations. We here replace these random independent Gaussian mutations by a quasi-random sample. The mod- ification is very easy to do, the modified algorithm is com- putationally more efficient and its convergence is faster in terms of the number of iterates for a given precision. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais (2007) (2007) internationale GECCO London Royaume-Uni (2007) (2007) Derandomization; Evolutionary Algorithms; Low-discrepancy;Quasi-Random Communications avec acte 1 (2007)

  21. inria-00173237, version 1 MATH:MATH_OC «Conditionning, halting criteria and choosing lambda», Teytaud, Olivier, Teytaud O., Teytaud O., TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We show the convergence of 1+ lambda-ES with standard step-size update-rules on a large family of fitness functions without any convexity assumption or quasi-convexity assumptions ([5, 6]). The result provides a rule for choosing lambda and shows the consistency of halting criteria based on thresholds on the step-size. The family of functions under work is defined through a conditionnumber that generalizes usual condition-numbers in a manner that only depends on level-sets. We consider that the definition of this conditionnumber is the relevant one for evolutionary algorithms; in particular, global convergence results without convexity or quasi-convexity assumptions are proved when this condition-number is finite. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS, G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais (2007) (2007) internationale EA07 Tours France (2007) (2007) halting criteria; theory; optimization;evolutionary algorithms Communications avec acte 1 (2007)

  22. inria-00173263, version 1 INFO:INFO_GT «Anytime many-armed bandits», Teytaud, Olivier; Gelly, Sylvain; Sebag, Michele, Teytaud O., Gelly S., Sebag M., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI This paper introduces the many-armed bandit problem (ManAB), where the number of arms is large comparatively to the relevant number of time steps. While the ManAB framework is relevant to many real-world applications, the state of the art does not offer anytime algorithms handling ManAB problems. Both theory and practice suggest that two problem categories must be distinguished; the easy category includes those problems where good arms have reward probability close to 1; the difficult category includes other problems. Two algorithms termed FAILURE and MUCBT are proposed for the ManAB framework. FAILURE and its variants extend the non-anytime approach proposed for the denumerable-armed bandit and non-asymptotic bounds are shown; it works very efficiently for easy ManAB problems. Meanwhile, MUCBT efficiently deals with difficult ManAB problems. I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.8: Problem Solving, Control Methods, and Search Anglais (2007) (2007) nationale CAP07 Grenoble France (2007) (2007) Communications avec acte 1 (2007)

  23. inria-00173241, version 1 MATH:MATH_OC «Slightly beyond Turing-Computability for studying Genetic Programming», Teytaud, Olivier, Teytaud O., Teytaud O., TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Inspired by genetic programming (GP), we study iterative algorithms for non-computable tasks and compare them to naive models. This framework justifies many practical standard tricks from GP and also provides complexity lower-bounds which justify the computational cost of GP thanks to the use of Kolmogorov's complexity in bounded time. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais (2007) (2007) internationale MCU'07 Orléans France (2007) (2007) Genetic Programming;computability; complexity Communications avec acte 1 (2007)

  24. inria-00173202, version 1 MATH:MATH_OC «Non linear programming for stochastic dynamic programming», Teytaud, Olivier; Gelly, Sylvain, Teytaud O., Gelly S., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Many stochastic dynamic programming tasks in continuous action-spaces are tackled through discretization. We here avoid discretization; then, approximate dynamic programming (ADP) involves (i) many learning tasks, performed here by Support Vector Machines, for Bellman-function-regression (ii) many non-linearoptimization tasks for action-selection, for which we compare many algorithms. We include discretizations of the domain as particular non-linear-programming-tools in our experiments, so that by the way we compare optimization approaches and discretization methods. We conclude that robustness is strongly required in the non-linear-optimizations in ADP, and experimental results show that (i) discretization is sometimes inefficient, but some specific discretization is very efficient for "bang-bang" problems (ii) simple evolutionary tools outperform quasi-random in a stable manner (iii) gradient-based techniques are much less stable (iv) for most high-dimensional "less unsmooth" problems Covariance-Matrix-Adaptation is first ranked. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais (2007) (2007) internationale Icinco 2007 Angers France (2007) (2007) Control;Dynamic programming;Non Linear Programming Communications avec acte 1 (2007)

  25. inria-00173204, version 1 MATH:MATH_OC «Active learning in regression, with an application to stochastic dynamic programming», Teytaud, Olivier; Gelly, Sylvain; Mary, Jérémie, Teytaud O., Gelly S., Mary J., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We study active learning as a derandomized form of sampling. We show that full derandomization is not suitable in a robust framework, propose partially derandomized samplings, and develop new active learning methods (i) in which expert knowledge is easy to integrate (ii) with a parameter for the exploration/exploitation dilemma (iii) less randomized than the full-random sampling (yet also not deterministic). Experiments are performed in the case of regression for value-function learning on a continuous domain. Our main results are (i) efficient partially derandomized point sets (ii) moderate-derandomization theorems (iii) experimental evidence of the importance of the frontier (iv) a new regression-specific user-friendly sampling tool lessrobust than blind samplers but that sometimes works very efficiently in large dimensions. All experiments can be reproduced by downloading the source code and running the provided command line. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais (2007) (2007) internationale ICINCO 2007 Angers France (2007) (2007) Active Learning; Stochastic Dynamic Programming; Sampling Communications avec acte 1 (2007)

  26. inria-00173224, version 1 MATH:MATH_OC «On the adaptation of the noise level for stochastic optimization», Teytaud, Olivier; Auger, Anne, Teytaud O., Auger A., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI This paper deals with the optimization of noisy fitness functions, where the noise level can be reduced by increasing the computational effort. We theoretically investigate the question of the control of the noise level. We analyse two different schemes for an adaptive control and prove sufficient conditions ensuring the existence of an homogeneous Markov chain, which is the first step to prove linear convergence when dealing with non-noisy fitness functions. We experimentally validate the relevance of the homogeneity criterion. Large-scale experiments conclude to the efficiency in a difficult framework. G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization Anglais (2007) (2007) internationale IEEE Congress on Evolutionary Computation Singapour Singapour (2007) (2007) Noisy optimization; evolutionary algorithms; Markov chains Communications avec acte 1 (2007)

  27. inria-00117392, version 1 INFO:INFO_LG «OpenDP a free Reinforcement Learning toolbox for discrete time control problems», Gelly, Sylvain; Teytaud, Olivier, Gelly S., Teytaud O., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI OpenDP (http://opendp.sourceforge.net) is a free software (under GPL) written in C++ for control problems: (i) with discrete time steps (either finite horizon, or approximation of infinite horizon by temporal-ring for stationnary problems), (ii) where the transition function newState = T (state, decision) can be encoded in C++, (iii) possibly stochastic (with the function T above depending on some random process). Anglais (2006-12-09) (2006) non spécifiée NIPS Workshop on Machine Learning Open Source Software Whistler (B.C.) (2006-12-09) (2006) Communications avec acte 1 (2006)

  28. inria-00112816, version 1 MATH:MATH_OC;INFO:INFO_AI «On the ultimate convergence rates for isotropic algorithms and the best choices among various forms of isotropy», Gelly, Sylvain; Mary, Jérémie; Teytaud, Olivier, Gelly S., Mary J., Teytaud O., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI In this paper, we show universal lower bounds for isotropic algorithms, that hold for any algorithm such that each new point is the sum of one already visited p oint plus one random isotropic direction multiplied by any step size (whenever the step size is chosen by an oracle with arbitrarily high computational power). The bound is 1 − O(1/d) for the constant in the linear convergence (i.e. the constant C such that the distance to the optimum after n steps is upp er b ounded by C n ), as already seen for some families of evolution strategies in [19, 12], in contrast with 1 − O(1) for the reverse case of a random step size and a direction chosen by an oracle with arbitrary high computational power. We then recall that isotropy does not uniquely determine the distribution of a sample on the sphere and show that the convergence rate in isotropic algorithms is improved by using stratified or antithetic isotropy instead of naive isotropy. We show at the end of the pap er that b eyond the mathematical proof, the result holds on exp eriments. We conclude that one should use antithetic-isotropy or stratified-isotropy, and never standard-isotropy. Anglais (2006-09-09) (2006) non spécifiée Parallel Problem Solving from Nature Reykjavik (2006-09-09) (2006) Communications avec acte 1 (2006)

  29. inria-00112813, version 1 INFO:INFO_AI «Comparison-based algorithms: worst-case optimality, optimality w.r.t a bayesian prior, the intraclass-variance minimization in EDA, and implementations with billiards», Gelly, Sylvain; Ruette, Sylvie; Teytaud, Olivier, Gelly S., Ruette S., Teytaud O., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Mathématiques d'Orsay - LM-Orsay - CNRS : UMR8628 - Université Paris Sud - Paris XI This paper is centered on the analysis of comparison-based algorithms. It has been shown recently that these algorithms are at most linearly convergent with a constant 1 − O(1/d); we here show that these algorithms are however optimal for robust optimization w.r.t increasing transformations of the fitness. We then turn our attention to the design of optimal comparison-based algorithms. No-Free-Lunch theorems have shown that introducing priors is necessary in order to design algorithms better than others; therefore, we include a bayesian prior in the spirit of learning theory. We show that these algorithms have a nice interpretation in terms of Estimation-Of-Distribution algorithms, and provide tools for the optimal design of generations of lambda-points by the way of billiard algorithms. Anglais (2006-09-09) (2006) non spécifiée Parallel Problem Solving from Nature BTP-Workshop Reykjavik (2006-09-09) (2006) Communications avec acte 1 (2006)

  30. inria-00112796, version 1 INFO:INFO_LG «Learning for stochastic dynamic programming», Gelly, Sylvain; Mary, Jérémie; Teytaud, Olivier, Gelly S., Mary J., Teytaud O., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We present experimental results about learning function values (i.e. Bellman values) in stochastic dynamic programming (SDP). All results come from openDP (opendp.sourceforge.net), a freely available source code, and therefore can be reproduced. The goal is an independent comparison of learning methods in the framework of SDP. Anglais (2006-04-26) (2006) non spécifiée 11th European Symposium on Artificial Neural Networks (ESANN) bruges Belgium (2006-04-26) (2006) Communications avec acte 1 (2006)

  31. inria-00112803, version 1 INFO:INFO_LG;INFO:INFO_NA «Resource-Aware Parameterizations of EDA», Gelly, Sylvain; Teytaud, Olivier; Cagne, Christian, Gelly S., Teytaud O., Cagne C., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI This paper presents a framework for the theoretical analysis of Estimation of Distribution Algorithms (EDA). Using this framework, derived from the VC-theory, we propose non-asymptotic bounds which depend on: 1) the population size 2) the selection rate, 3) the families of distributions used for the modelling, 4) the dimension, and 5) the number of iterations. To validate these results, optimization algorithms are applied to a context where bounds on resources are crucial, namely Design of Experiments, that is a black-box optimization with very few fitness-values evaluations. Anglais (2006-07-16) (2006) non spécifiée Congress on Evolutionary Computation Vancouver, BC, Canada (2006-07-16) (2006) Communications avec acte 1 (2006)

  32. hal-00113593, version 1 INFO:INFO_BT;SCCO:COMP «Statistical inference and data mining: false discoveries control», Lallich, Stéphane; Teytaud, Olivier; Prudhomme, Elie, Lallich S., Teytaud O., Prudhomme E., Lallich S. et al, Equipe de Recherche en Ingénierie des Connaissances - ERIC - Université Lumière - Lyon II : EA3083 - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Data Mining is characterised by its ability at processing large amounts of data. Among those are the data ”features”- variables or association rules that can be derived from them. Selecting the most interesting features is a classical data mining problem. That selection requires a large number of tests from which arise a number of false discoveries. An original non parametric control method is proposed in this paper. A new criterion, UAFWER, defined as the risk of exceeding a pre-set number of false discoveries, is controlled by BS FD, a bootstrap based algorithm that can be used on one- or two-sided problems. The usefulness of the procedure is illustrated by the selection of differentially interesting association rules on genetic data. Anglais (2006) (2006) Springer-Verlag 12 pages (2006) (2006) IASC Communications avec acte 1 (2006)

  33. hal-00113370, version 1 MATH:MATH_OC «Why Simulation-Based Approachs with Combined Fitness are a Good Approach for Mining Spaces of Turing-equivalent Functions», Teytaud, Olivier, Teytaud O., Teytaud O., TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We show negative results about the automatic generation of programs within bounded-time. Combining recursion theory and statistics, we contrast these negative results with positive computability results for iterative approachs like genetic programming, provided that the fitness combines e.g. fastness and size. We then show that simulation-based approachs (approachs evaluating only by simulation the quality of programs) like GP are not too far from the minimal time required for evaluating these combined fitnesses. Anglais (2006) (2006) non spécifiée IEEE 12 pages (2006) (2006) Communications avec acte 1 (2006)

  34. inria-00112820, version 1 MATH:MATH_OC;INFO:INFO_AI «General lower bounds for evolutionary algorithms», Teytaud, Olivier; Gelly, Sylvain, Teytaud O., Gelly S., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Evolutionary optimization, among which genetic optimization, is a general framework for optimization. It is known (i) easy to use (ii) robust (iii) derivative-free (iv) unfortunately slow. Recent work [8] in particular show that the convergence rate of some widely used evolution strategies (evolutionary optimization for continuous domains) can not be faster than linear (i.e. the logarithm of the distance to the optimum can not decrease faster than linearly), and that the constant in the linear convergence (i.e. the constant C such that the distance to the optimum after n steps is upp er b ounded by C n ) unfortunately converges quickly to 1 as the dimension increases to infinity. We here show a very wide generalization of this result: al l comparison-based algorithms have such a limitation. Note that our result also concerns methods like the Hooke & Jeeves algorithm, the simplex method, or any direct search method that only compares the values to previously seen values of the fitness. But it does not cover methods that use the value of the fitness (see [5] for cases in which the fitness-values are used), even if these methods do not use gradients. The former results deal with convergence with respect to the number of comparisons performed, and also include a very wide family of algorithms with resp ect to the number of function-evaluations. However, there is still place for faster convergence rates, for more original algorithms using the full ranking information of the population and not only selections among the population. We prove that, at least in some particular cases, using the full ranking information can improve these lower bounds, and ultimately provide sup erlinear convergence results. Anglais (2006-09-09) (2006) non spécifiée Parallel Problem Solving from Nature Reykjavik (2006-09-09) (2006) Communications avec acte 1 (2006)

  35. inria-00000540, version 1 MATH:MATH_OC «Local and global oder 3/2 convergence of a surrogate evolutionary algorithm», Auger, Anne; Schoenauer, Marc; Teytaud, Olivier, Auger A., Schoenauer M., Teytaud O., Auger A. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We prove a fast (better than superlinear) local convergence rate for an algorithm based on a quadratic approximation of the fitness function. An almost sure global convergence rate is proved for a corresponding memetic algorithm. Anglais (2005) (2005) non spécifiée ACM Press Proceedings of the 2005 conference on Genetic and evolutionary computation 857-864 GECCO - genetic and evolutionary computation conference Washington (2005) (2005) Communications avec acte 1 (2005)

  36. inria-00000545, version 1 MATH:MATH_OC «Convergence proofs, convergence rates and stopping criterions for multi-modal or multi-objective evolutionary algorithms», Bonnemay, Yann; Sebag, Michele; Teytaud, Olivier, Bonnemay Y., Sebag M., Teytaud O., Bonnemay Y. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We provide - convergence proofs - convergence rates - a stopping criterion for multi-objective or multi-modal evolutionary algorithms. Anglais (2005) (2005) internationale 12 pages Evolution artificielle Lille France (2005) (2005) Communications avec acte 1 (2005)

  37. inria-00000546, version 2 MATH:MATH_OC «Apprentissage statistique et programmation génétique: la croissance du code est-elle inévitable ?», Gelly, Sylvain; Teytaud, Olivier; Bredeche, Nicolas; Schoenauer, Marc, Gelly S., Teytaud O., Bredeche N., Schoenauer M., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Universal Consistency, the convergence to the minimum possible error rate in learning through genetic programming (GP), and Code bloat, the excessive increase of code size, are important issues in GP. This paper proposes a theoretical analysis of universal consistency and code bloat in the framework of symbolic regression in GP, from the viewpoint of Statistical Learning Theory, a well grounded mathematical toolbox for Machine Learning. Two kinds of bloat must be distinguished in that context, depending whether the target function has finite description length or not. Then, the Vapnik-Chervonenkis dimension of programs is computed, and we prove that a parsimonious fitness ensures Universal Consistency (i.e. the fact that the solution minimizing the empirical error does converge to the best possible error when the number of examples goes to infinity). However, it is proved that the standard method consisting in choosing a maximal program size depending on the number of examples might still result in programs of infinitely increasing size with their accuracy; a fitness biased by parsimony pressure is proposed. This fitness avoids unnecessary bloat while nevertheless preserving the Universal Consistency. Anglais (2005) (2005) non spécifiée 16 pages Conférence d'apprentissage Nice France (2005) (2005) Communications avec acte 1 (2005)

  38. inria-00000541, version 1 INFO:INFO_LG «Bayesian networks : a better than frequentist approach for parametrization, and a more accurate structural complexity measure than the number of parameters», Gelly, Sylvain; Teytaud, Olivier, Gelly S., Teytaud O., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We propose and justify a better-than-frequentist approach for bayesian network parametrization, and propose a structural entropy term that more precisely quantifies the complexity of a BN than the number of parameters. Algorithms for BN learning are deduced. Anglais (2005) (2005) non spécifiée 16 pages CAP Nice (2005) (2005) Communications avec acte 1 (2005)

  39. inria-00000217, version 1 MATH:MATH_OC «Taylor-based pseudo-metrics for random process fitting in dynamic programming.», Gelly, Sylvain; Mary, Jérémie; Teytaud, Olivier, Gelly S., Mary J., Teytaud O., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Stochastic optimization is the research of $x$ optimizing $E\ C(x,A)$, the expectation of $C(x,A)$, wher e $A$ is a random variable. Typically $C(x,a)$ is the cost related to a strategy $x$ which faces the reali zation $a$ of the random process. Many stochastic optimization problems deal with multiple time steps, leading to computationally difficu lt problems ; efficient solutions exist, for example through Bellman's optimality principle, but only provided that the random process is represented by a well structured process, typically an inhomogeneous Markovian process (hopefully with a finite number of states) or a scenario tree. The problem is that in the general case, $A$ is far from b eing Markovian. So, we look for $A'$, "looking like $A$", but belonging to a given family $\A'$ which do es not at all contain $A$. The problem is the numerical evaluation of "$A'$ looks like $A$". A classical method is the use of the Kantorovitch-Rubinstein distance or other transportation metrics \c ite{Pflug}, justified by straightforward bounds on the deviation $|E C(x,A)-E C(x,A')|$ through the use of the Kantorovitch-Rubinstein distance and uniform lipschitz conditions. These approaches might be bett er than the use of high-level statistics \cite{Keefer}. We propose other (pseudo-)distances, based upon refined inequalities, guaranteeing a good choice of $A'$. Moreover, as in many cases, we indeed prefer t he optimization with risk management, e.g. optimization of $EC(x,noise(A))$ where $noise(.)$ is a random noise modelizing the lack of knowledge on the precise random variables, we propose distances which can deal with a user-defined noise. Tests on artificial data sets with realistic loss functions show the rel evance of the method. Anglais (2005) (2005) non spécifiée 16 pages PDMIA Lille (2005) (2005) Communications avec acte 1 (2005)

  40. inria-00000549, version 1 INFO:INFO_LG «A Statistical Learning Theory Approach of Bloat», Teytaud, Olivier; Gelly, Sylvain; Bredeche, Nicolas; Schoenauer, Marc, Teytaud O., Gelly S., Bredeche N., Schoenauer M., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Code bloat, the excessive increase of code size, is an important is- sue in Genetic Programming (GP). This paper proposes a theoreti- cal analysis of code bloat in the framework of symbolic regression in GP, from the viewpoint of Statistical Learning Theory, a well grounded mathematical toolbox for Machine Learning. Two kinds of bloat must be distinguished in that context, depending whether the target function lies in the search space or not. Then, important mathematical results are proved using classical results from Sta- tistical Learning. Namely, the Vapnik-Cervonenkis dimension of programs is computed, and further results from Statistical Learn- ing allow to prove that a parsimonious fitness ensures Universal Consistency (the solution minimizing the empirical error does con- verge to the best possible error when the number of samples goes to infinity). However, it is proved that the standard method consisting in choosing a maximal program size depending on the number of samples might still result in programs of infinitely increasing size whith their accuracy; a more complicated modification of the fit- ness is proposed that theoretically avoids unnecessary bloat while nevertheless preserving the Universal Consistency. Anglais (2005-06-25) (2005) non spécifiée Genetic and Evolutionary Computation Conference 2005 (p427-428) Genetic and Evolutionary Computation Conference Washington D.C. USA (2005-06-25) (2005) Communications avec acte 1 (2005)

  41. inria-00000544, version 1 MATH:MATH_OC «Quasi-random mutations for evolution strategies», Teytaud, Olivier; Jebalia, Mohamed; Auger, Anne, Teytaud O., Jebalia M., Auger A., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI We prove linear convergence rates for some derandomized evolution strategie. Anglais (2005) (2005) internationale Springer (Artificial Evolution) 12 pages Evolution Artificielle Lille France (2005) (2005) Communications avec acte 1 (2005)

  42. hal-00185210, version 1 INFO:INFO_TI «Multigrid Convergence and Surface Area Estimation», Coeurjolly, David; Flin, Frédéric; Teytaud, Olivier; Tougne, Laure, Coeurjolly D., Flin F., Teytaud O., Tougne L., Coeurjolly D. et al, Laboratoire d'InfoRmatique en Images et Systèmes d'Information - LIRIS - CNRS : UMR5205 - Université Claude Bernard - Lyon I - Université Lumière - Lyon II - Institut National des Sciences Appliquées de Lyon - Ecole Centrale de Lyon - Météo-France - METEO-FRANCE - Météo France - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI Anglais (2003) (2003) internationale Springer Verlag 2616 101--119 Theoretical Foundations of Computer Vision "Geometry, Morphology, and Computational Imaging" Dagsthul Allemagne (2003) (2003) LNCS 2003 Communications avec acte 0 (2003)

  43. hal-00185220, version 1 INFO:INFO_TI «Segmentation and Length Estimation of 3D Discrete Curves», Coeurjolly, David; Debled-Rennesson, Isabelle; Teytaud, Olivier, Coeurjolly D., Debled-Rennesson I., Teytaud O., Coeurjolly D. et al, Laboratoire d'InfoRmatique en Images et Systèmes d'Information - LIRIS - CNRS : UMR5205 - Université Claude Bernard - Lyon I - Université Lumière - Lyon II - Institut National des Sciences Appliquées de Lyon - Ecole Centrale de Lyon - ADAGE - INRIA Lorraine - LORIA - INRIA - CNRS : UMR7503 - Université Henri Poincaré - Nancy I - Université Nancy II - Institut National Polytechnique de Lorraine - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI Anglais (2001) (2001) internationale Springer Berlin / Heidelberg 2243 295--313 Digital and Image Geometry: Advanced Lectures Dagsthul Allemagne (2001) (2001) G. Bertrand, A. Imiya, R. Klette Lecture Notes in Computer Science Communications avec acte 0 (2001)

  44. inria-00100500, version 1 INFO:INFO_OH «Segmentation and Length Estimation of 3D Discrete Curves», Coeurjolly, David; Debled-Rennesson, Isabelle; Teytaud, Olivier, Coeurjolly D., Debled-Rennesson I., Teytaud O., Coeurjolly D. et al, ADAGE - INRIA Lorraine - LORIA - INRIA - CNRS : UMR7503 - Université Henri Poincaré - Nancy I - Université Nancy II - Institut National Polytechnique de Lorraine We propose in this paper an arithmetical definition of 3-D discrete lines as well as an efficient construction algorithm. From this notion, an algorithm of 3-D discrete lines segmentation has been developed. It is then used to calculate the length of a discrete curve. A proof of the multigrid convergence of length estimators is presented. Anglais (2001) (2001) internationale Springer 2243 299-317 Digital and Image Geometry Schloss Dagstuhl, Germany (2001) (2001) G. Bertrand, A. Imiya and R. Klette Lecture notes in Computer Science 3d discrete line; segmentation; lengthestimation; discrete curve || 3droites discrètes 3d; segmentation; estimation de longueur; courbe discrète Colloque avec actes et comité de lecture. internationale. A01-R-155 || coeurjolly01a Communications avec acte 0 (2001)

Communications sans acte
  1. hal-00113368, version 1 SCCO:COMP «Quasi-Random resamplings, with applications to rule-samplng, cross-validation and (su-)bagging», Teytaud, Olivier; Gelly, Sylvain; Lallich, Stéphane; Prudhomme, Elie, Teytaud O., Gelly S., Lallich S., Prudhomme E., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Equipe de Recherche en Ingénierie des Connaissances - ERIC - Université Lumière - Lyon II : EA3083 Resampling (typically, but not necessarily, bootstrapping) is a well-known stochastic technique for improving estimates in particular for small samples. It is known very efficient in many cases. Its drawback is that resampling leads to a compromise computational cost / stability through the number of resamplings. The computational cost is due to the study of multiple randomly drawn resam- ples. Intuitively, we want some more properly distributed resamples to improve the stability of resampling-based algorithms. Quasi-random numbers are a well- known technique for improving the convergence rate of data-based estimates. We here consider quasi-random version of resamplings. We apply this technique to BSFD, a data-mining algorithm for simultaneous-hypothesis-testing, to cross- validation, and to (su-)bagging, an ensemble method for learning. We present quasi-random numbers in section 2. We present bootstrap and a quasi-random version of bootstrap-sampling in section 3. We present experimental results in section 4. Anglais (2006) (2006) International Workshop on Intelligent Information Acces --- IIIA 2006 France (2006) (2006) Quasi-Random ; Resampling ; Cross-Validation ; Bagging ; Subagging Communications sans acte 1 (2006)

  2. hal-00113362, version 1 INFO:INFO_NA;SCCO:COMP «How entropy-theorems can show that approximating high-dim Pareto-fronts is too hard», Teytaud, Olivier, Teytaud O., Teytaud O., TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI It is empirically established that multiobjective evolutionary algorithms do not scale well with the number of conflicting objectives. We here show that the convergence rate of any comparison-based multi-objective algorithm, for the Hausdorff distance, is not much better than the convergence rate of the random search, unless the number of objectives is very moderate, in a framework in which the stronger assumption is that the objectives have conflicts. Our conclusions are (i) the relevance of the number of conflicting objectives (ii) the relevance of random-search-based criterions (iii) the very-hardness of more than 3- objectives optimization (iv) some hints about new cross-over operators. Anglais (2006) (2006) Bridging the Gap between Theory and Practice - Workshop PPSN-BTP Reykjavik Islande (2006) (2006) Multi-Objective Optimization; Evolutionary Computation ; Theory Communications sans acte 1 (2006)

Ouvrages scientifiques
  1. inria-00173250, version 1 MATH:MATH_GM «Mathématiques pour l'agrégation», Teytaud, Olivier; Antonini, Christophe; Borgnat, Pierre; Chateau, Annie; Lebeau, Edouard, Teytaud O., Antonini C., Borgnat P., Chateau A., Lebeau E., Teytaud O. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Lycée Stanislas - Lycée Stanislas, Cannes - Laboratoire de Physique de l'ENS Lyon - Phys-ENS - CNRS : UMR5672 - École normale supérieure de Lyon - ENS Lyon - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM - CNRS : UMR5506 - Université Montpellier II - Sciences et Techniques du Languedoc - lycée henri poincaré - Lycée Henri Poincaré, Nancy Maths pour l'agreg. Français (2007) (2007) Dunod 736 () Mathématiques; agrégation Ouvrages scientifiques 0 (2007)

Chapitres d'ouvrages scientifiques
  1. hal-00105953, version 1 INFO:INFO_AI;MATH:MATH_ST «Estimation et contrôle des performances en généralisation des réseaux de neurones», Guermeur, Yann; Teytaud, Olivier, Guermeur Y., Teytaud O., Guermeur Y. et al, MODBIO - INRIA Lorraine - LORIA - INRIA - CNRS : UMR7503 - Université Henri Poincaré - Nancy I - Université Nancy II - Institut National Polytechnique de Lorraine - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI Introduction à la théorie statistique de l'apprentissage. Français (2006) (2006) Hermès 283 () Younes Bennani collection I2C Apprentissage Connexioniste, consistance du processus d'apprentissage, vitesse de convergence du risque empirique, mesures de capacité, résultats asymptotiques 63 pages Chapitres d'ouvrages scientifiques 1 (2006)

  2. hal-00113594, version 1 SCCO:COMP «Association rule interestingness: measure and statistical validation», Lallich, Stéphane; Teytaud, Olivier; Prudhomme, Elie, Lallich S., Teytaud O., Prudhomme E., Lallich S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Equipe de Recherche en Ingénierie des Connaissances - ERIC - Université Lumière - Lyon II : EA3083 The search for interesting Boolean association rules is an important topic in knowledge discovery in databases. The set of admissible rules for the selected support and condence thresholds can easily be extracted by algorithms based on support and condence, such as Apriori. However, they may produce a large number of rules, many of them are uninteresting. One has to resolve a two-tier problem: choosing the measures best suited to the problem at hand, then validating the interesting rules against the selected measures. First, the usual measures suggested in the literature will be reviewed and criteria to appreciate the qualities of these measures will be proposed. Statistical validation of the most interesting rules requests performing a large number of tests. Thus, controlling for false discoveries (type I errors) is of prime importance. An original bootstrap-based validation method is proposed which controls, for a given level, the number of false discoveries. The interest of this method for the selection of interesting association rules will be illustrated by several examples. Anglais (2006) (2006) Springer 25 () Guillet, Hamilton Quality measures in data mining, association rules; interestingness measure Chapitres d'ouvrages scientifiques 1 (2006)

Rapports
  1. inria-00117266, version 3 INFO:INFO_AI;INFO:INFO_LG «Modification of UCT with Patterns in Monte-Carlo Go», Gelly, Sylvain; Wang, Yizao; Munos, Rémi; Teytaud, Olivier, Gelly S., Wang Y., Munos R., Teytaud O., Gelly S. et al, TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI - Centre de Mathématiques Appliquées - CMAP - CNRS : UMR7641 - Université de Versailles-Saint Quentin en Yvelines - Polytechnique - X - SEQUEL - INRIA Futurs - INRIA - CNRS : UMR8022 - CNRS : UMR8146 - Université des Sciences et Technologies de Lille - Lille I - Université Charles de Gaulle - Lille III - Ecole Centrale de Lille Algorithm UCB1 for multi-armed bandit problem has already been extended to Algorithm UCT (Upper bound Confidence for Tree) which works for minimax tree search. We have developed a Monte-Carlo Go program, MoGo, which is the first computer Go program using UCT. We explain our modification of UCT for Go application and also the intelligent random simulation with patterns which has improved significantly the performance of MoGo. UCT combined with pruning techniques for large Go board is discussed, as well as parallelization of UCT. MoGo is now a top level Go program on $9\times9$ and $13\times13$ Go boards. Anglais (2006) (2006) () Rapport de recherche RR-6062 Rapports 1 (2006)

Documents sans référence de publication
  1. hal-00113668, version 1 INFO:INFO_LG;INFO:INFO_AI «Multi-armed Bandit, Dynamic Environments and Meta-Bandits», Hartland, Cédric; Gelly, Sylvain; Baskiotis, Nicolas; Teytaud, Olivier; Sebag, Michele, Hartland C., Gelly S., Baskiotis N., Teytaud O., Sebag M., Hartland C. et al, Laboratoire de Recherche en Informatique - LRI - CNRS : UMR8623 - Université Paris Sud - Paris XI - TAO - INRIA Futurs - INRIA - CNRS : UMR8623 - Université Paris Sud - Paris XI This paper presents the Adapt-EvE algorithm, extending the UCBT online learning algorithm (Auer et al. 2002) to abruptly changing environments. Adapt-EvE features an adaptive change-point detection test based on Page-Hinkley statistics, and two alternative xtra-exploration procedures respectively based on smooth-restart and Meta-Bandits. Anglais () () multi-armed bandit, statistical learning, ucb Documents sans référence de publication 1 (2006)