On the non-efficient PAC learnability of conjunctive queries

• URL: http://arxiv.org/abs/2208.10255v2
• Date: Wed, 26 Jul 2023 22:25:35 GMT
• Title: On the non-efficient PAC learnability of conjunctive queries
• Authors: Balder ten Cate, Maurice Funk, Jean Christoph Jung, Carsten Lutz
• Abstract summary: This note provides a self-contained exposition of the fact that conjunctive queries are not efficiently learnable. We also establish a strong negative PAC learnability result that applies to many restricted classes of conjunctive queries (CQs) We show that CQs (and UCQs) are efficiently learnable with membership queries.
• Score: 18.851061569487616
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This note serves three purposes: (i) we provide a self-contained exposition of the fact that conjunctive queries are not efficiently learnable in the Probably-Approximately-Correct (PAC) model, paying clear attention to the complicating fact that this concept class lacks the polynomial-size fitting property, a property that is tacitly assumed in much of the computational learning theory literature; (ii) we establish a strong negative PAC learnability result that applies to many restricted classes of conjunctive queries (CQs), including acyclic CQs for a wide range of notions of "acyclicity"; (iii) we show that CQs (and UCQs) are efficiently PAC learnable with membership queries.

Related papers

• Controlled Query Evaluation through Epistemic Dependencies [7.502796412126707]
  We show the expressive abilities of our framework and study the data complexity of CQE for (unions of) conjunctive queries. We prove tractability for the case of acyclic dependencies by providing a suitable query algorithm.
  arXiv  Detail & Related papers  (2024-05-03T19:48:07Z)
• Answering from Sure to Uncertain: Uncertainty-Aware Curriculum Learning for Video Question Answering [63.12469700986452]
  We introduce the concept of uncertainty-aware curriculum learning (CL) Here, uncertainty serves as the guiding principle for dynamically adjusting the difficulty. In practice, we seamlessly integrate the VideoQA model into our framework and conduct comprehensive experiments.
  arXiv  Detail & Related papers  (2024-01-03T02:29:34Z)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  We give a simple and efficient boosting algorithm, that does not require realizability assumptions. We present a new result on boosting for list learners, as well as provide a novel proof for the characterization of multiclass PAC learning.
  arXiv  Detail & Related papers  (2023-07-02T19:26:58Z)
• Querying Circumscribed Description Logic Knowledge Bases [9.526604375441073]
  Circumscription is one of the main approaches for defining non-monotonic description logics. We prove decidability of (U)CQ evaluation on circumscribed DL KBs. We also study the much simpler atomic queries (AQs)
  arXiv  Detail & Related papers  (2023-06-07T15:50:15Z)
• PACIFIC: Towards Proactive Conversational Question Answering over Tabular and Textual Data in Finance [96.06505049126345]
  We present a new dataset, named PACIFIC. Compared with existing CQA datasets, PACIFIC exhibits three key features: (i) proactivity, (ii) numerical reasoning, and (iii) hybrid context of tables and text. A new task is defined accordingly to study Proactive Conversational Question Answering (PCQA), which combines clarification question generation and CQA. UniPCQA performs multi-task learning over all sub-tasks in PCQA and incorporates a simple ensemble strategy to alleviate the error propagation issue in the multi-task learning by cross-validating top-$k$ sampled Seq2Seq
  arXiv  Detail & Related papers  (2022-10-17T08:06:56Z)
• Efficient Knowledge Compilation Beyond Weighted Model Counting [7.828647825246474]
  We introduce Second Level Algebraic Model Counting (2AMC) as a generic framework for these kinds of problems. First level techniques based on Knowledge Compilation (KC) have been adapted for specific 2AMC instances by imposing variable order constraints. We show that we can exploit the logical structure of a 2AMC problem to omit parts of these constraints, thus limiting the negative effect.
  arXiv  Detail & Related papers  (2022-05-16T08:10:40Z)
• Finite Entailment of UCRPQs over ALC Ontologies [0.82179684645881]
  We consider the query language, unions of conjunctive regular path queries (UCRPQs) We show a tight 2EXP bound for entailment of UCRPQs using the description logic ALC. There is a novel automata-based technique introducing a stratification of interpretations induced by the deterministic finite automaton underlying the input automaton.
  arXiv  Detail & Related papers  (2022-04-29T17:38:13Z)
• Actively Learning Concepts and Conjunctive Queries under ELr-Ontologies [22.218000867486726]
  We show that EL-concepts are not query learnable in the presence of ELI-ontologies. We also show that EL-concepts are not query learnable in the presence of ELI-ontologies.
  arXiv  Detail & Related papers  (2021-05-18T07:45:37Z)
• Counterfactual Variable Control for Robust and Interpretable Question Answering [57.25261576239862]
  Deep neural network based question answering (QA) models are neither robust nor explainable in many cases. In this paper, we inspect such spurious "capability" of QA models using causal inference. We propose a novel approach called Counterfactual Variable Control (CVC) that explicitly mitigates any shortcut correlation.
  arXiv  Detail & Related papers  (2020-10-12T10:09:05Z)
• Joint Contrastive Learning with Infinite Possibilities [114.45811348666898]
  This paper explores useful modifications of the recent development in contrastive learning via novel probabilistic modeling. We derive a particular form of contrastive loss named Joint Contrastive Learning (JCL)
  arXiv  Detail & Related papers  (2020-09-30T16:24:21Z)
• Probably Approximately Correct Constrained Learning [135.48447120228658]
  We develop a generalization theory based on the probably approximately correct (PAC) learning framework. We show that imposing a learner does not make a learning problem harder in the sense that any PAC learnable class is also a constrained learner. We analyze the properties of this solution and use it to illustrate how constrained learning can address problems in fair and robust classification.
  arXiv  Detail & Related papers  (2020-06-09T19:59:29Z)

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.