On the complexity of binary samples

DOI10.1007/S10472-008-9096-3zbMATH Open1171.68016arXiv0801.4794OpenAlexW2132883151MaRDI QIDQ1029587FDOQ1029587

Publication date: 13 July 2009

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

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

.

Full work available at URL: https://arxiv.org/abs/0801.4794

Recommendations

zbMATH Keywords

learning VC-dimension binary functions density of sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Combinatorics in computer science (68R05)

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)