On the complexity of binary samples

Abstract

Consider a class $\mathcal{H}$ of binary functions h: X→{ − 1, + 1} on an interval $X=[0, B]\subset \mbox{\rm IR}$. Define the sample width of h on a finite subset (a sample) S ⊂ X as ω _S (h) =  min _x ∈ S |ω _h (x)| where ω _h (x) = h(x) max {a ≥ 0: h(z) = h(x), x − a ≤ z ≤ x + a}. Let $\mathbb{S}_\ell$ be the space of all samples in X of cardinality ℓ and consider sets of wide samples, i.e., hypersets which are defined as $A_{\beta, h} = \{S\in \mathbb{S}_\ell: \omega_{S}(h) \geq \beta\}.$ Through an application of the Sauer-Shelah result on the density of sets an upper estimate is obtained on the growth function (or trace) of the class $\{A_{\beta, h}: h\in\mathcal{H}\}$, β > 0, i.e., on the number of possible dichotomies obtained by intersecting all hypersets with a fixed collection of samples $S\in\mathbb{S}_\ell$ of cardinality m. The estimate is $2\sum_{i=0}^{2\lfloor B/(2\beta)\rfloor}{m-\ell\choose i}$.