Belief Revision in Sentential Decision Diagrams

• URL: http://arxiv.org/abs/2201.08112v1
• Date: Thu, 20 Jan 2022 11:01:41 GMT
• Title: Belief Revision in Sentential Decision Diagrams
• Authors: Lilith Mattei and Alessandro Facchini and Alessandro Antonucci
• Abstract summary: We develop a general revision algorithm for SDDs based on a syntactic characterisation of Dalal revision. Preliminary experiments performed with randomly generated knowledge bases show the advantages of directly perform revision within SDD formalism.
• Score: 126.94029917018733
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Belief revision is the task of modifying a knowledge base when new information becomes available, while also respecting a number of desirable properties. Classical belief revision schemes have been already specialised to \emph{binary decision diagrams} (BDDs), the classical formalism to compactly represent propositional knowledge. These results also apply to \emph{ordered} BDDs (OBDDs), a special class of BDDs, designed to guarantee canonicity. Yet, those revisions cannot be applied to \emph{sentential decision diagrams} (SDDs), a typically more compact but still canonical class of Boolean circuits, which generalizes OBDDs, while not being a subclass of BDDs. Here we fill this gap by deriving a general revision algorithm for SDDs based on a syntactic characterisation of Dalal revision. A specialised procedure for DNFs is also presented. Preliminary experiments performed with randomly generated knowledge bases show the advantages of directly perform revision within SDD formalism.

Related papers

• Dataset Distillation from First Principles: Integrating Core Information Extraction and Purposeful Learning [10.116674195405126]
  We argue that a precise characterization of the underlying optimization problem must specify the inference task associated with the application of interest. Our formalization reveals novel applications of DD across different modeling environments. We present numerical results for two case studies important in contemporary settings.
  arXiv  Detail & Related papers  (2024-09-02T18:11:15Z)
• Outdated Issue Aware Decoding for Reasoning Questions on Edited Knowledge [93.54427119091174]
  We propose outDated ISsue aware deCOding to enhance the performance of edited models on reasoning questions. We capture the difference in the probability distribution between the original and edited models. We amplify the difference of the token prediction in the edited model to alleviate the outdated issue.
  arXiv  Detail & Related papers  (2024-06-05T03:00:15Z)
• Canonical Decision Diagrams Modulo Theories [0.19285000127136376]
  Decision diagrams are powerful tools to represent propositional formulas. Some forms of DDs (e.g., OBDDs, SDDs) are canonical, that is, (under given conditions on the atom list) they univocally represent equivalence classes of formulas. We present a novel technique to leverage DDs to SMT level, which has several advantages.
  arXiv  Detail & Related papers  (2024-04-25T09:34:49Z)
• Exploiting Asymmetry in Logic Puzzles: Using ZDDs for Symbolic Model Checking Dynamic Epistemic Logic [0.0]
  We use ZDDs to symbolically encode Kripke models used in Dynamic Epistemic Logic. We show that replacing BDDs with the right variant of ZDDs can significantly reduce memory usage. This suggests that ZDDs are a useful tool for model checking multi-agent systems.
  arXiv  Detail & Related papers  (2023-07-11T07:13:09Z)
• Optimal Decision Diagrams for Classification [68.72078059880018]
  We study the training of optimal decision diagrams from a mathematical programming perspective. We introduce a novel mixed-integer linear programming model for training. We show how this model can be easily extended for fairness, parsimony, and stability notions.
  arXiv  Detail & Related papers  (2022-05-28T18:31:23Z)
• Generalizable Person Re-Identification via Self-Supervised Batch Norm Test-Time Adaption [63.7424680360004]
  Batch Norm Test-time Adaption (BNTA) is a novel re-id framework that applies the self-supervised strategy to update BN parameters adaptively. BNTA explores the domain-aware information within unlabeled target data before inference, and accordingly modulates the feature distribution normalized by BN to adapt to the target domain.
  arXiv  Detail & Related papers  (2022-03-01T18:46:32Z)
• Relieving Long-tailed Instance Segmentation via Pairwise Class Balance [85.53585498649252]
  Long-tailed instance segmentation is a challenging task due to the extreme imbalance of training samples among classes. It causes severe biases of the head classes (with majority samples) against the tailed ones. We propose a novel Pairwise Class Balance (PCB) method, built upon a confusion matrix which is updated during training to accumulate the ongoing prediction preferences.
  arXiv  Detail & Related papers  (2022-01-08T07:48:36Z)
• Variable Shift SDD: A More Succinct Sentential Decision Diagram [10.91026094237478]
  Sentential Decision Diagram (SDD) is a tractable representation of Boolean functions. We propose a more succinct variant of SDD named Variable Shift SDD (VS-SDD) We show that VS-SDDs are never larger than SDDs and there are cases in which the size of a VS-SDD is exponentially smaller than that of an SDD.
  arXiv  Detail & Related papers  (2020-04-06T09:18:19Z)
• Simple and Effective Prevention of Mode Collapse in Deep One-Class Classification [93.2334223970488]
  We propose two regularizers to prevent hypersphere collapse in deep SVDD. The first regularizer is based on injecting random noise via the standard cross-entropy loss. The second regularizer penalizes the minibatch variance when it becomes too small.
  arXiv  Detail & Related papers  (2020-01-24T03:44:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.