Phase Transition Behavior in Knowledge Compilation
- URL: http://arxiv.org/abs/2007.10400v1
- Date: Mon, 20 Jul 2020 18:36:27 GMT
- Title: Phase Transition Behavior in Knowledge Compilation
- Authors: Rahul Gupta, Subhajit Roy, Kuldeep S. Meel
- Abstract summary: We study the behaviour of size and compile-time behaviour for random k-CNF formulas in the context of knowledge compilation.
Our work is similar in spirit to the early work in CSP community on phase transition behavior in SAT/CSP.
- Score: 52.68422776053012
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The study of phase transition behaviour in SAT has led to deeper
understanding and algorithmic improvements of modern SAT solvers. Motivated by
these prior studies of phase transitions in SAT, we seek to study the behaviour
of size and compile-time behaviour for random k-CNF formulas in the context of
knowledge compilation.
We perform a rigorous empirical study and analysis of the size and runtime
behavior for different knowledge compilation forms (and their corresponding
compilation algorithms): d-DNNFs, SDDs and OBDDs across multiple tools and
compilation algorithms. We employ instances generated from the random k-CNF
model with varying generation parameters to empirically reason about the
expected and median behavior of size and compilation-time for these languages.
Our work is similar in spirit to the early work in CSP community on phase
transition behavior in SAT/CSP. In a similar spirit, we identify the
interesting behavior with respect to different parameters: clause density and
solution density, a novel control parameter that we identify for the study of
phase transition behavior in the context of knowledge compilation. Furthermore,
we summarize our empirical study in terms of two concrete conjectures; a
rigorous study of these conjectures will possibly require new theoretical
tools.
Related papers
- Process Variant Analysis Across Continuous Features: A Novel Framework [0.0]
This research addresses the challenge of effectively segmenting cases within operational processes.
We present a novel approach employing a sliding window technique combined with the earth mover's distance to detect changes in control flow behavior.
We validate our methodology through a real-life case study in collaboration with UWV, the Dutch employee insurance agency.
arXiv Detail & Related papers (2024-05-06T16:10:13Z) - Exploring Continual Learning of Compositional Generalization in NLI [24.683598294766774]
We introduce the Continual Compositional Generalization in Inference (C2Gen NLI) challenge.
A model continuously acquires knowledge of constituting primitive inference tasks as a basis for compositional inferences.
Our analyses show that by learning subtasks continuously while observing their dependencies and increasing degrees of difficulty, continual learning can enhance composition generalization ability.
arXiv Detail & Related papers (2024-03-07T10:54:27Z) - On the Need of a Modeling Language for Distribution Shifts: Illustrations on Tabular Datasets [30.518020409197767]
We build an empirical testbed comprising natural shifts across 5 datasets and 60,000 method configurations.
We find $Y|X$-shifts are most prevalent on our testbed, in stark contrast to the heavy focus on $X$ (co)-shifts in the ML literature.
arXiv Detail & Related papers (2023-07-11T14:25:10Z) - iSCAN: Identifying Causal Mechanism Shifts among Nonlinear Additive
Noise Models [48.33685559041322]
This paper focuses on identifying the causal mechanism shifts in two or more related datasets over the same set of variables.
Code implementing the proposed method is open-source and publicly available at https://github.com/kevinsbello/iSCAN.
arXiv Detail & Related papers (2023-06-30T01:48:11Z) - A Mechanistic Interpretation of Arithmetic Reasoning in Language Models
using Causal Mediation Analysis [128.0532113800092]
We present a mechanistic interpretation of Transformer-based LMs on arithmetic questions.
This provides insights into how information related to arithmetic is processed by LMs.
arXiv Detail & Related papers (2023-05-24T11:43:47Z) - Amortized Inference for Causal Structure Learning [72.84105256353801]
Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test.
We train a variational inference model to predict the causal structure from observational/interventional data.
Our models exhibit robust generalization capabilities under substantial distribution shift.
arXiv Detail & Related papers (2022-05-25T17:37:08Z) - Schr\"odinger's Tree -- On Syntax and Neural Language Models [10.296219074343785]
Language models have emerged as NLP's workhorse, displaying increasingly fluent generation capabilities.
We observe a lack of clarity across numerous dimensions, which influences the hypotheses that researchers form.
We outline the implications of the different types of research questions exhibited in studies on syntax.
arXiv Detail & Related papers (2021-10-17T18:25:23Z) - Did the Cat Drink the Coffee? Challenging Transformers with Generalized
Event Knowledge [59.22170796793179]
Transformers Language Models (TLMs) were tested on a benchmark for the textitdynamic estimation of thematic fit
Our results show that TLMs can reach performances that are comparable to those achieved by SDM.
However, additional analysis consistently suggests that TLMs do not capture important aspects of event knowledge.
arXiv Detail & Related papers (2021-07-22T20:52:26Z) - A Constraint-Based Algorithm for the Structural Learning of
Continuous-Time Bayesian Networks [70.88503833248159]
We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks.
We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
arXiv Detail & Related papers (2020-07-07T07:34:09Z) - Structure learning for CTBN's via penalized maximum likelihood methods [2.997206383342421]
We study the structure learning problem, which is a more challenging task and the existing research on this topic is limited.
We prove that our algorithm, under mild regularity conditions, recognizes the dependence structure of the graph with high probability.
arXiv Detail & Related papers (2020-06-13T14:28:19Z)
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.