Le CRIL en bref

présentation

Le Centre de Recherche en Informatique de Lens (CRIL UMR 8188) est un laboratoire de l’Université d’Artois et du CNRS qui regroupe plus de cinquante membres : chercheurs, enseignants-chercheurs, doctorants et personnels administratifs et techniques.

En savoir

Recherches en intelligence artificielle et applications

mots clés du CRIL

Actualités (RSS)

Séminaire Autour des classes polynomiales pour les problèmes de satisfaction de contraintes

Achref El Mouelhi

Le problème de satisfaction des contraintes CSP (pour Constraint Satisfaction Problems en anglais) est connu pour être NP-complet, même pour le cas binaire. Cependant, en imposant certaines restrictions, sur la taille des domaines ou sur les contraintes, la résolution peut être accomplie en temps polynomial. Dans ce cas, on parle des propriétés traitables (tractables properties). L’ensemble d’instances satisfaisant une propriété traitable constitue une classe polynomiale (ou traitable). Par exemple, Il est connu que l’ensemble des instances qui satisfont la propriété des triangles cassés BTP (pour Broken-Triangle Property) ou ZOA (Zero/One/All) définissent des classes polynomiales pour les CSP binaires. En pratique, les classes polynomiales sont rarement présentes. En plus, elles nécessitent généralement des algorithmes ad-hoc pour la reconnaissance et pour la résolution. Par conséquent, les algorithmes de l’état de l’art comme, FC (pour Forward Checking), RFL (pour Real Full Lookahead) ou MAC (pour Maintaining Arc-Consistency) ne peuvent pas les exploiter.
Récemment, des efforts considérables ont été consacrés à l’identification des classes polynomiales qui sont facilement exploitées par les algorithmes de l’état de l’art cités ci-dessus. Par exemple, il a été prouvé que l’ensemble d’instances CSP ayant un nombre polynomial de cliques maximales dans le graphe de microstructure peuvent être résolues en temps polynomial par les algorithmes de résolution classiques. Ensuite, un nouveau cadre dont le but est d’étendre le champ des classes polynomiales a été proposé. En effet, il est basé sur la notion de transformation de CSP et introduit la notion de classe polynomiale cachée. Elle part du constat selon lequel les problèmes réels n’appartiennent pas en général à des classes polynomiales mais peuvent parfois, après simplification (en appliquant certains algorithmes de filtrages par cohérence locale, par exemple) en faire partie. Aussi, certains travaux ont montré que les propriétés traitables peuvent être utilisées pour éliminer des variables, fusionner des valeurs ou décomposer des contraintes tout en préservant la satisfiabilité. Plus précisément, l’absence de triangles cassés sur tous les couples de valeurs d’une variable d’une instance CSP arc-cohérente autorise l’élimination de cette variable sans affecter la satisfiabilité de l’instance. L’absence de triangles cassés sur un couple de valeurs d’une même variable d’une instance CSP donnée permet également de les fusionner sans modifier la satisfiabilité de l’instance.

Mots clés :
CSP, propriété traitable, triangle cassé, fusion de valeurs, élimination de variables.

En savoir

Séminaire Plausible Reasoning about Ontologies

Zied Bouraoui

Structured knowledge about entities increasingly plays an important role in various web applications (e.g. search engines, recommendation sites, and social networks). Such knowledge is available, for example, in ontologies such as SUMO or OpenCyc, in knowledge graphs such as DBpedia, Google Freebase, Facebook Graph and WikiData, as semantic markup (e.g. RDFa), or on web pages (e.g. in the form of tables, lists, or natural language assertions). While these web applications typically require some form of reasoning, deduction is often too limited in this setting. One cause for this limitation is that the available information may be conflicting. For instance, the concept “ice cream shop” is considered as type of “restaurant” on Wikipedia, but is disjoint from “restaurant” in OpenCyc. Another reason for this limitation is that available knowledge is often incomplete. For example, the SUMO ontology encodes knowledge about summer olympics games such as Basketball, Football and Handball, but mentions nothing about Beach volleyball. Clearly, web applications would benefit from robust commonsense reasoning methods that could handle inconsistency and incompleteness in a principled data-driven way.
Commonsense reasoning is a well-known problem in artificial intelligence. This problem has at least two facets. The first, largely studied in KR, concerns nonmonotonic reasoning frameworks, such as default logics and answer set programming. The second, which has traditionally been less addressed in KR, but has been widely studied in other research areas such as machine learning or information retrieval, relates to similarity and analogy based reasoning, including induction. Similarity and analogy are naturally a matter of degree, which makes it difficult, or even impossible, to study the latter types of commonsense reasoning in a purely symbolic setting.

To address this point, we developed a number of methods for robust and flexible data- driven reasoning with logic-based structured knowledge from the web (i.e. description logics or existential rules). At the centre of this work are semantic spaces, which act as an interface between logical representations and data, together with an efficient Bayesian inference machinery that allows us to make plausible inferences in a principled way. Semantic spaces are vector space representation of entities, which have been widely studied in the cognitive science literature to model phenomena such as categorisation, induction, vagueness, typicality, etc.

In this talk, I will show how such semantic spaces can be generated from a combination of structured knowledge and bag-of-words representations. I will then introduce a Bayesian method which is inspired by cognitive models of category based induction. This method is useful for deriving concept membership (e.g. x is a kind of X) and subsumption (e.g. every X is a Y) assertions, but it can not directly be applied to model relations between entities or
concepts (for instance, a rule of the form \forall x \forall y R(x,y) -> \exists z P(z,x) ). To overcome this limitation, three additional methods have been investigated. The first views this problem of “relation induction” as a Bayesian regression problem, the second considers it as a special case of category based induction, and the third models a form of analogical reasoning. Our experimental results show that this approaches can substantially outperform state-of-the-art methods for knowledge base completion.

Keywords:
Ontologies, Description Logics, Bayesian Inference, Vector Space Embeddings, Data-Driven Reasoning.

En savoir

Séminaire Resource games and redistributions

Nicolas Troquard

Séminaire Reasoning Defeasibly over Ontologies

Ivan Varzinczak (Univ Artois)

Description Logics (DLs) are a family of logic-based knowledge representation formalisms with appealing computational properties and a variety of applications at the confluence of modern artificial intelligence and other areas. In particular, DLs are well-suited for representing and reasoning about ontologies and therefore constitute the formal foundations of the Semantic Web.
The different DL formalisms that have been proposed in the literature provide us with a wide choice of constructors in the object language. However, these are intended to represent only classical, unquestionable knowledge, being unable to express the different aspects of uncertainty and vagueness that often show up in everyday life. Examples of these comprise the various guises of exceptions, typicality (and atypicality), approximations and many others, as usually encountered in the different forms of human quotidian reasoning. A similar argument can be put forward when moving to the level of entailment, that of the sanctioned conclusions from a knowledge base. DL systems provide for a variety of (standard and non-standard) reasoning services, but the underlying notion of entailment remains classical and therefore, depending on the application one has in mind, DLs inherit most of the criticisms raised in the development of the so-called non-classical logics.
In this regard, endowing DLs and their associated reasoning services with the ability to cope with defeasibility is a natural step in their development. Indeed, the past two decades have witnessed the surge of many attempts to introduce non-monotonic reasoning capabilities in a DL setting. These range from preferential approaches to circumscription-based ones, amongst others.
In spite of all the progress that has been achieved in the area, the study of non-monotonic reasoning in DLs remains a large avenue for exploration. To witness, the bulk of the effort in this direction has been put in the definition of accounts of defeasible subsumption and in the characterisation of appropriate notions of defeasible entailment relations. This suggests that existing approaches to reasoning with defeasible inheritance and typicality in ontologies may lack constructors that are important from a modelling perspective. Indeed, here we make a case for a number of additional defeasible constructs at the object level enriching the basic DL concept language and propose a corresponding preferential semantics. We show that this does not negatively affect decidability or complexity of reasoning for an important class of DLs, and that existing notions of preferential reasoning can be expressed in terms of our new constructs.

Keywords: Ontologies, Description Logics, Defeasible Reasoning, Preferential Semantics

En savoir

Participation du CRIL à #FranceIA



Dans le cadre du grand événement public de #FranceIA, la stratégie française en intelligence artificielle, le CRIL sera présent le 21 mars à la cité des sciences, Paris.

Le programme de la journée est disponible en ligne.

Le laboratoire y présentera son joueur de General Game Playing Woodstock, qui a remporté le dernier championnat du monde de la discipline, comme exemple du savoir faire Français dans le domaine.


En savoir