On-line learning of rectangles
Zhixiang Chen, Wolfgang Maass · 1992
This paper solves the following open problem: Is there an algorithm for on-line learning of rectangles i=1Πd{ai,ai+1,…,bi} over a discrete domain {1,…,n}d whose error bound is polylogarithmic in the size nd of the domain (i.e. polynomial in d and log n )? We give a positive solution by introducing a new design technique that appears to be of some interest on its own. The new learning algorithm for rectangles consists of 2d separate search strategies that search for the parameters a1,b1,…,ad,bd of the target rectangle. A learning algorithm with this type of modular design ends to fail because of the well known “credit assignment problem”: Which of the 2d local search strategies should be “blamed” when the global algorithm makes an error? We overcome this difficulty by employing local search strategies (“error tolerant binary search”) that are able to tolerate certain types of wrong credit assignments.