Overblog Suivre ce blog
Administration Créer mon blog
12 septembre 2009 6 12 /09 /septembre /2009 11:43

Vous avez un master d'informatique ou une thèse d'informatique ?
on embauche à Paris-Sud!

Les techniques de fouille d'arbre Monte-Carlo ont révolutionné le contrôle en temps discret en grande dimension. Participez à cette révolution et venez travailler chez nous!

Contact: olivier.teytaud@inria.fr

  • Si vous avez un master, venez en thèse (3 ans) pour innover en informatique et protéger l'environnement
    • Compétences requises:
      • Bonnes capacités au travail en équipe et à la communication (plusieurs équipes sont à l'oeuvre sur des ces sujets et il faut pouvoir interagir avec tout le monde);
      • Solides compétences de programmation
      • Des compétences en mathématiques appliquée ou en statistiques sont un gros plus.
      • Candidat très énergique requis; le candidat devra collaborer sur plusieurs applications (mais aura de l'aide sur chacun des développements, d'autres personnes étant financées sur chacune des tâches).
      • Les voyages à Taiwan sont obligatoires, le candidat doit donc ne pas avoir peur de passer 4 mois puis 8 mois à Taiwan (12 mois en tout).
    • Sujet:
    • Géographiquement:
      • Un tiers à Orsay (RER B arrêt Orsay Ville, http://tao.lri.fr)
      • Un tiers à Artelys (www.artelys.com)
      • Un tiers à Taiwan (deux voyages de 4 et 8 mois; logement et avion payés).

  • Si vous avez une thèse, venez en post-doc

    • Sujet: très libre, autour du thème des bandits.
    • Compétences requises: plusieurs profils envisageables:
    • Géographiquement: RER B, arrêt Orsay-Ville, Université Paris-Sud (http://tao.lri.fr)
Repost 0
Published by teytaud - dans Recherche
commenter cet article
5 septembre 2009 6 05 /09 /septembre /2009 12:25

A revolution in planning originated in MCTS algorithms. Below an introduction and a survey (oriented to popularization).

Introduction (video / slides) in french: http://www-c.inria.fr/Internet/rendez-vous/modele-et-algo/prise-de-decision-sequentielle-dans-l-incertain-application-au-jeu-de-go

Slides in english: www.lri.fr/~teytaud/nicta.pdf

MCTS/UCT are algorithms for taking decisions in uncertain environments. The principles are:
- iteratively growing tree;
- random simulations.

Algorithmically, in the case of Go (you can generalize easily to other problems):

  • a. First, you have in memory a tree with only one node, which is the current state of the Goban.

Example of UCT tree: each node "knows" its number of simulations and its number of wins. Thanks to David Silver, original author of this figure I guess.

  • b. Then, start at the root, and find a path until a leaf; for each node, you choose the son which has highest exploration/exploitation value: the exploration/exploitation value is typically the sum of

    • the exploitation term: the percentage of won simulations from this son.

    • the exploration term: the square root of the ratio log(nb simulations of the parent) / (nb of simulations of this son)

  • c. Then, randomly play from the leaf until the game is over.

  • d. Then, update the statistics in the tree: update the number of simulations in each node, and the number of wins for black/white.

  • e. If there is time left for thinking, go back to b.

  • f. Play the most simulated move from the root.

    (this is UCT, the clearest version of MCTS; there are plenty of variations)

    1. Main tricks in MCTS / UCT

    MCTS and UCT refer to the same family of algorithms. The main initial publications are
    Kocsis et al (ECML 06), Coulom 06, Chaslot et al 06.

    A strong improvement in the Monte-Carlo part, showing in particular that the Monte-Carlo should not "only" play well but also keep diversity, is "fill board"; http://hal.inria.fr/inria-00117266

    There are several works around the parallelization; Cazenave, Chaslot et al,, Gelly et al http://hal.inria.fr/inria-00287867/en/.

    For the case of Go, but probably with more importance than just Go, the importance of preserving diversity has been emphasized in a post on the computer-Go mailing-list for the case of Nakade;
Example of Nakade, given by D. Feldmann.

a solution has been published in http://www.lri.fr/~teytaud/eg.pdf, and a more general diversity preservation mecanism (termed "fillboard") was also proposed with nice results in 19x19 Go (same paper).

Some Meta-level MCTS was proposed, with more or less good results; this was for example used for designing an opening book, better than no opening book at all, but less efficient than handcrafted opening books in spite of years of computational power.

Please notice that in spite of the optimism of an IEEE spectrum publication, classical techniques like alpha-beta did not succeed for the game of Go ("cracking go", 2007).

2. Links between MCTS and other existing algorithms

A* is a famous algorithm for e.g. shortest path. The idea consists in developing a tree of possible futures; the algorithm iteratively expands the non-expanded node with maximum "score", where the score is an estimate of the distance to the optimum.

Dijkstra algorithm (related to A*), from combinatorica.com

The usual theoretical analysis of A* shows that it is "optimal" when the score is optimistic: it should (in a minimization problem) be a lower bound of the real value of the situation.

Optimism, a general view on MCTS/UCT, is exactly this. The interesting paper [Hren and Munos 08] http://www.springerlink.com/content/mu7227g225512347/ shows theoretical properties of "optimism" in the case of a proved bound.

UCT also iteratively expands the node with highest score. Usually, the score is computed also for already expanded nodes, but this is, I think, only for commodity of development.

Remark: A* has the notion of closed set, which is not used in usual MCTS implementations, whereas it makes sense. However, this is done in [De Mesmay et al 09] http://www.lri.fr/~rimmel/publi/TAG.pdf is an example in which there is an equivalent of "closed set".

3. Early publications related to MCTS/UCT

I like the reference Peret Garcia ECAI03, which was the first one in which I saw (out of games) the idea of locally developping a tree for the situation at which a decision should be taken. This idea might be considered as trivial for people working in games; it is not in areas in which the standart is Bellman's dynamic programming and variants.

I also like papers which try to have some learning from some branches to other branches, typically by evolutionary-like algorithms:
Fogel DB, Hays TJ, Hahn SL, and Quon J (2004) “A Self-Learning Evolutionary Chess Program,” Proceedings of the IEEE, Vol. 92:12, pp. 1947-1954.
An example of problem solved by the technique in Drake et al.

and Drake et al http://webdisk.lclark.edu/drake/publications/drake-gem2008-final.pdf

whenever for the moment these techniques do not work in the case of the game of Go.

The first ever win of a computer over a professional player in 19x19 (handicap 9, performed by MoGo against Kim Myungwan 8p in Portland 2008)

4. Results in computer-Go: computers vs humans

In 9x9 Go:
2007:win against a pro(5p)9x9(blitz) MoGo (Amsterdam)
2008:win against a pro(5p)9x9 MoGo (Paris)
2009:win against a pro(5p)9x9 as black MoGo (Rennes)
2009: win against a top pro (9p) 9x9 Fuego as white (Korea)
2009: win against a top pro (9p) 9x9 MoGoTW as black (Taipei)   (disadvantageous side!)
In 19x19 Go:
1998: ManyFaces looses with 29 stones against M. Mueller!
2008:win against a pro(8p)19x19,H9 MoGo (Portland)
2008:win against a pro(4p)19x19,H8 CrazyStone (Tokyo)
2008:win against a pro(4p)19x19,H7 CrazyStone (Tokyo)
2009:win against a pro(9p)19x19,H7 MoGo (Tainan), reproduced by Pachi in 2011 (IEEE SSCI)
2009:win against a pro(1p)19x19,H6 MoGo (Tainan)

Motoki Noguchi, the LLAIC organizers and a Go club of Clermont-Ferrand; mogo played 4 games against Motoki Noguchi (7D in France, professional level). MoGo won 2 games, but in one of them Motoki made a big mistake showing that he was perhaps not so concentrated at the end of the last game :-)
Repost 0
Published by teytaud - dans Recherche
commenter cet article
26 août 2009 3 26 /08 /août /2009 15:20
IEEE Fuzz is a very applied conference, with acceptance of almost all submitted papers, and nonetheless highly ranked in the Core ranking of journals and conferences. I will not comment on these facts, and on whether hhighly applied research conferences are a good idea or not; I will just below give a very brief idea of which domains were present at IEEE Fuzz.

All comments welcome - also comments by people far from computer-science as I'd like to know if non-scientists agree with the application fields chosen by people in computer-science.

The following applications were presented:

1. Medical early diagnos; definitely I'd like to work on things around that; let's cite in Fuzz:
   a. early detection of hand osteoarthritis

   b. Recognition of respiration patterns (application to respiration troubles
        while sleeping)
   c. Detection of dementia through respiration patterns (I find that amazing that one  
         can detect dementia just from respiration patterns!).
   d. Analysis of lesions of thorax
   e. Detection of elders' activity (for detecting health troubles from the behaviour - as
       for sismic troubles, Japan is highly concerned by this)

2. Biometry.
   a. Recogniition of agressive actions (a best paper award for this).

   b. Recognition of people from the pressure pattern of theirs steps
   c. Fingerprint classification

   d. Management of google-like requests

3. Automatic management of machines / clustes / grids
  a. Vulnerability detection in Linux kernels
  b. Automatic allocation & migration of jobs or grids (is someone aware of something which works, and
       not only experimentally in highly controlled conditions, in terms of jobs migrating on a
      heterogeneous grids ? I've only seen that in very easy contexts).

4.Applications to cars

   a. Detection of free parking spaces
   b. Network for real-time informations on the traffic

5. Computer-Go.
The session "computer-Go" was big. Many people attended, and not only people working on it - there is (hopefully :-) ) the idea that the strong recent changes in computer-Go have a deep impact on general artificial intelligence.

6. Other applications:
    a. seismic response control of a civil structure; of crouse, "Fuzz" is an important domain in
       Japan which is highly concerned with seismic troubles.
    b. Automatic music generation from examples

    c. Music rights protection systems
Repost 0
Published by teytaud - dans Recherche
commenter cet article
6 juillet 2009 1 06 /07 /juillet /2009 10:18

Cet article discute les méthodes de financements de travaux joints entre académie et industrie.
Il s'agit donc de discuter exclusivement de travaux:
  • ayant un lien avec l'industrie;
  • trop gros pour être financés sans demande spécifique de fond (ou impliquant des signatures que l'on ne peut fournir directement en tant que simples chercheurs).
Il s'agit ici d'exposer un point de vue, possiblement très lacunaire. Avec le sentiment qu'il y a un problème de fond sur ce sujet dans le monde de la recherche, j'essaie de faire avancer le débat en faisant une synthèse en tâchant de n'être ni trop dans le détail ni trop simpliste.
Les méthodes principales sont:
  • Thèses cofinancées: BDI, St2i, Cifre,etc: pour l'essentiel,se mettre d'accord avec une entreprise, et avoir l'accord d'organismes publics. On obtient par cette voie le financement d'un doctorant.
  • Financements ANR, RNTL, etc: on remplit un dossier, qui est évalué par des experts, et possiblement on reçoit les fonds. On reçoit par cette voie le financement d'un doctorant ou d'un post-doc, et de l'argent pour des frais liés au travail prévu.

Défauts du système.

  • Temps de réaction extrêmement long. Il faut attendre l'appel adéquat, puis attendre le résultat d'évaluation.
  • Très grosse lourdeur administrative. Enparticulier, les chercheurs / enseignants-chercheurs sont supposés gérer les aspects administratifs, ce pour quoi ils ne sont pas formés et surtout ce pour quoi les compétences spécifiques à leurs métiers sont inutiles. Le système américain, ainsi que le système finlandais, est nettement meilleur à ce niveau là, semble-t-il. L'inria, dans ses centres de recherche, apporte un net mieux semble-t-il.
  • Experts souvent peu motivés et peu concernés. On a tous vu à quel point l'ANR manquait d'experts; le conflit récent n'a rien arrangé (à titre individuel  je refuse systématiquement d'être expert ANR désormais). La pression bibliométrique n'arrange rien non plus: le fait de faire des évaluations est entièrement bénévole et hors toute évaluation. En augmentant la pression bibliométrique, on décourage les bonnes volontés sur les expertises ANR.
  • Etrange passage de l'argent.. Le système fournit, lors d'une thèse Cifre, une importante somme à l'entreprise via le CIR; cette somme est importante car elle est égale à A = B+C, une partie C étant supposée être reversée au laboratoire public. L'entreprise est financée car elle est supposée fournir, via la thèse Cifre, une part de recherche utile à toute la collectivité, sous forme de publications notamment.Néanmoins, si le laboratoire est évalué sur ses résultats de recherche, ce n'est pas le cas du tout l'entreprise: par conséquent, l'entreprise a tout intérêt à négocier une répartition où B est très élevé, et, une fois l'argent reçu, n'absolument pas se consacrer aux actvitiés de recherche et encore moins à la diffusion des travaux subventionnés.
  • Complications de recrutement: quand un financement est dédié (partiellement ou pleinement) à un recrutement, les contraintes adminsitratives, de délai, d'âge du candidat, de borne inférieure et/ou supérieure sur la qualification du candidat font qu'il est très difficile de trouver qqn. Souvent le recrutement se fait par défaut, sous la contrainte, personne ne voulant subir une deuxième fois le long protocole administratif. Ce système favorise le recrutement d'individus maladéquats, au détriment de bons éléments mal adaptés aux "cases" administratives ou aux dates imposés par les contraintes administratives.
  • Fonds propres et système allégé pour projets légers.
  • Financement Cifre basé sur un versement de la somme B à l'entreprise et C au laboratoire.
  • Pas de délai serré et moins de contrainte administrative sur les recrutements.
  • Charge administrative côté ANR, pas côté chercheurs (sinon on pénalise les labos à moins forte aide adminisrative).

Repost 0
Published by teytaud - dans Recherche
commenter cet article
5 juillet 2009 7 05 /07 /juillet /2009 16:51


Le jeu de Go est devenu un challenge classique en intelligence artificielle,
par sa grande dimension et sa complexité. En particulier, les humains restent
considérablement meilleurs que les ordinateurs. Néanmoins, l'écart s'est
considérablement réduit ces dernières années grâce à des techniques nouvelles
et généralistes, i.e. utilisables de manière générique pour des problèmes de
décision séquentielle dans l'incertain: tout l'intérêt de cette recherche est dans le fait
que la technique est applicable à une grande gamme de problèmes:
Fouille d'arbres Monte-Carlo.


On présentera l'algorithme, appelé "Monte-Carlo Tree Search" (ou "Upper
Confidence Trees" pour l'une de ses variantes), ses différences et ses
ressemblances avec les algorithmes usuels, et ses forces et faiblesses, très
apparentes sur le jeu de Go, ainsi que diverses applications loin des jeux.

Les bandits et le Go.
On présentera enfin un survol des formules dites de "bandit", abondamment
utilisées comme brique de base dans le Monte-Carlo Tree Search.



Ci-dessous à droite la première victoire contre un humain professionnel en jeu de Go 19x19, à 9 pierres de handicap:

  • Jean-Yves Audibert
  • Pierre Audouard
  • Vincent Berthier
  • Guillaume Chaslot
  • Christophe Fiter
  • Sylvain Gelly
  • Jean-Baptiste Hoock
  • Rémi Munos
  • Motoki Noguchi
  • Arpad Rimmel
  • Olivier Teytaud
  • Yizao Wang
  • Un grand merci au séminaire "Le modèle et l'algorithme" de Rocquencourt
  • Pardon pour les oublis probables!
Repost 0
Published by teytaud - dans Recherche
commenter cet article
5 juillet 2009 7 05 /07 /juillet /2009 16:11

Objectif: en apprentissage artificiel, traiter de grandes bases de données.

       Données: des couples entrée x sortie.
       Sorties: une fonction qui devine les sorties à partir des entrées
       Cadre: beaucoup de données.
  • imaginez un petit robot à qui vous montrez plein d'exemples d'ours et plein d'exemples d'éléphants, et qui doit apprendre à différencier les ours des éléphants.
  • imaginez un détecteur qui doit apprendre à faire la différence entre l'écho sonar d'une mine et l'écho sonar d'un rocher.
  • imaginez un détecteur qui en fonction d'indicateurs de votre chaine de production industrielle doit vous prédire la localisation d'une panne

Rapide survol de quelques techniques pour effectuer un apprentissage supervisé d'un grand jeu de données. Attention, fortement influencé par mon cadre applicatif préféré: grand nombre de points, mais dimension modérée. (difficile d'accès pour grand public - version encore à travailler, tout conseil bienvenu)  

1. Première approche: prendre un algo genre SVM gaussiennes et le rendre le plus efficace possible sur grandes bases, notamment à coups de parallélisme.

  • La parallel Mixture of SVMs: malheureusement speed-up modéré malgré des grands nombres de processeurs. 
  • La Cascade SVM: là aussi, amélioration modérée sauf si le nombre de support vectors est faible devant le volume du problème (cas assez rare pour des prévisions numériques, i.e. régression) 
Autres exemples pas encore assez étudiés pour que j'ai un avis: différents papiers sur l'amélioration des SVM gaussiennes ==> Core Support Vector Machines (semble avoir une généralité modérée mais il faudra que j'étude ça plus avant), "a gentle hessian for efficient gradient descent" que j'ai pas étudié assez aussi.

Conclusion (temporaire) à mon avis: des améliorations modérés;
il y a au moins un truc où le parallélisme apporte beaucoup, c'est le choix d'hyperparamètres "Weka-parallel: machine learning in parallel" ==> on parallélise la recherche d'hyperparamètres par cross-validation. Il y a aussi les méthodes "généralistes" de parallélisation, auxquelles je reviens plus bas.

2. Prendre un algo qui passe bien à l'échelle

...plutôt que d'optimiser à fond un algo qui passe mal.  Typiquement, se dire que les SVM linéaires c'est drôlement plus rapides et que ça compense le fait que c'est pas terrible asymptotiquement. Un arbre de décision, surtout en classification, peut aussi faire l'affaire, d'autant plus qu'il peut se randomiser commodémment et ainsi être parallélisé / mixé à du bagging ou subagging. L'article "Comments on << A parallel mixture of SVMs for large scale problems>>" signale en particulier que la "parallel mixture of SVMs" marche en fait beaucoup moins bien qu'une randomisation de C4.5 (moyenner plusieurs runs de C4.5 avec randomisation).


 Semble pas mal si dimension suffisamment grande pour que linéaire soit bon. Pour éviter le purement linéaire: des gens se sont mis à faire des reformulations non-linéaires rapides: random kitchen sinks (RKS; dans l'esprit des "reservoir methods" d'ailleurs), On est très loin des SVMs au bout du compte: la constante C des SVM devient sans impact pour la régression (on prend C=infini), et ça revient à faire du simple "linear least squares" sur des données transformées non-linéairement.

Conclusion: ça a l'air intéressant comme approche et très simple Cf l'article Rahimi et Recht: Weighted sums of Random Kitchen Sinks: Replacing minimization with randomization in Learning; aussi, sur leur page web, on trouve un codage en quelques lignes de matlab ou octave des RKS.

Autre idée, prendre les bons vieux réseaux de neurones à backprop, qui ont l'avantage de bigrement bien passer à l'échelle et de permettre facilement tant régression que classification

3. Paralléliser de manière externe 

(ci-dessus un des clusters de la formidable grille Grid5000)

Il s'agit de paralléliser sans toucher le fonctionnement interne de l'algorithme. Ca peut être avec les approches précédentes d'ailleurs. Quelques grandes catégories d'approches:

  • Bagging: forcément très parallèle tant que le nombre de procs est plus petit que le nombre de bootstraps. 
  • Approche tentante: le subagging, qui fait du bagging sur des petits morceaux de la base et non sur la base complète, et moyenne tout ça. Beaucoup plus parallèle que le bagging. 
  • Randomiser l'algorithme d'apprentissage (c'est finalement une généralisation de bagging/subagging et faire la moyenne des algos obtenus. En particulier, l'article " Comment on << A parallel Mixture of SVMs for Very Large Scale Problems >>" signale que randomiser C4.5 permet de faire beaucoup mieux que la parallel mixture of SVM citée plus haut et d'avoir un algo beaucoup plus parallèle (au total, sur l'appli du papier initial, ils vont beaucoup plus vite, sont largement plus efficace, et ont un programme beaucoup plus simple). 
  • random subspace: on prend pas les même feature pour les différents algos "Combining Bagging and Random Subspaces to Create Better Ensembles": random subspaces vraiment pas limités aux random forests ==> bon pour tout algo 
  • paralléliser la recherche d'hyperparamètres; on sent que c'est simple et efficace, cf "Weka-parallel: machine learning in parallel".
4. Conclusions (temporaires)
 (ces conclusions sont personnelles, instables car juste en début de projet):
  • subagging ça a l'air bien, simple, efficace, passant à l'échelle, sans trop de paramètres à régler;
  • parallélisation de recherche d'hyperparamètre aussi 
  • En cours: voir à quel point il est rentable de prendre un algo moins bien usuellement, mais qui s'avèrerait meilleur au niveau du passage à l'échelle, modulo quelques "random kitchen sinks" par exemple.
  • A tester urgemment: random subspace method (très lié aux RKS)
  • A tester urgemment: RKS à tester plus intensivement que je ne l'ai fait.
Repost 0
Published by teytaud - dans Recherche
commenter cet article