Authors: Zhixiang Chen, and Foued Ameur
Source: Journal of Computer and System Sciences Vol. 59, No. 1, 1999, 70 - 83.
Abstract. 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. Learning 14, 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.
©Copyright 1999, Academic Press