# カバリングナンバー Navigation: [[index]] | [[_index|concepts]] ## 定義 $\varepsilon$-被覆とは、集合 $A$ に対して有限点集合 $\{x_1, \ldots, x_N\}$ であって、各点を中心とする半径 $\varepsilon$ の開球の和集合が $A$ を覆うもの(すなわち $A \subset \bigcup_{i=1}^N B(x_i, \varepsilon)$)である。 カバリングナンバー $N(\varepsilon, A)$ とは、集合 $A$ の $\varepsilon$-被覆の最小の要素数である: $N(\varepsilon, A) = \min\{N \in \mathbb{N} \mid A \subset \bigcup_{i=1}^N B(x_i, \varepsilon)\}$ 直感的には「$A$ 内のどの点も距離 $\varepsilon$ 以内に代表点が存在するような最小の代表点集合の大きさ」である。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 機械学習理論での役割 無限の仮説クラス(連続パラメータ空間)に汎化誤差バウンドを拡張するための橋渡し手法として用いられる。手順: 1. パラメータ空間 $\mathcal{H}$ の $\varepsilon$-被覆(有限の代表点集合 $\mathcal{C}$)を構成する 2. 有限の代表点に対してユニオンバウンドと集中不等式を適用して一様収束を保証する 3. 損失の $L$-リプシッツ連続性を使い、任意の $\theta \in \mathcal{H}$ と最近傍の代表点 $\hat{\theta} \in \mathcal{C}$ の間の損失差 $|\hat{R}_n(\theta) - \hat{R}_n(\hat{\theta})| \le L\varepsilon$ を抑える 4. 三角不等式で全体の汎化誤差を上界する (Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## $d$ 次元球・立方体のカバリングナンバー $\ell_2$ ノルム球 $\mathcal{H} = \{\theta \in \mathbb{R}^d : \|\theta\| \le R\}$ は $d$ 次元立方体 $\mathcal{H}' = \{\theta : |\theta_i| \le R\}$ に含まれる。立方体を一辺 $2\varepsilon/\sqrt{d}$ の小立方体に分割すると: $N(\mathcal{H}; \varepsilon) \le N(\mathcal{H}'; \varepsilon) \le \left\lceil\frac{\sqrt{d}\,R}{\varepsilon}\right\rceil^d$ $\varepsilon = \frac{1}{4nL}$ を代入すると $N(\mathcal{H}; \frac{1}{4nL}) \le \lceil4\sqrt{d}\,RnL\rceil^d$ が得られ、カバリングナンバーが $n, d, R, L$ の多項式(の指数)で抑えられる。 このカバリングナンバーの対数が汎化誤差バウンドの次元依存項 $d\log(\cdot)$ として現れる。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## $L$-リプシッツ連続性との組み合わせ 損失 $\ell(X;\cdot)$ が $L$-リプシッツ連続であれば、代表点 $\hat{\theta}$ と真のパラメータ $\Theta^*$ の間の損失差を: $|\ell(X;\Theta^*) - \ell(X;\hat{\Theta}^*)| \le L\|\Theta^* - \hat{\Theta}^*\| \le L\varepsilon$ と抑えられる。これにより代表点への集中から任意の点への集中へと「橋渡し」できる。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 他の複雑度指標との関係 - **VC 次元**: 分類問題に特化した複雑度指標。2値損失クラスに対する一様収束を VC 次元で特徴付ける。 - **Rademacher 複雑度**: データに依存した複雑度指標。VC 次元より細かい解析が可能。 - **エントロピー数**: カバリングナンバーの対数 $\log N(\varepsilon, A)$。距離空間の複雑度を特徴付ける。 カバリングナンバーはこれらと密接に関連し、互いに変換可能なバウンドを与えることが多い。 ## 横断的知見 - カバリングナンバーを用いたバウンドは、高次元($d$ が大きい)になると指数的に大きくなるカバリングナンバーが問題になる。これが「次元の呪い」の一側面であり、深層学習の過パラメータ化(巨大な $d$)で古典的バウンドが崩壊する根拠でもある。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 未解決の問い - 深層ニューラルネットワークに対して、有効なカバリングナンバーのバウンドをパラメータ数 $d$ に依存しない形で得られる構造はあるか。 - 損失地形の「盆地」構造を使えば、実効的なカバリングナンバーを定数(盆地の個数 $K$)にまで削減できるか。 ## 関連 - [[汎化誤差バウンド]] — カバリングナンバーが登場する文脈 - [[集中不等式]] — ユニオンバウンドと組み合わせる道具 - [[PAC学習]] — 仮説クラスの複雑度を定量化する枠組み - [[深層学習の汎化]] — カバリングナンバーが破綻する状況とその対応 ## 出典 - [[@2025__joisino__絶対に分かる機械学習理論]] — 佐藤竜馬、2025-03-17