Learning Unions of Rectangles with Queries
1993-010-learning-rect.pdf (249.4Kb) Main report
MetadataShow full item record
CitationChen, 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]
We investigate the efficient learnability of unions of k rectangles in the discrete plane (1,...,n) 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.