Adnan Darwiche

NeurIPS Conference 2024 Conference Paper

Identifying Causal Effects Under Functional Dependencies

• Yizuo Chen
• Adnan Darwiche

We study the identification of causal effects, motivated by two improvements to identifiability which can be attained if one knows that some variables in a causal graph are functionally determined by their parents (without needing to know the specific functions). First, an unidentifiable causal effect may become identifiable when certain variables are functional. Second, certain functional variables can be excluded from being observed without affecting the identifiability of a causal effect, which may significantly reduce the number of needed variables in observational data. Our results are largely based on an elimination procedure which removes functional variables from a causal graph while preserving key properties in the resulting causal graph, including the identifiability of causal effects.

JELIA Conference 2023 Conference Paper

A New Class of Explanations for Classifiers with Non-binary Features

• Chunxi Ji
• Adnan Darwiche

Abstract Two types of explanations have been receiving increased attention in the literature when analyzing the decisions made by classifiers. The first type explains why a decision was made and is known as a sufficient reason for the decision, also an abductive explanation or a PI-explanation. The second type explains why some other decision was not made and is known as a necessary reason for the decision, also a contrastive or counterfactual explanation. These explanations were defined for classifiers with binary, discrete and, in some cases, continuous features. We show that these explanations can be significantly improved in the presence of non-binary features, leading to a new class of explanations that relay more information about decisions and the underlying classifiers. Necessary and sufficient reasons were also shown to be the prime implicates and implicants of the complete reason for a decision, which can be obtained using a quantification operator. We show that our improved notions of necessary and sufficient reasons are also prime implicates and implicants but for an improved notion of complete reason obtained by a new quantification operator that we also define and study.

IJCAI Conference 2023 Conference Paper

On the Complexity of Counterfactual Reasoning

• Yunqiu Han
• Yizuo Chen
• Adnan Darwiche

We study the computational complexity of counterfactual reasoning in relation to the complexity of associational and interventional reasoning on structural causal models (SCMs). We show that counterfactual reasoning is no harder than associational or interventional reasoning on fully specified SCMs in the context of two computational frameworks. The first framework is based on the notion of treewidth and includes the classical variable elimination and jointree algorithms. The second framework is based on the more recent and refined notion of causal treewidth which is directed towards models with functional dependencies such as SCMs. Our results are constructive and based on bounding the (causal) treewidth of twin networks---used in standard counterfactual reasoning that contemplates two worlds, real and imaginary---to the (causal) treewidth of the underlying SCM structure. In particular, we show that the latter (causal) treewidth is no more than twice the former plus one. Hence, if associational or interventional reasoning is tractable on a fully specified SCM then counterfactual reasoning is tractable too. We extend our results to general counterfactual reasoning that requires contemplating more than two worlds and discuss applications of our results to counterfactual reasoning with partially specified SCMs that are coupled with data. We finally present empirical results that measure the gap between the complexities of counterfactual reasoning and associational/interventional reasoning on random SCMs.

IJCAI Conference 2022 Conference Paper

On Quantifying Literals in Boolean Logic and its Applications to Explainable AI (Extended Abstract)

• Adnan Darwiche
• Pierre Marquis

Quantified Boolean logic results from adding operators to Boolean logic for existentially and universally quantifying variables. This extends the reach of Boolean logic by enabling a variety of applications that have been explored over the decades. The existential quantification of literals (variable states) and its applications have also been studied in the literature. We complement this by studying universal literal quantification and its applications, particularly to explainable AI. We also provide a novel semantics for quantification and discuss the interplay between variable/literal and existential/universal quantification. We further identify classes of Boolean formulas and circuits that allow efficient quantification. Literal quantification is more fine-grained than variable quantification, which leads to a refinement of quantified Boolean logic with literal quantification as its primitive.

AAAI Conference 2022 Conference Paper

On the Computation of Necessary and Sufficient Explanations

• Adnan Darwiche
• Chunxi Ji

The complete reason behind a decision is a Boolean formula that characterizes why the decision was made. This recently introduced notion has a number of applications, which include generating explanations, detecting decision bias and evaluating counterfactual queries. Prime implicants of the complete reason are known as sufficient reasons for the decision and they correspond to what is known as PI explanations and abductive explanations. In this paper, we refer to the prime implicates of a complete reason as necessary reasons for the decision. We justify this terminology semantically and show that necessary reasons correspond to what is known as contrastive explanations. We also study the computation of complete reasons for multi-class decision trees and graphs with nominal and numeric features for which we derive efficient, closed-form complete reasons. We further investigate the computation of shortest necessary and sufficient reasons for a broad class of complete reasons, which include the derived closed forms and the complete reasons for Sentential Decision Diagrams (SDDs). We provide an algorithm which can enumerate their shortest necessary reasons in output polynomial time. Enumerating shortest sufficient reasons for this class of complete reasons is hard even for a single reason. For this problem, we provide an algorithm that appears to be quite efficient as we show empirically.

UAI Conference 2022 Conference Paper

On the definition and computation of causal treewidth

• Yizuo Chen
• Adnan Darwiche

Causal treewidth is a recently introduced notion allowing one to speed up Bayesian network inference and to bound its complexity in the presence of functional dependencies (causal mechanisms) whose identities are unknown. Causal treewidth is no greater than treewidth and can be bounded even when treewidth is unbounded. The utility of causal treewidth has been illustrated recently in the context of causal inference and model-based supervised learning. However, the current definition of causal treewidth is descriptive rather than perspective, therefore limiting its full exploitation in a practical setting. We provide an extensive study of causal treewidth in this paper which moves us closer to realizing the full computational potential of this notion both theoretically and practically.

JAIR Journal 2021 Journal Article

On Quantifying Literals in Boolean Logic and its Applications to Explainable AI

• Adnan Darwiche
• Pierre Marquis

Quantified Boolean logic results from adding operators to Boolean logic for existentially and universally quantifying variables. This extends the reach of Boolean logic by enabling a variety of applications that have been explored over the decades. The existential quantification of literals (variable states) and its applications have also been studied in the literature. In this paper, we complement this by introducing and studying universal literal quantification and its applications, particularly to explainable AI. We also provide a novel semantics for quantification, discuss the interplay between variable/literal and existential/universal quantification, and identify some classes of Boolean formulas and circuits on which quantification can be done efficiently. Literal quantification is more fine-grained than variable quantification as the latter can be defined in terms of the former, leading to a refinement of quantified Boolean logic with literal quantification as its primitive.

ICML Conference 2021 Conference Paper

On Recovering from Modeling Errors Using Testing Bayesian Networks

• Haiying Huang 0002
• Adnan Darwiche

We consider the problem of supervised learning with Bayesian Networks when the used dependency structure is incomplete due to missing edges or missing variable states. These modeling errors induce independence constraints on the learned model that may not hold in the true, data-generating distribution. We provide a unified treatment of these modeling errors as instances of state-space abstractions. We then identify a class of Bayesian Networks and queries which allow one to fully recover from such modeling errors if one can choose Conditional Probability Tables (CPTs) dynamically based on evidence. We show theoretically that the recently proposed Testing Bayesian Networks (TBNs), which can be trained by compiling them into Testing Arithmetic Circuits (TACs), provide a promising construct for emulating this CPT selection mechanism. Finally, we present empirical results that illustrate the promise of TBNs as a tool for recovering from certain modeling errors in the context of supervised learning.

AIJ Journal 2021 Journal Article

Open-world probabilistic databases: Semantics, algorithms, complexity

• İsmail İlkan Ceylan
• Adnan Darwiche
• Guy Van den Broeck

Large-scale probabilistic knowledge bases are becoming increasingly important in academia and industry. They are continuously extended with new data, powered by modern information extraction tools that associate probabilities with knowledge base facts. The state of the art to store and process such data is founded on probabilistic databases. Many systems based on probabilistic databases, however, still have certain semantic deficiencies, which limit their potential applications. We revisit the semantics of probabilistic databases, and argue that the closed-world assumption of probabilistic databases, i. e. , the assumption that facts not appearing in the database have the probability zero, conflicts with the everyday use of large-scale probabilistic knowledge bases. To address this discrepancy, we propose open-world probabilistic databases, as a new probabilistic data model. In this new data model, the probabilities of unknown facts, also called open facts, can be assigned any probability value from a default probability interval. Our analysis entails that our model aligns better with many real-world tasks such as query answering, relational learning, knowledge base completion, and rule mining. We make various technical contributions. We show that the data complexity dichotomy, between polynomial time and Image 1, for evaluating unions of conjunctive queries on probabilistic databases can be lifted to our open-world model. This result is supported by an algorithm that computes the probabilities of the so-called safe queries efficiently. Based on this algorithm, we prove that evaluating safe queries is in linear time for probabilistic databases, under reasonable assumptions. This remains true in open-world probabilistic databases for a more restricted class of safe queries. We extend our data complexity analysis beyond unions of conjunctive queries, and obtain a host of complexity results for both classical and open-world probabilistic databases. We conclude our analysis with an in-depth investigation of the combined complexity in the respective models.

ECAI Conference 2020 Conference Paper

An Advance on Variable Elimination with Applications to Tensor-Based Computation

• Adnan Darwiche

We present new results on the classical algorithm of variable elimination, which underlies many algorithms including for probabilistic inference. The results relate to exploiting functional dependencies, allowing one to perform inference efficiently on models that have very large treewidth. The highlight of the advance is that it works with standard (dense) factors, without the need for sparse factors or techniques based on knowledge compilation that are commonly utilized. This is significant as it permits a direct implementation of the improved variable elimination algorithm using tensors and their operations, leading to extremely efficient implementations especially when learning model parameters. We illustrate the efficacy of our proposed algorithm by compiling Bayesian network queries into tensor graphs and then learning their parameters from labeled data using a standard tool for tensor computation.

ECAI Conference 2020 Conference Paper

On the Reasons Behind Decisions

• Adnan Darwiche
• Auguste Hirth

Recent work has shown that some common machine learning classifiers can be compiled into Boolean circuits that have the same input-output behavior. We present a theory for unveiling the reasons behind the decisions made by Boolean classifiers and study some of its theoretical and practical implications. We define notions such as sufficient, necessary and complete reasons behind decisions, in addition to classifier and decision bias. We show how these notions can be used to evaluate counterfactual statements such as “a decision will stick even if … because …. ” We present efficient algorithms for computing these notions, which are based on new advances on tractable Boolean circuits, and illustrate them using a case study.

KR Conference 2020 Conference Paper

On Tractable Representations of Binary Neural Networks

• Weijia Shi
• Andy Shih
• Adnan Darwiche
• Arthur Choi

We consider the compilation of a binary neural network’s decision function into tractable representations such as Ordered Binary Decision Diagrams (OBDDs) and Sentential Decision Diagrams (SDDs). Obtaining this function as an OBDD/SDD facilitates the explanation and formal verification of a neural network’s behavior. First, we consider the task of verifying the robustness of a neural network, and show how we can compute the expected robustness of a neural network, given an OBDD/SDD representation of it. Next, we consider a more efficient approach for compiling neural networks, based on a pseudo-polynomial time algorithm for compiling a neuron. We then provide a case study in a handwritten digits dataset, highlighting how two neural networks trained from the same dataset can have very high accuracies, yet have very different levels of robustness. Finally, in experiments, we show that it is feasible to obtain compact representations of neural networks as SDDs.

AAAI Conference 2019 Conference Paper

Compiling Bayesian Network Classifiers into Decision Graphs

• Andy Shih
• Arthur Choi
• Adnan Darwiche

We propose an algorithm for compiling Bayesian network classifiers into decision graphs that mimic the input and output behavior of the classifiers. In particular, we compile Bayesian network classifiers into ordered decision graphs, which are tractable and can be exponentially smaller in size than decision trees. This tractability facilitates reasoning about the behavior of Bayesian network classifiers, including the explanation of decisions they make. Our compilation algorithm comes with guarantees on the time of compilation and the size of compiled decision graphs. We apply our compilation algorithm to classifiers from the literature and discuss some case studies in which we show how to automatically explain their decisions and verify properties of their behavior.

ICML Conference 2019 Conference Paper

Conditional Independence in Testing Bayesian Networks

• Yujia Shen
• Haiying Huang 0002
• Arthur Choi
• Adnan Darwiche

Testing Bayesian Networks (TBNs) were introduced recently to represent a set of distributions, one of which is selected based on the given evidence and used for reasoning. TBNs are more expressive than classical Bayesian Networks (BNs): Marginal queries correspond to multi-linear functions in BNs and to piecewise multi-linear functions in TBNs. Moreover, TBN queries are universal approximators, like neural networks. In this paper, we study conditional independence in TBNs, showing that it can be inferred from d-separation as in BNs. We also study the role of TBN expressiveness and independence in dealing with the problem of learning with incomplete models (i. e. , ones that miss nodes or edges from the data-generating model). Finally, we illustrate our results on a number of concrete examples, including a case study on Hidden Markov Models.

AAAI Conference 2019 Conference Paper

Structured Bayesian Networks: From Inference to Learning with Routes

• Yujia Shen
• Anchal Goyanka
• Adnan Darwiche
• Arthur Choi

Structured Bayesian networks (SBNs) are a recently proposed class of probabilistic graphical models which integrate background knowledge in two forms: conditional independence constraints and Boolean domain constraints. In this paper, we propose the first exact inference algorithm for SBNs, based on compiling a given SBN to a Probabilistic Sentential Decision Diagram (PSDD). We further identify a tractable subclass of SBNs, which have PSDDs of polynomial size. These SBNs yield a tractable model of route distributions, whose structure can be learned from GPS data, using a simple algorithm that we propose. Empirically, we demonstrate the utility of our inference algorithm, showing that it can be an order-ofmagnitude more efficient than more traditional approaches to exact inference. We demonstrate the utility of our learning algorithm, showing that it can learn more accurate models and classifiers from GPS data.

SAT Conference 2019 Conference Paper

Verifying Binarized Neural Networks by Angluin-Style Learning

• Andy Shih
• Adnan Darwiche
• Arthur Choi

Abstract We consider the problem of verifying the behavior of binarized neural networks on some input region. We propose an Angluin-style learning algorithm to compile a neural network on a given region into an Ordered Binary Decision Diagram (OBDD), using a SAT solver as an equivalence oracle. The OBDD allows us to efficiently answer a range of verification queries, including counting, computing the probability of counterexamples, and identifying common characteristics of counterexamples. We also present experimental results on verifying binarized neural networks that recognize images of handwritten digits.

IJCAI Conference 2018 Conference Paper

A Symbolic Approach to Explaining Bayesian Network Classifiers

• Andy Shih
• Arthur Choi
• Adnan Darwiche

We propose an approach for explaining Bayesian network classifiers, which is based on compiling such classifiers into decision functions that have a tractable and symbolic form. We introduce two types of explanations for why a classifier may have classified an instance positively or negatively and suggest algorithms for computing these explanations. The first type of explanation identifies a minimal set of the currently active features that is responsible for the current classification, while the second type of explanation identifies a minimal set of features whose current state (active or not) is sufficient for the classification. We consider in particular the compilation of Naive and Latent-Tree Bayesian network classifiers into Ordered Decision Diagrams (ODDs), providing a context for evaluating our proposal using case studies and experiments based on classifiers from the literature.

JAIR Journal 2018 Journal Article

An Exhaustive DPLL Algorithm for Model Counting

• Umut Oztok
• Adnan Darwiche

State-of-the-art model counters are based on exhaustive DPLL algorithms, and have been successfully used in probabilistic reasoning, one of the key problems in AI. In this article, we present a new exhaustive DPLL algorithm with a formal semantics, a proof of correctness, and a modular design. The modular design is based on the separation of the core model counting algorithm from SAT solving techniques. We also show that the trace of our algorithm belongs to the language of Sentential Decision Diagrams (SDDs), which is a subset of Decision-DNNFs, the trace of existing state-of-the-art model counters. Still, our experimental analysis shows comparable results against state-of-the-art model counters. Furthermore, we obtain the first top-down SDD compiler, and show orders-of-magnitude improvements in SDD construction time against the existing bottom-up SDD compiler.

AAAI Conference 2018 Conference Paper

Conditional PSDDs: Modeling and Learning With Modular Knowledge

• Yujia Shen
• Arthur Choi
• Adnan Darwiche

Probabilistic Sentential Decision Diagrams (PSDDs) have been proposed for learning tractable probability distributions from a combination of data and background knowledge (in the form of Boolean constraints). In this paper, we propose a variant on PSDDs, called conditional PSDDs, for representing a family of distributions that are conditioned on the same set of variables. Conditional PSDDs can also be learned from a combination of data and (modular) background knowledge. We use conditional PSDDs to define a more structured version of Bayesian networks, in which nodes can have an exponential number of states, hence expanding the scope of domains where Bayesian networks can be applied. Compared to classical PSDDs, the new representation exploits the independencies captured by a Bayesian network to decompose the learning process into localized learning tasks, which enables the learning of better models while using less computation. We illustrate the promise of conditional PSDDs and structured Bayesian networks empirically, and by providing a case study to the modeling of distributions over routes on a map.

UAI Conference 2017 Conference Paper

A Tractable Probabilistic Model for Subset Selection

• Yujia Shen
• Arthur Choi
• Adnan Darwiche

Subset selection tasks, such as top-k ranking, induce datasets where examples have cardinalities that are known a priori. In this paper, we propose a tractable probabilistic model for subset selection and show how it can be learned from data. Our proposed model is interpretable and subsumes a previously introduced model based on logistic regression. We show how the parameters of our model can be estimated in closed form given complete data, and propose an algorithm for learning its structure in an interpretable space. We highlight the intuitive structures that we learn via case studies. We finally show how our proposed model can be viewed as an instance of the recently proposed Probabilistic Sentential Decision Diagram.

AIJ Journal 2017 Journal Article

Learning Bayesian network parameters under equivalence constraints

• Tiansheng Yao
• Arthur Choi
• Adnan Darwiche

We propose a principled approach for learning parameters in Bayesian networks from incomplete datasets, where the examples of a dataset are subject to equivalence constraints. These equivalence constraints arise from datasets where examples are tied together, in that we may not know the value of a particular variable, but whatever that value is, we know it must be the same across different examples. We formalize the problem by defining the notion of a constrained dataset and a corresponding constrained likelihood that we seek to optimize. We further propose a new learning algorithm that can effectively learn more accurate Bayesian networks using equivalence constraints, which we demonstrate empirically. Moreover, we highlight how our general approach can be brought to bear on more specialized learning tasks, such as those in semi-supervised clustering and topic modeling, where more domain-specific approaches were previously developed.

ICML Conference 2017 Conference Paper

On Relaxing Determinism in Arithmetic Circuits

• Arthur Choi
• Adnan Darwiche

The past decade has seen a significant interest in learning tractable probabilistic representations. Arithmetic circuits (ACs) were among the first proposed tractable representations, with some subsequent representations being instances of ACs with weaker or stronger properties. In this paper, we provide a formal basis under which variants on ACs can be compared, and where the precise roles and semantics of their various properties can be made more transparent. This allows us to place some recent developments on ACs in a clearer perspective and to also derive new results for ACs. This includes an exponential separation between ACs with and without determinism; completeness and incompleteness results; and tractability results (or lack thereof) when computing most probable explanations (MPEs).

IJCAI Conference 2017 Conference Paper

Open-World Probabilistic Databases: An Abridged Report

• Ismail Ilkan Ceylan
• Adnan Darwiche
• Guy Van den Broeck

Large-scale probabilistic knowledge bases are becoming increasingly important in academia and industry alike. They are constantly extended with new data, powered by modern information extraction tools that associate probabilities with database tuples. In this paper, we revisit the semantics underlying such systems. In particular, the closed-world assumption of probabilistic databases, that facts not in the database have probability zero, clearly conflicts with their everyday use. To address this discrepancy, we propose an open-world probabilistic database semantics, which relaxes the probabilities of open facts to default intervals. For this open-world setting, we lift the existing data complexity dichotomy of probabilistic databases, and propose an efficient evaluation algorithm for unions of conjunctive queries. We also show that query evaluation can become harder for non-monotone queries.

IJCAI Conference 2017 Conference Paper

Optimal Feature Selection for Decision Robustness in Bayesian Networks

• YooJung Choi
• Adnan Darwiche
• Guy Van den Broeck

In many applications, one can define a large set of features to support the classification task at hand. At test time, however, these become prohibitively expensive to evaluate, and only a small subset of features is used, often selected for their information-theoretic value. For threshold-based, Naive Bayes classifiers, recent work has suggested selecting features that maximize the expected robustness of the classifier, that is, the expected probability it maintains its decision after seeing more features. We propose the first algorithm to compute this expected same-decision probability for general Bayesian network classifiers, based on compiling the network into a tractable circuit representation. Moreover, we develop a search algorithm for optimal feature selection that utilizes efficient incremental circuit modifications. Experiments on Naive Bayes, as well as more general networks, show the efficacy and distinct behavior of this decision-making approach.

NeurIPS Conference 2017 Conference Paper

Tractability in Structured Probability Spaces

• Arthur Choi
• Yujia Shen
• Adnan Darwiche

Recently, the Probabilistic Sentential Decision Diagram (PSDD) has been proposed as a framework for systematically inducing and learning distributions over structured objects, including combinatorial objects such as permutations and rankings, paths and matchings on a graph, etc. In this paper, we study the scalability of such models in the context of representing and learning distributions over routes on a map. In particular, we introduce the notion of a hierarchical route distribution and show how they can be leveraged to construct tractable PSDDs over route distributions, allowing them to scale to larger maps. We illustrate the utility of our model empirically, in a route prediction task, showing how accuracy can be increased significantly compared to Markov models.

NeurIPS Conference 2016 Conference Paper

Learning Bayesian networks with ancestral constraints

• Eunice Yuh-Jie Chen
• Yujia Shen
• Arthur Choi
• Adnan Darwiche

We consider the problem of learning Bayesian networks optimally, when subject to background knowledge in the form of ancestral constraints. Our approach is based on a recently proposed framework for optimal structure learning based on non-decomposable scores, which is general enough to accommodate ancestral constraints. The proposed framework exploits oracles for learning structures using decomposable scores, which cannot accommodate ancestral constraints since they are non-decomposable. We show how to empower these oracles by passing them decomposable constraints that they can handle, which are inferred from ancestral constraints that they cannot handle. Empirically, we demonstrate that our approach can be orders-of-magnitude more efficient than alternative frameworks, such as those based on integer linear programming.

KR Conference 2016 Conference Paper

Open-World Probabilistic Databases

• Ismail Ilkan Ceylan
• Adnan Darwiche
• Guy Van den Broeck

Large-scale probabilistic knowledge bases are becoming increasingly important in academia and industry alike. They are constantly extended with new data, powered by modern information extraction tools that associate probabilities with database tuples. In this paper, we revisit the semantics underlying such systems. In particular, the closed-world assumption of probabilistic databases, that facts not in the database have probability zero, clearly conflicts with their everyday use. To address this discrepancy, we propose an open-world probabilistic database semantics, which relaxes the probabilities of open facts to intervals. While still assuming a finite domain, this semantics can provide meaningful answers when some probabilities are not precisely known. For this openworld setting, we propose an efficient evaluation algorithm for unions of conjunctive queries. Our open-world algorithm incurs no overhead compared to closed-world reasoning and runs in time linear in the size of the database for tractable queries. All other queries are #P-hard, implying a data complexity dichotomy between linear time and #P. For queries involving negation, however, open-world reasoning can become NP-, or even NPPP -hard. Finally, we discuss additional knowledge-representation layers that can further strengthen open-world reasoning about big uncertain data.

KR Conference 2016 Conference Paper

Solving PP^PP-complete Problems using Knowledge Compilation

• Umut Oztok
• Arthur Choi
• Adnan Darwiche

Knowledge compilation has been successfully used to solve beyond NP problems, including some PP-complete and NPPP -complete problems for Bayesian networks. In this work we show how knowledge compilation can be used to solve problems in the more intractable complexity class PPPP. This class contains NPPP and includes interesting AI problems, such as non-myopic value of information. We show how to solve the prototypical PPPP -complete problem M AJ M AJSAT in linear-time once the problem instance is compiled into a special class of Sentential Decision Diagrams. To show the practical value of our approach, we adapt it to answer the Same-Decision Probability (SDP) query, which was recently introduced for Bayesian networks. The SDP problem is also PPPP -complete. It is a value-of-information query that quantifies the robustness of threshold-based decisions and comes with a corresponding algorithm that was also recently proposed. We present favorable experimental results, comparing our new algorithm based on knowledge compilation with the state-of-the-art algorithm for computing the SDP.

AAAI Conference 2016 Conference Paper

Structured Features in Naive Bayes Classification

• Arthur Choi
• Nazgol Tavabi
• Adnan Darwiche

We propose the structured naive Bayes (SNB) classi- fier, which augments the ubiquitous naive Bayes classifier with structured features. SNB classifiers facilitate the use of complex features, such as combinatorial objects (e. g. , graphs, paths and orders) in a general but systematic way. Underlying the SNB classifier is the recently proposed Probabilistic Sentential Decision Diagram (PSDD), which is a tractable representation of probability distributions over structured spaces. We illustrate the utility and generality of the SNB classifier via case studies. First, we show how we can distinguish players of simple games in terms of play style and skill level based purely on observing the games they play. Second, we show how we can detect anomalous paths taken on graphs based purely on observing the paths themselves.

NeurIPS Conference 2016 Conference Paper

Tractable Operations for Arithmetic Circuits of Probabilistic Models

• Yujia Shen
• Arthur Choi
• Adnan Darwiche

We consider tractable representations of probability distributions and the polytime operations they support. In particular, we consider a recently proposed arithmetic circuit representation, the Probabilistic Sentential Decision Diagram (PSDD). We show that PSDD supports a polytime multiplication operator, while they do not support a polytime operator for summing-out variables. A polytime multiplication operator make PSDDs suitable for a broader class of applications compared to arithmetic circuits, which do not in general support multiplication. As one example, we show that PSDD multiplication leads to a very simple but effective compilation algorithm for probabilistic graphical models: represent each model factor as a PSDD, and then multiply them.

IJCAI Conference 2015 Conference Paper

A Top-Down Compiler for Sentential Decision Diagrams

• Umut Oztok
• Adnan Darwiche

The sentential decision diagram (SDD) has been recently proposed as a new tractable representation of Boolean functions that generalizes the influential ordered binary decision diagram (OBDD). Empirically, compiling CNFs into SDDs has yielded significant improvements in both time and space over compiling them into OBDDs, using a bottomup compilation approach. In this work, we present a top-down CNF to SDD compiler that is based on techniques from the SAT literature. We compare the presented compiler empirically to the state-ofthe-art, bottom-up SDD compiler, showing ordersof-magnitude improvements in compilation time.

UAI Conference 2015 Conference Paper

An Upper Bound on the Global Optimum in Parameter Estimation

• Khaled S. Refaat
• Adnan Darwiche

Learning graphical model parameters from incomplete data is a non-convex optimization problem. Iterative algorithms, such as Expectation Maximization (EM), can be used to get a local optimum solution. However, little is known about the quality of the learned local optimum, compared to the unknown global optimum. We exploit variables that are always observed in the dataset to get an upper bound on the global optimum which can give insight into the quality of the parameters learned by estimation algorithms.

IJCAI Conference 2015 Conference Paper

Data Compression for Learning MRF Parameters

• Khaled S. Refaat
• Adnan Darwiche

We propose a technique for decomposing and compressing the dataset in the parameter learning problem in Markov random fields. Our technique applies to incomplete datasets and exploits variables that are always observed in the given dataset. We show that our technique allows exact computation of the gradient and the likelihood, and can lead to orders-of-magnitude savings in learning time.

UAI Conference 2015 Conference Paper

Efficient Algorithms for Bayesian Network Parameter Learning from Incomplete Data

• Guy Van den Broeck
• Karthika Mohan
• Arthur Choi
• Adnan Darwiche
• Judea Pearl

We propose a family of efficient algorithms for learning the parameters of a Bayesian network from incomplete data. Our approach is based on recent theoretical analyses of missing data problems, which utilize a graphical representation, called the missingness graph. In the case of MCAR and MAR data, this graph need not be explicit, and yet we can still obtain closedform, asymptotically consistent parameter estimates, without the need for inference. When this missingness graph is explicated (based on background knowledge), even partially, we can obtain even more accurate estimates with less data. Empirically, we illustrate how we can learn the parameters of large networks from large datasets, which are beyond the scope of algorithms like EM (which require inference).

AAAI Conference 2015 Conference Paper

On the Role of Canonicity in Knowledge Compilation

• Guy Van den Broeck
• Adnan Darwiche

Knowledge compilation is a powerful reasoning paradigm with many applications across AI and computer science more broadly. We consider the problem of bottom-up compilation of knowledge bases, which is usually predicated on the existence of a polytime function for combining compilations using Boolean operators (usually called an Apply function). While such a polytime Apply function is known to exist for certain languages (e. g. , OBDDs) and not exist for others (e. g. , DNNFs), its existence for certain languages remains unknown. Among the latter is the recently introduced language of Sentential Decision Diagrams (SDDs): while a polytime Apply function exists for SDDs, it was unknown whether such a function exists for the important subset of compressed SDDs which are canonical. We resolve this open question in this paper and consider some of its theoretical and practical implications. Some of the findings we report question the common wisdom on the relationship between bottom-up compilation, language canonicity and the complexity of the Apply function.

NeurIPS Conference 2015 Conference Paper

Tractable Learning for Complex Probability Queries

• Jessa Bekker
• Jesse Davis
• Arthur Choi
• Adnan Darwiche
• Guy Van den Broeck

Tractable learning aims to learn probabilistic models where inference is guaranteed to be efficient. However, the particular class of queries that is tractable depends on the model and underlying representation. Usually this class is MPE or conditional probabilities $\Pr(\xs|\ys)$ for joint assignments~$\xs, \ys$. We propose a tractable learner that guarantees efficient inference for a broader class of queries. It simultaneously learns a Markov network and its tractable circuit representation, in order to guarantee and measure tractability. Our approach differs from earlier work by using Sentential Decision Diagrams (SDD) as the tractable language instead of Arithmetic Circuits (AC). SDDs have desirable properties, which more general representations such as ACs lack, that enable basic primitives for Boolean circuit compilation. This allows us to support a broader class of complex probability queries, including counting, threshold, and parity, in polytime.

IJCAI Conference 2015 Conference Paper

Tractable Learning for Structured Probability Spaces: A Case Study in Learning Preference Distributions

• Arthur Choi
• Guy Van den Broeck
• Adnan Darwiche

Probabilistic sentential decision diagrams (PSDDs) are a tractable representation of structured probability spaces, which are characterized by complex logical constraints on what constitutes a possible world. We develop general-purpose techniques for probabilistic reasoning and learning with PSDDs, allowing one to compute the probabilities of arbitrary logical formulas and to learn PSDDs from incomplete data. We illustrate the effectiveness of these techniques in the context of learning preference distributions, to which considerable work has been devoted in the past. We show, analytically and empirically, that our proposed framework is general enough to support diverse and complex data and query types. In particular, we show that it can learn maximum-likelihood models from partial rankings, pairwise preferences, and arbitrary preference constraints. Moreover, we show that it can efficiently answer many queries exactly, from expected and most likely rankings, to the probability of pairwise preferences, and diversified recommendations. This case study illustrates the effectiveness and flexibility of the developed PSDD framework as a domain-independent tool for learning and reasoning with structured probability spaces.

AAAI Conference 2015 Conference Paper

Value of Information Based on Decision Robustness

• Suming Chen
• Arthur Choi
• Adnan Darwiche

There are many criteria for measuring the value of information (VOI), each based on a different principle that is usually suitable for specific applications. We propose a new criterion for measuring the value of information, which values information that leads to robust decisions (i. e. , ones that are unlikely to change due to new information). We also introduce an algorithm for Naive Bayes networks that selects features with maximal VOI under the new criterion. We discuss the application of the new criterion to classification tasks, showing how it can be used to tradeoff the budget, allotted for acquiring information, with the classification accuracy. In particular, we show empirically that the new criterion can reduce the expended budget significantly while reducing the classification accuracy only slightly. We also show empirically that the new criterion leads to decisions that are much more robust than those based on traditional VOI criteria, such as information gain and classification loss. This make the new criterion particularly suitable for certain decision making applications.

ECAI Conference 2014 Conference Paper

CV-width: A New Complexity Parameter for CNFs

• Umut Oztok
• Adnan Darwiche

We present new complexity results on the compilation of CNFs into DNNFs and OBDDs. In particular, we introduce a new notion of width, called CV-width, which is specific to CNFs and that dominates the treewidth of the CNF incidence graph. We then show that CNFs can be compiled into structured DNNFs in time and space that are exponential only in CV-width. Not only does CV-width dominate the incidence graph treewidth, but the former width can be bounded when the latter is unbounded. We also introduce a restricted version of CV-width, called linear CV-width, and show that it dominates both pathwidth and cutwidth, which have been used to bound the complexity of OBDDs. We show that CNFs can be compiled into OBDDs in time and space that are exponential only in linear CV-width. We also show that linear CV-width can be bounded when pathwidth and cutwidth are unbounded. The new notion of width significantly improves existing upper bounds on both structured DNNFs and OBDDs, and is motived by a new decomposition technique that combines variable splitting with clause splitting.

NeurIPS Conference 2014 Conference Paper

Decomposing Parameter Estimation Problems

• Khaled Refaat
• Arthur Choi
• Adnan Darwiche

We propose a technique for decomposing the parameter learning problem in Bayesian networks into independent learning problems. Our technique applies to incomplete datasets and exploits variables that are either hidden or observed in the given dataset. We show empirically that the proposed technique can lead to orders-of-magnitude savings in learning time. We explain, analytically and empirically, the reasons behind our reported savings, and compare the proposed technique to related ones that are sometimes used by inference algorithms.

KR Conference 2014 Conference Paper

Probabilistic Sentential Decision Diagrams

• Doga Kisa
• Guy Van den Broeck
• Arthur Choi
• Adnan Darwiche

to perform weighted model counting efficiently. Second, that probabilistic reasoning can be reduced to weighted model counting. This development, which has its first roots in Darwiche (2002), has been underlying an increasing number of probabilistic reasoning systems in the last decade. This is especially true for representations that employ both logical and probabilistic elements (e. g., Chavira, Darwiche, and Jaeger (2006) and Fierens et al. (2011)). Moreover, the technique has been extended recently to certain first-order representations as well (Van den Broeck et al. 2011). This paper is concerned with an orthogonal contribution to this interplay between propositional logic and probability theory. The problem we tackle here is that of developing a representation of probability distributions in the presence of massive, logical constraints. That is, given a propositional logic theory which represents domain constraints, our goal is to develop a representation that induces a unique probability distribution over the models of the given theory. Moreover, the proposed representation should satisfy requirements that are sometimes viewed as necessary for the practical employment of such representations. These include a clear semantics of the representation parameters; an ability to reason with the representation efficiently; and an ability to learn its parameters from data, also efficiently. Our proposal is called a Probabilistic Sentential Decision Diagram (PSDD). It is based on the recently proposed Sentential Decision Diagram (SDD) for representing propositional theories (Darwiche 2011; Xue, Choi, and Darwiche 2012; Choi and Darwiche 2013). While the SDD is comprised of logical decision nodes, the PSDD is comprised of probabilistic decision nodes, which are induced by supplying a distribution over the branches of a logical decision node. Similar to SDDs, the PSDD is a canonical representation, but under somewhat more interesting conditions. Moreover, computing the probability of a term can be done in time linear in the PSDD size. In fact, the probability of each and every literal can be computed in only two passes over the PSDD. It is particularly notable that the local parameters of a PSDD have clear semantics with respect to the global distribution induced by the PSDD. We will also show that these parameters can be learned efficiently from complete data. This paper is structured as follows. We start by a concrete discussion on some of the applications that have driven the development of PSDDs and follow by an intuitive expo- We propose the Probabilistic Sentential Decision Diagram (PSDD): A complete and canonical representation of probability distributions defined over the models of a given propositional theory. Each parameter of a PSDD can be viewed as the (conditional) probability of making a decision in a corresponding Sentential Decision Diagram (SDD). The SDD itself is a recently proposed complete and canonical representation of propositional theories. We explore a number of interesting properties of PSDDs, including the independencies that underlie them. We show that the PSDD is a tractable representation. We further show how the parameters of a PSDD can be efficiently estimated, in closed form, from complete data. We empirically evaluate the quality of PSDDs learned from data, when we have knowledge, a priori, of the domain logical constraints.

KR Conference 2014 Conference Paper

Skolemization for Weighted First-Order Model Counting

• Guy Van den Broeck
• Wannes Meert
• Adnan Darwiche

probabilistic inference to a WMC problem on a propositional knowledge base (Chavira, Darwiche, and Jaeger 2006; Fierens et al. 2011; 2013). Encoding first-order probabilistic models into propositional logic retains a key advantage of the Bayesian network algorithms: WMC naturally exploits determinism and local structure in the probabilistic model (Boutilier et al. 1996; Chavira and Darwiche 2005). A disadvantage is that the high-level first-order structure is lost. Poole (2003) observed that knowing the symmetries that are abundant in first-order structure can speed up probabilistic inference. Lifted inference algorithms reason about groups of objects as a whole, similar to the high-level reasoning of first-order resolution. This has lead Van den Broeck et al. (2011) and Gogate and Domingos (2011) to propose weighted first-order model counting (WFOMC) as the core reasoning task underlying lifted inference algorithms. WFOMC assigns a weight to interpretations in finitedomain, function-free first-order logic, and computes the sum of the weights of all models. Counting models at the first-order level has computational advantages. For certain classes of theories, knowing the firstorder structure gives exponential speedups (Van den Broeck 2011). For example, counting the models of a first-order universally quantified CNF with up to two logical variables per clause can always be done in time polynomial in the size of the domain of discourse. In contrast, a propositionalization of these CNFs will often have a treewidth polynomial in the domains size, and propositional model counting runs in exponential time. One major limitation of first-order model counters, however, is that they require input in Skolem normal form (i. e., without existential quantifiers). This is a common requirement for first-order automated reasoning algorithms, such as theorem provers. It is usually dealt with by Skolemization, which introduces Skolem constants and functions. However, the introduction of functions is problematic for first-order model counters as they expect a function-free input. The main contribution of this paper is a Skolemization procedure that is specific for weighted first-order model counting. The procedure maps a logical input theory to an output theory that is devoid of existential quantifiers and functions, yet has an identical weighted first-order model count. The procedure is modular, in that it remains sound when extending the input and output theories with a new First-order model counting emerged recently as a novel reasoning task, at the core of efficient algorithms for probabilistic logics. We present a Skolemization algorithm for model counting problems that eliminates existential quantifiers from a first-order logic theory without changing its weighted model count. For certain subsets of first-order logic, lifted model counters were shown to run in time polynomial in the number of objects in the domain of discourse, where propositional model counters require exponential time. However, these guarantees apply only to Skolem normal form theories (i. e., no existential quantifiers) as the presence of existential quantifiers reduces lifted model counters to propositional ones. Since textbook Skolemization is not sound for model counting, these restrictions precluded efficient model counting for directed models, such as probabilistic logic programs, which rely on existential quantification. Our Skolemization procedure extends the applicability of first-order model counters to these representations. Moreover, it simplifies the design of lifted model counting algorithms.

IJCAI Conference 2013 Conference Paper

An Exact Algorithm for Computing the Same-Decision Probability

• Suming Chen
• Arthur Choi
• Adnan Darwiche

When using graphical models for decision making, the presence of unobserved variables may hinder our ability to reach the correct decision. A fundamental question here is whether or not one is ready to make a decision (stopping criteria), and if not, what additional observations should be made in order to better prepare for a decision (selection criteria). A recently introduced notion, the Same- Decision Probability (SDP), has been shown to be useful as both a stopping and a selection criteria. This query has been shown to be highly intractable, being PPPP –complete, and is exemplary of a class of queries which correspond to the computation of certain expectations. We propose the first exact algorithm for computing the SDP in this paper, and demonstrate its effectiveness on several real and synthetic networks. We also present a new complexity result for computing the SDP on models with a Naive Bayes structure.

AAAI Conference 2013 Conference Paper

Dynamic Minimization of Sentential Decision Diagrams

• Arthur Choi
• Adnan Darwiche

The Sentential Decision Diagram (SDD) is a recently proposed representation of Boolean functions, containing Ordered Binary Decision Diagrams (OBDDs) as a distinguished subclass. While OBDDs are characterized by total variable orders, SDDs are characterized more generally by vtrees. As both OBDDs and SDDs have canonical representations, searching for OBDDs and SDDs of minimal size simplifies to searching for variable orders and vtrees, respectively. For OBDDs, there are effective heuristics for dynamic reordering, based on locally swapping variables. In this paper, we propose an analogous approach for SDDs which navigates the space of vtrees via two operations: one based on tree rotations and a second based on swapping children in a vtree. We propose a particular heuristic for dynamically searching the space of vtrees, showing that it can find SDDs that are an order-of-magnitude more succinct than OBDDs found by dynamic reordering.

NeurIPS Conference 2013 Conference Paper

EDML for Learning Parameters in Directed and Undirected Graphical Models

• Khaled Refaat
• Arthur Choi
• Adnan Darwiche

EDML is a recently proposed algorithm for learning parameters in Bayesian networks. It was originally derived in terms of approximate inference on a meta-network, which underlies the Bayesian approach to parameter estimation. While this initial derivation helped discover EDML in the first place and provided a concrete context for identifying some of its properties (e. g. , in contrast to EM), the formal setting was somewhat tedious in the number of concepts it drew on. In this paper, we propose a greatly simplified perspective on EDML, which casts it as a general approach to continuous optimization. The new perspective has several advantages. First, it makes immediate some results that were non-trivial to prove initially. Second, it facilitates the design of EDML algorithms for new graphical models, leading to a new algorithm for learning parameters in Markov networks. We derive this algorithm in this paper, and show, empirically, that it can sometimes learn better estimates from complete data, several times faster than commonly used optimization methods, such as conjugate gradient and L-BFGS.

NeurIPS Conference 2013 Conference Paper

On the Complexity and Approximation of Binary Evidence in Lifted Inference

• Guy Van den Broeck
• Adnan Darwiche

Lifted inference algorithms exploit symmetries in probabilistic models to speed up inference. They show impressive performance when calculating unconditional probabilities in relational models, but often resort to non-lifted inference when computing conditional probabilities. The reason is that conditioning on evidence breaks many of the model's symmetries, which preempts standard lifting techniques. Recent theoretical results show, for example, that conditioning on evidence which corresponds to binary relations is #P-hard, suggesting that no lifting is to be expected in the worst case. In this paper, we balance this grim result by identifying the Boolean rank of the evidence as a key parameter for characterizing the complexity of conditioning in lifted inference. In particular, we show that conditioning on binary evidence with bounded Boolean rank is efficient. This opens up the possibility of approximating evidence by a low-rank Boolean matrix factorization, which we investigate both theoretically and empirically.

AAAI Conference 2012 Conference Paper

Basing Decisions on Sentences in Decision Diagrams

• Yexiang Xue
• Arthur Choi
• Adnan Darwiche

The Sentential Decision Diagram (SDD) is a recently proposed representation of Boolean functions, containing Ordered Binary Decision Diagrams (OBDDs) as a distinguished subclass. While OBDDs are characterized by total variable orders, SDDs are characterized by dissections of variable orders, known as vtrees. Despite this generality, SDDs retain a number of properties, such as canonicity and a polytime Apply operator, that have been critical to the practical success of OBDDs. Moreover, upper bounds on the size of SDDs were also given, which are tighter than comparable upper bounds on the size of OBDDs. In this paper, we analyze more closely some of the theoretical properties of SDDs and their size. In particular, we consider the impact of basing decisions on sentences (using dissections as in SDDs), in comparison to basing decisions on variables (using total variable orders as in OBDDs). Here, we identify a class of Boolean functions where basing decisions on sentences using dissections of a variable order can lead to exponentially more compact SDDs, compared to OBDDs based on the same variable order. Moreover, we identify a fundamental property of the decompositions that underlie SDDs and use it to show how certain changes to a vtree can also lead to exponential differences in the size of an SDD.

ECAI Conference 2012 Invited Paper

Generalized Decision Diagrams: The game is not over yet!

• Adnan Darwiche

Decision diagrams have played an influential role in computer science and AI over the past few decades, with OBDDs (Ordered Binary Decision Diagrams) as perhaps the most practical and influential example. The practical influence of OBDDs is typically attributed to their canonicity, their efficient support of Boolean combination operations, and the availability of effective heuristics for finding good variable orders (which characterize OBDDs and their size). Over the past few decades, significant efforts have been exerted to generalize OBDDs, with the goal of defining more succinct representations while retaining the attractive properties of OBDDs. On the theoretical side, these efforts have yielded a rich set of decision diagram generalizations. Practially, however, OBDDs remain as the single most used decision diagram in applications. In this talk, I will discuss a recent line of research for generalizing OBDDs based on a new type of Boolean-function decompositions (which generalize the Shannon decomposition underlying OBDDs). I will discuss in particular the class of Sentential Decision Diagrams (SDDs), which branch on arbitrary sentences instead of variables, and which are characterized by trees instead of total variable orders. SDDs retain the main attractive properties of OBDDs and include OBDDs as a special case. I will discuss recent theoretical and empirical results, and a soon-to-be-released open source package for supporting SDDs, which suggest a potential breakthrough in the quest for producing more practical generalizations of OBDDs.

UAI Conference 2012 Conference Paper

Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference

• Guy Van den Broeck
• Arthur Choi
• Adnan Darwiche

We propose an approach to lifted approximate inference for first-order probabilistic models, such as Markov logic networks. It is based on performing exact lifted inference in a simplified first-order model, which is found by relaxing first-order constraints, and then compensating for the relaxation. These simplified models can be incrementally improved by carefully recovering constraints that have been relaxed, also at the first-order level. This leads to a spectrum of approximations, with lifted belief propagation on one end, and exact lifted inference on the other. We discuss how relaxation, compensation, and recovery can be performed, all at the firstorder level, and show empirically that our approach substantially improves on the approximations of both propositional solvers and lifted belief propagation.

UAI Conference 2012 Conference Paper

New Advances and Theoretical Insights into EDML

• Khaled S. Refaat
• Arthur Choi
• Adnan Darwiche

EDML is a recently proposed algorithm for learning MAP parameters in Bayesian networks. In this paper, we present a number of new advances and insights on the EDML algorithm. First, we provide the multivalued extension of EDML, originally proposed for Bayesian networks over binary variables. Next, we identify a simplified characterization of EDML that further implies a simple fixed-point algorithm for the convex optimization problem that underlies it. This characterization further reveals a connection between EDML and EM: a fixed point of EDML is a fixed point of EM, and vice versa. We thus identify also a new characterization of EM fixed points, but in the semantics of EDML. Finally, we propose a hybrid EDML/EM algorithm that takes advantage of the improved empirical convergence behavior of EDML, while maintaining the monotonic improvement property of EM.

UAI Conference 2011 Conference Paper

EDML: A Method for Learning Parameters in Bayesian Networks

• Arthur Choi
• Khaled S. Refaat
• Adnan Darwiche

We propose a method called EDML for learning MAP parameters in binary Bayesian networks under incomplete data. The method assumes Beta priors and can be used to learn maximum likelihood parameters when the priors are uninformative. EDML exhibits interesting behaviors, especially when compared to EM. We introduce EDML, explain its origin, and study some of its properties both analytically and empirically.

AIJ Journal 2011 Journal Article

On the power of clause-learning SAT solvers as resolution engines

• Knot Pipatsrisawat
• Adnan Darwiche

In this work, we improve on existing results on the relationship between proof systems obtained from conflict-driven clause-learning SAT solvers and general resolution. Previous contributions such as those by Beame et al. (2004), Hertel et al. (2008), and Buss et al. (2008) demonstrated that variations on conflict-driven clause-learning SAT solvers corresponded to proof systems as powerful as general resolution. However, the models used in these studies required either an extra degree of non-determinism or a preprocessing step that is not utilized by state-of-the-art SAT solvers in practice. In this paper, we prove that conflict-driven clause-learning SAT solvers yield proof systems that indeed p-simulate general resolution without the need for any additional techniques. Moreover, we show that our result can be generalized to certain other practical variations of the solvers, which are based on different learning schemes and restart policies.

IJCAI Conference 2011 Conference Paper

SDD: A New Canonical Representation of Propositional Knowledge Bases

• Adnan Darwiche

We identify a new representation of propositional knowledge bases, the Sentential Decision Diagram SDD, which is interesting for a number of reasons. First, it is canonical in the presence of additional properties that resemble reduction rules of OBDDs. Second, SDDs can be combined using any Boolean operator in polytime. Third, CNFs with n variables and treewidth w have canonical SDDs of size O(n 2w), which is tighter than the bound on OBDDs based on pathwidth. Finally, every OBDD is an SDD. Hence, working with the latter does not preclude the former.

AAAI Conference 2010 Conference Paper

A Lower Bound on the Size of Decomposable Negation Normal Form

• Thammanit Pipatsrisawat
• Adnan Darwiche

We consider in this paper the size of a Decomposable Negation Normal Form (DNNF) that respects a given vtree (known as structured DNNF). This representation of propositional knowledge bases was introduced recently and shown to include OBDD as a special case (an OBDD variable ordering is a special type of vtree). We provide a lower bound on the size of any structured DNNF and discuss three particular instances of this bound, which correspond to three distinct subsets of structured DNNF (including OBDD). We show that our lower bound subsumes the influential Sieling and Wegener’s lower bound for OBDDs, which is typically used for identifying variable orderings that will cause a blowup in the OBDD size. We show that our lower bound allows for similar usage but with respect to vtrees, which provide structure for DNNFs in the same way that variable orderings provide structure for OBDDs. We finally discuss some of the theoretical and practical implications of our lower bound.

ECAI Conference 2010 Conference Paper

On Decomposability and Interaction Functions

• Knot Pipatsrisawat
• Adnan Darwiche

A formal notion of a Boolean-function decomposition was introduced recently and used to provide lower bounds on various representations of Boolean functions, which are subsets of decomposable negation normal form (DNNF). This notion has introduced a fundamental optimization problem for DNNF representations, which calls for computing decompositions of minimal size for a given partition of the function variables. We consider the problem of computing optimal decompositions in this paper for general Boolean functions and those represented using CNFs. We introduce the notion of an interaction function, which characterizes the relationship between two sets of variables and can form the basis of obtaining such decompositions. We contrast the use of these functions to the current practice of computing decompositions, which is based on heuristic methods that can be viewed as using approximations of interaction functions. We show that current methods can lead to decompositions that are exponentially larger than optimal decompositions, pinpoint the specific reasons for this lack of optimality, and finally present empirical results that illustrate some characteristics of interaction functions in contrast to their approximations.

JELIA Conference 2010 Invited Paper

Relax, Compensate and Then Recover: A Theory of Anytime, Approximate Inference

• Adnan Darwiche

Abstract This talk is based on two main ideas, one concerning exact probabilistic inference and the second concerning approximate probabilistic inference. Both ideas have their roots in symbolic inference and do complement each other.

ECAI Conference 2010 Conference Paper

Top-Down Algorithms for Constructing Structured DNNF: Theoretical and Practical Implications

• Knot Pipatsrisawat
• Adnan Darwiche

We introduce a top-down compilation algorithm for constructing structured DNNF for any Boolean function. With appropriate restrictions, the algorithm can produce various subsets of DNNF such as deterministic DNNF and OBDD. We derive a size upper bound for structured DNNF based on this algorithm and use the result to generalize similar upper bounds known for several Boolean functions in the case of OBDD. We then discuss two realizations of the algorithm that work on CNF formulas. We show that these algorithms have time and space complexities that are exponential in the treewidth and the dual treewidth of the input.

IJCAI Conference 2009 Conference Paper

• Knot Pipatsrisawat
• Adnan Darwiche

We present a new algorithm for computing upper bounds for an optimization version of the E- MAJSAT problem called functional E-MAJSAT. The algorithm utilizes the compilation language d- DNNF which underlies several state-of-the-art algorithms for solving related problems. This bound computation can be used in a branch-and-bound solver for solving functional E-MAJSAT. We then present a technique for pruning values from the branch-and-bound search tree based on the information available after each bound computation. We evaluated the proposed techniques in a MAP solver and a probabilistic conformant planner. In both cases, our experiments showed that the new techniques improved the efficiency of state-of-the-art solvers by orders of magnitude.

NeurIPS Conference 2009 Conference Paper

Approximating MAP by Compensating for Structural Relaxations

• Arthur Choi
• Adnan Darwiche

We introduce a new perspective on approximations to the maximum a posteriori (MAP) task in probabilistic graphical models, that is based on simplifying a given instance, and then tightening the approximation. First, we start with a structural relaxation of the original model. We then infer from the relaxation its deficiencies, and compensate for them. This perspective allows us to identify two distinct classes of approximations. First, we find that max-product belief propagation can be viewed as a way to compensate for a relaxation, based on a particular idealized case for exactness. We identify a second approach to compensation that is based on a more refined idealized case, resulting in a new approximation with distinct properties. We go on to propose a new class of algorithms that, starting with a relaxation, iteratively yields tighter approximations.

SAT Conference 2009 Conference Paper

Width-Based Restart Policies for Clause-Learning Satisfiability Solvers

• Knot Pipatsrisawat
• Adnan Darwiche

Abstract In this paper, we present a new class of restart policies, called width-based policies, for modern clause-learning SAT solvers. The new policies encourage the solvers to find refutation proofs with small widths by determining restarting points based on the sizes of conflict clauses learned rather than the number of conflicts experienced by the solvers. We show that width-based restart policies can outperform traditional restart policies on some special classes of SAT problems. We then propose different ways of adjusting the width parameter of the policies. Our experiment on industrial problems shows that width-based policies are competitive with the restart policy used by many state-of-the-art solvers. Moreover, we find that the combination of these two types of restart policies yields improvements on many classes of problems.

UAI Conference 2008 Conference Paper

Approximating the Partition Function by Deleting and then Correcting for Model Edges

• Arthur Choi
• Adnan Darwiche

We propose an approach for approximating the partition function which is based on two steps: (1) computing the partition function of a simplified model which is obtained by deleting model edges, and (2) rectifying the result by applying an edge-by-edge correction. The approach leads to an intuitive framework in which one can trade-off the quality of an approximation with the complexity of computing it. It also includes the Bethe free energy approximation as a degenerate case. We develop the approach theoretically in this paper and provide a number of empirical results that reveal its practical utility.

AIJ Journal 2008 Journal Article

On probabilistic inference by weighted model counting

• Mark Chavira
• Adnan Darwiche

A recent and effective approach to probabilistic inference calls for reducing the problem to one of weighted model counting (WMC) on a propositional knowledge base. Specifically, the approach calls for encoding the probabilistic model, typically a Bayesian network, as a propositional knowledge base in conjunctive normal form (CNF) with weights associated to each model according to the network parameters. Given this CNF, computing the probability of some evidence becomes a matter of summing the weights of all CNF models consistent with the evidence. A number of variations on this approach have appeared in the literature recently, that vary across three orthogonal dimensions. The first dimension concerns the specific encoding used to convert a Bayesian network into a CNF. The second dimensions relates to whether weighted model counting is performed using a search algorithm on the CNF, or by compiling the CNF into a structure that renders WMC a polytime operation in the size of the compiled structure. The third dimension deals with the specific properties of network parameters (local structure) which are captured in the CNF encoding. In this paper, we discuss recent work in this area across the above three dimensions, and demonstrate empirically its practical importance in significantly expanding the reach of exact probabilistic inference. We restrict our discussion to exact inference and model counting, even though other proposals have been extended for approximate inference and approximate model counting.

IJCAI Conference 2007 Conference Paper

• Mark Chavira
• Adnan Darwiche

Compiling Bayesian networks has proven an effective approach for inference that can utilize both global and local network structure. In this paper, we define a new method of compiling based on variable elimination (VE) and Algebraic Decision Diagrams (ADDs). The approach is important for the following reasons. First, it exploits local structure much more effectively than previous techniques based on VE. Second, the approach allows any of the many VE variants to compute answers to multiple queries simultaneously. Third, the approach makes a large body of research into more structured representations of factors relevant in many more circumstances than it has been previously. Finally, experimental results demonstrate that VE can exploit local structure as effectively as state--of--the--art algorithms based on conditioning on the networks considered, and can sometimes lead to much faster compilation times.

SAT Conference 2007 Conference Paper

A Lightweight Component Caching Scheme for Satisfiability Solvers

• Knot Pipatsrisawat
• Adnan Darwiche

Abstract We introduce in this paper a lightweight technique for reducing work repetition caused by non–chronological backtracking commonly practiced by DPLL–based SAT solvers. The presented technique can be viewed as a partial component caching scheme. Empirical evaluation of the technique reveals significant improvements on a broad range of industrial instances.

UAI Conference 2007 Conference Paper

Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks

• Arthur Choi
• Mark Chavira
• Adnan Darwiche

We formulate in this paper the mini-bucket algorithm for approximate inference in terms of exact inference on an approximate model produced by splitting nodes in a Bayesian network. The new formulation leads to a number of theoretical and practical implications. First, we show that branch-and-bound search algorithms that use mini-bucket bounds may operate in a drastically reduced search space. Second, we show that the proposed formulation inspires new mini-bucket heuristics and allows us to analyze existing heuristics from a new perspective. Finally, we show that this new formulation allows mini-bucket approximations to benefit from recent advances in exact inference, allowing one to significantly increase the reach of these approximations.

UAI Conference 2006 Conference Paper

A Variational Approach for Approximating Bayesian Networks by Edge Deletion

• Arthur Choi
• Adnan Darwiche

We consider in this paper the formulation of approximate inference in Bayesian networks as a problem of exact inference on an approximate network that results from deleting edges (to reduce treewidth). We have shown in earlier work that deleting edges calls for introducing auxiliary network parameters to compensate for lost dependencies, and proposed intuitive conditions for determining these parameters. We have also shown that our method corresponds to IBP when enough edges are deleted to yield a polytree, and corresponds to some generalizations of IBP when fewer edges are deleted. In this paper, we propose a different criteria for determining auxiliary parameters based on optimizing the KL-divergence between the original and approximate networks. We discuss the relationship between the two methods for selecting parameters, shedding new light on IBP and its generalizations. We also discuss the application of our new method to approximating inference problems which are exponential in constrained treewidth, including MAP and nonmyopic value of information.

SAT Conference 2006 Conference Paper

Encoding CNFs to Empower Component Analysis

• Mark Chavira
• Adnan Darwiche

Abstract Recent algorithms for model counting and compilation work by decomposing a CNF into syntactically independent components through variable splitting, and then solving the components recursively and independently. In this paper, we observe that syntactic component analysis can miss decomposition opportunities because the syntax may hide existing semantic independence, leading to unnecessary variable splitting. Moreover, we show that by applying a limited resolution strategy to the CNF prior to inference, one can transform the CNF to syntactically reveal such semantic independence. We describe a general resolution strategy for this purpose, and a more specific one that utilizes problem–specific structure. We apply our proposed techniques to CNF encodings of Bayesian networks, which can be used to answer probabilistic queries through weighted model counting and/or knowledge compilation. Experimental results demonstrate that our proposed techniques can have a large effect on the efficiency of inference, reducing time and space requirements significantly, and allowing inference to be performed on many CNFs that exhausted resources previously.

SAT Conference 2006 Conference Paper

Functional Treewidth: Bounding Complexity in the Presence of Functional Dependencies

• Yuliya Zabiyaka
• Adnan Darwiche

Abstract Many reasoning problems in logic and constraint satisfaction have been shown to be exponential only in the treewidth of their interaction graph: a graph which captures the structural interactions among variables in a problem. It has long been observed in both logic and constraint satisfaction, however, that problems may be easy even when their treewidth is quite high. To bridge some of the gap between theoretical bounds and actual runtime, we propose a complexity parameter, called functional treewidth, which refines treewidth by being sensitive to non–structural aspects of a problem: functional dependencies in particular. This measure dominates treewidth and can be used to bound the size of CNF compilations, which permit a variety of queries in polytime, including clausal implication, existential quantification, and model counting. We present empirical results which show how the new measure can predict the complexity of certain benchmarks, that would have been considered quite difficult based on treewidth alone.

UAI Conference 2006 Conference Paper

On the Robustness of Most Probable Explanations

• Hei Chan
• Adnan Darwiche

In Bayesian networks, a Most Probable Explanation (MPE) is a complete variable instantiation with a highest probability given the current evidence. In this paper, we discuss the problem of finding robustness conditions of the MPE under single parameter changes. Specifically, we ask the question: How much change in a single network parameter can we afford to apply while keeping the MPE unchanged? We will describe a procedure, which is the first of its kind, that computes this answer for each parameter in the Bayesian network variable in time O(n exp(w)), where n is the number of network variables and w is its treewidth.

UAI Conference 2005 Conference Paper

Exploiting Evidence in Probabilistic Inference

• Mark Chavira
• David Allen
• Adnan Darwiche

We define the notion of compiling a Bayesian network with evidence and provide a specific approach for evidence-based compilation, which makes use of logical processing. The approach is practical and advantageous in a number of application areas-including maximum likelihood estimation, sensitivity analysis, and MAP computations-and we provide specific empirical results in the domain of genetic linkage analysis. We also show that the approach is applicable for networks that do not contain determinism, and show that it empirically subsumes the performance of the quickscore algorithm when applied to noisy-or networks.

UAI Conference 2005 Conference Paper

On Bayesian Network Approximation by Edge Deletion

• Adnan Darwiche
• Hei Chan
• Arthur Choi

We consider the problem of deleting edges from a Bayesian network for the purpose of simplifying models in probabilistic inference. In particular, we propose a new method for deleting network edges, which is based on the evidence at hand. We provide some interesting bounds on the KL-divergence between original and approximate networks, which highlight the impact of given evidence on the quality of approximation and shed some light on good and bad candidates for edge deletion. We finally demonstrate empirically the promise of the proposed edge deletion technique as a basis for approximate inference.

AIJ Journal 2005 Journal Article

On the revision of probabilistic beliefs using uncertain evidence

• Hei Chan
• Adnan Darwiche

We revisit the problem of revising probabilistic beliefs using uncertain evidence, and report results on several major issues relating to this problem: how should one specify uncertain evidence? How should one revise a probability distribution? How should one interpret informal evidential statements? Should, and do, iterated belief revisions commute? And what guarantees can be offered on the amount of belief change induced by a particular revision? Our discussion is focused on two main methods for probabilistic revision: Jeffrey's rule of probability kinematics and Pearl's method of virtual evidence, where we analyze and unify these methods from the perspective of the questions posed above.

ICAPS Conference 2005 Conference Paper

Pruning Conformant Plans by Counting Models on Compiled d-DNNF Representations

• Héctor Palacios
• Blai Bonet
• Adnan Darwiche
• Hector Geffner

Optimal planners in the classical setting are built around two notions: branching and pruning. SAT-based planners for example branch by trying the values of a selected variable, and prune by propagating constraints and checking consistency. In the conformant setting, a similar branching scheme can be used if restricted to action variables, but the pruning scheme must be modified. Indeed, pruning branches that encode inconsistent partial plans is not sufficient since a partial plan may be consistent and complete (covering all the action variables) and still fail to be a conformant plan. This happens indeed when the plan does not conform to some possible initial state or transition. A remedy to this problem is to use a criterion stronger than consistency for pruning. This is actually what we do in this paper where the consistency-based pruning criterion used in classical planning is replaced by a validity-based criterion suitable for conformant planning. Under the assumption that actions are deterministic, a partial plan can be defined as valid when it is logically consistent with the theory and each possible initial state. A valid partial plan that is complete is guaranteed to encode a conformant plan, and vice versa. Checking validity, however, while useful for pruning can be very expensive. We show then that such validity checks can be performed in linear time provided that the theory encoding the problem is transformed into a logically equivalent theory in deterministic decomposable negation normal form (d-DNNF). In d-DNNF, plan validity checks can be reduced to two linear-time operations: projection (finding the strongest consequence of a formula over some of its variables) and model counting (finding the number of satisfying assignments). We then define and evaluate a conformant planner that branches on action variables, and prunes invalid partial plans in linear time. The empirical results are encouraging, showing the potential benefits of stronger forms of inference in planning tasks that are not reducible to SAT.

AIJ Journal 2004 Journal Article

A differential semantics for jointree algorithms

• James D. Park
• Adnan Darwiche

A new approach to inference in belief networks has been recently proposed, which is based on an algebraic representation of belief networks using multi-linear functions. According to this approach, belief network inference reduces to a simple process of evaluating and differentiating multi-linear functions. We show here that mainstream inference algorithms based on jointrees are a special case of the approach based on multi-linear functions, in a very precise sense. We use this result to prove new properties of jointree algorithms. We also discuss some practical and theoretical implications of this new finding.

AIJ Journal 2004 Journal Article

Compiling propositional weighted bases

• Adnan Darwiche
• Pierre Marquis

In this paper, we investigate the extent to which knowledge compilation can be used to improve model checking and inference from propositional weighted bases. We first focus on the compilability issue for both problems, deriving mainly non-compilability results in the case preferences are subject to change. Then, we present a general notion of C-normal weighted base that is parametrized by a tractable class C for the clausal entailment problem. We show how every weighted base can be turned (“compiled”) into a query-equivalent C-normal base whenever C is a complete class for propositional logic. Both negative and positive results are presented. On the one hand, complexity results are identified, showing that the inference problem from a C-normal weighted base is as difficult as in the general case, when the prime implicates, Horn cover or renamable Horn cover classes are targeted. On the other hand, we show that both the model checking and the (clausal) inference problem become tractable whenever DNNF-normal bases are considered. Moreover, we show that the set of all preferred models of a DNNF-normal weighted base can be computed in time polynomial in the output size, and as a consequence, model checking is also tractable for such bases. Finally, we sketch how our results can be used in model-based diagnosis in order to compute the most likely diagnoses of a system.

ECAI Conference 2004 Conference Paper

New Advances in Compiling CNF into Decomposable Negation Normal Form

• Adnan Darwiche

UAI Conference 2004 Conference Paper

Sensitivity Analysis in Bayesian Networks: From Single to Multiple Parameters

• Hei Chan
• Adnan Darwiche

Previous work on sensitivity analysis in Bayesian networks has focused on single parameters, where the goal is to understand the sensitivity of queries to single parameter changes, and to identify single parameter changes that would enforce a certain query constraint. In this paper, we expand the work to multiple parameters which may be in the CPT of a single variable, or the CPTs of multiple variables. Not only do we identify the solution space of multiple parameter changes that would be needed to enforce a query constraint, but we also show how to find the optimal solution, that is, the one which disturbs the current probability distribution the least (with respect to a specific measure of disturbance). We characterize the computational complexity of our new techniques and discuss their applications to developing and debugging Bayesian networks, and to the problem of reasoning about the value (reliability) of new information.

SAT Conference 2004 Conference Paper

Using DPLL for Efficient OBDD Construction

• Jinbo Huang
• Adnan Darwiche

The DPLL procedure has found great success in SAT, where search terminates on the first solution discovered. We show that this procedure is equally promising in a problem where exhaustive search is used, given that it is augmented with appropriate caching. Specifically, we propose two DPLL-based algorithms that construct OBDDs for CNF formulas. These algorithms have a worst-case complexity that is linear in the number of variables and size of the CNF, and exponential only in the cutwidth or pathwidth of the variable ordering. We show how modern SAT techniques can be harnessed by implementing the algorithms on top of an existing SAT solver. We discuss the advantage of this new construction method over the traditional approach, where OBDDs for subsets of the CNF formula are built and conjoined. Our experiments indicate that on many CNF benchmarks, the new method runs orders of magnitude faster than a comparable implementation of the traditional method.

IJCAI Conference 2003 Conference Paper

A Structure-Based Variable Ordering Heuristic for SAT

• Jinbo Huang
• Adnan Darwiche

We propose a variable ordering heuristic for SAT, which is based on a structural analysis of the SAT problem. We show that when the heuristic is used by a Davis-Putnam SAT solver that employs conflict-directed backtracking, it produces a divide-and-conquer behavior in which the SAT problem is recursively decomposed into smaller problems that are solved independently. We discuss the implications of this divide-and-conquer behavior on our ability to provide structure-based guarantees on the complexity of Davis-Putnam SAT solvers. We also report on the integration of this heuristic with ZChaff— a state-of-the-art SAT solver—showing experimentally that it significantly improves performance on a range of benchmark problems that exhibit structure.

UAI Conference 2003 Conference Paper

New Advances in Inference by Recursive Conditioning

• David Allen
• Adnan Darwiche

Recursive Conditioning (RC) was introduced recently as the first any-space algorithm for inference in Bayesian networks which can trade time for space by varying the size of its cache at the increment needed to store a floating point number. Under full caching, RC has an asymptotic time and space complexity which is comparable to mainstream algorithms based on variable elimination and clustering (exponential in the network treewidth and linear in its size). We show two main results about RC in this paper. First, we show that its actual space requirements under full caching are much more modest than those needed by mainstream methods and study the implications of this finding. Second, we show that RC can effectively deal with determinism in Bayesian networks by employing standard logical techniques, such as unit resolution, allowing a significant reduction in its time requirements in certain cases. We illustrate our results using a number of benchmark networks, including the very challenging ones that arise in genetic linkage analysis

IJCAI Conference 2003 Conference Paper

On the Revision of Probabilistic Beliefs using Uncertain Evidence

• Hei Chan
• Adnan Darwiche

We revisit the problem of revising probabilistic beliefs using uncertain evidence, and report results on four major issues relating to this problem: How to specify uncertain evidence? How to revise a distribution? Should, and do, iterated belief revisions commute? And how to provide guarantees on the amount of belief change induced by a revision? Our discussion is focused on two main methods for probabilistic revision: Jeffrey's rule of probability kinematics and Pearl's method of virtual evidence, where we analyze and unify these methods from the perspective of the questions posed above.

IJCAI Conference 2003 Conference Paper

Optimal Time-Space Tradeoff in Probabilistic Inference

• David Allen
• Adnan Darwiche

Recursive Conditioning, RC, is an any-space algorithm lor exact inference in Bayesian networks, which can trade space for time in increments of the size of a floating point number. This smooth tradeoff' is possible by varying the algorithm's cache size. When RC is run with a constrained cache size, an important problem arises: Which specific results should be cached in order to minimize the running time of the algorithm? RC is driven by a structure known as a dtree, and many such dtrees exist for a given Bayesian network. In this paper, we examine the problem of searching for an optimal caching scheme for a given dtree, and present some optimal time-space tradeoff curves for given dtrees of several published Bayesian networks. We also compare these curves to the memory requirements of state-of-the-art algorithms based on jointrees. Our results show that the memory requirements of these networks can be significantly reduced with only a minimal cost in time, allowing for exact inference in situations previously impractical. They also show that probabilistic reasoning systems can be efficiently designed to run under varying amounts of memory.

UAI Conference 2003 Conference Paper

Reasoning about Bayesian Network Classifiers

• Hei Chan
• Adnan Darwiche

Bayesian network classifiers are used in many fields, and one common class of classifiers are naive Bayes classifiers. In this paper, we introduce an approach for reasoning about Bayesian network classifiers in which we explicitly convert them into Ordered Decision Diagrams (ODDs), which are then used to reason about the properties of these classifiers. Specifically, we present an algorithm for converting any naive Bayes classifier into an ODD, and we show theoretically and experimentally that this algorithm can give us an ODD that is tractable in size even given an intractable number of instances. Since ODDs are tractable representations of classifiers, our algorithm allows us to efficiently test the equivalence of two naive Bayes classifiers and characterize discrepancies between them. We also show a number of additional results including a count of distinct classifiers that can be induced by changing some CPT in a naive Bayes classifier, and the range of allowable changes to a CPT which keeps the current classifier unchanged.

UAI Conference 2003 Conference Paper

Solving MAP Exactly using Systematic Search

• James D. Park
• Adnan Darwiche

MAP is the problem of finding a most probable instantiation of a set of variables in a Bayesian network given some evidence. Unlike computing posterior probabilities, or MPE (a special case of MAP), the time and space complexity of structural solutions for MAP are not only exponential in the network treewidth, but in a larger parameter known as the ``constrained' treewidth. In practice, this means that computing MAP can be orders of magnitude more expensive than computing posterior probabilities or MPE. This paper introduces a new, simple upper bound on the probability of a MAP solution, which admits a tradeoff between the bound quality and the time needed to compute it. The bound is shown to be generally much tighter than those of other methods of comparable complexity. We use this proposed upper bound to develop a branch-and-bound search algorithm for solving MAP exactly. Experimental results demonstrate that the search algorithm is able to solve many problems that are far beyond the reach of any structure-based method for MAP. For example, we show that the proposed algorithm can compute MAP exactly and efficiently for some networks whose constrained treewidth is more than 40

AAAI Conference 2002 Conference Paper

A Compiler for Deterministic, Decomposable Negation Normal Form

• Adnan Darwiche

We present a compiler for converting CNF formulas into deterministic, decomposable negation normal form (d-DNNF). This is a logical form that has been identified recently and shown to support a number of operations in polynomial time, including clausal entailment; model counting, minimization and enumeration; and probabilistic equivalence testing. d- DNNFs are also known to be a superset of, and more succinct than, OBDDs. The polytime logical operations supported by d-DNNFs are a subset of those supported by OBDDs, yet are sufficient for model-based diagnosis and planning applications. We present experimental results on compiling a variety of CNF formulas, some generated randomly and others corresponding to digital circuits. A number of the formulas we were able to compile efficiently could not be similarly handled by some state-of-the-art model counters, nor by some state-of-the-art OBDD compilers.

NeurIPS Conference 2002 Conference Paper

A Differential Semantics for Jointree Algorithms

• James Park
• Adnan Darwiche

A new approach to inference in belief networks has been recently proposed, which is based on an algebraic representation of belief networks using multi{linear functions. According to this approach, the key computational question is that of representing multi{linear functions compactly, since inference reduces to a simple process of ev aluating and difierentiating such functions. W e show here that mainstream inference algorithms based on jointrees are a special case of this approach in a v ery precise sense. W e use this result to prov e new properties of jointree algorithms, and then discuss some of its practical and theoretical implications.

KR Conference 2002 Conference Paper

A Logical Approach to Factoring Belief Networks

• Adnan Darwiche

NMR Workshop 2002 Conference Paper

Compilation of propositional weighted bases

• Adnan Darwiche
• Pierre Marquis

In this paper, we investigate the extent to which knowledge compilation can be used to improve inference from propositional weighted bases. We present a general notion of compilation of a weighted base that is parametrized by any equivalence-preserving compilation function. Both negative and positive results are presented. On the one hand, complexity results are identified, showing that the inference problem from a compiled weighted base is as difficult as in the general case, when the prime implicates, Horn cover or renamable Horn cover classes are targeted. On the other hand, we show that the inference problem becomes tractable whenever DIN N F-compilations are used and clausal queries are considered. Moreover, we show that the set of all preferred models of a DNNFcompilation of a weighted base can be computed in time polynomial in the output size. Finally, we sketch how our results can be used in model-based diagnosis in order to compute the most probable diagnoses of a system.

UAI Conference 2001 Conference Paper

Approximating MAP using Local Search

• James D. Park
• Adnan Darwiche

MAP is the problem of finding a most probable instantiation of a set of variables in a Bayesian network, given evidence. Unlike computing marginals, posteriors, and MPE (a special case of MAP), the time and space complexity of MAP is not only exponential in the network treewidth, but also in a larger parameter known as the "constrained" treewidth. In practice, this means that computing MAP can be orders of magnitude more expensive than computingposteriors or MPE. Thus, practitioners generally avoid MAP computations, resorting instead to approximating them by the most likely value for each MAP variableseparately, or by MPE.We present a method for approximating MAP using local search. This method has space complexity which is exponential onlyin the treewidth, as is the complexity of each search step. We investigate the effectiveness of different local searchmethods and several initialization strategies and compare them to otherapproximation schemes.Experimental results show that local search provides a much more accurate approximation of MAP, while requiring few search steps.Practically, this means that the complexity of local search is often exponential only in treewidth as opposed to the constrained treewidth, making approximating MAP as efficient as other computations.

AIJ Journal 2001 Journal Article

Recursive conditioning

• Adnan Darwiche

We introduce an any-space algorithm for exact inference in Bayesian networks, called recursive conditioning. On one extreme, recursive conditioning takes O(n) space and O(nexp(wlogn)) time—where n is the size of a Bayesian network and w is the width of a given elimination order—therefore, establishing a new complexity result for linear-space inference in Bayesian networks. On the other extreme, recursive conditioning takes O(nexp(w)) space and O(nexp(w)) time, therefore, matching the complexity of state-of-the-art algorithms based on clustering and elimination. In between linear and exponential space, recursive conditioning can utilize memory at increments of X-bytes, where X is the number of bytes needed to store a floating point number in a cache. Moreover, the algorithm is equipped with a formula for computing its average running time under any amount of space, hence, providing a valuable tool for time–space tradeoffs in demanding applications. Recursive conditioning is therefore the first algorithm for exact inference in Bayesian networks to offer a smooth tradeoff between time and space, and to explicate a smooth, quantitative relationship between these two important resources.

UAI Conference 2001 Conference Paper

When do Numbers Really Matter?

• Hei Chan
• Adnan Darwiche

Common wisdom has it that small distinctions in the probabilities quantifying a Bayesian network do not matter much for the resultsof probabilistic queries. However, one can easily develop realistic scenarios under which small variations in network probabilities can lead to significant changes in computed queries. A pending theoretical question is then to analytically characterize parameter changes that do or do not matter. In this paper, we study the sensitivity of probabilistic queries to changes in network parameters and prove some tight bounds on the impact that such parameters can have on queries. Our analytical results pinpoint some interesting situations under which parameter changes do or do not matter. These results are important for knowledge engineers as they help them identify influential network parameters. They are also important for approximate inference algorithms that preprocessnetwork CPTs to eliminate small distinctions in probabilities.

UAI Conference 2000 Conference Paper

A Differential Approach to Inference in Bayesian Networks

• Adnan Darwiche

We present a new approach for inference in Bayesian networks, which is mainly based on partial differentiation. According to this approach, one compiles a Bayesian network into a multivariate polynomial and then computes the partial derivatives of this polynomial with respect to each variable. We show that once such derivatives are made available, one can compute in constant-time answers to a large class of probabilistic queries, which are central to classical inference, parameter estimation, model validation and sensitivity analysis. We present a number of complexity results relating to the compilation of such polynomials and to the computation of their partial derivatives. We argue that the combined simplicity, comprehensiveness and computational complexity of the presented framework is unique among existing frameworks for inference in Bayesian networks.

UAI Conference 2000 Conference Paper

Any-Space Probabilistic Inference

• Adnan Darwiche

We have recently introduced an any-space algorithm for exact inference in Bayesian networks, called Recursive Conditioning, RC, which allows one to trade space with time at increments of X-bytes, where X is the number of bytes needed to cache a floating point number. In this paper, we present three key extensions of RC. First, we modify the algorithm so it applies to more general factorization of probability distributions, including (but not limited to) Bayesian network factorizations. Second, we present a forgetting mechanism which reduces the space requirements of RC considerably and then compare such requirmenets with those of variable elimination on a number of realistic networks, showing orders of magnitude improvements in certain cases. Third, we present a version of RC for computing maximum a posteriori hypotheses (MAP), which turns out to be the first MAP algorithm allowing a smooth time-space tradeoff. A key advantage of presented MAP algorithm is that it does not have to start from scratch each time a new query is presented, but can reuse some of its computations across multiple queries, leading to significant savings in ceratain cases.

IJCAI Conference 1999 Conference Paper

Compiling Knowledge into Decomposable Negation Normal Form

• Adnan Darwiche

We propose a method for compiling propositional theories into a new tractable form that we refer to as decomposable negation normal form (DNNF). We show a number of results about our compilation approach. First, we show that every propositional theory can be compiled into DNNF and present an algorithm to this effect. Second, we show that if a clausal form has a bounded treewidth, then its DNNF compilation has a linear size and can be computed in linear time — treewidth is a graphtheoretic parameter which measures the connectivity of the clausal form. Third, we show that once a propositional theory is compiled into DNNF, a number of reasoning tasks, such as satisfiability and forgetting, can be performed in linear time. Finally, we propose two techniques for approximating the DNNF compilation of a theory when the size of such compilation is too large to be practical. One of the techniques generates a sound but incomplete compilation, while the other generates a complete but unsound compilation. Together, these approximations bound the exact compilation from below and above in terms for their ability to answer queries.

IJCAI Conference 1999 Conference Paper

Utilizing Device Behavior in Structure-Based Diagnosis

• Adnan Darwiche

Structure-based approaches to diagnosis provide useful computational guarantees based on a device structure. In particular, these approaches can identify device structures for which the complexity of model-based diagnosis is guaranteed to be linear. Structure-based approaches, however, can fail to answer even the simplest diagnostic queries if the device structure is not well behaved (strongly connected). We show in this paper that this deficiency can be addressed to a reasonable extent by utilizing device behavioral properties (its component models in particular) which are typically ignored by structure-based approaches. Specifically, we present a structure-based algorithm for diagnosis which takes advantage of a device behavior and then present experimental results indicating that our algorithm can lead to significant (orders-of-magnitude) savings over pure structural approaches when applied to strongly connected devices.

UAI Conference 1998 Conference Paper

Dynamic Jointrees

• Adnan Darwiche

It is well known that one can ignore parts of a belief network when computing answers to certain probabilistic queries. It is also well known that the ignorable parts (if any) depend on the specific query of interest and, therefore, may change as the query changes. Algorithms based on jointrees, however, do not seem to take computational advantage of these facts given that they typically construct jointrees for worst-case queries; that is, queries for which every part of the belief network is considered relevant. To address this limitation, we propose in this paper a method for reconfiguring jointrees dynamically as the query changes. The reconfiguration process aims at maintaining a jointree which corresponds to the underlying belief network after it has been pruned given the current query. Our reconfiguration method is marked by three characteristics: (a) it is based on a non-classical definition of jointrees; (b) it is relatively efficient; and (c) it can reuse some of the computations performed before a jointree is reconfigured. We present preliminary experimental results which demonstrate significant savings over using static jointrees when query changes are considerable.

AIJ Journal 1997 Journal Article

A logical notion of conditional independence: properties and applications

• Adnan Darwiche

We propose a notion of conditional independence with respect to prepositional logic and study some of its key properties. We present several equivalent formulations of the proposed notion, each oriented towards a specific application of logical reasoning such as abduction and diagnosis. We suggest a framework for utilizing logical independence computationally by structuring a propositional logic database around a directed acyclic graph. This structuring explicates many of the independences satisfied by the underlying database. Based on these structural independences, we develop an algorithm for a class of structured databases that is not necessarily Horn. The algorithm is linear in the size of a database structure and can be used for deciding entailment, computing abductions and diagnoses. The presented results are motivated by similar results in the literature on probabilistic and constraint-based reasoning.

UAI Conference 1997 Conference Paper

A Standard Approach for Optimizing Belief Network Inference Using Query DAGs

• Adnan Darwiche
• Gregory M. Provan

This paper proposes a novel, algorithm-independent approach to optimizing belief network inference. rather than designing optimizations on an algorithm by algorithm basis, we argue that one should use an unoptimized algorithm to generate a Q-DAG, a compiled graphical representation of the belief network, and then optimize the Q-DAG and its evaluator instead. We present a set of Q-DAG optimizations that supplant optimizations designed for traditional inference algorithms, including zero compression, network pruning and caching. We show that our Q-DAG optimizations require time linear in the Q-DAG size, and significantly simplify the process of designing algorithms for optimizing belief network inference.

AIJ Journal 1997 Journal Article

On the logic of iterated belief revision

• Adnan Darwiche
• Judea Pearl

We show in this paper that the AGM postulates are too weak to ensure the rational preservation of conditional beliefs during belief revision, thus permitting improper responses to sequences of observations. We remedy this weakness by proposing four additional postulates, which are sound relative to a qualitative version of probabilistic conditioning. Contrary to the AGM framework, the proposed postulates characterize belief revision as a process which may depend on elements of an epistemic state that are not necessarily captured by a belief set. We also show that a simple modification to the AGM framework can allow belief revision to be a function of epistemic states. We establish a model-based representation theorem which characterizes the proposed postulates and constrains, in turn, the way in which entrenchment orderings may be transformed under iterated belief revision.

AAAI Conference 1997 Conference Paper

The Effect of Observations on the Complexity of Model-Based Diagnosis

• Adnan Darwiche

This paper shows how to efficiently diagnose systems by making use of observations. In particular, we present two theorems concerning the effect of observations on the complexity of Model-Based Diagnosis. The first theorem shows how the presence of certain observations allows us to decompose a diagnostic reasoning task into independent reasoning tasks on subsystems. The second theorem shows how the absence of certain observations allows us to ignore parts of a system during diagnostic reasoning. Another main contribution of this paper is an application of these theorems to diagnosing discrete-event systems. In particular, we identify observability and modularity characteristics of discrete-event systems that make them amenable to the presented theorems and, hence, to any diagnostic approach that employs these theorems effectively. This also explains why a particular approach that we have presented elsewhere has proven effective for diagnosing these systems.

UAI Conference 1996 Conference Paper

Query DAGs: A practical paradigm for implementing belief-network inference

• Adnan Darwiche
• Gregory M. Provan

AAAI Conference 1996 Conference Paper

Utilizing Knowledge-Base Semantics in Graph-Based Algorithms

• Adnan Darwiche

Graph-based algorithms convert a knowledge base with a graph structure into one with a tree structure (a join-tree) and then apply tree-inference on the result. Nodes in the join-tree are cliques of variables and tree-inference is exponential in w*, the size of the maximal clique in the join-tree. A central property of join-trees that validates tree-inference is the running-intersection property: the intersection of any two cliques must belong to every clique on the path between them. We present two key results in connection to graph-based algorithms. First, we show that the running-intersection property, although sufficient, is not necessary for validating tree-inference. We present a weaker property for this purpose, called running-interaction, that depends on non-structural (semantical) properties of a knowledge base. We also present a linear algorithm that may reduce w* of a join-tree, possibly destroying its running-intersection property, while maintaining its running-interaction property and, hence, its validity for tree-inference. Second, we develop a simple algorithm for generating trees satisfying the running-interaction property. The algorithm bypasses triangulation (the standard technique for constructing join-trees) and does not construct a join-tree first. We show that the proposed algorithm may in some cases generate trees that are more efficient than those generated by modifying a join-tree.

UAI Conference 1995 Conference Paper

Conditioning Algorithms for Exact and Approximate Inference in Causal Networks

• Adnan Darwiche

We present two algorithms for exact and approximate inference in causal networks. The first algorithm, dynamic conditioning, is a refinement of cutset conditioning that has linear complexity on some networks for which cutset conditioning is exponential. The second algorithm, B-conditioning, is an algorithm for approximate inference that allows one to trade-off the quality of approximations with the computation time. We also present some experimental results illustrating the properties of the proposed algorithms.

UAI Conference 1994 Conference Paper

Action Networks: A Framework for Reasoning about Actions and Change under Uncertainty

• Adnan Darwiche
• Moisés Goldszmidt

This work proposes action networks as a semantically well-founded framework for reasoning about actions and change under uncertainty. Action networks add two primitives to probabilistic causal networks: controllable variables and persistent variables. Controllable variables allow the representation of actions as directly setting the value of specific events in the domain, subject to preconditions. Persistent variables provide a canonical model of persistence according to which both the state of a variable and the causal mechanism dictating its value persist over time unless intervened upon by an action (or its consequences). Action networks also allow different methods for quantifying the uncertainty in causal relationships, which go beyond traditional probabilistic quantification. This paper describes both recent results and work in progress.

TARK Conference 1994 Conference Paper

On the Logic of iterated Belief Revision

• Adnan Darwiche
• Judea Pearl

We show in this paper that the AGM postulates are too weak to ensure the rational preservation of conditional beliefs during belief revision, thus permitting improper responses to sequences of obserwtions. We remedy this weakness by augmenting the AGM system with four additional postulates, which are sound relative to a qualitative version of probabilistic conditioning. Finally, we establish a model-based representation theorem which characterizes the augmented system of postulates and constrains, in turns, the way in which entrenchment orderings may be transformed under iterated belief revisions.

UAI Conference 1994 Conference Paper

On the Relation between Kappa Calculus and Probabilistic Reasoning

• Adnan Darwiche
• Moisés Goldszmidt

We study the connection between kappa calculus and probabilistic reasoning in diagnosis applications. Specifically, we abstract a probabilistic belief network for diagnosing faults into a kappa network and compare the ordering of faults computed using both methods. We show that, at least for the example examined, the ordering of faults coincide as long as all the causal relations in the original probabilistic network are taken into account. We also provide a formal analysis of some network structures where the two methods will differ. Both kappa rankings and infinitesimal probabilities have been used extensively to study default reasoning and belief revision. But little has been done on utilizing their connection as outlined above. This is partly because the relation between kappa and probability calculi assumes that probabilities are arbitrarily close to one (or zero). The experiments in this paper investigate this relation when this assumption is not satisfied. The reported results have important implications on the use of kappa rankings to enhance the knowledge engineering of uncertainty models.

AAAI Conference 1994 Conference Paper

Symbolic Causal Networks

• Adnan Darwiche

For a logical database to faithfully represent our beliefs about the world, one should not only insist on its logical consistency but also on its causal consistency. Intuitively, a database is causally inconsistent if it supports belief changes that contradict with our perceptions of causal influences - for example, coming to conclude that it must have rained only because the sprinkler was observed to be on. In this paper, we (1) suggest the notion of a causal structure to represent our perceptions of causal influences; (2) provide a formal definition of when a database is causally consistent with a given causal structure; (3) introduce symbolic causal networks as a tool for constructing databases that are guaranteed to be causally consistent; and (4) discuss various applications of causal consistency and symbolic causal networks, including nonmonotonic reasoning, Dempster-Shafer reasoning, truth maintenance, and reasoning about actions.

UAI Conference 1993 Conference Paper

Argument Calculus and Networks

• Adnan Darwiche

A major reason behind the success of probability calculus is that it possesses a number of valuable tools, which are based on the notion of probabilistic independence. In this paper, I identify a notion of logical independence that makes some of these tools available to a class of propositional databases, called argument databases. Specifically, I suggest a graphical representation of argument databases, called argument networks, which resemble Bayesian networks. I also suggest an algorithm for reasoning with argument networks, which resembles a basic algorithm for reasoning with Bayesian networks. Finally, I show that argument networks have several applications: Nonmonotonic reasoning, truth maintenance, and diagnosis.

UAI Conference 1992 Conference Paper

Objection-based Causal Exception Networks

• Adnan Darwiche