Learning Unions of Rectangles with Queries
Files
Main report
Date
1993
DOI
Authors
Chen, Zhixiang
Homer, Steven
Version
OA Version
Citation
Chen, Zhixiang; Homer, Steve. "Learning Unions of Rectangles with Queries", Technical Report BUCS-1993-010, Computer Science Department, Boston University, August 1993. [Available from: http://hdl.handle.net/2144/1473]
Abstract
We investigate the efficient learnability of unions of k rectangles in the discrete plane (1,...,n)[2] with equivalence and membership queries. We exhibit a learning algorithm that learns any union of k rectangles with O(k^3log n) queries, while the time complexity of this algorithm is bounded by O(k^5log n). We design our learning algorithm by finding "corners" and "edges" for rectangles contained in the target concept and then constructing the target concept from those "corners" and "edges". Our result provides a first approach to on-line learning of nontrivial subclasses of unions of intersections of halfspaces with equivalence and membership queries.