On the complexity of binary samples

Abstract: Consider a class

m H

of binary functions

h : X o - 1, + 1

on a finite interval

X = [0, B] s u b s e t R e a l

. Define the {em sample width} of

h

on a finite subset (a sample)

S s u b s e t X

as

w_{S} (h) e q u i v m i n_{x i n S} | w_{h} (x) |

, where

w_{h} (x) = h (x) m a x a g e q 0 : h (z) = h (x), x - a l e q z l e q x + a

. Let

m a t h b b S_{e} l l

be the space of all samples in

X

of cardinality

e l l

and consider sets of wide samples, i.e., {em hypersets} which are defined as

. 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

,

, i.e., on the number of possible dichotomies obtained by intersecting all hypersets with a fixed collection of samples

S i n m a t h b b S_{e} l l

of cardinality

m

. The estimate is

.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: On the complexity of binary samples

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1029587)