On-Line Learning of Rectangles
Abstract
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,…,nd 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.
Cite
Text
Chen and Maass. "On-Line Learning of Rectangles." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130387Markdown
[Chen and Maass. "On-Line Learning of Rectangles." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/chen1992colt-line/) doi:10.1145/130385.130387BibTeX
@inproceedings{chen1992colt-line,
title = {{On-Line Learning of Rectangles}},
author = {Chen, Zhixiang and Maass, Wolfgang},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1992},
pages = {16-28},
doi = {10.1145/130385.130387},
url = {https://mlanthology.org/colt/1992/chen1992colt-line/}
}