覆蓋數與度量熵

一個函數類別可以是無限的，但在給定的解析度下，真正實質相異的函數只有有限多個重要。想像擺放半徑 epsilon 的球，使類別中每個函數都落在某球心的 epsilon 範圍內；覆蓋數就是你所需的最少球心數，而它的對數就是度量熵。它是類別有效大小的、隨解析度而變的計數：解析度粗，代表元就少；解析度細，就多。

給定一個度量（常是樣本上的經驗距離），覆蓋數是最小 epsilon-網的基數，其對數即度量熵。它們以兩種方式餵入泛化。簡單的離散化加聯集界給出單一尺度的界；更銳利得多的是 Dudley 熵積分，它把度量熵的平方根對所有尺度積分，以界定 Rademacher 複雜度，捕捉了「多解析度波動會累加」的鏈結（chaining）直覺。覆蓋數也透過 Haussler 界與 VC 維度相連，並對實值類別連到肥打碎（fat-shattering）維度。

度量熵是貫通統計、逼近論與經驗過程論的通用語言；它的成長速率決定估計的極小極大率。若一個類別的對數覆蓋數以 epsilon 的某個負次方成長，便給出可預測的收斂速度，而那個指數往往等於某個平滑度與維度之比。代價在技術面：對深度網路這類豐富類別計算或界定覆蓋數十分精細，常常只知道到常數或對數的程度。