Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours IA (A. Cornuéjols) Introduction à lintelligence artificielle Antoine Cor

Cours IA (A. Cornuéjols) Introduction à lintelligence artificielle Antoine Cornuéjols AgroParisTech antoine.cornuejols@agroparistech.fr http://www.agroparistech.fr/ufr-info/membres/cornuejols/introduction.html 2/57 Cours IA (A. Cornuéjols) Organisation m 4 séances de 3h (cours + TD/TP) m Programme et références sur : http://www.agroparistech.fr/ufr-info/membres/cornuejols/Teaching/AGRO/Cours-IA/ iodaa-cours-IA.html m Contrôle continu : ❏ 2 DMs ❏ Quizz (10) ❏ Mini-Projet commun avec programmation et optimisation 3/57 Cours IA (A. Cornuéjols) Plan 1- Introduc)on à lIA ; Résolu.on de problèmes par explora)on de graphes 2- Résolu.on de problèmes en environnement non déterministe (avec adversaire) 3- Appren)ssage par renforcement 4- Planiﬁca)on. Formalisme STRIPS. Autres méthodes 5- Bayesian reasoning 6- Bayesian networks 7- HMM and Co 4/57 Cours IA (A. Cornuéjols) Plan du cours n°1 1- Introduction à lIA 1.1- Cest quoi lintelligence ? 1.2- Comment étudier lintelligence ? 5/57 Cours IA (A. Cornuéjols) Exemple : jeux ➥ Prise de décision 6/57 Cours IA (A. Cornuéjols) Exemple : robotique ➥ Perception ➥ Prise de décision ➥ Action ➥ Communication ➥ Apprentissage 7/57 Cours IA (A. Cornuéjols) Exemple : robotique m Projet COG au MIT 8/57 Cours IA (A. Cornuéjols) Exemple : robotique (3) m Analyse et interprétation de scène 9/57 Cours IA (A. Cornuéjols) Exemple : Analyse des flux de polluants Projet ONU m Capteurs disséminés m Aspects spatial et temporel m Analyse de documents sur le web m Objectifs : ❏ Prédiction ❏ Compréhension 10/57 Cours IA (A. Cornuéjols) Exemple : « intelligence ambiante» Action européenne (Kdubiq) m Omniprésence dobjets « intelligents » m Percevant leur environnement m Communiquant entre eux m Prenant des décisions m Objectifs : ❏ Aide aux usagers ❏ … § Rationalité limitée § Bande passante limitée § Environnements changeants § Apprentissage 11/57 Cours IA (A. Cornuéjols) Exemple : Systèmes ubiquitaires « intelligents » Applications m Domotique m Aide aux personnes handicapées m Station orbitale m … 12/57 Cours IA (A. Cornuéjols) Les manifestations de la cognition m Discrimination m Adaptation m Perception / associations / analogies / métaphores m Communication m Planification m Apprentissage et découverte 13/57 Cours IA (A. Cornuéjols) Quest-ce que lIA ? « The study of the conjecture that every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it. » Dartmouth Workshop, Summer of 1956 14/57 Cours IA (A. Cornuéjols) Quest-ce que lintelligence artificielle ? 15/57 Cours IA (A. Cornuéjols) Objectifs de lIA ? m Construire des machines pour une large variété dapplications augmentant les capacités de résolution de problèmes « mal posés » m Formaliser ce quest la connaissance m Mécaniser lintelligence m Utiliser des modèles computationnels pour comprendre des comportements complexes m Rendre linteraction avec les systèmes computationnels aussi simple quavec les humains 16/57 Cours IA (A. Cornuéjols) Sources de difficultés ? m La perception est ambiguë de manière inhérente ❏ « Jai laissé tomber lœuf sur le sol et il sest cassé » m Rationalité limitée ❏ Y-a-t-il un premier coup gagnant aux échecs ? m Compromis entre buts en conflits m Information incomplète et/ou incertaine 17/57 Cours IA (A. Cornuéjols) LIA par rapport à linformatique ❏ Etudie les problèmes insolubles en informatique classique m Solution optimale inconnue ou trop difficile à trouver/identifier m Des paramètres difficiles à maîtriser : connaissances incertaines, vagues, hypothétiques, ... ❏ Exigences dexplication ou de communication sophistiquée avec les utilisateurs ❏ Objectif dadaptation et dapprentissage avec lexpérience ❏ ... 18/57 Cours IA (A. Cornuéjols) Caractéristiques de lIA m Prise en compte de la Connaissance (symbolique) m Raisonnements ❏ Logiques / Probabilistes / imprécis / … ❏ Induction / analogie / … ❏ Heuristique ❏ Non déterministe vs. déterministe m Solutions satisfaisantes vs. Optimales m Pas programmé mais par apprentissage 19/57 Cours IA (A. Cornuéjols) Domaines dapplications de lIA m Ordonnancement et planiﬁca0on ❏ Système DART de la DARPA u0lisé pour la logis&que des opéra0ons « Desert storm » et « Desert shield » ❏ Système de changement de trajets pour American Airlines ❏ Système de planiﬁca&on et dordonnancement pour lassemblage des vols spa0aux européens (ESA) m Reconnaissance de la parole ❏ Émergence d’assistants sur les smartphones m Vision par ordinateur ❏ Systèmes de reconnaissance de visages, systèmes de surveillance (y compris suivi entre caméras) ❏ DARPA « Grand Challenge » et DARPA « Urban Challenge » ❏ Reconnaissance de lécriture manuscrite 20/57 Cours IA (A. Cornuéjols) Domaines dapplications de lIA m Systèmes de diagnostic ❏ Système Pathfinder et Internist en médecine (supérieurs aux médecins) ❏ Système daide aux consommateurs (Whirlpool) m Systèmes de conception et configuration ❏ Système XCON de DEC pour aider à la configuration de systèmes informatiques m Aide à la décision (e.g. financière) ❏ Systèmes de détection de fraude (IRS aux USA, banques (cartes de crédit)) ❏ Aide aux demandes de financement des particuliers 21/57 Cours IA (A. Cornuéjols) Domaines dapplications de lIA m Systèmes de classiﬁca0on ❏ SKYSURVEY de la NASA m Démonstra0on automa0que de théorèmes m Systèmes de jeu ❏ Champions du monde aux dames (anglo-saxonnes), othello, backgammon, échecs, go ❏ Le pocker ? Le bridge : pas encore ❏ Sert à concevoir des systèmes sadaptant à des milieux hos0les m Traduc0on automa0que ❏ Systèmes de traduc0on de Google (bientôt en temps réel) (MAIS …) 22/57 Cours IA (A. Cornuéjols) Les approches de lIA m Lécole symbolique ❏ La pensée consiste en une séquence de transformations de représentations ➥ Agents cognitifs délibératifs m Lécole sub-symbolique ❏ La pensée consiste en une transmission et une transformation de signaux ➥ Agents réactifs m Lécole de la cognition située ❏ La pensée ne réside pas dans la tête dun individu isolée mais est distribuée au sein dune société (incluant son histoire et sa culture) et suscitée par le contexte. ➥ Emergence et auto-organisation 23/57 Cours IA (A. Cornuéjols) Bref historique (1) 0. Depuis lAntiquité ... ❏ Bacon / Pascal / Descartes / Leibniz ❏ Babbage & Ada de Lovelace / Boole ❏ Réflexion sur les fondements des mathématiques 1. Les pionniers de lIA (~1936 - ~1956) ❏ Turing : les fonctions calculables sont définies par une machine ❏ Von Neumann : architecture des ordinateurs, réflexions sur les automates ❏ McCulloch & Pitts (1943) : Premier modèle formel du neurone ❏ Hebb (1949) : assemblées de neurones et règle dapprentissage ❏ Les conférences Macy et la première Cybernétique 24/57 Biological Neurons Axon Terminal Branches of Axon Dendrites Cours IA (A. Cornuéjols) 25/57 Axon Terminal Branches of Axon Dendrites S x1 x2 w1 w2 wn xn x3 w3 1er modèle formel de neurone McCulloch & Pitts (1943) Cours IA (A. Cornuéjols) 26/57 Cours IA (A. Cornuéjols) Bref historique (2) 2. LIA comme méthodes générales (~1956 - ~1968) ❏ La pensée comme manipulation de représentations discrètes des connaissances: IA symbolique m Démonstrateurs de théorèmes (principe de résolution (-> Prolog)) m Résolveurs universels de problèmes (GPS) m Le système CHECKER ❏ Premier connexionnisme m Le Perceptron [Rosenblatt, 1957-1962] ❏ MAIS des échecs : m La traduc0on automa0que m Les experts ne sont pas des experts universels !? m Le Perceptron est limité 27/57 L’espoir L’intelligence met en jeu des processus généraux de raisonnement Cours IA (A. Cornuéjols) 28/57 A C B C B C B A C B A C B A C B A B A A C ((BA) (C)) ((AB) (C)) ((B) (AC)) ((A) (BC)) ((CA) (B)) ((A) (CB)) bouger(B,A) bouger(B,C) État Opérateur ((A)(B)(C)) Raisonnement / résolution de problèmes Cours IA (A. Cornuéjols) 29/57 Raisonnement / résolution de problèmes m Recherche dans un graphe 5.1 The Logic Theorist and Heuristic Search Figure 5.2: The eight-puzzle. with. I will represent the starting position by the following structure, which is a list of three sublists: ((2, 8, 3), (1, 6, 4), (7, B, 5)). The ﬁrst sublist, namely, (2, 8, 3), names the occupants of the ﬁrst row of the puzzle array, and so on. B stands for the empty cell in the middle of the third row. In the same fashion, the goal conﬁguration is represented by the following structure: ((1, 2, 3), (8, B, 4), (7, 6, 5)). Next, we have to show how a computer can transform structures of the kind we have set up in a way that corresponds to the allowed moves of the puzzle. Note that when a tile is moved, it swaps places with the blank cell; that is, the blank cell moves too. The blank cell can either move within its row or can change rows. Corresponding to these moves of the blank cell, when a tile moves within its row, B swaps places with the number either to its left in its list (if there is one) or to its right (if there is one). A computer can easily make either of these transformations. When the blank cell moves up or down, B swaps places with the number in the corresponding position in the list to the left (if there is one) or in the list to the right (if there is one). These transformations can also be made quite easily by a computer program. Using the Newell and Simon approach, we start with the symbol uploads/Management/ tr-cours-ia-1-v2018x4.pdf