Approximating hyper-rectangles: Learning and pseudorandom sets

被引：28

作者：

Auer, P

Long, PM

Srinivasan, A

机构：

[1] Graz Univ Technol, Inst Theoret Comp Sci, A-8010 Graz, Austria

[2] Natl Univ Singapore, Dept Informat Syst & Comp Sci, Singapore 119260, Singapore

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1998年 / 57卷 / 03期

关键词：

rectangles; machine learning; PAC learning; derandomization; pseudorandomness; multiple-instance learning; explicit constructions; Ramsey graphs; random graphs; sample complexity; approximations of distributions;

D O I：

10.1006/jcss.1998.1593

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for several applied learning problems. Also, pseudorandom sets for rectangles have been actively studied recently because (i) they are a subproblem common to the derandomization of depth-2 (DNF) circuits and derandomizing randomized logspace, and (ii) they approximate the distribution of n independent multivalued random variables. We present improved upper bounds for a class of such problems of "approximating" high-dimensional rectangles that arise in PAC learning and pseudorandomness. (C) 1998 Academic Press.

引用

页码：376 / 388

页数：13

共 39 条

[1] NOTE ON RAMSEYS THEOREM [J].