## Learning Boxes in High Dimension

### Authors: Amos Beimel and Eyal Kushilevitz

ABSTRACT

We present exact learning algorithms that learn several classes of (discrete) boxes in $\{0,\ldots,\ell-1\}^n$. In particular we learn: (1) The class of unions of $O(\log n)$ boxes in time $\poly(n,\log\ell)$ (solving an open problem of \cite{GGM94,BGGM94}; in~\cite{BBBKV97} this class is shown to be learnable in time $\poly(n,\ell)$). (2) The class of unions of disjoint boxes in time $\poly(n,t,\log\ell)$, where $t$ is the number of boxes. (Previously this was known only in the case where all boxes are disjoint in one of the dimensions; in~\cite{BBBKV97} this class is shown to be learnable in time $\poly(n,t,\ell)$). In particular our algorithm learns the class of decision trees over $n$ variables, that take values in $\{0,\ldots,\ell-1\}$, with comparison nodes in time $\poly(n,t,\log\ell)$, where $t$ is the number of leaves (this was an open problem in \cite{Bsh93} which was shown in \cite{BBBKV96} to be learnable in time $\poly(n,t,\ell)$). (3) The class of unions of $O(1)$-degenerate boxes (that is, boxes that depend only on $O(1)$ variables) in time $\poly(n,t,\log\ell)$ (generalizing the learnability of $O(1)$-DNF and of boxes in $O(1)$ dimensions). The algorithm for this class uses only equivalence queries and it can also be used to learn the class of unions of $O(1)$ boxes (from equivalence queries only).

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-32.ps.gz