Covering number
In mathematics, a covering number is the number of balls of a given size needed to completely cover a given space, with possible overlaps between the balls. The covering number quantifies the size of a set and can be applied to general metric spaces. Two related concepts are the packing number, the number of disjoint balls that fit in a space, and the metric entropy, the number of points that fit in a space when constrained to lie at some fixed minimum distance apart.
Definition
Let be a metric space, let K be a subset of M, and let r be a positive real number. Let Br denote the closed Ball (mathematics)#In [general metric spaces|ball] of radius r centered at x. A subset C of M is an r-external covering of K if:In other words, for every there exists such that.
If furthermore C is a subset of K, then it is an r-internal covering.
The external covering number of K, denoted, is the minimum cardinality of any external covering of K. The internal covering number, denoted, is the minimum cardinality of any internal covering.
A subset P of K is a packing if and the set is pairwise disjoint. The packing number of K, denoted, is the maximum cardinality of any packing of K.
A subset S of K is r-''separated if each pair of points x'' and y in S satisfies d ≥ r. The metric entropy of K, denoted, is the maximum cardinality of any r-separated subset of K.
Properties
The following properties relate to covering numbers in the standard Euclidean space, :Application to machine learning
Let be a space of real-valued functions, with the ℓ-infinity metric.Suppose all functions in are bounded by a real constant.
Then, the covering number can be used to bound the generalization error
of learning functions from,
relative to the squared loss:
where and is the number of samples.