Les chercheurs font un pas de plus vers l'ajout de processus probabilistes aux machines déterministes
Un problème informatique à long terme - Simulation du jet de dés
Voici un exercice d'une simplicité trompeuse: trouvez un numéro de téléphone aléatoire. Sept numéros d'affilée, choisis de manière à ce que chacun d'eux soit également probable, et pour que votre choix du numéro suivant n'affecte pas le choix du prochain. Très probablement, cela ne fonctionnera pas pour vous. Vous ne pouvez pas me croire sur parole - des recherches menées depuis les années 1950 montrent que nous ne sommes pas aléatoires d'un point de vue mathématique, sans même s'en rendre compte.
Ne vous fâchez pas. Les ordinateurs ne génèrent pas non plus de nombres aléatoires. Ils ne devraient pas - les programmes et le matériel des ordinateurs fonctionnent selon la logique booléenne , pas les probabilités. «La culture informatique est basée sur le déterminisme», a déclaré Vikash Mansinhkaqui dirige un projet de calcul probabiliste au MIT - et cela apparaît à presque tous les niveaux. "
Cependant, les programmeurs veulent créer des programmes qui s'exécutent de manière aléatoire - parfois les tâches l'exigent. Au fil des ans, des algorithmes ingénieux ont été développés qui, bien qu'ils ne génèrent pas de nombres aléatoires, offrent des moyens intelligents et efficaces d'utiliser et de manipuler le hasard. L'une des tentatives les plus récentes a été faite par le groupe de Mansinkhee au MIT, qui est sur le point de dévoiler son Fast Loaded Dice Roller , ou FLDR, lors d'une conférence internationale sur l'IA et les statistiques en août.
Pour faire simple, FLDR utilise une séquence aléatoire pour simuler parfaitement un dé de triche (ou une pièce de monnaie mal pondérée ou des cartes marquées). "Il montre comment transformer un tirage au sort parfaitement aléatoire en un tirage déformé", a déclaré le mathématicienPeter Birhorst de l'Université de la Nouvelle-Orléans. Birhorst n'a pas participé à cette étude, mais considère que les prémisses sous-jacentes au FLDR sont «convaincantes».
FLDR ne vous donnera aucun avantage lorsque vous jouez au Monopoly ou aux tables de craps de Las Vegas. Cependant, ses créateurs disent qu'il permet d'intégrer des nombres aléatoires dans des logiciels ou du matériel nativement déterministes. L'intégration de ces incertitudes aidera les machines à faire des prédictions plus humaines et à mieux simuler des événements basés sur le hasard, comme le climat ou les marchés financiers.
L'aléatoire est un concept plus complexe qu'il n'y paraît. Chaque chiffre dans une séquence de chiffres aléatoires, où il n'y a pas de motif discernable, la probabilité d'occurrence est la même. Par exemple, le nombre π n'est pas aléatoire, mais on pense que par cette définition ses nombres sont aléatoires (les mathématiciens l'appellent «normal»): chaque chiffre de 0 à 9 apparaît approximativement le même nombre de fois.
Et bien que vous puissiez trouver des "générateurs de nombres aléatoires" sur Google, il n'y aura pas de pur hasard. Les processeurs, moteurs de recherche et générateurs de mots de passe actuels utilisent une méthode «pseudo-aléatoire» qui est «assez bonne» pour la plupart des tâches. Les nombres sont générés à partir de formules complexes - cependant, en théorie, connaître la formule peut prédire la séquence.
Les scientifiques tentent d'intégrer un véritable hasard dans les machines depuis au moins 80 ans. Jusque-là, des nombres aléatoires étaient prélevés sur d'anciens assistants fiables - ils jetaient des os, sortaient des balles avec des numéros d'un sac bien mélangé ou utilisaient d'autres appareils mécaniques. En 1927, un statisticien a échantillonné les données du recensement, compilant un tableau de 40 000 nombres aléatoires.
Vikash Mansinkhka, chef de projet informatique probabiliste au MIT
Les premières sources de nombres aléatoires étaient des machines physiques. Le premier générateur de nombres aléatoires a été inventé par les statisticiens britanniques Maurice George Kendall et Bernard Babington Smith, qui l'ont décrit en 1938. La voiture était placée dans une pièce sombre, et là, elle tournait un disque, divisé en 10 secteurs, numérotés de 0 à 9. Quand quelqu'un appuyait sur le bouton à intervalles irréguliers, de brefs éclairs de néon ou des étincelles éclairaient le disque, le saisissant de l'obscurité, il semblait une image figée où un seul numéro était visible. Une machine plus récente, Ernie, utilisait le bruit dans les tubes néons. Depuis 1957, elle sélectionne les numéros gagnants de la loterie britannique.
Plus tard, à la recherche de séquences vraiment aléatoires, les informaticiens, selon Birhorst, ont dû se tourner vers des phénomènes naturels tels que le rayonnement relique ou des systèmes quantiques imprévisibles. «Il existe dans la nature des processus aléatoires vraiment imprévisibles qui peuvent être exploités», a-t-il déclaré. "Un électron réfléchissant vers la gauche ou vers la droite ne peut pas dire à l'avance ce qu'il fera."
Cependant, le hasard ne vous mènera pas loin. À la fin des années 40, les physiciens ont commencé à générer des nombres aléatoires qui s'inscrivent dans une distribution de probabilité donnée. De tels outils - des versions théoriques des cubes NOS - ont fonctionné plus précisément dans des situations réelles, telles que les embouteillages ou les réactions chimiques. En 1976, les pionniers de l'informatique Donald Knuth et Andrew Yaoprésenté un algorithme capable de produire des échantillons aléatoires de n'importe quel tableau de résultats pondérés basés sur une séquence de nombres aléatoires. «C'est l'algorithme le plus efficace auquel vous puissiez penser», a déclaré Fera Saad, étudiante diplômée du laboratoire de Mansinkhke qui a dirigé les travaux du FLDR.
Malheureusement, dit Saad, l'algorithme fait connaître un compromis aux informaticiens: de nombreuses applications à exécution rapide utilisent beaucoup de mémoire, et les applications qui utilisent peu de mémoire peuvent prendre très longtemps. L'algorithme de Knuth et Yao entre dans la première catégorie, ce qui le rend élégant, mais trop gourmand en mémoire pour une utilisation pratique.
Cependant, Saad a proposé une décision intelligente au printemps dernier. Il s'est rendu compte que si la somme des poids des chiffres du cube est égale à une puissance de 2, l'algorithme s'avère efficace à la fois en mémoire et dans le temps. Imaginez que pour un cube à six côtés, les poids 1, 2, 3, 4, 5 et 1 sont ajoutés aux probabilités de déploiement des nombres de 1 à 6. Autrement dit, la probabilité de déploiement de 1 est 1/16 et 2 est 2/16. En conséquence, la somme des poids est de 16 - ou 2 4 - et l'algorithme s'avère efficace à la fois en mémoire et en temps.
Fera Saad, doctorante au MIT
Mais disons que les poids sont 1, 2, 3, 2, 4, 2, ce qui fait 14. Puisque 14 n'est pas une puissance de 2, l'algorithme Knut-Yao nécessitera beaucoup plus de mémoire. Saad s'est rendu compte que l'on pouvait ajouter du poids supplémentaire pour que les poids totalisent toujours une puissance de 2. Dans ce cas, vous pouvez ajouter un visage fictif avec un poids de 2, puis les poids totalisent 16. Si l'algorithme choisit un visage réel, cette valeur est enregistrée. Si elle est fictive, la valeur est ignorée et l'algorithme redémarre.
C'est la clé de l'efficacité du FLDR, ce qui en fait un outil de simulation puissant. La quantité de mémoire supplémentaire pour les lancers supplémentaires est insignifiante par rapport aux grandes quantités requises par la version originale de l'algorithme.
FLDR rend l'algorithme Knuth-Yao efficace et offre l'occasion d'élargir sa portée. Les simulations du changement climatique, les prévisions de récolte, les simulations de particules, les modèles de marché financier et les explosions nucléaires souterraines dépendent tous de nombres aléatoires distribués avec une probabilité pondérée. De plus, les nombres aléatoires sont au cœur des schémas cryptographiques qui protègent les données transmises sur Internet.
Mansinkhka dit que FLDR peut aider les chercheurs à trouver des moyens d'intégrer la probabilité dans les processeurs informatiques, c'est ce que fait son laboratoire du MIT. L'algorithme peut aider à améliorer les bibliothèques de logiciels et les nouvelles architectures de processeur qui peuvent générer des nombres aléatoires et les utiliser efficacement. Ce serait un changement significatif par rapport aux machines booléennes déterministes auxquelles nous sommes habitués.
«Nous pourrions avoir de bonnes chances d'intégrer l'aléatoire dans les éléments constitutifs du logiciel et du matériel», a-t-il déclaré.
Voir également: