Weekly Seminar: Logic and Algorithms in Database Theory and AI program

TITLE: Challenges in Building a Provenance-Aware Database Management System

We describe ProvSQL, software currently being developed in our team that adds support for provenance management and probabilistic query evaluation to a regular database management system, PostgreSQL. After recalling how different forms of provenance are computed over relational databases, and giving some basics of probabilistic query evaluation, we discuss research and engineering challenges in implementing techniques from the scientific literature on provenance management and probabilistic databases within a major database management system: use of circuits and knowledge compilation tools to compactly represent provenance and compute probabilities; exploitation of the structural properties of the queries or the database; interaction between provenance computation and query optimization; scaling up; development of application areas; etc.

TITLE: On Computing Probabilistic Explanations for Decision Trees 

LOCATION: Calvin Lab Auditorium

Formal XAI (explainable AI) is a growing area that focuses on computing explanations with mathematical guarantees for the decisions made by ML models. Inside formal XAI, one of the most studied cases is that of explaining the choices taken by decision trees, as they are traditionally deemed as one of the most interpretable classes of models. Recent work has focused on studying the computation of sufficient reasons, a kind of explanation in which given a decision tree T and an instance x, one explains the decision T(x) by providing a subset y of the features of x such that for any other instance z compatible with y, it holds that T(z) = T(x), intuitively meaning that the features in y are already enough to fully justify the classification of x by T. It has been argued, however, that sufficient reasons constitute a restrictive notion of explanation. For such a reason, the community has started to study their probabilistic counterpart, in which one requires that the probability of T(z) = T(x) must be at least some value δ, where z is a random instance that is compatible with y. We show that finding δ-sufficient-reasons that are minimal inclusion-wise does not admit polynomial-time algorithms (unless P = NP). This is in stark contrast with the deterministic case (δ=1) where inclusion-wise minimal sufficient-reasons are easy to compute.
 
This is joint work with: Marcelo Arenas, Miguel Romero and Bernardo Subsercaseaux

This talk can also be followed with the zoom link https://berkeley.zoom.us/my/simonszoom2.

TITLE: Acyclity and Notions of "Width" of Hypergraphs

Answering Conjunctive Queries (CQs) and, likewise solving Constraint Satisfaction Problems (CSPs) are classical NP-complete problems. The underlying structure of CQs and CSPs is captured by hypergraphs and it is well known that both problems become tractable if the underlying hypergraph is acyclic. However, acyclicity is a strong restriction. Consequently, several generalizations of acyclicity have been studied - each coming with some notion of width that measures the degree of cyclicity.Starting from acyclicity, some basic definitions and computational properties of various notions of "width" of hypergraphs will be presented in this talk: treewidth, hypertree width, generalized hypertree width, and fractional hypertree width. Time permitting, also adaptive width and submodular will be briefly mentioned.

This talk can also be followed with the zoom link https://berkeley.zoom.us/my/simonszoom2.