はじめに
Covering Numbers（被覆数）は、ある空間を指定した半径$\varepsilon$の球体で覆うときに必要な最小の球の個数$N(\varepsilon)$を表す概念です。Covering Numbersは特に、空間の複雑さやサイズを測定する際に非常に役立ち、機械学習において、汎化誤差の解析や関数空間の複雑性を定量化する際に重要です。
空間と距離
Covering Numberは、空間内の点同士の距離を定義する距離関数に依存します。この距離が空間の幾何学的な性質を決定します。
球体の定義
距離空間における球体とは、ある中心点を基準にして、半径$\varepsilon$以内に含まれる点の集合を指します。空間を覆う指定した半径$\varepsilon$の球体を用いて空間全体を覆おうとします。このとき、空間を完全に覆うのに必要な最小限の球体の数が Covering Numbers $N(\varepsilon)$です。
半径と球の数の関係
半径 $\varepsilon$ を小さくすると、空間全体を覆うために必要な球の数は増加します。この関係を解析することで、空間の複雑さや次元性を把握することができます。
Covering Numbersの証明