¿Qué significa cuando decimos que la mayoría de los puntos en un hipercubo están en el límite?

Si tengo un hipercubo de 50 dimensiones. Y defino su límite por o donde es la dimensión del hipercubo. Luego, calcular la proporción de puntos en el límite del hipercubo será . Qué significa eso? ¿Significa que el resto del espacio está vacío? Si el de los puntos están en el límite, entonces los puntos dentro del cubo no deben distribuirse uniformemente. $0<x_j<0.05$ $0.95<x_j<1$ $x_j$ $0.995$ $99\%$

machine-learning math Rohit Kumar Singh
fuente

No, significa que la periferia es más espaciosa y el efecto es proporcional a la dimensionalidad. Es algo contradictorio. Este fenómeno tiene consecuencias en la distribución de la distancia entre pares aleatorios de nodos que se vuelven relevantes cuando se quiere agrupar o calcular vecinos más cercanos en espacios de alta dimensión.

Emre

Calcule qué proporción de los puntos en un segmento de línea están cerca de su límite. Luego señala en un cuadrado. Luego señala en un cubo. ¿Qué puedes decir de ellos?

user253751

Respuestas:

Hablar de de los puntos en un hipercubo ' es un poco engañoso ya que un hipercubo contiene infinitos puntos. Hablemos de volumen en su lugar. $99\%$

El volumen de un hipercubo es el producto de sus longitudes laterales. Para el hipercubo de la unidad de 50 dimensiones, obtenemos

Total volume = \underset{50 times}{\underset{⏟}{1 \times 1 \times \dots \times 1}} = 1^{50} = 1.

$\text{Total volume} = \underbrace{1 \times 1 \times \dots \times 1}_{50 \text{ times}} = 1^{50} = 1.$

Ahora, excluyamos los límites del hipercubo y observemos el ' interior ' (pongo esto entre comillas porque el término matemático interior tiene un significado muy diferente). Solo conservamos los puntos que satisfacen ¿Cuál es el volumen de este ' interior '? Bueno, el ' interior ' es nuevamente un hipercubo, y la longitud de cada lado es ( ... ayuda a imaginar esto en dos y tres dimensiones). Entonces el volumen es $x = (x_1, x_2, \dots, x_{50})$

0.05 < x_{1} < 0.95 and 0.05 < x_{2} < 0.95 and \dots and 0.05 < x_{50} < 0.95.

$0.05 < x_1 < 0.95 \,\text{ and }\, 0.05 < x_2 < 0.95 \,\text{ and }\, \dots \,\text{ and }\, 0.05 < x_{50} < 0.95.$

0.9

$0.9$

= 0.95 - 0.05

$=0.95 - 0.05$

Interior volume = \underset{50 times}{\underset{⏟}{0.9 \times 0.9 \times \dots \times 0.9}} = {0.9}^{50} \approx 0.005.

$\text{Interior volume} = \underbrace{0.9 \times 0.9 \times \dots \times 0.9}_{50 \text{ times}} = 0.9^{50} \approx 0.005.$ Concluya que el volumen del ' límite ' (definido como la unidad de hipercubo sin el ' interior ') es

1 - {0.9}^{50} \approx 0.995.

$1 - 0.9^{50} \approx 0.995.$

Esto muestra que el del volumen de un hipercubo de 50 dimensiones se concentra en su " límite ". $99.5\%$

Seguimiento: Ignacio planteó una pregunta interesante sobre cómo se relaciona esto con la probabilidad. Aquí hay un ejemplo.

Supongamos que se le ocurrió un modelo (de aprendizaje automático) que predice los precios de la vivienda en base a 50 parámetros de entrada. Los 50 parámetros de entrada son independientes y están distribuidos uniformemente entre y . $0$ $1$

Digamos que su modelo funciona muy bien si ninguno de los parámetros de entrada es extremo: siempre que cada parámetro de entrada permanezca entre y , su modelo predice el precio de la vivienda casi a la perfección. Pero si uno o más parámetros de entrada son extremos (menores que o mayores que ), las predicciones de su modelo son absolutamente terribles. $0.05$ $0.95$ $0.05$ $0.95$

Cualquier parámetro de entrada dado es extremo con una probabilidad de solo . Claramente, este es un buen modelo, ¿verdad? ¡No! La probabilidad de que al menos uno de los parámetros sea extremo es Entonces, en el de los casos, la predicción de su modelo es terrible. $10\%$ $50$ $1 - 0.9^{50} \approx 0.995.$ $99.5\%$

Regla de oro: en altas dimensiones, las observaciones extremas son la regla y no la excepción.

Elias Strehle
fuente

Vale la pena usar la cita del OP "¿Significa que el resto del espacio está vacío?" y respondiendo: No, significa que el resto del espacio es relativamente pequeño . . . O similar en tus propias palabras. . .

Neil Slater

Muy buena explicación del término "maldición de la dimensionalidad"

ignatius

Preguntándose si lo siguiente es correcto: tomando este ejemplo, si un conjunto de características se distribuye uniformemente a lo largo de [0,1] en cada una de las 50 dimensiones, el (99.5% -0.5%) = 99% del volumen (característica de hipercubo espacio) captura solo los valores del 10% de cada característica

ignatius

"Cualquier parámetro de entrada dado es extremo con una probabilidad de solo 5%". Creo que esta probabilidad es del 10%.

Rodvi

@Rodvi: Tienes razón, por supuesto, ¡gracias! Arreglado.

Elias Strehle

Puede ver el patrón claramente incluso en dimensiones más bajas.

1ra dimensión. Tome una línea de longitud 10 y un límite de 1. La longitud del límite es 2 y la relación interior 8, 1: 4.

2da dimensión. Tome un cuadrado del lado 10 y el límite 1 nuevamente. El área del límite es 36, el interior 64, relación 9:16.

3ra dimensión. Misma longitud y límite. El volumen del límite es 488, el interior es 512, 61:64, ya que el límite ocupa casi tanto espacio como el interior.

4ta dimensión, ahora el límite es 5904 y el interior 4096: el límite ahora es más grande.

Incluso para longitudes de límite cada vez más pequeñas, a medida que la dimensión aumenta, el volumen del límite siempre superará al interior.

HP Williams
fuente

La mejor manera de "entenderlo" (aunque en mi humilde opinión es imposible para un humano) es comparar los volúmenes de una bola n-dimensional y un cubo n-dimensional. Con el crecimiento de n (dimensionalidad), todo el volumen de la pelota "se escapa" y se concentra en las esquinas del cubo. Este es un principio general útil para recordar en la teoría de la codificación y sus aplicaciones.

La mejor explicación del libro de texto se encuentra en el libro de Richard W. Hamming "Teoría de la codificación y la información" (3.6 Enfoque geométrico, p. 44).

El breve artículo en Wikipedia le dará un breve resumen del mismo si tiene en cuenta que el volumen de un cubo de unidad n-dimensional es siempre 1 ^ n.

Espero que sea de ayuda.

Alex Fedotov
fuente