Tous
les sujets de stage proposés par le LERIA sont indiqués ici.
Règles
de choix:
R1:
Un stage doit être choisi par un étudiant dans chacune des équipes (1., 2., 3.,
4.).
R2:
Les étudiants inscrits à Angers doivent choisir un stage dans ceux proposés à Angers
(1., 2., 3., 4., 5.).
R3:
Le choix est ensuite laissé libre parmi les équipes (1., 2., 3., 4.), les stage
inter-équipes ou inter-labos (5.).
A
vous de vous mettre d'accord pour que ces règles soient respectées. Je ferai un
point à l'issue de mon cours du 26 novembre et/ou une réunion à Angers fin
novembre. L'attribution des stages se fera après cette réunion.
N'hésitez
pas à me contacter en cas de difficultés.
S. Loiseau
Les
stages proposés par les laboratoires de Nantes sont sur le serveur
http://www.sciences.univ-nantes.fr/info/enseignement/dea/. Vous pouvez
les consulter; si vous tenez à y effectuer un stage, un échange d'étudiants
entre Nantes et Angers peut être envisagé. Un tel échange doit être validé par
le responsable du DEA d'Angers (S. Loiseau) ET la responsable du DEA de Nantes
(B. Daille).
1. Equipe MOC
Etude du problème MAX-SAT
Encadrement : F.Saubion et J.K Hao
Equipe Métaheuristiques et Optimisation Combinatoire
Lieu : LERIA , Angers
Le problème SAT, qui consiste à déterminer la satisfiabilité d’un ensemble de clauses en logique propositionnelle, apparaît comme un problème de première importance aussi bien d’un point de vue pratique que théorique; ses applications sont nombreuses et variées.
Diverses approches ont été proposées et se répartissent en deux grandes catégories : les méthodes complètes et les méthodes incomplètes. Les méthodes complètes, permettant le calcul de toutes les solutions, sont essentiellement basées sur la procédure de Davis-Putnam alors que les approches incomplètes utilisent des techniques issues de la recherche locale.
Dans le cadre de l’utilisation de méthodes incomplètes, pour des instances de grandes tailles qui deviennent éventuellement insatisfiables ou restent non résolues, on s’intéresse alors plus généralement au problème de satisfaction maximale, consistant à trouver une affectation satisfaisant un maximum de clauses (problème MAX-SAT).
Objectif :
L’objectif de ce stage sera d’étudier précisément les jeux de tests existants, habituellement utilisés pour le problème SAT, afin d’en isoler les propriétés et d’établir des critères de classification, dans le contexte de cette problématique MAX-SAT. Le but étant de proposer des générateurs automatiques d’instances spécifiques pour le problème MAX-SAT permettant de garantir un certain nombre de critères relatifs à leur difficulté potentielle puis de tester ces nouveaux jeux sur des solveurs réputés.
Compétences :
Ce stage permettra d’aborder les problèmes d’optimisation combinatoire dans le contexte particulier de la logique propositionnelle et d’étudier et de comparer des méthodes de résolution performantes.
Contacts : Frederic.Saubion@univ-angers.fr
Jin-Kao.Hao@univ-angers.fr
Un modèle évolutionniste pour l’optimisation sous contraintes
Encadrants : F. Saubion
et J.K. Hao
Equipe Métaheuristiques
et Optimisation Combinatoire
Lieu : LERIA , Angers
Les problèmes d’optimisation sous contraintes dans les domaines finis
trouvent de nombreuses applications pratiques : ordonnancement,
planification, emploi du temps … et diverses approches peuvent être envisagées
pour leur résolution. Un tel problème peut se modéliser, par exemple, comme la
maximisation de la valeur d’une fonction f(x1,…,xn)
sachant que les variables x1,…,xn sont soumises à un ensemble de contraintes C(x1,…,xn ). On peut donc distinguer deux
problématiques : la satisfaction consistant à trouver une affectation de
valeurs aux variables x1,…,xn vérifiant les contraintes C(x1,…,xn ) et le problème d’optimisation
consistant à déterminer parmi ces affectations celles qui maximisent f.
Concernant le
problème de satisfaction, nous disposons actuellement d’un schéma algorithmique
utilisant des techniques de propagation de contraintes dans un contexte
évolutionniste et intégrant également des heuristiques de recherche locale.
L’uniformité des structures utilisées autorise une interaction homogène entre
les différentes méthodes mises en oeuvre et permet également de bénéficier au
mieux de leurs atouts respectifs
Objectif :
L’objectif de ce
stage sera donc d ‘étendre ce schéma pour y intégrer d’autres mécanismes
propres à l’optimisation combinatoire en les associant au contexte
évolutionniste existant. On étudiera en particulier les possibilités
d’utilisation d’heuristiques spécifiques d’élagage et d’approximation.
Compétences :
Ce stage permettra à l’étudiant de se familiariser avec les techniques de résolution de contraintes ainsi qu’avec les principes des algorithmes évolutionnistes et des heuristiques de recherche locale.
Contacts : Frederic.Saubion@univ-angers.fr
Jin-Kao.Hao@univ-angers.fr
Coloration de graphes avec l’orientation acyclique
1. Définitions
Le problème de k-coloration est un problème de décision NP-complet dans le cas général. Il peut se définir comme suit : étant donnés un entier k et un graphe non orienté G=(V,E) défini par un ensemble V de sommets et un ensemble E d’arêtes reliant les sommets, on cherche une affectation – ou l’on doit montrer qu’il n’en existe pas – des k couleurs aux sommets de V telle que 2 sommets adjacents (i.e., reliés par une arête) soient coloriés différemment. Le problème d’optimisation qui lui est associé est de déterminer le nombre chromatique χ, c’est à dire le k minimum tel qu’une k-coloration existe.
2. Applications
Au-delà de l'importance théorique liée à leur résolution, les problèmes de coloration de graphes trouvent également un intérêt pratique dans la modélisation de problèmes réels issus de l'industrie. Citons, entre autres, l’élaboration d’emploi du temps (ou, plus formellement, l'ordonnancement de tâches avec contraintes sur les ressources), l'allocation de fréquences dans les réseaux radio-mobiles de télécommunications, l'allocation de registres, la vérification de circuits imprimés ou le calcul de matrices jacobiennes creuses. L’importance de ces problèmes est telle que de nombreux jeux d’instances existent (graphes DIMACS pour citer les plus connus).
3. Orientation acyclique et objectifs du stage
Dans ce stage, nous exploitons une piste récente fondée
sur une représentation du problème par l’intermédiaire de la notion
d’orientation acyclique. Une orientation acyclique (OA) d’un graphe non-orienté
est une orientation de ses arêtes telle que le graphe orienté ainsi obtenu ne
contienne pas de cycle. C’est un formalisme qui permet d’exprimer χ(G)
comme suit : 
avec Ω(G) l’ensemble des OAs de G, P(ω)
l’ensemble des chemins induits par ω et l(p) le nombre de
sommets de p. Cette représentation est jusqu’alors très peu étudiée pour
concevoir des algorithmes de coloration, en particulier des algorithmes
heuristiques.
Le premier objectif du stage consiste donc à proposer des algorithmes de coloration fondés sur la classe des métaheuristiques dites de « recherche locale » (recherche tabou par exemple) et de les expérimenter sur des jeux d’instances bien connus. Un deuxième objectif serait de développer des algorithmes hybrides combinant l’approche génétique et la recherche locale.
4. Informations pratiques
Encadrement : Jin-Kao Hao & Jean-Philippe Hamiez
Lieu de stage : LERIA , Université d’Angers – UFR Sciences
Équipe d’accueil : Métaheuristiques et optimisation combinatoire
(http://www.info.univ-angers.fr/info/leria.html).
Contacts : Jin-Kao Hao (hao@info.univ-angers.fr, 02 41 73 50 76)
Jean-Philippe Hamiez (hamiez@info.univ-angers.fr, 02 41 73 53 85)
Utilisation
de Méthodes Heuristiques pour la Résolution du « Longest Arc-Preserving
Common Subsequence Problem »
en
Bio-informatique
Encadrement : J.K. Hao et J.M. Richer
Lieu : LERIA , Angers
Présentation du sujet :
Le problème de
recherche d’une séquence commune la plus longue (Longest Common Subsequence)
est un problème bien connu en bio-informatique qui permet d’identifier des
similarités entre séquences et est utilisé entre autre pour la découverte de
motifs d’un ensemble de k séquences. Ce problème peut être résolu de
manière exacte grâce à un algorithme de programmation dynamique mais requiert
un temps de calcul prohibitif.
Le problème LCS peut
être étendu par arc-annotation de manière à prendre en compte la structure de
molécules comme l’ARN pour lesquelles les structures secondaire et tertiaire
jouent un rôle important dans la fonction attribuée à chaque molécule d’ARN. Le
problème intitulé LAPCS (Longest Arc-Preserving Common Subsequence)
consiste à ajouter à la structure primaire d’une séquence, une représentation
sous forme d’arcs indiquant les liaisons entre les différents acides
nucléiques. Le problème LAPCS consiste donc à comparer des séquences primaires
avec comme contrainte supplémentaire que les liaisons intra-moléculaires des
séquences soient conservées. Dans le cas général ce problème est NP-difficile
mais sous certaines conditions (notamment dans le cas de l’ARN où les arcs ne
se chevauchent pas) la relaxation de certaines contraintes permet de diminuer
la complexité du problème.
Nous proposons d’organiser le stage de DEA suivant 3 axes :
1) une étude bibliographique sur les méthodes existantes
2) la conception et le développement d’algorithmes heuristiques (génétique, tabou, recuit simulé, hybride) pour traiter le problème LAPCS (ou ses dérivés)
3) l’évaluation expérimentale et la validation des algorithmes à l’aide de jeux de tests (benchmarks) du domaine traité
Ce stage de DEA sera réalisé au LERIA (Laboratoire d’Etude et de Recherche en Informatique d’Angers : http://www.info.univ-angers.fr/info/leria.html).
Contacts : Jin-Kao Hao (hao@info.univ-angers.fr, 02 41 73 50 76)
Jean-Michel Richer (richer@info.univ-angers.fr, 02 41 73 52 34)
2. Equipe SBCI
Raisonnement
sur des diagrammes UML
dans le modèle des graphes conceptuels.
Responsables: Stéphane
Loiseau, David Genest
Lieu: Angers
Pour
concevoir une application utilisant le paradigme objet, des méthodes basées sur
des représentations graphiques sont habituellement utilisées. Plus précisément,
les diagrammes UML, et en premier lieu le diagramme de classes, permettent de
représenter différents aspects de l'application tels que les classes, les
enchaînements d'opérations, les états, etc. Ces représentations ont l'avantage
d'être graphiques et simples à interpréter. Toutefois, UML n'offre pas
d'opérations d'interrogation, par exemple pour rechercher une classe qui a
certaines caractéristiques. Il n'y a pas non plus d'opérations de contrôle (par
exemple pour s'assurer que la relation de généralisation entre classes est
utilisée partout où elle devrait l'être).
Le
modèle des graphes conceptuels est un modèle de représentation de connaissances
dans lequel les connaissances sont représentées graphiquement, et qui dispose
d'opérations permettant un raisonnement sur les connaissances représentées. Le
but de ce stage est d'étudier comment certaines notions usuelles dans le
paradigme objet (que l'on peut représenter graphiquement dans des diagrammes
UML) peuvent être représentées à l'aide de graphes conceptuels. Il s'agit aussi
de voir comment les opérations du modèle des graphes conceptuels ou des
extensions de ces opérations peuvent être utilisées pour fournir des fonctions
de recherche ou de contrôle qui peuvent être utiles lors de la conception ou
pour comprendre / exploiter / modifier des diagrammes UML existants.
Le
déroulement du stage se fera comme suit:
1)
Étude bibliographique sur les graphes conceptuels, sur les représentations
graphiques utiles à la conception à l'aide d'objets (UML), sur les mécanismes
de recherche et de contrôle en génie logiciel.
2)
Proposition d'un modèle permettant de représenter une (partie d'une) conception
par objets sous forme de graphes conceptuels, avec les opérations associées. La
proposition sera validée par la réalisation d'un prototype.
3)
Le mémoire de stage présentera les résultats obtenus en mettant l'accent sur
les apports de la proposition par rapport à UML "seul".
3. Equipe TALN
Titre : Représentation et raisonnement temporels dans la langue, une approche par les graphes d’intervalles.
Responsables scientifiques : Bernard Levrat, Tassadit Amghar
Les raisonnements automatiques à partir de textes qui reposent sur des relations temporelles supposent de pouvoir disposer d’une représentation conceptuelle du temps adaptée aux entités temporelles susceptibles d’être exprimées par la langue.
De nombreux travaux d’intelligence artificielle se sont fixés pour objectif de définir des ontologies temporelles[1] adaptées à la langue pour permettre l’implémentation de mécanismes de calcul permettant de résoudre les problèmes reposant sur des raisonnements mettant en jeu le temps afin de permettre la compréhension des textes.
Parmi ces travaux nous nous intéresserons particulièrement ici à ceux de J.F. Allen[2] qui définit une ontologie fondée sur les intervalles temporels et un ensemble de 13 relations permettant de repérer les positions remarquables de deux intervalles (l’un peut être contenu dans l’autre, ils peuvent être mitoyens (la borne supérieure de l’un est égale à la borne inférieure de l’autre, etc…).
Par ailleurs, des travaux en algorithmique combinatoire sur les graphes d’intervalles[3] ont mis en évidence l’intérêt à aborder les raisonnements temporels, qui peuvent se traduire en termes de CSP (problèmes à satisfaction de contraintes) exprimés par des graphes d’intervalles. L’adaptation d’algorithmes de résolution qui s’avèrent être NP-Complets dans le cas général, permet de ramener la complexité au cas polynomial pour certains problèmes temporels.
Le but du stage est d’étudier à partir des deux articles cités en référence les algorithmes de résolutions des problèmes temporels proposés et de le implémenter. Dans la mesure du possible on décrira la classe de problèmes temporels susceptibles d’être résolus en utilisant ces agorithmes.
Par ailleurs, G. Ligozat[4] propose une généralisation de la notion d’intervalle temporels, on demande d’étudier l’adaptation des algorithmes précédents à ces intervalles généralisés et d’étudier l’incidence de cette généralisation sur la complexité des algorithmes.
A titre de validation, un petit texte correspondant à une énigme policière sera utilisée pour tester le type de raisonnement susceptible d’être mené[5].
4. Equipe TII
Titre : programmes
logiques étendus possibilistes
Encadrants : Pascal Nicolas, Laurent Garcia
Un programme logique étendu est un ensemble de règles de la forme
h¬a1,…,an,
not b1, …, not bm
où h (la tête), les ai (le corps positif) et les bj (le corps négatif) sont des littéraux. Intuitivement, la règle a¬b,c, not d peut se lire « si l'on a b, c et si l'on n'a pas d alors on peut conclure a ». De manière formelle, la sémantique utilisée dans ce travail sera celle des ensembles réponses définie dans [3]. Ainsi, les programmes logiques munis de cette sémantique fournissent un formalisme non monotone de représentation des connaissances au même titre que la logique des défauts dont ils constituent un sous-ensemble.
Basée sur la théorie des possibilités [2], la logique possibiliste [1] est une logique qui permet de traiter de manière qualitative des informations entachées d'incertitude. De manière simple, elle attache à des formules de la logique classique un degré permettant de décrire le niveau de confiance de ces formules (c'est-à-dire que les degrés décrivent à quel point ces formules sont certainement vraies). Ce degré, compris entre 0 et 1, est exprimé à partir des deux mesures duales de possibilité et de nécessité définies dans la théorie des possibilités.
L'objectif de ce stage est d'étudier comment utiliser les notions développées dans le cadre de la logique possibiliste pour intégrer le traitement de l'incertitude dans le formalisme de la programmation logique étendue.
Bibliographie
[1]
D. Dubois, J. Lang, and H. Prade. Possibilistic logic. In D. Gabbay,
C. Hogger, and J. Robinson, editors, Handbook of Logic in
Artificial Intelligence and Logic Programming, volume 3, pages
439-513. Oxford University Press, 1995.
[2] D. Dubois and H. Prade, editors. Possibility
Theory - An Approach to Computerized Processing of Uncertainty. Plenum
Press, New-York, 1988.
[3] M. Gelfond and V. Lifschitz.
Classical negation in logic programs and disjunctive databases. New
Generation Computing, 9(3-4):363-385, 1991.
Titre : résolution
de formules booléennes quantifiées
Encadrants : Pascal Nicolas, Igor Stéphan
Une formule booléenne quantifiée (QBF) [1] est une formule composée de n variables propositionnelles toutes quantifiées par l'un des quantificateurs " ou $. Dans ce travail on se restreindra aux formules de la classe QBF2,$, c'est-à-dire de la forme
$ x1, x2,,…
"y1,
y2, … j
Une telle formule est valide, s'il existe une affectation (vrai ou faux) de chacune des variables quantifiées existentiellement (les xi) qui, quelle que soit l'affectation (vrai ou faux) donnée aux variables quantifiées universellement (les yj), rende vraie la formule j.
La première partie du stage de DEA consiste à faire le point sur les systèmes existants aptes à résoudre le problème de décision (savoir si la formule est valide ou non) et le problème de recherche (trouver l'affectation des variables xi qui rend la formule valide). De nombreuses informations sont disponibles sur le site web www.qbflib.org.
Dans le cas où la formule jest une conjonction de n formules j1,…, jn, le problème MAXQBF2,$, consiste à trouver l'affectation des xi qui maximise le nombre de sous-formules ji, qui sont satisfaites. La deuxième partie du stage consiste à proposer une méthode de résolution du problème MAXQBF2,$ à l'aide d'un algorithme génétique.
Bibliographie
[1] S. Coste-Marquis, H. Fargier, J. Lang, D. Le Berre, and P. Marquis. Résolution de formules booléennes quantifiées : problèmes et algorithmes. In Actes du 13ème Congrès Reconnaissance des Formes et Intelligence Artificielle (RFIA'02), pages 289-298, 2002.
5. Stages inter-équipes et inter-labos
Temps
linguistique et graphes conceptuels
Tassadit Amghar, David Genest
La détermination des connaissances temporelles associées à un ensemble d’évènements décrits dans un texte narratif met en particulier en jeu le temps, l’aspect et la signification des lexèmes verbaux de l’expression langagière associée à ces évènements.
Ces connaissances doivent permettre de reconstruire l’ordre chronologique des actions ou évènements décrits dans le texte afin, par exemple, de pouvoir réaliser des raisonnements analogues à ceux impliqués naturellement à la lecture d’un texte, dans le processus de réponse à des questions du type Quand est-ce arrivé ? L’action X est elle terminée ? …
Le langage des schèmes sémantico-cognitifs introduit par JP Desclés permet d’exprimer les différents éléments qui caractérisent l’information temporelle d’un point de vue linguistique à partir d’un ensemble de primitives sémantico-cognitives. Si, dans sa forme, il est bien adapté à une utilisation non automatisée, il reste problématique sitôt que l’on désire aboutir à un modèle informatique implémenté.
C’est pourquoi il est important de réaliser la traduction de connaissances temporelles initialement représentées dans ce formalisme en un langage de représentation des connaissances - le langage des graphes conceptuels de J. Sowa - connu pour son adéquation avec les applications du TALN et qui permet de réaliser automatiquement des raisonnements de sens commun. Les deux formalismes s'opposent principalement sur la part efficace de représentation/traitement qu'ils offrent. Les schèmes sémantico-cognitifs permettent en effet de représenter finement les nuances de la langue. Les graphes conceptuels quant à eux permettent de manipuler des représentations par le biais d'un ensemble d'opérations d'inférence.
Une première étude et une implémentation dans le langage Prolog, d’un tel changement de langage de représentation ont dores et déjà été réalisées pour des textes du type de celui qui suit, extrait d’un corpus d’accidents automobiles :
(1)Etant
arrêté momentanément sur la file droite du Bd des Italiens, (2)j'avais mis mon
clignotant, (3)j'étais à l'arrêt. (4)Le véhicule B arrivant sur ma gauche
(5)m'a serré de trop près et (6)m'a abîmé tout le côté avant gauche.
Le travail à réaliser consistera dans un premier temps à adapter l’implémentation précédemment réalisée à la plate-forme de manipulation de graphes conceptuels CoGITaNT implémentée en C++.
Une seconde étape permettra de poursuivre ce travail, en utilisant la possibilité offerte par CoGITaNT d’utiliser non plus des graphes conceptuels simples mais des graphes conceptuels emboîtés afin d’affiner la représentation des connaissances temporelles.
La conception et la validation du travail s’appuiera sur le corpus de constats illustré par le texte précédent.
Fouille
de règles d’exception
Béatrice DUVAL (LERIA
– Univ. Angers - bd@info.univ-angers.fr)
Fabrice Guillet (IRIN – Univ. Nantes – Fabrice.Guillet@polytech.univ-nantes.fr)
Dans le contexte de l’extraction des connaissances dans les données, la recherche de règles d’association s’appuie sur des critères permettant de retenir des règles solides, ayant par exemple un support et une confiance élevée. Cependant, confrontés à des ensembles de règles très volumineux, les décideurs ont besoin d’être aidés et guidés à l’aide de mesures de qualité [Tan et al., 2002] vers les règles qui sont susceptibles de les intéresser : par exemple les règles surprenantes [Gras et al., 2001]. Parmi les règles surprenantes, un intérêt tout spécial s’est porté sur les règles d’exception qui décrivent des situations déviant des situations habituelles décrites par des règles appelées règles de sens commun. Dans l’approche dite subjective, les règles de sens commun sont données par l’utilisateur et la recherche d’exceptions est alors un moyen de préciser les connaissances a priori sur le domaine. Dans l’approche objective, les règles de sens commun sont extraites automatiquement tout comme les règles d’exception.
L’objectif du travail est d’étudier les techniques de fouille de règles d’exception. Un intérêt particulier devra être porté sur la conception d’algorithmes efficaces et leur couplage à des indices de qualité adéquats. Il est notamment demandé d’implémenter un système de fouille de règles d’exception permettant de comparer les différents indices proposés dans la littérature : support et confiance, indice entropique, intensité d’implication, …. Ce travail doit permettre de préciser quelles mesures sont pertinentes dans le contexte particulier de la recherche d’exceptions. Enfin ce travail devra poser les bases de l’interactivité de ces algorithmes avec le décideur afin de le guider vers la découverte des règles surprenantes.
Plan de travail proposé :
1) Etudier les algorithmes et les indices proposés dans la littérature pour le calcul de règles d’exception. [Hussain et al. 2000, Duval et al. 2003]
2) Implémenter un algorithme efficace couplé à des indices pertinents facilitant la découverte des « meilleures » règles d’exception. Valider cet algorithme sur des jeux de données synthétiques et de données réelles.
3) Proposer une adaptation locale de cet algorithme pour l’intégrer à une approche interactive permettant à l’utilisateur de cibler les règles intéressantes sans avoir à parcourir l’ensemble des règles possibles. Pour cela on pourra utiliser une approche de ciblage (focusing) [Blanchard et al. 2003] vers des sous-ensembles réduits de règles intéressantes et d’associations entre ensembles cibles par des relations de voisinage (i.e. le voisinage d’une règle peut être ses meilleures exceptions).
Biliographie :
J.Blanchard,
F.Guillet, H. Briand. A
User-driven and Quality oriented Visualization for Mining Association Rules. In
Proc. of the Third IEEE International Conference on Data Mining, , ICDM'2003,
Melbourne, Florida, USA, November 19 - 22, 2003
Tan P., Kumar V., Srivastava J. (2002). Selecting the right Interestingness measure for association patterns. Actes ACM SIGKDD international conference on knowledge discovery and data mining KDD 2002. Edmonton, Canada.
R. Gras, P. Kuntz, R. Couturier, F. Guillet. Une version entropique de l'intensite d'implication pour les corpus volumineux. Extraction des Connaissances et Apprentissage (ECA), vol. 1, n? 1-2, 69-80, 2001. Hermes Science Publication.
B. Duval, A. Salleb, C. Vrain. Méthodes et mesures d'intérêt pour l'extraction de règles d'exception. Rapport du groupe de travail Gafoqualité de l'action STIC N°20 du CNRS. Soumis à la revue RNTI.
F. Hussain, H. Liu, E. Suzuki, H. Lu. Exception rule mining with a relative interestingness measure. PAKDD2000.
Edition intelligente de graphes
Ce
stage se déroule en co-encadrement entre le LERIA d'Angers et l'IRIN de Nantes.
La
nécessité de visualiser et/ou éditer des graphes sur écran est de plus en plus
importante dans de nombreux domaines (chemins dans le WEB, visualisation de
résolution utilisant les graphes, graphes utilisés pour représenter des
connaissances...), des travaux fondamentaux ont été réalisés par l'équipe de
recherche de l'IRIN pour optimiser "syntaxiquement" cette
visualisation (par exemple en minimisant le nombre de croisements des arcs).
Les
modèles de représentation et de raisonnement à base de connaissances prennent
une place croissante pour développer les systèmes informatiques de demain, dits
"intelligents". Parmi ces modèles, il existe un modèle utilisant des
graphes portant du sens (sémantique): le modèle dit "à base de
graphe conceptuel". De nombreux travaux de l'équipe SBCI du LERIA portent
sur ce modèle.
Il
s'agit dans ce stage d'étudier comment la sémantique portée par le modèle des
graphes conceptuels peut être utilisée pour visualiser et éditer des graphes en
général, et des graphes conceptuels en particulier.
Le
déroulement du stage se fera comme suit:
1)
Etude bibliographique sur la visualisation de graphes et le modèle des graphes
conceptuels. Cette étude se fera en même temps qu'une expérimentation des
outils d'édition de graphes des deux équipes, voire d'ailleurs si cela peut
être profitable
2)
Des propositions nouvelles pour éditer des graphes seront effectuées.
Elles
utiliseront la sémantique portée par le modèle des graphes conceptuels pour
visualiser et éditer des graphes conceptuels.
Un
domaine d'expérimentation sera choisi pour montrer la pertinence de l'approche.
Ce domaine pourra être un domaine déjà étudié par l'équipe du LERIA (ex:
recherche documentaire, accidentologie), ou un autre domaine (web sémantique).
Ces
propositions seront validées par un programme.
3)
Le mémoire de stage présentera les résultats obtenus en mettant l'accent sur
les nouveautés de l'approche.
Lieu
du stage:
à
l'EPUN de Nantes ou au LERIA d'Angers, (à discuter)
Contact
et encadrement:
Vous
pouvez contacter n'importe laquelle des trois personnes suivantes
P.
Kuntz (IRIN), pascale.kuntz@polytech.univ-nantes.fr
D.
Genest (LERIA), genest@info.univ-angers.fr
S.
Loiseau (LERIA), loiseau@info.univ-angers.fr
Résolution hybride distribuée de problèmes contraints
Mots-clés : programmation distribuée,
techniques hybrides, résolution de contraintes
Encadrants : Eric
Monfroy, équipe BCC, thème CoCoA, IRIN, Nantes
Bureau 223, 02 51 12 58 53,
Eric.Monfroy@irin.univ-nantes.fr
Frédéric
Saubion, équipe MOC, LERIA, Angers
Bureau H109,
02 41 73 52 23, Frederic.Saubion@univ-angers.fr
Description
du sujet : Conception d’un
solveur distribué hybride pour les problèmes de satisfaction de contraintes
Domaine :
La résolution des problèmes de satisfaction de contraintes (CSP) peut être abordée essentiellement sous deux angles, en utilisant des méthodes complètes ou incomplètes. Une approche complète a pour but de calculer toutes les solutions du problème ou de détecter éventuellement son inconsistance. Parmi ces diverses techniques, la propagation de contraintes apparaît comme l’un des outils les plus génériques et les plus fréquemment utilisés. Toutefois, ce type de résolution trouve ses limites lorsque l’espace de recherche augmente de manière importante. Afin de palier cette limitation, des algorithmes incomplets (ou approchés) ont été développés. Ces algorithmes peuvent fournir des solutions de très bonne qualité sur des problèmes de taille importante. Ils reposent principalement sur les concepts de recherche locale (recuit simulé, tabou).
Objectifs :
L’objectif
de ce stage sera d’étudier la mise en collaboration de ces deux types
d’approches au sein d’un modèle de calcul distribué et/ou parallèle et/ou
concurrent. Cette étude s’intéressera à la fois à une utilisation
parallèle/distribuée des composants de résolution (à la fois recherche locale
et propagation de contraintes) et de l’espace de recherche. Cette
parallélisation/distribution pourra de plus être abordée selon plusieurs
niveaux de granularité, allant de granularités fortes (telle que coopération
haut niveau entre recherche locale et propagation de contraintes) aux
granularités les plus fines (coopération entre les briques de base de la
recherche locale et de la propagation). Ces différents niveaux de granularité
permettront une étude approfondie de la complémentarité des mécanismes de
résolution.
Ce
stage permettra à l’étudiant qui le choisira d’aborder à la fois les techniques classiques utilisées pour la
résolution des CSP et de développer ses
compétences en ce qui concerne la conception d’applications distribuées/reparties
selon les différentes architectures et techniques qu’il aura étudiées et décidé
d’expérimenter.
Organisation
du travail : A discuter avec les encadrants.
Contexte :
La
résolution hybride et distribuée de contraintes est un domaine émergent au
croisement de la recherche locale, de la programmation par contrainte, et de la
programmation distribuée.
Ce
thème de recherche pourra être poursuivi en thèse. Ce travail s’inscrit dans le
cadre du projet CPER COM et de la collaboration existante entre l’IRIN et le
LERIA et portant sur l’étude de tels modèles de résolution hybrides.
Bibliographie :
Domaines :
programmation par contrainte, recherche locale, programmation distribuée.
Titre : Résolution
de programmes logiques étendus
Encadrants : Pascal Nicolas, Frédéric Saubion et Igor Stéphan
Un programme logique étendu est un ensemble de règles de la forme
h¬a1,…,an,
not b1, …, not bm
où h (la tête), les ai (le corps positif) et les bj (le corps négatif) sont des littéraux. Intuitivement, la règle a¬b,c, not d peut se lire « si l'on a b, c et si l'on n'a pas d alors on peut conclure a ». De manière formelle, la sémantique utilisée dans ce travail sera celle des ensembles réponses définie dans [2]. Ainsi, les programmes logiques munis de cette sémantique fournissent un formalisme non monotone de représentation des connaissances au même titre que la logique des défauts dont ils constituent un sous-ensemble. La perte de pouvoir de représentation par rapport à la logique des défauts est compensée par une plus faible complexité algorithmique permettant ainsi le développement de système de calculs de modèles stables aux performances satisfaisantes comme notamment :
Objectif : L'objectif de ce stage sera de concevoir et d'implémenter une méthode complète de calcul des ensembles réponses d'un programme donné en ayant une approche basée sur les règles, alors que les autres systèmes existants comme Smodels et DLV basent leur recherche sur les littéraux.
Une seconde phase du travail consistera alors à expérimenter le système obtenu sur un ensemble de jeux d'essais en s'appuyant sur les instances utilisées dans le cadre de la résolution du problème SAT. Cette phase expérimentale pourra initier une étude plus approfondie de la structure des instances utilisées afin d'en caractériser la difficulté.
Compétences : Ce stage permettra d'aborder les mécanismes complets de résolution dans le contexte particulier du raisonnement non monotone. Le travail demandé repose à la fois sur une étude des aspects théoriques de la résolution et sur la mise en pratique des méthodes qui en résulteront. Le choix de l'environnement de développement est laissé libre.
Bibliographie
[1] T. Eiter, N. Leone, C. Mateis,
G. Pfeifer, and F. Scarcello. The kr system dlv:progress report,
comparisons and benchmarks. In A. G. Cohn, L. Schubert, and
S. C. Shapiro, editors, Proceedings of the Sixth International
Conference on the Principles of Knowledge Representation and Reasoning,
pages 406-417. Morgan
Kaufmann Publishers, 1998.
[2] M. Gelfond and V. Lifschitz.
Classical negation in logic programs and disjunctive databases. New
Generation Computing, 9(3-4):363-385, 1991.
[3] I. Niemelä and P. Simons. Smodels -
an implementation of the stable model and well-founded semantics for normal
logic programs. In Proceedings of LPNMR, volume 1265 of Lecture
Notes in Artificial Intelligence, pages 420-429, 1997.
Fouille de connaissances – Une
approche cube de connaissances
Stéphane Loiseau
(LERIA – Univ. Angers - loiseau@info.univ-angers.fr)
Fabrice Guillet (IRIN – Univ. Nantes – Fabrice.Guillet@polytech.univ-nantes.fr)
L’évolution des systèmes informatiques s’oriente vers des systèmes d’informatique décisionnelle, dont l’enjeu réside dans une meilleure coopération entre systèmes informatiques et décideurs afin d’en améliorer la prise de décision. En particulier, dans le contexte de connaissances, ce sujet s’intéresse aux systèmes de raisonnement qui font collaborer un système informatique et les capacités de résolution de l'utilisateur humain.
Dans ce cadre, nous proposons une nouvelle approche mélangeant des aspects inférentiels décidés par le système avec les décisions/interprétations effectuées par l'utilisateur. Il s'agit concrètement de s’inspirer de l’approche fouille de données des cubes de données proposées en data-warehouse, afin de les appliquer non plus à des données mais à des connaissances afin de proposer un véritable cube de connaissances au décideur.
Le système exprimera son originalité selon deux points de vue par rapport au cubes de données classiques:
- Interprétation : l'information représentée devra être plus riche car elle devra représenter de véritables connaissances et une organisation de ces connaissances ayant un sens pour la prise de décision de l’ utilisateur ;
- Inférence et résolution : des processus inférentiels automatiques devront pouvoir être déclenchés sur la connaissance afin de permettre le déroulement d’un raisonnement automatique lors de l'utilisation du cube de connaissances.
Il sera donc nécessaire de définir des structures permettant l’organisation de la connaissance, de définir la manière de représenter les connaissances dans un cube, et de définir les opérateurs de manipulation des connaissances et de leur activation. Ainsi, des pliages, dépliages, inférence, raisonnement sous hypothèses seront possibles. Des règles de type datalog, et des terminologies (par exemple un support du modèle des graphes conceptuels) seront des approches potentielles.
Plan de travail proposé :
1. Etudier les techniques de fouille de cubes de données proposées en datawhare house et les modèles de représentation des connaissances dotés de capacités inférentielles (graphes conceptuels, rdf, …).
2. Proposer un mode d’organisation (définitions des dimensions) des connaissances dans le cube en facilitant l’accès, l’intelligibilité, la manipulation, la mesure de qualité et l’inférence.
3. Réaliser un prototype implémentant les solutions choisies.
Biliographie :
J.Blanchard,
F.Guillet, H. Briand. A
User-driven and Quality oriented Visualization for Mining Association Rules. In
Proc. of the Third IEEE International Conference on Data Mining, , ICDM'2003,
Melbourne, Florida, USA, November 19 - 22, 2003
Tan P., Kumar V., Srivastava J. (2002). Selecting the right Interestingness measure for association patterns. Actes ACM SIGKDD international conference on knowledge discovery and data mining KDD 2002. Edmonton, Canada.
R. Gras, P. Kuntz, R. Couturier, F. Guillet. Une version entropique de l'intensite d'implication pour les corpus volumineux. Extraction des Connaissances et Apprenti
G.Assadoui, D. Genest, S. Loiseau cartes cognitives de graphes conceptuels. RFIA 2004, à paraitre.
S. Loiseau Systèmes à base de connaissances, univ. Angers 2003