Exact learning for infinite families of concepts

• URL: http://arxiv.org/abs/2201.08225v1
• Date: Thu, 13 Jan 2022 07:32:47 GMT
• Title: Exact learning for infinite families of concepts
• Authors: Mikhail Moshkov
• Abstract summary: We study arbitrary infinite families of concepts each of which consists of an infinite set of elements and an infinite set of subsets of this set called concepts. We consider the notion of a problem over a family of concepts that is described by a finite number of elements.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, based on results of exact learning, test theory, and rough set theory, we study arbitrary infinite families of concepts each of which consists of an infinite set of elements and an infinite set of subsets of this set called concepts. We consider the notion of a problem over a family of concepts that is described by a finite number of elements: for a given concept, we should recognize which of the elements under consideration belong to this concept. As algorithms for problem solving, we consider decision trees of five types: (i) using membership queries, (ii) using equivalence queries, (iii) using both membership and equivalence queries, (iv) using proper equivalence queries, and (v) using both membership and proper equivalence queries. As time complexity, we study the depth of decision trees. In the worst case, with the growth of the number of elements in the problem description, the minimum depth of decision trees of the first type either grows as a logarithm or linearly, and the minimum depth of decision trees of each of the other types either is bounded from above by a constant or grows as a logarithm, or linearly. The obtained results allow us to distinguish seven complexity classes of infinite families of concepts.

Related papers

• Properly Learning Decision Trees with Queries Is NP-Hard [5.117810469621253]
  We prove that it is NP-hard to properly PAC learn decision trees with queries. We simplify and strengthen the best known lower bounds for a different problem of Decision Tree Minimization.
  arXiv  Detail & Related papers  (2023-07-09T04:29:43Z)
• Enriching Disentanglement: From Logical Definitions to Quantitative Metrics [59.12308034729482]
  Disentangling the explanatory factors in complex data is a promising approach for data-efficient representation learning. We establish relationships between logical definitions and quantitative metrics to derive theoretically grounded disentanglement metrics. We empirically demonstrate the effectiveness of the proposed metrics by isolating different aspects of disentangled representations.
  arXiv  Detail & Related papers  (2023-05-19T08:22:23Z)
• A Category-theoretical Meta-analysis of Definitions of Disentanglement [97.34033555407403]
  Disentangling the factors of variation in data is a fundamental concept in machine learning. This paper presents a meta-analysis of existing definitions of disentanglement.
  arXiv  Detail & Related papers  (2023-05-11T15:24:20Z)
• Logic for Explainable AI [11.358487655918676]
  A central quest in explainable AI relates to understanding the decisions made by (learned) classifiers. We discuss in this tutorial a comprehensive, semantical and computational theory of explainability along these dimensions.
  arXiv  Detail & Related papers  (2023-05-09T04:53:57Z)
• 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)
• Regularized impurity reduction: Accurate decision trees with complexity guarantees [20.170305081348328]
  We propose a tree-induction algorithm that gives a logarithmic approximation guarantee on the tree complexity. The enhanced algorithms strike an excellent balance between predictive accuracy and tree complexity.
  arXiv  Detail & Related papers  (2022-08-23T13:15:19Z)
• Joint Abductive and Inductive Neural Logical Reasoning [44.36651614420507]
  We formulate the problem of the joint abductive and inductive neural logical reasoning (AI-NLR) First, we incorporate description logic-based ontological axioms to provide the source of concepts. Then, we represent concepts and queries as fuzzy sets, i.e., sets whose elements have degrees of membership, to bridge concepts and queries with entities.
  arXiv  Detail & Related papers  (2022-05-29T07:41:50Z)
• Improved Quantum Query Upper Bounds Based on Classical Decision Trees [0.0]
  Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up.
  arXiv  Detail & Related papers  (2022-03-06T14:04:06Z)
• Exact learning and test theory [0.0]
  We study arbitrary infinite binary information systems each of which consists of an infinite set of elements. We consider the notion of a problem over information system, which is described by a finite number of attributes.
  arXiv  Detail & Related papers  (2022-01-12T15:10:22Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Foundations of Reasoning with Uncertainty via Real-valued Logics [70.43924776071616]
  We give a sound and strongly complete axiomatization that can be parametrized to cover essentially every real-valued logic. Our class of sentences are very rich, and each describes a set of possible real values for a collection of formulas of the real-valued logic.
  arXiv  Detail & Related papers  (2020-08-06T02:13: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.