カバー番号

数学において、被覆数とは、ボール同士が重なり合う可能性のある状態で、与えられた空間を完全に覆うために必要な、与えられたサイズのボールの数です。被覆数は集合の大きさを定量化し、一般的な距離空間に適用できます。関連する 2 つの概念は、パッキング数(空間に収まる互いに素なボールの数) と、距離エントロピー(一定の最小距離だけ離れているように制約されたときに空間に収まる点の数) です。

( M , d ) を距離空間、K をMのサブセット、r を正の実数とします。B _r ( x )はxを中心とする半径rの球を表します。 MのサブセットCがKのr 外部被覆である場合、次のようになります。

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

言い換えると、任意の に対してとなるものが存在する。 ${\displaystyle y\in K}$${\displaystyle x\in C}$${\displaystyle d(x,y)\leq r}$

さらにC がKのサブセットである場合、それはr 内部被覆です。

Kの外部被覆数 は、Kの任意の外部被覆の最小濃度です。内部被覆数 は、 任意の内部被覆の最小濃度です。 ${\displaystyle N_{r}^{\text{ext}}(K)}$${\displaystyle N_{r}^{\text{int}}(K)}$

Kの部分集合Pがパッキングであるとは、集合が対ごとに素である場合です。Kのパッキング数はと表記され、 Kのパッキングの最大濃度です。 ${\displaystyle P\subseteq K}$${\displaystyle \{B_{r}(x)\}_{x\in P}}$${\displaystyle N_{r}^{\text{pack}}(K)}$

Kの部分集合Sがr分離しているとは、 S内の各点xとyのペアがd ( x , y ) ≥ r を満たす場合です。Kのメトリックエントロピーは と表記され、 Kのr分離部分集合の最大濃度です。 ${\displaystyle N_{r}^{\text{met}}(K)}$

以下の性質は、標準ユークリッド空間における被覆数に関係する：^{[1] ：338}${\displaystyle \mathbb {R} ^{m}}$

を実数値関数の空間とし、l-無限計量を持つものとする（上の例3を参照）。 内のすべての関数が実定数 で制限されると仮定する。すると、 からの学習関数の一般化誤差を、損失の二乗に対して制限するために被覆数を使うことができる： ^{[2] : 61}${\displaystyle K}$${\displaystyle K}$${\displaystyle M}$${\displaystyle K}$

${\displaystyle \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}}}$

ここで、およびはサンプル数です。 ${\displaystyle r={\epsilon \over 8M}}$${\displaystyle m}$

• ポリゴンカバー
• キスナンバー