DIMACS TR: 97-32
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
DIMACS Home Page