Numer okładki

Nie należy mylić z numerem uzwojenia lub stopniem ciągłego mapowania , czasami nazywanym „liczbą pokrycia” lub „liczbą obejmującą”.

W matematyce liczba pokrywająca to liczba kulistych kul o danym rozmiarze potrzebnych do całkowitego pokrycia danej przestrzeni, z możliwym nachodzeniem na siebie. Dwie powiązane koncepcje to liczba upakowania , liczba rozłącznych kul, które mieszczą się w przestrzeni, oraz entropia metryczna , liczba punktów, które mieszczą się w przestrzeni, gdy są ograniczone do leżenia w określonej minimalnej odległości od siebie.

Definicja

Niech ( M , d ) będzie przestrzenią metryczną , niech K będzie podzbiorem M i niech r będzie dodatnią liczbą rzeczywistą . Niech B _r ( x ) oznacza kulę o promieniu r o środku w punkcie x . Podzbiór C z M jest r-zewnętrznym pokryciem K , jeśli:

${\ Displaystyle K \ subseteq \ bigcup _ {x \ w C} B_ {r} (x)}$ .

Innymi słowy, dla każdego $d$$x, y)$$\$ że ( .

Jeśli ponadto C jest podzbiorem K , to jest to r-pokrycie wewnętrzne .

Zewnętrzna liczba pokrycia K , $.$ jest pokrycia K Wewnętrzny numer pokrycia $to$ oznaczony dowolnego pokrycia

Podzbiór P z K jest opakowaniem $\in P}}$ jeśli i zbiór ${$$Displaystyle \ {B_ {r} (x) \} _ {$ jest rozłączne parami . Numer opakowania K , $oznaczony$ , K _ _

Podzbiór S z K jest r - rozdzielony , jeśli każda para punktów x i y w S spełnia d ( x , y ) ≥ r . Entropia metryczna K , $_$ , liczebnością K oddzielonego r _

Przykłady

1. Przestrzeń metryczna to linia rzeczywista. ${\ displaystyle \ mathbb {R}}$ . ${\ Displaystyle K \ podzbiór \ mathbb {R}}$ to zbiór liczb rzeczywistych, których wartość bezwzględna wynosi najwyżej ${\ displaystyle k}$ . Następnie istnieje zewnętrzne pokrycie przedziałów długości $\ textstyle \ lewo \ lceil {\ Frac {2k} {r}} \ prawo \ rceil}$$,$ obejmujące przedział ${\ Displaystyle [-k, k]}$ . Stąd:

   ${\ Displaystyle N_ {r} ^ {\ tekst {ext}} (K) \ równoważnik {\ Frac {2k} {r}}}$

2. Przestrzeń metryczna $.$ przestrzeń z metryką euklidesową ${\ Displaystyle K \ podzbiór \ mathbb {R} ^ {m}}$ to zbiór wektorów, których długość (norma) wynosi co najwyżej ${\ displaystyle k}$ . Jeśli leży w d -wymiarowej podprzestrzeni $Displaystyle$$\ mathbb {R} ^ {m}}$ , to:
   $\ Displaystyle N_{r}^{\text{ext}}(K)\leq \left({\frac {2k{\sqrt {d}}}{r}}\right)^{d}}$ .
3. Przestrzeń metryczna to przestrzeń funkcji o wartościach rzeczywistych z metryką l-nieskończoności . Liczba $.$$jest$ najmniejszą ${\ Displaystyle h_ {1}, \ ldots, h_ {k} \ w K}$ że takie, że dla wszystkich istnieje ${\ Displaystyle h \ w K}$$k \}}$${\ displaystyle i \$$r {$$displaystyle r$ tak, że najwyższa odległość między i wynosi $co$ najwyżej . Powyższe ograniczenie nie ma znaczenia $,$ ponieważ przestrzeń jest . Jednakże, gdy jest $zbiorem$ zwartym , każde jego pokrycie ma skończone pokrycie podrzędne, więc $}$${\ Displaystyle N_ {r} ^ {\ tekst {int}} (K$ jest skończony.

Nieruchomości

1. Wewnętrzne i zewnętrzne numery pokrycia, numer opakowania i entropia metryczna są ze sobą ściśle powiązane. Poniższy łańcuch nierówności zachodzi dla dowolnego podzbioru K przestrzeni metrycznej i dowolnej dodatniej liczby rzeczywistej r .

   ${\ Displaystyle N_ {2r} ^ {\ tekst {met}} (K)\równoważnik N_{r}^{\text{pack}}(K)\równoważnik N_{r}^{\text{ext}}(K)\równoważnik N_{r}^{\text{int} }(K)\leq N_{r}^{\text{met}}(K)}$

2. Każda funkcja z wyjątkiem wewnętrznej liczby pokrywającej jest nierosnąca w r i niemalejąca w K . Wewnętrzna liczba pokrywająca jest monotonna w r , ale niekoniecznie w K.

Następujące właściwości odnoszą się do liczb pokrywających w standardowej przestrzeni euklidesowej : ${\ displaystyle \ mathbb {R} ^ {m}}$ :

3. Jeśli wszystkie wektory w $są$$nie$ wektor stały to liczba pokrywająca się
4. Jeśli wszystkie wektory w $r$$}$ skalar , to:

   dla wszystkich : $\ displaystyle$${\ Displaystyle N_ {| k | \ cdot r} ^ {\ tekst {ext}} (k \ cdot K) = N_ {r} ^ {\ tekst {ext}}(K)}$

5. Jeśli wszystkie wektory w $}$$dla$ przez $stałą$ Lipschitza ze Lipschitza , to:
   wszystkich ${\ displaystyle r$ : ${\ Displaystyle N _ {| k | \ cdot r} ^ {\ tekst {ext}} (\ phi \ circ K) \ równoważnik N_ {r} ^ { \text{ext}}(K)}$

Zastosowanie do uczenia maszynowego

Niech $będzie$ przestrzenią funkcji o wartościach rzeczywistych z metryką l-nieskończoności patrz przykład 3 powyżej). Załóżmy $,$$stałą$ wszystkie funkcje w ograniczone rzeczywistą . Następnie można użyć liczby pokrywającej do ograniczenia błędu uogólnienia funkcji uczenia się w stosunku do kwadratu straty: ${\ displaystyle K}$

${\ Displaystyle \ OperatorName {Prób} \ lewo [\ sup _ {h \ in K} {\ duży \ vert } {\ tekst { GeneralizationError}}(h)-{\text{EmpiricalError}}(h){\big \vert }\geq \epsilon \right]\leq N_{r}^{\text{int}}(K)\,2 \exp {-m\epsilon ^{2} \ponad 2M^{4}}}$

gdzie ${\ displaystyle r = {\ epsilon \ ponad 8M}}$$i$ jest próbek.

Zobacz też

• Pokrycie wieloboku
• Całowanie numeru