On the Complexity of Binary Samples

Original · EN

Consider a class of binary functions h: X→{-1, +1} on a finite interval X=[0, B]⊂. Define the sample width of h on a finite subset (a sample) S⊂ X as ₛ(h) ≡ ₓ∈ ₛ |ₕ(x)|, where ₕ(x) = h(x) {a≥ 0: h(z)=h(x), x-a≤ z≤ x+a}. Let Sℓ be the space of all samples in X of cardinality ℓ and consider sets of wide samples, i.e., hypersets which are defined as Aᵦ, ₕ = {S∈ Sℓ: ₛ(h) ≥ β}. 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ᵦ, ₕ: h∈}, β>0, i.e., on the number of possible dichotomies obtained by intersecting all hypersets with a fixed collection of samples Sℓ of cardinality m. The estimate is 2∑ᵢ₌₀2 B/(2β)m-ℓ i.