Conjunctive Queries: Unique Characterizations and Exact Learnability
- URL: http://arxiv.org/abs/2008.06824v4
- Date: Wed, 24 Aug 2022 15:43:59 GMT
- Title: Conjunctive Queries: Unique Characterizations and Exact Learnability
- Authors: Balder ten Cate and Victor Dalmau
- Abstract summary: We present a new efficient exact learning algorithm for a class of conjunctive queries.
We also discuss implications for constructing frontiers in the homomorphism lattice of finite structures.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We answer the question which conjunctive queries are uniquely characterized
by polynomially many positive and negative examples, and how to construct such
examples efficiently. As a consequence, we obtain a new efficient exact
learning algorithm for a class of conjunctive queries. At the core of our
contributions lie two new polynomial-time algorithms for constructing frontiers
in the homomorphism lattice of finite structures. We also discuss implications
for the unique characterizability and learnability of schema mappings and of
description logic concepts.
Related papers
- Even-if Explanations: Formal Foundations, Priorities and Complexity [18.126159829450028]
We show that both linear and tree-based models are strictly more interpretable than neural networks.
We introduce a preference-based framework that enables users to personalize explanations based on their preferences.
arXiv Detail & Related papers (2024-01-17T11:38:58Z) - Counting Solutions to Conjunctive Queries: Structural and Hybrid
Tractability [9.41501655306019]
Counting the number of answers to conjunctive queries is a fundamental problem in databases that, under standard assumptions, does not have an efficient solution.
We pinpoint tractable classes by examining the structural properties of intrinsic instances and introducing the novel concept of #-hypertree decomposition.
arXiv Detail & Related papers (2023-11-24T16:09:12Z) - Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models.
A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters.
We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
arXiv Detail & Related papers (2023-10-05T07:10:40Z) - Query Structure Modeling for Inductive Logical Reasoning Over Knowledge
Graphs [67.043747188954]
We propose a structure-modeled textual encoding framework for inductive logical reasoning over KGs.
It encodes linearized query structures and entities using pre-trained language models to find answers.
We conduct experiments on two inductive logical reasoning datasets and three transductive datasets.
arXiv Detail & Related papers (2023-05-23T01:25:29Z) - On the Complexity of Representation Learning in Contextual Linear
Bandits [110.84649234726442]
We show that representation learning is fundamentally more complex than linear bandits.
In particular, learning with a given set of representations is never simpler than learning with the worst realizable representation in the set.
arXiv Detail & Related papers (2022-12-19T13:08:58Z) - Synergies between Disentanglement and Sparsity: Generalization and
Identifiability in Multi-Task Learning [79.83792914684985]
We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations.
Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
arXiv Detail & Related papers (2022-11-26T21:02:09Z) - Object Representations as Fixed Points: Training Iterative Refinement
Algorithms with Implicit Differentiation [88.14365009076907]
Iterative refinement is a useful paradigm for representation learning.
We develop an implicit differentiation approach that improves the stability and tractability of training.
arXiv Detail & Related papers (2022-07-02T10:00:35Z) - The Combinatorics of \textit{Salva Veritate} Principles [0.0]
Concepts of grammatical compositionality arise in many theories of both natural and artificial languages.
We propose that many instances of compositionality should entail non-trivial claims about the expressive power of languages.
arXiv Detail & Related papers (2022-01-13T19:00:56Z) - Differentiable Inductive Logic Programming for Structured Examples [6.8774606688738995]
We propose a new framework to learn logic programs from noisy and structured examples.
We show that our new framework can learn logic programs from noisy and structured examples, such as sequences or trees.
Our framework can be scaled to deal with complex programs that consist of several clauses with function symbols.
arXiv Detail & Related papers (2021-03-02T13:47:33Z) - A Diagnostic Study of Explainability Techniques for Text Classification [52.879658637466605]
We develop a list of diagnostic properties for evaluating existing explainability techniques.
We compare the saliency scores assigned by the explainability techniques with human annotations of salient input regions to find relations between a model's performance and the agreement of its rationales with human ones.
arXiv Detail & Related papers (2020-09-25T12:01:53Z) - Lattice Representation Learning [6.427169570069738]
We introduce theory and algorithms for learning discrete representations that take on a lattice that is embedded in an Euclidean space.
Lattice representations possess an interesting combination of properties: a) they can be computed explicitly using lattice quantization, yet they can be learned efficiently using the ideas we introduce.
This article will focus on laying the groundwork for exploring and exploiting the first two properties, including a new mathematical result linking expressions used during training and inference time and experimental validation on two popular datasets.
arXiv Detail & Related papers (2020-06-24T16:05:11Z)
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.