Номер покрытия - Covering number

Не путать с Номер обмотки или же степень непрерывного отображения, иногда называемое «покрывающим числом» или «охватывающим числом».

В математике номер покрытия это количество сферических мячи заданного размера, необходимого для полного покрытия заданного пространства с возможными перекрытиями. Две взаимосвязанные концепции: номер упаковки, количество непересекающихся шаров, которые умещаются в пространстве, и метрическая энтропия, количество точек, которые помещаются в пространстве, когда они ограничены лежать на некотором фиксированном минимальном расстоянии друг от друга.

Определение

Позволять (M, d) быть метрическое пространство, позволять K быть подмножеством M, и разреши р быть позитивным настоящий номер. Позволять B_р(Икс) обозначают мяч радиуса р сосредоточен на Икс. Подмножество C из M является r-внешнее покрытие из K если:

${displaystyle Ksubseteq cup _{xin C}B_{r}(x)}$.

Другими словами, для каждого ${displaystyle yin K}$ Существует ${displaystyle xin C}$ такой, что ${displaystyle d(x,y)leq r}$.

Если к тому же C это подмножество K, то это r-внутреннее покрытие.

В номер внешнего покрытия из K, обозначенный ${displaystyle N_{r}^{ ext{ext}}(K)}$, - минимальная мощность любого внешнего покрытия K. В внутренний номер покрытия, обозначенный ${displaystyle N_{r}^{ ext{int}}(K)}$, - минимальная мощность любого внутреннего покрытия.

Подмножество п из K это упаковка если ${displaystyle Psubseteq K}$ и набор ${displaystyle {B_{r}(x)}_{xin P}}$ является попарно непересекающиеся. В номер упаковки из K, обозначенный ${displaystyle N_{r}^{ ext{pack}}(K)}$, - максимальная мощность любой упаковки K.

Подмножество S из K является р-отделенный если каждая пара точек Икс и у в S удовлетворяет d(Икс, у) ≥ р. В метрическая энтропия из K, обозначенный ${displaystyle N_{r}^{ ext{met}}(K)}$, - максимальная мощность любого р-отделенное подмножество K.

Примеры

1. Метрическое пространство - это действительная линия. ${displaystyle mathbb {R} }$. ${displaystyle Ksubset mathbb {R} }$ представляет собой набор действительных чисел, абсолютное значение которых не превышает ${displaystyle k}$. Тогда есть внешнее покрытие ${displaystyle lceil 2k/rceil }$ интервалы длины ${displaystyle r}$, покрывающая интервал ${displaystyle [k,-k]}$. Следовательно:

${displaystyle N_{r}^{ ext{ext}}(K)leq (2k/r)}$

2. Метрическое пространство - это Евклидово пространство ${displaystyle mathbb {R} ^{m}}$ с Евклидова метрика.${displaystyle Ksubset mathbb {R} ^{m}}$ набор векторов, длина (норма) которых не превосходит ${displaystyle k}$.Если ${displaystyle K}$ лежит в d-мерное подпространство ${displaystyle mathbb {R} ^{m}}$, тогда:^[1]:337

${displaystyle N_{r}^{ ext{ext}}(K)leq (2k{sqrt {d}}/r)^{d}}$.

3. Метрическое пространство - это пространство вещественнозначных функций с l-бесконечность метрическая. ${displaystyle N_{r}^{ ext{int}}(K)}$это наименьшее число ${displaystyle k}$ такие, что существуют ${displaystyle h_{1},ldots ,h_{k}in K}$такое, что для всех ${displaystyle hin K}$ Существует ${displaystyle iin {1,ldots ,k}}$такое, что супремум расстояние между ${displaystyle h}$ и ${displaystyle h_{i}}$самое большее ${displaystyle r}$Вышеупомянутая оценка не имеет значения, так как пространство ${displaystyle infty }$-размерный. ${displaystyle K}$ это компактный набор, каждое его покрытие имеет конечное подпокрытие, поэтому ${displaystyle N_{r}^{ ext{int}}(K)}$ конечно.^[2]:61

Характеристики

1. Число внутреннего и внешнего покрытия, номер упаковки и метрическая энтропия тесно связаны. Следующая цепочка неравенств верна для любого подмножества K метрического пространства и любое положительное действительное число р.^[3]

${displaystyle N_{2r}^{ ext{met}}(K)leq N_{r}^{ ext{pack}}(K)leq N_{r}^{ ext{ext}}(K)leq N_{r}^{ ext{int}}(K)leq N_{r}^{ ext{met}}(K)}$

2. Все функции, кроме внутреннего покрывающего числа, не увеличиваются в р и не снижается в K. Номер внутреннего покрытия монотонный в р но не обязательно в K.

Следующие свойства относятся к покрывающим числам в стандарте. Евклидово пространство ${displaystyle mathbb {R} ^{m}}$:^[1]:338

3. Если все векторы в ${displaystyle K}$ переводятся на постоянный вектор ${displaystyle k_{0}in mathbb {R} ^{m}}$, то покрывающее число не меняется.

4. Если все векторы в ${displaystyle K}$ умножаются на скаляр ${displaystyle kin mathbb {R} }$, тогда:

для всех ${displaystyle r}$: ${displaystyle N_{|k|cdot r}^{ ext{ext}}(kcdot K)=N_{r}^{ ext{ext}}(K)}$

5. Если все векторы в ${displaystyle K}$ управляются Функция Липшица ${displaystyle phi }$ с Постоянная Липшица ${displaystyle k}$, тогда:

для всех ${displaystyle r}$: ${displaystyle N_{|k|cdot r}^{ ext{ext}}(phi circ K)leq N_{r}^{ ext{ext}}(K)}$

Приложение к машинному обучению

Позволять ${displaystyle K}$ - пространство действительных функций с l-бесконечность метрики (см. пример 3 выше). Предположим, что все функции в ${displaystyle K}$ ограничены действительной постоянной ${displaystyle M}$.Затем покрывающее число можно использовать для привязки ошибка обобщения функций обучения от ${displaystyle K}$относительно квадрата потерь:^[2]:61

${displaystyle mathrm {Prob} {ig [}sup _{hin K}|{ ext{GeneralizationError}}(h)-{ ext{EmpiricalError}}(h)|geq epsilon {ig ]}leq N_{r}^{ ext{int}}(K)cdot 2exp {-mepsilon ^{2} over 2M^{4}}}$

куда ${displaystyle r={epsilon over 8M}}$ и ${displaystyle m}$ количество образцов.

Смотрите также

• Полигональное покрытие
• Целующий номер

Рекомендации

1. Шалев-Шварц, Шай; Бен-Давид, Шай (2014). Понимание машинного обучения - от теории к алгоритмам. Издательство Кембриджского университета. ISBN  9781107057135.
2. Мохри, Мехриар; Ростамизаде, Афшин; Талвалкар, Амит (2012). Основы машинного обучения. США, Массачусетс: MIT Press. ISBN  9780262018258.
3. Тао, Терренс. «Метрические энтропийные аналоги теории множеств сумм». Получено 2 июн 2014.