In mathematics, a covering number is the number of spherical

ball A ball is a round object (usually spherical, but can sometimes be ovoid) with several uses. It is used in ball games, where the play of the game follows the state of the ball as it is hit, kicked or thrown by players. Balls can also be used f ...

s of a given size needed to completely cover a given space, with possible overlaps. 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 (''M'', ''d'') be a

metric space In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...

, let ''K'' be a subset of ''M'', and let ''r'' be a positive

real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...

. Let ''B''_''r''(''x'') denote the

of radius ''r'' centered at ''x''. A subset ''C'' of ''M'' is an ''r-external covering'' of ''K'' if: :

K \subseteq \bigcup_ B_r(x)

. In other words, for every

y\in K

there exists

x\in C

such that

d(x,y)\leq r

. If furthermore ''C'' is a subset of ''K'', then it is an ''r-internal covering''. The external covering number of ''K'', denoted

N^_r(K)

, is the minimum cardinality of any external covering of ''K''. The internal covering number, denoted

N^_r(K)

, is the minimum cardinality of any internal covering. A subset ''P'' of ''K'' is a ''packing'' if

P \subseteq K

and the set

\_

is pairwise disjoint. The packing number of ''K'', denoted

N^_r(K)

, 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''(''x'', ''y'') ≥ ''r''. The metric entropy of ''K'', denoted

N^_r(K)

, is the maximum cardinality of any ''r''-separated subset of ''K''.

Examples

Properties

The following properties relate to covering numbers in the standard

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...

\mathbb^m

Application to machine learning

Let

K

be a space of real-valued functions, with the

l-infinity In mathematics, \ell^\infty, the (real or complex) vector space of bounded sequences with the supremum norm, and L^\infty = L^\infty(X,\Sigma,\mu), the vector space of essentially bounded measurable functions with the essential supremum norm, are ...

metric (see example 3 above). Suppose all functions in

K

are bounded by a real constant

M

. Then, the covering number can be used to bound the

generalization error For supervised learning applications in machine learning and statistical learning theory, generalization error (also known as the out-of-sample error or the risk) is a measure of how accurately an algorithm is able to predict outcome values for pre ...

of learning functions from

K

, relative to the squared loss: :

\leq N^\text_r (K)\, 2\exp

where

r =

and

m

is the number of samples.

References

{{reflist Topology Metric geometry

Definition

Examples

Properties

Application to machine learning

See also

References