Número de cubierta

En matemáticas, un número de cobertura es el número de bolas de un tamaño determinado que se necesita para cubrir por completo un espacio determinado, con posibles superposiciones entre las bolas. El número de cobertura cuantifica el tamaño de un conjunto y se puede aplicar a espacios métricos generales . Dos conceptos relacionados son el número de empaquetamiento , el número de bolas disjuntas que caben en un espacio, y la entropía métrica , el número de puntos que caben en un espacio cuando se limita a estar separados por una distancia mínima fija.

Definición

Sea ( M , d ) un espacio métrico , sea K un subconjunto de M y sea r un número real positivo . Sea B _r ( x ) la esfera de radio r centrada en x . Un subconjunto C de M es una cobertura r-externa de K si:

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

En otras palabras, para cada existe tal que . ${\displaystyle y\in K}$ ${\displaystyle x\in C}$ ${\displaystyle d(x,y)\leq r}$

Si además C es un subconjunto de K , entonces es una cubierta r-interna .

El número de cobertura externa de K , denotado , es la cardinalidad mínima de cualquier cobertura externa de K. El número de cobertura interna , denotado , es la cardinalidad mínima de cualquier cobertura interna. ${\displaystyle N_{r}^{\text{ext}}(K)}$ ${\displaystyle N_{r}^{\text{int}}(K)}$

Un subconjunto P de K es un empaquetamiento si y el conjunto es disjunto por pares . El número de empaquetamiento de K , denotado , es la cardinalidad máxima de cualquier empaquetamiento de K. ${\displaystyle P\subseteq K}$ ${\displaystyle \{B_{r}(x)\}_{x\in P}}$ ${\displaystyle N_{r}^{\text{pack}}(K)}$

Un subconjunto S de K está r - separado si cada par de puntos x e y en S satisface d ( x , y ) ≥ r . La entropía métrica de K , denotada , es la cardinalidad máxima de cualquier subconjunto r -separado de K . ${\displaystyle N_{r}^{\text{met}}(K)}$

Ejemplos

1. El espacio métrico es la recta real . es un conjunto de números reales cuyo valor absoluto es como máximo . Entonces, existe un recubrimiento externo de intervalos de longitud , que cubre el intervalo . Por lo tanto: ${\displaystyle \mathbb {R} }$ ${\displaystyle K\subset \mathbb {R} }$ ${\displaystyle k}$ ${\textstyle \left\lceil {\frac {2k}{r}}\right\rceil }$ ${\displaystyle r}$ ${\displaystyle [-k,k]}$

   ${\displaystyle N_{r}^{\text{ext}}(K)\leq {\frac {2k}{r}}}$

2. El espacio métrico es el espacio euclidiano con métrica euclidiana . es un conjunto de vectores cuya longitud (norma) es como máximo . Si se encuentra en un subespacio d -dimensional de , entonces: ^{[1] : 337} ${\displaystyle \mathbb {R} ^{m}}$ ${\displaystyle K\subset \mathbb {R} ^{m}}$ ${\displaystyle k}$ ${\displaystyle K}$ ${\displaystyle \mathbb {R} ^{m}}$
   ${\displaystyle N_{r}^{\text{ext}}(K)\leq \left({\frac {2k{\sqrt {d}}}{r}}\right)^{d}}$.
3. El espacio métrico es el espacio de funciones de valores reales, con métrica l-infinita . El número de recubrimiento es el número más pequeño tal que, existen tales que, para todo existen tales que la distancia suprema entre y es como máximo . La cota anterior no es relevante ya que el espacio es -dimensional. Sin embargo, cuando es un conjunto compacto , cada recubrimiento de él tiene un subrecubrimiento finito, por lo que es finito. ^{[2] : 61} ${\displaystyle N_{r}^{\text{int}}(K)}$ ${\displaystyle k}$ ${\displaystyle h_{1},\ldots ,h_{k}\in K}$ ${\displaystyle h\in K}$ ${\displaystyle i\in \{1,\ldots ,k\}}$ ${\displaystyle h}$ ${\displaystyle h_{i}}$ ${\displaystyle r}$ ${\displaystyle \infty }$ ${\displaystyle K}$ ${\displaystyle N_{r}^{\text{int}}(K)}$

Propiedades

1. Los números de recubrimiento interno y externo, el número de empaquetamiento y la entropía métrica están estrechamente relacionados. La siguiente cadena de desigualdades se cumple para cualquier subconjunto K de un espacio métrico y cualquier número real positivo r . ^[3]

   ${\displaystyle 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. Cada función, excepto el número de cobertura interno , no es creciente en r ni decreciente en K. El número de cobertura interno es monótono en r pero no necesariamente en K.

Las siguientes propiedades se relacionan con los números de cobertura en el espacio euclidiano estándar : [ 1 ^{] : 338} ${\displaystyle \mathbb {R} ^{m}}$

3. Si todos los vectores en son traducidos por un vector constante , entonces el número de cobertura no cambia. ${\displaystyle K}$ ${\displaystyle k_{0}\in \mathbb {R} ^{m}}$
4. Si todos los vectores en se multiplican por un escalar , entonces: ${\displaystyle K}$ ${\displaystyle k\in \mathbb {R} }$

   Para todos : ${\displaystyle r}$ ${\displaystyle N_{|k|\cdot r}^{\text{ext}}(k\cdot K)=N_{r}^{\text{ext}}(K)}$

5. Si todos los vectores en son operados por una función de Lipschitz con constante de Lipschitz , entonces: ${\displaystyle K}$ ${\displaystyle \phi }$ ${\displaystyle k}$
   Para todos : ${\displaystyle r}$ ${\displaystyle N_{|k|\cdot r}^{\text{ext}}(\phi \circ K)\leq N_{r}^{\text{ext}}(K)}$

Aplicación al aprendizaje automático

Sea un espacio de funciones de valor real, con métrica l-infinita (ver ejemplo 3 anterior). Supongamos que todas las funciones en están limitadas por una constante real . Entonces, el número de cobertura se puede utilizar para limitar el error de generalización de las funciones de aprendizaje de , en relación con la pérdida al cuadrado: ^{[2] : 61} ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle M}$ ${\displaystyle K}$

${\displaystyle \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}}}$

donde y es el número de muestras. ${\displaystyle r={\epsilon \over 8M}}$ ${\displaystyle m}$

Véase también

• Cobertura poligonal
• Número de beso

Referencias

1. Shalev-Shwartz, Shai; Ben-David, Shai (2014). Comprensión del aprendizaje automático: de la teoría a los algoritmos . Cambridge University Press. ISBN 9781107057135.
2. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Fundamentos del aprendizaje automático . Estados Unidos, Massachusetts: MIT Press. ISBN 9780262018258.
3. Tao, Terence. "Análogos de entropía métrica de la teoría de conjuntos sumatorios" . Consultado el 2 de junio de 2014 .