Learning Concepts Definable in First-Order Logic with Counting

• URL: http://arxiv.org/abs/1909.03820v2
• Date: Sat, 23 Mar 2024 22:14:50 GMT
• Title: Learning Concepts Definable in First-Order Logic with Counting
• Authors: Steffen van Bergerem,
• Abstract summary: We show that FOCN over classes of structures of polylogarithmic degree can be consistently learned in sublinear time. We extend the result to probably approximately correct (PAC) learning for classes of structures of degree at most $(log log n)c$ for some constant $c$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study Boolean classification problems over relational background structures in the logical framework introduced by Grohe and Tur\'an (TOCS 2004). It is known (Grohe and Ritzert, LICS 2017) that classifiers definable in first-order logic over structures of polylogarithmic degree can be learned in sublinear time, where the degree of the structure and the running time are measured in terms of the size of the structure. We generalise the results to the first-order logic with counting FOCN, which was introduced by Kuske and Schweikardt (LICS 2017) as an expressive logic generalising various other counting logics. Specifically, we prove that classifiers definable in FOCN over classes of structures of polylogarithmic degree can be consistently learned in sublinear time. This can be seen as a first step towards extending the learning framework to include numerical aspects of machine learning. We extend the result to agnostic probably approximately correct (PAC) learning for classes of structures of degree at most $(\log \log n)^c$ for some constant $c$. Moreover, we show that bounding the degree is crucial to obtain sublinear-time learning algorithms. That is, we prove that, for structures of unbounded degree, learning is not possible in sublinear time, even for classifiers definable in plain first-order logic.

Related papers

• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  Formal language theory pertains specifically to recognizers. It is common to instead use proxy tasks that are similar in only an informal sense. We correct this mismatch by training and evaluating neural networks directly as binary classifiers of strings.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Simulating Petri nets with Boolean Matrix Logic Programming [4.762323642506732]
  We introduce a novel approach to deal with the limitations of high-level symbol manipulations. Within this framework, we propose two novel BMLP algorithms for a class of Petri nets known as elementary nets. We demonstrate empirically that BMLP algorithms can evaluate these programs 40 times faster than tabled B-Prolog, SWI-Prolog, XSB-Prolog and Clingo.
  arXiv  Detail & Related papers  (2024-05-18T23:17:00Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a complex reasoning schema over KG upon large language models (LLMs) We augment the arbitrary first-order logical queries via binary tree decomposition to stimulate the reasoning capability of LLMs. Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)
• Agnostic Membership Query Learning with Nontrivial Savings: New Results, Techniques [0.0]
  We consider learning with membership queries for classes at the frontier of learning. This approach is inspired by and continues the study of linearlearning with nontrivial savings'' We establish agnostic learning algorithms for circuits consisting of a sublinear number of gates.
  arXiv  Detail & Related papers  (2023-11-11T23:46:48Z)
• LOGICSEG: Parsing Visual Semantics with Neural Logic Learning and Reasoning [73.98142349171552]
  LOGICSEG is a holistic visual semantic that integrates neural inductive learning and logic reasoning with both rich data and symbolic knowledge. During fuzzy logic-based continuous relaxation, logical formulae are grounded onto data and neural computational graphs, hence enabling logic-induced network training. These designs together make LOGICSEG a general and compact neural-logic machine that is readily integrated into existing segmentation models.
  arXiv  Detail & Related papers  (2023-09-24T05:43:19Z)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning. Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
  arXiv  Detail & Related papers  (2023-06-21T07:34:27Z)
• Principled and Efficient Motif Finding for Structure Learning of Lifted Graphical Models [5.317624228510748]
  Structure learning is a core problem in AI central to the fields of neuro-symbolic AI and statistical relational learning. We present the first principled approach for mining structural motifs in lifted graphical models. We show that we outperform state-of-the-art structure learning approaches by up to 6% in terms of accuracy and up to 80% in terms of runtime.
  arXiv  Detail & Related papers  (2023-02-09T12:21:55Z)
• Discourse-Aware Graph Networks for Textual Logical Reasoning [142.0097357999134]
  Passage-level logical relations represent entailment or contradiction between propositional units (e.g., a concluding sentence) We propose logic structural-constraint modeling to solve the logical reasoning QA and introduce discourse-aware graph networks (DAGNs) The networks first construct logic graphs leveraging in-line discourse connectives and generic logic theories, then learn logic representations by end-to-end evolving the logic relations with an edge-reasoning mechanism and updating the graph features.
  arXiv  Detail & Related papers  (2022-07-04T14:38:49Z)
• Learning Gradual Argumentation Frameworks using Genetic Algorithms [5.953590600890214]
  We propose a genetic algorithm to simultaneously learn the structure of argumentative classification models. Our prototype learns argumentative classification models that are comparable to decision trees in terms of learning performance and interpretability.
  arXiv  Detail & Related papers  (2021-06-25T12:33:31Z)
• Learning Concepts Described by Weight Aggregation Logic [0.0]
  We introduce an extension of first-order logic that allows to aggregate weights ofs, compare such aggregates, and use them to build more complex formulas. We show that concepts definable in FOWA1 over a weighted background structure at most polylogarithmic degree are agnostically PAC-learnable in polylogarithmic time after pseudo-linear time preprocessing.
  arXiv  Detail & Related papers  (2020-09-22T14:32:42Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  We study the task of logical generalization using graph neural networks (GNNs) Our benchmark suite, GraphLog, requires that learning algorithms perform rule induction in different synthetic logics. We find that the ability for models to generalize and adapt is strongly determined by the diversity of the logical rules they encounter during training.
  arXiv  Detail & Related papers  (2020-03-14T05:45:55Z)

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.