Compression Schemes, Stable Definable Families, and o-Minimal Structures

被引：9

作者：

Johnson, H. R. ^{[1
]}

Laskowski, M. C. ^{[2
]}

机构：

[1] CUNY, Dept Math & CS, John Jay Coll, New York, NY 10021 USA

[2] Univ Maryland, Dept Math, College Pk, MD 20742 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2010年 / 43卷 / 04期

关键词：

Compression scheme; VC dimension; NIP; Independence dimension; Dependence; Warmuth conjecture; Stable; o-minimal; Type definition; Definable type; Density; Combinatorial complexity; UFTD; UDTFS; SAMPLE COMPRESSION; DIMENSION;

D O I：

10.1007/s00454-009-9201-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that any family of sets uniformly definable in an o-minimal structure has an extended compression scheme of size equal to the number of parameters in the defining formula. As a consequence, the combinatorial complexity (or density) of any definable family in a structure with a o-minimal theory is bounded by the number of parameters in the defining formula. Extended compression schemes for uniformly definable families corresponding to stable formulas are also shown to exist.

引用

页码：914 / 926

页数：13

共 18 条

[1] [Anonymous], J MACHINE LEARNING R
[2] [Anonymous], 1996, Notices Amer. Math. Soc
[3] [Anonymous], 1998, Tame topology and ominimal structures, DOI DOI 10.1017/CBO9780511525919
[4] [Anonymous], 1999, Cambridge Studies in Advanced Mathematics
[5] DENSITY AND DIMENSION
ASSOUAD, P
[J]. ANNALES DE L INSTITUT FOURIER, 1983, 33 (03) : 233 - 282
[6] Combinatorial Complexity in O-minimal Geometry
Basu, Saugata
[J]. STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, : 47 - 56
[7] Combinatorial variability of Vapnik-Chenvonenkis classes with applications to sample compression schemes
Ben-David, S
Litman, A
[J]. DISCRETE APPLIED MATHEMATICS, 1998, 86 (01) : 3 - 25
[8] Floyd S, 1995, MACH LEARN, V21, P269
[9] GABRIELOV AM, 1968, FUNCTIONAL ANAL APPL, V2, P282
[10] EPSILON-NETS AND SIMPLEX RANGE QUERIES
HAUSSLER, D
WELZL, E
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (02) : 127 - 151

← 1 2 →