Номер покрытия

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

Определение

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

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

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

Примеры

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

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

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

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

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

Применение в машинном обучении

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

\operatorname {Prob} \left[\sup _{h\in K}{\big \vert }{\text{ОшибкаОбобщения}}(h)-{\text{ЭмпирическаяОшибка}}(h){\big \vert }\geq \epsilon \right]\leq N_{r}^{\text{int}}(K)\,2\exp {-m\epsilon ^{2} \over 2M^{4}}

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

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

Ссылки

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

[book14-1] Шалев-Шварц, Шай; Бен-Дэвид, Шай (2014). Понимание машинного обучения – от теории к алгоритмам . Cambridge University Press. ISBN 9781107057135.

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

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