Oliver Markgraf

"Learning Union of Integer Hypercubes with Queries (with Applications to Monadic Decomposition)"

We study the problem of learning a nite 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 xed dimension d. Over a non- xed dimension, the problem subsumes the problem of learning DNF boolean formulas, a central open problem in the eld. We have also provided extensions to handle in nite 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 quanti er-free integer linear arithmetic formulas, which has been actively studied in recent years. In particular, a nite union of integer hypercubes correspond to a nite disjunction of monadic predicates over integer linear arithmetic (without modulo constraints). Our experiments suggest that our learning algorithms substantially outperform the existing algorithms.

Termin als Datei downloaden und in den Kalender importieren.