Author name cluster

Dan Suciu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

JAIR Journal 2022 Journal Article

On the Tractability of SHAP Explanations

Guy Van den Broeck
Anton Lykov
Maximilian Schleich
Dan Suciu

SHAP explanations are a popular feature-attribution mechanism for explainable AI. They use game-theoretic notions to measure the influence of individual features on the prediction of a machine learning model. Despite a lot of recent interest from both academia and industry, it is not known whether SHAP explanations of common machine learning models can be computed efficiently. In this paper, we establish the complexity of computing the SHAP explanation in three important settings. First, we consider fully-factorized data distributions, and show that the complexity of computing the SHAP explanation is the same as the complexity of computing the expected value of the model. This fully-factorized setting is often used to simplify the SHAP computation, yet our results show that the computation can be intractable for commonly used models such as logistic regression. Going beyond fully-factorized distributions, we show that computing SHAP explanations is already intractable for a very simple setting: computing SHAP explanations of trivial classifiers over naive Bayes distributions. Finally, we show that even computing SHAP over the empirical distribution is #P-hard.

PDF Details DOI

AAAI Conference 2021 Conference Paper

On the Tractability of SHAP Explanations

Guy Van den Broeck
Anton Lykov
Maximilian Schleich
Dan Suciu

SHAP explanations are a popular feature-attribution mechanism for explainable AI. They use game-theoretic notions to measure the influence of individual features on the prediction of a machine learning model. Despite a lot of recent interest from both academia and industry, it is not known whether SHAP explanations of common machine learning models can be computed efficiently. In this paper, we establish the complexity of computing the SHAP explanation in three important settings. First, we consider fully-factorized data distributions, and show that the complexity of computing the SHAP explanation is the same as the complexity of computing the expected value of the model. This fully-factorized setting is often used to simplify the SHAP computation, yet our results show that the computation can be intractable for commonly used models such as logistic regression. Going beyond fullyfactorized distributions, we show that computing SHAP explanations is already intractable for a very simple setting: computing SHAP explanations of trivial classifiers over naive Bayes distributions. Finally, we show that even computing SHAP over the empirical distribution is #P-hard.

PDF Details

Highlights Conference 2014 Conference Abstract

Invited talk: Communication Cost in Parallel Query Processing

Dan Suciu

Fix a full, conjunctive query, and consider the following problem: what is the amount of communication required to compute the query in parallel on p servers, over a large database instance? We define the Massively Parallel Communication (MPC) model, where the computation proceeds in rounds consisting of local computations followed by a global reshuffling of the data. Servers have unlimited computational power and are allowed to exchange any data, the only cost parameters are the number of rounds and the maximum amount of communication per server. There is a tradeoff between these two parameters. I will describe tight bounds on the amount of communication for the case of a single round, expressed in terms of a fractional edge packing of the query expression, and will given some weaker results for multi-round algorithms. Both these settings assume data with no skew. Finally, I will briefly discuss the single round, skewed-data case. Joint work with Paul Beame and Paris Koutris. 10: 00 10: 30 Breakfast & coffee

PDF Details

UAI Conference 2014 Conference Paper

Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting

Eric Gribkoff
Guy Van den Broeck
Dan Suciu

In this paper we study lifted inference for the Weighted First-Order Model Counting problem (WFOMC), which counts the assignments that satisfy a given sentence in first-order logic (FOL); it has applications in Statistical Relational Learning (SRL) and Probabilistic Databases (PDB). We present several results. First, we describe a lifted inference algorithm that generalizes prior approaches in SRL and PDB. Second, we provide a novel dichotomy result for a non-trivial fragment of FO CNF sentences, showing that for each sentence the WFOMC problem is either in PTIME or #Phard in the size of the input domain; we prove that, in the first case our algorithm solves the WFOMC problem in PTIME, and in the second case it fails. Third, we present several properties of the algorithm. Finally, we discuss limitations of lifted inference for symmetric probabilistic databases (where the weights of ground literals depend only on the relation name, and not on the constants of the domain), and prove the impossibility of a dichotomy result for the complexity of probabilistic inference for the entire language FOL.

Details

UAI Conference 2013 Conference Paper

Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases

Paul Beame
Jerry Li 0001
Sudeepa Roy 0001
Dan Suciu

The best current methods for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas can be seen, either directly or indirectly, as building decision-DNNF (decision decomposable negation normal form) representations of the input Boolean formulas. Decision-DNNFs are a special case of d- DNNFs where d stands for deterministic. We show that any decision-DNNF can be converted into an equivalent FBDD (free binary decision diagram) – also known as a readonce branching program (ROBP or 1-BP) – with only a quasipolynomial increase in representation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Leveraging known exponential lower bounds for FBDDs, we then obtain similar exponential lower bounds for decision-DNNFs which provide lower bounds for the recent algorithms. We also separate the power of decision-DNNFs from d-DNNFs and a generalization of decision-DNNFs known as AND- FBDDs. Finally we show how these imply exponential lower bounds for natural problems associated with probabilistic databases.

Details

NeurIPS Conference 2010 Conference Paper

Lifted Inference Seen from the Other Side : The Tractable Features

Abhay Jha
Vibhav Gogate
Alexandra Meliou
Dan Suciu

Lifted inference algorithms for representations that combine first-order logic and probabilistic graphical models have been the focus of much recent research. All lifted algorithms developed to date are based on the same underlying idea: take a standard probabilistic inference algorithm (e. g. , variable elimination, belief propagation etc. ) and improve its efficiency by exploiting repeated structure in the first-order model. In this paper, we propose an approach from the other side in that we use techniques from logic for probabilistic inference. In particular, we define a set of rules that look only at the logical representation to identify models for which exact efficient inference is possible. We show that our rules yield several new tractable classes that cannot be solved efficiently by any of the existing techniques.

PDF Details

I&C Journal 2001 Journal Article

Equivalence and Normal Forms for the Restricted and Bounded Fixpoint in the Nested Algebra

Marc Gyssens
Dan Suciu
Dirk Van Gucht

The nested model is an extension of the traditional, “flat” relational model in which relations can also have relation-valued entries. Its “default” query language, the nested algebra, is rather weak, unfortunately, since it is only a conservative extension of the traditional, flat relational algebra, and thus can express only a small fraction of the polynomial-time queries. Therefore, it was proposed to extend the nested algebra with a fixpoint construct, but the resulting language turned out to be too powerful: many inherently exponential queries could also be expressed. Two polynomial-time restrictions of the fixpoint closure of the nested algebra were proposed: the restricted fixpoint closure (by Gyssens and Van Gucht) and the bounded fixpoint closure (by Suciu). Here, we prove two results. First we show that both restrictions are equivalent in expressive power. The proof technique relies on known encodings of nested relations into flat ones, and on a novel technique, called type substitution, by which we reduce the equivalence of the two restrictions to its obvious counterpart in the flat relational model. Second we prove that both the bounded fixpoint queries and the restricted fixpoint queries admit normal forms, in which the fixpoint occurs exactly once. The proof technique relies on a novel encoding method of nested relations into flat ones.

Details DOI

IJCAI Conference 1999 Conference Paper

Verifying Integrity Constraints on Web Sites

Mary Ferndndez
Daniela Florescu
Alon Levy
Dan Suciu

Data-intensive Web sites have created a new form of knowledge base, as richly structured bodies of data. Several novel systems for creating dataintensive Web sites support declarative specification of a site's structure and content (i. e. , the pages, the data available in each page, and the links between pages). Declarative systems provide a platform on which A1 techniques can be developed that, further simplify the tasks of constructing and maintaining Web sites. This paper addresses the problem of specifying and verifying integrity constraints on a Web site's structure. We describe a language that can capture many practical constraints and an accompanying sound and complete verification algorithm. The algorithm has the important property that if the constraints are violated, it proposes fixes to either the constraints or to the site definition. Finally, we establish tight bounds on the complexity of the verification problem we consider.

PDF

TCS Journal 1998 Journal Article

Domain-independent queries on databases with external functions

Dan Suciu

We study queries over databases with external functions, from a language-independent perspective. The input and output types of the external functions can be atomic values, flat relations, nested relations, etc. We propose a new notion of data-independence for queries on databases with external functions, which extends naturally the notion of generic queries on relational databases without external functions. In contrast to previous such notions, ours can also be applied to queries expressed in query languages with iterations. Next, we propose two natural notions of computability for queries over databases with external functions, and prove that they are equivalent, under reasonable assumptions. Thus, our definition of computability is robust. Finally, based on this equivalence result, we give examples of complete query languages with external functions. A byproduct of the equivalence result is the fact that Relational Machines (Abiteboul and V. Vianu, 1991; Abiteboul et al. , 1992) are complete on nested relations: they are known not to be complete on flat relations.

Details DOI

TCS Journal 1997 Journal Article

Bounded fixpoints for complex objects

Dan Suciu

We study a query language for complex-object databases, which is designed to (1) express only tractable queries, and (2) be as expressive over flat relations as first-order logic with fixpoints. The language is obtained by extending the nested relational algebra, NRA, with a “bounded fixpoint” operator. Similar to results for flat relations, all tractable queries over ordered databases are expressible in this language. The main result consists in proving that this language is a conservative extension of the first-order logic with fixpoints, or of the while-queries, (depending on the interpretation of the bounded fixpoint: inflationary or partial). That is, a query from flat relations to flat relations is expressible in our language if and only if it is expressible in first-order logic with fixpoints, or in the while-queries, respectively. The proof technique for this theorem uses indexes to encode complex objects into flat relations. It can serve as basis for an implementation method of complex objects databases in terms of relational databases, which works well for queries expressed both with fixpoints and with bounded fixpoint. We also define a complex object logical calculus with fixpoints and prove that its range-restricted fragment is equivalent to NRA with bounded fixpoints.

Details DOI