Voilà
ce que l'on apprend à l'université Paul Sabatier a Toulouse (en
Informatique, spécialité Intelligence Artificielle, au niveau du
Doctorat Bac +8) : Ca fait rêver !
1. Apprentissage
L'apprentissage est un champ
de l'intelligence artificielle où l'on se propose de concevoir des
machines dont les performances s'améliorent avec l'expérience.
En d'autres termes, une telle machine simule le comportement évolutif
d'un être humain. Aujourd'hui, cette discipline est très diversifiée
allant de la fouille de données aux systèmes multi-agents
en passant par la programmation logique inductive et la théorie de
l'information. On tentera dans ce cours de donner un aperçu de l'ensemble
en évoquant aussi les problèmes classiques de test de performance
et d'évaluation de complexité.
Mots-clés : Emergence, Programmation logique inductive, Algorithmes
génétiques
Formalisation du problème
1. Le cadre standard : PAC apprenabilité
de Valiant
- Un exemple introductif
(rectangles dans R2)
- Le PAC modèle
- Ce qui est PAC apprenable
- Ce qui n'est pas PAC
apprenable
2. La dimension de Vapnik-chervonenkis
- Equivalence Rasoir d'Occam
- PAC apprentissage
- Bornes sur le nombre d'exemples
dans le cas fini
- Bornes dans le cas infini :
la VC-dimension
Applications : quelques systèmes positionnés par rapport
au modèle théorique
1. Les réseaux bayésiens
- Contexte d'apprentissage
- Définition et
exemples
- VC-dimension
2. Les réseaux de neurones
3. La programmation logique inductive
4. Les "support vector machines" de Vapnik
5. Les systèmes multi-agents adaptatifs
et l'émergence
6. Les algorithmes génétiques
Imprédictibilité
1. Définition et exemples dans le PAC
modèle
2. Une autre définition possible
- La théorie de
l'information de Kolmogorov
- La mesure de Solomonov-Levin
Prérequis : Des connaissances basiques en théorie
des probabilités et en logique.
Bibliographie :
- ISTAS J. Probabilités et statistiques, Ellipses.
- CORI R., LASCAR D. Logique mathématique. Cours et exercices. (Tome
I et Tome II), Masson, 1993.
2. Logiques Modales et Application
à l’Interaction
Ce cours présente les
principaux systèmes de logique modale puis une application au traitement
formel de l’interaction.
Introduction : Histoire et motivation en IA
Systèmes monomodaux et multimodaux
1. Généralités sur la sémantique
2. Système K
- Langage et Axiomatique
- Sémantique
(de Kripke) / Satisfaction, validité, vérité
- Caractérisation
(énoncé)
3. Les axiomes D, T, B, 4, 5
- Lecture des axiomes,
axiomatique
- Sémantique
du 2ième ordre
- Sémantique
du 1ier ordre
4. Déduction automatique et décidabilité
: la méthode des tableaux
- Règles classiques
/ pour K/ pour D, T, 4
- Adéquation
et complétude
- Terminaison et
test de boucle / Décidabilité
- Stratégies
complètes et terminantes, complexité
5. Systèmes multimodaux : multi-K et axiomes
d'interaction
- Axiomatique
- Sémantique
du 1er ordre
Application à la formalisation de l'interaction
1. Croyance
- Omniscience
- Introspection
- Connaissance versus
croyance
2. Actions
- Pré-conditions
et effets
- Persistance (frame
problem)
- Calcul des situations
- Causalité
(STIT)
- Actes de communication
3. Intentions
- à
la Cohen et Levesque :choix + engagement
- à
la Rao, Georgeff, Wooldridge: cadre B, D, I
4. Obligation
- Mondes idéaux
- Violation,
paradoxe de Ross
- Obligations
secondaires (contrary-to-duties)
3. Fondements linguistiques
et informatiques pour le traitement automatique
de la Langue Naturelle écrite
La communication Homme-Machine en
langage naturel, sous une grande diversité de formes (langue simplifiée,
schémas, langue standard, utilisées en interrogation, en mode
textuel, en situation de dialogue, dans le WEB, dans les autoroutes de l’information
et le multi-media, …) se trouve au cœur de nombreuses préoccupations
(interrogation de services, dialogue homme-machine, traductions, aide à
la rédaction technique, systèmes tutoriels). Elle fait appel
à des outils conceptuels ou techniques largement répandus
(ontologies, terminologies, systèmes de traits…).
Ce cours propose une analyse
des fondements théoriques du traitement automatique du langage naturel
écrit. Il propose les éléments fondamentaux linguistiques,
syntaxiques et sémantiques, cognitifs et conceptuels, de représentation
des connaissances et de traitement informatique.
Objectifs de la communication en langue naturelle
- Les enjeux, les exigences
- Familles d’applications
- Le langage et son environnement
Rappels d’éléments d’informatique théorique
- Grammaires, automates, systèmes de traits, stratégies
d’analyse et de génération,
- Techniques d’unification avancée, lambda-calcul
Typologie des applications incluant des éléments de langue
Fondements linguistiques
- Lexique : morphologie, sous-catégorisation,
rôles thématiques, relations lexicales
- Fondements de la syntaxe, techniques d’analyse syntaxique
et de construction de représentations
- Fondements de la sémantique : notions de sens,
principe de compositionalité, formalismes sémantiques
Méthodes d'analyse et d'évaluation
- Méthodes d'analyse de problèmes, dépouillement
de données langagières, annotations
- Evaluation des coûts, des besoins, des ressources
- Protocoles pour l'évaluation des productions
Quelques problèmes épistémologiques simples
- Dynamique et évolution du langage dans les applications
- Problèmes de la notion de sens
- Apprentissage des ressources linguistiques
Bibliographie :
- CRUSE A., Lexical Semantics, Cambridge university Press, 1986
- FELLBAUM C. A Semantic Network of English Verbs, in C. Fellbaum (ed.)
WordNet: An Electronic Lexical Database.
Cambridge, MA: MIT Press, 1997.
- FILLMORE C., The Case for Case, in Universals in Linguistic Theory, E.
Bach and R.T. Hams (eds.), Holt, Rinehart and Winston, New York, 1968.
- GRUBER J., Studies in Lexical Relations, Lexical Structures in Syntax
and Semantics, North Holland , 1967.
- JACKENDOFF R., Semantic Structures, MIT Press, 1990
- SAINT-DIZIER P. Advanced logic programming for language processing, Academic
Press, 1996.
4. Méthodes de Preuve,
d’Optimisation et de Satisfaction de Contraintes
Ce cours a vocation à
présenter des algorithmes génériques de recherche et
d'optimisation, et à les illustrer sur des problèmes spécifiques
tant de la recherche opérationnelle que plus spécifiquement
de l'Intelligence Artificielle (logique propositionnelle, problèmes
de satisfaction de contraintes, réseaux bayésiens).
Mots-clés : Production de conséquences, Optimisation,
Recherche incomplète, Satisfaction de Contraintes
Algorithmes énumératifs complets
1. Principe de base.
2. Illustration sur un problème classique
: le problème du voyageur de commerce.
3. Rappel sur le problème SAT ; la procédure
de Davis et Putnam
4. Définition du cadre des CSP et exemples
; recherche de solution par l'algorithme de backtrack.
5. Recherche d'une explication de probabilité
maximum dans les réseaux bayésiens.
Production de conséquences
1. Introduction : pourquoi la recherche de conséquence
(inférence, synthèse d'information, propagation).
2. Illustration sur SAT : résolution,
recherche d'impliqués premiers.
3. Amélioration d'algorithmes énumératifs
par recherche de conséquence (propagation): illustration sur les
CSP (backtrack intelligent), sur SAT.
4. Réseaux bayésiens : calcul de
marginales.
Recherche incomplète
1. Algorithmes énumératifs partiels.
2. Algorithmes de recherche locale : recuit simulé,
GSAT, "local searchtemplate''.
Notions de complexité computationnelle
1. Notion de complexité des problèmes
2. Réductions entre problèmes, complétude
pour une classe
3. Illustration : quelques problèmes polynomiaux
(2-SAT, Horn-SAT, ) et NP-complets (SAT, 3-SAT, consistance
d'un CSP, TSP, etc…).
Prérequis : De bonnes bases en logique propositionnelle
et en algorithmique générale.
Bibliographie :
- PAPADIMITRIOU C.M., Computational Complexity, Addison-Wesley Publishing
Company, 1994.
- TSANG E.P.K., Foundations of Constraint Satisfaction, Academic Press
Ltd., 1993.
- ALLIOT, SCHIEX, BRISSET, GARCIA, Intelligence artificielle et Informatique
théorique, Cépaduès, 2002.
5. Fondements des Systèmes
Multi-Agents
Ce cours doit permettre d'appréhender des modèles
de résolution collective de problèmes qui sont caractérisés
notamment comme complexes et distribués.
1. Introduction : positionnement par rapport à d'autres champs
de recherche en informatique
2. Un nouveau mode de résolution : la résolution collective,
exemples et introduction de l'interaction
3. Agent : concepts de base (autonomie, intentions) et architectures d'agent
4. Les organisations
5. L'environnement
6. L’interaction
7. La communication entre agents
- Les actes du langage
- La reconnaissance d'intentions
- Les ACL de FIPA, les protocoles
- La multi-modalité
8. Modèles et Théories des SMA
- Réseaux de contrats,
- Architectures réactives, délibératives,
hybrides, …
- La théorie de la dépendance de Castelfranchi,
- La logique de l'action de Cohen et Levesque
9. Conception de SMA
- Méthodologie de conception de systèmes
à agents ou de SMA : GAIA, MESSAGE ADELFE
10. Quelques plates-formes : JADE, MADKIT
11. Etude de cas
- Simulation de fourmis fourrageuses par SMA
- Systèmes de commerce électronique basé
sur les SMA
- Systèmes de robotique collective
Bibliographie :
- BRIOT J-P., DEMAZEAU Y., Principes et architectures des systèmes
multi-agents, Hermès 2001.
- WOOLDRIDGE. M., An introduction to Multi-Agent Systems, John Wiley &
Sons, 2002.
6. Représentation et
Traitement de l’Incertitude
Ce cours traite de la représentation et du traitement
de l'incertitude dans les systèmes à base de connaissances.
On y décrit quelques théories numériques
de représentation de l'incertitude, comme la théorie des probabilités,
la théorie des possibilités et la théorie de l'évidence.
On y décrit également des approches non
numériques, au traitement du raisonnement non-monotone.
Mots-clés : Incertitude, Plausibilité, Inférence,
Révision
Introduction
1. Généralités : incertitude
vis-à-vis de incomplétude, imprécision, inconsistance.
2. Notion d'ordre de plausibilité entre les
mondes possibles (de façon numérique ou non).
3. Problèmes principaux :
- représenter l'incertitude
sur les informations
- inférer (déduire/calculer)
les informations les plus plausibles
- réviser (ajouter
une nouvelle information)
- fusionner (des informations
incertaines)
Ces points seront déclinés (tout ou en partie) dans
les différents formalismes qui seront présentés dans
le cours.
Quelques approches numériques à la représentation
de l'incertitude
1. Rappels sur la théorie des probabilités
2. Théorie des possibilités
3. Théorie de l'Evidence
4. Introduction aux réseaux bayésiens
Prérequis : La logique classique.
7. Conception et Ergonomie
des Systèmes Coopératifs
Le but de ce cours consiste à décrire
de manière assez générale la Conception des Systèmes
Coopératifs ainsi que les méthodes ergonomiques associées.
Les Systèmes Coopératifs sont des systèmes conçus
pour supporter le travail de groupe nécessitant une activité
de coopération parmi tous les acteurs participant au processus. Il
existe plusieurs approches permettant de réaliser ces types de systèmes
que nous proposons de détailler.
Introduction générale
1. Les différentes formes de coopérations
- Coopération Homme/Machine
- Système supportant des
tâches collectives impliquant une coopération
2. Les différents types de systèmes coopératifs
3. Avantages, inconvénients des systèmes coopératifs
4. Les systèmes coopératifs d'un point
de vue systémique
5. La coopération homme/système,
agent/agent
Ergonomie des Systèmes Coopératifs
1. Méthodes d'analyse des activités coopératives
2. Importance de la compréhension des modes dégradés
3. Quelques approches conceptuelles pour l'analyse des
systèmes coopératifs
- Socio-linguistique - Interactionnisme
social - Analyse conversationnelle
- Ergonomie/Ingénierie
cognitive
- Sociologie pragmatique - Ethnométhodologie
- Anthropologie cognitive
- Théories instrumentales
de l’Activité
Conception des Systèmes Coopératifs
1. Conception de systèmes à base de connaissances
coopératifs
- Définition
- Les entrées du développement
de tels systèmes :
Analyse ergonomique (pointeur avec II)
Modélisation de l'utilisateur, des connaissances, de la coopération,
de la tâche
2. Un type d’application : la Décision de groupe
assistée par ordinateur
Méthodologie de la recherche
Etudes de cas
Bibliographie :
- SCHMIDT K. “Cooperative Work : A Conceptual Framework” , Distributed
Decision Making : Cognitive Models for Cooperative
Work, Edited by J. Rasmussen, B. Brehmer and J. Leplat, John Wiley,
1991.
- BOWERS J.M., BENFORD S.D. “Studies in Computer Supported Cooperative Work
; Theory, Practice and Design” Human Factors in Information
Technology , North Holland, 1991.
8. Planification et Décision
La planification, domaine essentiel
de l'IA, cherche à concevoir des systèmes capables de générer
automatiquement, par une procédure formalisée, un plan-solution.
Ce dernier est une collection organisée de descriptions d'opérations
destinée à guider l'action d'agents exécuteurs (systèmes
robotiques ou humains) qui doivent agir dans un monde particulier (et souvent
incertain) pour atteindre un but préalablement défini. Ce cours
présente les aspects fondamentaux de ce domaine.
Mots-clés : Planification, Décision, Incertitude
Introduction générale
1. Qu'est ce qu'un problème de décision/planification
? Pourquoi planifier ? Le mirage de la planification.
2. Typologie :
- des
actions, des tâches, et leur représentation (frame problem,
ramification...),
- des
plans,
- des
problèmes.
3. La planification modélisée comme :
- réutilisation
de plans,
- expertise,
- réaction,
- synthèse
de plans.
4. Quelques applications de la planification.
Algorithmes pour la synthèse de plans d'actions dans le cadre classique
1. Le cadre classique, les problèmes posés.
2. Le langage STRIPS et ses extensions.
3. Algorithmique de la synthèse de plans
:
- rappels sur la recherche
heuristique,
- la recherche dans les
espaces d'états (HSP, HSPR, FF, SHAPER…),
- la recherche dans les
espaces de plans (Tweak, Pweak, UCPOP…),
- les méthodes GRAPHPLAN,
LCGP…
- les méthodes SATPLAN,
- une synthèse de
la synthèse de plans,
4. Esquisse d'autres méthodes importantes (HTN,
logique et démonstration).
Extension du cadre classique : décision et planification en présence
d'incertitude
1. Du cadre classique à la prise en compte
de l'incertitude.
2. La théorie de la décision (individuelle)
:
- modélisation des
préférences,
- décision individuelle
dans le risque et dans l'incertain,
- attitude d'un agent face
au risque.
3. Planification dans l'incertain et processus
décisionnels markoviens :
- définitions et
typologie,
- MDP totalement observables
et méthodes de résolution,
- MDP partiellement observables
(POMDP), méthodes de résolution et d'approximation.
Prérequis : Algorithmes de recherche dans les espaces d'états
(largeur, profondeur, Hill Climbing, A*…), logique des prédicats.
Bibliographie :
- WILKINS D. E. Practical Planning, Morgan Kaufmann Publishers, 1988.
- ALLEN J.F. & col. Reasoning about Plans, Morgan Kaufmann Publishers
, 1991.
9. Sémantique et Extraction
de Connaissances
En traitement automatique des langues, le texte est
un objet d'étude central et transversal à de nombreuses thématiques.
Dans ce cours, nous abordons différents types d'applications qui
ont en commun de viser ou de nécessiter l'identification d'éléments
de sens à partir du contenu des textes. La granularité de
ces éléments ainsi que l'utilisation envisagée peuvent
être très variables.
Mots-clés : Textes, Ontologies, Web sémantique
Extraction de connaissances à partir de textes
- Enjeux, niveaux de traitement (des mots-clés aux formes structurées)
- Exemples, points difficiles
- Principes : grammaires et automates, règles et patrons de fouille
(apprentissage, représentation et application)
- Typologie de logiciels d'extraction de connaissances à partir
de textes
Structures textuelles
- Etude des textes au niveau macroscopique : enjeux
- Architecture textuelle, mise en forme matérielle et objets textuels
- Exemple : modèle MAT
Ontologies
- Ontologie formelle : principes structurels, représentation des
connaissances
- Ontologies et ressources lexicales ou terminologiques (structures,organisation,
différents niveaux de données)
- Ontologies : utilisation en TAL et recherche d'information (comme base
structurante de construction de lexiques, apport à l'analyse sémantique)
- Construction d'ontologies à partir de corpus de textes
Le Web sémantique
- Enjeux, approches, standards
- Place du TAL : des balises sémantiques (méta-données)
à l'analyse conceptuelle des contenus
- Apport de la formalisation, exemple du projet PICSEL
Systèmes Questions-Réponses
- Typologie de cette famille d'applications
- Typologie des questions,
- Rechercher la/les réponses : directes, coopératives et
raisonnements associés,
- Gérer les réponses incohérentes (venant du Web,
de textes)
Génération
- Le point de départ de la génération, le quoi dire
et le comment le dire, enjeux et problématique
- Fonctions de base : lexicalisation, agrégation et micro-planification
- La génération d'explications.
10. Types de Raisonnements
et leurs Applications
Ce cours a pour objectif de
présenter les grands types de raisonnements (déductif,
abductif, inductif, par analogie, argumentation) par la relation de conséquence
logique qui les caractérise ainsi que quelques unes de leurs applications.
Mots-clés : Types de raisonnement
1. Présentation du raisonnement déductif
Définition générale
Panorama des différents types de connaissances
traitées (croyances, connaissances temporelles, obligations, connaissances
incomplètes, incertaines)
Inférence plausible (logique des défauts,
théories de Brewka, inférence argumentative)
Raisonnement par analogie
2. Présentation du raisonnement abductif
Définition générale
Applications : diagnostic, génération
de réponses intentionnelles, détection d'incohérences
dans les règlementations
SOL résolution pour la génération
d'hypothèses abductives
Présentation d'un système ATMS et application
à la construction d'arguments
3. Présentation du raisonnement inductif
Définition générale
Généralisation et spécialisation
inductive
Application en apprentissage (génération
de règles floues)
11. Discours et Dialogue
Ce cours présente les
approches de la conversation en Sémantique et Pragmatique formelles.
Sont tout d'abord abordés les problèmes de représentation
du sens d'une phrase, d'un discours, son pouvoir inférentiel, les
principes généraux de son énonciation, la reconnaissance
des intentions sous-jacentes et les états mentaux des interlocuteurs.
Viennent ensuite les spécificités de la modélisation
du dialogue dans ses différents genres (orienté tâche,
négociation, argumentation...), que soient considérés
le dialogue naturel humain/humain ou les systèmes humain/machine.
Mots-clés : discours, dialogue
Introduction
1. A propos des Grammaires Catégorielles et de la Logique Intensionnelle
2. La Grammaire de Montague : le cas de la phrase
Le discours
1. Modèles du discours
2. Les extensions de la Grammaire de Montague
3. Les Maximes de conversation
4. Les Actes de Discours
Le dialogue
1. Les systèmes de dialogue coopératif et leurs modèles
2. Stratégies de dialogue
3. Les jeux de dialogue
Bibliographie :
- AUSTIN J.L. Quand dire c'est faire. Editions du Seuil, Paris, 1991.
- GRICE H.P. Logic and conversation. In Cole P., Morgan J. (Eds) Syntax
and semantics 3 : Speech acts. Academic Press, New-York, 1975.
- KAMP H., REY le U. From Discourse to Logic. Kluwer, Dordrecht, 1993.
- SEARLE J.R. L'intentionnalité, essai de philosophie des états
mentaux. Les Editions de Minuit.
| 