LEARNING BOXES IN HIGH DIMENSION

We present exact learning algorithms that learn several classes of (di screte) boxes in [O,..., l - 1](n). In particular we learn: (1) The cl ass of unions of O (log n) boxes in time poly(n, log l) (solving an op en problem of [16] and [12]; in [3] this class is shown to be learnabl e in time poly(n, l)). (2) The class of unions of disjoint boxes in ti me poly(n, t, log l), 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 [3] this class is shown to be learnable in time poly(n ,t, l).) In particular our algorithm learns the class of decision tree s over n variables, that take values in (O,..., l - 1), with compariso n nodes in time poly(n, t, log l), where t is the number of leaves (th is was an open problem in [9] which was shown in [4] to be learnable i n time poly(n, t, l)). (3) The class of unions of O(1)-degenerate boxe s (that is, boxes that depend only on O(1) variables) in time poly(n, t, log l) (generalizing the learnability of O(1)-DNF and of boxes in O (1) dimensions). The algorithm for this class uses only equivalence qu eries and it can also be used to learn the class of unions of O(1) box es (from equivalence queries only).