The Learnability of Unions of Two Rectangles in the Two-Dimensional Discretized Space

摘要

We study the problem of properly learning unions of two axis-parallel rectangles over the domain {0, n−1}2 in the on-line model with equivalence queries. When only O(log n) equivalence queries are allowed, this problem is one of the five interesting open problems proposed by W. Maass and G. Turán (Mach. Learning14, 1994, 251–269), regarding learning geometric concepts. In this paper, we design an efficient algorithm that properly learns unions of two rectangles over the domain {0, n−1}2 using O(log2 n) equivalence queries.