Explique a un niño "Maldición de dimensionalidad"

92

Escuché muchas veces sobre la maldición de la dimensionalidad, pero de alguna manera todavía no puedo entender la idea, todo está nublado.

¿Alguien puede explicar esto de la manera más intuitiva, como se lo explicaría a un niño, para que yo (y los demás confundidos como estoy) pudiéramos entender esto definitivamente?


EDITAR:

Ahora, digamos que el niño de alguna manera escuchó sobre la agrupación (por ejemplo, sabe cómo agrupar sus juguetes :)). ¿Cómo haría el aumento de la dimensionalidad dificultar el trabajo de agrupar sus juguetes?

Por ejemplo, solían considerar solo la forma del juguete y el color del juguete (juguetes de un solo color), pero ahora también deben considerar el tamaño y el peso de los juguetes. ¿Por qué es más difícil para el niño encontrar juguetes similares?


EDITAR 2

En aras de la discusión, necesito aclarar que: "¿Por qué es más difícil para el niño encontrar juguetes similares"? También quiero decir ¿por qué se pierde la noción de distancia en espacios de alta dimensión?

Marko
fuente
44
Buena pregunta. Y realmente estás sacando al niño en cada estadístico aquí: D Me hiciste usar un emoticón en el intercambio de pila también :)
Dawny33
2
Relacionado, pero no un duplicado: stats.stackexchange.com/questions/99171/…
Reinstale a Monica el
66
¿"Maldición de dimensionalidad para un niño"? No antes de acostarse.
ttnphns

Respuestas:

78

Probablemente al niño le gustará comer galletas, así que supongamos que tiene un camión completo con galletas que tienen un color diferente, una forma diferente, un sabor diferente, un precio diferente ...

Si el niño tiene que elegir pero solo tiene en cuenta una característica, por ejemplo, el sabor, entonces tiene cuatro posibilidades: dulce, salado, agrio, amargo, por lo que el niño solo tiene que probar cuatro galletas para encontrar lo que más le gusta.

Si al niño le gustan las combinaciones de sabor y color, y hay 4 (soy bastante optimista aquí :-)) diferentes colores, entonces ya tiene que elegir entre 4x4 diferentes tipos;

Si quiere, además, tener en cuenta la forma de las cookies y hay 5 formas diferentes, entonces deberá probar 4x4x5 = 80 cookies

Podríamos continuar, pero después de comer todas estas galletas, es posible que ya tenga dolor de barriga ... antes de que pueda tomar su mejor decisión :-) Además del dolor de barriga, puede ser muy difícil recordar las diferencias en el sabor. de cada galleta

Como puede ver (@Almo), la mayoría (¿todas?) De las cosas se vuelven más complicadas a medida que aumenta el número de dimensiones, esto se aplica a los adultos, a las computadoras y también a los niños.


fuente
Si esto explica el concepto correcto (realmente no sé si lo hace), entonces me gusta esta respuesta porque estoy bastante seguro de que un niño podría entenderlo.
Almo
14
Me gusta tu respuesta, pero siento que está a medio camino. Me gustaría ver una respuesta que aborde cómo las distancias se vuelven cada vez menos significativas a medida que aumenta el número de dimensiones.
TrynnaDoStat
1
@ TrynnaDoStat: bueno, respondí la pregunta, ¿no pedía distancias? ¿Creo que ninguna de las respuestas publicadas hasta ahora habla de distancias? ¿Tengo mucha curiosidad si te pregunto por qué solo me lo preguntas a mí?
3
@fcoppens Porque tu respuesta es la que más me gusta =)
TrynnaDoStat
Entonces, si tiene más dimensiones, entonces también necesita más datos, lo que podría no ser posible.
Anton Andreev
53

La analogía que me gusta usar para la maldición de la dimensionalidad es un poco más geométrica, pero espero que sea lo suficientemente útil para tu hijo.

Es fácil cazar un perro y tal vez atraparlo si estuviera corriendo por la llanura (dos dimensiones). Es mucho más difícil cazar pájaros, que ahora tienen una dimensión extra en la que pueden moverse. Si pretendemos que los fantasmas son seres de dimensiones superiores (como la Esfera que interactúa con A. Square en Flatland ), son aún más difíciles de atrapar. :)

JM está de vuelta.
fuente
55
¡Oh, esta es buena! Incluso iría en dirección 1D ... ¿Tal vez una oruga moviéndose en un tubo?
Greg
2
Buen punto ... ¿Entonces quizás una rama de árbol muy delgada, con una oruga? De alguna manera se aproxima a una dimensión. Naturalmente, los pájaros los cazan, ¿tal vez un cuervo cerca?
Greg
1
Oh! La manipulación de la gravedad no sería suficiente si los cuervos aprendieran una táctica (¡son muy inteligentes!): Cazan en parejas, cuando uno se acerca desde abajo y el otro desde arriba. Saben que si el error usa la superpotencia, pesaría las probabilidades a favor de uno de esos cuervos. Hmmm ... Entonces, ¿qué pasa con un error con dos superpoderes: la manipulación de la gravedad y la compresión del tiempo? ¿No contaría eso como un error terriblemente difícil de cazar en 5 dimensiones?
Greg
1
Atrapar a 2 perros corriendo puede verse como una cacería en 4d, 10 perros en 20d, 10 golondrinas en 30d ...
denis
1
@Greg, "atrapar" realmente no tiene nada que ver con la dimensión, simplemente corren de forma independiente (algunas también de manera independiente)
Denis
19

Ok, entonces analicemos el ejemplo del niño que agrupa sus juguetes.
Imagine que el niño solo tiene 3 juguetes:

  1. un balón de fútbol azul
  2. un freesbe azul
  3. un cubo verde (bueno, tal vez no sea el juguete más divertido que puedas imaginar)

Hagamos la siguiente hipótesis inicial sobre cómo se puede hacer un juguete:

  1. Los colores posibles son: rojo, verde, azul.
  2. Las formas posibles son: círculo, cuadrado, triángulo

Ahora podemos tener (num_colors * num_shapes) = 3 * 3 = 9 grupos posibles.

El niño agruparía los juguetes de la siguiente manera:

  • El GRUPO A) contiene la bola azul y el azul libre, porque tienen el mismo color y forma
  • GRUPO B) contiene el cubo verde súper divertido

Usando solo estas 2 dimensiones (color, forma) tenemos 2 grupos no vacíos: en este primer caso, 7/9 ~ 77% de nuestro espacio está vacío.

Ahora aumentemos el número de dimensiones que el niño debe tener en cuenta. También hacemos la siguiente hipótesis sobre cómo se puede hacer un juguete:

  1. El tamaño del juguete puede variar entre unos pocos centímetros y un metro, en pasos de diez centímetros: 0-10 cm, 11-20 cm, ..., 91 cm-1 m
  2. El peso del juguete puede variar de manera similar hasta 1 kilogramo, con pasos de 100 gramos: 0-100g, 101-200g, ..., 901g-1kg.

Si queremos agrupar nuestros juguetes AHORA, tenemos (num_colors * num_shapes * num_sizes * num_weights) = 3 * 3 * 10 * 10 = 900 grupos posibles.

El niño agruparía los juguetes de la siguiente manera:

  • GRUPO A) contiene el balón de fútbol azul porque es azul y pesado
  • GRUPO B) contiene el azul libre porque es azul y claro
  • CLUSTER C) contiene el cubo verde súper divertido

Usando las 4 dimensiones actuales (forma, color, tamaño, peso) solo 3 grupos no están vacíos: en este caso, 897/900 ~ 99.7% del espacio está vacío.

Este es un ejemplo de lo que encuentra en Wikipedia ( https://en.wikipedia.org/wiki/Curse_of_dimensionality ):
... cuando la dimensionalidad aumenta, el volumen del espacio aumenta tan rápido que los datos disponibles se vuelven escasos.


Editar: no estoy seguro de poder explicarle a un niño por qué la distancia a veces va mal en espacios de alta dimensión, pero tratemos de continuar con nuestro ejemplo del niño y sus juguetes.

Considere solo las 2 primeras características {color, forma}, todos están de acuerdo en que la bola azul es más similar al azul libre que al cubo verde.

Ahora agreguemos otras 98 características {digamos: tamaño, peso, día_de_producción_del_juguete, material, suavidad, día_en_que_el_todo_fue_comprado_por_daddy, precio, etc.}: bueno, para mí sería cada vez más difícil juzgar qué juguete es similar a cuál.

Entonces:

  1. Una gran cantidad de características pueden ser irrelevantes en una cierta comparación de similitud, lo que lleva a una corrupción de la relación señal / ruido.
  2. En grandes dimensiones, todos los ejemplos son "parecidos".

Si me escuchas, una buena conferencia es "Algunas cosas útiles que debes saber sobre el aprendizaje automático" ( http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf ), el párrafo 6 en particular presenta esto tipo de razonamiento

¡Espero que esto ayude!

ndrplz
fuente
Me gusta mucho tu explicación, gracias. Ahora entiendo mucho mejor la escasez del espacio, pero ¿podría "ilustrar" la parte de por qué es difícil para el niño encontrar qué juguetes son más similares en caso de tener más dimensiones? Corrígeme si me equivoco, pero entiendo que la noción de distancia se corrompe en tales espacios, por lo que es más difícil determinar qué juguetes son más similares. ¿Porqué es eso?
Marko
Este argumento parece confundir tamaño con dimensionalidad. La división de longitudes y pesos en diez contenedores es arbitraria. Si bien la introducción de estos dos nuevos factores agrega solo dos dimensiones a la configuración, el binning infla su estimación del "tamaño" del "espacio". Sin embargo, sin cambiar la situación en absoluto, podría haber agrupado el tamaño y el peso en contenedores y concluir que esencialmente todo el espacio está "vacío". 10100
whuber
@whuber: tienes razón, para que sea demasiado simple, usé las palabras equivocadas
ndrplz
@whuber: pero dimensión se considera a menudo como una medida de (algún concepto de) "tamaño"
kjetil b Halvorsen
@Kjetil es un punto interesante que bien podría valer la pena explorar. Pero, ¿no le parece importante aclarar el sentido en que una dimensión es un "tamaño" y distinguirla de otros significados de "tamaño" en un entorno estadístico?
whuber
14

Me he encontrado con el siguiente enlace que proporciona una explicación muy intuitiva (y detallada) de la maldición de la dimensionalidad: http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/

En este artículo, discutiremos la llamada 'Maldición de la dimensionalidad' y explicaremos por qué es importante al diseñar un clasificador. En las siguientes secciones proporcionaré una explicación intuitiva de este concepto, ilustrada por un claro ejemplo de sobreajuste debido a la maldición de la dimensionalidad.

En pocas palabras, este artículo deriva (intuitivamente) que agregar más funciones (es decir, aumentar la dimensionalidad de nuestro espacio de funciones) requiere recopilar más datos. De hecho, la cantidad de datos que necesitamos recopilar (para evitar el sobreajuste) crece exponencialmente a medida que agregamos más dimensiones.

También tiene bonitas ilustraciones como la siguiente:

ingrese la descripción de la imagen aquí

kostas
fuente
+1, ¡el enlace es muy bueno! He editado una cita y una imagen de ejemplo, pero si además puede proporcionar un breve resumen de lo que se explica allí, sería aún mejor.
ameba
1
Gracias por la sugerencia. He editado la respuesta en consecuencia.
kostas
8

La maldición de la dimensionalidad es algo difusa en la definición, ya que describe cosas diferentes pero relacionadas en diferentes disciplinas. Lo siguiente ilustra la maldición de dimensionalidad del aprendizaje automático:

Supongamos que una niña tiene diez juguetes, de los cuales solo le gustan los que están en cursiva:

  • un oso de peluche marrón
  • un auto azul
  • un tren rojo
  • una excavadora amarilla
  • un libro verde
  • una morsa de felpa gris
  • un carro negro
  • una bola rosa
  • un libro blanco
  • una muñeca naranja

Ahora, su padre quiere darle un juguete nuevo como regalo para su cumpleaños y quiere asegurarse de que le guste. Él piensa mucho en lo que los juguetes que le gustan tienen en común y finalmente llega a una solución. Él le da a su hija un rompecabezas de todos los colores. Cuando a ella no le gusta, él responde: “¿Por qué no te gusta? Contiene la letra w. "

El padre ha sido víctima de la maldición de la dimensionalidad (y la optimización en la muestra). Al considerar las letras, se movía en un espacio de 26 dimensiones y, por lo tanto, era muy probable que encontrara algún criterio para separar los juguetes que le gustaban a la hija. Esto no necesitaba ser un criterio de una sola letra como en el ejemplo, pero también podría haber sido algo así como

contiene al menos uno de a, n y p pero ninguno de u, f y s.

Para determinar adecuadamente si las letras son un buen criterio para determinar qué juguetes le gustan a su hija, el padre tendría que conocer las preferencias de su hija en una cantidad gigantesca de juguetes¹, o simplemente usar su cerebro y solo considerar los parámetros que realmente pueden concebir que afecten a la hija. opinión.


226

Wrzlprmft
fuente
1
+1 Muy claro, gracias. Esta debería ser la respuesta aceptada.
MiniQuark
7
  • Piense en un círculo encerrado en la unidad cuadrada.
  • Piense en una esfera encerrada en el cubo de la unidad.
  • Piense en una hiperesfera n-dimensional encerrada en el hipercubo de la unidad n-dimensional.

1n

π/4π/6

Aksakal
fuente
5

Yo: "Estoy pensando en un pequeño animal marrón que comienza con 'S'. ¿Qué es?"

Ella: "¡Ardilla!"

Yo: "OK, uno más difícil. Estoy pensando en un pequeño animal marrón. ¿Qué es?"

Ella: "¿Todavía una ardilla?"

Yo no"

Ella: "¿Rata, ratón, campañol?

Yo: "No"

Ella: "Umm ... dame una pista"

Yo: "No, pero haré algo mejor: te dejaré responder a una pregunta validada cruzada"

Ella: [gemidos]

Yo: "La pregunta es: ¿cuál es la maldición de la dimensionalidad? Y ya sabes la respuesta"

Ella: "¿Sí?"

Yo: "Sí. ¿Por qué fue más difícil adivinar el primer animal que el segundo?"

Ella: "¿Porque hay más pequeños animales marrones que pequeños animales marrones que comienzan con 'S'?"

Yo: "Correcto. Y esa es la maldición de la dimensionalidad. Juguemos de nuevo".

Ella: "OK"

Yo: "Estoy pensando en algo. ¿Qué es?"

Ella: "No es justo. Este juego es muy difícil".

Yo: "Cierto. Es por eso que lo llaman una maldición. Simplemente no puedes hacerlo bien sin saber las cosas en las que tiendo a pensar".

conjugadoprior
fuente
4

Supongamos que desea enviar algunos productos. Desea desperdiciar la menor cantidad de espacio posible al empacar los productos (es decir, dejar la menor cantidad de espacio vacío posible), porque los costos de envío están relacionados con el volumen del sobre / caja. Los contenedores a su disposición (sobres, cajas) tienen ángulos rectos, por lo que no hay sacos, etc.

Primer problema: envíe un bolígrafo (una "línea"): puede construir una caja a su alrededor sin perder espacio.

Segundo problema: envíe un CD (una "esfera"). Necesitas ponerlo en un sobre cuadrado. Dependiendo de la edad del niño, es posible que pueda calcular cuánto del sobre permanecerá vacío (y aún así saber que hay CD y no solo descargas ;-)).

Tercer problema: envía una pelota de fútbol (¡fútbol, ​​y tiene que estar inflado!). Deberá colocarlo en una caja y quedará algo de espacio vacío. Ese espacio vacío será una fracción mayor del volumen total que en el ejemplo de CD.

En ese momento, mi intuición al usar esta analogía se detiene, porque no puedo imaginar una cuarta dimensión.

EDITAR: La analogía es más útil (si es que lo hace) para la estimación no paramétrica, que utiliza observaciones "locales" al punto de interés para estimar, por ejemplo, una densidad o una función de regresión en ese punto. La maldición de la dimensionalidad es que en dimensiones más altas, uno necesita un vecindario mucho más grande para un número dado de observaciones (lo que hace que la noción de localidad sea cuestionable) o una gran cantidad de datos.

Christoph Hanck
fuente
Ok, gracias por la explicación. Entonces, básicamente, es más difícil "llenar" todo el espacio, ¿por eso necesita una muestra mucho más grande? Necesito hacer mi pregunta un poco más específica :) Lo editaré, por favor revise la otra parte también.
Marko
Sí, vea mi edición, tendrá que pensar en la agrupación
Christoph Hanck
3
nn
@whuber Aquí es donde entra la maldición en el ejemplo de serie temporal. Digamos que nuestra serie de tiempo es una caminata aleatoria sobre una cierta cantidad de tiempo (discreto), y en cada etapa el caminante mueve una cantidad aleatoria (iid ~ uniforme (-1, 1)). Estás haciendo un seguimiento de una mosca en una línea, por ejemplo. Ahora sus reacciones / vista son tan buenas, y para mantener sus ojos sobre la marcha sin tener que moverse alrededor de la línea, necesita que se mueva como máximo 0.5 unidades en cualquier dirección. Por supuesto, si espera lo suficiente, la mosca saltará esta cantidad y la perderá. Pero, por un período fijo de tiempo, cuántos caminos (cont.)
Julien Clancy
te hará perder la noción de la mosca? La maldición de la dimensionalidad dice: prácticamente todas, a medida que dejas que el tiempo se agrande. Y puede hacer que su vista sea tan fina como desee (es decir, puede detectar movimientos casi 1 en cualquier dirección) y sucede lo mismo.
Julien Clancy
1

Mis 6 años están más en el verso de la investigación de la causa principal, como en "¿pero de dónde viene todo este gas en el universo?" ... bueno, me imagino que su hijo entiende "dimensiones superiores", lo que parece muy improbable para mí

n[0,1]n[12,12]n

(12)n2n

Ahora ve a recoger tu habitación, papá tiene que trabajar.

2n12

Elvis
fuente
1
Uh, sí, esto es lo mismo que la respuesta de cookie de f coppens, pero menos creativa. Pero puede ayudar a los que no son niños a verlo así ...
Elvis
0

Hay un clásico problema de matemática de libros de texto que muestra esto.

¿Preferiría ganar (opción 1) 100 centavos al día, todos los días durante un mes, o (opción 2) un centavo duplicado todos los días durante un mes? Puede hacerle esta pregunta a su hijo.

Si eliges la opción 1,
en el día 1 obtienes 100 centavos en el día 2 obtienes 100 centavos en el día 3 obtienes 100 centavos ... en el día 30 obtienes 100 centavos

nth

el número total de centavos se calcula multiplicando el número de días por el número de centavos por día:

i=130100=30100=3000

Si elige la opción 2:
en el día 1 obtiene 1 centavo en el día 2 obtiene 2 centavos en el día 3 obtiene 4 centavos en el día 4 obtiene 8 centavos en el día 5 obtiene 16 centavos ... en el día 30 obtiene 1,073,741,824 centavos

nth2n

i=1302n=(231)1=21474836481=2147483647

Cualquiera con avaricia elegirá el número más grande. La codicia simple es fácil de encontrar y requiere poco pensamiento. Los animales que no hablan son fácilmente capaces de codicia: los insectos son muy buenos en eso. Los humanos son capaces de mucho más.

Si comienzas con un centavo en lugar de cien, la codicia es más fácil, pero si cambias la potencia de un polinomio es más complejo. Complejo también puede significar mucho más valioso.

Acerca de "la maldición"
La operación matemática "más importante" relacionada con la física es la inversión matricial. Impulsa soluciones de sistemas de ecuaciones diferenciales parciales, las más comunes son las ecuaciones de Maxwell (electromagnética), las ecuaciones de Navier Stokes (fluidos), la ecuación de Poisson (transferencia difusiva) y las variaciones en la Ley de Hookes (sólidos deformables). Cada una de estas ecuaciones tiene cursos universitarios construidos alrededor de ellos.

n3

La maldición existe porque si se supera hay una olla de valor dorado al final del arco iris. No es fácil: las grandes mentes han abordado el problema enérgicamente.

enlazar:

Estudiante
fuente
1
Su ejemplo parece estar más relacionado con mostrar la diferencia entre el crecimiento polinómico y exponencial, en oposición a la maldición de la dimensionalidad.
JM no es un estadístico
El crecimiento polinómico y exponencial son la maldición. Si fuera lineal, el cifrado no funcionaría, y la fusión en una botella sería fácil de simular. Aquí hay una enumeración de la "maldición" (hipervínculo de Wikipedia), sin la cual las matemáticas de la computadora de repente se volverían mucho más sorprendentes de lo que ya son. en.wikipedia.org/wiki/…
EngrStudent
Es una tradición urbana que en 2008 descubrió un gran avance en la inversión matricial que cae por debajo del orden 2, pero se clasificó y se utiliza para simulaciones de armas nucleares o algo así.
EngrStudent
1
Estaba casi convencido hasta que "se usaba para simulaciones de armas nucleares o algo así". ; P Pero en serio, Coppersmith-Winograd parece ser el mejor, aunque con una constante implícita que solo lo hace útil para matrices realmente grandes.
JM no es un estadístico
Relacionado tangencialmente con su respuesta y comentario anterior: calcular el determinante de manera eficiente no es demasiado difícil, pero calcular el permanente es una cuestión diferente.
JM no es un estadístico
0

Fcop ofreció una gran analogía con las cookies, pero solo ha cubierto el aspecto de la densidad de muestreo de la maldición de la dimensionalidad. Podemos extender esta analogía al volumen de muestreo o la distancia distribuyendo la misma cantidad de cookies de Fcop en, por ejemplo, diez cajas en una línea, 10x10 cajas planas en la mesa y 10x10x10 en una pila. Luego puede demostrar que para comer la misma porción de galletas, el niño tendrá que abrir cada vez más cajas.

Realmente se trata de las expectativas, pero tomemos un enfoque del "peor de los casos" para ilustrar.

Si hay 8 galletas y queremos comer la mitad, es decir, 4, de 10 cajas en el peor de los casos, solo tenemos que abrir 6 cajas. Eso es 60%, casi la mitad también. De 10x10 (nuevamente en el peor de los casos) - 96 (%). Y de 10x10x10 - 996 (99,6%). ¡Eso es casi todos!

Puede ser la analogía de la sala de almacenamiento y la distancia recorrida entre las habitaciones sería mejor que las cajas aquí.

Diego
fuente
Buena extensión :-)