The Valda seminar is held every few weeks, usually at ENS (45 rue d’Ulm, 75005 Paris), and usually on Friday mornings. The seminar calendar is below, and can be also subscribed to: iCalendar (ICS).
Seminar: Nofar Carmeli
Seminar: Nofar Carmeli
4 December 201810:30 - 11:30 ENS, S16
Enumeration of UCQs with Constant Delay
We discuss the complexity of enumerating the answers of Unions of Conjunctive Queries (UCQs), and focus on the ability to list output tuples with constant delay following linear-time preprocessing. A known dichotomy classifies the self-join-free CQs into those that admit such enumeration, and those that do not. However, this classification no longer holds in the common case where the database exhibits dependencies among attributes. In such cases, some queries classified as hard are in fact tractable, and we generalize the dichotomy to accommodate Functional Dependencies (FDs). Next, we aspire to have a similar characterization for UCQs, even when there are no FDs. It was claimed in the past that a UCQ is hard if one of its queries is hard. We examine the task of enumerating UCQs, and show that some unions containing a hard query are tractable. In fact, a UCQ may be tractable even if it does not contain a single tractable CQ.
Reasoning over Existential Rules with Acyclicity Notions
The chase is a sound and complete (albeit non-terminating) algorithm for conjunctive query answering over ontologies of existential rules. On the theoretical side, we develop sufficient conditions to guarantee its termination (i.e., acyclicity notions), and study several restrictions that furthermore ensure its polynomiality. On the practical side, we empirically study the generality of these conditions and we extend the Datalog engine VLog to develop an efficient implementation of the chase. Furthermore, we conduct an extensive evaluation, and show that VLog can compete with the state of the art, regarding runtime, scalability, and memory efficiency.
Knowledge Tracing Machines – Factorization Machines for Knowledge Tracing
Knowledge tracing is a sequence prediction problem where the goal is to predict the outcomes of students over questions as they are interacting with a learning platform. By tracking the evolution of the knowledge of some student, one can provide feedback, and optimize instruction accordingly. Existing methods are either based on temporal latent variable models like deep knowledge tracing, or factor analysis like item response theory. We present factorization machines (FMs), a model for regression or classification that encompasses several existing models in the educational data mining literature as special cases, notably additive factor model, performance factor model, and multidimensional item response theory. We show, using several real datasets of tens of thousands of users and items, that FMs can estimate student knowledge accurately and fast even when student data is sparsely observed, and handle side information such as multiple knowledge components and number of attempts at item or skill level. We will open up to other applications in crowdsourcing and preference elicitation. To reproduce our experiments, a tutorial is available on: https://github.com/jilljenn/ktm. The article is on arXiv: https://arxiv.org/abs/1811.03388