Constrained versions of Sauer's lemma

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

Let [n] = {1, ..., n}. For a function h : [n] → {0, 1}, x ∈ [n] and y ∈ {0, 1} define by the widthωh (x, y) of h at x the largest nonnegative integer a such that h (z) = y on x - a ≤ z ≤ x + a. We consider finite VC-dimension classes of functions h constrained to have a width ωh (xi, yi) which is larger than N for all points in a sample ζ = {(xi, yi)}1 or a width no larger than N over the whole domain [n]. Extending Sauer's lemma, a tight upper bound with closed-form estimates is obtained on the cardinality of several such classes.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)2753-2767
عدد الصفحات15
دوريةDiscrete Applied Mathematics
مستوى الصوت156
رقم الإصدار14
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 28 يوليو 2008

بصمة

أدرس بدقة موضوعات البحث “Constrained versions of Sauer's lemma'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا