Le cyberblog du coyote

Le jeu de go, un domaine où les ordinateurs ne sont pas à la hauteur du cerveau humain. Mais ils y font des progrès spectaculaires en utilisant les méthodes dites « de Monte Carlo ».

Lire l'article complet sur Interstices.

Par la force de la déduction logique, un logiciel peut-il construire une hypothèse à partir de résultats ? Peut-il inférer des lois physiques à partir d'observations ? En allant plus loin, pourrait-il mener à bien une expérience ? Ce sujet n'est plus un débat de philosophie ou de science-fiction. A ces trois questions, la réponse est oui. D'ailleurs, ces robots savants existent déjà...

La même semaine, deux équipes publient leurs résultats portant sur un même sujet : faire réaliser par un système robotisé le travail d'un scientifique. A l'université d'Aberystwyth, au Pays de Galles (Royaume-Uni), le projet, baptisé Robot Scientist, existe depuis plusieurs années. Là-bas, on vient de mettre la dernière main à Adam – dont le nom est l'acronyme de A Discovery Machine – , un spécialiste de génétique que l'on a fait travailler sur le génome de la levure de boulanger (Saccharomyces cerevisiae). Ross King et ses collègues en rapportent les étonnants résultats dans la revue Science.
Adam est d'abord un logiciel. L'équipe du projet Robot Scientist a mis au point un langage particulier, capable de manipuler des graphes représentant les réactions chimiques connues entre des molécules. Le logiciel est notamment capable de remonter à la structure d'un gène codant pour une certaine protéine (par exemple une enzyme).
Mais Adam n'est pas qu'un logiciel. C'est aussi un robot en ce sens qu'il peut manipuler des sources de réactifs, des boîtes de Petri, un congélateur, un incubateur et quelques autres ustensiles d'un laboratoire de biochimie. Sa première mission était d'identifier les gènes codant pour treize enzymes, dites orphelines, c'est-à-dire dont on ignore le gène correspondant. Adam avait à sa disposition des cultures de différents mutants de la levure, caractérisés par l'inactivation de certains gènes.
A l'issue de son travail logique, ce chercheur débutant a élaboré une série d'hypothèses qu'il a pu tester en analysant le génome de ses levures en culture. Finalement, ce laborantin zélé, qui peut réaliser un millier d'expériences par jour, a émis vingt hypothèses, dont douze ont été vérifiées expérimentalement par des chercheurs de chair et d'os.
De l'autre côté de l'Atlantique, Michael Schmidt et Hod Lipson, du Cornell Computational Synthesis Lab, ont mis au point un algorithme capable de déduire des lois physiques de données issues d'expériences. Pour démontrer ses possibilités, les deux chercheurs viennent de publier dans la même revue Science les déductions réalisées par leur algorithme à partir de plusieurs systèmes oscillants, du pendule simple au pendule double (le second attaché à l'extrémité du premier).
Quant à l'équipe britannique, elle ne compte pas s'arrêter à Adam. Logiquement baptisé Eve, le second robot scientifique du projet aura pour thème de travail la recherche de nouveaux médicaments.
Pour des travaux de laboratoire qui requiert des milliers d'expériences et des déductions portant sur un grand nombre de données, on comprend tout l'intérêt de ce genre d'assistants, capables de faciliter grandement la tâche d'une équipe de chercheurs. De tels laboratoires automatisés pourraient aussi jouer un rôle dans l'analyse d'échantillons à la surface d'une autre planète.
On est cependant encore loin d'un système robotisé capable de conduire une recherche complète et de publier un résultat, bref de remplacer intégralement un scientifique... (Pour information, cet article a été rédigé de manière réellement digitale, c'est-à-dire avec de vrais doigts guidés par un cerveau humain avec la seule assistance logicielle d'un traitement de texte.)

Source : Futura-Sciences

Les logiciels peinent à reconnaître un visage. De face, devant la caméra, passe encore. Mais s'il est perdu dans une foule, vu selon une orientation quelconque, les résultats chutent dramatiquement. Or, contre toute attente, les abeilles y parviennent... Il n'y a donc qu'à copier leur savoir-faire. C'est ce qu'affirme un chercheur australien, soutenu par l'US Air Force.

Une abeille n'a qu'un million de neurones dans son cerveau, ou plutôt son ganglion cérébral (car l'insecte a d'autres ganglions dans le thorax et l'abdomen). Pourtant ses prouesses n'en finissent pas d'étonner. Concernant la vision, par exemple, les scientifiques se sont longtemps demandés comment les insectes volants pouvaient analyser aussi rapidement leur environnement. La réponse intéresse l'entomologiste mais aussi le roboticien qui espère y trouver des idées nouvelles. On sait aujourd'hui que l'analyse visuelle du vol chez les insectes repose sur un travail assez simple. En est-il de même pour la reconnaissance de formes ?
A l'université Monash (campus de Clayton), en Australie, Adrian Dyer, spécialiste de la physiologie de la vision chez les insectes, s'est penché sur la question. En 2005, lui et son équipe publiaient d'étonnants résultats sur la reconnaissance de formes dont sont capables les abeilles. Entraînées par un jeu de récompenses (un liquide sucré) et de punitions (un liquide amer, à la quinine), ces insectes apprennent en une journée à reconnaître des photographies de visages humains ! Plusieurs images de différentes personnes étaient piquées sur une plaque et les insectes devaient y reconnaître un visage présenté auparavant. Les biologistes ont juste découvert une limite à cette performance : présentée à l'envers, une photographie de visage n'est jamais reconnue.
Récemment, le même Adrian Dyer, avec Quoc Vuong (université de Newcastle, Royaume-Uni), a poussé l'expérience plus loin en étudiant la reconnaissance de visages humains présentés sous différents angles... L'idée était de comprendre comment les insectes visualisent les objets tridimensionnels. La difficulté est grande car des angles de vue différents modifient profondément l'aspect d'un objet. Comme le soulignent les chercheurs dans leur article paru dans la revue PlosOne, on sait que ce travail exige un apprentissage chez le jeune primate. Qu'en est-il chez des animaux au cerveau minuscule ?

Une abeille peut créer mentalement une reconstitution en 3D

Pour les insectes butineurs, cette performance est pourtant très utile car ils doivent reconnaître une certaine fleur quelle que soit la position dans laquelle elle se présente. Comme dans la première expérience ce 2005, les biologistes ont entraîné les abeilles à reconnaître des visages humains (en fait un parmi deux). Mais cette fois, les photographies apparaissaient sur un écran permettant de montrer trois angles de vue différents (0°, 30° et 60°), pour l'apprentissage ou pour la phase de test.
Quatre groupes d'insectes ont été constitués, qui ont permis de comprendre un des secrets de la vision en relief des abeilles. Entraînés à reconnaître un visage présenté sous un seul angle, les insectes échouent à le reconnaître lorsqu'il est présenté sous un autre angle. Par exemple, ceux qui le connaissent de face (à 0° donc) ne le reconnaîtront ni à 30° ni à 60°. En revanche, les abeilles qui ont appris à reconnaître un visage montré sous un angle de 0° et sous un angle de 60° ne se tromperont pas devant le même visage à 30° !
Conclusion des chercheurs : le très modeste cerveau des abeilles est capable d'interpolation. Ayant vu un objet de face et sous un angle de 60°, elles sauront identifier une vue intermédiaire comme si elles avaient construit mentalement une représentation en trois dimensions.
Les biologistes sont encore loin de comprendre les mécanismes en jeu mais ils s'intéressent déjà aux neurones activés dans ce genre d'exercice. Si l'on parvenait à comprendre comment s'organisent les réseaux de neurones pour résoudre ce genre de problème, la technique pourrait inspirer la programmation de logiciels de reconnaissance de formes ou de traitement d'image. C'est pourquoi l'armée de l'air des Etats-Unis (plus précisément le US Air Force Office of Scientific Research) soutient ce projet depuis deux ans...

Source : Futura-Sciences

L'analyse d'image reste un problème complexe et un logiciel a toujours bien du mal à identifier un certain objet au milieu d'une photographie. Si celle-ci présente une résolution très faible, la tâche s'apparente à une mission impossible. Mais des chercheurs américains viennent de trouver une solution... en utilisant un algorithme le plus simple possible.
Même dans une image de qualité médiocre, un humain peut facilement reconnaître des objets (voiture, chaise, maison, etc.). Un ordinateur pourrait-il en faire autant ? C’est à cette question que des chercheurs du MIT et de l’université de New York ont voulu répondre.
Dans la revue Transactions on Pattern Analysis and Machine Intelligence, Antonio Torralba, Rob Fergus et William Freeman ont présenté une approche très originale de la reconnaissance d’objets sur des images en basse résolution. Le but du jeu est le suivant : on présente une image à un ordinateur et celui-ci doit reconnaître l’objet (vélo, plante, chaussures, etc.) présent dans l’image. Il existe déjà de nombreux algorithmes capables de réaliser une telle tâche. Mais ces chercheurs ont compliqué le problème en diminuant drastiquement la résolution des images afin de réduire l’espace mémoire occupé.

Approche par la couleur

La démarche est originale. Plutôt que de développer des algorithmes de plus en plus complexes, les auteurs ont au contraire utilisé un algorithme le plus simple possible. Pour cela, ils ont créé une immense base de données contenant près de 80 millions d’images miniatures en basse résolution récoltées sur Internet et accompagnées du nom de l’objet contenu dans chacune d'elles.
Pour reconnaître une nouvelle image, ils la comparent à toutes celles de cette photothèque. Grâce à une structure de données adaptée, cette recherche peut se faire quasi instantanément. L’image sélectionnée est celle paraissant la plus proche par ses couleurs. La méthode est donc des plus simples mais les résultats présentés sont impressionnants. Les auteurs ont aussi appliqué leur méthode à la reconnaissance de scène et à la détection de visages.

Source : Futura-Sciences

Une nouvelle avancée logicielle en matière d'intelligence artificielle vient d'être présentée à l'exposition de Las Vegas consacrée aux jeux, mieux connue sous le nom de "Gaming Life Expo". Polaris, le programme informatique en question, est le premier programme réussissant à battre une équipe de joueurs de poker renommés dont chacun des membres avait remporté au moins 1 million de dollars de gains. Cette victoire de Polaris ne signifie pour autant pas que le logiciel est un joueur imbattable de poker. Le programme ne se montre actuellement performant qu'en un contre un et en Texas hold'em à pot limite. Mais les développeurs espèrent pouvoir rapidement mettre au point un programme capable de remporter des tournois de Texas hold'em no limit au plus haut niveau.
En 1997, le Deep Blue d'IBM était devenu le premier ordinateur à battre un champion du monde d'échecs et l'an dernier une équipe de chercheurs a présenté un programme capable de ne jamais perdre une partie de dames. Ces jeux étaient jusque là dominés par les humains mais étaient modélisables informatiquement et les avancées en intelligence artificielle étaient ainsi attendues. Le poker en revanche met en jeu des paramètres de bluff, de ruse et de tromperie qui ne sont pas traditionnellement associés avec les cartes mères, portes logiques et circuits intégrés. Si aux échecs ou aux dames l'ordinateur connait toutes les positions des pièces sur le plateau, il n'en va pas de même au poker où les décisions doivent être prises sans connaître le jeu de l'adversaire. Les ordinateurs ne tiennent pas encore toutes les ficelles des décisions complexes des joueurs mais Polaris réussi remarquablement dans les variantes du jeu pour lesquelles les incertitudes sont moins nombreuses. Lorsque la puissance de calcul disponible sera capable de créer, comme pour les échecs et les dames, des arbres de décision déterminant l'action permettant la plus grande probabilité de gain les futures versions de Polaris pourront alors rivaliser avec les humains et s'asseoir aux tables des plus grands champions.
Un problème fondamental risque cependant d'occuper les chercheurs pour de nombreuses années encore, à savoir le fait que pour un joueur de poker, la meilleure stratégie dépend du style de jeu l'adversaire et l'analyse informatique des comportements risque de se heurter aux tromperies délibérées des joueurs qui eux ne choisissent pas toujours des voies rationnelles.

Source : Bulletins-electroniques.com

L'ordinateur va devenir presque imbattable aux échecs
par Brian Church

Les ordinateurs d'échecs seront pratiquement imbattables dans dix ans, ce qui pourrait favoriser l'adoption de nouvelles règles pour ce jeu millénaire, comme la variante aléatoire imaginée par l'Américain Bobby Fischer, affirme le champion du monde bulgare Veselin Topalov.
"Aujourd'hui, je ne crains pas les humains, mais je pense que les ordinateurs sont très forts", avoue le grand-maître, interrogé par l'Associated Press. "Ils seront probablement meilleurs que 99,9% des humains dans une décennie."
Topalov, 30 ans, évoque également le possible avènement futur des "échecs aléatoires Fischer", inventés par l'ancien champion du monde, consistant à disposer les pièces maîtresses de manière aléatoire afin de réduire l'importance de la mémorisation des multiples variantes d'ouverture.
Le champion prédit l'émergence à terme des échecs aléatoires alors que "les ordinateurs et (la connaissance des) ouverture épuisent le jeu pratiqué aujourd'hui".
Repositionner au hasard les pièces maîtresses, situées sur la première et la dernière rangée de l'échiquier, permet de créer 960 positions initiales différentes. Cette technique prive le joueur surentraîné de son avantage et favorise la créativité.
Si Topalov n'a jamais essayé la méthode Fischer, il la juge intéressante. "Elle révèle le talent des joueurs. Vous oubliez tous les livres (de théorie sur les ouvertures) parce qu'ils deviennent complètement inutiles."
On ne sait pas comment les ordinateurs se comporteraient avec cette nouvelle règle. "Bien sûr, lorsqu'il s'agit de calcul pur on ne peut être meilleur (que les ordinateurs) mais sur les prévisions à long terme, ils ne sont pas très bons pour positionner leurs pièces", assure Topalov.
"Le problème avec les ordinateurs c'est qu'on ne peut les effrayer, ni bluffer. Il n'y a pas de combat psychologique", souligne-t-il.
Topalov a remporté l'an dernier le titre mondial version FIDE (l'autre titre est détenu par le Russe Vladimir Kramnik, NDLR), la fédération internationale basée en Grèce. La championne du monde Antoaneta Stefanova et le champion du monde senior Liuben Spassov sont également bulgares. La suprématie de la Bulgarie en matière d'échecs s'explique par l'enseignement dispensé dans cette discipline par l'ancien régime communiste.
En 2004, Topalov a été le meilleur compétiteur humain d'une épreuve opposant trois grands-maîtres à des machines, qui l'ont emporté. Le champion bulgare a fait match nul contre le super ordinateur Hydra, mais estime qu'il aurait dû gagner. "Il a défendu de manière fantastique (...) mais on a vu qu'il avait des failles." Topalov se dit prêt à un nouveau duel contre ce redoutable ordinateur en 2006.
Basé à Abu Dhabi, aux Emirats arabes unis, Hydra peut calculer 200 millions de coups à la seconde et possède une puissance de calcul 200 fois supérieure à celle d'un PC ordinaire, selon son site Internet.
Des grands-maîtres aident les informaticiens à concevoir de telles machines, note Topalov. Et ils risquent ainsi d'être un jour confrontés à leur propre création. "Je n'aimerais pas (jouer contre moi-même)", plaisante le champion bulgare.

Source: Branchez-vous!

Des scientifiques canadiens ont mis au point un programme d'ordinateur impossible à battre au jeu de dames. Une formidable avancée dans le domaine de l'intelligence artificielle.
Jonathan Schaeffer, détenteur de la chaire de sciences informatiques à l'université d'Alberta (Canada), aidé par d'autres informaticiens de cet établissement, se sont acharnés durant 18 ans à programmer les quelque 500 milliards de milliards de combinaisons possibles au jeu de dames, un grand classique du genre répandu dans le monde entier.
Et le résultat est là : Chinook, puisque c'est le nom du logiciel, s'avère impossible à battre. Au pire, il conduira une partie jusqu'à une impasse débouchant sur la nullité, et confronté à un autre ordinateur utilisant le même programme, ne produira que des parties nulles.
"Nous avons monté la barre de plusieurs échelons dans ce qu'il est possible de faire en matière de technologie informatique et d'intelligence artificielle" déclare Jonathan Schaeffer, qui s'avoue lui-même piètre joueur de dames. Jaap van den Herik, éditeur de la revue "International Computer Games Journal", ne tarit pas d'éloges en qualifiant cette réalisation de "véritable avancée dans le domaine de l'intelligence artificielle".
Pour mettre au point son programme, Schaeffer a mobilisé environ 50 ordinateurs quotidiennement depuis 1989, parfois jusqu'à 200 dans les moments critiques, et a fait appel à plusieurs joueurs professionnels.
A l'origine, Chinook avait été élaboré pour participer au Championnat du Monde de Dames. Perdant en finale en 1992, il l'a remporté deux ans plus tard en devenant ainsi le premier logiciel à obtenir un titre mondial dans un jeu de compétition. Mais estimant alors que les ordinateurs de nouvelle génération devraient permettre de créer un programme infaillible, Schaeffer se remettait au travail en 2001 pour arriver au résultat actuel.

Pour en savoir plus : checkers, Chinook
Et sur les humains qui jouent aux dames : International checkers world records

En matière de traduction automatique, la marge de progression est énorme. Discipline complexe mais assurément utile, la traduction par programme est l'objet de nombreuses recherches. Un organisme américain a noté les moteurs de traductions. Dans les premiers rangs, un des grands de l'informatique : Google.
Le rapport a été publié le 1er novembre. Il avait pour objectif de faire un état de l'art dans la traduction automatique. Les exemples choisis ont été des traductions de l'arabe et du chinois (mandarin) vers l'anglais. Les sources à traduire venaient des grandes agences de presse, de newsgroups et des médias traditionels. Le score de chaque traducteur a été évalué avec des méthodes de mesures statistiques, notamment la méthode BLEU de IBM.
Avec les différentes notations, on obtient plus de 20 classements. Cependant, on voit apparaître un acteur bien connu de l'informatique dans les premières places (souvent numéro 1) : Google.
Au lieu de se pencher sur les structures grammaticales et les approches anthropologiques de tout bord (comme tout bon chercheur en linguistique), Google a préféré l'approche statistique et ça marche plutôt bien. L'algorithme découpe le texte en phrases simples. Puis, on recherche des traductions déjà effectuées pour ces phrases simples. Le moteur évalue chaque solution et choisit la meilleure suivant ses statistiques et le contexte. Ce n'est plus la construction grammaticale qui compte mais les données qui ont déjà été traduites dans le passé. Google, expert en moteur de recherche, devient expert en traduction.

Sources : Sur la Toile, NIST 2006 Machine Translation Evaluation Official Results

Article de Mathieu Rached paru dans l'édition électronique du Monde du 03.08.07

Deux joueurs de poker américains de renommée mondiale, Phil Laak et Ali Eslami, viennent de se mesurer à un programme informatique littéralement bluffant, baptisé Polaris, mis au point à l'université d'Alberta, au Canada. Les deux humains ont gagné de justesse.
Cette compétition de "Texas Hold'em", variante du poker la plus jouée, a eu lieu à Vancouver, lors de la Conférence annuelle sur l'intelligence artificielle qui s'est achevée le 24 juillet. La quatrième partie, cruciale, après un match nul, une victoire pour l'ordinateur et un gain pour les humains, a tourné à l'avantage des deux humains.
Ils faisaient équipe face à deux programmes jumeaux : les cartes avec lesquelles Phil Laak jouait contre une copie de Polaris étaient les mêmes que celles distribuées à une deuxième version du logiciel qui s'opposait à Ali Eslami. Si Phil perdait à cause de mauvaises "mains" reçues, ses pertes pouvaient être équilibrées par son camarade. La part d'aléa propre aux jeux de cartes était ainsi équilibrée.
"Le poker est plus difficile pour les ordinateurs que les échecs", affirme Jonathan Schaeffer, qui a lancé le programme de recherche "poker" il y a seize ans à l'université d'Alberta. Avec 1018 combinaisons possibles, le challenge technologique paraît pourtant bien faible en regard des 10120 parties possibles au jeu d'échecs, mais c'est compter sans la puissance du bluff, longtemps considéré comme un atout propre à l'homme. "Les mathématiques du jeu prédisent que c'est une erreur de ne pas y avoir recours", souligne cependant Neil Burch, un des concepteurs du logiciel.
Une technique dont peut désormais user la machine : "Quelques "mains" ont la possibilité d'être des bluffs, Polaris le sait et décide alors de les tenter ou pas", précise encore Neil Burch. Pas de capteurs particuliers ni de caméra, le logiciel prend seulement en compte toutes les cartes et les mises d'argent. La technique principale du jeu de Polaris repose sur une "stratégie d'équilibre", qui revient à donner le moins d'argent possible au meilleur joueur.

LA PSYCHOLOGIE EST UNE FAIBLESSE

Qu'en est-il de la psychologie du joueur ? "Le logiciel n'a pas la possibilité d'estimer le caractère et les émotions de son adversaire", précise Neil Burch. "La psychologie, c'est juste une faiblesse humaine", affirme d'ailleurs le laboratoire canadien sur son site.
Contrairement à Deep Blue, le célèbre joueur d'échecs artificiel, Polaris n'avait pas bachoté. Ni les profils des joueurs ni leurs parties types n'avaient été étudiés avant cette première compétition. Un traitement du jeu froid et rigoureux, en somme, purement mathématique, qui a mis en difficulté les deux joueurs professionnels.
Ceux-ci doivent peut-être leur salut à la soif d'expérimenter des pères de Polaris. Les scientifiques ont en effet mis à profit la compétition pour lui faire endosser plusieurs profils dirigés par un logiciel maître, lors des derniers rounds, ce qui a nui à la performance finale.
Si "pour réussir, il ne suffit pas de prévoir, il faut aussi savoir improviser", comme l'a écrit Isaac Asimov, la machine a montré qu'elle était capable elle aussi d'intégrer le facteur chance dans son jeu, de choisir, et de tenir en échec l'homme au poker. Darse Billing, un des concepteurs de Polaris, entend bien améliorer le logiciel, et ne serait "pas surpris qu'il puisse l'emporter prochainement". La machine est-elle impatiente ? On peut encore raisonnablement en douter.

A voir : The University of Alberta Computer Poker Research Group

Personne à qui parler? Eh bien allez voir ALICE -The Artificial Linguistic Internet Computer Entity, et engagez une conversation. C'est étonnant. Seule condition: parler anglais.
ALICE est un logiciel qui simule une conversation naturelle. Il a reçu le prix Loebner 2004. En 2005, c'est Jabberwacky qui a remporté le premier prix.
Le test de Turing, qui est utilisé pour attribuer le prix Loebner, est une proposition de test d'intelligence artificielle ayant la faculté d'imiter la conversation humaine. Décrit par Alan Turing en 1950 dans sa publication « Computing machinery and intelligence », ce test consiste à mettre en confrontation verbale un humain avec un ordinateur et un autre humain à l'aveugle. Si l'homme qui engage les conversations n'est pas capable de dire qui est l'ordinateur et qui est l'autre homme, on peut considérer que le logiciel de l'ordinateur a passé avec succès le test. Pour l'instant, aucun programme n'a encore passé le test de Turing, même pas Alice.