Approches techniques

Plan

Test de Turing

Le test de Turing a d'abord été présenté par Alan M. Turing (1912-1954) comme un « jeu d'imitation » dans son article de 1950 « Computing, Machinery and Intelligence » qui commença avec la phrase suivante : « Les machines peuvent-elles penser? Cela devrait commencer par les définitions des termes « machine » et « penser ». Le Test de Turing connu aujourd'hui est fait pour déterminer si un programme informatique est intelligent, mais le jeu d'imitation original d'Alan Turing peut être décrit ainsi : le jeu est joué par trois personnes, un homme (A), une femme (B) et un interrogateur (C) qui peut être des deux sexes. L'interrogateur est situé dans une salle séparée des deux autres. Le jeu consiste en un ensemble de questions que l'interrogateur pose tour à tour aux deux autres joueurs, chacun d'entre eux répondant selon le but qui lui est assigné. Le but de l'interrogateur est de déterminer lequel est l'homme et lequel est la femme. Il ne les connaît que par des étiquettes X et Y et à la fin du jeu il dit soit « X est A et Y est B », soit « X est B et Y est A ». Afin de déterminer cela, l'interrogateur peut poser n'importe quelles questions. Le but du joueur A est de tromper l’interrogateur. Afin que la voix ne puisse pas aider l'interrogateur, la communication se fait par ordinateur. Le but du jeu pour le troisième joueur (B) est d'aider l'interrogateur. Sa meilleure stratégie est probablement de donner des réponses vraies. La question « les machines peuvent-elles penser? » peut être substituée par une autre : « un ordinateur est-il capable de jouer aussi efficacement à ce jeu d'imitation que l'homme? ». L'interrogateur se trompera-t-il aussi souvent lorsque le jeu est joué de cette manière que lorsqu'il est joué entre un homme et une femme? Ainsi, aujourd'hui, le Test de Turing a été redéfini et désigne donc un test impliquant une machine : l'interrogateur peut dialoguer avec une personne et une machine grâce a un ordinateur mais ne peut les voir. Sa tache est de déterminer lequel des deux est la machine et lequel est humain uniquement en leur posant des questions. Si la machine peut tromper l'interrogateur, elle peut être considérée comme intelligente.

Le test de Turing

Ce test a été le sujet de différentes critiques et a été au cœur de nombreuses discussions dans l'IA, la philosophie et les sciences cognitives pendant les 50 dernières années.

Il semble important de faire une remarque concernant le jeu de l’imitation, tel que l’appelle Turing. A l’ère de la programmation informatique, on peut très bien envisager une machine programmée pour faire correspondre à chaque type de question une réponse de manière automatique. Il suffirait d’avoir la patience de prévoir toutes les possibilités (ce qui est théoriquement envisageable). Ce type de programme pourrait même détecter non-sens, répétitions et autres…, et ainsi passer avec succès l’épreuve du test de Turing. C’est ici qu’intervient l’avertissement : un tel type de programme ne correspond en aucun cas à une Intelligence Artificielle, ou entité approchante. Ce que conçoit Turing est une machine capable de lier mots et sens, de trouver une réponse satisfaisante (« humaine ») sur le point de vue du sens, et de l’exprimer convenablement au point de vue du langage. Il est évident qu’une telle machine aurait de grands avantages sur le plan technique, car cette capacité associée à sa puissance de calcul lui permettrait d’accomplir un grand nombre de taches, certaines mieux que l’Homme. Mais, en imaginant une machine capable de réussir le jeu de l’imitation, elle n’en aurait pas pour autant acquis son statut de « véritable » Intelligence artificielle. En effet, il lui manquerait un point important : l’autonomie. En effet, une telle machine ne ferait que répondre à un ordre assigné, sans être capable de penser par elle-même (même si, à partir de données de base, elle serait capable de pousser sa « réflexion »). C’est ici encore un obstacle à l’Intelligence Artificielle. A quand une machine se lamentant da sa condition mécanique ? Se demandant si Dieu existe ? En arrivant à la conclusion qu’elle est puisqu’elle pense ?

Le grand mérite de ce test est d'opérationnaliser la question : les ordinateurs peuvent-ils penser? Il permet de se passer d'une définition pour l'instant inaccessible de ce qu'est l'intelligence. Deux questions distinctes se posent naturellement :

  • pourra-t-on réaliser un jour une machine qui passe ce test avec succès ?
  • si oui, pourra-t-on dire que cette machine est intelligente ?

Les partisans de ce qu'on appelle l'IA forte répondent oui aux deux questions. Beaucoup de littérature a été consacrée à ce test ainsi qu'aux réponses que l'on peut apporter aux questions précédentes. Voir par exemple ci-dessous l'argument de la « Chambre chinoise » de Ronald Searle qui entend prouver que la réponse à la deuxième question doit être non. Alain Turing a fait le prédiction suivante : « Dans une cinquantaine d'années, il sera possible de programmer des ordinateurs de façon à ce qu'ils jouent si bien au jeu de l'imitation qu'un interrogateur moyen n'aura pas plus de 70% de chances de procéder à l'identification exacte après 5 minutes d'interrogation. » Cette prédiction ne s'est pas réalisée et il semble que l'on en soit encore assez loin même si le temps d'interrogation est petit et le taux d'erreur admissible assez grand. Un des rares chatterbot (robot de discussion littéralement) les plus performants actuellement, ALICE, remporte effectivement des prix mais n'arrive pas à imiter vraiment un être humain. ALICE repose en effet sur une gigantesque base de données où toutes les questions possibles et inimaginables sont inscrites ainsi que leurs réponses respectives. Mais ce système est un cul-de-sac : non seulement, il va devenir très lourd au fil du temps mais surtout on remarque qu'Alice tourne en rond quand elle ne sait quoi répondre : en bref, elle est incapable de réellement apprendre, ce qui n'en fait pas un véritable « agent intelligent ».

On peut émettre plusieurs objections à ce test : Une machine peut être intelligente sans être capable de parler exactement comme un humain. On ne peut limiter l'intelligence à l'intelligence humaine. Ce test n'étudie que les actes et non les pensées. L'ordinateur pourrait imiter l'attitude d'un humain sans être réellement intelligent. Le test dépend trop de la subjectivité du juge. Un être humain trop intelligent, qui ferait des calculs mentaux très rapidement par exemple, risquerait d'être considéré comme une machine

Alan Turing a lui-même souligné plusieurs objections à son test :

  • objection théologique
    « Penser est une fonction de l'âme immortelle de l'homme. Dieu a donné une âme immortelle à tout homme et à toute femme, mais à aucun autre animal ni à aucune machine. Aucun animal ni aucune machine ne peut donc penser. »

  • objection de l'autruche (une objection certes pas très scientifique)
    « Le fait que les machines pensent aurait des conséquences trop épouvantables. Il vaut mieux croire et espérer qu'elles ne peuvent pas le faire. »

  • objection mathématique
    Cette objection est basée sur le théorème d'incomplétude de Gödel de 1931. Quelque soit le système formel S (pourvu qu'il soit assez puissant), il existe des énoncés vrais (et que l'on peut montrer tels) que S ne peut pas produire. L'homme peut donc prouver plus de choses qu'une machine. Cette objection a particulièrement été étudiée par Lucas. La réfutation la plus courante consiste à dire que si S est un système formel qui ne peut pas produire l'énoncé vrai E, on peut facilement construire un système formel S' qui peut produire toutes les vérités produites par S ainsi que E. Il suffit de prendre S' = S ? {E}. D'une part, il n'existe pas de vérités échappant à tout système formel et d'autre part, il n'est nullement exclus que l'homme n'ait pas les mêmes limites.

  • objection de la conscience
    Ecrire un sonnet ou composer un concerto nécessite de ressentir ce que l'on fait, c'est-à-dire au minimum, d'en avoir conscience. Or une machine ne possède pas de conscience. Mais comment s'assurer qu'un homme ressent ce qu'il dit, qu'il possède une conscience ? A ce propos, Hoffstadter et Dennett citent l'histoire des deux sages taoïstes :
    « Deux sages étaient debout sur un pont enjambant une rivière. L'un dit à l'autre : « j'aimerais être un poisson, ils sont si heureux ! » Le second répondit : « Comment savez-vous si les poissons sont heureux ou non ? Vous n'êtes pas un poisson. » Et le premier répondit : « Mais vous n'êtes pas moi, alors comment savez-vous si je sais ce que ressentent les poissons ? »

  • « La Machine Analytique n'a pas la prétention de créer quoi que ce soit. Elle peut faire tout ce que nous savons lui ordonner de faire. » Cette objection est devenue très classique. L'homme crée la machine, il a donc une supériorité sur elle. Il est pourtant facile de programmer une machine afin qu'elle réalise des tâches que son programmeur ne sait pas forcément faire (comme bien jouer aux échecs, par exemple).

La chambre chinoise de Searle

Le philosophe anglais John Searle décrit dans l'article « Minds, Brains and Programs » publié en 1980 une expérience de pensée (Gedankenexperiment) qui selon lui permet de réfuter l'assertion défendue par les partisans de l'IA forte selon laquelle une machine satisfaisant avec succès au critère de Turing doit être considérée comme intelligente. Cette expérience peut être décrite de la manière suivante : John Searle est enfermé dans une pièce ne communiquant avec l'extérieur que par un guichet et contenant un (très) gros livre dans lequel est écrit une succession de questions et de réponses pertinentes à ces questions, questions et réponses étant rédigées en chinois. Searle précise qu'il ne connaît rien au chinois et que l'anglais est sa langue maternelle. Un expérimentateur lui transmet des messages par le guichet, tantôt en anglais, tantôt en chinois. Searle répond directement aux messages rédigés en anglais alors que pour ceux rédigés en chinois, il est obligé de consulter le livre jusqu'à trouver une question identique au message ; il recopie alors la réponse associée. Searle fait alors remarquer que pour l'expérimentateur extérieur, les messages transmis en chinois sembleront aussi pertinents que ceux transmis en anglais. Et pourtant Searle connaît l'anglais alors qu'il ne connaît rien au chinois. De manière analogue, on ne peut pas déduire du fait qu'un programme passe avec succès le test de Turing qu'il comprenne de quoi il est question. L'argument semble très fort à première vue. On lui fait souvent l'objection suivante : s'il est vrai que Searle ne connaît pas le chinois, que peut-on dire du système composé de Searle et du livre ? Les partisans de l'IA forte diront que ce système connaît le chinois. La preuve en est qu'il est capable de répondre de manière pertinente à n'importe quelle question rédigée en chinois. Cette objection n'est valide que si on considère le logiciel informatique testé comme étant équivalent à Searle seulement, et le livre étant un outil indépendant du logiciel.

Approches techniques avec l'informatique

Au XVIIIème siècle, les philosophes René Descartes et Gittfried Wilhelm Leibniz rêvent de pouvoir traduire les activités humaines par un certain nombres de principes. Cela devrait leur permettre de mieux comprendre la raison humaine car les idées naissent de la pensée. Pour G.W. Leibniz, penser c'est calculer, il est ainsi l'un des précurseurs de la théorie comme quoi il serait possible de transcrire la pensée sous forme d'algorithmes.

Au début du XIXème siècle, le logicien George Boole invente le calcul symbolique ou language binaire, qui traduit toutes les opérations logiques « si », « alors », « ou », « et » ... sous forme d'opérations mathématiques simples à partir des chiffres 0 et 1. Comme Leibniz, Boole souhaite mathématiser l'esprit humain.

En 1936, le mathématicien anglais Alan M.Turing imagine un dispositif virtuel, « la machine de Turing », qui traduirait en une suite d'opérations simples, un problème mathématique humainement calculable. Il invente l'algorithme, une des bases de l'informatique.

En 1958, John McCarthy, un des principaux pionniers de l'intelligence artificielle, crée le language de programmation LISP(pour LIST Processing qui signifie traitement de ligne). Il est initialement développé en tant que modèle pratique pour représenter des programmes par contraste avec la notion théorique de la machine de Turing. Les languages de programmation, utilisés pour programmer des logiciels, sont des languages ressemblant à un language humain, traduits par un compilateur spécifique à chaque language en language binaire, compréhensible par l'ordinateur. Le language binaire est une suite de 0 et de 1, qui correspondent à l'état physique (conducteur ou non conducteur) des éléments électroniques ou magnétiques constituant l'ordinateur.

La construction de programmes d’intelligence artificielle s'appuie sur plusieurs approches:

3 approches

Algorithmes

L'algorithme est un outil de calcul rapide au service de l'homme. C'est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver avec certitude en un nombre fini d'étapes à un certain résultat. Il existe des algorithmes de jeux, de recherche d'un chemin, d'optimisation ... Les algorithmes se sont développés avec les ordinateurs et la nécessité d'automatiser les calculs. Un programme est un algorithme écrit dans un langage digeste pour l'ordinateur.

Ci-dessous un exemple d'un algorithme créé par nous-même pour trouver un ensemble de nombre premier dans une intervalle.
On suit toutes les étapes indiquées. Dans certains cas, l'exécution peut être longue :

Trouver tous les nombres premiers jusqu'à N:

  • l'algorithme explore
  • selon la séquence parfaitement codifiée,
  • toutes les possibilités de division
  • de chaque nombre inférieur à N
  • par tous les nombres inférieurs à la racine carrée de N (car un nombre ne peut pas être divisé par un nombre supérieur à sa racine carré)
Cliquez ici pour tester l'application.

Une approche algorithmique nécessite l’écriture du processus à suivre par un humain pour résoudre le problème, puis sa transcription en un programme. Lorsque le problème est complexe, ce peut être une étape couteuse ou impossible. Les ordinateurs sont des machines complètement logiques, qui suivent à la lettre chacune des instructions du programme, sans jamais se tromper, contrairement à l’homme. Cependant aucune machine n’est capable elle-même de concevoir des algorithmes, l’intelligence du programmeur est toujours derrière.

"Les machines pourront un jour résoudre tous les problèmes, mais ne pourront jamais en poser un." Einstein

Systèmes experts

Harry M Collins fait le pari que lorsque les machines deviendront plus puissantes, on cessera de considérer l'expertise humaine comme une collection de règles ou alors le nombre de règles augmentera considérablement et restera bien au-delà de l'horizon des machines.

Un système expert est un outil informatique capable de reproduire les mécanismes cognitifs d'un expert humain, dans un domaine particulier. Il s'agit de l'une des voies tentant d'aboutir à l'intelligence artificielle. En 1965 l'informaticien états-unien Edward Feigenbaum conçoit le premier système expert DENDRAL, qui détermine la formule chimique d'une molécule.

Un système expert peut se décomposer en deux composantes principales : la base de connaissances et le moteur d'inférence dont le rôle est de raisonner à partir des données contenues dans la base de connaissances.

La base de connaissances

Elle est composée d'une base de règles qui rassemble la connaissance et le savoir-faire de l'expert sous forme de règles de déduction et d'une base de faits qui contient les données concernant le cas à traiter.

La base de règles : une règle se présente sous la forme d'une équation de logique formelle : Si X alors Y, où X est appelé prémisse et Y conclusion. X rassemble les conditions que l'on veut avoir pour obtenir Y. Exemple de règles :

  • "SI un animal a six pattes ALORS c'est un insecte"
  • "SI un animal a quatre pattes ET S'IL a des mamelles ET S'IL a un groin MAIS S'IL n'est pas sauvage, ALORS c'est un cochon"
  • "SI un arbuste a des feuilles composées ET palmées ET SI les feuilles ont 3 à 7 folioles ET un rameau très épineux ALORS c'est une ronce"

Grâce à ce type de représentation proche du language naturel, la connaissance du système sera facilement accessible à l'utilisateur qui pourra ainsi aisément la modifier ou l'agrandir. La modélisation de la connaissance sous forme de règles est possible pour les sciences à peu près exactes (électronique, mécanique, physique etc.) où la connaissance est explicite, et pour les sciences dites "humaines" comme la psychologie où la connaissance est empirique.

La base de faits constitue la mémoire de travail du système expert. Elle est variable au cours de l'exécution et vidée lorsque l'exécution se termine. Au début de la session elle contient ce que l'on sait du cas examiné avant toute intervention du moteur d'inférence. Puis elle est complétée par les faits déduits par le moteur ou demandés à l'utilisateur. Les faits élémentaires de la base peuvent avoir des valeurs booléennes (VRAI ou FAUX), symboliques (ensemble fini de symboles) ou réelles (valeurs appartenant à un ensemble continu). Exemple de faits :

  • "Nombre de pattes de l'animal = 4"
  • "L'animal pond des oeufs = FAUX"

Le moteur d'inférence

Pour exploiter les règles de la base de connaissances, un moteur d'inférence est nécessaire pour relier la description d'un problème aux capacités d'analyse d'une situation donnée. Le moteur d'inférence est capable de répondre à des questions, de raisonner et de tirer des conséquences impliquées par la connaissance incluse dans le système. Il est écrit dans un language d'intelligence artificielle tel que le LISP ou le PROLOG.

Pour cela, le moteur d'inférence va enchaîner les règles de la base de règles, il va effectuer un chaînage, c'est-à-dire un raisonnement. Il existe plusieurs types de chaînages :

  • le chaînage avant : il permet de déduire des faits découlant des données initiale. Les règles dont les prémisses sont connues sont enclenchées jusqu'à ce que le fait à déduire soit connu ou qu'aucune règle ne puisse être déclenchée. Explications : on veut déduire un fait X. On examine toutes les règles où ce fait X apparaît en prémisse. Toutes les règles dont les prémisses sont connues sont alors déclenchées : on obtient de nouvelles valeurs pour les variables et on déclenche de nouveau toutes les règles dont les prémisses sont connues. Si des règles pour lesquelles une expression de X apparaît en prémisse sont déclenchées (que ce soit à partir du deuxième tour ou du centième), c'est donc que leur prémisse est vérifiée : on obtient ainsi des équations en fonction de X plus ou moins complexes que l'ordinateur va résoudre. On aura donc déduit à partir des autres faits connus un fait X inconnu.

  • le chaînage arrière : le mécanisme du chaînage arrière consiste à partir du fait que l'on souhaite établir, à rechercher toutes les règles qui concluent sur ce fait, à établir la liste des faits qu'il suffit de prouver pour que ces règles puissent se déclencher puis à appliquer le même mécanisme aux faits contenus dans ces listes, et ainsi de suite jusqu'à ce que l'on retombe sur un fait déjà connu. Le chaînage arrière est un mécanisme d'induction : on vérifie les hypothèses en remontant depuis l'objectif. On cherche ainsi à vérifier si un fait est possible.

  • le chaînage mixte : il utilise les deux chaînages présentés ci-dessus. Ce sont les caractéristiques du problème qui vont conditionner le chaînage qu'il est judicieux d'utiliser. Ainsi lorsque les faits sont peu nombreux ou que le but est inconnu, il est préférable d'utiliser un chaînage avant. Si les buts sont peu nombreux ou/et précis, le chaînage arrière convient mieux.

Schéma résumant ce qu'est un système expert

Système expert

Applications, inconvénients et limites

Les systèmes experts sont utilisés lorsque les méthodes algorithmiques classiques ne peuvent pas être appliquées avec succès. Ils sont généralement conçus pour résoudre des problèmes de classification ou de décision (diagnostic médical, prescription thérapeutique, régulation d'échanges boursiers, etc.).

Les systèmes experts, très utilisés dans le monde de l'entreprise, ne sont utiles et envisageables que dans des domaines possédant des experts humains. Ces experts sont des individus qui connaissent bien le domaine à modéliser et qui sont aussi capables de transmettre leur savoir. En fait le système expert ne crée pas l’intelligence, mais aide à la partager et la mettre en oeuvre en intégrant des expertises venant d’individus différents, contrairement à la solution algorithmique où tout passe par l’intelligence d’un programmeur. Les systèmes experts ne s'appliquent que là où la modélisation de la connaissance est possible sous forme de règles. D'une manière générale, les problèmes purement mathématiques ne sont pas les bons exemples pour montrer les performances des systèmes experts.

D’autre part, la cognition quotidienne prend place dans un univers dont il est impossible de faire une description sans ambiguïté. Ce n’est pas le cas des micro-univers de l’IA, dont les propriétés et éléments sont, dans leur ensemble, clairement prédéfinis, au même titre que ceux du jeu d’échecs. Les cas qui n'ont pas été correctement prévus par l'expert ne seront pas correctement traités par la machine.

Exemple de limites d'un système expert : imaginons le programme "passage" formé des règles suivantes :

    Je peux passer devant X si
  • X me fait un sourire furtif et
  • X maintient un contact oculaire prolongé
Dans le cas où X sourit et me regarde, puis-je vraiment passer? Et si X était aveugle! Il faut ajouter une nouvelle condition à la règle:
  • et X non-aveugle
Sans parler de la définition des mots utilisés:
  • un sourire est furtif si sa durée est inférieure à une seconde
  • un sourire n'est pas un mouvement involontaire
  • etc.

En fait, le problème est que tout le champ des connaissances doit être couvert de manière exhaustive, faute de quoi on s'expose à des conclusions erronées.

Les réseaux de neurones

L'intelligence est-elle une forme complexe de calcul ? Comme tout ce qui peut être calculé par des algorithmes peut l'être par une machine, la question de l'intelligence artificielle "forte" ou "faible" revient donc à la suivante : les neurones du cerveau obéissent-ils à des règles algorithmiques ou non ? Les processus cognitifs réalisent-ils de simples calculs ?

L'idée principale de l’approche neuronique de l’intelligence artificielle est de modéliser l'entité de base du cerveau humain, c'est-à-dire le neurone, et d'en assembler plusieurs afin de se rapprocher du raisonnement humain. On construit alors un réseau constitué de plusieurs couches de neurones, dont le nombre est déterminé par la complexité du problème à résoudre. Par exemple, pour des problèmes linéaires, donc simples, une à deux couches suffisent et la résolution du problème est très rapide.

Fonctionnement

Neurones Et Synapses

Les neurones communiquent entre eux en émettant des signaux électriques d’intensité plus ou moins importante. Chaque neurone effectue une sommation des signaux qui lui parviennent, et lorsque la sommation atteint une valeur de seuil, le neurone émet alors à son tour un signal. La transmission du signal est assurée par les synapses : les synapses excitatrices, qui renvoient un signal proportionnel au signal reçu, et les synapses inhibitrices, qui renvoient un signal inversement proportionnel au signal reçu.

Construction d’un réseau

Pour résoudre un problème à l’aide d’un réseau de neurones, il faut tout d’abord construire le réseau en fonction du problème à traiter. On choisit le nombre de couches, la façon dont les neurones vont être reliés entre eux, et la fonction des différents synapses utilisées (inhibitrices ou excitatrices).

Puis on passe à la phase d’apprentissage : elle dépend beaucoup de la structure du réseau mis en place. Son but est de déterminer les paramètres de chaque neurone pour obtenir le message de sortie voulu. Il existe un certain nombre de paramètres à ajuster : le poids des connexions entre neurones, la valeur de seuil qui lui est propre. Ces paramètres déterminent la fonction du message de chaque neurone, lorsqu’il arrive à la sortie : la fonction d’activation va en effet les prendre en compte et donner une valeur de sortie en fonction de ces paramètres. Un algorithme d’apprentissage est réalisé pour régler le réseau neuronal : on prend des valeurs que l’on connaît à titre d’exemple et on les teste jusqu’à l’obtention d’un résultat convenable. Lorsque l’algorithme atteint un état stable, la phase d’apprentissage est terminée.

Un réseau neuronal est donc une structure mathématique capable d’apprendre depuis un grand nombre d’exemples et de modéliser une série de relations. A chaque nouveau stimulus, c’est-à-dire a chaque fois que l’on envoie un signal aux premiers neurones d’entrée, le réseau propose une solution résultant des exemples qu’il a appris. Finalement un réseau de neurones reproduit un raisonnement mathématique tout simple : on part d’hypothèses connues pour arriver à une solution...

Applications, avantages et inconvénients

L’avantage des réseaux de neurones est qu’ils acceptent des données incomplètes voire incertaines. Ils présentent de plus une grande robustesse face aux défaillances techniques, et s’enrichissent de leurs expériences ; chaque nouvelle solution peut servir pour traiter un nouveau problème. Par contre leur architecture parallèle nécessite l’emploi de processeurs spécialisés pour accélérer les calculs : en effet la structure en couches est très complexe et plus le nombre de connexions entre neurones est important plus le message met de temps pour arriver à la sortie. De plus, il est nécessaire de passer par la phase d’apprentissage avant d’utiliser le réseau. Enfin il ne faut surtout pas penser qu’un réseau de neurones est capable d’égaler un cerveau humain, dont la structure est encore trop peu connue et trop complexe pour qu’on puisse la répliquer.

Les réseaux neuronaux ont été développés pour résoudre des problèmes de contrôle, de reconnaissance de formes ou de mots, de décision, de mémorisation... Ils sont couramment employés dans de nombreux programmes comme la reconnaissance vocale, et sont aussi utilisés pour les radars et les sonars, pour reconnaître des sons, des signaux.

Les Algorithmes Génétiques

Cette technique est basée sur la théorie de l’évolution de Darwin. A partir des données du problème, on crée une « population » de solutions possibles. Les caractéristiques de chaque solution représentent ses gènes. Puis, on évalue chacune des solutions. On élimine celles qui se sont montrées inutiles ou désastreuses, et on recombine les gènes des autres afin d’obtenir de nouveaux individus-solutions. Selon la théorie évolutionniste, cette nouvelle génération sera globalement plus adaptée au problème que la précédente. On réitère alors le procédé jusqu’à la naissance d’une solution que l’on jugera satisfaisante.

Fonctionnement

Structure

Un algorithme génétique a la structure suivante :

  • Initialiser le temps (t=0)
  • Créer une population initiale
  • Evaluer l’adaptation de chaque individu
  • Tant que (il n’y a pas de solution satisfaisante) et (le temps est inférieur au temps limite) alors :
    • Incrémenter le temps ( t = t + 1 )
    • Sélectionner les parents
    • Déterminer les gènes des nouveaux-nés par recombinaison des gènes parentaux
    • Faire subir des mutations aléatoires à la population
    • Evaluer l’adaptation de chaque individu
    • Sélectionner les survivants

Explication de chaque étape
  • Création de la population initiale : si on n’a aucune idée de la solution du problème, la population est générée aléatoirement. Sinon, on crée des individus qui représentent les solutions dont on dispose. Mais le principal problème est de choisir la taille de la population. Les biologistes ont introduits le concept de « diversité requise » pour représenter le fait que pour survivre, une espèce doit être suffisamment hétérogène. Par ailleurs, une population trop grande augmente le temps de calcul. Il faut donc trouver le bon compromis.
  • Evaluation de l’adaptation : afin de mesurer les « performances » de chaque individu, ont introduit une fonction d’adaptation. Cette fonction correspond au profit, à l’utilité de la solution par rapport au problème.
  • Sélection des parents : pour que la génération suivante soit plus performante, on doit faire s’accoupler les meilleurs individus. Chaque individu aura donc une chance proportionnelle à son adaptation de devenir parent.
  • Recombinaison (crossing-over) : afin de donner naissance à un nouvel individu, il ne suffit pas de copier le génome de l’un des parents, mais au contraire, de prendre aléatoirement quelques gênes de chacun des parents. Ce phénomène, présent dans la nature, est appelé crossing-over. Il s’agit d’un phénomène essentiel qui permet d’explorer l’ensemble des solutions possibles.
  • Mutation : les mutations sont des modifications aléatoires du génome. Bien sûr, il ne faut pas muter tous les gênes d’un individu, sinon il serait déterminé entièrement aléatoirement. Il faut au contraire en modifier une petite partie, afin d’apporter quelque chose de nouveau à l’individu. Mais la mutation a un rôle secondaire par rapport à la recombinaison, et on lui attribue en général une faible probabilité (de l’ordre 1/1000).
  • Sélection des survivants : cette étape consiste à ne garder que les solutions les plus intéressantes, tout en gardant une population assez grande et assez diversifiée. On choisit en général de conserver la taille d’une population d’une génération à l’autre. Il y aura donc autant de « morts » que de « nouveaux-nés ». Parfois, on choisit de garder seulement les «enfants ». Cela assure la diversité et de l’évolution de la population.

Avantages et Inconvénients

Le grand avantage des algorithmes génétiques est le fait que pour parvenir au résultat, on n’a pas besoin de connaître les caractéristiques de la solution du problème, mais seulement de déterminer parmi deux solutions quelle est la meilleure. Par contre ce genre d’algorithme est très couteux en temps de calcul, difficile à programmer (les paramètres comme la taille de la population et la fonction d’adaptation sont difficiles à établir), et il n’a qu’une très faible chance, voire aucune, de trouver la solution idéale, il ne fait qu’en approcher.

Exemples d’application : les algorithmes génétiques sont utilisés pour dessiner des ailes d’avions efficaces. L’algorithme va définir une aile comme une chaîne de variables (la taille, le poids, la forme…) et créer des centaines de milliers de modèles d’ailes artificielles, tester chacun de ces modèles pour déterminer lesquels sont conformes aux performances désirées puis les sélectionner en ne laissant « survivre » que les solutions les plus aptes aux nécessités de l’avion à construire.

L’intelligence des jeux

L’Homme contre l’ordinateur

Le 11 mai 1997, Garry Kasparov alors indiscutable numéro un mondial aux échecs, est battu par l'ordinateur Deeper Blue. Cette défaite résonna comme celle de l'Homme face à l'ordinateur. Bien que Gary Kasparov ait pris sa revanche quelque temps après, les programmes d'échecs ont évolué et, en décembre 2006, Deep Fritz, un nouvel ordinateur, bat le numéro trois mondial Vladimir Kramnik. La domination des programmes informatiques aux échecs est alors totale.


Garry Kasparov lors de sa défaite contre Deeper Blue. Prise de tête?

L'ordinateur est-il devenu plus intelligent que son créateur? Pas encore! Il reste encore un jeu de réflexion où les humains dominent largement les ordinateurs: le jeu de go. Ce jeu viendrait de Chine et daterait d'il y a plus de 4000 ans mais la plus ancienne référence écrite au jeu de go date de 548 av J-C. On compte aujourd'hui plus de 40 millions de joueurs à travers la planète et des compétitions prestigieuses sont organisées régulièrement et sont largement dotées. Les prix des plus prestigieuses de ces compétitions atteignent les mêmes montants que ceux de Roland Garros.

La complexité de certains jeux

Le go est un jeu de logique qui se joue sur une grille de 19*19 intersections. Deux joueurs, les noirs et les blancs, posent chacun à leur tour un jeton sur une intersection de la grille libre. Deux pierres de mêmes couleurs situées sur des intersections adjacentes sont dites connectées et les pierres connectées forment alors une chaîne. Les intersections libres et adjacentes à une chaîne sont appelées liberté de la chaîne. Lorsque toutes les libertés sont occupées par des jetons adverses, la chaîne est enlevée du plateau. Le but du jeu est d'occuper le plus de territoire, c’est-à-dire des intersections libres délimitées par des pierres de même couleur. À la fin de la partie, le vainqueur est celui qui possède le plus de territoire.


Jeu de Go

Aujourd'hui, le go a pris la place des échecs comme terrain d'affrontement entre l'homme et la machine. Les meilleurs programmes de go atteignent seulement le niveau d'un amateur humain moyen.

Après avoir examiné les méthodes classiques utilisées par les ordinateurs pour jouer au go ou à d’autres jeux de logique, et les limites de ces méthodes, nous verrons que l'approche proposée par des professionnels, fondée sur les notions de hasard et de probabilité, a permis ce progrès. Le go, les échecs, les dames ou encore le morpion sont des jeux finis. C’est-à-dire qu’il existe une stratégie optimale qui permet de jouer au mieux en fonction des répliques de l’adversaire. Il suffirait donc en théorie d’étudier tous les coups possibles jusqu'à la fin de la partie et ensuite de suivre la séquence de coups qui mènerait à une partie victorieuse ; si une telle séquence existait, ce qui n’est prouvé ni pour les échecs, ni pour le jeu de go. En effet, la richesse combinatoire du jeu de go est gigantesque : il existe 361 possibilités pour poser la première pierre, 360 pour la deuxième et ainsi de suite… Le nombre total de positions possibles à ce jeu est de l’ordre de 10170 ! Par comparaison le nombre de positions possibles est de l’ordre de 106 au morpion et « seulement » 1050 aux échecs. L’exploration par calculs des parties possibles est aujourd’hui hors de portée des ordinateurs. Les programmes doivent donc se contenter d’analyser les coups possibles jusqu'à une profondeur limitée, qui dépend des ressources de calculs de l’ordinateur.

La recherche des meilleurs coups par la machine

On représente souvent les calculs par un arbre, la racine représentant la position actuelle, les feuilles les positions résultantes après les séquences de coups explorées, qui sont représentées par les branches, et les nœuds de l’arbre étant les coups intermédiaires.


Un exemple d’arbre.

Un programme informatique dispose de deux outils pour déterminer le meilleur coup possible. Le premier est une fonction dite heuristique, qui intègre en général des connaissances de jeu acquises par des humains, et calcule de façon approchée le nombre de positions possibles. Le second outil est un algorithme de recherche arborescente. Il calcule, à partir des valeurs des positions atteintes après l’exploration par l’heuristique, la valeur de la position en cours (la racine) et les valeurs des positions intermédiaires. Le meilleur coup est celui qui conduit au nœud de la plus grande valeur qui succède immédiatement à la racine. La première difficulté concerne l’évaluation d’une position. Une fonction heuristique doit rendre compte à la fois des attributs locaux (tactiques, à court terme) et globaux (stratégiques, à long terme) de la position. Aux échecs, ces deux niveaux sont relativement imbriqués, car les interactions d’un petit groupe de pièces influent directement sur la situation globale du jeu. En revanche, au go, le lien entre l’échelon tactique et le niveau stratégique est moins direct. Les connaissances tactiques et stratégiques élaborées par les experts du jeu de go sont moins nombreuses et plus difficiles à mettre en œuvre que dans le cas des échecs. En conséquence, les fonctions heuristiques développées pour le jeu de go sont encore très imprécises et gourmandes et temps de calcul. Le second écueil est la complexité combinatoire. Dans une position de go quelconque, il existe en moyenne de l’ordre de 200 coups possibles contre environ 40 aux échecs. L’arbre est donc plus grand, plus dense, le nombre de feuilles est beaucoup plus élevé. Dans les deux cas, le nombre de feuilles de l’arbre croit exponentiellement avec sa profondeur, mais avec un exposant de 200 pour le go contre 40 pour les échecs. Quatre coups seulement peuvent ainsi mener à environ 1,5 milliard de position différentes. Le temps de calculs devient très vite colossal avec la profondeur de l’analyse. En pratique, la complexité du go est telle que les méthodes usuelles de recherche arborescente ne permettent pas d’aller au-delà d’une profondeur de trois à quatre coups, contre une dizaine aux échecs. Or la profondeur d’analyse requise pour déterminer un coup de go est souvent très élevée. Alors qu’aux échecs, il est rare de devoir calculer plus d’un dizaine de coups à l’avance pour explorer une combinaison précise, certaines situations du jeu de go doivent être explorées dans plusieurs direction pendant plus de 30 coups avant qu’une évolution ne se dessine clairement. Compte tenu de toutes ces difficultés, il n’est pas étonnant que les performances des programmes soient décevantes.

Les atouts de l’Homme

Mais pour un humain au contraire, il est très facile d’évaluer une situation sur le goban (table de jeu pour le go). En effet, notre système visuel très performant, configuré pour identifier les formes et les régularités, est particulièrement adapté pour appréhender les motifs à grandes échelles formés par les chaînes de pierres sur le goban, ainsi que pour en compléter les lacunes ou pour en prolonger le développement en pensée. Quelques pierres suffisent à notre cerveau pour imaginer le territoire qu’elles délimitent. Dans une moindre part, cette vision géométrique est aussi l’un des atouts des grands maîtres d’échec, mais elle est alors moins naturelle. Ainsi, malgré des capacités de calcul formel limitées, les joueurs humains ont une capacité d’anticipation supérieure à celle des programmes informatiques. Contrairement aux joueurs d’échec, les joueurs professionnels de go restent aujourd’hui invaincus face aux ordinateurs comme Goemate, Go++.

Les nouvelles voies explorées

Cependant les programmes de Go ont progressé durant les dernières années, autant dans le domaine des heuristiques que dans celui de la recherche arborescente. Bernd Bruegmann, de l’université de Californie à San Francisco, a eu l’idée d’utiliser des techniques aléatoires, c’est la technique Monte-Carlo. Le principe de cette technique est d’utiliser le hasard pour simuler plusieurs réalisations d’une quantité que l’on souhaite évaluer, et ensuite prendre la moyenne de ces réalisations. Au go, évaluer une position via une simulation Monte-Carlo consiste, dans la version la plus simple, à terminer la partie en jouant des coups au hasard. Seuls les coups intrinsèquement mauvais sont proscrits. L’heuristique fondée sur les simulations Monte-Carlo présente de nombreux avantages par rapport à celles fondées sur les connaissances expertes. Ne nécessitant des connaissances de jeu que très sommaires, elle est facile à implanter. Autre conséquence de cette simplicité, elle est peu gourmande en temps de calcul : elle réalise 5000 évaluations globales par seconde contre environ 200 pour une heuristique classique (même si celle-ci peut analyser des situations tactiques limitées à un rythme 1000 fois plus élevé). En outre, cette méthode prend en compte à la fois le caractère global et le caractère local d’une position. Seul point faible, l’heuristique Monte-Carlo est d’autant moins performante que la fin de la partie est éloignée. Chaque coup joué dans la simulation augmente ou diminue en effet aléatoirement la valeur de la position, de sorte que plus on enchaîne de coups, plus les probabilités de dévier par rapport à la valeur réelle de la position sont élevées. L’évaluation par Monte-Carlo s’est révélée très efficace. Il peut sembler étonnant qu’introduire le hasard dans un jeu totalement déterministe donne d’aussi bons résultats. C’est pourtant ce que nous faisons tous les jours lorsque nous devons résoudre des problèmes de nature déterminisme dont l’analyse est trop complexe. Le hasard est aussi derrière les progrès réalisés en matière d'algorithme de recherche arborescente. Un tel compromis apparaît dans de nombreuses disciplines mêlant apprentissage et optimisation.

Homme et ordinateur, l'écart se resserre.

Depuis les années 1980, des confrontations entre programmes de jeu de go sont organisées pour encourager les recherches dans ce domaine et évaluer les progrès accomplis. Les olympiades informatiques qui se tiennent tous les quatre ans comportent ainsi un tournoi de go. Sur internet, des serveurs permettent de faire jouer des programmes et des joueurs humains ensemble sur différentes tailles de goban, et d'établir des classements. Chaque mois, sur le serveur KGS, un tournoi de logiciels est organisé. Pour la première fois, les humains ont du souci à se faire quant à la montée de la méthode Monte-Carlo. En raison du niveau limité des programmes actuels, les joueurs de go professionnel se sentent à l'abri de toute menace pour encore de nombreuses années encore. Combien de temps ce sentiment de sûreté va-t-il durer ? Le chemin est encore long, mais la marge de progression pour des techniques aussi récentes est élevée. Et les ordinateurs ont tout leur temps pour améliorer leur intelligence de jeu...

Partie suivante : Pourquoi ces limites à l'intelligence artificielle ?