Покрывающий номер

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

Определение [ править ]

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

{\ Displaystyle К \ substeq \ чашка _ {х \ in C} B_ {r} (x)}

.

Другими словами, для каждого существует такое, что . ${\ displaystyle y \ in K}$ ${\ displaystyle x \ in C}$ ${\ Displaystyle д (х, у) \ leq г}$

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

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

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

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

Примеры [ править ]

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

N_{r}^{\text{ext}}(K)\leq (2k/r)

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

N_{r}^{\text{ext}}(K)\leq (2k{\sqrt {d}}/r)^{d}

.

3. Метрическое пространство - это пространство вещественнозначных функций с l-бесконечной метрикой. Число покрытия - это наименьшее число, такое, что существует такое, что для всех существует такое, что супремум расстояние между и не больше . Приведенная выше оценка не имеет значения, поскольку пространство -мерно. Однако, когда является компактным множеством , каждое его покрытие имеет конечное подпокрытие, поэтому оно конечно. ^[2]^:⁶¹ $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)$

Свойства [ править ]

1. Числа внутреннего и внешнего покрытия, номер упаковки и метрическая энтропия тесно связаны. Следующая цепочка неравенств верна для любого подмножества 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)

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

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

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

4. Если все векторы в умножены на скаляр , то: $K$ $k\in \mathbb {R}$

для всех :

r

N_{|k|\cdot r}^{\text{ext}}(k\cdot K)=N_{r}^{\text{ext}}(K)

5. Если все векторы в управляются липшицевой функцией с константой Липшица , то: $K$ $\phi$ $k$

для всех :

r

N_{|k|\cdot r}^{\text{ext}}(\phi \circ K)\leq N_{r}^{\text{ext}}(K)

Применение к машинному обучению [ править ]

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

\mathrm {Prob} {\big [}\sup _{h\in K}|{\text{GeneralizationError}}(h)-{\text{EmpiricalError}}(h)|\geq \epsilon {\big ]}\leq N_{r}^{\text{int}}(K)\cdot 2\exp {-m\epsilon ^{2} \over 2M^{4}}

где и - количество отсчетов.

r={\epsilon \over 8M}

m

См. Также [ править ]

Ссылки [ править ]

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

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

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

[3] Тао, Терренс. «Метрические энтропийные аналоги теории множеств сумм» . Проверено 2 июня 2014 . CS1 maint: discouraged parameter (link)

[1]