Learning unions of high-dimensional boxes over the reals

Citation
A. Beimel et E. Kushilevitz, Learning unions of high-dimensional boxes over the reals, INF PROCESS, 73(5-6), 2000, pp. 213-220
Citations number
21
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
73
Issue
5-6
Year of publication
2000
Pages
213 - 220
Database
ISI
SICI code
0020-0190(20000331)73:5-6<213:LUOHBO>2.0.ZU;2-5
Abstract
Beimel and Kushilevitz (1997) presented an algorithm that exactly learns (u sing membership queries and equivalence queries) several classes of unions of boxes in high dimension over finite discrete domains. The running time o f the algorithm is polynomial in the logarithm of the size of the domain an d other parameters of the target function (in particular, the dimension). W e go one step further and present a PAC + MQ algorithm whose running time i s independent of the size of the domain. Thus, we can learn such classes of boxes over infinite domains. Specifically, we learn unions of t disjoint n -dimensional boxes over the reals in time polynomial in n and t, and unions of O(log n) (possibly intersecting) n-dimensional boxes over the reals in time polynomial in n. (C) 2000 Published by Elsevier Science B.V. All right s reserved.