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. (shrink)

Recent work has shown that the input-output behavior of some common machine learning classifiers can be captured in symbolic form, allowing one to reason about the behavior of these classifiers using symbolic techniques. This includes explaining decisions, measuring robustness, and proving formal properties of machine learning classifiers by reasoning about the corresponding symbolic classifiers. In this work, we present a theory for unveiling the _reasons_ behind the decisions made by Boolean classifiers and study some of its theoretical and practical implications. (...) At the core of our theory is the notion of a _complete reason,_ which can be viewed as a necessary and sufficient condition for why a decision was made. We show how the complete reason can be used for computing notions such as sufficient reasons (also known as PI-explanations and abductive explanations), how it can be used for determining decision and classifier bias and how it can be used for evaluating counterfactual statements such as “a decision will stick even if...because....” We present a linear-time algorithm for computing the complete reasoning behind a decision, assuming the classifier is represented by a Boolean circuit of appropriate form. We then show how the computed complete reason can be used to answer many queries about a decision in linear or polynomial time. We finally conclude with a case study that illustrates the various notions and techniques we introduced. (shrink)

We address in this paper the problem of counting the models of a propositional theory under incremental changes to its literals. Specifcally, we show that if a propositional theory Δ is in a special form that we call smooth, deterministic, decomposable negation normal form, then for any consistent set of literals S, we can simultaneously count the models of Δ ∪ S and the models of every theory Δ ∪ T where T results from adding, removing or flipping a literal (...) in S. We present two results relating to the time and space complexity of compiling propositional theories into sd-DNNF. First, we show that if a conjunctive normal form has a bounded treewidth, then it can be compiled into an sd-DNNF in time and space which are linear in its size. Second, we show that sd-DNNF is a strictly more space efficient representation than Free Binary Decision Diagrams. Finally, we discuss some applications of the counting results to truth maintenance systems, belief revision, and model-based diagnosis. (shrink)

We address in this paper the problem of counting the models of a propositional theory under incremental changes to its literals. Specifcally, we show that if a propositional theory Δ is in a special form that we call smooth, deterministic, decomposable negation normal form (sd-DNNF), then for any consistent set of literals S, we can simultaneously count (in time linear in the size of Δ) the models of Δ ∪ S and the models of every theory Δ ∪ T where (...) T results from adding, removing or flipping a literal in S. We present two results relating to the time and space complexity of compiling propositional theories into sd-DNNF. First, we show that if a conjunctive normal form (CNF) has a bounded treewidth, then it can be compiled into an sd-DNNF in time and space which are linear in its size. Second, we show that sd-DNNF is a strictly more space efficient representation than Free Binary Decision Diagrams (FBDDs). Finally, we discuss some applications of the counting results to truth maintenance systems, belief revision, and model-based diagnosis. (shrink)