On the Complexity of Binary Samples

Abstract

Consider a class $\mH$ of binary functions $h:X\to \{-1,+1\}$ on a finite interval $X=[0, B]\subset \Real$. Define the {\em sample width} of $h$ on a finite subset (a sample) $S\subset X$ as $\w_S(h) \equiv \min_{x\in S} |\w_h(x)|$, where $\w_h(x) = h(x) \max\{a\geq 0: h(z)=h(x), x-a\leq z\leq x+a\}$. Let ${\mathbb{S}}_{\ell }$ be the space of all samples in $X$ of cardinality $\ell$ and consider sets of wide samples, i.e., {\em hypersets} which are defined as $A_{β, h} = \{S\in \mathbb{S}_\ell: \w_{S}(h) \geq β\}$. 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}: h\in\mH\}$, $\beta >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 }\left(\genfrac{}{}{0ex}{}{m-\ell }{i}\right)$.