News Informatique : décembre 2011

Vers de meilleurs algorithmes capables de se « battre » en eux

Deux touristes se promènent dans la savanne Africaine et ils entendent un lion rugir un petit peu plus loin. Immédiatement, l’un des deux ouvre son sac et sort ses chaussures de course. « Mais tu es fou » lui dit son ami, « tu ne pourras jamais courir plus vite que le lion! ». Le deuxième répond alors, « Pas grave, il suffit que je cours plus vite que toi! ».

Traditionnellement en informatique, l’objectif d’un algorithme est de fournir la solution optimale et de tenter de minimiser le temps de calcul pour obtenir cette solution. Cependant à part dans des problèmes mathématiques bien définis pour lesquels une solution optimale existe vraiment, la plaisanterie ci-dessus démontre que dans une situation pratique il n’est pas toujours avantageux de trouver une solution « parfaite », mais simplement de mettre en place une stratégie supérieure à celle proposée par la compétition. Un groupe de mathématiciens travaillant au département de recherche et développement de la branche Israelienne de Microsoft ainsi que au Techion à Haifa vient de faire des progrés importants dans la compréhension des propriétés des algorithmes, non pas « optimaux » mais plutôt « compétitifs ».

De manière à mieux illustrer le coeur du sujet, imaginons qu’une séries de 10 morceaux d’informations (page webs par exemple) soient organisées en une liste allant de la page la plus populaire (n1) jusqu’à la page la moins populaire (n10) dans le sens le plus naturel (n1 > n2 > … > n9 > n10). Une telle organisation correspond à un algorithme « glouton ». En l’absence de compétition, il est évident que cette organisation est optimale. Imaginons maintenant une compétition entre deux agents dont le but est de fournir un « moteur de recherche » permettant aux utilisateurs de retrouver les informations qu’ils souhaitent le plus rapidemenent possible. Dans ce cas, il est clair que l’organisation « naive » proposée ci-dessus représente un cas très spécial qui n’est « optimal » que dans un sens abstrait. Si la page la plus populaire représente la demande de 40% des utilistateurs, l’organisation présentée ci-dessus laisse 60% des utilisateurs insatisfaits. Cela signifie que dans un environnement compétitif, il suffit qu’une compagnie offre un « moteur de recherche » qui donne plus d’importance à des pages un peu moins populaires (et donc devient non-optimal) pour en fait se rapprocher de la demande des utilisateurs. Typiquement, après plusieurs étapes de réajustement, il est attendu que tous les compétiteurs finissent par converger vers un une solution « équilibrée ». Il s’agit d’une situation dans laquelle les agents, ayant finalement compris leurs stratégies réciproques, ne peuvent plus changer de stratégie sans affaiblir leur propre position. En théorie des jeux, on parle d’équilibre de « Nash ».

Pouvoir déterminer à l’avance quelle sera la solution d' »équilibre », représente donc un problème d’importance capitale. Malheureusement, il est extrèmenent difficile d’aborder ce genre de question de manière satisfaisante car la complexité du temps de calcul augmente exponenetiellement avec la taille des informations. Un groupe de chercheurs de Microsoft Israel et du Technion viennent de prouver un certains nombres de théorèmes mathématiques qui ouvrent une nouvelle avenue de recherche dans ce domaine. En se basant sur un modèle simplifiée ne contenant que 2 participants (situation déjà non-triviale en terme de complexité), les mathématiciens ont développé une théorie probabilistique permettant de prouver l’existence ou non, de stratégies compétitives capables de « battre » la stratégie optimale (mais sans compétition). Dans quelques examples particuliers, ils ont même réussi à construire explicitement des stratégies compétitives.

Ces travaux offrent une excursion dans un domaine des mathématiques encore très peu étudiées. Les applications possibles des techniques mises en place par Microsoft Israel vont bien au-delà de l’informatique et des mathématiques. Par exemple, des questions du genre: « Sous quelles conditions est-ce que la compétition entre plusieurs stratégies engendre une amélioration ou une dégradation du niveau de performance attendue? », intéressent également de nombreuses autres disciplines allant de la politique à l’économie.

En savoir plus : http://www.bulletins-electroniques.com/actualites/68493.htm

Une connexion sans fil aussi rapide qu’avec la fibre optique

Alors que la fibre optique est encore en cours de déploiement en France, des chercheurs japonais de l’université d’Osaka et le fabricant de composants électroniques Rohm sont parvenus à créer une puce capable de transférer des données sans fil à des vitesses comparables… à celles obtenues par la fibre optique.

En effet, deux de ces puces ont échangé des données sans fil à un débit de 1,5 Gb/s (un record du monde ! ) en utilisant des ondes « térahertz », ondes situées entre la lumière et les ondes radio sur le spectre électromagnétique. Ces puces ont été développé en utilisant l’effet tunnel [1], découvert par un chercheur japonais (Leo Esaki) qui a reçu le prix Nobel de physique en 1973 pour cette avancée. Les chercheurs affirment qu’il est possible, grâce à cette technologie, d’atteindre une vitesse de 30 Gb/s.

Le semiconducteur, d’une longueur de deux centimètres et d’une hauteur d’un centimètre, est attaché à une antenne de la taille d’un grain de riz. Il peut être produit pour seulement quelques centaines de yens (soit quelques euros). Cela diffère fortement des puces actuelles de 20 cm, coûtant plusieurs millions de yens (plusieurs dizaines de milliers d’euros) et n’atteignant qu’au maximum 100 Mb/s en débit de transmission.

Le processus de fabrication en série de ces puces devra être développé, afin de pouvoir équiper de futurs téléphones portables et autres équipements électroniques dans trois ou quatre années.

En savoir plus : http://www.bulletins-electroniques.com/actualites/68321.htm

Vers des moteurs de recherche plus intelligents

Rechercher des informations détaillées sur un sujet précis sur Internet est parfois une opération assez frustrante. Il est souvent nécessaire d’ajuster de manière astucieuse les « mots clefs » en plus d’utiliser au mieux toutes les options des moteurs de recherche de manière à obtenir un lien vers un le site souhaité. Ce problème est du au fait que le moteur de recherche n’interprète pas toujours nos requêtes de la même manière qu’un être humain comprend naturellement.

Soucieuse de remédier à cette situation et avec l’objectif d’améliorer la qualité de ses services, la compagnie Américaine Google vient de commencer une collaboration avec des informatitiens à l’Université de Tel Aviv. Spécialisée dans le domaine de l’intelligence artificielle, l’équipe de chercheurs est dirigée par le Prof. Yishay Mansour.

Grâce à une série de travaux récents, les scientifiques israéliens ont mis au point de nouveaux algorithmes capables de changer et d’influencer les décisions d’ordinateur en temps réel. L’idée consiste à « éduquer » l’ordinateur en lui « apprenant » à mesurer le degré de chevauchement entre le résultat souhaité et le résultat proposé par le moteur de recherche. Après une période d’apprentissage pendant laquelle le moteur de recherche « fait connaissance » avec les besoins d’un internaute particulier, il devient ensuite beaucoup plus rapide et ne répète pas les erreurs d’interprétations originales.

Il convient de noter que ce nouveau projet contribue à des liens déjà trés forts entre Google et le milieu académique israélien. En fait, le directeur de la branche israélienne de Google, le Prof. Yossi Matias, est d’ailleurs lui même un membre du département d’informatique de l’Université de Tel Aviv. Dans le cas du Prof. Yishay Mansour, l’investissement de la part de Google vient de l’espoir que le travail de son équipe pourrait déboucher sur une amélioration des algorithmes utilisés dans des programmes commerciaux tels que les plateformes publicitaires AdWords et AdSense.

En savoir plus : http://www.bulletins-electroniques.com/actualites/68492.htm

Sources : Bulletins électroniques