Покрытие номер

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

Определение

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

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

.

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

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

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

Подмножество P множества K является упаковкой , если $P\subseteq K$ и набор $\{B_{r}(x)\}_{x\in P}$ попарно не пересекается . Номер упаковки K , обозначаемый $N_{r}^{\text{pack}}(K)$ , — максимальная мощность любой упаковки K .

Подмножество S множества K является r - разделенным , если каждая пара точек x и y в S удовлетворяет условию d ( x , y ) ≥ r . Метрическая энтропия K , обозначаемая $N_{r}^{\text{met}}(K)$ , — максимальная мощность любого r -разделенного подмножества K .

Примеры

Метрическое пространство — это действительная линия $\mathbb {R}$ . $K\subset \mathbb {R}$ представляет собой набор действительных чисел, абсолютное значение которых не превышает $k$ . Затем происходит внешнее покрытие ${\textstyle \left\lceil {\frac {2k}{r}}\right\rceil }$ интервалы длины $r$ , охватывающий интервал $[-k,k]$ . Следовательно:
$N_{r}^{\text{ext}}(K)\leq {\frac {2k}{r}}$
Метрическое пространство — это евклидово пространство. $\mathbb {R} ^{m}$ с евклидовой метрикой . $K\subset \mathbb {R} ^{m}$ представляет собой набор векторов, длина (норма) которых не превосходит $k$ . Если $K$ лежит в d -мерном подпространстве $\mathbb {R} ^{m}$ , затем: ^[1]^: 337
$N_{r}^{\text{ext}}(K)\leq \left({\frac {2k{\sqrt {d}}}{r}}\right)^{d}$ .
Метрическое пространство — это пространство вещественных функций с метрикой l-бесконечности . Покрывающий номер $N_{r}^{\text{int}}(K)$ это наименьшее число $k$ такие, что существуют $h_{1},\ldots ,h_{k}\in K$ такой, что для всех $h\in K$ существует $i\in \{1,\ldots ,k\}$ такое, что максимальное расстояние между $h$ и $h_{i}$ самое большее $r$ . Приведенная выше оценка не имеет значения, поскольку пространство $\infty$ -мерный. Однако, когда $K$ — компакт , каждое его покрытие имеет конечное подпокрытие, поэтому $N_{r}^{\text{int}}(K)$ конечно. ^[2]^: 61

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

Числа внутреннего и внешнего покрытия, число упаковки и метрическая энтропия тесно связаны между собой. Следующая цепочка неравенств справедлива для любого подмножества K метрического пространства и любого положительного действительного числа r . ^[3]
$N_{2r}^{\text{met}}(K)\leq N_{r}^{\text{pack}}(K)\leq N_{r}^{\text{ext}}(K)\leq N_{r}^{\text{int}}(K)\leq N_{r}^{\text{met}}(K)$
кроме внутреннего накрывающего числа, не возрастает по r и не убывает по K. Каждая функция , Внутреннее накрывающее число монотонно по r но не обязательно по K. ,

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

Если все векторы в $K$ переводятся постоянным вектором $k_{0}\in \mathbb {R} ^{m}$ , то число покрытия не изменится.
Если все векторы в $K$ умножаются на скаляр $k\in \mathbb {R}$ , затем:
для всех $r$ : $N_{|k|\cdot r}^{\text{ext}}(k\cdot K)=N_{r}^{\text{ext}}(K)$
Если все векторы в $K$ управляются функцией Липшица $\phi$ с постоянной Липшица $k$ , затем:
для всех $r$ : $N_{|k|\cdot r}^{\text{ext}}(\phi \circ K)\leq N_{r}^{\text{ext}}(K)$

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

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

\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}}

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

См. также

Ссылки

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

[book14-1] Перейти обратно: ^а ^б Шалев-Шварц, Шай; Бен-Давид, Шай (2014). Понимание машинного обучения – от теории к алгоритмам . Издательство Кембриджского университета. ISBN 9781107057135 .

[book12-2] Перейти обратно: ^а ^б Мори, Мехриар ; Ростамизаде, Афшин; Талвалкар, Амит (2012). Основы машинного обучения . США, Массачусетс: MIT Press. ISBN 9780262018258 .

[3] Тао, Теренс. «Метрические энтропийные аналоги теории множеств» . Проверено 2 июня 2014 г.

[1]

[2]

[3]