Séminaire La logique de typicité propositionnelle
Ivan Varzinczak - CRIL CNRS & Univ Artois
Dans cet exposé, je présenterai la logique de typicité propositionnelle PTL. Cette logique enrichît la logique propositionnelle classique avec un opérateur unaire permettant de représenter de façon explicite une notion de typicité d’une formule. L’intuition derrière cet opérateur est de capturer les situations les plus typiques (ou normales, ou conventionnelles, en fonction de l’application en question) où une formule donnée est vraie. La sémantique de PTL est en termes de modèles préférentiels, plus précisément les modèles modulaires, étudiés dans l’approche KLM pour le raisonnement non monotone. Cela nous permet de montrer que les conditionnels à la KLM peuvent être simulés directement dans PTL. Je présenterai certaines propriétés intéressantes de PTL, notamment (1) le fait qu’il y a des formules de PTL qui ne peuvent pas être exprimées comme des conditionnels KLM, et (2) le fait que PTL nous permet de simuler la révision de croyances à la AGM directement dans le langage objet. Cela fait de PTL un formalisme à la fois simple et suffisamment puissant pour servir de framework dans lequel analyser des approches pour le raisonnement non monotone en logique propositionnelle. Je finirai avec une discussion à propos de différentes notions de conséquence logique non monotones dans le cadre de PTL et j’en proposerai trois candidates appropriées.
Pour plus de détails : https://arxiv.org/abs/1809.10946
Séminaire Trust-sensitive Belief Revision
Richard Booth - Cardiff University, UK
Belief revision is concerned with incorporating new information into a pre-existing set of beliefs. When the new information comes from another agent, we must first determine if that agent should be trusted. In this talk, we define trust as a pre-processing step before revision. We emphasise that trust in an agent is often restricted to a particular domain of expertise. We demonstrate that this form of trust can be captured by associating a state partition with each agent, then relativising all reports to this partition before revising. We position the resulting family of trust-sensitive revision operators within the class of selective revision operators of Ferme and Hansson, and we examine its properties. In particular, we show how trust-sensitive revision is manipulable, in the sense that agents can sometimes have incentive to pass on misleading information. This is joint work with Aaron Hunter.
Séminaire Beyond NP Revolution
**Kuldeep Meel - National University of Singapore **
The paradigmatic NP-complete problem of Boolean satisfiability (SAT) solving is a central problem in Computer Science. While the mention of SAT can be traced to early 19th century, efforts to develop practically successful SAT solvers go back to 1950s. The past 20 years have witnessed a “NP revolution” with the development of conflict-driven clause-learning (CDCL) SAT solvers. Such solvers combine a classical backtracking search with a rich set of effective heuristics. While 20 years ago SAT solvers were able to solve instances with at most a few hundred variables, modern SAT solvers solve instances with up to millions of variables in a reasonable time.
The “NP-revolution” opens up opportunities to design practical algorithms with rigorous guarantees for problems in complexity classes beyond NP by replacing a NP oracle with a SAT Solver. In this talk, we will discuss how we use NP revolution to design practical algorithms for two fundamental problems in artificial intelligence and formal methods: Constrained Counting and Sampling
Kuldeep Meel is an Assistant Professor of Computer Science in School of Computing at the National University of Singapore where he holds the Sung Kah Kay Assistant Professorship. He received his Ph.D. (2017) and M.S. (2014) degree in Computer Science from Rice University. He holds B. Tech. (with Honors) degree (2012) in Computer Science and Engineering from Indian Institute of Technology, Bombay. His research interests lie at the intersection of Artificial Intelligence and Formal Methods. Meel has co-presented tutorials at top-tier AI conferences, IJCAI 2018, AAAI 2017, and UAI 2016. His work received the 2018 Ralph Budd Award for Best PhD Thesis in Engineering, 2014 Outstanding Masters Thesis Award from Vienna Center of Logic and Algorithms and Best Student Paper Award at CP 2015. He received the IBM Ph.D. Fellowship and the 2016-17 Lodieska Stockbridge Vaughn Fellowship for his work on constrained sampling and counting.
Communication complexity is a classical subarea of theoretical computer science that is however not very well known in other parts of computer science. It studies basic questions on the communication costs when solving computational problems. There are many applications, e.g. in chip design, distributed algorithms and, more interestingly for AI researchers, in knowledge compilation.
Here I will give a very gentle introduction into some of the basic concepts of communication complexity. We will consider relatively simple models and study different techniques for lower bounds. We will also see how to use these models to prove lower bounds for OBDD representations of Boolean functions. If time allows, we also have a look at some more complicated models and show how they relate to more general representations in knowledge compilation.
This presentation will not be on cutting edge research in the area. Instead, it will be a tutorial on some basic aspects whose goal it is to introduce the members of CRIL to the very pretty area of communication complexity.
Iin this talk, we will first introduce and motivate the verybasic principles of imprecise probabilistic (IP) approaches, that
replace precise-valued probabilities and expectations by bounded
intervals. The talk will then focus on the use of IP in supervised
classification, using the extension of the naive Bayes classifier as
an illustration. Finally, we will briefly mention some challenges
concerning the application of IP to supervised learning over