Courte histoire
de l'IA

- Master Informatique -
Université du Havre

Damien Olivier / LITIS

Survol historique

Chronologie des avancées de l'IA

Des premiers propos - 1948

En réponse à une présentation lors d'un congrés comme quoi il était impossibe qu'une machine pense.
“You insist that there is something a machine cannot do. If you will tell me precisely what it is that a machine cannot do, then I can always make a machine which will do just that!”
Von Newman
Référence à la thèse de Church-Turing.

Un début discret - 1949

  • Claude Shannon exprime comment un ordinateur pourrait jouer aux échecs
“The chess machine is an ideal one to start with, since: (1) the problem is sharply defined both in allowed operations (the moves) and in the ultimate goal (checkmate); (2) it is neither so simple as to be trivial nor too difficult for satisfactory solution; (3) chess is generally considered to require ‘thinking’ for skillful play; a solution of this problem will force us either to admit the possibility of a mechanized thinking or to further restrict our concept of ‘thinking’; (4) the discrete structure of chess fits well into the digital nature of modern computers. … It is clear then that the problem is not that of designing a machine to play perfect chess (which is quite impractical) nor one which merely plays legal chess (which is trivial). We would like to play a skillful game, perhaps comparable to that of a good human player.”

Un début discret - 1949

  • Basée sur des états ;
  • Idée de Shannon : Minimax (Th. Von Neumann 1928) ;
  • Basée sur une exploration exhaustive ;
  • Arbre de jeu ;
  • Fonction d'évaluation.

Problème : explosion combinatoire


MinMax
Arbre MinMax.

Le test de Turing - 1950

  • Jeu de l'imitation, nom : test de Turing inventé par A.C. Clarke 2001 l'Odyssée de l'espace ;
  • A rapprocher de la cinquième partie du Discours de la méthode de Descartes :
    • Imaginons un automate fabriqué par un artisan doué d'une habileté supérieure, et imitant parfaitement l'apparence et le comportement d'un être humain ; nous aurions toujours, soutient Descartes, deux moyens de ne pas confondre cet automate avec un homme véritable : la parole et l'action réfléchie.
  • Présenté et discuté ailleurs dans le cours.

TuroChamp - 1951


  • Programme proposé par Alan Turing ;
  • Considéré comme le premier programme de jeu d'échec ;
  • Non implanté à l'époque car nécessitant trop de mémoire ;
  • Turing l'a exécuté manuellement et

    il a perdu !


MinMax
Alan Turing

Georgetown-IBM expérience - 1954

  • Traduction automatique ;
  • 60 phrases en russe vers l'anglais ;
  • Approche lexicographique ;
  • Mi pyeryedayem mislyi posryedstvom ryechyi. We transmit thoughts by means of speech. Nous transmettons des pensées par la parole.

La naissance de l'IA - 1956


  • Congrès de Datmouth ;
    • Organisé par Marvin Minsky, John McCarthy, Claude Shannon et Nathan Rochester ;
    • Participants : Ray Solomonoff, Oliver Selfridge, Trenchard More, Arthur Samuel, Allen Newell et Herbert A. Simon ;
    • Démonstration par Newell et Simon de "Logic Theorist" ;
    • McCarthy propose "Artificial Intelligence" comme nom du champ scientifique.

“Every aspect of learning or any other feature of intelligence can be so precisely described that a machine can be made to simulate it.”

La théorie devient du code - 1956


  • Idée de Samuel : l'apprentissage ;
  • Basé sur Minimax ;
  • Le programme devient meilleur au fil du temps sans intervention humaine,
    • "Rote-learning" (par coeur), stocke les valeurs de certaines positions précédemment évaluée avec Minimax ;
    • "Apprentissage par la généralisation", modif de la fonction d'évaluation en fonction de résultat d'ancienne partie.
MinMax
Apprentissage par coeur

Logic theorist - 1956


  • Allen Newell, Hebert A. Simon et Cliff Shaw ;
  • Construction d'un arbre de recherche ;
  • Démonstration de thèorème ;
  • A démontré 38 des 52 théorèmes de "Principia Mathématica (ch2)" ;
  • A fourni une démonstration plus élégante d'un des théorèmes" ;
Principia Mathematica
Principia Mathematica

    General Problem Solver - 1957

  • Allen Newell, Hebert A. Simon et Cliff Shaw ;
  • Basé sur les clauses de Horn, logique des prédicats ;
  • Notion d'heuristique ;
  • Proche des systèmes de production, préfigure les systèmes experts.

Programmation symbolique - 1958

  • LISP (LISt Processing) - McCarthy ;
  • Langage d'abord fonctionnel ;
  • Basé sur le lambda calcul ;
  • Syntaxe parenthésée sous forme de S-expression ;
  • Permet la métaprogrammation, programmes qui se modifient ;

(defun factorial (n)
  (if (= n 0) 1
      (* n (factorial (- n 1)))))

John McCarthy
John McCarthy

Réseau de neurones - 1958


  • Le perceptron - Frank Rosenblat à partir des travaux de McCulloch et Pitts + Hebbs ;
  • Inspiré du système visuel ;
  • Capable d'apprentissage par correction d'erreur en modifiant les poids des signaux ;
  • En 69 Minsky et Papert montrent que le perceptron ne peut pas faire de OU exclusif ;
  • => Pas de pb non linéaire ;
  • Oublié jusqu'en 1982, renaît avec Hopfield.
John McCarthy
John McCarthy
  • une couche de cellules d’association, neurones formels ;
  • Une couche d’unités sensorielles ;
  • une couche de cellules de décisions, sortie du perceptron.

Les programmes commencent à gagner - 1958

  • Performance modeste ;
  • Gagne face à des débutants ;
  • Amélioration de MiniMax avec la coupure alpha/beta ;
  • Permet d'augmenter la profondeur de recherche.
Coupure alapha,beta
Coupure alapha,beta

Geometry theorem proving machine - 1959

  • Herbert Gelernter (IBM) ;
  • Fonctionnement en arrière, on part du but et on remonte ;
  • Première démonstration géométrique considérée comme plus élégante que celles des manuels scolaires ;
  • Abandonné par IBM.
« Dans un triangle, l’angle B est égal à l’angle C. Démontrez que le côté AB est égal au côté BC »
Démonstration non pas en considérant les deux sous-triangles découpés par la hauteur
« Considérons les triangles ABC et ACB : ces deux triangles sont semblables et possèdent des côtés correspondants BC et CB égaux. Ils sont donc égaux et AB est en conséquence égal à BC »

Intégration - 1961

  • Utilise la méthodologie de Logic Theorist ;
  • Exploration d'arbres ET/OU ;
  • Donnera naissance à MACSYMA (69), puis Maxima ou Mathematica.

Algorithme d'unification - 1965

  • Généralise le modus ponens ;
  • Robinson ;
  • Règle d'inférence utilisée en logique du premier ordre ;
  • Utilisé par Prolog.

ELIZA - 1965

  • Joseph Weizenbaum ;
  • Simule un psychothérapeute rogérien ;
  • Reformule les affirmations en questions.
ELIZA
ELIZA

Dendral - 1965

  • Edward Feigenbaum, Bruce Buchanan, Joshua Lederberg (médecin) et Carl Djerassi (chimiste) ;
  • Premier système expert ;
  • Identification des constituants chimiques d'un matériau à partir de spectrométrie de masse et de résonance magnétique nucléaire ;
  • Écrit en LISP ;
  • La première version mélangeait connaissance et traitement ;
  • Ensuite META-Dendral.

Mac Hack - 1968

  • Richard D. Greenblatt MIT ;
  • Machine-Aided Cognition ;
  • Premier programme d'échec à jouer dans des tournois (humains) ;
  • Premier à avoir un classement ;
  • Premier à gagner en tournoi contre des joueurs classés.
Mac Hack
Mac Hack

Le tour du Go - 1968

John McCarthy
John McCarthy

Jeu de GO - 1968

  • Difficile d'utiliser un arbre de recherche (explosion combinatoire) ;
  • Représentation proche de celle d'un joueur ;
  • Recherche de forme ;
  • Utilisation d'une fonction de hachage ;
  • Idée d'Alfred Zobrist dans son PhD.
Les patterns vus par Zobrist
Les patterns vus par Zobrist

Shakey the robot - 1969

  • Premier robot capable de raisonner sur ses actions ;
  • Transformée de Hough (reconnaissance de ligne) ;
  • Algorithme A* ;
  • Graphe de visibilité (sommets accessibles).
Le robot Shakey
Le robot Shakey

Publication de perceptrons - 1969

  • Marvin Minsky et Seymour Papert ;
  • Démontre l'intérêt du perceptron ;
  • MAIS montre que l’algorithme du perceptron ne converge que si les classes sont linéairement séparables ;
  • Annonce l'hiver de l'IA jusqu'en ~ 80
Frontière de discrimination non linéaire
Frontière de discrimination non linéaire

SHRDLU et les micro-mondes - 1970

  • Un des premiers programmes informatiques de compréhension du langage naturel  ;
  • Terry Winograd au MIT ;
  • Écrit en Micro Planner et en Lisp  ;
  • Monde des blocs ;
Personne : Prends un gros bloc rouge.
SHRDLU : OK.
Personne : Attrape la pyramide.
SHRDLU : Je ne comprends pas de quelle pyramide
vous parlez.
Personne (changeant d’avis) : Trouve un bloc
plus grand que celui que tu tiens et mets-le dans la boîte.
SHRDLU : Par « le », je suppose que vous voulez dire
« le bloc plus grand que celui que je tiens ».
SHRDLU : OK.
Personne : Que contient la boîte ?
SHRDLU : La pyramide bleue et le bloc.
Le monde des blocs
Le monde des blocs

Prolog - 1972

  • A. Colmerauer et P. Roussel, Marseille ;
  • PROgrammation LOGique ;
  • Basé sur le calcul des prédicats du premier ordre ;
  • Unification, récursivité et retour sur trace ;
  • Négation (plus tard).

parent(jorge, andres).
parent(andres, felipe).

grandparent(X,Y) :- parent(X, Z), parent(Z, Y).

? grandparent(jorge,_).
%true
%il y a assez d'information pour dire
%que jorge a un grandparent connu.

%Hypothèse du monde clos → il n'y a pas assez d'information
%pour arriver à une conclusion -> false
? grandparent(andres,_).
%false
%Négation par l'échec appuyé sur l'hypothèse du monde clos
? not(grandparent(andres,_)).
%true

MYCIN - 1974

  • Ted Shortliffe ;
  • Système expert à base de règle en présence d'incertain ;
  • Coefficients de vraissemblance ;
  • Donnait dans 69% des cas la bonne thérapie ;
  • Meilleurs résultats que les experts du domaine.
$$ {\displaystyle CF(x,y)={\begin{cases}X+Y-XY\ \ \ X,Y>0\\X+Y+XY\ \ \ X,Y<0\\(X+Y)/(1-min(|X|,|Y|))\ \ \ sinon\end{cases}}} $$

Les frames (cadres) - 1975

  • Marvin Minski ;
  • Part du constat qu'il est difficile de rprésenter des choses simples comme une chaise en logique ;
  • Schank parle d'approches alogiques ou brouillonnes ;
  • Opposition aux paradigmes dit élégants, comme LISP, PROLOG ...
  • Frame : englobe toutes des hypothèses de culture générale d'un thème donné, mais
    • Les faits ne sont pas toujours vrais ;
    • les déductions à partir de ces faits ne sont pas toutes logiques.
  • Origine des langages orientés objets ?
Les informations sont stockées dans un slot. Elles contiennent :
  • Les faits ou les données
    • Valeurs (facettes)
  • Les procédures
    • IF-NEEDED
    • IF-ADDED
  • Valeurs par défaut
    • Pour les données
    • Pour les procédures
  • D'autres frames

Prix Nobel - 1978

  • Hebert Simon ;
  • Prix Nobel d'économie ;
  • Rationalité limitée ;
  • Satisficing : satisfying (satisfaisant) et sufficing (suffisant) ;
  • Solution "suffisamment bonne" plutôt "qu'optimale" si l'exploration de toutes les alternatives "coûte trop cher".

Backgammon - 1979

  • Hans Berliner ;
  • Utilise la logique floue ;
  • La victoire 7-1 était due à en partie de la chance ;
    • BKG
    BKG

    Logique non monotone - 1979

    • McDermott, Jon Doyle et John McCarthy ;
    • Raisonnement non monotone :
      • Tout raisonnement qui permet d'établir des conclusions qui pourront être invalidées en présence de nouvelles informations ;
      • Conclusion basées sur à la fois la présence d'information et l'absence ;
      • Si je sais A en l'absence de B je peux déduire C.

    Stanford Cart - 1979

    • Hans Moravec, MIT ;
    • Premier véhicule autonome évitant des obstacles.

    Machines LISP - 1980

    • Initiés par Richard Greenblatt et Thomas Knight en 73 ;
    • Noftsker et Greenblatt ;
    • Début de la commercialisation ;
    Machine LISP
    Machine LISP

    Machine de 5ème génération - 1981

    • Lampes (1), transistors et diodes (2), circuits intégrés (3), microprocesseurs (4) ;
    • Projet Japonais, ordinateur massivement parallèle ;
    • Basé sur Prolog ;
    • Projet Alvey (GB) en réaction.

    Réseau de neurone de Hopfield - 1982

    • Réseau récurrent : systèmes dynamiques constitués de neurones interconnectés interagissant non-linéairement ;
    • Asynchrone : un seul neurone est mis à jour à chaque unité de temps ;
    • Chaque neurone est connecté à tous les autres ;
    • Un neurone ne possède ni couche d’entrée, ni couche de sortie ;
    • Les neurones ont un état binaire.
    Neurone de Hopfield
    Neurone de Hopfield

    Algèbre d'intervalle - 1983

    • Proposés par Allen ;
    • Permet des raisonnements spatio-temporels ;
    • Définit les relations possibles entre des intervalles de temps ;
    • Propose une table de composition.
    x < y x se déroule avant y
    x M y x rencontre y (meet)
    x O y x rencontre y (overlap)
    x S y x démarre y (start)
    x D y x se déroule pendant y (during)
    x F y x termine y (finish)
    x = y x se déroule avant y

    Les réseaux de neurones reviennent - 1984

    • Réseau dynamique, réseau de Hopfield (82) ;
    • Carte auto-adaptatrice de Kohonen (84) ;
    • Apprentissage supervisé avec l'algorithme de rétropropagation du gardient ;
    • On commence à parler d'apprentissage profond (Lecun).

    Voiture autonome - 1986

    • Ernst Dickmanns (Munich) ;
    • Dans des rues vides ;
    • 55 mph ~88 km/h.

    Société de l'esprit - 1986

    • Marvin Minsky ;
    • Esprit = architecture d'agents élémentaires, indépendants, mais surtout hiérarchisés ;
    • Agents :
      • Les plus courants, les K-lines, agent de mémoire à court terme servant à activer d'autres agents ;
      • Les nèmes représentent les connaissanxes ;
      • Les nomes traitent les connaissances ;
      • Les polynèmes permettent d'activer des agents représentant des aspects différents d'un même objet ;
      • Les paranomes permettent de manipuler simultanément différents modes de représentations des connaissances. ;
    • Les agents de base se combinent pour générer des actions complexes ;
    • Cerveau A = esprit, cerveau B contrôle le cerveau A.
    Société de l'esprit
    Société de l'esprit

    Architecture de subsomption - 1986

    • R. Brooks pour de la robotique ;
    • Couches hiérarchisées, les plus hautes sont plus prioritaires ;
    • Plusieurs modules, chaque module étant responsable de la réalisation d'une tâche simple ;
    • Les couches hautes sont les plus abstraites.
    Architecture de subsomption
    Architecture de subsomption

    Le second hiver de l'IA - 1987

    • De 1987 à 1993 ;
    • Les machines dédiées sont de moins en moins utilisées ;
    • Les systèmes experts ont un coût de maintenance trop élevé ;
    • Les objectifs des ordinateurs de 5ème génération ne sont pas atteints.

    Le début de la fin pour les humains - 1989

    • Sauf pour le Go ;
    • Deux orientations  :
      1. Les ordinateurs deviennent plus puissant ;
        • Une base de données d'ouverture ;
        • Alpha-beta avec une fonction d'évaluation au petit oignon ;
        • Une base de données de données de fin de partie ;
        • -> Chinook (Dame), Deep Thought fonction d'évaluation apprise(Echec).
      2. Apprentissage par renforcement ;
        • Neurogammon, pas très bon au début !

    Agents - 1990

    • Entité autonome qui perçoit par capteurs un environnement et agit par des actionneurs sur celui-ci
    • Il tend à atteindre un but ;
    • Il peut apprendre ou utiliser des connaissances éventuellement ;
    • Judea Pearl, Allen Newell pour les formes modernes.
    Agent réactif
    Agent réactif
    Agent cognitif
    Agent cognitif

    DART - 1991

    • Dynamic Analysis and Replanning Tool ;
    • Utilise des agents intelligents ;
    • Planification dynamique ;
    • Utilisé pendant la première guerre du golfe ;
    • Logistique militaire.

    TD-Gammon - 1992

    • Gerald Tesauro (IBM) ;
    • Réseau de neurones ;
    • Apprentissage par renforcement (Temporal Difference learning) ;
    • Apprend en jouant contre des versions antérieures de lui-même ;
    • Niveau de jeu légèrement inférieur aux meilleurs joueurs ;
    • Trouve des nouvelles stratégies ;
    • -> conduit à des progrès dans le jeu  !
    TD-Gammon
    TD-Gammon

    CHINOOK - 1994

    • Jonathan Schaeffer ;
    • Jeu de dame ;
    • Premier programme informatique à avoir gagné le titre de champion du monde dans une compétition d'un jeu de stratégie ;
    • En 90 participe au championnat du monde, 2ème ;
    • En 94 il est champion du monde ;
    • En 2007 papier "Checkers Is Solved" par Schaeffer et al ;
    • Meilleur résultat possible si deux joueurs jouent optimalement = partie nulle.
    Chinook
    Chinook

    DEEP BLUE - 1997

    • IBM ;
    • Deep Thought x Big Blue = Deep Blue ;
    • En 96 perd 4 à 2 ;
    • En 97 gagne 3,5–2,5 ;
    • Evalue 200 millions de positions par seconde ;
    • La victoire serait due à un bug !
    • Mais en 2006 Deep Fritz vs. Vladimir Kramnik sur un PC 2 Intel Core 2 Duo, 8 millions positions par second, 4 à 2.
    Kasparov vs. Deep Blue
    Kasparov vs. Deep Blue

    Logistello - 1997

    • Michael Buro ;
    • Bat le champion du monde Takeshi Murakami 6–0.
    Logistello
    Logistello

    AIBO - 1999

    • AIBO (Artificial Intelligent RoBOt) homonyme de 相棒 du japonais "compagnon", Sony ;
    • Robots autonomes et pouvant apprendre en fonction de stimuli provenant de l'environnement ou d'autres AIBO ;
    • Abandonné en 2007 par Sony.
    AIBO 1er proto
    AIBO 1er proto
    AIBO 1er proto

    L'IA est remplacée par le smart ! - 2000 ...

    • L'IA a envahi beaucoup de domaine spécifique ;
    • HAL n'est pas là, mais .... ;
      • Le smart : smart toys, smartphones, smart cities .... ;
      • L'intelligence computationnelle  :
        • Réseaux de neurones ;
        • La logique floue et d'autres ;
        • Les algorithmes évolutionnistes (algorithmes génétiques et programmation génétique ;
        • L'Intelligence collective. ;
    • Les robots arrivent ;
    • On commence a parler de singularité.

    ROOMBA - 2004

    • Socité iRobot ;
    • Aspirateur ;
    • Se recharge seul ;
    • Se déplace et evite les obstacles.
    Roomba
    Time lapse de Roomba

    Spirit et Opportunity 2004

    • NASA et Caltech ;
    • Navigation autonome à la surface de Mars ;
    • Amarssissage : 4/01/2004 et 25/01/2004 ;
    • 25 mai 2011 ensablage de Spirit ;
    • Opportunity roule encore (15/11/16) ;
    • Le (27/06/16) 42.85 km.
    Opportunity
    Opportunity

    DARPA Grand Challenge 2004

    • DARPA, Defense Advanced Research Projects Agency ;
    • 2004 et 2005 Désert des Mojaves, 2007 parcours urbain ;
    • Déplacement de manière autonome ;
    • Moins de 10 heures pour le parcours ;
    • Positionnement GPS et d'autres signaux disponibles pour les civils ;
    • Fonctionnement entièrement autonome.
    DARPA

    ASIMO - 2005

    • Honda ;
    • Advanced Step in Innovative Mobility, « ashimo » (des jambes aussi) en japonais ;
    • Mémoire ;
    • Capacités de calcul ;
    • Identification des objets mobiles ;
    • Identification des gestes ;
    • Possibilité de serrer la main d'une personne quand celle-ci le sollicite, tout en gérant sa force ;
    • Reconnaissance vocale (possibilité de distinguer les voix et les bruits parasites) ;
    • Reconnaissance des visages et des êtres humains (suivre une personne, saluer une personne qui s'approche, s'adresser à une personne par son nom) ;
    Première version ASIMO
    Première version ASIMO

    Google car - 2009

    • Sebastian Thrun, père de Google Street View ;
    • Puis Chris Urmson, vainqueur challenge DARPA en 2007 (Carnegie Mellon) ;
    • Deux types de véhicules autonomes :
      • Des véhicules de série modifiés par Google ;
      • Des véhicules électriques et autonomes entièrement conçus par Google ;

    WATSON - 2011

    • IBM - DeepQA research project ;
    • Répondre à des questions formulées en langage naturel ;
    • Remporte le jeu Jeopardy, face à 2 champions (+ 100 victoires) ;
    • "Comprend" l’énoncé des questions ;
    • Buzze pour prendre la main ;
    • Trouve les réponses en quelques secondes ;
    • Choisit le thème et la mise ;
    • Problème ouvert contrairement au échec !! ;
    • Passe t-il le test de Turing ?
    Jeopardy
    16/02/2011 Jeopardy

    Assistant personnel intelligent - 2011

    • Reconnaissance vocale ;
    • Traitement du langage naturel ;
    • Synthèse vocale ;
    • Siri (Apple), Google Now, Cortana (Microsoft) ;
    • Vers la vie digitale ??

    Autonomous Weapons - 2015

    Deep Mind DQN - 2015

    • Google ;
    • Réseau de neurone profond et apprentissage par renforcement ;
    • Jeu sur Atari ~ 1980, Pong, pacman...
    • Algorithme capable d’apprendre directement de ses expériences ;
    • Très bons résultats, mais encore des pb sur les planifications longues.

    Deep Mind AlphaGo - 2015

    • Jeu de Go ;
    • Gagne contre le champion d'Europe ;
    • Basé sur un arbre de recherche de Monté-carlo ;
    • Utilise un réseau de neurone profond et de l'apprentissage par renforcement ;
    • Apprendre à explorer les parties intéressantes de l'arbre ;
    • Apprendre à évaluer le l'état du goban.

    Deep Mind AlphaGo - 2016

    • Bat Lee Sedol ;
    • Triomphe de l'apprentissage profond ?