Learning union of integer hypercubes with queries (with applications to monadic decomposition)

DOI10.1007/978-3-030-81688-9_12MaRDI QIDQ832265zbMATH OpenOpenAlexFDO

Authors Oliver Markgraf, Daniel Stan, Anthony Widjaja Lin

Publication date 25 March 2022

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2105.13071

Mathematics Subject Classification ID

Computational learning theory (68Q32) Logic in computer science (03B70)

Abstract: We study the problem of learning a finite union of integer (axis-aligned) hypercubes over the d-dimensional integer lattice, i.e., whose edges are parallel to the coordinate axes. This is a natural generalization of the classic problem in the computational learning theory of learning rectangles. We provide a learning algorithm with access to a minimally adequate teacher (i.e. membership and equivalence oracles) that solves this problem in polynomial-time, for any fixed dimension d. Over a non-fixed dimension, the problem subsumes the problem of learning DNF boolean formulas, a central open problem in the field. We have also provided extensions to handle infinite hypercubes in the union, as well as showing how subset queries could improve the performance of the learning algorithm in practice. Our problem has a natural application to the problem of monadic decomposition of quantifier-free integer linear arithmetic formulas, which has been actively studied in recent years. In particular, a finite union of integer hypercubes correspond to a finite disjunction of monadic predicates over integer linear arithmetic (without modulo constraints). Our experiments suggest that our learning algorithms substantially outperform the existing algorithms.

Recommendations

• Learning unions of high-dimensional boxes over the reals
• Learning Unions of ω(1)-Dimensional Rectangles
• Learning boxes in high dimension
• Exact Learning of Discretized Geometric Concepts
• Learning unions of (1)-dimensional rectangles

Cites work

• scientific article; zbMATH DE number 7561596 (Why is no real title available?)
• A constraint-based approach to solving games on infinite graphs
• Algorithms and lower bounds for on-line learning of geometrical concepts
• An optimal algorithm for proper learning of unions of two rectangles with queries
• Characterizing PAC-learnability of semilinear sets
• Decision problems among the main subfamilies of rational relations
• Decision procedures. An algorithmic point of view
• Learning Minimal Separating DFA’s for Compositional Verification
• Learning regular sets from queries and counterexamples
• Learning semilinear sets from examples and via queries
• Liveness of randomised parameterised systems under arbitrary schedulers
• Monadic decomposition
• Monadic decomposition in integer linear arithmetic
• On the number of prime implicants
• Parameterized synthesis with safety properties
• Queries and concept learning
• The learnability of unions of two rectangles in the two-dimensional discretized space
• The power of symbolic automata and transducers
• Variable independence for first-order definable constraints
• When won't membership queries help?

Cited in

(1)

• Finding the Rare Cube

Describes a project that uses

Uses Software

• z3

This page was built for publication: Learning union of integer hypercubes with queries (with applications to monadic decomposition)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832265)