Overblog Suivre ce blog
Administration Créer mon blog
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.

koc.jpg
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;
koc2.jpg
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.

koc3.jpg
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.
drake.jpg
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.

koc4.jpg
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)

koc5.jpg
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
29 août 2009 6 29 /08 /août /2009 21:28

Une jeune narratrice moyennement sympathique (pour moi :-) ) raconte une courte période de temps où elle découvre la sexualité (majoritairement lesbienne), plus ou moins l'amour, et même le goût/sens des responsabilités. Elle fait aussi connaissance un peu mieux avec ses parents pour voir qu'ils sont plus remarquables qu'elle ne le croyait avant; et même que certains de ses amis qu'elle prend pour des gamins ne sont pas forcément plus gamins qu'elle tout le temps. Ca fait beaucoup, c'est l'adolescence en rythme accéléré; et pour compliquer les choses c'est dans une Inde qui change pas mal aussi. Les incohérences de la narratrice sont bien celles de l'adolescence;
je me suis même surpris à la trouver attachante comme une presqu'enfant même si elle a l'air casse-pieds comme une vraie ado.

Je vais commencer par le point qui m'a énervé, mais j'ai aimé ce livre. Ce qui m'irrite donc d'abord; quelle déception devant le retour régulier des analogies entre relations humaines et sciences dures. Certes, c'est tellement isolé dans le livre qu'on pourrait presque le découper pour faire une version 2 du livre, une version sans ça, pour enlever cette tâche. Ca donne l'impression d'avoir été rajouté a posteriori, et c'est une couche de trop; pas pertinente, pas intéressante. Oui, nous montrer le goût de la narratrice pour les sciences était intéressant; une chose de plus à acquérir à cet âge (enfin, pour certains :-) ), et c'est un élément quii collait bien avec la personnalité de la bête. Mais les analogies sont des fiascos, et laissent penser que l'auteur maitrise mal les sujets techniques qu'elle a voulu inclure. Pas d'élégance, pas de rigueur, rien de bien dans ces analogies; et elles reviennent régulièrement, donnant le sentiment d'une intention.

Bon j'arrête de ronchonner sur ce point de détail qui fait vérue, pour en venir à ce qui m'a plu. Ce roman, en plein dans les transitions, de l'adolescence mais aussi de l'Inde (intéressant sujet de la discrimination positive !), est une vraie réussite avec sa narratrice trop grande pour l'enfance et trop petite pour le monde adulte; aussi, une ado moderne mais psychologiquement si enracinée dans le système des castes.

Bon, je m'enthousiasme peut-être vite, j'ai très peu lu de livres sur l'adolescence; peut-être que les gens qui en ont lu des kilos vont trouver ça moins plaisant que moi :-)
Repost 0
Published by teytaud - dans Littérature
commenter cet article
26 août 2009 3 26 /08 /août /2009 15:23
Une saine lecture, accessible sans longue expérience de la vie, tout à fait recommandable à partir de 12 ans.

Jean Dutourd (D), de l'Académie Française, a écrit << L'âme sensible >>,
livre qui s'ouvre sur une jolie définition de l'âme par Alain:
"L'âme, c'est ce qui refuse le corps. Par exemple, ce qui refuse
de fuir quand le corps tremble, ce qui refuse de frapper quand le
corps s'irrite, ce qui refuse de boire quand le corps a soif, ce qui refuse
de prendre quand le corps désire, ce qui refuse d'abandonner quand le corps a
horreur. Ces refus sont des faits de l'homme. [...]"
Exercice pour les neurologues: en acceptant cette définition, localiser
l'âme dans le cerveau humain :-)



Cette définition sert de base pour glorifier l'esprit de contradiction, le goût à s'opposer; ceci sera le guide de lecture de D, pour s'attaquer à un texte de Mérimée (M) sur Stendhal (S). Les lignes qui suivent discutent donc en quelque sorte d'un livre où D parle de M qui parle de S.

D, qui n'aime pas tout le monde, incendie au passage Sautelet, Victor Cousin, un peu Mérimée aussi, André Rousseaux, Canova, André Gide, Alain Fournier, etc.

D écrit simple et direct; il aime S, et se positionne fréquemment dans la même
catégorie que S; l'Histoire et les histoires sont appelées à la rescousse
pour souligner les similitudes entre S et D.
D s'apprécie lui-même en appréciant S. Ce n'est après tout
pas le moindre des mérites du livre, car S, comme D, a connu de
grandes tranches d'Histoire et de belles histoires, qui pimentent adéquatement
l'ouvrage.

D dit n'écrire que pour quelques uns; le monde pour lui se répartit en beaucoup de
sots et quelques grandes âmes; affirmant notamment l'importance du courage physique
dont S et lui ont fait preuve. Ce n'est pas si fréquent, comme le dit D pour s'absoudre
de faire sa propre promotion, et c'est donc plaisant par rareté; par contre, le courage de faire la vaisselle, de
changer les couches, de gérer les enfants, de faire la lessive, n'est pas le sujet du livre.

On parle dans ce livre de gaieté dans les circonstaces les plus graves comme preuve et moyen de grandeur d'âme;
on parle de savoir-vivre dans les salons (les salons sont d'ailleurs défendus comme succédané de la guerre
pour voir le coeur des gens); c'est, sans ironie de ma part, beau comme tout, avec quelques belles et intéressantes
lignes au passage sur la gentillesse originalement définie.
Par contre on ne trouve pas dans l'ouvrage le courage et le savoir-vivre du quotidien ou de la persévérance, qui ne sont pourtant pas rien:

- aujourd'hui, alors que l'opportunisme l'emporte chez nos politiques, la persévérance et la dignité sur la durée ne sont pas rien, et on aurait aimé une idée de grandeur d'âme qui ne néglige pas cela;

- aussi, alors que l'on ne néglige plus totalement dans les devoirs d'un humain d'aujourdhui
la gestion du quotidien ou des enfants (pas comme à l'époque ancienne où ces tâches étaient totalement renvoyées à la moitié la moins bien défendue de l'humanité), d'autres formes de grandeur d'âme méritent a minima d'être évoquées;
mais enfin, D est de son époque et de son milieu et ses points de vue s'en ressentent; cela dit,
son livre est très joli dans son périmètre bien défini. Remarquez qu'avec la définition d'Alain
on peut tout à fait faire entrer aussi ces aspects dans la grandeur d'âme; mais le texte de D par contre
est ciblé sur une petite partie de ce qu'on peut couvrir avec cette définition.

On peut apprécier l'astucieuse construction autour de l'esprit de contradiction,
inspirée par la définition donnée par Alain, habile car permettant de dire tout et son contraire;
on s'abstiendra ici de relever les contradictions; il ne s'agit pas d'un ouvrage scientifique,
mais de façonner, par touches, une idée de l'âme, de la grandeur d'âme.

C'est beau, la grandeur d'âme, mais qui va mettre à sécher le
linge ? La grande âme change-t-elle des couches, passe-t-elle l'éponge, ou laisse-t-elle ça aux "domestiques" (terme
qui revient plusieurs fois, quand il s'agit de mépriser; on méprise au détour d'un paragraphe
aussi ceux "qui ne savent pas lire").

Merci D, S et M pour les belles lignes sur l'amour, où sont joliment délimitées ou agrégées l'idée Don Juan (pour
de faux) et l'idée du coeur sensible. Dans l'esprit général du livre, on verra l'idée très vieille France (très
répandue sous l'Empire selon M) selon laquelle une femme doit être prise d'assaut; j'aurais aimé voir l'avis
de D sur la question symétrique (un homme doit il être pris d'assaut ?) qui aurait eu le mérite d'être plus
originale. Mais enfin, on sent bien que c'est un peu révolutionnaire, comme question, pour un livre
qui prend ses racines quelque part sous Napoléon.

Peu de contradictions, en fait, des "grandes" traditions, quel que soit le domaine; c'est le charme de l'ouvrage, tout
d'une pièce; tout en conservatisme pour certaines choses; c'est son périmètre plus que sa limite tant il est vrai que sur ce
créneau bien défini, et dans la limite d'une certaine idée de la grandeur d'âme, il y avait à faire et c'est bien fait.
Un ouvrage donc où D se mouille peu; essentiellement d'accord avec la postérité concernant la critique littéraire ou musicale, à l'exception néanmoins de Tchaikovski (ou il corrige prudemment le tir dans une note postérieure à l'édition originale,
la longévité de D faisant qu'il a pu voir ce que décida la postérité finalement) et Gide (où D persiste, il faut dire
que Gide et D ne sont pas dans la même tendance). On n'envisagera pas d'autre monde que le notre avec "L'âme sensible",
juste un retour un arrière et de l'idéalisation de certains aspects;
on n'apprend rien des détails où est pourtant souvent le diable; on voit par contre ce que le 18ème siècle
a fait de beau dans le cadre qui était le sien; un cadre où pas mal de choses n'étaient pas envisageables.

Enfin, D décrit S dans sa vie à partir de S dans ses écrits, tout en disant (contradiction) pour s'opposer à Sainte-Beuve qu'il ne faut pas remonter à l'auteur à partir de l'oeuvre; peut-être est-il périlleux pour D de s'opposer, quant à l'homme S plutôt que l'écrain S, à M qui a le mérite d'avoir connu tant l'homme que l'oeuvre.

Ce livre est conforme à l'idée que je me fais d'un livre qui contient sur la couverture "de l'Académie Française";
les enfants pourront passer par ce livre de la tradition chevaleresque, souvent en vogue vers 7 ou 8 ans, à l'idée
"Les grandes âmes à la guerre", ou "Les grandes âmes dans les salons", ou encore "Les grandes âmes et l'amour". Ils n'iront pas jusqu'à "Les grandes âmes au bureau", "Les grandes âmes avec leurs enfants", "Les grandes âmes au
quotidien".

On sent (et D le dit) que D s'emmerde un peu en temps de paix (p214 dans l'édition Folio, n°46). C'est lorsqu'il
dit qu'en temps de paix les grandes âmes se voient moins que j'ai le moins envie de le rejoindre; peut-être
est-ce vrai, mais seulement pour sa conception à lui de la grandeur d'âme. Il est vrai que si on commençait
à se dire que la grandeur d'âme est multiforme, que si changer une couche est certes moins glorieux que s'évader
des prisons allemandes et être résistant il n'en est pas moins vrai que changer pas mal de centaines de couches
sans flemme et épanouir ses enfants en gardant le sourire est par contre une forme de grandeur d'âme aussi,
et l'on se dirait même que des types comme Churchill (ou D, ou S, ou Napoléon, ou Einstein) sont grands par certains côtés mais aussi inévitablement bien petits par d'autres; et D est allergique à cette idée, avec ses catégories (les sots, les grandes âmes), ses hiérarchies simples.

Voilà voilà; j'ai bien rigolé, j'ai appris des choses, j'ai vu un point de vue, c'est très académile française, c'est très 18ème; malgré le côté un peu acide de mes lignes il n'empêche que le livre est disons marquant; il a une personnalité ce bouquin.
Repost 0
Published by teytaud - dans Littérature
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
8 août 2009 6 08 /08 /août /2009 15:46

1 pif

2 paf

3 pouf

Repost 0
Published by teytaud - dans Personel
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.
Méthodes.
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.
Propositions.
  • 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

http://static.inria.fr/www/videos/Rocquencourt/modele-algo/20090604-Modele-Algo-Olivier-Teytaud.zip

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.

Vidéo:
http://static.inria.fr/www/videos/Rocquencourt/modele-algo/20090604-Modele-Algo-Olivier-Teytaud.zip
 

 

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


Gens:
  • 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.
       Vulgarisation/exemples:
  • 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.


Exemples:
  • 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