Cubriendo el número

En matemáticas, un número de cobertura es el número de bolas esféricas de un tamaño dado necesarias para cubrir por completo un espacio determinado, con posibles superposiciones. 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 están obligados 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 bola de radio r centrada en x . Un subconjunto C de M es una cobertura externa r de K si:

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

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

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

El número de recubrimiento externo de K , denotado${\displaystyle N_{r}^{\text{ext}}(K)}$, Es la cardinalidad mínima de cualquier cubierta externa de K . El número de revestimiento interno , indicado${\displaystyle N_{r}^{\text{int}}(K)}$, es la cardinalidad mínima de cualquier revestimiento interno.

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

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

Ejemplos

1. El espacio métrico es la línea real ${\displaystyle \mathbb {R} }$. ${\displaystyle K\subset \mathbb {R} }$ es un conjunto de números reales cuyo valor absoluto es como máximo ${\displaystyle k}$. Luego, hay una cubierta externa de${\displaystyle \lceil 2k/r\rceil }$ intervalos de longitud ${\displaystyle r}$, cubriendo el intervalo ${\displaystyle [k,-k]}$. Por eso:

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

2. El espacio métrico es el espacio euclidiano. ${\displaystyle \mathbb {R} ^{m}}$con la métrica euclidiana .${\displaystyle K\subset \mathbb {R} ^{m}}$ es un conjunto de vectores cuya longitud (norma) es como máximo ${\displaystyle k}$. Si${\displaystyle K}$se encuentra en un subespacio d- dimensional de${\displaystyle \mathbb {R} ^{m}}$, luego: ^{[1] : 337}

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

3. El espacio métrico es el espacio de funciones con valores reales, con la métrica l-infinito . El número de cobertura${\displaystyle N_{r}^{\text{int}}(K)}$es el número más pequeño ${\displaystyle k}$ tal que, existen ${\displaystyle h_{1},\ldots ,h_{k}\in K}$tal que, para todos ${\displaystyle h\in K}$ existe ${\displaystyle i\in \{1,\ldots ,k\}}$tal que la distancia suprema entre ${\displaystyle h}$ y ${\displaystyle h_{i}}$es como máximo ${\displaystyle r}$. El límite anterior no es relevante ya que el espacio es${\displaystyle \infty }$-dimensional. Sin embargo cuando${\displaystyle K}$es un conjunto compacto , cada cubierta tiene una subcapa finita, por lo que${\displaystyle N_{r}^{\text{int}}(K)}$es finito. ^{[2] : 61}

Propiedades

1. Los números de recubrimiento interno y externo, el número de empaque y la entropía métrica están estrechamente relacionados. La siguiente cadena de desigualdades es válida 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 recubrimiento interna es no creciente en r y no decreciente en K . El número de recubrimiento interior es monótona en r pero no necesariamente en K .

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

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

4. Si todos los vectores en ${\displaystyle K}$ se multiplican por un escalar ${\displaystyle k\in \mathbb {R} }$, luego:

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 ${\displaystyle K}$son operados por una función de Lipschitz ${\displaystyle \phi }$con constante de Lipschitz ${\displaystyle k}$, luego:

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

Dejar ${\displaystyle K}$ser un espacio de funciones con valores reales, con la métrica l-infinito (ver ejemplo 3 arriba). Suponga que todas las funciones en${\displaystyle K}$ están delimitados por una constante real ${\displaystyle M}$. Entonces, el número de cobertura se puede usar para limitar el error de generalización de las funciones de aprendizaje de${\displaystyle K}$, relativo a la pérdida al cuadrado: ^{[2] : 61}

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

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

Ver también

• Revestimiento poligonal
• Número de besos

Referencias

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