¿Comprende la ilustración de la maldición de la dimensionalidad?

Question

Entiendo cómo funciona la maldición de la alta dimensionalidad cuando la mayoría de las características son irrelevantes en este artículo tan citado: Algunas cosas útiles que hay que saber sobre el aprendizaje automático pero me atasco al leer la siguiente ilustración:

Este se debe a que en dimensiones altas todos ejemplos se parecen. Supongamos, por ejemplo, que los ejemplos se disponen en una cuadrícula regular, y consideremos una prueba ejemplo $x_t$ . Si la cuadrícula es d-dimensional, $x_t$ 's 2d ejemplos más cercanos son están todos a la misma distancia de él. Por tanto aumenta la dimensionalidad, más ejemplos se convierten en vecinos más cercanos de $x_t$ hasta la elección de vecino más próximo (y, por tanto, de clase) sea efectivamente aleatoria

La primera frase es poco intuitivo . Sobre todo, ¿por qué Si la cuadrícula es d-dimensional, $x_t$ 's 2d ejemplos más cercanos son todos a la misma distancia de él ?

Para concretar, hay dos coordenadas(A y B) en un plano 2d:

Utilizando geogebra

Supongamos que (0, 0) es el ejemplo de prueba, y podemos ver que A está más cerca de él que B. Me pregunto si B estaría tan cerca del ejemplo de prueba como A en cualquier espacio de dimensión superior. Si es así, ¿cómo? Si no, ¿cómo todos ¿las muestras se parecen?

Answer 1

Veamos las primeras dimensiones.

• Para $d=1$ , si los ejemplos están dispuestos en una cuadrícula regular, esto sólo significa que están a distancias iguales en una línea recta, por ejemplo, en los números enteros. Podemos suponer que nuestro ejemplo de prueba $x_t$ está en el origen, $x_t=0$ . Hay dos vecinos más cercanos con la misma distancia $1$ es decir, los puntos en $1$ y $-1$ .

• Para $d=2$ tenemos un plano, y la cuadrícula regular podría estar formada por todos los puntos enteros bidimensionales. Para un ejemplo de prueba de nuevo (sin pérdida de generalidad) en el origen, hay cuatro vecinos más cercanos, de nuevo todos con distancia $1$ : $(0,1)$ , $(-1,0)$ , $(0,-1)$ y $(1,0)$ .

• Para $d=3$ tenemos una cuadrícula regular en un espacio tridimensional. Nuestro ejemplo de prueba en el origen tiene ahora seis vecinos más cercanos, todos a la distancia $1$ .

En general, puesto que tenemos $d$ dimensiones y podemos suponer que nuestra cuadrícula regular sólo consiste en la $d$ -puntos enteros dimensionales, podemos tomar el ejemplo de prueba en el origen, y luego podemos encontrar todas las $2d$ vecinos más cercanos eligiendo uno de los $d$ dimensiones y estableciendo esa coordenada en $1$ o $-1$ y dejando el resto de coordenadas en $0$ .

El problema que esto ilustra es que si no hay estructura en nuestro problema (es decir, nuestros ejemplos están en una cuadrícula regular, sin conglomerados, quizás con algo de ruido), entonces seleccionar un número fijo $k$ de los vecinos más próximos puede significar simplemente elegirlos al azar, ya que hay muchos vecinos más próximos, que sólo pueden diferenciarse debido al ruido.

Answer 2

Especialmente, ¿por qué Si la cuadrícula es d-dimensional, $x_t$ Los dos ejemplos más cercanos están todos a la misma distancia de él. ? ¿Podría alguien visualizar la ilustración (si es posible)?

El ejemplo habla de un regular rejilla.

En un regular tiene para cada línea de la cuadrícula (en cada dimensión) dos nodos vecinos, uno en +1 y otro en -1.

En el caso de una distribución no regular, los dos vecinos más próximos ya no se encuentran a una distancia exactamente similar y existe cierta aleatoriedad. Pero el ejemplo de la cuadrícula regular muestra que hay muchas direcciones en las que se puede encontrar un vecino más próximo (y esto facilita que el ruido supere a la señal).

Answer 3

Creo que @Stephan Kolassa explica bien lo que querían decir los autores en ese párrafo. La base teórica de que "en dimensiones altas todas las muestras se parecen" se expone en la sección 3.4 Resultado de la inestabilidad de este documento .

Omitiendo la prueba de la página 6, esencialmente

... todos los puntos convergen a la misma distancia del punto de consulta. Por tanto, en estas condiciones, el concepto de vecino más próximo deja de ser útil.

Creo que si los autores citaran este artículo en lugar de utilizar ese ejemplo de cuadrícula, la presentación sería mucho más clara. Los resultados en dimensiones superiores pueden ser poco intuitivos porque vivimos en un mundo tridimensional.

Answer 4

imagina el cubo unitario $[0,1]^d$ . Todos los datos de entrenamiento se muestrean uniformemente dentro de este cubo, es decir. $i,x_i[0,1]^d$ y estamos considerando la $k=10$ vecinos más cercanos de dicho punto de prueba.

Sea la longitud de arista del hipercubo más pequeño que contiene todos los vecinos k más próximos de un punto de prueba. Entonces $^d\frac{k}{n}$ y $(\frac{k}{n})^{1/d}$ . Si n=1000, ¿cuánto mide?

Así que como d0 casi todo el espacio es necesario para encontrar el 10-NN.

Para simular el fenómeno, llevé a cabo el siguiente experimento (implemente el ejemplo de la referencia):

import matplotlib.pyplot as plt
%matplotlib inline
plt.rcParams.update({'figure.figsize':(7,5), 'figure.dpi':100})
import numpy as np
np.random.seed(0) 
from scipy.spatial import distance_matrix
min_val = 0
max_val = 1
n = 1000

for d in (2, 3, 10, 100, 1000, 10000):
    a = np.random.rand(n, d)
    b = np.random.rand(n, d)
    distances = distance_matrix(a, b)
    distances = np.array(distances).flatten()
    plt.hist(distances, bins=100, weights=np.ones(len(distances)) / len(distances))
    # plt.gca().set(title='Frequency Histogram', ylabel='Frequency')
    plt.show() 

Y las tramas coinciden muy bien con las de la referencia.

Referencias:

1. Lección 2: vecinos más próximos a k