Movatterモバイル変換

Covering number

العربية

From Wikipedia, the free encyclopedia

Not to be confused withWinding number ordegree of a continuous mapping, sometimes called "covering number" or "engulfing number".

Inmathematics, acovering number is the number ofballs 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 generalmetric spaces. Two related concepts are thepacking number, the number of disjoint balls that fit in a space, and themetric entropy, the number of points that fit in a space when constrained to lie at some fixed minimum distance apart.

Definition

[edit]

Let (M,d) be ametric space, letK be a subset ofM, and letr be a positivereal number. LetB_r(x) denote the closedball of radiusr centered atx. A subsetC ofM is anr-external covering ofK if:

K\subseteq \bigcup _{x\in C}B_{r}(x)

In other words, for every $y\in K$ there exists $x\in C$ such that $d(x,y)\leq r$ .

If furthermoreC is a subset ofK, then it is anr-internal covering.

Theexternal covering number ofK, denoted $N_{r}^{\text{ext}}(K)$ , is the minimumcardinality of any external covering ofK. Theinternal covering number, denoted $N_{r}^{\text{int}}(K)$ , is the minimum cardinality of any internal covering.

A subsetP ofK is apacking if $P\subseteq K$ and the set $\{B_{r}(x)\}_{x\in P}$ ispairwise disjoint. Thepacking number ofK, denoted $N_{r}^{\text{pack}}(K)$ , is the maximum cardinality of any packing ofK.

A subsetS ofK isr-separated if each pair of pointsx andy inS satisfiesd(x,y) ≥r. Themetric entropy ofK, denoted $N_{r}^{\text{met}}(K)$ , is the maximum cardinality of anyr-separated subset ofK.

Examples

[edit]

The metric space is the real line $\mathbb {R}$ . $K\subset \mathbb {R}$ is a set of real numbers whose absolute value is at most $k {\displaystyle k}$ . Then, there is an external covering of ${\textstyle \left\lceil {\frac {2k}{r}}\right\rceil }$ intervals of length $r {\displaystyle r}$ , covering the interval $[-k,k]$ . Hence:
$N_{r}^{\text{ext}}(K)\leq {\frac {2k}{r}}$
The metric space is theEuclidean space $\mathbb {R} ^{m}$ with theEuclidean metric. $K\subset \mathbb {R} ^{m}$ is a set of vectors whose length (norm) is at most $k {\displaystyle k}$ . If $K {\displaystyle K}$ lies in ad-dimensional subspace of $\mathbb {R} ^{m}$ , then:^[1]^: 337
$N_{r}^{\text{ext}}(K)\leq \left({\frac {2k{\sqrt {d}}}{r}}\right)^{d}$ .
The metric space is the space of real-valued functions, with theℓ-infinity metric. The covering number $N_{r}^{\text{int}}(K)$ is the smallest number $k {\displaystyle k}$ such that there exist $h_{1},\ldots ,h_{k}\in K$ such that, for all $h\in K$ there exists $i\in \{1,\ldots ,k\}$ such that the supremum distance between $h {\displaystyle h}$ and $h_{i}$ is at most $r {\displaystyle r}$ . The above bound is not relevant since the space is $\infty$ -dimensional. However, when $K {\displaystyle K}$ is acompact set, every covering of it has a finite sub-covering, so $N_{r}^{\text{int}}(K)$ is finite.^[2]^: 61

Properties

[edit]

The internal and external covering numbers, the packing number, and the metric entropy are all closely related. The following chain of inequalities holds for any subsetK of a metric space and any positive real numberr.^[3]
$N_{2r}^{\text{met}}(K)\leq N_{r}^{\text{pack}}(K)\leq N_{r}^{\text{ext}}(K)\leq N_{r}^{\text{int}}(K)\leq N_{r}^{\text{met}}(K)$
Each function except the internal covering number is non-increasing inr and non-decreasing inK. The internal covering number is monotone inr but not necessarily inK.

The following properties relate to covering numbers in the standardEuclidean space, $\mathbb {R} ^{m}$ :^[1]^: 338

If all vectors in $K {\displaystyle K}$ are translated by a constant vector $k_{0}\in \mathbb {R} ^{m}$ , then the covering number does not change.
If all vectors in $K {\displaystyle K}$ are multiplied by a scalar $k\in \mathbb {R}$ , then:
for all $r {\displaystyle r}$ : $N_{|k|\cdot r}^{\text{ext}}(k\cdot K)=N_{r}^{\text{ext}}(K)$
If all vectors in $K {\displaystyle K}$ are operated by aLipschitz function $\phi$ withLipschitz constant $k {\displaystyle k}$ , then:
for all $r {\displaystyle r}$ : $N_{|k|\cdot r}^{\text{ext}}(\phi \circ K)\leq N_{r}^{\text{ext}}(K)$

Application to machine learning

[edit]

Let $K {\displaystyle K}$ be a space of real-valued functions, with theℓ-infinity metric (see example 3 above).Suppose all functions in $K {\displaystyle K}$ are bounded by a real constant $M {\displaystyle M}$ .Then, the covering number can be used to bound thegeneralization errorof learning functions from $K {\displaystyle K}$ ,relative to the squared loss:^[2]^: 61

\operatorname {Prob} \left[\sup _{h\in K}{\big \vert }{\text{GeneralizationError}}(h)-{\text{EmpiricalError}}(h){\big \vert }\geq \epsilon \right]\leq N_{r}^{\text{int}}(K)\,2\exp {-m\epsilon ^{2} \over 2M^{4}}

where $r={\epsilon \over 8M}$ and $m {\displaystyle m}$ is the number of samples.

References

[edit]

^^a ^bShalev-Shwartz, Shai; Ben-David, Shai (2014).Understanding Machine Learning – from Theory to Algorithms. Cambridge University Press.ISBN 9781107057135.
^^a ^bMohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2012).Foundations of Machine Learning. US, Massachusetts: MIT Press.ISBN 9780262018258.
^Tao, Terence (20 March 2014)."Metric entropy analogues of sum set theory". Retrieved2 June 2014.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Covering_number&oldid=1314228981"

Categories:

[8]ページ先頭

Movatterモバイル変換

Definition

Examples

Properties

Application to machine learning

See also

References